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