First cut trivial re-materialization support.

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

4 files changed, 151 insertions, 26 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 36db38e..a968063 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -50,6 +50,11 @@ namespace {
   EnableJoining("join-liveintervals",
                 cl::desc("Coallesce copies (default=true)"),
                 cl::init(true));
+
+  static cl::opt<bool>
+  EnableReMat("enable-rematerialization",
+                cl::desc("Perform trivial re-materialization"),
+                cl::init(false));
 }
 
 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
@@ -155,8 +160,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
         RemoveMachineInstrFromMaps(mii);
         mii = mbbi->erase(mii);
         ++numPeep;
-      }
-      else {
+      } else {
         for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
           const MachineOperand &mop = mii->getOperand(i);
           if (mop.isRegister() && mop.getReg() &&
@@ -165,9 +169,13 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
             unsigned reg = rep(mop.getReg());
             mii->getOperand(i).setReg(reg);
 
+            // If the definition instruction is re-materializable, its spill
+            // weight is zero.
             LiveInterval &RegInt = getInterval(reg);
-            RegInt.weight +=
-              (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth);
+            if (!RegInt.remat) {
+              RegInt.weight +=
+                (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth);
+            }
           }
         }
         ++mii;
@@ -300,7 +308,9 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
         MachineOperand& mop = MI->getOperand(i);
         if (mop.isRegister() && mop.getReg() == li.reg) {
-          if (MachineInstr *fmi = mri_->foldMemoryOperand(MI, i, slot)) {
+          MachineInstr *fmi = li.remat ? NULL
+            : mri_->foldMemoryOperand(MI, i, slot);
+          if (fmi) {
             // Attempt to fold the memory reference into the instruction.  If we
             // can do this, we don't need to insert spill code.
             if (lv_)
@@ -345,8 +355,11 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
 
             // create a new register for this spill
             vrm.grow();
+            if (li.remat)
+              vrm.setVirtIsReMaterialized(NewVReg, li.remat);
             vrm.assignVirt2StackSlot(NewVReg, slot);
             LiveInterval &nI = getOrCreateInterval(NewVReg);
+            nI.remat = li.remat;
             assert(nI.empty());
 
             // the spill weight is now infinity as it
@@ -422,6 +435,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
   // done once for the vreg.  We use an empty interval to detect the first
   // time we see a vreg.
   if (interval.empty()) {
+    // Remember if the definition can be rematerialized.
+    if (EnableReMat &&
+        vi.DefInst && tii_->isReMaterializable(vi.DefInst->getOpcode()))
+      interval.remat = vi.DefInst;
+
     // Get the Idx of the defining instructions.
     unsigned defIndex = getDefIndex(MIIdx);
 
@@ -497,6 +515,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
     }
 
   } else {
+    // Can't safely assume definition is rematierializable anymore.
+    interval.remat = NULL;
+
     // If this is the second time we see a virtual register definition, it
     // must be due to phi elimination or two addr elimination.  If this is
     // the result of two address elimination, then the vreg is one of the
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 76fc580..8ce7e8a 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
+#include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "PhysRegTracker.h"
 #include "VirtRegMap.h"
@@ -600,7 +601,12 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   // linearscan.
   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
-    int slot = vrm_->assignVirt2StackSlot(cur->reg);
+    // if the current interval is re-materializable, remember so and don't
+    // assign it a spill slot.
+    if (cur->remat)
+      vrm_->setVirtIsReMaterialized(cur->reg, cur->remat);
+    int slot = cur->remat ? vrm_->assignVirtReMatId(cur->reg)
+      : vrm_->assignVirt2StackSlot(cur->reg);
     std::vector<LiveInterval*> added =
       li_->addIntervalsForSpills(*cur, *vrm_, slot);
     if (added.empty())
@@ -627,7 +633,7 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
   std::vector<LiveInterval*> added;
   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
          "did not choose a register to spill?");
-  std::vector<bool> toSpill(mri_->getNumRegs(), false);
+  BitVector toSpill(mri_->getNumRegs());
 
   // We are going to spill minReg and all its aliases.
   toSpill[minReg] = true;
@@ -653,7 +659,10 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
         cur->overlapsFrom(*i->first, i->second)) {
       DOUT << "\t\t\tspilling(a): " << *i->first << '\n';
       earliestStart = std::min(earliestStart, i->first->beginNumber());
-      int slot = vrm_->assignVirt2StackSlot(i->first->reg);
+      if (i->first->remat)
+        vrm_->setVirtIsReMaterialized(reg, i->first->remat);
+      int slot = i->first->remat ? vrm_->assignVirtReMatId(reg)
+        : vrm_->assignVirt2StackSlot(reg);
       std::vector<LiveInterval*> newIs =
         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
@@ -667,7 +676,10 @@ void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
         cur->overlapsFrom(*i->first, i->second-1)) {
       DOUT << "\t\t\tspilling(i): " << *i->first << '\n';
       earliestStart = std::min(earliestStart, i->first->beginNumber());
-      int slot = vrm_->assignVirt2StackSlot(reg);
+      if (i->first->remat)
+        vrm_->setVirtIsReMaterialized(reg, i->first->remat);
+      int slot = i->first->remat ? vrm_->assignVirtReMatId(reg)
+        : vrm_->assignVirt2StackSlot(reg);
       std::vector<LiveInterval*> newIs =
         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index 9a1e58f..dfa5e43 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -35,6 +35,7 @@
 using namespace llvm;
 
 STATISTIC(NumSpills, "Number of register spills");
+STATISTIC(NumReMats, "Number of re-materialization");
 STATISTIC(NumStores, "Number of stores added");
 STATISTIC(NumLoads , "Number of loads added");
 STATISTIC(NumReused, "Number of values reused");
@@ -60,7 +61,8 @@ namespace {
 
 VirtRegMap::VirtRegMap(MachineFunction &mf)
   : TII(*mf.getTarget().getInstrInfo()), MF(mf), 
-    Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT) {
+    Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT),
+    ReMatId(MAX_STACK_SLOT+1) {
   grow();
 }
 
@@ -88,6 +90,15 @@ void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
   Virt2StackSlotMap[virtReg] = frameIndex;
 }
 
+int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
+  assert(MRegisterInfo::isVirtualRegister(virtReg));
+  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
+         "attempt to assign re-mat id to already spilled register");
+  Virt2StackSlotMap[virtReg] = ReMatId;
+  ++NumReMats;
+  return ReMatId++;
+}
+
 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
                             unsigned OpNo, MachineInstr *NewMI) {
   // Move previous memory references folded to new instruction.
@@ -227,13 +238,17 @@ namespace {
       DOUT << "\n**** Local spiller rewriting function '"
            << MF.getFunction()->getName() << "':\n";
 
+      std::vector<MachineInstr *> ReMatedMIs;
       for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
            MBB != E; ++MBB)
-        RewriteMBB(*MBB, VRM);
+        RewriteMBB(*MBB, VRM, ReMatedMIs);
+      for (unsigned i = 0, e = ReMatedMIs.size(); i != e; ++i)
+        delete ReMatedMIs[i];
       return true;
     }
   private:
