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