Recover most of the compile time regression due to recent live interval changes.
1. Eliminate the costly live interval "swapping".
2. Change ValueNumberInfo container from SmallVector to std::vector. The former
performs slowly when the vector size is very large.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41536 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 9697d43..0be4e9b 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -288,25 +288,12 @@
void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
int *RHSValNoAssignments,
SmallVector<VNInfo, 16> &NewValueNumberInfo) {
-
- // Try to do the least amount of work possible. In particular, if there are
- // more liverange chunks in the other set than there are in the 'this' set,
- // swap sets to merge the fewest chunks in possible.
- //
- // Also, if one range is a physreg and one is a vreg, we always merge from the
- // vreg into the physreg, which leaves the vreg intervals pristine.
- if ((Other.ranges.size() > ranges.size() &&
- MRegisterInfo::isVirtualRegister(reg)) ||
- MRegisterInfo::isPhysicalRegister(Other.reg)) {
- swap(Other);
- std::swap(LHSValNoAssignments, RHSValNoAssignments);
- }
// Determine if any of our live range values are mapped. This is uncommon, so
// we want to avoid the interval scan if not.
bool MustMapCurValNos = false;
for (unsigned i = 0, e = getNumValNums(); i != e; ++i) {
- if (ValueNumberInfo[i].def == ~1U) continue; // tombstone value #
+ if (getDefForValNum(i) == ~1U) continue; // tombstone value #
if (i != (unsigned)LHSValNoAssignments[i]) {
MustMapCurValNos = true;
break;
@@ -345,7 +332,9 @@
// Update val# info first. Increasing live ranges may invalidate some kills.
ValueNumberInfo.clear();
- ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end());
+ for (SmallVector<VNInfo, 16>::iterator I = NewValueNumberInfo.begin(),
+ E = NewValueNumberInfo.end(); I != E; ++I)
+ ValueNumberInfo.push_back(*I);
// Okay, now insert the RHS live ranges into the LHS.
iterator InsertPos = begin();
@@ -472,7 +461,7 @@
ValueNumberInfo.pop_back();
} while (ValueNumberInfo.back().def == ~1U);
} else {
- ValueNumberInfo[V1].def = ~1U;
+ setDefForValNum(V1, ~1U);
}
}
@@ -511,22 +500,25 @@
// Print value number info.
if (getNumValNums()) {
OS << " ";
- for (unsigned i = 0; i != getNumValNums(); ++i) {
- if (i) OS << " ";
- OS << i << "@";
- if (ValueNumberInfo[i].def == ~1U) {
+ unsigned vnum = 0;
+ for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
+ ++i, ++vnum) {
+ const VNInfo &vni = *i;
+ if (vnum) OS << " ";
+ OS << vnum << "@";
+ if (vni.def == ~1U) {
OS << "x";
} else {
- if (ValueNumberInfo[i].def == ~0U)
+ if (vni.def == ~0U)
OS << "?";
else
- OS << ValueNumberInfo[i].def;
- unsigned e = ValueNumberInfo[i].kills.size();
- if (e) {
+ OS << vni.def;
+ unsigned ee = vni.kills.size();
+ if (ee) {
OS << "-(";
- for (unsigned j = 0; j != e; ++j) {
- OS << ValueNumberInfo[i].kills[j];
- if (j != e-1)
+ for (unsigned j = 0; j != ee; ++j) {
+ OS << vni.kills[j];
+ if (j != ee-1)
OS << " ";
}
OS << ")";
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 276a509..d8d0ce2 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -309,7 +309,8 @@
// Otherwise, if one of the intervals being joined is a physreg, this method
// always canonicalizes DstInt to be it. The output "SrcInt" will not have
// been modified, so we can use this information below to update aliases.
- if (JoinIntervals(DstInt, SrcInt)) {
+ bool Swapped = false;
+ if (JoinIntervals(DstInt, SrcInt, Swapped)) {
if (isDead) {
// Result of the copy is dead. Propagate this property.
if (SrcStart == 0) {
@@ -330,8 +331,8 @@
if (isShorten || isDead) {
// Shorten the destination live interval.
- if (repSrcReg == DstInt.reg)
- DstInt.removeRange(RemoveStart, RemoveEnd);
+ if (Swapped)
+ SrcInt.removeRange(RemoveStart, RemoveEnd);
}
} else {
// Coalescing failed.
@@ -345,9 +346,12 @@
return false;
}
- bool Swapped = repSrcReg == DstInt.reg;
- if (Swapped)
+ LiveInterval *ResSrcInt = &SrcInt;
+ LiveInterval *ResDstInt = &DstInt;
+ if (Swapped) {
std::swap(repSrcReg, repDstReg);
+ std::swap(ResSrcInt, ResDstInt);
+ }
assert(MRegisterInfo::isVirtualRegister(repSrcReg) &&
"LiveInterval::join didn't work right!");
@@ -356,15 +360,15 @@
// have clobbered values for this range.
if (MRegisterInfo::isPhysicalRegister(repDstReg)) {
// Unset unnecessary kills.
- if (!DstInt.containsOneValue()) {
- for (LiveInterval::Ranges::const_iterator I = SrcInt.begin(),
- E = SrcInt.end(); I != E; ++I)
+ if (!ResDstInt->containsOneValue()) {
+ for (LiveInterval::Ranges::const_iterator I = ResSrcInt->begin(),
+ E = ResSrcInt->end(); I != E; ++I)
unsetRegisterKills(I->start, I->end, repDstReg);
}
// Update the liveintervals of sub-registers.
for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS)
- li_->getInterval(*AS).MergeInClobberRanges(SrcInt);
+ li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt);
} else {
// Merge use info if the destination is a virtual register.
LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg);
@@ -372,7 +376,7 @@
dVI.NumUses += sVI.NumUses;
}
- DOUT << "\n\t\tJoined. Result = "; DstInt.print(DOUT, mri_);
+ DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_);
DOUT << "\n";
// Remember these liveintervals have been joined.
@@ -380,10 +384,6 @@
if (MRegisterInfo::isVirtualRegister(repDstReg))
JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister);
- // If the intervals were swapped by Join, swap them back so that the register
- // mapping (in the r2i map) is correct.
- if (Swapped) SrcInt.swap(DstInt);
-
// repSrcReg is guarateed to be the register whose live interval that is
// being merged.
li_->removeInterval(repSrcReg);
@@ -586,7 +586,8 @@
/// physreg, this method always canonicalizes LHS to be it. The output
/// "RHS" will not have been modified, so we can use this information
/// below to update aliases.
-bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) {
+bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS,
+ LiveInterval &RHS, bool &Swapped) {
// Compute the final value assignment, assuming that the live ranges can be
// coalesced.
SmallVector<int, 16> LHSValNoAssignments;
@@ -815,8 +816,17 @@
// If we get here, we know that we can coalesce the live ranges. Ask the
// intervals to coalesce themselves now.
- LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
- ValueNumberInfo);
+ if ((RHS.ranges.size() > LHS.ranges.size() &&
+ MRegisterInfo::isVirtualRegister(LHS.reg)) ||
+ MRegisterInfo::isPhysicalRegister(RHS.reg)) {
+ RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0],
+ ValueNumberInfo);
+ Swapped = true;
+ } else {
+ LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
+ ValueNumberInfo);
+ Swapped = false;
+ }
return true;
}