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

SCM Repository

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

Diff of /branches/pure-cfg/src/compiler/IL/ssa-fn.sml

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

revision 477, Sat Nov 13 16:02:07 2010 UTC revision 478, Sun Nov 14 04:15:48 2010 UTC
# Line 2  Line 2 
2   *   *
3   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
  *  
  * The IL is a combination of a block-structured tree and an SSA control-flow  
  * graph of blocks.  
5   *)   *)
6    
7  signature SSA =  signature SSA =
# Line 15  Line 12 
12    
13    (***** CFG *****)    (***** CFG *****)
14    
15      datatype node = ND of {      datatype cfg = CFG of {
16            entry : node ref,       (* the entry node of a graph; not necessarily an ENTRY node *)
17            exit : node ref         (* the exit node of a graph; not necessarily a DIE, STABILIZE,
18                                     * or EXIT node.
19                                     *)
20          }
21    
22        and node = ND of {
23          id : Stamp.stamp,          id : Stamp.stamp,
24          props : PropList.holder,          props : PropList.holder,
25          kind : node_kind          kind : node_kind
# Line 28  Line 32 
32            }            }
33        | JOIN of {        | JOIN of {
34              preds : node list ref,              preds : node list ref,
35              phis : (var * var list) list ref,   (* phi statements *)              phis : phi list ref,
36              succ : node ref              succ : node ref
37            }            }
38        | COND of {        | COND of {
# Line 37  Line 41 
41              trueBranch : node ref,              trueBranch : node ref,
42              falseBranch : node ref              falseBranch : node ref
43            }            }
44        | BLOCK of {        | COM of  {                       (* comment *)
45              pred : node ref,              pred : node ref,
46              body : assign list ref,              stm : assign,
47              succ : node ref              succ : node ref
48            }            }
49        | NEW of {        | ASSIGN of {                     (* assignment *)
50                pred : node ref,
51                stm : assign,
52                succ : node ref
53              }
54          | NEW of {                        (* create new actor instance *)
55              pred : node ref,              pred : node ref,
56              actor : Atom.atom,              actor : Atom.atom,
57              args : var list,              args : var list,
# Line 58  Line 67 
67              pred : node ref              pred : node ref
68            }            }
69    
   (***** Statements *****)  
   
     and stmt = STM of {  
         id : Stamp.stamp,  
         props : PropList.holder,  
         kind : stmt_kind,  
         next : stmt option              (* next statement at this structural level *)  
       }  
   
     and stmt_kind  
       = S_SIMPLE of node                (* ENTRY, JOIN, BLOCK, NEW, DIE, STABILIZE, or EXIT node *)  
       | S_IF of {  
             cond : node,                (* COND node *)  
             thenBranch : stmt,  
             elseBranch : stmt  
           }  
       | S_LOOP of {  
             hdr : stmt,  
             cond : node,                (* COND node *)  
             body : stmt  
           }  
   
