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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3839 - (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 2364 * 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 2364 * 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 2364 * 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 2364 * 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 2364 * 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 2364 * 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 : jhr 1640 (***** strand state variables *****)
46 :    
47 :     datatype state_var = SV of {
48 : jhr 2364 id : Stamp.stamp, (* variable's unique ID *)
49 : jhr 1640 name : string, (* variable's name *)
50 :     ty : Ty.ty, (* variable's type *)
51 :     output : bool, (* true for output variables *)
52 : jhr 2364 props : PropList.holder
53 : jhr 1640 }
54 :    
55 : jhr 1232 (***** CFG *****)
56 :    
57 :     datatype cfg = CFG of {
58 : jhr 2364 entry : node, (* the entry node of a graph; not necessarily an ENTRY node *)
59 :     exit : node (* the exit node of a graph; not necessarily an EXIT node. *)
60 : jhr 1232 }
61 :    
62 :     and node = ND of {
63 : jhr 2364 id : Stamp.stamp,
64 :     props : PropList.holder,
65 :     kind : node_kind
66 : jhr 1232 }
67 :    
68 :     and node_kind
69 :     = NULL
70 :     | ENTRY of {
71 : jhr 2364 succ : node ref
72 :     }
73 : jhr 1232 | JOIN of {
74 : jhr 2364 preds : node list ref,
75 :     phis : phi list ref,
76 :     succ : node ref
77 :     }
78 : jhr 1232 | COND of {
79 : jhr 2364 pred : node ref,
80 :     cond : var,
81 :     trueBranch : node ref,
82 :     falseBranch : node ref
83 :     }
84 : lamonts 2083 | FOREACH of {
85 : jhr 2298 pred : node ref,
86 :     cond : var,
87 :     phis : phi list ref,
88 :     stmBranch : node ref,
89 :     varStrandName : string ref,
90 :     shouldReplace : bool ref,
91 :     stmBranchDone : bool ref,
92 :     succ : node ref
93 :     }
94 : jhr 2364 | COM of { (* comment *)
95 :     pred : node ref,
96 :     text : string list,
97 :     succ : node ref
98 :     }
99 :     | ASSIGN of { (* assignment *)
100 :     pred : node ref,
101 :     stm : assign,
102 :     succ : node ref
103 :     }
104 :     | MASSIGN of { (* multi-assignment *)
105 :     pred : node ref,
106 :     stm : massign,
107 :     succ : node ref
108 :     }
109 :     | NEW of { (* create new strand instance *)
110 :     pred : node ref,
111 :     strand : Atom.atom,
112 :     args : var list,
113 :     succ : node ref
114 :     }
115 : jhr 1640 | SAVE of { (* save state variable *)
116 :     pred: node ref,
117 :     lhs : state_var,
118 :     rhs : var,
119 :     succ : node ref
120 :     }
121 : jhr 2364 | EXIT of { (* includes die and stabilize *)
122 :     pred : node ref,
123 :     kind : ExitKind.kind, (* kind of exit node *)
124 :     live : var list (* live variables *)
125 :     }
126 : jhr 1232
127 : lamonts 2098 and strand_set
128 : lamonts 2203 = SS_All
129 : lamonts 2098 | SS_Stable
130 : lamonts 2203 | SS_Active
131 : lamonts 2098
132 : jhr 1232 and rhs
133 : jhr 1640 = STATE of state_var (* read strand state variable *)
134 :     | VAR of var
135 : jhr 1232 | LIT of Literal.literal
136 : lamonts 2083 | SELECTOR of var * Atom.atom
137 : lamonts 2101 | STRAND_SET of strand_set list
138 : jhr 1232 | OP of Op.rator * var list
139 : jhr 1922 | APPLY of MathFuns.name * var list (* basis function application *)
140 : jhr 2364 | CONS of Ty.ty * var list (* tensor/sequence-value construction *)
141 : jhr 1232
142 :     and var = V of {
143 : jhr 2364 name : string, (* name *)
144 :     id : Stamp.stamp, (* unique ID *)
145 :     ty : Ty.ty, (* type *)
146 :     bind : var_bind ref, (* binding *)
147 :     useCnt : int ref, (* count of uses *)
148 :     props : PropList.holder
149 : jhr 1232 }
150 :    
151 :     and var_bind
152 :     = VB_NONE
153 : jhr 2364 | VB_RHS of rhs (* defined by an assignment (includes globals and state variables) *)
154 : jhr 1640 | VB_MULTIOP of int * Op.rator * var list
155 :     (* n'th result of operator in multi-assignment *)
156 : jhr 2364 | VB_PHI of var list (* defined by a phi node *)
157 :     | VB_PARAM (* parameter to a strand *)
158 : jhr 1232
159 :     withtype assign = (var * rhs)
160 : jhr 1640 and massign = (var list * Op.rator * var list)
161 : jhr 2364 and phi = (var * var list)
162 : jhr 1232
163 : jhr 1640 datatype assignment = ASSGN of assign | MASSGN of massign
164 : jhr 1232
165 : jhr 1640
166 : jhr 1232 (***** Program representation *****)
167 :    
168 :     datatype program = Program of {
169 : jhr 2364 props : StrandUtil.program_prop list,
170 : lamonts 2467 mutableGlobals: var list,
171 : jhr 2364 globalInit : cfg,
172 :     globalBlock : cfg,
173 : jhr 3839 reductionBlock: (cfg * int list), (* the int list is the schedule for the reductions *)
174 : jhr 2364 initially : initially,
175 :     strands : strand list
176 : jhr 1232 }
177 :    
178 :     and initially = Initially of {
179 : jhr 2364 isArray : bool, (* true for initially array, false for collection *)
180 :     rangeInit : cfg, (* code to compute bounds of iteration *)
181 :     iters : (var * var * var) list, (* "for" i = min .. max *)
182 :     create : (cfg * Atom.atom * var list)
183 : jhr 1232 }
184 :    
185 :     and strand = Strand of {
186 : jhr 2364 name : Atom.atom,
187 :     params : var list,
188 :     state : state_var list,
189 :     stateInit : cfg,
190 :     methods : method list
191 : jhr 1232 }
192 :    
193 :     and method = Method of {
194 : jhr 2364 name : StrandUtil.method_name,
195 :     body : cfg (* method body *)
196 : jhr 1232 }
197 :    
198 : jhr 1640 (* operations on strand-state variables *)
199 :     structure StateVar : sig
200 :     val new : bool * string * Ty.ty -> state_var
201 : jhr 2364 val name : state_var -> string
202 :     val ty : state_var -> Ty.ty
203 : jhr 1640 val isOutput : state_var -> bool
204 : jhr 2364 val same : state_var * state_var -> bool
205 :     val compare : state_var * state_var -> order
206 :     val hash : state_var -> word
207 : jhr 1640 val toString : state_var -> string
208 :     (* properties *)
209 : jhr 2364 val newProp : (state_var -> 'a) -> {
210 :     getFn : state_var -> 'a,
211 :     peekFn : state_var -> 'a option,
212 :     setFn : state_var * 'a -> unit,
213 :     clrFn : state_var -> unit
214 :     }
215 :     val newFlag : unit -> {
216 :     getFn : state_var -> bool,
217 :     setFn : state_var * bool -> unit
218 :     }
219 : jhr 1640 (* collections *)
220 : jhr 2364 structure Map : ORD_MAP where type Key.ord_key = state_var
221 :     structure Set : ORD_SET where type Key.ord_key = state_var
222 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = state_var
223 : jhr 1640 end
224 :    
225 : jhr 1232 (* operations on CFGs *)
226 :     structure CFG : sig
227 :     (* the empty CFG *)
228 : jhr 2364 val empty : cfg
229 : jhr 1232 (* is a CFG empty? *)
230 : jhr 2364 val isEmpty : cfg -> bool
231 : jhr 1232 (* create a basic block from a list of assignments *)
232 : jhr 2364 val mkBlock : assignment list -> cfg
233 : jhr 1232 (* entry/exit nodes of a CFG *)
234 : jhr 2364 val entry : cfg -> node
235 :     val exit : cfg -> node
236 : jhr 1232 (* return the list of variables that are live at exit from a CFG *)
237 : jhr 2364 val liveAtExit : cfg -> var list
238 : jhr 1232 (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
239 :     * be in preorder with parents before children.
240 :     *)
241 : jhr 2364 val sort : cfg -> node list
242 : jhr 1232 (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)
243 : jhr 2364 val apply : (node -> unit) -> cfg -> unit
244 : jhr 1232 (*
245 :     (* rewrite a CFG by applying a partial function to the nodes in the graph. If NONE is returned,
246 :     * then no change to the node, if SOME(cfg) is returned, then the node is replaced by the
247 :     * subgraph, which may be empty. This function returns true if any nodes were rewritten.
248 :     *)
249 : jhr 2364 val rewrite : (node -> cfg option) -> cfg -> bool
250 : jhr 1232 *)
251 :     (* delete a simple node from a CFG *)
252 : jhr 2364 val deleteNode : node -> unit
253 : jhr 1232 (* replace a simple node in a cfg with a different simple node *)
254 : jhr 2364 val replaceNode : (node * node) -> unit
255 : jhr 1232 (* replace a simple node in a cfg with a subgraph *)
256 : jhr 2364 val replaceNodeWithCFG : (node * cfg) -> unit
257 : jhr 1232 (* concatenate two CFGs *)
258 : jhr 2364 val concat : cfg * cfg -> cfg
259 : jhr 1640 (* prepend a node to a CFG *)
260 : jhr 2364 val prependNode : node * cfg -> cfg
261 : jhr 1232 (* append a node to a CFG *)
262 : jhr 2364 val appendNode : cfg * node -> cfg
263 : jhr 1232 (* update the exit of a CFG by modifying the live variable list *)
264 : jhr 2364 val updateExit : cfg * (var list -> var list) -> cfg
265 : jhr 1232 end
266 :    
267 :     (* operations on CFG nodes *)
268 :     structure Node : sig
269 : jhr 2364 val id : node -> Stamp.stamp
270 :     val kind : node -> node_kind
271 :     val same : node * node -> bool
272 :     val compare : node * node -> order
273 :     val hash : node -> word
274 :     val toString : node -> string
275 :     val isNULL : node -> bool
276 : jhr 1232 (* variable defs and uses; may include duplicates *)
277 : jhr 2364 val uses : node -> var list
278 :     val defs : node -> var list
279 : jhr 1301 (* dummy node with NULL kind *)
280 : jhr 2364 val dummy : node
281 : jhr 1232 (* CFG edges *)
282 : jhr 2364 val hasPred : node -> bool
283 :     val preds : node -> node list
284 :     val setPred : node * node -> unit
285 :     val hasSucc : node -> bool
286 :     val succs : node -> node list
287 :     val setSucc : node * node -> unit
288 :     val setStmBranch : node * node -> unit (* set statement branch succesor for FOREACH node *)
289 :     val setTrueBranch : node * node -> unit (* set trueBranch successor for COND node *)
290 :     val setFalseBranch : node * node -> unit (* set falseBranch successor for COND node *)
291 :     val addEdge : node * node -> unit
292 : jhr 1232 (* replace the edge src-->oldDst by the edge src-->dst *)
293 : jhr 2364 val replaceInEdge : {src : node, oldDst : node, dst : node} -> unit
294 : jhr 1232 (* replace the edge oldSrc-->dst by the edge src-->dst *)
295 : jhr 2364 val replaceOutEdge : {oldSrc : node, src : node, dst : node} -> unit
296 : jhr 1232 (* constructors *)
297 : jhr 2364 val mkENTRY : unit -> node
298 :     val mkJOIN : (var * var list) list -> node
299 :     val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node
300 :     val mkFOREACH : {cond: var, stmBranch: node, sName : string, phis:(var * var list) list} -> node
301 :     val mkCOM : string list -> node
302 :     val mkASSIGN : assign -> node
303 :     val mkMASSIGN : massign -> node
304 :     val mkNEW : {strand : Atom.atom, args : var list} -> node
305 : jhr 1640 val mkSAVE : (state_var * var) -> node
306 : jhr 2364 val mkEXIT : ExitKind.kind * var list -> node
307 :     val mkFRAGMENT : var list -> node
308 :     val mkSINIT : unit -> node
309 :     val mkRETURN : var list -> node
310 :     val mkACTIVE : unit -> node
311 :     val mkSTABILIZE : unit -> node
312 :     val mkDIE : unit -> node
313 : jhr 1232 (* properties *)
314 : jhr 2364 val newProp : (node -> 'a) -> {
315 :     getFn : node -> 'a,
316 :     peekFn : node -> 'a option,
317 :     setFn : node * 'a -> unit,
318 :     clrFn : node -> unit
319 :     }
320 :     val newFlag : unit -> {
321 :     getFn : node -> bool,
322 :     setFn : node * bool -> unit
323 :     }
324 : jhr 1232 end
325 :    
326 :     (* operations on variables *)
327 :     structure Var : sig
328 : jhr 2364 val new : string * Ty.ty -> var
329 :     val copy : var -> var
330 :     val name : var -> string
331 :     val ty : var -> Ty.ty
332 :     val binding : var -> var_bind
333 :     val setBinding : var * var_bind -> unit
334 :     val useCount : var -> int
335 :     val same : var * var -> bool
336 :     val compare : var * var -> order
337 :     val hash : var -> word
338 :     val toString : var -> string
339 : jhr 1232 (* properties *)
340 : jhr 2364 val newProp : (var -> 'a) -> {
341 :     getFn : var -> 'a,
342 :     peekFn : var -> 'a option,
343 :     setFn : var * 'a -> unit,
344 :     clrFn : var -> unit
345 :     }
346 :     val newFlag : unit -> {
347 :     getFn : var -> bool,
348 :     setFn : var * bool -> unit
349 :     }
350 : jhr 1232 (* collections *)
351 : jhr 2364 structure Map : ORD_MAP where type Key.ord_key = var
352 :     structure Set : ORD_SET where type Key.ord_key = var
353 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
354 : jhr 1232 end
355 :    
356 :     (* operations on RHS expressions *)
357 :     structure RHS : sig
358 : jhr 2298 (* val reductionSame : reduction * reduction -> bool *)
359 :     (* FIXME: why are these strand_set functions defined here? *)
360 : jhr 2364 val strandSetSame : strand_set list * strand_set list -> bool
361 : jhr 2298 (* val reductionToString: reduction -> string *)
362 : jhr 2364 val toStringSets : strand_set list -> string list
363 :     val toString : rhs -> string
364 :     val vars : rhs -> var list
365 :     val map : (var -> var) -> rhs -> rhs
366 :     val app : (var -> unit) -> rhs -> unit
367 : jhr 1232 end
368 :    
369 :     (* return a string representation of a variable binding *)
370 :     val vbToString : var_bind -> string
371 :    
372 :     (* return a string representation of a PHI node *)
373 :     val phiToString : phi -> string
374 :    
375 :     (* return a string representation of an assignment *)
376 :     val assignToString : assign -> string
377 : jhr 1640 val massignToString : massign -> string
378 : jhr 1232
379 :     end

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