X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fdfo.lisp;h=68469c8f2dd921333d71ccf9affccde282bbbb1f;hb=ba7659c92f2b7fac7e9532a3db9114c5bdc4ab55;hp=044b564cbc981b4cfee1e9ab21ff2325d21e8dad;hpb=20748f2dd7965dcd1446a1cb27e5a5af18a0e5bb;p=sbcl.git diff --git a/src/compiler/dfo.lisp b/src/compiler/dfo.lisp index 044b564..68469c8 100644 --- a/src/compiler/dfo.lisp +++ b/src/compiler/dfo.lisp @@ -25,7 +25,6 @@ (unless (block-flag ep) (find-dfo-aux ep head component) (return nil)))))) - (let ((num 0)) (declare (fixnum num)) (do-blocks-backwards (block component :both) @@ -89,22 +88,19 @@ (defun find-dfo-aux (block head component) (unless (eq (block-component block) component) (join-components component (block-component block))) - (unless (block-flag block) (setf (block-flag block) t) (dolist (succ (block-succ block)) (find-dfo-aux succ head component)) - (remove-from-dfo block) (add-to-dfo block head)) (values)) ;;; This function is called on each block by FIND-INITIAL-DFO-AUX -;;; before it walks the successors. It looks at the home lambda's bind -;;; block to see whether that block is in some other component: - +;;; 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-CALL-GRAPH on the home function to move it +;;; DFO-WALK-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. @@ -117,14 +113,14 @@ ;;; the same component, even when they might not seem reachable from ;;; the environment entry. Consider the case of code that is only ;;; reachable from a non-local exit. -(defun walk-home-call-graph (block component) +(defun scavenge-home-dependency-graph (block component) (declare (type cblock block) (type component component)) (let ((home-lambda (block-home-lambda block))) (if (eq (functional-kind home-lambda) :deleted) component (let ((home-component (lambda-component home-lambda))) (cond ((eq (component-kind home-component) :initial) - (dfo-scavenge-call-graph home-lambda component)) + (dfo-scavenge-dependency-graph home-lambda component)) ((eq home-component component) component) (t @@ -155,10 +151,9 @@ ((block-flag block) component) (t (setf (block-flag block) t) - (let ((current (walk-home-call-graph block component))) + (let ((current (scavenge-home-dependency-graph block component))) (dolist (succ (block-succ block)) (setq current (find-initial-dfo-aux succ current))) - (remove-from-dfo block) (add-to-dfo block (component-head current)) current))))) @@ -191,9 +186,24 @@ (res home)))) (res))) -;;; Move the code for FUN and all functions called by it into -;;; COMPONENT. If FUN is already in COMPONENT, then we just return -;;; that component. +;;; If CLAMBDA is not 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.) +;;; +;;; FIXME: Very likely we should be scavenging NLX-based dependencies +;;; here too. OTOH, there's a lot of global weirdness in NLX handling, +;;; so it might be taken care of some other way that I haven't figured +;;; out yet. Perhaps the best way to address this would be to try to +;;; construct a NLX-based test case which fails in the same way as the +;;; closure-based test case on cmucl-imp 2001-11-29.) ;;; ;;; 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 @@ -201,16 +211,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 @@ -219,56 +229,62 @@ ;;; 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-call-graph (fun component) - (declare (type clambda fun) (type component component)) - (/show "entering DFO-SCAVENGE-CALL-GRAPH" fun 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) - (/show "LAMBDA is already in COMPONENT") component) ((not (eq (component-kind old-lambda-component) :initial)) - (/show "joining COMPONENTs") (join-components old-lambda-component component) old-lambda-component) ((block-flag bind-block) - (/show "do-nothing (BLOCK-FLAG BIND-BLOCK) case") component) (t - (/show "full scavenge case") - (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)))) - - (/show (functional-kind fun)) - (/show (lambda-calls fun)) - (when (eq (functional-kind fun) :external) - (/show (find-reference-funs fun))) - - (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-call-graph (first funs) res)) - (funs calls (rest funs))) - ((null funs) 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 call relationships. + (let ((calls (if (eq (lambda-kind clambda) :external) + (append (find-reference-funs clambda) + (lambda-calls clambda)) + (lambda-calls clambda)))) + (dolist (call calls) + (let ((call-home (lambda-home call))) + (setf res (dfo-scavenge-dependency-graph call-home res))))) + ;; Scavenge closure-over relationships: if FUN refers to a + ;; variable whose home lambda is not FUN, then the home lambda + ;; should be in the same component as FUN. (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.) + (dolist (var (lambda-refers-to-vars clambda)) + (unless (null (lambda-var-refs var)) ; i.e. unless deleted + (let ((var-home-home (lambda-home (lambda-var-home var)))) + (unless (eql (lambda-kind var-home-home) :deleted) + (setf res + (dfo-scavenge-dependency-graph var-home-home res)))))) + ;; 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))))) @@ -342,7 +358,6 @@ ;;; blocks. We assume that the FLAGS have already been cleared. (defun find-initial-dfo (toplevel-lambdas) (declare (list toplevel-lambdas)) - (/show "entering FIND-INITIAL-DFO" toplevel-lambdas) (collect ((components)) ;; We iterate over the lambdas in each initial component, trying ;; to put each function in its own component, but joining it to @@ -350,17 +365,14 @@ ;; 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) - ;; are moved to the appropriate newc component tail. + ;; are moved to the appropriate new component tail. (dolist (toplevel-lambda toplevel-lambdas) - (/show toplevel-lambda) (let* ((block (lambda-block toplevel-lambda)) (old-component (block-component block)) (old-component-lambdas (component-lambdas old-component)) (new-component nil)) - (/show old-component old-component-lambdas) (aver (member toplevel-lambda old-component-lambdas)) (dolist (component-lambda old-component-lambdas) - (/show component-lambda) (aver (member (functional-kind component-lambda) '(:optional :external :toplevel nil :escape :cleanup))) @@ -373,15 +385,14 @@ ;; seem a better name than just "". (component-name-from-functional-debug-name component-lambda))) - (let ((res (dfo-scavenge-call-graph component-lambda new-component))) + (let ((res (dfo-scavenge-dependency-graph component-lambda + new-component))) (when (eq res new-component) - (/show "saving" new-component (component-lambdas new-component)) (aver (not (position new-component (components)))) (components new-component) (setq new-component nil)))) (when (eq (component-kind old-component) :initial) (aver (null (component-lambdas old-component))) - (/show "clearing/deleting OLD-COMPONENT because KIND=:INITIAL") (let ((tail (component-tail old-component))) (dolist (pred (block-pred tail)) (let ((pred-component (block-component pred))) @@ -401,7 +412,7 @@ (separate-toplevelish-components (components)))) ;;; Insert the code in LAMBDA at the end of RESULT-LAMBDA. -(defun merge-1-tl-lambda (result-lambda lambda) +(defun merge-1-toplevel-lambda (result-lambda lambda) (declare (type clambda result-lambda lambda)) ;; Delete the lambda, and combine the LETs and entries. @@ -498,7 +509,7 @@ (add-continuation-use use new)))) (dolist (lambda (rest lambdas)) - (merge-1-tl-lambda result-lambda lambda))) + (merge-1-toplevel-lambda result-lambda lambda))) (t (dolist (lambda (rest lambdas)) (setf (functional-entry-fun lambda) nil)