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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 199 - (view) (download)

1 : jhr 137 (* ssa-fn.sml
2 : jhr 124 *
3 :     * COPYRIGHT (c) 2010 The Diderot Project (http://diderot.cs.uchicago.edu)
4 :     * All rights reserved.
5 : jhr 137 *
6 :     * The IL is a combination of a block-structured tree and an SSA control-flow
7 :     * graph of blocks.
8 : jhr 124 *)
9 :    
10 : jhr 198 signature SSA =
11 :     sig
12 :    
13 :     structure Op : OPERATORS
14 :    
15 :     datatype program = Program of {
16 :     globals : var list,
17 :     globalInit : stmt,
18 :     actors : actor list
19 :     (* 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 :     }
45 :     | IF of {
46 :     cond : var,
47 :     thenBranch : stmt,
48 :     elseBranch : stmt
49 :     }
50 :     | LOOP of {
51 :     hdr : stmt,
52 :     cond : var,
53 :     body : stmt,
54 :     exit : stmt
55 :     }
56 :     | NEW of {
57 :     actor : Atom.atom,
58 :     args : var list,
59 :     succ : stmt
60 :     }
61 :     | DIE
62 :     | STABILIZE
63 :     | EXIT
64 :    
65 :     and rhs
66 :     = VAR of var
67 :     | LIT of Literal.literal
68 :     | OP of Op.rator * var list
69 :     | CONS of var list (* tensor-value construction *)
70 :    
71 :     and var = V of {
72 :     name : string, (* name *)
73 :     id : Stamp.stamp, (* unique ID *)
74 :     useCnt : int ref, (* count of uses *)
75 :     props : PropList.holder
76 :     }
77 :    
78 :     withtype assign = (var * rhs)
79 :    
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 : jhr 199 structure Var : sig
104 :     val new : string -> var
105 :     val same : var * var -> bool
106 :     val compare : var * var -> order
107 :     val hash : var -> word
108 :     val toString : var -> string
109 :     structure Map : ORD_MAP where type Key.ord_key = var
110 :     structure Set : ORD_SET where type Key.ord_key = var
111 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
112 :     end
113 : jhr 198
114 :     end
115 :    
116 :     functor SSAFn (Op : OPERATORS) : SSA =
117 : jhr 192 struct
118 : jhr 137
119 : jhr 192 structure Op = Op
120 : jhr 137
121 : jhr 197 datatype program = Program of {
122 :     globals : var list,
123 :     globalInit : stmt,
124 :     actors : actor list
125 :     (* initialization *)
126 :     }
127 :    
128 :     and actor = Actor of {
129 :     name : Atom.atom,
130 :     params : var list,
131 :     state : var list,
132 :     stateInit : stmt,
133 :     methods : method list
134 :     }
135 :    
136 :     and method = Method of Atom.atom * stmt
137 :    
138 :     and stmt = STM of {
139 : jhr 188 id : Stamp.stamp,
140 :     props : PropList.holder,
141 : jhr 192 preds : stmt list ref,
142 :     phis : (var * var list) list ref, (* phi statements *)
143 :     kind : stmt_kind ref
144 : jhr 188 }
145 :    
146 : jhr 192 and stmt_kind
147 :     = BLOCK of {
148 :     succ : stmt,
149 :     body : assign list
150 :     }
151 :     | IF of {
152 :     cond : var,
153 :     thenBranch : stmt,
154 :     elseBranch : stmt
155 :     }
156 :     | LOOP of {
157 :     hdr : stmt,
158 :     cond : var,
159 :     body : stmt,
160 :     exit : stmt
161 :     }
162 :     | NEW of {
163 :     actor : Atom.atom,
164 :     args : var list,
165 :     succ : stmt
166 :     }
167 :     | DIE
168 :     | STABILIZE
169 :     | EXIT
170 :    
171 : jhr 188 and rhs
172 :     = VAR of var
173 :     | LIT of Literal.literal
174 :     | OP of Op.rator * var list
175 :     | CONS of var list (* tensor-value construction *)
176 :    
177 : jhr 192 and var = V of {
178 : jhr 137 name : string, (* name *)
179 :     id : Stamp.stamp, (* unique ID *)
180 :     useCnt : int ref, (* count of uses *)
181 :     props : PropList.holder
182 : jhr 124 }
183 :    
184 : jhr 192 withtype assign = (var * rhs)
185 : jhr 188
186 : jhr 192 fun same (STM{id=a, ...}, STM{id=b, ...}) = Stamp.same(a, b)
187 :     fun compare (STM{id=a, ...}, STM{id=b, ...}) = Stamp.compare(a, b)
188 :     fun hash (STM{id, ...}) = Stamp.hash id
189 : jhr 188
190 : jhr 192 fun succs (STM{kind, ...}) = (case !kind
191 :     of BLOCK{succ, ...} => [succ]
192 :     | IF{thenBranch, elseBranch, ...} => [thenBranch, elseBranch]
193 :     | LOOP{exit, ...} => [exit]
194 :     | NEW{succ, ...} => [succ]
195 :     | _ => []
196 :     (* end case *))
197 : jhr 188
198 : jhr 192 (* set the successor of a statement *)
199 :     fun setSucc (STM{kind, ...}, stm) = (case !kind
200 :     of BLOCK{succ, body} => kind := BLOCK{succ=stm, body=body}
201 :     | IF{thenBranch, elseBranch, ...} => (
202 :     setSucc(thenBranch, stm);
203 :     setSucc(elseBranch, stm))
204 :     | LOOP{hdr, cond, body, exit} => kind := LOOP{hdr=hdr, cond=cond, body=body, exit=stm}
205 :     | NEW{actor, args, succ} => kind := NEW{actor=actor, args=args, succ=stm}
206 :     | _ => () (* no successor *)
207 :     (* end case *))
208 : jhr 188
209 : jhr 192 fun preds (STM{preds, ...}) = !preds
210 : jhr 124
211 : jhr 192 fun addPred (STM{preds, ...}, stm) =
212 :     if not(List.exists (fn b => same(stm, b)) (!preds))
213 :     then preds := stm :: !preds
214 :     else ();
215 : jhr 137
216 : jhr 192 fun mkSTM kind = STM{
217 : jhr 137 id = Stamp.new(),
218 : jhr 188 props = PropList.newHolder(),
219 : jhr 192 preds = ref [],
220 :     phis = ref [],
221 :     kind = ref kind
222 : jhr 137 }
223 :    
224 : jhr 192 val dummy = mkSTM EXIT
225 : jhr 137
226 : jhr 192 fun mkBLOCK args = mkSTM(BLOCK args)
227 :     fun mkIF args = mkSTM(IF args)
228 :     fun mkLOOP args = mkSTM(LOOP args)
229 : jhr 197 fun mkNEW args = mkSTM(NEW args)
230 : jhr 192 fun mkDIE () = mkSTM DIE
231 :     fun mkSTABILIZE () = mkSTM STABILIZE
232 :     fun mkEXIT () = mkSTM EXIT
233 : jhr 137
234 : jhr 199 structure Var =
235 :     struct
236 :     fun new name = V{
237 :     name = name,
238 :     id = Stamp.new(),
239 :     useCnt = ref 0,
240 :     props = PropList.newHolder()
241 :     }
242 :     fun same (V{id=a, ...}, V{id=b, ...}) = Stamp.same(a, b)
243 :     fun compare (V{id=a, ...}, V{id=b, ...}) = Stamp.compare(a, b)
244 :     fun hash (V{id, ...}) = Stamp.hash id
245 :     fun toString (V{name, id, ...}) = name ^ Stamp.toString id
246 :     local
247 :     structure V =
248 :     struct
249 :     type ord_key = var
250 :     val compare = compare
251 :     end
252 :     in
253 :     structure Map = RedBlackMapFn (V)
254 :     structure Set = RedBlackSetFn (V)
255 :     end
256 :     structure Tbl = HashTableFn (
257 :     struct
258 :     type hash_key = var
259 :     val hashVal = hash
260 :     val sameKey = same
261 :     end)
262 :     end
263 : jhr 197
264 : jhr 124 end

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