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

SCM Repository

[diderot] Diff of /branches/vis15/src/compiler/cfg-ir/ssa-fn.sml
ViewVC logotype

Diff of /branches/vis15/src/compiler/cfg-ir/ssa-fn.sml

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

revision 3506, Fri Dec 18 04:03:54 2015 UTC revision 3840, Mon May 9 20:42:08 2016 UTC
# Line 12  Line 12 
12    
13  functor SSAFn (  functor SSAFn (
14    
15      val ilName : string      val irName : string
16    
17      structure Ty : SSA_TYPES      structure Ty : SSA_TYPES
18      structure Op : OPERATORS where type ty = Ty.ty      structure Op : OPERATORS where type ty = Ty.ty
# Line 22  Line 22 
22      structure Ty = Ty      structure Ty = Ty
23      structure Op = Op      structure Op = Op
24    
25      val ilName = ilName      val irName = irName
26    
27    (***** CFG *****)    (***** CFG *****)
28    
29        datatype global_kind = datatype GlobalVarKind.t
30    
31      datatype cfg = CFG of {      datatype cfg = CFG of {
32          entry : node,   (* the entry node of a graph; not necessarily an ENTRY node *)          entry : node,   (* the entry node of a graph; not necessarily an ENTRY node *)
33          exit : node     (* the exit node of a graph; not necessarily an EXIT node. *)          exit : node     (* the exit node of a graph; not necessarily an EXIT node. *)
# Line 50  Line 52 
52            }            }
53        | COND of {        | COND of {
54              pred : node ref,              pred : node ref,
55              cond : var,              cond : var ref,             (* the variable being tested (we use a ref to allow rewriting) *)
56              trueBranch : node ref,              trueBranch : node ref,
57              falseBranch : node ref              falseBranch : node ref
58            }            }
# Line 60  Line 62 
62              phis : phi list ref,        (* phi nodes (as in JOIN) *)              phis : phi list ref,        (* phi nodes (as in JOIN) *)
63              mask : bool list ref,       (* true for incoming fake edges *)              mask : bool list ref,       (* true for incoming fake edges *)
64              var : var,                  (* the loop variable *)              var : var,                  (* the loop variable *)
65              src : var,                  (* the source of values being iterated over *)              src : var ref,              (* the source of values being iterated over *)
66              bodyEntry : node ref,       (* the loop body entry node *)              bodyEntry : node ref,       (* the loop body entry node *)
67              bodyExit : node ref,        (* the loop body exit node *)              bodyExit : node ref,        (* the loop body exit node *)
68              succ : node ref             (* the loop-exit edge *)              succ : node ref             (* the loop-exit edge *)
69            }            }
70          | NEXT of {                       (* a loop-body exit node *)
71                pred : node ref,            (* the predecessor *)
72                succ : node ref             (* the FOREACH node *)
73              }
74        | COM of  {                       (* comment *)        | COM of  {                       (* comment *)
75              pred : node ref,              pred : node ref,
76              text : string list,              text : string list,
# Line 131  Line 137 
137                                          (* n'th result of operator in multi-assignment *)                                          (* n'th result of operator in multi-assignment *)
138        | VB_PHI of var option list       (* defined by a phi node *)        | VB_PHI of var option list       (* defined by a phi node *)
139        | VB_PARAM                        (* parameter to a strand *)        | VB_PARAM                        (* parameter to a strand *)
140          | VB_ITER                         (* bound in a foreach loop *)
141    
142    (***** global variables *****)    (***** global variables *****)
143      and global_var = GV of {      and global_var = GV of {
# Line 138  Line 145 
145          name : string,                  (* variable's name *)          name : string,                  (* variable's name *)
146          ty : Ty.ty,                     (* variable's type *)          ty : Ty.ty,                     (* variable's type *)
147          kind : global_kind,             (* the variable kind *)          kind : global_kind,             (* the variable kind *)
148            updated : bool,                 (* true if the global variable is modified in the *)
149                                            (* global-update code *)
150            binding : var option ref,       (* the local variable used to define this global variable
151                                             * (i.e., in a GASSIGN node).  This field will be NONE
152                                             * for mutable variables.
153                                             *)
154            useCnt : int ref,               (* count of uses *)
155          props : PropList.holder          props : PropList.holder
156        }        }
157    
     and global_kind = ConstVar | InputVar | GlobalVar  
   
158    (***** strand state variables *****)    (***** strand state variables *****)
159      and state_var = SV of {      and state_var = SV of {
160          id : Stamp.stamp,               (* variable's unique ID *)          id : Stamp.stamp,               (* variable's unique ID *)
161          name : string,                  (* variable's name *)          name : string,                  (* variable's name *)
162          ty : Ty.ty,                     (* variable's type *)          ty : Ty.ty,                     (* variable's type *)
163          output : bool,                  (* true for output variables *)          output : bool,                  (* true for output variables *)
164            varying : bool,                 (* true for variables that are modified during super steps *)
165            shared : bool,                  (* true for variables that are read by other strands *)
166          props : PropList.holder          props : PropList.holder
167        }        }
168    
# Line 195  Line 209 
209    
210      structure GlobalVar =      structure GlobalVar =
211        struct        struct
212          fun new (kind, name, ty) = GV{          fun new (kind, isUpdated, name, ty) = GV{
213                  id = Stamp.new(),                  id = Stamp.new(),
214                  name = name,                  name = name,
215                  ty = ty,                  ty = ty,
216                  kind = kind,                  kind = kind,
217                    updated = isUpdated,
218                    binding = ref NONE,
219                    useCnt = ref 0,
220                  props = PropList.newHolder()                  props = PropList.newHolder()
221                }                }
222          fun name (GV{name, ...}) = name          fun name (GV{name, ...}) = name
223          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id
224          fun kind (GV{kind, ...}) = kind          fun kind (GV{kind, ...}) = kind
225            fun isUpdated (GV{updated, ...}) = updated
226            fun bindingOf (GV{binding, ...}) = !binding
227            fun setBinding (GV{binding, ...}, x) = (binding := SOME x)
228          fun ty (GV{ty, ...}) = ty          fun ty (GV{ty, ...}) = ty
229          fun isInput (GV{kind=InputVar, ...}) = true          fun isInput (GV{kind=InputVar, ...}) = true
230            | isInput _ = false            | isInput _ = false
231            fun useCount (GV{useCnt, ...}) = !useCnt
232          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)
233          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)
234          fun hash (GV{id, ...}) = Stamp.hash id          fun hash (GV{id, ...}) = Stamp.hash id
# Line 236  Line 257 
257    
258      structure StateVar =      structure StateVar =
259        struct        struct
260          fun new (isOut, name, ty) = SV{          fun new (isOut, name, ty, varying, shared) = SV{
261                  id = Stamp.new(),                  id = Stamp.new(),
262                  name = name,                  name = name,
263                  ty = ty,                  ty = ty,
264                  output = isOut,                  output = isOut,
265                    varying = varying,
266                    shared = shared,
267                  props = PropList.newHolder()                  props = PropList.newHolder()
268                }                }
269          fun name (SV{name, ...}) = name          fun name (SV{name, ...}) = name
270          fun ty (SV{ty, ...}) = ty          fun ty (SV{ty, ...}) = ty
271          fun isOutput (SV{output, ...}) = output          fun isOutput (SV{output, ...}) = output
272            fun isVarying (SV{varying, ...}) = varying
273            fun isShared (SV{shared, ...}) = shared
274          fun same (SV{id=a, ...}, SV{id=b, ...}) = Stamp.same(a, b)          fun same (SV{id=a, ...}, SV{id=b, ...}) = Stamp.same(a, b)
275          fun compare (SV{id=a, ...}, SV{id=b, ...}) = Stamp.compare(a, b)          fun compare (SV{id=a, ...}, SV{id=b, ...}) = Stamp.compare(a, b)
276          fun hash (SV{id, ...}) = Stamp.hash id          fun hash (SV{id, ...}) = Stamp.hash id
# Line 292  Line 317 
317          fun compare (V{id=a, ...}, V{id=b, ...}) = Stamp.compare(a, b)          fun compare (V{id=a, ...}, V{id=b, ...}) = Stamp.compare(a, b)
318          fun hash (V{id, ...}) = Stamp.hash id          fun hash (V{id, ...}) = Stamp.hash id
319          fun toString (V{name, id, ...}) = name ^ Stamp.toString id          fun toString (V{name, id, ...}) = name ^ Stamp.toString id
320            fun getDef x = (case binding x
321                   of VB_RHS rhs => (case rhs
322                         of GLOBAL gv => if GlobalVar.isInput gv
323                              then rhs (* inputs could be different at runtime! *)
324                              else (case GlobalVar.bindingOf gv
325                                 of SOME x => getDef x
326                                  | NONE => rhs
327                                (* end case *))
328                          | VAR x => getDef x
329                          | _ => rhs
330                        (* end case *))
331                    | _ => VAR x
332                  (* end case *))
333        (* properties *)        (* properties *)
334          fun newProp initFn = PropList.newProp (fn (V{props, ...}) => props, initFn)          fun newProp initFn = PropList.newProp (fn (V{props, ...}) => props, initFn)
335          fun newFlag () = PropList.newFlag (fn (V{props, ...}) => props)          fun newFlag () = PropList.newFlag (fn (V{props, ...}) => props)
# Line 328  Line 366 
366                        | JOIN _ => "JOIN"                        | JOIN _ => "JOIN"
367                        | COND _ => "COND"                        | COND _ => "COND"
368                        | FOREACH _ => "FOREACH"                        | FOREACH _ => "FOREACH"
369                          | NEXT _ => "NEXT"
370                        | COM _ => "COM"                        | COM _ => "COM"
371                        | ASSIGN _ => "ASSIGN"                        | ASSIGN _ => "ASSIGN"
372                        | MASSIGN _ => "MASSIGN"                        | MASSIGN _ => "MASSIGN"
# Line 349  Line 388 
388                      in                      in
389                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)
390                      end                      end
391                  | COND{cond, ...} => [cond]                  | COND{cond, ...} => [!cond]
392                  | FOREACH{src, phis, ...} => let                  | FOREACH{src, phis, ...} => let
393                      fun add ([], ys) = ys                      fun add ([], ys) = ys
394                        | add (SOME x :: xs, ys) = add(xs, x::ys)                        | add (SOME x :: xs, ys) = add(xs, x::ys)
395                        | add (NONE :: xs, ys) = add(xs, ys)                        | add (NONE :: xs, ys) = add(xs, ys)
396                      in                      in
397                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [src] (!phis)                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [!src] (!phis)
398                      end                      end
399                    | NEXT _ => []
400                  | ASSIGN{stm=(y, rhs), ...} => (case rhs                  | ASSIGN{stm=(y, rhs), ...} => (case rhs
401                       of GLOBAL _ => []                       of GLOBAL _ => []
402                        | STATE _ => []                        | STATE _ => []
# Line 384  Line 424 
424          fun mkENTRY () = new (ENTRY{succ = ref dummy})          fun mkENTRY () = new (ENTRY{succ = ref dummy})
425          fun mkJOIN phis = new (JOIN{preds = ref [], mask = ref [], phis = ref phis, succ = ref dummy})          fun mkJOIN phis = new (JOIN{preds = ref [], mask = ref [], phis = ref phis, succ = ref dummy})
426          fun mkCOND cond = new (COND{          fun mkCOND cond = new (COND{
427                  pred = ref dummy, cond = cond,                  pred = ref dummy, cond = ref cond,
428                  trueBranch = ref dummy, falseBranch = ref dummy                  trueBranch = ref dummy, falseBranch = ref dummy
429                })                })
430          fun mkFOREACH (var, src) = new (FOREACH{          fun mkFOREACH (var, src) = (
431                  Var.setBinding (var, VB_ITER);
432                  new (FOREACH{
433                  pred = ref dummy,                  pred = ref dummy,
434                  phis = ref [], mask = ref [],                  phis = ref [], mask = ref [],
435                  var = var, src = src,                    var = var, src = ref src,
436                  bodyEntry = ref dummy,                  bodyEntry = ref dummy,
437                  bodyExit = ref dummy,                  bodyExit = ref dummy,
438                  succ = ref dummy                  succ = ref dummy
439                })                  }))
440            fun mkNEXT () = new(NEXT{pred = ref dummy, succ = ref dummy})
441          fun mkCOM text = new (COM{pred = ref dummy, text = text, succ = ref dummy})          fun mkCOM text = new (COM{pred = ref dummy, text = text, succ = ref dummy})
442          fun mkASSIGN (lhs, rhs) = (          fun mkASSIGN (lhs, rhs) = (
443                Var.setBinding (lhs, VB_RHS rhs);                Var.setBinding (lhs, VB_RHS rhs);
# Line 408  Line 451 
451                  setB (0, lhs);                  setB (0, lhs);
452                  new (MASSIGN{pred = ref dummy, stm = (lhs, rator, args), succ = ref dummy})                  new (MASSIGN{pred = ref dummy, stm = (lhs, rator, args), succ = ref dummy})
453                end                end
454          fun mkGASSIGN (lhs, rhs) = new (GASSIGN{          fun mkGASSIGN (lhs, rhs) = (
455                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy                if not(GlobalVar.isUpdated lhs) then GlobalVar.setBinding(lhs, rhs) else ();
456                })                new (GASSIGN{pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy}))
457          fun mkNEW {strand, args} = new (NEW{          fun mkNEW {strand, args} = new (NEW{
458                  pred = ref dummy, strand = strand, args = args, succ = ref dummy                  pred = ref dummy, strand = strand, args = args, succ = ref dummy
459                })                })
# Line 442  Line 485 
485                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)
486                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)
487                  | FOREACH{pred, ...} => pred := nd                  | FOREACH{pred, ...} => pred := nd
488                    | NEXT{pred, ...} => pred := nd
489                  | COND{pred, ...} => pred := nd                  | COND{pred, ...} => pred := nd
490                  | COM{pred, ...} => pred := nd                  | COM{pred, ...} => pred := nd
491                  | ASSIGN{pred, ...} => pred := nd                  | ASSIGN{pred, ...} => pred := nd
# Line 457  Line 501 
501                  | JOIN{preds, ...} => !preds                  | JOIN{preds, ...} => !preds
502                  | COND{pred, ...} => [!pred]                  | COND{pred, ...} => [!pred]
503                  | FOREACH{pred, bodyExit, ...} => [!pred, !bodyExit]                  | FOREACH{pred, bodyExit, ...} => [!pred, !bodyExit]
504                    | NEXT{pred, ...} => [!pred]
505                  | COM{pred, ...} => [!pred]                  | COM{pred, ...} => [!pred]
506                  | ASSIGN{pred, ...} => [!pred]                  | ASSIGN{pred, ...} => [!pred]
507                  | MASSIGN{pred, ...} => [!pred]                  | MASSIGN{pred, ...} => [!pred]
# Line 472  Line 517 
517                  | COND _ => true                  | COND _ => true
518                  | COM _ => true                  | COM _ => true
519                  | FOREACH _ => true                  | FOREACH _ => true
520                    | NEXT _ => true
521                  | ASSIGN _ => true                  | ASSIGN _ => true
522                  | MASSIGN _ => true                  | MASSIGN _ => true
523                  | GASSIGN _ => true                  | GASSIGN _ => true
# Line 486  Line 532 
532                  | JOIN{succ, ...} => succ := nd                  | JOIN{succ, ...} => succ := nd
533                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)
534                  | FOREACH{succ, ...} => succ := nd                  | FOREACH{succ, ...} => succ := nd
535                    | NEXT{succ, ...} => succ := nd
536                  | COM{succ, ...} => succ := nd                  | COM{succ, ...} => succ := nd
537                  | ASSIGN{succ, ...} => succ := nd                  | ASSIGN{succ, ...} => succ := nd
538                  | MASSIGN{succ, ...} => succ := nd                  | MASSIGN{succ, ...} => succ := nd
# Line 500  Line 547 
547                  | JOIN{succ, ...} => [!succ]                  | JOIN{succ, ...} => [!succ]
548                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]
549                  | FOREACH{bodyEntry, succ, ...} => [!bodyEntry, !succ]                  | FOREACH{bodyEntry, succ, ...} => [!bodyEntry, !succ]
550                    | NEXT{succ, ...} => [!succ]
551                  | COM{succ, ...} => [!succ]                  | COM{succ, ...} => [!succ]
552                  | ASSIGN{succ, ...} => [!succ]                  | ASSIGN{succ, ...} => [!succ]
553                  | MASSIGN{succ, ...} => [!succ]                  | MASSIGN{succ, ...} => [!succ]
# Line 529  Line 577 
577  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
578  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);
579  raise ex)  raise ex)
580    (* FIXME: the names replaceInEdge and replaceOutEdge are backwards! *)
581        (* replace the edge src-->oldDst by the edge src-->dst *)        (* replace the edge src-->oldDst by the edge src-->dst *)
582          fun replaceInEdge {src, oldDst, dst} = (          fun replaceInEdge {src, oldDst, dst} = (
583              (* first set the successor of src *)              (* first set the successor of src *)
# Line 544  Line 593 
593                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
594                (* end case *);                (* end case *);
595              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
596                setPred (dst, src))                case kind oldDst
597                   of FOREACH{bodyExit, pred, ...} =>
598                        if same(!bodyExit, src)
599                          then setBodyExit (dst, src)
600                          else setPred (dst, src)
601                    | _ => setPred (dst, src)
602                  (* end case *))
603  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
604  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);
605  raise ex)  raise ex)
# Line 668  Line 723 
723                        in                        in
724                          preds := edit (!preds)                          preds := edit (!preds)
725                        end                        end
726                      | FOREACH{pred=pred', bodyExit, ...} =>
727                          if Node.same(!pred', nd)
728                            then pred' := pred
729                            else bodyExit := pred
730                      | NEXT _ => raise Fail "deleteNode(NEXT)"
731                    | _ => Node.setPred (succ, pred)                    | _ => Node.setPred (succ, pred)
732                  (* end case *);                  (* end case *);
733                (* replace the successor edge from pred to nd with an edge from pred to succ *)                (* replace the successor edge from pred to nd with an edge from pred to succ *)
# Line 677  Line 737 
737                        * situation where both branches are the same node.                        * situation where both branches are the same node.
738                        *)                        *)
739                         if Node.same(!trueBranch, nd)                         if Node.same(!trueBranch, nd)
740                           then Node.setTrueBranch(pred, succ)                           then trueBranch := succ
741                           else ();                           else ();
742                         if Node.same(!falseBranch, nd)                         if Node.same(!falseBranch, nd)
743                           then Node.setFalseBranch(pred, succ)                           then falseBranch := succ
744                           else ())                           else ())
745                      | FOREACH{bodyEntry, succ=succ', ...} =>
746                          if Node.same(!bodyEntry, nd)
747                            then bodyEntry := succ
748                            else succ' := succ
749                    | _ => Node.setSucc (pred, succ)                    | _ => Node.setSucc (pred, succ)
750                  (* end case *)                  (* end case *)
751                end                end
# Line 787  Line 851 
851         * node, then the block is inserted immediatly before the exit.         * node, then the block is inserted immediatly before the exit.
852         *)         *)
853          fun appendBlock (cfg, []) = cfg          fun appendBlock (cfg, []) = cfg
854            | appendBlock (cfg as CFG{entry, exit}, stms) = (case exit            | appendBlock (cfg as CFG{entry, exit}, stms) = let
                of ND{kind=EXIT{pred, ...}, ...} => let  
855                      fun mkNode (ASSGN stm) = Node.mkASSIGN stm                      fun mkNode (ASSGN stm) = Node.mkASSIGN stm
856                        | mkNode (MASSGN stm) = Node.mkMASSIGN stm                        | mkNode (MASSGN stm) = Node.mkMASSIGN stm
857                        | mkNode (GASSGN stm) = Node.mkGASSIGN stm                        | mkNode (GASSGN stm) = Node.mkGASSIGN stm
# Line 799  Line 862 
862                              Node.addEdge (prev, nd);                              Node.addEdge (prev, nd);
863                              nd                              nd
864                            end                            end
865                  in
866                    case exit
867                     of ND{kind=EXIT{pred, ...}, ...} => let
868                          val last = List.foldl f (!pred) stms
869                          in
870                            pred := last;
871                            Node.setSucc(last, exit);
872                            cfg
873                          end
874                      | ND{kind=NEXT{pred, ...}, ...} => let
875                      val last = List.foldl f (!pred) stms                      val last = List.foldl f (!pred) stms
876                      in                      in
877                        pred := last;                        pred := last;
# Line 806  Line 879 
879                        cfg                        cfg
880                      end                      end
881                  | _ => concat(cfg, mkBlock stms)                  | _ => concat(cfg, mkBlock stms)
882                (* end case *))                  (* end case *)
883                  end
884        end        end
885    
886      structure RHS =      structure RHS =
# Line 870  Line 944 
944                        "<", Ty.toString ty, ">{",                        "<", Ty.toString ty, ">{",
945                        String.concatWithMap "," Var.toString xs, "}"                        String.concatWithMap "," Var.toString xs, "}"
946                      ]                      ]
 (* FIXME: proper printing of Ein applications *)  
947                  | EINAPP(ein, xs) => String.concat [                  | EINAPP(ein, xs) => String.concat [
948                        "EIN(", String.concatWithMap "," Var.toString xs, ")"                        EinPP.toString ein, " (",
949                          String.concatWithMap "," Var.toString xs, ")"
950                      ]                      ]
951                (* end case *))                (* end case *))
952        end        end
# Line 889  Line 963 
963              String.concatWithMap "," (fn NONE => "_" | SOME x => Var.toString x) xs, ")"              String.concatWithMap "," (fn NONE => "_" | SOME x => Var.toString x) xs, ")"
964            ]            ]
965        | vbToString VB_PARAM = "PARAM"        | vbToString VB_PARAM = "PARAM"
966          | vbToString VB_ITER = "ITER"
967    
968    (* return a string representation of a PHI node *)    (* return a string representation of a PHI node *)
969      fun phiToString (y, xs) = String.concat [      fun phiToString (y, xs) = String.concat [

Legend:
Removed from v.3506  
changed lines
  Added in v.3840

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