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 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 2356 val globalScope = 1 (* global initialization *)
48 : jhr 2636 val inputScope = 2 (* global inputs *)
49 :     val initiallyScope = 3 (* initial strand creation *)
50 :     val paramScope = 3 (* strand parameter *)
51 :     val strandScope = 4 (* strand initialization *)
52 :     val methodScope = 5 (* defined/used in a strand method *)
53 :     val methodStateScope = 6 (* state variable in a strand method *)
54 : jhr 1115
55 :     (* property that maps variables to the depth where they are bound *)
56 :     val {getFn=getBindDepth : IL.var -> int, setFn=setBindDepth, clrFn=clrBindDepth, ...} =
57 : jhr 2356 V.newProp (fn x => raise Fail("no binding depth set for " ^ V.toString x))
58 : jhr 1115
59 :     (* property that maps variables to the maximum depth where they are used *)
60 : jhr 1640 val {peekFn=peekUseDepth, getFn=getUseDepth, setFn=setUseDepth, clrFn=clrUseDepth, ...} =
61 : jhr 2356 V.newProp (fn x => undefinedScope)
62 : jhr 1115
63 :     (* boolean flag on strand-state variables that vary across method executions *)
64 : jhr 1640 val {getFn=isVarying, setFn=setVarying} = StV.newFlag ()
65 : jhr 1115
66 :     (* walk the program determining the binding and maximum use depths of all variables *)
67 :     fun assignDepths (IL.Program{
68 : jhr 2356 props,
69 :     globalInit,
70 :     initially = IL.Initially{rangeInit, iters, create, ...},
71 :     strands
72 :     }) = let
73 :     fun setMaxUse depth x = if (depth > getUseDepth x)
74 : jhr 1640 then setUseDepth(x, depth)
75 :     else ()
76 : jhr 2356 fun doNode depth nd = (case IL.Node.kind nd
77 :     of IL.EXIT{kind, live, ...} => (case kind
78 :     of ExitKind.FRAGMENT => List.app (setMaxUse depth) live
79 :     | ExitKind.RETURN => List.app (setMaxUse depth) live
80 :     | _ => () (* we don't count ACTIVE, etc. as uses *)
81 :     (* end case *))
82 :     | _ => (
83 :     List.app (setMaxUse depth) (IL.Node.uses nd);
84 :     List.app (fn x => setBindDepth(x, depth)) (IL.Node.defs nd))
85 :     (* end case *))
86 : jhr 2636 fun doGlobalInitNode nd = (case IL.Node.kind nd
87 :     of IL.ASSIGN{stm=(x, IL.OP(LowOps.Input _, _)), ...} => setMaxUse inputScope x
88 :     | _ => doNode globalScope nd
89 :     (* end case *))
90 : jhr 2356 fun doCFG (depth, cfg) = IL.CFG.apply (doNode depth) cfg
91 :     fun assignDepthsForMethod state (IL.Method{body, ...}) = let
92 :     (* check to see which state variables are invariant *)
93 :     fun doMethodNode nd = (case IL.Node.kind nd
94 :     of IL.SAVE{lhs, rhs, ...} => let
95 : jhr 1640 fun varying () = (
96 :     setVarying(lhs, true);
97 :     setMaxUse methodScope rhs)
98 :     in
99 :     (* check to see if the state variable is varying on the path to
100 :     * this node.
101 :     *)
102 :     case V.binding rhs
103 :     of IL.VB_RHS(IL.STATE x) =>
104 :     if StV.same(x, lhs)
105 :     (* we don't count non-varying save uses of variables as setting
106 :     * the scope of a variable. This will allow us to determine
107 :     * which state variables are actually used in a method, since
108 :     * those will be bound to variables with methodScope.
109 :     *)
110 :     then setMaxUse strandScope rhs
111 :     else varying()
112 :     | _ => varying()
113 :     (* end case *)
114 :     end
115 : jhr 2356 | _ => doNode methodScope nd
116 :     (* end case *))
117 :     in
118 :     IL.CFG.apply doMethodNode body
119 :     end
120 :     (* assign use depths for a strand. The state variables are a bit tricky. We first
121 :     * propagate information from the stateInit and methods up to the state-variable
122 :     * list. Then we copy the accumulated use-depth information back down to the
123 :     * corresponding variables in the stateInit and methods.
124 :     *)
125 :     fun doStrand (IL.Strand{params, state, stateInit, methods, ...}) = (
126 :     List.app (fn x => setBindDepth(x, paramScope)) params;
127 :     (* assign depths for the stateInit code *)
128 :     doCFG (strandScope, stateInit);
129 : jhr 1640 (* examine the methods *)
130 : jhr 2356 List.app (assignDepthsForMethod state) methods)
131 :     in
132 : jhr 2636 IL.CFG.apply doGlobalInitNode globalInit;
133 : jhr 2356 (* 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 : jhr 1115
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 2356 in
154 :     (* 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 :     end
157 : jhr 1115
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 : jhr 2356 if IL.CFG.isEmpty initCFG
163 : jhr 1640 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 2356 (* 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 :     fun chkParam (x, (usedParams, shadowVars, initCFG)) = (
184 :     if getUseDepth x > strandScope
185 :     then let
186 :     val x' = StV.new(false, V.name x, V.ty x)
187 :     val initCFG = IL.CFG.appendNode (initCFG, IL.Node.mkSAVE(x', x))
188 :     in
189 :     LowILCensus.inc x;
190 :     (x::usedParams, x'::shadowVars, initCFG)
191 :     end
192 :     else (usedParams, shadowVars, initCFG))
193 :     val (xs, ys, initCFG) = List.foldr chkParam ([], [], IL.CFG.empty) params
194 :     in
195 :     (xs, ys, initCFG)
196 :     end
197 :     (* prepend the stateInit CFG with the shadow-variable initialization *)
198 :     val stateInit = prependCFG(initShadowVars, stateInit)
199 :     (* assign variable scopes for variables in a method and rename uses of the parameters *)
200 :     fun doMethod (IL.Method{name, body}) = let
201 : jhr 1640 (* 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 2356 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 2356 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 :     fun doPhi (lhs, rhs) = (lhs, renameList rhs)
235 :     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 :     IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !trueBranch};
249 :     IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !falseBranch}
250 :     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 :     of IL.STATE x => ()
257 : jhr 1640 | IL.VAR x => if changed x
258 : jhr 2356 then replace (IL.VAR(rename x))
259 :     else ()
260 :     | IL.LIT _ => ()
261 :     | IL.OP(rator, args) => if List.exists changed args
262 :     then replace (IL.OP(rator, renameList args))
263 :     else ()
264 :     | IL.APPLY(f, args) => if List.exists changed args
265 :     then replace (IL.APPLY(f, renameList args))
266 :     else ()
267 :     | IL.CONS(ty, args) => if List.exists changed args
268 :     then replace (IL.CONS(ty, renameList args))
269 :     else ()
270 :     (* end case *)
271 :     end
272 : jhr 1640 | IL.MASSIGN{stm=(lhs, rator, args), ...} =>
273 :     if List.exists changed args
274 :     then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN(lhs, rator, renameList args))
275 :     else ()
276 : jhr 2356 | IL.NEW{strand, args, ...} =>
277 :     if List.exists changed args
278 :     then IL.CFG.replaceNode(
279 :     nd,
280 :     IL.Node.mkNEW{strand=strand, args=renameList args})
281 :     else ()
282 :     | IL.SAVE{lhs, rhs, ...} => if (isVarying lhs)
283 : jhr 1640 then ()
284 :     else IL.CFG.deleteNode nd
285 : jhr 2356 | _ => ()
286 :     (* end case *)
287 :     end
288 :     val _ = IL.CFG.apply doNode body
289 :     in
290 :     IL.Method{
291 :     name = name,
292 :     body = prependCFG (loadCFG, body)
293 :     }
294 :     end
295 :     in
296 :     IL.Strand{
297 :     name = name,
298 :     params = params,
299 :     state = shadowVars @ state,
300 :     stateInit = stateInit,
301 :     methods = List.map doMethod methods
302 :     }
303 :     end
304 : jhr 1115
305 :     fun optimize prog = let
306 : jhr 2356 val IL.Program{props, globalInit, initially, strands} = prog
307 :     (* first we compute binding and use depths *)
308 :     val _ = assignDepths prog
309 : jhr 1640 (* then rewrite the code *)
310 : jhr 2356 val globalInit = assignScopeForGlobalInit globalInit
311 :     val strands = List.map assignScopeForStrand strands
312 :     in
313 :     IL.Program{props=props, globalInit=globalInit, initially=initially, strands=strands}
314 :     end
315 : jhr 1115
316 :     end

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