summaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/RegisterCoalescer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/RegisterCoalescer.cpp')
-rw-r--r--llvm/lib/CodeGen/RegisterCoalescer.cpp227
1 files changed, 205 insertions, 22 deletions
diff --git a/llvm/lib/CodeGen/RegisterCoalescer.cpp b/llvm/lib/CodeGen/RegisterCoalescer.cpp
index 6ff5ddbc023d..a3f75d82d0ec 100644
--- a/llvm/lib/CodeGen/RegisterCoalescer.cpp
+++ b/llvm/lib/CodeGen/RegisterCoalescer.cpp
@@ -40,6 +40,7 @@
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
+#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegisterInfo.h"
@@ -119,32 +120,46 @@ static cl::opt<unsigned> LargeIntervalFreqThreshold(
namespace {
+ class JoinVals;
+
class RegisterCoalescer : public MachineFunctionPass,
private LiveRangeEdit::Delegate {
- MachineFunction* MF;
- MachineRegisterInfo* MRI;
- const TargetRegisterInfo* TRI;
- const TargetInstrInfo* TII;
- LiveIntervals *LIS;
- const MachineLoopInfo* Loops;
- AliasAnalysis *AA;
+ MachineFunction* MF = nullptr;
+ MachineRegisterInfo* MRI = nullptr;
+ const TargetRegisterInfo* TRI = nullptr;
+ const TargetInstrInfo* TII = nullptr;
+ LiveIntervals *LIS = nullptr;
+ const MachineLoopInfo* Loops = nullptr;
+ AliasAnalysis *AA = nullptr;
RegisterClassInfo RegClassInfo;
+ /// Debug variable location tracking -- for each VReg, maintain an
+ /// ordered-by-slot-index set of DBG_VALUEs, to help quick
+ /// identification of whether coalescing may change location validity.
+ using DbgValueLoc = std::pair<SlotIndex, MachineInstr*>;
+ DenseMap<unsigned, std::vector<DbgValueLoc>> DbgVRegToValues;
+
+ /// VRegs may be repeatedly coalesced, and have many DBG_VALUEs attached.
+ /// To avoid repeatedly merging sets of DbgValueLocs, instead record
+ /// which vregs have been coalesced, and where to. This map is from
+ /// vreg => {set of vregs merged in}.
+ DenseMap<unsigned, SmallVector<unsigned, 4>> DbgMergedVRegNums;
+
/// A LaneMask to remember on which subregister live ranges we need to call
/// shrinkToUses() later.
LaneBitmask ShrinkMask;
/// True if the main range of the currently coalesced intervals should be
/// checked for smaller live intervals.
- bool ShrinkMainRange;
+ bool ShrinkMainRange = false;
/// True if the coalescer should aggressively coalesce global copies
/// in favor of keeping local copies.
- bool JoinGlobalCopies;
+ bool JoinGlobalCopies = false;
/// True if the coalescer should aggressively coalesce fall-thru
/// blocks exclusively containing copies.
- bool JoinSplitEdges;
+ bool JoinSplitEdges = false;
/// Copy instructions yet to be coalesced.
SmallVector<MachineInstr*, 8> WorkList;
@@ -225,7 +240,8 @@ namespace {
/// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
/// lanemasks already adjusted to the coalesced register.
void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
- LaneBitmask LaneMask, CoalescerPair &CP);
+ LaneBitmask LaneMask, CoalescerPair &CP,
+ unsigned DstIdx);
/// Join the liveranges of two subregisters. Joins @p RRange into
/// @p LRange, @p RRange may be invalid afterwards.
@@ -325,6 +341,19 @@ namespace {
MI->eraseFromParent();
}
+ /// Walk over function and initialize the DbgVRegToValues map.
+ void buildVRegToDbgValueMap(MachineFunction &MF);
+
+ /// Test whether, after merging, any DBG_VALUEs would refer to a
+ /// different value number than before merging, and whether this can
+ /// be resolved. If not, mark the DBG_VALUE as being undef.
+ void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,
+ JoinVals &LHSVals, LiveRange &RHS,
+ JoinVals &RHSVals);
+
+ void checkMergingChangesDbgValuesImpl(unsigned Reg, LiveRange &OtherRange,
+ LiveRange &RegRange, JoinVals &Vals2);
+
public:
static char ID; ///< Class identification, replacement for typeinfo
@@ -1648,8 +1677,7 @@ void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
}
}
-void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
- unsigned DstReg,
+void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, unsigned DstReg,
unsigned SubIdx) {
bool DstIsPhys = Register::isPhysicalRegister(DstReg);
LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
@@ -1705,8 +1733,15 @@ void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) {
if (!DstInt->hasSubRanges()) {
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
- LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
- DstInt->createSubRangeFrom(Allocator, Mask, *DstInt);
+ LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
+ LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);
+ LaneBitmask UnusedLanes = FullMask & ~UsedLanes;
+ DstInt->createSubRangeFrom(Allocator, UsedLanes, *DstInt);
+ // The unused lanes are just empty live-ranges at this point.
+ // It is the caller responsibility to set the proper
+ // dead segments if there is an actual dead def of the
+ // unused lanes. This may happen with rematerialization.
+ DstInt->createSubRange(Allocator, UnusedLanes);
}
SlotIndex MIIdx = UseMI->isDebugValue()
? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
@@ -2195,6 +2230,7 @@ class JoinVals {
/// NewVNInfo. This is suitable for passing to LiveInterval::join().
SmallVector<int, 8> Assignments;
+ public:
/// Conflict resolution for overlapping values.
enum ConflictResolution {
/// No overlap, simply keep this value.
@@ -2223,6 +2259,7 @@ class JoinVals {
CR_Impossible
};
+ private:
/// Per-value info for LI. The lane bit masks are all relative to the final
/// joined register, so they can be compared directly between SrcReg and
/// DstReg.
@@ -2383,6 +2420,11 @@ public:
/// Get the value assignments suitable for passing to LiveInterval::join.
const int *getAssignments() const { return Assignments.data(); }
+
+ /// Get the conflict resolution for a value number.
+ ConflictResolution getResolution(unsigned Num) const {
+ return Vals[Num].Resolution;
+ }
};
} // end anonymous namespace
@@ -3115,7 +3157,8 @@ void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
LiveInterval *LI) {
for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
// Get the def location before markUnused() below invalidates it.
- SlotIndex Def = LR.getValNumInfo(i)->def;
+ VNInfo *VNI = LR.getValNumInfo(i);
+ SlotIndex Def = VNI->def;
switch (Vals[i].Resolution) {
case CR_Keep: {
// If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
@@ -3131,8 +3174,6 @@ void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
// In such cases, removing this def from the main range must be
// complemented by extending the main range to account for the liveness
// of the other subrange.
- VNInfo *VNI = LR.getValNumInfo(i);
- SlotIndex Def = VNI->def;
// The new end point of the main range segment to be extended.
SlotIndex NewEnd;
if (LI != nullptr) {
@@ -3272,7 +3313,8 @@ void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
const LiveRange &ToMerge,
LaneBitmask LaneMask,
- CoalescerPair &CP) {
+ CoalescerPair &CP,
+ unsigned ComposeSubRegIdx) {
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
LI.refineSubRanges(
Allocator, LaneMask,
@@ -3285,7 +3327,7 @@ void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
}
},
- *LIS->getSlotIndexes(), *TRI);
+ *LIS->getSlotIndexes(), *TRI, ComposeSubRegIdx);
}
bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {
@@ -3351,12 +3393,12 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
if (!RHS.hasSubRanges()) {
LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
: TRI->getSubRegIndexLaneMask(SrcIdx);
- mergeSubRangeInto(LHS, RHS, Mask, CP);
+ mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);
} else {
// Pair up subranges and merge.
for (LiveInterval::SubRange &R : RHS.subranges()) {
LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
- mergeSubRangeInto(LHS, R, Mask, CP);
+ mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);
}
}
LLVM_DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
@@ -3385,6 +3427,9 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
while (!ShrinkRegs.empty())
shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
+ // Scan and mark undef any DBG_VALUEs that would refer to a different value.
+ checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
+
// Join RHS into LHS.
LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
@@ -3416,6 +3461,140 @@ bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
}
+void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF)
+{
+ const SlotIndexes &Slots = *LIS->getSlotIndexes();
+ SmallVector<MachineInstr *, 8> ToInsert;
+
+ // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
+ // vreg => DbgValueLoc map.
+ auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {
+ for (auto *X : ToInsert)
+ DbgVRegToValues[X->getOperand(0).getReg()].push_back({Slot, X});
+
+ ToInsert.clear();
+ };
+
+ // Iterate over all instructions, collecting them into the ToInsert vector.
+ // Once a non-debug instruction is found, record the slot index of the
+ // collected DBG_VALUEs.
+ for (auto &MBB : MF) {
+ SlotIndex CurrentSlot = Slots.getMBBStartIdx(&MBB);
+
+ for (auto &MI : MBB) {
+ if (MI.isDebugValue() && MI.getOperand(0).isReg() &&
+ MI.getOperand(0).getReg().isVirtual()) {
+ ToInsert.push_back(&MI);
+ } else if (!MI.isDebugInstr()) {
+ CurrentSlot = Slots.getInstructionIndex(MI);
+ CloseNewDVRange(CurrentSlot);
+ }
+ }
+
+ // Close range of DBG_VALUEs at the end of blocks.
+ CloseNewDVRange(Slots.getMBBEndIdx(&MBB));
+ }
+
+ // Sort all DBG_VALUEs we've seen by slot number.
+ for (auto &Pair : DbgVRegToValues)
+ llvm::sort(Pair.second);
+}
+
+void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,
+ LiveRange &LHS,
+ JoinVals &LHSVals,
+ LiveRange &RHS,
+ JoinVals &RHSVals) {
+ auto ScanForDstReg = [&](unsigned Reg) {
+ checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
+ };
+
+ auto ScanForSrcReg = [&](unsigned Reg) {
+ checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
+ };
+
+ // Scan for potentially unsound DBG_VALUEs: examine first the register number
+ // Reg, and then any other vregs that may have been merged into it.
+ auto PerformScan = [this](unsigned Reg, std::function<void(unsigned)> Func) {
+ Func(Reg);
+ if (DbgMergedVRegNums.count(Reg))
+ for (unsigned X : DbgMergedVRegNums[Reg])
+ Func(X);
+ };
+
+ // Scan for unsound updates of both the source and destination register.
+ PerformScan(CP.getSrcReg(), ScanForSrcReg);
+ PerformScan(CP.getDstReg(), ScanForDstReg);
+}
+
+void RegisterCoalescer::checkMergingChangesDbgValuesImpl(unsigned Reg,
+ LiveRange &OtherLR,
+ LiveRange &RegLR,
+ JoinVals &RegVals) {
+ // Are there any DBG_VALUEs to examine?
+ auto VRegMapIt = DbgVRegToValues.find(Reg);
+ if (VRegMapIt == DbgVRegToValues.end())
+ return;
+
+ auto &DbgValueSet = VRegMapIt->second;
+ auto DbgValueSetIt = DbgValueSet.begin();
+ auto SegmentIt = OtherLR.begin();
+
+ bool LastUndefResult = false;
+ SlotIndex LastUndefIdx;
+
+ // If the "Other" register is live at a slot Idx, test whether Reg can
+ // safely be merged with it, or should be marked undef.
+ auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,
+ &LastUndefIdx](SlotIndex Idx) -> bool {
+ // Our worst-case performance typically happens with asan, causing very
+ // many DBG_VALUEs of the same location. Cache a copy of the most recent
+ // result for this edge-case.
+ if (LastUndefIdx == Idx)
+ return LastUndefResult;
+
+ // If the other range was live, and Reg's was not, the register coalescer
+ // will not have tried to resolve any conflicts. We don't know whether
+ // the DBG_VALUE will refer to the same value number, so it must be made
+ // undef.
+ auto OtherIt = RegLR.find(Idx);
+ if (OtherIt == RegLR.end())
+ return true;
+
+ // Both the registers were live: examine the conflict resolution record for
+ // the value number Reg refers to. CR_Keep meant that this value number
+ // "won" and the merged register definitely refers to that value. CR_Erase
+ // means the value number was a redundant copy of the other value, which
+ // was coalesced and Reg deleted. It's safe to refer to the other register
+ // (which will be the source of the copy).
+ auto Resolution = RegVals.getResolution(OtherIt->valno->id);
+ LastUndefResult = Resolution != JoinVals::CR_Keep &&
+ Resolution != JoinVals::CR_Erase;
+ LastUndefIdx = Idx;
+ return LastUndefResult;
+ };
+
+ // Iterate over both the live-range of the "Other" register, and the set of
+ // DBG_VALUEs for Reg at the same time. Advance whichever one has the lowest
+ // slot index. This relies on the DbgValueSet being ordered.
+ while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {
+ if (DbgValueSetIt->first < SegmentIt->end) {
+ // "Other" is live and there is a DBG_VALUE of Reg: test if we should
+ // set it undef.
+ if (DbgValueSetIt->first >= SegmentIt->start &&
+ DbgValueSetIt->second->getOperand(0).getReg() != 0 &&
+ ShouldUndef(DbgValueSetIt->first)) {
+ // Mark undef, erase record of this DBG_VALUE to avoid revisiting.
+ DbgValueSetIt->second->getOperand(0).setReg(0);
+ continue;
+ }
+ ++DbgValueSetIt;
+ } else {
+ ++SegmentIt;
+ }
+ }
+}
+
namespace {
/// Information concerning MBB coalescing priority.
@@ -3698,6 +3877,10 @@ bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
if (VerifyCoalescing)
MF->verify(this, "Before register coalescing");
+ DbgVRegToValues.clear();
+ DbgMergedVRegNums.clear();
+ buildVRegToDbgValueMap(fn);
+
RegClassInfo.runOnMachineFunction(fn);
// Join (coalesce) intervals if requested.
generated by cgit v1.3 (git 2.53.0) at 2026-07-30 07:45:48 +0000