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 465, Thu Oct 28 22:17:34 2010 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 *)    (* expand the EvalKernel operations into vector operations.  The parameters
85      fun computeVoxelAddress (info, vec) = ??     * are
86       *    result  -- the lhs variable to store the result
87       *    d       -- the vector width of the operation, which should be equal
88       *               to twice the support of the kernel
89       *    h       -- the kernel
90       *    k       -- the derivative of the kernel to evaluate
91       *
92       * The generated code is computing
93       *
94       *    result = a_0 + x*(a_1 + x*(a_2 + ... x*a_n) ... )
95       *
96       * as a d-wide vector operation, where n is the degree of the kth derivative
97       * of h and the a_i are coefficient vectors that have an element for each
98       * piece of h.  The computation is implemented as follows
99       *
100       *    m_n     = x * a_n
101       *    s_{n-1} = a_{n-1} + m_n
102       *    m_{n-1} = x * s_{n-1}
103       *    s_{n-2} = a_{n-2} + m_{n-1}
104       *    m_{n-2} = x * s_{n-2}
105       *    ...
106       *    s_1     = a_1 + m_2
107       *    m_1     = x * s_1
108       *    result  = a_0 + m_1
109       *)
110        fun expandEvalKernel (result, d, h, k, [x]) = let
111              val {isCont, segs} = Kernel.curve (h, k)
112            (* degree of polynomial *)
113              val deg = List.length(hd segs) - 1
114            (* convert to a vector of vectors to give fast access *)
115              val segs = Vector.fromList (List.map Vector.fromList segs)
116            (* get the kernel coefficient value for the d'th term of the i'th
117             * segment.
118             *)
119              fun coefficient d i =
120                    Literal.Float(ratToFloat (Vector.sub (Vector.sub(segs, i), d)))
121              val ty = DstTy.VecTy d
122              val coeffs = List.tabulate (deg+1,
123                    fn i => DstIL.Var.new("a"^Int.toString i, ty))
124            (* code to define the coefficient vectors *)
125              val coeffVecs = let
126                    fun mk (x, (i, code)) = let
127                          val lits = List.tabulate(d, coefficient i)
128                          val vars = List.tabulate(d, fn _ => DstIL.Var.new("_f", DstTy.realTy))
129                          val code =
130                                ListPair.map (fn (x, lit) => (x, DstIL.LIT lit)) (vars, lits) @
131                                  (x, DstIL.CONS vars) :: code
132                          in
133                            (i-1, code)
134                          end
135                    in
136                      #2 (List.foldr mk (deg, []) coeffs)
137                    end
138            (* build the evaluation of the polynomials in reverse order *)
139              fun pTmp i = DstIL.Var.new("prod" ^ Int.toString i, ty)
140              fun sTmp i = DstIL.Var.new("sum" ^ Int.toString i, ty)
141              fun eval (i, [coeff]) = let
142                    val m = pTmp i
143                    in
144                      (m, [(m, DstIL.OP(DstOp.Mul ty, [x, coeff]))])
145                    end
146                | eval (i, coeff:r) = let
147                    val (m, stms) = eval(i+1, r)
148                    val s = sTmp i
149                    val m' = mTmp i
150                    val stms =
151                          (m', DstIL.OP(DstOp.Mul ty, [x, s])) ::
152                          (s, DstIL.OP(DstOp.Add ty, [coeff, m])) ::
153                          stms
154                    in
155                      (m', stms)
156                    end
157              val evalCode = let
158                    val a0::r = coeffs
159                    val (m, stms) = eval (1, r)
160                    in
161                      List.rev ((result, DstIL.OP(DstOp.Add ty, [a0, m]))::stms)
162                    end
163              in
164                coeffVecs @ evalCode
165              end
166    
167      (* compute the load address for a given set of voxels indices.  For the
168       * operation
169       *
170       *    VoxelAddress<info>(i_1, ..., i_d)
171       *
172       * the address is given by
173       *
174       *    base + szb * (i_1 + N_2 * (i_2 + N_3 * (... + N_d * i_d) ...))
175       *
176       * where
177       *    base    -- base address of the image data
178       *    szb     -- image-element size in bytes
179       *    N_i     -- size of ith axis in elements
180       *)
181        fun expandVoxelAddress (result, info, indices) = raise Fail "unimplemented"
182    
183      fun expandOp (env, y, rator, args) = let      fun expandOp (env, y, rator, args) = let
184            fun assign rator' =            val args' = renameList(env, args)
185                  [(y, DstIL.OP(rator', renameList(env, args)))]            fun assign rator' = [(y, DstIL.OP(rator', args'))]
186            in            in
187              case rator              case rator
188               of SrcOp.Add ty =>               of SrcOp.Add ty => assign (DstOp.Add ty)
189                | SrcOp.Sub ty =>                | SrcOp.Sub ty => assign (DstOp.Sub ty)
190                | SrcOp.Mul ty =>                | SrcOp.Mul ty => assign (DstOp.Mul ty)
191                | SrcOp.Div ty =>                | SrcOp.Div ty => assign (DstOp.Div ty)
192                | SrcOp.Neg ty =>                | SrcOp.Neg ty => assign (DstOp.Neg ty)
193                | SrcOp.LT ty =>                | SrcOp.LT ty => assign (DstOp.LT ty)
194                | SrcOp.LTE ty =>                | SrcOp.LTE ty => assign (DstOp.LTE ty)
195                | SrcOp.EQ ty =>                | SrcOp.EQ ty => assign (DstOp.EQ ty)
196                | SrcOp.NEQ ty =>                | SrcOp.NEQ ty => assign (DstOp.NEQ ty)
197                | SrcOp.GT ty =>                | SrcOp.GT ty => assign (DstOp.GT ty)
198                | SrcOp.GTE ty =>                | SrcOp.GTE ty => assign (DstOp.GTE ty)
199                | SrcOp.Not =>                | SrcOp.Not => assign (DstOp.Not)
200                | SrcOp.Max =>                | SrcOp.Max => assign (DstOp.Max)
201                | SrcOp.Min =>                | SrcOp.Min => assign (DstOp.Min)
202                | SrcOp.Sin =>                | SrcOp.Sin => assign (DstOp.Sin)
203                | SrcOp.Cos =>                | SrcOp.Cos => assign (DstOp.Cos)
204                | SrcOp.Pow =>                | SrcOp.Pow => assign (DstOp.Pow)
205                | SrcOp.Dot d =>                | SrcOp.Dot d => assign (DstOp.Dot d)
206                | SrcOp.Cross =>                | SrcOp.Cross => assign (DstOp.Cross)
207                | SrcOp.Select ty =>  * int                | SrcOp.Select(ty, i)=> assign (DstOp.Select(ty, i))
208                | SrcOp.Norm d =>                | SrcOp.Norm d => assign (DstOp.Norm d)
209                | SrcOp.Scale d =>                | SrcOp.Scale d => assign (DstOp.Scale d)
210                | SrcOp.InvScale d =>                | SrcOp.InvScale d => assign (DstOp.InvScale d)
211                | SrcOp.CL =>                | SrcOp.CL => assign (DstOp.CL)
212                | SrcOp.PrincipleEvec ty =>                | SrcOp.PrincipleEvec ty => assign (DstOp.PrincipleEvec ty)
213                | SrcOp.Subscript ty =>                | SrcOp.Subscript ty => assign (DstOp.Subscript ty)
214                | SrcOp.Floor d =>                | SrcOp.Floor d => assign (DstOp.Floor d)
215                | SrcOp.IntToReal =>                | SrcOp.IntToReal => assign (DstOp.IntToReal)
216                | SrcOp.TruncToInt d =>                | SrcOp.TruncToInt d => assign (DstOp.TruncToInt d)
217                | SrcOp.RoundToInt d =>                | SrcOp.RoundToInt d => assign (DstOp.RoundToInt d)
218                | SrcOp.CeilToInt d =>                | SrcOp.CeilToInt d => assign (DstOp.CeilToInt d)
219                | SrcOp.FloorToInt d =>                | SrcOp.FloorToInt d => assign (DstOp.FloorToInt d)
220                | SrcOp.VoxelAddress info =>                | SrcOp.VoxelAddress info => expandVoxelAddress (y, info, args')
221                | SrcOp.LoadVoxels(rty, d) =>                | SrcOp.LoadVoxels(rty, d) => assign (DstOp.LoadVoxels(rty, d))
222                | SrcOp.Transform info =>                | SrcOp.PosToImgSpace info => assign (DstOp.PosToImgSpace info)
223                | SrcOp.EvalKernel(d, h, k) =>                | SrcOp.GradToWorldSpace info => assign (DstOp.GradToWorldSpace info)
224                | SrcOp.LoadImage info =>                | SrcOp.EvalKernel(d, h, k) => expandEvalKernel(y, d, h, k, args')
225                | SrcOp.Inside info =>                | SrcOp.LoadImage info => assign (DstOp.LoadImage info)
226                | SrcOp.Input(ty, name) =>                | SrcOp.Inside info => assign (DstOp.Inside info)
227                | SrcOp.InputWithDefault(ty, name) =>                | SrcOp.Input(ty, name) => assign (DstOp.Input(ty, name))
228                | _ => raise Fail("unexpected " ^ SrcOp.toString rator)                | SrcOp.InputWithDefault(ty, name) => assign (DstOp.InputWithDefault(ty, name))
229              (* end case *)              (* end case *)
230            end            end
231    

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

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