Spiller now remove unused spill slots.

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

8 files changed, 132 insertions, 23 deletions

diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h
index 9934bf6..856fb34 100644
--- a/include/llvm/CodeGen/MachineFrameInfo.h
+++ b/include/llvm/CodeGen/MachineFrameInfo.h
@@ -80,7 +80,8 @@ class MachineFrameInfo {
 
   // StackObject - Represent a single object allocated on the stack.
   struct StackObject {
-    // The size of this object on the stack. 0 means a variable sized object
+    // The size of this object on the stack. 0 means a variable sized object,
+    // ~0ULL means a dead object.
     uint64_t Size;
 
     // Alignment - The required alignment of this stack slot.
@@ -292,6 +293,14 @@ public:
     return Objects[ObjectIdx+NumFixedObjects].isImmutable;
   }
 
+  /// isDeadObjectIndex - Returns true if the specified index corresponds to
+  /// a dead object.
+  bool isDeadObjectIndex(int ObjectIdx) const {
+    assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() &&
+           "Invalid Object Idx!");
+    return Objects[ObjectIdx+NumFixedObjects].Size == ~0ULL;
+  }
+
   /// CreateStackObject - Create a new statically sized stack object, returning
   /// a postive identifier to represent it.
   ///
@@ -304,6 +313,17 @@ public:
     return Objects.size()-NumFixedObjects-1;
   }
 
+  /// RemoveStackObject - Remove or mark dead a statically sized stack object.
+  ///
+  void RemoveStackObject(int ObjectIdx) {
+    if (ObjectIdx == (int)(Objects.size()-NumFixedObjects-1))
+      // Last object, simply pop it off the list.
+      Objects.pop_back();
+    else
+      // Mark it dead.
+      Objects[ObjectIdx+NumFixedObjects].Size = ~0ULL;
+  }
+
   /// CreateVariableSizedObject - Notify the MachineFrameInfo object that a
   /// variable sized object has been created.  This must be created whenever a
   /// variable sized object is created, whether or not the index returned is
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 716c370..00ba2e7 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -764,6 +764,9 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
                            : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
   if (fmi) {
+    // Remember this instruction uses the spill slot.
+    if (isSS) vrm.addSpillSlotUse(Slot, 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_)
diff --git a/lib/CodeGen/MachineFunction.cpp b/lib/CodeGen/MachineFunction.cpp
index 3089617..9bcf250 100644
--- a/lib/CodeGen/MachineFunction.cpp
+++ b/lib/CodeGen/MachineFunction.cpp
@@ -350,6 +350,10 @@ void MachineFrameInfo::print(const MachineFunction &MF, std::ostream &OS) const{
   for (unsigned i = 0, e = Objects.size(); i != e; ++i) {
     const StackObject &SO = Objects[i];
     OS << "  <fi #" << (int)(i-NumFixedObjects) << ">: ";
+    if (SO.Size == ~0ULL) {
+      OS << "dead\n";
+      continue;
+    }
     if (SO.Size == 0)
       OS << "variable sized";
     else
diff --git a/lib/CodeGen/PrologEpilogInserter.cpp b/lib/CodeGen/PrologEpilogInserter.cpp
index 1fec4c9..3cc2aa6 100644
--- a/lib/CodeGen/PrologEpilogInserter.cpp
+++ b/lib/CodeGen/PrologEpilogInserter.cpp
@@ -406,6 +406,8 @@ void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
       continue;
     if (RS && (int)i == RS->getScavengingFrameIndex())
       continue;
+    if (FFI->isDeadObjectIndex(i))
+      continue;
 
     // If stack grows down, we need to add size of find the lowest
     // address of the object.
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index fe81fdd..2e2dc5b 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -42,6 +42,7 @@ STATISTIC(NumLoads , "Number of loads added");
 STATISTIC(NumReused, "Number of values reused");
 STATISTIC(NumDSE   , "Number of dead stores elided");
 STATISTIC(NumDCE   , "Number of copies elided");
+STATISTIC(NumDSS   , "Number of dead spill slots removed");
 
 namespace {
   enum SpillerName { simple, local };
@@ -64,7 +65,9 @@ VirtRegMap::VirtRegMap(MachineFunction &mf)
   : TII(*mf.getTarget().getInstrInfo()), MF(mf), 
     Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT),
     Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
-    Virt2SplitKillMap(0), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1) {
+    Virt2SplitKillMap(0), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1),
+    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) {
+  SpillSlotToUsesMap.resize(8);
   grow();
 }
 
@@ -83,21 +86,28 @@ int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
          "attempt to assign stack slot to already spilled register");
   const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(virtReg);
-  int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
-                                                        RC->getAlignment());
-  Virt2StackSlotMap[virtReg] = frameIndex;
+  int SS = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
+                                                RC->getAlignment());
+  if (LowSpillSlot == NO_STACK_SLOT)
+    LowSpillSlot = SS;
+  if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
+    HighSpillSlot = SS;
+  unsigned Idx = SS-LowSpillSlot;
+  while (Idx >= SpillSlotToUsesMap.size())
+    SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
+  Virt2StackSlotMap[virtReg] = SS;
   ++NumSpills;
