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

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