1 ;;;; This file implements the environment analysis phase for the
2 ;;;; compiler. This phase annotates IR1 with a hierarchy environment
3 ;;;; structures, determining the physical environment that each LAMBDA
4 ;;;; allocates its variables and finding what values are closed over
5 ;;;; by each physical environment.
7 ;;;; This software is part of the SBCL system. See the README file for
10 ;;;; This software is derived from the CMU CL system, which was
11 ;;;; written at Carnegie Mellon University and released into the
12 ;;;; public domain. The software is in the public domain and is
13 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
14 ;;;; files for more information.
18 ;;; Do environment analysis on the code in COMPONENT. This involves
20 ;;; 1. Make a PHYSENV structure for each non-LET LAMBDA, assigning
21 ;;; the LAMBDA-PHYSENV for all LAMBDAs.
22 ;;; 2. Find all values that need to be closed over by each
23 ;;; physical environment.
24 ;;; 3. Scan the blocks in the component closing over non-local-exit
26 ;;; 4. Delete all non-top-level functions with no references. This
27 ;;; should only get functions with non-NULL kinds, since normal
28 ;;; functions are deleted when their references go to zero.
29 (defun physenv-analyze (component)
30 (declare (type component component
))
31 (aver (every (lambda (x)
32 (eq (functional-kind x
) :deleted
))
33 (component-new-functionals component
)))
34 (setf (component-new-functionals component
) ())
35 (dolist (clambda (component-lambdas component
))
36 (reinit-lambda-physenv clambda
))
37 (mapc #'add-lambda-vars-and-let-vars-to-closures
38 (component-lambdas component
))
40 (find-non-local-exits component
)
41 (recheck-dynamic-extent-lvars component
)
42 (find-cleanup-points component
)
43 (tail-annotate component
)
45 (dolist (fun (component-lambdas component
))
46 (when (null (leaf-refs fun
))
47 (let ((kind (functional-kind fun
)))
48 (unless (or (eq kind
:toplevel
)
49 (functional-has-external-references-p fun
))
50 (aver (member kind
'(:optional
:cleanup
:escape
)))
51 (setf (functional-kind fun
) nil
)
52 (delete-functional fun
)))))
54 (setf (component-nlx-info-generated-p component
) t
)
57 ;;; This is to be called on a COMPONENT with top level LAMBDAs before
58 ;;; the compilation of the associated non-top-level code to detect
59 ;;; closed over top level variables. We just do COMPUTE-CLOSURE on all
60 ;;; the lambdas. This will pre-allocate environments for all the
61 ;;; functions with closed-over top level variables. The post-pass will
62 ;;; use the existing structure, rather than allocating a new one. We
63 ;;; return true if we discover any possible closure vars.
64 (defun pre-physenv-analyze-toplevel (component)
65 (declare (type component component
))
67 (dolist (lambda (component-lambdas component
))
68 (when (add-lambda-vars-and-let-vars-to-closures lambda
)
72 ;;; If CLAMBDA has a PHYSENV, return it, otherwise assign an empty one
74 (defun get-lambda-physenv (clambda)
75 (declare (type clambda clambda
))
76 (let ((homefun (lambda-home clambda
)))
77 (or (lambda-physenv homefun
)
78 (let ((res (make-physenv :lambda homefun
)))
79 (setf (lambda-physenv homefun
) res
)
80 ;; All the LETLAMBDAs belong to HOMEFUN, and share the same
81 ;; PHYSENV. Thus, (1) since HOMEFUN's PHYSENV was NIL,
82 ;; theirs should be NIL too, and (2) since we're modifying
83 ;; HOMEFUN's PHYSENV, we should modify theirs, too.
84 (dolist (letlambda (lambda-lets homefun
))
85 (aver (eql (lambda-home letlambda
) homefun
))
86 (aver (null (lambda-physenv letlambda
)))
87 (setf (lambda-physenv letlambda
) res
))
90 ;;; If FUN has no physical environment, assign one, otherwise clean up
91 ;;; the old physical environment and the INDIRECT flag on LAMBDA-VARs.
92 ;;; This is necessary because pre-analysis is done before
94 (defun reinit-lambda-physenv (fun)
95 (let ((old (lambda-physenv (lambda-home fun
))))
97 (setf (physenv-closure old
) nil
)
99 (dolist (var (lambda-vars fun
))
100 (setf (lambda-var-indirect var
) nil
))))
102 (map nil
#'clear
(lambda-lets fun
))))
104 (get-lambda-physenv fun
))))
107 ;;; Get NODE's environment, assigning one if necessary.
108 (defun get-node-physenv (node)
109 (declare (type node node
))
110 (get-lambda-physenv (node-home-lambda node
)))
112 ;;; private guts of ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES
114 ;;; This is the old CMU CL COMPUTE-CLOSURE, which only works on
115 ;;; LAMBDA-VARS directly, not on the LAMBDA-VARS of LAMBDA-LETS. It
116 ;;; seems never to be valid to use this operation alone, so in SBCL,
117 ;;; it's private, and the public interface,
118 ;;; ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES, always runs over all the
119 ;;; variables, not only the LAMBDA-VARS of CLAMBDA itself but also
120 ;;; the LAMBDA-VARS of CLAMBDA's LAMBDA-LETS.
121 (defun %add-lambda-vars-to-closures
(clambda)
122 (let ((physenv (get-lambda-physenv clambda
))
124 (note-unreferenced-vars clambda
)
125 (dolist (var (lambda-vars clambda
))
126 (dolist (ref (leaf-refs var
))
127 (let ((ref-physenv (get-node-physenv ref
)))
128 (unless (eq ref-physenv physenv
)
129 (when (lambda-var-sets var
)
130 (setf (lambda-var-indirect var
) t
))
131 (setq did-something t
)
132 (close-over var ref-physenv physenv
))))
133 (dolist (set (basic-var-sets var
))
135 ;; Variables which are set but never referenced can be
136 ;; optimized away, and closing over them here would just
137 ;; interfere with that. (In bug 147, it *did* interfere with
138 ;; that, causing confusion later. This UNLESS solves that
139 ;; problem, but I (WHN) am not 100% sure it's best to solve
140 ;; the problem this way instead of somehow solving it
141 ;; somewhere upstream and just doing (AVER (LEAF-REFS VAR))
143 (unless (null (leaf-refs var
))
145 (let ((set-physenv (get-node-physenv set
)))
146 (unless (eq set-physenv physenv
)
147 (setf did-something t
148 (lambda-var-indirect var
) t
)
149 (close-over var set-physenv physenv
))))))
152 ;;; Find any variables in CLAMBDA -- either directly in LAMBDA-VARS or
153 ;;; in the LAMBDA-VARS of elements of LAMBDA-LETS -- with references
154 ;;; outside of the home environment and close over them. If a
155 ;;; closed-over variable is set, then we set the INDIRECT flag so that
156 ;;; we will know the closed over value is really a pointer to the
157 ;;; value cell. We also warn about unreferenced variables here, just
158 ;;; because it's a convenient place to do it. We return true if we
159 ;;; close over anything.
160 (defun add-lambda-vars-and-let-vars-to-closures (clambda)
161 (declare (type clambda clambda
))
162 (let ((did-something nil
))
163 (when (%add-lambda-vars-to-closures clambda
)
164 (setf did-something t
))
165 (dolist (lambda-let (lambda-lets clambda
))
166 ;; There's no need to recurse through full COMPUTE-CLOSURE
167 ;; here, since LETS only go one layer deep.
168 (aver (null (lambda-lets lambda-let
)))
169 (when (%add-lambda-vars-to-closures lambda-let
)
170 (setf did-something t
)))
173 (defun xep-allocator (xep)
174 (let ((entry (functional-entry-fun xep
)))
175 (functional-allocator entry
)))
177 ;;; Make sure that THING is closed over in REF-PHYSENV and in all
178 ;;; PHYSENVs for the functions that reference REF-PHYSENV's function
179 ;;; (not just calls). HOME-PHYSENV is THING's home environment. When we
180 ;;; reach the home environment, we stop propagating the closure.
181 (defun close-over (thing ref-physenv home-physenv
)
182 (declare (type physenv ref-physenv home-physenv
))
183 (let ((flooded-physenvs nil
))
184 (labels ((flood (flooded-physenv)
185 (unless (or (eql flooded-physenv home-physenv
)
186 (member flooded-physenv flooded-physenvs
))
187 (push flooded-physenv flooded-physenvs
)
188 (unless (memq thing
(physenv-closure flooded-physenv
))
189 (push thing
(physenv-closure flooded-physenv
))
190 (let ((lambda (physenv-lambda flooded-physenv
)))
191 (cond ((eq (functional-kind lambda
) :external
)
192 (let* ((alloc-node (xep-allocator lambda
))
193 (alloc-lambda (node-home-lambda alloc-node
))
194 (alloc-physenv (get-lambda-physenv alloc-lambda
)))
195 (flood alloc-physenv
)
196 (dolist (ref (leaf-refs lambda
))
198 (get-node-physenv ref
) alloc-physenv
))))
199 (t (dolist (ref (leaf-refs lambda
))
200 ;; FIXME: This assertion looks
201 ;; reasonable, but does not work for
204 (let ((dest (node-dest ref
)))
205 (aver (basic-combination-p dest
))
206 (aver (eq (basic-combination-kind dest
) :local
)))
207 (flood (get-node-physenv ref
))))))))))
208 (flood ref-physenv
)))
213 #!-sb-fluid
(declaim (inline should-exit-check-tag-p
))
214 (defun exit-should-check-tag-p (exit)
215 (declare (type exit exit
))
216 (not (zerop (policy exit check-tag-existence
))))
218 ;;; Insert the entry stub before the original exit target, and add a
219 ;;; new entry to the PHYSENV-NLX-INFO. The %NLX-ENTRY call in the
220 ;;; stub is passed the NLX-INFO as an argument so that the back end
221 ;;; knows what entry is being done.
223 ;;; The link from the EXIT block to the entry stub is changed to be a
224 ;;; link from the component head. Similarly, the EXIT block is linked
225 ;;; to the component tail. This leaves the entry stub reachable, but
226 ;;; makes the flow graph less confusing to flow analysis.
228 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
229 ;;; last node in the cleanup code to be the enclosing environment, to
230 ;;; represent the fact that the binding was undone as a side effect of
231 ;;; the exit. This will cause a lexical exit to be broken up if we are
232 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
233 ;;; other cleanups that may have to be done on the way.
234 (defun insert-nlx-entry-stub (exit env
)
235 (declare (type physenv env
) (type exit exit
))
236 (let* ((exit-block (node-block exit
))
237 (next-block (first (block-succ exit-block
)))
238 (entry (exit-entry exit
))
239 (cleanup (entry-cleanup entry
))
240 (info (make-nlx-info cleanup exit
))
241 (new-block (insert-cleanup-code exit-block next-block
245 (component (block-component new-block
)))
246 (unlink-blocks exit-block new-block
)
247 (link-blocks exit-block
(component-tail component
))
248 (link-blocks (component-head component
) new-block
)
250 (setf (exit-nlx-info exit
) info
)
251 (setf (nlx-info-target info
) new-block
)
252 (setf (nlx-info-safe-p info
) (exit-should-check-tag-p exit
))
253 (push info
(physenv-nlx-info env
))
254 (push info
(cleanup-nlx-info cleanup
))
255 (when (member (cleanup-kind cleanup
) '(:catch
:unwind-protect
))
256 (setf (node-lexenv (block-last new-block
))
257 (node-lexenv entry
))))
261 ;;; Do stuff necessary to represent a non-local exit from the node
262 ;;; EXIT into ENV. This is called for each non-local exit node, of
263 ;;; which there may be several per exit continuation. This is what we
265 ;;; -- If there isn't any NLX-INFO entry in the environment, make
266 ;;; an entry stub, otherwise just move the exit block link to
267 ;;; the component tail.
268 ;;; -- Close over the NLX-INFO in the exit environment.
269 ;;; -- If the exit is from an :ESCAPE function, then substitute a
270 ;;; constant reference to NLX-INFO structure for the escape
271 ;;; function reference. This will cause the escape function to
272 ;;; be deleted (although not removed from the DFO.) The escape
273 ;;; function is no longer needed, and we don't want to emit code
275 ;;; -- Change the %NLX-ENTRY call to use the NLX lvar so that 1) there
276 ;;; will be a use to represent the NLX use; 2) make life easier for
277 ;;; the stack analysis.
278 (defun note-non-local-exit (env exit
)
279 (declare (type physenv env
) (type exit exit
))
280 (let ((lvar (node-lvar exit
))
281 (exit-fun (node-home-lambda exit
))
282 (info (find-nlx-info exit
)))
284 (let ((block (node-block exit
)))
285 (aver (= (length (block-succ block
)) 1))
286 (unlink-blocks block
(first (block-succ block
)))
287 (link-blocks block
(component-tail (block-component block
)))
288 (setf (exit-nlx-info exit
) info
)
289 (unless (nlx-info-safe-p info
)
290 (setf (nlx-info-safe-p info
)
291 (exit-should-check-tag-p exit
)))))
293 (insert-nlx-entry-stub exit env
)
294 (setq info
(exit-nlx-info exit
))
296 (close-over info
(node-physenv exit
) env
)
297 (when (eq (functional-kind exit-fun
) :escape
)
299 (setf (node-derived-type x
) *wild-type
*))
300 (leaf-refs exit-fun
))
301 (substitute-leaf (find-constant info
) exit-fun
))
303 (let ((node (block-last (nlx-info-target info
))))
304 (unless (node-lvar node
)
305 (aver (eq lvar
(node-lvar exit
)))
306 (setf (node-derived-type node
) (lvar-derived-type lvar
))
307 (add-lvar-use node lvar
)))))
310 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
311 ;;; when we find a block that ends in a non-local EXIT node. We also
312 ;;; ensure that all EXIT nodes are either non-local or degenerate by
313 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
314 ;;; for later phases.
315 (defun find-non-local-exits (component)
316 (declare (type component component
))
317 (dolist (lambda (component-lambdas component
))
318 (dolist (entry (lambda-entries lambda
))
319 (dolist (exit (entry-exits entry
))
320 (let ((target-physenv (node-physenv entry
)))
321 (if (eq (node-physenv exit
) target-physenv
)
322 (maybe-delete-exit exit
)
323 (note-non-local-exit target-physenv exit
))))))
326 ;;;; final decision on stack allocation of dynamic-extent structures
327 (defun recheck-dynamic-extent-lvars (component)
328 (declare (type component component
))
329 (dolist (lambda (component-lambdas component
))
330 (loop for entry in
(lambda-entries lambda
)
331 for cleanup
= (entry-cleanup entry
)
332 do
(when (eq (cleanup-kind cleanup
) :dynamic-extent
)
333 (collect ((real-dx-lvars))
334 (loop for what in
(cleanup-info cleanup
)
337 (if (lvar-good-for-dx-p what t component
)
338 (let ((real (principal-lvar what
)))
339 (setf (lvar-dynamic-extent real
) cleanup
)
340 (real-dx-lvars real
))
341 (setf (lvar-dynamic-extent what
) nil
)))
344 (arg (first (basic-combination-args call
)))
345 (funs (lvar-value arg
))
348 (binding* ((() (leaf-dynamic-extent fun
)
350 (xep (functional-entry-fun fun
)
352 (closure (physenv-closure
353 (get-lambda-physenv xep
))))
357 (setf (leaf-dynamic-extent fun
) nil
)))))
359 (setf (lvar-dynamic-extent arg
) cleanup
)
360 (real-dx-lvars arg
))))))
361 (let ((real-dx-lvars (delete-duplicates (real-dx-lvars))))
362 (setf (cleanup-info cleanup
) real-dx-lvars
)
363 (setf (component-dx-lvars component
)
364 (append real-dx-lvars
(component-dx-lvars component
))))))))
367 ;;;; cleanup emission
369 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
370 ;;; cleanup code as we go. When we are done, convert the cleanup code
371 ;;; in an implicit MV-PROG1. We have to force local call analysis of
372 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
373 ;;; actually have to do anything, then we don't insert any cleanup
374 ;;; code. (FIXME: There's some confusion here, left over from CMU CL
375 ;;; comments. CLEANUP1 isn't mentioned in the code of this function.
376 ;;; It is in code elsewhere, but if the comments for this function
377 ;;; mention it they should explain the relationship to the other code.)
379 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
380 ;;; a "tail" local call.
382 ;;; We don't need to adjust the ending cleanup of the cleanup block,
383 ;;; since the cleanup blocks are inserted at the start of the DFO, and
384 ;;; are thus never scanned.
385 (defun emit-cleanups (block1 block2
)
386 (declare (type cblock block1 block2
))
389 (let ((cleanup2 (block-start-cleanup block2
)))
390 (do ((cleanup (block-end-cleanup block1
)
391 (node-enclosing-cleanup (cleanup-mess-up cleanup
))))
392 ((eq cleanup cleanup2
))
393 (let* ((node (cleanup-mess-up cleanup
))
394 (args (when (basic-combination-p node
)
395 (basic-combination-args node
))))
396 (ecase (cleanup-kind cleanup
)
398 (code `(%special-unbind
',(lvar-value (first args
)))))
400 (code `(%catch-breakup
)))
402 (code `(%unwind-protect-breakup
))
403 (let ((fun (ref-leaf (lvar-uses (second args
)))))
405 (code `(%funcall
,fun
))))
407 (dolist (nlx (cleanup-nlx-info cleanup
))
408 (code `(%lexical-exit-breakup
',nlx
))))
410 (when (not (null (cleanup-info cleanup
)))
411 (code `(%cleanup-point
)))))))
414 (aver (not (node-tail-p (block-last block1
))))
415 (insert-cleanup-code block1 block2
418 (dolist (fun (reanalyze-funs))
419 (locall-analyze-fun-1 fun
)))))
423 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
424 ;;; see a successor in the same environment with a different cleanup.
425 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
426 ;;; the current cleanup, since in that case we are just messing up the
427 ;;; environment, hence this is not the place to clean it.
428 (defun find-cleanup-points (component)
429 (declare (type component component
))
430 (do-blocks (block1 component
)
431 (let ((env1 (block-physenv block1
))
432 (cleanup1 (block-end-cleanup block1
)))
433 (dolist (block2 (block-succ block1
))
434 (when (block-start block2
)
435 (let ((env2 (block-physenv block2
))
436 (cleanup2 (block-start-cleanup block2
)))
437 (unless (or (not (eq env2 env1
))
438 (eq cleanup1 cleanup2
)
440 (eq (node-enclosing-cleanup
441 (cleanup-mess-up cleanup2
))
443 (emit-cleanups block1 block2
)))))))
446 ;;; Mark optimizable tail-recursive uses of function result
447 ;;; continuations with the corresponding TAIL-SET.
448 (defun tail-annotate (component)
449 (declare (type component component
))
450 (dolist (fun (component-lambdas component
))
451 (let ((ret (lambda-return fun
)))
452 ;; Nodes whose type is NIL (i.e. don't return) such as calls to
453 ;; ERROR are never annotated as TAIL-P, in order to preserve
454 ;; debugging information.
456 ;; FIXME: It might be better to add another DEFKNOWN property
457 ;; (e.g. NO-TAIL-RECURSION) and use it for error-handling
458 ;; functions like ERROR, instead of spreading this special case
459 ;; net so widely. --WHN?
461 ;; Why is that bad? Because this non-elimination of
462 ;; non-returning tail calls causes the XEP for FOO appear in
463 ;; backtrace for (defun foo (x) (error "foo ~S" x)) wich seems
464 ;; less then optimal. --NS 2005-02-28
466 (let ((result (return-result ret
)))
467 (do-uses (use result
)
468 (when (and (policy use merge-tail-calls
)
469 (basic-combination-p use
)
470 (immediately-used-p result use
)
471 (or (not (eq (node-derived-type use
) *empty-type
*))
472 (eq (basic-combination-kind use
) :local
)))
473 (setf (node-tail-p use
) t
)))))))