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.
6 * MLton is released under a BSD-style license.
7 * See the file MLton-LICENSE for details.
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.
16 * Here is a description of the algorithm.
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
22 * 2. For each variable record the block in which is defined and the list of
23 * blocks where it is used.
25 * Now, for each variable, propagate the liveness information backwards from uses
26 * along basic blocks until the definition block is reached.
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.
33 functor Live (S: LIVE_STRUCTS): LIVE =
37 datatype z = datatype Statement.t
38 datatype z = datatype Transfer.t
42 datatype t = T of {live: Var.t Buffer.t,
43 liveHS: {handler: Label.t option ref,
44 link: unit option ref},
48 fun layout (T {name, ...}) = Layout.str name
50 fun new (name: string) =
51 T {live = Buffer.new {dummy = Var.bogus},
52 liveHS = {handler = ref NONE,
57 fun live (T {live, ...}) = Buffer.toVector live
59 fun liveHS (T {liveHS = {handler, link}, ...}) =
61 link = isSome (!link)}
63 fun equals (T {preds = r, ...}, T {preds = r', ...}) = r = r'
65 fun addEdge (b, T {preds, ...}) =
66 if List.exists (!preds, fn b' => equals (b, b'))
68 else List.push (preds, b)
72 ("Live.LiveInfo.addEdge", layout, layout, Unit.layout)
77 Trace.trace ("Live.consider", LiveInfo.layout, Bool.layout)
79 fun live (function, {shouldConsider: Var.t -> bool}) =
82 Trace.trace ("Live.shouldConsider", Var.layout, Bool.layout)
84 val {args, blocks, ...} = Function.dest function
94 fun loopFormals v = Vector.foreach (v, loopVar)
97 (blocks, fn Block.T {args, statements, transfer, ...} =>
99 ; Vector.foreach (statements, fn s =>
100 Statement.foreachDef (s, loopVar))
101 ; Transfer.foreachDef (transfer, loopVar)))
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)]]
109 val {get = labelInfo: Label.t -> {argInfo: LiveInfo.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,
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 =
128 then (List.push (allVars, x)
129 ; #defined (varInfo x) := SOME defined)
132 Trace.trace2 ("Live.setDefined",
133 Var.layout, LiveInfo.layout, Unit.layout)
135 (* Set the labelInfo for each block. *)
138 (blocks, fn block as Block.T {args, label, ...} =>
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")
146 | _ => let val b = LiveInfo.new (name ^ "b")
147 val b' = LiveInfo.new (name ^ "c")
148 val _ = LiveInfo.addEdge (b, b')
152 setLabelInfo (label, {argInfo = argInfo,
154 bodyInfo = bodyInfo})
156 (* Add the control-flow edges and set the defines and uses for each
159 val head = LiveInfo.new "main"
160 val _ = Vector.foreach (args, fn (x, _) => setDefined (x, head))
164 fn Block.T {args, kind, label, statements, transfer, ...} =>
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
174 Kind.Cont {handler, ...} =>
175 Handler.foreachLabel (handler, goto)
177 fun define (x: Var.t): unit = setDefined (x, b)
178 fun use (x: Var.t): unit =
181 let val {used, ...} = varInfo x
185 | b' :: _ => LiveInfo.equals (b, b'))
187 else List.push (used, b)
190 val use = Trace.trace ("Live.use", Var.layout, Unit.layout) use
195 val _ = Statement.foreachDefUse (s, {def = define o #1,
200 List.push (handlerLinkDefUses, Use ((), b))
202 List.push (handlerCodeDefUses, Def b)
204 List.push (handlerLinkDefUses, Def b)
211 val {block = Block.T {kind, ...}, ...} = labelInfo l
215 List.push (handlerCodeDefUses, Use (l, b))
219 Transfer.foreachDefLabelUse (transfer, {def = define o #1,
224 (* Back-propagate every variable from uses to define point. *)
225 fun processVar (x: Var.t): unit =
226 if not (shouldConsider x)
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
237 | SOME x' => Var.equals (x, x'))
239 else (Buffer.add (live, x)
240 ; List.push (todo, b)
242 val consider = traceConsider consider
243 val consider = ignore o consider
244 val _ = List.foreach (!used, consider)
248 | LiveInfo.T {preds, ...} :: bs =>
250 ; List.foreach (!preds, consider)
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
265 fun handlerLink (defuse: 'a defuse list ref,
266 sel: {handler: Label.t option ref,
267 link: unit option ref} -> 'a option ref) =
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.
277 (!defuse, [], fn (du, defs) =>
280 | Use (a, b as LiveInfo.T {liveHS, ...}) =>
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.
291 | b' :: _ => LiveInfo.equals (b, b'))
293 else (sel liveHS := SOME a
294 ; List.push (todo, (a, b)))
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))
302 else (sel liveHS := SOME a
303 ; List.push (todo, (a, b)))
307 | (a, LiveInfo.T {preds, ...}) :: bs =>
309 ; List.foreach (!preds, fn b => consider (b, a))
315 val _ = handlerLink (handlerCodeDefUses, #handler)
316 val _ = handlerLink (handlerLinkDefUses, #link)
317 val {get = labelLive, rem = remLabelLive, ...} =
323 val {bodyInfo, argInfo, ...} = labelInfo l
324 val () = removeLabelInfo l
325 val {handler, link} = LiveInfo.liveHS bodyInfo
327 {begin = LiveInfo.live bodyInfo,
328 beginNoFormals = LiveInfo.live argInfo,
332 val () = Vector.foreach (blocks, fn b =>
333 ignore (labelLive (Block.label b)))
342 val l = Block.label b
343 val {begin, beginNoFormals, handler, link} = labelLive l
346 (seq [Label.layout l,
348 record [("begin", Vector.layout Var.layout begin),
350 Vector.layout Var.layout beginNoFormals),
351 ("handler", Option.layout Label.layout handler),
352 ("link", Bool.layout link)]])
356 {labelLive = labelLive,
357 remLabelLive = remLabelLive}
361 Trace.trace2 ("Live.live", Func.layout o Function.name, Layout.ignore,