STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple, "Number of splits that were simple");
+STATISTIC(NumCopies, "Number of copies inserted for splitting");
+STATISTIC(NumRemats, "Number of rematerialized defs for splitting");
+STATISTIC(NumRepairs, "Number of invalid live ranges repaired");
//===----------------------------------------------------------------------===//
// Split Analysis
UseBlocks.clear();
ThroughBlocks.clear();
CurLI = 0;
+ DidRepairRange = false;
}
SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
if (!calcLiveBlockInfo()) {
// FIXME: calcLiveBlockInfo found inconsistencies in the live range.
// I am looking at you, SimpleRegisterCoalescing!
+ DidRepairRange = true;
+ ++NumRepairs;
DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
const_cast<LiveIntervals&>(LIS)
.shrinkToUses(const_cast<LiveInterval*>(CurLI));
/// where CurLI is live.
bool SplitAnalysis::calcLiveBlockInfo() {
ThroughBlocks.resize(MF.getNumBlockIDs());
- NumThroughBlocks = 0;
+ NumThroughBlocks = NumGapBlocks = 0;
if (CurLI->empty())
return true;
SlotIndex Start, Stop;
tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
- // LVI is the first live segment overlapping MBB.
- BI.LiveIn = LVI->start <= Start;
- if (!BI.LiveIn)
- BI.Def = LVI->start;
-
- // Find the first and last uses in the block.
- bool Uses = UseI != UseE && *UseI < Stop;
- if (Uses) {
+ // If the block contains no uses, the range must be live through. At one
+ // point, SimpleRegisterCoalescing could create dangling ranges that ended
+ // mid-block.
+ if (UseI == UseE || *UseI >= Stop) {
+ ++NumThroughBlocks;
+ ThroughBlocks.set(BI.MBB->getNumber());
+ // The range shouldn't end mid-block if there are no uses. This shouldn't
+ // happen.
+ if (LVI->end < Stop)
+ return false;
+ } else {
+ // This block has uses. Find the first and last uses in the block.
BI.FirstUse = *UseI;
assert(BI.FirstUse >= Start);
do ++UseI;
while (UseI != UseE && *UseI < Stop);
BI.LastUse = UseI[-1];
assert(BI.LastUse < Stop);
- }
- // Look for gaps in the live range.
- bool hasGap = false;
- BI.LiveOut = true;
- while (LVI->end < Stop) {
- SlotIndex LastStop = LVI->end;
- if (++LVI == LVE || LVI->start >= Stop) {
- BI.Kill = LastStop;
- BI.LiveOut = false;
- break;
- }
- if (LastStop < LVI->start) {
- hasGap = true;
- BI.Kill = LastStop;
- BI.Def = LVI->start;
+ // LVI is the first live segment overlapping MBB.
+ BI.LiveIn = LVI->start <= Start;
+
+ // Look for gaps in the live range.
+ BI.LiveOut = true;
+ while (LVI->end < Stop) {
+ SlotIndex LastStop = LVI->end;
+ if (++LVI == LVE || LVI->start >= Stop) {
+ BI.LiveOut = false;
+ BI.LastUse = LastStop;
+ break;
+ }
+ if (LastStop < LVI->start) {
+ // There is a gap in the live range. Create duplicate entries for the
+ // live-in snippet and the live-out snippet.
+ ++NumGapBlocks;
+
+ // Push the Live-in part.
+ BI.LiveThrough = false;
+ BI.LiveOut = false;
+ UseBlocks.push_back(BI);
+ UseBlocks.back().LastUse = LastStop;
+
+ // Set up BI for the live-out part.
+ BI.LiveIn = false;
+ BI.LiveOut = true;
+ BI.FirstUse = LVI->start;
+ }
}
- }
- // Don't set LiveThrough when the block has a gap.
- BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
- if (Uses)
+ // Don't set LiveThrough when the block has a gap.
+ BI.LiveThrough = BI.LiveIn && BI.LiveOut;
UseBlocks.push_back(BI);
- else {
- ++NumThroughBlocks;
- ThroughBlocks.set(BI.MBB->getNumber());
- }
- // FIXME: This should never happen. The live range stops or starts without a
- // corresponding use. An earlier pass did something wrong.
- if (!BI.LiveThrough && !Uses)
- return false;
- // LVI is now at LVE or LVI->end >= Stop.
- if (LVI == LVE)
- break;
+ // LVI is now at LVE or LVI->end >= Stop.
+ if (LVI == LVE)
+ break;
+ }
// Live segment ends exactly at Stop. Move to the next segment.
if (LVI->end == Stop && ++LVI == LVE)
else
MFI = LIS.getMBBFromIndex(LVI->start);
}
+
+ assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
return true;
}
+unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
+ if (cli->empty())
+ return 0;
+ LiveInterval *li = const_cast<LiveInterval*>(cli);
+ LiveInterval::iterator LVI = li->begin();
+ LiveInterval::iterator LVE = li->end();
+ unsigned Count = 0;
+
+ // Loop over basic blocks where li is live.
+ MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start);
+ SlotIndex Stop = LIS.getMBBEndIdx(MFI);
+ for (;;) {
+ ++Count;
+ LVI = li->advanceTo(LVI, Stop);
+ if (LVI == LVE)
+ return Count;
+ do {
+ ++MFI;
+ Stop = LIS.getMBBEndIdx(MFI);
+ } while (Stop <= LVI->start);
+ }
+}
+
bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
unsigned OrigReg = VRM.getOriginal(CurLI->reg);
const LiveInterval &Orig = LIS.getInterval(OrigReg);
SlotIndex Def;
LiveInterval *LI = Edit->get(RegIdx);
+ // We may be trying to avoid interference that ends at a deleted instruction,
+ // so always begin RegIdx 0 early and all others late.
+ bool Late = RegIdx != 0;
+
// Attempt cheap-as-a-copy rematerialization.
LiveRangeEdit::Remat RM(ParentVNI);
if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) {
- Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
+ Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late);
+ ++NumRemats;
} else {
// Can't remat, just insert a copy from parent.
CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
.addReg(Edit->getReg());
- Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
+ Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
+ .getDefIndex();
+ ++NumCopies;
}
// Define the value in Reg.
else {
// Live-out, but we need updateSSA to tell us the value.
LiveOutSeen.set(MBB->getNumber());
- LiveOutCache[MBB] = LiveOutPair(0, 0);
+ LiveOutCache[MBB] = LiveOutPair((VNInfo*)0,
+ (MachineDomTreeNode*)0);
}
}
BlockStart = BlockEnd;
Edit->eliminateDeadDefs(Dead, LIS, VRM, TII);
}
-void SplitEditor::finish() {
+void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
++NumFinished;
// At this point, the live intervals in Edit contain VNInfos corresponding to
for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
(*I)->RenumberValues(LIS);
+ // Provide a reverse mapping from original indices to Edit ranges.
+ if (LRMap) {
+ LRMap->clear();
+ for (unsigned i = 0, e = Edit->size(); i != e; ++i)
+ LRMap->push_back(i);
+ }
+
// Now check if any registers were separated into multiple components.
ConnectedVNInfoEqClasses ConEQ(LIS);
for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
SmallVector<LiveInterval*, 8> dups;
dups.push_back(li);
- for (unsigned i = 1; i != NumComp; ++i)
+ for (unsigned j = 1; j != NumComp; ++j)
dups.push_back(&Edit->create(LIS, VRM));
ConEQ.Distribute(&dups[0], MRI);
+ // The new intervals all map back to i.
+ if (LRMap)
+ LRMap->resize(Edit->size(), i);
}
// Calculate spill weight and allocation hints for new intervals.
Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops);
+
+ assert(!LRMap || LRMap->size() == Edit->size());
}
projects / oota-llvm.git / blobdiff