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

SCM Repository

[diderot] Annotation of /branches/pure-cfg/src/compiler/low-il/var-analysis.sml
ViewVC logotype

Annotation of /branches/pure-cfg/src/compiler/low-il/var-analysis.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1017 - (view) (download)

1 : jhr 1017 (* var-analysis.sml
2 :     *
3 :     * COPYRIGHT (c) 2011 The Diderot Project (http://diderot-language.cs.uchicago.edu)
4 :     * All rights reserved.
5 :     *
6 :     * The variable analysis phase does four things:
7 :     *
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 :     * 3) determine which instance variables are invariant over all strands, and thus
15 :     * can be lifted to global scope, and which strand variables are invariant across
16 :     * the strand execution.
17 :     *
18 :     * 4) eliminate unused and useless variables.
19 :     *)
20 :    
21 :     structure VarAnalysis : sig
22 :    
23 :     structure IL : SSA
24 :    
25 :     (* the scope of a variable describes the extent of its use. *)
26 :     datatype scope
27 :     = Global (* bound globally and used in strands *)
28 :     | StrandParam (* parameter to strand creation *)
29 :     | StrandConstState (* state variable that is invariant over strand execution *)
30 :     | StrandState (* strand state variable *)
31 :     | Local (* local binding not used in nested scopes *)
32 :    
33 :     val varScope : IL.var -> scope
34 :    
35 :     val optimize : IL.program -> IL.program
36 :    
37 :     end = struct
38 :    
39 :     structure IL = LowIL
40 :     structure V = IL.Var
41 :     structure VMap = V.Map
42 :    
43 :     datatype scope
44 :     = Global (* bound globally and used in strands *)
45 :     | StrandParam (* parameter to strand creation *)
46 :     | StrandConstState (* state variable that is invariant over strand execution *)
47 :     | StrandState (* strand state variable *)
48 :     | Local (* local binding not used in nested scopes *)
49 :    
50 :     (* nesting depths of scopes *)
51 :     val undefinedScope = 0
52 :     val globalScope = 1 (* global initialization *)
53 :     val initiallyScope = 2 (* initial strand creation *)
54 :     val paramScope = 2 (* strand parameter *)
55 :     val strandScope = 3 (* strand initialization *)
56 :     val methodScope = 4 (* defined/used in a strand method *)
57 :     val methodStateScope = 5 (* state variable in a strand method *)
58 :    
59 :     (* property that maps variables to the depth where they are bound *)
60 :     val {getFn=getBindDepth : IL.var -> int, setFn=setBindDepth, clrFn=clrBindDepth, ...} =
61 :     V.newProp (fn x => raise Fail("no binding depth set for " ^ V.toString x))
62 :    
63 :     (* property that maps variables to the maximum depth where they are used *)
64 :     val {peekFn=peekUseDepth : IL.var -> int option, setFn=setUseDepth, clrFn=clrUseDepth, ...} =
65 :     V.newProp (fn x => raise Fail("no use depth set for " ^ V.toString x))
66 :     fun getUseDepth x = (case peekUseDepth x
67 :     of NONE => undefinedScope
68 :     | SOME d => d
69 :     (* end case *))
70 :    
71 :     (* property that maps variables to their assigned scope *)
72 :     val {getFn=varScope : IL.var -> scope, setFn=setVarScope, ...} = V.newProp (fn x => Local)
73 :    
74 :     (* walk the program determining the binding and maximum use depths of all variables *)
75 :     fun assignDepths (IL.Program{
76 :     globalInit,
77 :     initially = IL.Initially{rangeInit, iters, create, ...},
78 :     strands
79 :     }) = let
80 :     fun setMaxUse depth x = (case peekUseDepth x
81 :     of NONE => setUseDepth(x, depth)
82 :     | SOME d => if (depth > d) then setUseDepth(x, depth) else ()
83 :     (* end case *))
84 :     fun doNode depth nd = (
85 :     List.app (setMaxUse depth) (IL.Node.uses nd);
86 :     List.app (fn x => setBindDepth(x, depth)) (IL.Node.defs nd))
87 :     fun doCFG (depth, cfg) = IL.CFG.apply (doNode depth) cfg
88 :     fun doMethod (IL.Method{stateIn, body, ...}) = let
89 :     fun doMethodNode nd = (case IL.Node.kind nd
90 :     of IL.EXIT{live, ...} => List.app (setMaxUse methodStateScope) live
91 :     | _ => doNode methodScope nd
92 :     (* end case *))
93 :     in
94 :     List.app (fn x => setBindDepth(x, methodStateScope)) stateIn;
95 :     IL.CFG.apply doMethodNode body
96 :     end
97 :     fun doStrand (IL.Strand{params, stateInit, methods, ...}) = (
98 :     List.app (fn x => setBindDepth(x, paramScope)) params;
99 :     doCFG (strandScope, stateInit);
100 :     List.app doMethod methods)
101 :     in
102 :     doCFG (globalScope, globalInit);
103 :     (* do initially code *)
104 :     doCFG (initiallyScope, rangeInit);
105 :     List.app
106 :     (fn (i, min, max) => (
107 :     setBindDepth (i, initiallyScope);
108 :     setMaxUse initiallyScope min;
109 :     setMaxUse initiallyScope max)
110 :     ) iters;
111 :     doCFG (initiallyScope, #1 create);
112 :     List.app (setMaxUse initiallyScope) (#3 create);
113 :     (* do strands *)
114 :     List.app doStrand strands
115 :     end
116 :    
117 :     (* Assign variable scopes to variables that are initialized in the global initialization.
118 :     * For the global initialization, variables that have a maxUseDepth > globalScope are
119 :     * really global. The others are local.
120 :     *)
121 :     fun assignScopeForGlobalInit globalInit = let
122 :     fun doNode nd = let
123 :     fun setBindDepth x = let
124 :     val scope = if getUseDepth x > globalScope then Global else Local
125 :     in
126 :     setVarScope (x, scope)
127 :     end
128 :     in
129 :     List.app setBindDepth (IL.Node.defs nd)
130 :     end
131 :     val _ = IL.CFG.apply doNode globalInit
132 :     (* create a new exit node that only has those globals with Global scope *)
133 :     val newExit = let
134 :     val IL.EXIT{kind, live, ...} = IL.Node.kind(IL.CFG.exit globalInit)
135 :     val newLive = List.filter (fn x => varScope x = Global) live
136 :     in
137 :     IL.Node.mkEXIT (kind, newLive)
138 :     end
139 :     in
140 :     IL.CFG.replaceNode (IL.CFG.exit globalInit, newExit);
141 :     IL.CFG{
142 :     entry = IL.CFG.entry globalInit,
143 :     exit = newExit
144 :     }
145 :     end
146 :    
147 :     (* Assign variable scopes to variables that are initialized in the initial-strand creation
148 :     * code. Since the scoping rules for Diderot limit these variables to be used in this
149 :     * scope, all of them are marked as having Local scope,
150 :     *)
151 :     fun assignScopeForInitially (initially as IL.Initially{rangeInit, iters, create, ...}) = let
152 :     fun setScope x = setVarScope(x, Local)
153 :     fun doNode nd = List.app setScope (IL.Node.defs nd)
154 :     in
155 :     IL.CFG.apply doNode rangeInit;
156 :     List.app (fn (i, _, _) => setScope i) iters;
157 :     IL.CFG.apply doNode (#1 create);
158 :     initially
159 :     end
160 :    
161 :     fun rename (env, x) = (case VMap.find (env, x)
162 :     of NONE => x
163 :     | SOME x' => x'
164 :     (* end case *))
165 :    
166 :     (* Assign variable scopes to variables that are used in a strand *)
167 :     fun assignScopeForStrand (strand as IL.Strand{name, params, state, stateInit, methods}) = let
168 :     (* assign variable scope for the state variables *)
169 :     val _ = List.app (fn (_, x) => setVarScope(x, StrandState)) state
170 :     (* assign variable scopes for variables that are defined in the stateInit code *)
171 :     val _ = let
172 :     fun doVar x = if (getUseDepth x > strandScope)
173 :     then setVarScope(x, StrandState)
174 :     else setVarScope(x, Local)
175 :     fun doNode nd = List.app doVar (IL.Node.defs nd)
176 :     in
177 :     IL.CFG.apply doNode stateInit
178 :     end
179 :     (* for any parameter that is used inside methods, we need to introduce a
180 :     * shadow state variable.
181 :     *)
182 :     val (shadowVars, initShadowVars) = let
183 :     fun chkParam (x, (shadowVars, inits)) = (
184 :     setVarScope (x, StrandParam); (* set the scope while we're at it *)
185 :     if getUseDepth x > strandScope
186 :     then let
187 :     val x' = V.copy x
188 :     val init = (x', IL.VAR x)
189 :     in
190 :     setUseDepth(x', getUseDepth x);
191 :     setVarScope (x', StrandConstState);
192 :     ((false, x)::shadowVars, init::inits)
193 :     end
194 :     else (shadowVars, inits))
195 :     val (xs, stms) = List.foldr chkParam ([], []) params
196 :     in
197 :     (xs, IL.CFG.mkBlock stms)
198 :     end
199 :     (* extend the stateInit CFG with the shadow-variable initialization *)
200 :     val stateInit = if IL.CFG.isEmpty initShadowVars
201 :     then stateInit
202 :     else let
203 :     val initEntry = IL.CFG.entry stateInit
204 :     val IL.ENTRY{succ as ref fstNd} = IL.Node.kind initEntry
205 :     val IL.CFG{entry, exit} = initShadowVars
206 :     in
207 :     IL.Node.replaceInEdge {src = initEntry, oldDst = fstNd, dst = entry};
208 :     IL.Node.replaceOutEdge {oldSrc = initEntry, src = exit, dst = fstNd};
209 :     stateInit
210 :     end
211 :     (* rewrite the exit node of the stateInit to only return the strand state variables *)
212 :     val stateInit = let
213 :     val IL.EXIT{kind, live, ...} = IL.Node.kind(IL.CFG.exit stateInit)
214 :     fun isStrandState x = (case varScope x
215 :     of StrandConstState => true
216 :     | StrandState => true
217 :     | _ => false
218 :     (* end case *))
219 :     val live' = List.filter isStrandState live
220 :     val newExit = IL.Node.mkEXIT(kind, live')
221 :     in
222 :     IL.CFG.replaceNode (IL.CFG.exit stateInit, newExit);
223 :     IL.CFG{entry = IL.CFG.entry stateInit, exit = newExit}
224 :     end
225 :     (* assign variable scopes for variables in a method and rename uses of the parameters *)
226 :     fun doMethod (IL.Method{name, stateIn, body}) = let
227 :     val (env, extraVars) = List.foldr
228 :     (fn ((_, x), (env, xs)) => let
229 :     val x' = IL.Var.copy x
230 :     in
231 :     setUseDepth(x', getUseDepth x);
232 :     setVarScope (x', StrandConstState);
233 :     (VMap.insert(env, x, x'), x'::xs)
234 :     end
235 :     ) (VMap.empty, []) shadowVars
236 :     val _ = ListPair.appEq
237 :     (fn ((_, x), x') => setVarScope (x', varScope x))
238 :     (state, stateIn)
239 :     (* set the variable scope for variables defined in a method *)
240 :     fun setScope x = if getUseDepth x > methodScope
241 :     then setVarScope (x, StrandState)
242 :     else setVarScope (x, Local)
243 :     (* in case the exit node get rewritten, we need to reset it *)
244 :     val exitNd = ref(IL.CFG.exit body)
245 :     (* rewrite a node if necessary *)
246 :     fun doNode nd = let
247 :     fun changed x = VMap.inDomain(env, x)
248 :     fun renameList (env, xs) = List.map (fn x => rename(env, x)) xs
249 :     in
250 :     case IL.Node.kind nd
251 :     of IL.JOIN{phis, ...} => let
252 :     fun doPhi (lhs, rhs) = (
253 :     setScope lhs;
254 :     (lhs, renameList(env, rhs)))
255 :     in
256 :     phis := List.map doPhi (!phis)
257 :     end
258 :     | IL.COND{pred, cond, trueBranch, falseBranch} =>
259 :     if changed cond
260 :     then let
261 :     val newNd = IL.Node.mkCOND {
262 :     cond = rename(env, cond),
263 :     trueBranch = !trueBranch,
264 :     falseBranch = !falseBranch
265 :     }
266 :     in
267 :     IL.Node.replaceInEdge {src = !pred, oldDst = nd, dst = newNd};
268 :     IL.Node.replaceOutEdge {oldSrc = nd, src = nd, dst = !trueBranch};
269 :     IL.Node.replaceOutEdge {oldSrc = nd, src = nd, dst = !falseBranch}
270 :     end
271 :     else ()
272 :     | IL.ASSIGN{stm=(lhs, rhs), ...} => let
273 :     fun replace rhs = IL.CFG.replaceNode(nd, IL.Node.mkASSIGN(lhs, rhs))
274 :     in
275 :     setScope lhs;
276 :     case rhs
277 :     of IL.VAR x => if changed x
278 :     then replace (IL.VAR(rename(env, x)))
279 :     else ()
280 :     | IL.LIT _ => ()
281 :     | IL.OP(rator, args) => if List.exists changed args
282 :     then replace (IL.OP(rator, renameList(env, args)))
283 :     else ()
284 :     | IL.APPLY(f, args) => if List.exists changed args
285 :     then replace (IL.APPLY(f, renameList(env, args)))
286 :     else ()
287 :     | IL.CONS(ty, args) => if List.exists changed args
288 :     then replace (IL.CONS(ty, renameList(env, args)))
289 :     else ()
290 :     (* end case *)
291 :     end
292 :     | IL.NEW{strand, args, ...} =>
293 :     if List.exists changed args
294 :     then IL.CFG.replaceNode(
295 :     nd,
296 :     IL.Node.mkNEW{strand=strand, args=renameList(env, args)})
297 :     else ()
298 :     | IL.EXIT{kind, live, ...} =>
299 :     if (List.exists (fn x => varScope x = StrandConstState) live)
300 :     then let (* filter out StrandConstState vars *)
301 :     val live' = List.filter (fn x => varScope x = StrandState) live
302 :     val newNd = IL.Node.mkEXIT(kind, live')
303 :     in
304 :     if IL.Node.same(nd, !exitNd)
305 :     then (
306 :     IL.CFG.replaceNode (nd, newNd);
307 :     exitNd := newNd)
308 :     else ();
309 :     IL.CFG.replaceNode (nd, newNd)
310 :     end
311 :     else ()
312 :     | _ => ()
313 :     (* end case *)
314 :     end
315 :     val _ = IL.CFG.apply doNode body
316 :     in
317 :     IL.Method{
318 :     name = name,
319 :     stateIn = extraVars @ stateIn,
320 :     body = IL.CFG{entry = IL.CFG.entry body, exit = !exitNd}
321 :     }
322 :     end
323 :     in
324 :     IL.Strand{
325 :     name = name,
326 :     params = params,
327 :     state = shadowVars @ state,
328 :     stateInit = stateInit,
329 :     methods = List.map doMethod methods
330 :     }
331 :     end
332 :    
333 :     fun optimize prog = let
334 :     val IL.Program{globalInit, initially, strands} = prog
335 :     (* first we compute binding and use depths *)
336 :     val _ = assignDepths prog
337 :     val globalInit = assignScopeForGlobalInit globalInit
338 :     val initially = assignScopeForInitially initially
339 :     val strands = List.map assignScopeForStrand strands
340 :     in
341 :     IL.Program{globalInit=globalInit, initially=initially, strands=strands}
342 :     end
343 :    
344 :     end

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