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

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