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/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 26722a3..b786b1d 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -377,8 +377,9 @@
vni->def = InstrSlots::scale(vni->def, factor);
for (unsigned i = 0; i < vni->kills.size(); ++i) {
- if (vni->kills[i] != 0)
- vni->kills[i] = InstrSlots::scale(vni->kills[i], factor);
+ if (!vni->kills[i].isPHIKill)
+ vni->kills[i].killIdx =
+ InstrSlots::scale(vni->kills[i].killIdx, factor);
}
}
}
@@ -840,7 +841,9 @@
if (ee || vni->hasPHIKill()) {
OS << "-(";
for (unsigned j = 0; j != ee; ++j) {
- OS << vni->kills[j];
+ OS << vni->kills[j].killIdx;
+ if (vni->kills[j].isPHIKill)
+ OS << "*";
if (j != ee-1)
OS << " ";
}
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);
diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp
index ae60c86..076f489 100644
--- a/lib/CodeGen/PreAllocSplitting.cpp
+++ b/lib/CodeGen/PreAllocSplitting.cpp
@@ -543,7 +543,7 @@
// FIXME: Need to set kills properly for inter-block stuff.
if (LI->isKill(RetVNI, UseIndex)) LI->removeKill(RetVNI, UseIndex);
if (IsIntraBlock)
- LI->addKill(RetVNI, EndIndex);
+ LI->addKill(RetVNI, EndIndex, false);
} else if (ContainsDefs && ContainsUses) {
SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB];
SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
@@ -605,7 +605,7 @@
if (foundUse && LI->isKill(RetVNI, StartIndex))
LI->removeKill(RetVNI, StartIndex);
if (IsIntraBlock) {
- LI->addKill(RetVNI, EndIndex);
+ LI->addKill(RetVNI, EndIndex, false);
}
}
@@ -682,7 +682,7 @@
I->second->setHasPHIKill(true);
unsigned KillIndex = LIs->getMBBEndIdx(I->first);
if (!LiveInterval::isKill(I->second, KillIndex))
- LI->addKill(I->second, KillIndex);
+ LI->addKill(I->second, KillIndex, false);
}
}
@@ -694,7 +694,7 @@
EndIndex = LIs->getMBBEndIdx(MBB);
LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI));
if (IsIntraBlock)
- LI->addKill(RetVNI, EndIndex);
+ LI->addKill(RetVNI, EndIndex, false);
// Memoize results so we don't have to recompute them.
if (!IsIntraBlock)
@@ -771,7 +771,7 @@
VNInfo* DeadVN = NewVNs[&*DI];
LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN));
- LI->addKill(DeadVN, DefIdx);
+ LI->addKill(DeadVN, DefIdx, false);
}
}
@@ -801,14 +801,15 @@
VNsToCopy.push_back(OldVN);
// Locate two-address redefinitions
- for (SmallVector<unsigned, 4>::iterator KI = OldVN->kills.begin(),
+ for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(),
KE = OldVN->kills.end(); KI != KE; ++KI) {
- MachineInstr* MI = LIs->getInstructionFromIndex(*KI);
+ assert(!KI->isPHIKill && "VN previously reported having no PHI kills.");
+ MachineInstr* MI = LIs->getInstructionFromIndex(KI->killIdx);
unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg);
if (DefIdx == ~0U) continue;
if (MI->isRegTiedToUseOperand(DefIdx)) {
VNInfo* NextVN =
- CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(*KI));
+ CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(KI->killIdx));
if (NextVN == OldVN) continue;
Stack.push_back(NextVN);
}
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 7e7d6b8..48e6d45 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -356,7 +356,7 @@
bool BHasPHIKill = BValNo->hasPHIKill();
SmallVector<VNInfo*, 4> BDeadValNos;
- SmallVector<unsigned, 4> BKills;
+ VNInfo::KillSet BKills;
std::map<unsigned, unsigned> BExtend;
// If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
@@ -395,7 +395,7 @@
if (Extended)
UseMO.setIsKill(false);
else
- BKills.push_back(li_->getUseIndex(UseIdx)+1);
+ BKills.push_back(VNInfo::KillInfo(false, li_->getUseIndex(UseIdx)+1));
}
unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
@@ -441,9 +441,9 @@
ValNo->def = AValNo->def;
ValNo->copy = NULL;
for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) {
- unsigned Kill = ValNo->kills[j];
+ unsigned Kill = ValNo->kills[j].killIdx;
if (Kill != BLR->end)
- BKills.push_back(Kill);
+ BKills.push_back(VNInfo::KillInfo(ValNo->kills[j].isPHIKill, Kill));
}
ValNo->kills.clear();
for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
@@ -547,7 +547,7 @@
// of last use.
LastUse->setIsKill();
removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
- li.addKill(LR->valno, LastUseIdx+1);
+ li.addKill(LR->valno, LastUseIdx+1, false);
unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
DstReg == li.reg) {
@@ -674,9 +674,7 @@
LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
if (DstLR == LI.end())
return false;
- unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1;
- if (DstLR->valno->kills.size() == 1 &&
- DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill())
+ if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0].isPHIKill)
return true;
return false;
}
@@ -1019,7 +1017,7 @@
}
if (LastUse) {
LastUse->setIsKill();
- li.addKill(VNI, LastUseIdx+1);
+ li.addKill(VNI, LastUseIdx+1, false);
} else {
// Remove dead implicit_def's.
while (!ImpDefs.empty()) {
diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index 405cd80..faaee0a 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -136,7 +136,7 @@
VNInfo *vni =
li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
- vni->kills.push_back(storeInstIdx);
+ li->addKill(vni, storeInstIdx, false);
DOUT << " Inserting store range: [" << start << ", " << end << ")\n";
LiveRange lr(start, end, vni);
@@ -201,7 +201,7 @@
VNInfo *vni =
li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
- vni->kills.push_back(lis->getInstructionIndex(mi));
+ li->addKill(vni, lis->getInstructionIndex(mi), false);
DOUT << " Intserting load range: [" << start << ", " << end << ")\n";
LiveRange lr(start, end, vni);
diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index ca99528..efd19fa 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -829,8 +829,8 @@
VNInfo* FirstVN = *Int.vni_begin();
FirstVN->setHasPHIKill(false);
if (I->getOperand(i).isKill())
- FirstVN->kills.push_back(
- LiveIntervals::getUseIndex(LI.getInstructionIndex(I)));
+ Int.addKill(FirstVN,
+ LiveIntervals::getUseIndex(LI.getInstructionIndex(I)), false);
LiveRange LR (LI.getMBBStartIdx(I->getParent()),
LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1,