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 1156, Sun May 8 21:20:52 2011 UTC revision 1157, Mon May 9 15:47:35 2011 UTC
# Line 1  Line 1 
1  (* ssa-fn.sml  (* ssa-fn.sml
2   *   *
3   * COPYRIGHT (c) 2010 The Diderot Project (http://diderot-language.cs.uchicago.edu)   * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4   * All rights reserved.   * All rights reserved.
5   *   *
6   * 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 ILs in the Diderot
# Line 8  Line 8 
8   * in their types and operators.   * in their types and operators.
9   *)   *)
10    
 signature SSA =  
   sig  
   
     val ilName : string  
   
     structure Ty : SSA_TYPES  
     structure Op : OPERATORS where type ty = Ty.ty  
   
   (***** CFG *****)  
   
     datatype cfg = CFG of {  
         entry : node,   (* the entry node of a graph; not necessarily an ENTRY node *)  
         exit : node     (* the exit node of a graph; not necessarily an EXIT node. *)  
       }  
   
     and node = ND of {  
         id : Stamp.stamp,  
         props : PropList.holder,  
         kind : node_kind  
       }  
   
     and node_kind  
       = NULL  
       | ENTRY of {  
             succ : node ref  
           }  
       | JOIN of {  
             preds : node list ref,  
             phis : phi list ref,  
             succ : node ref  
           }  
       | COND of {  
             pred : node ref,  
             cond : var,  
             trueBranch : node ref,  
             falseBranch : node ref  
           }  
       | COM of  {                       (* comment *)  
             pred : node ref,  
             text : string list,  
             succ : node ref  
           }  
       | ASSIGN of {                     (* assignment *)  
             pred : node ref,  
             stm : assign,  
             succ : node ref  
           }  
       | NEW of {                        (* create new strand instance *)  
             pred : node ref,  
             strand : Atom.atom,  
             args : var list,  
             succ : node ref  
           }  
       | EXIT of {                       (* includes die and stabilize *)  
             pred : node ref,  
             kind : ExitKind.kind,       (* kind of exit node *)  
             live : var list             (* live variables *)  
           }  
   
     and rhs  
       = VAR of var  
       | LIT of Literal.literal  
       | OP of Op.rator * var list  
       | APPLY of ILBasis.name * var list (* basis function application *)  
       | CONS of Ty.ty * var list        (* tensor/sequence-value construction *)  
   
     and var = V of {  
         name : string,                  (* name *)  
         id : Stamp.stamp,               (* unique ID *)  
         ty : Ty.ty,                     (* type *)  
         bind : var_bind ref,            (* binding *)  
         useCnt : int ref,               (* count of uses *)  
         props : PropList.holder  
       }  
   
     and var_bind  
       = VB_NONE  
       | VB_RHS of rhs                   (* defined by an assignment (includes globals and state variables) *)  
       | VB_PHI of var list              (* defined by a phi node *)  
       | VB_PARAM                        (* parameter to a strand *)  
   
     withtype assign = (var * rhs)  
          and phi = (var * var list)  
   
   
   (***** Program representation *****)  
   
     datatype program = Program of {  
         globalInit : cfg,  
         initially : initially,  
         strands : strand list  
       }  
   
     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)  
       }  
   
     and strand = Strand of {  
         name : Atom.atom,  
         params : var list,  
         state : (bool * var) list,      (* output variables are marked with true *)  
         stateInit : cfg,  
         methods : method list  
       }  
   
     and method = Method of {  
         name : Atom.atom,  
         stateIn : var list,     (* names of state variables on method entry *)  
         body : cfg              (* method body *)  
       }  
   
   (* operations on CFGs *)  
     structure CFG : sig  
       (* the empty CFG *)  
         val empty : cfg  
       (* is a CFG empty? *)  
         val isEmpty : cfg -> bool  
       (* create a basic block from a list of assignments *)  
         val mkBlock : assign list -> cfg  
       (* entry/exit nodes of a CFG *)  
         val entry : cfg -> node  
         val exit : cfg -> node  
       (* return the list of variables that are live at exit from a CFG *)  
         val liveAtExit : cfg -> var list  
       (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will  
        * be in preorder with parents before children.  
        *)  
         val sort : cfg -> node list  
       (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)  
         val apply : (node -> unit) -> cfg -> unit  
 (*  
       (* rewrite a CFG by applying a partial function to the nodes in the graph.  If NONE is returned,  
        * then no change to the node, if SOME(cfg) is returned, then the node is replaced by the  
        * subgraph, which may be empty.  This function returns true if any nodes were rewritten.  
        *)  
         val rewrite : (node -> cfg option) -> cfg -> bool  
 *)  
       (* delete a simple node from a CFG *)  
         val deleteNode : node -> unit  
       (* replace a simple node in a cfg with a different simple node *)  
         val replaceNode : (node * node) -> unit  
       (* replace a simple node in a cfg with a subgraph *)  
         val replaceNodeWithCFG : (node * cfg) -> unit  
       (* concatenate two CFGs *)  
         val concat : cfg * cfg -> cfg  
       (* append a node to a CFG *)  
         val appendNode : cfg * node -> cfg  
       (* update the exit of a CFG by modifying the live variable list *)  
         val updateExit : cfg * (var list -> var list) -> cfg  
       end  
   
   (* operations on CFG nodes *)  
     structure Node : sig  
         val id : node -> Stamp.stamp  
         val kind : node -> node_kind  
         val same : node * node -> bool  
         val compare : node * node -> order  
         val hash : node -> word  
         val toString : node -> string  
         val isNULL : node -> bool  
       (* variable defs and uses; may include duplicates *)  
         val uses : node -> var list  
         val defs : node -> var list  
       (* dummy node *)  
         val dummy : node  
       (* CFG edges *)  
         val hasPred : node -> bool  
         val preds : node -> node list  
         val setPred : node * node -> unit  
         val hasSucc : node -> bool  
         val succs : node -> node list  
         val setSucc : node * node -> unit  
         val setTrueBranch : node * node -> unit  (* set trueBranch successor for COND node *)  
         val setFalseBranch : node * node -> unit (* set falseBranch successor for COND node *)  
         val addEdge : node * node -> unit  
       (* replace the edge src-->oldDst by the edge src-->dst *)  
         val replaceInEdge : {src : node, oldDst : node, dst : node} -> unit  
       (* replace the edge oldSrc-->dst by the edge src-->dst *)  
         val replaceOutEdge : {oldSrc : node, src : node, dst : node} -> unit  
       (* constructors *)  
         val mkENTRY : unit -> node  
         val mkJOIN : (var * var list) list -> node  
         val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node  
         val mkCOM : string list -> node  
         val mkASSIGN : assign -> node  
         val mkNEW : {strand : Atom.atom, args : var list} -> node  
         val mkEXIT : ExitKind.kind * var list -> node  
         val mkFRAGMENT : var list -> node  
         val mkRETURN : var list -> node  
         val mkACTIVE : var list -> node  
         val mkSTABILIZE : var list -> node  
         val mkDIE : unit -> node  
       (* properties *)  
         val newProp : (node -> 'a) -> {  
                 getFn : node -> 'a,  
                 peekFn : node -> 'a option,  
                 setFn : node * 'a -> unit,  
                 clrFn : node -> unit  
               }  
         val newFlag : unit -> {  
                 getFn : node -> bool,  
                 setFn : node * bool -> unit  
               }  
       end  
   
   (* operations on variables *)  
     structure Var : sig  
         val new : string * Ty.ty -> var  
         val copy : var -> var  
         val name : var -> string  
         val ty : var -> Ty.ty  
         val binding : var -> var_bind  
         val setBinding : var * var_bind -> unit  
         val useCount : var -> int  
         val same : var * var -> bool  
         val compare : var * var -> order  
         val hash : var -> word  
         val toString : var -> string  
       (* properties *)  
         val newProp : (var -> 'a) -> {  
                 getFn : var -> 'a,  
                 peekFn : var -> 'a option,  
                 setFn : var * 'a -> unit,  
                 clrFn : var -> unit  
               }  
         val newFlag : unit -> {  
                 getFn : var -> bool,  
                 setFn : var * bool -> unit  
               }  
       (* collections *)  
         structure Map : ORD_MAP where type Key.ord_key = var  
         structure Set : ORD_SET where type Key.ord_key = var  
         structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var  
       end  
   
   (* operations on RHS expressions *)  
     structure RHS : sig  
         val toString : rhs -> string  
         val vars : rhs -> var list  
         val map : (var -> var) -> rhs -> rhs  
         val app : (var -> unit) -> rhs -> unit  
       end  
   
   (* return a string representation of a variable binding *)  
     val vbToString : var_bind -> string  
   
   (* return a string representation of a PHI node *)  
     val phiToString : phi -> string  
   
   (* return a string representation of an assignment *)  
     val assignToString : assign -> string  
   
   end  
   
11  functor SSAFn (  functor SSAFn (
12    
13      val ilName : string      val ilName : string
# Line 485  Line 228 
228                })                })
229          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})
230          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)          fun mkFRAGMENT xs = mkEXIT (ExitKind.FRAGMENT, xs)
231            fun mkSINIT xs = mkEXIT (ExitKind.SINIT, xs)
232          fun mkRETURN xs = mkEXIT (ExitKind.RETURN, xs)          fun mkRETURN xs = mkEXIT (ExitKind.RETURN, xs)
233          fun mkACTIVE xs = mkEXIT (ExitKind.ACTIVE, xs)          fun mkACTIVE xs = mkEXIT (ExitKind.ACTIVE, xs)
234          fun mkSTABILIZE xs = mkEXIT (ExitKind.STABILIZE, xs)          fun mkSTABILIZE xs = mkEXIT (ExitKind.STABILIZE, xs)

Legend:
Removed from v.1156  
changed lines
  Added in v.1157

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