-    void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM);
+    void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
+                    std::vector<MachineInstr*> &ReMatedMIs);
   };
 }
 
@@ -338,8 +353,11 @@ public:
     SpillSlotsAvailable[Slot] =
       std::make_pair((Reg << 1) | (unsigned)CanClobber, DefUses);
   
-    DOUT << "Remembering SS#" << Slot << " in physreg "
-         << MRI->getName(Reg) << "\n";
+    if (Slot > VirtRegMap::MAX_STACK_SLOT)
+      DOUT << "Remembering RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1;
+    else
+      DOUT << "Remembering SS#" << Slot;
+    DOUT << " in physreg " << MRI->getName(Reg) << "\n";
   }
 
   /// canClobberPhysReg - Return true if the spiller is allowed to change the 
@@ -405,7 +423,11 @@ void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
            "Bidirectional map mismatch!");
     SpillSlotsAvailable.erase(Slot);
     DOUT << "PhysReg " << MRI->getName(PhysReg)
-         << " clobbered, invalidating SS#" << Slot << "\n";
+         << " clobbered, invalidating ";
+    if (Slot > VirtRegMap::MAX_STACK_SLOT)
+      DOUT << "RM#" << Slot-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
+    else
+      DOUT << "SS#" << Slot << "\n";
   }
 }
 
