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 3349 - (view) (download)

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

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