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 ;; KLUDGE: Workaround for lp#308914: we keep track of number of blocks
193 ;; needing repeats, and bug out if we get stuck.
194 (loop with head
= (component-head component
)
197 do
(psetq last-todo todo
199 do
(do-blocks (block component
)
200 (unless (block-flag block
)
201 (let ((pred (find-if #'block-flag
(block-pred block
))))
202 (when (and (eq pred head
)
203 (not (bind-p (block-start-node block
))))
204 (let ((entry (nle-block-entry-block block
)))
205 (setq pred
(if (block-flag entry
) entry nil
))))
207 (setf (block-flag block
) t
)
208 (order-block-uvl-sets block pred
))
211 do
(when (= last-todo todo
)
212 ;; If the todo count is the same as on last iteration, it means
213 ;; we are stuck, which in turn means the unmarked blocks are
214 ;; actually unreachable, so UVL set ordering for them doesn't
216 (return-from order-uvl-sets
))
219 ;;; This is called when we discover that the stack-top unknown-values
220 ;;; lvar at the end of BLOCK1 is different from that at the start of
221 ;;; BLOCK2 (its successor).
223 ;;; We insert a call to a funny function in a new cleanup block
224 ;;; introduced between BLOCK1 and BLOCK2. Since control analysis and
225 ;;; LTN have already run, we must do make an IR2 block, then do
226 ;;; ADD-TO-EMIT-ORDER and LTN-ANALYZE-BELATED-BLOCK on the new
227 ;;; block. The new block is inserted after BLOCK1 in the emit order.
229 ;;; If the control transfer between BLOCK1 and BLOCK2 represents a
230 ;;; tail-recursive return or a non-local exit, then the cleanup code
231 ;;; will never actually be executed. It doesn't seem to be worth the
232 ;;; risk of trying to optimize this, since this rarely happens and
233 ;;; wastes only space.
234 (defun discard-unused-values (block1 block2
)
235 (declare (type cblock block1 block2
))
236 (collect ((cleanup-code))
237 (labels ((find-popped (before after
)
238 ;; Returns (VALUES popped last-popped rest), where
239 ;; BEFORE = (APPEND popped rest) and
240 ;; (EQ (FIRST rest) (FIRST after))
242 (values before
(first (last before
)) nil
)
243 (loop with first-preserved
= (car after
)
244 for last-popped
= nil then maybe-popped
246 for maybe-popped
= (car rest
)
247 while
(neq maybe-popped first-preserved
)
248 collect maybe-popped into popped
249 finally
(return (values popped last-popped rest
)))))
250 (discard (before-stack after-stack
)
252 ((eq (car before-stack
) (car after-stack
))
253 (binding* ((moved-count (mismatch before-stack after-stack
)
256 (loop for moved-lvar in before-stack
258 collect moved-lvar into moved
259 collect
`',moved-lvar into qmoved
260 finally
(return (values moved qmoved
))))
261 (q-last-moved (car (last qmoved
)))
262 ((nil last-nipped rest
)
263 (find-popped (nthcdr moved-count before-stack
)
264 (nthcdr moved-count after-stack
))))
266 `(%nip-values
',last-nipped
,q-last-moved
268 (discard (nconc moved rest
) after-stack
)))
270 (multiple-value-bind (popped last-popped rest
)
271 (find-popped before-stack after-stack
)
272 (declare (ignore popped
))
273 (cleanup-code `(%pop-values
',last-popped
))
274 (discard rest after-stack
))))))
275 (discard (ir2-block-end-stack (block-info block1
))
276 (ir2-block-start-stack (block-info block2
))))
278 (let* ((block (insert-cleanup-code block1 block2
279 (block-start-node block2
)
280 `(progn ,@(cleanup-code))))
281 (2block (make-ir2-block block
)))
282 (setf (block-info block
) 2block
)
283 (add-to-emit-order 2block
(block-info block1
))
284 (ltn-analyze-belated-block block
))))
290 ;;; Return a list of all the blocks containing genuine uses of one of
291 ;;; the RECEIVERS (blocks) and DX-LVARS. Exits are excluded, since
292 ;;; they don't drop through to the receiver.
293 (defun find-pushing-blocks (receivers dx-lvars
)
294 (declare (list receivers dx-lvars
))
295 (collect ((res nil adjoin
))
296 (dolist (rec receivers
)
297 (dolist (pop (ir2-block-popped (block-info rec
)))
300 (res (node-block use
))))))
301 (dolist (dx-lvar dx-lvars
)
302 (do-uses (use dx-lvar
)
303 (res (node-block use
))))
306 ;;; Analyze the use of unknown-values and DX lvars in COMPONENT,
307 ;;; inserting cleanup code to discard values that are generated but
308 ;;; never received. This phase doesn't need to be run when
309 ;;; Values-Receivers and Dx-Lvars are null, i.e. there are no
310 ;;; unknown-values lvars used across block boundaries and no DX LVARs.
311 (defun stack-analyze (component)
312 (declare (type component component
))
313 (let* ((2comp (component-info component
))
314 (receivers (ir2-component-values-receivers 2comp
))
315 (generators (find-pushing-blocks receivers
316 (component-dx-lvars component
))))
318 (dolist (block generators
)
319 (find-pushed-lvars block
))
321 ;;; Compute sets of live UVLs and DX LVARs
322 (loop for did-something
= nil
323 do
(do-blocks-backwards (block component
)
324 (when (update-uvl-live-sets block
)
325 (setq did-something t
)))
328 (order-uvl-sets component
)
330 (do-blocks (block component
)
331 (let ((top (ir2-block-end-stack (block-info block
))))
332 (dolist (succ (block-succ block
))
333 (when (and (block-start succ
)
334 (not (eq (ir2-block-start-stack (block-info succ
))
336 (discard-unused-values block succ
))))))