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 (find-cleanup-points component)
42 (tail-annotate component)
44 (dolist (fun (component-lambdas component))
45 (when (null (leaf-refs fun))
46 (let ((kind (functional-kind fun)))
47 (unless (or (eq kind :toplevel)
48 (functional-has-external-references-p fun))
49 (aver (member kind '(:optional :cleanup :escape)))
50 (setf (functional-kind fun) nil)
51 (delete-functional fun)))))
53 (setf (component-nlx-info-generated-p component) t)
56 ;;; This is to be called on a COMPONENT with top level LAMBDAs before
57 ;;; the compilation of the associated non-top-level code to detect
58 ;;; closed over top level variables. We just do COMPUTE-CLOSURE on all
59 ;;; the lambdas. This will pre-allocate environments for all the
60 ;;; functions with closed-over top level variables. The post-pass will
61 ;;; use the existing structure, rather than allocating a new one. We
62 ;;; return true if we discover any possible closure vars.
63 (defun pre-physenv-analyze-toplevel (component)
64 (declare (type component component))
66 (dolist (lambda (component-lambdas component))
67 (when (add-lambda-vars-and-let-vars-to-closures lambda)
71 ;;; This is like old CMU CL PRE-ENVIRONMENT-ANALYZE-TOPLEVEL, except
72 ;;; (1) It's been brought into the post-0.7.0 world where the property
73 ;;; HAS-EXTERNAL-REFERENCES-P is orthogonal to the property of
74 ;;; being specialized/optimized for locall at top level.
75 ;;; (2) There's no return value, since we don't care whether we
76 ;;; find any possible closure variables.
78 ;;; I wish I could find an explanation of why
79 ;;; PRE-ENVIRONMENT-ANALYZE-TOPLEVEL is important. The old CMU CL
81 ;;; Called on component with top level lambdas before the
82 ;;; compilation of the associated non-top-level code to detect
83 ;;; closed over top level variables. We just do COMPUTE-CLOSURE on
84 ;;; all the lambdas. This will pre-allocate environments for all
85 ;;; the functions with closed-over top level variables. The
86 ;;; post-pass will use the existing structure, rather than
87 ;;; allocating a new one. We return true if we discover any
88 ;;; possible closure vars.
89 ;;; But that doesn't seem to explain either why it's important to do
90 ;;; this for top level lambdas, or why it's important to do it only
91 ;;; for top level lambdas instead of just doing it indiscriminately
92 ;;; for all lambdas. I do observe that when it's not done, compiler
93 ;;; assertions occasionally fail. My tentative hypothesis for why it's
94 ;;; important to do it is that other environment analysis expects to
95 ;;; bottom out on the outermost enclosing thing, and (insert
96 ;;; mysterious reason here) it's important to set up bottomed-out-here
97 ;;; environments before anything else. I haven't been able to guess
98 ;;; why it's important to do it selectively instead of
99 ;;; indiscriminately. -- WHN 2001-11-10
100 (defun preallocate-physenvs-for-toplevelish-lambdas (component)
101 (dolist (clambda (component-lambdas component))
102 (when (lambda-toplevelish-p clambda)
103 (add-lambda-vars-and-let-vars-to-closures clambda)))
106 ;;; If CLAMBDA has a PHYSENV, return it, otherwise assign an empty one
108 (defun get-lambda-physenv (clambda)
109 (declare (type clambda clambda))
110 (let ((homefun (lambda-home clambda)))
111 (or (lambda-physenv homefun)
112 (let ((res (make-physenv :lambda homefun)))
113 (setf (lambda-physenv homefun) res)
114 ;; All the LETLAMBDAs belong to HOMEFUN, and share the same
115 ;; PHYSENV. Thus, (1) since HOMEFUN's PHYSENV was NIL,
116 ;; theirs should be NIL too, and (2) since we're modifying
117 ;; HOMEFUN's PHYSENV, we should modify theirs, too.
118 (dolist (letlambda (lambda-lets homefun))
119 (aver (eql (lambda-home letlambda) homefun))
120 (aver (null (lambda-physenv letlambda)))
121 (setf (lambda-physenv letlambda) res))
124 ;;; If FUN has no physical environment, assign one, otherwise clean up
125 ;;; the old physical environment, removing/flagging variables that
126 ;;; have no sets or refs. If a var has no references, we remove it
127 ;;; from the closure. We always clear the INDIRECT flag. This is
128 ;;; necessary because pre-analysis is done before optimization.
129 (defun reinit-lambda-physenv (fun)
130 (let ((old (lambda-physenv (lambda-home fun))))
132 (setf (physenv-closure old)
133 (delete-if (lambda (x)
134 (and (lambda-var-p x)
135 (null (leaf-refs x))))
136 (physenv-closure old)))
138 (dolist (var (lambda-vars fun))
139 (setf (lambda-var-indirect var) nil))))
141 (map nil #'clear (lambda-lets fun))))
143 (get-lambda-physenv fun))))
146 ;;; Get NODE's environment, assigning one if necessary.
147 (defun get-node-physenv (node)
148 (declare (type node node))
149 (get-lambda-physenv (node-home-lambda node)))
151 ;;; private guts of ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES
153 ;;; This is the old CMU CL COMPUTE-CLOSURE, which only works on
154 ;;; LAMBDA-VARS directly, not on the LAMBDA-VARS of LAMBDA-LETS. It
155 ;;; seems never to be valid to use this operation alone, so in SBCL,
156 ;;; it's private, and the public interface,
157 ;;; ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES, always runs over all the
158 ;;; variables, not only the LAMBDA-VARS of CLAMBDA itself but also
159 ;;; the LAMBDA-VARS of CLAMBDA's LAMBDA-LETS.
160 (defun %add-lambda-vars-to-closures (clambda)
161 (let ((physenv (get-lambda-physenv clambda))
163 (note-unreferenced-vars clambda)
164 (dolist (var (lambda-vars clambda))
165 (dolist (ref (leaf-refs var))
166 (let ((ref-physenv (get-node-physenv ref)))
167 (unless (eq ref-physenv physenv)
168 (when (lambda-var-sets var)
169 (setf (lambda-var-indirect var) t))
170 (setq did-something t)
171 (close-over var ref-physenv physenv))))
172 (dolist (set (basic-var-sets var))
174 ;; Variables which are set but never referenced can be
175 ;; optimized away, and closing over them here would just
176 ;; interfere with that. (In bug 147, it *did* interfere with
177 ;; that, causing confusion later. This UNLESS solves that
178 ;; problem, but I (WHN) am not 100% sure it's best to solve
179 ;; the problem this way instead of somehow solving it
180 ;; somewhere upstream and just doing (AVER (LEAF-REFS VAR))
182 (unless (null (leaf-refs var))
184 (let ((set-physenv (get-node-physenv set)))
185 (unless (eq set-physenv physenv)
186 (setf did-something t
187 (lambda-var-indirect var) t)
188 (close-over var set-physenv physenv))))))
191 ;;; Find any variables in CLAMBDA -- either directly in LAMBDA-VARS or
192 ;;; in the LAMBDA-VARS of elements of LAMBDA-LETS -- with references
193 ;;; outside of the home environment and close over them. If a
194 ;;; closed-over variable is set, then we set the INDIRECT flag so that
195 ;;; we will know the closed over value is really a pointer to the
196 ;;; value cell. We also warn about unreferenced variables here, just
197 ;;; because it's a convenient place to do it. We return true if we
198 ;;; close over anything.
199 (defun add-lambda-vars-and-let-vars-to-closures (clambda)
200 (declare (type clambda clambda))
201 (let ((did-something nil))
202 (when (%add-lambda-vars-to-closures clambda)
203 (setf did-something t))
204 (dolist (lambda-let (lambda-lets clambda))
205 ;; There's no need to recurse through full COMPUTE-CLOSURE
206 ;; here, since LETS only go one layer deep.
207 (aver (null (lambda-lets lambda-let)))
208 (when (%add-lambda-vars-to-closures lambda-let)
209 (setf did-something t)))
212 ;;; Make sure that THING is closed over in REF-PHYSENV and in all
213 ;;; PHYSENVs for the functions that reference REF-PHYSENV's function
214 ;;; (not just calls). HOME-PHYSENV is THING's home environment. When we
215 ;;; reach the home environment, we stop propagating the closure.
216 (defun close-over (thing ref-physenv home-physenv)
217 (declare (type physenv ref-physenv home-physenv))
218 (let ((flooded-physenvs nil))
219 (named-let flood ((flooded-physenv ref-physenv))
220 (unless (or (eql flooded-physenv home-physenv)
221 (member flooded-physenv flooded-physenvs))
222 (push flooded-physenv flooded-physenvs)
223 (pushnew thing (physenv-closure flooded-physenv))
224 (dolist (ref (leaf-refs (physenv-lambda flooded-physenv)))
225 (flood (get-node-physenv ref))))))
230 ;;; Insert the entry stub before the original exit target, and add a
231 ;;; new entry to the PHYSENV-NLX-INFO. The %NLX-ENTRY call in the
232 ;;; stub is passed the NLX-INFO as an argument so that the back end
233 ;;; knows what entry is being done.
235 ;;; The link from the EXIT block to the entry stub is changed to be a
236 ;;; link from the component head. Similarly, the EXIT block is linked
237 ;;; to the component tail. This leaves the entry stub reachable, but
238 ;;; makes the flow graph less confusing to flow analysis.
240 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
241 ;;; last node in the cleanup code to be the enclosing environment, to
242 ;;; represent the fact that the binding was undone as a side effect of
243 ;;; the exit. This will cause a lexical exit to be broken up if we are
244 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
245 ;;; other cleanups that may have to be done on the way.
246 (defun insert-nlx-entry-stub (exit env)
247 (declare (type physenv env) (type exit exit))
248 (let* ((exit-block (node-block exit))
249 (next-block (first (block-succ exit-block)))
250 (entry (exit-entry exit))
251 (cleanup (entry-cleanup entry))
252 (info (make-nlx-info cleanup exit))
253 (new-block (insert-cleanup-code exit-block next-block
257 (component (block-component new-block)))
258 (unlink-blocks exit-block new-block)
259 (link-blocks exit-block (component-tail component))
260 (link-blocks (component-head component) new-block)
262 (setf (nlx-info-target info) new-block)
263 (push info (physenv-nlx-info env))
264 (push info (cleanup-nlx-info cleanup))
265 (when (member (cleanup-kind cleanup) '(:catch :unwind-protect))
266 (setf (node-lexenv (block-last new-block))
267 (node-lexenv entry))))
271 ;;; Do stuff necessary to represent a non-local exit from the node
272 ;;; EXIT into ENV. This is called for each non-local exit node, of
273 ;;; which there may be several per exit continuation. This is what we
275 ;;; -- If there isn't any NLX-INFO entry in the environment, make
276 ;;; an entry stub, otherwise just move the exit block link to
277 ;;; the component tail.
278 ;;; -- Close over the NLX-INFO in the exit environment.
279 ;;; -- If the exit is from an :ESCAPE function, then substitute a
280 ;;; constant reference to NLX-INFO structure for the escape
281 ;;; function reference. This will cause the escape function to
282 ;;; be deleted (although not removed from the DFO.) The escape
283 ;;; function is no longer needed, and we don't want to emit code
285 ;;; -- Change the %NLX-ENTRY call to use the NLX lvar so that 1) there
286 ;;; will be a use to represent the NLX use; 2) make life easier for
287 ;;; the stack analysis.
288 (defun note-non-local-exit (env exit)
289 (declare (type physenv env) (type exit exit))
290 (let ((lvar (node-lvar exit))
291 (exit-fun (node-home-lambda exit)))
292 (if (find-nlx-info exit)
293 (let ((block (node-block exit)))
294 (aver (= (length (block-succ block)) 1))
295 (unlink-blocks block (first (block-succ block)))
296 (link-blocks block (component-tail (block-component block))))
297 (insert-nlx-entry-stub exit env))
298 (let ((info (find-nlx-info exit)))
300 (close-over info (node-physenv exit) env)
301 (when (eq (functional-kind exit-fun) :escape)
303 (setf (node-derived-type x) *wild-type*))
304 (leaf-refs exit-fun))
305 (substitute-leaf (find-constant info) exit-fun))
307 (let ((node (block-last (nlx-info-target info))))
308 (unless (node-lvar node)
309 (aver (eq lvar (node-lvar exit)))
310 (setf (node-derived-type node) (lvar-derived-type lvar))
311 (add-lvar-use node lvar))))))
314 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
315 ;;; when we find a block that ends in a non-local EXIT node. We also
316 ;;; ensure that all EXIT nodes are either non-local or degenerate by
317 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
318 ;;; for later phases.
319 (defun find-non-local-exits (component)
320 (declare (type component component))
321 (dolist (lambda (component-lambdas component))
322 (dolist (entry (lambda-entries lambda))
323 (dolist (exit (entry-exits entry))
324 (let ((target-physenv (node-physenv entry)))
325 (if (eq (node-physenv exit) target-physenv)
326 (maybe-delete-exit exit)
327 (note-non-local-exit target-physenv exit))))))
330 ;;;; cleanup emission
332 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
333 ;;; cleanup code as we go. When we are done, convert the cleanup code
334 ;;; in an implicit MV-PROG1. We have to force local call analysis of
335 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
336 ;;; actually have to do anything, then we don't insert any cleanup
337 ;;; code. (FIXME: There's some confusion here, left over from CMU CL
338 ;;; comments. CLEANUP1 isn't mentioned in the code of this function.
339 ;;; It is in code elsewhere, but if the comments for this function
340 ;;; mention it they should explain the relationship to the other code.)
342 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
343 ;;; a "tail" local call.
345 ;;; We don't need to adjust the ending cleanup of the cleanup block,
346 ;;; since the cleanup blocks are inserted at the start of the DFO, and
347 ;;; are thus never scanned.
348 (defun emit-cleanups (block1 block2)
349 (declare (type cblock block1 block2))
352 (let ((cleanup2 (block-start-cleanup block2)))
353 (do ((cleanup (block-end-cleanup block1)
354 (node-enclosing-cleanup (cleanup-mess-up cleanup))))
355 ((eq cleanup cleanup2))
356 (let* ((node (cleanup-mess-up cleanup))
357 (args (when (basic-combination-p node)
358 (basic-combination-args node))))
359 (ecase (cleanup-kind cleanup)
361 (code `(%special-unbind ',(lvar-value (first args)))))
363 (code `(%catch-breakup)))
365 (code `(%unwind-protect-breakup))
366 (let ((fun (ref-leaf (lvar-uses (second args)))))
368 (code `(%funcall ,fun))))
370 (dolist (nlx (cleanup-nlx-info cleanup))
371 (code `(%lexical-exit-breakup ',nlx))))
373 (code `(%dynamic-extent-end))))))
376 (aver (not (node-tail-p (block-last block1))))
377 (insert-cleanup-code block1 block2
380 (dolist (fun (reanalyze-funs))
381 (locall-analyze-fun-1 fun)))))
385 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
386 ;;; see a successor in the same environment with a different cleanup.
387 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
388 ;;; the current cleanup, since in that case we are just messing up the
389 ;;; environment, hence this is not the place to clean it.
390 (defun find-cleanup-points (component)
391 (declare (type component component))
392 (do-blocks (block1 component)
393 (let ((env1 (block-physenv block1))
394 (cleanup1 (block-end-cleanup block1)))
395 (dolist (block2 (block-succ block1))
396 (when (block-start block2)
397 (let ((env2 (block-physenv block2))
398 (cleanup2 (block-start-cleanup block2)))
399 (unless (or (not (eq env2 env1))
400 (eq cleanup1 cleanup2)
402 (eq (node-enclosing-cleanup
403 (cleanup-mess-up cleanup2))
405 (emit-cleanups block1 block2)))))))
408 ;;; Mark optimizable tail-recursive uses of function result
409 ;;; continuations with the corresponding TAIL-SET.
410 (defun tail-annotate (component)
411 (declare (type component component))
412 (dolist (fun (component-lambdas component))
413 (let ((ret (lambda-return fun)))
414 ;; Nodes whose type is NIL (i.e. don't return) such as calls to
415 ;; ERROR are never annotated as TAIL-P, in order to preserve
416 ;; debugging information.
418 ;; FIXME: It might be better to add another DEFKNOWN property
419 ;; (e.g. NO-TAIL-RECURSION) and use it for error-handling
420 ;; functions like ERROR, instead of spreading this special case
423 (let ((result (return-result ret)))
424 (do-uses (use result)
425 (when (and (policy use merge-tail-calls)
426 (basic-combination-p use)
427 (immediately-used-p result use)
428 (or (not (eq (node-derived-type use) *empty-type*))
429 (eq (basic-combination-kind use) :local)))
430 (setf (node-tail-p use) t)))))))