diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -2398,10 +2398,49 @@
 
     if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
       if (LoadI->getPointerOperand() == Store->getOperand(1)) {
+        // Get the defining access for the load.
         auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
-        // If both accesses share the same defining access, no instructions
-        // between them can modify the memory location.
-        return LoadAccess == Def->getDefiningAccess();
+        // Fast path: the defining accesses are the same.
+        bool IsDead = LoadAccess == Def->getDefiningAccess();
+        if (IsDead)
+          return true;
+
+        // Look through phi accesses. Recursively scan all phi accesses by adding them
+        // to a worklist. Bail when we run into a memory def.
+        SetVector<MemoryAccess *> ToCheck;
+        MemoryAccess *Current = Def->getDefiningAccess();
+        // We don't want to bail when we run into the store memory def. But, the phi
+        // access may point to it. So, pretend like we've already checked it.
+        ToCheck.insert(Def);
+        ToCheck.insert(Current);
+        // Start at current (1) to simulate already having checked Def.
+        for (unsigned I = 1; I < ToCheck.size(); ++I) {
+          Current = ToCheck[I];
+          if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
+            // Check all the operands.
+            for (auto *V : PhiAccess->incoming_values())
+              ToCheck.insert(V);
+            continue;
+          }
+
+          // If we found a memory def, bail. This happens when we have an unrelated
+          // write in between an otherwise noop store.
+          if (isa<MemoryDef>(Current)) {
+            // TODO: Skip no alias MemoryDefs that have no aliasing reads.
+            // We are searching for the definition of the store's destination. So, if
+            // that is the same definition as the load, then this is a noop.
+            IsDead = LoadAccess == Current;
+            // Either way, we need to keep checking to make sure there aren't
+            // any other MemoryDefs.
+            continue;
+          }
+
+          // The store is also a noop if the defining access of a use of the store's
+          // memory is the same as the load's defining access.
+          if (cast<MemoryUse>(Current)->getDefiningAccess() == LoadAccess)
+            IsDead = true;
+        }
+        return IsDead;
       }
     }
 
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll
@@ -101,6 +101,47 @@
   ret i32 0
 }
 
+; Remove redundant store if loaded value is in another block inside a loop.
+define i32 @test31(i1 %c, i32* %p, i32 %i) {
+; CHECK-LABEL: @test31(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  ret i32 0
+}
+
+; Don't remove "redundant" store if %p is possibly stored to.
+define i32 @test46(i1 %c, i32* %p, i32* %p2, i32 %i) {
+; CHECK-LABEL: @test46(
+; CHECK:  load
+; CHECK:  store
+; CHECK:  store
+; CHECK:  ret i32 0
+;
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  store i32 0, i32* %p2, align 4
+  br i1 undef, label %bb3, label %bb1
+bb3:
+  ret i32 0
+}
+
 declare void @unknown_func()
 
 ; Remove redundant store, which is in the lame loop as the load.
@@ -167,5 +208,3 @@
   store i32 %a, i32* %Q
   ret void
 }
-
-
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll
@@ -4,14 +4,16 @@
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
-; Remove redundant store if loaded value is in another block inside a loop.
-define i32 @test31(i1 %c, i32* %p, i32 %i) {
-; CHECK-LABEL: @test31(
+; Remove both redundant stores if loaded value is in another block inside a loop.
+define i32 @test47(i1 %c, i32* %p, i32 %i) {
+; CHECK-LABEL: @test47(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    br i1 undef, label [[BB2]], label [[BB3:%.*]]
+; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
@@ -21,5 +23,8 @@
   store i32 %v, i32* %p, align 4
   br i1 undef, label %bb1, label %bb2
 bb2:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb3, label %bb1
+bb3:
   ret i32 0
 }