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
@@ -1833,8 +1833,48 @@
 
   // Get the defining access for the load.
   auto *LoadAccess = MSSA.getMemoryAccess(Load)->getDefiningAccess();
-  // The store is dead if the defining accesses are the same.
-  return LoadAccess == KillingDef->getDefiningAccess();
+  // Fast path: the defining accesses are the same.
+  bool IsDead = LoadAccess == KillingDef->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 = KillingDef->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(KillingDef);
+  ToCheck.insert(Current);
+  // Start at current (1) to simulate already having checked KillingDef.
+  for (unsigned I = 1; I < ToCheck.size(); ++I) {
+    Current = ToCheck[I];
+    if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
+      // Check all the operands.
+      for (unsigned PhiIndex = 0; PhiIndex < PhiAccess->getNumOperands();
+           ++PhiIndex)
+        ToCheck.insert(PhiAccess->getOperand(PhiIndex));
+      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)) {
+      // 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;
+      if (!IsDead)
+        break;
+      // If the store is not dead, we need to keep checking.
+      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;
 }
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
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,26 @@
   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
+}
+
 declare void @unknown_func()
 
 ; Remove redundant store, which is in the lame loop as the load.
@@ -167,5 +187,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
@@ -116,26 +116,6 @@
 
 declare void @unknown_func()
 
-; 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
-}
-
 define void @test43a(i32* %P, i32* noalias %Q) {
 ; CHECK-LABEL: @test43a(
 ; CHECK-NEXT:  entry:
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll
@@ -290,7 +290,6 @@
 define i32 @test29(i1 %c, i32* %p, i32* %p2, i32 %i) {
 ; CHECK-LABEL: @test29(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
@@ -298,7 +297,6 @@
 ; CHECK-NEXT:    store i32 [[I:%.*]], i32* [[P2:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
@@ -321,7 +319,6 @@
 define i32 @test30(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test30(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
@@ -329,7 +326,6 @@
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
@@ -350,10 +346,8 @@
 define i32 @test32(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test32(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2: