Add FastDSE, a new algorithm for doing dead store elimination. This algorithm is not as accurate

as the current DSE, but it only a linear scan over each block, rather than quadratic.  Eventually
(once it has been improved somewhat), this will replace the current DSE.

NOTE: This has not yet been extensively tested.


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

3 files changed, 138 insertions, 0 deletions

diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index be98f074b7..b445ba05be 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -61,6 +61,7 @@ namespace {
       (void) llvm::createDeadStoreEliminationPass();
       (void) llvm::createDeadTypeEliminationPass();
       (void) llvm::createEdgeProfilerPass();
+      (void) llvm::createFastDeadStoreEliminationPass();
       (void) llvm::createFunctionInliningPass();
       (void) llvm::createFunctionProfilerPass();
       (void) llvm::createGCSEPass();
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
index 948d6b5aae..ff12dc9ab7 100644
--- a/include/llvm/Transforms/Scalar.h
+++ b/include/llvm/Transforms/Scalar.h
@@ -325,6 +325,13 @@ FunctionPass *createGVNPREPass();
 
 //===----------------------------------------------------------------------===//
 //
+// FastDeadStoreElimination - This pass deletes stores that are post-dominated by
+// must-aliased stores and are not loaded used between the stores.
+//
+FunctionPass *createFastDeadStoreEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
 // CodeGenPrepare - This pass prepares a function for instruction selection.
 //
 FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0);
diff --git a/lib/Transforms/Scalar/FastDSE.cpp b/lib/Transforms/Scalar/FastDSE.cpp
new file mode 100644
index 0000000000..10873cd8ed
--- /dev/null
+++ b/lib/Transforms/Scalar/FastDSE.cpp
@@ -0,0 +1,130 @@
+//===- DeadStoreElimination.cpp - Dead Store Elimination ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a trivial dead store elimination that only considers
+// basic-block local redundant stores.
+//
+// FIXME: This should eventually be extended to be a post-dominator tree
+// traversal.  Doing so would be pretty trivial.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "fdse"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Function.h"
+#include "llvm/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Support/Compiler.h"
+using namespace llvm;
+
+STATISTIC(NumFastStores, "Number of stores deleted");
+STATISTIC(NumFastOther , "Number of other instrs removed");
+
+namespace {
+  struct VISIBILITY_HIDDEN FDSE : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    FDSE() : FunctionPass((intptr_t)&ID) {}
+
+    virtual bool runOnFunction(Function &F) {
+      bool Changed = false;
+      for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+        Changed |= runOnBasicBlock(*I);
+      return Changed;
+    }
+
+    bool runOnBasicBlock(BasicBlock &BB);
+    void DeleteDeadInstructionChains(Instruction *I,
+                                     SetVector<Instruction*> &DeadInsts);
+
+    // getAnalysisUsage - We require post dominance frontiers (aka Control
+    // Dependence Graph)
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.setPreservesCFG();
+      AU.addRequired<MemoryDependenceAnalysis>();
+      AU.addPreserved<MemoryDependenceAnalysis>();
+    }
+  };
+  char FDSE::ID = 0;
+  RegisterPass<FDSE> X("fdse", "Fast Dead Store Elimination");
+}
+
+FunctionPass *llvm::createFastDeadStoreEliminationPass() { return new FDSE(); }
+
+bool FDSE::runOnBasicBlock(BasicBlock &BB) {
+  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+  
+  DenseMap<Value*, StoreInst*> lastStore;
+  SetVector<Instruction*> possiblyDead;
+  
+  bool MadeChange = false;
+  
+  // Do a top-down walk on the BB
+  for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ++BBI) {
+    // If we find a store...
+    if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
+      
+      // ... to a pointer that has been stored to before...
+      if (lastStore.count(S->getPointerOperand())) {
+        StoreInst* last = lastStore[S->getPointerOperand()];
+        
+        // ... and no other memory dependencies are between them....
+        if (MD.getDependency(S) == last) {
+          // Remove it!
+          MD.removeInstruction(last);
+          
+          // DCE instructions only used to calculate that store
+          if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0)))
+            possiblyDead.insert(D);
+          
+          last->eraseFromParent();
+          NumFastStores++;
+          MadeChange = true;
+        }
+      }
+      
+      // Update our most-recent-store map
+      lastStore.insert(std::make_pair(S->getPointerOperand(), S));
+    }
+  }
+  
+  // Do a trivial DCE
+  while (!possiblyDead.empty()) {
+    Instruction *I = possiblyDead.back();
+    possiblyDead.pop_back();
+    DeleteDeadInstructionChains(I, possiblyDead);
+  }
+  
+  return MadeChange;
+}
+
+void FDSE::DeleteDeadInstructionChains(Instruction *I,
+                                      SetVector<Instruction*> &DeadInsts) {
+  // Instruction must be dead.
+  if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
+
+  // Let the memory dependence know
+  getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I);
+
+  // See if this made any operands dead.  We do it this way in case the
+  // instruction uses the same operand twice.  We don't want to delete a
+  // value then reference it.
+  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+    if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
+      DeadInsts.insert(Op);      // Attempt to nuke it later.
+    I->setOperand(i, 0);         // Drop from the operand list.
+  }
+
+  I->eraseFromParent();
+  ++NumFastOther;
+}