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