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

SCM Repository

[diderot] Diff of /branches/vis15/src/compiler/low-to-tree/low-to-tree.sml
ViewVC logotype

Diff of /branches/vis15/src/compiler/low-to-tree/low-to-tree.sml

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

revision 3853, Fri May 13 18:14:10 2016 UTC revision 3866, Mon May 16 16:48:13 2016 UTC
# Line 8  Line 8 
8    
9  structure LowToTree : sig  structure LowToTree : sig
10    
11      val translate : LowIR.program * Env.target_info -> TreeIR.program      val translate : LowIR.program * TreeIR.target_info -> TreeIR.program
12    
13    end = struct    end = struct
14    
# Line 71  Line 71 
71      local      local
72        val {peekFn : IR.var -> eq_var_rep option, setFn, ...} =        val {peekFn : IR.var -> eq_var_rep option, setFn, ...} =
73              V.newProp (fn x => raise Fail(V.toString x))              V.newProp (fn x => raise Fail(V.toString x))
74      in  
75      fun eqClassRepOf (env, x) = (case UnifyVars.eqClassOf x        fun repOf (env, x, x') = (case peekFn x'
            of SOME x' => (case peekFn x'  
76                   of SOME b => b                   of SOME b => b
77                    | NONE => let                    | NONE => let
78                        val rep = (case V.ty x'                    val rep = (case V.ty x
79                               of Ty.TensorTy[d] => VEC(Util.newVectorVars(Env.layoutVec env d))                               of Ty.TensorTy[d] => VEC(Util.newVectorVars(Env.layoutVec env d))
80                                | ty => VAR(Util.newLocalVar x)                                | ty => VAR(Util.newLocalVar x)
81                              (* end case *))                              (* end case *))
# Line 85  Line 84 
84                          rep                          rep
85                        end                        end
86                  (* end case *))                  (* end case *))
87        in
88    
89        fun eqClassRepOf (env, x) = (case UnifyVars.eqClassOf x
90               of SOME x' => repOf (env, x, x')
91              | NONE => NOEQ              | NONE => NOEQ
92            (* end case *))            (* end case *))
93    
94        fun useVar env = let
95              val useV = Env.useVar env
96              in
97                fn x => (case UnifyVars.eqClassOf x
98                      of SOME x' => (case repOf (env, x, x')
99                           of VAR x => Env.TREE(T.E_Var x)
100                            | VEC xs => let
101                                val Ty.TensorTy[d] = V.ty x
102                                in
103                                  Env.VEC(Env.layoutVec env d, List.map T.E_Var xs)
104                                end
105                            | NOEQ => raise Fail "impossible"
106                          (* end case *))
107                       | NONE => useV x
108                     (* end case *))
109              end
110      end      end
111    
112      fun mkBlock stms = T.Block{locals = ref [], body = stms}      fun mkBlock stms = T.Block{locals = ref [], body = stms}
113      fun mkIf (x, stms, []) = T.S_IfThen(x, mkBlock stms)      fun mkIf (x, stms, []) = T.S_IfThen(x, mkBlock stms)
114        | mkIf (x, stms1, stms2) = T.S_IfThenElse(x, mkBlock stms1, mkBlock stms2)        | mkIf (x, stms1, stms2) = T.S_IfThenElse(x, mkBlock stms1, mkBlock stms2)
115        fun mkAssign (x, e) = T.S_Assign(false, x, e)
116        fun mkDefn (x, e) = T.S_Assign(true, x, e)
117    
118      fun cvtScalarTy Ty.BoolTy = TTy.BoolTy      fun cvtScalarTy Ty.BoolTy = TTy.BoolTy
119        | cvtScalarTy Ty.IntTy = TTy.IntTy        | cvtScalarTy Ty.IntTy = TTy.IntTy
120        | cvtScalarTy (Ty.TensorTy[]) = TTy.realTy        | cvtScalarTy (Ty.TensorTy[]) = TTy.realTy
121        | cvtScalarTy ty = raise Fail(concat["cvtScalarTy(", Ty.toString ty, ")"])        | cvtScalarTy ty = raise Fail(concat["cvtScalarTy(", Ty.toString ty, ")"])
122    
123      (* define a new local variable and bind x to it. *)
124        fun newLocal (env, x) = let
125              val x' = Util.newLocalVar x
126              in
127                Env.bindSimple (env, x, Env.TREE(T.E_Var x'));
128                x'
129              end
130    
131    (* get a variable's binding as a single argument expression.  This means that    (* get a variable's binding as a single argument expression.  This means that
132     * if x is bound to a vector of expressions, then we need to pack it.     * if x is bound to a vector of expressions, then we need to pack it.
133     *)     *)
134      fun singleArg env x = (case Env.useVar env x      fun singleArg env x = (case useVar env x
135             of Env.TREE e => e             of Env.TREE e => e
136              | Env.VEC(layout, es) => T.E_Pack(layout, es)              | Env.VEC(layout, es) => T.E_Pack(layout, es)
137            (* end case *))            (* end case *))
138    
139      fun scalarArg env x = (case Env.useVar env x      fun scalarArg env x = (case useVar env x
140             of Env.TREE e => e             of Env.TREE e => e
141              | _ => raise Fail("expected scalar binding for " ^ IR.Var.toString x)              | _ => raise Fail("expected scalar binding for " ^ IR.Var.toString x)
142            (* end case *))            (* end case *))
143    
144      fun vectorArg (env, x) = (case Env.useVar env x      fun vectorArg (env, x) = (case useVar env x
145             of Env.TREE e => (case IR.Var.ty x             of Env.TREE e => (case V.ty x
146                   of Ty.TensorTy[d] => let                   of Ty.TensorTy[d] => let
147                        val layout = Env.layoutVec env d                        val layout = Env.layoutVec env d
148  (* QUESTION: can "e" be a complicated expression or are we guaranteed that it will just  (* QUESTION: can "e" be a complicated expression or are we guaranteed that it will just
# Line 124  Line 154 
154                        in                        in
155                          (layout, es)                          (layout, es)
156                        end                        end
157                    | ty => raise Fail("expected TensorTy[_], but found " ^ Ty.toString ty)                    | ty => raise Fail(concat[
158                            "expected ", V.toString x, " : TensorTy[_], but found " ^ Ty.toString ty
159                          ])
160                  (* end case *))                  (* end case *))
161              | Env.VEC(layout, es) => (layout, es)              | Env.VEC(layout, es) => (layout, es)
162            (* end case *))            (* end case *))
# Line 146  Line 178 
178            end            end
179    
180      fun trOp (env, srcRator, args) = let      fun trOp (env, srcRator, args) = let
 (* FIXME: if the use count of lhs is > 1, then we should bind to a local variable *)  
181            fun bindOp rator = Env.TREE(T.E_Op(rator, List.map (scalarArg env) args))            fun bindOp rator = Env.TREE(T.E_Op(rator, List.map (scalarArg env) args))
182            fun bindVOp rator = let            fun bindVOp rator = let
183                  val (layout, argss) = vectorArgs (env, args)                  val (layout, argss) = vectorArgs (env, args)
# Line 184  Line 215 
215                | Op.RLerp => bindOp TOp.RLerp                | Op.RLerp => bindOp TOp.RLerp
216                | Op.VAdd _ => bindVOp TOp.VAdd                | Op.VAdd _ => bindVOp TOp.VAdd
217                | Op.VSub _ => bindVOp TOp.VSub                | Op.VSub _ => bindVOp TOp.VSub
218                | Op.VScale _ => bindVOp TOp.VScale                | Op.VScale _ => let
219                      val [s, v] = args
220                      val s = scalarArg env s
221                      val (layout, vs) = vectorArg (env, v)
222                      val exps = ListPair.map
223                          (fn (w, x) => T.E_Op(TOp.VScale w, [s, x]))
224                            (#pieces layout, vs)
225                      in
226                        Env.VEC(layout, exps)
227                      end
228                | Op.VMul _ => bindVOp TOp.VMul                | Op.VMul _ => bindVOp TOp.VMul
229                | Op.VNeg _ => bindVOp TOp.VNeg                | Op.VNeg _ => bindVOp TOp.VNeg
230                | Op.VSum _ => raise Fail "FIXME: VSum"                | Op.VSum _ => let
231                      val [v] = args
232                      val ({pieces, ...}, es) = vectorArg (env, v)
233                      val e::es = ListPair.map (fn (w, v) => T.E_Op(TOp.VSum w, [v])) (pieces, es)
234                      in
235                        Env.TREE(List.foldr (fn (e, es) => T.E_Op(TOp.RAdd, [e, es])) e es)
236                      end
237                | Op.VIndex(_, i) => let                | Op.VIndex(_, i) => let
238                      val [v] = args
239  (* FIXME: more efficient to lookup the variable and avoid expanding TREE args *)  (* FIXME: more efficient to lookup the variable and avoid expanding TREE args *)
240                    val ({pieces, ...}, es) = vectorArg (env, hd args)                    val ({pieces, ...}, es) = vectorArg (env, v)
241                    fun select (i, w::ws, e::es) =                    fun select (i, w::ws, e::es) =
242                          if (i < w)                          if (i < w)
 (* FIXME: what if lhs is used more than once? *)  
243                            then Env.TREE(T.E_Op(TOp.VIndex(w, i), [e]))                            then Env.TREE(T.E_Op(TOp.VIndex(w, i), [e]))
244                            else select (i-w, ws, es)                            else select (i-w, ws, es)
245                      | select _ = raise Fail("bogus " ^ Op.toString srcRator)                      | select _ = raise Fail("bogus " ^ Op.toString srcRator)
246                    in                    in
247                      select (i, pieces, es)                      select (i, pieces, es)
248                    end                    end
249                | Op.VClamp n => bindVOp TOp.VClamp                | Op.VClamp n => let
250                      val [v, lo, hi] = args
251                      val (layout, vs) = vectorArg (env, v)
252                      val lo = scalarArg env lo
253                      val hi = scalarArg env hi
254                      val exps = ListPair.map
255                          (fn (w, x) => T.E_Op(TOp.VClamp w, [x, lo, hi]))
256                            (#pieces layout, vs)
257                      in
258                        Env.VEC(layout, exps)
259                      end
260                | Op.VMapClamp n => bindVOp TOp.VMapClamp                | Op.VMapClamp n => bindVOp TOp.VMapClamp
261                | Op.VLerp n => bindVOp TOp.VLerp                | Op.VLerp n => bindVOp TOp.VLerp
262                | Op.TensorIndex(ty, idxs) => bindOp(TOp.TensorIndex(Util.trType ty, idxs))                | Op.TensorIndex(ty, idxs) => bindOp(TOp.TensorIndex(Util.trType ty, idxs))
# Line 269  Line 325 
325           *)           *)
326            fun bindSimple rhs = (case eqClassRepOf(env, lhs)            fun bindSimple rhs = (case eqClassRepOf(env, lhs)
327                   of NOEQ =>(Env.bindSimple (env, lhs, Env.TREE rhs); [])                   of NOEQ =>(Env.bindSimple (env, lhs, Env.TREE rhs); [])
328                    | VAR x' => [T.S_Assign(x', rhs)]                    | VAR x' => [mkAssign(x', rhs)]
329                      | VEC _ => raise Fail "unexpected VEC"
330                    (* end case *))
331              fun assignOp (rator, args) = (case eqClassRepOf(env, lhs)
332                     of NOEQ =>
333                          [mkDefn(newLocal (env, lhs), T.E_Op(rator, List.map (scalarArg env) args))]
334                      | VAR x' => [mkAssign(x', T.E_Op(rator, List.map (scalarArg env) args))]
335                    | VEC _ => raise Fail "unexpected VEC"                    | VEC _ => raise Fail "unexpected VEC"
336                  (* end case *))                  (* end case *))
           fun assignOp (rator, args) = let  
 (* FIXME: what if lhs is EqClass var? *)  
                 val t = Util.newLocalVar lhs  
                 val stm = T.S_Assign(t, T.E_Op(rator, List.map (scalarArg env) args))  
                 in  
                   Env.bindSimple (env, lhs, Env.TREE(T.E_Var t));  
                   [stm]  
                 end  
