| blob | 4dea2e2cbfe3e7495a7724de6891ca3b9be1ce75 |
1 ;;;; This file contains the lifetime analysis phase in the compiler.
3 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; more information.
5 ;;;;
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
13 \f
14 ;;;; utilities
16 ;;; Link in a GLOBAL-CONFLICTS structure for TN in BLOCK with NUMBER
17 ;;; as the LTN number. The conflict is inserted in the per-TN
18 ;;; GLOBAL-CONFLICTS thread after the TN's CURRENT-CONFLICT. We change
19 ;;; the CURRENT-CONFLICT to point to the new conflict. Since we scan
20 ;;; the blocks in reverse DFO, this list is automatically built in
21 ;;; order. We have to actually scan the current GLOBAL-TNs for the
22 ;;; block in order to keep that thread sorted.
32 new)
35 new)))
41 ;;; Do the actual insertion of the conflict NEW into BLOCK's global
42 ;;; conflicts.
56 ;;; Reset the CURRENT-CONFLICT slot in all packed TNs to point to the
57 ;;; head of the GLOBAL-CONFLICTS thread.
62 ;;; Cache the results of BLOCK-PHYSENV during lifetime analysis.
63 ;;;
64 ;;; Fetching the home-lambda of a block (needed in block-physenv) can
65 ;;; be an expensive operation under some circumstances, and it needs
66 ;;; to be done a lot during lifetime analysis when compiling with high
67 ;;; DEBUG (e.g. 30% of the total compilation time for CL-PPCRE with
68 ;;; DEBUG 3 just for that).
74 physenv)))
75 \f
76 ;;;; pre-pass
78 ;;; Convert TN (currently local) to be a global TN, since we
79 ;;; discovered that it is referenced in more than one block. We just
80 ;;; add a global-conflicts structure with a kind derived from the KILL
81 ;;; and LIVE sets.
93 tn block num))
96 ;;; Scan all references to packed TNs in block. We assign LTN numbers
97 ;;; to each referenced TN, and also build the Kill and Live sets that
98 ;;; summarize the references to each TN for purposes of lifetime
99 ;;; analysis.
100 ;;;
101 ;;; It is possible that we will run out of LTN numbers. If this
102 ;;; happens, then we return the VOP that we were processing at the
103 ;;; time we ran out, otherwise we return NIL.
104 ;;;
105 ;;; If a TN is referenced in more than one block, then we must
106 ;;; represent references using GLOBAL-CONFLICTS structures. When we
107 ;;; first see a TN, we assume it will be local. If we see a reference
108 ;;; later on in a different block, then we go back and fix the TN to
109 ;;; global.
110 ;;;
111 ;;; We must globalize TNs that have a block other than the current one
112 ;;; in their LOCAL slot and have no GLOBAL-CONFLICTS. The latter
113 ;;; condition is necessary because we always set Local and
114 ;;; LOCAL-NUMBER when we process a reference to a TN, even when the TN
115 ;;; is already known to be global.
116 ;;;
117 ;;; When we see reference to global TNs during the scan, we add the
118 ;;; global-conflict as :READ-ONLY, since we don't know the correct
119 ;;; kind until we are done scanning the block.
154 nil)
156 ;;; Finish up the global conflicts for TNs referenced in BLOCK
157 ;;; according to the local Kill and Live sets.
158 ;;;
159 ;;; We set the kind for TNs already in the global-TNs. If not written
160 ;;; at all, then is :READ-ONLY, the default. Must have been referenced
161 ;;; somehow, or we wouldn't have conflicts for it.
162 ;;;
163 ;;; We also iterate over all the local TNs, looking for TNs local to
164 ;;; this block that are still live at the block beginning, and thus
165 ;;; must be global. This case is only important when a TN is read in a
166 ;;; block but not written in any other, since otherwise the write
167 ;;; would promote the TN to global. But this does happen with various
168 ;;; passing-location TNs that are magically written. This also serves
169 ;;; to propagate the lives of erroneously uninitialized TNs so that
170 ;;; consistency checks can detect them.
182 :write
197 ;;; Move the code after the VOP LOSE in 2BLOCK into its own block. The
198 ;;; block is linked into the emit order following 2BLOCK. NUMBER is
199 ;;; the block number assigned to the new block. We return the new
200 ;;; block.
220 new))
222 ;;; Clear the global and local conflict info in BLOCK so that we can
223 ;;; recompute it without any old cruft being retained. It is assumed
224 ;;; that all LTN numbers are in use.
225 ;;;
226 ;;; First we delete all the global conflicts. The conflict we are
227 ;;; deleting must be the last in the TN's GLOBAL-CONFLICTS, but we
228 ;;; must scan for it in order to find the previous conflict.
229 ;;;
230 ;;; Next, we scan the local TNs, nulling out the LOCAL slot in all TNs
231 ;;; with no global conflicts. This allows these TNs to be treated as
232 ;;; local when we scan the block again.
233 ;;;
234 ;;; If there are conflicts, then we set LOCAL to one of the
235 ;;; conflicting blocks. This ensures that LOCAL doesn't hold over
236 ;;; BLOCK as its value, causing the subsequent reanalysis to think
237 ;;; that the TN has already been seen in that block.
238 ;;;
239 ;;; This function must not be called on blocks that have :MORE TNs.
269 nil))))))
273 ;;; This provides a panic mode for assigning LTN numbers when there is
274 ;;; a VOP with so many more operands that they can't all be assigned
275 ;;; distinct numbers. When this happens, we recover by assigning all
276 ;;; the &MORE operands the same LTN number. We can get away with this,
277 ;;; since all &MORE args (and results) are referenced simultaneously
278 ;;; as far as conflict analysis is concerned.
279 ;;;
280 ;;; BLOCK is the IR2-BLOCK that the MORE VOP is at the end of. OPS is
281 ;;; the full argument or result TN-REF list. Fixed is the types of the
282 ;;; fixed operands (used only to skip those operands.)
283 ;;;
284 ;;; What we do is grab a LTN number, then make a :READ-ONLY global
285 ;;; conflict for each more operand TN. We require that there be no
286 ;;; existing global conflict in BLOCK for any of the operands. Since
287 ;;; conflicts must be cleared before the first call, this only
288 ;;; prohibits the same TN being used both as a more operand and as any
289 ;;; other operand to the same VOP.
290 ;;;
291 ;;; We don't have to worry about getting the correct conflict kind,
292 ;;; since INIT-GLOBAL-CONFLICT-KIND will fix things up. Similarly,
293 ;;; FIND-LOCAL-REFERENCES will set the local conflict bit
294 ;;; corresponding to this call.
295 ;;;
296 ;;; We also set the LOCAL and LOCAL-NUMBER slots in each TN. It is
297 ;;; possible that there are no operands in any given call to this
298 ;;; function, but there had better be either some more args or more
299 ;;; results.
335 ;;; Loop over the blocks in COMPONENT, assigning LTN numbers and
336 ;;; recording TN birth and death. The only interesting action is when
337 ;;; we run out of local TN numbers while finding local references.
338 ;;;
339 ;;; If we run out of LTN numbers while processing a VOP within the
340 ;;; block, then we just split off the VOPs we have successfully
341 ;;; processed into their own block.
342 ;;;
343 ;;; If we run out of LTN numbers while processing the our first VOP
344 ;;; (the last in the block), then it must be the case that this VOP
345 ;;; has large more operands. We split the VOP into its own block, and
346 ;;; then call COALESCE-MORE-LTN-NUMBERS to assign all the more
347 ;;; args/results the same LTN number(s).
348 ;;;
349 ;;; In either case, we clear the lifetime information that we computed
350 ;;; so far, recomputing it after taking corrective action.
351 ;;;
352 ;;; Whenever we split a block, we finish the pre-pass on the split-off
353 ;;; block by doing FIND-LOCAL-REFERENCES and
354 ;;; INIT-GLOBAL-CONFLICT-KIND. This can't run out of LTN numbers.
395 \f
396 ;;;; environment TN stuff
398 ;;; Add a :LIVE global conflict for TN in 2BLOCK if there is none
399 ;;; present. If DEBUG-P is false (a :ENVIRONMENT TN), then modify any
400 ;;; existing conflict to be :LIVE.
416 nil)
422 ;;; Return true if TN represents a closed-over variable with an
423 ;;; "implicit" value-cell.
430 ;;; If BLOCK ends with a TAIL LOCAL COMBINATION, the function called.
431 ;;; Otherwise, NIL.
439 ;;; Iterate over all the blocks in ENV, setting up :LIVE conflicts for
440 ;;; TN. We make the TN global if it isn't already. The TN must have at
441 ;;; least one reference.
445 ;; Prevent infinite recursion due to recursive tail calls.
458 prev))))
462 ;; If BLOCK ends with a TAIL LOCAL COMBINATION and TN is an
463 ;; "implicit value cell" then setup conflicts for the callee
464 ;; function as well.
472 ;;; Iterate over all the environment TNs, adding always-live conflicts
473 ;;; as appropriate.
485 ;;; Convert a :NORMAL or :DEBUG-ENVIRONMENT TN to an :ENVIRONMENT TN.
486 ;;; This requires adding :LIVE conflicts to all blocks in TN-PHYSENV.
491 (:debug-environment
496 (:normal
504 \f
505 ;;;; flow analysis
507 ;;; For each GLOBAL-TN in BLOCK2 that is :LIVE, :READ or :READ-ONLY,
508 ;;; ensure that there is a corresponding GLOBAL-CONFLICT in BLOCK1. If
509 ;;; there is none, make a :LIVE GLOBAL-CONFLICT. If there is a
510 ;;; :READ-ONLY conflict, promote it to :LIVE.
511 ;;;
512 ;;; If we did add a new conflict, return true, otherwise false. We
513 ;;; don't need to return true when we promote a :READ-ONLY conflict,
514 ;;; since it doesn't reveal any new information to predecessors of
515 ;;; BLOCK1.
516 ;;;
517 ;;; We use the TN-CURRENT-CONFLICT to walk through the global
518 ;;; conflicts. Since the global conflicts for a TN are ordered by
519 ;;; block, we can be sure that the CURRENT-CONFLICT always points at
520 ;;; or before the block that we are looking at. This allows us to
521 ;;; quickly determine if there is a global conflict for a given TN in
522 ;;; BLOCK1.
523 ;;;
524 ;;; When we scan down the conflicts, we know that there must be at
525 ;;; least one conflict for TN, since we got our hands on TN by picking
526 ;;; it out of a conflict in BLOCK2.
527 ;;;
528 ;;; We leave the CURRENT-CONFLICT pointing to the conflict for BLOCK1.
529 ;;; The CURRENT-CONFLICT must be initialized to the head of the
530 ;;; GLOBAL-CONFLICTS for the TN between each flow analysis iteration.
532 ;;; FASTP is a KLUDGE: SBCL used to update the current-conflict only
533 ;;; for the read-only case, but switched at one point to always
534 ;;; updating it. This generally speeds up the compiler nicely, but
535 ;;; sometimes it causes an infinite loop in the updating machinery,
536 ;;; We cheat by switching off the fast path if it seems we're looping
537 ;;; longer then expected.
552 number1)
553 ;; The TN-CURRENT-CONFLICT finger overshot. Reset it
554 ;; conservatively.
562 number1))
569 (:read-only
573 nil)
583 did-something))
585 ;;; Do backward global flow analysis to find all TNs live at each
586 ;;; block boundary.
589 ;; KLUDGE: This is the second part of the FASTP kludge in
590 ;; propagate-live-tns: we pass fastp for ten first attempts,
591 ;; and then switch to the works-for-sure version.
592 ;;
593 ;; The upstream uses the fast version always, but sometimes
594 ;; that gets stuck in a loop...
596 do
604 prev))))
623 \f
624 ;;;; post-pass
626 ;;; Note that TN conflicts with all current live TNs. NUM is TN's LTN
627 ;;; number. We bit-ior LIVE-BITS with TN's LOCAL-CONFLICTS, and set TN's
628 ;;; number in the conflicts of all TNs in LIVE-LIST.
640 ;;; Compute a bit vector of the TNs live after VOP that aren't results.
651 live))
653 ;;; This is used to determine whether a :DEBUG-ENVIRONMENT TN should
654 ;;; be considered live at block end. We return true if a VOP with
655 ;;; non-null SAVE-P appears before the first read of TN (hence is seen
656 ;;; first in our backward scan.)
664 ;;; If the block has no successors, or its successor is the component
665 ;;; tail, then all :DEBUG-ENVIRONMENT TNs are always added, regardless
666 ;;; of whether they appeared to be live. This ensures that these TNs
667 ;;; are considered to be live throughout blocks that read them, but
668 ;;; don't have any interesting successors (such as a return or tail
669 ;;; call.) In this case, we set the corresponding bit in LIVE-IN as
670 ;;; well.
698 ;;; Return as values, a LTN bit-vector and a list (threaded by
699 ;;; TN-NEXT*) representing the TNs live at the end of BLOCK (exclusive
700 ;;; of :LIVE TNs).
701 ;;;
702 ;;; We iterate over the TNs in the global conflicts that are live at
703 ;;; the block end, setting up the TN-LOCAL-CONFLICTS and
704 ;;; TN-LOCAL-NUMBER, and adding the TN to the live list.
705 ;;;
706 ;;; If a :MORE result is not live, we effectively fake a read to it.
707 ;;; This is part of the action described in ENSURE-RESULTS-LIVE.
708 ;;;
709 ;;; At the end, we call MAKE-DEBUG-ENVIRONEMNT-TNS-LIVE to make debug
710 ;;; environment TNs appear live when appropriate, even when they
711 ;;; aren't.
712 ;;;
713 ;;; ### Note: we alias the global-conflicts-conflicts here as the
714 ;;; tn-local-conflicts.
746 ;;; A function called in CONFLICT-ANALYZE-1-BLOCK when we have a VOP
747 ;;; with SAVE-P true. We compute the save-set, and if :FORCE-TO-STACK,
748 ;;; force all the live TNs to be stack environment TNs.
760 tn
764 ;;; FIXME: The next 3 macros aren't needed in the target runtime.
765 ;;; Figure out some way to make them only at build time. (Just
766 ;;; (EVAL-WHEN (:COMPILE-TOPLEVEL :EXECUTE) (DEFMACRO ..)) isn't good enough,
767 ;;; since we need CL:DEFMACRO at build-the-cross-compiler time and
768 ;;; SB!XC:DEFMACRO at run-the-cross-compiler time.)
770 ;;; This is used in SCAN-VOP-REFS to simultaneously do something to
771 ;;; all of the TNs referenced by a big more arg. We have to treat
772 ;;; these TNs specially, since when we set or clear the bit in the
773 ;;; live TNs, the represents a change in the liveness of all the more
774 ;;; TNs. If we iterated as normal, the next more ref would be thought
775 ;;; to be not live when it was, etc. We update Ref to be the last
776 ;;; :more ref we scanned, so that the main loop will step to the next
777 ;;; non-more ref.
790 ;;; Handle the part of CONFLICT-ANALYZE-1-BLOCK that scans the REFs
791 ;;; for the current VOP. This macro shamelessly references free
792 ;;; variables in C-A-1-B.
813 ;;; This macro is called by CONFLICT-ANALYZE-1-BLOCK to scan the
814 ;;; current VOP's results, and make any dead ones live. This is
815 ;;; necessary, since even though a result is dead after the VOP, it
816 ;;; may be in use for an extended period within the VOP (especially if
817 ;;; it has :FROM specified.) During this interval, temporaries must be
818 ;;; noted to conflict with the result. More results are finessed in
819 ;;; COMPUTE-INITIAL-CONFLICTS, so we ignore them here.
831 ;;; Compute the block-local conflict information for BLOCK. We iterate
832 ;;; over all the TN-REFs in a block in reference order, maintaining
833 ;;; the set of live TNs in both a list and a bit-vector
834 ;;; representation.
848 ;;; Conflict analyze each block, and also add it.
853 \f
854 ;;;; alias TN stuff
856 ;;; Destructively modify OCONF to include the conflict information in CONF.
874 ;; Make original conflict with all the local TNs the alias
875 ;; conflicted with.
878 t)
882 ;; Make all the local TNs that conflicted with the alias
883 ;; conflict with the original.
889 ;; Same for global TNs...
895 ;; Make the original TN live everywhere that the alias was live.
904 ;; Delete the alias's conflict info.
909 conf))
913 ;;; Co-opt CONF to be a conflict for TN.
921 conf)
928 ;;; Do CONVERT-TO-GLOBAL on TN if it has no global conflicts. Copy the
929 ;;; local conflicts into the global bit vector.
937 t))
942 ;;; For each :ALIAS TN, destructively merge the conflict info into the
943 ;;; original TN and replace the uses of the alias.
944 ;;;
945 ;;; For any block that uses only the alias TN, just insert that
946 ;;; conflict into the conflicts for the original TN, changing the LTN
947 ;;; map to refer to the original TN. This gives a result
948 ;;; indistinguishable from the what there would have been if the
949 ;;; original TN had always been referenced. This leaves no sign that
950 ;;; an alias TN was ever involved.
951 ;;;
952 ;;; If a block has references to both the alias and the original TN,
953 ;;; then we call MERGE-ALIAS-BLOCK-CONFLICTS to combine the conflicts
954 ;;; into the original conflict.
987 conf
989 oconf))
1010 ;;; On high debug levels, for all variables that a lambda closes over
1011 ;;; convert the TNs to :ENVIRONMENT TNs (in the physical environment
1012 ;;; of that lambda). This way the debugger can display the variables.
1022 \f
1030 \f
1031 ;;;; conflict testing
1033 ;;; Test for a conflict between the local TN X and the global TN Y. We
1034 ;;; just look for a global conflict of Y in X's block, and then test
1035 ;;; for conflict in that block.
1036 ;;;
1037 ;;; [### Might be more efficient to scan Y's global conflicts. This
1038 ;;; depends on whether there are more global TNs than blocks.]
1048 num))))))))))
1050 ;;; Test for conflict between two global TNs X and Y.
1069 ;; x-conf, y-conf true, x-num, y-num corresponding block numbers.
1077 ltn-num-x)))
1082 ;;; Return true if X and Y are distinct and the lifetimes of X and Y
1083 ;;; overlap at any point.