70      and rhs      and rhs
71        = VAR of var        = VAR of var
72        | LIT of Literal.literal        | LIT of Literal.literal
# Line 103  Line 90 
90        | VB_STATE_VAR        | VB_STATE_VAR
91    
92      withtype assign = (var * rhs)      withtype assign = (var * rhs)
93             and phi = (var * var list)
94    
95    
96      (***** Program representation *****)
97    
98      datatype program = Program of {      datatype program = Program of {
99          globals : var list,          globals : var list,
100          globalInit : stmt,          globalInit : cfg,
101          actors : actor list          actors : actor list
102          (* initialization *)          (* initialization *)
103        }        }
# Line 115  Line 106 
106          name : Atom.atom,          name : Atom.atom,
107          params : var list,          params : var list,
108          state : var list,          state : var list,
109          stateInit : stmt,          stateInit : cfg,
110          methods : method list          methods : method list
111        }        }
112    
# Line 123  Line 114 
114          name : Atom.atom,          name : Atom.atom,
115          stateIn : var list,     (* names of state variables on method entry *)          stateIn : var list,     (* names of state variables on method entry *)
116          stateOut : var list,    (* names of state variables on method exit *)          stateOut : var list,    (* names of state variables on method exit *)
117          body : stmt             (* method body *)          body : cfg              (* method body *)
118        }        }
119    
120    
121      (* operations on CFGs *)
122        structure CFG : sig
123          (* create a basic block from a list of assignments *)
124            val mkBlock : assign list -> cfg
125          (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
126           * be in preorder with parents before children.
127           *)
128            val sort : cfg -> node list
129          (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)
130            val apply : (node -> unit) -> cfg -> unit
131          (* replace a simple node in a cfg with a subgraph *)
132            val splice : (node * cfg) -> unit
133          end
134    
135      (* operations on CFG nodes *)
136      structure Node : sig      structure Node : sig
137            val id : node -> Stamp.stamp
138            val kind : node -> node_kind
139          val same : node * node -> bool          val same : node * node -> bool
140          val compare : node * node -> order          val compare : node * node -> order
141          val hash : node -> word          val hash : node -> word
# Line 146  Line 155 
155          val mkENTRY : unit -> node          val mkENTRY : unit -> node
156          val mkJOIN : (var * var list) list -> node          val mkJOIN : (var * var list) list -> node
157          val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node          val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node
158          val mkBLOCK : assign list -> node          val mkCOM : string list -> node
159            val mkASSIGN : assign list -> node
160          val mkNEW : {actor : Atom.atom, args : var list} -> node          val mkNEW : {actor : Atom.atom, args : var list} -> node
161          val mkDIE : unit -> node          val mkDIE : unit -> node
162          val mkSTABILIZE : unit -> node          val mkSTABILIZE : unit -> node
# Line 164  Line 174 
174                }                }
175        end        end
176    
177      structure Stmt : sig    (* operations on variables *)
         val same : stmt * stmt -> bool  
         val compare : stmt * stmt -> order  
         val hash : stmt -> word  
         val toString : stmt -> string  
       (* return the entry node of the statement *)  
         val entry : stmt -> node  
       (* return the tail-end node of a statement (not applicable to S_IF or S_LOOP) *)  
         val tail : stmt -> node  
       (* statement constructor functions *)  
         val new : (stmt_kind * stmt option) -> stmt  
         val mkENTRY : stmt option -> stmt  
         val mkJOIN : (var * var list) list * stmt option -> stmt  
         val mkIF : var * stmt * stmt * stmt option -> stmt  
         val mkBLOCK : assign list * stmt option -> stmt  
         val mkNEW : Atom.atom * var list * stmt option -> stmt  
         val mkDIE : unit -> stmt  
         val mkSTABILIZE : unit -> stmt  
         val mkEXIT : unit -> stmt  
       (* properties *)  
         val newProp : (stmt -> 'a) -> {  
                 getFn : stmt -> 'a,  
                 peekFn : stmt -> 'a option,  
                 setFn : stmt * 'a -> unit,  
                 clrFn : stmt -> unit  
               }  
         val newFlag : unit -> {  
                 getFn : stmt -> bool,  
                 setFn : stmt * bool -> unit  
               }  
       end  
   
178      structure Var : sig      structure Var : sig
179          val new : string * Ty.ty -> var          val new : string * Ty.ty -> var
180          val name : var -> string          val name : var -> string
# Line 225  Line 204 
204        end        end
205    
206    (* return a string representation of a PHI node *)    (* return a string representation of a PHI node *)
207      val phiToString : (var * var list) -> string      val phiToString : phi -> string
208    
209    (* return a string representation of an assignment *)    (* return a string representation of an assignment *)
210      val assignToString : assign -> string      val assignToString : assign -> string
211    
   (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will  
    * be in preorder with parents before children.  
    *)  
     val sortNodes : stmt -> node list  
   
   (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)  
     val applyToNodes : (node -> unit) -> stmt -> unit  
   
