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

SCM Repository

[diderot] Annotation of /branches/vis12/src/compiler/simplify/simplify.sml
ViewVC logotype

Annotation of /branches/vis12/src/compiler/simplify/simplify.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2141 - (view) (download)

1 : jhr 171 (* simplify.sml
2 :     *
3 : jhr 435 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 : jhr 171 * All rights reserved.
5 :     *
6 :     * Simplify the AST representation.
7 :     *)
8 :    
9 :     structure Simplify : sig
10 :    
11 : jhr 1140 val transform : Error.err_stream * AST.program -> Simple.program
12 : jhr 171
13 :     end = struct
14 :    
15 :     structure Ty = Types
16 :     structure S = Simple
17 : jhr 2013 structure InP = Inputs
18 : jhr 171
19 :     local
20 :     val tempName = Atom.atom "_t"
21 :     in
22 :     fun newTemp ty = Var.new (tempName, AST.LocalVar, ty)
23 :     end
24 :    
25 :     (* make a block out of a list of statements that are in reverse order *)
26 : jhr 197 fun mkBlock stms = S.Block(List.rev stms)
27 : jhr 171
28 : jhr 2012 (* convert an AST expression to an input initialization. Note that the Diderot grammar
29 :     * limits the forms of expression that we might encounter in this context.
30 :     *)
31 : jhr 2059 fun expToInit (ty, exp) = (case exp
32 : jhr 2013 of AST.E_Lit(Literal.Int n) => InP.Int n
33 :     | AST.E_Lit(Literal.Float f) => InP.Real f
34 :     | AST.E_Lit(Literal.String s) => InP.String s
35 :     | AST.E_Lit(Literal.Bool b) => InP.Bool b
36 : jhr 2011 | AST.E_Tuple es => raise Fail "E_Tuple not yet implemented"
37 :     | AST.E_Cons es => let
38 : jhr 2059 val shp = (case ty
39 :     of Ty.T_Tensor(Ty.Shape shp) => List.map (fn (Ty.DimConst d) => d) shp
40 :     | _ => raise Fail "not tensor type"
41 : jhr 2011 (* end case *))
42 : jhr 2059 fun flatten (AST.E_Lit(Literal.Int n), l) = FloatLit.fromInt n :: l
43 :     | flatten (AST.E_Lit(Literal.Float f), l) = f :: l
44 :     | flatten (AST.E_Coerce{e, ...}, l) = flatten(e, l)
45 :     | flatten (AST.E_Cons es, l) = flattenList (es, l)
46 :     | flatten _ = raise Fail "impossible"
47 :     and flattenList ([], l) = l
48 :     | flattenList (x::xs, l) = flatten(x, flattenList(xs, l))
49 : jhr 2011 in
50 : jhr 2059 InP.Tensor(shp, Vector.fromList(flattenList (es, [])))
51 : jhr 2011 end
52 : jhr 2059 (*
53 : jhr 2011 | AST.E_Seq es => ??
54 :     | AST.E_Coerce{srcTy, dstTy, e} => ??
55 : jhr 2014 *)
56 : jhr 2011 | _ => raise Fail "impossible initialization expression"
57 :     (* end case *))
58 :    
59 : jhr 2013 fun inputImage (nrrd, dim, shape) = let
60 :     val dim = TypeUtil.monoDim dim
61 :     val shp = TypeUtil.monoShape shape
62 :     in
63 :     case ImageInfo.fromNrrd(NrrdInfo.getInfo nrrd, dim, shp)
64 :     of NONE => raise Fail(concat["nrrd file \"", nrrd, "\" does not have expected type"])
65 :     | SOME info => InP.Proxy(nrrd, info)
66 :     (* end case *)
67 :     end
68 :    
69 : jhr 2140 (* is the given statement's continuation the syntactically following statement? *)
70 :     fun contIsNext (AST.S_Block stms) = List.all contIsNext stms
71 :     | contIsNext AST.S_Die = false
72 :     | contIsNext AST.S_Stabilize = false
73 :     | contIsNext (AST.S_Return _) = false
74 :     | contIsNext _ = true
75 :    
76 : jhr 227 fun simplifyProgram (AST.Program dcls) = let
77 : jhr 2011 val inputs = ref []
78 : jhr 171 val globals = ref []
79 :     val globalInit = ref []
80 : jhr 2135 val funcs = ref []
81 : jhr 1116 val initially = ref NONE
82 : jhr 511 val strands = ref []
83 : jhr 1116 fun setInitially init = (case !initially
84 :     of NONE => initially := SOME init
85 :     (* FIXME: the check for multiple initially decls should happen in type checking *)
86 :     | SOME _ => raise Fail "multiple initially declarations"
87 :     (* end case *))
88 : jhr 171 fun simplifyDecl dcl = (case dcl
89 : jhr 1301 of AST.D_Input(x, desc, NONE) => let
90 : jhr 2011 val (ty, init) = (case Var.monoTypeOf x
91 : jhr 2013 of ty as Ty.T_Image{dim, shape} => let
92 : jhr 2014 val info = ImageInfo.mkInfo(TypeUtil.monoDim dim, TypeUtil.monoShape shape)
93 : jhr 2013 in
94 :     (ty, SOME(InP.Image info))
95 :     end
96 : jhr 2011 | ty => (ty, NONE)
97 : jhr 1996 (* end case *))
98 : jhr 2013 val inp = InP.INP{
99 : jhr 2011 ty = ty,
100 :     name = Var.nameOf x,
101 :     desc = desc,
102 :     init = init
103 :     }
104 : jhr 185 in
105 : jhr 2011 inputs := (x, inp) :: !inputs
106 : jhr 185 end
107 : jhr 1992 | AST.D_Input(x, desc, SOME(AST.E_LoadNrrd(tvs, nrrd, ty))) => let
108 : jhr 1996 (* load the nrrd proxy here *)
109 : jhr 1993 val info = NrrdInfo.getInfo nrrd
110 : jhr 2011 val (ty, init) = (case Var.monoTypeOf x
111 : jhr 2013 of ty as Ty.T_DynSequence _ => (ty, InP.DynSeq nrrd)
112 :     | ty as Ty.T_Image{dim, shape} => (ty, inputImage(nrrd, dim, shape))
113 : jhr 1992 | _ => raise Fail "impossible"
114 :     (* end case *))
115 : jhr 2013 val inp = InP.INP{
116 : jhr 2011 ty = ty,
117 :     name = Var.nameOf x,
118 :     desc = desc,
119 :     init = SOME init
120 :     }
121 : jhr 1992 in
122 : jhr 2011 inputs := (x, inp) :: !inputs
123 : jhr 1992 end
124 : jhr 1301 | AST.D_Input(x, desc, SOME e) => let
125 : jhr 2059 val ty = Var.monoTypeOf x
126 : jhr 2013 val inp = InP.INP{
127 : jhr 2059 ty = ty,
128 : jhr 2011 name = Var.nameOf x,
129 :     desc = desc,
130 : jhr 2059 init = SOME(expToInit(ty, e))
131 : jhr 2011 }
132 : jhr 171 in
133 : jhr 2011 inputs := (x, inp) :: !inputs
134 : jhr 171 end
135 :     | AST.D_Var(AST.VD_Decl(x, e)) => let
136 :     val (stms, e') = simplifyExp (e, [])
137 :     in
138 :     globals := x :: !globals;
139 :     globalInit := S.S_Assign(x, e') :: (stms @ !globalInit)
140 :     end
141 : jhr 2135 | AST.D_Func(f, params, body) =>
142 :     funcs := S.Func{f=f, params=params, body=simplifyBlock body} :: !funcs
143 : jhr 511 | AST.D_Strand info => strands := simplifyStrand info :: !strands
144 : jhr 1116 | AST.D_InitialArray(creat, iters) =>
145 :     setInitially (simplifyInit(true, creat, iters))
146 :     | AST.D_InitialCollection(creat, iters) =>
147 :     setInitially (simplifyInit(false, creat, iters))
148 : jhr 171 (* end case *))
149 :     in
150 :     List.app simplifyDecl dcls;
151 : jhr 175 S.Program{
152 : jhr 2011 inputs = List.rev(!inputs),
153 : jhr 171 globals = List.rev(!globals),
154 :     globalInit = mkBlock (!globalInit),
155 : jhr 2135 funcs = List.rev(!funcs),
156 : jhr 1116 init = (case !initially
157 :     (* FIXME: the check for the initially block should really happen in typechecking *)
158 :     of NONE => raise Fail "missing initially declaration"
159 :     | SOME blk => blk
160 :     (* end case *)),
161 : jhr 511 strands = List.rev(!strands)
162 : jhr 171 }
163 :     end
164 :    
165 : jhr 1116 and simplifyInit (isArray, AST.C_Create(strand, exps), iters) = let
166 :     val (stms, xs) = simplifyExpsToVars (exps, [])
167 :     val creat = S.C_Create{
168 :     argInit = mkBlock stms,
169 :     name = strand,
170 :     args = xs
171 :     }
172 :     fun simplifyIter (AST.I_Range(x, e1, e2), (iters, stms)) = let
173 :     val (stms, lo) = simplifyExpToVar (e1, stms)
174 :     val (stms, hi) = simplifyExpToVar (e2, stms)
175 :     in
176 :     ({param=x, lo=lo, hi=hi}::iters, stms)
177 :     end
178 :     val (iters, stms) = List.foldl simplifyIter ([], []) iters
179 :     in
180 :     S.Initially{
181 :     isArray = isArray,
182 :     rangeInit = mkBlock stms,
183 :     iters = List.rev iters,
184 :     create = creat
185 :     }
186 :     end
187 :    
188 : jhr 511 and simplifyStrand {name, params, state, methods} = let
189 : jhr 171 fun simplifyState ([], xs, stms) = (List.rev xs, mkBlock stms)
190 :     | simplifyState (AST.VD_Decl(x, e) :: r, xs, stms) = let
191 :     val (stms, e') = simplifyExp (e, stms)
192 :     in
193 :     simplifyState (r, x::xs, S.S_Assign(x, e') :: stms)
194 :     end
195 :     val (xs, stm) = simplifyState (state, [], [])
196 :     in
197 : jhr 511 S.Strand{
198 : jhr 173 name = name,
199 : jhr 171 params = params,
200 :     state = xs, stateInit = stm,
201 :     methods = List.map simplifyMethod methods
202 :     }
203 :     end
204 :    
205 :     and simplifyMethod (AST.M_Method(name, body)) =
206 : jhr 197 S.Method(name, simplifyBlock body)
207 : jhr 171
208 : jhr 1116 (* simplify a statement into a single statement (i.e., a block if it expands
209 :     * into more than one new statement).
210 : jhr 171 *)
211 :     and simplifyBlock stm = mkBlock (simplifyStmt (stm, []))
212 :    
213 :     and simplifyStmt (stm, stms) = (case stm
214 :     of AST.S_Block body => let
215 : jhr 2140 (* FIXME: we should probably prune unreachable code in the typechecker and issue a warning! *)
216 : jhr 171 fun simplify ([], stms) = stms
217 : jhr 2140 | simplify (stm::r, stms) = if contIsNext stm
218 :     then simplify (r, simplifyStmt (stm, stms))
219 :     else simplify (r, []) (* prune unreachable statements *)
220 : jhr 171 in
221 :     simplify (body, stms)
222 :     end
223 :     | AST.S_Decl(AST.VD_Decl(x, e)) => let
224 :     val (stms, e') = simplifyExp (e, stms)
225 :     in
226 :     S.S_Assign(x, e') :: stms
227 :     end
228 :     | AST.S_IfThenElse(e, s1, s2) => let
229 :     val (stms, x) = simplifyExpToVar (e, stms)
230 :     val s1 = simplifyBlock s1
231 :     val s2 = simplifyBlock s2
232 :     in
233 :     S.S_IfThenElse(x, s1, s2) :: stms
234 :     end
235 :     | AST.S_Assign(x, e) => let
236 :     val (stms, e') = simplifyExp (e, stms)
237 :     in
238 :     S.S_Assign(x, e') :: stms
239 :     end
240 :     | AST.S_New(name, args) => let
241 :     val (stms, xs) = simplifyExpsToVars (args, stms)
242 :     in
243 :     S.S_New(name, xs) :: stms
244 :     end
245 :     | AST.S_Die => S.S_Die :: stms
246 :     | AST.S_Stabilize => S.S_Stabilize :: stms
247 : jhr 2135 | AST.S_Return e => let
248 :     val (stms, x) = simplifyExpToVar (e, stms)
249 :     in
250 :     S.S_Return x :: stms
251 :     end
252 : jhr 1640 | AST.S_Print args => let
253 :     val (stms, xs) = simplifyExpsToVars (args, stms)
254 :     in
255 :     S.S_Print xs :: stms
256 :     end
257 : jhr 171 (* end case *))
258 :    
259 :     and simplifyExp (exp, stms) = (
260 :     case exp
261 : jhr 197 of AST.E_Var x => (case Var.kindOf x
262 :     of Var.BasisVar => let
263 :     val ty = Var.monoTypeOf x
264 :     val x' = newTemp ty
265 :     val stm = S.S_Assign(x', S.E_Apply(x, [], [], ty))
266 :     in
267 :     (stm::stms, S.E_Var x')
268 :     end
269 :     | _ => (stms, S.E_Var x)
270 :     (* end case *))
271 : jhr 171 | AST.E_Lit lit => (stms, S.E_Lit lit)
272 :     | AST.E_Tuple es => raise Fail "E_Tuple not yet implemented"
273 :     | AST.E_Apply(f, tyArgs, args, ty) => let
274 :     val (stms, xs) = simplifyExpsToVars (args, stms)
275 :     in
276 :     (stms, S.E_Apply(f, tyArgs, xs, ty))
277 :     end
278 :     | AST.E_Cons es => let
279 :     val (stms, xs) = simplifyExpsToVars (es, stms)
280 :     in
281 :     (stms, S.E_Cons xs)
282 :     end
283 : jhr 1688 | AST.E_Seq es => let
284 :     val (stms, xs) = simplifyExpsToVars (es, stms)
285 :     in
286 :     (stms, S.E_Seq xs)
287 :     end
288 : jhr 399 | AST.E_Slice(e, indices, ty) => let (* tensor slicing *)
289 : jhr 395 val (stms, x) = simplifyExpToVar (e, stms)
290 : jhr 399 fun f ([], ys, stms) = (stms, List.rev ys)
291 :     | f (NONE::es, ys, stms) = f (es, NONE::ys, stms)
292 :     | f (SOME e::es, ys, stms) = let
293 :     val (stms, y) = simplifyExpToVar (e, stms)
294 :     in
295 :     f (es, SOME y::ys, stms)
296 :     end
297 :     val (stms, indices) = f (indices, [], stms)
298 : jhr 395 in
299 : jhr 399 (stms, S.E_Slice(x, indices, ty))
300 : jhr 395 end
301 : jhr 416 | AST.E_Cond(e1, e2, e3, ty) => let
302 : jhr 171 (* a conditional expression gets turned into an if-then-else statememt *)
303 : jhr 416 val result = newTemp ty
304 : jhr 1116 val (stms, x) = simplifyExpToVar (e1, S.S_Var result :: stms)
305 : jhr 171 fun simplifyBranch e = let
306 :     val (stms, e) = simplifyExp (e, [])
307 :     in
308 :     mkBlock (S.S_Assign(result, e)::stms)
309 :     end
310 : jhr 415 val s1 = simplifyBranch e2
311 :     val s2 = simplifyBranch e3
312 : jhr 171 in
313 :     (S.S_IfThenElse(x, s1, s2) :: stms, S.E_Var result)
314 :     end
315 : jhr 2026 | AST.E_LoadNrrd(_, nrrd, ty) => (case TypeUtil.prune ty
316 :     of ty as Ty.T_DynSequence _ => (stms, S.E_LoadSeq(ty, nrrd))
317 :     | ty as Ty.T_Image{dim, shape} => let
318 :     val dim = TypeUtil.monoDim dim
319 :     val shp = TypeUtil.monoShape shape
320 :     in
321 :     case ImageInfo.fromNrrd(NrrdInfo.getInfo nrrd, dim, shp)
322 :     of NONE => raise Fail(concat[
323 :     "nrrd file \"", nrrd, "\" does not have expected type"
324 :     ])
325 :     | SOME info => (stms, S.E_LoadImage(ty, nrrd, info))
326 :     (* end case *)
327 :     end
328 :     | _ => raise Fail "bogus type for E_LoadNrrd"
329 :     (* end case *))
330 : jhr 1687 | AST.E_Coerce{srcTy, dstTy, e} => let
331 :     val (stms, x) = simplifyExpToVar (e, stms)
332 :     val result = newTemp dstTy
333 :     in
334 :     (S.S_Assign(result, S.E_Coerce{srcTy=srcTy, dstTy=dstTy, x=x})::stms, S.E_Var result)
335 :     end
336 : jhr 171 (* end case *))
337 :    
338 :     and simplifyExpToVar (exp, stms) = let
339 :     val (stms, e) = simplifyExp (exp, stms)
340 :     in
341 :     case e
342 :     of S.E_Var x => (stms, x)
343 :     | _ => let
344 :     val x = newTemp (S.typeOf e)
345 :     in
346 :     (S.S_Assign(x, e)::stms, x)
347 :     end
348 :     (* end case *)
349 :     end
350 :    
351 :     and simplifyExpsToVars (exps, stms) = let
352 :     fun f ([], xs, stms) = (stms, List.rev xs)
353 :     | f (e::es, xs, stms) = let
354 :     val (stms, x) = simplifyExpToVar (e, stms)
355 :     in
356 :     f (es, x::xs, stms)
357 :     end
358 :     in
359 :     f (exps, [], stms)
360 :     end
361 :    
362 : jhr 1140 fun transform (errStrm, ast) = let
363 : jhr 227 val simple = simplifyProgram ast
364 : jhr 2141 val _ = SimplePP.output (Log.logFile(), "simplify", simple) (* DEBUG *)
365 :     val simple = Inliner.transform simple
366 :     val _ = SimplePP.output (Log.logFile(), "inlining", simple) (* DEBUG *)
367 : jhr 1993 (*
368 : jhr 227 val simple = Lift.transform simple
369 : jhr 1140 handle Eval.Error msg => (Error.error(errStrm, msg); simple)
370 : jhr 1993 *)
371 : jhr 227 in
372 :     simple
373 :     end
374 :    
375 : jhr 171 end

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