Update to in-place spilling framework. Includes live interval scaling and trivial rewriter.

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

1 files changed, 110 insertions, 87 deletions

diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index eb2a8a1..ce63121 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -12,6 +12,7 @@
 #include "Spiller.h"
 #include "VirtRegMap.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
@@ -19,28 +20,105 @@
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/Debug.h"
 
-#include <algorithm>
-#include <map>
-
 using namespace llvm;
 
 Spiller::~Spiller() {}
 
 namespace {
 
-class TrivialSpiller : public Spiller {
-public:
-  TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) :
-    mf(mf), lis(lis), vrm(vrm)
+/// Utility class for spillers.
+class SpillerBase : public Spiller {
+protected:
+
+  MachineFunction *mf;
+  LiveIntervals *lis;
+  LiveStacks *ls;
+  MachineFrameInfo *mfi;
+  MachineRegisterInfo *mri;
+  const TargetInstrInfo *tii;
+  VirtRegMap *vrm;
+  
+  /// Construct a spiller base. 
+  SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
+    mf(mf), lis(lis), ls(ls), vrm(vrm)
   {
     mfi = mf->getFrameInfo();
     mri = &mf->getRegInfo();
     tii = mf->getTarget().getInstrInfo();
   }
 
-  std::vector<LiveInterval*> spill(LiveInterval *li) {
+  /// Insert a store of the given vreg to the given stack slot immediately
+  /// after the given instruction. Returns the base index of the inserted
+  /// instruction. The caller is responsible for adding an appropriate
+  /// LiveInterval to the LiveIntervals analysis.
+  unsigned insertStoreFor(MachineInstr *mi, unsigned ss,
+                          unsigned newVReg,
+                          const TargetRegisterClass *trc) {
+    MachineBasicBlock::iterator nextInstItr(mi); 
+    ++nextInstItr;
+
+    if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
+      lis->scaleNumbering(2);
+      ls->scaleNumbering(2);
+    }
+
+    unsigned miIdx = lis->getInstructionIndex(mi);
+
+    assert(lis->hasGapAfterInstr(miIdx));
+
+    tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg,
+                             true, ss, trc);
+    MachineBasicBlock::iterator storeInstItr(mi);
+    ++storeInstItr;
+    MachineInstr *storeInst = &*storeInstItr;
+    unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
+
+    assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
+           "Store inst index already in use.");
+    
+    lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
+
+    return storeInstIdx;
+  }
+
+  /// Insert a load of the given veg from the given stack slot immediately
+  /// before the given instruction. Returns the base index of the inserted
+  /// instruction. The caller is responsible for adding an appropriate
+  /// LiveInterval to the LiveIntervals analysis.
+  unsigned insertLoadFor(MachineInstr *mi, unsigned ss,
+                         unsigned newVReg,
+                         const TargetRegisterClass *trc) {
+    MachineBasicBlock::iterator useInstItr(mi);
+
+    if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
+      lis->scaleNumbering(2);
+      ls->scaleNumbering(2);
+    }
+
+    unsigned miIdx = lis->getInstructionIndex(mi);
+
+    assert(lis->hasGapBeforeInstr(miIdx));
+    
+    tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc);
+    MachineBasicBlock::iterator loadInstItr(mi);
+    --loadInstItr;
+    MachineInstr *loadInst = &*loadInstItr;
+    unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
+
+    assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
+           "Load inst index already in use.");
+
+    lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
+
+    return loadInstIdx;
+  }
 
-    DOUT << "Trivial spiller spilling " << *li << "\n";
+
+  /// Add spill ranges for every use/def of the live interval, inserting loads
+  /// immediately before each use, and stores after each def. No folding is
+  /// attempted.
+  std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
+    DOUT << "Spilling everywhere " << *li << "\n";
 
     assert(li->weight != HUGE_VALF &&
            "Attempting to spill already spilled value.");
@@ -51,16 +129,16 @@ public:
     std::vector<LiveInterval*> added;
     
     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
-    /*unsigned ss = mfi->CreateStackObject(trc->getSize(),
-                                         trc->getAlignment());*/
     unsigned ss = vrm->assignVirt2StackSlot(li->reg);
 
