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