Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Diff of /trunk/src/compiler/mid-to-low/mid-to-low.sml
ViewVC logotype

Diff of /trunk/src/compiler/mid-to-low/mid-to-low.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 459, Wed Oct 27 12:54:03 2010 UTC revision 511, Tue Feb 8 17:01:43 2011 UTC
# Line 12  Line 12 
12    
13    end = struct    end = struct
14    
   
15      structure SrcIL = MidIL      structure SrcIL = MidIL
16      structure SrcOp = MidOps      structure SrcOp = MidOps
17      structure VTbl = SrcIL.Var.Tbl      structure VTbl = SrcIL.Var.Tbl
18      structure DstIL = LowIL      structure DstIL = LowIL
19        structure DstTy = LowILTypes
20      structure DstOp = LowOps      structure DstOp = LowOps
21    
22      type var_env = DstIL.var VTbl.hash_table      type var_env = DstIL.var VTbl.hash_table
# Line 24  Line 24 
24      fun rename (env : var_env, x) = (case VTbl.find env x      fun rename (env : var_env, x) = (case VTbl.find env x
25             of SOME x' => x'             of SOME x' => x'
26              | NONE => let              | NONE => let
27                  val x' = DstIL.Var.new (SrcIL.Var.name x)                  val x' = DstIL.Var.new (SrcIL.Var.name x, SrcIL.Var.ty x)
28                  in                  in
29                    VTbl.insert env (x, x');                    VTbl.insert env (x, x');
30                    x'                    x'
# Line 32  Line 32 
32            (* end case *))            (* end case *))
33      fun renameList (env, xs) = List.map (fn x => rename(env, x)) xs      fun renameList (env, xs) = List.map (fn x => rename(env, x)) xs
34    
35    (* expand the EvalKernel operations into vector operations.  The parameters are    (* convert a rational to a FloatLit.float value.  We do this by long division
36       * with a cutoff when we get to 12 digits.
37       *)
38        fun ratToFloat r = (case Rational.explode r
39               of {sign=0, ...} => FloatLit.zero false
40                | {sign, num, denom=1} => FloatLit.fromInt(sign * IntInf.toInt num)
41                | {sign, num, denom} => let
42                  (* normalize so that num <= denom *)
43                    val (denom, exp) = let
44                          fun lp (n, denom) = if (denom < num)
45                                then lp(n+1, denom*10)
46                                else (denom, n)
47                          in
48                            lp (1, denom)
49                          end
50                  (* normalize so that num <= denom < 10*num *)
51                    val (num, exp) = let
52                          fun lp (n, num) = if (10*num < denom)
53                                then lp(n-1, 10*num)
54                                else (num, n)
55                          in
56                            lp (exp, num)
57                          end
58                  (* divide num/denom, computing the resulting digits *)
59                    fun divLp (n, a) = let
60                          val (q, r) = IntInf.divMod(a, denom)
61                          in
62                            if (r = 0) then (q, [])
63                            else if (n < 12) then let
64                              val (d, dd) = divLp(n+1, 10*r)
65                              in
66                                if (d < 10)
67                                  then (q, (IntInf.toInt d)::dd)
68                                  else (q+1, 0::dd)
69                              end
70                            else if (IntInf.div(10*r, denom) < 5)
71                              then (q, [])
72                              else (q+1, []) (* round up *)
73                          end
74                    val digits = let
75                          val (d, dd) = divLp (0, num)
76                          in
77                            (IntInf.toInt d)::dd
78                          end
79                    in
80                      FloatLit.fromDigits{isNeg=(sign < 0), digits=digits, exp=exp}
81                    end
82              (* end case *))
83    
84        fun imul (r, a, b) = (r, DstIL.OP(DstOp.Mul DstTy.intTy, [a, b]))
85        fun iadd (r, a, b) = (r, DstIL.OP(DstOp.Add DstTy.intTy, [a, b]))
86    
87      (* expand the EvalKernel operations into vector operations.  The parameters
88       * are
89     *    result  -- the lhs variable to store the result     *    result  -- the lhs variable to store the result
90     *    d       -- the vector width of the operation, which should be equal to twice the     *    d       -- the vector width of the operation, which should be equal
91     *               support of the kernel     *               to twice the support of the kernel
92     *    h       -- the kernel     *    h       -- the kernel
93     *    k       -- the derivative of the kernel to evaluate     *    k       -- the derivative of the kernel to evaluate
94       *
95       * The generated code is computing
96       *
97       *    result = a_0 + x*(a_1 + x*(a_2 + ... x*a_n) ... )
98       *
99       * as a d-wide vector operation, where n is the degree of the kth derivative
100       * of h and the a_i are coefficient vectors that have an element for each
101       * piece of h.  The computation is implemented as follows
102       *
103       *    m_n     = x * a_n
104       *    s_{n-1} = a_{n-1} + m_n
105       *    m_{n-1} = x * s_{n-1}
106       *    s_{n-2} = a_{n-2} + m_{n-1}
107       *    m_{n-2} = x * s_{n-2}
108       *    ...
109       *    s_1     = a_1 + m_2
110       *    m_1     = x * s_1
111       *    result  = a_0 + m_1
112     *)     *)
113      fun expandKernel (result, d, h, k) = let      fun expandEvalKernel (result, d, h, k, [x]) = let
114            val {isCont, segs} = Kernel.curve (h, k)            val {isCont, segs} = Kernel.curve (h, k)
115            (* degree of polynomial *)
116              val deg = List.length(hd segs) - 1
117            (* convert to a vector of vectors to give fast access *)
118              val segs = Vector.fromList (List.map Vector.fromList segs)
119            (* get the kernel coefficient value for the d'th term of the i'th
120             * segment.
121             *)
122              fun coefficient d i =
123                    Literal.Float(ratToFloat (Vector.sub (Vector.sub(segs, i), d)))
124              val ty = DstTy.VecTy d
125              val coeffs = List.tabulate (deg+1,
126                    fn i => DstIL.Var.new("a"^Int.toString i, ty))
127            (* code to define the coefficient vectors *)
128              val coeffVecs = let
129                    fun mk (x, (i, code)) = let
130                          val lits = List.tabulate(d, coefficient i)
131                          val vars = List.tabulate(d, fn _ => DstIL.Var.new("_f", DstTy.realTy))
132                          val code =
133                                ListPair.map (fn (x, lit) => (x, DstIL.LIT lit)) (vars, lits) @
134                                  (x, DstIL.CONS vars) :: code
135            in            in
136                            (i-1, code)
137                          end
138                    in
139                      #2 (List.foldr mk (deg, []) coeffs)
140                    end
141            (* build the evaluation of the polynomials in reverse order *)
142              fun pTmp i = DstIL.Var.new("prod" ^ Int.toString i, ty)
143              fun sTmp i = DstIL.Var.new("sum" ^ Int.toString i, ty)
144              fun eval (i, [coeff]) = let
145                    val m = pTmp i
146                    in
147                      (m, [(m, DstIL.OP(DstOp.Mul ty, [x, coeff]))])
148                    end
149                | eval (i, coeff::r) = let
150                    val (m, stms) = eval(i+1, r)
151                    val s = sTmp i
152                    val m' = pTmp i
153                    val stms =
154                          (m', DstIL.OP(DstOp.Mul ty, [x, s])) ::
155                          (s, DstIL.OP(DstOp.Add ty, [coeff, m])) ::
156                          stms
157                    in
158                      (m', stms)
159                    end
160              val evalCode = let
161                    val a0::r = coeffs
162                    val (m, stms) = eval (1, r)
163                    in
164                      List.rev ((result, DstIL.OP(DstOp.Add ty, [a0, m]))::stms)
165                    end
166              in
167                coeffVecs @ evalCode
168            end            end
169    
170    (* compute the load address for a given set of voxels indices *)    (* compute the load address for a given set of voxels indices.  For the
171      fun expandVoxelAddress (result, info) = ??     * operation
172       *
173       *    VoxelAddress<info>(i_1, ..., i_d)
174       *
175       * the address is given by
176       *
177       *    base + szb * (i_1 + N_2 * (i_2 + N_3 * (... + N_d * i_d) ...))
178       *
179       * where
180       *    base    -- base address of the image data
181       *    szb     -- image-element size in bytes
182       *    N_i     -- size of ith axis in elements
183       *)
184        fun expandVoxelAddress (result, info, indices) = let
185              val ImageInfo.ImgInfo{ty=(d, rTy), sizes=_::sizes, ...} = info
186            (* generate the address computation code in reverse order *)
187              fun gen (d, [n], [ix]) = let
188                    val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)
189                    val t = DstIL.Var.new ("t", DstTy.intTy)
190                    val code = [
191                            imul(t, n', ix),
192                            (n', DstIL.LIT(Literal.Int(IntInf.fromInt n)))
193                          ]
194                    in
195                      (t, code)
196                    end
197                | gen (d, n::ns, ix::ixs) = let
198                    val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)
199                    val t1 = DstIL.Var.new ("t1", DstTy.intTy)
200                    val t2 = DstIL.Var.new ("t2", DstTy.intTy)
201                    val (t, code) = gen (d+1, ns, ixs)
202                    val code =
203                          imul(t2, n', t1) ::
204                          (n', DstIL.LIT(Literal.Int(IntInf.fromInt n))) ::
205                          iadd(t1, ix, t) :: code
206                    in
207                      (t2, code)
208                    end
209              val voxSzb = List.foldl Int.* (RawTypes.sizeb rTy) d
210              val (offset, code) = gen (0, voxSzb :: sizes, indices)
211              val base = DstIL.Var.new ("imgBaseAddr", DstTy.AddrTy)
212              val code = (result, DstIL.OP(DstOp.Add DstTy.AddrTy, [base, offset])) ::
213                    (base, DstIL.OP(DstOp.ImageAddress info, [])) ::
214                    code
215              in
216                List.rev code
217              end
218    
219      fun expandOp (env, y, rator, args) = let      fun expandOp (env, y, rator, args) = let
220            fun assign rator' =            val args' = renameList(env, args)
221                  [(y, DstIL.OP(rator', renameList(env, args)))]            fun assign rator' = [(y, DstIL.OP(rator', args'))]
222            in            in
223              case rator              case rator
224               of SrcOp.Add ty => assign (DstOp.Add ty)               of SrcOp.Add ty => assign (DstOp.Add ty)
# Line 71  Line 240 
240                | SrcOp.Pow => assign (DstOp.Pow)                | SrcOp.Pow => assign (DstOp.Pow)
241                | SrcOp.Dot d => assign (DstOp.Dot d)                | SrcOp.Dot d => assign (DstOp.Dot d)
242                | SrcOp.Cross => assign (DstOp.Cross)                | SrcOp.Cross => assign (DstOp.Cross)
243                | SrcOp.Select ty => assign (DstOp.Select ty) * int                | SrcOp.Select(ty, i)=> assign (DstOp.Select(ty, i))
244                | SrcOp.Norm d => assign (DstOp.Norm d)                | SrcOp.Norm d => assign (DstOp.Norm d)
245                | SrcOp.Scale d => assign (DstOp.Scale d)                | SrcOp.Scale d => assign (DstOp.Scale d)
246                | SrcOp.InvScale d => assign (DstOp.InvScale d)                | SrcOp.InvScale d => assign (DstOp.InvScale d)
# Line 84  Line 253 
253                | SrcOp.RoundToInt d => assign (DstOp.RoundToInt d)                | SrcOp.RoundToInt d => assign (DstOp.RoundToInt d)
254                | SrcOp.CeilToInt d => assign (DstOp.CeilToInt d)                | SrcOp.CeilToInt d => assign (DstOp.CeilToInt d)
255                | SrcOp.FloorToInt d => assign (DstOp.FloorToInt d)                | SrcOp.FloorToInt d => assign (DstOp.FloorToInt d)
256                | SrcOp.VoxelAddress info => expandVoxelAddress (y, info)                | SrcOp.VoxelAddress info => expandVoxelAddress (y, info, args')
257                | SrcOp.LoadVoxels(rty, d) => assign (DstOp.LoadVoxels(rty, d))                | SrcOp.LoadVoxels(rty, d) => assign (DstOp.LoadVoxels(rty, d))
258                | SrcOp.Transform info => assign (DstOp.Transform info)                | SrcOp.PosToImgSpace info => assign (DstOp.PosToImgSpace info)
259                | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k)                | SrcOp.GradToWorldSpace info => assign (DstOp.GradToWorldSpace info)
260                  | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k, args')
261                | SrcOp.LoadImage info => assign (DstOp.LoadImage info)                | SrcOp.LoadImage info => assign (DstOp.LoadImage info)
262                | SrcOp.Inside info => assign (DstOp.Inside info)                | SrcOp.Inside info => assign (DstOp.Inside info)
263                | SrcOp.Input(ty, name) => assign (DstOp.Input(ty, name))                | SrcOp.Input(ty, name) => assign (DstOp.Input(ty, name))
264                | SrcOp.InputWithDefault(ty, name) => assign (DstOp.InputWithDefault(ty, name))                | SrcOp.InputWithDefault(ty, name) => assign (DstOp.InputWithDefault(ty, name))
               | _ => raise Fail("unexpected " ^ SrcOp.toString rator)  
265              (* end case *)              (* end case *)
266            end            end
267    
# Line 120  Line 289 
289          val expand = expand          val expand = expand
290        end)        end)
291    
292      fun translate (SrcIL.Program{globals, globalInit, actors}) = let      fun translate (SrcIL.Program{globals, globalInit, strands}) = let
293            val env = VTbl.mkTable (256, Fail "env")            val env = VTbl.mkTable (256, Fail "env")
294            fun transMethod (SrcIL.Method{name, stateIn, stateOut, body}) =            fun transMethod (SrcIL.Method{name, stateIn, stateOut, body}) =
295                  DstIL.Method{                  DstIL.Method{
# Line 129  Line 298 
298                      stateOut = renameList (env, stateOut),                      stateOut = renameList (env, stateOut),
299                      body = Trans.translate (env, body)                      body = Trans.translate (env, body)
300                    }                    }
301            fun transActor (SrcIL.Actor{name, params, state, stateInit, methods}) =            fun transStrand (SrcIL.Strand{name, params, state, stateInit, methods}) =
302                  DstIL.Actor{                  DstIL.Strand{
303                      name = name,                      name = name,
304                      params = renameList (env, params),                      params = renameList (env, params),
305                      state = renameList (env, state),                      state = renameList (env, state),
# Line 141  Line 310 
310              DstIL.Program{              DstIL.Program{
311                  globals = renameList (env, globals),                  globals = renameList (env, globals),
312                  globalInit = Trans.translate (env, globalInit),                  globalInit = Trans.translate (env, globalInit),
313                  actors = List.map transActor actors                  strands = List.map transStrand strands
314                }                }
315            end            end
316    

Legend:
Removed from v.459  
changed lines
  Added in v.511

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0