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.
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.
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.
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.
23 (defun find-pushed-lvars (block)
24 (let* ((2block (block-info block
))
25 (popped (ir2-block-popped 2block
))
27 (lvar-dest (car (last popped
)))
31 (do-nodes (node lvar block
)
32 (when (eq node last-pop
)
36 (or (lvar-dynamic-extent lvar
)
37 (let ((dest (lvar-dest lvar
))
38 (2lvar (lvar-info lvar
)))
39 (and (not (eq (node-block dest
) block
))
41 (eq (ir2-lvar-kind 2lvar
) :unknown
)))))
42 (aver (or saw-last
(not last-pop
)))
45 (setf (ir2-block-pushed 2block
) (pushed))))
48 ;;;; Computation of live UVL sets
49 (defun nle-block-nlx-info (block)
50 (let* ((start-node (block-start-node block
))
51 (nlx-ref (ctran-next (node-next start-node
)))
52 (nlx-info (constant-value (ref-leaf nlx-ref
))))
54 (defun nle-block-entry-block (block)
55 (let* ((nlx-info (nle-block-nlx-info block
))
56 (mess-up (cleanup-mess-up (nlx-info-cleanup nlx-info
)))
57 (entry-block (node-block mess-up
)))
60 ;;; Add LVARs from LATE to EARLY; use EQ to check whether EARLY has
62 (defun merge-uvl-live-sets (early late
)
63 (declare (type list early late
))
65 (dolist (e late early
)
68 ;;; Update information on stacks of unknown-values LVARs on the
69 ;;; boundaries of BLOCK. Return true if the start stack has been
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.
75 (defun update-uvl-live-sets (block)
76 (declare (type cblock block
))
77 (let* ((2block (block-info block
))
78 (original-start (ir2-block-start-stack 2block
))
79 (end (ir2-block-end-stack 2block
))
81 (dolist (succ (block-succ block
))
82 (setq new-end
(merge-uvl-live-sets new-end
83 (ir2-block-start-stack (block-info succ
)))))
84 (map-block-nlxes (lambda (nlx-info)
85 (let* ((nle (nlx-info-target nlx-info
))
86 (nle-start-stack (ir2-block-start-stack
88 (exit-lvar (nlx-info-lvar nlx-info
))
89 (next-stack (if exit-lvar
90 (remove exit-lvar nle-start-stack
)
92 (setq new-end
(merge-uvl-live-sets
93 new-end next-stack
))))
96 (dolist (lvar (cleanup-info dx-cleanup
))
97 (do-uses (generator lvar
)
98 (let* ((block (node-block generator
))
99 (2block (block-info 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
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.
113 ;; FIXME: This is not quite true: REFs to DX
114 ;; closures don't end their blocks!
115 (setq new-end
(merge-uvl-live-sets
116 new-end
(ir2-block-end-stack 2block
)))
117 (setq new-end
(merge-uvl-live-sets
118 new-end
(ir2-block-pushed 2block
))))))))
120 (setf (ir2-block-end-stack 2block
) new-end
)
122 (let ((start new-end
))
123 (setq start
(set-difference start
(ir2-block-pushed 2block
)))
124 (setq start
(merge-uvl-live-sets start
(ir2-block-popped 2block
)))
126 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
127 ;; ENTRY will be actually live at NLE.
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.
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?
137 (when (and (eq (component-head (block-component block
))
138 (first (block-pred block
)))
139 (not (bind-p (block-start-node block
))))
140 (let* ((nlx-info (nle-block-nlx-info block
))
141 (cleanup (nlx-info-cleanup nlx-info
)))
142 (unless (eq (cleanup-kind cleanup
) :unwind-protect
)
143 (let* ((entry-block (node-block (cleanup-mess-up cleanup
)))
144 (entry-stack (ir2-block-start-stack (block-info entry-block
))))
145 (setq start
(merge-uvl-live-sets start entry-stack
))))))
147 (when *check-consistency
*
148 (aver (subsetp original-start start
)))
149 (cond ((subsetp start original-start
)
152 (setf (ir2-block-start-stack 2block
) start
)
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.
162 (defun order-block-uvl-sets (block pred
)
163 (let* ((2block (block-info block
))
164 (pred-end-stack (ir2-block-end-stack (block-info pred
)))
165 (start (ir2-block-start-stack 2block
))
166 (start-stack (loop for lvar in pred-end-stack
167 when
(memq lvar start
)
169 (end (ir2-block-end-stack 2block
)))
170 (when *check-consistency
*
171 (aver (subsetp start start-stack
)))
172 (setf (ir2-block-start-stack 2block
) start-stack
)
174 (let* ((last (block-last block
))
175 (tailp-lvar (if (node-tail-p last
) (node-lvar last
)))
176 (end-stack start-stack
))
177 (dolist (pop (ir2-block-popped 2block
))
178 (aver (eq pop
(car end-stack
)))
180 (dolist (push (ir2-block-pushed 2block
))
181 (aver (not (memq push end-stack
)))
182 (push push end-stack
))
183 (aver (subsetp end end-stack
))
184 (when (and tailp-lvar
185 (eq (ir2-lvar-kind (lvar-info tailp-lvar
)) :unknown
))
186 (aver (eq tailp-lvar
(first end-stack
)))
188 (setf (ir2-block-end-stack 2block
) end-stack
))))
190 (defun order-uvl-sets (component)
191 (clear-flags component
)
192 (loop with head
= (component-head component
)
195 (do-blocks (block component
)
196 (unless (block-flag block
)
197 (let ((pred (find-if #'block-flag
(block-pred block
))))
198 (when (and (eq pred head
)
199 (not (bind-p (block-start-node block
))))
200 (let ((entry (nle-block-entry-block block
)))
201 (setq pred
(if (block-flag entry
) entry nil
))))
203 (setf (block-flag block
) t
)
204 (order-block-uvl-sets block pred
))
206 (setq repeat-p t
))))))
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).
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.
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.
224 (defun discard-unused-values (block1 block2
)
225 (declare (type cblock block1 block2
))
226 (collect ((cleanup-code))
227 (labels ((find-popped (before after
)
228 ;; Returns (VALUES popped last-popped rest), where
229 ;; BEFORE = (APPEND popped rest) and
230 ;; (EQ (FIRST rest) (FIRST after))
232 (values before
(first (last before
)) nil
)
233 (loop with first-preserved
= (car after
)
234 for last-popped
= nil then maybe-popped
236 for maybe-popped
= (car rest
)
237 while
(neq maybe-popped first-preserved
)
238 collect maybe-popped into popped
239 finally
(return (values popped last-popped rest
)))))
240 (discard (before-stack after-stack
)
242 ((eq (car before-stack
) (car after-stack
))
243 (binding* ((moved-count (mismatch before-stack after-stack
)
246 (loop for moved-lvar in before-stack
248 collect moved-lvar into moved
249 collect
`',moved-lvar into qmoved
250 finally
(return (values moved qmoved
))))
251 (q-last-moved (car (last qmoved
)))
252 ((nil last-nipped rest
)
253 (find-popped (nthcdr moved-count before-stack
)
254 (nthcdr moved-count after-stack
))))
256 `(%nip-values
',last-nipped
,q-last-moved
258 (discard (nconc moved rest
) after-stack
)))
260 (multiple-value-bind (popped last-popped rest
)
261 (find-popped before-stack after-stack
)
262 (declare (ignore popped
))
263 (cleanup-code `(%pop-values
',last-popped
))
264 (discard rest after-stack
))))))
265 (discard (ir2-block-end-stack (block-info block1
))
266 (ir2-block-start-stack (block-info block2
))))
268 (let* ((block (insert-cleanup-code block1 block2
269 (block-start-node block2
)
270 `(progn ,@(cleanup-code))))
271 (2block (make-ir2-block block
)))
272 (setf (block-info block
) 2block
)
273 (add-to-emit-order 2block
(block-info block1
))
274 (ltn-analyze-belated-block block
))))
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.
283 (defun find-pushing-blocks (receivers dx-lvars
)
284 (declare (list receivers dx-lvars
))
285 (collect ((res nil adjoin
))
286 (dolist (rec receivers
)
287 (dolist (pop (ir2-block-popped (block-info rec
)))
290 (res (node-block use
))))))
291 (dolist (dx-lvar dx-lvars
)
292 (do-uses (use dx-lvar
)
293 (res (node-block use
))))
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.
301 (defun stack-analyze (component)
302 (declare (type component component
))
303 (let* ((2comp (component-info component
))
304 (receivers (ir2-component-values-receivers 2comp
))
305 (generators (find-pushing-blocks receivers
306 (component-dx-lvars component
))))
308 (dolist (block generators
)
309 (find-pushed-lvars block
))
311 ;;; Compute sets of live UVLs and DX LVARs
312 (loop for did-something
= nil
313 do
(do-blocks-backwards (block component
)
314 (when (update-uvl-live-sets block
)
315 (setq did-something t
)))
318 (order-uvl-sets component
)
320 (do-blocks (block component
)
321 (let ((top (ir2-block-end-stack (block-info block
))))
322 (dolist (succ (block-succ block
))
323 (when (and (block-start succ
)
324 (not (eq (ir2-block-start-stack (block-info succ
))
326 (discard-unused-values block succ
))))))