| blob | 10a17684bbbcaed898fb8cc8009a2c7ebf94e532 |
1 ;;;; This file implements the copy propagation phase of the compiler,
2 ;;;; which uses global flow analysis to eliminate unnecessary copying
3 ;;;; of variables.
5 ;;;; This software is part of the SBCL system. See the README file for
6 ;;;; more information.
7 ;;;;
8 ;;;; This software is derived from the CMU CL system, which was
9 ;;;; written at Carnegie Mellon University and released into the
10 ;;;; public domain. The software is in the public domain and is
11 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
12 ;;;; files for more information.
16 ;;; In copy propagation, we manipulate sets of TNs. We only consider
17 ;;; TNs whose sole write is by a MOVE VOP. This allows us to use a
18 ;;; degenerate version of reaching definitions: since each such TN has
19 ;;; only one definition, the TN can stand for the definition. We can
20 ;;; get away with this simplification, since the TNs that would be
21 ;;; subject to copy propagation are nearly always single-writer
22 ;;; (mostly temps allocated to ensure evaluation order is perserved).
23 ;;; Only TNs written by MOVEs are interesting, since all we do with
24 ;;; this information is delete spurious MOVEs.
25 ;;;
26 ;;; There are additional semantic constraints on whether a TN can be
27 ;;; considered to be a copy. See TN-IS-A-COPY-OF.
28 ;;;
29 ;;; If a TN is in the IN set for a block, that TN is a copy of a TN
30 ;;; which still has the same value it had at the time the move was
31 ;;; done. Any reference to a TN in the IN set can be replaced with a
32 ;;; reference to the TN moved from. When we delete all reads of such a
33 ;;; TN, we can delete the MOVE VOP. IN is computed as the intersection
34 ;;; of OUT for all the predecessor blocks.
35 ;;;
36 ;;; In this flow analysis scheme, the KILL set is the set of all
37 ;;; interesting TNs where the copied TN is modified by the block (in
38 ;;; any way.)
39 ;;;
40 ;;; GEN is the set of all interesting TNs that are copied in the block
41 ;;; (whose write appears in the block.)
42 ;;;
43 ;;; OUT is (union (difference IN KILL) GEN)
45 ;;; If TN is subject to copy propagation, then return the TN it is a copy
46 ;;; of, otherwise NIL.
47 ;;;
48 ;;; We also only consider TNs where neither the TN nor the copied TN
49 ;;; are wired or restricted. If we extended the life of a wired or
50 ;;; restricted TN, register allocation might fail, and we can't
51 ;;; substitute arbitrary things for references to wired or restricted
52 ;;; TNs, since the reader may be expencting the argument to be in a
53 ;;; particular place (as in a passing location.)
54 ;;;
55 ;;; The TN must be a :NORMAL TN. Other TNs might have hidden
56 ;;; references or be otherwise bizarre.
57 ;;;
58 ;;; A TN is also inelegible if we want to preserve it to facilitate
59 ;;; debugging.
60 ;;;
61 ;;; The SCs of the TN's primitive types is a subset of the SCs of the
62 ;;; copied TN. Moves between TNs of different primitive type SCs may
63 ;;; need to be changed into coercions, so we can't squeeze them out.
64 ;;; The reason for testing for subset of the SCs instead of the same
65 ;;; primitive type is that this test lets T be substituted for LIST,
66 ;;; POSITIVE-FIXNUM for FIXNUM, etc. Note that more SCs implies fewer
67 ;;; possible values, or a subtype relationship, since more SCs implies
68 ;;; more possible representations.
88 ;; Do we not care about preserving this this
89 ;; TN for debugging?
94 ;; arguments of local functions have hidden write
98 arg-tn)))))))
100 ;;; Init the sets in BLOCK for copy propagation. To find GEN, we just
101 ;;; look for MOVE vops, and then see whether the result is a eligible
102 ;;; copy TN. To find KILL, we must look at all VOP results, seeing
103 ;;; whether any of the reads of the written TN are copies for eligible
104 ;;; TNs.
115 t)))
116 ;; WANTED: explanation of UNLESS above.
133 ;;; Do the flow analysis step for copy propagation on BLOCK. We rely
134 ;;; on OUT being initialized to GEN, and use SSET-UNION-OF-DIFFERENCE
135 ;;; to incrementally build the union in OUT, rather than replacing OUT
136 ;;; each time.
145 in
150 ;;; Return true if ARG is a reference to a TN that we can copy
151 ;;; propagate to. In addition to dealing with copy chains (as
152 ;;; discussed below), we also discard references that are arguments
153 ;;; to a local call, since IR2tran introduces temps in that context
154 ;;; to preserve parallel assignment semantics.
171 ;;; Make use of the result of flow analysis to eliminate copies. We
172 ;;; scan the VOPs in block, propagating copies and keeping our IN set
173 ;;; in sync.
174 ;;;
175 ;;; Original-Copy-Of is an EQ hash table that we use to keep track of
176 ;;; renamings when there are copy chains, i.e. copies of copies. When
177 ;;; we see copy of a copy, we enter the first copy in the table with
178 ;;; the second copy as a key. When we see a reference to a TN in a
179 ;;; copy chain, we can only substitute the first copied TN for the
180 ;;; reference when all intervening copies in the copy chain are also
181 ;;; available. Otherwise, we just leave the reference alone. It is
182 ;;; possible that we might have been able to reference one of the
183 ;;; intermediate copies instead, but that copy might have already been
184 ;;; deleted, since we delete the move immediately when the references
185 ;;; go to zero.
186 ;;;
187 ;;; To understand why we always can to the substitution when the copy
188 ;;; chain recorded in the Original-Copy-Of table hits NIL, note that
189 ;;; we make an entry in the table iff we change the arg of a copy. If
190 ;;; an entry is not in the table, it must be that we hit a move which
191 ;;; *originally* referenced our Copy-Of TN. If all the intervening
192 ;;; copies reach our reference, then Copy-Of must reach the reference.
193 ;;;
194 ;;; Note that due to our restricting copies to single-writer TNs, it
195 ;;; will always be the case that when the first copy in a chain
196 ;;; reaches the reference, all intervening copies reach also reach the
197 ;;; reference. We don't exploit this, since we have to work backward
198 ;;; from the last copy.
199 ;;;
200 ;;; In this discussion, we are really only playing with the tail of
201 ;;; the true copy chain for which all of the copies have already had
202 ;;; PROPAGATE-COPIES done on them. But, because we do this pass in
203 ;;; DFO, it is virtually always the case that we will process earlier
204 ;;; copies before later ones. In perverse cases (non-reducible flow
205 ;;; graphs), we just miss some optimization opportinities.
214 ;; Substitute copied TN for copy when we find a reference to a copy.
215 ;; If the copy is left with no reads, delete the move to the copy.
227 ;; Kill any elements in IN that are copies of a TN we are clobbering.
233 ;; If this VOP is a copy, add the copy TN to IN.
238 ;;; Do copy propagation on COMPONENT by initializing the flow analysis
239 ;;; sets, doing flow analysis, and then propagating copies using the
240 ;;; results.