@@ -599,7 +621,8 @@ namespace {
 
 /// rewriteMBB - Keep track of which spills are available even after the
 /// register allocator is done with them.  If possible, avoid reloading vregs.
-void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
+void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
+                              std::vector<MachineInstr*> &ReMatedMIs) {
 
   DOUT << MBB.getBasicBlock()->getName() << ":\n";
 
@@ -629,6 +652,27 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
     // Loop over all of the implicit defs, clearing them from our available
     // sets.
     const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
+
+    // If this instruction is being rematerialized, just remove it!
+    if (TID->Flags & M_REMATERIALIZIBLE) {
+      bool Remove = true;
+      for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+        MachineOperand &MO = MI.getOperand(i);
+        if (!MO.isRegister() || MO.getReg() == 0)
+          continue;   // Ignore non-register operands.
+        if (MO.isDef() && !VRM.isReMaterialized(MO.getReg())) {
+          Remove = false;
+          break;
+        }
+      }
+      if (Remove) {
+        VRM.RemoveFromFoldedVirtMap(&MI);
+        ReMatedMIs.push_back(MI.removeFromParent());
+        MII = NextMII;
+        continue;
+      }
+    }
+
     const unsigned *ImpDef = TID->ImplicitDefs;
     if (ImpDef) {
       for ( ; *ImpDef; ++ImpDef) {
@@ -670,6 +714,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
       if (!MO.isUse())
         continue;  // Handle defs in the loop below (handle use&def here though)
 
+      bool doReMat = VRM.isReMaterialized(VirtReg);
       int StackSlot = VRM.getStackSlot(VirtReg);
       unsigned PhysReg;
 
@@ -695,7 +740,11 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
         
         if (CanReuse) {
           // If this stack slot value is already available, reuse it!
-          DOUT << "Reusing SS#" << StackSlot << " from physreg "
+          if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
+            DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
+          else
+            DOUT << "Reusing SS#" << StackSlot;
+          DOUT << " from physreg "
                << MRI->getName(PhysReg) << " for vreg"
                << VirtReg <<" instead of reloading into physreg "
                << MRI->getName(VRM.getPhys(VirtReg)) << "\n";
@@ -767,8 +816,11 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
         // incoming, we don't need to inserted a dead copy.
         if (DesignatedReg == PhysReg) {
           // If this stack slot value is already available, reuse it!
-          DOUT << "Reusing SS#" << StackSlot << " from physreg "
-               << MRI->getName(PhysReg) << " for vreg"
+          if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
+            DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
+          else
+            DOUT << "Reusing SS#" << StackSlot;
+          DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg"
                << VirtReg
                << " instead of reloading into same physreg.\n";
           MI.getOperand(i).setReg(PhysReg);
@@ -828,12 +880,16 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
       
       PhysRegsUsed[PhysReg] = true;
       ReusedOperands.markClobbered(PhysReg);
-      MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
+      if (doReMat)
+        MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg));
+      else
+        MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
       // This invalidates PhysReg.
       Spills.ClobberPhysReg(PhysReg);
 
       // Any stores to this stack slot are not dead anymore.
-      MaybeDeadStores.erase(StackSlot);
+      if (!doReMat)
+        MaybeDeadStores.erase(StackSlot);
       Spills.addAvailable(StackSlot, &MI, PhysReg);
       // Assumes this is the last use. IsKill will be unset if reg is reused
       // unless it's a two-address operand.
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index 5b06c01..61ce92f 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -18,6 +18,7 @@
 #define LLVM_CODEGEN_VIRTREGMAP_H
 
 #include "llvm/Target/MRegisterInfo.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/IndexedMap.h"
 #include "llvm/Support/Streams.h"
 #include <map>
@@ -28,6 +29,12 @@ namespace llvm {
 
   class VirtRegMap {
   public:
+    enum {
+      NO_PHYS_REG = 0,
+      NO_STACK_SLOT = ~0 >> 1,
+      MAX_STACK_SLOT = (1 << 18)-1
+    };
+
     enum ModRef { isRef = 1, isMod = 2, isModRef = 3 };
     typedef std::multimap<MachineInstr*,
                           std::pair<unsigned, ModRef> > MI2VirtMapTy;
@@ -53,14 +60,20 @@ namespace llvm {
     /// read/written by this instruction.
     MI2VirtMapTy MI2VirtMap;
 
+    /// ReMatMap - This is irtual register to re-materialized instruction
+    /// mapping. Each virtual register whose definition is going to be
+    /// re-materialized has an entry in it.
+    std::map<unsigned, const MachineInstr*> ReMatMap;
+
+    /// ReMatId - Instead of assigning a stack slot to a to be rematerialized
+    /// virtaul register, an unique id is being assinged. This keeps track of
+    /// the highest id used so far. Note, this starts at (1<<18) to avoid
+    /// conflicts with stack slot numbers.
+    int ReMatId;
+
     VirtRegMap(const VirtRegMap&);     // DO NOT IMPLEMENT
     void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
 
-    enum {
-      NO_PHYS_REG = 0,
-      NO_STACK_SLOT = ~0 >> 1
-    };
-
   public:
     VirtRegMap(MachineFunction &mf);
 
@@ -125,6 +138,29 @@ namespace llvm {
     /// the specified stack slot
     void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
 
+    /// @brief assign an unique re-materialization id to the specified
+    /// virtual register.
+    int assignVirtReMatId(unsigned virtReg);
+
+    /// @brief returns true if the specified virtual register is being
+    /// re-materialized.
+    bool isReMaterialized(unsigned virtReg) const {
+      return ReMatMap.count(virtReg) != 0;
+    }
+
+    /// @brief returns the original machine instruction being re-issued
+    /// to re-materialize the specified virtual register.
+    const MachineInstr *getReMaterializedMI(unsigned virtReg) {
+      return ReMatMap[virtReg];
+    }
+
+    /// @brief records the specified virtual register will be
+    /// re-materialized and the original instruction which will be re-issed
+    /// for this purpose.
+    void setVirtIsReMaterialized(unsigned virtReg, MachineInstr *def) {
+      ReMatMap[virtReg] = def;
+    }
+
     /// @brief Updates information about the specified virtual register's value
     /// folded into newMI machine instruction.  The OpNum argument indicates the
     /// operand number of OldMI that is folded.