| blob | 00730cbafa714760b17dfbda0d34ee4ba7e2df60 |
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
101 ;; DX objects, living in the LVAR, are
102 ;; alive in the environment, protected
103 ;; by the CLEANUP. We also cannot move
104 ;; them (because, in general, we cannot
105 ;; track all references to
106 ;; them). Therefore, everything,
107 ;; allocated deeper than a DX object,
108 ;; should be kept alive until the
109 ;; object is deallocated.
121 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
122 ;; ENTRY will be actually live at NLE.
123 ;;
124 ;; BUT, UNWIND-PROTECTor is called in the environment, which has
125 ;; nothing in common with the environment of its entry. So we
126 ;; fictively compute its stack from the containing cleanups, but
127 ;; do not propagate additional LVARs from the entry, thus
128 ;; preveting bogus stack cleanings.
129 ;;
130 ;; TODO: Insert a check that no values are discarded in UWP. Or,
131 ;; maybe, we just don't need to create NLX-ENTRY for UWP?
145 nil)
148 t)))))
150 \f
151 ;;;; Ordering of live UVL stacks
153 ;;; Put UVLs on the start/end stacks of BLOCK in the right order. PRED
154 ;;; is a predecessor of BLOCK with already sorted stacks; because all
155 ;;; UVLs being live at the BLOCK start are live in PRED, we just need
156 ;;; to delete dead UVLs.
163 collect lvar))
188 with repeat-p do
202 while repeat-p))
203 \f
204 ;;; This is called when we discover that the stack-top unknown-values
205 ;;; lvar at the end of BLOCK1 is different from that at the start of
206 ;;; BLOCK2 (its successor).
207 ;;;
208 ;;; We insert a call to a funny function in a new cleanup block
209 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
210 ;;; LTN have already run, we must do make an IR2 block, then do
211 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
212 ;;; block. The new block is inserted after BLOCK1 in the emit order.
213 ;;;
214 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
215 ;;; tail-recursive return or a non-local exit, then the cleanup code
216 ;;; will never actually be executed. It doesn't seem to be worth the
217 ;;; risk of trying to optimize this, since this rarely happens and
218 ;;; wastes only space.
223 ;; Returns (VALUES popped last-popped rest), where
224 ;; BEFORE = (APPEND popped rest) and
225 ;; (EQ (FIRST rest) (FIRST after))
229 for last-popped = nil then maybe-popped
230 for rest on before
233 collect maybe-popped into popped
242 repeat moved-count
243 collect moved-lvar into moved
244 collect `',moved-lvar into qmoved
272 \f
273 ;;;; stack analysis
275 ;;; Return a list of all the blocks containing genuine uses of one of
276 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
277 ;;; they don't drop through to the receiver.
291 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
292 ;;; inserting cleanup code to discard values that are generated but
293 ;;; never received. This phase doesn't need to be run when
294 ;;; Values-Receivers and Dx-Lvars are null, i.e. there are no
295 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
306 ;;; Compute sets of live UVLs and DX LVARs
311 while did-something)
320 top)))