212    end    end
213    
214  functor SSAFn (  functor SSAFn (
# Line 250  Line 221 
221      structure Ty = Ty      structure Ty = Ty
222      structure Op = Op      structure Op = Op
223    
224      datatype node = ND of {    (***** CFG *****)
225    
226        datatype cfg = CFG of {
227            entry : node ref,       (* the entry node of a graph; not necessarily an ENTRY node *)
228            exir : node ref         (* the exit node of a graph; not necessarily a DIE, STABILIZE,
229                                     * or EXIT node.
230                                     *)
231          }
232    
233        and node = ND of {
234          id : Stamp.stamp,          id : Stamp.stamp,
235          props : PropList.holder,          props : PropList.holder,
236          kind : node_kind          kind : node_kind
# Line 263  Line 243 
243            }            }
244        | JOIN of {        | JOIN of {
245              preds : node list ref,              preds : node list ref,
246              phis : (var * var list) list ref,   (* phi statements *)              phis : phi list ref,
247              succ : node ref              succ : node ref
248            }            }
249        | COND of {        | COND of {
# Line 272  Line 252 
252              trueBranch : node ref,              trueBranch : node ref,
253              falseBranch : node ref              falseBranch : node ref
254            }            }
255        | BLOCK of {        | COM of  {                       (* comment *)
256              pred : node ref,              pred : node ref,
257              body : assign list ref,              text : string list,
258              succ : node ref              succ : node ref
259            }            }
260        | NEW of {        | ASSIGN of {                     (* assignment *)
261                pred : node ref,
262                stm : assign,
263                succ : node ref
264              }
265          | NEW of {                        (* create new actor instance *)
266              pred : node ref,              pred : node ref,
267              actor : Atom.atom,              actor : Atom.atom,
268              args : var list,              args : var list,
# Line 293  Line 278 
278              pred : node ref              pred : node ref
279            }            }
280    
   (***** Statements *****)  
   
     and stmt = STM of {  
         id : Stamp.stamp,  
         props : PropList.holder,  
         kind : stmt_kind,  
         next : stmt option              (* next statement at this structural level *)  
       }  
   
     and stmt_kind  
       = S_SIMPLE of node                (* ENTRY, JOIN, BLOCK, NEW, DIE, STABILIZE, or EXIT node *)  
       | S_IF of {  
             cond : node,                (* COND node *)  
             thenBranch : stmt,  
             elseBranch : stmt  
           }  
       | S_LOOP of {  
             hdr : stmt,  
             cond : node,                (* COND node *)  
             body : stmt  
           }  
   
281      and rhs      and rhs
282        = VAR of var        = VAR of var
283        | LIT of Literal.literal        | LIT of Literal.literal
# Line 323  Line 286 
286    
287      and var = V of {      and var = V of {
288          name : string,                  (* name *)          name : string,                  (* name *)
289            id : Stamp.stamp,               (* unique ID *)
290          ty : Ty.ty,                     (* type *)          ty : Ty.ty,                     (* type *)
291          bind : var_bind ref,            (* binding *)          bind : var_bind ref,            (* binding *)
         id : Stamp.stamp,               (* unique ID *)  
292          useCnt : int ref,               (* count of uses *)          useCnt : int ref,               (* count of uses *)
293          props : PropList.holder          props : PropList.holder
294        }        }
# Line 338  Line 301 
301        | VB_STATE_VAR        | VB_STATE_VAR
302    
303      withtype assign = (var * rhs)      withtype assign = (var * rhs)
304             and phi = (var * var list)
305    
306    
307      (***** Program representation *****)
308    
309      datatype program = Program of {      datatype program = Program of {
310          globals : var list,          globals : var list,
311          globalInit : stmt,          globalInit : cfg,
312          actors : actor list          actors : actor list
313          (* initialization *)          (* initialization *)
314        }        }
# Line 350  Line 317 
317          name : Atom.atom,          name : Atom.atom,
318          params : var list,          params : var list,
319          state : var list,          state : var list,
320          stateInit : stmt,          stateInit : cfg,
321          methods : method list          methods : method list
322        }        }
323    
# Line 358  Line 325 
325          name : Atom.atom,          name : Atom.atom,
326          stateIn : var list,     (* names of state variables on method entry *)          stateIn : var list,     (* names of state variables on method entry *)
327          stateOut : var list,    (* names of state variables on method exit *)          stateOut : var list,    (* names of state variables on method exit *)
328          body : stmt             (* method body *)          body : cfg              (* method body *)
329        }        }
330    
331      structure Node =      structure Node =
# Line 372  Line 339 
339                        | ENTRY _ => "ENTRY"                        | ENTRY _ => "ENTRY"
340                        | JOIN _ => "JOIN"                        | JOIN _ => "JOIN"
341                        | COND _ => "COND"                        | COND _ => "COND"
342                        | BLOCK _ => "BLOCK"                        | COM _ => "COM"
343                          | ASSIGN _ => "ASSIGN"
344                        | NEW _ => "NEW"                        | NEW _ => "NEW"
345                        | DIE _ => "DIE"                        | DIE _ => "DIE"
346                        | STABILIZE _ => "STABILIZE"                        | STABILIZE _ => "STABILIZE"
# Line 389  Line 357 
357                  pred = ref dummy, cond = cond,                  pred = ref dummy, cond = cond,
358                  trueBranch = ref trueBranch, falseBranch = ref falseBranch                  trueBranch = ref trueBranch, falseBranch = ref falseBranch
359                })                })
360          fun mkBLOCK body = new (BLOCK{pred = ref dummy, body = ref body, succ = ref dummy})          fun mkCOM text = new (COM{pred = ref dummy, text = text, succ = ref dummy})
361            fun mkASSIGN stm = new (ASSIGN{pred = ref dummy, stm = stm, succ = ref dummy})
362          fun mkNEW {actor, args} = new (NEW{          fun mkNEW {actor, args} = new (NEW{
363                  pred = ref dummy, actor = actor, args = args, succ = ref dummy                  pred = ref dummy, actor = actor, args = args, succ = ref dummy
364                })                })
# Line 404  Line 373 
373                      then ()                      then ()
374                      else preds := nd :: !preds                      else preds := nd :: !preds
375                  | COND{pred, ...} => pred := nd                  | COND{pred, ...} => pred := nd
376                  | BLOCK{pred, ...} => pred := nd                  | COM{pred, ...} => pred := nd
377                    | ASSIGN{pred, ...} => pred := nd
378                  | NEW{pred, ...} => pred := nd                  | NEW{pred, ...} => pred := nd
379                  | DIE{pred} => pred := nd                  | DIE{pred} => pred := nd
380                  | STABILIZE{pred} => pred := nd                  | STABILIZE{pred} => pred := nd
# Line 415  Line 385 
385                  | ENTRY _ => []                  | ENTRY _ => []
386                  | JOIN{preds, ...} => !preds                  | JOIN{preds, ...} => !preds
387                  | COND{pred, ...} => [!pred]                  | COND{pred, ...} => [!pred]
388                  | BLOCK{pred, ...} => [!pred]                  | COM{pred, ...} => [!pred]
389                    | ASSIGN{pred, ...} => [!pred]
390                  | NEW{pred, ...} => [!pred]                  | NEW{pred, ...} => [!pred]
391                  | DIE{pred} => [!pred]                  | DIE{pred} => [!pred]
392                  | STABILIZE{pred} => [!pred]                  | STABILIZE{pred} => [!pred]
# Line 423  Line 394 
394                (* end case *))                (* end case *))
395          fun hasSucc (ND{kind, ...}) = (case kind          fun hasSucc (ND{kind, ...}) = (case kind
396                 of NULL => false                 of NULL => false
397                  | ENTRY{succ} => true                  | ENTRY _ => true
398                  | JOIN{succ, ...} => true                  | JOIN _ => true
399                  | COND{trueBranch, falseBranch, ...} => true                  | COND _ => true
400                  | BLOCK{succ, ...} => true                  | COM _ => true
401                  | NEW{succ, ...} => true                  | ASSIGN _ => true
402                    | NEW _ => true
403                  | DIE _ => false                  | DIE _ => false
404                  | STABILIZE _ => false                  | STABILIZE _ => false
405                  | EXIT _ => false                  | EXIT _ => false
# Line 437  Line 409 
409                  | ENTRY{succ} => succ := nd                  | ENTRY{succ} => succ := nd
410                  | JOIN{succ, ...} => succ := nd                  | JOIN{succ, ...} => succ := nd
411                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)                  | COND _ => raise Fail("setSucc on COND node "^toString nd0)
412                  | BLOCK{succ, ...} => succ := nd                  | COM{succ, ...} => succ := nd
413                    | ASSIGN{succ, ...} => succ := nd
414                  | NEW{succ, ...} => succ := nd                  | NEW{succ, ...} => succ := nd
415                  | DIE _ => raise Fail("setSucc on DIE node "^toString nd0)                  | DIE _ => raise Fail("setSucc on DIE node "^toString nd0)
416                  | STABILIZE _ => raise Fail("setSucc on STABILIZE node "^toString nd0)                  | STABILIZE _ => raise Fail("setSucc on STABILIZE node "^toString nd0)
# Line 448  Line 421 
421                  | ENTRY{succ} => [!succ]                  | ENTRY{succ} => [!succ]
422                  | JOIN{succ, ...} => [!succ]                  | JOIN{succ, ...} => [!succ]
423                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]                  | COND{trueBranch, falseBranch, ...} => [!trueBranch, !falseBranch]
424                  | BLOCK{succ, ...} => [!succ]                  | COM{succ, ...} => [!succ]
425                    | ASSIGN{succ, ...} => [!succ]
426                  | NEW{succ, ...} => [!succ]                  | NEW{succ, ...} => [!succ]
427                  | DIE _ => []                  | DIE _ => []
428                  | STABILIZE _ => []                  | STABILIZE _ => []
# Line 474  Line 448 
448                PropList.newFlag (fn (ND{props, ...}) => props)                PropList.newFlag (fn (ND{props, ...}) => props)
449        end        end
450    
     structure Stmt =  
       struct  
         fun same (STM{id=a, ...}, STM{id=b, ...}) = Stamp.same(a, b)  
         fun compare (STM{id=a, ...}, STM{id=b, ...}) = Stamp.compare(a, b)  
         fun hash (STM{id, ...}) = Stamp.hash id  
         fun toString (STM{id, kind, ...}) = let  
               val tag = (case kind  
                      of S_SIMPLE(ND{kind, ...}) => (case kind  
                            of NULL => "NULL"  
                             | ENTRY _ => "ENTRY"  
                             | JOIN _ => "JOIN"  
                             | COND _ => raise Fail "unexpected S_SIMPLE with COND node"  
                             | BLOCK _ => "BLOCK"  
                             | NEW _ => "NEW"  
                             | DIE _ => "DIE"  
                             | STABILIZE _ => "STABILIZE"  
                             | EXIT _ => "EXIT"  
                           (* end case *))  
                       | S_IF _ => "IF"  
                       | S_LOOP _ => "LOOP"  
                     (* end case *))  
               in  
                 tag ^ Stamp.toString id  
               end  
       (* return the entry node of the statement *)  
         fun entry (STM{kind, ...}) = (case kind  
                of S_SIMPLE nd => nd  
                 | S_IF{cond, ...} => cond  
                 | S_LOOP{hdr, ...} => entry hdr  
               (* end case *))  
       (* return the tail-end node of a statement (not applicable to S_IF or S_LOOP) *)  
         fun tail (STM{kind, ...}) = (case kind  
                of S_SIMPLE nd => nd  
                 | S_IF{cond, ...} => raise Fail "tail of IF"  
                 | S_LOOP{hdr, ...} => raise Fail "tail of LOOP"  
               (* end case *))  
       (* statement constructor functions *)  
         fun new (kind, next) = STM{  
             id = Stamp.new(),  
             props = PropList.newHolder(),  
             kind = kind,  
             next = next  
           }  
         val dummy = new (S_SIMPLE(Node.dummy), NONE)  
         fun mkENTRY next = new (S_SIMPLE(Node.mkENTRY ()), next)  
         fun mkJOIN (phis, next) = new (S_SIMPLE(Node.mkJOIN phis), next)  
         fun mkIF (cond, thenBranch, elseBranch, next) = let  
               val cond = Node.mkCOND {  
                     cond = cond,  
                     trueBranch = entry thenBranch,  
                     falseBranch = entry elseBranch  
                   }  
               in  
                 Node.setPred (entry thenBranch, cond);  
                 Node.setPred (entry elseBranch, cond);  
                 new (S_IF{cond = cond, thenBranch = thenBranch, elseBranch = elseBranch}, next)  
               end  
         fun mkBLOCK (body, next) = new (S_SIMPLE(Node.mkBLOCK body), next)  
         fun mkNEW (actor, args, next) = new (S_SIMPLE(Node.mkNEW{actor=actor, args=args}), next)  
         fun mkDIE () = new (S_SIMPLE(Node.mkDIE ()), NONE)  
         fun mkSTABILIZE () = new (S_SIMPLE(Node.mkSTABILIZE ()), NONE)  
         fun mkEXIT () = new (S_SIMPLE(Node.mkEXIT ()), NONE)  
       (* properties *)  
         fun newProp initFn =  
               PropList.newProp (fn (STM{props, ...}) => props, initFn)  
         fun newFlag () =  
               PropList.newFlag (fn (STM{props, ...}) => props)  
       end  
   
