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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3349 - (view) (download)

1 : jhr 1115 (* var-analysis.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 1115 * All rights reserved.
7 :     *
8 : jhr 1640 * The variable analysis phase does the following things:
9 : jhr 1115 *
10 :     * 1) determine which variables that are bound at global level are used in strand
11 :     * or method scopes.
12 :     *
13 :     * 2) determine which strand parameters are used in methods (and thus have to be
14 :     * shadowed by instance variables).
15 :     *
16 : jhr 1640 * 3) determine which strand state variables are invariant across the strand
17 :     * execution.
18 : jhr 1115 *
19 :     * 4) eliminate unused and useless variables.
20 : jhr 1640 *
21 :     * TODO
22 :     *
23 :     * 5) determine which state variables are invariant over all strands and thus
24 :     * can be lifted to global scope
25 :     *
26 :     * 6) determine which state variables are not used and thus can be eliminated.
27 : jhr 1115 *)
28 :    
29 :     structure VarAnalysis : sig
30 :    
31 :     structure IL : SSA
32 :    
33 : jhr 1640 val optimize : IL.program -> IL.program
34 : jhr 1115
35 : jhr 1640 (* returns true if the state variable is invariant over strand execution *)
36 :     val isVarying : IL.state_var -> bool
37 : jhr 1115
38 :     end = struct
39 :    
40 :     structure IL = LowIL
41 :     structure V = IL.Var
42 : jhr 1640 structure StV = IL.StateVar
43 : jhr 1115 structure VMap = V.Map
44 :    
45 :     (* nesting depths of scopes *)
46 :     val undefinedScope = 0
47 : jhr 2298 val globalScope = 1 (* global initialization *)
48 : lamonts 2467 val globalBlockScope = 2 (* global block *)
49 :     val inputScope = 3 (* global inputs *)
50 :     val initiallyScope = 4 (* initial strand creation *)
51 :     val paramScope = 5 (* strand parameter *)
52 :     val strandScope = 6 (* strand initialization *)
53 :     val methodScope = 7 (* defined/used in a strand method *)
54 :     val methodStateScope = 8 (* state variable in a strand method *)
55 : jhr 1115
56 :     (* property that maps variables to the depth where they are bound *)
57 :     val {getFn=getBindDepth : IL.var -> int, setFn=setBindDepth, clrFn=clrBindDepth, ...} =
58 : jhr 2298 V.newProp (fn x => raise Fail("no binding depth set for " ^ V.toString x))
59 : jhr 1115
60 :     (* property that maps variables to the maximum depth where they are used *)
61 : jhr 1640 val {peekFn=peekUseDepth, getFn=getUseDepth, setFn=setUseDepth, clrFn=clrUseDepth, ...} =
62 : jhr 2298 V.newProp (fn x => undefinedScope)
63 : jhr 1115
64 :     (* boolean flag on strand-state variables that vary across method executions *)
65 : jhr 1640 val {getFn=isVarying, setFn=setVarying} = StV.newFlag ()
66 : jhr 1115
67 :     (* walk the program determining the binding and maximum use depths of all variables *)
68 :     fun assignDepths (IL.Program{
69 : jhr 2298 props,
70 : lamonts 2467 mutableGlobals,
71 : jhr 2298 globalInit,
72 : jhr 2344 globalBlock,
73 : lamonts 2526 reductionBlock as (rBlk,pList),
74 : jhr 2298 initially = IL.Initially{rangeInit, iters, create, ...},
75 :     strands
76 :     }) = let
77 :     fun setMaxUse depth x = if (depth > getUseDepth x)
78 : jhr 1640 then setUseDepth(x, depth)
79 :     else ()
80 : jhr 2298 fun doNode depth nd = (case IL.Node.kind nd
81 :     of IL.EXIT{kind, live, ...} => (case kind
82 : jhr 2344 of ExitKind.FRAGMENT => List.app (setMaxUse depth) live
83 : jhr 2298 | ExitKind.RETURN => List.app (setMaxUse depth) live
84 :     | _ => () (* we don't count ACTIVE, etc. as uses *)
85 :     (* end case *))
86 :     | _ => (
87 :     List.app (setMaxUse depth) (IL.Node.uses nd);
88 :     List.app (fn x => setBindDepth(x, depth)) (IL.Node.defs nd))
89 :     (* end case *))
90 :     fun doGlobalInitNode nd = (case IL.Node.kind nd
91 :     of IL.ASSIGN{stm=(x, IL.OP(LowOps.Input _, _)), ...} => setMaxUse inputScope x
92 :     | _ => doNode globalScope nd
93 :     (* end case *))
94 :     fun doCFG (depth, cfg) = IL.CFG.apply (doNode depth) cfg
95 :     fun assignDepthsForMethod state (IL.Method{body, ...}) = let
96 :     (* check to see which state variables are invariant *)
97 :     fun doMethodNode nd = (case IL.Node.kind nd
98 :     of IL.SAVE{lhs, rhs, ...} => let
99 : jhr 1640 fun varying () = (
100 :     setVarying(lhs, true);
101 :     setMaxUse methodScope rhs)
102 :     in
103 :     (* check to see if the state variable is varying on the path to
104 :     * this node.
105 :     *)
106 :     case V.binding rhs
107 :     of IL.VB_RHS(IL.STATE x) =>
108 :     if StV.same(x, lhs)
109 :     (* we don't count non-varying save uses of variables as setting
110 :     * the scope of a variable. This will allow us to determine
111 :     * which state variables are actually used in a method, since
112 :     * those will be bound to variables with methodScope.
113 :     *)
114 :     then setMaxUse strandScope rhs
115 :     else varying()
116 :     | _ => varying()
117 :     (* end case *)
118 :     end
119 : jhr 2298 | _ => doNode methodScope nd
120 :     (* end case *))
121 :     in
122 :     IL.CFG.apply doMethodNode body
123 :     end
124 :     (* assign use depths for a strand. The state variables are a bit tricky. We first
125 :     * propagate information from the stateInit and methods up to the state-variable
126 :     * list. Then we copy the accumulated use-depth information back down to the
127 :     * corresponding variables in the stateInit and methods.
128 :     *)
129 :     fun doStrand (IL.Strand{params, state, stateInit, methods, ...}) = (
130 :     List.app (fn x => setBindDepth(x, paramScope)) params;
131 :     (* assign depths for the stateInit code *)
132 :     doCFG (strandScope, stateInit);
133 : jhr 1640 (* examine the methods *)
134 : jhr 2298 List.app (assignDepthsForMethod state) methods)
135 :     in
136 :     IL.CFG.apply doGlobalInitNode globalInit;
137 :     (* do initially code *)
138 :     doCFG (initiallyScope, rangeInit);
139 : lamonts 2526 doCFG (globalBlockScope, rBlk);
140 : lamonts 2453 doCFG (globalBlockScope, globalBlock);
141 : jhr 2298 List.app
142 :     (fn (i, min, max) => (
143 :     setBindDepth (i, initiallyScope);
144 :     setMaxUse initiallyScope min;
145 :     setMaxUse initiallyScope max)
146 :     ) iters;
147 :     doCFG (initiallyScope, #1 create);
148 :     List.app (setMaxUse initiallyScope) (#3 create);
149 :     (* do strands *)
150 :     List.app doStrand strands
151 :     end
152 : jhr 1115
153 :     (* Assign variable scopes to variables that are initialized in the global initialization.
154 :     * For the global initialization, variables that have a maxUseDepth > globalScope are
155 :     * really global. The others are local.
156 :     *)
157 :     fun assignScopeForGlobalInit globalInit = let
158 : lamonts 2467 fun isGlobal x = (getUseDepth x > globalScope)
159 : lamonts 2160
160 : jhr 2298 in
161 :     (* create a new exit node that only has those globals with Global scope *)
162 :     IL.CFG.updateExit (globalInit, fn live => List.filter isGlobal live)
163 :     end
164 : jhr 1115
165 : lamonts 2221
166 :     fun assignScopeForGlobalBlock globalInit = let
167 : lamonts 2467 fun isGlobal x = (getUseDepth x > globalBlockScope)
168 : jhr 2298 in
169 :     (* create a new exit node that only has those globals with Global scope *)
170 :     IL.CFG.updateExit (globalInit, fn live => List.filter isGlobal live)
171 :     end
172 : lamonts 2221
173 : jhr 1640 (* insert a sequence of statements (initCFG) between the entry node of cfg and its
174 :     * successor.
175 : jhr 1115 *)
176 : jhr 1640 fun prependCFG (initCFG, cfg) =
177 : jhr 2298 if IL.CFG.isEmpty initCFG
178 : jhr 1640 then cfg
179 :     else let
180 :     val initEntry = IL.CFG.entry cfg
181 :     val IL.ENTRY{succ as ref fstNd} = IL.Node.kind initEntry
182 :     val IL.CFG{entry, exit} = initCFG
183 :     in
184 :     IL.Node.replaceInEdge {src = initEntry, oldDst = fstNd, dst = entry};
185 :     IL.Node.replaceOutEdge {oldSrc = initEntry, src = exit, dst = fstNd};
186 :     cfg
187 :     end
188 : jhr 1115
189 :     (* Assign variable scopes to variables that are used in a strand *)
190 :     fun assignScopeForStrand (strand as IL.Strand{name, params, state, stateInit, methods}) = let
191 : jhr 1640 (* FIXME: strand state variables that are only used in the stateInit code can be replaced by local vars *)
192 : jhr 2298 (* for any parameter that is used inside methods, we need to introduce a
193 :     * shadow state variable. Here we compute the list of parameters that are
194 :     * used inside strand methods, the new state variables that we create to
195 :     * shadow them, and the statements to initialize the shadow variables.
196 :     *)
197 :     val (usedParams, shadowVars, initShadowVars) = let
198 :     fun chkParam (x, (usedParams, shadowVars, initCFG)) = (
199 :     if getUseDepth x > strandScope
200 :     then let
201 :     val x' = StV.new(false, V.name x, V.ty x)
202 :     val initCFG = IL.CFG.appendNode (initCFG, IL.Node.mkSAVE(x', x))
203 :     in
204 :     LowILCensus.inc x;
205 :     (x::usedParams, x'::shadowVars, initCFG)
206 :     end
207 :     else (usedParams, shadowVars, initCFG))
208 :     val (xs, ys, initCFG) = List.foldr chkParam ([], [], IL.CFG.empty) params
209 :     in
210 :     (xs, ys, initCFG)
211 :     end
212 :     (* prepend the stateInit CFG with the shadow-variable initialization *)
213 :     val stateInit = prependCFG(initShadowVars, stateInit)
214 :     (* assign variable scopes for variables in a method and rename uses of the parameters *)
215 :     fun doMethod (IL.Method{name, body}) = let
216 : jhr 1640 (* create local names for the parameters and the code to read them out from the
217 :     * shadow state variables.
218 :     *)
219 :     val (env, loadCFG) = let
220 :     fun f (x::xs, y::ys, env, loadCFG) = let
221 :     val x' = V.copy x
222 :     val env = VMap.insert(env, x, x')
223 :     val loadCFG = IL.CFG.appendNode (loadCFG, IL.Node.mkASSIGN(x', IL.STATE y))
224 :     in
225 :     f (xs, ys, env, loadCFG)
226 :     end
227 :     | f ([], [], env, loadCFG) = (env, loadCFG)
228 :     in
229 :     f (usedParams, shadowVars, VMap.empty, IL.CFG.empty)
230 :     end
231 :     (* rename used parameters *)
232 : jhr 2298 fun rename x = (case VMap.find (env, x)
233 :     of NONE => x
234 :     | SOME x' => (
235 :     (* replacing x with x', so adjust census counts *)
236 :     LowILCensus.dec x; LowILCensus.inc x';
237 :     x')
238 :     (* end case *))
239 : jhr 1640 (* process method-body nodes. We rename parameters to the local variable that
240 :     * is read out from the shadow state variable and we remove save nodes for non-varying
241 :     * state variables.
242 :     *)
243 : jhr 2298 fun doNode nd = let
244 :     fun changed x = VMap.inDomain(env, x)
245 :     val renameList = List.map rename
246 :     in
247 :     case IL.Node.kind nd
248 :     of IL.JOIN{phis, ...} => let
249 :     fun doPhi (lhs, rhs) = (lhs, renameList rhs)
250 :     in
251 :     phis := List.map doPhi (!phis)
252 :     end
253 :     | IL.COND{pred, cond, trueBranch, falseBranch} =>
254 :     if changed cond
255 :     then let
256 :     val newNd = IL.Node.mkCOND {
257 :     cond = rename cond,
258 :     trueBranch = !trueBranch,
259 :     falseBranch = !falseBranch
260 :     }
261 :     in
262 :     IL.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
263 :     IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !trueBranch};
264 :     IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !falseBranch}
265 :     end
266 :     else ()
267 :     | IL.ASSIGN{stm=(lhs, rhs), ...} => let
268 :     fun replace rhs = IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(lhs, rhs))
269 :     in
270 :     case rhs
271 :     of IL.STATE x => ()
272 : jhr 1640 | IL.VAR x => if changed x
273 : jhr 2298 then replace (IL.VAR(rename x))
274 :     else ()
275 :     | IL.LIT _ => ()
276 : jhr 2344 | IL.SELECTOR(x,field) => if changed x
277 :     then replace (IL.SELECTOR(rename x, field))
278 : jhr 2298 else ()
279 :     | IL.OP(rator, args) => if List.exists changed args
280 :     then replace (IL.OP(rator, renameList args))
281 :     else ()
282 :     | IL.APPLY(f, args) => if List.exists changed args
283 :     then replace (IL.APPLY(f, renameList args))
284 :     else ()
285 :     | IL.CONS(ty, args) => if List.exists changed args
286 :     then replace (IL.CONS(ty, renameList args))
287 :     else ()
288 :     (* end case *)
289 :     end
290 : jhr 1640 | IL.MASSIGN{stm=(lhs, rator, args), ...} =>
291 :     if List.exists changed args
292 :     then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN(lhs, rator, renameList args))
293 :     else ()
294 : jhr 2298 | IL.NEW{strand, args, ...} =>
295 :     if List.exists changed args
296 :     then IL.CFG.replaceNode(
297 :     nd,
298 :     IL.Node.mkNEW{strand=strand, args=renameList args})
299 :     else ()
300 :     | IL.SAVE{lhs, rhs, ...} => if (isVarying lhs)
301 : jhr 1640 then ()
302 :     else IL.CFG.deleteNode nd
303 : jhr 2298 | _ => ()
304 :     (* end case *)
305 :     end
306 :     val _ = IL.CFG.apply doNode body
307 :     in
308 :     IL.Method{
309 :     name = name,
310 :     body = prependCFG (loadCFG, body)
311 :     }
312 :     end
313 :     in
314 :     IL.Strand{
315 :     name = name,
316 :     params = params,
317 :     state = shadowVars @ state,
318 :     stateInit = stateInit,
319 :     methods = List.map doMethod methods
320 :     }
321 :     end
322 : jhr 1115
323 :     fun optimize prog = let
324 : lamonts 2526 val IL.Program{props, globalInit, mutableGlobals, globalBlock, reductionBlock as (rBlk,pList), initially, strands} = prog
325 : jhr 2298 (* first we compute binding and use depths *)
326 :     val _ = assignDepths prog
327 : jhr 1640 (* then rewrite the code *)
328 : jhr 2298 val globalInit = assignScopeForGlobalInit globalInit
329 : lamonts 2526 val reductionBlock = assignScopeForGlobalBlock rBlk
330 : jhr 2298 val globalBlock = assignScopeForGlobalBlock globalBlock
331 :     val strands = List.map assignScopeForStrand strands
332 :     in
333 :     IL.Program{
334 :     props = props,
335 : lamonts 2467 mutableGlobals = mutableGlobals,
336 : lamonts 2526 globalInit = globalInit, globalBlock = globalBlock, reductionBlock=(reductionBlock,pList),
337 : jhr 2298 initially=initially, strands=strands
338 :     }
339 :     end
340 : jhr 1115
341 :     end

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