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

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