Line data Source code
1 : //===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file This file implements the LiveInterval analysis pass which is used
11 : /// by the Linear Scan Register allocator. This pass linearizes the
12 : /// basic blocks of the function in DFS order and computes live intervals for
13 : /// each virtual and physical register.
14 : //
15 : //===----------------------------------------------------------------------===//
16 :
17 : #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 : #include "LiveRangeCalc.h"
19 : #include "llvm/ADT/ArrayRef.h"
20 : #include "llvm/ADT/DepthFirstIterator.h"
21 : #include "llvm/ADT/SmallPtrSet.h"
22 : #include "llvm/ADT/SmallVector.h"
23 : #include "llvm/ADT/iterator_range.h"
24 : #include "llvm/Analysis/AliasAnalysis.h"
25 : #include "llvm/CodeGen/LiveInterval.h"
26 : #include "llvm/CodeGen/LiveVariables.h"
27 : #include "llvm/CodeGen/MachineBasicBlock.h"
28 : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
29 : #include "llvm/CodeGen/MachineDominators.h"
30 : #include "llvm/CodeGen/MachineFunction.h"
31 : #include "llvm/CodeGen/MachineInstr.h"
32 : #include "llvm/CodeGen/MachineInstrBundle.h"
33 : #include "llvm/CodeGen/MachineOperand.h"
34 : #include "llvm/CodeGen/MachineRegisterInfo.h"
35 : #include "llvm/CodeGen/Passes.h"
36 : #include "llvm/CodeGen/SlotIndexes.h"
37 : #include "llvm/CodeGen/VirtRegMap.h"
38 : #include "llvm/MC/LaneBitmask.h"
39 : #include "llvm/MC/MCRegisterInfo.h"
40 : #include "llvm/Pass.h"
41 : #include "llvm/Support/BlockFrequency.h"
42 : #include "llvm/Support/CommandLine.h"
43 : #include "llvm/Support/Compiler.h"
44 : #include "llvm/Support/Debug.h"
45 : #include "llvm/Support/MathExtras.h"
46 : #include "llvm/Support/raw_ostream.h"
47 : #include "llvm/Target/TargetRegisterInfo.h"
48 : #include "llvm/Target/TargetSubtargetInfo.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 53254 : INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
63 : "Live Interval Analysis", false, false)
64 53254 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
65 53254 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
66 53254 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
67 1459673 : 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 72306 : cl::opt<bool> UseSegmentSetForPhysRegs(
81 216918 : "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
82 216918 : cl::desc(
83 72306 : "Use segment set for the computation of the live ranges of physregs."));
84 :
85 : } // end namespace llvm
86 :
87 18355 : void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
88 18355 : AU.setPreservesCFG();
89 18355 : AU.addRequired<AAResultsWrapperPass>();
90 18355 : AU.addPreserved<AAResultsWrapperPass>();
91 18355 : AU.addPreserved<LiveVariables>();
92 36710 : AU.addPreservedID(MachineLoopInfoID);
93 18355 : AU.addRequiredTransitiveID(MachineDominatorsID);
94 36710 : AU.addPreservedID(MachineDominatorsID);
95 18355 : AU.addPreserved<SlotIndexes>();
96 18355 : AU.addRequiredTransitive<SlotIndexes>();
97 18355 : MachineFunctionPass::getAnalysisUsage(AU);
98 18355 : }
99 :
100 128485 : LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {
101 18355 : initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
102 18355 : }
103 :
104 145951 : LiveIntervals::~LiveIntervals() {
105 18243 : delete LRCalc;
106 36488 : }
107 :
108 157431 : void LiveIntervals::releaseMemory() {
109 : // Free the live intervals themselves.
110 3396035 : for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
111 7751855 : delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
112 314862 : VirtRegIntervals.clear();
113 314862 : RegMaskSlots.clear();
114 314862 : RegMaskBits.clear();
115 314862 : RegMaskBlocks.clear();
116 :
117 72673589 : for (LiveRange *LR : RegUnitRanges)
118 72201296 : delete LR;
119 314862 : RegUnitRanges.clear();
120 :
121 : // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
122 157431 : VNInfoAllocator.Reset();
123 157431 : }
124 :
125 157407 : bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
126 157407 : MF = &fn;
127 157407 : MRI = &MF->getRegInfo();
128 157407 : TRI = MF->getSubtarget().getRegisterInfo();
129 157407 : TII = MF->getSubtarget().getInstrInfo();
130 314814 : AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
131 157407 : Indexes = &getAnalysis<SlotIndexes>();
132 157407 : DomTree = &getAnalysis<MachineDominatorTree>();
133 :
134 157407 : if (!LRCalc)
135 17831 : LRCalc = new LiveRangeCalc();
136 :
137 : // Allocate space for all virtual registers.
138 472221 : VirtRegIntervals.resize(MRI->getNumVirtRegs());
139 :
140 157407 : computeVirtRegs();
141 157407 : computeRegMasks();
142 157407 : computeLiveInRegUnits();
143 :
144 157407 : if (EnablePrecomputePhysRegs) {
145 : // For stress testing, precompute live ranges of all physical register
146 : // units, including reserved registers.
147 0 : for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
148 0 : getRegUnit(i);
149 : }
150 : DEBUG(dump());
151 157407 : return true;
152 : }
153 :
154 0 : void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
155 0 : OS << "********** INTERVALS **********\n";
156 :
157 : // Dump the regunits.
158 0 : for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
159 0 : if (LiveRange *LR = RegUnitRanges[Unit])
160 0 : OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n';
161 :
162 : // Dump the virtregs.
163 0 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
164 0 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
165 0 : if (hasInterval(Reg))
166 0 : OS << getInterval(Reg) << '\n';
167 : }
168 :
169 0 : OS << "RegMasks:";
170 0 : for (SlotIndex Idx : RegMaskSlots)
171 0 : OS << ' ' << Idx;
172 0 : OS << '\n';
173 :
174 0 : printInstrs(OS);
175 0 : }
176 :
177 0 : void LiveIntervals::printInstrs(raw_ostream &OS) const {
178 0 : OS << "********** MACHINEINSTRS **********\n";
179 0 : MF->print(OS, Indexes);
180 0 : }
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 2217671 : LiveInterval* LiveIntervals::createInterval(unsigned reg) {
189 2217671 : float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F;
190 4435342 : return new LiveInterval(reg, Weight);
191 : }
192 :
193 : /// Compute the live interval of a virtual register, based on defs and uses.
194 2137535 : void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
195 : assert(LRCalc && "LRCalc not initialized.");
196 : assert(LI.empty() && "Should only compute empty intervals.");
197 4275070 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
198 4275070 : LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
199 2137535 : computeDeadValues(LI, nullptr);
200 2137535 : }
201 :
202 157407 : void LiveIntervals::computeVirtRegs() {
203 3276496 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
204 2961682 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
205 5923364 : if (MRI->reg_nodbg_empty(Reg))
206 862887 : continue;
207 : createAndComputeVirtRegInterval(Reg);
208 : }
209 157407 : }
210 :
211 157407 : void LiveIntervals::computeRegMasks() {
212 314814 : RegMaskBlocks.resize(MF->getNumBlockIDs());
213 :
214 : // Find all instructions with regmask operands.
215 785015 : for (const MachineBasicBlock &MBB : *MF) {
216 625588 : std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
217 625588 : RMB.first = RegMaskSlots.size();
218 :
219 : // Some block starts, such as EH funclets, create masks.
220 312794 : if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
221 228 : RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
222 114 : RegMaskBits.push_back(Mask);
223 : }
224 :
225 10496550 : for (const MachineInstr &MI : MBB) {
226 22088537 : for (const MachineOperand &MO : MI.operands()) {
227 17465850 : if (!MO.isRegMask())
228 17277193 : continue;
229 377314 : RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
230 188657 : RegMaskBits.push_back(MO.getRegMask());
231 : }
232 : }
233 :
234 : // Some block ends, such as funclet returns, create masks. Put the mask on
235 : // the last instruction of the block, because MBB slot index intervals are
236 : // half-open.
237 312794 : if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
238 : assert(!MBB.empty() && "empty return block?");
239 142 : RegMaskSlots.push_back(
240 284 : Indexes->getInstructionIndex(MBB.back()).getRegSlot());
241 71 : RegMaskBits.push_back(Mask);
242 : }
243 :
244 : // Compute the number of register mask instructions in this block.
245 625588 : RMB.second = RegMaskSlots.size() - RMB.first;
246 : }
247 157407 : }
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 770264 : void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
264 : assert(LRCalc && "LRCalc not initialized.");
265 1540528 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
266 :
267 : // The physregs aliasing Unit are the roots and their super-registers.
268 : // Create all values as dead defs before extending to uses. Note that roots
269 : // may share super-registers. That's OK because createDeadDefs() is
270 : // idempotent. It is very rare for a register unit to have multiple roots, so
271 : // uniquing super-registers is probably not worthwhile.
272 770264 : bool IsReserved = false;
273 2311133 : for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
274 770605 : bool IsRootReserved = true;
275 770605 : for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
276 5203073 : Super.isValid(); ++Super) {
277 8864936 : unsigned Reg = *Super;
278 8864936 : if (!MRI->reg_empty(Reg))
279 424803 : LRCalc->createDeadDefs(LR, Reg);
280 : // A register unit is considered reserved if all its roots and all their
281 : // super registers are reserved.
282 8864936 : if (!MRI->isReserved(Reg))
283 4348357 : IsRootReserved = false;
284 : }
285 770605 : IsReserved |= IsRootReserved;
286 : }
287 : assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
288 : "reserved computation mismatch");
289 :
290 : // Now extend LR to reach all uses.
291 : // Ignore uses of reserved registers. We only track defs of those.
292 770264 : if (!IsReserved) {
293 2295069 : for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
294 765023 : for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
295 5175259 : Super.isValid(); ++Super) {
296 8820472 : unsigned Reg = *Super;
297 8820472 : if (!MRI->reg_empty(Reg))
298 419873 : LRCalc->extendToUses(LR, Reg);
299 : }
300 : }
301 : }
302 :
303 : // Flush the segment set to the segment vector.
304 770264 : if (UseSegmentSetForPhysRegs)
305 770264 : LR.flushSegmentSet();
306 770264 : }
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 157407 : void LiveIntervals::computeLiveInRegUnits() {
312 157407 : RegUnitRanges.resize(TRI->getNumRegUnits());
313 : DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
314 :
315 : // Keep track of the live range sets allocated.
316 314814 : SmallVector<unsigned, 8> NewRanges;
317 :
318 : // Check all basic blocks for live-ins.
319 785015 : for (const MachineBasicBlock &MBB : *MF) {
320 : // We only care about ABI blocks: Entry + landing pads.
321 804792 : if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
322 164156 : continue;
323 :
324 : // Create phi-defs at Begin for all live-in registers.
325 297276 : SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
326 : DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber());
327 584156 : for (const auto &LI : MBB.liveins()) {
328 945615 : for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
329 743710 : unsigned Unit = *Units;
330 743710 : LiveRange *LR = RegUnitRanges[Unit];
331 371855 : if (!LR) {
332 : // Use segment set to speed-up initial computation of the live range.
333 589030 : LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
334 294515 : NewRanges.push_back(Unit);
335 : }
336 371855 : VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
337 : (void)VNI;
338 : DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
339 : }
340 : }
341 : DEBUG(dbgs() << '\n');
342 : }
343 : DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
344 :
345 : // Compute the 'normal' part of the ranges.
346 766736 : for (unsigned Unit : NewRanges)
347 589030 : computeRegUnitRange(*RegUnitRanges[Unit], Unit);
348 157407 : }
349 :
350 94028 : static void createSegmentsForValues(LiveRange &LR,
351 : iterator_range<LiveInterval::vni_iterator> VNIs) {
352 210395 : for (VNInfo *VNI : VNIs) {
353 116367 : if (VNI->isUnused())
354 1233 : continue;
355 115134 : SlotIndex Def = VNI->def;
356 230268 : LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
357 : }
358 94028 : }
359 :
360 : using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
361 :
362 94028 : static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
363 : ShrinkToUsesWorkList &WorkList,
364 : const LiveRange &OldRange) {
365 : // Keep track of the PHIs that are in use.
366 188056 : SmallPtrSet<VNInfo*, 8> UsedPHIs;
367 : // Blocks that have already been added to WorkList as live-out.
368 94028 : SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
369 :
370 : // Extend intervals to reach all uses in WorkList.
371 13376950 : while (!WorkList.empty()) {
372 26565844 : SlotIndex Idx = WorkList.back().first;
373 26565844 : VNInfo *VNI = WorkList.back().second;
374 26565844 : WorkList.pop_back();
375 13282922 : const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
376 13282922 : SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
377 :
378 : // Extend the live range for VNI to be live at Idx.
379 13282922 : if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
380 : assert(ExtVNI == VNI && "Unexpected existing value number");
381 : (void)ExtVNI;
382 : // Is this a PHIDef we haven't seen before?
383 39527257 : if (!VNI->isPHIDef() || VNI->def != BlockStart ||
384 13181211 : !UsedPHIs.insert(VNI).second)
385 13162074 : continue;
386 : // The PHI is live, make sure the predecessors are live-out.
387 37475 : for (const MachineBasicBlock *Pred : MBB->predecessors()) {
388 19545 : if (!LiveOut.insert(Pred).second)
389 1223 : continue;
390 18322 : SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
391 : // A predecessor is not required to have a live-out value for a PHI.
392 18322 : if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
393 36636 : WorkList.push_back(std::make_pair(Stop, PVNI));
394 : }
395 8965 : continue;
396 : }
397 :
398 : // VNI is live-in to MBB.
399 : DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
400 223766 : LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
401 :
402 : // Make sure VNI is live-out from the predecessors.
403 366931 : for (const MachineBasicBlock *Pred : MBB->predecessors()) {
404 143165 : if (!LiveOut.insert(Pred).second)
405 33675 : continue;
406 109490 : SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
407 : assert(OldRange.getVNInfoBefore(Stop) == VNI &&
408 : "Wrong value out of predecessor");
409 218980 : WorkList.push_back(std::make_pair(Stop, VNI));
410 : }
411 : }
412 94028 : }
413 :
414 93799 : bool LiveIntervals::shrinkToUses(LiveInterval *li,
415 : SmallVectorImpl<MachineInstr*> *dead) {
416 : DEBUG(dbgs() << "Shrink: " << *li << '\n');
417 : assert(TargetRegisterInfo::isVirtualRegister(li->reg)
418 : && "Can only shrink virtual registers");
419 :
420 : // Shrink subregister live ranges.
421 93799 : bool NeedsCleanup = false;
422 187767 : for (LiveInterval::SubRange &S : li->subranges()) {
423 169 : shrinkToUses(S, li->reg);
424 338 : if (S.empty())
425 0 : NeedsCleanup = true;
426 : }
427 93799 : if (NeedsCleanup)
428 0 : li->removeEmptySubRanges();
429 :
430 : // Find all the values used, including PHI kills.
431 187598 : ShrinkToUsesWorkList WorkList;
432 :
433 : // Visit all instructions reading li->reg.
434 93799 : unsigned Reg = li->reg;
435 26702470 : for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
436 26514387 : if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg))
437 205386 : continue;
438 39464232 : SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
439 13154744 : LiveQueryResult LRQ = li->Query(Idx);
440 13154744 : VNInfo *VNI = LRQ.valueIn();
441 13154744 : if (!VNI) {
442 : // This shouldn't happen: readsVirtualRegister returns true, but there is
443 : // no live value. It is likely caused by a target getting <undef> flags
444 : // wrong.
445 : DEBUG(dbgs() << Idx << '\t' << UseMI
446 : << "Warning: Instr claims to read non-existent value in "
447 : << *li << '\n');
448 2 : continue;
449 : }
450 : // Special case: An early-clobber tied operand reads and writes the
451 : // register one slot early.
452 13204991 : if (VNInfo *DefVNI = LRQ.valueDefined())
453 5365 : Idx = DefVNI->def;
454 :
455 26309484 : WorkList.push_back(std::make_pair(Idx, VNI));
456 : }
457 :
458 : // Create new live ranges with only minimal live segments per def.
459 187598 : LiveRange NewLR;
460 375196 : createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
461 93799 : extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
462 :
463 : // Move the trimmed segments back.
464 93799 : li->segments.swap(NewLR.segments);
465 :
466 : // Handle dead values.
467 93799 : bool CanSeparate = computeDeadValues(*li, dead);
468 : DEBUG(dbgs() << "Shrunk: " << *li << '\n');
469 93799 : return CanSeparate;
470 : }
471 :
472 2231334 : bool LiveIntervals::computeDeadValues(LiveInterval &LI,
473 : SmallVectorImpl<MachineInstr*> *dead) {
474 2231334 : bool MayHaveSplitComponents = false;
475 9299704 : for (VNInfo *VNI : LI.valnos) {
476 2605702 : if (VNI->isUnused())
477 1195 : continue;
478 2604507 : SlotIndex Def = VNI->def;
479 2604507 : LiveRange::iterator I = LI.FindSegmentContaining(Def);
480 : assert(I != LI.end() && "Missing segment for VNI");
481 :
482 : // Is the register live before? Otherwise we may have to add a read-undef
483 : // flag for subregister defs.
484 2604507 : unsigned VReg = LI.reg;
485 2892507 : if (MRI->shouldTrackSubRegLiveness(VReg)) {
486 944583 : if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
487 416300 : MachineInstr *MI = getInstructionFromIndex(Def);
488 208150 : MI->setRegisterDefReadUndef(VReg);
489 : }
490 : }
491 :
492 5209014 : if (I->end != Def.getDeadSlot())
493 2552718 : continue;
494 51789 : if (VNI->isPHIDef()) {
495 : // This is a dead PHI. Remove it.
496 716 : VNI->markUnused();
497 1432 : LI.removeSegment(I);
498 : DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
499 716 : MayHaveSplitComponents = true;
500 : } else {
501 : // This is a dead def. Make sure the instruction knows.
502 102146 : MachineInstr *MI = getInstructionFromIndex(Def);
503 : assert(MI && "No instruction defining live value");
504 51073 : MI->addRegisterDead(LI.reg, TRI);
505 51073 : if (dead && MI->allDefsAreDead()) {
506 : DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
507 44190 : dead->push_back(MI);
508 : }
509 : }
510 : }
511 2231334 : return MayHaveSplitComponents;
512 : }
513 :
514 229 : void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
515 : DEBUG(dbgs() << "Shrink: " << SR << '\n');
516 : assert(TargetRegisterInfo::isVirtualRegister(Reg)
517 : && "Can only shrink virtual registers");
518 : // Find all the values used, including PHI kills.
519 458 : ShrinkToUsesWorkList WorkList;
520 :
521 : // Visit all instructions reading Reg.
522 229 : SlotIndex LastIdx;
523 1427 : for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
524 : // Skip "undef" uses.
525 5 : if (!MO.readsReg())
526 373 : continue;
527 : // Maybe the operand is for a subregister we don't care about.
528 735 : unsigned SubReg = MO.getSubReg();
529 735 : if (SubReg != 0) {
530 1192 : LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
531 596 : if ((LaneMask & SR.LaneMask).none())
532 332 : continue;
533 : }
534 : // We only need to visit each instruction once.
535 403 : MachineInstr *UseMI = MO.getParent();
536 1209 : SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
537 403 : if (Idx == LastIdx)
538 31 : continue;
539 372 : LastIdx = Idx;
540 :
541 372 : LiveQueryResult LRQ = SR.Query(Idx);
542 372 : VNInfo *VNI = LRQ.valueIn();
543 : // For Subranges it is possible that only undef values are left in that
544 : // part of the subregister, so there is no real liverange at the use
545 372 : if (!VNI)
546 0 : continue;
547 :
548 : // Special case: An early-clobber tied operand reads and writes the
549 : // register one slot early.
550 590 : if (VNInfo *DefVNI = LRQ.valueDefined())
551 52 : Idx = DefVNI->def;
552 :
553 744 : WorkList.push_back(std::make_pair(Idx, VNI));
554 : }
555 :
556 : // Create a new live ranges with only minimal live segments per def.
557 458 : LiveRange NewLR;
558 916 : createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
559 229 : extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
560 :
561 : // Move the trimmed ranges back.
562 229 : SR.segments.swap(NewLR.segments);
563 :
564 : // Remove dead PHI value numbers
565 1211 : for (VNInfo *VNI : SR.valnos) {
566 524 : if (VNI->isUnused())
567 38 : continue;
568 972 : const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
569 : assert(Segment != nullptr && "Missing segment for VNI");
570 1458 : if (Segment->end != VNI->def.getDeadSlot())
571 418 : continue;
572 68 : if (VNI->isPHIDef()) {
573 : // This is a dead PHI. Remove it.
574 : DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
575 16 : VNI->markUnused();
576 16 : SR.removeSegment(*Segment);
577 : }
578 : }
579 :
580 : DEBUG(dbgs() << "Shrunk: " << SR << '\n');
581 229 : }
582 :
583 72823 : void LiveIntervals::extendToIndices(LiveRange &LR,
584 : ArrayRef<SlotIndex> Indices,
585 : ArrayRef<SlotIndex> Undefs) {
586 : assert(LRCalc && "LRCalc not initialized.");
587 145646 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
588 361914 : for (SlotIndex Idx : Indices)
589 216268 : LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
590 72823 : }
591 :
592 129926 : void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
593 : SmallVectorImpl<SlotIndex> *EndPoints) {
594 129926 : LiveQueryResult LRQ = LR.Query(Kill);
595 129926 : VNInfo *VNI = LRQ.valueOutOrDead();
596 129926 : if (!VNI)
597 129201 : return;
598 :
599 115326 : MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
600 230652 : SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
601 :
602 : // If VNI isn't live out from KillMBB, the value is trivially pruned.
603 230652 : if (LRQ.endPoint() < MBBEnd) {
604 114601 : LR.removeSegment(Kill, LRQ.endPoint());
605 114601 : if (EndPoints) EndPoints->push_back(LRQ.endPoint());
606 : return;
607 : }
608 :
609 : // VNI is live out of KillMBB.
610 725 : LR.removeSegment(Kill, MBBEnd);
611 725 : if (EndPoints) EndPoints->push_back(MBBEnd);
612 :
613 : // Find all blocks that are reachable from KillMBB without leaving VNI's live
614 : // range. It is possible that KillMBB itself is reachable, so start a DFS
615 : // from each successor.
616 : using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;
617 1450 : VisitedTy Visited;
618 2604 : for (MachineBasicBlock *Succ : KillMBB->successors()) {
619 : for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
620 3462 : I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
621 4429 : I != E;) {
622 3275 : MachineBasicBlock *MBB = *I;
623 :
624 : // Check if VNI is live in to MBB.
625 6550 : SlotIndex MBBStart, MBBEnd;
626 13100 : std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
627 3275 : LiveQueryResult LRQ = LR.Query(MBBStart);
628 4028 : if (LRQ.valueIn() != VNI) {
629 : // This block isn't part of the VNI segment. Prune the search.
630 753 : I.skipChildren();
631 1908 : continue;
632 : }
633 :
634 : // Prune the search if VNI is killed in MBB.
635 5446 : if (LRQ.endPoint() < MBBEnd) {
636 402 : LR.removeSegment(MBBStart, LRQ.endPoint());
637 402 : if (EndPoints) EndPoints->push_back(LRQ.endPoint());
638 402 : I.skipChildren();
639 402 : continue;
640 : }
641 :
642 : // VNI is live through MBB.
643 2120 : LR.removeSegment(MBBStart, MBBEnd);
644 2120 : if (EndPoints) EndPoints->push_back(MBBEnd);
645 2120 : ++I;
646 : }
647 : }
648 : }
649 :
650 : //===----------------------------------------------------------------------===//
651 : // Register allocator hooks.
652 : //
653 :
654 134820 : void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
655 : // Keep track of regunit ranges.
656 269640 : SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
657 : // Keep track of subregister ranges.
658 : SmallVector<std::pair<const LiveInterval::SubRange*,
659 269640 : LiveRange::const_iterator>, 4> SRs;
660 :
661 2704104 : for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
662 2434464 : unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
663 4868928 : if (MRI->reg_nodbg_empty(Reg))
664 1255358 : continue;
665 1179106 : const LiveInterval &LI = getInterval(Reg);
666 2358212 : if (LI.empty())
667 6037 : continue;
668 :
669 : // Find the regunit intervals for the assigned register. They may overlap
670 : // the virtual register live range, cancelling any kills.
671 1173069 : RU.clear();
672 5076285 : for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid();
673 : ++Unit) {
674 3114156 : const LiveRange &RURange = getRegUnit(*Unit);
675 1557078 : if (RURange.empty())
676 747572 : continue;
677 3238024 : RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
678 : }
679 :
680 1173069 : if (MRI->subRegLivenessEnabled()) {
681 205182 : SRs.clear();
682 550301 : for (const LiveInterval::SubRange &SR : LI.subranges()) {
683 559748 : SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
684 : }
685 : }
686 :
687 : // Every instruction that kills Reg corresponds to a segment range end
688 : // point.
689 5094071 : for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
690 : ++RI) {
691 : // A block index indicates an MBB edge.
692 3149728 : if (RI->end.isBlock())
693 126690 : continue;
694 2896348 : MachineInstr *MI = getInstructionFromIndex(RI->end);
695 1448174 : if (!MI)
696 0 : continue;
697 :
698 : // Check if any of the regunits are live beyond the end of RI. That could
699 : // happen when a physreg is defined as a copy of a virtreg:
700 : //
701 : // %EAX = COPY %vreg5
702 : // FOO %vreg5 <--- MI, cancel kill because %EAX is live.
703 : // BAR %EAX<kill>
704 : //
705 : // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
706 5310348 : for (auto &RUP : RU) {
707 968533 : const LiveRange &RURange = *RUP.first;
708 968533 : LiveRange::const_iterator &I = RUP.second;
709 1937066 : if (I == RURange.end())
710 285383 : continue;
711 683150 : I = RURange.advanceTo(I, RI->end);
712 2045757 : if (I == RURange.end() || I->start >= RI->end)
713 680443 : continue;
714 : // I is overlapping RI.
715 : goto CancelKill;
716 : }
717 :
718 1445467 : if (MRI->subRegLivenessEnabled()) {
719 : // When reading a partial undefined value we must not add a kill flag.
720 : // The regalloc might have used the undef lane for something else.
721 : // Example:
722 : // %vreg1 = ... ; R32: %vreg1
723 : // %vreg2:high16 = ... ; R64: %vreg2
724 : // = read %vreg2<kill> ; R64: %vreg2
725 : // = read %vreg1 ; R32: %vreg1
726 : // The <kill> flag is correct for %vreg2, but the register allocator may
727 : // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0
728 : // are actually never written by %vreg2. After assignment the <kill>
729 : // flag at the read instruction is invalid.
730 267599 : LaneBitmask DefinedLanesMask;
731 267599 : if (!SRs.empty()) {
732 : // Compute a mask of lanes that are defined.
733 : DefinedLanesMask = LaneBitmask::getNone();
734 819253 : for (auto &SRP : SRs) {
735 355717 : const LiveInterval::SubRange &SR = *SRP.first;
736 355717 : LiveRange::const_iterator &I = SRP.second;
737 711434 : if (I == SR.end())
738 34291 : continue;
739 321426 : I = SR.advanceTo(I, RI->end);
740 1066095 : if (I == SR.end() || I->start >= RI->end)
741 206776 : continue;
742 : // I is overlapping RI
743 : DefinedLanesMask |= SR.LaneMask;
744 : }
745 : } else
746 : DefinedLanesMask = LaneBitmask::getAll();
747 :
748 267599 : bool IsFullWrite = false;
749 1723021 : for (const MachineOperand &MO : MI->operands()) {
750 2731696 : if (!MO.isReg() || MO.getReg() != Reg)
751 1227497 : continue;
752 276702 : if (MO.isUse()) {
753 : // Reading any undefined lanes?
754 638877 : LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
755 425918 : if ((UseMask & ~DefinedLanesMask).any())
756 : goto CancelKill;
757 63743 : } else if (MO.getSubReg() == 0) {
758 : // Writing to the full register?
759 : assert(MO.isDef());
760 3124 : IsFullWrite = true;
761 : }
762 : }
763 :
764 : // If an instruction writes to a subregister, a new segment starts in
765 : // the LiveInterval. But as this is only overriding part of the register
766 : // adding kill-flags is not correct here after registers have been
767 : // assigned.
768 218822 : if (!IsFullWrite) {
769 : // Next segment has to be adjacent in the subregister write case.
770 216014 : LiveRange::const_iterator N = std::next(RI);
771 493859 : if (N != LI.end() && N->start == RI->end)
772 : goto CancelKill;
773 : }
774 : }
775 :
776 1337650 : MI->addRegisterKilled(Reg, nullptr);
777 1337650 : continue;
778 110524 : CancelKill:
779 110524 : MI->clearRegisterKills(Reg, nullptr);
780 1337650 : }
781 : }
782 134820 : }
783 :
784 : MachineBasicBlock*
785 5252933 : LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
786 : // A local live range must be fully contained inside the block, meaning it is
787 : // defined and killed at instructions, not at block boundaries. It is not
788 : // live in or or out of any block.
789 : //
790 : // It is technically possible to have a PHI-defined live range identical to a
791 : // single block, but we are going to return false in that case.
792 :
793 10505866 : SlotIndex Start = LI.beginIndex();
794 5252933 : if (Start.isBlock())
795 : return nullptr;
796 :
797 10499062 : SlotIndex Stop = LI.endIndex();
798 5249531 : if (Stop.isBlock())
799 : return nullptr;
800 :
801 : // getMBBFromIndex doesn't need to search the MBB table when both indexes
802 : // belong to proper instructions.
803 4993903 : MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
804 4993903 : MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
805 4993903 : return MBB1 == MBB2 ? MBB1 : nullptr;
806 : }
807 :
808 : bool
809 39 : LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
810 220 : for (const VNInfo *PHI : LI.valnos) {
811 214 : if (PHI->isUnused() || !PHI->isPHIDef())
812 99 : continue;
813 16 : const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
814 : // Conservatively return true instead of scanning huge predecessor lists.
815 8 : if (PHIMBB->pred_size() > 100)
816 : return true;
817 20 : for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
818 32 : if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
819 : return true;
820 : }
821 : return false;
822 : }
823 :
824 3941371 : float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
825 : const MachineBlockFrequencyInfo *MBFI,
826 : const MachineInstr &MI) {
827 3941371 : BlockFrequency Freq = MBFI->getBlockFreq(MI.getParent());
828 3941371 : const float Scale = 1.0f / MBFI->getEntryFreq();
829 7882742 : return (isDef + isUse) * (Freq.getFrequency() * Scale);
830 : }
831 :
832 : LiveRange::Segment
833 0 : LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) {
834 0 : LiveInterval& Interval = createEmptyInterval(reg);
835 0 : VNInfo *VN = Interval.getNextValue(
836 0 : SlotIndex(getInstructionIndex(startInst).getRegSlot()),
837 0 : getVNInfoAllocator());
838 0 : LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
839 0 : getMBBEndIdx(startInst.getParent()), VN);
840 0 : Interval.addSegment(S);
841 :
842 0 : return S;
843 : }
844 :
845 : //===----------------------------------------------------------------------===//
846 : // Register mask functions
847 : //===----------------------------------------------------------------------===//
848 :
849 1356977 : bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
850 : BitVector &UsableRegs) {
851 2713954 : if (LI.empty())
852 : return false;
853 4070931 : LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
854 :
855 : // Use a smaller arrays for local live ranges.
856 1356977 : ArrayRef<SlotIndex> Slots;
857 1356977 : ArrayRef<const uint32_t*> Bits;
858 1356977 : if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
859 2382140 : Slots = getRegMaskSlotsInBlock(MBB->getNumber());
860 2382140 : Bits = getRegMaskBitsInBlock(MBB->getNumber());
861 : } else {
862 165907 : Slots = getRegMaskSlots();
863 165907 : Bits = getRegMaskBits();
864 : }
865 :
866 : // We are going to enumerate all the register mask slots contained in LI.
867 : // Start with a binary search of RegMaskSlots to find a starting point.
868 : ArrayRef<SlotIndex>::iterator SlotI =
869 4070931 : std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
870 1356977 : ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
871 :
872 : // No slots in range, LI begins after the last call.
873 1356977 : if (SlotI == SlotE)
874 : return false;
875 :
876 : bool Found = false;
877 : while (true) {
878 : assert(*SlotI >= LiveI->start);
879 : // Loop over all slots overlapping this segment.
880 3779926 : while (*SlotI < LiveI->end) {
881 : // *SlotI overlaps LI. Collect mask bits.
882 2755058 : if (!Found) {
883 : // This is the first overlap. Initialize UsableRegs to all ones.
884 142617 : UsableRegs.clear();
885 142617 : UsableRegs.resize(TRI->getNumRegs(), true);
886 142617 : Found = true;
887 : }
888 : // Remove usable registers clobbered by this mask.
889 8265174 : UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
890 2755058 : if (++SlotI == SlotE)
891 : return Found;
892 : }
893 : // *SlotI is beyond the current LI segment.
894 1024868 : LiveI = LI.advanceTo(LiveI, *SlotI);
895 1024868 : if (LiveI == LiveE)
896 : return Found;
897 : // Advance SlotI until it overlaps.
898 2792236 : while (*SlotI < LiveI->start)
899 2238691 : if (++SlotI == SlotE)
900 : return Found;
901 : }
902 : }
903 :
904 : //===----------------------------------------------------------------------===//
905 : // IntervalUpdate class.
906 : //===----------------------------------------------------------------------===//
907 :
908 : /// Toolkit used by handleMove to trim or extend live intervals.
909 391142 : class LiveIntervals::HMEditor {
910 : private:
911 : LiveIntervals& LIS;
912 : const MachineRegisterInfo& MRI;
913 : const TargetRegisterInfo& TRI;
914 : SlotIndex OldIdx;
915 : SlotIndex NewIdx;
916 : SmallPtrSet<LiveRange*, 8> Updated;
917 : bool UpdateFlags;
918 :
919 : public:
920 : HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
921 : const TargetRegisterInfo& TRI,
922 : SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
923 195571 : : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
924 391142 : UpdateFlags(UpdateFlags) {}
925 :
926 : // FIXME: UpdateFlags is a workaround that creates live intervals for all
927 : // physregs, even those that aren't needed for regalloc, in order to update
928 : // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
929 : // flags, and postRA passes will use a live register utility instead.
930 225128 : LiveRange *getRegUnitLI(unsigned Unit) {
931 225128 : if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
932 64294 : return &LIS.getRegUnit(Unit);
933 321668 : return LIS.getCachedRegUnit(Unit);
934 : }
935 :
936 : /// Update all live ranges touched by MI, assuming a move from OldIdx to
937 : /// NewIdx.
938 195571 : void updateAllRanges(MachineInstr *MI) {
939 : DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
940 195571 : bool hasRegMask = false;
941 1369213 : for (MachineOperand &MO : MI->operands()) {
942 1173642 : if (MO.isRegMask())
943 0 : hasRegMask = true;
944 1173642 : if (!MO.isReg())
945 600416 : continue;
946 573226 : if (MO.isUse()) {
947 387670 : if (!MO.readsReg())
948 204 : continue;
949 : // Aggressively clear all kill flags.
950 : // They are reinserted by VirtRegRewriter.
951 : MO.setIsKill(false);
952 : }
953 :
954 573022 : unsigned Reg = MO.getReg();
955 573022 : if (!Reg)
956 46430 : continue;
957 526592 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
958 357066 : LiveInterval &LI = LIS.getInterval(Reg);
959 357066 : if (LI.hasSubRanges()) {
960 74809 : unsigned SubReg = MO.getSubReg();
961 61315 : LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
962 197439 : : MRI.getMaxLaneMaskForVReg(Reg);
963 407554 : for (LiveInterval::SubRange &S : LI.subranges()) {
964 515872 : if ((S.LaneMask & LaneMask).none())
965 150043 : continue;
966 107893 : updateRange(S, Reg, S.LaneMask);
967 : }
968 : }
969 357066 : updateRange(LI, Reg, LaneBitmask::getNone());
970 357066 : continue;
971 : }
972 :
973 : // For physregs, only update the regunits that actually have a
974 : // precomputed live range.
975 564180 : for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
976 450256 : if (LiveRange *LR = getRegUnitLI(*Units))
977 67288 : updateRange(*LR, *Units, LaneBitmask::getNone());
978 : }
979 195571 : if (hasRegMask)
980 0 : updateRegMaskSlots();
981 195571 : }
982 :
983 : private:
984 : /// Update a single live range, assuming an instruction has been moved from
985 : /// OldIdx to NewIdx.
986 532247 : void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
987 532247 : if (!Updated.insert(&LR).second)
988 : return;
989 : DEBUG({
990 : dbgs() << " ";
991 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
992 : dbgs() << PrintReg(Reg);
993 : if (LaneMask.any())
994 : dbgs() << " L" << PrintLaneMask(LaneMask);
995 : } else {
996 : dbgs() << PrintRegUnit(Reg, &TRI);
997 : }
998 : dbgs() << ":\t" << LR << '\n';
999 : });
1000 511290 : if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1001 454332 : handleMoveDown(LR);
1002 : else
1003 56958 : handleMoveUp(LR, Reg, LaneMask);
1004 : DEBUG(dbgs() << " -->\t" << LR << '\n');
1005 : LR.verify();
1006 : }
1007 :
1008 : /// Update LR to reflect an instruction has been moved downwards from OldIdx
1009 : /// to NewIdx (OldIdx < NewIdx).
1010 454332 : void handleMoveDown(LiveRange &LR) {
1011 454332 : LiveRange::iterator E = LR.end();
1012 : // Segment going into OldIdx.
1013 908664 : LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1014 :
1015 : // No value live before or after OldIdx? Nothing to do.
1016 907090 : if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1017 : return;
1018 :
1019 : LiveRange::iterator OldIdxOut;
1020 : // Do we have a value live-in to OldIdx?
1021 446511 : if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1022 : // If the live-in value already extends to NewIdx, there is nothing to do.
1023 270107 : if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1024 : return;
1025 : // Aggressively remove all kill flags from the old kill point.
1026 : // Kill flags shouldn't be used while live intervals exist, they will be
1027 : // reinserted by VirtRegRewriter.
1028 359264 : if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1029 121409 : for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1030 296614 : if (MO->isReg() && MO->isUse())
1031 26750 : MO->setIsKill(false);
1032 :
1033 : // Is there a def before NewIdx which is not OldIdx?
1034 179632 : LiveRange::iterator Next = std::next(OldIdxIn);
1035 223969 : if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1036 : SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1037 : // If we are here then OldIdx was just a use but not a def. We only have
1038 : // to ensure liveness extends to NewIdx.
1039 : LiveRange::iterator NewIdxIn =
1040 442 : LR.advanceTo(Next, NewIdx.getBaseIndex());
1041 : // Extend the segment before NewIdx if necessary.
1042 340 : if (NewIdxIn == E ||
1043 : !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1044 102 : LiveRange::iterator Prev = std::prev(NewIdxIn);
1045 204 : Prev->end = NewIdx.getRegSlot();
1046 : }
1047 : // Extend OldIdxIn.
1048 221 : OldIdxIn->end = Next->start;
1049 221 : return;
1050 : }
1051 :
1052 : // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1053 : // invalid by overlapping ranges.
1054 179411 : bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1055 538233 : OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1056 : // If this was not a kill, then there was no def and we're done.
1057 179411 : if (!isKill)
1058 : return;
1059 :
1060 : // Did we have a Def at OldIdx?
1061 166629 : OldIdxOut = Next;
1062 203525 : if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1063 : return;
1064 : } else {
1065 : OldIdxOut = OldIdxIn;
1066 : }
1067 :
1068 : // If we are here then there is a Definition at OldIdx. OldIdxOut points
1069 : // to the segment starting there.
1070 : assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1071 : "No def?");
1072 206561 : VNInfo *OldIdxVNI = OldIdxOut->valno;
1073 : assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1074 :
1075 : // If the defined value extends beyond NewIdx, just move the beginning
1076 : // of the segment to NewIdx.
1077 619683 : SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1078 206561 : if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1079 192433 : OldIdxVNI->def = NewIdxDef;
1080 192433 : OldIdxOut->start = OldIdxVNI->def;
1081 192433 : return;
1082 : }
1083 :
1084 : // If we are here then we have a Definition at OldIdx which ends before
1085 : // NewIdx.
1086 :
1087 : // Is there an existing Def at NewIdx?
1088 : LiveRange::iterator AfterNewIdx
1089 28256 : = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1090 28256 : bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1091 17848 : if (!OldIdxDefIsDead &&
1092 : SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1093 : // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1094 : VNInfo *DefVNI;
1095 4824 : if (OldIdxOut != LR.begin() &&
1096 1104 : !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1097 : OldIdxOut->start)) {
1098 : // There is no gap between OldIdxOut and its predecessor anymore,
1099 : // merge them.
1100 1103 : LiveRange::iterator IPrev = std::prev(OldIdxOut);
1101 1103 : DefVNI = OldIdxVNI;
1102 1103 : IPrev->end = OldIdxOut->end;
1103 : } else {
1104 : // The value is live in to OldIdx
1105 2617 : LiveRange::iterator INext = std::next(OldIdxOut);
1106 : assert(INext != E && "Must have following segment");
1107 : // We merge OldIdxOut and its successor. As we're dealing with subreg
1108 : // reordering, there is always a successor to OldIdxOut in the same BB
1109 : // We don't need INext->valno anymore and will reuse for the new segment
1110 : // we create later.
1111 2617 : DefVNI = OldIdxVNI;
1112 2617 : INext->start = OldIdxOut->end;
1113 2617 : INext->valno->def = INext->start;
1114 : }
1115 : // If NewIdx is behind the last segment, extend that and append a new one.
1116 3720 : if (AfterNewIdx == E) {
1117 : // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1118 : // one position.
1119 : // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1120 : // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1121 0 : std::copy(std::next(OldIdxOut), E, OldIdxOut);
1122 : // The last segment is undefined now, reuse it for a dead def.
1123 0 : LiveRange::iterator NewSegment = std::prev(E);
1124 0 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1125 : DefVNI);
1126 0 : DefVNI->def = NewIdxDef;
1127 :
1128 0 : LiveRange::iterator Prev = std::prev(NewSegment);
1129 0 : Prev->end = NewIdxDef;
1130 : } else {
1131 : // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1132 : // one position.
1133 : // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1134 : // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1135 11160 : std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1136 3720 : LiveRange::iterator Prev = std::prev(AfterNewIdx);
1137 : // We have two cases:
1138 3720 : if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1139 : // Case 1: NewIdx is inside a liverange. Split this liverange at
1140 : // NewIdxDef into the segment "Prev" followed by "NewSegment".
1141 3720 : LiveRange::iterator NewSegment = AfterNewIdx;
1142 3720 : *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1143 3720 : Prev->valno->def = NewIdxDef;
1144 :
1145 3720 : *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1146 3720 : DefVNI->def = Prev->start;
1147 : } else {
1148 : // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1149 : // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1150 0 : *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1151 0 : DefVNI->def = NewIdxDef;
1152 : assert(DefVNI != AfterNewIdx->valno);
1153 : }
1154 : }
1155 : return;
1156 : }
1157 :
1158 20243 : if (AfterNewIdx != E &&
1159 : SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1160 : // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1161 : // that value.
1162 : assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1163 0 : LR.removeValNo(OldIdxVNI);
1164 : } else {
1165 : // There was no existing def at NewIdx. We need to create a dead def
1166 : // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1167 : // a new segment at the place where we want to construct the dead def.
1168 : // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1169 : // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1170 : assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1171 20816 : std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1172 : // We can reuse OldIdxVNI now.
1173 10408 : LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1174 10408 : VNInfo *NewSegmentVNI = OldIdxVNI;
1175 10408 : NewSegmentVNI->def = NewIdxDef;
1176 10408 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1177 : NewSegmentVNI);
1178 : }
1179 : }
1180 :
1181 : /// Update LR to reflect an instruction has been moved upwards from OldIdx
1182 : /// to NewIdx (NewIdx < OldIdx).
1183 56958 : void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
1184 56958 : LiveRange::iterator E = LR.end();
1185 : // Segment going into OldIdx.
1186 113916 : LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1187 :
1188 : // No value live before or after OldIdx? Nothing to do.
1189 112831 : if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1190 : return;
1191 :
1192 : LiveRange::iterator OldIdxOut;
1193 : // Do we have a value live-in to OldIdx?
1194 54899 : if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1195 : // If the live-in value isn't killed here, then we have no Def at
1196 : // OldIdx, moreover the value must be live at NewIdx so there is nothing
1197 : // to do.
1198 32193 : bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1199 32193 : if (!isKill)
1200 27147 : return;
1201 :
1202 : // At this point we have to move OldIdxIn->end back to the nearest
1203 : // previous use or (dead-)def but no further than NewIdx.
1204 : SlotIndex DefBeforeOldIdx
1205 62598 : = std::max(OldIdxIn->start.getDeadSlot(),
1206 104330 : NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1207 20866 : OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1208 :
1209 : // Did we have a Def at OldIdx? If not we are done now.
1210 20866 : OldIdxOut = std::next(OldIdxIn);
1211 29446 : if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1212 : return;
1213 : } else {
1214 22706 : OldIdxOut = OldIdxIn;
1215 23655 : OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1216 : }
1217 :
1218 : // If we are here then there is a Definition at OldIdx. OldIdxOut points
1219 : // to the segment starting there.
1220 : assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1221 : "No def?");
1222 27752 : VNInfo *OldIdxVNI = OldIdxOut->valno;
1223 : assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1224 55504 : bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1225 :
1226 : // Is there an existing def at NewIdx?
1227 83256 : SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1228 55504 : LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1229 27752 : if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1230 : assert(NewIdxOut->valno != OldIdxVNI &&
1231 : "Same value defined more than once?");
1232 : // If OldIdx was a dead def remove it.
1233 0 : if (!OldIdxDefIsDead) {
1234 : // Remove segment starting at NewIdx and move begin of OldIdxOut to
1235 : // NewIdx so it can take its place.
1236 0 : OldIdxVNI->def = NewIdxDef;
1237 0 : OldIdxOut->start = NewIdxDef;
1238 0 : LR.removeValNo(NewIdxOut->valno);
1239 : } else {
1240 : // Simply remove the dead def at OldIdx.
1241 0 : LR.removeValNo(OldIdxVNI);
1242 : }
1243 : } else {
1244 : // Previously nothing was live after NewIdx, so all we have to do now is
1245 : // move the begin of OldIdxOut to NewIdx.
1246 27752 : if (!OldIdxDefIsDead) {
1247 : // Do we have any intermediate Defs between OldIdx and NewIdx?
1248 31999 : if (OldIdxIn != E &&
1249 : SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1250 : // OldIdx is not a dead def and NewIdx is before predecessor start.
1251 880 : LiveRange::iterator NewIdxIn = NewIdxOut;
1252 : assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1253 880 : const SlotIndex SplitPos = NewIdxDef;
1254 880 : OldIdxVNI = OldIdxIn->valno;
1255 :
1256 : // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1257 880 : OldIdxOut->valno->def = OldIdxIn->start;
1258 880 : *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1259 : OldIdxOut->valno);
1260 : // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1261 : // We Slide [NewIdxIn, OldIdxIn) down one position.
1262 : // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1263 : // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1264 880 : std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1265 : // NewIdxIn is now considered undef so we can reuse it for the moved
1266 : // value.
1267 880 : LiveRange::iterator NewSegment = NewIdxIn;
1268 880 : LiveRange::iterator Next = std::next(NewSegment);
1269 880 : if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1270 : // There is no gap between NewSegment and its predecessor.
1271 300 : *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1272 : Next->valno);
1273 300 : *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI);
1274 300 : Next->valno->def = SplitPos;
1275 : } else {
1276 : // There is a gap between NewSegment and its predecessor
1277 : // Value becomes live in.
1278 580 : *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1279 580 : NewSegment->valno->def = SplitPos;
1280 : }
1281 : } else {
1282 : // Leave the end point of a live def.
1283 25968 : OldIdxOut->start = NewIdxDef;
1284 25968 : OldIdxVNI->def = NewIdxDef;
1285 30239 : if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1286 272 : OldIdxIn->end = NewIdx.getRegSlot();
1287 : }
1288 : } else {
1289 : // OldIdxVNI is a dead def. It may have been moved across other values
1290 : // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1291 : // down one position.
1292 : // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1293 : // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1294 1808 : std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1295 : // OldIdxVNI can be reused now to build a new dead def segment.
1296 904 : LiveRange::iterator NewSegment = NewIdxOut;
1297 904 : VNInfo *NewSegmentVNI = OldIdxVNI;
1298 904 : *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1299 : NewSegmentVNI);
1300 904 : NewSegmentVNI->def = NewIdxDef;
1301 : }
1302 : }
1303 : }
1304 :
1305 0 : void updateRegMaskSlots() {
1306 : SmallVectorImpl<SlotIndex>::iterator RI =
1307 0 : std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
1308 0 : OldIdx);
1309 : assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1310 : "No RegMask at OldIdx.");
1311 0 : *RI = NewIdx.getRegSlot();
1312 : assert((RI == LIS.RegMaskSlots.begin() ||
1313 : SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1314 : "Cannot move regmask instruction above another call");
1315 : assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1316 : SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1317 : "Cannot move regmask instruction below another call");
1318 0 : }
1319 :
1320 : // Return the last use of reg between NewIdx and OldIdx.
1321 20866 : SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
1322 : LaneBitmask LaneMask) {
1323 20866 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1324 16592 : SlotIndex LastUse = Before;
1325 98173 : for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1326 48397 : if (MO.isUndef())
1327 12 : continue;
1328 48385 : unsigned SubReg = MO.getSubReg();
1329 33932 : if (SubReg != 0 && LaneMask.any()
1330 85864 : && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1331 8519 : continue;
1332 :
1333 39866 : const MachineInstr &MI = *MO.getParent();
1334 39866 : SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1335 58249 : if (InstSlot > LastUse && InstSlot < OldIdx)
1336 2825 : LastUse = InstSlot.getRegSlot();
1337 : }
1338 16592 : return LastUse;
1339 : }
1340 :
1341 : // This is a regunit interval, so scanning the use list could be very
1342 : // expensive. Scan upwards from OldIdx instead.
1343 : assert(Before < OldIdx && "Expected upwards move");
1344 4274 : SlotIndexes *Indexes = LIS.getSlotIndexes();
1345 4274 : MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1346 :
1347 : // OldIdx may not correspond to an instruction any longer, so set MII to
1348 : // point to the next instruction after OldIdx, or MBB->end().
1349 4274 : MachineBasicBlock::iterator MII = MBB->end();
1350 8548 : if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1351 4274 : Indexes->getNextNonNullIndex(OldIdx)))
1352 4274 : if (MI->getParent() == MBB)
1353 4188 : MII = MI;
1354 :
1355 4274 : MachineBasicBlock::iterator Begin = MBB->begin();
1356 47345 : while (MII != Begin) {
1357 142035 : if ((--MII)->isDebugValue())
1358 143 : continue;
1359 47202 : SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1360 :
1361 : // Stop searching when Before is reached.
1362 47202 : if (!SlotIndex::isEarlierInstr(Before, Idx))
1363 8490 : return Before;
1364 :
1365 : // Check if MII uses Reg.
1366 209197 : for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1367 483757 : if (MO->isReg() && !MO->isUndef() &&
1368 320463 : TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
1369 79764 : TRI.hasRegUnit(MO->getReg(), Reg))
1370 58 : return Idx.getRegSlot();
1371 : }
1372 : // Didn't reach Before. It must be the first instruction in the block.
1373 0 : return Before;
1374 : }
1375 : };
1376 :
1377 195571 : void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
1378 : assert(!MI.isBundled() && "Can't handle bundled instructions yet.");
1379 195571 : SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1380 195571 : Indexes->removeMachineInstrFromMaps(MI);
1381 195571 : SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1382 : assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1383 : OldIndex < getMBBEndIdx(MI.getParent()) &&
1384 : "Cannot handle moves across basic block boundaries.");
1385 :
1386 586713 : HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1387 195571 : HME.updateAllRanges(&MI);
1388 195571 : }
1389 :
1390 0 : void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
1391 : MachineInstr &BundleStart,
1392 : bool UpdateFlags) {
1393 0 : SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1394 0 : SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1395 0 : HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1396 0 : HME.updateAllRanges(&MI);
1397 0 : }
1398 :
1399 40 : void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1400 : const MachineBasicBlock::iterator End,
1401 : const SlotIndex endIdx,
1402 : LiveRange &LR, const unsigned Reg,
1403 : LaneBitmask LaneMask) {
1404 40 : LiveInterval::iterator LII = LR.find(endIdx);
1405 40 : SlotIndex lastUseIdx;
1406 40 : if (LII == LR.begin()) {
1407 : // This happens when the function is called for a subregister that only
1408 : // occurs _after_ the range that is to be repaired.
1409 : return;
1410 : }
1411 20 : if (LII != LR.end() && LII->start < endIdx)
1412 0 : lastUseIdx = LII->end;
1413 : else
1414 20 : --LII;
1415 :
1416 158 : for (MachineBasicBlock::iterator I = End; I != Begin;) {
1417 118 : --I;
1418 118 : MachineInstr &MI = *I;
1419 118 : if (MI.isDebugValue())
1420 0 : continue;
1421 :
1422 236 : SlotIndex instrIdx = getInstructionIndex(MI);
1423 236 : bool isStartValid = getInstructionFromIndex(LII->start);
1424 236 : bool isEndValid = getInstructionFromIndex(LII->end);
1425 :
1426 : // FIXME: This doesn't currently handle early-clobber or multiple removed
1427 : // defs inside of the region to repair.
1428 826 : for (MachineInstr::mop_iterator OI = MI.operands_begin(),
1429 118 : OE = MI.operands_end();
1430 826 : OI != OE; ++OI) {
1431 708 : const MachineOperand &MO = *OI;
1432 1376 : if (!MO.isReg() || MO.getReg() != Reg)
1433 668 : continue;
1434 :
1435 40 : unsigned SubReg = MO.getSubReg();
1436 80 : LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1437 40 : if ((Mask & LaneMask).none())
1438 0 : continue;
1439 :
1440 40 : if (MO.isDef()) {
1441 20 : if (!isStartValid) {
1442 0 : if (LII->end.isDead()) {
1443 0 : SlotIndex prevStart;
1444 0 : if (LII != LR.begin())
1445 0 : prevStart = std::prev(LII)->start;
1446 :
1447 : // FIXME: This could be more efficient if there was a
1448 : // removeSegment method that returned an iterator.
1449 0 : LR.removeSegment(*LII, true);
1450 0 : if (prevStart.isValid())
1451 0 : LII = LR.find(prevStart);
1452 : else
1453 0 : LII = LR.begin();
1454 : } else {
1455 0 : LII->start = instrIdx.getRegSlot();
1456 0 : LII->valno->def = instrIdx.getRegSlot();
1457 0 : if (MO.getSubReg() && !MO.isUndef())
1458 : lastUseIdx = instrIdx.getRegSlot();
1459 : else
1460 : lastUseIdx = SlotIndex();
1461 0 : continue;
1462 : }
1463 : }
1464 :
1465 20 : if (!lastUseIdx.isValid()) {
1466 0 : VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1467 : LiveRange::Segment S(instrIdx.getRegSlot(),
1468 0 : instrIdx.getDeadSlot(), VNI);
1469 0 : LII = LR.addSegment(S);
1470 40 : } else if (LII->start != instrIdx.getRegSlot()) {
1471 0 : VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1472 0 : LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1473 0 : LII = LR.addSegment(S);
1474 : }
1475 :
1476 20 : if (MO.getSubReg() && !MO.isUndef())
1477 0 : lastUseIdx = instrIdx.getRegSlot();
1478 : else
1479 : lastUseIdx = SlotIndex();
1480 20 : } else if (MO.isUse()) {
1481 : // FIXME: This should probably be handled outside of this branch,
1482 : // either as part of the def case (for defs inside of the region) or
1483 : // after the loop over the region.
1484 40 : if (!isEndValid && !LII->end.isBlock())
1485 20 : LII->end = instrIdx.getRegSlot();
1486 20 : if (!lastUseIdx.isValid())
1487 20 : lastUseIdx = instrIdx.getRegSlot();
1488 : }
1489 : }
1490 : }
1491 : }
1492 :
1493 : void
1494 20 : LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1495 : MachineBasicBlock::iterator Begin,
1496 : MachineBasicBlock::iterator End,
1497 : ArrayRef<unsigned> OrigRegs) {
1498 : // Find anchor points, which are at the beginning/end of blocks or at
1499 : // instructions that already have indexes.
1500 226 : while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin))
1501 : --Begin;
1502 160 : while (End != MBB->end() && !Indexes->hasIndex(*End))
1503 : ++End;
1504 :
1505 20 : SlotIndex endIdx;
1506 40 : if (End == MBB->end())
1507 0 : endIdx = getMBBEndIdx(MBB).getPrevSlot();
1508 : else
1509 40 : endIdx = getInstructionIndex(*End);
1510 :
1511 20 : Indexes->repairIndexesInRange(MBB, Begin, End);
1512 :
1513 158 : for (MachineBasicBlock::iterator I = End; I != Begin;) {
1514 118 : --I;
1515 118 : MachineInstr &MI = *I;
1516 118 : if (MI.isDebugValue())
1517 0 : continue;
1518 826 : for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
1519 118 : MOE = MI.operands_end();
1520 826 : MOI != MOE; ++MOI) {
1521 1284 : if (MOI->isReg() &&
1522 1284 : TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
1523 64 : !hasInterval(MOI->getReg())) {
1524 0 : createAndComputeVirtRegInterval(MOI->getReg());
1525 : }
1526 : }
1527 : }
1528 :
1529 100 : for (unsigned Reg : OrigRegs) {
1530 60 : if (!TargetRegisterInfo::isVirtualRegister(Reg))
1531 20 : continue;
1532 :
1533 40 : LiveInterval &LI = getInterval(Reg);
1534 : // FIXME: Should we support undefs that gain defs?
1535 80 : if (!LI.hasAtLeastOneValue())
1536 0 : continue;
1537 :
1538 80 : for (LiveInterval::SubRange &S : LI.subranges())
1539 0 : repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1540 :
1541 40 : repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1542 : }
1543 20 : }
1544 :
1545 6630 : void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
1546 19890 : for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
1547 13260 : if (LiveRange *LR = getCachedRegUnit(*Unit))
1548 100 : if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1549 100 : LR->removeValNo(VNI);
1550 : }
1551 6630 : }
1552 :
1553 83419 : void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
1554 : // LI may not have the main range computed yet, but its subranges may
1555 : // be present.
1556 166836 : VNInfo *VNI = LI.getVNInfoAt(Pos);
1557 83417 : if (VNI != nullptr) {
1558 : assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1559 83417 : LI.removeValNo(VNI);
1560 : }
1561 :
1562 : // Also remove the value defined in subranges.
1563 166888 : for (LiveInterval::SubRange &S : LI.subranges()) {
1564 100 : if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1565 150 : if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1566 50 : S.removeValNo(SVNI);
1567 : }
1568 83419 : LI.removeEmptySubRanges();
1569 83419 : }
1570 :
1571 63783 : void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
1572 : SmallVectorImpl<LiveInterval*> &SplitLIs) {
1573 68775 : ConnectedVNInfoEqClasses ConEQ(*this);
1574 63783 : unsigned NumComp = ConEQ.Classify(LI);
1575 63783 : if (NumComp <= 1)
1576 58791 : return;
1577 : DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1578 4992 : unsigned Reg = LI.reg;
1579 9984 : const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
1580 13103 : for (unsigned I = 1; I < NumComp; ++I) {
1581 8111 : unsigned NewVReg = MRI->createVirtualRegister(RegClass);
1582 8111 : LiveInterval &NewLI = createEmptyInterval(NewVReg);
1583 8111 : SplitLIs.push_back(&NewLI);
1584 : }
1585 9984 : ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1586 : }
1587 :
1588 163 : void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
1589 : assert(LRCalc && "LRCalc not initialized.");
1590 326 : LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1591 163 : LRCalc->constructMainRangeFromSubranges(LI);
1592 217081 : }
|
