0.8.19.32:
[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   (recheck-dynamic-extent-lvars component)
42   (find-cleanup-points component)
43   (tail-annotate component)
44
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)))))
53
54   (setf (component-nlx-info-generated-p component) t)
55   (values))
56
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))
66   (let ((found-it nil))
67     (dolist (lambda (component-lambdas component))
68       (when (add-lambda-vars-and-let-vars-to-closures lambda)
69         (setq found-it t)))
70     found-it))
71
72 ;;; If CLAMBDA has a PHYSENV, return it, otherwise assign an empty one
73 ;;; and return that.
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))
88           res))))
89
90 ;;; If FUN has no physical environment, assign one, otherwise clean up
91 ;;; the old physical environment, removing/flagging variables that
92 ;;; have no sets or refs. If a var has no references, we remove it
93 ;;; from the closure. We always clear the INDIRECT flag. This is
94 ;;; necessary because pre-analysis is done before optimization.
95 (defun reinit-lambda-physenv (fun)
96   (let ((old (lambda-physenv (lambda-home fun))))
97     (cond (old
98            (setf (physenv-closure old)
99                  (delete-if (lambda (x)
100                               (and (lambda-var-p x)
101                                    (null (leaf-refs x))))
102                             (physenv-closure old)))
103            (flet ((clear (fun)
104                     (dolist (var (lambda-vars fun))
105                       (setf (lambda-var-indirect var) nil))))
106              (clear fun)
107              (map nil #'clear (lambda-lets fun))))
108           (t
109            (get-lambda-physenv fun))))
110   (values))
111
112 ;;; Get NODE's environment, assigning one if necessary.
113 (defun get-node-physenv (node)
114   (declare (type node node))
115   (get-lambda-physenv (node-home-lambda node)))
116
117 ;;; private guts of ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES
118 ;;;
119 ;;; This is the old CMU CL COMPUTE-CLOSURE, which only works on
120 ;;; LAMBDA-VARS directly, not on the LAMBDA-VARS of LAMBDA-LETS. It
121 ;;; seems never to be valid to use this operation alone, so in SBCL,
122 ;;; it's private, and the public interface,
123 ;;; ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES, always runs over all the
124 ;;; variables, not only the LAMBDA-VARS of CLAMBDA itself but also
125 ;;; the LAMBDA-VARS of CLAMBDA's LAMBDA-LETS.
126 (defun %add-lambda-vars-to-closures (clambda)
127   (let ((physenv (get-lambda-physenv clambda))
128         (did-something nil))
129     (note-unreferenced-vars clambda)
130     (dolist (var (lambda-vars clambda))
131       (dolist (ref (leaf-refs var))
132         (let ((ref-physenv (get-node-physenv ref)))
133           (unless (eq ref-physenv physenv)
134             (when (lambda-var-sets var)
135               (setf (lambda-var-indirect var) t))
136             (setq did-something t)
137             (close-over var ref-physenv physenv))))
138       (dolist (set (basic-var-sets var))
139
140         ;; Variables which are set but never referenced can be
141         ;; optimized away, and closing over them here would just
142         ;; interfere with that. (In bug 147, it *did* interfere with
143         ;; that, causing confusion later. This UNLESS solves that
144         ;; problem, but I (WHN) am not 100% sure it's best to solve
145         ;; the problem this way instead of somehow solving it
146         ;; somewhere upstream and just doing (AVER (LEAF-REFS VAR))
147         ;; here.)
148         (unless (null (leaf-refs var))
149
150           (let ((set-physenv (get-node-physenv set)))
151             (unless (eq set-physenv physenv)
152               (setf did-something t
153                     (lambda-var-indirect var) t)
154               (close-over var set-physenv physenv))))))
155     did-something))
156
157 ;;; Find any variables in CLAMBDA -- either directly in LAMBDA-VARS or
158 ;;; in the LAMBDA-VARS of elements of LAMBDA-LETS -- with references
159 ;;; outside of the home environment and close over them. If a
160 ;;; closed-over variable is set, then we set the INDIRECT flag so that
161 ;;; we will know the closed over value is really a pointer to the
162 ;;; value cell. We also warn about unreferenced variables here, just
163 ;;; because it's a convenient place to do it. We return true if we
164 ;;; close over anything.
165 (defun add-lambda-vars-and-let-vars-to-closures (clambda)
166   (declare (type clambda clambda))
167   (let ((did-something nil))
168     (when (%add-lambda-vars-to-closures clambda)
169       (setf did-something t))
170     (dolist (lambda-let (lambda-lets clambda))
171       ;; There's no need to recurse through full COMPUTE-CLOSURE
172       ;; here, since LETS only go one layer deep.
173       (aver (null (lambda-lets lambda-let)))
174       (when (%add-lambda-vars-to-closures lambda-let)
175         (setf did-something t)))
176     did-something))
177
178 (defun xep-allocator (xep)
179   (let ((entry (functional-entry-fun xep)))
180     (functional-allocator entry)))
181
182 ;;; Make sure that THING is closed over in REF-PHYSENV and in all
183 ;;; PHYSENVs for the functions that reference REF-PHYSENV's function
184 ;;; (not just calls). HOME-PHYSENV is THING's home environment. When we
185 ;;; reach the home environment, we stop propagating the closure.
186 (defun close-over (thing ref-physenv home-physenv)
187   (declare (type physenv ref-physenv home-physenv))
188   (let ((flooded-physenvs nil))
189     (labels ((flood (flooded-physenv)
190                (unless (or (eql flooded-physenv home-physenv)
191                            (member flooded-physenv flooded-physenvs))
192                  (push flooded-physenv flooded-physenvs)
193                  (unless (memq thing (physenv-closure flooded-physenv))
194                    (push thing (physenv-closure flooded-physenv))
195                    (let ((lambda (physenv-lambda flooded-physenv)))
196                      (cond ((eq (functional-kind lambda) :external)
197                             (let* ((alloc-node (xep-allocator lambda))
198                                    (alloc-lambda (node-home-lambda alloc-node))
199                                    (alloc-physenv (get-lambda-physenv alloc-lambda)))
200                               (flood alloc-physenv)
201                               (dolist (ref (leaf-refs lambda))
202                                 (close-over lambda
203                                             (get-node-physenv ref) alloc-physenv))))
204                            (t (dolist (ref (leaf-refs lambda))
205                                 ;; FIXME: This assertion looks
206                                 ;; reasonable, but does not work for
207                                 ;; :CLEANUPs.
208                                 #+nil
209                                 (let ((dest (node-dest ref)))
210                                   (aver (basic-combination-p dest))
211                                   (aver (eq (basic-combination-kind dest) :local)))
212                                 (flood (get-node-physenv ref))))))))))
213       (flood ref-physenv)))
214   (values))
215 \f
216 ;;;; non-local exit
217
218 #!-sb-fluid (declaim (inline should-exit-check-tag-p))
219 (defun exit-should-check-tag-p (exit)
220   (declare (type exit exit))
221   (not (zerop (policy exit check-tag-existence))))
222
223 ;;; Insert the entry stub before the original exit target, and add a
224 ;;; new entry to the PHYSENV-NLX-INFO. The %NLX-ENTRY call in the
225 ;;; stub is passed the NLX-INFO as an argument so that the back end
226 ;;; knows what entry is being done.
227 ;;;
228 ;;; The link from the EXIT block to the entry stub is changed to be a
229 ;;; link from the component head. Similarly, the EXIT block is linked
230 ;;; to the component tail. This leaves the entry stub reachable, but
231 ;;; makes the flow graph less confusing to flow analysis.
232 ;;;
233 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
234 ;;; last node in the cleanup code to be the enclosing environment, to
235 ;;; represent the fact that the binding was undone as a side effect of
236 ;;; the exit. This will cause a lexical exit to be broken up if we are
237 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
238 ;;; other cleanups that may have to be done on the way.
239 (defun insert-nlx-entry-stub (exit env)
240   (declare (type physenv env) (type exit exit))
241   (let* ((exit-block (node-block exit))
242          (next-block (first (block-succ exit-block)))
243          (entry (exit-entry exit))
244          (cleanup (entry-cleanup entry))
245          (info (make-nlx-info cleanup exit))
246          (new-block (insert-cleanup-code exit-block next-block
247                                          entry
248                                          `(%nlx-entry ',info)
249                                          cleanup))
250          (component (block-component new-block)))
251     (unlink-blocks exit-block new-block)
252     (link-blocks exit-block (component-tail component))
253     (link-blocks (component-head component) new-block)
254
255     (setf (exit-nlx-info exit) info)
256     (setf (nlx-info-target info) new-block)
257     (setf (nlx-info-safe-p info) (exit-should-check-tag-p exit))
258     (push info (physenv-nlx-info env))
259     (push info (cleanup-nlx-info cleanup))
260     (when (member (cleanup-kind cleanup) '(:catch :unwind-protect))
261       (setf (node-lexenv (block-last new-block))
262             (node-lexenv entry))))
263
264   (values))
265
266 ;;; Do stuff necessary to represent a non-local exit from the node
267 ;;; EXIT into ENV. This is called for each non-local exit node, of
268 ;;; which there may be several per exit continuation. This is what we
269 ;;; do:
270 ;;; -- If there isn't any NLX-INFO entry in the environment, make
271 ;;;    an entry stub, otherwise just move the exit block link to
272 ;;;    the component tail.
273 ;;; -- Close over the NLX-INFO in the exit environment.
274 ;;; -- If the exit is from an :ESCAPE function, then substitute a
275 ;;;    constant reference to NLX-INFO structure for the escape
276 ;;;    function reference. This will cause the escape function to
277 ;;;    be deleted (although not removed from the DFO.)  The escape
278 ;;;    function is no longer needed, and we don't want to emit code
279 ;;;    for it.
280 ;;; -- Change the %NLX-ENTRY call to use the NLX lvar so that 1) there
281 ;;;    will be a use to represent the NLX use; 2) make life easier for
282 ;;;    the stack analysis.
283 (defun note-non-local-exit (env exit)
284   (declare (type physenv env) (type exit exit))
285   (let ((lvar (node-lvar exit))
286         (exit-fun (node-home-lambda exit))
287         (info (find-nlx-info exit)))
288     (cond (info
289            (let ((block (node-block exit)))
290              (aver (= (length (block-succ block)) 1))
291              (unlink-blocks block (first (block-succ block)))
292              (link-blocks block (component-tail (block-component block)))
293              (setf (exit-nlx-info exit) info)
294              (unless (nlx-info-safe-p info)
295                (setf (nlx-info-safe-p info)
296                      (exit-should-check-tag-p exit)))))
297           (t
298            (insert-nlx-entry-stub exit env)
299            (setq info (exit-nlx-info exit))
300            (aver info)))
301     (close-over info (node-physenv exit) env)
302     (when (eq (functional-kind exit-fun) :escape)
303       (mapc (lambda (x)
304               (setf (node-derived-type x) *wild-type*))
305             (leaf-refs exit-fun))
306       (substitute-leaf (find-constant info) exit-fun))
307     (when lvar
308       (let ((node (block-last (nlx-info-target info))))
309         (unless (node-lvar node)
310           (aver (eq lvar (node-lvar exit)))
311           (setf (node-derived-type node) (lvar-derived-type lvar))
312           (add-lvar-use node lvar)))))
313   (values))
314
315 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
316 ;;; when we find a block that ends in a non-local EXIT node. We also
317 ;;; ensure that all EXIT nodes are either non-local or degenerate by
318 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
319 ;;; for later phases.
320 (defun find-non-local-exits (component)
321   (declare (type component component))
322   (dolist (lambda (component-lambdas component))
323     (dolist (entry (lambda-entries lambda))
324       (dolist (exit (entry-exits entry))
325         (let ((target-physenv (node-physenv entry)))
326           (if (eq (node-physenv exit) target-physenv)
327               (maybe-delete-exit exit)
328               (note-non-local-exit target-physenv exit))))))
329   (values))
330 \f
331 ;;;; final decision on stack allocation of dynamic-extent structures
332 (defun recheck-dynamic-extent-lvars (component)
333   (declare (type component component))
334   (dolist (lambda (component-lambdas component))
335     (loop for entry in (lambda-entries lambda)
336             for cleanup = (entry-cleanup entry)
337             do (when (eq (cleanup-kind cleanup) :dynamic-extent)
338                  (collect ((real-dx-lvars))
339                    (loop for what in (cleanup-info cleanup)
340                          do (etypecase what
341                               (lvar
342                                (let* ((lvar what)
343                                       (use (lvar-uses lvar)))
344                                  (if (and (combination-p use)
345                                           (eq (basic-combination-kind use) :known)
346                                           (awhen (fun-info-stack-allocate-result
347                                                   (basic-combination-fun-info use))
348                                             (funcall it use)))
349                                      (real-dx-lvars lvar)
350                                      (setf (lvar-dynamic-extent lvar) nil))))
351                               (node ; DX closure
352                                (let* ((call what)
353                                       (arg (first (basic-combination-args call)))
354                                       (funs (lvar-value arg))
355                                       (dx nil))
356                                  (dolist (fun funs)
357                                    (binding* ((() (leaf-dynamic-extent fun)
358                                                   :exit-if-null)
359                                               (xep (functional-entry-fun fun)
360                                                    :exit-if-null)
361                                               (closure (physenv-closure
362                                                         (get-lambda-physenv xep))))
363                                      (cond (closure
364                                             (setq dx t))
365                                            (t
366                                             (setf (leaf-dynamic-extent fun) nil)))))
367                                  (when dx
368                                    (setf (lvar-dynamic-extent arg) cleanup)
369                                    (real-dx-lvars arg))))))
370                    (setf (cleanup-info cleanup) (real-dx-lvars))
371                    (setf (component-dx-lvars component)
372                          (append (real-dx-lvars) (component-dx-lvars component)))))))
373   (values))
374 \f
375 ;;;; cleanup emission
376
377 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
378 ;;; cleanup code as we go. When we are done, convert the cleanup code
379 ;;; in an implicit MV-PROG1. We have to force local call analysis of
380 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
381 ;;; actually have to do anything, then we don't insert any cleanup
382 ;;; code. (FIXME: There's some confusion here, left over from CMU CL
383 ;;; comments. CLEANUP1 isn't mentioned in the code of this function.
384 ;;; It is in code elsewhere, but if the comments for this function
385 ;;; mention it they should explain the relationship to the other code.)
386 ;;;
387 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
388 ;;; a "tail" local call.
389 ;;;
390 ;;; We don't need to adjust the ending cleanup of the cleanup block,
391 ;;; since the cleanup blocks are inserted at the start of the DFO, and
392 ;;; are thus never scanned.
393 (defun emit-cleanups (block1 block2)
394   (declare (type cblock block1 block2))
395   (collect ((code)
396             (reanalyze-funs))
397     (let ((cleanup2 (block-start-cleanup block2)))
398       (do ((cleanup (block-end-cleanup block1)
399                     (node-enclosing-cleanup (cleanup-mess-up cleanup))))
400           ((eq cleanup cleanup2))
401         (let* ((node (cleanup-mess-up cleanup))
402                (args (when (basic-combination-p node)
403                        (basic-combination-args node))))
404           (ecase (cleanup-kind cleanup)
405             (:special-bind
406              (code `(%special-unbind ',(lvar-value (first args)))))
407             (:catch
408              (code `(%catch-breakup)))
409             (:unwind-protect
410              (code `(%unwind-protect-breakup))
411              (let ((fun (ref-leaf (lvar-uses (second args)))))
412                (reanalyze-funs fun)
413                (code `(%funcall ,fun))))
414             ((:block :tagbody)
415              (dolist (nlx (cleanup-nlx-info cleanup))
416                (code `(%lexical-exit-breakup ',nlx))))
417             (:dynamic-extent
418              (when (not (null (cleanup-info cleanup)))
419                (code `(%cleanup-point)))))))
420
421       (when (code)
422         (aver (not (node-tail-p (block-last block1))))
423         (insert-cleanup-code block1 block2
424                              (block-last block1)
425                              `(progn ,@(code)))
426         (dolist (fun (reanalyze-funs))
427           (locall-analyze-fun-1 fun)))))
428
429   (values))
430
431 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
432 ;;; see a successor in the same environment with a different cleanup.
433 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
434 ;;; the current cleanup, since in that case we are just messing up the
435 ;;; environment, hence this is not the place to clean it.
436 (defun find-cleanup-points (component)
437   (declare (type component component))
438   (do-blocks (block1 component)
439     (let ((env1 (block-physenv block1))
440           (cleanup1 (block-end-cleanup block1)))
441       (dolist (block2 (block-succ block1))
442         (when (block-start block2)
443           (let ((env2 (block-physenv block2))
444                 (cleanup2 (block-start-cleanup block2)))
445             (unless (or (not (eq env2 env1))
446                         (eq cleanup1 cleanup2)
447                         (and cleanup2
448                              (eq (node-enclosing-cleanup
449                                   (cleanup-mess-up cleanup2))
450                                  cleanup1)))
451               (emit-cleanups block1 block2)))))))
452   (values))
453
454 ;;; Mark optimizable tail-recursive uses of function result
455 ;;; continuations with the corresponding TAIL-SET.
456 (defun tail-annotate (component)
457   (declare (type component component))
458   (dolist (fun (component-lambdas component))
459     (let ((ret (lambda-return fun)))
460       ;; Nodes whose type is NIL (i.e. don't return) such as calls to
461       ;; ERROR are never annotated as TAIL-P, in order to preserve
462       ;; debugging information.
463       ;;
464       ;; FIXME: It might be better to add another DEFKNOWN property
465       ;; (e.g. NO-TAIL-RECURSION) and use it for error-handling
466       ;; functions like ERROR, instead of spreading this special case
467       ;; net so widely.
468       (when ret
469         (let ((result (return-result ret)))
470           (do-uses (use result)
471             (when (and (policy use merge-tail-calls)
472                        (basic-combination-p use)
473                        (immediately-used-p result use)
474                        (or (not (eq (node-derived-type use) *empty-type*))
475                            (eq (basic-combination-kind use) :local)))
476               (setf (node-tail-p use) t)))))))
477   (values))