-  return frameIndex;
+  return SS;
 }
 
-void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
+void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
          "attempt to assign stack slot to already spilled register");
-  assert((frameIndex >= 0 ||
-          (frameIndex >= MF.getFrameInfo()->getObjectIndexBegin())) &&
+  assert((SS >= 0 ||
+          (SS >= MF.getFrameInfo()->getObjectIndexBegin())) &&
          "illegal fixed frame index");
-  Virt2StackSlotMap[virtReg] = frameIndex;
+  Virt2StackSlotMap[virtReg] = SS;
 }
 
 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
@@ -115,6 +125,13 @@ void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
   Virt2ReMatIdMap[virtReg] = id;
 }
 
+void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
+  if (!MF.getFrameInfo()->isFixedObjectIndex(FI)) {
+    assert(FI >= 0 && "Spill slot index should not be negative!");
+    SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
+  }
+}
+
 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
                             MachineInstr *NewMI, ModRef MRInfo) {
   // Move previous memory references folded to new instruction.
@@ -134,6 +151,21 @@ void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
   MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
 }
 
+void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
+  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+    MachineOperand &MO = MI->getOperand(i);
+    if (!MO.isFrameIndex())
+      continue;
+    int FI = MO.getIndex();
+    if (MF.getFrameInfo()->isFixedObjectIndex(FI))
+      continue;
+    SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
+  }
+  MI2VirtMap.erase(MI);
+  SpillPt2VirtMap.erase(MI);
+  RestorePt2VirtMap.erase(MI);
+}
+
 void VirtRegMap::print(std::ostream &OS) const {
   const TargetRegisterInfo* TRI = MF.getTarget().getRegisterInfo();
 
@@ -204,14 +236,18 @@ bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
                   std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
                   == LoadedRegs.end()) {
                 TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
+                MachineInstr *LoadMI = prior(MII);
+                VRM.addSpillSlotUse(StackSlot, LoadMI);
                 LoadedRegs.push_back(VirtReg);
                 ++NumLoads;
-                DOUT << '\t' << *prior(MII);
+                DOUT << '\t' << *LoadMI;
               }
 
               if (MO.isDef()) {
                 TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true,
                                         StackSlot, RC);
+                MachineInstr *StoreMI = next(MII);
+                VRM.addSpillSlotUse(StackSlot, StoreMI);
                 ++NumStores;
               }
             }
@@ -260,6 +296,16 @@ namespace {
            MBB != E; ++MBB)
         RewriteMBB(*MBB, VRM);
 
+      // Mark unused spill slots.
+      MachineFrameInfo *MFI = MF.getFrameInfo();
+      int SS = VRM.getLowSpillSlot();
+      if (SS != VirtRegMap::NO_STACK_SLOT)
+        for (int e = VRM.getHighSpillSlot(); SS <= e; ++SS)
+          if (!VRM.isSpillSlotUsed(SS)) {
+            MFI->RemoveStackObject(SS);
+            ++NumDSS;
+          }
+
       DOUT << "**** Post Machine Instrs ****\n";
       DEBUG(MF.dump());
 
@@ -725,6 +771,8 @@ namespace {
             } else {
               TII->loadRegFromStackSlot(*MBB, MII, NewPhysReg,
                                         NewOp.StackSlotOrReMat, AliasRC);
+              MachineInstr *LoadMI = prior(MII);
+              VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI);
               // Any stores to this stack slot are not dead anymore.
               MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL;            
               ++NumLoads;
@@ -906,7 +954,9 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
                                   std::vector<MachineOperand*> &KillOps,
                                   VirtRegMap &VRM) {
   TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC);
-  DOUT << "Store:\t" << *next(MII);
+  MachineInstr *StoreMI = next(MII);
+  VRM.addSpillSlotUse(StackSlot, StoreMI);
+  DOUT << "Store:\t" << *StoreMI;
 
   // If there is a dead store to this stack slot, nuke it now.
   if (LastStore) {
@@ -918,8 +968,8 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
     bool CheckDef = PrevMII != MBB.begin();
     if (CheckDef)
       --PrevMII;
-    MBB.erase(LastStore);
     VRM.RemoveMachineInstrFromMaps(LastStore);
+    MBB.erase(LastStore);
     if (CheckDef) {
       // Look at defs of killed registers on the store. Mark the defs
       // as dead since the store has been deleted and they aren't
@@ -931,8 +981,8 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
           if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
             // FIXME: This assumes a remat def does not have side
             // effects.
-            MBB.erase(DeadDef);
             VRM.RemoveMachineInstrFromMaps(DeadDef);
+            MBB.erase(DeadDef);
             ++NumDRM;
           }
         }