337            in            in
338              case rhs              case rhs
339               of IR.GLOBAL x => bindSimple (T.E_Global(mkGlobalVar x))               of IR.GLOBAL x => bindSimple (T.E_Global(mkGlobalVar x))
# Line 287  Line 341 
341                    bindSimple (T.E_State(NONE, getStateVar fld))                    bindSimple (T.E_State(NONE, getStateVar fld))
342                | IR.STATE(SOME x, fld) =>                | IR.STATE(SOME x, fld) =>
343                    bindSimple (T.E_State(SOME(scalarArg env x), getStateVar fld))                    bindSimple (T.E_State(SOME(scalarArg env x), getStateVar fld))
344                | IR.VAR x => (case Env.useVar env x                | IR.VAR x => raise Fail "FIXME: VAR"
                    of Env.TREE e => ??  
                     | Env.VEC(layout, es) => ??  
                   (* end case *))  
345                | IR.LIT lit => bindSimple (T.E_Lit lit)                | IR.LIT lit => bindSimple (T.E_Lit lit)
346                | IR.OP(Op.EigenVecs2x2, args) => assignOp (TOp.EigenVecs2x2, args)                | IR.OP(Op.EigenVecs2x2, args) => assignOp (TOp.EigenVecs2x2, args)
347                | IR.OP(Op.EigenVecs3x3, args) => assignOp (TOp.EigenVecs3x3, args)                | IR.OP(Op.EigenVecs3x3, args) => assignOp (TOp.EigenVecs3x3, args)
# Line 298  Line 349 
349                | IR.OP(Op.EigenVals3x3, args) => assignOp (TOp.EigenVals3x3, args)                | IR.OP(Op.EigenVals3x3, args) => assignOp (TOp.EigenVals3x3, args)
350                | IR.OP(rator, args) => let                | IR.OP(rator, args) => let
351                    val rhs = trOp (env, rator, args)                    val rhs = trOp (env, rator, args)
352                      val needAssignment = (V.useCount lhs > 1) orelse (Env.isInlineOp env rator)
353                    in                    in
354                      if Env.isInlineOp env rator                      case (rhs, eqClassRepOf(env, lhs), needAssignment)
                       then (case (rhs, eqClassRepOf(env, lhs), V.useCount lhs > 1)  
355                            of (_, NOEQ, false) => (Env.bindSimple (env, lhs, rhs); [])                            of (_, NOEQ, false) => (Env.bindSimple (env, lhs, rhs); [])
356                             | (Env.TREE e, NOEQ, true) => let                        | (Env.TREE e, NOEQ, true) => [mkDefn(newLocal(env, lhs), e)]
357                                  val t = Util.newLocalVar lhs                        | (Env.TREE e, VAR x', _) => [mkAssign(x', e)]
                                 in  
                                   Env.bindSimple (env, lhs, Env.TREE(T.E_Var t));  
                                   [T.S_Assign(t, e)]  
                                 end  
                            | (Env.TREE e, VAR x', _) => [T.S_Assign(x', e)]  