451      structure Var =      structure Var =
452        struct        struct
453          fun new (name, ty) = V{          fun new (name, ty) = V{
# Line 585  Line 490 
490            end)            end)
491        end        end
492    
493    (* return a string representation of a PHI node *)      structure CFG =
494      fun phiToString (y, xs) = String.concat [        struct
495              Ty.toString(Var.ty y), " ", Var.toString y, " = PHI(",        (* create a basic block from a list of assignments *)
496              String.concatWith "," (List.map Var.toString xs), ")"          fun mkBlock [] = CFG{entry = Node.dummy, exit = Node.dummy}
497            ]            | mkBlock (stm::stms) = let
498                  val entry = Node.mkASSIGN stm
499    (* return a string representation of an assignment *)                fun f (stm, prev) = let
500      fun assignToString (y, rhs) = let                      val nd = Node.mkASSIGN stm
           val rhs = (case rhs  
                  of VAR x => Var.toString x  
                   | LIT lit => Literal.toString lit  
                   | OP(rator, xs) => String.concat [  
                         Op.toString rator,  
                         "(", String.concatWith "," (List.map Var.toString xs), ")"  
                       ]  
                   | CONS xs => String.concat [  
                         "[", String.concatWith "," (List.map Var.toString xs), "]"  
                       ]  
                 (* end case *))  