@@ -1006,8 +1056,10 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           ReMaterialize(MBB, MII, Phys, VirtReg, TRI, VRM);
         } else {
           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
-          TII->loadRegFromStackSlot(MBB, &MI, Phys, VRM.getStackSlot(VirtReg),
-                                    RC);
+          int SS = VRM.getStackSlot(VirtReg);
+          TII->loadRegFromStackSlot(MBB, &MI, Phys, SS, RC);
+          MachineInstr *LoadMI = prior(MII);
+          VRM.addSpillSlotUse(SS, LoadMI);
           ++NumLoads;
         }
         // This invalidates Phys.
@@ -1031,6 +1083,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
         int StackSlot = VRM.getStackSlot(VirtReg);
         TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC);
         MachineInstr *StoreMI = next(MII);
+        VRM.addSpillSlotUse(StackSlot, StoreMI);
         DOUT << "Store:\t" << StoreMI;
         VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
       }
@@ -1257,6 +1310,8 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
       } else {
         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
         TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
+        MachineInstr *LoadMI = prior(MII);
+        VRM.addSpillSlotUse(SSorRMId, LoadMI);
         ++NumLoads;
       }
       // This invalidates PhysReg.
@@ -1431,9 +1486,9 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
         if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
           ++NumDCE;
           DOUT << "Removing now-noop copy: " << MI;
+          VRM.RemoveMachineInstrFromMaps(&MI);
           MBB.erase(&MI);
           Erased = true;
-          VRM.RemoveMachineInstrFromMaps(&MI);
           Spills.disallowClobberPhysReg(VirtReg);
           goto ProcessNextInst;
         }
@@ -1507,9 +1562,9 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
             ++NumDCE;
             DOUT << "Removing now-noop copy: " << MI;
+            VRM.RemoveMachineInstrFromMaps(&MI);
             MBB.erase(&MI);
             Erased = true;
-            VRM.RemoveMachineInstrFromMaps(&MI);
             UpdateKills(*LastStore, RegKills, KillOps);
             goto ProcessNextInst;
           }
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index a7f47de..d1c14f6 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -20,6 +20,7 @@
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Streams.h"
 #include <map>
 
@@ -98,6 +99,12 @@ namespace llvm {
     /// conflicts with stack slot numbers.
     int ReMatId;
 
+    /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
+    int LowSpillSlot, HighSpillSlot;
+
+    /// SpillSlotToUsesMap - Records uses for each register spill slot.
+    SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
+
     VirtRegMap(const VirtRegMap&);     // DO NOT IMPLEMENT
     void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
 
@@ -299,6 +306,25 @@ namespace llvm {
       RestorePt2VirtMap.erase(I);
     }
 
+    /// @brief Return lowest spill slot index.
+    int getLowSpillSlot() const {
+      return LowSpillSlot;
+    }
+
+    /// @brief Return highest spill slot index.
+    int getHighSpillSlot() const {
+      return HighSpillSlot;
+    }
+
+    /// @brief Records a spill slot use.
+    void addSpillSlotUse(int FrameIndex, MachineInstr *MI);
+
+    /// @brief Returns true if spill slot has been used.
+    bool isSpillSlotUsed(int FrameIndex) const {
+      assert(FrameIndex >= 0 && "Spill slot index should not be negative!");
+      return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
+    }
+
     /// @brief Updates information about the specified virtual register's value
     /// folded into newMI machine instruction.
     void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI,
@@ -317,11 +343,7 @@ namespace llvm {
     
     /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
     /// the folded instruction map and spill point map.
-    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
-      MI2VirtMap.erase(MI);
-      SpillPt2VirtMap.erase(MI);
-      RestorePt2VirtMap.erase(MI);
-    }
+    void RemoveMachineInstrFromMaps(MachineInstr *MI);
 
     void print(std::ostream &OS) const;
     void print(std::ostream *OS) const { if (OS) print(*OS); }
diff --git a/lib/Target/ARM/ARMRegisterInfo.cpp b/lib/Target/ARM/ARMRegisterInfo.cpp
index 3be0d7a..3276849 100644
--- a/lib/Target/ARM/ARMRegisterInfo.cpp
+++ b/lib/Target/ARM/ARMRegisterInfo.cpp
@@ -870,6 +870,8 @@ static unsigned estimateStackSize(MachineFunction &MF, MachineFrameInfo *MFI) {
     if (FixedOff > Offset) Offset = FixedOff;
   }
   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
+    if (FFI->isDeadObjectIndex(i))
+      continue;
     Offset += FFI->getObjectSize(i);
     unsigned Align = FFI->getObjectAlignment(i);
     // Adjust to alignment boundary
diff --git a/test/CodeGen/X86/2008-02-22-ReMatBug.ll b/test/CodeGen/X86/2008-02-22-ReMatBug.ll
index c26c19e..fd97b61 100644
--- a/test/CodeGen/X86/2008-02-22-ReMatBug.ll
+++ b/test/CodeGen/X86/2008-02-22-ReMatBug.ll
@@ -1,4 +1,5 @@
 ; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of re-materialization} | grep 3
+; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of dead spill slots removed}
 ; rdar://5761454
 
 	%struct.quad_struct = type { i32, i32, %struct.quad_struct*, %struct.quad_struct*, %struct.quad_struct*, %struct.quad_struct*, %struct.quad_struct* }