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 2162 - (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 : lamonts 2160 fun isGlobal x = (* HACK: Need to keep grid cell/dimensions around so they can be used during runtime*)
153 : lamonts 2162 if (V.name x) = "qWinDim" then true
154 :     else (if (V.name x) = "qCellDim" then true
155 :     else (if (V.name x) = "qGridDim" then true
156 :     else (getUseDepth x > globalScope)))
157 : lamonts 2160
158 : jhr 1115 in
159 : jhr 1232 (* create a new exit node that only has those globals with Global scope *)
160 :     IL.CFG.updateExit (globalInit, fn live => List.filter isGlobal live)
161 : jhr 1115 end
162 :    
163 : jhr 1640 (* insert a sequence of statements (initCFG) between the entry node of cfg and its
164 :     * successor.
165 : jhr 1115 *)
166 : jhr 1640 fun prependCFG (initCFG, cfg) =
167 :     if IL.CFG.isEmpty initCFG
168 :     then cfg
169 :     else let
170 :     val initEntry = IL.CFG.entry cfg
171 :     val IL.ENTRY{succ as ref fstNd} = IL.Node.kind initEntry
172 :     val IL.CFG{entry, exit} = initCFG
173 :     in
174 :     IL.Node.replaceInEdge {src = initEntry, oldDst = fstNd, dst = entry};
175 :     IL.Node.replaceOutEdge {oldSrc = initEntry, src = exit, dst = fstNd};
176 :     cfg
177 :     end
178 : jhr 1115
179 :     (* Assign variable scopes to variables that are used in a strand *)
180 :     fun assignScopeForStrand (strand as IL.Strand{name, params, state, stateInit, methods}) = let
181 : jhr 1640 (* FIXME: strand state variables that are only used in the stateInit code can be replaced by local vars *)
182 : jhr 1115 (* for any parameter that is used inside methods, we need to introduce a
183 :     * shadow state variable. Here we compute the list of parameters that are
184 :     * used inside strand methods, the new state variables that we create to
185 :     * shadow them, and the statements to initialize the shadow variables.
186 :     *)
187 :     val (usedParams, shadowVars, initShadowVars) = let
188 : jhr 1640 fun chkParam (x, (usedParams, shadowVars, initCFG)) = (
189 : jhr 1115 if getUseDepth x > strandScope
190 :     then let
191 : jhr 1640 val x' = StV.new(false, V.name x, V.ty x)
192 :     val initCFG = IL.CFG.appendNode (initCFG, IL.Node.mkSAVE(x', x))
193 : jhr 1115 in
194 :     LowILCensus.inc x;
195 : jhr 1640 (x::usedParams, x'::shadowVars, initCFG)
196 : jhr 1115 end
197 : jhr 1640 else (usedParams, shadowVars, initCFG))
198 :     val (xs, ys, initCFG) = List.foldr chkParam ([], [], IL.CFG.empty) params
199 : jhr 1115 in
200 : jhr 1640 (xs, ys, initCFG)
201 : jhr 1115 end
202 : jhr 1232 (* prepend the stateInit CFG with the shadow-variable initialization *)
203 : jhr 1640 val stateInit = prependCFG(initShadowVars, stateInit)
204 : jhr 1115 (* assign variable scopes for variables in a method and rename uses of the parameters *)
205 : jhr 1640 fun doMethod (IL.Method{name, body}) = let
206 :     (* create local names for the parameters and the code to read them out from the
207 :     * shadow state variables.
208 :     *)
209 :     val (env, loadCFG) = let
210 :     fun f (x::xs, y::ys, env, loadCFG) = let
211 :     val x' = V.copy x
212 :     val env = VMap.insert(env, x, x')
213 :     val loadCFG = IL.CFG.appendNode (loadCFG, IL.Node.mkASSIGN(x', IL.STATE y))
214 :     in
215 :     f (xs, ys, env, loadCFG)
216 :     end
217 :     | f ([], [], env, loadCFG) = (env, loadCFG)
218 :     in
219 :     f (usedParams, shadowVars, VMap.empty, IL.CFG.empty)
220 :     end
221 :     (* rename used parameters *)
222 : jhr 1115 fun rename x = (case VMap.find (env, x)
223 :     of NONE => x
224 :     | SOME x' => (
225 :     (* replacing x with x', so adjust census counts *)
226 :     LowILCensus.dec x; LowILCensus.inc x';
227 :     x')
228 :     (* end case *))
229 : jhr 1640 (* process method-body nodes. We rename parameters to the local variable that
230 :     * is read out from the shadow state variable and we remove save nodes for non-varying
231 :     * state variables.
232 :     *)
233 : jhr 1115 fun doNode nd = let
234 :     fun changed x = VMap.inDomain(env, x)
235 :     val renameList = List.map rename
236 :     in
237 :     case IL.Node.kind nd
238 :     of IL.JOIN{phis, ...} => let
239 : jhr 1640 fun doPhi (lhs, rhs) = (lhs, renameList rhs)
240 : jhr 1115 in
241 :     phis := List.map doPhi (!phis)
242 :     end
243 :     | IL.COND{pred, cond, trueBranch, falseBranch} =>
244 :     if changed cond
245 :     then let
246 :     val newNd = IL.Node.mkCOND {
247 :     cond = rename cond,
248 :     trueBranch = !trueBranch,
249 :     falseBranch = !falseBranch
250 :     }
251 :     in
252 :     IL.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
253 : jhr 1232 IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !trueBranch};
254 :     IL.Node.replaceOutEdge {oldSrc = nd, src = newNd, dst = !falseBranch}
255 : jhr 1115 end
256 :     else ()
257 :     | IL.ASSIGN{stm=(lhs, rhs), ...} => let
258 :     fun replace rhs = IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(lhs, rhs))
259 :     in
260 :     case rhs
261 : jhr 1640 of IL.STATE x => ()
262 :     | IL.VAR x => if changed x
263 : jhr 1115 then replace (IL.VAR(rename x))
264 :     else ()
265 :     | IL.LIT _ => ()
266 : lamonts 2083 | IL.SELECTOR(x,field) => if changed x
267 :     then replace (IL.SELECTOR(rename x,field))
268 :     else ()
269 : jhr 1115 | IL.OP(rator, args) => if List.exists changed args
270 :     then replace (IL.OP(rator, renameList args))
271 :     else ()
272 :     | IL.APPLY(f, args) => if List.exists changed args
273 :     then replace (IL.APPLY(f, renameList args))
274 :     else ()
275 :     | IL.CONS(ty, args) => if List.exists changed args
276 :     then replace (IL.CONS(ty, renameList args))
277 :     else ()
278 :     (* end case *)
279 :     end
280 : jhr 1640 | IL.MASSIGN{stm=(lhs, rator, args), ...} =>
281 :     if List.exists changed args
282 :     then IL.CFG.replaceNode(nd, IL.Node.mkMASSIGN(lhs, rator, renameList args))
283 :     else ()
284 : jhr 1115 | IL.NEW{strand, args, ...} =>
285 :     if List.exists changed args
286 :     then IL.CFG.replaceNode(
287 :     nd,
288 :     IL.Node.mkNEW{strand=strand, args=renameList args})
289 :     else ()
290 : jhr 1640 | IL.SAVE{lhs, rhs, ...} => if (isVarying lhs)
291 :     then ()
292 :     else IL.CFG.deleteNode nd
293 : jhr 1115 | _ => ()
294 :     (* end case *)
295 :     end
296 :     val _ = IL.CFG.apply doNode body
297 :     in
298 :     IL.Method{
299 :     name = name,
300 : jhr 1640 body = prependCFG (loadCFG, body)
301 : jhr 1115 }
302 :     end
303 :     in
304 :     IL.Strand{
305 :     name = name,
306 :     params = params,
307 : jhr 1640 state = shadowVars @ state,
308 : jhr 1115 stateInit = stateInit,
309 :     methods = List.map doMethod methods
310 :     }
311 :     end
312 :    
313 :     fun optimize prog = let
314 : lamonts 2101 val IL.Program{props, globalInit, globalReduce, initially, strands} = prog
315 : jhr 1115 (* first we compute binding and use depths *)
316 :     val _ = assignDepths prog
317 : jhr 1640 (* then rewrite the code *)
318 : jhr 1115 val globalInit = assignScopeForGlobalInit globalInit
319 : lamonts 2101 val globalReduce = assignScopeForGlobalInit globalReduce
320 : jhr 1115 val strands = List.map assignScopeForStrand strands
321 :     in
322 : lamonts 2101 IL.Program{props=props, globalInit=globalInit, globalReduce = globalReduce, initially=initially, strands=strands}
323 : jhr 1115 end
324 :    
325 :     end

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