aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveIntervals.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/LiveIntervals.cpp')
-rw-r--r--lib/CodeGen/LiveIntervals.cpp143
1 files changed, 102 insertions, 41 deletions
diff --git a/lib/CodeGen/LiveIntervals.cpp b/lib/CodeGen/LiveIntervals.cpp
index 79fdba7e062a..471775f8706b 100644
--- a/lib/CodeGen/LiveIntervals.cpp
+++ b/lib/CodeGen/LiveIntervals.cpp
@@ -37,6 +37,7 @@
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/Config/llvm-config.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
@@ -147,7 +148,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
getRegUnit(i);
}
- DEBUG(dump());
+ LLVM_DEBUG(dump());
return true;
}
@@ -310,7 +311,7 @@ void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
/// entering the entry block or a landing pad.
void LiveIntervals::computeLiveInRegUnits() {
RegUnitRanges.resize(TRI->getNumRegUnits());
- DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
+ LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
// Keep track of the live range sets allocated.
SmallVector<unsigned, 8> NewRanges;
@@ -323,7 +324,7 @@ void LiveIntervals::computeLiveInRegUnits() {
// Create phi-defs at Begin for all live-in registers.
SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
- DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
+ LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
for (const auto &LI : MBB.liveins()) {
for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
unsigned Unit = *Units;
@@ -335,12 +336,12 @@ void LiveIntervals::computeLiveInRegUnits() {
}
VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
(void)VNI;
- DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
+ LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
}
}
- DEBUG(dbgs() << '\n');
+ LLVM_DEBUG(dbgs() << '\n');
}
- DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
+ LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
// Compute the 'normal' part of the ranges.
for (unsigned Unit : NewRanges)
@@ -357,26 +358,40 @@ static void createSegmentsForValues(LiveRange &LR,
}
}
-using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
-
-static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
- ShrinkToUsesWorkList &WorkList,
- const LiveRange &OldRange) {
+void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
+ ShrinkToUsesWorkList &WorkList,
+ unsigned Reg, LaneBitmask LaneMask) {
// Keep track of the PHIs that are in use.
SmallPtrSet<VNInfo*, 8> UsedPHIs;
// Blocks that have already been added to WorkList as live-out.
SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
+ auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
+ -> const LiveRange& {
+ if (M.none())
+ return I;
+ for (const LiveInterval::SubRange &SR : I.subranges()) {
+ if ((SR.LaneMask & M).any()) {
+ assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
+ return SR;
+ }
+ }
+ llvm_unreachable("Subrange for mask not found");
+ };
+
+ const LiveInterval &LI = getInterval(Reg);
+ const LiveRange &OldRange = getSubRange(LI, LaneMask);
+
// Extend intervals to reach all uses in WorkList.
while (!WorkList.empty()) {
SlotIndex Idx = WorkList.back().first;
VNInfo *VNI = WorkList.back().second;
WorkList.pop_back();
- const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
- SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
+ const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
+ SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
// Extend the live range for VNI to be live at Idx.
- if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
+ if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
assert(ExtVNI == VNI && "Unexpected existing value number");
(void)ExtVNI;
// Is this a PHIDef we haven't seen before?
@@ -387,7 +402,7 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
for (const MachineBasicBlock *Pred : MBB->predecessors()) {
if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
+ SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
// A predecessor is not required to have a live-out value for a PHI.
if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
WorkList.push_back(std::make_pair(Stop, PVNI));
@@ -396,24 +411,37 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
}
// VNI is live-in to MBB.
- DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
- LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
+ LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
+ Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
// Make sure VNI is live-out from the predecessors.
for (const MachineBasicBlock *Pred : MBB->predecessors()) {
if (!LiveOut.insert(Pred).second)
continue;
- SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
- assert(OldRange.getVNInfoBefore(Stop) == VNI &&
- "Wrong value out of predecessor");
- WorkList.push_back(std::make_pair(Stop, VNI));
+ SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
+ if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
+ assert(OldVNI == VNI && "Wrong value out of predecessor");
+ (void)OldVNI;
+ WorkList.push_back(std::make_pair(Stop, VNI));
+ } else {
+#ifndef NDEBUG
+ // There was no old VNI. Verify that Stop is jointly dominated
+ // by <undef>s for this live range.
+ assert(LaneMask.any() &&
+ "Missing value out of predecessor for main range");
+ SmallVector<SlotIndex,8> Undefs;
+ LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
+ assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
+ "Missing value out of predecessor for subrange");
+#endif
+ }
}
}
}
bool LiveIntervals::shrinkToUses(LiveInterval *li,
SmallVectorImpl<MachineInstr*> *dead) {
- DEBUG(dbgs() << "Shrink: " << *li << '\n');
+ LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
assert(TargetRegisterInfo::isVirtualRegister(li->reg)
&& "Can only shrink virtual registers");
@@ -442,9 +470,10 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
// This shouldn't happen: readsVirtualRegister returns true, but there is
// no live value. It is likely caused by a target getting <undef> flags
// wrong.
- DEBUG(dbgs() << Idx << '\t' << UseMI
- << "Warning: Instr claims to read non-existent value in "
- << *li << '\n');
+ LLVM_DEBUG(
+ dbgs() << Idx << '\t' << UseMI
+ << "Warning: Instr claims to read non-existent value in "
+ << *li << '\n');
continue;
}
// Special case: An early-clobber tied operand reads and writes the
@@ -458,14 +487,14 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
// Create new live ranges with only minimal live segments per def.
LiveRange NewLR;
createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
- extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
+ extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
// Move the trimmed segments back.
li->segments.swap(NewLR.segments);
// Handle dead values.
bool CanSeparate = computeDeadValues(*li, dead);
- DEBUG(dbgs() << "Shrunk: " << *li << '\n');
+ LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
return CanSeparate;
}
@@ -495,7 +524,7 @@ bool LiveIntervals::computeDeadValues(LiveInterval &LI,
// This is a dead PHI. Remove it.
VNI->markUnused();
LI.removeSegment(I);
- DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
+ LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
MayHaveSplitComponents = true;
} else {
// This is a dead def. Make sure the instruction knows.
@@ -503,7 +532,7 @@ bool LiveIntervals::computeDeadValues(LiveInterval &LI,
assert(MI && "No instruction defining live value");
MI->addRegisterDead(LI.reg, TRI);
if (dead && MI->allDefsAreDead()) {
- DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
+ LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
dead->push_back(MI);
}
}
@@ -512,7 +541,7 @@ bool LiveIntervals::computeDeadValues(LiveInterval &LI,
}
void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
- DEBUG(dbgs() << "Shrink: " << SR << '\n');
+ LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
assert(TargetRegisterInfo::isVirtualRegister(Reg)
&& "Can only shrink virtual registers");
// Find all the values used, including PHI kills.
@@ -556,7 +585,7 @@ void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
// Create a new live ranges with only minimal live segments per def.
LiveRange NewLR;
createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
- extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
+ extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
// Move the trimmed ranges back.
SR.segments.swap(NewLR.segments);
@@ -571,13 +600,14 @@ void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
- DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
+ LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
+ << " may separate interval\n");
VNI->markUnused();
SR.removeSegment(*Segment);
}
}
- DEBUG(dbgs() << "Shrunk: " << SR << '\n');
+ LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
}
void LiveIntervals::extendToIndices(LiveRange &LR,
@@ -785,7 +815,7 @@ MachineBasicBlock*
LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
// A local live range must be fully contained inside the block, meaning it is
// defined and killed at instructions, not at block boundaries. It is not
- // live in or or out of any block.
+ // live in or out of any block.
//
// It is technically possible to have a PHI-defined live range identical to a
// single block, but we are going to return false in that case.
@@ -942,7 +972,8 @@ public:
/// Update all live ranges touched by MI, assuming a move from OldIdx to
/// NewIdx.
void updateAllRanges(MachineInstr *MI) {
- DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
+ LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
+ << *MI);
bool hasRegMask = false;
for (MachineOperand &MO : MI->operands()) {
if (MO.isRegMask())
@@ -992,7 +1023,7 @@ private:
void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
if (!Updated.insert(&LR).second)
return;
- DEBUG({
+ LLVM_DEBUG({
dbgs() << " ";
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
dbgs() << printReg(Reg);
@@ -1007,7 +1038,7 @@ private:
handleMoveDown(LR);
else
handleMoveUp(LR, Reg, LaneMask);
- DEBUG(dbgs() << " -->\t" << LR << '\n');
+ LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
LR.verify();
}
@@ -1291,6 +1322,36 @@ private:
if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
OldIdxIn->end = NewIdx.getRegSlot();
}
+ } else if (OldIdxIn != E
+ && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
+ && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
+ // OldIdxVNI is a dead def that has been moved into the middle of
+ // another value in LR. That can happen when LR is a whole register,
+ // but the dead def is a write to a subreg that is dead at NewIdx.
+ // The dead def may have been moved across other values
+ // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
+ // down one position.
+ // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
+ // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
+ std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
+ // Modify the segment at NewIdxOut and the following segment to meet at
+ // the point of the dead def, with the following segment getting
+ // OldIdxVNI as its value number.
+ *NewIdxOut = LiveRange::Segment(
+ NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
+ *(NewIdxOut + 1) = LiveRange::Segment(
+ NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
+ OldIdxVNI->def = NewIdxDef;
+ // Modify subsequent segments to be defined by the moved def OldIdxVNI.
+ for (auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
+ Idx->valno = OldIdxVNI;
+ // Aggressively remove all dead flags from the former dead definition.
+ // Kill/dead flags shouldn't be used while live intervals exist; they
+ // will be reinserted by VirtRegRewriter.
+ if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
+ for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
+ if (MO->isReg() && !MO->isUse())
+ MO->setIsDead(false);
} else {
// OldIdxVNI is a dead def. It may have been moved across other values
// in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
@@ -1360,7 +1421,7 @@ private:
MachineBasicBlock::iterator Begin = MBB->begin();
while (MII != Begin) {
- if ((--MII)->isDebugValue())
+ if ((--MII)->isDebugInstr())
continue;
SlotIndex Idx = Indexes->getInstructionIndex(*MII);
@@ -1422,7 +1483,7 @@ void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
for (MachineBasicBlock::iterator I = End; I != Begin;) {
--I;
MachineInstr &MI = *I;
- if (MI.isDebugValue())
+ if (MI.isDebugInstr())
continue;
SlotIndex instrIdx = getInstructionIndex(MI);
@@ -1519,7 +1580,7 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
for (MachineBasicBlock::iterator I = End; I != Begin;) {
--I;
MachineInstr &MI = *I;
- if (MI.isDebugValue())
+ if (MI.isDebugInstr())
continue;
for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
MOE = MI.operands_end();
@@ -1580,7 +1641,7 @@ void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
unsigned NumComp = ConEQ.Classify(LI);
if (NumComp <= 1)
return;
- DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
+ LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
unsigned Reg = LI.reg;
const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
for (unsigned I = 1; I < NumComp; ++I) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 08:05:50 +0000