Add a spiller option to llc. A simple spiller will come soon. When we get CFG in the machine code represenation a global spiller will also be possible. Also document the linear scan register allocator but mark it as experimental for now.

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

5 files changed, 87 insertions, 46 deletions

diff --git a/docs/CommandGuide/llc.html b/docs/CommandGuide/llc.html
index 3671042..4583b11 100644
--- a/docs/CommandGuide/llc.html
+++ b/docs/CommandGuide/llc.html
@@ -150,6 +150,19 @@ OPTIONS
 
 		<di> local
 		<dd>Local register allocator</dd>
+
+		<di> linearscan
+		<dd>Linear scan global register allocator (experimental)</dd>
+
+	<li>-spiller=&lt;sp&gt;
+	<br>
+        Specify the spiller to use for register allocators that support it.
+        Currently this option is used by the linear scan register
+        allocator. The default is <i>local</i>.
+        Valid spillers are:
+	<dl compact>
+		<di> local
+		<dd>Local spiller</dd>
 	</dl>
 	<p>
 
diff --git a/lib/CodeGen/Passes.cpp b/lib/CodeGen/Passes.cpp
index bdcac4c..2fb6cb4 100644
--- a/lib/CodeGen/Passes.cpp
+++ b/lib/CodeGen/Passes.cpp
@@ -26,7 +26,7 @@ namespace {
            cl::Prefix,
            cl::values(clEnumVal(simple,      "  simple register allocator"),
                       clEnumVal(local,       "  local register allocator"),
-                      clEnumVal(linearscan,  "  linear-scan global register allocator"),
+                      clEnumVal(linearscan,  "  linear scan register allocator (experimental)"),
                       0),
            cl::init(local));
 }
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index d6c53cd..e92abe1 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -41,6 +41,7 @@ namespace {
 
         std::auto_ptr<PhysRegTracker> prt_;
         std::auto_ptr<VirtRegMap> vrm_;
+        std::auto_ptr<Spiller> spiller_;
 
         typedef std::vector<float> SpillWeights;
         SpillWeights spillWeights_;
@@ -147,12 +148,13 @@ bool RA::runOnMachineFunction(MachineFunction &fn) {
     li_ = &getAnalysis<LiveIntervals>();
     if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
     vrm_.reset(new VirtRegMap(*mf_));
+    if (!spiller_.get()) spiller_.reset(createSpiller());
 
     initIntervalSets(li_->getIntervals());
 
     linearScan();
 
-    eliminateVirtRegs(*mf_, *vrm_);
+    spiller_->runOnMachineFunction(*mf_, *vrm_);
 
     return true;
 }
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index 1238a2c..1187fc2 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -22,9 +22,10 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
-#include "Support/Statistic.h"
+#include "Support/CommandLine.h"
 #include "Support/Debug.h"
 #include "Support/DenseMap.h"
+#include "Support/Statistic.h"
 #include "Support/STLExtras.h"
 #include <iostream>
 
@@ -35,6 +36,15 @@ namespace {
     Statistic<> numStores("spiller", "Number of stores added");
     Statistic<> numLoads ("spiller", "Number of loads added");
 
+    enum SpillerName { local };
+
+    cl::opt<SpillerName>
+    SpillerOpt("spiller",
+               cl::desc("Spiller to use: (default: local)"),
+               cl::Prefix,
+               cl::values(clEnumVal(local, "  local spiller"),
+                          0),
+               cl::init(local));
 }
 
 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
@@ -88,41 +98,44 @@ std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
     return std::cerr << '\n';
 }
 
+Spiller::~Spiller()
+{
+
+}
+
 namespace {
 
-    class Spiller {
+    class LocalSpiller : public Spiller {
         typedef std::vector<unsigned> Phys2VirtMap;
         typedef std::vector<bool> PhysFlag;
         typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
 
-        MachineFunction& mf_;
-        const TargetMachine& tm_;
-        const TargetInstrInfo& tii_;
-        const MRegisterInfo& mri_;
-        const VirtRegMap& vrm_;
+        MachineFunction* mf_;
+        const TargetMachine* tm_;
+        const TargetInstrInfo* tii_;
+        const MRegisterInfo* mri_;
+        const VirtRegMap* vrm_;
         Phys2VirtMap p2vMap_;
         PhysFlag dirty_;
         Virt2MI lastDef_;
 
     public:
-        Spiller(MachineFunction& mf, const VirtRegMap& vrm)
-            : mf_(mf),
-              tm_(mf_.getTarget()),
-              tii_(tm_.getInstrInfo()),
-              mri_(*tm_.getRegisterInfo()),
-              vrm_(vrm),
-              p2vMap_(mri_.getNumRegs(), 0),
-              dirty_(mri_.getNumRegs(), false),
-              lastDef_() {
+        bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
+            mf_ = &mf;
+            tm_ = &mf_->getTarget();
+            tii_ = &tm_->getInstrInfo();
+            mri_ = tm_->getRegisterInfo();
+            vrm_ = &vrm;
+            p2vMap_.assign(mri_->getNumRegs(), 0);
+            dirty_.assign(mri_->getNumRegs(), false);
+
             DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
             DEBUG(std::cerr << "********** Function: "
-                  << mf_.getFunction()->getName() << '\n');
-        }
+                  << mf_->getFunction()->getName() << '\n');
 
-        void eliminateVirtRegs() {
-            for (MachineFunction::iterator mbbi = mf_.begin(),
-                     mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
-                lastDef_.grow(mf_.getSSARegMap()->getLastVirtReg());
+            for (MachineFunction::iterator mbbi = mf_->begin(),
+                     mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
+                lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
                 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
                 eliminateVirtRegsInMbb(*mbbi);
                 // clear map, dirty flag and last ref
@@ -130,6 +143,7 @@ namespace {
                 dirty_.assign(dirty_.size(), false);
                 lastDef_.clear();
             }
+            return true;
         }
 
     private:
@@ -137,21 +151,21 @@ namespace {
                                MachineBasicBlock::iterator mii,
                                unsigned physReg) {
             unsigned virtReg = p2vMap_[physReg];
-            if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
+            if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
                 assert(lastDef_[virtReg] && "virtual register is mapped "
                        "to a register and but was not defined!");
                 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
                 MachineBasicBlock::iterator nextLastRef = next(lastDef);
-                mri_.storeRegToStackSlot(*lastDef->getParent(),
+                mri_->storeRegToStackSlot(*lastDef->getParent(),
                                          nextLastRef,
                                          physReg,
-                                         vrm_.getStackSlot(virtReg),
-                                         mri_.getRegClass(physReg));
+                                         vrm_->getStackSlot(virtReg),
+                                         mri_->getRegClass(physReg));
                 ++numStores;
                 DEBUG(std::cerr << "added: ";
-                      prior(nextLastRef)->print(std::cerr, tm_);
+                      prior(nextLastRef)->print(std::cerr, *tm_);
                       std::cerr << "after: ";
-                      lastDef->print(std::cerr, tm_));
+                      lastDef->print(std::cerr, *tm_));
                 lastDef_[virtReg] = 0;
             }
             p2vMap_[physReg] = 0;
@@ -162,7 +176,7 @@ namespace {
                            MachineBasicBlock::iterator mii,
                            unsigned physReg) {
             vacateJustPhysReg(mbb, mii, physReg);
-            for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
+            for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
                 vacateJustPhysReg(mbb, mii, *as);
         }
 
@@ -175,13 +189,13 @@ namespace {
                 vacatePhysReg(mbb, mii, physReg);
                 p2vMap_[physReg] = virtReg;
                 // load if necessary
-                if (vrm_.hasStackSlot(virtReg)) {
-                    mri_.loadRegFromStackSlot(mbb, mii, physReg,
-                                              vrm_.getStackSlot(virtReg),
-                                              mri_.getRegClass(physReg));
+                if (vrm_->hasStackSlot(virtReg)) {
+                    mri_->loadRegFromStackSlot(mbb, mii, physReg,
+                                              vrm_->getStackSlot(virtReg),
+                                              mri_->getRegClass(physReg));
                     ++numLoads;
                     DEBUG(std::cerr << "added: ";
-                          prior(mii)->print(std::cerr,tm_));
+                          prior(mii)->print(std::cerr, *tm_));
                     lastDef_[virtReg] = mii;
                 }
             }
@@ -208,8 +222,8 @@ namespace {
                 // we clear all physical registers that may contain
                 // the value of the spilled virtual register
                 VirtRegMap::MI2VirtMap::const_iterator i, e;
-                for (tie(i, e) = vrm_.getFoldedVirts(mii); i != e; ++i) {
-                    unsigned physReg = vrm_.getPhys(i->second);
+                for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
+                    unsigned physReg = vrm_->getPhys(i->second);
                     if (physReg) vacateJustPhysReg(mbb, mii, physReg);
                 }
 
@@ -219,7 +233,7 @@ namespace {
                     if (op.isRegister() && op.getReg() && op.isUse() &&
                         MRegisterInfo::isVirtualRegister(op.getReg())) {
                         unsigned virtReg = op.getReg();
-                        unsigned physReg = vrm_.getPhys(virtReg);
+                        unsigned physReg = vrm_->getPhys(virtReg);
                         handleUse(mbb, mii, virtReg, physReg);
                         mii->SetMachineOperandReg(i, physReg);
                         // mark as dirty if this is def&use
@@ -231,7 +245,7 @@ namespace {
                 }
 
                 // spill implicit defs
-                const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
+                const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
                 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
                     vacatePhysReg(mbb, mii, *id);
 
@@ -243,13 +257,13 @@ namespace {
                         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
                             vacatePhysReg(mbb, mii, op.getReg());
                         else {
-                            unsigned physReg = vrm_.getPhys(op.getReg());
+                            unsigned physReg = vrm_->getPhys(op.getReg());
                             handleDef(mbb, mii, op.getReg(), physReg);
                             mii->SetMachineOperandReg(i, physReg);
                         }
                 }
 
-                DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
+                DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_));
             }
 
             for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
@@ -259,8 +273,13 @@ namespace {
     };
 }
 
-
-void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
+llvm::Spiller* llvm::createSpiller()
 {
-    Spiller(mf, vrm).eliminateVirtRegs();
+    switch (SpillerOpt) {
+    default:
+        std::cerr << "no spiller selected";
+        abort();
+    case local:
+        return new LocalSpiller();
+    }
 }
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index 90cc44d..3c2f8ee 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -108,7 +108,14 @@ namespace llvm {
 
     std::ostream& operator<<(std::ostream& os, const VirtRegMap& li);
 
-    void eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm);
+    struct Spiller {
+        virtual ~Spiller();
+
+        virtual bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) = 0;
+
+    };
+
+    Spiller* createSpiller();
 
 } // End llvm namespace