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

Parent Directory | Revision Log

---

Revision 1131 - (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 :	jhr	1131	| IL.EXIT{kind=ExitKind.DIE, ...} => ()
377 :	jhr	1115	| IL.EXIT{kind, live, ...} =>
378 :			if outStateNeedsFiltering
379 :			then let (* filter out StradConstState and Local vars *)
380 :			fun chkVar ((_, x), x', xs) = if (varScope x <> StrandState)
381 :			then xs
382 :			else x' :: xs
383 :			val live' = ListPair.foldrEq chkVar [] (state, live)
384 :			val newNd = IL.Node.mkEXIT(kind, live')
385 :			in
386 :			if IL.Node.same(nd, !exitNd)
387 :			then (
388 :			IL.CFG.replaceNode (nd, newNd);
389 :			exitNd := newNd)
390 :			else ();
391 :			IL.CFG.replaceNode (nd, newNd)
392 :			end
393 :			else ()
394 :			| _ => ()
395 :			(* end case *)
396 :			end
397 :			val _ = IL.CFG.apply doNode body
398 :			in
399 :			IL.Method{
400 :			name = name,
401 :			stateIn = extraVars @ filteredStateIn,
402 :			body = IL.CFG{entry = IL.CFG.entry body, exit = !exitNd}
403 :			}
404 :			end
405 :			in
406 :			IL.Strand{
407 :			name = name,
408 :			params = params,
409 :			state = shadowVars @ filteredState,
410 :			stateInit = stateInit,
411 :			methods = List.map doMethod methods
412 :			}
413 :			end
414 :
415 :			fun optimize prog = let
416 :			val IL.Program{globalInit, initially, strands} = prog
417 :			(* first we compute binding and use depths *)
418 :			val _ = assignDepths prog
419 :			val globalInit = assignScopeForGlobalInit globalInit
420 :			val initially = assignScopeForInitially initially
421 :			val strands = List.map assignScopeForStrand strands
422 :			in
423 :			IL.Program{globalInit=globalInit, initially=initially, strands=strands}
424 :			end
425 :
426 :			end

---

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