0.8.15:
[sbcl.git] / src / compiler / dfo.lisp
index f747b65..51a5953 100644 (file)
@@ -22,7 +22,7 @@
   (let ((head (component-head component)))
     (do ()
        ((dolist (ep (block-succ head) t)
-          (unless (block-flag ep)
+          (unless (or (block-flag ep) (block-delete-p ep))
             (find-dfo-aux ep head component)
             (return nil))))))
   (let ((num 0))
     (do-blocks-backwards (block component :both)
       (if (block-flag block)
          (setf (block-number block) (incf num))
-         (setf (block-delete-p block) t)))
-    (do-blocks (block component)
-      (unless (block-flag block)
-       (delete-block block))))
+         (delete-block-lazily block)))
+    (clean-component component (component-head component)))
   (values))
 
 ;;; Move all the code and entry points from OLD to NEW. The code in
@@ -59,7 +57,7 @@
       (unless (eq old-next old-tail)
        (setf (block-next head) old-next)
        (setf (block-prev old-next) head)
-       
+
        (setf (block-prev next) old-last)
        (setf (block-next old-last) next))
 
     (setf (component-lambdas new)
          (nconc (component-lambdas old) (component-lambdas new)))
     (setf (component-lambdas old) nil)
-    (setf (component-new-funs new) (nconc (component-new-funs old)
-                                         (component-new-funs new))
-         (component-new-funs old) nil)
+    (setf (component-new-functionals new)
+         (nconc (component-new-functionals old)
+                (component-new-functionals new)))
+    (setf (component-new-functionals old) nil)
 
     (dolist (xp (block-pred old-tail))
       (unlink-blocks xp old-tail)
 (defun find-dfo-aux (block head component)
   (unless (eq (block-component block) component)
     (join-components component (block-component block)))
-  (unless (block-flag block)
+  (unless (or (block-flag block) (block-delete-p block))
     (setf (block-flag block) t)
     (dolist (succ (block-succ block))
       (find-dfo-aux succ head component))
+    (when (component-nlx-info-generated-p component)
+      ;; FIXME: We also need (and do) this walk before physenv
+      ;; analysis, but at that time we are probably not very
+      ;; interested in the actual DF order.
+      ;;
+      ;; TODO: It is probable that one of successors have the same (or
+      ;; similar) set of NLXes; try to shorten the walk (but think
+      ;; about a loop, the only exit from which is non-local).
+      (map-block-nlxes (lambda (nlx-info)
+                         (let ((nle (nlx-info-target nlx-info)))
+                         (find-dfo-aux nle head component)))
+                       block))
     (remove-from-dfo block)
     (add-to-dfo block head))
   (values))
 ;;; before it walks the successors. It looks at the home CLAMBDA's
 ;;; BIND block to see whether that block is in some other component:
 ;;; -- If the block is in the initial component, then do
-;;;    DFO-WALK-DEPENDENCY-GRAPH on the home function to move it
+;;;    DFO-SCAVENGE-DEPENDENCY-GRAPH on the home function to move it
 ;;;    into COMPONENT.
 ;;; -- If the block is in some other component, join COMPONENT into
 ;;;    it and return that component.
          (res home))))
     (res)))
 
-;;; If FUN is not already in COMPONENT, just return that component.
-;;; Otherwise, move the code for FUN and all functions it physically
-;;; depends on (either because of calls or because of closure
-;;; relationships) into COMPONENT, or possibly into another COMPONENT
-;;; that we find to be related. Return whatever COMPONENT we actually
-;;; merged into.
+;;; If CLAMBDA is already in COMPONENT, just return that
+;;; component. Otherwise, move the code for CLAMBDA and all lambdas it
+;;; physically depends on (either because of calls or because of
+;;; closure relationships) into COMPONENT, or possibly into another
+;;; COMPONENT that we find to be related. Return whatever COMPONENT we
+;;; actually merged into.
+;;;
+;;; (Note: The analogous CMU CL code only scavenged call-based
+;;; dependencies, not closure dependencies. That seems to've been by
+;;; oversight, not by design, as per the bug reported by WHN on
+;;; cmucl-imp ca. 2001-11-29 and explained by DTC shortly after.)
 ;;;
 ;;; If the function is in an initial component, then we move its head
 ;;; and tail to COMPONENT and add it to COMPONENT's lambdas. It is
 ;;; unreachable) because if the return is unreachable it (and its
 ;;; successor link) will be deleted in the post-deletion pass.
 ;;;
