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 3485, Sun Dec 6 13:48:48 2015 UTC revision 3505, Fri Dec 18 02:47:03 2015 UTC
# Line 56  Line 56 
56            }            }
57        | FOREACH of {                    (* foreach-loop; this node combines aspects of the COND        | FOREACH of {                    (* foreach-loop; this node combines aspects of the COND
58                                           * and JOIN nodes. *)                                           * and JOIN nodes. *)
59              preds : node list ref,      (* the predecessors; the first item is the entry edge              pred : node ref,            (* the predecessor *)
                                          * and the others are the loop back edges. *)  
60              phis : phi list ref,        (* phi nodes (as in JOIN) *)              phis : phi list ref,        (* phi nodes (as in JOIN) *)
61              mask : bool list ref,       (* true for incoming fake edges *)              mask : bool list ref,       (* true for incoming fake edges *)
62              var : var,                  (* the loop variable *)              var : var,                  (* the loop variable *)
63              src : var,                  (* the source of values being iterated over *)              src : var,                  (* the source of values being iterated over *)
64              body : node ref,            (* the loop body *)              bodyEntry : node ref,       (* the loop body entry node *)
65                bodyExit : node ref,        (* the loop body exit node *)
66              succ : node ref             (* the loop-exit edge *)              succ : node ref             (* the loop-exit edge *)
67            }            }
68        | COM of  {                       (* comment *)        | COM of  {                       (* comment *)
# Line 101  Line 101 
101        | EXIT of {                       (* includes die and stabilize *)        | EXIT of {                       (* includes die and stabilize *)
102              pred : node ref,              pred : node ref,
103              kind : ExitKind.kind,       (* kind of exit node *)              kind : ExitKind.kind,       (* kind of exit node *)
             live : var list,            (* live variables *)  
104              succ : node option ref      (* optional fake control-flow edge for when the EXIT is *)              succ : node option ref      (* optional fake control-flow edge for when the EXIT is *)
105                                          (* not the CFG exit node *)                                          (* not the CFG exit node *)
106            }            }
# Line 163  Line 162 
162    
163    (***** Program representation *****)    (***** Program representation *****)
164    
165        type input = global_var Inputs.input
166    
167      datatype program = Program of {      datatype program = Program of {
168          props : Properties.t list,          props : Properties.t list,
169          consts : global_var list,       (* large constant variables *)          consts : global_var list,       (* large constant variables *)
170          inputs : global_var list,       (* global input variables *)          inputs : input list,            (* global input variables *)
         globals : global_var list,      (* other global variables *)  
171          constInit : cfg,                (* code that initializes constants and inputs *)          constInit : cfg,                (* code that initializes constants and inputs *)
172            globals : global_var list,      (* other global variables *)
173          globalInit : cfg,               (* CFG to initialize other globals (if any) *)          globalInit : cfg,               (* CFG to initialize other globals (if any) *)
174          strand : strand,                (* the strand definition *)          strand : strand,                (* the strand definition *)
175          create : create,                (* initial strand creation *)          create : create,                (* initial strand creation *)
# Line 366  Line 367 
367                  | GASSIGN{rhs, ...} => [rhs]                  | GASSIGN{rhs, ...} => [rhs]
368                  | NEW{args, ...} => args                  | NEW{args, ...} => args
369                  | SAVE{rhs, ...} => [rhs]                  | SAVE{rhs, ...} => [rhs]
                 | EXIT{live, ...} => live  
370                  | _ => []                  | _ => []
371                (* end case *))                (* end case *))
372          fun defs (ND{kind, ...}) = (case kind          fun defs (ND{kind, ...}) = (case kind
# Line 384  Line 384 
384                  trueBranch = ref dummy, falseBranch = ref dummy                  trueBranch = ref dummy, falseBranch = ref dummy
385                })                })
386          fun mkFOREACH (var, src) = new (FOREACH{          fun mkFOREACH (var, src) = new (FOREACH{
387                  preds = ref [],                  pred = ref dummy,
388                  phis = ref [], mask = ref [],                  phis = ref [], mask = ref [],
389                  var = var, src = src,                  var = var, src = src,
390                  body = ref dummy, succ = ref dummy                  bodyEntry = ref dummy,
391                    bodyExit = ref dummy,
392                    succ = ref dummy
393                })                })
394          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})
395          fun mkASSIGN (lhs, rhs) = (          fun mkASSIGN (lhs, rhs) = (
# Line 411  Line 413 
413          fun mkSAVE (lhs, rhs) = new (SAVE{          fun mkSAVE (lhs, rhs) = new (SAVE{
414                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy
415                })                })
416          fun mkEXIT (kind, xs) = new (EXIT{kind = kind, live = xs, pred = ref dummy, succ = ref NONE})          fun mkEXIT kind = new (EXIT{kind = kind, pred = ref dummy, succ = ref NONE})
417          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)          fun mkRETURN () = mkEXIT ExitKind.RETURN
418          fun mkRETURN () = mkEXIT (ExitKind.RETURN, [])          fun mkACTIVE () = mkEXIT ExitKind.ACTIVE
419          fun mkACTIVE () = mkEXIT (ExitKind.ACTIVE, [])          fun mkSTABILIZE () = mkEXIT ExitKind.STABILIZE
420          fun mkSTABILIZE () = mkEXIT (ExitKind.STABILIZE, [])          fun mkDIE () = mkEXIT ExitKind.DIE
421          fun mkDIE () = mkEXIT (ExitKind.DIE, [])          fun mkUNREACHABLE () = mkEXIT ExitKind.UNREACHABLE
         fun mkUNREACHABLE () = mkEXIT (ExitKind.UNREACHABLE, [])  
422          fun isNULL (ND{kind=NULL, ...}) = true          fun isNULL (ND{kind=NULL, ...}) = true
423            | isNULL _ = false            | isNULL _ = false
424        (* is a node reachable from the CFG entry; UNREACHABLE exit nodes and JOINs with no real        (* is a node reachable from the CFG entry; UNREACHABLE exit nodes and JOINs with no real
# Line 436  Line 437 
437                 of NULL => raise Fail("setPred on NULL node " ^ toString nd0)                 of NULL => raise Fail("setPred on NULL node " ^ toString nd0)
438                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)
439                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)
440                  | FOREACH{preds, ...} => preds := !preds @ [nd]                  | FOREACH{pred, ...} => pred := nd
441                  | COND{pred, ...} => pred := nd                  | COND{pred, ...} => pred := nd
442                  | COM{pred, ...} => pred := nd                  | COM{pred, ...} => pred := nd
443                  | ASSIGN{pred, ...} => pred := nd                  | ASSIGN{pred, ...} => pred := nd
# Line 451  Line 452 
452                  | ENTRY _ => []                  | ENTRY _ => []
453                  | JOIN{preds, ...} => !preds                  | JOIN{preds, ...} => !preds
454                  | COND{pred, ...} => [!pred]                  | COND{pred, ...} => [!pred]
455                  | FOREACH{preds, ...} => !preds                  | FOREACH{pred, bodyExit, ...} => [!pred, !bodyExit]
456                  | COM{pred, ...} => [!pred]                  | COM{pred, ...} => [!pred]
457                  | ASSIGN{pred, ...} => [!pred]                  | ASSIGN{pred, ...} => [!pred]
458                  | MASSIGN{pred, ...} => [!pred]                  | MASSIGN{pred, ...} => [!pred]
# Line 480  Line 481 
481                  | ENTRY{succ} => succ := nd                  | ENTRY{succ} => succ := nd
482                  | JOIN{succ, ...} => succ := nd                  | JOIN{succ, ...} => succ := nd
483                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)
484                  | FOREACH _ => raise Fail("setSucc on FOREACH node "^toString nd0)                  | FOREACH{succ, ...} => succ := nd
485                  | COM{succ, ...} => succ := nd                  | COM{succ, ...} => succ := nd
486                  | ASSIGN{succ, ...} => succ := nd                  | ASSIGN{succ, ...} => succ := nd
487                  | MASSIGN{succ, ...} => succ := nd                  | MASSIGN{succ, ...} => succ := nd
# Line 494  Line 495 
495                  | ENTRY{succ} => [!succ]                  | ENTRY{succ} => [!succ]
496                  | JOIN{succ, ...} => [!succ]                  | JOIN{succ, ...} => [!succ]
497                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]
498                  | FOREACH{body, succ, ...} => [!body, !succ]                  | FOREACH{bodyEntry, succ, ...} => [!bodyEntry, !succ]
499                  | COM{succ, ...} => [!succ]                  | COM{succ, ...} => [!succ]
500                  | ASSIGN{succ, ...} => [!succ]                  | ASSIGN{succ, ...} => [!succ]
501                  | MASSIGN{succ, ...} => [!succ]                  | MASSIGN{succ, ...} => [!succ]
# Line 509  Line 510 
510            | setTrueBranch (nd, _) = raise Fail("setTrueBranch on " ^ toString nd)            | setTrueBranch (nd, _) = raise Fail("setTrueBranch on " ^ toString nd)
511          fun setFalseBranch (ND{kind=COND{falseBranch, ...}, ...}, nd) = falseBranch := nd          fun setFalseBranch (ND{kind=COND{falseBranch, ...}, ...}, nd) = falseBranch := nd
512            | setFalseBranch (nd, _) = raise Fail("setFalseBranch on " ^ toString nd)            | setFalseBranch (nd, _) = raise Fail("setFalseBranch on " ^ toString nd)
513          fun setBodyBranch (ND{kind=FOREACH{body, ...}, ...}, nd) = body := nd          fun setBodyEntry (ND{kind=FOREACH{bodyEntry, ...}, ...}, nd) = bodyEntry := nd
514            | setBodyBranch (nd, _) = raise Fail("setBodyBranch on " ^ toString nd)            | setBodyEntry (nd, _) = raise Fail("setBodyEntry on " ^ toString nd)
515          fun setExitBranch (ND{kind=FOREACH{succ, ...}, ...}, nd) = succ := nd          fun setBodyExit (ND{kind=FOREACH{bodyExit, ...}, ...}, nd) = bodyExit := nd
516            | setExitBranch (nd, _) = raise Fail("setExitBranch on " ^ toString nd)            | setBodyExit (nd, _) = raise Fail("setBodyExit on " ^ toString nd)
517          fun setEdgeMask (ND{kind=JOIN{mask, ...}, ...}, mask') = mask := mask'          fun setEdgeMask (ND{kind=JOIN{mask, ...}, ...}, mask') = mask := mask'
518            | setEdgeMask (nd, _) = raise Fail("setEdgeMask on " ^ toString nd)            | setEdgeMask (nd, _) = raise Fail("setEdgeMask on " ^ toString nd)
519          fun addEdge (nd1, nd2) = (          fun addEdge (nd1, nd2) = (
# Line 524  Line 525 
525  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
526  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);
527  raise ex)  raise ex)
528          (* replace the edge src-->oldDst by the edge src-->dst *)
529          fun replaceInEdge {src, oldDst, dst} = (          fun replaceInEdge {src, oldDst, dst} = (
530              (* first set the successor of src *)              (* first set the successor of src *)
531                case kind src                case kind src
# Line 531  Line 533 
533                      if same(!trueBranch, oldDst)                      if same(!trueBranch, oldDst)
534                        then trueBranch := dst                        then trueBranch := dst
535                        else falseBranch := dst                        else falseBranch := dst
536                    | FOREACH{bodyEntry, succ, ...} =>
537                        if same(!bodyEntry, oldDst)
538                          then bodyEntry := dst
539                          else succ := dst
540                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
541                (* end case *);                (* end case *);
542              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
# Line 538  Line 544 
544  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
545  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);
546  raise ex)  raise ex)
547          (* replace the edge oldSrc-->dst by the edge src-->dst *)
548          fun replaceOutEdge {oldSrc, src, dst} = (          fun replaceOutEdge {oldSrc, src, dst} = (
549              (* first set the successor of src *)              (* first set the successor of src *)
550                case kind oldSrc                case kind oldSrc
# Line 545  Line 552 
552                      if same(!trueBranch, dst)                      if same(!trueBranch, dst)
553                        then setTrueBranch (src, dst)                        then setTrueBranch (src, dst)
554                        else setFalseBranch (src, dst)                        else setFalseBranch (src, dst)
555                    | FOREACH{bodyEntry, succ, ...} =>
556                        if same(!bodyEntry, dst)
557                          then setBodyEntry (src, dst)
558                          else setSucc (src, dst)
559                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
560                (* end case *);                (* end case *);
561              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
# Line 555  Line 566 
566                      in                      in
567                        preds := edit (!preds)                        preds := edit (!preds)
568                      end                      end
569                    | FOREACH{bodyExit, pred, ...} =>
570                        if same(!bodyExit, oldSrc)
571                          then bodyExit := src
572                          else pred := src
573                  | _ => setPred (dst, src)                  | _ => setPred (dst, src)
574                (* end case *))                (* end case *))
575  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
# Line 597  Line 612 
612          fun entry (CFG{entry = nd, ...}) = nd          fun entry (CFG{entry = nd, ...}) = nd
613          fun exit (CFG{exit = nd, ...}) = nd          fun exit (CFG{exit = nd, ...}) = nd
614    
       (* return the list of variables that are live at exit from a CFG *)  
         fun liveAtExit cfg = (case Node.kind(exit cfg)  
                of EXIT{live, ...} => live  
                 | _ => raise Fail "bogus exit node"  
               (* end case *))  
   
615        (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will        (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
616         * be in preorder with parents before children.         * be in preorder with parents before children.
617         *)         *)
# Line 794  Line 803 
803                      end                      end
804                  | _ => concat(cfg, mkBlock stms)                  | _ => concat(cfg, mkBlock stms)
805                (* end case *))                (* end case *))
   
       (* update the exit of a CFG by modifying the live variable list *)  
         fun updateExit (CFG{entry, exit as ND{kind, ...}}, f) = let  
               val newExit = (case kind  
                      of EXIT{pred, kind, live, succ=ref NONE} => let  
                           val newNd = Node.mkEXIT(kind, f live)  
                           in  
                             Node.replaceInEdge {src = !pred, oldDst = exit, dst = newNd};  
                             newNd  
                           end  
                       | _ => raise Fail "bogus exit node for updateExit"  
                     (* end case *))  
               in  
                 CFG{entry=entry, exit=newExit}  
               end  
806        end        end
807    
808      structure RHS =      structure RHS =

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

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