New Spiller interface and trivial implementation.

llvm-svn: 72030

3 files changed, 262 insertions, 2 deletions

diff --git a/llvm/lib/CodeGen/RegAllocLinearScan.cpp b/llvm/lib/CodeGen/RegAllocLinearScan.cpp
index c5ce455b0ae..ac6ab323416 100644
--- a/llvm/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/llvm/lib/CodeGen/RegAllocLinearScan.cpp
@@ -14,6 +14,7 @@
 #define DEBUG_TYPE "regalloc"
 #include "VirtRegMap.h"
 #include "VirtRegRewriter.h"
+#include "Spiller.h"
 #include "llvm/Function.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
@@ -56,6 +57,11 @@ PreSplitIntervals("pre-alloc-split",
                   cl::desc("Pre-register allocation live interval splitting"),
                   cl::init(false), cl::Hidden);
 
+static cl::opt<bool>
+NewSpillFramework("new-spill-framework",
+                  cl::desc("New spilling framework"),
+                  cl::init(false), cl::Hidden);
+
 static RegisterRegAlloc
 linearscanRegAlloc("linearscan", "linear scan register allocator",
                    createLinearScanRegisterAllocator);
@@ -127,6 +133,8 @@ namespace {
 
     std::auto_ptr<VirtRegRewriter> rewriter_;
 
+    std::auto_ptr<Spiller> spiller_;
+
   public:
     virtual const char* getPassName() const {
       return "Linear Scan Register Allocator";
@@ -420,6 +428,13 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
 
   vrm_ = &getAnalysis<VirtRegMap>();
   if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
+  
+  if (NewSpillFramework) {
+    spiller_.reset(createSpiller(mf_, li_, vrm_));
+  }
+  else {
+    spiller_.reset(0);
+  }
 
   initIntervalSets();
 
@@ -1108,8 +1123,15 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
     SmallVector<LiveInterval*, 8> spillIs;
-    std::vector<LiveInterval*> added =
-      li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
+    std::vector<LiveInterval*> added;
+    
+    if (!NewSpillFramework) {
+      added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
+    }
+    else {
+      added = spiller_->spill(cur); 
+    }
+
     std::sort(added.begin(), added.end(), LISorter());
     addStackInterval(cur, ls_, li_, mri_, *vrm_);
     if (added.empty())
diff --git a/llvm/lib/CodeGen/Spiller.cpp b/llvm/lib/CodeGen/Spiller.cpp
new file mode 100644
index 00000000000..eb2a8a10b25
--- /dev/null
+++ b/llvm/lib/CodeGen/Spiller.cpp
@@ -0,0 +1,206 @@
+//===-- llvm/CodeGen/Spiller.cpp -  Spiller -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "spiller"
+
+#include "Spiller.h"
+#include "VirtRegMap.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#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)
+  {
+    mfi = mf->getFrameInfo();
+    mri = &mf->getRegInfo();
+    tii = mf->getTarget().getInstrInfo();
+  }
+
+  std::vector<LiveInterval*> spill(LiveInterval *li) {
+
+    DOUT << "Trivial spiller spilling " << *li << "\n";
+
+    assert(li->weight != HUGE_VALF &&
+           "Attempting to spill already spilled value.");
+
+    assert(!li->isStackSlot() &&
+           "Trying to spill a stack slot.");
+
+    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()) {
+
+      MachineInstr *mi = &*regItr;
+
+      SmallVector<unsigned, 2> indices;
+      bool hasUse = false;
+      bool hasDef = false;
+    
+      for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
+        MachineOperand &op = mi->getOperand(i);
+
+        if (!op.isReg() || op.getReg() != li->reg)
+          continue;
+      
+        hasUse |= mi->getOperand(i).isUse();
+        hasDef |= mi->getOperand(i).isDef();
+      
+        indices.push_back(i);
+      }
+
+      unsigned newVReg = mri->createVirtualRegister(trc);
+      LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
+      newLI->weight = HUGE_VALF;
+
+      vrm->grow();
+      vrm->assignVirt2StackSlot(newVReg, ss);
+
+      for (unsigned i = 0; i < indices.size(); ++i) {
+        mi->getOperand(indices[i]).setReg(newVReg);
+
+        if (mi->getOperand(indices[i]).isUse()) {
+          mi->getOperand(indices[i]).setIsKill(true);
+        }
+      }
+
+      if (hasUse) {
+        unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc);
+        unsigned start = lis->getDefIndex(loadInstIdx),
+                 end = lis->getUseIndex(lis->getInstructionIndex(mi));
+
+        VNInfo *vni =
+          newLI->getNextValue(loadInstIdx, 0, lis->getVNInfoAllocator());
+        vni->kills.push_back(lis->getInstructionIndex(mi));
+        LiveRange lr(start, end, vni);
+
+        newLI->addRange(lr);
+        added.push_back(newLI);
+      }
+
+      if (hasDef) {
+        unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc);
+        unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
+                 end = lis->getUseIndex(storeInstIdx);
+
+        VNInfo *vni =
+          newLI->getNextValue(storeInstIdx, 0, lis->getVNInfoAllocator());
+        vni->kills.push_back(storeInstIdx);
+        LiveRange lr(start, end, vni);
+      
+        newLI->addRange(lr);
+        added.push_back(newLI);
+      }
+
+      regItr = mri->reg_begin(li->reg);
+    }
+
+
+    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);
+
+    return loadInstIdx;
+  }
+
+};
+
+}
+
+
+llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
+                                   VirtRegMap *vrm) {
+  return new TrivialSpiller(mf, lis, vrm);
+}
diff --git a/llvm/lib/CodeGen/Spiller.h b/llvm/lib/CodeGen/Spiller.h
new file mode 100644
index 00000000000..f17a0b55a07
--- /dev/null
+++ b/llvm/lib/CodeGen/Spiller.h
@@ -0,0 +1,32 @@
+//===-- llvm/CodeGen/Spiller.h - Spiller -*- C++ -*------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SPILLER_H
+#define LLVM_CODEGEN_SPILLER_H
+
+#include <vector>
+
+namespace llvm {
+
+  /// Spiller interface.
+  ///
+  /// Implementations are utility classes which insert spill or remat code on
+  /// demand.
+  class Spiller {
+  public:
+    virtual ~Spiller() = 0;
+    virtual std::vector<class LiveInterval*> spill(class LiveInterval *li) = 0;
+  };
+
+  /// Create and return a spiller object, as specified on the command line.
+  Spiller* createSpiller(class MachineFunction *mf, class LiveIntervals *li,
+                         class VirtRegMap *vrm);
+}
+
+#endif