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
))
64 (dolist (e late early
)
67 ;;; Update information on stacks of unknown-values LVARs on the
68 ;;; boundaries of BLOCK. Return true if the start stack has been
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.
74 (defun update-uvl-live-sets (block)
75 (declare (type cblock block
))
76 (let* ((2block (block-info block
))
77 (original-start (ir2-block-start-stack 2block
))
78 (end (ir2-block-end-stack 2block
))
80 (dolist (succ (block-succ block
))
81 (setq new-end
(merge-uvl-live-sets new-end
82 (ir2-block-start-stack (block-info succ
)))))
83 (map-block-nlxes (lambda (nlx-info)
84 (let* ((nle (nlx-info-target nlx-info
))
85 (nle-start-stack (ir2-block-start-stack
87 (exit-lvar (nlx-info-lvar nlx-info
))
88 (next-stack (if exit-lvar
89 (remove exit-lvar nle-start-stack
)
91 (setq new-end
(merge-uvl-live-sets
92 new-end next-stack
))))
95 (dolist (lvar (cleanup-info dx-cleanup
))
96 (let* ((generator (lvar-use lvar
))
97 (block (node-block generator
))
98 (2block (block-info 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.
107 (setq new-end
(merge-uvl-live-sets
108 new-end
(ir2-block-end-stack 2block
)))
109 (setq new-end
(merge-uvl-live-sets
110 new-end
(ir2-block-pushed 2block
)))))))
112 (setf (ir2-block-end-stack 2block
) new-end
)
114 (let ((start new-end
))
115 (setq start
(set-difference start
(ir2-block-pushed 2block
)))
116 (setq start
(merge-uvl-live-sets start
(ir2-block-popped 2block
)))
118 ;; We cannot delete unused UVLs during NLX, so all UVLs live at
119 ;; ENTRY will be actually live at NLE.
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.
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?
129 (when (and (eq (component-head (block-component block
))
130 (first (block-pred block
)))
131 (not (bind-p (block-start-node block
))))
132 (let* ((nlx-info (nle-block-nlx-info block
))
133 (cleanup (nlx-info-cleanup nlx-info
)))
134 (unless (eq (cleanup-kind cleanup
) :unwind-protect
)
135 (let* ((entry-block (node-block (cleanup-mess-up cleanup
)))
136 (entry-stack (ir2-block-start-stack (block-info entry-block
))))
137 (setq start
(merge-uvl-live-sets start entry-stack
))))))
139 (when *check-consistency
*
140 (aver (subsetp original-start start
)))
141 (cond ((subsetp start original-start
)
144 (setf (ir2-block-start-stack 2block
) start
)
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.
154 (defun order-block-uvl-sets (block pred
)
155 (let* ((2block (block-info block
))
156 (pred-end-stack (ir2-block-end-stack (block-info pred
)))
157 (start (ir2-block-start-stack 2block
))
158 (start-stack (loop for lvar in pred-end-stack
159 when
(memq lvar start
)
161 (end (ir2-block-end-stack 2block
)))
162 (when *check-consistency
*
163 (aver (subsetp start start-stack
)))
164 (setf (ir2-block-start-stack 2block
) start-stack
)
166 (let* ((last (block-last block
))
167 (tailp-lvar (if (node-tail-p last
) (node-lvar last
)))
168 (end-stack start-stack
))
169 (dolist (pop (ir2-block-popped 2block
))
170 (aver (eq pop
(car end-stack
)))
172 (dolist (push (ir2-block-pushed 2block
))
173 (aver (not (memq push end-stack
)))
174 (push push end-stack
))
175 (aver (subsetp end end-stack
))
176 (when (and tailp-lvar
177 (eq (ir2-lvar-kind (lvar-info tailp-lvar
)) :unknown
))
178 (aver (eq tailp-lvar
(first end-stack
)))
180 (setf (ir2-block-end-stack 2block
) end-stack
))))
182 (defun order-uvl-sets (component)
183 (clear-flags component
)
184 (loop with head
= (component-head component
)
187 (do-blocks (block component
)
188 (unless (block-flag block
)
189 (let ((pred (find-if #'block-flag
(block-pred block
))))
190 (when (and (eq pred head
)
191 (not (bind-p (block-start-node block
))))
192 (let ((entry (nle-block-entry-block block
)))
193 (setq pred
(if (block-flag entry
) entry nil
))))
195 (setf (block-flag block
) t
)
196 (order-block-uvl-sets block pred
))
198 (setq repeat-p t
))))))
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).
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.
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.
216 (defun discard-unused-values (block1 block2
)
217 (declare (type cblock block1 block2
))
218 (collect ((cleanup-code))
219 (labels ((find-popped (before after
)
220 ;; Returns (VALUES popped last-popped rest), where
221 ;; BEFORE = (APPEND popped rest) and
222 ;; (EQ (FIRST rest) (FIRST after))
224 (values before
(first (last before
)) nil
)
225 (loop with first-preserved
= (car after
)
226 for last-popped
= nil then maybe-popped
228 for maybe-popped
= (car rest
)
229 while
(neq maybe-popped first-preserved
)
230 collect maybe-popped into popped
231 finally
(return (values popped last-popped rest
)))))
232 (discard (before-stack after-stack
)
234 ((eq (car before-stack
) (car after-stack
))
235 (binding* ((moved-count (mismatch before-stack after-stack
)
238 (loop for moved-lvar in before-stack
240 collect moved-lvar into moved
241 collect
`',moved-lvar into qmoved
242 finally
(return (values moved qmoved
))))
243 (q-last-moved (car (last qmoved
)))
244 ((nil last-nipped rest
)
245 (find-popped (nthcdr moved-count before-stack
)
246 (nthcdr moved-count after-stack
))))
248 `(%nip-values
',last-nipped
,q-last-moved
250 (discard (nconc moved rest
) after-stack
)))
252 (multiple-value-bind (popped last-popped rest
)
253 (find-popped before-stack after-stack
)
254 (declare (ignore popped
))
255 (cleanup-code `(%pop-values
',last-popped
))
256 (discard rest after-stack
))))))
257 (discard (ir2-block-end-stack (block-info block1
))
258 (ir2-block-start-stack (block-info block2
))))
260 (let* ((block (insert-cleanup-code block1 block2
261 (block-start-node block2
)
262 `(progn ,@(cleanup-code))))
263 (2block (make-ir2-block block
)))
264 (setf (block-info block
) 2block
)
265 (add-to-emit-order 2block
(block-info block1
))
266 (ltn-analyze-belated-block block
))))
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.
275 (defun find-pushing-blocks (receivers dx-lvars
)
276 (declare (list receivers dx-lvars
))
277 (collect ((res nil adjoin
))
278 (dolist (rec receivers
)
279 (dolist (pop (ir2-block-popped (block-info rec
)))
282 (res (node-block use
))))))
283 (dolist (dx-lvar dx-lvars
)
284 (do-uses (use dx-lvar
)
285 (res (node-block use
))))
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.
293 (defun stack-analyze (component)
294 (declare (type component component
))
295 (let* ((2comp (component-info component
))
296 (receivers (ir2-component-values-receivers 2comp
))
297 (generators (find-pushing-blocks receivers
298 (component-dx-lvars component
))))
300 (dolist (block generators
)
301 (find-pushed-lvars block
))
303 ;;; Compute sets of live UVLs and DX LVARs
304 (loop for did-something
= nil
305 do
(do-blocks-backwards (block component
)
306 (when (update-uvl-live-sets block
)
307 (setq did-something t
)))
310 (order-uvl-sets component
)
312 (do-blocks (block component
)
313 (let ((top (ir2-block-end-stack (block-info block
))))
314 (dolist (succ (block-succ block
))
315 (when (and (block-start succ
)
316 (not (eq (ir2-block-start-stack (block-info succ
))
318 (discard-unused-values block succ
))))))