| blob | 51d416dbf9241be14f42ffa8cb7cf57bf9db6e23 |
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 ;;; Update information on stacks of unknown-values LVARs on the
69 ;;; boundaries of BLOCK. Return true if the start stack has been
70 ;;; changed.
71 ;;;
72 ;;; An LVAR is live at the end iff it is live at some of blocks, which
73 ;;; BLOCK can transfer control to. There are two kind of control
74 ;;; transfers: normal, expressed with BLOCK-SUCC, and NLX.
91 nle-start-stack)))
93 new-end next-stack))))
94 block
100 ;; DX objects, living in the LVAR, are alive in
101 ;; the environment, protected by the CLEANUP. We
102 ;; also cannot move them (because, in general, we
103 ;; cannot track all references to them).
104 ;; Therefore, everything, allocated deeper than a
105 ;; DX object -- that is, before the DX object --
106 ;; should be kept alive until the object is
107 ;; deallocated.
108 ;;
109 ;; Since DX generators end their blocks, we can
110 ;; find out UVLs allocated before them by looking
111 ;; at the stack at the end of the block.
112 ;;
113 ;; FIXME: This is not quite true: REFs to DX
114 ;; closures don't end their blocks!
126 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
127 ;; ENTRY will be actually live at NLE.
128 ;;
129 ;; BUT, UNWIND-PROTECTor is called in the environment, which has
130 ;; nothing in common with the environment of its entry. So we
131 ;; fictively compute its stack from the containing cleanups, but
132 ;; do not propagate additional LVARs from the entry, thus
133 ;; preveting bogus stack cleanings.
134 ;;
135 ;; TODO: Insert a check that no values are discarded in UWP. Or,
136 ;; maybe, we just don't need to create NLX-ENTRY for UWP?
150 nil)
153 t)))))
155 \f
156 ;;;; Ordering of live UVL stacks
158 ;;; Put UVLs on the start/end stacks of BLOCK in the right order. PRED
159 ;;; is a predecessor of BLOCK with already sorted stacks; because all
160 ;;; UVLs being live at the BLOCK start are live in PRED, we just need
161 ;;; to delete dead UVLs.
168 collect lvar))
193 with repeat-p do
207 while repeat-p))
208 \f
209 ;;; This is called when we discover that the stack-top unknown-values
210 ;;; lvar at the end of BLOCK1 is different from that at the start of
211 ;;; BLOCK2 (its successor).
212 ;;;
213 ;;; We insert a call to a funny function in a new cleanup block
214 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
215 ;;; LTN have already run, we must do make an IR2 block, then do
216 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
217 ;;; block. The new block is inserted after BLOCK1 in the emit order.
218 ;;;
219 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
220 ;;; tail-recursive return or a non-local exit, then the cleanup code
221 ;;; will never actually be executed. It doesn't seem to be worth the
222 ;;; risk of trying to optimize this, since this rarely happens and
223 ;;; wastes only space.
228 ;; Returns (VALUES popped last-popped rest), where
229 ;; BEFORE = (APPEND popped rest) and
230 ;; (EQ (FIRST rest) (FIRST after))
234 for last-popped = nil then maybe-popped
235 for rest on before
238 collect maybe-popped into popped
247 repeat moved-count
248 collect moved-lvar into moved
249 collect `',moved-lvar into qmoved
277 \f
278 ;;;; stack analysis
280 ;;; Return a list of all the blocks containing genuine uses of one of
281 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
282 ;;; they don't drop through to the receiver.
296 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
297 ;;; inserting cleanup code to discard values that are generated but
298 ;;; never received. This phase doesn't need to be run when
299 ;;; Values-Receivers and Dx-Lvars are null, i.e. there are no
300 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
311 ;;; Compute sets of live UVLs and DX LVARs
316 while did-something)
325 top)))