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