From 8aa895b19a64796a4c1f7cd0cb0750ad34263ea0 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Mon, 28 Jul 2008 16:14:26 +0000
Subject: [PATCH] Add support for eliminating stores that store the same value
 that was just loaded. This fixes PR2599.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54133 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/DeadStoreElimination.cpp           | 37 ++++++++++++++++++-
 .../2008-07-28-load-store.ll                  | 14 +++++++
 2 files changed, 49 insertions(+), 2 deletions(-)
 create mode 100644 test/Transforms/DeadStoreElimination/2008-07-28-load-store.ll

diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp
index 4662e05aba5..0011d9566e3 100644
--- a/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -26,6 +26,7 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Transforms/Utils/Local.h"
@@ -85,9 +86,11 @@ namespace {
     // Dependence Graph)
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesCFG();
+      AU.addRequired<DominatorTree>();
       AU.addRequired<TargetData>();
       AU.addRequired<AliasAnalysis>();
       AU.addRequired<MemoryDependenceAnalysis>();
+      AU.addPreserved<DominatorTree>();
       AU.addPreserved<AliasAnalysis>();
       AU.addPreserved<MemoryDependenceAnalysis>();
     }
@@ -172,8 +175,37 @@ bool DSE::runOnBasicBlock(BasicBlock &BB) {
       // No known stores after the free
       last = 0;
     } else {
-      // Update our most-recent-store map.
-      last = cast<StoreInst>(BBI);
+      StoreInst* S = cast<StoreInst>(BBI);
+      
+      // If we're storing the same value back to a pointer that we just
+      // loaded from, then the store can be removed;
+      if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) {
+        Instruction* dep = MD.getDependency(S);
+        DominatorTree& DT = getAnalysis<DominatorTree>();
+        
+        if (S->getParent() == L->getParent() &&
+            S->getPointerOperand() == L->getPointerOperand() &&
+            ( dep == MemoryDependenceAnalysis::None ||
+              dep == MemoryDependenceAnalysis::NonLocal ||
+              DT.dominates(dep, L))) {
+          if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
+            possiblyDead.insert(D);
+          if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
+            possiblyDead.insert(D);
+          
+          // Avoid iterator invalidation.
+          BBI--;
+          
+          MD.removeInstruction(S);
+          S->eraseFromParent();
+          NumFastStores++;
+          MadeChange = true;
+        } else
+          // Update our most-recent-store map.
+          last = S;
+      } else
+        // Update our most-recent-store map.
+        last = S;
     }
   }
   
@@ -287,6 +319,7 @@ bool DSE::handleEndBlock(BasicBlock& BB,
             possiblyDead.insert(D);
         
           BBI++;
+          MD.removeInstruction(S);
           S->eraseFromParent();
           NumFastStores++;
           MadeChange = true;
diff --git a/test/Transforms/DeadStoreElimination/2008-07-28-load-store.ll b/test/Transforms/DeadStoreElimination/2008-07-28-load-store.ll
new file mode 100644
index 00000000000..0ba8479a2c5
--- /dev/null
+++ b/test/Transforms/DeadStoreElimination/2008-07-28-load-store.ll
@@ -0,0 +1,14 @@
+; RUN: llvm-as < %s | opt -dse | llvm-dis | not grep tmp5
+; PR2599
+
+define void @foo({ i32, i32 }* %x) nounwind  {
+entry:
+	%tmp4 = getelementptr { i32, i32 }* %x, i32 0, i32 0		; <i32*> [#uses=2]
+	%tmp5 = load i32* %tmp4, align 4		; <i32> [#uses=1]
+	%tmp7 = getelementptr { i32, i32 }* %x, i32 0, i32 1		; <i32*> [#uses=2]
+	%tmp8 = load i32* %tmp7, align 4		; <i32> [#uses=1]
+	%tmp17 = sub i32 0, %tmp8		; <i32> [#uses=1]
+	store i32 %tmp5, i32* %tmp4, align 4
+	store i32 %tmp17, i32* %tmp7, align 4
+	ret void
+}
-- 
2.34.1