Use pool allocator for all the VNInfo's to improve memory access locality. This reduces coalescing time on siod Mac OS X PPC by 35%. Also remove the back ptr from VNInfo to LiveInterval and other tweaks.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41729 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 53ffbe3..4d38f0a 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -124,7 +124,7 @@
ranges.erase(next(I), MergeTo);
// Update kill info.
- removeKills(*ValNo, OldEnd, I->end-1);
+ removeKills(ValNo, OldEnd, I->end-1);
// If the newly formed range now touches the range after it and if they have
// the same value number, merge the two ranges into one range.
@@ -233,7 +233,7 @@
// If the span we are removing is at the start of the LiveRange, adjust it.
if (I->start == Start) {
if (I->end == End) {
- removeKills(*I->valno, Start, End);
+ removeKills(I->valno, Start, End);
ranges.erase(I); // Removed the whole LiveRange.
} else
I->start = End;
@@ -243,7 +243,7 @@
// Otherwise if the span we are removing is at the end of the LiveRange,
// adjust the other way.
if (I->end == End) {
- removeKills(*I->valno, Start, End);
+ removeKills(I->valno, Start, End);
I->end = Start;
return;
}
@@ -296,17 +296,8 @@
for (unsigned i = 0; i != NumVals; ++i) {
unsigned LHSValID = LHSValNoAssignments[i];
if (i != LHSValID ||
- (NewVNInfo[LHSValID] && NewVNInfo[LHSValID]->parent != this))
+ (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i)))
MustMapCurValNos = true;
-
- // There might be some dead val#, create VNInfo for them.
- if (i < NumNewVals) {
- VNInfo *VNI = NewVNInfo[i];
- if (!VNI) {
- VNI = new VNInfo(this, i, ~1U, 0);
- NewVNInfo[i] = VNI;
- }
- }
}
// If we have to apply a mapping to our base interval assignment, rewrite it
@@ -345,27 +336,18 @@
OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]);
// Update val# info. Renumber them and make sure they all belong to this
- // LiveInterval now.
- for (unsigned i = 0; i != NumVals; ++i) {
- if (i == NumNewVals)
- break;
+ // LiveInterval now. Also remove dead val#'s.
+ unsigned NumValNos = 0;
+ for (unsigned i = 0; i < NumNewVals; ++i) {
VNInfo *VNI = NewVNInfo[i];
- if (VNI->parent != this || VNI->id != i) {
- VNI->parent = this;
- VNI->id = i; // Renumber val#.
- valnos[i] = VNI;
+ if (VNI) {
+ if (i >= NumVals)
+ valnos.push_back(VNI);
+ else
+ valnos[NumValNos] = VNI;
+ VNI->id = NumValNos++; // Renumber val#.
}
}
- for (unsigned i = NumVals; i < NumNewVals; ++i) {
- VNInfo *VNI = NewVNInfo[i];
- if (!VNI)
- VNI = new VNInfo(this, i, ~1U, 0);
- else {
- VNI->parent = this;
- VNI->id = i; // Renumber val#.
- }
- valnos.push_back(VNI);
- }
if (NumNewVals < NumVals)
valnos.resize(NumNewVals); // shrinkify
@@ -375,6 +357,7 @@
for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
// Map the valno in the other live range to the current live range.
I->valno = NewVNInfo[OtherAssignments[RangeNo]];
+ assert(I->valno && "Adding a dead range?");
InsertPos = addRangeFrom(*I, InsertPos);
}
@@ -403,13 +386,14 @@
/// MergeInClobberRanges - For any live ranges that are not defined in the
/// current interval, but are defined in the Clobbers interval, mark them
/// used with an unknown definition value.
-void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers) {
+void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
+ BumpPtrAllocator &VNInfoAllocator) {
if (Clobbers.begin() == Clobbers.end()) return;
// Find a value # to use for the clobber ranges. If there is already a value#
// for unknown values, use it.
// FIXME: Use a single sentinal number for these!
- VNInfo *ClobberValNo = getNextValue(~0U, 0);
+ VNInfo *ClobberValNo = getNextValue(~0U, 0, VNInfoAllocator);
iterator IP = begin();
for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) {
@@ -448,7 +432,7 @@
// Make sure V2 is smaller than V1.
if (V1->id < V2->id) {
- copyValNumInfo(*V1, *V2);
+ copyValNumInfo(V1, V2);
std::swap(V1, V2);
}
@@ -492,9 +476,7 @@
// ~1U so it can be nuked later.
if (V1->id == getNumValNums()-1) {
do {
- VNInfo *VNI = valnos.back();
valnos.pop_back();
- delete VNI;
} while (valnos.back()->def == ~1U);
} else {
V1->def = ~1U;
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 25de7c3..2f93b76 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -62,6 +62,7 @@
}
void LiveIntervals::releaseMemory() {
+ VNInfoAllocator.Reset();
mi2iMap_.clear();
i2miMap_.clear();
r2iMap_.clear();
@@ -448,13 +449,13 @@
if (HasUse) {
LiveRange LR(getLoadIndex(index), getUseIndex(index),
- nI.getNextValue(~0U, 0));
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
DOUT << " +" << LR;
nI.addRange(LR);
}
if (HasDef) {
LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(~0U, 0));
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
DOUT << " +" << LR;
nI.addRange(LR);
}
@@ -500,9 +501,9 @@
VNInfo *ValNo;
unsigned SrcReg, DstReg;
if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNo = interval.getNextValue(defIndex, 0);
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
else
- ValNo = interval.getNextValue(defIndex, SrcReg);
+ ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
assert(ValNo->id == 0 && "First value in interval is not 0?");
@@ -526,7 +527,7 @@
LiveRange LR(defIndex, killIdx, ValNo);
interval.addRange(LR);
DOUT << " +" << LR << "\n";
- interval.addKill(*ValNo, killIdx);
+ interval.addKill(ValNo, killIdx);
return;
}
}
@@ -565,7 +566,7 @@
LiveRange LR(getMBBStartIdx(Kill->getParent()),
killIdx, ValNo);
interval.addRange(LR);
- interval.addKill(*ValNo, killIdx);
+ interval.addKill(ValNo, killIdx);
DOUT << " +" << LR;
}
@@ -597,8 +598,8 @@
// The new value number (#1) is defined by the instruction we claimed
// defined value #0.
- VNInfo *ValNo = interval.getNextValue(0, 0);
- interval.copyValNumInfo(*ValNo, *OldValNo);
+ VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
+ interval.copyValNumInfo(ValNo, OldValNo);
// Value#0 is now defined by the 2-addr instruction.
OldValNo->def = RedefIndex;
@@ -608,8 +609,8 @@
LiveRange LR(DefIndex, RedefIndex, ValNo);
DOUT << " replace range with " << LR;
interval.addRange(LR);
- interval.addKill(*ValNo, RedefIndex);
- interval.removeKills(*ValNo, RedefIndex, OldEnd);
+ interval.addKill(ValNo, RedefIndex);
+ interval.removeKills(ValNo, RedefIndex, OldEnd);
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
@@ -628,22 +629,22 @@
"PHI elimination vreg should have one kill, the PHI itself!");
// Remove the old range that we now know has an incorrect number.
- VNInfo *VNI = interval.getFirstValNumInfo();
+ VNInfo *VNI = interval.getValNumInfo(0);
MachineInstr *Killer = vi.Kills[0];
unsigned Start = getMBBStartIdx(Killer->getParent());
unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
DOUT << " Removing [" << Start << "," << End << "] from: ";
interval.print(DOUT, mri_); DOUT << "\n";
interval.removeRange(Start, End);
- interval.addKill(*VNI, Start+1); // odd # means phi node
+ interval.addKill(VNI, Start+1); // odd # means phi node
DOUT << " RESULT: "; interval.print(DOUT, mri_);
// Replace the interval with one of a NEW value number. Note that this
// value number isn't actually defined by an instruction, weird huh? :)
- LiveRange LR(Start, End, interval.getNextValue(~0, 0));
+ LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
DOUT << " replace range with " << LR;
interval.addRange(LR);
- interval.addKill(*LR.valno, End);
+ interval.addKill(LR.valno, End);
DOUT << " RESULT: "; interval.print(DOUT, mri_);
}
@@ -655,14 +656,14 @@
VNInfo *ValNo;
unsigned SrcReg, DstReg;
if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNo = interval.getNextValue(defIndex, 0);
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
else
- ValNo = interval.getNextValue(defIndex, SrcReg);
+ ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
- interval.addKill(*ValNo, killIndex-1); // odd # means phi node
+ interval.addKill(ValNo, killIndex-1); // odd # means phi node
DOUT << " +" << LR;
}
}
@@ -724,10 +725,10 @@
// Already exists? Extend old live interval.
LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
VNInfo *ValNo = (OldLR != interval.end())
- ? OldLR->valno : interval.getNextValue(start, SrcReg);
+ ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
LiveRange LR(start, end, ValNo);
interval.addRange(LR);
- interval.addKill(*LR.valno, end);
+ interval.addKill(LR.valno, end);
DOUT << " +" << LR << '\n';
}
@@ -792,9 +793,9 @@
}
}
- LiveRange LR(start, end, interval.getNextValue(start, 0));
+ LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
interval.addRange(LR);
- interval.addKill(*LR.valno, end);
+ interval.addKill(LR.valno, end);
DOUT << " +" << LR << '\n';
}
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 03e416b..4d5c081 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -158,7 +158,7 @@
for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) {
LiveInterval &AliasLI = li_->getInterval(*AS);
AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
- AliasLI.getNextValue(FillerStart, 0)));
+ AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
}
}
@@ -366,7 +366,8 @@
// Update the liveintervals of sub-registers.
for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS)
- li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt);
+ li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt,
+ li_->getVNInfoAllocator());
} else {
// Merge use info if the destination is a virtual register.
LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg);
@@ -564,13 +565,13 @@
// Okay, now that there is a single LHS value number that we're merging the
// RHS into, update the value number info for the LHS to indicate that the
// value number is defined where the RHS value number was.
- const VNInfo *VNI = RHS.getFirstValNumInfo();
+ const VNInfo *VNI = RHS.getValNumInfo(0);
LHSValNo->def = VNI->def;
LHSValNo->reg = VNI->reg;
// Okay, the final step is to loop over the RHS live intervals, adding them to
// the LHS.
- LHS.addKills(*LHSValNo, VNI->kills);
+ LHS.addKills(LHSValNo, VNI->kills);
LHS.MergeRangesInAsValue(RHS, LHSValNo);
LHS.weight += RHS.weight;
if (RHS.preference && !LHS.preference)
@@ -625,7 +626,7 @@
int RHSVal0DefinedFromLHS = -1;
int RHSValID = -1;
VNInfo *RHSValNoInfo = NULL;
- VNInfo *RHSValNoInfo0 = RHS.getFirstValNumInfo();
+ VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0);
unsigned RHSSrcReg = RHSValNoInfo0->reg;
if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) {
// If RHS is not defined as a copy from the LHS, we can use simpler and
@@ -809,8 +810,8 @@
E = LHSValsDefinedFromRHS.end(); I != E; ++I) {
VNInfo *VNI = I->first;
unsigned LHSValID = LHSValNoAssignments[VNI->id];
- LiveInterval::removeKill(*NewVNInfo[LHSValID], VNI->def);
- RHS.addKills(*NewVNInfo[LHSValID], VNI->kills);
+ LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def);
+ RHS.addKills(NewVNInfo[LHSValID], VNI->kills);
}
RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo);
@@ -821,8 +822,8 @@
E = RHSValsDefinedFromLHS.end(); I != E; ++I) {
VNInfo *VNI = I->first;
unsigned RHSValID = RHSValNoAssignments[VNI->id];
- LiveInterval::removeKill(*NewVNInfo[RHSValID], VNI->def);
- LHS.addKills(*NewVNInfo[RHSValID], VNI->kills);
+ LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def);
+ LHS.addKills(NewVNInfo[RHSValID], VNI->kills);
}
LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo);