X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fdfo.lisp;h=51a5953bdf5cfb50a8dce43e73ecb38c1fc2d027;hb=b63c4fb9b98fa8188e17ba926e150ba417a74635;hp=f747b6511dddcbc39f3679b509b21a409fe25b16;hpb=dc038a23a34c53e44b6de20b3e391cc05470e4af;p=sbcl.git diff --git a/src/compiler/dfo.lisp b/src/compiler/dfo.lisp index f747b65..51a5953 100644 --- a/src/compiler/dfo.lisp +++ b/src/compiler/dfo.lisp @@ -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)) @@ -30,10 +30,8 @@ (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)) @@ -69,9 +67,10 @@ (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) @@ -88,10 +87,22 @@ (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)) @@ -100,7 +111,7 @@ ;;; 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. @@ -186,12 +197,17 @@ (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 @@ -199,16 +215,16 @@ ;;; 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 @@ -217,11 +233,12 @@ ;;; 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) @@ -231,32 +248,64 @@ ((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))))) @@ -308,15 +357,15 @@ (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). @@ -336,11 +385,10 @@ ;; 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)) @@ -407,7 +455,7 @@ ;; 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)))) @@ -450,12 +498,9 @@ ;; 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 @@ -471,14 +516,9 @@ ;; 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)))