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 3470, Mon Nov 30 17:51:33 2015 UTC revision 3506, Fri Dec 18 04:03:54 2015 UTC
# Line 5  Line 5 
5   * COPYRIGHT (c) 2015 The University of Chicago   * COPYRIGHT (c) 2015 The University of Chicago
6   * All rights reserved.   * All rights reserved.
7   *   *
8   * The SSAFn functor is used to generate the High, Med, and Low ILs in the Diderot   * The SSAFn functor is used to generate the High, Med, and Low IRs in the Diderot
9   * compiler.  These ILs have the same program and control-flow structure, but differ   * compiler.  These IRs have the same program and control-flow structure, but differ
10   * in their types and operators.   * in their types and operators.
11   *)   *)
12    
# Line 54  Line 54 
54              trueBranch : node ref,              trueBranch : node ref,
55              falseBranch : node ref              falseBranch : node ref
56            }            }
57          | FOREACH of {                    (* foreach-loop; this node combines aspects of the COND
58                                             * and JOIN nodes. *)
59                pred : node ref,            (* the predecessor *)
60                phis : phi list ref,        (* phi nodes (as in JOIN) *)
61                mask : bool list ref,       (* true for incoming fake edges *)
62                var : var,                  (* the loop variable *)
63                src : var,                  (* the source of values being iterated over *)
64                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 *)
67              }
68        | COM of  {                       (* comment *)        | COM of  {                       (* comment *)
69              pred : node ref,              pred : node ref,
70              text : string list,              text : string list,
# Line 90  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 127  Line 137 
137          id : Stamp.stamp,               (* variable's unique ID *)          id : Stamp.stamp,               (* variable's unique ID *)
138          name : string,                  (* variable's name *)          name : string,                  (* variable's name *)
139          ty : Ty.ty,                     (* variable's type *)          ty : Ty.ty,                     (* variable's type *)
140          input : bool,                   (* true for input variables *)          kind : global_kind,             (* the variable kind *)
141          props : PropList.holder          props : PropList.holder
142        }        }
143    
144        and global_kind = ConstVar | InputVar | GlobalVar
145    
146    (***** strand state variables *****)    (***** strand state variables *****)
147      and state_var = SV of {      and state_var = SV of {
148          id : Stamp.stamp,               (* variable's unique ID *)          id : Stamp.stamp,               (* variable's unique ID *)
# Line 152  Line 164 
164    
165    (***** Program representation *****)    (***** Program representation *****)
166    
167        type input = global_var Inputs.input
168    
169      datatype program = Program of {      datatype program = Program of {
170          props : Properties.t list,          props : Properties.t list,
171          globals : global_var list,      (* global variables (both input and non-input) *)          consts : global_var list,       (* large constant variables *)
172          inputInit : cfg,                (* CFG to initialize input globals (if any) *)          inputs : input list,            (* global input variables *)
173            constInit : cfg,                (* code that initializes constants and inputs *)
174            globals : global_var list,      (* other global variables *)
175          globalInit : cfg,               (* CFG to initialize other globals (if any) *)          globalInit : cfg,               (* CFG to initialize other globals (if any) *)
176          initially : initially,          strand : strand,                (* the strand definition *)
177          strands : strand list          create : create,                (* initial strand creation *)
178        }          update : cfg option             (* optional update code. *)
   
     and initially = Initially of {  
         isArray : bool,                 (* true for initially array, false for collection *)  
         rangeInit : cfg,                (* code to compute bounds of iteration *)  
         iters : (var * var * var) list, (* "for" i = min .. max *)  
         create : (cfg * Atom.atom * var list)  
179        }        }
180    
181      and strand = Strand of {      and strand = Strand of {
# Line 173  Line 183 
183          params : var list,          params : var list,
184          state : state_var list,          state : state_var list,
185          stateInit : cfg,          stateInit : cfg,
186          methods : method list          initM : cfg option,
187            updateM : cfg,
188            stabilizeM : cfg option
189        }        }
190    
191      and method = Method of {      and create = Create of {
192          name : StrandUtil.method_name,          dim : int option,               (* grid dimension; NONE for collections *)
193          body : cfg              (* method body *)          code : cfg                      (* the loop nest for creating the strands *)
194        }        }
195    
196      structure GlobalVar =      structure GlobalVar =
197        struct        struct
198          fun new (isIn, name, ty) = GV{          fun new (kind, name, ty) = GV{
199                  id = Stamp.new(),                  id = Stamp.new(),
200                  name = name,                  name = name,
201                  ty = ty,                  ty = ty,
202                  input = isIn,                  kind = kind,
203                  props = PropList.newHolder()                  props = PropList.newHolder()
204                }                }
205          fun name (GV{name, ...}) = name          fun name (GV{name, ...}) = name
206          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id          fun uniqueName (GV{id, name, ...}) = name ^ Stamp.toString id
207            fun kind (GV{kind, ...}) = kind
208          fun ty (GV{ty, ...}) = ty          fun ty (GV{ty, ...}) = ty
209          fun isInput (GV{input, ...}) = input          fun isInput (GV{kind=InputVar, ...}) = true
210              | isInput _ = false
211          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)          fun same (GV{id=a, ...}, GV{id=b, ...}) = Stamp.same(a, b)
212          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)          fun compare (GV{id=a, ...}, GV{id=b, ...}) = Stamp.compare(a, b)
213          fun hash (GV{id, ...}) = Stamp.hash id          fun hash (GV{id, ...}) = Stamp.hash id
# Line 313  Line 327 
327                        | ENTRY _ => "ENTRY"                        | ENTRY _ => "ENTRY"
328                        | JOIN _ => "JOIN"                        | JOIN _ => "JOIN"
329                        | COND _ => "COND"                        | COND _ => "COND"
330                          | FOREACH _ => "FOREACH"
331                        | COM _ => "COM"                        | COM _ => "COM"
332                        | ASSIGN _ => "ASSIGN"                        | ASSIGN _ => "ASSIGN"
333                        | MASSIGN _ => "MASSIGN"                        | MASSIGN _ => "MASSIGN"
# Line 335  Line 350 
350                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)                        List.foldr (fn ((_, xs), ys) => add(xs, ys)) [] (!phis)
351                      end                      end
352                  | COND{cond, ...} => [cond]                  | COND{cond, ...} => [cond]
353                    | FOREACH{src, phis, ...} => let
354                        fun add ([], ys) = ys
355                          | add (SOME x :: xs, ys) = add(xs, x::ys)
356                          | add (NONE :: xs, ys) = add(xs, ys)
357                        in
358                          List.foldr (fn ((_, xs), ys) => add(xs, ys)) [src] (!phis)
359                        end
360                  | ASSIGN{stm=(y, rhs), ...} => (case rhs                  | ASSIGN{stm=(y, rhs), ...} => (case rhs
361                       of GLOBAL _ => []                       of GLOBAL _ => []
362                        | STATE _ => []                        | STATE _ => []
# Line 349  Line 371 
371                  | GASSIGN{rhs, ...} => [rhs]                  | GASSIGN{rhs, ...} => [rhs]
372                  | NEW{args, ...} => args                  | NEW{args, ...} => args
373                  | SAVE{rhs, ...} => [rhs]                  | SAVE{rhs, ...} => [rhs]
                 | EXIT{live, ...} => live  
374                  | _ => []                  | _ => []
375                (* end case *))                (* end case *))
376          fun defs (ND{kind, ...}) = (case kind          fun defs (ND{kind, ...}) = (case kind
377                 of JOIN{phis, ...} => List.map #1 (!phis)                 of JOIN{phis, ...} => List.map #1 (!phis)
378                    | FOREACH{var, phis, ...} => var :: List.map #1 (!phis)
379                  | ASSIGN{stm=(y, _), ...} => [y]                  | ASSIGN{stm=(y, _), ...} => [y]
380                  | MASSIGN{stm=(ys, _, _), ...} => ys                  | MASSIGN{stm=(ys, _, _), ...} => ys
381                  | _ => []                  | _ => []
# Line 365  Line 387 
387                  pred = ref dummy, cond = cond,                  pred = ref dummy, cond = cond,
388                  trueBranch = ref dummy, falseBranch = ref dummy                  trueBranch = ref dummy, falseBranch = ref dummy
389                })                })
390            fun mkFOREACH (var, src) = new (FOREACH{
391                    pred = ref dummy,
392                    phis = ref [], mask = ref [],
393                    var = var, src = src,
394                    bodyEntry = ref dummy,
395                    bodyExit = ref dummy,
396                    succ = ref dummy
397                  })
398          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})
399          fun mkASSIGN (lhs, rhs) = (          fun mkASSIGN (lhs, rhs) = (
400                Var.setBinding (lhs, VB_RHS rhs);                Var.setBinding (lhs, VB_RHS rhs);
# Line 387  Line 417 
417          fun mkSAVE (lhs, rhs) = new (SAVE{          fun mkSAVE (lhs, rhs) = new (SAVE{
418                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy                  pred = ref dummy, lhs = lhs, rhs = rhs, succ = ref dummy
419                })                })
420          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})
421          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)          fun mkRETURN () = mkEXIT ExitKind.RETURN
422          fun mkSINIT () = mkEXIT (ExitKind.SINIT, [])          fun mkACTIVE () = mkEXIT ExitKind.ACTIVE
423          fun mkRETURN xs = mkEXIT (ExitKind.RETURN, xs)          fun mkSTABILIZE () = mkEXIT ExitKind.STABILIZE
424          fun mkACTIVE () = mkEXIT (ExitKind.ACTIVE, [])          fun mkDIE () = mkEXIT ExitKind.DIE
425          fun mkSTABILIZE () = mkEXIT (ExitKind.STABILIZE, [])          fun mkUNREACHABLE () = mkEXIT ExitKind.UNREACHABLE
         fun mkDIE () = mkEXIT (ExitKind.DIE, [])  
         fun mkUNREACHABLE () = mkEXIT (ExitKind.UNREACHABLE, [])  
