Add SplitEditor to SplitKit. This class will be used to edit live intervals and

rewrite instructions for live range splitting.

Still work in progress.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109469 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 305 insertions, 10 deletions

diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp
index 1016c0ae9f..d8616fd8fb 100644
--- a/lib/CodeGen/InlineSpiller.cpp
+++ b/lib/CodeGen/InlineSpiller.cpp
@@ -110,8 +110,8 @@ bool InlineSpiller::split() {
   splitAnalysis_.analyze(li_);
 
   if (const MachineLoop *loop = splitAnalysis_.getBestSplitLoop()) {
-    if (splitAroundLoop(splitAnalysis_, loop))
-      return true;
+    SplitEditor(splitAnalysis_, lis_, vrm_).splitAroundLoop(loop);
+    return true;
   }
   return false;
 }
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 7d5eaf4643..a41d677fbb 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -14,8 +14,10 @@
 
 #define DEBUG_TYPE "splitter"
 #include "SplitKit.h"
+#include "VirtRegMap.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
@@ -47,6 +49,7 @@ void SplitAnalysis::clear() {
   usingInstrs_.clear();
   usingBlocks_.clear();
   usingLoops_.clear();
+  curli_ = 0;
 }
 
 bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
@@ -268,11 +271,216 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
   return Best;
 }
 
+
+//===----------------------------------------------------------------------===//
+//                               Split Editor
+//===----------------------------------------------------------------------===//
+
+/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
+SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm)
+  : sa_(sa), lis_(lis), vrm_(vrm),
+    mri_(vrm.getMachineFunction().getRegInfo()),
+    tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()),
+    dupli_(0), openli_(0)
+{
+  const LiveInterval *curli = sa_.getCurLI();
+  assert(curli && "SplitEditor created from empty SplitAnalysis");
+
+  // Make sure curli is assigned a stack slot, so all our intervals get the
+  // same slot as curli.
+  if (vrm_.getStackSlot(curli->reg) == VirtRegMap::NO_STACK_SLOT)
+    vrm_.assignVirt2StackSlot(curli->reg);
+
+  // Create an interval for dupli that is a copy of curli.
+  dupli_ = createInterval();
+  dupli_->Copy(*curli, &mri_, lis_.getVNInfoAllocator());
+  DEBUG(dbgs() << "SplitEditor DupLI: " << *dupli_ << '\n');
+}
+
+LiveInterval *SplitEditor::createInterval() {
+  unsigned curli = sa_.getCurLI()->reg;
+  unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli));
+  LiveInterval &Intv = lis_.getOrCreateInterval(Reg);
+  vrm_.grow();
+  vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli));
+  return &Intv;
+}
+
+VNInfo *SplitEditor::mapValue(VNInfo *dupliVNI) {
+  VNInfo *&VNI = valueMap_[dupliVNI];
+  if (!VNI)
+    VNI = openli_->createValueCopy(dupliVNI, lis_.getVNInfoAllocator());
+  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();
+}
+
+/// 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");
+
+  SlotIndex EndA = lis_.getMBBEndIdx(&A);
+  VNInfo *DupVNIA = dupli_->getVNInfoAt(EndA.getPrevIndex());
+  if (!DupVNIA) {
+    DEBUG(dbgs() << "  ignoring copyToPHI, 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));
+
+  // 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#"
+                 << B.getNumber() << ".\n");
+    return;
+  }
+
+  VNInfo *VNIB = openli_->getVNInfoAt(StartB);
+  if (!VNIB) {
+    // Create a phi value.
+    VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false,
+                                 lis_.getVNInfoAllocator());
+    VNIB->setIsPHIDef(true);
+    // Add a minimal range for the new value.
+    openli_->addRange(LiveRange(VNIB->def, std::min(EndB, DupB->end), VNIB));
+
+    VNInfo *&mapVNI = valueMap_[DupB->valno];
+    if (mapVNI) {
+      // Multiple copies - must create PHI value.
+      abort();
+    } else {
+      // This is the first copy of dupLR. Mark the mapping.
+      mapVNI = VNIB;
+    }
+
+  }
+
+  DEBUG(dbgs() << "  copyToPHI at " << DefIdx << ": " << *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));
+}
+
+void SplitEditor::useLI(SlotIndex Start, SlotIndex End) {
+  assert(openli_ && "openLI not called before useLI");
+
+  // Map the dupli values from the interval into openli_
+  LiveInterval::const_iterator B = dupli_->begin(), E = dupli_->end();
+  LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
+
+  if (I != B) {
+    --I;
+    // I begins before Start, but overlaps. openli may already have a value from
+    // copyToLI.
+    if (I->end > Start && !openli_->liveAt(Start))
+      openli_->addRange(LiveRange(Start, std::min(End, I->end),
+                        mapValue(I->valno)));
+    ++I;
+  }
+
+  // The remaining ranges begin after Start.
+  for (;I != E && I->start < End; ++I)
+    openli_->addRange(LiveRange(I->start, std::min(End, I->end),
+                                mapValue(I->valno)));
+  DEBUG(dbgs() << "  added range [" << Start << ';' << End << "): " << *openli_
+               << '\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");
+
+  // Insert the COPY instruction.
+  MachineInstr *MI =
+    BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY), openli_->reg)
+      .addReg(dupli_->reg);
+  SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI);
+
+  DEBUG(dbgs() << "  copyFromLI at " << Idx << ": " << *openli_ << '\n');
+  return Idx;
+}
+
+/// closeLI - 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");
+  openli_ = 0;
+}
+
+/// rewrite - after all the new live ranges have been created, rewrite
+/// instructions using curli to use the new intervals.
+void SplitEditor::rewrite() {
+  assert(!openli_ && "Previous LI not closed before rewrite");
+}
+
+
 //===----------------------------------------------------------------------===//
 //                               Loop Splitting
 //===----------------------------------------------------------------------===//
 
-bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {
-  return false;
+void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
+  SplitAnalysis::LoopBlocks Blocks;
+  sa_.getLoopBlocks(Loop, Blocks);
+
+  // Break critical edges as needed.
+  SplitAnalysis::BlockPtrSet CriticalExits;
+  sa_.getCriticalExits(Blocks, CriticalExits);
+  assert(CriticalExits.empty() && "Cannot break critical exits yet");
+
+  // Create new live interval for the loop.
+  openLI();
+
+  // 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());
+  }
+
+  // Switch all loop blocks.
+  for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(),
+       E = Blocks.Loop.end(); I != E; ++I)
+     useLI(**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());
+  }
+
+  // Done.
+  closeLI();
+  rewrite();
+  abort();
 }
 
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index cd059dffd6..601fc17092 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -14,19 +14,22 @@
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 
 namespace llvm {
 
 class LiveInterval;
 class LiveIntervals;
-class MachineBasicBlock;
 class MachineInstr;
-class MachineFunction;
-class MachineFunctionPass;
 class MachineLoop;
 class MachineLoopInfo;
+class MachineRegisterInfo;
 class TargetInstrInfo;
+class VirtRegMap;
+class VNInfo;
 
+/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
+/// opportunities.
 class SplitAnalysis {
   const MachineFunction &mf_;
   const LiveIntervals &lis_;
@@ -63,6 +66,8 @@ public:
   /// split.
   void analyze(const LiveInterval *li);
 
+  const LiveInterval *getCurLI() { return curli_; }
+
   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
   /// new interval.
   void clear();
@@ -113,8 +118,85 @@ public:
   const MachineLoop *getBestSplitLoop();
 };
 
-/// splitAroundLoop - Try to split curli into a separate live interval inside
-/// the loop. Retun true on success.
-bool splitAroundLoop(SplitAnalysis&, const MachineLoop*);
+/// SplitEditor - Edit machine code and LiveIntervals for live range
+/// splitting.
+///
+/// 1. Create a SplitEditor from a SplitAnalysis. This will create a new
+///    LiveInterval, dupli, that is identical to SA.curli.
+/// 2. Start a new live interval with openLI.
+/// 3. Insert copies to the new interval with copyTo* and mark the ranges where
+///    it should be used with use*.
+/// 4. Insert back-copies with copyFromLI.
+/// 5. Finish the current LI with closeLI and repeat from 2.
+/// 6. Rewrite instructions with rewrite().
+///
+class SplitEditor {
+  SplitAnalysis &sa_;
+  LiveIntervals &lis_;
+  VirtRegMap &vrm_;
+  MachineRegisterInfo &mri_;
+  const TargetInstrInfo &tii_;
+
+  /// dupli_ - Created as a copy of sa_.curli_, ranges are carved out as new
+  /// intervals get added through openLI / closeLI.
+  LiveInterval *dupli_;
+
+  /// Currently open LiveInterval.
+  LiveInterval *openli_;
+
+  /// createInterval - Create a new virtual register and LiveInterval with same
+  /// register class and spill slot as curli.
+  LiveInterval *createInterval();
+
+	/// valueMap_ - Map values in dupli to values in openli. These are direct 1-1
+	/// mappings, and do not include values created by inserted copies.
+	DenseMap<VNInfo*,VNInfo*> valueMap_;
+
+	/// mapValue - Return the openli value that corresponds to the given dupli
+	/// value.
+	VNInfo *mapValue(VNInfo *dupliVNI);	
+
+public:
+  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
+  SplitEditor(SplitAnalysis&, LiveIntervals&, VirtRegMap&);
+
+	/// getAnalysis - Get the corresponding analysis.
+	SplitAnalysis &getAnalysis() { return sa_; }
+
+  /// Create a new virtual register and live interval to be used by following
+  /// use* and copy* calls.
+  void openLI();
+
+  /// 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 copyToPHI(MachineBasicBlock &A, MachineBasicBlock &B);
+
+  /// useLI - indicate that all instructions in MBB should use openli.
+  void useLI(const MachineBasicBlock &MBB);
+
+  /// useLI - indicate that all instructions in range should use openli.
+  void useLI(SlotIndex Start, SlotIndex End);
+
+  /// copyFromLI - Insert a copy back to dupli from openli at position I.
+	/// This also marks the remainder of MBB as not used by openli.
+  SlotIndex copyFromLI(MachineBasicBlock &MBB, MachineBasicBlock::iterator I);
+
+  /// closeLI - Indicate that we are done editing the currently open
+  /// LiveInterval, and ranges can be trimmed.
+  void closeLI();
+
+  /// rewrite - after all the new live ranges have been created, rewrite
+  /// instructions using curli to use the new intervals.
+  void rewrite();
+
+  // ===--- High level methods ---===
+
+  /// splitAroundLoop - Split curli into a separate live interval inside
+  /// the loop.
+  void splitAroundLoop(const MachineLoop*);
+
+};
+
 
 }
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index a5599f68b6..87a9b2a7c4 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -152,6 +152,11 @@ namespace llvm {
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
+    MachineFunction &getMachineFunction() const {
+      assert(MF && "getMachineFunction called before runOnMAchineFunction");
+      return *MF;
+    }
+
     void grow();
 
     /// @brief returns true if the specified virtual register is