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 431, Mon Oct 18 22:27:21 2010 UTC revision 1116, Thu May 5 04:49:02 2011 UTC
# Line 1  Line 1 
1  (* mid-to-low.sml  (* mid-to-low.sml
2   *   *
3   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
5   *   *
6   * Translation from MidIL to LowIL representations.   * Translation from MidIL to LowIL representations.
# Line 8  Line 8 
8    
9  structure MidToLow : sig  structure MidToLow : sig
10    
11      val translate : HighIL.program -> MidIL.program      val translate : MidIL.program -> LowIL.program
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 *)    (* convert a rational to a FloatLit.float value.  We do this by long division
36      fun expandKernel (dimSize, kern, k, vec) = ??     * 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    (* compute the load address for a given set of voxels indices *)      fun imul (r : DstIL.var, a, b) = (r, DstIL.OP(DstOp.Mul DstTy.intTy, [a, b]))
85      fun computeVoxelAddress (info, vec) = ??      fun iadd (r : DstIL.var, a, b) = (r, DstIL.OP(DstOp.Add DstTy.intTy, [a, b]))
86        fun ilit (r : DstIL.var, n) = (r, DstIL.LIT(Literal.Int(IntInf.fromInt n)))
87    
88      (* expand the EvalKernel operations into vector operations.  The parameters
89       * are
90       *    result  -- the lhs variable to store the result
91       *    d       -- the vector width of the operation, which should be equal
92       *               to twice the support of the kernel
93       *    h       -- the kernel
94       *    k       -- the derivative of the kernel to evaluate
95       *
96       * The generated code is computing
97       *
98       *    result = a_0 + x*(a_1 + x*(a_2 + ... x*a_n) ... )
99       *
100       * as a d-wide vector operation, where n is the degree of the kth derivative
101       * of h and the a_i are coefficient vectors that have an element for each
102       * piece of h.  The computation is implemented as follows
103       *
104       *    m_n     = x * a_n
105       *    s_{n-1} = a_{n-1} + m_n
106       *    m_{n-1} = x * s_{n-1}
107       *    s_{n-2} = a_{n-2} + m_{n-1}
108       *    m_{n-2} = x * s_{n-2}
109       *    ...
110       *    s_1     = a_1 + m_2
111       *    m_1     = x * s_1
112       *    result  = a_0 + m_1
113       *
114       * Note that the coeffient vectors are flipped (cf high-to-low/probe.sml).
115       *)
116        fun expandEvalKernel (result, d, h, k, [x]) = let
117              val {isCont, segs} = Kernel.curve (h, k)
118            (* degree of polynomial *)
119              val deg = List.length(hd segs) - 1
120            (* convert to a vector of vectors to give fast access *)
121              val segs = Vector.fromList (List.rev (List.map Vector.fromList segs))
122            (* get the kernel coefficient value for the d'th term of the i'th
123             * segment.
124             *)
125              fun coefficient d i =
126                    Literal.Float(ratToFloat (Vector.sub (Vector.sub(segs, i), d)))
127              val ty = DstTy.vecTy d
128              val coeffs = List.tabulate (deg+1,
129                    fn i => DstIL.Var.new("a"^Int.toString i, ty))
130            (* code to define the coefficient vectors *)
131              val coeffVecs = let
132                    fun mk (x, (i, code)) = let
133                          val lits = List.tabulate(d, coefficient i)
134                          val vars = List.tabulate(d, fn _ => DstIL.Var.new("_f", DstTy.realTy))
135                          val code =
136                                ListPair.map (fn (x, lit) => (x, DstIL.LIT lit)) (vars, lits) @
137                                  (x, DstIL.CONS(DstIL.Var.ty x, vars)) :: code
138                          in
139                            (i-1, code)
140                          end
141                    in
142                      #2 (List.foldr mk (deg, []) coeffs)
143                    end
144            (* build the evaluation of the polynomials in reverse order *)
145              fun pTmp i = DstIL.Var.new("prod" ^ Int.toString i, ty)
146              fun sTmp i = DstIL.Var.new("sum" ^ Int.toString i, ty)
147              fun eval (i, [coeff]) = let
148                    val m = pTmp i
149                    in
150                      (m, [(m, DstIL.OP(DstOp.Mul ty, [x, coeff]))])
151                    end
152                | eval (i, coeff::r) = let
153                    val (m, stms) = eval(i+1, r)
154                    val s = sTmp i
155                    val m' = pTmp i
156                    val stms =
157                          (m', DstIL.OP(DstOp.Mul ty, [x, s])) ::
158                          (s, DstIL.OP(DstOp.Add ty, [coeff, m])) ::
159                          stms
160                    in
161                      (m', stms)
162                    end
163              val evalCode = (case coeffs
164                     of [a0] => (* constant function *)
165                          [(result, DstIL.VAR a0)]
166                      | a0::r => let
167                          val (m, stms) = eval (1, r)
168                          in
169                            List.rev ((result, DstIL.OP(DstOp.Add ty, [a0, m]))::stms)
170                          end
171                    (* end case *))
172              in
173                coeffVecs @ evalCode
174              end
175    
176    (* FIXME: we will get better down-stream CSE if we structure the address computation
177     * as
178     *      (base + stride * (...)) + offset
179     * since the lhs argument will be the same for each sample.
180     *)
181      (* add code to handle the offset and stride when addressing non-scalar image data *)
182        fun adjustForStrideAndOffset (1, _, ix, code) = (ix, code)
183          | adjustForStrideAndOffset (stride, 0, ix, code) = let
184              val offp = DstIL.Var.new ("offp", DstTy.intTy)
185              val stride' = DstIL.Var.new ("stride", DstTy.intTy)
186              in
187                (offp, imul(offp, stride', ix) :: ilit(stride', stride) :: code)
188              end
189          | adjustForStrideAndOffset (stride, offset, ix, code) = let
190              val offp = DstIL.Var.new ("offp", DstTy.intTy)
191              val stride' = DstIL.Var.new ("stride", DstTy.intTy)
192              val offset' = DstIL.Var.new ("offset", DstTy.intTy)
193              val t = DstIL.Var.new ("t", DstTy.intTy)
194              val code =
195                    iadd(offp, offset', t) ::
196                    ilit (offset', offset) ::
197                    imul(t, stride', ix) ::
198                    ilit (stride', stride) ::
199                    code
200              in
201                (offp, code)
202              end
203    
204      (* compute the load address for a given set of voxels indices.  For the
205       * operation
206       *
207       *    VoxelAddress<info,offset>(i_1, ..., i_d)
208       *
209       * the address is given by
210       *
211       *    base + offset + stride * (i_1 + N_1 * (i_2 + N_2 * (... + N_{d-1} * i_d) ...))
212       *
213       * where
214       *    base    -- base address of the image data
215       *    stride  -- number of samples per voxel
216       *    offset  -- offset of sample being addressed
217       *    N_i     -- size of ith axis in elements
218       *
219       * Note that we are following the Nrrd convention that the axes are ordered
220       * in fastest to slowest order.  We are also assuming the C semantics of address
221       * arithmetic, where the offset will be automatically scaled by the size of the
222       * elements.
223       *)
224        fun expandVoxelAddress (result, info, offset, [img, ix]) = let
225              val dim = ImageInfo.dim info
226              val sizes = ImageInfo.sizes info
227              val stride = ImageInfo.stride info
228              val shape = ImageInfo.voxelShape info
229              val (offp, code) = adjustForStrideAndOffset (stride, offset, ix, [])
230              val addrTy = DstTy.AddrTy info
231              val base = DstIL.Var.new ("imgBaseAddr", addrTy)
232              val code = (result, DstIL.OP(DstOp.Add addrTy, [base, offp])) ::
233                    (base, DstIL.OP(DstOp.ImageAddress info, [img])) ::
234                    code
235              in
236                List.rev code
237              end
238          | expandVoxelAddress (result, info, offset, img::ix1::indices) = let
239              val dim = ImageInfo.dim info
240              val sizes = ImageInfo.sizes info
241              val stride = ImageInfo.stride info
242              val shape = ImageInfo.voxelShape info
243            (* get N_1 ... N_{d-1} *)
244              val sizes = List.take (sizes, List.length sizes - 1)
245            (* generate the address computation code in reverse order *)
246              fun gen (d, [n], [ix]) = let
247                    val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)
248                    val t = DstIL.Var.new ("t", DstTy.intTy)
249                    val code = [
250                            imul(t, n', ix),
251                            ilit(n', n)
252                          ]
253                    in
254                      (t, code)
255                    end
256                | gen (d, n::ns, ix::ixs) = let
257                    val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)
258                    val t1 = DstIL.Var.new ("t1", DstTy.intTy)
259                    val t2 = DstIL.Var.new ("t2", DstTy.intTy)
260                    val (t, code) = gen (d+1, ns, ixs)
261                    val code =
262                          imul(t2, n', t1) ::
263                          ilit(n', n) ::
264                          iadd(t1, ix, t) :: code
265                    in
266                      (t2, code)
267                    end
268              val (tmp, code) = gen (0, sizes, indices)
269              val t = DstIL.Var.new ("index", DstTy.intTy)
270              val code = iadd(t, ix1, tmp) :: code
271              val (offp, code) = adjustForStrideAndOffset (stride, offset, t, code)
272              val addrTy = DstTy.AddrTy info
273              val base = DstIL.Var.new ("imgBaseAddr", addrTy)
274              val code = (result, DstIL.OP(DstOp.Add addrTy, [base, offp])) ::
275                    (base, DstIL.OP(DstOp.ImageAddress info, [img])) ::
276                    code
277              in
278                List.rev code
279              end
280    
281      fun expandOp (env, y, rator, args) = let      fun expandOp (env, y, rator, args) = let
282            fun assign rator' =            val args' = renameList(env, args)
283                  [(y, DstIL.OP(rator', renameList(env, args)))]            fun assign rator' = [(y, DstIL.OP(rator', args'))]
284            in            in
285              case rator              case rator
286               of SrcOp.Add ty =>               of SrcOp.Add ty => assign (DstOp.Add ty)
287                | SrcOp.Sub ty =>                | SrcOp.Sub ty => assign (DstOp.Sub ty)
288                | SrcOp.Mul ty =>                | SrcOp.Mul ty => assign (DstOp.Mul ty)
289                | SrcOp.Div ty =>                | SrcOp.Div ty => assign (DstOp.Div ty)
290                | SrcOp.Neg ty =>                | SrcOp.Neg ty => assign (DstOp.Neg ty)
291                | SrcOp.LT ty =>                | SrcOp.Abs ty => assign (DstOp.Abs ty)
292                | SrcOp.LTE ty =>                | SrcOp.LT ty => assign (DstOp.LT ty)
293                | SrcOp.EQ ty =>                | SrcOp.LTE ty => assign (DstOp.LTE ty)
294                | SrcOp.NEQ ty =>                | SrcOp.EQ ty => assign (DstOp.EQ ty)
295                | SrcOp.GT ty =>                | SrcOp.NEQ ty => assign (DstOp.NEQ ty)
296                | SrcOp.GTE ty =>                | SrcOp.GT ty => assign (DstOp.GT ty)
297                | SrcOp.Not =>                | SrcOp.GTE ty => assign (DstOp.GTE ty)
298                | SrcOp.Max =>                | SrcOp.Not => assign (DstOp.Not)
299                | SrcOp.Min =>                | SrcOp.Max => assign (DstOp.Max)
300                | SrcOp.Sin =>                | SrcOp.Min => assign (DstOp.Min)
301                | SrcOp.Cos =>                | SrcOp.Lerp ty => assign (DstOp.Lerp ty)
302                | SrcOp.Pow =>                | SrcOp.Dot d => assign (DstOp.Dot d)
303                | SrcOp.Dot d =>                | SrcOp.MulVecMat(d1, d2) => assign (DstOp.MulVecMat(d1, d2))
304                | SrcOp.Cross =>                | SrcOp.MulMatVec(d1, d2) => assign (DstOp.MulMatVec(d1, d2))
305                | SrcOp.Select ty =>  * int                | SrcOp.MulMatMat(d1, d2, d3) => assign (DstOp.MulMatMat(d1, d2, d3))
306                | SrcOp.Norm d =>                | SrcOp.Cross => assign (DstOp.Cross)
307                | SrcOp.Scale d =>                | SrcOp.Select(ty, i) => assign (DstOp.Select(ty, i))
308                | SrcOp.InvScale d =>                | SrcOp.Norm ty => assign (DstOp.Norm ty)
309                | SrcOp.CL =>                | SrcOp.Normalize d => assign (DstOp.Normalize d)
310                | SrcOp.PrincipleEvec ty =>                | SrcOp.Scale ty => assign (DstOp.Scale ty)
311                | SrcOp.Subscript ty =>                | SrcOp.Zero ty => assign (DstOp.Zero ty)
312                | SrcOp.Floor d =>                | SrcOp.CL => assign (DstOp.CL)
313                | SrcOp.IntToReal =>                | SrcOp.PrincipleEvec ty => assign (DstOp.PrincipleEvec ty)
314                | SrcOp.TruncToInt d =>                | SrcOp.Identity n => assign (DstOp.Identity n)
315                | SrcOp.RoundToInt d =>                | SrcOp.Trace d => assign (DstOp.Trace d)
316                | SrcOp.CeilToInt d =>                | SrcOp.Subscript ty => assign (DstOp.Subscript ty)
317                | SrcOp.FloorToInt d =>                | SrcOp.Ceiling d => assign (DstOp.Ceiling d)
318                | SrcOp.VoxelAddress info =>                | SrcOp.Floor d => assign (DstOp.Floor d)
319                | SrcOp.LoadVoxels(rty, d) =>                | SrcOp.Round d => assign (DstOp.Round d)
320                | SrcOp.Transform info =>                | SrcOp.Trunc d => assign (DstOp.Trunc d)
321                | SrcOp.EvalKernel(d, h, k) =>                | SrcOp.IntToReal => assign (DstOp.IntToReal)
322                | SrcOp.LoadImage info =>                | SrcOp.RealToInt d => assign (DstOp.RealToInt d)
323                | SrcOp.Inside info =>                | SrcOp.VoxelAddress(info, offset) => expandVoxelAddress (y, info, offset, args')
324                | SrcOp.Input(ty, name) =>                | SrcOp.LoadVoxels(rty, d) => assign (DstOp.LoadVoxels(rty, d))
325                | SrcOp.InputWithDefault(ty, name) =>                | SrcOp.PosToImgSpace info => assign (DstOp.PosToImgSpace info)
326                | _ => raise Fail("unexpected " ^ SrcOp.toString rator)                | SrcOp.TensorToWorldSpace(info, ty) => assign (DstOp.TensorToWorldSpace(info, ty))
327                  | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k, args')
328                  | SrcOp.LoadImage info => assign (DstOp.LoadImage info)
329                  | SrcOp.Inside info => assign (DstOp.Inside info)
330                  | SrcOp.Input(ty, name) => assign (DstOp.Input(ty, name))
331                  | SrcOp.InputWithDefault(ty, name) => assign (DstOp.InputWithDefault(ty, name))
332              (* end case *)              (* end case *)
333            end            end
334    
335    (* expand a SrcIL assignment to a list of DstIL assignments *)    (* expand a SrcIL assignment to a DstIL CFG *)
336      fun expand (env, (y, rhs)) = let      fun expand (env, (y, rhs)) = let
337            val y' = rename (env, y)            val y' = rename (env, y)
338            fun assign rhs = [(y', rhs)]            fun assign rhs = [(y', rhs)]
# Line 96  Line 341 
341               of SrcIL.VAR x => assign (DstIL.VAR(rename(env, x)))               of SrcIL.VAR x => assign (DstIL.VAR(rename(env, x)))
342                | SrcIL.LIT lit => assign (DstIL.LIT lit)                | SrcIL.LIT lit => assign (DstIL.LIT lit)
343                | SrcIL.OP(rator, args) => expandOp (env, y', rator, args)                | SrcIL.OP(rator, args) => expandOp (env, y', rator, args)
344                | SrcIL.CONS args => assign (DstIL.CONS(renameList(env, args)))                | SrcIL.APPLY(f, args) => assign(DstIL.APPLY(f, renameList(env, args)))
345                  | SrcIL.CONS(ty, args) => assign (DstIL.CONS(ty, renameList(env, args)))
346              (* end case *)              (* end case *)
347            end            end
348    
# Line 108  Line 354 
354          type var_env = var_env          type var_env = var_env
355    
356          val rename = rename          val rename = rename
357          val expand = expand          val renameList = renameList
358            val expand = DstIL.CFG.mkBlock o expand
359        end)        end)
360    
361      fun translate (SrcIL.Program{globals, globalInit, actors}) = let      fun translate prog = let
362            val env = VTbl.mkTable (256, Fail "env")            val prog = Trans.translate prog
363            fun transMethod (SrcIL.Method{name, stateIn, stateOut, body}) =            in
364                  DstIL.Method{              LowILCensus.init prog;
365                      name = name,              prog
                     stateIn = renameList (env, stateIn),  
                     stateOut = renameList (env, stateOut),  
                     body = Trans.translate (env, body)  
                   }  
           fun transActor (SrcIL.Actor{name, params, state, stateInit, methods}) =  
                 DstIL.Actor{  
                     name = name,  
                     params = renameList (env, params),  
                     state = renameList (env, state),  
                     stateInit = Trans.translate (env, stateInit),  
                     methods = List.map transMethod methods  
                   }  
           in  
             DstIL.Program{  
                 globals = renameList (env, globals),  
                 globalInit = Trans.translate (env, globalInit),  
                 actors = List.map transActor actors  
               }  
366            end            end
367    
368    end    end

Legend:
Removed from v.431  
changed lines
  Added in v.1116

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