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)
44 (analyze-indirect-lambda-vars component)
46 (dolist (fun (component-lambdas component))
47 (when (null (leaf-refs fun))
48 (let ((kind (functional-kind fun)))
49 (unless (or (eq kind :toplevel)
50 (functional-has-external-references-p fun))
51 (aver (member kind '(:optional :cleanup :escape)))
52 (setf (functional-kind fun) nil)
53 (delete-functional fun)))))
55 (setf (component-nlx-info-generated-p component) t)
58 ;;; This is to be called on a COMPONENT with top level LAMBDAs before
59 ;;; the compilation of the associated non-top-level code to detect
60 ;;; closed over top level variables. We just do COMPUTE-CLOSURE on all
61 ;;; the lambdas. This will pre-allocate environments for all the
62 ;;; functions with closed-over top level variables. The post-pass will
63 ;;; use the existing structure, rather than allocating a new one. We
64 ;;; return true if we discover any possible closure vars.
65 (defun pre-physenv-analyze-toplevel (component)
66 (declare (type component component))
68 (dolist (lambda (component-lambdas component))
69 (when (add-lambda-vars-and-let-vars-to-closures lambda)
73 ;;; If CLAMBDA has a PHYSENV, return it, otherwise assign an empty one
75 (defun get-lambda-physenv (clambda)
76 (declare (type clambda clambda))
77 (let ((homefun (lambda-home clambda)))
78 (or (lambda-physenv homefun)
79 (let ((res (make-physenv :lambda homefun)))
80 (setf (lambda-physenv homefun) res)
81 ;; All the LETLAMBDAs belong to HOMEFUN, and share the same
82 ;; PHYSENV. Thus, (1) since HOMEFUN's PHYSENV was NIL,
83 ;; theirs should be NIL too, and (2) since we're modifying
84 ;; HOMEFUN's PHYSENV, we should modify theirs, too.
85 (dolist (letlambda (lambda-lets homefun))
86 (aver (eql (lambda-home letlambda) homefun))
87 (aver (null (lambda-physenv letlambda)))
88 (setf (lambda-physenv letlambda) res))
91 ;;; If FUN has no physical environment, assign one, otherwise clean up
92 ;;; the old physical environment and the INDIRECT flag on LAMBDA-VARs.
93 ;;; This is necessary because pre-analysis is done before
95 (defun reinit-lambda-physenv (fun)
96 (let ((old (lambda-physenv (lambda-home fun))))
98 (setf (physenv-closure old) nil)
100 (dolist (var (lambda-vars fun))
101 (setf (lambda-var-indirect var) nil))))
103 (map nil #'clear (lambda-lets fun))))
105 (get-lambda-physenv fun))))
108 ;;; Get NODE's environment, assigning one if necessary.
109 (defun get-node-physenv (node)
110 (declare (type node node))
111 (get-lambda-physenv (node-home-lambda node)))
113 ;;; private guts of ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES
115 ;;; This is the old CMU CL COMPUTE-CLOSURE, which only works on
116 ;;; LAMBDA-VARS directly, not on the LAMBDA-VARS of LAMBDA-LETS. It
117 ;;; seems never to be valid to use this operation alone, so in SBCL,
118 ;;; it's private, and the public interface,
119 ;;; ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES, always runs over all the
120 ;;; variables, not only the LAMBDA-VARS of CLAMBDA itself but also
121 ;;; the LAMBDA-VARS of CLAMBDA's LAMBDA-LETS.
122 (defun %add-lambda-vars-to-closures (clambda)
123 (let ((physenv (get-lambda-physenv clambda))
125 (note-unreferenced-vars clambda)
126 (dolist (var (lambda-vars clambda))
127 (dolist (ref (leaf-refs var))
128 (let ((ref-physenv (get-node-physenv ref)))
129 (unless (eq ref-physenv physenv)
130 (when (lambda-var-sets var)
131 (setf (lambda-var-indirect var) t))
132 (setq did-something t)
133 (close-over var ref-physenv physenv))))
134 (dolist (set (basic-var-sets var))
136 ;; Variables which are set but never referenced can be
137 ;; optimized away, and closing over them here would just
138 ;; interfere with that. (In bug 147, it *did* interfere with
139 ;; that, causing confusion later. This UNLESS solves that
140 ;; problem, but I (WHN) am not 100% sure it's best to solve
141 ;; the problem this way instead of somehow solving it
142 ;; somewhere upstream and just doing (AVER (LEAF-REFS VAR))
144 (unless (null (leaf-refs var))
146 (let ((set-physenv (get-node-physenv set)))
147 (unless (eq set-physenv physenv)
148 (setf did-something t
149 (lambda-var-indirect var) t)
150 (close-over var set-physenv physenv))))))
153 ;;; Find any variables in CLAMBDA -- either directly in LAMBDA-VARS or
154 ;;; in the LAMBDA-VARS of elements of LAMBDA-LETS -- with references
155 ;;; outside of the home environment and close over them. If a
156 ;;; closed-over variable is set, then we set the INDIRECT flag so that
157 ;;; we will know the closed over value is really a pointer to the
158 ;;; value cell. We also warn about unreferenced variables here, just
159 ;;; because it's a convenient place to do it. We return true if we
160 ;;; close over anything.
161 (defun add-lambda-vars-and-let-vars-to-closures (clambda)
162 (declare (type clambda clambda))
163 (let ((did-something nil))
164 (when (%add-lambda-vars-to-closures clambda)
165 (setf did-something t))
166 (dolist (lambda-let (lambda-lets clambda))
167 ;; There's no need to recurse through full COMPUTE-CLOSURE
168 ;; here, since LETS only go one layer deep.
169 (aver (null (lambda-lets lambda-let)))
170 (when (%add-lambda-vars-to-closures lambda-let)
171 (setf did-something t)))
174 (defun xep-allocator (xep)
175 (let ((entry (functional-entry-fun xep)))
176 (functional-allocator entry)))
178 ;;; Make sure that THING is closed over in REF-PHYSENV and in all
179 ;;; PHYSENVs for the functions that reference REF-PHYSENV's function
180 ;;; (not just calls). HOME-PHYSENV is THING's home environment. When we
181 ;;; reach the home environment, we stop propagating the closure.
182 (defun close-over (thing ref-physenv home-physenv)
183 (declare (type physenv ref-physenv home-physenv))
184 (let ((flooded-physenvs nil))
185 (labels ((flood (flooded-physenv)
186 (unless (or (eql flooded-physenv home-physenv)
187 (member flooded-physenv flooded-physenvs))
188 (push flooded-physenv flooded-physenvs)
189 (unless (memq thing (physenv-closure flooded-physenv))
190 (push thing (physenv-closure flooded-physenv))
191 (let ((lambda (physenv-lambda flooded-physenv)))
192 (cond ((eq (functional-kind lambda) :external)
193 (let* ((alloc-node (xep-allocator lambda))
194 (alloc-lambda (node-home-lambda alloc-node))
195 (alloc-physenv (get-lambda-physenv alloc-lambda)))
196 (flood alloc-physenv)
197 (dolist (ref (leaf-refs lambda))
199 (get-node-physenv ref) alloc-physenv))))
200 (t (dolist (ref (leaf-refs lambda))
201 ;; FIXME: This assertion looks
202 ;; reasonable, but does not work for
205 (let ((dest (node-dest ref)))
206 (aver (basic-combination-p dest))
207 (aver (eq (basic-combination-kind dest) :local)))
208 (flood (get-node-physenv ref))))))))))
209 (flood ref-physenv)))
212 ;;; Find LAMBDA-VARs that are marked as needing to support indirect
213 ;;; access (SET at some point after initial creation) that are present
214 ;;; in CLAMBDAs not marked as being DYNAMIC-EXTENT (meaning that the
215 ;;; value-cell involved must be able to survive past the extent of the
216 ;;; allocating frame), and mark them (the LAMBDA-VARs) as needing
217 ;;; explicit value-cells. Because they are already closed-over, the
218 ;;; LAMBDA-VARs already appear in the closures of all of the CLAMBDAs
219 ;;; that need checking.
220 (defun analyze-indirect-lambda-vars (component)
221 (dolist (fun (component-lambdas component))
222 (unless (leaf-dynamic-extent fun)
223 (let ((closure (physenv-closure (lambda-physenv fun))))
224 (dolist (var closure)
225 (when (and (lambda-var-p var)
226 (lambda-var-indirect var))
227 (setf (lambda-var-explicit-value-cell var) t)))))))
231 #!-sb-fluid (declaim (inline should-exit-check-tag-p))
232 (defun exit-should-check-tag-p (exit)
233 (declare (type exit exit))
234 (not (zerop (policy exit check-tag-existence))))
236 ;;; Insert the entry stub before the original exit target, and add a
237 ;;; new entry to the PHYSENV-NLX-INFO. The %NLX-ENTRY call in the
238 ;;; stub is passed the NLX-INFO as an argument so that the back end
239 ;;; knows what entry is being done.
241 ;;; The link from the EXIT block to the entry stub is changed to be a
242 ;;; link from the component head. Similarly, the EXIT block is linked
243 ;;; to the component tail. This leaves the entry stub reachable, but
244 ;;; makes the flow graph less confusing to flow analysis.
246 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
247 ;;; last node in the cleanup code to be the enclosing environment, to
248 ;;; represent the fact that the binding was undone as a side effect of
249 ;;; the exit. This will cause a lexical exit to be broken up if we are
250 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
251 ;;; other cleanups that may have to be done on the way.
252 (defun insert-nlx-entry-stub (exit env)
253 (declare (type physenv env) (type exit exit))
254 (let* ((exit-block (node-block exit))
255 (next-block (first (block-succ exit-block)))
256 (entry (exit-entry exit))
257 (cleanup (entry-cleanup entry))
258 (info (make-nlx-info cleanup exit))
259 (new-block (insert-cleanup-code exit-block next-block
263 (component (block-component new-block)))
264 (unlink-blocks exit-block new-block)
265 (link-blocks exit-block (component-tail component))
266 (link-blocks (component-head component) new-block)
268 (setf (exit-nlx-info exit) info)
269 (setf (nlx-info-target info) new-block)
270 (setf (nlx-info-safe-p info) (exit-should-check-tag-p exit))
271 (push info (physenv-nlx-info env))
272 (push info (cleanup-info cleanup))
273 (when (member (cleanup-kind cleanup) '(:catch :unwind-protect))
274 (setf (node-lexenv (block-last new-block))
275 (node-lexenv entry))))
279 ;;; Do stuff necessary to represent a non-local exit from the node
280 ;;; EXIT into ENV. This is called for each non-local exit node, of
281 ;;; which there may be several per exit continuation. This is what we
283 ;;; -- If there isn't any NLX-INFO entry in the environment, make
284 ;;; an entry stub, otherwise just move the exit block link to
285 ;;; the component tail.
286 ;;; -- Close over the NLX-INFO in the exit environment.
287 ;;; -- If the exit is from an :ESCAPE function, then substitute a
288 ;;; constant reference to NLX-INFO structure for the escape
289 ;;; function reference. This will cause the escape function to
290 ;;; be deleted (although not removed from the DFO.) The escape
291 ;;; function is no longer needed, and we don't want to emit code
293 ;;; -- Change the %NLX-ENTRY call to use the NLX lvar so that 1) there
294 ;;; will be a use to represent the NLX use; 2) make life easier for
295 ;;; the stack analysis.
296 (defun note-non-local-exit (env exit)
297 (declare (type physenv env) (type exit exit))
298 (let ((lvar (node-lvar exit))
299 (exit-fun (node-home-lambda exit))
300 (info (find-nlx-info exit)))
302 (let ((block (node-block exit)))
303 (aver (= (length (block-succ block)) 1))
304 (unlink-blocks block (first (block-succ block)))
305 (link-blocks block (component-tail (block-component block)))
306 (setf (exit-nlx-info exit) info)
307 (unless (nlx-info-safe-p info)
308 (setf (nlx-info-safe-p info)
309 (exit-should-check-tag-p exit)))))
311 (insert-nlx-entry-stub exit env)
312 (setq info (exit-nlx-info exit))
314 (close-over info (node-physenv exit) env)
315 (when (eq (functional-kind exit-fun) :escape)
317 (setf (node-derived-type x) *wild-type*))
318 (leaf-refs exit-fun))
319 (substitute-leaf (find-constant info) exit-fun))
321 (let ((node (block-last (nlx-info-target info))))
322 (unless (node-lvar node)
323 (aver (eq lvar (node-lvar exit)))
324 (setf (node-derived-type node) (lvar-derived-type lvar))
325 (add-lvar-use node lvar)))))
328 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
329 ;;; when we find a block that ends in a non-local EXIT node. We also
330 ;;; ensure that all EXIT nodes are either non-local or degenerate by
331 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
332 ;;; for later phases.
333 (defun find-non-local-exits (component)
334 (declare (type component component))
335 (dolist (lambda (component-lambdas component))
336 (dolist (entry (lambda-entries lambda))
337 (dolist (exit (entry-exits entry))
338 (let ((target-physenv (node-physenv entry)))
339 (if (eq (node-physenv exit) target-physenv)
340 (maybe-delete-exit exit)
341 (note-non-local-exit target-physenv exit))))))
344 ;;;; final decision on stack allocation of dynamic-extent structures
345 (defun recheck-dynamic-extent-lvars (component)
346 (declare (type component component))
347 (dolist (lambda (component-lambdas component))
348 (loop for entry in (lambda-entries lambda)
349 for cleanup = (entry-cleanup entry)
350 do (when (eq (cleanup-kind cleanup) :dynamic-extent)
351 (collect ((real-dx-lvars))
352 (loop for what in (cleanup-info cleanup)
355 (let ((dx (car what))
357 (cond ((lvar-good-for-dx-p lvar dx component)
358 ;; Since the above check does deep
359 ;; checks. we need to deal with the deep
360 ;; results in here as well.
361 (dolist (cell (handle-nested-dynamic-extent-lvars
363 (let ((real (principal-lvar (cdr cell))))
364 (setf (lvar-dynamic-extent real) cleanup)
365 (real-dx-lvars real))))
367 (note-no-stack-allocation lvar)
368 (setf (lvar-dynamic-extent lvar) nil)))))
371 (arg (first (basic-combination-args call)))
372 (funs (lvar-value arg))
375 (binding* ((() (leaf-dynamic-extent fun)
377 (xep (functional-entry-fun fun)
379 (closure (physenv-closure
380 (get-lambda-physenv xep))))
384 (setf (leaf-dynamic-extent fun) nil)))))
386 (setf (lvar-dynamic-extent arg) cleanup)
387 (real-dx-lvars arg))))))
388 (let ((real-dx-lvars (delete-duplicates (real-dx-lvars))))
389 (setf (cleanup-info cleanup) real-dx-lvars)
390 (setf (component-dx-lvars component)
391 (append real-dx-lvars (component-dx-lvars component))))))))
394 ;;;; cleanup emission
396 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
397 ;;; cleanup code as we go. When we are done, convert the cleanup code
398 ;;; in an implicit MV-PROG1. We have to force local call analysis of
399 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
400 ;;; actually have to do anything, then we don't insert any cleanup
401 ;;; code. (FIXME: There's some confusion here, left over from CMU CL
402 ;;; comments. CLEANUP1 isn't mentioned in the code of this function.
403 ;;; It is in code elsewhere, but if the comments for this function
404 ;;; mention it they should explain the relationship to the other code.)
406 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
407 ;;; a "tail" local call.
409 ;;; We don't need to adjust the ending cleanup of the cleanup block,
410 ;;; since the cleanup blocks are inserted at the start of the DFO, and
411 ;;; are thus never scanned.
412 (defun emit-cleanups (block1 block2)
413 (declare (type cblock block1 block2))
416 (let ((cleanup2 (block-start-cleanup block2)))
417 (do ((cleanup (block-end-cleanup block1)
418 (node-enclosing-cleanup (cleanup-mess-up cleanup))))
419 ((eq cleanup cleanup2))
420 (let* ((node (cleanup-mess-up cleanup))
421 (args (when (basic-combination-p node)
422 (basic-combination-args node))))
423 (ecase (cleanup-kind cleanup)
425 (code `(%special-unbind ',(lvar-value (first args)))))
427 (code `(%catch-breakup)))
429 (code `(%unwind-protect-breakup))
430 (let ((fun (ref-leaf (lvar-uses (second args)))))
432 (code `(%funcall ,fun))))
434 (dolist (nlx (cleanup-info cleanup))
435 (code `(%lexical-exit-breakup ',nlx))))
437 (when (not (null (cleanup-info cleanup)))
438 (code `(%cleanup-point)))))))
441 (aver (not (node-tail-p (block-last block1))))
442 (insert-cleanup-code block1 block2
445 (dolist (fun (reanalyze-funs))
446 (locall-analyze-fun-1 fun)))))
450 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
451 ;;; see a successor in the same environment with a different cleanup.
452 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
453 ;;; the current cleanup, since in that case we are just messing up the
454 ;;; environment, hence this is not the place to clean it.
455 (defun find-cleanup-points (component)
456 (declare (type component component))
457 (do-blocks (block1 component)
458 (let ((env1 (block-physenv block1))
459 (cleanup1 (block-end-cleanup block1)))
460 (dolist (block2 (block-succ block1))
461 (when (block-start block2)
462 (let ((env2 (block-physenv block2))
463 (cleanup2 (block-start-cleanup block2)))
464 (unless (or (not (eq env2 env1))
465 (eq cleanup1 cleanup2)
467 (eq (node-enclosing-cleanup
468 (cleanup-mess-up cleanup2))
470 (emit-cleanups block1 block2)))))))
473 ;;; Mark optimizable tail-recursive uses of function result
474 ;;; continuations with the corresponding TAIL-SET.
475 (defun tail-annotate (component)
476 (declare (type component component))
477 (dolist (fun (component-lambdas component))
478 (let ((ret (lambda-return fun)))
479 ;; Nodes whose type is NIL (i.e. don't return) such as calls to
480 ;; ERROR are never annotated as TAIL-P, in order to preserve
481 ;; debugging information.
483 ;; FIXME: It might be better to add another DEFKNOWN property
484 ;; (e.g. NO-TAIL-RECURSION) and use it for error-handling
485 ;; functions like ERROR, instead of spreading this special case
486 ;; net so widely. --WHN?
488 ;; Why is that bad? Because this non-elimination of
489 ;; non-returning tail calls causes the XEP for FOO appear in
490 ;; backtrace for (defun foo (x) (error "foo ~S" x)) wich seems
491 ;; less then optimal. --NS 2005-02-28
493 (let ((result (return-result ret)))
494 (do-uses (use result)
495 (when (and (policy use merge-tail-calls)
496 (basic-combination-p use)
497 (immediately-used-p result use)
498 (or (not (eq (node-derived-type use) *empty-type*))
499 (eq (basic-combination-kind use) :local)))
500 (setf (node-tail-p use) t)))))))