-    MachineRegisterInfo::reg_iterator regItr = mri->reg_begin(li->reg);
-    
-    while (regItr != mri->reg_end()) {
+    for (MachineRegisterInfo::reg_iterator
+         regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
 
       MachineInstr *mi = &*regItr;
-
+      do {
+        ++regItr;
+      } while (regItr != mri->reg_end() && (&*regItr == mi));
+      
       SmallVector<unsigned, 2> indices;
       bool hasUse = false;
       bool hasDef = false;
@@ -78,12 +156,12 @@ public:
       }
 
       unsigned newVReg = mri->createVirtualRegister(trc);
-      LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
-      newLI->weight = HUGE_VALF;
-
       vrm->grow();
       vrm->assignVirt2StackSlot(newVReg, ss);
 
+      LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
+      newLI->weight = HUGE_VALF;
+      
       for (unsigned i = 0; i < indices.size(); ++i) {
         mi->getOperand(indices[i]).setReg(newVReg);
 
@@ -92,6 +170,8 @@ public:
         }
       }
 
+      assert(hasUse || hasDef);
+
       if (hasUse) {
         unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc);
         unsigned start = lis->getDefIndex(loadInstIdx),
@@ -103,7 +183,6 @@ public:
         LiveRange lr(start, end, vni);
 
         newLI->addRange(lr);
-        added.push_back(newLI);
       }
 
       if (hasDef) {
@@ -117,90 +196,34 @@ public:
         LiveRange lr(start, end, vni);
       
         newLI->addRange(lr);
-        added.push_back(newLI);
       }
 
-      regItr = mri->reg_begin(li->reg);
+      added.push_back(newLI);
     }
 
 
     return added;
   }
 
+};
 
-private:
-
-  MachineFunction *mf;
-  LiveIntervals *lis;
-  MachineFrameInfo *mfi;
-  MachineRegisterInfo *mri;
-  const TargetInstrInfo *tii;
-  VirtRegMap *vrm;
-
-
-
-  void makeRoomForInsertBefore(MachineInstr *mi) {
-    if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
-      lis->computeNumbering();
-    }
-
-    assert(lis->hasGapBeforeInstr(lis->getInstructionIndex(mi)));
-  }
-
-  unsigned insertStoreFor(MachineInstr *mi, unsigned ss,
-                          unsigned newVReg,
-                          const TargetRegisterClass *trc) {
-    MachineBasicBlock::iterator nextInstItr(mi); 
-    ++nextInstItr;
-
-    makeRoomForInsertBefore(&*nextInstItr);
-
-    unsigned miIdx = lis->getInstructionIndex(mi);
-
-    tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg,
-                             true, ss, trc);
-    MachineBasicBlock::iterator storeInstItr(mi);
-    ++storeInstItr;
-    MachineInstr *storeInst = &*storeInstItr;
-    unsigned storeInstIdx = miIdx + LiveIntervals::InstrSlots::NUM;
-
-    assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
-           "Store inst index already in use.");
-    
-    lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
-
-    return storeInstIdx;
-  }
-
-  unsigned insertLoadFor(MachineInstr *mi, unsigned ss,
-                         unsigned newVReg,
-                         const TargetRegisterClass *trc) {
-    MachineBasicBlock::iterator useInstItr(mi);
-
-    makeRoomForInsertBefore(mi);
- 
-    unsigned miIdx = lis->getInstructionIndex(mi);
-    
-    tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc);
-    MachineBasicBlock::iterator loadInstItr(mi);
-    --loadInstItr;
-    MachineInstr *loadInst = &*loadInstItr;
-    unsigned loadInstIdx = miIdx - LiveIntervals::InstrSlots::NUM;
 
-    assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
-           "Load inst index already in use.");
-
-    lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
+/// Spills any live range using the spill-everywhere method with no attempt at
+/// folding.
+class TrivialSpiller : public SpillerBase {
+public:
+  TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
+    SpillerBase(mf, lis, ls, vrm) {}
 
-    return loadInstIdx;
+  std::vector<LiveInterval*> spill(LiveInterval *li) {
+    return trivialSpillEverywhere(li);
   }
 
 };
 
 }
 
-
 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
-                                   VirtRegMap *vrm) {
-  return new TrivialSpiller(mf, lis, vrm);
+                                   LiveStacks *ls, VirtRegMap *vrm) {
+  return new TrivialSpiller(mf, lis, ls, vrm);
 }