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

SCM Repository

[diderot] Annotation of /trunk/src/compiler/tree-il/var-analysis.sml
ViewVC logotype

Annotation of /trunk/src/compiler/tree-il/var-analysis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1115 - (view) (download)

1 : jhr 1115 (* var-analysis.sml
2 :     *
3 :     * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * The variable analysis phase does four things:
7 :     *
8 :     * 1) determine which variables that are bound at global level are used in strand
9 :     * or method scopes.
10 :     *
11 :     * 2) determine which strand parameters are used in methods (and thus have to be
12 :     * shadowed by instance variables).
13 :     *
14 :     * 3) determine which instance variables are invariant over all strands, and thus
15 :     * can be lifted to global scope, and which strand variables are invariant across
16 :     * the strand execution.
17 :     *
18 :     * 4) eliminate unused and useless variables.
19 :     *)
20 :    
21 :     structure VarAnalysis : sig
22 :    
23 :     structure IL : SSA
24 :    
25 :     (* the scope of a variable describes the extent of its use. *)
26 :     datatype scope
27 :     = Global (* bound globally and used in strands *)
28 :     | StrandParam (* parameter to strand creation *)
29 :     | StrandConstState (* state variable that is invariant over strand execution *)
30 :     | StrandState (* strand state variable *)
31 :     | Local (* local binding not used in nested scopes *)
32 :    
33 :     val scopeToString : scope -> string
34 :    
35 :     val varScope : IL.var -> scope
36 :    
37 :     val isGlobal : IL.var -> bool
38 :    
39 :     val optimize : IL.program -> IL.program
40 :    
41 :     end = struct
42 :    
43 :     structure IL = LowIL
44 :     structure V = IL.Var
45 :     structure VMap = V.Map
46 :    
47 :     datatype scope
48 :     = Global (* bound globally and used in strands *)
49 :     | StrandParam (* parameter to strand creation *)
50 :     | StrandConstState (* state variable that is invariant over strand execution *)
51 :     | StrandState (* strand state variable *)
52 :     | Local (* local binding not used in nested scopes *)
53 :    
54 :     fun scopeToString s = (case s
55 :     of Global => "Global"
56 :     | StrandParam => "StrandParam"
57 :     | StrandConstState => "StrandConstState"
58 :     | StrandState => "StrandState"
59 :     | Local => "Local"
60 :     (* end case *))
61 :    
62 :     (* nesting depths of scopes *)
63 :     val undefinedScope = 0
64 :     val globalScope = 1 (* global initialization *)
65 :     val initiallyScope = 2 (* initial strand creation *)
66 :     val paramScope = 2 (* strand parameter *)
67 :     val strandScope = 3 (* strand initialization *)
68 :     val methodScope = 4 (* defined/used in a strand method *)
69 :     val methodStateScope = 5 (* state variable in a strand method *)
70 :    
71 :     (* property that maps variables to the depth where they are bound *)
72 :     val {getFn=getBindDepth : IL.var -> int, setFn=setBindDepth, clrFn=clrBindDepth, ...} =
73 :     V.newProp (fn x => raise Fail("no binding depth set for " ^ V.toString x))
74 :    
75 :     (* property that maps variables to the maximum depth where they are used *)
76 :     val {peekFn=peekUseDepth : IL.var -> int option, setFn=setUseDepth, clrFn=clrUseDepth, ...} =
77 :     V.newProp (fn x => raise Fail("no use depth set for " ^ V.toString x))
78 :     fun getUseDepth x = (case peekUseDepth x
79 :     of NONE => undefinedScope
80 :     | SOME d => d
81 :     (* end case *))
82 :    
83 :     (* property that maps variables to their assigned scope *)
84 :     val {getFn=varScope : IL.var -> scope, setFn=setVarScope, ...} = V.newProp (fn x => Local)
85 :    
86 :     (* boolean flag on strand-state variables that vary across method executions *)
87 :     val {getFn=isVarying, setFn=setVarying} = V.newFlag ()
88 :    
89 :     fun isGlobal x = (varScope x = Global)
90 :    
91 :     (* walk the program determining the binding and maximum use depths of all variables *)
92 :     fun assignDepths (IL.Program{
93 :     globalInit,
94 :     initially = IL.Initially{rangeInit, iters, create, ...},
95 :     strands
96 :     }) = let
97 :     fun setMaxUse depth x = (case peekUseDepth x
98 :     of NONE => setUseDepth(x, depth)
99 :     | SOME d => if (depth > d) then setUseDepth(x, depth) else ()
100 :     (* end case *))
101 :     fun doNode depth nd = (case IL.Node.kind nd
102 :     of IL.EXIT{kind, live, ...} => (case kind
103 :     of ExitKind.FRAGMENT => List.app (setMaxUse depth) live
104 :     | ExitKind.RETURN => List.app (setMaxUse depth) live
105 :     | _ => () (* we don't count ACTIVE, etc. as uses *)
106 :     (* end case *))
107 :     | _ => (
108 :     List.app (setMaxUse depth) (IL.Node.uses nd);
109 :     List.app (fn x => setBindDepth(x, depth)) (IL.Node.defs nd))
110 :     (* end case *))
111 :     fun doCFG (depth, cfg) = IL.CFG.apply (doNode depth) cfg
112 :     fun doMethod state (IL.Method{stateIn, body, ...}) = let
113 :     val stateInVec = Vector.fromList stateIn
114 :     (* check to see which state variables are invariant on the path from
115 :     * the method entry to this point.
116 :     *)
117 :     fun chk (_, []) = ()
118 :     | chk (i, x::xs) = let
119 :     val x' = Vector.sub(stateInVec, i)
120 :     in
121 :     if V.same(x, x')
122 :     then ()
123 :     else setVarying (x', true);
124 :     chk (i+1, xs)
125 :     end
126 :     fun doMethodNode nd = (case IL.Node.kind nd
127 :     of IL.EXIT{live, ...} => chk (0, live)
128 :     | _ => doNode methodScope nd
129 :     (* end case *))
130 :     (* this function is used to propagate info from stateIn variables to state *)
131 :     fun propInfo ((_, x), x') = (
132 :     if isVarying x' then setVarying(x, true) else ();
133 :     setMaxUse (getUseDepth x') x)
134 :     in
135 :     List.app (fn x => setBindDepth(x, methodStateScope)) stateIn;
136 :     IL.CFG.apply doMethodNode body;
137 :     (* need to propagate maxUse from stateIn variables to state variables *)
138 :     ListPair.appEq propInfo (state, stateIn)
139 :     end
140 :     fun doStrand (IL.Strand{params, state, stateInit, methods, ...}) = (
141 :     List.app (fn x => setBindDepth(x, paramScope)) params;
142 :     doCFG (strandScope, stateInit);
143 :     List.app (doMethod state) methods)
144 :     in
145 :     doCFG (globalScope, globalInit);
146 :     (* do initially code *)
147 :     doCFG (initiallyScope, rangeInit);
148 :     List.app
149 :     (fn (i, min, max) => (
150 :     setBindDepth (i, initiallyScope);
151 :     setMaxUse initiallyScope min;
152 :     setMaxUse initiallyScope max)
153 :     ) iters;
154 :     doCFG (initiallyScope, #1 create);
155 :     List.app (setMaxUse initiallyScope) (#3 create);
156 :     (* do strands *)
157 :     List.app doStrand strands
158 :     end
159 :    
160 :     (* Assign variable scopes to variables that are initialized in the global initialization.
161 :     * For the global initialization, variables that have a maxUseDepth > globalScope are
162 :     * really global. The others are local.
163 :     *)
164 :     fun assignScopeForGlobalInit globalInit = let
165 :     fun doNode nd = let
166 :     fun setBindDepth x = let
167 :     val scope = if getUseDepth x > globalScope then Global else Local
168 :     in
169 :     setVarScope (x, scope)
170 :     end
171 :     in
172 :     List.app setBindDepth (IL.Node.defs nd)
173 :     end
174 :     val _ = IL.CFG.apply doNode globalInit
175 :     (* create a new exit node that only has those globals with Global scope *)
176 :     val newExit = let
177 :     val IL.EXIT{kind, live, ...} = IL.Node.kind(IL.CFG.exit globalInit)
178 :     val newLive = List.filter isGlobal live
179 :     in
180 :     IL.Node.mkEXIT (kind, newLive)
181 :     end
182 :     in
183 :     IL.CFG.replaceNode (IL.CFG.exit globalInit, newExit);
184 :     IL.CFG{
185 :     entry = IL.CFG.entry globalInit,
186 :     exit = newExit
187 :     }
188 :     end
189 :    
190 :     (* Assign variable scopes to variables that are initialized in the initial-strand creation
191 :     * code. Since the scoping rules for Diderot limit these variables to be used in this
192 :     * scope, all of them are marked as having Local scope,
193 :     *)
194 :     fun assignScopeForInitially (initially as IL.Initially{rangeInit, iters, create, ...}) = let
195 :     fun setScope x = setVarScope(x, Local)
196 :     fun doNode nd = List.app setScope (IL.Node.defs nd)
197 :     in
198 :     IL.CFG.apply doNode rangeInit;
199 :     List.app (fn (i, _, _) => setScope i) iters;
200 :     IL.CFG.apply doNode (#1 create);
201 :     initially
202 :     end
203 :    
204 :     (* Assign variable scopes to variables that are used in a strand *)
205 :     fun assignScopeForStrand (strand as IL.Strand{name, params, state, stateInit, methods}) = let
206 :     (* assign variable scopes for variables that are defined in the stateInit code *)
207 :     val _ = let
208 :     fun doVar x = if (getUseDepth x > strandScope)
209 :     then setVarScope(x, StrandState)
210 :     else setVarScope(x, Local)
211 :     fun doNode nd = List.app doVar (IL.Node.defs nd)
212 :     in
213 :     IL.CFG.apply doNode stateInit
214 :     end
215 :     (* assign variable scope for the state variables; state variables (other than the
216 :     * output) that are not used in the strand methods can be reclassified as Local.
217 :     * Note that this pass may change some of the assignments from the processing of stateInit.
218 :     *)
219 :     val filteredState = let
220 :     fun setScope (isOut, x) =
221 :     if isVarying x
222 :     then (setVarScope(x, StrandState); true)
223 :     else if isOut orelse (getUseDepth x > strandScope)
224 :     then (setVarScope(x, StrandConstState); true)
225 :     else (
226 :     LowILCensus.dec x; (* we are removing the implicit use *)
227 :     setVarScope(x, Local);
228 :     false)
229 :     in
230 :     List.filter setScope state
231 :     end
232 :     (* for any parameter that is used inside methods, we need to introduce a
233 :     * shadow state variable. Here we compute the list of parameters that are
234 :     * used inside strand methods, the new state variables that we create to
235 :     * shadow them, and the statements to initialize the shadow variables.
236 :     *)
237 :     val (usedParams, shadowVars, initShadowVars) = let
238 :     fun chkParam (x, (usedParams, shadowVars, inits)) = (
239 :     setVarScope (x, StrandParam); (* set the scope while we're at it *)
240 :     if getUseDepth x > strandScope
241 :     then let
242 :     val x' = V.copy x
243 :     val init = (x', IL.VAR x)
244 :     in
245 :     LowILCensus.inc x;
246 :     setUseDepth(x', getUseDepth x);
247 :     setVarScope (x', StrandConstState);
248 :     (x::usedParams, (false, x')::shadowVars, init::inits)
249 :     end
250 :     else (usedParams, shadowVars, inits))
251 :     val (xs, ys, stms) = List.foldr chkParam ([], [], []) params
252 :     in
253 :     (xs, ys, IL.CFG.mkBlock stms)
254 :     end
255 :     (* extend the stateInit CFG with the shadow-variable initialization *)
256 :     val stateInit = if IL.CFG.isEmpty initShadowVars
257 :     then stateInit
258 :     else let
259 :     val initEntry = IL.CFG.entry stateInit
260 :     val IL.ENTRY{succ as ref fstNd} = IL.Node.kind initEntry
261 :     val IL.CFG{entry, exit} = initShadowVars
262 :     in
263 :     IL.Node.replaceInEdge {src = initEntry, oldDst = fstNd, dst = entry};
264 :     IL.Node.replaceOutEdge {oldSrc = initEntry, src = exit, dst = fstNd};
265 :     stateInit
266 :     end
267 :     (* rewrite the exit node of the stateInit to only return the strand state variables *)
268 :     val stateInit = let
269 :     val IL.EXIT{kind, live, ...} = IL.Node.kind(IL.CFG.exit stateInit)
270 :     fun isStrandState x = (case varScope x
271 :     of StrandConstState => true
272 :     | StrandState => true
273 :     | _ => false
274 :     (* end case *))
275 :     val live' = List.filter isStrandState live
276 :     val newExit = IL.Node.mkEXIT(kind, (List.map #2 shadowVars) @ live')
277 :     in
278 :     IL.CFG.replaceNode (IL.CFG.exit stateInit, newExit);
279 :     IL.CFG{entry = IL.CFG.entry stateInit, exit = newExit}
280 :     end
281 :     (* assign variable scopes for variables in a method and rename uses of the parameters *)
282 :     fun doMethod (IL.Method{name, stateIn, body}) = let
283 :     (* filter out any state variables that have been given Local scope and set
284 :     * the scope for the local copies of the variables.
285 :     *)
286 :     val filteredStateIn = let
287 :     fun chk ((_, x), x', xs) = let
288 :     val scope = varScope x
289 :     in
290 :     setVarScope (x', scope);
291 :     if scope = Local then xs else x'::xs
292 :     end
293 :     in
294 :     ListPair.foldrEq chk [] (state, stateIn)
295 :     end
296 :     (* generate the extra shadow variables and initialize the environment to map
297 :     * parameters to their shadows.
298 :     *)
299 :     val (env, extraVars) = List.foldr
300 :     (fn (x, (env, xs)) => let
301 :     val x' = IL.Var.copy x
302 :     in
303 :     setUseDepth(x', getUseDepth x);
304 :     setVarScope (x', StrandConstState);
305 :     (VMap.insert(env, x, x'), x'::xs)
306 :     end
307 :     ) (VMap.empty, []) usedParams
308 :     fun rename x = (case VMap.find (env, x)
309 :     of NONE => x
310 :     | SOME x' => (
311 :     (* replacing x with x', so adjust census counts *)
312 :     LowILCensus.dec x; LowILCensus.inc x';
313 :     x')
314 :     (* end case *))
315 :     (* set the variable scope for variables defined in a method *)
316 :     fun setScope x = if getUseDepth x > methodScope
317 :     then setVarScope (x, StrandState)
318 :     else setVarScope (x, Local)
319 :     (* in case the exit node get rewritten, we need to reset it *)
320 :     val exitNd = ref(IL.CFG.exit body)
321 :     (* do we need to filter the output states of methods? *)
322 :     val outStateNeedsFiltering = List.exists (fn (_, x) => varScope x <> StrandState) state
323 :     (* rewrite a node if necessary *)
324 :     fun doNode nd = let
325 :     fun changed x = VMap.inDomain(env, x)
326 :     val renameList = List.map rename
327 :     in
328 :     case IL.Node.kind nd
329 :     of IL.JOIN{phis, ...} => let
330 :     fun doPhi (lhs, rhs) = (
331 :     setScope lhs;
332 :     (lhs, renameList rhs))
333 :     in
334 :     phis := List.map doPhi (!phis)
335 :     end
336 :     | IL.COND{pred, cond, trueBranch, falseBranch} =>
337 :     if changed cond
338 :     then let
339 :     val newNd = IL.Node.mkCOND {
340 :     cond = rename cond,
341 :     trueBranch = !trueBranch,
342 :     falseBranch = !falseBranch
343 :     }
344 :     in
345 :     IL.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
346 :     IL.Node.replaceOutEdge {oldSrc = nd, src = nd, dst = !trueBranch};
347 :     IL.Node.replaceOutEdge {oldSrc = nd, src = nd, dst = !falseBranch}
348 :     end
349 :     else ()
350 :     | IL.ASSIGN{stm=(lhs, rhs), ...} => let
351 :     fun replace rhs = IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(lhs, rhs))
352 :     in
353 :     setScope lhs;
354 :     case rhs
355 :     of IL.VAR x => if changed x
356 :     then replace (IL.VAR(rename x))
357 :     else ()
358 :     | IL.LIT _ => ()
359 :     | IL.OP(rator, args) => if List.exists changed args
360 :     then replace (IL.OP(rator, renameList args))
361 :     else ()
362 :     | IL.APPLY(f, args) => if List.exists changed args
363 :     then replace (IL.APPLY(f, renameList args))
364 :     else ()
365 :     | IL.CONS(ty, args) => if List.exists changed args
366 :     then replace (IL.CONS(ty, renameList args))
367 :     else ()
368 :     (* end case *)
369 :     end
370 :     | IL.NEW{strand, args, ...} =>
371 :     if List.exists changed args
372 :     then IL.CFG.replaceNode(
373 :     nd,
374 :     IL.Node.mkNEW{strand=strand, args=renameList args})
375 :     else ()
376 :     | IL.EXIT{kind, live, ...} =>
377 :     if outStateNeedsFiltering
378 :     then let (* filter out StradConstState and Local vars *)
379 :     fun chkVar ((_, x), x', xs) = if (varScope x <> StrandState)
380 :     then xs
381 :     else x' :: xs
382 :     val live' = ListPair.foldrEq chkVar [] (state, live)
383 :     val newNd = IL.Node.mkEXIT(kind, live')
384 :     in
385 :     if IL.Node.same(nd, !exitNd)
386 :     then (
387 :     IL.CFG.replaceNode (nd, newNd);
388 :     exitNd := newNd)
389 :     else ();
390 :     IL.CFG.replaceNode (nd, newNd)
391 :     end
392 :     else ()
393 :     | _ => ()
394 :     (* end case *)
395 :     end
396 :     val _ = IL.CFG.apply doNode body
397 :     in
398 :     IL.Method{
399 :     name = name,
400 :     stateIn = extraVars @ filteredStateIn,
401 :     body = IL.CFG{entry = IL.CFG.entry body, exit = !exitNd}
402 :     }
403 :     end
404 :     in
405 :     IL.Strand{
406 :     name = name,
407 :     params = params,
408 :     state = shadowVars @ filteredState,
409 :     stateInit = stateInit,
410 :     methods = List.map doMethod methods
411 :     }
412 :     end
413 :    
414 :     fun optimize prog = let
415 :     val IL.Program{globalInit, initially, strands} = prog
416 :     (* first we compute binding and use depths *)
417 :     val _ = assignDepths prog
418 :     val globalInit = assignScopeForGlobalInit globalInit
419 :     val initially = assignScopeForInitially initially
420 :     val strands = List.map assignScopeForStrand strands
421 :     in
422 :     IL.Program{globalInit=globalInit, initially=initially, strands=strands}
423 :     end
424 :    
425 :     end

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