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