Index: lib/Transforms/Scalar/DeadStoreElimination.cpp
===================================================================
--- lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -493,37 +493,54 @@
 
     MemDepResult InstDep = MD->getDependency(Inst);
 
-    // Ignore any store where we can't find a local dependence.
-    // FIXME: cross-block DSE would be fun. :)
-    if (!InstDep.isDef() && !InstDep.isClobber())
-      continue;
-
     // If we're storing the same value back to a pointer that we just
     // loaded from, then the store can be removed.
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
-      if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
+      if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
-            SI->getOperand(0) == DepLoad && isRemovable(SI)) {
-          DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
-                       << "LOAD: " << *DepLoad << "\n  STORE: " << *SI << '\n');
+            isRemovable(SI)) {
 
-          // DeleteDeadInstruction can delete the current instruction.  Save BBI
-          // in case we need it.
-          WeakVH NextInst(BBI);
+          Instruction *DepInst = InstDep.getInst();
+          if (!DepInst) {
+            // No dependency in the same block. Next try: see if we can get one
+            // in another block.
+            SmallVector<NonLocalDepResult, 8> Deps;
+            MD->getNonLocalPointerDependency(SI, Deps);
+            
+            // For simplicity we just just accept a sinlge dependency.
+            if (Deps.size() == 1) {
+              DepInst = Deps[0].getResult().getInst();
+            }
+          }
+          // Check if the single dependency is exactly the load instruction.
+          if (DepInst == DepLoad) {
+            DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n  "
+                         << "LOAD: " << *DepLoad << "\n  STORE: " << *SI
+                         << '\n');
 
-          DeleteDeadInstruction(SI, *MD, TLI);
+            // DeleteDeadInstruction can delete the current instruction. Save
+            // BBI in case we need it.
+            WeakVH NextInst(BBI);
 
-          if (!NextInst)  // Next instruction deleted.
-            BBI = BB.begin();
-          else if (BBI != BB.begin())  // Revisit this instruction if possible.
-            --BBI;
-          ++NumFastStores;
-          MadeChange = true;
-          continue;
+            DeleteDeadInstruction(SI, *MD, TLI);
+
+            if (!NextInst)  // Next instruction deleted.
+              BBI = BB.begin();
+            else if (BBI != BB.begin())  // Revisit this instruction if possible.
+              --BBI;
+            ++NumFastStores;
+            MadeChange = true;
+            continue;
+          }
         }
       }
     }
 
+    // Ignore any store where we can't find a local dependence.
+    // FIXME: cross-block DSE would be fun. :)
+    if (!InstDep.isDef() && !InstDep.isClobber())
+      continue;
+
     // Figure out what location is being stored to.
     MemoryLocation Loc = getLocForWrite(Inst, *AA);
 
Index: test/Transforms/DeadStoreElimination/simple.ll
===================================================================
--- test/Transforms/DeadStoreElimination/simple.ll
+++ test/Transforms/DeadStoreElimination/simple.ll
@@ -350,3 +350,77 @@
   store i8 %tmp, i8* %p.4, align 1
   ret i8* %q
 }
+
+; Remove redudant store if loaded value is in another block.
+; CHECK-LABEL: @test26(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test26(i1, i32*) {
+entry:
+  %l2 = load i32, i32* %1, align 4
+  br i1 %0, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 %l2, i32* %1, align 4
+  br label %bb3
+bb3:
+  ret i32 0
+}
+
+; Remove redudant store if loaded value is in another block.
+; CHECK-LABEL: @test27(
+; CHECK-NOT: store
+; CHECK: ret
+define i32 @test27(i1, i32*) {
+entry:
+  %l2 = load i32, i32* %1, align 4
+  br i1 %0, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 %l2, i32* %1, align 4
+  ret i32 0
+}
+
+; Don't remove redudant store because of may-aliased store.
+; CHECK-LABEL: @test28(
+; CHECK: bb3:
+; CHECK-NEXT: store i32 %l2
+define i32 @test28(i1, i32*, i32*, i32) {
+entry:
+  %l2 = load i32, i32* %1, align 4
+
+  ; Might overwrite value at %1
+  store i32 %3, i32* %2, align 4
+  br i1 %0, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  br label %bb3
+bb3:
+  store i32 %l2, i32* %1, align 4
+  ret i32 0
+}
+
+; Don't remove redudant store because of may-aliased store.
+; CHECK-LABEL: @test29(
+; CHECK: bb3:
+; CHECK-NEXT: store i32 %l2
+define i32 @test29(i1, i32*, i32*, i32) {
+entry:
+  %l2 = load i32, i32* %1, align 4
+  br i1 %0, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  ; Might overwrite value at %1
+  store i32 %3, i32* %2, align 4
+  br label %bb3
+bb3:
+  store i32 %l2, i32* %1, align 4
+  ret i32 0
+}
+