501            in            in
502              String.concat [Ty.toString(Var.ty y), " ", Var.toString y, " = ", rhs]                        Node.addEdge (prev, nd);
503                          nd
504                        end
505                  val exit = List.foldl f entry stms
506                  in
507                    CFG{entry = entry, exit = exit}
508            end            end
509    
510    (* 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
511     * be in preorder with parents before children.     * be in preorder with parents before children.
512     *)     *)
513      fun sortNodes stmt = let          fun sort (CFG{entry, ...} = let
514            val {getFn, setFn} = PropList.newFlag (fn (ND{props, ...}) => props)            val {getFn, setFn} = PropList.newFlag (fn (ND{props, ...}) => props)
515            fun dfs (nd, l) =            fun dfs (nd, l) =
516                  if getFn nd                  if getFn nd
# Line 619  Line 518 
518                    else (                    else (
519                      setFn (nd, true);                      setFn (nd, true);
520                      nd :: List.foldl dfs l (Node.succs nd))                      nd :: List.foldl dfs l (Node.succs nd))
521            val nodes = dfs (Stmt.entry stmt, [])                val nodes = dfs (entry, [])
522            in            in
523              List.app (fn nd => setFn(nd, false)) nodes;              List.app (fn nd => setFn(nd, false)) nodes;
524              nodes              nodes
525            end            end
526    
527    (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)    (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)
528      fun applyToNodes (f : node -> unit) stmt = let          fun apply (f : node -> unit) (CFG{entry, ...}) = let
529            val {getFn, setFn} = PropList.newFlag (fn (ND{props, ...}) => props)            val {getFn, setFn} = PropList.newFlag (fn (ND{props, ...}) => props)
530            fun dfs (nd, l) =            fun dfs (nd, l) =
531                  if getFn nd                  if getFn nd
# Line 635  Line 534 
534                      f nd; (* visit *)                      f nd; (* visit *)
535                      setFn (nd, true);                      setFn (nd, true);
536                      nd :: List.foldl dfs l (Node.succs nd))                      nd :: List.foldl dfs l (Node.succs nd))
537            val nodes = dfs (Stmt.entry stmt, [])                val nodes = dfs (entry, [])
538            in            in
539              List.app (fn nd => setFn(nd, false)) nodes              List.app (fn nd => setFn(nd, false)) nodes
540            end            end
541    
542          (* replace a simple node in a cfg with a subgraph *)
543            fun splice (nd, CFG{entry, exit}) = ??
544    
545    end    end
546    
547      (* return a string representation of a PHI node *)
548        fun phiToString (y, xs) = String.concat [
549                Ty.toString(Var.ty y), " ", Var.toString y, " = PHI(",
550                String.concatWith "," (List.map Var.toString xs), ")"
551              ]
552    
553      (* return a string representation of an assignment *)
554        fun assignToString (y, rhs) = let
555              val rhs = (case rhs
556                     of VAR x => Var.toString x
557                      | LIT lit => Literal.toString lit
558                      | OP(rator, xs) => String.concat [
559                            Op.toString rator,
560                            "(", String.concatWith "," (List.map Var.toString xs), ")"
561                          ]
562                      | CONS xs => String.concat [
563                            "[", String.concatWith "," (List.map Var.toString xs), "]"
564                          ]
565                    (* end case *))
566              in
567                String.concat [Ty.toString(Var.ty y), " ", Var.toString y, " = ", rhs]
568              end
569    
570      end (* SSAFn *)

Legend:
Removed from v.477  
changed lines
  Added in v.478

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