-;;; We then do a FIND-DFO-AUX starting at the head of FUN. If this
+;;; We then do a FIND-DFO-AUX starting at the head of CLAMBDA. If this
 ;;; flow-graph walk encounters another component (which can only
 ;;; happen due to a non-local exit), then we move code into that
 ;;; component instead. We then recurse on all functions called from
-;;; FUN, moving code into whichever component the preceding call
+;;; CLAMBDA, moving code into whichever component the preceding call
 ;;; returned.
 ;;;
-;;; If FUN is in the initial component, but the BLOCK-FLAG is set in
-;;; the bind block, then we just return COMPONENT, since we must have
-;;; already reached this function in the current walk (or the
+;;; If CLAMBDA is in the initial component, but the BLOCK-FLAG is set
+;;; in the bind block, then we just return COMPONENT, since we must
+;;; have already reached this function in the current walk (or the
 ;;; component would have been changed).
 ;;;
 ;;; If the function is an XEP, then we also walk all functions that
 ;;; ensures that conversion of a full call to a local call won't
 ;;; result in a need to join components, since the components will
 ;;; already be one.
-(defun dfo-scavenge-dependency-graph (fun component)
-  (declare (type clambda fun) (type component component))
-  (let* ((bind-block (node-block (lambda-bind fun)))
+(defun dfo-scavenge-dependency-graph (clambda component)
+  (declare (type clambda clambda) (type component component))
+  (assert (not (eql (lambda-kind clambda) :deleted)))
+  (let* ((bind-block (node-block (lambda-bind clambda)))
         (old-lambda-component (block-component bind-block))
-        (return (lambda-return fun)))
+        (return (lambda-return clambda)))
     (cond
      ((eq old-lambda-component component)
       component)
      ((block-flag bind-block)
       component)
      (t
-      (push fun (component-lambdas component))
+      (push clambda (component-lambdas component))
       (setf (component-lambdas old-lambda-component)
-           (delete fun (component-lambdas old-lambda-component)))
+           (delete clambda (component-lambdas old-lambda-component)))
       (link-blocks (component-head component) bind-block)
       (unlink-blocks (component-head old-lambda-component) bind-block)
       (when return
        (let ((return-block (node-block return)))
          (link-blocks return-block (component-tail component))
          (unlink-blocks return-block (component-tail old-lambda-component))))
-      (let ((calls (if (eq (functional-kind fun) :external)
-                      (append (find-reference-funs fun)
-                              (lambda-calls fun))
-                      (lambda-calls fun))))
-       (do ((res (find-initial-dfo-aux bind-block component)
-                 (dfo-scavenge-dependency-graph (first remaining-calls) res))
-            (remaining-calls calls (rest remaining-calls)))
-           ((null remaining-calls)
-            res)
-         (declare (type component res))))))))
-
-;;; Return true if FUN is either an XEP or has EXITS to some of its
-;;; ENTRIES.
-(defun has-xep-or-nlx (fun)
-  (declare (type clambda fun))
-  (or (eq (functional-kind fun) :external)
-      (let ((entries (lambda-entries fun)))
+      (let ((res (find-initial-dfo-aux bind-block component)))
+       (declare (type component res))
+       ;; Scavenge related lambdas.
+       (labels ((scavenge-lambda (clambda)
+                  (setf res
+                        (dfo-scavenge-dependency-graph (lambda-home clambda)
+                                                       res)))
+                (scavenge-possibly-deleted-lambda (clambda)
+                  (unless (eql (lambda-kind clambda) :deleted)
+                    (scavenge-lambda clambda)))
+                ;; Scavenge call relationship.
+                (scavenge-call (called-lambda)
+                  (scavenge-lambda called-lambda))
+                ;; Scavenge closure over a variable: if CLAMBDA
+                ;; refers to a variable whose home lambda is not
+                ;; CLAMBDA, then the home lambda should be in the
+                ;; same component as CLAMBDA. (sbcl-0.6.13, and CMU
+                ;; CL, didn't do this, leading to the occasional
+                ;; failure when physenv analysis, which is local to
+                ;; each component, would bogusly conclude that a
+                ;; closed-over variable was unused and thus delete
+                ;; it. See e.g. cmucl-imp 2001-11-29.)
+                (scavenge-closure-var (var)
+                  (unless (null (lambda-var-refs var)) ; unless var deleted
+                    (let ((var-home-home (lambda-home (lambda-var-home var))))
+                      (scavenge-possibly-deleted-lambda var-home-home))))
+                ;; Scavenge closure over an entry for nonlocal exit.
+                ;; This is basically parallel to closure over a
+                ;; variable above.
+                (scavenge-entry (entry)
+                  (declare (type entry entry))
+                  (let ((entry-home (node-home-lambda entry)))
+                    (scavenge-possibly-deleted-lambda entry-home))))
+         (dolist (cc (lambda-calls-or-closes clambda))
+           (etypecase cc
+             (clambda (scavenge-call cc))
+             (lambda-var (scavenge-closure-var cc))
+             (entry (scavenge-entry cc))))
+         (when (eq (lambda-kind clambda) :external)
+           (mapc #'scavenge-call (find-reference-funs clambda))))
+       ;; Voila.
+       res)))))
+
+;;; Return true if CLAMBDA either is an XEP or has EXITS to some of
+;;; its ENTRIES.
+(defun has-xep-or-nlx (clambda)
+  (declare (type clambda clambda))
+  (or (eq (functional-kind clambda) :external)
+      (let ((entries (lambda-entries clambda)))
        (and entries
             (find-if #'entry-exits entries)))))
 
 
     (values (real) (top) (real-top))))
 
-;; COMPONENTs want strings for names, LEAF-DEBUG-NAMEs mightn't be
-;; strings..
+;;; COMPONENTs want strings for names, LEAF-DEBUG-NAMEs mightn't be
+;;; strings...
 (defun component-name-from-functional-debug-name (functional)
   (declare (type functional functional))
   (let ((leaf-debug-name (leaf-debug-name functional)))
     (the simple-string
       (if (stringp leaf-debug-name)
          leaf-debug-name
-         (debug-namify "function ~S" leaf-debug-name)))))
+         (debug-namify "function " leaf-debug-name)))))
 
 ;;; Given a list of top level lambdas, return
 ;;;   (VALUES NONTOP-COMPONENTS TOP-COMPONENTS HAIRY-TOP-COMPONENTS).
     ;; an existing component if we find that there are references
     ;; between them. Any code that is left in an initial component
     ;; must be unreachable, so we can delete it. Stray links to the
-    ;; initial component tail (due NIL function terminated blocks)
+    ;; initial component tail (due to NIL function terminated blocks)
     ;; are moved to the appropriate new component tail.
     (dolist (toplevel-lambda toplevel-lambdas)
-      (let* ((block (lambda-block toplevel-lambda))
-            (old-component (block-component block))
+      (let* ((old-component (lambda-component toplevel-lambda))
             (old-component-lambdas (component-lambdas old-component))
             (new-component nil))
        (aver (member toplevel-lambda old-component-lambdas))
     ;; in the old LAMBDA into the new one (with LETs implicitly moved
     ;; by changing their home.)
     (do-blocks (block component)
-      (do-nodes (node cont block)
+      (do-nodes (node nil block)
        (let ((lexenv (node-lexenv node)))
          (when (eq (lexenv-lambda lexenv) lambda)
            (setf (lexenv-lambda lexenv) result-lambda))))
     ;; is always a preceding REF NIL node in top level lambdas.
     (let ((return (lambda-return lambda)))
       (when return
-       (let ((return-block (node-block return))
-             (result (return-result return)))
-         (setf (block-last return-block) (continuation-use result))
-         (flush-dest result)
-         (delete-continuation result)
-         (link-blocks return-block result-return-block))))))
+       (link-blocks (node-block return) result-return-block)
+        (flush-dest (return-result return))
+        (unlink-node return)))))
 
 ;;; Given a non-empty list of top level LAMBDAs, smash them into a
 ;;; top level lambda and component, returning these as values. We use
       ;; Make sure the result's return node starts a block so that we
       ;; can splice code in before it.
       (let ((prev (node-prev
-                  (continuation-use
-                   (return-result result-return)))))
-       (when (continuation-use prev)
-         (node-ends-block (continuation-use prev)))
-       (do-uses (use prev)
-         (let ((new (make-continuation)))
-           (delete-continuation-use use)
-           (add-continuation-use use new))))
+                  (lvar-uses (return-result result-return)))))
+       (when (ctran-use prev)
+         (node-ends-block (ctran-use prev))))
 
       (dolist (lambda (rest lambdas))
        (merge-1-toplevel-lambda result-lambda lambda)))