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

SCM Repository

[diderot] Diff of /branches/vis12-cl/src/compiler/IL/ssa-fn.sml
ViewVC logotype

Diff of /branches/vis12-cl/src/compiler/IL/ssa-fn.sml

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

revision 2824, Mon Nov 10 17:06:01 2014 UTC revision 2825, Mon Nov 10 21:06:31 2014 UTC
# Line 40  Line 40 
40              succ : node ref              succ : node ref
41            }            }
42        | JOIN of {        | JOIN of {
43              preds : node list ref,              preds : node list ref,      (* includes fake control-flow edges *)
44              phis : phi list ref,              mask : bool list ref,       (* true for incoming fake edges *)
45                phis : phi list ref,        (* data-flow joins corresponding to the edges in preds *)
46              succ : node ref              succ : node ref
47            }            }
48        | COND of {        | COND of {
# Line 86  Line 87 
87        | EXIT of {                       (* includes die and stabilize *)        | EXIT of {                       (* includes die and stabilize *)
88              pred : node ref,              pred : node ref,
89              kind : ExitKind.kind,       (* kind of exit node *)              kind : ExitKind.kind,       (* kind of exit node *)
90              live : var list             (* live variables *)              live : var list,            (* live variables *)
91                succ : node option ref      (* optional fake control-flow edge for when the EXIT is *)
92                                            (* not the CFG exit node *)
93            }            }
94    
95      and rhs      and rhs
# Line 112  Line 115 
115        | VB_RHS of rhs                   (* defined by an assignment (includes globals and state variables) *)        | VB_RHS of rhs                   (* defined by an assignment (includes globals and state variables) *)
116        | VB_MULTIOP of int * Op.rator * var list        | VB_MULTIOP of int * Op.rator * var list
117                                          (* n'th result of operator in multi-assignment *)                                          (* n'th result of operator in multi-assignment *)
118        | VB_PHI of var list              (* defined by a phi node *)        | VB_PHI of var option list       (* defined by a phi node *)
119        | VB_PARAM                        (* parameter to a strand *)        | VB_PARAM                        (* parameter to a strand *)
120    
121    (***** global variables *****)    (***** global variables *****)
# Line 137  Line 140 
140    
141      withtype assign = (var * rhs)      withtype assign = (var * rhs)
142           and massign = (var list * Op.rator * var list)           and massign = (var list * Op.rator * var list)
143           and phi = (var * var list)           and phi = (var * var option list)      (* NONE for fake edges *)
144    
145      datatype assignment      datatype assignment
146        = ASSGN of assign        = ASSGN of assign
# Line 327  Line 330 
330          fun new kind = ND{id = Stamp.new(), props = PropList.newHolder(), kind = kind}          fun new kind = ND{id = Stamp.new(), props = PropList.newHolder(), kind = kind}
331        (* variable defs and uses *)        (* variable defs and uses *)
332          fun uses (ND{kind, ...}) = (case kind          fun uses (ND{kind, ...}) = (case kind
333                 of JOIN{phis, ...} => List.foldr (fn ((_, xs), ys) => xs@ys) [] (!phis)                 of JOIN{phis, ...} => let
334                        fun add ([], ys) = ys
335                          | add (SOME x :: xs, ys) = add(xs, x::ys)
336                          | add (NONE :: xs, ys) = add(xs, ys)
337                        in
338                          List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)
339                        end
340                  | COND{cond, ...} => [cond]                  | COND{cond, ...} => [cond]
341                  | ASSIGN{stm=(y, rhs), ...} => (case rhs                  | ASSIGN{stm=(y, rhs), ...} => (case rhs
342                       of GLOBAL _ => []                       of GLOBAL _ => []
# Line 353  Line 362 
362                (* end case *))                (* end case *))
363          val dummy = new NULL          val dummy = new NULL
364          fun mkENTRY () = new (ENTRY{succ = ref dummy})          fun mkENTRY () = new (ENTRY{succ = ref dummy})
365          fun mkJOIN phis = new (JOIN{preds = ref [], phis = ref phis, succ = ref dummy})          fun mkJOIN phis = new (JOIN{preds = ref [], mask = ref [], phis = ref phis, succ = ref dummy})
366          fun mkCOND {cond, trueBranch, falseBranch} = new (COND{          fun mkCOND {cond, trueBranch, falseBranch} = new (COND{
367                  pred = ref dummy, cond = cond,                  pred = ref dummy, cond = cond,
368                  trueBranch = ref trueBranch, falseBranch = ref falseBranch                  trueBranch = ref trueBranch, falseBranch = ref falseBranch
# Line 380  Line 389 
389          fun mkSAVE (lhs, rhs) = new (SAVE{          fun mkSAVE (lhs, rhs) = new (SAVE{
390                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy
391                })                })
392          fun mkEXIT (kind, xs) = new (EXIT{kind = kind, live = xs, pred = ref dummy})          fun mkEXIT (kind, xs) = new (EXIT{kind = kind, live = xs, pred = ref dummy, succ = ref NONE})
393          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)
394          fun mkSINIT () = mkEXIT (ExitKind.SINIT, [])          fun mkSINIT () = mkEXIT (ExitKind.SINIT, [])
395          fun mkRETURN xs = mkEXIT (ExitKind.RETURN, xs)          fun mkRETURN xs = mkEXIT (ExitKind.RETURN, xs)
396          fun mkACTIVE () = mkEXIT (ExitKind.ACTIVE, [])          fun mkACTIVE () = mkEXIT (ExitKind.ACTIVE, [])
397          fun mkSTABILIZE () = mkEXIT (ExitKind.STABILIZE, [])          fun mkSTABILIZE () = mkEXIT (ExitKind.STABILIZE, [])
398          fun mkDIE () = mkEXIT (ExitKind.DIE, [])          fun mkDIE () = mkEXIT (ExitKind.DIE, [])
399            fun mkUNREACHABLE () = mkEXIT (ExitKind.UNREACHABLE, [])
400          fun isNULL (ND{kind=NULL, ...}) = true          fun isNULL (ND{kind=NULL, ...}) = true
401            | isNULL _ = false            | isNULL _ = false
402          (* is a node reachable from the CFG entry; UNREACHABLE exit nodes and JOINs with no real
403           * predecessors are unreachable.
404           *)
405            fun isReachable (ND{kind=EXIT{kind=ExitKind.UNREACHABLE, ...}, ...}) = false
406              | isReachable (ND{kind=JOIN{mask, ...}, ...}) = List.exists not (!mask)
407              | isReachable _ = true
408        (* editing node edges *)        (* editing node edges *)
409          fun hasPred (ND{kind, ...}) = (case kind          fun hasPred (ND{kind, ...}) = (case kind
410                 of NULL => false                 of NULL => false
# Line 434  Line 450 
450                  | GASSIGN _ => true                  | GASSIGN _ => true
451                  | NEW _ => true                  | NEW _ => true
452                  | SAVE _ => true                  | SAVE _ => true
453                    | EXIT{succ=ref(SOME _), ...} => true
454                  | EXIT _ => false                  | EXIT _ => false
455                (* end case *))                (* end case *))
456          fun setSucc (nd0 as ND{kind, ...}, nd) = (case kind          fun setSucc (nd0 as ND{kind, ...}, nd) = (case kind
# Line 447  Line 464 
464                  | GASSIGN{succ, ...} => succ := nd                  | GASSIGN{succ, ...} => succ := nd
465                  | NEW{succ, ...} => succ := nd                  | NEW{succ, ...} => succ := nd
466                  | SAVE{succ, ...} => succ := nd                  | SAVE{succ, ...} => succ := nd
467                  | EXIT _ => raise Fail("setSucc on EXIT node "^toString nd0)                  | EXIT{succ, ...} => succ := SOME nd
468                (* end case *))                (* end case *))
469          fun succs (nd as ND{kind, ...}) = (case kind          fun succs (ND{kind, ...}) = (case kind
470                 of NULL => [] (*raise Fail("succs on NULL node "^toString nd)*)                 of NULL => [] (*raise Fail("succs on NULL node "^toString nd)*)
471                  | ENTRY{succ} => [!succ]                  | ENTRY{succ} => [!succ]
472                  | JOIN{succ, ...} => [!succ]                  | JOIN{succ, ...} => [!succ]
# Line 460  Line 477 
477                  | GASSIGN{succ, ...} => [!succ]                  | GASSIGN{succ, ...} => [!succ]
478                  | NEW{succ, ...} => [!succ]                  | NEW{succ, ...} => [!succ]
479                  | SAVE{succ, ...} => [!succ]                  | SAVE{succ, ...} => [!succ]
480                    | EXIT{succ=ref(SOME nd), ...} => [nd]
481                  | EXIT _ => []                  | EXIT _ => []
482                (* end case *))                (* end case *))
483          fun setTrueBranch (ND{kind=COND{trueBranch, ...}, ...}, nd) = trueBranch := nd          fun setTrueBranch (ND{kind=COND{trueBranch, ...}, ...}, nd) = trueBranch := nd
# Line 634  Line 652 
652                  | SAVE{pred, succ, ...} => (                  | SAVE{pred, succ, ...} => (
653                      Node.replaceInEdge {src = !pred, oldDst = oldNd, dst = node};                      Node.replaceInEdge {src = !pred, oldDst = oldNd, dst = node};
654                      Node.replaceOutEdge {oldSrc = oldNd, src = node, dst = !succ})                      Node.replaceOutEdge {oldSrc = oldNd, src = node, dst = !succ})
655                  | EXIT{pred, ...} =>                  | EXIT{pred, succ=ref NONE, ...} =>
656                      Node.replaceInEdge {src = !pred, oldDst = oldNd, dst = node}                      Node.replaceInEdge {src = !pred, oldDst = oldNd, dst = node}
657                  | _ => raise Fail(concat[                  | _ => raise Fail(concat[
658                        "unsupported replaceNode(", Node.toString oldNd, ", ", Node.toString node, ")"                        "unsupported replaceNode(", Node.toString oldNd, ", ", Node.toString node, ")"
# Line 712  Line 730 
730                (* end case *))                (* end case *))
731    
732        (* insert a block of assignments at the end of the CFG argument  If the CFG has an EXIT        (* insert a block of assignments at the end of the CFG argument  If the CFG has an EXIT
733         * node, then the block is inserted immediatly following the exit.         * node, then the block is inserted immediatly before the exit.
734         *)         *)
735          fun appendBlock (cfg, []) = cfg          fun appendBlock (cfg, []) = cfg
736            | appendBlock (cfg as CFG{entry, exit}, stms) = (case exit            | appendBlock (cfg as CFG{entry, exit}, stms) = (case exit
# Line 739  Line 757 
757        (* update the exit of a CFG by modifying the live variable list *)        (* update the exit of a CFG by modifying the live variable list *)
758          fun updateExit (CFG{entry, exit as ND{kind, ...}}, f) = let          fun updateExit (CFG{entry, exit as ND{kind, ...}}, f) = let
759                val newExit = (case kind                val newExit = (case kind
760                       of EXIT{pred, kind, live} => let                       of EXIT{pred, kind, live, succ=ref NONE} => let
761                            val newNd = Node.mkEXIT(kind, f live)                            val newNd = Node.mkEXIT(kind, f live)
762                            in                            in
763                              Node.replaceInEdge {src = !pred, oldDst = exit, dst = newNd};                              Node.replaceInEdge {src = !pred, oldDst = exit, dst = newNd};
# Line 821  Line 839 
839              "[", String.concatWith "," (List.map Var.toString xs), "])"              "[", String.concatWith "," (List.map Var.toString xs), "])"
840            ]            ]
841        | vbToString (VB_PHI xs) = concat[        | vbToString (VB_PHI xs) = concat[
842              "PHI(", String.concatWith "," (List.map Var.toString xs), ")"              "PHI(",
843                String.concatWith "," (List.map (fn NONE => "_" | SOME x => Var.toString x) xs), ")"
844            ]            ]
845        | vbToString VB_PARAM = "PARAM"        | vbToString VB_PARAM = "PARAM"
846    
847    (* return a string representation of a PHI node *)    (* return a string representation of a PHI node *)
848      fun phiToString (y, xs) = String.concat [      fun phiToString (y, xs) = String.concat [
849              Ty.toString(Var.ty y), " ", Var.toString y, " = PHI(",              Ty.toString(Var.ty y), " ", Var.toString y, " = PHI(",
850              String.concatWith "," (List.map Var.toString xs), ")"              String.concatWith "," (List.map (fn NONE => "_" | SOME x => Var.toString x) xs), ")"
851            ]            ]
852    
853    (* return a string representation of an assignment *)    (* return a string representation of an assignment *)

Legend:
Removed from v.2824  
changed lines
  Added in v.2825

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