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

SCM Repository

[diderot] Annotation of /branches/lamont/src/compiler/translate/translate.sml
ViewVC logotype

Annotation of /branches/lamont/src/compiler/translate/translate.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2084 - (view) (download)

1 : jhr 137 (* translate.sml
2 :     *
3 : jhr 435 * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 : jhr 137 * All rights reserved.
5 :     *
6 : jhr 1116 * Translate Simple-AST code into the IL representation. This translation is based on the
7 :     * algorithm described in
8 :     *
9 :     * Single-pass generation of static single assignment form for structured languages
10 :     * ACM TOPLAS, Nov. 1994
11 :     * by Brandis and MossenBock.
12 : jhr 137 *)
13 :    
14 :     structure Translate : sig
15 :    
16 : jhr 176 val translate : Simple.program -> HighIL.program
17 : jhr 137
18 :     end = struct
19 :    
20 : jhr 176 structure S = Simple
21 : jhr 394 structure Ty = Types
22 : jhr 137 structure VMap = Var.Map
23 : jhr 189 structure VSet = Var.Set
24 : jhr 168 structure IL = HighIL
25 : jhr 1640 structure Op = HighOps
26 : jhr 394 structure DstTy = HighILTypes
27 : jhr 1116 structure Census = HighILCensus
28 : jhr 137
29 : jhr 1640 val cvtTy = TranslateTy.tr
30 :    
31 : jhr 1116 (* maps from SimpleAST variables to the current corresponding SSA variable *)
32 : jhr 511 type env = IL.var VMap.map
33 :    
34 : jhr 1640 (* +DEBUG *)
35 :     fun prEnv (prefix, env) = let
36 :     val wid = ref 0
37 :     fun pr s = (print s; wid := !wid + size s)
38 :     fun nl () = if (!wid > 0) then (print "\n"; wid := 0) else ()
39 :     fun prElem (src, dst) = let
40 :     val s = String.concat [
41 :     " ", Var.uniqueNameOf src, "->", IL.Var.toString dst
42 :     ]
43 :     in
44 :     pr s;
45 :     if (!wid >= 100) then (nl(); pr " ") else ()
46 :     end
47 :     in
48 :     pr prefix; pr " ENV: {"; nl(); pr " ";
49 :     VMap.appi prElem env;
50 :     nl(); pr "}"; nl()
51 :     end
52 :     (* -DEBUG *)
53 :    
54 : jhr 197 fun lookup env x = (case VMap.find (env, x)
55 : jhr 176 of SOME x' => x'
56 :     | NONE => raise Fail(concat[
57 : jhr 197 "no binding for ", Var.uniqueNameOf x, " in environment"
58 : jhr 176 ])
59 :     (* end case *))
60 :    
61 : jhr 189 (* create a new instance of a variable *)
62 : jhr 394 fun newVar x = IL.Var.new (Var.nameOf x, cvtTy(Var.monoTypeOf x))
63 : jhr 189
64 : jhr 1116 (* generate fresh SSA variables and add them to the environment *)
65 :     fun freshVars (env, xs) = let
66 :     fun cvtVar (x, (env, xs)) = let
67 :     val x' = newVar x
68 :     in
69 :     (VMap.insert(env, x, x'), x'::xs)
70 :     end
71 :     val (env, xs) = List.foldl cvtVar (env, []) xs
72 :     in
73 :     (env, List.rev xs)
74 :     end
75 :    
76 : lamonts 2083 (* Determines the type of join. The foreach node does not have a seperate join node the node itself is the join node.
77 :     so you need something to differentiate between the two for commiting joins and getting their node. *)
78 :     datatype joinType
79 :     = NORMAL_JOIN
80 :     | FOREACH_JOIN
81 :    
82 : jhr 1116 (* a pending-join node tracks the phi nodes needed to join the assignments
83 :     * that flow into the join node.
84 :     *)
85 :     datatype join = JOIN of {
86 : lamonts 2083 env : env ref, (* the environment that was current at the conditional *)
87 : jhr 1232 (* associated with this node. *)
88 : jhr 1116 arity : int ref, (* actual number of predecessors *)
89 :     nd : IL.node, (* the CFG node for this pending join *)
90 :     phiMap : IL.phi VMap.map ref, (* a mapping from Simple AST variables that are assigned *)
91 :     (* to their phi nodes. *)
92 : lamonts 2083 predKill : bool array, (* killed predecessor edges (because of DIE or STABILIZE *)
93 :     joinTy : joinType (* Determines if this join contains a JOIN node (if statements) or FOREACH node (foreach statements) *)
94 : jhr 1116 }
95 :    
96 :     (* a stack of pending joins. The first component specifies the path index of the current
97 :     * path to the join.
98 :     *)
99 :     type pending_joins = (int * join) list
100 :    
101 :     (* create a new pending-join node *)
102 : jhr 1232 fun newJoin (env, arity) = JOIN{
103 : lamonts 2083 env = ref env, arity = ref arity, joinTy = NORMAL_JOIN, nd = IL.Node.mkJOIN [], phiMap = ref VMap.empty,
104 : jhr 1116 predKill = Array.array(arity, false)
105 :     }
106 :    
107 : lamonts 2083 (* LAMONT: COMMENT *)
108 :     fun newJoinWithNode(env,arity,nd as IL.ND{kind=IL.FOREACH{...}, ...}) = JOIN {
109 :     env = ref env, arity = ref arity,joinTy = FOREACH_JOIN, nd = nd, phiMap = ref VMap.empty,
110 :     predKill = Array.array(arity, false)
111 :     }
112 :    
113 : jhr 1116 (* record that a path to the top join in the stack has been killed because f DIE or STABILIZE *)
114 :     fun killPath ((i, JOIN{arity, predKill, ...}) :: _) = (
115 :     arity := !arity - 1;
116 :     Array.update (predKill, i, true))
117 :     | killPath _ = ()
118 :    
119 :     (* record an assignment to the IL variable dstVar (corresponding to the Simple AST variable
120 :     * srcVar) in the current pending-join node. The predIndex specifies which path into the
121 :     * JOIN node this assignment occurs on.
122 :     *)
123 : jhr 1232 fun recordAssign ([], _, _) = ()
124 : lamonts 2083 | recordAssign ((predIndex, JOIN{env, phiMap, predKill, nd, joinTy,...})::_, srcVar, dstVar) = let
125 : jhr 1116 val arity = Array.length predKill (* the original arity before any killPath calls *)
126 :     val m = !phiMap
127 :     in
128 : lamonts 2083 case VMap.find (!env, srcVar)
129 : jhr 1116 of NONE => () (* local temporary *)
130 :     | SOME dstVar' => (case VMap.find (m, srcVar)
131 :     of NONE => let
132 :     val lhs = newVar srcVar
133 :     val rhs = List.tabulate (arity, fn i => if (i = predIndex) then dstVar else dstVar')
134 :     in
135 : jhr 1232 (*
136 :     print(concat["recordAssign: ", Var.uniqueNameOf srcVar, " --> ", IL.Var.toString lhs,
137 :     " @ ", IL.Node.toString nd, "\n"]);
138 :     *)
139 : lamonts 2083 if joinTy = FOREACH_JOIN then
140 :     let
141 :     val IL.ND{kind=IL.FOREACH{shouldReplace, ...}, ...} = nd
142 :     in
143 :     (env := VMap.insert(!env,srcVar,lhs);
144 :     shouldReplace := true)
145 :     end
146 :     else
147 :     ();
148 :    
149 : jhr 1116 phiMap := VMap.insert (m, srcVar, (lhs, rhs))
150 :     end
151 :     | SOME(lhs, rhs) => let
152 :     fun update (i, l as x::r) = if (i = predIndex)
153 :     then dstVar::r
154 :     else x::update(i+1, r)
155 :     | update _ = raise Fail "invalid predecessor index"
156 :     in
157 :     phiMap := VMap.insert (m, srcVar, (lhs, update(0, rhs)))
158 :     end
159 :     (* end case *))
160 :     (* end case *)
161 :     end
162 :    
163 :     (* complete a pending join operation by filling in the phi nodes from the phi map and
164 :     * updating the environment.
165 :     *)
166 : lamonts 2083 fun commitJoin (joinStk, JOIN{env, arity, nd, phiMap, joinTy, predKill}) = (case !arity
167 :     of 0 => (!env, NONE)
168 : jhr 1763 | 1 => let
169 :     (* there is only one path to the join, so we do not need phi nodes, but
170 :     * we still need to propogate assignments to the next join on the stack.
171 :     *)
172 :     val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd
173 :     val ix = let (* find pred of this join *)
174 :     fun find i = if Array.sub(predKill, i) then find(i+1) else i
175 :     in
176 :     find 0
177 :     end
178 :     fun doVar (srcVar, (_, xs), env) = let
179 :     val dstVar = List.nth(xs, ix)
180 :     in
181 :     (*
182 :     print(concat["doVar (", Var.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
183 :     *)
184 :     recordAssign (joinStk, srcVar, dstVar);
185 :     VMap.insert (env, srcVar, dstVar)
186 :     end
187 : lamonts 2083 val env = VMap.foldli doVar (!env) (!phiMap)
188 : jhr 1763 in
189 :     (env, SOME nd)
190 :     end
191 : jhr 1116 | n => if (n = Array.length predKill)
192 :     then let
193 : lamonts 2083 val phis = (case joinTy of
194 :     NORMAL_JOIN => let
195 :     val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd
196 :     in
197 :     phis
198 :     end
199 :     |FOREACH_JOIN => let
200 :     val IL.ND{kind=IL.FOREACH{phis, ...}, ...} = nd
201 :     in
202 :     phis
203 :     end)
204 : jhr 1116 fun doVar (srcVar, phi as (dstVar, _), (env, phis)) = (
205 : jhr 1232 (*
206 :     print(concat["doVar (", Var.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
207 :     *)
208 :     recordAssign (joinStk, srcVar, dstVar);
209 : jhr 1116 (VMap.insert (env, srcVar, dstVar), phi::phis))
210 : lamonts 2083 val (env, phis') = VMap.foldli doVar (!env, []) (!phiMap)
211 : jhr 1116 in
212 :     phis := phis';
213 :     (env, SOME nd)
214 :     end
215 :     else raise Fail "FIXME: prune killed paths."
216 :     (* end case *))
217 :    
218 : jhr 168 (* expression translation *)
219 : jhr 1116 fun cvtExp (env : env, lhs, exp) = (case exp
220 : jhr 1640 of S.E_Var x => [IL.ASSGN(lhs, IL.VAR(lookup env x))]
221 :     | S.E_Lit lit => [IL.ASSGN(lhs, IL.LIT lit)]
222 : lamonts 2083 | S.E_SphereQuery (args,ty) => let
223 :     val args' = List.map (lookup env) args
224 :     in
225 : lamonts 2084 [IL.ASSGN(lhs,IL.OP(HighOps.SphereQuery (cvtTy ty),args'))]
226 : lamonts 2083 end
227 :     | S.E_Selector(x,f) => let
228 :     val x' = lookup env x
229 :     in
230 :     [IL.ASSGN(lhs,IL.SELECTOR(x',f))]
231 :     end
232 :     | S.E_Tuple xs => raise Fail "E_Tuple not implemeted"
233 :     | S.E_Apply(f, tyArgs, args, ty) => let
234 : jhr 188 val args' = List.map (lookup env) args
235 :     in
236 :     TranslateBasis.translate (lhs, f, tyArgs, args')
237 :     end
238 : jhr 1640 | S.E_Cons args => [IL.ASSGN(lhs, IL.CONS(IL.Var.ty lhs, List.map (lookup env) args))]
239 : jhr 1688 | S.E_Seq args => [IL.ASSGN(lhs, IL.CONS(IL.Var.ty lhs, List.map (lookup env) args))]
240 : jhr 400 | S.E_Slice(x, indices, ty) => let
241 :     val x = lookup env x
242 :     val mask = List.map isSome indices
243 :     fun cvt NONE = NONE
244 :     | cvt (SOME x) = SOME(lookup env x)
245 :     val indices = List.mapPartial cvt indices
246 :     in
247 :     if List.all (fn b => b) mask
248 : jhr 2027 then [IL.ASSGN(lhs, IL.OP(Op.TensorSub(IL.Var.ty x), x::indices))]
249 :     else [IL.ASSGN(lhs, IL.OP(Op.Slice(IL.Var.ty lhs, mask), x::indices))]
250 : jhr 400 end
251 : jhr 2016 (* DEPRECATED
252 : jhr 1301 | S.E_Input(_, name, desc, NONE) =>
253 : jhr 2027 [IL.ASSGN(lhs, IL.OP(Op.Input(IL.Var.ty lhs, name, desc), []))]
254 : jhr 1301 | S.E_Input(_, name, desc, SOME dflt) =>
255 : jhr 2027 [IL.ASSGN(lhs, IL.OP(Op.InputWithDefault(IL.Var.ty lhs, name, desc), [lookup env dflt]))]
256 : jhr 2016 *)
257 : jhr 1687 | S.E_Coerce{srcTy, dstTy, x} => (case (srcTy, dstTy)
258 :     of (Ty.T_Int, Ty.T_Tensor _) =>
259 : jhr 2027 [IL.ASSGN(lhs, IL.OP(Op.IntToReal, [lookup env x]))]
260 : jhr 1687 | (Ty.T_Sequence(ty, Ty.DimConst n), Ty.T_DynSequence _) =>
261 : jhr 2027 [IL.ASSGN(lhs, IL.OP(Op.MkDynamic(cvtTy ty, n), [lookup env x]))]
262 : jhr 1943 | (Ty.T_Field _, Ty.T_Field _) =>
263 : jhr 1687 (* change in continuity is a no-op *)
264 :     [IL.ASSGN(lhs, IL.VAR(lookup env x))]
265 :     | _ => raise Fail "unsupported type coercion"
266 :     (* end case *))
267 : jhr 2027 | S.E_LoadSeq(ty, nrrd) => [IL.ASSGN(lhs, IL.OP(Op.LoadSeq(cvtTy ty, nrrd), []))]
268 :     | S.E_LoadImage(ty, nrrd, info) => [IL.ASSGN(lhs, IL.OP(Op.LoadImage(cvtTy ty, nrrd, info), []))]
269 : jhr 176 (* end case *))
270 : jhr 168
271 : jhr 1640 (* add nodes to save the strand state, followed by an exit node *)
272 :     fun saveStrandState (env, (srcState, dstState), exit) = let
273 :     val stateOut = List.map (lookup env) srcState
274 :     fun save (x, x', cfg) = IL.CFG.appendNode (cfg, IL.Node.mkSAVE(x, x'))
275 :     in
276 :     IL.CFG.appendNode (
277 :     ListPair.foldlEq save IL.CFG.empty (dstState, stateOut),
278 :     exit)
279 :     end
280 : jhr 2026 (*DEBUG*)handle ex => raise ex
281 : jhr 1640
282 : jhr 1116 fun cvtBlock (state, env : env, joinStk, S.Block stms) = let
283 : lamonts 2083 (* LAMONT COMMENT THIS SECTION!!!! *)
284 :     fun cvtLoopBlock(forNode as IL.ND{kind=IL.FOREACH{shouldReplace, ...}, ...},state,joinStk,blk) = let
285 :     val (_,JOIN{env,...})::_ = joinStk
286 :     val(cfg0,e) = cvtBlock (state,!env,joinStk, blk)
287 :     in
288 :     (
289 :     if(!shouldReplace = true) then
290 :     (shouldReplace := false;
291 :     cvtLoopBlock(forNode,state,joinStk,blk))
292 :     else
293 :     (cfg0,e))
294 :     end
295 :    
296 : jhr 1116 fun cvt (env : env, cfg, []) = (cfg, env)
297 :     | cvt (env, cfg, stm::stms) = (case stm
298 :     of S.S_Var x => let
299 :     val x' = newVar x
300 :     in
301 :     cvt (VMap.insert (env, x, x'), cfg, stms)
302 :     end
303 :     | S.S_Assign(lhs, rhs) => let
304 :     val lhs' = newVar lhs
305 :     val assigns = cvtExp (env, lhs', rhs)
306 :     in
307 : jhr 1232 (*
308 :     print "doAssign\n";
309 :     *)
310 :     recordAssign (joinStk, lhs, lhs');
311 : jhr 1116 cvt (
312 :     VMap.insert(env, lhs, lhs'),
313 :     IL.CFG.concat(cfg, IL.CFG.mkBlock assigns),
314 :     stms)
315 :     end
316 :     | S.S_IfThenElse(x, b0, b1) => let
317 : jhr 192 val x' = lookup env x
318 : jhr 1232 val join = newJoin (env, 2)
319 : jhr 1116 val (cfg0, _) = cvtBlock (state, env, (0, join)::joinStk, b0)
320 :     val (cfg1, _) = cvtBlock (state, env, (1, join)::joinStk, b1)
321 :     val cond = IL.Node.mkCOND {
322 :     cond = x',
323 :     trueBranch = IL.Node.dummy,
324 :     falseBranch = IL.Node.dummy
325 :     }
326 : jhr 190 in
327 : jhr 1116 IL.Node.addEdge (IL.CFG.exit cfg, cond);
328 : jhr 1232 case commitJoin (joinStk, join)
329 : jhr 1116 of (env, SOME joinNd) => (
330 :     if IL.CFG.isEmpty cfg0
331 :     then (
332 :     IL.Node.setTrueBranch (cond, joinNd);
333 :     IL.Node.setPred (joinNd, cond))
334 :     else (
335 :     IL.Node.setTrueBranch (cond, IL.CFG.entry cfg0);
336 :     IL.Node.setPred (IL.CFG.entry cfg0, cond);
337 :     IL.Node.addEdge (IL.CFG.exit cfg0, joinNd));
338 :     if IL.CFG.isEmpty cfg1
339 :     then (
340 :     IL.Node.setFalseBranch (cond, joinNd);
341 :     IL.Node.setPred (joinNd, cond))
342 :     else (
343 :     IL.Node.setFalseBranch (cond, IL.CFG.entry cfg1);
344 :     IL.Node.setPred (IL.CFG.entry cfg1, cond);
345 :     IL.Node.addEdge (IL.CFG.exit cfg1, joinNd));
346 :     cvt (
347 :     env,
348 : jhr 1339 IL.CFG.concat (
349 :     cfg,
350 :     IL.CFG{entry = cond, exit = joinNd}),
351 : jhr 1116 stms))
352 :     (* the join node has only zero predecessors, so
353 :     * it was killed.
354 :     *)
355 :     | (env, NONE) => raise Fail "unimplemented" (* FIXME *)
356 : jhr 192 (* end case *)
357 : jhr 190 end
358 : lamonts 2083 | S.S_Foreach(x,e',blk) => let
359 :     val cond' = lookup env x
360 :     val forNode = IL.Node.mkFOREACH{
361 :     cond = cond',
362 :     phis = [],
363 :     sName = "",
364 :     stmBranch = IL.Node.dummy
365 :     }
366 :     val join = newJoinWithNode(env, 2,forNode)
367 :     val (cfg0, _) = cvtLoopBlock(forNode,state,(1, join)::joinStk, blk)
368 :     in
369 :     case commitJoin (joinStk, join)
370 :     of (env, SOME joinND) => (
371 :     if IL.CFG.isEmpty cfg0
372 :     then (
373 :     ())
374 :     else (
375 :     IL.Node.setPred (IL.CFG.entry cfg0, joinND);
376 :     IL.Node.setStmBranch(joinND, IL.CFG.entry cfg0);
377 :     IL.Node.addEdge (IL.CFG.exit cfg0, joinND));
378 :     cvt (
379 :     env,
380 :     IL.CFG.appendNode (cfg, joinND),
381 :     stms))
382 :    
383 :    
384 :     (* the join node has only zero predecessors, so
385 :     * it was killed. *)
386 :    
387 :     | (env, NONE) => raise Fail "unimplemented" (* FIXME *)
388 :     (* end case *)
389 :     end
390 : jhr 1116 | S.S_New(strandId, args) => let
391 :     val nd = IL.Node.mkNEW{
392 :     strand = strandId,
393 :     args = List.map (lookup env) args
394 :     }
395 : jhr 192 in
396 : jhr 1116 cvt (env, IL.CFG.appendNode (cfg, nd), stms)
397 : jhr 194 end
398 : jhr 1116 | S.S_Die => (
399 :     killPath joinStk;
400 :     (IL.CFG.appendNode (cfg, IL.Node.mkDIE ()), env))
401 : jhr 1640 | S.S_Stabilize => (
402 :     killPath joinStk;
403 :     (IL.CFG.concat (cfg, saveStrandState (env, state, IL.Node.mkSTABILIZE())), env))
404 :     | S.S_Print args => let
405 :     val args = List.map (lookup env) args
406 :     val nd = IL.Node.mkMASSIGN([], Op.Print(List.map IL.Var.ty args), args)
407 :     in
408 :     cvt (env, IL.CFG.appendNode (cfg, nd), stms)
409 :     end
410 : jhr 192 (* end case *))
411 :     in
412 : jhr 1116 cvt (env, IL.CFG.empty, stms)
413 : jhr 192 end
414 : jhr 1339 (*DEBUG*)handle ex => raise ex
415 : jhr 168
416 : jhr 1232 fun cvtTopLevelBlock (env, blk, mkExit) = let
417 : jhr 1640 val (cfg, env) = cvtBlock (([], []), env, [], blk)
418 :     val cfg = IL.CFG.prependNode (IL.Node.mkENTRY(), cfg)
419 :     val cfg = IL.CFG.concat (cfg, mkExit env)
420 : jhr 256 in
421 : jhr 1640 (cfg, env)
422 : jhr 256 end
423 : jhr 1339 (*DEBUG*)handle ex => raise ex
424 : jhr 256
425 : jhr 1116 (* FIXME: the following function could be refactored with cvtTopLevelBlock to share code *)
426 : jhr 1232 fun cvtFragmentBlock (env0, blk) = let
427 : jhr 1640 val (cfg, env) = cvtBlock (([], []), env0, [], blk)
428 : jhr 1116 val entry = IL.Node.mkENTRY ()
429 : jhr 1232 (* the live variables out are those that were not live coming in *)
430 :     val liveOut = VMap.foldli
431 :     (fn (x, x', xs) => if VMap.inDomain(env0, x) then xs else x'::xs)
432 :     [] env
433 :     val exit = IL.Node.mkFRAGMENT liveOut
434 : jhr 1116 in
435 :     if IL.CFG.isEmpty cfg
436 :     then IL.Node.addEdge (entry, exit)
437 :     else (
438 :     IL.Node.addEdge (entry, IL.CFG.entry cfg);
439 : jhr 1232 IL.Node.addEdge (IL.CFG.exit cfg, exit));
440 : jhr 1116 (IL.CFG{entry = entry, exit = exit}, env)
441 :     end
442 : jhr 1339 (*DEBUG*)handle ex => raise ex
443 : jhr 1116
444 : jhr 1640 fun cvtMethod (env, name, state, svars, blk) = let
445 :     (* load the state into fresh variables *)
446 :     val (env, loadCFG) = let
447 :     (* allocate shadow variables for the state variables *)
448 :     val (env, stateIn) = freshVars (env, state)
449 :     fun load (x, x') = IL.ASSGN(x, IL.STATE x')
450 :     in
451 :     (env, IL.CFG.mkBlock (ListPair.map load (stateIn, svars)))
452 :     end
453 : jhr 1116 (* convert the body of the method *)
454 : jhr 1640 val (cfg, env) = cvtBlock ((state, svars), env, [], blk)
455 : jhr 1116 (* add the entry/exit nodes *)
456 :     val entry = IL.Node.mkENTRY ()
457 : jhr 1640 val loadCFG = IL.CFG.prependNode (entry, loadCFG)
458 : jhr 1444 val exit = (case name
459 : jhr 1640 of StrandUtil.Update => IL.Node.mkACTIVE ()
460 :     | StrandUtil.Stabilize => IL.Node.mkRETURN []
461 : jhr 1444 (* end case *))
462 : jhr 1640 val body = IL.CFG.concat (loadCFG, cfg)
463 :     (*DEBUG**val _ = prEnv (StrandUtil.nameToString name, env);*)
464 :     (* FIXME: the following code doesn't work properly *)
465 :     val body = if IL.Node.hasSucc(IL.CFG.exit body)
466 :     then IL.CFG.concat (body, saveStrandState (env, (state, svars), exit))
467 :     else IL.CFG{entry = IL.CFG.entry body, exit = exit}
468 : jhr 1116 in
469 :     IL.Method{
470 :     name = name,
471 : jhr 1640 body = body
472 : jhr 1116 }
473 :     end
474 : jhr 1640 (*DEBUG*)handle ex => (print(concat["error in cvtMethod(", StrandUtil.nameToString name, ", ...)\n"]); raise ex)
475 : jhr 1116
476 :     (* convert the initially code *)
477 :     fun cvtInitially (env, S.Initially{isArray, rangeInit, create, iters}) = let
478 :     val S.C_Create{argInit, name, args} = create
479 :     fun cvtIter ({param, lo, hi}, (env, iters)) = let
480 :     val param' = newVar param
481 :     val env = VMap.insert (env, param, param')
482 :     val iter = (param', lookup env lo, lookup env hi)
483 : jhr 256 in
484 : jhr 1116 (env, iter::iters)
485 : jhr 256 end
486 : jhr 1116 val (cfg, env) = cvtFragmentBlock (env, rangeInit)
487 :     val (env, iters) = List.foldl cvtIter (env, []) iters
488 :     val (argInitCFG, env) = cvtFragmentBlock (env, argInit)
489 : jhr 256 in
490 : jhr 1116 IL.Initially{
491 :     isArray = isArray,
492 :     rangeInit = cfg,
493 :     iters = List.rev iters,
494 :     create = (argInitCFG, name, List.map (lookup env) args)
495 :     }
496 : jhr 256 end
497 :    
498 : jhr 1640 (* check strands for properties *)
499 :     fun checkProps strands = let
500 :     val hasDie = ref false
501 :     val hasNew = ref false
502 :     fun chkStm e = (case e
503 :     of S.S_IfThenElse(_, b1, b2) => (chkBlk b1; chkBlk b2)
504 :     | S.S_New _ => (hasNew := true)
505 :     | S.S_Die => (hasDie := true)
506 :     | _ => ()
507 :     (* end case *))
508 :     and chkBlk (S.Block body) = List.app chkStm body
509 :     fun chkStrand (S.Strand{stateInit, methods, ...}) = let
510 :     fun chkMeth (S.Method(_, body)) = chkBlk body
511 :     in
512 :     chkBlk stateInit;
513 :     List.app chkMeth methods
514 :     end
515 :     fun condCons (x, v, l) = if !x then v::l else l
516 :     in
517 :     List.app chkStrand strands;
518 :     condCons (hasDie, StrandUtil.StrandsMayDie,
519 :     condCons (hasNew, StrandUtil.NewStrands, []))
520 :     end
521 :    
522 : jhr 2018 fun cvtInputs inputs = let
523 :     fun cvt ((x, inp), (env, stms)) = let
524 :     val x' = newVar x
525 :     val stm = IL.ASSGN(x', IL.OP(Op.Input(Inputs.map cvtTy inp), []))
526 :     in
527 :     (VMap.insert(env, x, x'), stm::stms)
528 :     end
529 :     val (env, stms) = List.foldr cvt (VMap.empty, []) inputs
530 :     in
531 :     (IL.CFG.mkBlock stms, env)
532 :     end
533 :    
534 : jhr 2016 fun translate (S.Program{inputs, globals, globalInit, init, strands}) = let
535 : jhr 1640 val (globalInit, env) = let
536 :     fun mkExit env = let
537 :     val nd = IL.Node.mkRETURN(VMap.listItems env)
538 :     in
539 :     IL.CFG{entry = nd, exit = nd}
540 :     end
541 : jhr 2018 val (inputBlk, env) = cvtInputs inputs
542 :     val (globBlk, env) = cvtBlock (([], []), env, [], globalInit)
543 :     val cfg = IL.CFG.prependNode (IL.Node.mkENTRY(), inputBlk)
544 :     val cfg = IL.CFG.concat(cfg, globBlk)
545 :     val cfg = IL.CFG.concat (cfg, mkExit env)
546 : jhr 1640 in
547 : jhr 2018 (cfg, env)
548 : jhr 1640 end
549 : jhr 2018 (* construct a reduced environment that just defines the globals (including inputs). *)
550 : jhr 1116 val env = let
551 : jhr 200 val lookup = lookup env
552 : jhr 1116 fun cvtVar (x, env) = VMap.insert(env, x, lookup x)
553 : jhr 2018 val env = List.foldl (fn ((x, _), env) => cvtVar(x, env)) VMap.empty inputs
554 :     val env = List.foldl cvtVar env globals
555 : jhr 200 in
556 : jhr 1116 env
557 : jhr 200 end
558 : jhr 1116 val init = cvtInitially (env, init)
559 : jhr 511 fun cvtStrand (S.Strand{name, params, state, stateInit, methods}) = let
560 : jhr 1232 (* extend the global environment with the strand's parameters *)
561 : jhr 200 val (env, params) = let
562 :     fun cvtParam (x, (env, xs)) = let
563 :     val x' = newVar x
564 :     in
565 :     (VMap.insert(env, x, x'), x'::xs)
566 :     end
567 :     val (env, params) = List.foldl cvtParam (env, []) params
568 :     in
569 :     (env, List.rev params)
570 :     end
571 : jhr 1640 (* create the state variables *)
572 :     val svars = let
573 :     fun newSVar x = IL.StateVar.new (
574 :     Var.kindOf x = S.StrandOutputVar,
575 :     Var.nameOf x, cvtTy(Var.monoTypeOf x))
576 :     in
577 :     List.map newSVar state
578 :     end
579 : jhr 1232 (* convert the state initialization code *)
580 :     val (stateInit, env) = let
581 : jhr 1640 fun mkExit env = saveStrandState (env, (state, svars), IL.Node.mkSINIT())
582 : jhr 1232 in
583 :     cvtTopLevelBlock (env, stateInit, mkExit)
584 :     end
585 : jhr 1640 fun cvtMeth (S.Method(name, blk)) = cvtMethod (env, name, state, svars, blk)
586 : jhr 200 in
587 : jhr 511 IL.Strand{
588 : jhr 200 name = name,
589 :     params = params,
590 : jhr 1640 state = svars,
591 : jhr 200 stateInit = stateInit,
592 : jhr 1116 methods = List.map cvtMeth methods
593 : jhr 200 }
594 :     end
595 : jhr 511 val prog = IL.Program{
596 : jhr 1640 props = checkProps strands,
597 : jhr 1116 globalInit = globalInit,
598 :     initially = init,
599 :     strands = List.map cvtStrand strands
600 :     }
601 : jhr 511 in
602 :     Census.init prog;
603 :     prog
604 : jhr 200 end
605 : jhr 176
606 : jhr 137 end

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