From 3b2c01723c2f7270e357f3b8502bb80572b3e644 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Fri, 20 Feb 2009 09:11:36 +0000
Subject: [PATCH] Add a quick pass to the stack slot colorer to eliminate some
 trivially redundant spills after coloring. Ideally these would never get
 created in the first place, but until we enhance the spiller to have a more
 global picture of what's happening, this is necessary for code quality in
 some circumstances.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65120 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/StackSlotColoring.cpp | 62 +++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp
index fdd2336e78d..39b0c59a1bf 100644
--- a/lib/CodeGen/StackSlotColoring.cpp
+++ b/lib/CodeGen/StackSlotColoring.cpp
@@ -19,6 +19,8 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -30,12 +32,20 @@ DisableSharing("no-stack-slot-sharing",
              cl::init(false), cl::Hidden,
              cl::desc("Surpress slot sharing during stack coloring"));
 
+static cl::opt<bool>
+EnableDCE("enable-ssc-dce",
+               cl::init(false), cl::Hidden,
+               cl::desc("Enable slot coloring DCE"));
+
 STATISTIC(NumEliminated,   "Number of stack slots eliminated due to coloring");
+STATISTIC(NumDeadAccesses,
+                          "Number of trivially dead stack accesses eliminated");
 
 namespace {
   class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass {
     LiveStacks* LS;
     MachineFrameInfo *MFI;
+    const TargetInstrInfo  *TII;
 
     // SSIntervals - Spill slot intervals.
     std::vector<LiveInterval*> SSIntervals;
@@ -67,6 +77,7 @@ namespace {
     
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<LiveStacks>();
+      
       AU.addPreservedID(MachineLoopInfoID);
       AU.addPreservedID(MachineDominatorsID);
       MachineFunctionPass::getAnalysisUsage(AU);
@@ -82,6 +93,7 @@ namespace {
     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
     int ColorSlot(LiveInterval *li);
     bool ColorSlots(MachineFunction &MF);
+    bool removeDeadStores(MachineBasicBlock* MBB);
   };
 } // end anonymous namespace
 
@@ -260,10 +272,55 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) {
   return true;
 }
 
+/// removeDeadStores - Scan through a basic block and look for loads followed
+/// by stores.  If they're both using the same stack slot, then the store is
+/// definitely dead.  This could obviously be much more aggressive (consider
+/// pairs with instructions between them), but such extensions might have a
+/// considerable compile time impact.
+bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) {
+  // FIXME: This could be much more aggressive, but we need to investigate
+  // the compile time impact of doing so.
+  bool changed = false;
+
+  SmallVector<MachineInstr*, 4> toErase;
+
+  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
+       I != E; ++I) {
+    MachineBasicBlock::iterator NextMI = next(I);
+    if (NextMI == MBB->end()) continue;
+    
+    int FirstSS, SecondSS;
+    unsigned LoadReg = 0;
+    unsigned StoreReg = 0;
+    if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue;
+    if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue;
+    if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue;
+    
+    ++NumDeadAccesses;
+    changed = true;
+    
+    if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) {
+      ++NumDeadAccesses;
+      toErase.push_back(I);
+    }
+    
+    toErase.push_back(NextMI);
+    ++I;
+  }
+  
+  for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(),
+       E = toErase.end(); I != E; ++I)
+    (*I)->eraseFromParent();
+  
+  return changed;
+}
+
+
 bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
   DOUT << "********** Stack Slot Coloring **********\n";
 
   MFI = MF.getFrameInfo();
+  TII = MF.getTarget().getInstrInfo();
   LS = &getAnalysis<LiveStacks>();
 
   bool Changed = false;
@@ -280,5 +337,10 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) {
     Assignments[i].clear();
   Assignments.clear();
 
+  if (EnableDCE) {
+    for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
+      Changed |= removeDeadStores(I);
+  }
+
   return Changed;
 }
-- 
2.34.1