426          fun isNULL (ND{kind=NULL, ...}) = true          fun isNULL (ND{kind=NULL, ...}) = true
427            | isNULL _ = false            | isNULL _ = false
428        (* 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 413  Line 441 
441                 of NULL => raise Fail("setPred on NULL node " ^ toString nd0)                 of NULL => raise Fail("setPred on NULL node " ^ toString nd0)
442                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)                  | ENTRY _ => raise Fail("setPred on ENTRY node " ^ toString nd0)
443                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)                  | JOIN{preds, ...} => preds := !preds @ [nd]  (* assume preds are added in order *)
444                    | FOREACH{pred, ...} => pred := nd
445                  | COND{pred, ...} => pred := nd                  | COND{pred, ...} => pred := nd
446                  | COM{pred, ...} => pred := nd                  | COM{pred, ...} => pred := nd
447                  | ASSIGN{pred, ...} => pred := nd                  | ASSIGN{pred, ...} => pred := nd
# Line 427  Line 456 
456                  | ENTRY _ => []                  | ENTRY _ => []
457                  | JOIN{preds, ...} => !preds                  | JOIN{preds, ...} => !preds
458                  | COND{pred, ...} => [!pred]                  | COND{pred, ...} => [!pred]
459                    | FOREACH{pred, bodyExit, ...} => [!pred, !bodyExit]
460                  | COM{pred, ...} => [!pred]                  | COM{pred, ...} => [!pred]
461                  | ASSIGN{pred, ...} => [!pred]                  | ASSIGN{pred, ...} => [!pred]
462                  | MASSIGN{pred, ...} => [!pred]                  | MASSIGN{pred, ...} => [!pred]
# Line 441  Line 471 
471                  | JOIN _ => true                  | JOIN _ => true
472                  | COND _ => true                  | COND _ => true
473                  | COM _ => true                  | COM _ => true
474                    | FOREACH _ => true
475                  | ASSIGN _ => true                  | ASSIGN _ => true
476                  | MASSIGN _ => true                  | MASSIGN _ => true
477                  | GASSIGN _ => true                  | GASSIGN _ => true
# Line 454  Line 485 
485                  | ENTRY{succ} => succ := nd                  | ENTRY{succ} => succ := nd
486                  | JOIN{succ, ...} => succ := nd                  | JOIN{succ, ...} => succ := nd
487                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)
488                    | FOREACH{succ, ...} => succ := nd
489                  | COM{succ, ...} => succ := nd                  | COM{succ, ...} => succ := nd
490                  | ASSIGN{succ, ...} => succ := nd                  | ASSIGN{succ, ...} => succ := nd
491                  | MASSIGN{succ, ...} => succ := nd                  | MASSIGN{succ, ...} => succ := nd
# Line 467  Line 499 
499                  | ENTRY{succ} => [!succ]                  | ENTRY{succ} => [!succ]
500                  | JOIN{succ, ...} => [!succ]                  | JOIN{succ, ...} => [!succ]
501                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]
502                    | FOREACH{bodyEntry, succ, ...} => [!bodyEntry, !succ]
503                  | COM{succ, ...} => [!succ]                  | COM{succ, ...} => [!succ]
504                  | ASSIGN{succ, ...} => [!succ]                  | ASSIGN{succ, ...} => [!succ]
505                  | MASSIGN{succ, ...} => [!succ]                  | MASSIGN{succ, ...} => [!succ]
# Line 481  Line 514 
514            | setTrueBranch (nd, _) = raise Fail("setTrueBranch on " ^ toString nd)            | setTrueBranch (nd, _) = raise Fail("setTrueBranch on " ^ toString nd)
515          fun setFalseBranch (ND{kind=COND{falseBranch, ...}, ...}, nd) = falseBranch := nd          fun setFalseBranch (ND{kind=COND{falseBranch, ...}, ...}, nd) = falseBranch := nd
516            | setFalseBranch (nd, _) = raise Fail("setFalseBranch on " ^ toString nd)            | setFalseBranch (nd, _) = raise Fail("setFalseBranch on " ^ toString nd)
517            fun setBodyEntry (ND{kind=FOREACH{bodyEntry, ...}, ...}, nd) = bodyEntry := nd
518              | setBodyEntry (nd, _) = raise Fail("setBodyEntry on " ^ toString nd)
519            fun setBodyExit (ND{kind=FOREACH{bodyExit, ...}, ...}, nd) = bodyExit := nd
520              | setBodyExit (nd, _) = raise Fail("setBodyExit on " ^ toString nd)
521          fun setEdgeMask (ND{kind=JOIN{mask, ...}, ...}, mask') = mask := mask'          fun setEdgeMask (ND{kind=JOIN{mask, ...}, ...}, mask') = mask := mask'
522            | setEdgeMask (nd, _) = raise Fail("setEdgeMask on " ^ toString nd)            | setEdgeMask (nd, _) = raise Fail("setEdgeMask on " ^ toString nd)
523          fun addEdge (nd1, nd2) = (          fun addEdge (nd1, nd2) = (
# Line 492  Line 529 
529  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
530  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);  print(concat["error in addEdge(", toString nd1, ",", toString nd2, ")\n"]);
531  raise ex)  raise ex)
532          (* replace the edge src-->oldDst by the edge src-->dst *)
533          fun replaceInEdge {src, oldDst, dst} = (          fun replaceInEdge {src, oldDst, dst} = (
534              (* first set the successor of src *)              (* first set the successor of src *)
535                case kind src                case kind src
# Line 499  Line 537 
537                      if same(!trueBranch, oldDst)                      if same(!trueBranch, oldDst)
538                        then trueBranch := dst                        then trueBranch := dst
539                        else falseBranch := dst                        else falseBranch := dst
540                    | FOREACH{bodyEntry, succ, ...} =>
541                        if same(!bodyEntry, oldDst)
542                          then bodyEntry := dst
543                          else succ := dst
544                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
545                (* end case *);                (* end case *);
546              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
# Line 506  Line 548 
548  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
549  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);  print(concat["error in replaceInEdge(", toString src, ",", toString oldDst, ",", toString dst, ")\n"]);
550  raise ex)  raise ex)
551          (* replace the edge oldSrc-->dst by the edge src-->dst *)
552          fun replaceOutEdge {oldSrc, src, dst} = (          fun replaceOutEdge {oldSrc, src, dst} = (
553              (* first set the successor of src *)              (* first set the successor of src *)
554                case kind oldSrc                case kind oldSrc
# Line 513  Line 556 
556                      if same(!trueBranch, dst)                      if same(!trueBranch, dst)
557                        then setTrueBranch (src, dst)                        then setTrueBranch (src, dst)
558                        else setFalseBranch (src, dst)                        else setFalseBranch (src, dst)
559                    | FOREACH{bodyEntry, succ, ...} =>
560                        if same(!bodyEntry, dst)
561                          then setBodyEntry (src, dst)
562                          else setSucc (src, dst)
563                  | _ => setSucc (src, dst)                  | _ => setSucc (src, dst)
564                (* end case *);                (* end case *);
565              (* then set the predecessor of dst *)              (* then set the predecessor of dst *)
# Line 523  Line 570 
570                      in                      in
571                        preds := edit (!preds)                        preds := edit (!preds)
572                      end                      end
573                    | FOREACH{bodyExit, pred, ...} =>
574                        if same(!bodyExit, oldSrc)
575                          then bodyExit := src
576                          else pred := src
577                  | _ => setPred (dst, src)                  | _ => setPred (dst, src)
578                (* end case *))                (* end case *))
579  (*DEBUG*)handle ex => (  (*DEBUG*)handle ex => (
# Line 565  Line 616 
616          fun entry (CFG{entry = nd, ...}) = nd          fun entry (CFG{entry = nd, ...}) = nd
617          fun exit (CFG{exit = nd, ...}) = nd          fun exit (CFG{exit = nd, ...}) = nd
618    
       (* 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 *))  
   
619        (* 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
620         * be in preorder with parents before children.         * be in preorder with parents before children.
621         *)         *)
# Line 762  Line 807 
807                      end                      end
808                  | _ => concat(cfg, mkBlock stms)                  | _ => concat(cfg, mkBlock stms)
809                (* 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  
810        end        end
811    
812      structure RHS =      structure RHS =

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

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