358                             | (Env.VEC(layout, es), NOEQ, true) => let                             | (Env.VEC(layout, es), NOEQ, true) => let
359                                  val vs = Util.newVectorVars layout                                  val vs = Util.newVectorVars layout
360                                  in                                  in
361                                    Env.bindSimple (env, lhs, Env.VEC(layout, List.map T.E_Var vs));                                    Env.bindSimple (env, lhs, Env.VEC(layout, List.map T.E_Var vs));
362                                    ListPair.mapEq T.S_Assign (vs, es)                              ListPair.mapEq mkDefn (vs, es)
363                                  end                                  end
364                             | (Env.VEC(layout, es), VEC xs, _) => ??                        | (Env.VEC(layout, es), VEC xs, _) => ListPair.mapEq mkAssign (xs, es)
365                             | _ => raise Fail "inconsistent"                             | _ => raise Fail "inconsistent"
366                           (* end case *))                      (* end case *)
                       else ??  
367                    end                    end
368                | IR.CONS(args, Ty.TensorTy[d]) => let                | IR.CONS(args, Ty.TensorTy[d]) => let
369                    val {padded, pieces, ...} = Env.layoutVec env d                    val layout = Env.layoutVec env d
370                      fun mkVecs (args, w::ws) = let
371                          (* take arguments from args to build a vector value of width w; pad as
372                           * necessary.
373                           *)
374                            fun take (0, args, es) = T.E_Vec(w, List.rev es) :: mkVecs (args, ws)
375                              | take (i, [], es) = if #padded layout andalso null ws
376                                  then [T.E_Vec(w, List.rev es)]
377                                  else raise Fail "too few arguments for CONS"
378                              | take (i, arg::args, es) = take (i-1, args, scalarArg env arg :: es)
379                            in
380                              take (w, args, [])
381                            end
382                        | mkVecs ([], []) = []
383                        | mkVecs (_, []) = raise Fail "too many arguments for CONS"
384                      val es = mkVecs (args, #pieces layout)
385                      in
386                        case (eqClassRepOf(env, lhs), V.useCount lhs > 1)
387                         of (NOEQ, false) => (Env.bindVar(env, lhs, Env.VEC(layout, es)); [])
388                          | (NOEQ, true) => let
389                              val vs = Util.newVectorVars layout
390                    in                    in
391                      ??                              Env.bindSimple (env, lhs, Env.VEC(layout, List.map T.E_Var vs));
392                                ListPair.mapEq mkDefn (vs, es)
393                              end
394                          | (VEC xs, _) => ListPair.mapEq mkAssign (xs, es)
395                          | _ => raise Fail "inconsistent"
396                        (* end case *)
397                    end                    end
398                | IR.CONS(args, Ty.TensorTy shape) => ??                | IR.CONS(args, ty) => [
399                | IR.SEQ(args, ty) => ??                      mkDefn (
400                          newLocal(env, lhs),
401                          T.E_Cons(List.map (singleArg env) args, Util.trType ty))
402                      ]
403                  | IR.SEQ(args, ty) => [
404                        mkDefn (
405                          newLocal(env, lhs),
406                          T.E_Seq(List.map (singleArg env) args, Util.trType ty))
407                      ]
408                | rhs => raise Fail(concat["unexpected ", IR.RHS.toString rhs, " in LowIR code"])                | rhs => raise Fail(concat["unexpected ", IR.RHS.toString rhs, " in LowIR code"])
409              (* end case *)              (* end case *)
410            end            end
411    handle ex => (
412    print(concat["trAssign: ", V.toString lhs, " = ", IR.RHS.toString rhs, "\n"]);
413    raise ex)
414    
415    (* In order to reconstruct the block-structure from the CFG, we keep a stack of open ifs.    (* In order to reconstruct the block-structure from the CFG, we keep a stack of open ifs.
416     * the items on this stack distinguish between when we are processing the then and else     * the items on this stack distinguish between when we are processing the then and else
# Line 347  Line 428 
428        | ELSE_BR of T.stm list * T.exp * T.stm list * IR.node_kind        | ELSE_BR of T.stm list * T.exp * T.stm list * IR.node_kind
429    
430      fun trCFGWithEnv (env, cfg) = let      fun trCFGWithEnv (env, cfg) = let
431            fun useScalar x = (case Env.useVar env x            fun useScalar x = (case useVar env x
432                   of Env.TREE e => e                   of Env.TREE e => e
433                    | _ => raise Fail("expected scalar binding for " ^ V.toString x)                    | _ => raise Fail("expected scalar binding for " ^ V.toString x)
434                  (* end case *))                  (* end case *))
# Line 402  Line 483 
483                        end                        end
484                    | IR.FOREACH{var, src, bodyEntry, succ, ...} => let                    | IR.FOREACH{var, src, bodyEntry, succ, ...} => let
485                        val src = useScalar (!src)                        val src = useScalar (!src)
486                        val var = Util.newIterVar var                        val var' = Util.newIterVar var
487                        val stms = Env.flushPending (env, stms)                        val stms = Env.flushPending (env, stms)
488                          val _ = Env.bindSimple (env, var, Env.TREE(T.E_Var var'))
489                        val body = doNode (!bodyEntry, [], [])                        val body = doNode (!bodyEntry, [], [])
490                        val stm = T.S_Foreach(var, src, body)                        val stm = T.S_Foreach(var', src, body)
491                        in                        in
492                          doNode (!succ, ifStk, stm::stms)                          doNode (!succ, ifStk, stm::stms)
493                        end                        end
# Line 417  Line 499 
499                        in                        in
500                          doNode (!succ, ifStk, stms' @ stms)                          doNode (!succ, ifStk, stms' @ stms)
501                        end                        end
502                    | IR.MASSIGN{stm=(ys, rator, xs), succ, ...} => let                    | IR.MASSIGN{stm=([], Op.Print tys, xs), succ, ...} => let
503                        fun doLHSVar (y, ys) = let                        val stm = T.S_Print(List.map Util.trType tys, List.map (singleArg env) xs)
                             val t = Util.newLocalVar y  
                             in  
                               Env.bindSimple (env, y, Env.TREE(T.E_Var t));  
                               t::ys  
                             end  
                       val ys = List.foldr doLHSVar [] ys  
                       val rator = (case rator  
                              of Op.Print tys => TOp.Print(List.map Util.trType tys)  
                               | _ => raise Fail(concat[  
                                     "unexepected operator ", Op.toString rator, " for MASSIGN"  
                                   ])  
                             (* end case *))  
                       val stm = T.S_MAssign(ys, T.E_Op(rator, List.map (singleArg env) xs))  
504                        in                        in
505                          doNode (!succ, ifStk, stm :: stms)                          doNode (!succ, ifStk, stm :: stms)
506                        end                        end
507                      | IR.MASSIGN{stm=(ys, rator, xs), succ, ...} => raise Fail(concat[
508                            "unexepected operator ", Op.toString rator, " for MASSIGN"
509                          ])
510                    | IR.GASSIGN{lhs, rhs, succ, ...} => let                    | IR.GASSIGN{lhs, rhs, succ, ...} => let
511                        val stm = T.S_GAssign(mkGlobalVar lhs, singleArg env rhs)                        val stm = T.S_GAssign(mkGlobalVar lhs, singleArg env rhs)
512                        in                        in
# Line 468  Line 540 
540                        (* end case *))                        (* end case *))
541                  (* end case *))                  (* end case *))
542            in            in
543              ScopeVars.assignScopes (doNode (IR.CFG.entry cfg, [], []))              doNode (IR.CFG.entry cfg, [], [])
544            end            end
545    
546      fun trCFG info cfg = trCFGWithEnv (Env.new info, cfg)      fun trCFG info cfg = ScopeVars.assignScopes ([], trCFGWithEnv (Env.new info, cfg))
547    
548      fun trStrand info strand = let      fun trStrand info strand = let
549            val trCFG = trCFG info            val trCFG = trCFG info
550            val IR.Strand{name, params, state, stateInit, initM, updateM, stabilizeM} = strand            val IR.Strand{name, params, state, stateInit, initM, updateM, stabilizeM} = strand
551            val params' = List.map Util.newParamVar params            val params' = List.map Util.newParamVar params
           val env = Env.new info  
           val () = ListPair.appEq  
                 (fn (x, x') => Env.bindSimple (env, x, Env.TREE(T.E_Var x'))) (params, params')  
552            val state' = List.map getStateVar state            val state' = List.map getStateVar state
553              val stateInit' = let
554                    val env = Env.new info
555                    in
556                      ListPair.appEq
557                        (fn (x, x') => Env.bindSimple (env, x, Env.TREE(T.E_Var x')))
558                          (params, params');
559                      ScopeVars.assignScopes (params', trCFGWithEnv (env, stateInit))
560                    end
561            in            in
562              T.Strand{              T.Strand{
563                  name = name,                  name = name,
564                  params = params',                  params = params',
565                  state = state',                  state = state',
566                  stateInit = trCFGWithEnv (env, stateInit),                  stateInit = stateInit',
567                  initM = Option.map trCFG initM,                  initM = Option.map trCFG initM,
568                  updateM = trCFG updateM,                  updateM = trCFG updateM,
569                  stabilizeM = Option.map trCFG stabilizeM                  stabilizeM = Option.map trCFG stabilizeM
# Line 501  Line 578 
578            in            in
579              TreeIR.Program{              TreeIR.Program{
580                  props = props,                  props = props,
581                    target = info,
582                  consts = List.map mkGlobalVar consts,                  consts = List.map mkGlobalVar consts,
583                  inputs = List.map (Inputs.map mkGlobalVar) inputs,                  inputs = List.map (Inputs.map mkGlobalVar) inputs,
584                  constInit = trCFG constInit,                  constInit = trCFG constInit,

Legend:
Removed from v.3853  
changed lines
  Added in v.3866

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