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 1301 - (view) (download)
Original Path: trunk/src/compiler/IL/ssa-sig.sml

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 :     * 1) The exit of the globalInit CFG has kind RETURN and the scope of the live variables
13 :     * is the whole program.
14 :     *
15 :     * 2) The scope of the parameters of a strand is the stateInit CFG and the methods of the
16 :     * strand.
17 :     *
18 :     * 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 :     *
22 :     * 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 :     *
26 :     * 5) Each method has a list of variables, called stateIn, which corresponds to the
27 :     * variables in the strand's state-variable list.
28 :     *
29 :     * 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 :     *)
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 :     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 :     }
49 :    
50 :     and node = ND of {
51 :     id : Stamp.stamp,
52 :     props : PropList.holder,
53 :     kind : node_kind
54 :     }
55 :    
56 :     and node_kind
57 :     = NULL
58 :     | ENTRY of {
59 :     succ : node ref
60 :     }
61 :     | JOIN of {
62 :     preds : node list ref,
63 :     phis : phi list ref,
64 :     succ : node ref
65 :     }
66 :     | COND of {
67 :     pred : node ref,
68 :     cond : var,
69 :     trueBranch : node ref,
70 :     falseBranch : node ref
71 :     }
72 :     | COM of { (* comment *)
73 :     pred : node ref,
74 :     text : string list,
75 :     succ : node ref
76 :     }
77 :     | ASSIGN of { (* assignment *)
78 :     pred : node ref,
79 :     stm : assign,
80 :     succ : node ref
81 :     }
82 :     | NEW of { (* create new strand instance *)
83 :     pred : node ref,
84 :     strand : Atom.atom,
85 :     args : var list,
86 :     succ : node ref
87 :     }
88 :     | EXIT of { (* includes die and stabilize *)
89 :     pred : node ref,
90 :     kind : ExitKind.kind, (* kind of exit node *)
91 :     live : var list (* live variables *)
92 :     }
93 :    
94 :     and rhs
95 :     = VAR of var
96 :     | LIT of Literal.literal
97 :     | OP of Op.rator * var list
98 :     | APPLY of ILBasis.name * var list (* basis function application *)
99 :     | CONS of Ty.ty * var list (* tensor/sequence-value construction *)
100 :    
101 :     and var = V of {
102 :     name : string, (* name *)
103 :     id : Stamp.stamp, (* unique ID *)
104 :     ty : Ty.ty, (* type *)
105 :     bind : var_bind ref, (* binding *)
106 :     useCnt : int ref, (* count of uses *)
107 :     props : PropList.holder
108 :     }
109 :    
110 :     and var_bind
111 :     = VB_NONE
112 :     | VB_RHS of rhs (* defined by an assignment (includes globals and state variables) *)
113 :     | VB_PHI of var list (* defined by a phi node *)
114 :     | VB_PARAM (* parameter to a strand *)
115 :    
116 :     withtype assign = (var * rhs)
117 :     and phi = (var * var list)
118 :    
119 :    
120 :     (***** Program representation *****)
121 :    
122 :     datatype program = Program of {
123 :     globalInit : cfg,
124 :     initially : initially,
125 :     strands : strand list
126 :     }
127 :    
128 :     and initially = Initially of {
129 :     isArray : bool, (* true for initially array, false for collection *)
130 :     rangeInit : cfg, (* code to compute bounds of iteration *)
131 :     iters : (var * var * var) list, (* "for" i = min .. max *)
132 :     create : (cfg * Atom.atom * var list)
133 :     }
134 :    
135 :     and strand = Strand of {
136 :     name : Atom.atom,
137 :     params : var list,
138 :     state : (bool * var) list, (* output variables are marked with true *)
139 :     stateInit : cfg,
140 :     methods : method list
141 :     }
142 :    
143 :     and method = Method of {
144 :     name : Atom.atom,
145 :     stateIn : var list, (* names of state variables on method entry *)
146 :     body : cfg (* method body *)
147 :     }
148 :    
149 :     (* operations on CFGs *)
150 :     structure CFG : sig
151 :     (* the empty CFG *)
152 :     val empty : cfg
153 :     (* is a CFG empty? *)
154 :     val isEmpty : cfg -> bool
155 :     (* create a basic block from a list of assignments *)
156 :     val mkBlock : assign list -> cfg
157 :     (* entry/exit nodes of a CFG *)
158 :     val entry : cfg -> node
159 :     val exit : cfg -> node
160 :     (* return the list of variables that are live at exit from a CFG *)
161 :     val liveAtExit : cfg -> var list
162 :     (* DFS sorting of the graph rooted at the entry to a statement; the resulting list will
163 :     * be in preorder with parents before children.
164 :     *)
165 :     val sort : cfg -> node list
166 :     (* apply a function to all of the nodes in the graph rooted at the entry to the statement *)
167 :     val apply : (node -> unit) -> cfg -> unit
168 :     (*
169 :     (* rewrite a CFG by applying a partial function to the nodes in the graph. If NONE is returned,
170 :     * then no change to the node, if SOME(cfg) is returned, then the node is replaced by the
171 :     * subgraph, which may be empty. This function returns true if any nodes were rewritten.
172 :     *)
173 :     val rewrite : (node -> cfg option) -> cfg -> bool
174 :     *)
175 :     (* delete a simple node from a CFG *)
176 :     val deleteNode : node -> unit
177 :     (* replace a simple node in a cfg with a different simple node *)
178 :     val replaceNode : (node * node) -> unit
179 :     (* replace a simple node in a cfg with a subgraph *)
180 :     val replaceNodeWithCFG : (node * cfg) -> unit
181 :     (* concatenate two CFGs *)
182 :     val concat : cfg * cfg -> cfg
183 :     (* append a node to a CFG *)
184 :     val appendNode : cfg * node -> cfg
185 :     (* update the exit of a CFG by modifying the live variable list *)
186 :     val updateExit : cfg * (var list -> var list) -> cfg
187 :     end
188 :    
189 :     (* operations on CFG nodes *)
190 :     structure Node : sig
191 :     val id : node -> Stamp.stamp
192 :     val kind : node -> node_kind
193 :     val same : node * node -> bool
194 :     val compare : node * node -> order
195 :     val hash : node -> word
196 :     val toString : node -> string
197 :     val isNULL : node -> bool
198 :     (* variable defs and uses; may include duplicates *)
199 :     val uses : node -> var list
200 :     val defs : node -> var list
201 : jhr 1301 (* dummy node with NULL kind *)
202 : jhr 1232 val dummy : node
203 :     (* CFG edges *)
204 :     val hasPred : node -> bool
205 :     val preds : node -> node list
206 :     val setPred : node * node -> unit
207 :     val hasSucc : node -> bool
208 :     val succs : node -> node list
209 :     val setSucc : node * node -> unit
210 :     val setTrueBranch : node * node -> unit (* set trueBranch successor for COND node *)
211 :     val setFalseBranch : node * node -> unit (* set falseBranch successor for COND node *)
212 :     val addEdge : node * node -> unit
213 :     (* replace the edge src-->oldDst by the edge src-->dst *)
214 :     val replaceInEdge : {src : node, oldDst : node, dst : node} -> unit
215 :     (* replace the edge oldSrc-->dst by the edge src-->dst *)
216 :     val replaceOutEdge : {oldSrc : node, src : node, dst : node} -> unit
217 :     (* constructors *)
218 :     val mkENTRY : unit -> node
219 :     val mkJOIN : (var * var list) list -> node
220 :     val mkCOND : {cond : var, trueBranch : node, falseBranch : node} -> node
221 :     val mkCOM : string list -> node
222 :     val mkASSIGN : assign -> node
223 :     val mkNEW : {strand : Atom.atom, args : var list} -> node
224 :     val mkEXIT : ExitKind.kind * var list -> node
225 :     val mkFRAGMENT : var list -> node
226 :     val mkSINIT : var list -> node
227 :     val mkRETURN : var list -> node
228 :     val mkACTIVE : var list -> node
229 :     val mkSTABILIZE : var list -> node
230 :     val mkDIE : unit -> node
231 :     (* properties *)
232 :     val newProp : (node -> 'a) -> {
233 :     getFn : node -> 'a,
234 :     peekFn : node -> 'a option,
235 :     setFn : node * 'a -> unit,
236 :     clrFn : node -> unit
237 :     }
238 :     val newFlag : unit -> {
239 :     getFn : node -> bool,
240 :     setFn : node * bool -> unit
241 :     }
242 :     end
243 :    
244 :     (* operations on variables *)
245 :     structure Var : sig
246 :     val new : string * Ty.ty -> var
247 :     val copy : var -> var
248 :     val name : var -> string
249 :     val ty : var -> Ty.ty
250 :     val binding : var -> var_bind
251 :     val setBinding : var * var_bind -> unit
252 :     val useCount : var -> int
253 :     val same : var * var -> bool
254 :     val compare : var * var -> order
255 :     val hash : var -> word
256 :     val toString : var -> string
257 :     (* properties *)
258 :     val newProp : (var -> 'a) -> {
259 :     getFn : var -> 'a,
260 :     peekFn : var -> 'a option,
261 :     setFn : var * 'a -> unit,
262 :     clrFn : var -> unit
263 :     }
264 :     val newFlag : unit -> {
265 :     getFn : var -> bool,
266 :     setFn : var * bool -> unit
267 :     }
268 :     (* collections *)
269 :     structure Map : ORD_MAP where type Key.ord_key = var
270 :     structure Set : ORD_SET where type Key.ord_key = var
271 :     structure Tbl : MONO_HASH_TABLE where type Key.hash_key = var
272 :     end
273 :    
274 :     (* operations on RHS expressions *)
275 :     structure RHS : sig
276 :     val toString : rhs -> string
277 :     val vars : rhs -> var list
278 :     val map : (var -> var) -> rhs -> rhs
279 :     val app : (var -> unit) -> rhs -> unit
280 :     end
281 :    
282 :     (* return a string representation of a variable binding *)
283 :     val vbToString : var_bind -> string
284 :    
285 :     (* return a string representation of a PHI node *)
286 :     val phiToString : phi -> string
287 :    
288 :     (* return a string representation of an assignment *)
289 :     val assignToString : assign -> string
290 :    
291 :     end

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