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

SCM Repository

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

Diff of /trunk/src/compiler/IL/ssa-fn.sml

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

revision 176, Mon Jul 26 19:47:48 2010 UTC revision 198, Mon Aug 2 21:26:57 2010 UTC
# Line 9  Line 9 
9    
10  signature SSA =  signature SSA =
11    sig    sig
12    
13      structure Op : OPERATORS      structure Op : OPERATORS
14    
15      datatype var = V of {      datatype program = Program of {
16          name : string,                  (* name *)          globals : var list,
17          id : Stamp.stamp,               (* unique ID *)          globalInit : stmt,
18          useCnt : int ref,               (* count of uses *)          actors : actor list
19          props : PropList.holder          (* initialization *)
20          }
21    
22        and actor = Actor of {
23            name : Atom.atom,
24            params : var list,
25            state : var list,
26            stateInit : stmt,
27            methods : method list
28          }
29    
30        and method = Method of Atom.atom * stmt
31    
32        and stmt = STM of {
33            id : Stamp.stamp,
34            props : PropList.holder,
35            preds : stmt list ref,
36            phis : (var * var list) list ref,       (* phi statements *)
37            kind : stmt_kind ref
38          }
39    
40        and stmt_kind
41          = BLOCK of {
42                succ : stmt,
43                body : assign list
44        }        }
   
   (* a statement is a CFG fragment with a single entrypoint and  
    * a single continuation.  
    *)  
     datatype stmt  
       = BLOCK of stmt  
       | SEQ of stmt list  
45        | IF of {        | IF of {
           pre : stmt,  
46            cond : var,            cond : var,
47            trueBranch : stmt              thenBranch : stmt,
48            falseBranch : stmt              elseBranch : stmt
49          }          }
50        | WHILE of {        | LOOP of {
51            hdr : block,              hdr : stmt,
52            cond : var,            cond : var,
53            body : stmt              body : stmt,
54                exit : stmt
55          }          }
56          | NEW of {
57      and block = BLK of {              actor : Atom.atom,
58            parent : stmt ref,                    (* parent statement of this block *)              args : var list,
59            id : Stamp.stamp,                     (* unique ID *)              succ : stmt
           preds : block list ref,               (* list of predecessor blocks in the CFG *)  
           phi : (var * var list) list ref,      (* phi statements *)  
           body : simple_stmt list ref,  
           succs : block list ref                (* successor blocks in the CFG *)  
60          }          }
   
     and simple_stmt  
       = ASSIGN of var * rhs  
61        | DIE        | DIE
62        | STABILIZE        | STABILIZE
63        | RETURN        | EXIT
64    
65      and rhs      and rhs
66        = VAR of var        = VAR of var
# Line 57  Line 68 
68        | OP of Op.rator * var list        | OP of Op.rator * var list
69        | CONS of var list                (* tensor-value construction *)        | CONS of var list                (* tensor-value construction *)
70    
71      val newVar : string -> var      and var = V of {
72      val newBlock : unit -> block          name : string,                  (* name *)
73            id : Stamp.stamp,               (* unique ID *)
74            useCnt : int ref,               (* count of uses *)
75            props : PropList.holder
76          }
77    
78      val entryBlock : stmt -> block      withtype assign = (var * rhs)
79      val nextBlock : stmt -> block  
80        val same : stmt * stmt -> bool
81        val compare : stmt * stmt -> order
82        val hash : stmt -> word
83    
84        val succs : stmt -> stmt list
85    
86      (* set the successor of a statement *)
87        val setSucc : stmt * stmt -> unit
88    
89        val preds : stmt -> stmt list
90    
91        val addPred : stmt * stmt -> unit
92    
93        val dummy : stmt
94    
95        val mkBLOCK : {succ : stmt, body : assign list} -> stmt
96        val mkIF : {cond : var, thenBranch : stmt, elseBranch : stmt} -> stmt
97        val mkLOOP : {hdr : stmt, cond : var, body : stmt, exit : stmt} -> stmt
98        val mkNEW : {actor : Atom.atom, args : var list, succ : stmt} -> stmt
99        val mkDIE : unit -> stmt
100        val mkSTABILIZE : unit -> stmt
101        val mkEXIT : unit -> stmt
102    
103        val newVar : string -> var
104    
105    end    end
106    
107  functor SSAFn (Op : OPERATORS) : SSA =  functor SSAFn (Op : OPERATORS) : SSA =
108    struct    struct
109    
110      datatype var = V of {      structure Op = Op
111          name : string,                  (* name *)  
112          id : Stamp.stamp,               (* unique ID *)      datatype program = Program of {
113          useCnt : int ref,               (* count of uses *)          globals : var list,
114          props : PropList.holder          globalInit : stmt,
115            actors : actor list
116            (* initialization *)
117          }
118    
119        and actor = Actor of {
120            name : Atom.atom,
121            params : var list,
122            state : var list,
123            stateInit : stmt,
124            methods : method list
125        }        }
126    
127    datatype stmt      and method = Method of Atom.atom * stmt
128      = EXIT  
129      | SEQ of block * stmt      and stmt = STM of {
130            id : Stamp.stamp,
131            props : PropList.holder,
132            preds : stmt list ref,
133            phis : (var * var list) list ref,       (* phi statements *)
134            kind : stmt_kind ref
135          }
136    
137        and stmt_kind
138          = BLOCK of {
139                succ : stmt,
140                body : assign list
141              }
142      | IF of {      | IF of {
         pre : stmt,  
143          cond : var,          cond : var,
144          trueBranch : stmt,              thenBranch : stmt,
145          falseBranch : stmt,              elseBranch : stmt
         next : stmt             (* ?? *)  
146        }        }
147      | WHILE of {        | LOOP of {
148          hdr : stmt,          hdr : stmt,
149          cond : var,          cond : var,
150          body : stmt,          body : stmt,
151          exit : stmt             (* ?? *)              exit : stmt
152        }        }
153          | NEW of {
154    and block = BLK of {              actor : Atom.atom,
155          parent : stmt ref,                      (* parent statement of this block *)              args : var list,
156          id : Stamp.stamp,                       (* unique ID *)              succ : stmt
         preds : block list ref,                 (* list of predecessor blocks in the CFG *)  
         phi : (var * var list) list ref,        (* phi statements *)  
         body : simple_stmt list ref,  
         succs : block list ref                  (* successor blocks in the CFG *)  
157        }        }
   
   and simple_stmt  
     = ASSIGN of var * rhs  
