1 ;;;; This file implements the environment analysis phase for the
2 ;;;; compiler. This phase annotates IR1 with a hierarchy environment
3 ;;;; structures, determining the environment that each LAMBDA
4 ;;;; allocates its variables and finding what values are closed over
5 ;;;; by each 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 an ENVIRONMENT structure for each non-LET LAMBDA, assigning
21 ;;; the LAMBDA-ENVIRONMENT for all LAMBDAs.
22 ;;; 2. Find all values that need to be closed over by each environment.
23 ;;; 3. Scan the blocks in the component closing over non-local-exit
25 ;;; 4. Delete all non-top-level functions with no references. This
26 ;;; should only get functions with non-NULL kinds, since normal
27 ;;; functions are deleted when their references go to zero. If
28 ;;; *BYTE-COMPILING*, then don't delete optional entries with no
29 ;;; references, since the byte interpreter wants to call entries
30 ;;; that the XEP doesn't.
31 (defun environment-analyze (component)
32 (declare (type component component))
33 (aver (every (lambda (x)
34 (eq (functional-kind x) :deleted))
35 (component-new-functions component)))
36 (setf (component-new-functions component) ())
37 (dolist (fun (component-lambdas component))
38 (reinit-lambda-environment fun))
39 (dolist (fun (component-lambdas component))
41 (dolist (let (lambda-lets fun))
42 (compute-closure let)))
44 (find-non-local-exits component)
45 (find-cleanup-points component)
46 (tail-annotate component)
48 (dolist (fun (component-lambdas component))
49 (when (null (leaf-refs fun))
50 (let ((kind (functional-kind fun)))
51 (unless (or (eq kind :top-level)
52 (functional-has-external-references-p fun)
53 (and *byte-compiling* (eq kind :optional)))
54 (aver (member kind '(:optional :cleanup :escape)))
55 (setf (functional-kind fun) nil)
56 (delete-functional fun)))))
60 ;;; This is to be called on a COMPONENT with top-level LAMBDAs before
61 ;;; the compilation of the associated non-top-level code to detect
62 ;;; closed over top-level variables. We just do COMPUTE-CLOSURE on all
63 ;;; the lambdas. This will pre-allocate environments for all the
64 ;;; functions with closed-over top-level variables. The post-pass will
65 ;;; use the existing structure, rather than allocating a new one. We
66 ;;; return true if we discover any possible closure vars.
67 (defun pre-environment-analyze-top-level (component)
68 (declare (type component component))
70 (dolist (lambda (component-lambdas component))
71 (when (compute-closure lambda)
73 (dolist (let (lambda-lets lambda))
74 (when (compute-closure let)
78 ;;; This is like old CMU CL PRE-ENVIRONMENT-ANALYZE-TOP-LEVEL, except
79 ;;; (1) It's been brought into the post-0.7.0 world where the property
80 ;;; HAS-EXTERNAL-REFERENCES-P is orthogonal to the property of
81 ;;; being specialized/optimized for locall at top level.
82 ;;; (2) There's no return value, since we don't care whether we
83 ;;; find any possible closure variables.
85 ;;; I wish I could find an explanation of why
86 ;;; PRE-ENVIRONMENT-ANALYZE-TOP-LEVEL is important. The old CMU CL
88 ;;; Called on component with top-level lambdas before the
89 ;;; compilation of the associated non-top-level code to detect
90 ;;; closed over top-level variables. We just do COMPUTE-CLOSURE on
91 ;;; all the lambdas. This will pre-allocate environments for all
92 ;;; the functions with closed-over top-level variables. The
93 ;;; post-pass will use the existing structure, rather than
94 ;;; allocating a new one. We return true if we discover any
95 ;;; possible closure vars.
96 ;;; But that doesn't seem to explain why it's important. I do observe
97 ;;; that when it's not done, compiler assertions occasionally fail. My
98 ;;; tentative hypothesis is that other environment analysis expects to
99 ;;; bottom out on the outermost enclosing thing, and (insert
100 ;;; mysterious reason here) it's important to set up bottomed-out-here
101 ;;; environments before anything else. -- WHN 2001-09-30
102 (defun preallocate-environments-for-top-levelish-lambdas (component)
103 (dolist (clambda (component-lambdas component))
104 (when (lambda-top-levelish-p clambda)
105 (compute-closure clambda)))
108 ;;; If FUN has an environment, return it, otherwise assign an empty one.
109 (defun get-lambda-environment (fun)
110 (declare (type clambda fun))
111 (let* ((fun (lambda-home fun))
112 (env (lambda-environment fun)))
114 (let ((res (make-environment :function fun)))
115 (setf (lambda-environment fun) res)
116 (dolist (letlambda (lambda-lets fun))
117 ;; This assertion is to make explicit an
118 ;; apparently-otherwise-undocumented property of existing
119 ;; code: We never overwrite an old LAMBDA-ENVIRONMENT.
121 (aver (null (lambda-environment letlambda)))
122 ;; I *think* this is true regardless of LAMBDA-KIND.
124 (aver (eql (lambda-home letlambda) fun))
125 (setf (lambda-environment letlambda) res))
128 ;;; If FUN has no physical environment, assign one, otherwise clean up
129 ;;; the old physical environment, removing/flagging variables that
130 ;;; have no sets or refs. If a var has no references, we remove it
131 ;;; from the closure. If it has no sets, we clear the INDIRECT flag.
132 ;;; This is necessary because pre-analysis is done before
134 (defun reinit-lambda-environment (fun)
135 (let ((old (lambda-environment (lambda-home fun))))
137 (setf (environment-closure old)
138 (delete-if #'(lambda (x)
139 (and (lambda-var-p x)
140 (null (leaf-refs x))))
141 (environment-closure old)))
143 (dolist (var (lambda-vars fun))
144 (unless (lambda-var-sets var)
145 (setf (lambda-var-indirect var) nil)))))
147 (dolist (let (lambda-lets fun))
150 (get-lambda-environment fun))))
153 ;;; Get NODE's environment, assigning one if necessary.
154 (defun get-node-environment (node)
155 (declare (type node node))
156 (get-lambda-environment (node-home-lambda node)))
158 ;;; Find any variables in FUN with references outside of the home
159 ;;; environment and close over them. If a closed over variable is set,
160 ;;; then we set the INDIRECT flag so that we will know the closed over
161 ;;; value is really a pointer to the value cell. We also warn about
162 ;;; unreferenced variables here, just because it's a convenient place
163 ;;; to do it. We return true if we close over anything.
164 (defun compute-closure (fun)
165 (declare (type clambda fun))
166 (let ((env (get-lambda-environment fun))
168 (note-unreferenced-vars fun)
169 (dolist (var (lambda-vars fun))
170 (dolist (ref (leaf-refs var))
171 (let ((ref-env (get-node-environment ref)))
172 (unless (eq ref-env env)
173 (when (lambda-var-sets var)
174 (setf (lambda-var-indirect var) t))
175 (setq did-something t)
176 (close-over var ref-env env))))
177 (dolist (set (basic-var-sets var))
178 (let ((set-env (get-node-environment set)))
179 (unless (eq set-env env)
180 (setq did-something t)
181 (setf (lambda-var-indirect var) t)
182 (close-over var set-env env)))))
185 ;;; Make sure that THING is closed over in REF-ENV and in all
186 ;;; environments for the functions that reference REF-ENV's function
187 ;;; (not just calls.) HOME-ENV is THING's home environment. When we
188 ;;; reach the home environment, we stop propagating the closure.
189 (defun close-over (thing ref-env home-env)
190 (declare (type environment ref-env home-env))
191 (cond ((eq ref-env home-env))
192 ((member thing (environment-closure ref-env)))
194 (push thing (environment-closure ref-env))
195 (dolist (call (leaf-refs (environment-function ref-env)))
196 (close-over thing (get-node-environment call) home-env))))
201 ;;; Insert the entry stub before the original exit target, and add a
202 ;;; new entry to the ENVIRONMENT-NLX-INFO. The %NLX-ENTRY call in the
203 ;;; stub is passed the NLX-INFO as an argument so that the back end
204 ;;; knows what entry is being done.
206 ;;; The link from the EXIT block to the entry stub is changed to be a
207 ;;; link to the component head. Similarly, the EXIT block is linked to
208 ;;; the component tail. This leaves the entry stub reachable, but
209 ;;; makes the flow graph less confusing to flow analysis.
211 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
212 ;;; last node in the cleanup code to be the enclosing environment, to
213 ;;; represent the fact that the binding was undone as a side-effect of
214 ;;; the exit. This will cause a lexical exit to be broken up if we are
215 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
216 ;;; other cleanups that may have to be done on the way.
217 (defun insert-nlx-entry-stub (exit env)
218 (declare (type environment env) (type exit exit))
219 (let* ((exit-block (node-block exit))
220 (next-block (first (block-succ exit-block)))
221 (cleanup (entry-cleanup (exit-entry exit)))
222 (info (make-nlx-info :cleanup cleanup
223 :continuation (node-cont exit)))
224 (entry (exit-entry exit))
225 (new-block (insert-cleanup-code exit-block next-block
228 (entry-cleanup entry)))
229 (component (block-component new-block)))
230 (unlink-blocks exit-block new-block)
231 (link-blocks exit-block (component-tail component))
232 (link-blocks (component-head component) new-block)
234 (setf (nlx-info-target info) new-block)
235 (push info (environment-nlx-info env))
236 (push info (cleanup-nlx-info cleanup))
237 (when (member (cleanup-kind cleanup) '(:catch :unwind-protect))
238 (setf (node-lexenv (block-last new-block))
239 (node-lexenv entry))))
243 ;;; Do stuff necessary to represent a non-local exit from the node
244 ;;; EXIT into ENV. This is called for each non-local exit node, of
245 ;;; which there may be several per exit continuation. This is what we
247 ;;; -- If there isn't any NLX-Info entry in the environment, make
248 ;;; an entry stub, otherwise just move the exit block link to
249 ;;; the component tail.
250 ;;; -- Close over the NLX-Info in the exit environment.
251 ;;; -- If the exit is from an :Escape function, then substitute a
252 ;;; constant reference to NLX-Info structure for the escape
253 ;;; function reference. This will cause the escape function to
254 ;;; be deleted (although not removed from the DFO.) The escape
255 ;;; function is no longer needed, and we don't want to emit code
256 ;;; for it. We then also change the %NLX-ENTRY call to use the
257 ;;; NLX continuation so that there will be a use to represent
259 (defun note-non-local-exit (env exit)
260 (declare (type environment env) (type exit exit))
261 (let ((entry (exit-entry exit))
262 (cont (node-cont exit))
263 (exit-fun (node-home-lambda exit)))
265 (if (find-nlx-info entry cont)
266 (let ((block (node-block exit)))
267 (aver (= (length (block-succ block)) 1))
268 (unlink-blocks block (first (block-succ block)))
269 (link-blocks block (component-tail (block-component block))))
270 (insert-nlx-entry-stub exit env))
272 (let ((info (find-nlx-info entry cont)))
274 (close-over info (node-environment exit) env)
275 (when (eq (functional-kind exit-fun) :escape)
277 (setf (node-derived-type x) *wild-type*))
278 (leaf-refs exit-fun))
279 (substitute-leaf (find-constant info) exit-fun)
280 (let ((node (block-last (nlx-info-target info))))
281 (delete-continuation-use node)
282 (add-continuation-use node (nlx-info-continuation info))))))
286 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
287 ;;; when we find a block that ends in a non-local EXIT node. We also
288 ;;; ensure that all EXIT nodes are either non-local or degenerate by
289 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
290 ;;; for later phases.
291 (defun find-non-local-exits (component)
292 (declare (type component component))
293 (dolist (lambda (component-lambdas component))
294 (dolist (entry (lambda-entries lambda))
295 (dolist (exit (entry-exits entry))
296 (let ((target-env (node-environment entry)))
297 (if (eq (node-environment exit) target-env)
298 (maybe-delete-exit exit)
299 (note-non-local-exit target-env exit))))))
303 ;;;; cleanup emission
305 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
306 ;;; cleanup code as we go. When we are done, convert the cleanup code
307 ;;; in an implicit MV-PROG1. We have to force local call analysis of
308 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
309 ;;; actually have to do anything, then we don't insert any cleanup
312 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
313 ;;; a "tail" local call.
315 ;;; We don't need to adjust the ending cleanup of the cleanup block,
316 ;;; since the cleanup blocks are inserted at the start of the DFO, and
317 ;;; are thus never scanned.
318 (defun emit-cleanups (block1 block2)
319 (declare (type cblock block1 block2))
322 (let ((cleanup2 (block-start-cleanup block2)))
323 (do ((cleanup (block-end-cleanup block1)
324 (node-enclosing-cleanup (cleanup-mess-up cleanup))))
325 ((eq cleanup cleanup2))
326 (let* ((node (cleanup-mess-up cleanup))
327 (args (when (basic-combination-p node)
328 (basic-combination-args node))))
329 (ecase (cleanup-kind cleanup)
331 (code `(%special-unbind ',(continuation-value (first args)))))
333 (code `(%catch-breakup)))
335 (code `(%unwind-protect-breakup))
336 (let ((fun (ref-leaf (continuation-use (second args)))))
338 (code `(%funcall ,fun))))
340 (dolist (nlx (cleanup-nlx-info cleanup))
341 (code `(%lexical-exit-breakup ',nlx)))))))
344 (aver (not (node-tail-p (block-last block1))))
345 (insert-cleanup-code block1 block2
348 (dolist (fun (reanalyze-funs))
349 (local-call-analyze-1 fun)))))
353 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
354 ;;; see a successor in the same environment with a different cleanup.
355 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
356 ;;; the current cleanup, since in that case we are just messing up the
357 ;;; environment, hence this is not the place to clean it.
358 (defun find-cleanup-points (component)
359 (declare (type component component))
360 (do-blocks (block1 component)
361 (let ((env1 (block-environment block1))
362 (cleanup1 (block-end-cleanup block1)))
363 (dolist (block2 (block-succ block1))
364 (when (block-start block2)
365 (let ((env2 (block-environment block2))
366 (cleanup2 (block-start-cleanup block2)))
367 (unless (or (not (eq env2 env1))
368 (eq cleanup1 cleanup2)
370 (eq (node-enclosing-cleanup
371 (cleanup-mess-up cleanup2))
373 (emit-cleanups block1 block2)))))))
376 ;;; Mark all tail-recursive uses of function result continuations with
377 ;;; the corresponding TAIL-SET. Nodes whose type is NIL (i.e. don't
378 ;;; return) such as calls to ERROR are never annotated as tail in
379 ;;; order to preserve debugging information.
380 (defun tail-annotate (component)
381 (declare (type component component))
382 (dolist (fun (component-lambdas component))
383 (let ((ret (lambda-return fun)))
385 (let ((result (return-result ret)))
386 (do-uses (use result)
387 (when (and (immediately-used-p result use)
388 (or (not (eq (node-derived-type use) *empty-type*))
389 (not (basic-combination-p use))
390 (eq (basic-combination-kind use) :local)))
391 (setf (node-tail-p use) t)))))))