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

SCM Repository

[diderot] Annotation of /branches/vis12-cl/src/compiler/IL/ssa-sig.sml
ViewVC logotype

Annotation of /branches/vis12-cl/src/compiler/IL/ssa-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2825 - (view) (download)

1 : jhr 1232 (* ssa-sig.sml
2 :     *
3 :     * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * The SSA signature is the signature of the HighIL, MidIL, and LowIL modules, which implement
7 :     * the core intermediate languages of the Diderot compiler. These ILs have the same program
8 :     * and control-flow structure, but differ in their types and operators.
9 :     *
10 :     * Some properties:
11 :     *
12 : jhr 2279 * 1) The exit of the globalInit CFG has kind RETURN and the scope of the live variables
13 :     * is the whole program.
14 : jhr 1232 *
15 : jhr 2279 * 2) The scope of the parameters of a strand is the stateInit CFG and the methods of the
16 :     * strand.
17 : jhr 1232 *
18 : jhr 2279 * 3) Each strand has a list of strand-state variables (the "state" field). These variables
19 :     * are not defined or used in the code, but serve as the "master template" for the
20 :     * strand's state.
21 : jhr 1232 *
22 : jhr 2279 * 4) The exit of the stateInit CFG in a strand has kind SINIT and the number of live
23 :     * variables should be the same as the number of variables in the strand's state-variable
24 :     * list.
25 : jhr 1232 *
26 : jhr 2279 * 5) Each method has a list of variables, called stateIn, which corresponds to the
27 :     * variables in the strand's state-variable list.
28 : jhr 1232 *
29 : jhr 2279 * 6) The exit node(s) of the update method should have kind ACTIVE, STABILIZE, or DIE.
30 :     * The live variables at a ACTIVE or STABILIZE exit correspond to the variables in
31 :     * the strand's state-variable list. (Note that this property is modified after the
32 :     * variable-analysis phase).
33 : jhr 1232 *)
34 :    
35 :     signature SSA =
36 :     sig
37 :    
38 :     val ilName : string
39 :    
40 :     structure Ty : SSA_TYPES
41 :     structure Op : OPERATORS where type ty = Ty.ty
42 :    
43 :     (***** CFG *****)
44 :    
45 :     datatype cfg = CFG of {
46 : jhr 2279 entry : node, (* the entry node of a graph; not necessarily an ENTRY node *)
47 :     exit : node (* the exit node of a graph; not necessarily an EXIT node. *)
48 : jhr 1232 }
49 :    
50 :     and node = ND of {
51 : jhr 2279 id : Stamp.stamp,
52 :     props : PropList.holder,
53 :     kind : node_kind
54 : jhr 1232 }
55 :    
56 :     and node_kind
57 :     = NULL
58 :     | ENTRY of {
59 : jhr 2279 succ : node ref
60 :     }
61 : jhr 1232 | JOIN of {
62 : jhr 2825 preds : node list ref, (* includes fake control-flow edges *)
63 :     mask : bool list ref, (* true for incoming fake edges *)
64 :     phis : phi list ref, (* data-flow joins corresponding to the edges in preds *)
65 : jhr 2279 succ : node ref
66 :     }
67 : jhr 1232 | COND of {
68 : jhr 2279 pred : node ref,
69 :     cond : var,
70 :     trueBranch : node ref,
71 :     falseBranch : node ref
72 :     }
73 :     | COM of { (* comment *)
74 :     pred : node ref,
75 :     text : string list,
76 :     succ : node ref
77 :     }
78 : jhr 2804 | ASSIGN of { (* local-variable assignment *)
79 : jhr 2279 pred : node ref,
80 :     stm : assign,
81 :     succ : node ref
82 :     }
83 :     | MASSIGN of { (* multi-assignment *)
84 :     pred : node ref,
85 :     stm : massign,
86 :     succ : node ref
87 :     }
88 : jhr 2804 | GASSIGN of { (* global variable assignment *)
89 :     pred: node ref,
90 :     lhs : global_var,
91 :     rhs : var,
92 :     succ : node ref
93 :     }
94 : jhr 2279 | NEW of { (* create new strand instance *)
95 :     pred : node ref,
96 :     strand : Atom.atom,
97 :     args : var list,
98 :     succ : node ref
99 :     }
100 : jhr 1640 | SAVE of { (* save state variable *)
101 :     pred: node ref,
102 :     lhs : state_var,
103 :     rhs : var,
104 :     succ : node ref
105 :     }
106 : jhr 2279 | EXIT of { (* includes die and stabilize *)
107 :     pred : node ref,
108 :     kind : ExitKind.kind, (* kind of exit node *)
109 : jhr 2825 live : var list, (* live variables *)
110 :     succ : node option ref (* optional fake control-flow edge for when the EXIT is *)
111 :     (* not the CFG exit node *)
112 : jhr 2279 }
113 : jhr 1232
114 :     and rhs
115 : jhr 2804 = GLOBAL of global_var (* read global variable *)
116 :     | STATE of state_var (* read strand state variable *)
117 : jhr 1640 | VAR of var
118 : jhr 1232 | LIT of Literal.literal
119 :     | OP of Op.rator * var list
120 : jhr 1922 | APPLY of MathFuns.name * var list (* basis function application *)
121 : jhr 2279 | CONS of Ty.ty * var list (* tensor/sequence-value construction *)
122 : jhr 1232
123 :     and var = V of {
124 : jhr 2279 name : string, (* name *)
125 :     id : Stamp.stamp, (* unique ID *)
126 :     ty : Ty.ty, (* type *)
127 :     bind : var_bind ref, (* binding *)
128 :     useCnt : int ref, (* count of uses *)
129 :     props : PropList.holder
130 : jhr 1232 }
131 :    
132 :     and var_bind
133 :     = VB_NONE
134 : jhr 2279 | VB_RHS of rhs (* defined by an assignment (includes globals and state variables) *)
135 : jhr 1640 | VB_MULTIOP of int * Op.rator * var list
136 :     (* n'th result of operator in multi-assignment *)
137 : jhr 2825 | VB_PHI of var option list (* defined by a phi node *)
138 : jhr 2279 | VB_PARAM (* parameter to a strand *)
139 : jhr 1232
140 : jhr 2804 (***** global variables *****)
141 :     and global_var = GV of {
142 :     id : Stamp.stamp, (* variable's unique ID *)
143 :     name : string, (* variable's name *)
144 :     ty : Ty.ty, (* variable's type *)
145 :     bind : var ref, (* binding *)
146 :     useCnt : int ref, (* count of uses *)
147 :     input : bool, (* true for input variables *)
148 :     props : PropList.holder
149 :     }
150 :    
151 :     (***** strand state variables *****)
152 :     and state_var = SV of {
153 :     id : Stamp.stamp, (* variable's unique ID *)
154 :     name : string, (* variable's name *)
155 :     ty : Ty.ty, (* variable's type *)
156 :     output : bool, (* true for output variables *)
157 :     props : PropList.holder
158 :     }
159 :    
160 : jhr 1232 withtype assign = (var * rhs)
161 : jhr 1640 and massign = (var list * Op.rator * var list)
162 : jhr 2825 and phi = (var * var option list) (* NONE for fake edges *)
163 : jhr 1232
164 : jhr 2804 datatype assignment
165 :     = ASSGN of assign
166 :     | MASSGN of massign
167 :     | GASSGN of (global_var * var)
168 :     | SAV of (state_var * var)
169 : jhr 1232
170 :     (***** Program representation *****)
171 :    
172 :     datatype program = Program of {
173 : jhr 2279 props : StrandUtil.program_prop list,
174 : jhr 2804 globals : global_var list, (* global variables (both input and non-input) *)
175 :     inputInit : cfg, (* CFG to initialize input globals (if any) *)
176 :     globalInit : cfg, (* CFG to initialize other globals (if any) *)
177 : jhr 2279 initially : initially,
178 :     strands : strand list
179 : jhr 1232 }
180 :    
181 :     and initially = Initially of {
182 : jhr 2279 isArray : bool, (* true for initially array, false for collection *)
183 :     rangeInit : cfg, (* code to compute bounds of iteration *)
184 :     iters : (var * var * var) list, (* "for" i = min .. max *)
185 :     create : (cfg * Atom.atom * var list)
186 : jhr 1232 }
187 :    
188 :     and strand = Strand of {
189 : jhr 2279 name : Atom.atom,
190 :     params : var list,
191 :     state : state_var list,
192 :     stateInit : cfg,
193 :     methods : method list
194 : jhr 1232 }
195 :    
196 :     and method = Method of {
197 : jhr 2279 name : StrandUtil.method_name,
198 :     body : cfg (* method body *)
199 : jhr 1232 }
200 :    
201 : jhr 2804 (* operations on global variables *)
202 :     structure GlobalVar : sig
203 :     val new : bool * string * Ty.ty -> global_var
204 :     val name : global_var -> string
205 : jhr 2819 val uniqueName : global_var -> string
206 : jhr 2804 val ty : global_var -> Ty.ty
207 :     val binding : global_var -> var
208 :     val setBinding : global_var * var -> unit
209 :     val useCount : global_var -> int
210 :     val isInput : global_var -> bool
211 :     val same : global_var * global_var -> bool
212 :     val compare : global_var * global_var -> order
213 :     val hash : global_var -> word
214 :     val toString : global_var -> string
215 :     (* properties *)
216 :     val newProp : (global_var -> 'a) -> {
217 :     getFn : global_var -> 'a,
218 :     peekFn : global_var -> 'a option,
219 :     setFn : global_var * 'a -> unit,
220 :     clrFn : global_var -> unit
221 :     }
222 :     val newFlag : unit -> {
223 :     getFn : global_var -> bool,
224 :     setFn : global_var * bool -> unit
225 :     }
226 :     (* collections *)
227 :     structure Map : ORD_MAP where type Key.ord_key = global_var
228 :     structure Set : ORD_SET where type Key.ord_key = global_var
229 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = global_var
230 :     end
231 :    
232 : jhr 1640 (* operations on strand-state variables *)
233 :     structure StateVar : sig
234 :     val new : bool * string * Ty.ty -> state_var
235 : jhr 2279 val name : state_var -> string
236 :     val ty : state_var -> Ty.ty
237 : jhr 1640 val isOutput : state_var -> bool
238 : jhr 2279 val same : state_var * state_var -> bool
239 :     val compare : state_var * state_var -> order
240 :     val hash : state_var -> word
241 : jhr 1640 val toString : state_var -> string
242 :     (* properties *)
243 : jhr 2279 val newProp : (state_var -> 'a) -> {
244 :     getFn : state_var -> 'a,
245 :     peekFn : state_var -> 'a option,
246 :     setFn : state_var * 'a -> unit,
247 :     clrFn : state_var -> unit
248 :     }
249 :     val newFlag : unit -> {
250 :     getFn : state_var -> bool,
251 :     setFn : state_var * bool -> unit
252 :     }
253 : jhr 1640 (* collections *)
254 : jhr 2279 structure Map : ORD_MAP where type Key.ord_key = state_var
255 :     structure Set : ORD_SET where type Key.ord_key = state_var
256 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = state_var
257 : jhr 1640 end
258 :    
259 : jhr 1232 (* operations on CFGs *)
260 :     structure CFG : sig
261 :     (* the empty CFG *)
262 : jhr 2279 val empty : cfg
263 : jhr 1232 (* is a CFG empty? *)
264 : jhr 2279 val isEmpty : cfg -> bool
265 : jhr 1232 (* create a basic block from a list of assignments *)
266 : jhr 2279 val mkBlock : assignment list -> cfg
267 : jhr 1232 (* entry/exit nodes of a CFG *)
268 : jhr 2279 val entry : cfg -> node
269 :     val exit : cfg -> node
270 : jhr 1232 (* return the list of variables that are live at exit from a CFG *)
271 : jhr 2279 val liveAtExit : cfg -> var list
272 : jhr 1232 (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
273 :     * be in preorder with parents before children.
274 :     *)
275 : jhr 2279 val sort : cfg -> node list
276 : jhr 2804 (* apply a function to all of the nodes in the graph rooted at the entry to the CFG *)
277 : jhr 2279 val apply : (node -> unit) -> cfg -> unit
278 : jhr 1232 (*
279 :     (* rewrite a CFG by applying a partial function to the nodes in the graph. If NONE is returned,
280 :     * then no change to the node, if SOME(cfg) is returned, then the node is replaced by the
281 :     * subgraph, which may be empty. This function returns true if any nodes were rewritten.
282 :     *)
283 : jhr 2279 val rewrite : (node -> cfg option) -> cfg -> bool
284 : jhr 1232 *)
285 :     (* delete a simple node from a CFG *)
286 : jhr 2279 val deleteNode : node -> unit
287 : jhr 1232 (* replace a simple node in a cfg with a different simple node *)
288 : jhr 2279 val replaceNode : (node * node) -> unit
289 : jhr 1232 (* replace a simple node in a cfg with a subgraph *)
290 : jhr 2279 val replaceNodeWithCFG : (node * cfg) -> unit
291 : jhr 1232 (* concatenate two CFGs *)
292 : jhr 2279 val concat : cfg * cfg -> cfg
293 : jhr 1640 (* prepend a node to a CFG *)
294 : jhr 2279 val prependNode : node * cfg -> cfg
295 : jhr 1232 (* append a node to a CFG *)
296 : jhr 2279 val appendNode : cfg * node -> cfg
297 : jhr 2804 (* insert a block of assignments at the beginning of the CFG. If the CFG has an ENTRY
298 :     * node, then the block is inserted immediatly following the entry.
299 :     *)
300 :     val prependBlock : assignment list * cfg -> cfg
301 :     (* insert a block of assignments at the end of the CFG argument If the CFG has an EXIT
302 :     * node, then the block is inserted immediatly following the exit.
303 :     *)
304 :     val appendBlock : cfg * assignment list -> cfg
305 : jhr 1232 (* update the exit of a CFG by modifying the live variable list *)
306 : jhr 2279 val updateExit : cfg * (var list -> var list) -> cfg
307 : jhr 1232 end
308 :    
309 :     (* operations on CFG nodes *)
310 :     structure Node : sig
311 : jhr 2279 val id : node -> Stamp.stamp
312 :     val kind : node -> node_kind
313 :     val same : node * node -> bool
314 :     val compare : node * node -> order
315 :     val hash : node -> word
316 :     val toString : node -> string
317 :     val isNULL : node -> bool
318 : jhr 2825 val isReachable : node -> bool
319 : jhr 1232 (* variable defs and uses; may include duplicates *)
320 : jhr 2279 val uses : node -> var list
321 :     val defs : node -> var list
322 : jhr 1301 (* dummy node with NULL kind *)
323 : jhr 2279 val dummy : node
324 : jhr 1232 (* CFG edges *)
325 : jhr 2279 val hasPred : node -> bool
326 :     val preds : node -> node list
327 :     val setPred : node * node -> unit
328 :     val hasSucc : node -> bool
329 :     val succs : node -> node list
330 :     val setSucc : node * node -> unit
331 :     val setTrueBranch : node * node -> unit (* set trueBranch successor for COND node *)
332 :     val setFalseBranch : node * node -> unit (* set falseBranch successor for COND node *)
333 :     val addEdge : node * node -> unit
334 : jhr 1232 (* replace the edge src-->oldDst by the edge src-->dst *)
335 : jhr 2279 val replaceInEdge : {src : node, oldDst : node, dst : node} -> unit
336 : jhr 1232 (* replace the edge oldSrc-->dst by the edge src-->dst *)
337 : jhr 2279 val replaceOutEdge : {oldSrc : node, src : node, dst : node} -> unit
338 : jhr 1232 (* constructors *)
339 : jhr 2279 val mkENTRY : unit -> node
340 : jhr 2825 val mkJOIN : phi list -> node
341 : jhr 2279 val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node
342 :     val mkCOM : string list -> node
343 :     val mkASSIGN : assign -> node
344 :     val mkMASSIGN : massign -> node
345 : jhr 2804 val mkGASSIGN : (global_var * var) -> node
346 : jhr 2279 val mkNEW : {strand : Atom.atom, args : var list} -> node
347 : jhr 1640 val mkSAVE : (state_var * var) -> node
348 : jhr 2279 val mkEXIT : ExitKind.kind * var list -> node
349 :     val mkFRAGMENT : var list -> node
350 :     val mkSINIT : unit -> node
351 :     val mkRETURN : var list -> node
352 :     val mkACTIVE : unit -> node
353 :     val mkSTABILIZE : unit -> node
354 :     val mkDIE : unit -> node
355 : jhr 2825 val mkUNREACHABLE : unit -> node
356 : jhr 1232 (* properties *)
357 : jhr 2279 val newProp : (node -> 'a) -> {
358 :     getFn : node -> 'a,
359 :     peekFn : node -> 'a option,
360 :     setFn : node * 'a -> unit,
361 :     clrFn : node -> unit
362 :     }
363 :     val newFlag : unit -> {
364 :     getFn : node -> bool,
365 :     setFn : node * bool -> unit
366 :     }
367 : jhr 1232 end
368 :    
369 :     (* operations on variables *)
370 :     structure Var : sig
371 : jhr 2279 val new : string * Ty.ty -> var
372 :     val copy : var -> var
373 :     val name : var -> string
374 :     val ty : var -> Ty.ty
375 :     val binding : var -> var_bind
376 :     val setBinding : var * var_bind -> unit
377 :     val useCount : var -> int
378 :     val same : var * var -> bool
379 :     val compare : var * var -> order
380 :     val hash : var -> word
381 :     val toString : var -> string
382 : jhr 1232 (* properties *)
383 : jhr 2279 val newProp : (var -> 'a) -> {
384 :     getFn : var -> 'a,
385 :     peekFn : var -> 'a option,
386 :     setFn : var * 'a -> unit,
387 :     clrFn : var -> unit
388 :     }
389 :     val newFlag : unit -> {
390 :     getFn : var -> bool,
391 :     setFn : var * bool -> unit
392 :     }
393 : jhr 1232 (* collections *)
394 : jhr 2279 structure Map : ORD_MAP where type Key.ord_key = var
395 :     structure Set : ORD_SET where type Key.ord_key = var
396 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
397 : jhr 1232 end
398 :    
399 :     (* operations on RHS expressions *)
400 :     structure RHS : sig
401 : jhr 2279 val toString : rhs -> string
402 :     val vars : rhs -> var list
403 :     val map : (var -> var) -> rhs -> rhs
404 :     val app : (var -> unit) -> rhs -> unit
405 : jhr 1232 end
406 :    
407 :     (* return a string representation of a variable binding *)
408 :     val vbToString : var_bind -> string
409 :    
410 :     (* return a string representation of a PHI node *)
411 :     val phiToString : phi -> string
412 :    
413 :     (* return a string representation of an assignment *)
414 :     val assignToString : assign -> string
415 : jhr 1640 val massignToString : massign -> string
416 : jhr 2683 val assignmentToString : assignment -> string
417 : jhr 1232
418 :     end

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