| blob | e42d02edc97ccc07d99f7306d2526f87ebb38c1c |
1 ;;;; This file contains the code that finds the initial components and
2 ;;;; DFO, and recomputes the DFO if it is invalidated.
4 ;;;; This software is part of the SBCL system. See the README file for
5 ;;;; more information.
6 ;;;;
7 ;;;; This software is derived from the CMU CL system, which was
8 ;;;; written at Carnegie Mellon University and released into the
9 ;;;; public domain. The software is in the public domain and is
10 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
11 ;;;; files for more information.
15 ;;; Find the DFO for a component, deleting any unreached blocks and
16 ;;; merging any other components we reach. We repeatedly iterate over
17 ;;; the entry points, since new ones may show up during the walk.
37 ;;; Move all the code and entry points from OLD to NEW. The code in
38 ;;; OLD is inserted at the head of NEW. This is also called during LET
39 ;;; conversion when we are about in insert the body of a LET in a
40 ;;; different component. [A local call can be to a different component
41 ;;; before FIND-INITIAL-DFO runs.]
83 ;;; Do a depth-first walk from BLOCK, inserting ourself in the DFO
84 ;;; after HEAD. If we somehow find ourselves in another component,
85 ;;; then we join that component to our component.
95 ;; FIXME: We also need (and do) this walk before physenv
96 ;; analysis, but at that time we are probably not very
97 ;; interested in the actual DF order.
98 ;;
99 ;; TODO: It is probable that one of successors have the same (or
100 ;; similar) set of NLXes; try to shorten the walk (but think
101 ;; about a loop, the only exit from which is non-local).
105 block))
110 ;;; This function is called on each block by FIND-INITIAL-DFO-AUX
111 ;;; before it walks the successors. It looks at the home CLAMBDA's
112 ;;; BIND block to see whether that block is in some other component:
113 ;;; -- If the block is in the initial component, then do
114 ;;; DFO-SCAVENGE-DEPENDENCY-GRAPH on the home function to move it
115 ;;; into COMPONENT.
116 ;;; -- If the block is in some other component, join COMPONENT into
117 ;;; it and return that component.
118 ;;; -- If the home function is deleted, do nothing. BLOCK must
119 ;;; eventually be discovered to be unreachable as well. This can
120 ;;; happen when we have a NLX into a function with no references.
121 ;;; The escape function still has refs (in the deleted function).
122 ;;;
123 ;;; This ensures that all the blocks in a given environment will be in
124 ;;; the same component, even when they might not seem reachable from
125 ;;; the environment entry. Consider the case of code that is only
126 ;;; reachable from a non-local exit.
131 component
136 component)
139 home-component))))))
141 ;;; This is somewhat similar to FIND-DFO-AUX, except that it merges
142 ;;; the current component with any strange component, rather than the
143 ;;; other way around. This is more efficient in the common case where
144 ;;; the current component doesn't have much stuff in it.
145 ;;;
146 ;;; We return the current component as a result, allowing the caller
147 ;;; to detect when the old current component has been merged with
148 ;;; another.
149 ;;;
150 ;;; We walk blocks in initial components as though they were already
151 ;;; in the current component, moving them to the current component in
152 ;;; the process. The blocks are inserted at the head of the current
153 ;;; component.
161 this)
170 current)))))
172 ;;; Return a list of all the home lambdas that reference FUN (may
173 ;;; contain duplications).
174 ;;;
175 ;;; References to functions which local call analysis could not (or
176 ;;; were chosen not) to local call convert will appear as references
177 ;;; to XEP lambdas. We can ignore references to XEPs that appear in
178 ;;; :TOPLEVEL components, since environment analysis goes to special
179 ;;; effort to allow closing over of values from a separate top level
180 ;;; component. (And now that HAS-EXTERNAL-REFERENCES-P-ness
181 ;;; generalizes :TOPLEVEL-ness, we ignore those too.) All other
182 ;;; references must cause components to be joined.
183 ;;;
184 ;;; References in deleted functions are also ignored, since this code
185 ;;; will be deleted eventually.
203 ;;; If CLAMBDA is already in COMPONENT, just return that
204 ;;; component. Otherwise, move the code for CLAMBDA and all lambdas it
205 ;;; physically depends on (either because of calls or because of
206 ;;; closure relationships) into COMPONENT, or possibly into another
207 ;;; COMPONENT that we find to be related. Return whatever COMPONENT we
208 ;;; actually merged into.
209 ;;;
210 ;;; (Note: The analogous CMU CL code only scavenged call-based
211 ;;; dependencies, not closure dependencies. That seems to've been by
212 ;;; oversight, not by design, as per the bug reported by WHN on
213 ;;; cmucl-imp ca. 2001-11-29 and explained by DTC shortly after.)
214 ;;;
215 ;;; If the function is in an initial component, then we move its head
216 ;;; and tail to COMPONENT and add it to COMPONENT's lambdas. It is
217 ;;; harmless to move the tail (even though the return might be
218 ;;; unreachable) because if the return is unreachable it (and its
219 ;;; successor link) will be deleted in the post-deletion pass.
220 ;;;
221 ;;; We then do a FIND-DFO-AUX starting at the head of CLAMBDA. If this
222 ;;; flow-graph walk encounters another component (which can only
223 ;;; happen due to a non-local exit), then we move code into that
224 ;;; component instead. We then recurse on all functions called from
225 ;;; CLAMBDA, moving code into whichever component the preceding call
226 ;;; returned.
227 ;;;
228 ;;; If CLAMBDA is in the initial component, but the BLOCK-FLAG is set
229 ;;; in the bind block, then we just return COMPONENT, since we must
230 ;;; have already reached this function in the current walk (or the
231 ;;; component would have been changed).
232 ;;;
233 ;;; If the function is an XEP, then we also walk all functions that
234 ;;; contain references to the XEP. This is done so that environment
235 ;;; analysis doesn't need to cross component boundaries. This also
236 ;;; ensures that conversion of a full call to a local call won't
237 ;;; result in a need to join components, since the components will
238 ;;; already be one.
247 component)
250 old-lambda-component)
252 component)
265 ;; Scavenge related lambdas.
269 res)))
273 ;; Scavenge call relationship.
276 ;; Scavenge closure over a variable: if CLAMBDA
277 ;; refers to a variable whose home lambda is not
278 ;; CLAMBDA, then the home lambda should be in the
279 ;; same component as CLAMBDA. (sbcl-0.6.13, and CMU
280 ;; CL, didn't do this, leading to the occasional
281 ;; failure when physenv analysis, which is local to
282 ;; each component, would bogusly conclude that a
283 ;; closed-over variable was unused and thus delete
284 ;; it. See e.g. cmucl-imp 2001-11-29.)
289 ;; Scavenge closure over an entry for nonlocal exit.
290 ;; This is basically parallel to closure over a
291 ;; variable above.
303 ;; Voila.
304 res)))))
306 ;;; Return true if CLAMBDA either is an XEP or has EXITS to some of
307 ;;; its ENTRIES.
315 ;;; Compute the result of FIND-INITIAL-DFO given the list of all
316 ;;; resulting components. Components with a :TOPLEVEL lambda, but no
317 ;;; normal XEPs or potential non-local exits are marked as :TOPLEVEL.
318 ;;; If there is a :TOPLEVEL lambda, and also a normal XEP, then we
319 ;;; treat the component as normal, but also return such components in
320 ;;; a list as the third value. Components with no entry of any sort
321 ;;; are deleted.
335 ;; is newer than the rest of this function, and
336 ;; doesn't really seem to fit into its mindset. Here
337 ;; we mark components which contain such FUNCTIONs
338 ;; them as :COMPLEX-TOPLEVEL, since they do get
339 ;; executed at run time, and since it's not valid to
340 ;; delete them just because they don't have any
341 ;; references from pure :TOPLEVEL components. -- WHN
342 has-external-references
364 ;;; Given a list of top level lambdas, return
365 ;;; (VALUES NONTOP-COMPONENTS TOP-COMPONENTS HAIRY-TOP-COMPONENTS).
366 ;;; Each of the three values returned is a list of COMPONENTs:
367 ;;; NONTOP-COMPONENTS = non-top-level-ish COMPONENTs;
368 ;;; TOP-COMPONENTS = top-level-ish COMPONENTs;
369 ;;; HAIRY-TOP-COMPONENTS = a subset of NONTOP-COMPONENTS, those
370 ;;; elements which include a top-level-ish lambda.
371 ;;;
372 ;;; We assign the DFO for each component, and delete any unreachable
373 ;;; blocks. We assume that the FLAGS have already been cleared.
377 ;; We iterate over the lambdas in each initial component, trying
378 ;; to put each function in its own component, but joining it to
379 ;; an existing component if we find that there are references
380 ;; between them. Any code that is left in an initial component
381 ;; must be unreachable, so we can delete it. Stray links to the
382 ;; initial component tail (due to NIL function terminated blocks)
383 ;; are moved to the appropriate new component tail.
396 ;; This isn't necessarily an ideal name for the
397 ;; component, since it might end up with multiple
398 ;; lambdas in it, not just this one, but it does
399 ;; seem a better name than just "<unknown>".
402 new-component)))
417 ;; When we are done, we assign DFNs.
424 ;; Pull out top-level-ish code.
426 \f
427 ;;; Insert the code in LAMBDA at the end of RESULT-LAMBDA.
431 ;; Delete the lambda, and combine the LETs and entries.
447 ;; Move blocks into the new COMPONENT, and move any nodes directly
448 ;; in the old LAMBDA into the new one (with LETs implicitly moved
449 ;; by changing their home.)
457 ;; Splice the blocks into the new DFO, and unlink them from the
458 ;; old component head and tail. Non-return blocks that jump to the
459 ;; tail (NIL-returning calls) are switched to go to the new tail.
482 ;; Switch the end of the code from the return block to the start of
483 ;; the next chunk.
489 ;; If there is a return, then delete it (making the preceding node
490 ;; the last node) and link the block to the result return. There
491 ;; is always a preceding REF NIL node in top level lambdas.
498 ;;; Given a non-empty list of top level LAMBDAs, smash them into a
499 ;;; top level lambda and component, returning these as values. We use
500 ;;; the first lambda and its component, putting the other code in that
501 ;;; component and deleting the other lambdas.
509 ;; KLUDGE: why is the node deleted but clambda still has a return?
510 ;; see a test-case for this in tests/merge-lambdas.lisp
511 ;; But now it can only be exercised with block
512 ;; compilation, which doesn't seem to work anyway.
516 ;; Make sure the result's return node starts a block so that we
517 ;; can splice code in before it.