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