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

SCM Repository

[diderot] Annotation of /branches/vis15/src/compiler/cfg-ir/ssa-sig.sml
ViewVC logotype

Annotation of /branches/vis15/src/compiler/cfg-ir/ssa-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3501 - (view) (download)

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

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