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

source code of llvm/lib/CodeGen/LiveIntervals.cpp