Home My Page Projects Code Snippets Project Openings diderot

# SCM Repository

[diderot] Diff of /branches/charisee/src/compiler/mid-to-low/mid-to-low.sml
 [diderot] / branches / charisee / src / compiler / mid-to-low / mid-to-low.sml

# Diff of /branches/charisee/src/compiler/mid-to-low/mid-to-low.sml

revision 511, Tue Feb 8 17:01:43 2011 UTC revision 1116, Thu May 5 04:49:02 2011 UTC
# Line 81  Line 81
81                  end                  end
82            (* end case *))            (* end case *))
83
84      fun imul (r, a, b) = (r, DstIL.OP(DstOp.Mul DstTy.intTy, [a, b]))      fun imul (r : DstIL.var, 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]))      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    (* expand the EvalKernel operations into vector operations.  The parameters
89     * are     * are
# Line 109  Line 110
110     *    s_1     = a_1 + m_2     *    s_1     = a_1 + m_2
111     *    m_1     = x * s_1     *    m_1     = x * s_1
112     *    result  = a_0 + m_1     *    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      fun expandEvalKernel (result, d, h, k, [x]) = let
117            val {isCont, segs} = Kernel.curve (h, k)            val {isCont, segs} = Kernel.curve (h, k)
118          (* degree of polynomial *)          (* degree of polynomial *)
119            val deg = List.length(hd segs) - 1            val deg = List.length(hd segs) - 1
120          (* convert to a vector of vectors to give fast access *)          (* convert to a vector of vectors to give fast access *)
121            val segs = Vector.fromList (List.map Vector.fromList segs)            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          (* get the kernel coefficient value for the d'th term of the i'th
123           * segment.           * segment.
124           *)           *)
125            fun coefficient d i =            fun coefficient d i =
126                  Literal.Float(ratToFloat (Vector.sub (Vector.sub(segs, i), d)))                  Literal.Float(ratToFloat (Vector.sub (Vector.sub(segs, i), d)))
127            val ty = DstTy.VecTy d            val ty = DstTy.vecTy d
128            val coeffs = List.tabulate (deg+1,            val coeffs = List.tabulate (deg+1,
129                  fn i => DstIL.Var.new("a"^Int.toString i, ty))                  fn i => DstIL.Var.new("a"^Int.toString i, ty))
130          (* code to define the coefficient vectors *)          (* code to define the coefficient vectors *)
# Line 131  Line 134
134                        val vars = List.tabulate(d, fn _ => DstIL.Var.new("_f", DstTy.realTy))                        val vars = List.tabulate(d, fn _ => DstIL.Var.new("_f", DstTy.realTy))
135                        val code =                        val code =
136                              ListPair.map (fn (x, lit) => (x, DstIL.LIT lit)) (vars, lits) @                              ListPair.map (fn (x, lit) => (x, DstIL.LIT lit)) (vars, lits) @
137                                (x, DstIL.CONS vars) :: code                                (x, DstIL.CONS(DstIL.Var.ty x, vars)) :: code
138                        in                        in
139                          (i-1, code)                          (i-1, code)
140                        end                        end
# Line 157  Line 160
160                  in                  in
161                    (m', stms)                    (m', stms)
162                  end                  end
163            val evalCode = let            val evalCode = (case coeffs
164                  val a0::r = coeffs                   of [a0] => (* constant function *)
165                          [(result, DstIL.VAR a0)]
166                      | a0::r => let
167                  val (m, stms) = eval (1, r)                  val (m, stms) = eval (1, r)
168                  in                  in
169                    List.rev ((result, DstIL.OP(DstOp.Add ty, [a0, m]))::stms)                    List.rev ((result, DstIL.OP(DstOp.Add ty, [a0, m]))::stms)
170                  end                  end
171                    (* end case *))
172            in            in
173              coeffVecs @ evalCode              coeffVecs @ evalCode
174            end            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 =
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    (* compute the load address for a given set of voxels indices.  For the
205     * operation     * operation
206     *     *
208     *     *
209     * the address is given by     * the address is given by
210     *     *
211     *    base + szb * (i_1 + N_2 * (i_2 + N_3 * (... + N_d * i_d) ...))     *    base + offset + stride * (i_1 + N_1 * (i_2 + N_2 * (... + N_{d-1} * i_d) ...))
212     *     *
213     * where     * where
214     *    base    -- base address of the image data     *    base    -- base address of the image data
215     *    szb     -- image-element size in bytes     *    stride  -- number of samples per voxel
216       *    offset  -- offset of sample being addressed
217     *    N_i     -- size of ith axis in elements     *    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, indices) = let      fun expandVoxelAddress (result, info, offset, [img, ix]) = let
225            val ImageInfo.ImgInfo{ty=(d, rTy), sizes=_::sizes, ...} = info            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, [])
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 *)          (* generate the address computation code in reverse order *)
246            fun gen (d, [n], [ix]) = let            fun gen (d, [n], [ix]) = let
247                  val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)                  val n' = DstIL.Var.new ("n" ^ Int.toString d, DstTy.intTy)
248                  val t = DstIL.Var.new ("t", DstTy.intTy)                  val t = DstIL.Var.new ("t", DstTy.intTy)
249                  val code = [                  val code = [
250                          imul(t, n', ix),                          imul(t, n', ix),
251                          (n', DstIL.LIT(Literal.Int(IntInf.fromInt n)))                          ilit(n', n)
252                        ]                        ]
253                  in                  in
254                    (t, code)                    (t, code)
# Line 201  Line 260
260                  val (t, code) = gen (d+1, ns, ixs)                  val (t, code) = gen (d+1, ns, ixs)
261                  val code =                  val code =
262                        imul(t2, n', t1) ::                        imul(t2, n', t1) ::
263                        (n', DstIL.LIT(Literal.Int(IntInf.fromInt n))) ::                        ilit(n', n) ::
265                  in                  in
266                    (t2, code)                    (t2, code)
267                  end                  end
268            val voxSzb = List.foldl Int.* (RawTypes.sizeb rTy) d            val (tmp, code) = gen (0, sizes, indices)
269            val (offset, code) = gen (0, voxSzb :: sizes, indices)            val t = DstIL.Var.new ("index", DstTy.intTy)
271            val code = (result, DstIL.OP(DstOp.Add DstTy.AddrTy, [base, offset])) ::            val (offp, code) = adjustForStrideAndOffset (stride, offset, t, code)
275                    (base, DstIL.OP(DstOp.ImageAddress info, [img])) ::
276                  code                  code
277            in            in
278              List.rev code              List.rev code
# Line 226  Line 288
288                | SrcOp.Mul ty => assign (DstOp.Mul ty)                | SrcOp.Mul ty => assign (DstOp.Mul ty)
289                | SrcOp.Div ty => assign (DstOp.Div ty)                | SrcOp.Div ty => assign (DstOp.Div ty)
290                | SrcOp.Neg ty => assign (DstOp.Neg ty)                | SrcOp.Neg ty => assign (DstOp.Neg ty)
291                  | SrcOp.Abs ty => assign (DstOp.Abs ty)
292                | SrcOp.LT ty => assign (DstOp.LT ty)                | SrcOp.LT ty => assign (DstOp.LT ty)
293                | SrcOp.LTE ty => assign (DstOp.LTE ty)                | SrcOp.LTE ty => assign (DstOp.LTE ty)
294                | SrcOp.EQ ty => assign (DstOp.EQ ty)                | SrcOp.EQ ty => assign (DstOp.EQ ty)
# Line 235  Line 298
298                | SrcOp.Not => assign (DstOp.Not)                | SrcOp.Not => assign (DstOp.Not)
299                | SrcOp.Max => assign (DstOp.Max)                | SrcOp.Max => assign (DstOp.Max)
300                | SrcOp.Min => assign (DstOp.Min)                | SrcOp.Min => assign (DstOp.Min)
301                | SrcOp.Sin => assign (DstOp.Sin)                | SrcOp.Lerp ty => assign (DstOp.Lerp ty)
| SrcOp.Cos => assign (DstOp.Cos)
| SrcOp.Pow => assign (DstOp.Pow)
302                | SrcOp.Dot d => assign (DstOp.Dot d)                | SrcOp.Dot d => assign (DstOp.Dot d)
303                  | SrcOp.MulVecMat(d1, d2) => assign (DstOp.MulVecMat(d1, d2))
304                  | SrcOp.MulMatVec(d1, d2) => assign (DstOp.MulMatVec(d1, d2))
305                  | SrcOp.MulMatMat(d1, d2, d3) => assign (DstOp.MulMatMat(d1, d2, d3))
306                | SrcOp.Cross => assign (DstOp.Cross)                | SrcOp.Cross => assign (DstOp.Cross)
307                | SrcOp.Select(ty, i)=> assign (DstOp.Select(ty, i))                | SrcOp.Select(ty, i)=> assign (DstOp.Select(ty, i))
308                | SrcOp.Norm d => assign (DstOp.Norm d)                | SrcOp.Norm ty => assign (DstOp.Norm ty)
309                | SrcOp.Scale d => assign (DstOp.Scale d)                | SrcOp.Normalize d => assign (DstOp.Normalize d)
310                | SrcOp.InvScale d => assign (DstOp.InvScale d)                | SrcOp.Scale ty => assign (DstOp.Scale ty)
311                  | SrcOp.Zero ty => assign (DstOp.Zero ty)
312                | SrcOp.CL => assign (DstOp.CL)                | SrcOp.CL => assign (DstOp.CL)
313                | SrcOp.PrincipleEvec ty => assign (DstOp.PrincipleEvec ty)                | SrcOp.PrincipleEvec ty => assign (DstOp.PrincipleEvec ty)
314                  | SrcOp.Identity n => assign (DstOp.Identity n)
315                  | SrcOp.Trace d => assign (DstOp.Trace d)
316                | SrcOp.Subscript ty => assign (DstOp.Subscript ty)                | SrcOp.Subscript ty => assign (DstOp.Subscript ty)
317                  | SrcOp.Ceiling d => assign (DstOp.Ceiling d)
318                | SrcOp.Floor d => assign (DstOp.Floor d)                | SrcOp.Floor d => assign (DstOp.Floor d)
319                  | SrcOp.Round d => assign (DstOp.Round d)
320                  | SrcOp.Trunc d => assign (DstOp.Trunc d)
321                | SrcOp.IntToReal => assign (DstOp.IntToReal)                | SrcOp.IntToReal => assign (DstOp.IntToReal)
322                | SrcOp.TruncToInt d => assign (DstOp.TruncToInt d)                | SrcOp.RealToInt d => assign (DstOp.RealToInt d)
323                | SrcOp.RoundToInt d => assign (DstOp.RoundToInt d)                | SrcOp.VoxelAddress(info, offset) => expandVoxelAddress (y, info, offset, args')
| SrcOp.CeilToInt d => assign (DstOp.CeilToInt d)
| SrcOp.FloorToInt d => assign (DstOp.FloorToInt d)
325                | SrcOp.PosToImgSpace info => assign (DstOp.PosToImgSpace info)                | SrcOp.PosToImgSpace info => assign (DstOp.PosToImgSpace info)
326                | SrcOp.GradToWorldSpace info => assign (DstOp.GradToWorldSpace info)                | SrcOp.TensorToWorldSpace(info, ty) => assign (DstOp.TensorToWorldSpace(info, ty))
327                | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k, args')                | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k, args')
329                | SrcOp.Inside info => assign (DstOp.Inside info)                | SrcOp.Inside info => assign (DstOp.Inside info)
# Line 265  Line 332
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 274  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 286  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, strands}) = 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 transStrand (SrcIL.Strand{name, params, state, stateInit, methods}) =
DstIL.Strand{
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),
strands = List.map transStrand strands
}
366            end            end
367
368    end    end

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