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

1 files changed, 172 insertions, 55 deletions

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index a41d677fbb..70cfc065a3 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -222,6 +222,13 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
   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 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
 //===----------------------------------------------------------------------===//
 
 /// 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 @@ VNInfo *SplitEditor::mapValue(VNInfo *dupliVNI) {
   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");
+/// 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());
+}
+
+/// 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;
 }
 
-/// 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");
+/// 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 @@ void SplitEditor::copyToPHI(MachineBasicBlock &A, MachineBasicBlock &B) {
 
   }
 
-  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 @@ void SplitEditor::useLI(SlotIndex Start, SlotIndex End) {
 
   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 @@ void SplitEditor::useLI(SlotIndex Start, SlotIndex End) {
                << '\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();
+
+  // 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() << "  copyFromLI at " << Idx << ": " << *openli_ << '\n');
-  return Idx;
+  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 @@ void SplitEditor::closeLI() {
 /// 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 @@ void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
   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();
 }