Lines Matching refs:live
27 convergence, delayed phi lowering, and local live range splitting).
54 begins the live range of the dest Variable, and may end the live range of one
60 - Liveness analysis and live range construction are prerequisites for register
75 - We also enhance it to allow overlapping live ranges to share the same
89 assigments, which create spurious interferences in live ranges.
91 - Within each basic block, we aggressively split each variable's live range at
92 every use, so that portions of the live range can get registers even if the
93 whole live range can't. Doing this separately for each basic block avoids
101 calculate the live range of each variable. The live range is represented as a
110 block, we keep track of the live-in and live-out set, i.e. the set of variables
111 that are live coming into or going out of the basic block. Processing of a
112 basic block starts by initializing a temporary set as the union of the live-in
113 sets of the basic block's successor blocks. (This basic block's live-out set is
116 instruction are marked as live, by adding them to the temporary set, and the
117 dest variable of the instruction (if any) is marked as not-live, by removing it
119 instructions, we add/union the temporary set into the basic block's live-in set.
120 If this changes the basic block's live-in set, then we mark all of this basic
127 The result of this pass is the live-in and live-out set for each basic block.
137 the vast majority of variables are referenced, and therefore live, only in a
143 live-in and live-out bit vectors is limited to the number of multi-block
147 For the purpose of live range construction, we also need to track definitions
155 After the live-in and live-out sets are calculated, we construct each variable's
156 live range (as an ordered list of instruction ranges, described above). We do
157 this by considering the live-in and live-out sets, combined with LiveBegin and
164 The basic liveness pass, described above, keeps track of when a variable's live
167 representing that the particular variable's live range begins or ends at the
168 particular instruction. When the liveness pass finds a variable whose live
171 During live range construction, the LiveBegin and LiveEnd vectors are sorted by
173 variable appears in both LiveBegin and LiveEnd, then its live range is entirely
174 within this block. If it appears in only LiveBegin, then its live range starts
176 then its live range starts at the beginning of the block and ends here. (Note
177 that this only covers the live range within this block, and this process is
180 It is also possible that a variable is live within this block but its live range
182 taking the intersection of the live-in and live-out sets.
184 As a result of these data structures, performance of liveness analysis and live
195 <ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF>`_. It allows live ranges to
222 with source variables ``S1,S2,...``, and that instruction ends the live range of
242 In many cases, the program variable and temporary variable have overlapping live
246 variable's live range, and the temporary variable has no definitions within the
247 program variable's live range with the exception of the copy assignment.
280 performance, as the bulk of the cost ends up being in live range overlap
315 A = phi(B) // B's live range ends here
316 C = phi(D) // D's live range ends here
320 A = B // end of B's live range
321 C = D // end of D's live range
323 The potential problem here is that A and D's live ranges overlap, and so they
348 variable's live range, and actively spill/restore that register around the live
353 Local live range splitting
357 a register for its entire live range, or not at all. This is unfortunate when a
358 variable has many uses close together, but ultimately a large enough live range
362 from having a register when their live ranges contain a call instruction.
364 The general solution here is some policy for splitting live ranges. A variable
387 instructions. The live ranges of these copies are usually much smaller, and
395 First, for register allocation, the cost tends to be dominated by live range
396 overlap computations, whose cost is roughly proportional to the size of the live
397 range. All the new variable copies' live ranges sum up to the original
398 variable's live range, so the cost isn't vastly greater.