Add simple spiller.

[oota-llvm.git] / lib / CodeGen / LiveIntervalAnalysis.cpp

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 00e366fbb307e3e0955025a3f9125a5c6123729f..d6cc357fd5425b00f49f5413c7b1a25b93645aa5 100644 (file)
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -16,7 +16,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "liveintervals"
-#include "llvm/CodeGen/LiveIntervals.h"
+#include "LiveIntervals.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
@@ -31,6 +31,7 @@
 #include "Support/Debug.h"
 #include "Support/Statistic.h"
 #include "Support/STLExtras.h"
+#include "VirtRegMap.h"
 #include <cmath>
 #include <iostream>
 #include <limits>
@@ -134,7 +135,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
              mii != mie; ) {
             for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
                 const MachineOperand& mop = mii->getOperand(i);
-                if (mop.isRegister()) {
+                if (mop.isRegister() && mop.getReg()) {
                     // replace register with representative register
                     unsigned reg = rep(mop.getReg());
                     mii->SetMachineOperandReg(i, reg);
@@ -171,17 +172,22 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
                     std::ostream_iterator<Interval>(std::cerr, "\n")));
     DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
     DEBUG(
-        for (unsigned i = 0; i != i2miMap_.size(); ++i) {
-            if (const MachineInstr* mi = i2miMap_[i]) {
-                std:: cerr << i * InstrSlots::NUM << '\t';
-                mi->print(std::cerr, *tm_);
+        for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
+             mbbi != mbbe; ++mbbi) {
+            std::cerr << mbbi->getBasicBlock()->getName() << ":\n";
+            for (MachineBasicBlock::iterator mii = mbbi->begin(),
+                     mie = mbbi->end(); mii != mie; ++mii) {
+                std::cerr << getInstructionIndex(mii) << '\t';
+                mii->print(std::cerr, *tm_);
             }
         });
 
     return true;
 }
 
-void LiveIntervals::updateSpilledInterval(Interval& li, int slot)
+void LiveIntervals::updateSpilledInterval(Interval& li,
+                                          VirtRegMap& vrm,
+                                          int slot)
 {
     assert(li.weight != std::numeric_limits<float>::infinity() &&
            "attempt to spill already spilled interval!");
@@ -199,27 +205,40 @@ void LiveIntervals::updateSpilledInterval(Interval& li, int slot)
             while (!getInstructionFromIndex(index)) index += InstrSlots::NUM;
             MachineBasicBlock::iterator mi = getInstructionFromIndex(index);
 
+        for_operand:
             for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
                 MachineOperand& mop = mi->getOperand(i);
                 if (mop.isRegister() && mop.getReg() == li.reg) {
-                    // This is tricky. We need to add information in
-                    // the interval about the spill code so we have to
-                    // use our extra load/store slots.
-                    //
-                    // If we have a use we are going to have a load so
-                    // we start the interval from the load slot
-                    // onwards. Otherwise we start from the def slot.
-                    unsigned start = (mop.isUse() ?
-                                      getLoadIndex(index) :
-                                      getDefIndex(index));
-                    // If we have a def we are going to have a store
-                    // right after it so we end the interval after the
-                    // use of the next instruction. Otherwise we end
-                    // after the use of this instruction.
-                    unsigned end = 1 + (mop.isDef() ?
-                                        getUseIndex(index+InstrSlots::NUM) :
-                                        getUseIndex(index));
-                    li.addRange(start, end);
+                    MachineInstr* old = mi;
+                    if (mri_->foldMemoryOperand(mi, i, slot)) {
+                        lv_->instructionChanged(old, mi);
+                        vrm.virtFolded(li.reg, old, mi);
+                        mi2iMap_.erase(old);
+                        i2miMap_[index/InstrSlots::NUM] = mi;
+                        mi2iMap_[mi] = index;
+                        ++numFolded;
+                        goto for_operand;
+                    }
+                    else {
+                        // This is tricky. We need to add information in
+                        // the interval about the spill code so we have to
+                        // use our extra load/store slots.
+                        //
+                        // If we have a use we are going to have a load so
+                        // we start the interval from the load slot
+                        // onwards. Otherwise we start from the def slot.
+                        unsigned start = (mop.isUse() ?
+                                          getLoadIndex(index) :
+                                          getDefIndex(index));
+                        // If we have a def we are going to have a store
+                        // right after it so we end the interval after the
+                        // use of the next instruction. Otherwise we end
+                        // after the use of this instruction.
+                        unsigned end = 1 + (mop.isDef() ?
+                                            getUseIndex(index+InstrSlots::NUM) :
+                                            getUseIndex(index));
+                        li.addRange(start, end);
+                    }
                 }
             }
         }
@@ -227,6 +246,7 @@ void LiveIntervals::updateSpilledInterval(Interval& li, int slot)
     // the new spill weight is now infinity as it cannot be spilled again
     li.weight = std::numeric_limits<float>::infinity();
     DEBUG(std::cerr << '\n');
+    DEBUG(std::cerr << "\t\t\t\tupdated interval: " << li << '\n');
 }
 
 void LiveIntervals::printRegName(unsigned reg) const
@@ -417,7 +437,7 @@ void LiveIntervals::computeIntervals()
             for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
                 MachineOperand& mop = mi->getOperand(i);
                 // handle register defs - build intervals
-                if (mop.isRegister() && mop.isDef())
+                if (mop.isRegister() && mop.getReg() && mop.isDef())
                     handleRegisterDef(mbb, mi, mop.getReg());
             }
         }
@@ -652,8 +672,10 @@ void LiveIntervals::Interval::join(const LiveIntervals::Interval& other)
 LiveIntervals::Interval::Ranges::iterator
 LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it)
 {
-    for (Ranges::iterator n = next(it);
-         n != ranges.end() && ((it->second & 1) + it->second) >= n->first; ) {
+    Ranges::iterator n;
+    while ((n = next(it)) != ranges.end()) {
+        if (n->first > it->second)
+            break;
         it->second = std::max(it->second, n->second);
         n = ranges.erase(n);
     }
@@ -665,7 +687,8 @@ LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it)
 {
     while (it != ranges.begin()) {
         Ranges::iterator p = prior(it);
-        if (it->first > ((p->second & 1) + p->second)) break;
+        if (it->first > p->second)
+            break;
 
         it->first = std::min(it->first, p->first);
         it->second = std::max(it->second, p->second);