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

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