158      | DIE      | DIE
159      | STABILIZE      | STABILIZE
160      | RETURN        | EXIT
161    
162      and rhs      and rhs
163        = VAR of var        = VAR of var
164          | LIT of Literal.literal
165        | OP of Op.rator * var list        | OP of Op.rator * var list
166          | CONS of var list                (* tensor-value construction *)
167    
168    (* block properties *)      and var = V of {
169      fun parentOf (BLK{parent, ...}) = !parent          name : string,                  (* name *)
170      fun predsOf (BLK{preds, ...}) = !preds          id : Stamp.stamp,               (* unique ID *)
171      fun succsOf (BLK{succs, ...}) = !succs          useCnt : int ref,               (* count of uses *)
172            props : PropList.holder
   (* IL construction code *)  
     fun newVar name = V{  
             name = name,  
             id = Stamp.new(),  
             useCnt = ref 0,  
             props = PropList.newHolder()  
173            }            }
174    
175      fun newBlock () = BLK{      withtype assign = (var * rhs)
176              parent = ref(SEQ[]),  
177        fun same (STM{id=a, ...}, STM{id=b, ...}) = Stamp.same(a, b)
178        fun compare (STM{id=a, ...}, STM{id=b, ...}) = Stamp.compare(a, b)
179        fun hash (STM{id, ...}) = Stamp.hash id
180    
181        fun succs (STM{kind, ...}) = (case !kind
182               of BLOCK{succ, ...} => [succ]
183                | IF{thenBranch, elseBranch, ...} => [thenBranch, elseBranch]
184                | LOOP{exit, ...} => [exit]
185                | NEW{succ, ...} => [succ]
186                | _ => []
187              (* end case *))
188    
189      (* set the successor of a statement *)
190        fun setSucc (STM{kind, ...}, stm) = (case !kind
191               of BLOCK{succ, body} => kind := BLOCK{succ=stm, body=body}
192                | IF{thenBranch, elseBranch, ...} => (
193                    setSucc(thenBranch, stm);
194                    setSucc(elseBranch, stm))
195                | LOOP{hdr, cond, body, exit} => kind := LOOP{hdr=hdr, cond=cond, body=body, exit=stm}
196                | NEW{actor, args, succ} => kind := NEW{actor=actor, args=args, succ=stm}
197                | _ => () (* no successor *)
198              (* end case *))
199    
200        fun preds (STM{preds, ...}) = !preds
201    
202        fun addPred (STM{preds, ...}, stm) =
203              if not(List.exists (fn b => same(stm, b)) (!preds))
204                then preds := stm :: !preds
205                else ();
206    
207        fun mkSTM kind = STM{
208              id = Stamp.new(),              id = Stamp.new(),
209                props = PropList.newHolder(),
210              preds = ref[],              preds = ref[],
211              phi = ref[],              phis = ref [],
212              body = ref[],              kind = ref kind
             succs = ref[]  
213            }            }
214    
215      local      val dummy = mkSTM EXIT
       fun setParent (BKL{parent, ...}, s) = (parent := s)  
     in  
     fun mkBLOCK blk = let  
           val s = BLOCK blk  
           in  
             setParent (blk, s);  
             s  
           end  
   
     fun mkIF (pre, cond, t, f) = let  
           val s = IF{pre=pre, cond=cond, trueBranch=t, falseBranch=f}  
           in  
             setParent (pre, s);  
             s  
           end  
   
     fun mkWHILE (hdr, cond, body) = let  
           val s = WHILE{hdr=hdr, cond=cond, body=body}  
           in  
             setParent (hdr, s);  
             s  
           end  
216    
217      end (* local *)      fun mkBLOCK args = mkSTM(BLOCK args)
218        fun mkIF args = mkSTM(IF args)
219        fun mkLOOP args = mkSTM(LOOP args)
220        fun mkNEW args = mkSTM(NEW args)
221        fun mkDIE () = mkSTM DIE
222        fun mkSTABILIZE () = mkSTM STABILIZE
223        fun mkEXIT () = mkSTM EXIT
224    
225      fun entryBlock (BLOCK blk) = blk      fun newVar name = V{
226        | entryBlock (SEQ(s1::_)) = entryBlock s1              name = name,
227        | entryBlock (IF{pre, ...}) = entryBlock pre              id = Stamp.new(),
228        | entryBlock (WHILE{hdr, ...}) = entryBlock hdr              useCnt = ref 0,
229                props = PropList.newHolder()
230      fun nextBlock (SEQ(, next)) = nextBlock next            }
       | nextBlock (SEQ stms) = nextBlock(List.last stms)  
       | nextBlock (IF{pre, ...}) = entryBlock pre  
       | nextBlock (WHILE{hdr, ...}) = entryBlock hdr  
231    
232    end    end

Legend:
Removed from v.176  
changed lines
  Added in v.198

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