(unless (block-flag ep)
(find-dfo-aux ep head component)
(return nil))))))
-
(let ((num 0))
(declare (fixnum num))
(do-blocks-backwards (block component :both)
(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.
;;; 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
((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)))))
(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
;;; 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-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)))))
;;; 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
;; 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)))
;; seem a better name than just "<unknown>".
(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)))
(separate-toplevelish-components (components))))
\f
;;; 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.
(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)