Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 2017 Matthew Fluet. |
2 | * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh | |
3 | * Jagannathan, and Stephen Weeks. | |
4 | * Copyright (C) 1997-2000 NEC Research Institute. | |
5 | * | |
6 | * MLton is released under a BSD-style license. | |
7 | * See the file MLton-LICENSE for details. | |
8 | * | |
9 | ||
10 | * This pass is based on the liveness algorithm described in section 4.13, | |
11 | * page 132, of Morgan's "Building an Optimizing Compiler". BTW, the Dragon | |
12 | * book and Muchnick's book provided no help at all on speeding up liveness. | |
13 | * They suggest using bit-vectors, which is infeasible for MLton due to the | |
14 | * large size of and number of variables in SSA functions. | |
15 | * | |
16 | * Here is a description of the algorithm. | |
17 | * | |
18 | * Walk over the whole program and | |
19 | * 1. Build the predecessor graph of basic blocks. Each basic block records the | |
20 | * set of its predecessors and the set of variables live at the beginning of | |
21 | * the block. | |
22 | * 2. For each variable record the block in which is defined and the list of | |
23 | * blocks where it is used. | |
24 | * | |
25 | * Now, for each variable, propagate the liveness information backwards from uses | |
26 | * along basic blocks until the definition block is reached. | |
27 | * | |
28 | * That's it. The reason why it's so fast is that it processes one variable at a | |
29 | * time, and hence the operation to determine if that variable is in the live | |
30 | * list for a particular block is constant time -- the variable is either at the | |
31 | * head of the list or it's not there. | |
32 | *) | |
33 | functor Live (S: LIVE_STRUCTS): LIVE = | |
34 | struct | |
35 | ||
36 | open S | |
37 | datatype z = datatype Statement.t | |
38 | datatype z = datatype Transfer.t | |
39 | ||
40 | structure LiveInfo = | |
41 | struct | |
42 | datatype t = T of {live: Var.t Buffer.t, | |
43 | liveHS: {handler: Label.t option ref, | |
44 | link: unit option ref}, | |
45 | name: string, | |
46 | preds: t list ref} | |
47 | ||
48 | fun layout (T {name, ...}) = Layout.str name | |
49 | ||
50 | fun new (name: string) = | |
51 | T {live = Buffer.new {dummy = Var.bogus}, | |
52 | liveHS = {handler = ref NONE, | |
53 | link = ref NONE}, | |
54 | name = name, | |
55 | preds = ref []} | |
56 | ||
57 | fun live (T {live, ...}) = Buffer.toVector live | |
58 | ||
59 | fun liveHS (T {liveHS = {handler, link}, ...}) = | |
60 | {handler = !handler, | |
61 | link = isSome (!link)} | |
62 | ||
63 | fun equals (T {preds = r, ...}, T {preds = r', ...}) = r = r' | |
64 | ||
65 | fun addEdge (b, T {preds, ...}) = | |
66 | if List.exists (!preds, fn b' => equals (b, b')) | |
67 | then () | |
68 | else List.push (preds, b) | |
69 | ||
70 | val addEdge = | |
71 | Trace.trace2 | |
72 | ("Live.LiveInfo.addEdge", layout, layout, Unit.layout) | |
73 | addEdge | |
74 | end | |
75 | ||
76 | val traceConsider = | |
77 | Trace.trace ("Live.consider", LiveInfo.layout, Bool.layout) | |
78 | ||
79 | fun live (function, {shouldConsider: Var.t -> bool}) = | |
80 | let | |
81 | val shouldConsider = | |
82 | Trace.trace ("Live.shouldConsider", Var.layout, Bool.layout) | |
83 | shouldConsider | |
84 | val {args, blocks, ...} = Function.dest function | |
85 | val _ = | |
86 | Control.diagnostic | |
87 | (fn () => | |
88 | let | |
89 | val numVars = ref 0 | |
90 | fun loopVar (x, _) = | |
91 | if shouldConsider x | |
92 | then Int.inc numVars | |
93 | else () | |
94 | fun loopFormals v = Vector.foreach (v, loopVar) | |
95 | val () = | |
96 | Vector.foreach | |
97 | (blocks, fn Block.T {args, statements, transfer, ...} => | |
98 | (loopFormals args | |
99 | ; Vector.foreach (statements, fn s => | |
100 | Statement.foreachDef (s, loopVar)) | |
101 | ; Transfer.foreachDef (transfer, loopVar))) | |
102 | open Layout | |
103 | in | |
104 | align [seq [str "Live info for ", | |
105 | Func.layout (Function.name function)], | |
106 | seq [str " num blocks ", Int.layout (Vector.length blocks)], | |
107 | seq [str " num vars ", Int.layout (!numVars)]] | |
108 | end) | |
109 | val {get = labelInfo: Label.t -> {argInfo: LiveInfo.t, | |
110 | block: Block.t, | |
111 | bodyInfo: LiveInfo.t}, | |
112 | rem = removeLabelInfo, | |
113 | set = setLabelInfo, ...} = | |
114 | Property.getSetOnce (Label.plist, | |
115 | Property.initRaise ("live info", Label.layout)) | |
116 | val {get = varInfo: Var.t -> {defined: LiveInfo.t option ref, | |
117 | used: LiveInfo.t list ref}, | |
118 | rem = removeVarInfo, ...} = | |
119 | Property.get (Var.plist, | |
120 | Property.initFun (fn _ => {defined = ref NONE, | |
121 | used = ref []})) | |
122 | datatype 'a defuse = Def of LiveInfo.t | Use of 'a * LiveInfo.t | |
123 | val handlerCodeDefUses: Label.t defuse list ref = ref [] | |
124 | val handlerLinkDefUses: unit defuse list ref = ref [] | |
125 | val allVars: Var.t list ref = ref [] | |
126 | fun setDefined (x: Var.t, defined): unit = | |
127 | if shouldConsider x | |
128 | then (List.push (allVars, x) | |
129 | ; #defined (varInfo x) := SOME defined) | |
130 | else () | |
131 | val setDefined = | |
132 | Trace.trace2 ("Live.setDefined", | |
133 | Var.layout, LiveInfo.layout, Unit.layout) | |
134 | setDefined | |
135 | (* Set the labelInfo for each block. *) | |
136 | val _ = | |
137 | Vector.foreach | |
138 | (blocks, fn block as Block.T {args, label, ...} => | |
139 | let | |
140 | val name = Label.toString label | |
141 | val (argInfo, bodyInfo) = | |
142 | case Vector.length args of | |
143 | 0 => let val b = LiveInfo.new (name ^ "a") | |
144 | in (b, b) | |
145 | end | |
146 | | _ => let val b = LiveInfo.new (name ^ "b") | |
147 | val b' = LiveInfo.new (name ^ "c") | |
148 | val _ = LiveInfo.addEdge (b, b') | |
149 | in (b, b') | |
150 | end | |
151 | in | |
152 | setLabelInfo (label, {argInfo = argInfo, | |
153 | block = block, | |
154 | bodyInfo = bodyInfo}) | |
155 | end) | |
156 | (* Add the control-flow edges and set the defines and uses for each | |
157 | * variable. | |
158 | *) | |
159 | val head = LiveInfo.new "main" | |
160 | val _ = Vector.foreach (args, fn (x, _) => setDefined (x, head)) | |
161 | val _ = | |
162 | Vector.foreach | |
163 | (blocks, | |
164 | fn Block.T {args, kind, label, statements, transfer, ...} => | |
165 | let | |
166 | val {argInfo, bodyInfo = b, ...} = labelInfo label | |
167 | val _ = Vector.foreach (args, fn (x, _) => setDefined (x, argInfo)) | |
168 | fun goto l = LiveInfo.addEdge (b, #argInfo (labelInfo l)) | |
169 | (* Make sure that a cont's live vars includes variables live in its | |
170 | * handler. | |
171 | *) | |
172 | val _ = | |
173 | case kind of | |
174 | Kind.Cont {handler, ...} => | |
175 | Handler.foreachLabel (handler, goto) | |
176 | | _ => () | |
177 | fun define (x: Var.t): unit = setDefined (x, b) | |
178 | fun use (x: Var.t): unit = | |
179 | if shouldConsider x | |
180 | then | |
181 | let val {used, ...} = varInfo x | |
182 | in | |
183 | if (case !used of | |
184 | [] => false | |
185 | | b' :: _ => LiveInfo.equals (b, b')) | |
186 | then () | |
187 | else List.push (used, b) | |
188 | end | |
189 | else () | |
190 | val use = Trace.trace ("Live.use", Var.layout, Unit.layout) use | |
191 | val _ = | |
192 | Vector.foreach | |
193 | (statements, fn s => | |
194 | let | |
195 | val _ = Statement.foreachDefUse (s, {def = define o #1, | |
196 | use = use}) | |
197 | val _ = | |
198 | case s of | |
199 | SetExnStackSlot => | |
200 | List.push (handlerLinkDefUses, Use ((), b)) | |
201 | | SetHandler _ => | |
202 | List.push (handlerCodeDefUses, Def b) | |
203 | | SetSlotExnStack => | |
204 | List.push (handlerLinkDefUses, Def b) | |
205 | | _ => () | |
206 | in | |
207 | () | |
208 | end) | |
209 | fun label l = | |
210 | let | |
211 | val {block = Block.T {kind, ...}, ...} = labelInfo l | |
212 | in | |
213 | case kind of | |
214 | Kind.Handler => | |
215 | List.push (handlerCodeDefUses, Use (l, b)) | |
216 | | _ => goto l | |
217 | end | |
218 | val _ = | |
219 | Transfer.foreachDefLabelUse (transfer, {def = define o #1, | |
220 | label = label, | |
221 | use = use}) | |
222 | in () | |
223 | end) | |
224 | (* Back-propagate every variable from uses to define point. *) | |
225 | fun processVar (x: Var.t): unit = | |
226 | if not (shouldConsider x) | |
227 | then () | |
228 | else | |
229 | let | |
230 | val {defined, used, ...} = varInfo x | |
231 | val defined = valOf (!defined) | |
232 | val todo: LiveInfo.t list ref = ref [] | |
233 | fun consider (b as LiveInfo.T {live, ...}) = | |
234 | if LiveInfo.equals (b, defined) | |
235 | orelse (case Buffer.last live of | |
236 | NONE => false | |
237 | | SOME x' => Var.equals (x, x')) | |
238 | then false | |
239 | else (Buffer.add (live, x) | |
240 | ; List.push (todo, b) | |
241 | ; true) | |
242 | val consider = traceConsider consider | |
243 | val consider = ignore o consider | |
244 | val _ = List.foreach (!used, consider) | |
245 | fun loop () = | |
246 | case !todo of | |
247 | [] => () | |
248 | | LiveInfo.T {preds, ...} :: bs => | |
249 | (todo := bs | |
250 | ; List.foreach (!preds, consider) | |
251 | ; loop ()) | |
252 | val _ = loop () | |
253 | in () | |
254 | end | |
255 | val processVar = | |
256 | Trace.trace ("Live.processVar", Var.layout, Unit.layout) processVar | |
257 | val _ = List.foreach (!allVars, processVar) | |
258 | val _ = Function.foreachDef (function, fn (x, _) => removeVarInfo x) | |
259 | (* handler code and link slots are harder; in particular, they don't | |
260 | * satisfy the SSA invariant -- there are multiple definitions; | |
261 | * furthermore, a def and use in a block does not mean that the def | |
262 | * occurs before the use. But, a back propagated use will always | |
263 | * come after a def in the same block | |
264 | *) | |
265 | fun handlerLink (defuse: 'a defuse list ref, | |
266 | sel: {handler: Label.t option ref, | |
267 | link: unit option ref} -> 'a option ref) = | |
268 | let | |
269 | val todo: ('a * LiveInfo.t) list ref = ref [] | |
270 | (* The foldr is important because the statements in each block were | |
271 | * visited in order, meaning that the earlier statements appear | |
272 | * later in !defuse. Hence, with the foldr, the defs and uses are | |
273 | * visited in order for each block. | |
274 | *) | |
275 | val defs = | |
276 | List.foldr | |
277 | (!defuse, [], fn (du, defs) => | |
278 | case du of | |
279 | Def b => b::defs | |
280 | | Use (a, b as LiveInfo.T {liveHS, ...}) => | |
281 | let | |
282 | val _ = | |
283 | if | |
284 | (* Since we are visiting all of the statements | |
285 | * in the block together, in order, we are | |
286 | * guaranteed that if there is a prior definition | |
287 | * then it will be first on defs. | |
288 | *) | |
289 | (case defs of | |
290 | [] => false | |
291 | | b' :: _ => LiveInfo.equals (b, b')) | |
292 | then () | |
293 | else (sel liveHS := SOME a | |
294 | ; List.push (todo, (a, b))) | |
295 | in | |
296 | defs | |
297 | end) | |
298 | fun consider (b as LiveInfo.T {liveHS, ...}, a: 'a) = | |
299 | if List.exists (defs, fn b' => LiveInfo.equals (b, b')) | |
300 | orelse isSome (!(sel liveHS)) | |
301 | then () | |
302 | else (sel liveHS := SOME a | |
303 | ; List.push (todo, (a, b))) | |
304 | fun loop () = | |
305 | case !todo of | |
306 | [] => () | |
307 | | (a, LiveInfo.T {preds, ...}) :: bs => | |
308 | (todo := bs | |
309 | ; List.foreach (!preds, fn b => consider (b, a)) | |
310 | ; loop ()) | |
311 | val _ = loop () | |
312 | in | |
313 | () | |
314 | end | |
315 | val _ = handlerLink (handlerCodeDefUses, #handler) | |
316 | val _ = handlerLink (handlerLinkDefUses, #link) | |
317 | val {get = labelLive, rem = remLabelLive, ...} = | |
318 | Property.get | |
319 | (Label.plist, | |
320 | Property.initFun | |
321 | (fn l => | |
322 | let | |
323 | val {bodyInfo, argInfo, ...} = labelInfo l | |
324 | val () = removeLabelInfo l | |
325 | val {handler, link} = LiveInfo.liveHS bodyInfo | |
326 | in | |
327 | {begin = LiveInfo.live bodyInfo, | |
328 | beginNoFormals = LiveInfo.live argInfo, | |
329 | handler = handler, | |
330 | link = link} | |
331 | end)) | |
332 | val () = Vector.foreach (blocks, fn b => | |
333 | ignore (labelLive (Block.label b))) | |
334 | val _ = | |
335 | Control.diagnostics | |
336 | (fn display => | |
337 | let open Layout | |
338 | in | |
339 | Vector.foreach | |
340 | (blocks, fn b => | |
341 | let | |
342 | val l = Block.label b | |
343 | val {begin, beginNoFormals, handler, link} = labelLive l | |
344 | in | |
345 | display | |
346 | (seq [Label.layout l, | |
347 | str " ", | |
348 | record [("begin", Vector.layout Var.layout begin), | |
349 | ("beginNoFormals", | |
350 | Vector.layout Var.layout beginNoFormals), | |
351 | ("handler", Option.layout Label.layout handler), | |
352 | ("link", Bool.layout link)]]) | |
353 | end) | |
354 | end) | |
355 | in | |
356 | {labelLive = labelLive, | |
357 | remLabelLive = remLabelLive} | |
358 | end | |
359 | ||
360 | val live = | |
361 | Trace.trace2 ("Live.live", Func.layout o Function.name, Layout.ignore, | |
362 | Layout.ignore) | |
363 | live | |
364 | ||
365 | end |