Checkpoint SplitKit progress.
We are now at a point where we can split around simple single-entry, single-exit
loops, although still with some bugs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110257 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index a41d677..70cfc06 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -222,6 +222,13 @@
for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
E = usingLoops_.end(); I != E; ++I) {
getLoopBlocks(*I, Blocks);
+
+ // FIXME: We need an SSA updater to properly handle multiple exit blocks.
+ if (Blocks.Exits.size() > 1) {
+ DEBUG(dbgs() << "MultipleExits: " << **I);
+ continue;
+ }
+
LoopPtrSet *LPS = 0;
switch(analyzeLoopPeripheralUse(Blocks)) {
case OutsideLoop:
@@ -277,11 +284,14 @@
//===----------------------------------------------------------------------===//
/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
-SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm)
+SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
+ std::vector<LiveInterval*> &intervals)
: sa_(sa), lis_(lis), vrm_(vrm),
mri_(vrm.getMachineFunction().getRegInfo()),
tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()),
- dupli_(0), openli_(0)
+ dupli_(0), openli_(0),
+ intervals_(intervals),
+ firstInterval(intervals_.size())
{
const LiveInterval *curli = sa_.getCurLI();
assert(curli && "SplitEditor created from empty SplitAnalysis");
@@ -313,44 +323,56 @@
return VNI;
}
-/// Create a new virtual register and live interval to be used by following
-/// use* and copy* calls.
-void SplitEditor::openLI() {
- assert(!openli_ && "Previous LI not closed before openLI");
- openli_ = createInterval();
+/// Insert a COPY instruction curli -> li. Allocate a new value from li
+/// defined by the COPY. Note that rewrite() will deal with the curli
+/// register, so this function can be used to copy from any interval - openli,
+/// curli, or dupli.
+VNInfo *SplitEditor::insertCopy(LiveInterval &LI,
+ MachineBasicBlock &MBB,
+ MachineBasicBlock::iterator I) {
+ unsigned curli = sa_.getCurLI()->reg;
+ MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY),
+ LI.reg).addReg(curli);
+ SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
+ return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator());
}
-/// copyToPHI - Insert a copy to openli at the end of A, and catch it with a
-/// PHI def at the beginning of the successor B. This call is ignored if dupli
-/// is not live out of A.
-void SplitEditor::copyToPHI(MachineBasicBlock &A, MachineBasicBlock &B) {
- assert(openli_ && "openLI not called before copyToPHI");
+/// Create a new virtual register and live interval.
+void SplitEditor::openIntv() {
+ assert(!openli_ && "Previous LI not closed before openIntv");
+ openli_ = createInterval();
+ intervals_.push_back(openli_);
+ liveThrough_ = false;
+}
+
+/// enterIntvAtEnd - Enter openli at the end of MBB.
+/// PhiMBB is a successor inside openli where a PHI value is created.
+/// Currently, all entries must share the same PhiMBB.
+void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) {
+ assert(openli_ && "openIntv not called before enterIntvAtEnd");
SlotIndex EndA = lis_.getMBBEndIdx(&A);
VNInfo *DupVNIA = dupli_->getVNInfoAt(EndA.getPrevIndex());
if (!DupVNIA) {
- DEBUG(dbgs() << " ignoring copyToPHI, dupli not live out of BB#"
+ DEBUG(dbgs() << " ignoring enterIntvAtEnd, dupli not live out of BB#"
<< A.getNumber() << ".\n");
return;
}
- // Insert the COPY instruction at the end of A.
- MachineInstr *MI = BuildMI(A, A.getFirstTerminator(), DebugLoc(),
- tii_.get(TargetOpcode::COPY), dupli_->reg)
- .addReg(openli_->reg);
- SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
-
// Add a phi kill value and live range out of A.
- VNInfo *VNIA = openli_->getNextValue(DefIdx, MI, true,
- lis_.getVNInfoAllocator());
- openli_->addRange(LiveRange(DefIdx, EndA, VNIA));
+ VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator());
+ openli_->addRange(LiveRange(VNIA->def, EndA, VNIA));
+
+ // FIXME: If this is the only entry edge, we don't need the extra PHI value.
+ // FIXME: If there are multiple entry blocks (so not a loop), we need proper
+ // SSA update.
// Now look at the start of B.
SlotIndex StartB = lis_.getMBBStartIdx(&B);
SlotIndex EndB = lis_.getMBBEndIdx(&B);
LiveRange *DupB = dupli_->getLiveRangeContaining(StartB);
if (!DupB) {
- DEBUG(dbgs() << " copyToPHI:, dupli not live in to BB#"
+ DEBUG(dbgs() << " enterIntvAtEnd: dupli not live in to BB#"
<< B.getNumber() << ".\n");
return;
}
@@ -375,16 +397,16 @@
}
- DEBUG(dbgs() << " copyToPHI at " << DefIdx << ": " << *openli_ << '\n');
+ DEBUG(dbgs() << " enterIntvAtEnd: " << *openli_ << '\n');
}
-/// useLI - indicate that all instructions in MBB should use openli.
-void SplitEditor::useLI(const MachineBasicBlock &MBB) {
- useLI(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB));
+/// useIntv - indicate that all instructions in MBB should use openli.
+void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
+ useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB));
}
-void SplitEditor::useLI(SlotIndex Start, SlotIndex End) {
- assert(openli_ && "openLI not called before useLI");
+void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
+ assert(openli_ && "openIntv not called before useIntv");
// Map the dupli values from the interval into openli_
LiveInterval::const_iterator B = dupli_->begin(), E = dupli_->end();
@@ -392,8 +414,7 @@
if (I != B) {
--I;
- // I begins before Start, but overlaps. openli may already have a value from
- // copyToLI.
+ // I begins before Start, but overlaps. openli may already have a value.
if (I->end > Start && !openli_->liveAt(Start))
openli_->addRange(LiveRange(Start, std::min(End, I->end),
mapValue(I->valno)));
@@ -408,24 +429,95 @@
<< '\n');
}
-/// copyFromLI - Insert a copy back to dupli from openli at position I.
-SlotIndex SplitEditor::copyFromLI(MachineBasicBlock &MBB, MachineBasicBlock::iterator I) {
- assert(openli_ && "openLI not called before copyFromLI");
+/// leaveIntvAtTop - Leave the interval at the top of MBB.
+/// Currently, only one value can leave the interval.
+void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
+ assert(openli_ && "openIntv not called before leaveIntvAtTop");
+
+ SlotIndex Start = lis_.getMBBStartIdx(&MBB);
+ LiveRange *DupLR = dupli_->getLiveRangeContaining(Start);
+
+ // Is dupli even live-in to MBB?
+ if (!DupLR) {
+ DEBUG(dbgs() << " leaveIntvAtTop at " << Start << ": not live\n");
+ return;
+ }
+
+ // Is dupli defined by PHI at the beginning of MBB?
+ bool isPHIDef = DupLR->valno->isPHIDef() &&
+ DupLR->valno->def.getBaseIndex() == Start;
+
+ // If MBB is using a value of dupli that was defined outside the openli range,
+ // we don't want to copy it back here.
+ if (!isPHIDef && !openli_->liveAt(DupLR->valno->def)) {
+ DEBUG(dbgs() << " leaveIntvAtTop at " << Start
+ << ": using external value\n");
+ liveThrough_ = true;
+ return;
+ }
// Insert the COPY instruction.
- MachineInstr *MI =
- BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY), openli_->reg)
- .addReg(dupli_->reg);
- SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI);
+ MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(),
+ tii_.get(TargetOpcode::COPY), openli_->reg)
+ .addReg(dupli_->reg);
+ SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
- DEBUG(dbgs() << " copyFromLI at " << Idx << ": " << *openli_ << '\n');
- return Idx;
+ // Adjust dupli and openli values.
+ if (isPHIDef) {
+ // dupli was already a PHI on entry to MBB. Simply insert an openli PHI,
+ // and shift the dupli def down to the COPY.
+ VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
+ lis_.getVNInfoAllocator());
+ VNI->setIsPHIDef(true);
+ openli_->addRange(LiveRange(VNI->def, Idx, VNI));
+
+ dupli_->removeRange(Start, Idx);
+ DupLR->valno->def = Idx;
+ DupLR->valno->setIsPHIDef(false);
+ } else {
+ // The dupli value was defined somewhere inside the openli range.
+ DEBUG(dbgs() << " leaveIntvAtTop source value defined at "
+ << DupLR->valno->def << "\n");
+ // FIXME: We may not need a PHI here if all predecessors have the same
+ // value.
+ VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false,
+ lis_.getVNInfoAllocator());
+ VNI->setIsPHIDef(true);
+ openli_->addRange(LiveRange(VNI->def, Idx, VNI));
+
+ // FIXME: What if DupLR->valno is used by multiple exits? SSA Update.
+
+ // closeIntv is going to remove the superfluous live ranges.
+ DupLR->valno->def = Idx;
+ DupLR->valno->setIsPHIDef(false);
+ }
+
+ DEBUG(dbgs() << " leaveIntvAtTop at " << Idx << ": " << *openli_ << '\n');
}
-/// closeLI - Indicate that we are done editing the currently open
+/// closeIntv - Indicate that we are done editing the currently open
/// LiveInterval, and ranges can be trimmed.
-void SplitEditor::closeLI() {
- assert(openli_ && "openLI not called before closeLI");
+void SplitEditor::closeIntv() {
+ assert(openli_ && "openIntv not called before closeIntv");
+
+ DEBUG(dbgs() << " closeIntv cleaning up\n");
+
+ DEBUG(dbgs() << " dup " << *dupli_ << '\n');
+ DEBUG(dbgs() << " open " << *openli_ << '\n');
+
+ if (liveThrough_) {
+ DEBUG(dbgs() << " value live through region, leaving dupli as is.\n");
+ } else {
+ // live out with copies inserted, or killed by region. Either way we need to
+ // remove the overlapping region from dupli.
+ for (LiveInterval::iterator I = openli_->begin(), E = openli_->end();
+ I != E; ++I) {
+ dupli_->removeRange(I->start, I->end);
+ }
+ // FIXME: A block branching to the entry block may also branch elsewhere
+ // curli is live. We need both openli and curli to be live in that case.
+ DEBUG(dbgs() << " dup2 " << *dupli_ << '\n');
+ }
openli_ = 0;
}
@@ -433,6 +525,39 @@
/// instructions using curli to use the new intervals.
void SplitEditor::rewrite() {
assert(!openli_ && "Previous LI not closed before rewrite");
+ const LiveInterval *curli = sa_.getCurLI();
+ for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg),
+ RE = mri_.reg_end(); RI != RE;) {
+ MachineOperand &MO = RI.getOperand();
+ MachineInstr *MI = MO.getParent();
+ ++RI;
+ if (MI->isDebugValue()) {
+ DEBUG(dbgs() << "Zapping " << *MI);
+ // FIXME: We can do much better with debug values.
+ MO.setReg(0);
+ continue;
+ }
+ SlotIndex Idx = lis_.getInstructionIndex(MI);
+ Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
+ LiveInterval *LI = dupli_;
+ for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) {
+ LiveInterval *testli = intervals_[i];
+ if (testli->liveAt(Idx)) {
+ LI = testli;
+ break;
+ }
+ }
+ if (LI)
+ MO.setReg(LI->reg);
+ DEBUG(dbgs() << "rewrite " << Idx << '\t' << *MI);
+ }
+
+ // dupli_ goes in last, after rewriting.
+ if (dupli_)
+ intervals_.push_back(dupli_);
+
+ // FIXME: *Calculate spill weights, allocation hints, and register classes for
+ // firstInterval..
}
@@ -450,37 +575,29 @@
assert(CriticalExits.empty() && "Cannot break critical exits yet");
// Create new live interval for the loop.
- openLI();
+ openIntv();
// Insert copies in the predecessors.
for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
E = Blocks.Preds.end(); I != E; ++I) {
MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
- copyToPHI(MBB, *Loop->getHeader());
+ enterIntvAtEnd(MBB, *Loop->getHeader());
}
// Switch all loop blocks.
for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(),
E = Blocks.Loop.end(); I != E; ++I)
- useLI(**I);
+ useIntv(**I);
// Insert back copies in the exit blocks.
for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(),
E = Blocks.Exits.end(); I != E; ++I) {
MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
- SlotIndex Start = lis_.getMBBStartIdx(&MBB);
- VNInfo *VNI = sa_.getCurLI()->getVNInfoAt(Start);
- // Only insert a back copy if curli is live and is either a phi or a value
- // defined inside the loop.
- if (!VNI) continue;
- if (openli_->liveAt(VNI->def) ||
- (VNI->isPHIDef() && VNI->def.getBaseIndex() == Start))
- copyFromLI(MBB, MBB.begin());
+ leaveIntvAtTop(MBB);
}
// Done.
- closeLI();
+ closeIntv();
rewrite();
- abort();
}