| blob | fcbd1e7a78fb220812bd248a962b373334e4bdb9 |
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.
177 ;;
178 ;; FIXME: This is not quite true: REFs to DX
179 ;; closures don't end their blocks!
187 ;; If a block starts with an "entry DX" node (the start of a DX
188 ;; environment) then we need to back-propagate the DX LVARs to
189 ;; their allocation sites. We need to be clever about this
190 ;; because some code paths may not allocate all of the DX LVARs.
191 ;;
192 ;; FIXME: Use BLOCK-FLAG to make this happen only once.
203 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
204 ;; ENTRY will be actually live at NLE.
205 ;;
206 ;; BUT, UNWIND-PROTECTor is called in the environment, which has
207 ;; nothing in common with the environment of its entry. So we
208 ;; fictively compute its stack from the containing cleanups, but
209 ;; do not propagate additional LVARs from the entry, thus
210 ;; preveting bogus stack cleanings.
211 ;;
212 ;; TODO: Insert a check that no values are discarded in UWP. Or,
213 ;; maybe, we just don't need to create NLX-ENTRY for UWP?
227 nil)
230 t)))))
232 \f
233 ;;;; Ordering of live UVL stacks
238 collect item))
243 result)
256 ;;; Put UVLs on the start/end stacks of BLOCK in the right order. PRED
257 ;;; is a predecessor of BLOCK with already sorted stacks; if all UVLs
258 ;;; being live at the BLOCK start are live in PRED we just need to
259 ;;; delete killed UVLs, otherwise we need (thanks to conditional or
260 ;;; nested DX) to set a total order for the UVLs live at the end of
261 ;;; all predecessors.
270 ;; If BLOCK is a control-flow join for DX allocation paths with
271 ;; different sets of DX LVARs being pushed then we cannot
272 ;; process it correctly until all of its predecessors have been
273 ;; processed.
276 ;; If we are in the conditional-DX control-flow join case then
277 ;; we need to find an order for START-STACK that is compatible
278 ;; with all of our predecessors.
305 t)
309 ;; KLUDGE: Workaround for lp#308914: we keep track of number of blocks
310 ;; needing repeats, and bug out if we get stuck.
328 ;; If the todo count is the same as on last iteration and
329 ;; there are still blocks to do, it means we are stuck,
330 ;; which in turn means the unmarked blocks are actually
331 ;; unreachable and should have been eliminated by DCE,
332 ;; and will very likely cause problems with later parts
333 ;; of STACK analysis, so abort now if we're in trouble.
336 \f
337 ;;; This is called when we discover that the stack-top unknown-values
338 ;;; lvar at the end of BLOCK1 is different from that at the start of
339 ;;; BLOCK2 (its successor).
340 ;;;
341 ;;; We insert a call to a funny function in a new cleanup block
342 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
343 ;;; LTN have already run, we must do make an IR2 block, then do
344 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
345 ;;; block. The new block is inserted after BLOCK1 in the emit order.
346 ;;;
347 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
348 ;;; tail-recursive return or a non-local exit, then the cleanup code
349 ;;; will never actually be executed. It doesn't seem to be worth the
350 ;;; risk of trying to optimize this, since this rarely happens and
351 ;;; wastes only space.
356 ;; Returns (VALUES popped last-popped rest), where
357 ;; BEFORE = (APPEND popped rest) and
358 ;; (EQ (FIRST rest) (FIRST after))
362 for last-popped = nil then maybe-popped
363 for rest on before
366 collect maybe-popped into popped
375 repeat moved-count
376 collect moved-lvar into moved
377 collect `',moved-lvar into qmoved
395 for previous-lvar = nil then lvar
396 for lvar in after-stack
403 start-stack end-stack)))
412 ;; Set the start and end stacks to make traces less
413 ;; confusing. Purely cosmetic.
420 \f
421 ;;;; stack analysis
423 ;;; Return a list of all the blocks containing genuine uses of one of
424 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
425 ;;; they don't drop through to the receiver.
439 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
440 ;;; inserting cleanup code to discard values that are generated but
441 ;;; never received and to set appropriate bounds for DX values that
442 ;;; are cleaned up but never allocated. This phase doesn't need to be
443 ;;; run when Values-Receivers and Dx-Lvars are null, i.e. there are no
444 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
455 ;;; Compute sets of live UVLs and DX LVARs
460 while did-something)
469 top)))