Improved tracking of value number kills. VN kills are now represented
as an (index,bool) pair. The bool flag records whether the kill is a
PHI kill or not. This code will be used to enable splitting of live
intervals containing PHI-kills.
A slight change to live interval weights introduced an extra spill
into lsr-code-insertion (outside the critical sections). The test
condition has been updated to reflect this.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75097 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 52a30bc..27ab5d5 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -92,6 +92,8 @@
mi2iMap_.clear();
i2miMap_.clear();
r2iMap_.clear();
+ terminatorGaps.clear();
+
// Release VNInfo memroy regions after all VNInfo objects are dtor'd.
VNInfoAllocator.Reset();
while (!ClonedMIs.empty()) {
@@ -223,6 +225,7 @@
MBB2IdxMap.clear();
mi2iMap_.clear();
i2miMap_.clear();
+ terminatorGaps.clear();
FunctionSize = 0;
@@ -241,6 +244,19 @@
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
+
+ if (I == MBB->getFirstTerminator()) {
+ // Leave a gap for before terminators, this is where we will point
+ // PHI kills.
+ bool inserted =
+ terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+ assert(inserted &&
+ "Multiple 'first' terminators encountered during numbering.");
+ i2miMap_.push_back(0);
+
+ MIIndex += InstrSlots::NUM;
+ }
+
bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
assert(inserted && "multiple MachineInstr -> index mappings");
inserted = true;
@@ -256,11 +272,24 @@
while (Slots--)
i2miMap_.push_back(0);
}
+
+ if (MBB->getFirstTerminator() == MBB->end()) {
+ // Leave a gap for before terminators, this is where we will point
+ // PHI kills.
+ bool inserted =
+ terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+ assert(inserted &&
+ "Multiple 'first' terminators encountered during numbering.");
+ i2miMap_.push_back(0);
+
+ MIIndex += InstrSlots::NUM;
+ }
// Set the MBB2IdxMap entry for this MBB.
MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
}
+
std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
if (!OldI2MI.empty())
@@ -335,18 +364,31 @@
// Remap the VNInfo kill indices, which works the same as
// the end indices above.
for (size_t i = 0; i < vni->kills.size(); ++i) {
- // PHI kills don't need to be remapped.
- if (!vni->kills[i]) continue;
-
- unsigned index = (vni->kills[i]-1) / InstrSlots::NUM;
- unsigned offset = vni->kills[i] % InstrSlots::NUM;
+ unsigned killIdx = vni->kills[i].killIdx;
+
+ unsigned index = (killIdx - 1) / InstrSlots::NUM;
+ unsigned offset = killIdx % InstrSlots::NUM;
+
if (offset == InstrSlots::LOAD) {
- std::vector<IdxMBBPair>::const_iterator I =
+ assert("Value killed at a load slot.");
+ /*std::vector<IdxMBBPair>::const_iterator I =
std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
--I;
- vni->kills[i] = getMBBEndIdx(I->second);
+ vni->kills[i] = getMBBEndIdx(I->second);*/
} else {
+ if (vni->kills[i].isPHIKill) {
+ std::vector<IdxMBBPair>::const_iterator I =
+ std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
+ --I;
+ vni->kills[i].killIdx = terminatorGaps[I->second];
+ } else {
+ assert(OldI2MI[index] != 0 &&
+ "Kill refers to instruction not present in index maps.");
+ vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
+ }
+
+ /*
unsigned idx = index;
while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
@@ -355,6 +397,7 @@
(idx == index ? offset : 0);
else
vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
+ */
}
}
}
@@ -379,6 +422,13 @@
}
std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
+ // Scale terminator gaps.
+ for (DenseMap<MachineBasicBlock*, unsigned>::iterator
+ TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
+ TGI != TGE; ++TGI) {
+ terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
+ }
+
// Scale the intervals.
for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
LI->second->scaleNumbering(factor);
@@ -589,7 +639,7 @@
LiveRange LR(defIndex, killIdx, ValNo);
interval.addRange(LR);
DOUT << " +" << LR << "\n";
- interval.addKill(ValNo, killIdx);
+ interval.addKill(ValNo, killIdx, false);
return;
}
}
@@ -622,7 +672,7 @@
LiveRange LR(getMBBStartIdx(Kill->getParent()),
killIdx, ValNo);
interval.addRange(LR);
- interval.addKill(ValNo, killIdx);
+ interval.addKill(ValNo, killIdx, false);
DOUT << " +" << LR;
}
@@ -671,7 +721,7 @@
LiveRange LR(DefIndex, RedefIndex, ValNo);
DOUT << " replace range with " << LR;
interval.addRange(LR);
- interval.addKill(ValNo, RedefIndex);
+ interval.addKill(ValNo, RedefIndex, false);
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
@@ -696,7 +746,11 @@
unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
DOUT << " Removing [" << Start << "," << End << "] from: ";
interval.print(DOUT, tri_); DOUT << "\n";
- interval.removeRange(Start, End);
+ interval.removeRange(Start, End);
+ assert(interval.ranges.size() == 1 &&
+ "newly discovered PHI interval has >1 ranges.");
+ MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
+ interval.addKill(VNI, terminatorGaps[killMBB], true);
VNI->setHasPHIKill(true);
DOUT << " RESULT: "; interval.print(DOUT, tri_);
@@ -707,7 +761,7 @@
LR.valno->setIsPHIDef(true);
DOUT << " replace range with " << LR;
interval.addRange(LR);
- interval.addKill(LR.valno, End);
+ interval.addKill(LR.valno, End, false);
DOUT << " RESULT: "; interval.print(DOUT, tri_);
}
@@ -731,7 +785,7 @@
unsigned killIndex = getMBBEndIdx(mbb) + 1;
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
- interval.addKill(ValNo, killIndex);
+ interval.addKill(ValNo, terminatorGaps[mbb], true);
ValNo->setHasPHIKill(true);
DOUT << " +" << LR;
}
@@ -819,7 +873,7 @@
ValNo->setHasRedefByEC(true);
LiveRange LR(start, end, ValNo);
interval.addRange(LR);
- interval.addKill(LR.valno, end);
+ interval.addKill(LR.valno, end, false);
DOUT << " +" << LR << '\n';
}
@@ -910,7 +964,7 @@
LiveRange LR(start, end, vni);
interval.addRange(LR);
- interval.addKill(LR.valno, end);
+ interval.addKill(LR.valno, end, false);
DOUT << " +" << LR << '\n';
}
@@ -1608,7 +1662,10 @@
MachineBasicBlock *MBB, unsigned Idx) const {
unsigned End = getMBBEndIdx(MBB);
for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
- unsigned KillIdx = VNI->kills[j];
+ if (VNI->kills[j].isPHIKill)
+ continue;
+
+ unsigned KillIdx = VNI->kills[j].killIdx;
if (KillIdx > Idx && KillIdx < End)
return true;
}
@@ -2412,13 +2469,14 @@
}
LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
- MachineInstr* startInst) {
+ MachineInstr* startInst) {
LiveInterval& Interval = getOrCreateInterval(reg);
VNInfo* VN = Interval.getNextValue(
getInstructionIndex(startInst) + InstrSlots::DEF,
startInst, true, getVNInfoAllocator());
VN->setHasPHIKill(true);
- VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
+ VN->kills.push_back(
+ VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
getMBBEndIdx(startInst->getParent()) + 1, VN);
Interval.addRange(LR);