| blob | 4ac4c7af2d82b5651b800da1dd2fd33a1b5b315c |
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.
67 ;;; Update information on stacks of unknown-values LVARs on the
68 ;;; boundaries of BLOCK. Return true if the start stack has been
69 ;;; changed.
70 ;;;
71 ;;; An LVAR is live at the end iff it is live at some of blocks, which
72 ;;; BLOCK can transfer control to. There are two kind of control
73 ;;; transfers: normal, expressed with BLOCK-SUCC, and NLX.
90 nle-start-stack)))
92 new-end next-stack))))
93 block
99 ;; DX objects, living in the LVAR, are
100 ;; alive in the environment, protected by
101 ;; the CLEANUP. We also cannot move them
102 ;; (because, in general, we cannot track
103 ;; all references to them). Therefore,
104 ;; everything, allocated deeper than a DX
105 ;; object, should be kept alive until the
106 ;; object is deallocated.
118 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
119 ;; ENTRY will be actually live at NLE.
120 ;;
121 ;; BUT, UNWIND-PROTECTor is called in the environment, which has
122 ;; nothing in common with the environment of its entry. So we
123 ;; fictively compute its stack from the containing cleanups, but
124 ;; do not propagate additional LVARs from the entry, thus
125 ;; preveting bogus stack cleanings.
126 ;;
127 ;; TODO: Insert a check that no values are discarded in UWP. Or,
128 ;; maybe, we just don't need to create NLX-ENTRY for UWP?
142 nil)
145 t)))))
147 \f
148 ;;;; Ordering of live UVL stacks
150 ;;; Put UVLs on the start/end stacks of BLOCK in the right order. PRED
151 ;;; is a predecessor of BLOCK with already sorted stacks; because all
152 ;;; UVLs being live at the BLOCK start are live in PRED, we just need
153 ;;; to delete dead UVLs.
160 collect lvar))
185 with repeat-p do
199 while repeat-p))
200 \f
201 ;;; This is called when we discover that the stack-top unknown-values
202 ;;; lvar at the end of BLOCK1 is different from that at the start of
203 ;;; BLOCK2 (its successor).
204 ;;;
205 ;;; We insert a call to a funny function in a new cleanup block
206 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
207 ;;; LTN have already run, we must do make an IR2 block, then do
208 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
209 ;;; block. The new block is inserted after BLOCK1 in the emit order.
210 ;;;
211 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
212 ;;; tail-recursive return or a non-local exit, then the cleanup code
213 ;;; will never actually be executed. It doesn't seem to be worth the
214 ;;; risk of trying to optimize this, since this rarely happens and
215 ;;; wastes only space.
220 ;; Returns (VALUES popped last-popped rest), where
221 ;; BEFORE = (APPEND popped rest) and
222 ;; (EQ (FIRST rest) (FIRST after))
226 for last-popped = nil then maybe-popped
227 for rest on before
230 collect maybe-popped into popped
239 repeat moved-count
240 collect moved-lvar into moved
241 collect `',moved-lvar into qmoved
269 \f
270 ;;;; stack analysis
272 ;;; Return a list of all the blocks containing genuine uses of one of
273 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
274 ;;; they don't drop through to the receiver.
288 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
289 ;;; inserting cleanup code to discard values that are generated but
290 ;;; never received. This phase doesn't need to be run when
291 ;;; Values-Receivers and Dx-Lvars are null, i.e. there are no
292 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
303 ;;; Compute sets of live UVLs and DX LVARs
308 while did-something)
317 top)))