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-funs component)))
  34   (setf (component-new-funs component) ())
  35   (dolist (fun (component-lambdas component))
  36     (reinit-lambda-physenv fun))
  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. If it has no sets, we clear the INDIRECT flag.
 127 ;;; This is necessary because pre-analysis is done before
 128 ;;; optimization.
 129 (defun reinit-lambda-physenv (fun)
 130   (let ((old (lambda-physenv (lambda-home fun))))
 131     (cond (old
 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)))
 137            (flet ((clear (fun)
 138                     (dolist (var (lambda-vars fun))
 139                       (unless (lambda-var-sets var)
 140                         (setf (lambda-var-indirect var) nil)))))
 141              (clear fun)
 142              (map nil #'clear (lambda-lets fun))))
 143           (t
 144            (get-lambda-physenv fun))))
 145   (values))
 146
 147 ;;; Get NODE's environment, assigning one if necessary.
 148 (defun get-node-physenv (node)
 149   (declare (type node node))
 150   (get-lambda-physenv (node-home-lambda node)))
 151
 152 ;;; private guts of ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES
 153 ;;;
 154 ;;; This is the old CMU CL COMPUTE-CLOSURE, which only works on
 155 ;;; LAMBDA-VARS directly, not on the LAMBDA-VARS of LAMBDA-LETS. It
 156 ;;; seems never to be valid to use this operation alone, so in SBCL,
 157 ;;; it's private, and the public interface,
 158 ;;; ADD-LAMBDA-VARS-AND-LET-VARS-TO-CLOSURES, always runs over all the
 159 ;;; variables, not only the LAMBDA-VARS of CLAMBDA itself but also
 160 ;;; the LAMBDA-VARS of CLAMBDA's LAMBDA-LETS.
 161 (defun %add-lambda-vars-to-closures (clambda)
 162   (let ((physenv (get-lambda-physenv clambda))
 163         (did-something nil))
 164     (note-unreferenced-vars clambda)
 165     (dolist (var (lambda-vars clambda))
 166       (dolist (ref (leaf-refs var))
 167         (let ((ref-physenv (get-node-physenv ref)))
 168           (unless (eq ref-physenv physenv)
 169             (when (lambda-var-sets var)
 170               (setf (lambda-var-indirect var) t))
 171             (setq did-something t)
 172             (close-over var ref-physenv physenv))))
 173       (dolist (set (basic-var-sets var))
 174         (let ((set-physenv (get-node-physenv set)))
 175           (unless (eq set-physenv physenv)
 176             (setq did-something t)
 177             (setf (lambda-var-indirect var) t)
 178             (close-over var set-physenv physenv)))))
 179     did-something))
 180
 181 ;;; Find any variables in CLAMBDA -- either directly in LAMBDA-VARS or
 182 ;;; in the LAMBDA-VARS of elements of LAMBDA-LETS -- with references
 183 ;;; outside of the home environment and close over them. If a
 184 ;;; closed-over variable is set, then we set the INDIRECT flag so that
 185 ;;; we will know the closed over value is really a pointer to the
 186 ;;; value cell. We also warn about unreferenced variables here, just
 187 ;;; because it's a convenient place to do it. We return true if we
 188 ;;; close over anything.
 189 (defun add-lambda-vars-and-let-vars-to-closures (clambda)
 190   (declare (type clambda clambda))
 191   (let ((did-something nil))
 192     (when (%add-lambda-vars-to-closures clambda)
 193       (setf did-something t))
 194     (dolist (lambda-let (lambda-lets clambda))
 195       ;; There's no need to recurse through full COMPUTE-CLOSURE
 196       ;; here, since LETS only go one layer deep.
 197       (aver (null (lambda-lets lambda-let)))
 198       (when (%add-lambda-vars-to-closures lambda-let)
 199         (setf did-something t)))
 200     did-something))
 201
 202 ;;; Make sure that THING is closed over in REF-PHYSENV and in all
 203 ;;; PHYSENVs for the functions that reference REF-PHYSENV's function
 204 ;;; (not just calls). HOME-PHYSENV is THING's home environment. When we
 205 ;;; reach the home environment, we stop propagating the closure.
 206 (defun close-over (thing ref-physenv home-physenv)
 207   (declare (type physenv ref-physenv home-physenv))
 208   (let ((flooded-physenvs nil))
 209     (named-let flood ((flooded-physenv ref-physenv))
 210       (unless (or (eql flooded-physenv home-physenv)
 211                   (member flooded-physenv flooded-physenvs))
 212         (push flooded-physenv flooded-physenvs)
 213         (pushnew thing (physenv-closure flooded-physenv))
 214         (dolist (ref (leaf-refs (physenv-lambda flooded-physenv)))
 215           (flood (get-node-physenv ref))))))
 216   (values))
 217 \f
 218 ;;;; non-local exit
 219
 220 ;;; Insert the entry stub before the original exit target, and add a
 221 ;;; new entry to the PHYSENV-NLX-INFO. The %NLX-ENTRY call in the
 222 ;;; stub is passed the NLX-INFO as an argument so that the back end
 223 ;;; knows what entry is being done.
 224 ;;;
 225 ;;; The link from the EXIT block to the entry stub is changed to be a
 226 ;;; link to the component head. Similarly, the EXIT block is linked to
 227 ;;; the component tail. This leaves the entry stub reachable, but
 228 ;;; makes the flow graph less confusing to flow analysis.
 229 ;;;
 230 ;;; If a CATCH or an UNWIND-protect, then we set the LEXENV for the
 231 ;;; last node in the cleanup code to be the enclosing environment, to
 232 ;;; represent the fact that the binding was undone as a side-effect of
 233 ;;; the exit. This will cause a lexical exit to be broken up if we are
 234 ;;; actually exiting the scope (i.e. a BLOCK), and will also do any
 235 ;;; other cleanups that may have to be done on the way.
 236 (defun insert-nlx-entry-stub (exit env)
 237   (declare (type physenv env) (type exit exit))
 238   (let* ((exit-block (node-block exit))
 239          (next-block (first (block-succ exit-block)))
 240          (cleanup (entry-cleanup (exit-entry exit)))
 241          (info (make-nlx-info :cleanup cleanup
 242                               :continuation (node-cont exit)))
 243          (entry (exit-entry exit))
 244          (new-block (insert-cleanup-code exit-block next-block
 245                                          entry
 246                                          `(%nlx-entry ',info)
 247                                          (entry-cleanup entry)))
 248          (component (block-component new-block)))
 249     (unlink-blocks exit-block new-block)
 250     (link-blocks exit-block (component-tail component))
 251     (link-blocks (component-head component) new-block)
 252
 253     (setf (nlx-info-target info) new-block)
 254     (push info (physenv-nlx-info env))
 255     (push info (cleanup-nlx-info cleanup))
 256     (when (member (cleanup-kind cleanup) '(:catch :unwind-protect))
 257       (setf (node-lexenv (block-last new-block))
 258             (node-lexenv entry))))
 259
 260   (values))
 261
 262 ;;; Do stuff necessary to represent a non-local exit from the node
 263 ;;; EXIT into ENV. This is called for each non-local exit node, of
 264 ;;; which there may be several per exit continuation. This is what we
 265 ;;; do:
 266 ;;; -- If there isn't any NLX-Info entry in the environment, make
 267 ;;;    an entry stub, otherwise just move the exit block link to
 268 ;;;    the component tail.
 269 ;;; -- Close over the NLX-Info in the exit environment.
 270 ;;; -- If the exit is from an :Escape function, then substitute a
 271 ;;;    constant reference to NLX-Info structure for the escape
 272 ;;;    function reference. This will cause the escape function to
 273 ;;;    be deleted (although not removed from the DFO.)  The escape
 274 ;;;    function is no longer needed, and we don't want to emit code
 275 ;;;    for it. We then also change the %NLX-ENTRY call to use the
 276 ;;;    NLX continuation so that there will be a use to represent
 277 ;;;    the NLX use.
 278 (defun note-non-local-exit (env exit)
 279   (declare (type physenv env) (type exit exit))
 280   (let ((entry (exit-entry exit))
 281         (cont (node-cont exit))
 282         (exit-fun (node-home-lambda exit)))
 283
 284     (if (find-nlx-info entry cont)
 285         (let ((block (node-block exit)))
 286           (aver (= (length (block-succ block)) 1))
 287           (unlink-blocks block (first (block-succ block)))
 288           (link-blocks block (component-tail (block-component block))))
 289         (insert-nlx-entry-stub exit env))
 290
 291     (let ((info (find-nlx-info entry cont)))
 292       (aver info)
 293       (close-over info (node-physenv exit) env)
 294       (when (eq (functional-kind exit-fun) :escape)
 295         (mapc #'(lambda (x)
 296                   (setf (node-derived-type x) *wild-type*))
 297               (leaf-refs exit-fun))
 298         (substitute-leaf (find-constant info) exit-fun)
 299         (let ((node (block-last (nlx-info-target info))))
 300           (delete-continuation-use node)
 301           (add-continuation-use node (nlx-info-continuation info))))))
 302
 303   (values))
 304
 305 ;;; Iterate over the EXITs in COMPONENT, calling NOTE-NON-LOCAL-EXIT
 306 ;;; when we find a block that ends in a non-local EXIT node. We also
 307 ;;; ensure that all EXIT nodes are either non-local or degenerate by
 308 ;;; calling IR1-OPTIMIZE-EXIT on local exits. This makes life simpler
 309 ;;; for later phases.
 310 (defun find-non-local-exits (component)
 311   (declare (type component component))
 312   (dolist (lambda (component-lambdas component))
 313     (dolist (entry (lambda-entries lambda))
 314       (dolist (exit (entry-exits entry))
 315         (let ((target-env (node-physenv entry)))
 316           (if (eq (node-physenv exit) target-env)
 317               (maybe-delete-exit exit)
 318               (note-non-local-exit target-env exit))))))
 319
 320   (values))
 321 \f
 322 ;;;; cleanup emission
 323
 324 ;;; Zoom up the cleanup nesting until we hit CLEANUP1, accumulating
 325 ;;; cleanup code as we go. When we are done, convert the cleanup code
 326 ;;; in an implicit MV-PROG1. We have to force local call analysis of
 327 ;;; new references to UNWIND-PROTECT cleanup functions. If we don't
 328 ;;; actually have to do anything, then we don't insert any cleanup
 329 ;;; code.
 330 ;;;
 331 ;;; If we do insert cleanup code, we check that BLOCK1 doesn't end in
 332 ;;; a "tail" local call.
 333 ;;;
 334 ;;; We don't need to adjust the ending cleanup of the cleanup block,
 335 ;;; since the cleanup blocks are inserted at the start of the DFO, and
 336 ;;; are thus never scanned.
 337 (defun emit-cleanups (block1 block2)
 338   (declare (type cblock block1 block2))
 339   (collect ((code)
 340             (reanalyze-funs))
 341     (let ((cleanup2 (block-start-cleanup block2)))
 342       (do ((cleanup (block-end-cleanup block1)
 343                     (node-enclosing-cleanup (cleanup-mess-up cleanup))))
 344           ((eq cleanup cleanup2))
 345         (let* ((node (cleanup-mess-up cleanup))
 346                (args (when (basic-combination-p node)
 347                        (basic-combination-args node))))
 348           (ecase (cleanup-kind cleanup)
 349             (:special-bind
 350              (code `(%special-unbind ',(continuation-value (first args)))))
 351             (:catch
 352              (code `(%catch-breakup)))
 353             (:unwind-protect
 354              (code `(%unwind-protect-breakup))
 355              (let ((fun (ref-leaf (continuation-use (second args)))))
 356                (reanalyze-funs fun)
 357                (code `(%funcall ,fun))))
 358             ((:block :tagbody)
 359              (dolist (nlx (cleanup-nlx-info cleanup))
 360                (code `(%lexical-exit-breakup ',nlx)))))))
 361
 362       (when (code)
 363         (aver (not (node-tail-p (block-last block1))))
 364         (insert-cleanup-code block1 block2
 365                              (block-last block1)
 366                              `(progn ,@(code)))
 367         (dolist (fun (reanalyze-funs))
 368           (locall-analyze-fun-1 fun)))))
 369
 370   (values))
 371
 372 ;;; Loop over the blocks in COMPONENT, calling EMIT-CLEANUPS when we
 373 ;;; see a successor in the same environment with a different cleanup.
 374 ;;; We ignore the cleanup transition if it is to a cleanup enclosed by
 375 ;;; the current cleanup, since in that case we are just messing up the
 376 ;;; environment, hence this is not the place to clean it.
 377 (defun find-cleanup-points (component)
 378   (declare (type component component))
 379   (do-blocks (block1 component)
 380     (let ((env1 (block-physenv block1))
 381           (cleanup1 (block-end-cleanup block1)))
 382       (dolist (block2 (block-succ block1))
 383         (when (block-start block2)
 384           (let ((env2 (block-physenv block2))
 385                 (cleanup2 (block-start-cleanup block2)))
 386             (unless (or (not (eq env2 env1))
 387                         (eq cleanup1 cleanup2)
 388                         (and cleanup2
 389                              (eq (node-enclosing-cleanup
 390                                   (cleanup-mess-up cleanup2))
 391                                  cleanup1)))
 392               (emit-cleanups block1 block2)))))))
 393   (values))
 394
 395 ;;; Mark all tail-recursive uses of function result continuations with
 396 ;;; the corresponding TAIL-SET. Nodes whose type is NIL (i.e. don't
 397 ;;; return) such as calls to ERROR are never annotated as tail in
 398 ;;; order to preserve debugging information.
 399 (defun tail-annotate (component)
 400   (declare (type component component))
 401   (dolist (fun (component-lambdas component))
 402     (let ((ret (lambda-return fun)))
 403       (when ret
 404         (let ((result (return-result ret)))
 405           (do-uses (use result)
 406             (when (and (immediately-used-p result use)
 407                      (or (not (eq (node-derived-type use) *empty-type*))
 408                          (not (basic-combination-p use))
 409                          (eq (basic-combination-kind use) :local)))
 410                 (setf (node-tail-p use) t)))))))
 411   (values))