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 3505, Fri Dec 18 02:47:03 2015 UTC revision 3550, Wed Jan 6 15:51:57 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 *)
# Line 131  Line 133 
133                                          (* n'th result of operator in multi-assignment *)                                          (* n'th result of operator in multi-assignment *)
134        | VB_PHI of var option list       (* defined by a phi node *)        | VB_PHI of var option list       (* defined by a phi node *)
135        | VB_PARAM                        (* parameter to a strand *)        | VB_PARAM                        (* parameter to a strand *)
136          | VB_ITER                         (* bound in a foreach loop *)
137    
138    (***** global variables *****)    (***** global variables *****)
139      and global_var = GV of {      and global_var = GV of {
140          id : Stamp.stamp,               (* variable's unique ID *)          id : Stamp.stamp,               (* variable's unique ID *)
141          name : string,                  (* variable's name *)          name : string,                  (* variable's name *)
142          ty : Ty.ty,                     (* variable's type *)          ty : Ty.ty,                     (* variable's type *)
143          input : bool,                   (* true for input variables *)          kind : global_kind,             (* the variable kind *)
144            updated : bool,                 (* true if the global variable is modified in the *)
145                                            (* global-update code *)
146            binding : var option ref,       (* the local variable used to define this global variable
147                                             * (i.e., in a GASSIGN node).  This field will be NONE
148                                             * for mutable variables.
149                                             *)
150            useCnt : int ref,               (* count of uses *)
151          props : PropList.holder          props : PropList.holder
152        }        }
153    
# Line 193  Line 203 
203    
204      structure GlobalVar =      structure GlobalVar =
205        struct        struct
206          fun new (isIn, name, ty) = GV{          fun new (kind, isUpdated, name, ty) = GV{
207                  id = Stamp.new(),                  id = Stamp.new(),
208                  name = name,                  name = name,
209                  ty = ty,                  ty = ty,
210                  input = isIn,                  kind = kind,
211                    updated = isUpdated,
212                    binding = ref NONE,
213                    useCnt = ref 0,
214                  props = PropList.newHolder()                  props = PropList.newHolder()
215                }                }
216          fun name (GV{name, ...}) = name          fun name (GV{name, ...}) = name
217          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id
218            fun kind (GV{kind, ...}) = kind
219            fun isUpdated (GV{updated, ...}) = updated
220            fun bindingOf (GV{binding, ...}) = !binding
221            fun setBinding (GV{binding, ...}, x) = (binding := SOME x)
222          fun ty (GV{ty, ...}) = ty          fun ty (GV{ty, ...}) = ty
223          fun isInput (GV{input, ...}) = input          fun isInput (GV{kind=InputVar, ...}) = true
224              | isInput _ = false
225            fun useCount (GV{useCnt, ...}) = !useCnt
226          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)
227          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)
228          fun hash (GV{id, ...}) = Stamp.hash id          fun hash (GV{id, ...}) = Stamp.hash id
# Line 345  Line 364 
364                      in                      in
365                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)
366                      end                      end
367                  | COND{cond, ...} => [cond]                  | COND{cond, ...} => [!cond]
368                  | FOREACH{src, phis, ...} => let                  | FOREACH{src, phis, ...} => let
369                      fun add ([], ys) = ys                      fun add ([], ys) = ys
370                        | add (SOME x :: xs, ys) = add(xs, x::ys)                        | add (SOME x :: xs, ys) = add(xs, x::ys)
371                        | add (NONE :: xs, ys) = add(xs, ys)                        | add (NONE :: xs, ys) = add(xs, ys)
372                      in                      in
373                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [src] (!phis)                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [!src] (!phis)
374                      end                      end
375                  | ASSIGN{stm=(y, rhs), ...} => (case rhs                  | ASSIGN{stm=(y, rhs), ...} => (case rhs
376                       of GLOBAL _ => []                       of GLOBAL _ => []
# Line 380  Line 399 
399          fun mkENTRY () = new (ENTRY{succ = ref dummy})          fun mkENTRY () = new (ENTRY{succ = ref dummy})
400          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})
401          fun mkCOND cond = new (COND{          fun mkCOND cond = new (COND{
402                  pred = ref dummy, cond = cond,                  pred = ref dummy, cond = ref cond,
403                  trueBranch = ref dummy, falseBranch = ref dummy                  trueBranch = ref dummy, falseBranch = ref dummy
404                })                })
405          fun mkFOREACH (var, src) = new (FOREACH{          fun mkFOREACH (var, src) = (
406                  Var.setBinding (var, VB_ITER);
407                  new (FOREACH{
408                  pred = ref dummy,                  pred = ref dummy,
409                  phis = ref [], mask = ref [],                  phis = ref [], mask = ref [],
410                  var = var, src = src,                    var = var, src = ref src,
411                  bodyEntry = ref dummy,                  bodyEntry = ref dummy,
412                  bodyExit = ref dummy,                  bodyExit = ref dummy,
413                  succ = ref dummy                  succ = ref dummy
414                })                  }))
415          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})
416          fun mkASSIGN (lhs, rhs) = (          fun mkASSIGN (lhs, rhs) = (
417                Var.setBinding (lhs, VB_RHS rhs);                Var.setBinding (lhs, VB_RHS rhs);
# Line 525  Line 546 
546  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
547  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);
548  raise ex)  raise ex)
549    (* FIXME: the names replaceInEdge and replaceOutEdge are backwards! *)
550        (* replace the edge src-->oldDst by the edge src-->dst *)        (* replace the edge src-->oldDst by the edge src-->dst *)
551          fun replaceInEdge {src, oldDst, dst} = (          fun replaceInEdge {src, oldDst, dst} = (
552              (* first set the successor of src *)              (* first set the successor of src *)
# Line 540  Line 562 
562                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
563                (* end case *);                (* end case *);
564              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
565                setPred (dst, src))                case kind oldDst
566                   of FOREACH{bodyExit, pred, ...} =>
567                        if same(!bodyExit, src)
568                          then setBodyExit (dst, src)
569                          else setPred (dst, src)
570                    | _ => setPred (dst, src)
571                  (* end case *))
572  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
573  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);
574  raise ex)  raise ex)
# Line 664  Line 692 
692                        in                        in
693                          preds := edit (!preds)                          preds := edit (!preds)
694                        end                        end
695                      | FOREACH{pred=pred', bodyExit, ...} =>
696                          if Node.same(!pred', nd)
697                            then pred' := pred
698                            else bodyExit := pred
699                    | _ => Node.setPred (succ, pred)                    | _ => Node.setPred (succ, pred)
700                  (* end case *);                  (* end case *);
701                (* 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 673  Line 705 
705                        * situation where both branches are the same node.                        * situation where both branches are the same node.
706                        *)                        *)
707                         if Node.same(!trueBranch, nd)                         if Node.same(!trueBranch, nd)
708                           then Node.setTrueBranch(pred, succ)                           then trueBranch := succ
709                           else ();                           else ();
710                         if Node.same(!falseBranch, nd)                         if Node.same(!falseBranch, nd)
711                           then Node.setFalseBranch(pred, succ)                           then falseBranch := succ
712                           else ())                           else ())
713                      | FOREACH{bodyEntry, succ=succ', ...} =>
714                          if Node.same(!bodyEntry, nd)
715                            then bodyEntry := succ
716                            else succ' := succ
717                    | _ => Node.setSucc (pred, succ)                    | _ => Node.setSucc (pred, succ)
718                  (* end case *)                  (* end case *)
719                end                end
# Line 866  Line 902 
902                        "<", Ty.toString ty, ">{",                        "<", Ty.toString ty, ">{",
903                        String.concatWithMap "," Var.toString xs, "}"                        String.concatWithMap "," Var.toString xs, "}"
904                      ]                      ]
 (* FIXME: proper printing of Ein applications *)  
905                  | EINAPP(ein, xs) => String.concat [                  | EINAPP(ein, xs) => String.concat [
906                        "EIN(", String.concatWithMap "," Var.toString xs, ")"                        EinPP.toString ein, " (",
907                          String.concatWithMap "," Var.toString xs, ")"
908                      ]                      ]
909                (* end case *))                (* end case *))
910        end        end
# Line 885  Line 921 
921              String.concatWithMap "," (fn NONE => "_" | SOME x => Var.toString x) xs, ")"              String.concatWithMap "," (fn NONE => "_" | SOME x => Var.toString x) xs, ")"
922            ]            ]
923        | vbToString VB_PARAM = "PARAM"        | vbToString VB_PARAM = "PARAM"
924          | vbToString VB_ITER = "ITER"
925    
926    (* return a string representation of a PHI node *)    (* return a string representation of a PHI node *)
927      fun phiToString (y, xs) = String.concat [      fun phiToString (y, xs) = String.concat [

Legend:
Removed from v.3505  
changed lines
  Added in v.3550

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