earlycse can do trivial with-a-block dead store

elimination as well.  This deletes 60 stores in 176.gcc
that largely come from bitfield code.


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

2 files changed, 48 insertions, 6 deletions

diff --git a/lib/Transforms/Scalar/EarlyCSE.cpp b/lib/Transforms/Scalar/EarlyCSE.cpp
index 4ff150a..9e7092b 100644
--- a/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -30,6 +30,7 @@ STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
 STATISTIC(NumCSE,      "Number of instructions CSE'd");
 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
+STATISTIC(NumDSE,      "Number of trivial dead stores removed");
 
 static unsigned getHash(const void *V) {
   return DenseMapInfo<const void*>::getHashValue(V);
@@ -290,6 +291,12 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
   if (BB->getSinglePredecessor() == 0)
     ++CurrentGeneration;
   
+  /// LastStore - Keep track of the last non-volatile store that we saw... for
+  /// as long as there in no instruction that reads memory.  If we see a store
+  /// to the same location, we delete the dead store.  This zaps trivial dead
+  /// stores which can occur in bitfield code among other things.
+  StoreInst *LastStore = 0;
+  
   bool Changed = false;
 
   // See if any instructions in the block can be eliminated.  If so, do it.  If
@@ -337,7 +344,10 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
     // If this is a non-volatile load, process it.
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
       // Ignore volatile loads.
-      if (LI->isVolatile()) continue;
+      if (LI->isVolatile()) {
+        LastStore = 0;
+        continue;
+      }
       
       // If we have an available version of this load, and if it is the right
       // generation, replace this instruction.
@@ -356,9 +366,14 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
       // Otherwise, remember that we have this instruction.
       AvailableLoads->insert(Inst->getOperand(0),
                           std::pair<Value*, unsigned>(Inst, CurrentGeneration));
+      LastStore = 0;
       continue;
     }
     
+    // If this instruction may read from memory, forget LastStore.
+    if (Inst->mayReadFromMemory())
+      LastStore = 0;
+    
     // If this is a read-only call, process it.
     if (CallValue::canHandle(Inst)) {
       // If we have an available version of this call, and if it is the right
@@ -386,14 +401,31 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
     if (Inst->mayWriteToMemory()) {
       ++CurrentGeneration;
      
-      // Okay, we just invalidated anything we knew about loaded values.  Try to
-      // salvage *something* by remembering that the stored value is a live
-      // version of the pointer.  It is safe to forward from volatile stores to
-      // non-volatile loads, so we don't have to check for volatility of the
-      // store.
       if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+        // We do a trivial form of DSE if there are two stores to the same
+        // location with no intervening loads.  Delete the earlier store.
+        if (LastStore &&
+            LastStore->getPointerOperand() == SI->getPointerOperand()) {
+          DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << "  due to: "
+                << *Inst << '\n');
+          LastStore->eraseFromParent();
+          Changed = true;
+          ++NumDSE;
+          LastStore = 0;
+          continue;
+        }
+        
+        // Okay, we just invalidated anything we knew about loaded values.  Try
+        // to salvage *something* by remembering that the stored value is a live
+        // version of the pointer.  It is safe to forward from volatile stores
+        // to non-volatile loads, so we don't have to check for volatility of
+        // the store.
         AvailableLoads->insert(SI->getPointerOperand(),
          std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration));
+        
+        // Remember that this was the last store we saw for DSE.
+        if (!SI->isVolatile())
+          LastStore = SI;
       }
     }
   }
diff --git a/test/Transforms/EarlyCSE/basic.ll b/test/Transforms/EarlyCSE/basic.ll
index 5599a1c..bc152e7 100644
--- a/test/Transforms/EarlyCSE/basic.ll
+++ b/test/Transforms/EarlyCSE/basic.ll
@@ -96,3 +96,13 @@ define i32 @test6(i32 *%P) {
   ret i32 %V1
   ; CHECK: ret i32 42
 }
+
+;; Trivial dead store elimination.
+; CHECK: @test7
+define void @test7(i32 *%P) {
+  store i32 42, i32* %P
+  store i32 45, i32* %P
+  ret void
+  ; CHECK-NEXT: store i32 45
+  ; CHECK-NEXT: ret void
+}