/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveIntervals.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LiveIntervals.cpp - Live Interval Analysis -------------------------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | /// \file This file implements the LiveInterval analysis pass which is used |
10 | | /// by the Linear Scan Register allocator. This pass linearizes the |
11 | | /// basic blocks of the function in DFS order and computes live intervals for |
12 | | /// each virtual and physical register. |
13 | | // |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #include "llvm/CodeGen/LiveIntervals.h" |
17 | | #include "LiveRangeCalc.h" |
18 | | #include "llvm/ADT/ArrayRef.h" |
19 | | #include "llvm/ADT/DepthFirstIterator.h" |
20 | | #include "llvm/ADT/SmallPtrSet.h" |
21 | | #include "llvm/ADT/SmallVector.h" |
22 | | #include "llvm/ADT/iterator_range.h" |
23 | | #include "llvm/Analysis/AliasAnalysis.h" |
24 | | #include "llvm/CodeGen/LiveInterval.h" |
25 | | #include "llvm/CodeGen/LiveVariables.h" |
26 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
27 | | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
28 | | #include "llvm/CodeGen/MachineDominators.h" |
29 | | #include "llvm/CodeGen/MachineFunction.h" |
30 | | #include "llvm/CodeGen/MachineInstr.h" |
31 | | #include "llvm/CodeGen/MachineInstrBundle.h" |
32 | | #include "llvm/CodeGen/MachineOperand.h" |
33 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
34 | | #include "llvm/CodeGen/Passes.h" |
35 | | #include "llvm/CodeGen/SlotIndexes.h" |
36 | | #include "llvm/CodeGen/TargetRegisterInfo.h" |
37 | | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
38 | | #include "llvm/CodeGen/VirtRegMap.h" |
39 | | #include "llvm/Config/llvm-config.h" |
40 | | #include "llvm/MC/LaneBitmask.h" |
41 | | #include "llvm/MC/MCRegisterInfo.h" |
42 | | #include "llvm/Pass.h" |
43 | | #include "llvm/Support/BlockFrequency.h" |
44 | | #include "llvm/Support/CommandLine.h" |
45 | | #include "llvm/Support/Compiler.h" |
46 | | #include "llvm/Support/Debug.h" |
47 | | #include "llvm/Support/MathExtras.h" |
48 | | #include "llvm/Support/raw_ostream.h" |
49 | | #include <algorithm> |
50 | | #include <cassert> |
51 | | #include <cstdint> |
52 | | #include <iterator> |
53 | | #include <tuple> |
54 | | #include <utility> |
55 | | |
56 | | using namespace llvm; |
57 | | |
58 | | #define DEBUG_TYPE "regalloc" |
59 | | |
60 | | char LiveIntervals::ID = 0; |
61 | | char &llvm::LiveIntervalsID = LiveIntervals::ID; |
62 | 102k | INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", |
63 | 102k | "Live Interval Analysis", false, false) |
64 | 102k | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
65 | 102k | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
66 | 102k | INITIALIZE_PASS_DEPENDENCY(SlotIndexes) |
67 | 102k | INITIALIZE_PASS_END(LiveIntervals, "liveintervals", |
68 | | "Live Interval Analysis", false, false) |
69 | | |
70 | | #ifndef NDEBUG |
71 | | static cl::opt<bool> EnablePrecomputePhysRegs( |
72 | | "precompute-phys-liveness", cl::Hidden, |
73 | | cl::desc("Eagerly compute live intervals for all physreg units.")); |
74 | | #else |
75 | | static bool EnablePrecomputePhysRegs = false; |
76 | | #endif // NDEBUG |
77 | | |
78 | | namespace llvm { |
79 | | |
80 | | cl::opt<bool> UseSegmentSetForPhysRegs( |
81 | | "use-segment-set-for-physregs", cl::Hidden, cl::init(true), |
82 | | cl::desc( |
83 | | "Use segment set for the computation of the live ranges of physregs.")); |
84 | | |
85 | | } // end namespace llvm |
86 | | |
87 | 42.9k | void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { |
88 | 42.9k | AU.setPreservesCFG(); |
89 | 42.9k | AU.addRequired<AAResultsWrapperPass>(); |
90 | 42.9k | AU.addPreserved<AAResultsWrapperPass>(); |
91 | 42.9k | AU.addPreserved<LiveVariables>(); |
92 | 42.9k | AU.addPreservedID(MachineLoopInfoID); |
93 | 42.9k | AU.addRequiredTransitiveID(MachineDominatorsID); |
94 | 42.9k | AU.addPreservedID(MachineDominatorsID); |
95 | 42.9k | AU.addPreserved<SlotIndexes>(); |
96 | 42.9k | AU.addRequiredTransitive<SlotIndexes>(); |
97 | 42.9k | MachineFunctionPass::getAnalysisUsage(AU); |
98 | 42.9k | } |
99 | | |
100 | 42.9k | LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) { |
101 | 42.9k | initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); |
102 | 42.9k | } |
103 | | |
104 | 42.7k | LiveIntervals::~LiveIntervals() { |
105 | 42.7k | delete LRCalc; |
106 | 42.7k | } |
107 | | |
108 | 564k | void LiveIntervals::releaseMemory() { |
109 | 564k | // Free the live intervals themselves. |
110 | 21.2M | for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i20.6M ) |
111 | 20.6M | delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; |
112 | 564k | VirtRegIntervals.clear(); |
113 | 564k | RegMaskSlots.clear(); |
114 | 564k | RegMaskBits.clear(); |
115 | 564k | RegMaskBlocks.clear(); |
116 | 564k | |
117 | 564k | for (LiveRange *LR : RegUnitRanges) |
118 | 120M | delete LR; |
119 | 564k | RegUnitRanges.clear(); |
120 | 564k | |
121 | 564k | // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. |
122 | 564k | VNInfoAllocator.Reset(); |
123 | 564k | } |
124 | | |
125 | 564k | bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { |
126 | 564k | MF = &fn; |
127 | 564k | MRI = &MF->getRegInfo(); |
128 | 564k | TRI = MF->getSubtarget().getRegisterInfo(); |
129 | 564k | TII = MF->getSubtarget().getInstrInfo(); |
130 | 564k | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
131 | 564k | Indexes = &getAnalysis<SlotIndexes>(); |
132 | 564k | DomTree = &getAnalysis<MachineDominatorTree>(); |
133 | 564k | |
134 | 564k | if (!LRCalc) |
135 | 40.6k | LRCalc = new LiveRangeCalc(); |
136 | 564k | |
137 | 564k | // Allocate space for all virtual registers. |
138 | 564k | VirtRegIntervals.resize(MRI->getNumVirtRegs()); |
139 | 564k | |
140 | 564k | computeVirtRegs(); |
141 | 564k | computeRegMasks(); |
142 | 564k | computeLiveInRegUnits(); |
143 | 564k | |
144 | 564k | if (EnablePrecomputePhysRegs) { |
145 | 0 | // For stress testing, precompute live ranges of all physical register |
146 | 0 | // units, including reserved registers. |
147 | 0 | for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) |
148 | 0 | getRegUnit(i); |
149 | 0 | } |
150 | 564k | LLVM_DEBUG(dump()); |
151 | 564k | return true; |
152 | 564k | } |
153 | | |
154 | 2 | void LiveIntervals::print(raw_ostream &OS, const Module* ) const { |
155 | 2 | OS << "********** INTERVALS **********\n"; |
156 | 2 | |
157 | 2 | // Dump the regunits. |
158 | 256 | for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit254 ) |
159 | 254 | if (LiveRange *LR = RegUnitRanges[Unit]) |
160 | 0 | OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n'; |
161 | 2 | |
162 | 2 | // Dump the virtregs. |
163 | 8 | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i6 ) { |
164 | 6 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
165 | 6 | if (hasInterval(Reg)) |
166 | 6 | OS << getInterval(Reg) << '\n'; |
167 | 6 | } |
168 | 2 | |
169 | 2 | OS << "RegMasks:"; |
170 | 2 | for (SlotIndex Idx : RegMaskSlots) |
171 | 0 | OS << ' ' << Idx; |
172 | 2 | OS << '\n'; |
173 | 2 | |
174 | 2 | printInstrs(OS); |
175 | 2 | } |
176 | | |
177 | 2 | void LiveIntervals::printInstrs(raw_ostream &OS) const { |
178 | 2 | OS << "********** MACHINEINSTRS **********\n"; |
179 | 2 | MF->print(OS, Indexes); |
180 | 2 | } |
181 | | |
182 | | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
183 | | LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const { |
184 | | printInstrs(dbgs()); |
185 | | } |
186 | | #endif |
187 | | |
188 | 13.4M | LiveInterval* LiveIntervals::createInterval(unsigned reg) { |
189 | 13.4M | float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf0 : 0.0F; |
190 | 13.4M | return new LiveInterval(reg, Weight); |
191 | 13.4M | } |
192 | | |
193 | | /// Compute the live interval of a virtual register, based on defs and uses. |
194 | 12.8M | void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { |
195 | 12.8M | assert(LRCalc && "LRCalc not initialized."); |
196 | 12.8M | assert(LI.empty() && "Should only compute empty intervals."); |
197 | 12.8M | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
198 | 12.8M | LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); |
199 | 12.8M | computeDeadValues(LI, nullptr); |
200 | 12.8M | } |
201 | | |
202 | 564k | void LiveIntervals::computeVirtRegs() { |
203 | 20.2M | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i19.6M ) { |
204 | 19.6M | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
205 | 19.6M | if (MRI->reg_nodbg_empty(Reg)) |
206 | 7.20M | continue; |
207 | 12.4M | createAndComputeVirtRegInterval(Reg); |
208 | 12.4M | } |
209 | 564k | } |
210 | | |
211 | 564k | void LiveIntervals::computeRegMasks() { |
212 | 564k | RegMaskBlocks.resize(MF->getNumBlockIDs()); |
213 | 564k | |
214 | 564k | // Find all instructions with regmask operands. |
215 | 2.92M | for (const MachineBasicBlock &MBB : *MF) { |
216 | 2.92M | std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()]; |
217 | 2.92M | RMB.first = RegMaskSlots.size(); |
218 | 2.92M | |
219 | 2.92M | // Some block starts, such as EH funclets, create masks. |
220 | 2.92M | if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { |
221 | 131 | RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); |
222 | 131 | RegMaskBits.push_back(Mask); |
223 | 131 | } |
224 | 2.92M | |
225 | 27.3M | for (const MachineInstr &MI : MBB) { |
226 | 86.1M | for (const MachineOperand &MO : MI.operands()) { |
227 | 86.1M | if (!MO.isRegMask()) |
228 | 84.6M | continue; |
229 | 1.51M | RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); |
230 | 1.51M | RegMaskBits.push_back(MO.getRegMask()); |
231 | 1.51M | } |
232 | 27.3M | } |
233 | 2.92M | |
234 | 2.92M | // Some block ends, such as funclet returns, create masks. Put the mask on |
235 | 2.92M | // the last instruction of the block, because MBB slot index intervals are |
236 | 2.92M | // half-open. |
237 | 2.92M | if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { |
238 | 82 | assert(!MBB.empty() && "empty return block?"); |
239 | 82 | RegMaskSlots.push_back( |
240 | 82 | Indexes->getInstructionIndex(MBB.back()).getRegSlot()); |
241 | 82 | RegMaskBits.push_back(Mask); |
242 | 82 | } |
243 | 2.92M | |
244 | 2.92M | // Compute the number of register mask instructions in this block. |
245 | 2.92M | RMB.second = RegMaskSlots.size() - RMB.first; |
246 | 2.92M | } |
247 | 564k | } |
248 | | |
249 | | //===----------------------------------------------------------------------===// |
250 | | // Register Unit Liveness |
251 | | //===----------------------------------------------------------------------===// |
252 | | // |
253 | | // Fixed interference typically comes from ABI boundaries: Function arguments |
254 | | // and return values are passed in fixed registers, and so are exception |
255 | | // pointers entering landing pads. Certain instructions require values to be |
256 | | // present in specific registers. That is also represented through fixed |
257 | | // interference. |
258 | | // |
259 | | |
260 | | /// Compute the live range of a register unit, based on the uses and defs of |
261 | | /// aliasing registers. The range should be empty, or contain only dead |
262 | | /// phi-defs from ABI blocks. |
263 | 4.28M | void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { |
264 | 4.28M | assert(LRCalc && "LRCalc not initialized."); |
265 | 4.28M | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
266 | 4.28M | |
267 | 4.28M | // The physregs aliasing Unit are the roots and their super-registers. |
268 | 4.28M | // Create all values as dead defs before extending to uses. Note that roots |
269 | 4.28M | // may share super-registers. That's OK because createDeadDefs() is |
270 | 4.28M | // idempotent. It is very rare for a register unit to have multiple roots, so |
271 | 4.28M | // uniquing super-registers is probably not worthwhile. |
272 | 4.28M | bool IsReserved = false; |
273 | 8.57M | for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root4.28M ) { |
274 | 4.28M | bool IsRootReserved = true; |
275 | 4.28M | for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); |
276 | 32.5M | Super.isValid(); ++Super28.2M ) { |
277 | 28.2M | unsigned Reg = *Super; |
278 | 28.2M | if (!MRI->reg_empty(Reg)) |
279 | 2.10M | LRCalc->createDeadDefs(LR, Reg); |
280 | 28.2M | // A register unit is considered reserved if all its roots and all their |
281 | 28.2M | // super registers are reserved. |
282 | 28.2M | if (!MRI->isReserved(Reg)) |
283 | 27.5M | IsRootReserved = false; |
284 | 28.2M | } |
285 | 4.28M | IsReserved |= IsRootReserved; |
286 | 4.28M | } |
287 | 4.28M | assert(IsReserved == MRI->isReservedRegUnit(Unit) && |
288 | 4.28M | "reserved computation mismatch"); |
289 | 4.28M | |
290 | 4.28M | // Now extend LR to reach all uses. |
291 | 4.28M | // Ignore uses of reserved registers. We only track defs of those. |
292 | 4.28M | if (!IsReserved) { |
293 | 8.52M | for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root4.26M ) { |
294 | 4.26M | for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true); |
295 | 32.4M | Super.isValid(); ++Super28.2M ) { |
296 | 28.2M | unsigned Reg = *Super; |
297 | 28.2M | if (!MRI->reg_empty(Reg)) |
298 | 2.08M | LRCalc->extendToUses(LR, Reg); |
299 | 28.2M | } |
300 | 4.26M | } |
301 | 4.26M | } |
302 | 4.28M | |
303 | 4.28M | // Flush the segment set to the segment vector. |
304 | 4.28M | if (UseSegmentSetForPhysRegs) |
305 | 4.28M | LR.flushSegmentSet(); |
306 | 4.28M | } |
307 | | |
308 | | /// Precompute the live ranges of any register units that are live-in to an ABI |
309 | | /// block somewhere. Register values can appear without a corresponding def when |
310 | | /// entering the entry block or a landing pad. |
311 | 564k | void LiveIntervals::computeLiveInRegUnits() { |
312 | 564k | RegUnitRanges.resize(TRI->getNumRegUnits()); |
313 | 564k | LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); |
314 | 564k | |
315 | 564k | // Keep track of the live range sets allocated. |
316 | 564k | SmallVector<unsigned, 8> NewRanges; |
317 | 564k | |
318 | 564k | // Check all basic blocks for live-ins. |
319 | 2.92M | for (const MachineBasicBlock &MBB : *MF) { |
320 | 2.92M | // We only care about ABI blocks: Entry + landing pads. |
321 | 2.92M | if ((&MBB != &MF->front() && !MBB.isEHPad()2.35M ) || MBB.livein_empty()580k ) |
322 | 2.42M | continue; |
323 | 499k | |
324 | 499k | // Create phi-defs at Begin for all live-in registers. |
325 | 499k | SlotIndex Begin = Indexes->getMBBStartIdx(&MBB); |
326 | 499k | LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB)); |
327 | 1.14M | for (const auto &LI : MBB.liveins()) { |
328 | 2.53M | for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units1.38M ) { |
329 | 1.38M | unsigned Unit = *Units; |
330 | 1.38M | LiveRange *LR = RegUnitRanges[Unit]; |
331 | 1.38M | if (!LR) { |
332 | 1.35M | // Use segment set to speed-up initial computation of the live range. |
333 | 1.35M | LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs); |
334 | 1.35M | NewRanges.push_back(Unit); |
335 | 1.35M | } |
336 | 1.38M | VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); |
337 | 1.38M | (void)VNI; |
338 | 1.38M | LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id); |
339 | 1.38M | } |
340 | 1.14M | } |
341 | 499k | LLVM_DEBUG(dbgs() << '\n'); |
342 | 499k | } |
343 | 564k | LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); |
344 | 564k | |
345 | 564k | // Compute the 'normal' part of the ranges. |
346 | 564k | for (unsigned Unit : NewRanges) |
347 | 1.35M | computeRegUnitRange(*RegUnitRanges[Unit], Unit); |
348 | 564k | } |
349 | | |
350 | | static void createSegmentsForValues(LiveRange &LR, |
351 | 768k | iterator_range<LiveInterval::vni_iterator> VNIs) { |
352 | 1.08M | for (VNInfo *VNI : VNIs) { |
353 | 1.08M | if (VNI->isUnused()) |
354 | 10.6k | continue; |
355 | 1.07M | SlotIndex Def = VNI->def; |
356 | 1.07M | LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI)); |
357 | 1.07M | } |
358 | 768k | } |
359 | | |
360 | | void LiveIntervals::extendSegmentsToUses(LiveRange &Segments, |
361 | | ShrinkToUsesWorkList &WorkList, |
362 | 768k | unsigned Reg, LaneBitmask LaneMask) { |
363 | 768k | // Keep track of the PHIs that are in use. |
364 | 768k | SmallPtrSet<VNInfo*, 8> UsedPHIs; |
365 | 768k | // Blocks that have already been added to WorkList as live-out. |
366 | 768k | SmallPtrSet<const MachineBasicBlock*, 16> LiveOut; |
367 | 768k | |
368 | 768k | auto getSubRange = [](const LiveInterval &I, LaneBitmask M) |
369 | 768k | -> const LiveRange& { |
370 | 768k | if (M.none()) |
371 | 767k | return I; |
372 | 2.34k | for (const LiveInterval::SubRange &SR : I.subranges())1.08k { |
373 | 2.34k | if ((SR.LaneMask & M).any()) { |
374 | 1.08k | assert(SR.LaneMask == M && "Expecting lane masks to match exactly"); |
375 | 1.08k | return SR; |
376 | 1.08k | } |
377 | 2.34k | } |
378 | 1.08k | llvm_unreachable0 ("Subrange for mask not found"); |
379 | 1.08k | }; |
380 | 768k | |
381 | 768k | const LiveInterval &LI = getInterval(Reg); |
382 | 768k | const LiveRange &OldRange = getSubRange(LI, LaneMask); |
383 | 768k | |
384 | 768k | // Extend intervals to reach all uses in WorkList. |
385 | 15.9M | while (!WorkList.empty()) { |
386 | 15.1M | SlotIndex Idx = WorkList.back().first; |
387 | 15.1M | VNInfo *VNI = WorkList.back().second; |
388 | 15.1M | WorkList.pop_back(); |
389 | 15.1M | const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot()); |
390 | 15.1M | SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB); |
391 | 15.1M | |
392 | 15.1M | // Extend the live range for VNI to be live at Idx. |
393 | 15.1M | if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) { |
394 | 2.18M | assert(ExtVNI == VNI && "Unexpected existing value number"); |
395 | 2.18M | (void)ExtVNI; |
396 | 2.18M | // Is this a PHIDef we haven't seen before? |
397 | 2.18M | if (!VNI->isPHIDef() || VNI->def != BlockStart152k || |
398 | 2.18M | !UsedPHIs.insert(VNI).second122k ) |
399 | 2.07M | continue; |
400 | 103k | // The PHI is live, make sure the predecessors are live-out. |
401 | 378k | for (const MachineBasicBlock *Pred : MBB->predecessors())103k { |
402 | 378k | if (!LiveOut.insert(Pred).second) |
403 | 28.3k | continue; |
404 | 349k | SlotIndex Stop = Indexes->getMBBEndIdx(Pred); |
405 | 349k | // A predecessor is not required to have a live-out value for a PHI. |
406 | 349k | if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop)) |
407 | 349k | WorkList.push_back(std::make_pair(Stop, PVNI)); |
408 | 349k | } |
409 | 103k | continue; |
410 | 103k | } |
411 | 12.9M | |
412 | 12.9M | // VNI is live-in to MBB. |
413 | 12.9M | LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); |
414 | 12.9M | Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); |
415 | 12.9M | |
416 | 12.9M | // Make sure VNI is live-out from the predecessors. |
417 | 18.6M | for (const MachineBasicBlock *Pred : MBB->predecessors()) { |
418 | 18.6M | if (!LiveOut.insert(Pred).second) |
419 | 6.12M | continue; |
420 | 12.5M | SlotIndex Stop = Indexes->getMBBEndIdx(Pred); |
421 | 12.5M | if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) { |
422 | 12.5M | assert(OldVNI == VNI && "Wrong value out of predecessor"); |
423 | 12.5M | (void)OldVNI; |
424 | 12.5M | WorkList.push_back(std::make_pair(Stop, VNI)); |
425 | 12.5M | } else { |
426 | | #ifndef NDEBUG |
427 | | // There was no old VNI. Verify that Stop is jointly dominated |
428 | | // by <undef>s for this live range. |
429 | | assert(LaneMask.any() && |
430 | | "Missing value out of predecessor for main range"); |
431 | | SmallVector<SlotIndex,8> Undefs; |
432 | | LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes); |
433 | | assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) && |
434 | | "Missing value out of predecessor for subrange"); |
435 | | #endif |
436 | | } |
437 | 12.5M | } |
438 | 12.9M | } |
439 | 768k | } |
440 | | |
441 | | bool LiveIntervals::shrinkToUses(LiveInterval *li, |
442 | 767k | SmallVectorImpl<MachineInstr*> *dead) { |
443 | 767k | LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n'); |
444 | 767k | assert(TargetRegisterInfo::isVirtualRegister(li->reg) |
445 | 767k | && "Can only shrink virtual registers"); |
446 | 767k | |
447 | 767k | // Shrink subregister live ranges. |
448 | 767k | bool NeedsCleanup = false; |
449 | 767k | for (LiveInterval::SubRange &S : li->subranges()) { |
450 | 973 | shrinkToUses(S, li->reg); |
451 | 973 | if (S.empty()) |
452 | 1 | NeedsCleanup = true; |
453 | 973 | } |
454 | 767k | if (NeedsCleanup) |
455 | 1 | li->removeEmptySubRanges(); |
456 | 767k | |
457 | 767k | // Find all the values used, including PHI kills. |
458 | 767k | ShrinkToUsesWorkList WorkList; |
459 | 767k | |
460 | 767k | // Visit all instructions reading li->reg. |
461 | 767k | unsigned Reg = li->reg; |
462 | 3.18M | for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) { |
463 | 3.18M | if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg)3.18M ) |
464 | 920k | continue; |
465 | 2.26M | SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); |
466 | 2.26M | LiveQueryResult LRQ = li->Query(Idx); |
467 | 2.26M | VNInfo *VNI = LRQ.valueIn(); |
468 | 2.26M | if (!VNI) { |
469 | 2 | // This shouldn't happen: readsVirtualRegister returns true, but there is |
470 | 2 | // no live value. It is likely caused by a target getting <undef> flags |
471 | 2 | // wrong. |
472 | 2 | LLVM_DEBUG( |
473 | 2 | dbgs() << Idx << '\t' << UseMI |
474 | 2 | << "Warning: Instr claims to read non-existent value in " |
475 | 2 | << *li << '\n'); |
476 | 2 | continue; |
477 | 2 | } |
478 | 2.26M | // Special case: An early-clobber tied operand reads and writes the |
479 | 2.26M | // register one slot early. |
480 | 2.26M | if (VNInfo *DefVNI = LRQ.valueDefined()) |
481 | 64.9k | Idx = DefVNI->def; |
482 | 2.26M | |
483 | 2.26M | WorkList.push_back(std::make_pair(Idx, VNI)); |
484 | 2.26M | } |
485 | 767k | |
486 | 767k | // Create new live ranges with only minimal live segments per def. |
487 | 767k | LiveRange NewLR; |
488 | 767k | createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); |
489 | 767k | extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone()); |
490 | 767k | |
491 | 767k | // Move the trimmed segments back. |
492 | 767k | li->segments.swap(NewLR.segments); |
493 | 767k | |
494 | 767k | // Handle dead values. |
495 | 767k | bool CanSeparate = computeDeadValues(*li, dead); |
496 | 767k | LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n'); |
497 | 767k | return CanSeparate; |
498 | 767k | } |
499 | | |
500 | | bool LiveIntervals::computeDeadValues(LiveInterval &LI, |
501 | 13.6M | SmallVectorImpl<MachineInstr*> *dead) { |
502 | 13.6M | bool MayHaveSplitComponents = false; |
503 | 16.0M | for (VNInfo *VNI : LI.valnos) { |
504 | 16.0M | if (VNI->isUnused()) |
505 | 10.4k | continue; |
506 | 16.0M | SlotIndex Def = VNI->def; |
507 | 16.0M | LiveRange::iterator I = LI.FindSegmentContaining(Def); |
508 | 16.0M | assert(I != LI.end() && "Missing segment for VNI"); |
509 | 16.0M | |
510 | 16.0M | // Is the register live before? Otherwise we may have to add a read-undef |
511 | 16.0M | // flag for subregister defs. |
512 | 16.0M | unsigned VReg = LI.reg; |
513 | 16.0M | if (MRI->shouldTrackSubRegLiveness(VReg)) { |
514 | 661k | if ((I == LI.begin() || std::prev(I)->end < Def206k ) && !VNI->isPHIDef()457k ) { |
515 | 457k | MachineInstr *MI = getInstructionFromIndex(Def); |
516 | 457k | MI->setRegisterDefReadUndef(VReg); |
517 | 457k | } |
518 | 661k | } |
519 | 16.0M | |
520 | 16.0M | if (I->end != Def.getDeadSlot()) |
521 | 15.6M | continue; |
522 | 446k | if (VNI->isPHIDef()) { |
523 | 13.5k | // This is a dead PHI. Remove it. |
524 | 13.5k | VNI->markUnused(); |
525 | 13.5k | LI.removeSegment(I); |
526 | 13.5k | LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); |
527 | 13.5k | MayHaveSplitComponents = true; |
528 | 432k | } else { |
529 | 432k | // This is a dead def. Make sure the instruction knows. |
530 | 432k | MachineInstr *MI = getInstructionFromIndex(Def); |
531 | 432k | assert(MI && "No instruction defining live value"); |
532 | 432k | MI->addRegisterDead(LI.reg, TRI); |
533 | 432k | if (dead && MI->allDefsAreDead()363k ) { |
534 | 363k | LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI); |
535 | 363k | dead->push_back(MI); |
536 | 363k | } |
537 | 432k | } |
538 | 446k | } |
539 | 13.6M | return MayHaveSplitComponents; |
540 | 13.6M | } |
541 | | |
542 | 1.08k | void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { |
543 | 1.08k | LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n'); |
544 | 1.08k | assert(TargetRegisterInfo::isVirtualRegister(Reg) |
545 | 1.08k | && "Can only shrink virtual registers"); |
546 | 1.08k | // Find all the values used, including PHI kills. |
547 | 1.08k | ShrinkToUsesWorkList WorkList; |
548 | 1.08k | |
549 | 1.08k | // Visit all instructions reading Reg. |
550 | 1.08k | SlotIndex LastIdx; |
551 | 2.11k | for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { |
552 | 2.11k | // Skip "undef" uses. |
553 | 2.11k | if (!MO.readsReg()) |
554 | 6 | continue; |
555 | 2.11k | // Maybe the operand is for a subregister we don't care about. |
556 | 2.11k | unsigned SubReg = MO.getSubReg(); |
557 | 2.11k | if (SubReg != 0) { |
558 | 1.83k | LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); |
559 | 1.83k | if ((LaneMask & SR.LaneMask).none()) |
560 | 706 | continue; |
561 | 1.40k | } |
562 | 1.40k | // We only need to visit each instruction once. |
563 | 1.40k | MachineInstr *UseMI = MO.getParent(); |
564 | 1.40k | SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot(); |
565 | 1.40k | if (Idx == LastIdx) |
566 | 38 | continue; |
567 | 1.36k | LastIdx = Idx; |
568 | 1.36k | |
569 | 1.36k | LiveQueryResult LRQ = SR.Query(Idx); |
570 | 1.36k | VNInfo *VNI = LRQ.valueIn(); |
571 | 1.36k | // For Subranges it is possible that only undef values are left in that |
572 | 1.36k | // part of the subregister, so there is no real liverange at the use |
573 | 1.36k | if (!VNI) |
574 | 8 | continue; |
575 | 1.35k | |
576 | 1.35k | // Special case: An early-clobber tied operand reads and writes the |
577 | 1.35k | // register one slot early. |
578 | 1.35k | if (VNInfo *DefVNI = LRQ.valueDefined()) |
579 | 53 | Idx = DefVNI->def; |
580 | 1.35k | |
581 | 1.35k | WorkList.push_back(std::make_pair(Idx, VNI)); |
582 | 1.35k | } |
583 | 1.08k | |
584 | 1.08k | // Create a new live ranges with only minimal live segments per def. |
585 | 1.08k | LiveRange NewLR; |
586 | 1.08k | createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); |
587 | 1.08k | extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask); |
588 | 1.08k | |
589 | 1.08k | // Move the trimmed ranges back. |
590 | 1.08k | SR.segments.swap(NewLR.segments); |
591 | 1.08k | |
592 | 1.08k | // Remove dead PHI value numbers |
593 | 1.74k | for (VNInfo *VNI : SR.valnos) { |
594 | 1.74k | if (VNI->isUnused()) |
595 | 148 | continue; |
596 | 1.60k | const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); |
597 | 1.60k | assert(Segment != nullptr && "Missing segment for VNI"); |
598 | 1.60k | if (Segment->end != VNI->def.getDeadSlot()) |
599 | 1.37k | continue; |
600 | 228 | if (VNI->isPHIDef()) { |
601 | 59 | // This is a dead PHI. Remove it. |
602 | 59 | LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def |
603 | 59 | << " may separate interval\n"); |
604 | 59 | VNI->markUnused(); |
605 | 59 | SR.removeSegment(*Segment); |
606 | 59 | } |
607 | 228 | } |
608 | 1.08k | |
609 | 1.08k | LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n'); |
610 | 1.08k | } |
611 | | |
612 | | void LiveIntervals::extendToIndices(LiveRange &LR, |
613 | | ArrayRef<SlotIndex> Indices, |
614 | 85.3k | ArrayRef<SlotIndex> Undefs) { |
615 | 85.3k | assert(LRCalc && "LRCalc not initialized."); |
616 | 85.3k | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
617 | 85.3k | for (SlotIndex Idx : Indices) |
618 | 296k | LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs); |
619 | 85.3k | } |
620 | | |
621 | | void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, |
622 | 202k | SmallVectorImpl<SlotIndex> *EndPoints) { |
623 | 202k | LiveQueryResult LRQ = LR.Query(Kill); |
624 | 202k | VNInfo *VNI = LRQ.valueOutOrDead(); |
625 | 202k | if (!VNI) |
626 | 58.0k | return; |
627 | 144k | |
628 | 144k | MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); |
629 | 144k | SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB); |
630 | 144k | |
631 | 144k | // If VNI isn't live out from KillMBB, the value is trivially pruned. |
632 | 144k | if (LRQ.endPoint() < MBBEnd) { |
633 | 142k | LR.removeSegment(Kill, LRQ.endPoint()); |
634 | 142k | if (EndPoints) EndPoints->push_back(LRQ.endPoint()); |
635 | 142k | return; |
636 | 142k | } |
637 | 2.17k | |
638 | 2.17k | // VNI is live out of KillMBB. |
639 | 2.17k | LR.removeSegment(Kill, MBBEnd); |
640 | 2.17k | if (EndPoints) EndPoints->push_back(MBBEnd); |
641 | 2.17k | |
642 | 2.17k | // Find all blocks that are reachable from KillMBB without leaving VNI's live |
643 | 2.17k | // range. It is possible that KillMBB itself is reachable, so start a DFS |
644 | 2.17k | // from each successor. |
645 | 2.17k | using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>; |
646 | 2.17k | VisitedTy Visited; |
647 | 3.25k | for (MachineBasicBlock *Succ : KillMBB->successors()) { |
648 | 3.25k | for (df_ext_iterator<MachineBasicBlock*, VisitedTy> |
649 | 3.25k | I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited); |
650 | 8.97k | I != E;) { |
651 | 5.72k | MachineBasicBlock *MBB = *I; |
652 | 5.72k | |
653 | 5.72k | // Check if VNI is live in to MBB. |
654 | 5.72k | SlotIndex MBBStart, MBBEnd; |
655 | 5.72k | std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); |
656 | 5.72k | LiveQueryResult LRQ = LR.Query(MBBStart); |
657 | 5.72k | if (LRQ.valueIn() != VNI) { |
658 | 2.57k | // This block isn't part of the VNI segment. Prune the search. |
659 | 2.57k | I.skipChildren(); |
660 | 2.57k | continue; |
661 | 2.57k | } |
662 | 3.15k | |
663 | 3.15k | // Prune the search if VNI is killed in MBB. |
664 | 3.15k | if (LRQ.endPoint() < MBBEnd) { |
665 | 732 | LR.removeSegment(MBBStart, LRQ.endPoint()); |
666 | 732 | if (EndPoints) EndPoints->push_back(LRQ.endPoint()); |
667 | 732 | I.skipChildren(); |
668 | 732 | continue; |
669 | 732 | } |
670 | 2.41k | |
671 | 2.41k | // VNI is live through MBB. |
672 | 2.41k | LR.removeSegment(MBBStart, MBBEnd); |
673 | 2.41k | if (EndPoints) EndPoints->push_back(MBBEnd); |
674 | 2.41k | ++I; |
675 | 2.41k | } |
676 | 3.25k | } |
677 | 2.17k | } |
678 | | |
679 | | //===----------------------------------------------------------------------===// |
680 | | // Register allocator hooks. |
681 | | // |
682 | | |
683 | 484k | void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { |
684 | 484k | // Keep track of regunit ranges. |
685 | 484k | SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU; |
686 | 484k | // Keep track of subregister ranges. |
687 | 484k | SmallVector<std::pair<const LiveInterval::SubRange*, |
688 | 484k | LiveRange::const_iterator>, 4> SRs; |
689 | 484k | |
690 | 19.1M | for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i18.6M ) { |
691 | 18.6M | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
692 | 18.6M | if (MRI->reg_nodbg_empty(Reg)) |
693 | 10.8M | continue; |
694 | 7.82M | const LiveInterval &LI = getInterval(Reg); |
695 | 7.82M | if (LI.empty()) |
696 | 10.3k | continue; |
697 | 7.81M | |
698 | 7.81M | // Find the regunit intervals for the assigned register. They may overlap |
699 | 7.81M | // the virtual register live range, cancelling any kills. |
700 | 7.81M | RU.clear(); |
701 | 16.9M | for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid(); |
702 | 9.14M | ++Unit) { |
703 | 9.14M | const LiveRange &RURange = getRegUnit(*Unit); |
704 | 9.14M | if (RURange.empty()) |
705 | 5.78M | continue; |
706 | 3.36M | RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end))); |
707 | 3.36M | } |
708 | 7.81M | |
709 | 7.81M | if (MRI->subRegLivenessEnabled()) { |
710 | 308k | SRs.clear(); |
711 | 308k | for (const LiveInterval::SubRange &SR : LI.subranges()) { |
712 | 214k | SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end))); |
713 | 214k | } |
714 | 308k | } |
715 | 7.81M | |
716 | 7.81M | // Every instruction that kills Reg corresponds to a segment range end |
717 | 7.81M | // point. |
718 | 19.7M | for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; |
719 | 11.9M | ++RI) { |
720 | 11.9M | // A block index indicates an MBB edge. |
721 | 11.9M | if (RI->end.isBlock()) |
722 | 3.56M | continue; |
723 | 8.34M | MachineInstr *MI = getInstructionFromIndex(RI->end); |
724 | 8.34M | if (!MI) |
725 | 0 | continue; |
726 | 8.34M | |
727 | 8.34M | // Check if any of the regunits are live beyond the end of RI. That could |
728 | 8.34M | // happen when a physreg is defined as a copy of a virtreg: |
729 | 8.34M | // |
730 | 8.34M | // %eax = COPY %5 |
731 | 8.34M | // FOO %5 <--- MI, cancel kill because %eax is live. |
732 | 8.34M | // BAR killed %eax |
733 | 8.34M | // |
734 | 8.34M | // There should be no kill flag on FOO when %5 is rewritten as %eax. |
735 | 8.34M | for (auto &RUP : RU) { |
736 | 3.85M | const LiveRange &RURange = *RUP.first; |
737 | 3.85M | LiveRange::const_iterator &I = RUP.second; |
738 | 3.85M | if (I == RURange.end()) |
739 | 851k | continue; |
740 | 3.00M | I = RURange.advanceTo(I, RI->end); |
741 | 3.00M | if (I == RURange.end() || I->start >= RI->end2.97M ) |
742 | 2.99M | continue; |
743 | 15.5k | // I is overlapping RI. |
744 | 15.5k | goto CancelKill; |
745 | 15.5k | } |
746 | 8.34M | |
747 | 8.34M | if (8.32M MRI->subRegLivenessEnabled()8.32M ) { |
748 | 393k | // When reading a partial undefined value we must not add a kill flag. |
749 | 393k | // The regalloc might have used the undef lane for something else. |
750 | 393k | // Example: |
751 | 393k | // %1 = ... ; R32: %1 |
752 | 393k | // %2:high16 = ... ; R64: %2 |
753 | 393k | // = read killed %2 ; R64: %2 |
754 | 393k | // = read %1 ; R32: %1 |
755 | 393k | // The <kill> flag is correct for %2, but the register allocator may |
756 | 393k | // assign R0L to %1, and R0 to %2 because the low 32bits of R0 |
757 | 393k | // are actually never written by %2. After assignment the <kill> |
758 | 393k | // flag at the read instruction is invalid. |
759 | 393k | LaneBitmask DefinedLanesMask; |
760 | 393k | if (!SRs.empty()) { |
761 | 154k | // Compute a mask of lanes that are defined. |
762 | 154k | DefinedLanesMask = LaneBitmask::getNone(); |
763 | 507k | for (auto &SRP : SRs) { |
764 | 507k | const LiveInterval::SubRange &SR = *SRP.first; |
765 | 507k | LiveRange::const_iterator &I = SRP.second; |
766 | 507k | if (I == SR.end()) |
767 | 71.1k | continue; |
768 | 436k | I = SR.advanceTo(I, RI->end); |
769 | 436k | if (I == SR.end() || I->start >= RI->end298k ) |
770 | 281k | continue; |
771 | 154k | // I is overlapping RI |
772 | 154k | DefinedLanesMask |= SR.LaneMask; |
773 | 154k | } |
774 | 154k | } else |
775 | 239k | DefinedLanesMask = LaneBitmask::getAll(); |
776 | 393k | |
777 | 393k | bool IsFullWrite = false; |
778 | 2.20M | for (const MachineOperand &MO : MI->operands()) { |
779 | 2.20M | if (!MO.isReg() || MO.getReg() != Reg1.23M ) |
780 | 1.79M | continue; |
781 | 405k | if (MO.isUse()) { |
782 | 309k | // Reading any undefined lanes? |
783 | 309k | LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); |
784 | 309k | if ((UseMask & ~DefinedLanesMask).any()) |
785 | 72.2k | goto CancelKill; |
786 | 96.0k | } else if (MO.getSubReg() == 0) { |
787 | 13.4k | // Writing to the full register? |
788 | 13.4k | assert(MO.isDef()); |
789 | 13.4k | IsFullWrite = true; |
790 | 13.4k | } |
791 | 405k | } |
792 | 393k | |
793 | 393k | // If an instruction writes to a subregister, a new segment starts in |
794 | 393k | // the LiveInterval. But as this is only overriding part of the register |
795 | 393k | // adding kill-flags is not correct here after registers have been |
796 | 393k | // assigned. |
797 | 393k | if (321k !IsFullWrite321k ) { |
798 | 308k | // Next segment has to be adjacent in the subregister write case. |
799 | 308k | LiveRange::const_iterator N = std::next(RI); |
800 | 308k | if (N != LI.end() && N->start == RI->end85.1k ) |
801 | 81.8k | goto CancelKill; |
802 | 8.17M | } |
803 | 321k | } |
804 | 8.17M | |
805 | 8.17M | MI->addRegisterKilled(Reg, nullptr); |
806 | 8.17M | continue; |
807 | 169k | CancelKill: |
808 | 169k | MI->clearRegisterKills(Reg, nullptr); |
809 | 169k | } |
810 | 7.81M | } |
811 | 484k | } |
812 | | |
813 | | MachineBasicBlock* |
814 | 46.7M | LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { |
815 | 46.7M | // A local live range must be fully contained inside the block, meaning it is |
816 | 46.7M | // defined and killed at instructions, not at block boundaries. It is not |
817 | 46.7M | // live in or out of any block. |
818 | 46.7M | // |
819 | 46.7M | // It is technically possible to have a PHI-defined live range identical to a |
820 | 46.7M | // single block, but we are going to return false in that case. |
821 | 46.7M | |
822 | 46.7M | SlotIndex Start = LI.beginIndex(); |
823 | 46.7M | if (Start.isBlock()) |
824 | 60.7k | return nullptr; |
825 | 46.6M | |
826 | 46.6M | SlotIndex Stop = LI.endIndex(); |
827 | 46.6M | if (Stop.isBlock()) |
828 | 6.46M | return nullptr; |
829 | 40.2M | |
830 | 40.2M | // getMBBFromIndex doesn't need to search the MBB table when both indexes |
831 | 40.2M | // belong to proper instructions. |
832 | 40.2M | MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); |
833 | 40.2M | MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); |
834 | 40.2M | return MBB1 == MBB2 ? MBB133.4M : nullptr6.78M ; |
835 | 40.2M | } |
836 | | |
837 | | bool |
838 | 501 | LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { |
839 | 1.73k | for (const VNInfo *PHI : LI.valnos) { |
840 | 1.73k | if (PHI->isUnused() || !PHI->isPHIDef()) |
841 | 1.59k | continue; |
842 | 137 | const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); |
843 | 137 | // Conservatively return true instead of scanning huge predecessor lists. |
844 | 137 | if (PHIMBB->pred_size() > 100) |
845 | 0 | return true; |
846 | 137 | for (const MachineBasicBlock *Pred : PHIMBB->predecessors()) |
847 | 383 | if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred))) |
848 | 5 | return true; |
849 | 137 | } |
850 | 501 | return false496 ; |
851 | 501 | } |
852 | | |
853 | | float LiveIntervals::getSpillWeight(bool isDef, bool isUse, |
854 | | const MachineBlockFrequencyInfo *MBFI, |
855 | 24.6M | const MachineInstr &MI) { |
856 | 24.6M | return getSpillWeight(isDef, isUse, MBFI, MI.getParent()); |
857 | 24.6M | } |
858 | | |
859 | | float LiveIntervals::getSpillWeight(bool isDef, bool isUse, |
860 | | const MachineBlockFrequencyInfo *MBFI, |
861 | 24.6M | const MachineBasicBlock *MBB) { |
862 | 24.6M | BlockFrequency Freq = MBFI->getBlockFreq(MBB); |
863 | 24.6M | const float Scale = 1.0f / MBFI->getEntryFreq(); |
864 | 24.6M | return (isDef + isUse) * (Freq.getFrequency() * Scale); |
865 | 24.6M | } |
866 | | |
867 | | LiveRange::Segment |
868 | 0 | LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) { |
869 | 0 | LiveInterval& Interval = createEmptyInterval(reg); |
870 | 0 | VNInfo *VN = Interval.getNextValue( |
871 | 0 | SlotIndex(getInstructionIndex(startInst).getRegSlot()), |
872 | 0 | getVNInfoAllocator()); |
873 | 0 | LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()), |
874 | 0 | getMBBEndIdx(startInst.getParent()), VN); |
875 | 0 | Interval.addSegment(S); |
876 | 0 |
|
877 | 0 | return S; |
878 | 0 | } |
879 | | |
880 | | //===----------------------------------------------------------------------===// |
881 | | // Register mask functions |
882 | | //===----------------------------------------------------------------------===// |
883 | | |
884 | | bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, |
885 | 9.35M | BitVector &UsableRegs) { |
886 | 9.35M | if (LI.empty()) |
887 | 0 | return false; |
888 | 9.35M | LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); |
889 | 9.35M | |
890 | 9.35M | // Use a smaller arrays for local live ranges. |
891 | 9.35M | ArrayRef<SlotIndex> Slots; |
892 | 9.35M | ArrayRef<const uint32_t*> Bits; |
893 | 9.35M | if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { |
894 | 6.74M | Slots = getRegMaskSlotsInBlock(MBB->getNumber()); |
895 | 6.74M | Bits = getRegMaskBitsInBlock(MBB->getNumber()); |
896 | 6.74M | } else { |
897 | 2.60M | Slots = getRegMaskSlots(); |
898 | 2.60M | Bits = getRegMaskBits(); |
899 | 2.60M | } |
900 | 9.35M | |
901 | 9.35M | // We are going to enumerate all the register mask slots contained in LI. |
902 | 9.35M | // Start with a binary search of RegMaskSlots to find a starting point. |
903 | 9.35M | ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start); |
904 | 9.35M | ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); |
905 | 9.35M | |
906 | 9.35M | // No slots in range, LI begins after the last call. |
907 | 9.35M | if (SlotI == SlotE) |
908 | 4.40M | return false; |
909 | 4.94M | |
910 | 4.94M | bool Found = false; |
911 | 8.54M | while (true8.54M ) { |
912 | 8.54M | assert(*SlotI >= LiveI->start); |
913 | 8.54M | // Loop over all slots overlapping this segment. |
914 | 30.9M | while (*SlotI < LiveI->end) { |
915 | 22.9M | // *SlotI overlaps LI. Collect mask bits. |
916 | 22.9M | if (!Found) { |
917 | 2.22M | // This is the first overlap. Initialize UsableRegs to all ones. |
918 | 2.22M | UsableRegs.clear(); |
919 | 2.22M | UsableRegs.resize(TRI->getNumRegs(), true); |
920 | 2.22M | Found = true; |
921 | 2.22M | } |
922 | 22.9M | // Remove usable registers clobbered by this mask. |
923 | 22.9M | UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); |
924 | 22.9M | if (++SlotI == SlotE) |
925 | 525k | return Found; |
926 | 22.9M | } |
927 | 8.54M | // *SlotI is beyond the current LI segment. |
928 | 8.54M | LiveI = LI.advanceTo(LiveI, *SlotI); |
929 | 8.02M | if (LiveI == LiveE) |
930 | 4.25M | return Found; |
931 | 3.77M | // Advance SlotI until it overlaps. |
932 | 10.8M | while (3.77M *SlotI < LiveI->start) |
933 | 7.21M | if (++SlotI == SlotE) |
934 | 163k | return Found; |
935 | 3.77M | } |
936 | 4.94M | } |
937 | | |
938 | | //===----------------------------------------------------------------------===// |
939 | | // IntervalUpdate class. |
940 | | //===----------------------------------------------------------------------===// |
941 | | |
942 | | /// Toolkit used by handleMove to trim or extend live intervals. |
943 | | class LiveIntervals::HMEditor { |
944 | | private: |
945 | | LiveIntervals& LIS; |
946 | | const MachineRegisterInfo& MRI; |
947 | | const TargetRegisterInfo& TRI; |
948 | | SlotIndex OldIdx; |
949 | | SlotIndex NewIdx; |
950 | | SmallPtrSet<LiveRange*, 8> Updated; |
951 | | bool UpdateFlags; |
952 | | |
953 | | public: |
954 | | HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, |
955 | | const TargetRegisterInfo& TRI, |
956 | | SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) |
957 | | : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), |
958 | 838k | UpdateFlags(UpdateFlags) {} |
959 | | |
960 | | // FIXME: UpdateFlags is a workaround that creates live intervals for all |
961 | | // physregs, even those that aren't needed for regalloc, in order to update |
962 | | // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill |
963 | | // flags, and postRA passes will use a live register utility instead. |
964 | 634k | LiveRange *getRegUnitLI(unsigned Unit) { |
965 | 634k | if (UpdateFlags && !MRI.isReservedRegUnit(Unit)611k ) |
966 | 325k | return &LIS.getRegUnit(Unit); |
967 | 309k | return LIS.getCachedRegUnit(Unit); |
968 | 309k | } |
969 | | |
970 | | /// Update all live ranges touched by MI, assuming a move from OldIdx to |
971 | | /// NewIdx. |
972 | 838k | void updateAllRanges(MachineInstr *MI) { |
973 | 838k | LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " |
974 | 838k | << *MI); |
975 | 838k | bool hasRegMask = false; |
976 | 3.12M | for (MachineOperand &MO : MI->operands()) { |
977 | 3.12M | if (MO.isRegMask()) |
978 | 0 | hasRegMask = true; |
979 | 3.12M | if (!MO.isReg()) |
980 | 1.08M | continue; |
981 | 2.03M | if (MO.isUse()) { |
982 | 1.21M | if (!MO.readsReg()) |
983 | 309 | continue; |
984 | 1.21M | // Aggressively clear all kill flags. |
985 | 1.21M | // They are reinserted by VirtRegRewriter. |
986 | 1.21M | MO.setIsKill(false); |
987 | 1.21M | } |
988 | 2.03M | |
989 | 2.03M | unsigned Reg = MO.getReg(); |
990 | 2.03M | if (!Reg) |
991 | 18.5k | continue; |
992 | 2.01M | if (TargetRegisterInfo::isVirtualRegister(Reg)) { |
993 | 1.50M | LiveInterval &LI = LIS.getInterval(Reg); |
994 | 1.50M | if (LI.hasSubRanges()) { |
995 | 103k | unsigned SubReg = MO.getSubReg(); |
996 | 103k | LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)84.5k |
997 | 103k | : MRI.getMaxLaneMaskForVReg(Reg)19.0k ; |
998 | 360k | for (LiveInterval::SubRange &S : LI.subranges()) { |
999 | 360k | if ((S.LaneMask & LaneMask).none()) |
1000 | 218k | continue; |
1001 | 142k | updateRange(S, Reg, S.LaneMask); |
1002 | 142k | } |
1003 | 103k | } |
1004 | 1.50M | updateRange(LI, Reg, LaneBitmask::getNone()); |
1005 | 1.50M | continue; |
1006 | 1.50M | } |
1007 | 514k | |
1008 | 514k | // For physregs, only update the regunits that actually have a |
1009 | 514k | // precomputed live range. |
1010 | 1.14M | for (MCRegUnitIterator Units(Reg, &TRI); 514k Units.isValid(); ++Units634k ) |
1011 | 634k | if (LiveRange *LR = getRegUnitLI(*Units)) |
1012 | 359k | updateRange(*LR, *Units, LaneBitmask::getNone()); |
1013 | 514k | } |
1014 | 838k | if (hasRegMask) |
1015 | 0 | updateRegMaskSlots(); |
1016 | 838k | } |
1017 | | |
1018 | | private: |
1019 | | /// Update a single live range, assuming an instruction has been moved from |
1020 | | /// OldIdx to NewIdx. |
1021 | 2.00M | void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { |
1022 | 2.00M | if (!Updated.insert(&LR).second) |
1023 | 57.4k | return; |
1024 | 1.94M | LLVM_DEBUG({ |
1025 | 1.94M | dbgs() << " "; |
1026 | 1.94M | if (TargetRegisterInfo::isVirtualRegister(Reg)) { |
1027 | 1.94M | dbgs() << printReg(Reg); |
1028 | 1.94M | if (LaneMask.any()) |
1029 | 1.94M | dbgs() << " L" << PrintLaneMask(LaneMask); |
1030 | 1.94M | } else { |
1031 | 1.94M | dbgs() << printRegUnit(Reg, &TRI); |
1032 | 1.94M | } |
1033 | 1.94M | dbgs() << ":\t" << LR << '\n'; |
1034 | 1.94M | }); |
1035 | 1.94M | if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) |
1036 | 1.76M | handleMoveDown(LR); |
1037 | 179k | else |
1038 | 179k | handleMoveUp(LR, Reg, LaneMask); |
1039 | 1.94M | LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n'); |
1040 | 1.94M | LR.verify(); |
1041 | 1.94M | } |
1042 | | |
1043 | | /// Update LR to reflect an instruction has been moved downwards from OldIdx |
1044 | | /// to NewIdx (OldIdx < NewIdx). |
1045 | 1.76M | void handleMoveDown(LiveRange &LR) { |
1046 | 1.76M | LiveRange::iterator E = LR.end(); |
1047 | 1.76M | // Segment going into OldIdx. |
1048 | 1.76M | LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); |
1049 | 1.76M | |
1050 | 1.76M | // No value live before or after OldIdx? Nothing to do. |
1051 | 1.76M | if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)1.76M ) |
1052 | 72.3k | return; |
1053 | 1.69M | |
1054 | 1.69M | LiveRange::iterator OldIdxOut; |
1055 | 1.69M | // Do we have a value live-in to OldIdx? |
1056 | 1.69M | if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { |
1057 | 1.03M | // If the live-in value already extends to NewIdx, there is nothing to do. |
1058 | 1.03M | if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end)) |
1059 | 454k | return; |
1060 | 579k | // Aggressively remove all kill flags from the old kill point. |
1061 | 579k | // Kill flags shouldn't be used while live intervals exist, they will be |
1062 | 579k | // reinserted by VirtRegRewriter. |
1063 | 579k | if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end)) |
1064 | 236k | for (MIBundleOperands MO(*KillMI); 39.0k MO.isValid(); ++MO197k ) |
1065 | 197k | if (MO->isReg() && MO->isUse()105k ) |
1066 | 68.7k | MO->setIsKill(false); |
1067 | 579k | |
1068 | 579k | // Is there a def before NewIdx which is not OldIdx? |
1069 | 579k | LiveRange::iterator Next = std::next(OldIdxIn); |
1070 | 579k | if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start)111k && |
1071 | 579k | SlotIndex::isEarlierInstr(Next->start, NewIdx)43.3k ) { |
1072 | 342 | // If we are here then OldIdx was just a use but not a def. We only have |
1073 | 342 | // to ensure liveness extends to NewIdx. |
1074 | 342 | LiveRange::iterator NewIdxIn = |
1075 | 342 | LR.advanceTo(Next, NewIdx.getBaseIndex()); |
1076 | 342 | // Extend the segment before NewIdx if necessary. |
1077 | 342 | if (NewIdxIn == E || |
1078 | 342 | !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)266 ) { |
1079 | 76 | LiveRange::iterator Prev = std::prev(NewIdxIn); |
1080 | 76 | Prev->end = NewIdx.getRegSlot(); |
1081 | 76 | } |
1082 | 342 | // Extend OldIdxIn. |
1083 | 342 | OldIdxIn->end = Next->start; |
1084 | 342 | return; |
1085 | 342 | } |
1086 | 578k | |
1087 | 578k | // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR |
1088 | 578k | // invalid by overlapping ranges. |
1089 | 578k | bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); |
1090 | 578k | OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()); |
1091 | 578k | // If this was not a kill, then there was no def and we're done. |
1092 | 578k | if (!isKill) |
1093 | 38.6k | return; |
1094 | 540k | |
1095 | 540k | // Did we have a Def at OldIdx? |
1096 | 540k | OldIdxOut = Next; |
1097 | 540k | if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)104k ) |
1098 | 472k | return; |
1099 | 660k | } else { |
1100 | 660k | OldIdxOut = OldIdxIn; |
1101 | 660k | } |
1102 | 1.69M | |
1103 | 1.69M | // If we are here then there is a Definition at OldIdx. OldIdxOut points |
1104 | 1.69M | // to the segment starting there. |
1105 | 1.69M | assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && |
1106 | 728k | "No def?"); |
1107 | 728k | VNInfo *OldIdxVNI = OldIdxOut->valno; |
1108 | 728k | assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); |
1109 | 728k | |
1110 | 728k | // If the defined value extends beyond NewIdx, just move the beginning |
1111 | 728k | // of the segment to NewIdx. |
1112 | 728k | SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); |
1113 | 728k | if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) { |
1114 | 698k | OldIdxVNI->def = NewIdxDef; |
1115 | 698k | OldIdxOut->start = OldIdxVNI->def; |
1116 | 698k | return; |
1117 | 698k | } |
1118 | 30.1k | |
1119 | 30.1k | // If we are here then we have a Definition at OldIdx which ends before |
1120 | 30.1k | // NewIdx. |
1121 | 30.1k | |
1122 | 30.1k | // Is there an existing Def at NewIdx? |
1123 | 30.1k | LiveRange::iterator AfterNewIdx |
1124 | 30.1k | = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot()); |
1125 | 30.1k | bool OldIdxDefIsDead = OldIdxOut->end.isDead(); |
1126 | 30.1k | if (!OldIdxDefIsDead && |
1127 | 30.1k | SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)5.48k ) { |
1128 | 5.48k | // OldIdx is not a dead def, and NewIdxDef is inside a new interval. |
1129 | 5.48k | VNInfo *DefVNI; |
1130 | 5.48k | if (OldIdxOut != LR.begin() && |
1131 | 5.48k | !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end, |
1132 | 2.28k | OldIdxOut->start)) { |
1133 | 2.28k | // There is no gap between OldIdxOut and its predecessor anymore, |
1134 | 2.28k | // merge them. |
1135 | 2.28k | LiveRange::iterator IPrev = std::prev(OldIdxOut); |
1136 | 2.28k | DefVNI = OldIdxVNI; |
1137 | 2.28k | IPrev->end = OldIdxOut->end; |
1138 | 3.20k | } else { |
1139 | 3.20k | // The value is live in to OldIdx |
1140 | 3.20k | LiveRange::iterator INext = std::next(OldIdxOut); |
1141 | 3.20k | assert(INext != E && "Must have following segment"); |
1142 | 3.20k | // We merge OldIdxOut and its successor. As we're dealing with subreg |
1143 | 3.20k | // reordering, there is always a successor to OldIdxOut in the same BB |
1144 | 3.20k | // We don't need INext->valno anymore and will reuse for the new segment |
1145 | 3.20k | // we create later. |
1146 | 3.20k | DefVNI = OldIdxVNI; |
1147 | 3.20k | INext->start = OldIdxOut->end; |
1148 | 3.20k | INext->valno->def = INext->start; |
1149 | 3.20k | } |
1150 | 5.48k | // If NewIdx is behind the last segment, extend that and append a new one. |
1151 | 5.48k | if (AfterNewIdx == E) { |
1152 | 0 | // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up |
1153 | 0 | // one position. |
1154 | 0 | // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end |
1155 | 0 | // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end |
1156 | 0 | std::copy(std::next(OldIdxOut), E, OldIdxOut); |
1157 | 0 | // The last segment is undefined now, reuse it for a dead def. |
1158 | 0 | LiveRange::iterator NewSegment = std::prev(E); |
1159 | 0 | *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), |
1160 | 0 | DefVNI); |
1161 | 0 | DefVNI->def = NewIdxDef; |
1162 | 0 |
|
1163 | 0 | LiveRange::iterator Prev = std::prev(NewSegment); |
1164 | 0 | Prev->end = NewIdxDef; |
1165 | 5.48k | } else { |
1166 | 5.48k | // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up |
1167 | 5.48k | // one position. |
1168 | 5.48k | // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -| |
1169 | 5.48k | // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -| |
1170 | 5.48k | std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut); |
1171 | 5.48k | LiveRange::iterator Prev = std::prev(AfterNewIdx); |
1172 | 5.48k | // We have two cases: |
1173 | 5.48k | if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) { |
1174 | 5.48k | // Case 1: NewIdx is inside a liverange. Split this liverange at |
1175 | 5.48k | // NewIdxDef into the segment "Prev" followed by "NewSegment". |
1176 | 5.48k | LiveRange::iterator NewSegment = AfterNewIdx; |
1177 | 5.48k | *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno); |
1178 | 5.48k | Prev->valno->def = NewIdxDef; |
1179 | 5.48k | |
1180 | 5.48k | *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI); |
1181 | 5.48k | DefVNI->def = Prev->start; |
1182 | 5.48k | } else { |
1183 | 0 | // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and |
1184 | 0 | // turn Prev into a segment from NewIdx to AfterNewIdx->start. |
1185 | 0 | *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI); |
1186 | 0 | DefVNI->def = NewIdxDef; |
1187 | 0 | assert(DefVNI != AfterNewIdx->valno); |
1188 | 0 | } |
1189 | 5.48k | } |
1190 | 5.48k | return; |
1191 | 5.48k | } |
1192 | 24.6k | |
1193 | 24.6k | if (AfterNewIdx != E && |
1194 | 24.6k | SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)22.6k ) { |
1195 | 0 | // There is an existing def at NewIdx. The def at OldIdx is coalesced into |
1196 | 0 | // that value. |
1197 | 0 | assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?"); |
1198 | 0 | LR.removeValNo(OldIdxVNI); |
1199 | 24.6k | } else { |
1200 | 24.6k | // There was no existing def at NewIdx. We need to create a dead def |
1201 | 24.6k | // at NewIdx. Shift segments over the old OldIdxOut segment, this frees |
1202 | 24.6k | // a new segment at the place where we want to construct the dead def. |
1203 | 24.6k | // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -| |
1204 | 24.6k | // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -| |
1205 | 24.6k | assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators"); |
1206 | 24.6k | std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut); |
1207 | 24.6k | // We can reuse OldIdxVNI now. |
1208 | 24.6k | LiveRange::iterator NewSegment = std::prev(AfterNewIdx); |
1209 | 24.6k | VNInfo *NewSegmentVNI = OldIdxVNI; |
1210 | 24.6k | NewSegmentVNI->def = NewIdxDef; |
1211 | 24.6k | *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), |
1212 | 24.6k | NewSegmentVNI); |
1213 | 24.6k | } |
1214 | 24.6k | } |
1215 | | |
1216 | | /// Update LR to reflect an instruction has been moved upwards from OldIdx |
1217 | | /// to NewIdx (NewIdx < OldIdx). |
1218 | 179k | void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { |
1219 | 179k | LiveRange::iterator E = LR.end(); |
1220 | 179k | // Segment going into OldIdx. |
1221 | 179k | LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex()); |
1222 | 179k | |
1223 | 179k | // No value live before or after OldIdx? Nothing to do. |
1224 | 179k | if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)177k ) |
1225 | 5.54k | return; |
1226 | 173k | |
1227 | 173k | LiveRange::iterator OldIdxOut; |
1228 | 173k | // Do we have a value live-in to OldIdx? |
1229 | 173k | if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) { |
1230 | 83.5k | // If the live-in value isn't killed here, then we have no Def at |
1231 | 83.5k | // OldIdx, moreover the value must be live at NewIdx so there is nothing |
1232 | 83.5k | // to do. |
1233 | 83.5k | bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end); |
1234 | 83.5k | if (!isKill) |
1235 | 12.4k | return; |
1236 | 71.1k | |
1237 | 71.1k | // At this point we have to move OldIdxIn->end back to the nearest |
1238 | 71.1k | // previous use or (dead-)def but no further than NewIdx. |
1239 | 71.1k | SlotIndex DefBeforeOldIdx |
1240 | 71.1k | = std::max(OldIdxIn->start.getDeadSlot(), |
1241 | 71.1k | NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber())); |
1242 | 71.1k | OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask); |
1243 | 71.1k | |
1244 | 71.1k | // Did we have a Def at OldIdx? If not we are done now. |
1245 | 71.1k | OldIdxOut = std::next(OldIdxIn); |
1246 | 71.1k | if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)18.8k ) |
1247 | 66.2k | return; |
1248 | 90.2k | } else { |
1249 | 90.2k | OldIdxOut = OldIdxIn; |
1250 | 90.2k | OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut)20.6k : E69.5k ; |
1251 | 90.2k | } |
1252 | 173k | |
1253 | 173k | // If we are here then there is a Definition at OldIdx. OldIdxOut points |
1254 | 173k | // to the segment starting there. |
1255 | 173k | assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) && |
1256 | 95.1k | "No def?"); |
1257 | 95.1k | VNInfo *OldIdxVNI = OldIdxOut->valno; |
1258 | 95.1k | assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def"); |
1259 | 95.1k | bool OldIdxDefIsDead = OldIdxOut->end.isDead(); |
1260 | 95.1k | |
1261 | 95.1k | // Is there an existing def at NewIdx? |
1262 | 95.1k | SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber()); |
1263 | 95.1k | LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot()); |
1264 | 95.1k | if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) { |
1265 | 0 | assert(NewIdxOut->valno != OldIdxVNI && |
1266 | 0 | "Same value defined more than once?"); |
1267 | 0 | // If OldIdx was a dead def remove it. |
1268 | 0 | if (!OldIdxDefIsDead) { |
1269 | 0 | // Remove segment starting at NewIdx and move begin of OldIdxOut to |
1270 | 0 | // NewIdx so it can take its place. |
1271 | 0 | OldIdxVNI->def = NewIdxDef; |
1272 | 0 | OldIdxOut->start = NewIdxDef; |
1273 | 0 | LR.removeValNo(NewIdxOut->valno); |
1274 | 0 | } else { |
1275 | 0 | // Simply remove the dead def at OldIdx. |
1276 | 0 | LR.removeValNo(OldIdxVNI); |
1277 | 0 | } |
1278 | 95.1k | } else { |
1279 | 95.1k | // Previously nothing was live after NewIdx, so all we have to do now is |
1280 | 95.1k | // move the begin of OldIdxOut to NewIdx. |
1281 | 95.1k | if (!OldIdxDefIsDead) { |
1282 | 76.0k | // Do we have any intermediate Defs between OldIdx and NewIdx? |
1283 | 76.0k | if (OldIdxIn != E && |
1284 | 76.0k | SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)7.17k ) { |
1285 | 456 | // OldIdx is not a dead def and NewIdx is before predecessor start. |
1286 | 456 | LiveRange::iterator NewIdxIn = NewIdxOut; |
1287 | 456 | assert(NewIdxIn == LR.find(NewIdx.getBaseIndex())); |
1288 | 456 | const SlotIndex SplitPos = NewIdxDef; |
1289 | 456 | OldIdxVNI = OldIdxIn->valno; |
1290 | 456 | |
1291 | 456 | // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut. |
1292 | 456 | OldIdxOut->valno->def = OldIdxIn->start; |
1293 | 456 | *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end, |
1294 | 456 | OldIdxOut->valno); |
1295 | 456 | // OldIdxIn and OldIdxVNI are now undef and can be overridden. |
1296 | 456 | // We Slide [NewIdxIn, OldIdxIn) down one position. |
1297 | 456 | // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -| |
1298 | 456 | // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |
1299 | 456 | std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut); |
1300 | 456 | // NewIdxIn is now considered undef so we can reuse it for the moved |
1301 | 456 | // value. |
1302 | 456 | LiveRange::iterator NewSegment = NewIdxIn; |
1303 | 456 | LiveRange::iterator Next = std::next(NewSegment); |
1304 | 456 | if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) { |
1305 | 219 | // There is no gap between NewSegment and its predecessor. |
1306 | 219 | *NewSegment = LiveRange::Segment(Next->start, SplitPos, |
1307 | 219 | Next->valno); |
1308 | 219 | *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI); |
1309 | 219 | Next->valno->def = SplitPos; |
1310 | 237 | } else { |
1311 | 237 | // There is a gap between NewSegment and its predecessor |
1312 | 237 | // Value becomes live in. |
1313 | 237 | *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI); |
1314 | 237 | NewSegment->valno->def = SplitPos; |
1315 | 237 | } |
1316 | 75.6k | } else { |
1317 | 75.6k | // Leave the end point of a live def. |
1318 | 75.6k | OldIdxOut->start = NewIdxDef; |
1319 | 75.6k | OldIdxVNI->def = NewIdxDef; |
1320 | 75.6k | if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)6.71k ) |
1321 | 21 | OldIdxIn->end = NewIdx.getRegSlot(); |
1322 | 75.6k | } |
1323 | 76.0k | } else if (19.0k OldIdxIn != E19.0k |
1324 | 19.0k | && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)18.3k |
1325 | 19.0k | && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)1 ) { |
1326 | 1 | // OldIdxVNI is a dead def that has been moved into the middle of |
1327 | 1 | // another value in LR. That can happen when LR is a whole register, |
1328 | 1 | // but the dead def is a write to a subreg that is dead at NewIdx. |
1329 | 1 | // The dead def may have been moved across other values |
1330 | 1 | // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) |
1331 | 1 | // down one position. |
1332 | 1 | // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | |
1333 | 1 | // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| |
1334 | 1 | std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); |
1335 | 1 | // Modify the segment at NewIdxOut and the following segment to meet at |
1336 | 1 | // the point of the dead def, with the following segment getting |
1337 | 1 | // OldIdxVNI as its value number. |
1338 | 1 | *NewIdxOut = LiveRange::Segment( |
1339 | 1 | NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno); |
1340 | 1 | *(NewIdxOut + 1) = LiveRange::Segment( |
1341 | 1 | NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI); |
1342 | 1 | OldIdxVNI->def = NewIdxDef; |
1343 | 1 | // Modify subsequent segments to be defined by the moved def OldIdxVNI. |
1344 | 1 | for (auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx0 ) |
1345 | 0 | Idx->valno = OldIdxVNI; |
1346 | 1 | // Aggressively remove all dead flags from the former dead definition. |
1347 | 1 | // Kill/dead flags shouldn't be used while live intervals exist; they |
1348 | 1 | // will be reinserted by VirtRegRewriter. |
1349 | 1 | if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx)) |
1350 | 6 | for (MIBundleOperands MO(*KillMI); 1 MO.isValid(); ++MO5 ) |
1351 | 5 | if (MO->isReg() && !MO->isUse()) |
1352 | 1 | MO->setIsDead(false); |
1353 | 19.0k | } else { |
1354 | 19.0k | // OldIdxVNI is a dead def. It may have been moved across other values |
1355 | 19.0k | // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut) |
1356 | 19.0k | // down one position. |
1357 | 19.0k | // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - | |
1358 | 19.0k | // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -| |
1359 | 19.0k | std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut)); |
1360 | 19.0k | // OldIdxVNI can be reused now to build a new dead def segment. |
1361 | 19.0k | LiveRange::iterator NewSegment = NewIdxOut; |
1362 | 19.0k | VNInfo *NewSegmentVNI = OldIdxVNI; |
1363 | 19.0k | *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(), |
1364 | 19.0k | NewSegmentVNI); |
1365 | 19.0k | NewSegmentVNI->def = NewIdxDef; |
1366 | 19.0k | } |
1367 | 95.1k | } |
1368 | 95.1k | } |
1369 | | |
1370 | 0 | void updateRegMaskSlots() { |
1371 | 0 | SmallVectorImpl<SlotIndex>::iterator RI = |
1372 | 0 | llvm::lower_bound(LIS.RegMaskSlots, OldIdx); |
1373 | 0 | assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && |
1374 | 0 | "No RegMask at OldIdx."); |
1375 | 0 | *RI = NewIdx.getRegSlot(); |
1376 | 0 | assert((RI == LIS.RegMaskSlots.begin() || |
1377 | 0 | SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && |
1378 | 0 | "Cannot move regmask instruction above another call"); |
1379 | 0 | assert((std::next(RI) == LIS.RegMaskSlots.end() || |
1380 | 0 | SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && |
1381 | 0 | "Cannot move regmask instruction below another call"); |
1382 | 0 | } |
1383 | | |
1384 | | // Return the last use of reg between NewIdx and OldIdx. |
1385 | | SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg, |
1386 | 71.1k | LaneBitmask LaneMask) { |
1387 | 71.1k | if (TargetRegisterInfo::isVirtualRegister(Reg)) { |
1388 | 50.8k | SlotIndex LastUse = Before; |
1389 | 128k | for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) { |
1390 | 128k | if (MO.isUndef()) |
1391 | 3 | continue; |
1392 | 128k | unsigned SubReg = MO.getSubReg(); |
1393 | 128k | if (SubReg != 0 && LaneMask.any()37.1k |
1394 | 128k | && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none()23.4k ) |
1395 | 16.2k | continue; |
1396 | 112k | |
1397 | 112k | const MachineInstr &MI = *MO.getParent(); |
1398 | 112k | SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); |
1399 | 112k | if (InstSlot > LastUse && InstSlot < OldIdx19.5k ) |
1400 | 11.1k | LastUse = InstSlot.getRegSlot(); |
1401 | 112k | } |
1402 | 50.8k | return LastUse; |
1403 | 50.8k | } |
1404 | 20.2k | |
1405 | 20.2k | // This is a regunit interval, so scanning the use list could be very |
1406 | 20.2k | // expensive. Scan upwards from OldIdx instead. |
1407 | 20.2k | assert(Before < OldIdx && "Expected upwards move"); |
1408 | 20.2k | SlotIndexes *Indexes = LIS.getSlotIndexes(); |
1409 | 20.2k | MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before); |
1410 | 20.2k | |
1411 | 20.2k | // OldIdx may not correspond to an instruction any longer, so set MII to |
1412 | 20.2k | // point to the next instruction after OldIdx, or MBB->end(). |
1413 | 20.2k | MachineBasicBlock::iterator MII = MBB->end(); |
1414 | 20.2k | if (MachineInstr *MI = Indexes->getInstructionFromIndex( |
1415 | 20.2k | Indexes->getNextNonNullIndex(OldIdx))) |
1416 | 20.2k | if (MI->getParent() == MBB) |
1417 | 19.3k | MII = MI; |
1418 | 20.2k | |
1419 | 20.2k | MachineBasicBlock::iterator Begin = MBB->begin(); |
1420 | 86.8k | while (MII != Begin) { |
1421 | 86.8k | if ((--MII)->isDebugInstr()) |
1422 | 2 | continue; |
1423 | 86.8k | SlotIndex Idx = Indexes->getInstructionIndex(*MII); |
1424 | 86.8k | |
1425 | 86.8k | // Stop searching when Before is reached. |
1426 | 86.8k | if (!SlotIndex::isEarlierInstr(Before, Idx)) |
1427 | 20.2k | return Before; |
1428 | 66.5k | |
1429 | 66.5k | // Check if MII uses Reg. |
1430 | 261k | for (MIBundleOperands MO(*MII); 66.5k MO.isValid(); ++MO194k ) |
1431 | 194k | if (MO->isReg() && !MO->isUndef()135k && |
1432 | 194k | TargetRegisterInfo::isPhysicalRegister(MO->getReg())134k && |
1433 | 194k | TRI.hasRegUnit(MO->getReg(), Reg)63.2k ) |
1434 | 0 | return Idx.getRegSlot(); |
1435 | 66.5k | } |
1436 | 20.2k | // Didn't reach Before. It must be the first instruction in the block. |
1437 | 20.2k | return Before0 ; |
1438 | 20.2k | } |
1439 | | }; |
1440 | | |
1441 | 838k | void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) { |
1442 | 838k | // It is fine to move a bundle as a whole, but not an individual instruction |
1443 | 838k | // inside it. |
1444 | 838k | assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) && |
1445 | 838k | "Cannot move instruction in bundle"); |
1446 | 838k | SlotIndex OldIndex = Indexes->getInstructionIndex(MI); |
1447 | 838k | Indexes->removeMachineInstrFromMaps(MI); |
1448 | 838k | SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); |
1449 | 838k | assert(getMBBStartIdx(MI.getParent()) <= OldIndex && |
1450 | 838k | OldIndex < getMBBEndIdx(MI.getParent()) && |
1451 | 838k | "Cannot handle moves across basic block boundaries."); |
1452 | 838k | |
1453 | 838k | HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); |
1454 | 838k | HME.updateAllRanges(&MI); |
1455 | 838k | } |
1456 | | |
1457 | | void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI, |
1458 | | MachineInstr &BundleStart, |
1459 | 0 | bool UpdateFlags) { |
1460 | 0 | SlotIndex OldIndex = Indexes->getInstructionIndex(MI); |
1461 | 0 | SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); |
1462 | 0 | HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); |
1463 | 0 | HME.updateAllRanges(&MI); |
1464 | 0 | } |
1465 | | |
1466 | | void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, |
1467 | | const MachineBasicBlock::iterator End, |
1468 | | const SlotIndex endIdx, |
1469 | | LiveRange &LR, const unsigned Reg, |
1470 | 57 | LaneBitmask LaneMask) { |
1471 | 57 | LiveInterval::iterator LII = LR.find(endIdx); |
1472 | 57 | SlotIndex lastUseIdx; |
1473 | 57 | if (LII == LR.begin()) { |
1474 | 29 | // This happens when the function is called for a subregister that only |
1475 | 29 | // occurs _after_ the range that is to be repaired. |
1476 | 29 | return; |
1477 | 29 | } |
1478 | 28 | if (LII != LR.end() && LII->start < endIdx0 ) |
1479 | 0 | lastUseIdx = LII->end; |
1480 | 28 | else |
1481 | 28 | --LII; |
1482 | 28 | |
1483 | 194 | for (MachineBasicBlock::iterator I = End; I != Begin;) { |
1484 | 166 | --I; |
1485 | 166 | MachineInstr &MI = *I; |
1486 | 166 | if (MI.isDebugInstr()) |
1487 | 0 | continue; |
1488 | 166 | |
1489 | 166 | SlotIndex instrIdx = getInstructionIndex(MI); |
1490 | 166 | bool isStartValid = getInstructionFromIndex(LII->start); |
1491 | 166 | bool isEndValid = getInstructionFromIndex(LII->end); |
1492 | 166 | |
1493 | 166 | // FIXME: This doesn't currently handle early-clobber or multiple removed |
1494 | 166 | // defs inside of the region to repair. |
1495 | 166 | for (MachineInstr::mop_iterator OI = MI.operands_begin(), |
1496 | 166 | OE = MI.operands_end(); |
1497 | 1.15k | OI != OE; ++OI991 ) { |
1498 | 991 | const MachineOperand &MO = *OI; |
1499 | 991 | if (!MO.isReg() || MO.getReg() != Reg808 ) |
1500 | 935 | continue; |
1501 | 56 | |
1502 | 56 | unsigned SubReg = MO.getSubReg(); |
1503 | 56 | LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); |
1504 | 56 | if ((Mask & LaneMask).none()) |
1505 | 0 | continue; |
1506 | 56 | |
1507 | 56 | if (MO.isDef()) { |
1508 | 28 | if (!isStartValid) { |
1509 | 0 | if (LII->end.isDead()) { |
1510 | 0 | SlotIndex prevStart; |
1511 | 0 | if (LII != LR.begin()) |
1512 | 0 | prevStart = std::prev(LII)->start; |
1513 | 0 |
|
1514 | 0 | // FIXME: This could be more efficient if there was a |
1515 | 0 | // removeSegment method that returned an iterator. |
1516 | 0 | LR.removeSegment(*LII, true); |
1517 | 0 | if (prevStart.isValid()) |
1518 | 0 | LII = LR.find(prevStart); |
1519 | 0 | else |
1520 | 0 | LII = LR.begin(); |
1521 | 0 | } else { |
1522 | 0 | LII->start = instrIdx.getRegSlot(); |
1523 | 0 | LII->valno->def = instrIdx.getRegSlot(); |
1524 | 0 | if (MO.getSubReg() && !MO.isUndef()) |
1525 | 0 | lastUseIdx = instrIdx.getRegSlot(); |
1526 | 0 | else |
1527 | 0 | lastUseIdx = SlotIndex(); |
1528 | 0 | continue; |
1529 | 0 | } |
1530 | 28 | } |
1531 | 28 | |
1532 | 28 | if (!lastUseIdx.isValid()) { |
1533 | 0 | VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); |
1534 | 0 | LiveRange::Segment S(instrIdx.getRegSlot(), |
1535 | 0 | instrIdx.getDeadSlot(), VNI); |
1536 | 0 | LII = LR.addSegment(S); |
1537 | 28 | } else if (LII->start != instrIdx.getRegSlot()) { |
1538 | 0 | VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator); |
1539 | 0 | LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); |
1540 | 0 | LII = LR.addSegment(S); |
1541 | 0 | } |
1542 | 28 | |
1543 | 28 | if (MO.getSubReg() && !MO.isUndef()0 ) |
1544 | 0 | lastUseIdx = instrIdx.getRegSlot(); |
1545 | 28 | else |
1546 | 28 | lastUseIdx = SlotIndex(); |
1547 | 28 | } else if (MO.isUse()) { |
1548 | 28 | // FIXME: This should probably be handled outside of this branch, |
1549 | 28 | // either as part of the def case (for defs inside of the region) or |
1550 | 28 | // after the loop over the region. |
1551 | 28 | if (!isEndValid && !LII->end.isBlock()) |
1552 | 28 | LII->end = instrIdx.getRegSlot(); |
1553 | 28 | if (!lastUseIdx.isValid()) |
1554 | 28 | lastUseIdx = instrIdx.getRegSlot(); |
1555 | 28 | } |
1556 | 56 | } |
1557 | 166 | } |
1558 | 28 | } |
1559 | | |
1560 | | void |
1561 | | LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, |
1562 | | MachineBasicBlock::iterator Begin, |
1563 | | MachineBasicBlock::iterator End, |
1564 | 29 | ArrayRef<unsigned> OrigRegs) { |
1565 | 29 | // Find anchor points, which are at the beginning/end of blocks or at |
1566 | 29 | // instructions that already have indexes. |
1567 | 86 | while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin)75 ) |
1568 | 57 | --Begin; |
1569 | 58 | while (End != MBB->end() && !Indexes->hasIndex(*End)) |
1570 | 29 | ++End; |
1571 | 29 | |
1572 | 29 | SlotIndex endIdx; |
1573 | 29 | if (End == MBB->end()) |
1574 | 0 | endIdx = getMBBEndIdx(MBB).getPrevSlot(); |
1575 | 29 | else |
1576 | 29 | endIdx = getInstructionIndex(*End); |
1577 | 29 | |
1578 | 29 | Indexes->repairIndexesInRange(MBB, Begin, End); |
1579 | 29 | |
1580 | 201 | for (MachineBasicBlock::iterator I = End; I != Begin;) { |
1581 | 172 | --I; |
1582 | 172 | MachineInstr &MI = *I; |
1583 | 172 | if (MI.isDebugInstr()) |
1584 | 0 | continue; |
1585 | 172 | for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), |
1586 | 172 | MOE = MI.operands_end(); |
1587 | 1.19k | MOI != MOE; ++MOI1.02k ) { |
1588 | 1.02k | if (MOI->isReg() && |
1589 | 1.02k | TargetRegisterInfo::isVirtualRegister(MOI->getReg())838 && |
1590 | 1.02k | !hasInterval(MOI->getReg())95 ) { |
1591 | 0 | createAndComputeVirtRegInterval(MOI->getReg()); |
1592 | 0 | } |
1593 | 1.02k | } |
1594 | 172 | } |
1595 | 29 | |
1596 | 87 | for (unsigned Reg : OrigRegs) { |
1597 | 87 | if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
1598 | 30 | continue; |
1599 | 57 | |
1600 | 57 | LiveInterval &LI = getInterval(Reg); |
1601 | 57 | // FIXME: Should we support undefs that gain defs? |
1602 | 57 | if (!LI.hasAtLeastOneValue()) |
1603 | 0 | continue; |
1604 | 57 | |
1605 | 57 | for (LiveInterval::SubRange &S : LI.subranges()) |
1606 | 0 | repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); |
1607 | 57 | |
1608 | 57 | repairOldRegInRange(Begin, End, endIdx, LI, Reg); |
1609 | 57 | } |
1610 | 29 | } |
1611 | | |
1612 | 21.7k | void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) { |
1613 | 43.6k | for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit21.8k ) { |
1614 | 21.8k | if (LiveRange *LR = getCachedRegUnit(*Unit)) |
1615 | 530 | if (VNInfo *VNI = LR->getVNInfoAt(Pos)) |
1616 | 460 | LR->removeValNo(VNI); |
1617 | 21.8k | } |
1618 | 21.7k | } |
1619 | | |
1620 | 688k | void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { |
1621 | 688k | // LI may not have the main range computed yet, but its subranges may |
1622 | 688k | // be present. |
1623 | 688k | VNInfo *VNI = LI.getVNInfoAt(Pos); |
1624 | 688k | if (VNI != nullptr) { |
1625 | 688k | assert(VNI->def.getBaseIndex() == Pos.getBaseIndex()); |
1626 | 688k | LI.removeValNo(VNI); |
1627 | 688k | } |
1628 | 688k | |
1629 | 688k | // Also remove the value defined in subranges. |
1630 | 688k | for (LiveInterval::SubRange &S : LI.subranges()) { |
1631 | 90 | if (VNInfo *SVNI = S.getVNInfoAt(Pos)) |
1632 | 89 | if (SVNI->def.getBaseIndex() == Pos.getBaseIndex()) |
1633 | 89 | S.removeValNo(SVNI); |
1634 | 90 | } |
1635 | 688k | LI.removeEmptySubRanges(); |
1636 | 688k | } |
1637 | | |
1638 | | void LiveIntervals::splitSeparateComponents(LiveInterval &LI, |
1639 | 444k | SmallVectorImpl<LiveInterval*> &SplitLIs) { |
1640 | 444k | ConnectedVNInfoEqClasses ConEQ(*this); |
1641 | 444k | unsigned NumComp = ConEQ.Classify(LI); |
1642 | 444k | if (NumComp <= 1) |
1643 | 379k | return; |
1644 | 64.5k | LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); |
1645 | 64.5k | unsigned Reg = LI.reg; |
1646 | 64.5k | const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); |
1647 | 147k | for (unsigned I = 1; I < NumComp; ++I82.4k ) { |
1648 | 82.4k | unsigned NewVReg = MRI->createVirtualRegister(RegClass); |
1649 | 82.4k | LiveInterval &NewLI = createEmptyInterval(NewVReg); |
1650 | 82.4k | SplitLIs.push_back(&NewLI); |
1651 | 82.4k | } |
1652 | 64.5k | ConEQ.Distribute(LI, SplitLIs.data(), *MRI); |
1653 | 64.5k | } |
1654 | | |
1655 | 625 | void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { |
1656 | 625 | assert(LRCalc && "LRCalc not initialized."); |
1657 | 625 | LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); |
1658 | 625 | LRCalc->constructMainRangeFromSubranges(LI); |
1659 | 625 | } |