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

SCM Repository

[diderot] Diff of /trunk/src/compiler/translate/translate.sml
ViewVC logotype

Diff of /trunk/src/compiler/translate/translate.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1339, Mon Jun 13 19:56:59 2011 UTC revision 2476, Mon Oct 14 09:36:13 2013 UTC
# Line 18  Line 18 
18    end = struct    end = struct
19    
20      structure S = Simple      structure S = Simple
21      structure Ty = Types      structure Ty = SimpleTypes
22      structure VMap = Var.Map      structure VMap = SimpleVar.Map
23      structure VSet = Var.Set      structure VSet = SimpleVar.Set
24      structure IL = HighIL      structure IL = HighIL
25        structure Op = HighOps
26      structure DstTy = HighILTypes      structure DstTy = HighILTypes
27      structure Census = HighILCensus      structure Census = HighILCensus
28    
29        val cvtTy = TranslateTy.tr
30    
31    (* maps from SimpleAST variables to the current corresponding SSA variable *)    (* maps from SimpleAST variables to the current corresponding SSA variable *)
32      type env = IL.var VMap.map      type env = IL.var VMap.map
33    
34    (* +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                            " ", SimpleVar.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      fun lookup env x = (case VMap.find (env, x)      fun lookup env x = (case VMap.find (env, x)
55             of SOME x' => x'             of SOME x' => x'
56              | NONE => raise Fail(concat[              | NONE => raise Fail(concat[
57                    "no binding for ", Var.uniqueNameOf x, " in environment"                    "no binding for ", SimpleVar.uniqueNameOf x, " in environment"
58                  ])                  ])
59            (* end case *))            (* end case *))
60    
     fun cvtTy ty = (case TypeUtil.prune ty  
            of Ty.T_Bool => DstTy.BoolTy  
             | Ty.T_Int => DstTy.IntTy  
             | Ty.T_String => DstTy.StringTy  
             | Ty.T_Kernel _ => DstTy.KernelTy  
             | Ty.T_Tensor(Ty.Shape dd) => let  
                 fun cvtDim (Ty.DimConst 1) = NONE  
                   | cvtDim (Ty.DimConst d) = SOME d  
                 in  
                   DstTy.TensorTy(List.mapPartial cvtDim dd)  
                 end  
             | Ty.T_Image{dim=Ty.DimConst d, shape} => DstTy.ImageTy d  
             | Ty.T_Field fld => DstTy.FieldTy  
             | ty => raise Fail("cvtTy: unexpected " ^ TypeUtil.toString ty)  
           (* end case *))  
   
61    (* create a new instance of a variable *)    (* create a new instance of a variable *)
62      fun newVar x = IL.Var.new (Var.nameOf x, cvtTy(Var.monoTypeOf x))      fun newVar x = IL.Var.new (SimpleVar.nameOf x, cvtTy(SimpleVar.typeOf x))
63    
64    (* generate fresh SSA variables and add them to the environment *)    (* generate fresh SSA variables and add them to the environment *)
65      fun freshVars (env, xs) = let      fun freshVars (env, xs) = let
# Line 113  Line 120 
120                          val rhs = List.tabulate (arity, fn i => if (i = predIndex) then dstVar else dstVar')                          val rhs = List.tabulate (arity, fn i => if (i = predIndex) then dstVar else dstVar')
121                          in                          in
122  (*  (*
123  print(concat["recordAssign: ", Var.uniqueNameOf srcVar, " --> ", IL.Var.toString lhs,  print(concat["recordAssign: ", SimpleVar.uniqueNameOf srcVar, " --> ", IL.Var.toString lhs,
124  " @ ", IL.Node.toString nd, "\n"]);  " @ ", IL.Node.toString nd, "\n"]);
125  *)  *)
126                            phiMap := VMap.insert (m, srcVar, (lhs, rhs))                            phiMap := VMap.insert (m, srcVar, (lhs, rhs))
# Line 135  Line 142 
142     *)     *)
143      fun commitJoin (joinStk, JOIN{env, arity, nd, phiMap, predKill}) = (case !arity      fun commitJoin (joinStk, JOIN{env, arity, nd, phiMap, predKill}) = (case !arity
144             of 0 => (env, NONE)             of 0 => (env, NONE)
145              | 1 => (* there is only one path to the join, so we do not need phi nodes *)              | 1 => let
146                  (* there is only one path to the join, so we do not need phi nodes, but
147                   * we still need to propogate assignments to the next join on the stack.
148                   *)
149                    val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd
150                    val ix = let (* find pred of this join *)
151                          fun find i = if Array.sub(predKill, i) then find(i+1) else i
152                          in
153                            find 0
154                          end
155                    fun doVar (srcVar, (_, xs), env) = let
156                          val dstVar = List.nth(xs, ix)
157                          in
158    (*
159    print(concat["doVar (", SimpleVar.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
160    *)
161                            recordAssign (joinStk, srcVar, dstVar);
162                            VMap.insert (env, srcVar, dstVar)
163                          end
164                    val env = VMap.foldli doVar env (!phiMap)
165                    in
166                  (env, SOME nd)                  (env, SOME nd)
167                    end
168              | n => if (n = Array.length predKill)              | n => if (n = Array.length predKill)
169                  then let                  then let
170                    val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd                    val IL.ND{kind=IL.JOIN{phis, ...}, ...} = nd
171                    fun doVar (srcVar, phi as (dstVar, _), (env, phis)) = (                    fun doVar (srcVar, phi as (dstVar, _), (env, phis)) = (
172  (*  (*
173  print(concat["doVar (", Var.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);  print(concat["doVar (", SimpleVar.uniqueNameOf srcVar, ", ", IL.phiToString phi, ", _) @ ", IL.Node.toString nd, "\n"]);
174  *)  *)
175                          recordAssign (joinStk, srcVar, dstVar);                          recordAssign (joinStk, srcVar, dstVar);
176                          (VMap.insert (env, srcVar, dstVar), phi::phis))                          (VMap.insert (env, srcVar, dstVar), phi::phis))
# Line 156  Line 184 
184    
185    (* expression translation *)    (* expression translation *)
186      fun cvtExp (env : env, lhs, exp) = (case exp      fun cvtExp (env : env, lhs, exp) = (case exp
187             of S.E_Var x => [(lhs, IL.VAR(lookup env x))]             of S.E_Var x => [IL.ASSGN(lhs, IL.VAR(lookup env x))]
188              | S.E_Lit lit => [(lhs, IL.LIT lit)]              | S.E_Lit lit => [IL.ASSGN(lhs, IL.LIT lit)]
189              | S.E_Tuple xs => raise Fail "E_Tuple not implemeted"              | S.E_Tuple xs => raise Fail "E_Tuple not implemeted"
190              | S.E_Apply(f, tyArgs, args, ty) => let              | S.E_Apply _ => raise Fail "unexpected E_Apply"
191                | S.E_Prim(f, tyArgs, args, ty) => let
192                  val args' = List.map (lookup env) args                  val args' = List.map (lookup env) args
193                  in                  in
194                    TranslateBasis.translate (lhs, f, tyArgs, args')                    TranslateBasis.translate (lhs, f, tyArgs, args')
195                  end                  end
196              | S.E_Cons args => [(lhs, IL.CONS(IL.Var.ty lhs, List.map (lookup env) args))]              | S.E_Cons args => [IL.ASSGN(lhs, IL.CONS(IL.Var.ty lhs, List.map (lookup env) args))]
197              | S.E_Slice(x, indices, ty) => let              | S.E_Slice(x, indices, ty) => let
198                  val x = lookup env x                  val x = lookup env x
199                  val mask = List.map isSome indices                  val mask = List.map isSome indices
# Line 173  Line 202 
202                  val indices = List.mapPartial cvt indices                  val indices = List.mapPartial cvt indices
203                  in                  in
204                    if List.all (fn b => b) mask                    if List.all (fn b => b) mask
205                      then [(lhs, IL.OP(HighOps.Subscript(IL.Var.ty x), x::indices))]                      then [IL.ASSGN(lhs, IL.OP(Op.TensorSub(IL.Var.ty x), x::indices))]
206                      else [(lhs, IL.OP(HighOps.Slice(IL.Var.ty lhs, mask), x::indices))]                      else [IL.ASSGN(lhs, IL.OP(Op.Slice(IL.Var.ty x, mask), x::indices))]
207                  end                  end
208              | S.E_Input(_, name, desc, NONE) =>              | S.E_Coerce{srcTy, dstTy, x} => (case (srcTy, dstTy)
209                  [(lhs, IL.OP(HighOps.Input(IL.Var.ty lhs, name, desc), []))]                   of (Ty.T_Int, Ty.T_Tensor _) =>
210              | S.E_Input(_, name, desc, SOME dflt) =>                        [IL.ASSGN(lhs, IL.OP(Op.IntToReal, [lookup env x]))]
211                  [(lhs, IL.OP(HighOps.InputWithDefault(IL.Var.ty lhs, name, desc), [lookup env dflt]))]                    | (Ty.T_Field _, Ty.T_Field _) =>
212              | S.E_LoadImage(info, name) => [(lhs, IL.OP(HighOps.LoadImage info, [lookup env name]))]                      (* change in continuity is a no-op *)
213                          [IL.ASSGN(lhs, IL.VAR(lookup env x))]
214                      | _ => raise Fail(concat[
215                            "unsupported type coercion: ", Ty.toString srcTy,
216                            " ==> ", Ty.toString dstTy
217                          ])
218                    (* end case *))
219                | S.E_Input(_, name, NONE, NONE) =>
220                    [IL.ASSGN(lhs, IL.OP(HighOps.Input(IL.Var.ty lhs, name, ""), []))]
221                | S.E_Input(_, name, SOME desc, NONE) =>
222                    [IL.ASSGN(lhs, IL.OP(HighOps.Input(IL.Var.ty lhs, name, desc), []))]
223                | S.E_Input(_, name, NONE, SOME dflt) =>
224                    [IL.ASSGN(lhs, IL.OP(HighOps.InputWithDefault(IL.Var.ty lhs, name, ""), [lookup env dflt]))]
225                | S.E_Input(_, name, SOME desc, SOME dflt) =>
226                    [IL.ASSGN(lhs, IL.OP(HighOps.InputWithDefault(IL.Var.ty lhs, name, desc), [lookup env dflt]))]
227                | S.E_LoadImage(info, name) => [IL.ASSGN(lhs, IL.OP(HighOps.LoadImage info, [lookup env name]))]
228            (* end case *))            (* end case *))
229    
230      (* add nodes to save the strand state, followed by an exit node *)
231        fun saveStrandState (env, (srcState, dstState), exit) = let
232              val stateOut = List.map (lookup env) srcState
233              fun save (x, x', cfg) = IL.CFG.appendNode (cfg, IL.Node.mkSAVE(x, x'))
234              in
235                IL.CFG.appendNode (
236                  ListPair.foldlEq save IL.CFG.empty (dstState, stateOut),
237                  exit)
238              end
239    (*DEBUG*)handle ex => raise ex
240    
241      fun cvtBlock (state, env : env, joinStk, S.Block stms) = let      fun cvtBlock (state, env : env, joinStk, S.Block stms) = let
242            fun cvt (env : env, cfg, []) = (cfg, env)            fun cvt (env : env, cfg, []) = (cfg, env)
243              | cvt (env, cfg, stm::stms) = (case stm              | cvt (env, cfg, stm::stms) = (case stm
# Line 257  Line 312 
312                    | S.S_Die => (                    | S.S_Die => (
313                        killPath joinStk;                        killPath joinStk;
314                        (IL.CFG.appendNode (cfg, IL.Node.mkDIE ()), env))                        (IL.CFG.appendNode (cfg, IL.Node.mkDIE ()), env))
315                    | S.S_Stabilize => let                    | S.S_Stabilize => (
                       val stateOut = List.map (lookup env) state  
                       in  
316                          killPath joinStk;                          killPath joinStk;
317                          (IL.CFG.appendNode (cfg, IL.Node.mkSTABILIZE stateOut), env)                        (IL.CFG.concat (cfg, saveStrandState (env, state, IL.Node.mkSTABILIZE())), env))
318                      | S.S_Return _ => raise Fail "unexpected return"
319                      | S.S_Print args => let
320                          val args = List.map (lookup env) args
321                          val nd = IL.Node.mkMASSIGN([], Op.Print(List.map IL.Var.ty args), args)
322                          in
323                            cvt (env, IL.CFG.appendNode (cfg, nd), stms)
324                        end                        end
325                  (* end case *))                  (* end case *))
326            in            in
# Line 270  Line 329 
329  (*DEBUG*)handle ex => raise ex  (*DEBUG*)handle ex => raise ex
330    
331      fun cvtTopLevelBlock (env, blk, mkExit) = let      fun cvtTopLevelBlock (env, blk, mkExit) = let
332            val (cfg, env) = cvtBlock ([], env, [], blk)            val (cfg, env) = cvtBlock (([], []), env, [], blk)
333            val entry = IL.Node.mkENTRY ()            val cfg = IL.CFG.prependNode (IL.Node.mkENTRY(), cfg)
334            val exit = mkExit env            val cfg = IL.CFG.concat (cfg, mkExit env)
335            in            in
336              if IL.CFG.isEmpty cfg              (cfg, env)
               then IL.Node.addEdge (entry, exit)  
               else (  
                 IL.Node.addEdge (entry, IL.CFG.entry cfg);  
               (* NOTE: this addEdge could fail if all control paths end in DIE or STABILIZE,  
                * so we wrap it in a handler  
                *)  
                 IL.Node.addEdge (IL.CFG.exit cfg, exit) handle _ => ());  
             (IL.CFG{entry = entry, exit = exit}, env)  
337            end            end
338  (*DEBUG*)handle ex => raise ex  (*DEBUG*)handle ex => raise ex
339    
340  (* FIXME: the following function could be refactored with cvtTopLevelBlock to share code *)  (* FIXME: the following function could be refactored with cvtTopLevelBlock to share code *)
341      fun cvtFragmentBlock (env0, blk) = let      fun cvtFragmentBlock (env0, blk) = let
342            val (cfg, env) = cvtBlock ([], env0, [], blk)            val (cfg, env) = cvtBlock (([], []), env0, [], blk)
343            val entry = IL.Node.mkENTRY ()            val entry = IL.Node.mkENTRY ()
344          (* the live variables out are those that were not live coming in *)          (* the live variables out are those that were not live coming in *)
345            val liveOut = VMap.foldli            val liveOut = VMap.foldli
# Line 305  Line 356 
356            end            end
357  (*DEBUG*)handle ex => raise ex  (*DEBUG*)handle ex => raise ex
358    
359      fun cvtMethod (env, name, state, blk) = let      fun cvtMethod (env, name, state, svars, blk) = let
360          (* allocate fresh variables for the state variables *)          (* load the state into fresh variables *)
361              val (env, loadCFG) = let
362                  (* allocate shadow variables for the state variables *)
363            val (env, stateIn) = freshVars (env, state)            val (env, stateIn) = freshVars (env, state)
364                    fun load (x, x') = IL.ASSGN(x, IL.STATE x')
365                    in
366                      (env, IL.CFG.mkBlock (ListPair.map load (stateIn, svars)))
367                    end
368          (* convert the body of the method *)          (* convert the body of the method *)
369            val (cfg, env) = cvtBlock (state, env, [], blk)            val (cfg, env) = cvtBlock ((state, svars), env, [], blk)
370          (* add the entry/exit nodes *)          (* add the entry/exit nodes *)
           val stateOut = List.map (lookup env) state  
371            val entry = IL.Node.mkENTRY ()            val entry = IL.Node.mkENTRY ()
372            val exit = IL.Node.mkACTIVE stateOut            val loadCFG = IL.CFG.prependNode (entry, loadCFG)
373              val exit = (case name
374                     of StrandUtil.Update => IL.Node.mkACTIVE ()
375                      | StrandUtil.Stabilize => IL.Node.mkRETURN []
376                    (* end case *))
377              val body = IL.CFG.concat (loadCFG, cfg)
378    (*DEBUG**val _ = prEnv (StrandUtil.nameToString name, env);*)
379    (* FIXME: the following code doesn't work properly *)
380              val body = if IL.Node.hasSucc(IL.CFG.exit body)
381                    then IL.CFG.concat (body, saveStrandState (env, (state, svars), exit))
382                    else IL.CFG{entry = IL.CFG.entry body, exit = exit}
383            in            in
             if IL.CFG.isEmpty cfg  
               then IL.Node.addEdge (entry, exit)  
               else (  
                 IL.Node.addEdge (entry, IL.CFG.entry cfg);  
               (* NOTE: this addEdge could fail if all control paths end in DIE or STABILIZE,  
                * so we wrap it in a handler  
                *)  
                 IL.Node.addEdge (IL.CFG.exit cfg, exit) handle _ => ());  
384              IL.Method{              IL.Method{
385                  name = name,                  name = name,
386                  stateIn = stateIn,                  body = body
                 body = IL.CFG{entry = entry, exit = exit}  
387                }                }
388            end            end
389  (*DEBUG*)handle ex => (print(concat["error in cvtMethod(", Atom.toString name, ", ...)\n"]); raise ex)  (*DEBUG*)handle ex => (print(concat["error in cvtMethod(", StrandUtil.nameToString name, ", ...)\n"]); raise ex)
390    
391    (* convert the initially code *)    (* convert the initially code *)
392      fun cvtInitially (env, S.Initially{isArray, rangeInit, create, iters}) = let      fun cvtInitially (env, S.Initially{isArray, rangeInit, create, iters}) = let
# Line 353  Line 410 
410                }                }
411            end            end
412    
413      fun translate (S.Program{globals, globalInit, init, strands}) = let    (* check strands for properties *)
414            val (globalInit, env) =      fun checkProps strands = let
415                  cvtTopLevelBlock (            val hasDie = ref false
416                    VMap.empty, globalInit,            val hasNew = ref false
417                    fn env => IL.Node.mkRETURN(VMap.listItems env))            fun chkStm e = (case e
418                     of S.S_IfThenElse(_, b1, b2) => (chkBlk b1; chkBlk b2)
419                      | S.S_New _ => (hasNew := true)
420                      | S.S_Die => (hasDie := true)
421                      | _ => ()
422                  (* end case *))
423              and chkBlk (S.Block body) = List.app chkStm body
424              fun chkStrand (S.Strand{stateInit, methods, ...}) = let
425                    fun chkMeth (S.Method(_, body)) = chkBlk body
426                    in
427                      chkBlk stateInit;
428                      List.app chkMeth methods
429                    end
430              fun condCons (x, v, l) = if !x then v::l else l
431              in
432                List.app chkStrand strands;
433                condCons (hasDie, StrandUtil.StrandsMayDie,
434                condCons (hasNew, StrandUtil.NewStrands, []))
435              end
436    
437        fun translate (S.Program{globals, globalInit, funcs, init, strands}) = let
438              val (globalInit, env) = let
439                    fun mkExit env = let
440                          val nd = IL.Node.mkRETURN(VMap.listItems env)
441                          in
442                            IL.CFG{entry = nd, exit = nd}
443                          end
444                    in
445                      cvtTopLevelBlock (VMap.empty, globalInit, mkExit)
446                    end
447          (* construct a reduced environment that just defines the globals. *)          (* construct a reduced environment that just defines the globals. *)
448            val env = let            val env = let
449                  val lookup = lookup env                  val lookup = lookup env
# Line 379  Line 465 
465                        in                        in
466                          (env, List.rev params)                          (env, List.rev params)
467                        end                        end
468                  (* create the state variables *)
469                    val svars = let
470                          fun newSVar x = IL.StateVar.new (
471                                SimpleVar.kindOf x = S.StrandOutputVar,
472                                SimpleVar.nameOf x, cvtTy(SimpleVar.typeOf x))
473                          in
474                            List.map newSVar state
475                          end
476                (* convert the state initialization code *)                (* convert the state initialization code *)
477                  val (stateInit, env) = let                  val (stateInit, env) = let
478                        fun mkExit env = IL.Node.mkSINIT(List.map (lookup env) state)                        fun mkExit env = saveStrandState (env, (state, svars), IL.Node.mkSINIT())
479                        in                        in
480                          cvtTopLevelBlock (env, stateInit, mkExit)                          cvtTopLevelBlock (env, stateInit, mkExit)
481                        end                        end
482                (* the state-variable list is constructed by generating fresh variables for the                  fun cvtMeth (S.Method(name, blk)) = cvtMethod (env, name, state, svars, blk)
                * state variables and pairing them with a boolean that is true if the variable  
                * is an output variable.  Note that these IL variables are not defined or used.  
                *)  
                 val state' = let  
                       fun cvtStateVar x = (Var.kindOf x = S.StrandOutputVar, newVar x)  
                       in  
                         List.map cvtStateVar state  
                       end  
                 fun cvtMeth (S.Method(name, blk)) = cvtMethod (env, name, state, blk)  
483                  in                  in
484                    IL.Strand{                    IL.Strand{
485                        name = name,                        name = name,
486                        params = params,                        params = params,
487                        state = state',                        state = svars,
488                        stateInit = stateInit,                        stateInit = stateInit,
489                        methods = List.map cvtMeth methods                        methods = List.map cvtMeth methods
490                      }                      }
491                  end                  end
492            val prog = IL.Program{            val prog = IL.Program{
493                      props = checkProps strands,
494                    globalInit = globalInit,                    globalInit = globalInit,
495                    initially = init,                    initially = init,
496                    strands = List.map cvtStrand strands                    strands = List.map cvtStrand strands

Legend:
Removed from v.1339  
changed lines
  Added in v.2476

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