| blob | ab88bea2322717ae148ed1d3773769b1591d2286 |
1 ;;;; This file implements the stack analysis phase in the compiler. We
2 ;;;; analyse lifetime of dynamically allocated object packets on stack
3 ;;;; and insert cleanups where necessary.
4 ;;;;
5 ;;;; Currently there are two kinds of interesting stack packets: UVLs,
6 ;;;; whose use and destination lie in different blocks, and LVARs of
7 ;;;; constructors of dynamic-extent objects.
9 ;;;; This software is part of the SBCL system. See the README file for
10 ;;;; more information.
11 ;;;;
12 ;;;; This software is derived from the CMU CL system, which was
13 ;;;; written at Carnegie Mellon University and released into the
14 ;;;; public domain. The software is in the public domain and is
15 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
16 ;;;; files for more information.
19 \f
20 ;;; Scan through BLOCK looking for uses of :UNKNOWN lvars that have
21 ;;; their DEST outside of the block. We do some checking to verify the
22 ;;; invariant that all pushes come after the last pop.
28 nil)))
40 2lvar
47 \f
48 ;;;; Computation of live UVL sets
53 nlx-info))
58 entry-block))
60 ;;; Add LVARs from LATE to EARLY; use EQ to check whether EARLY has
61 ;;; been changed.
64 ;; FIXME: O(N^2)
68 ;; Blocks are numbered in reverse DFO order, so the "lowest common
69 ;; dominator" of a set of blocks is the closest dominator of all of
70 ;; the blocks.
72 ;; FIXME: NIL is defined as a valid value for BLOCK-DOMINATORS,
73 ;; meaning "all blocks in component". Actually handle this case.
84 ;;; Carefully back-propagate DX LVARs from the start of their
85 ;;; environment to where they are allocated, along all code paths
86 ;;; which actually allocate said LVARs.
90 ;; We have to back-propagate the lifetime of DX-LVAR to its USEs,
91 ;; but only along the paths which actually USE it. The naive
92 ;; solution (which we're going with for now) is a depth-first search
93 ;; over an arbitrarily complex chunk of flow graph that is known to
94 ;; have a single entry block.
106 ;; The LVAR is live on exit from a use-block, but
107 ;; not on entry.
111 ;; Don't go back past START-BLOCK.
116 ;; Never follow the same path segment twice.
129 ;;; Update information on stacks of unknown-values LVARs on the
130 ;;; boundaries of BLOCK. Return true if the start stack has been
131 ;;; changed.
132 ;;;
133 ;;; An LVAR is live at the end iff it is live at some of blocks, which
134 ;;; BLOCK can transfer control to. There are two kind of control
135 ;;; transfers: normal, expressed with BLOCK-SUCC, and NLX.
144 ;; Don't back-propagate DX
145 ;; LVARs automatically,
146 ;; they're handled specially.
156 nle-start-stack)))
158 new-end next-stack))))
159 block
165 ;; DX objects, living in the LVAR, are alive in
166 ;; the environment, protected by the CLEANUP. We
167 ;; also cannot move them (because, in general, we
168 ;; cannot track all references to them).
169 ;; Therefore, everything, allocated deeper than a
170 ;; DX object -- that is, before the DX object --
171 ;; should be kept alive until the object is
172 ;; deallocated.
173 ;;
174 ;; Since DX generators end their blocks, we can
175 ;; find out UVLs allocated before them by looking
176 ;; at the stack at the end of the block.
184 ;; If a block starts with an "entry DX" node (the start of a DX
185 ;; environment) then we need to back-propagate the DX LVARs to
186 ;; their allocation sites. We need to be clever about this
187 ;; because some code paths may not allocate all of the DX LVARs.
188 ;;
189 ;; FIXME: Use BLOCK-FLAG to make this happen only once.
200 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
201 ;; ENTRY will be actually live at NLE.
202 ;;
203 ;; BUT, UNWIND-PROTECTor is called in the environment, which has
204 ;; nothing in common with the environment of its entry. So we
205 ;; fictively compute its stack from the containing cleanups, but
206 ;; do not propagate additional LVARs from the entry, thus
207 ;; preveting bogus stack cleanings.
208 ;;
209 ;; TODO: Insert a check that no values are discarded in UWP. Or,
210 ;; maybe, we just don't need to create NLX-ENTRY for UWP?
224 nil)
227 t)))))
229 \f
230 ;;;; Ordering of live UVL stacks
235 collect item))
240 result)
253 ;;; Put UVLs on the start/end stacks of BLOCK in the right order. PRED
254 ;;; is a predecessor of BLOCK with already sorted stacks; if all UVLs
255 ;;; being live at the BLOCK start are live in PRED we just need to
256 ;;; delete killed UVLs, otherwise we need (thanks to conditional or
257 ;;; nested DX) to set a total order for the UVLs live at the end of
258 ;;; all predecessors.
267 ;; If BLOCK is a control-flow join for DX allocation paths with
268 ;; different sets of DX LVARs being pushed then we cannot
269 ;; process it correctly until all of its predecessors have been
270 ;; processed.
273 ;; If we are in the conditional-DX control-flow join case then
274 ;; we need to find an order for START-STACK that is compatible
275 ;; with all of our predecessors.
302 t)
306 ;; KLUDGE: Workaround for lp#308914: we keep track of number of blocks
307 ;; needing repeats, and bug out if we get stuck.
325 ;; If the todo count is the same as on last iteration and
326 ;; there are still blocks to do, it means we are stuck,
327 ;; which in turn means the unmarked blocks are actually
328 ;; unreachable and should have been eliminated by DCE,
329 ;; and will very likely cause problems with later parts
330 ;; of STACK analysis, so abort now if we're in trouble.
333 \f
334 ;;; This is called when we discover that the stack-top unknown-values
335 ;;; lvar at the end of BLOCK1 is different from that at the start of
336 ;;; BLOCK2 (its successor).
337 ;;;
338 ;;; We insert a call to a funny function in a new cleanup block
339 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
340 ;;; LTN have already run, we must do make an IR2 block, then do
341 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
342 ;;; block. The new block is inserted after BLOCK1 in the emit order.
343 ;;;
344 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
345 ;;; tail-recursive return or a non-local exit, then the cleanup code
346 ;;; will never actually be executed. It doesn't seem to be worth the
347 ;;; risk of trying to optimize this, since this rarely happens and
348 ;;; wastes only space.
353 ;; Returns (VALUES popped last-popped rest), where
354 ;; BEFORE = (APPEND popped rest) and
355 ;; (EQ (FIRST rest) (FIRST after))
359 for last-popped = nil then maybe-popped
360 for rest on before
363 collect maybe-popped into popped
372 repeat moved-count
373 collect moved-lvar into moved
374 collect `',moved-lvar into qmoved
392 for previous-lvar = nil then lvar
393 for lvar in after-stack
400 start-stack end-stack)))
411 ;; Set the start and end stacks to make traces less
412 ;; confusing. Purely cosmetic.
417 \f
418 ;;;; stack analysis
420 ;;; Return a list of all the blocks containing genuine uses of one of
421 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
422 ;;; they don't drop through to the receiver.
436 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
437 ;;; inserting cleanup code to discard values that are generated but
438 ;;; never received and to set appropriate bounds for DX values that
439 ;;; are cleaned up but never allocated. This phase doesn't need to be
440 ;;; run when Values-Receivers and Dx-Lvars are null, i.e. there are no
441 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
452 ;; Compute sets of live UVLs and DX LVARs
457 while did-something)
466 top)))