Index: lib/Transforms/Scalar/DeadStoreElimination.cpp
===================================================================
--- lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -750,11 +750,15 @@
                                 const TargetLibraryInfo *TLI) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
+  bool MayThrow = false;
 
   // Do a top-down walk on the BB.
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
     Instruction *Inst = &*BBI++;
 
+    if (Inst->mayThrow())
+      MayThrow = true;
+
     // Handle 'free' calls specially.
     if (CallInst *F = isFreeCall(Inst, TLI)) {
       MadeChange |= handleFree(F, AA, MD, DT, TLI);
@@ -845,6 +849,27 @@
       if (!DepLoc.Ptr)
         break;
 
+      // Make sure we don't look past a call which might throw. This is an
+      // issue because MemoryDependenceAnalysis works in the wrong direction:
+      // it finds instructions which dominate the current instruction, rather than
+      // instructions which are post-dominated by the current instruction.
+      //
+      // If the underlying object is a non-escaping memory allocation, any store
+      // to it is dead along the unwind edge. Otherwise, we need to preserve
+      // the store.
+      // FIXME: Check whether a throwing call is actually between the stores, instead
+      // of just in the same block.  Maybe using OrderedBasicBlock?
+      if (MayThrow) {
+        const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
+        bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
+        if (!IsStoreDeadOnUnwind) {
+          IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
+              !PointerMayBeCapturedBefore(Underlying, true, true, Inst, DT, false);
+        }
+        if (!IsStoreDeadOnUnwind)
+          break;
+      }
+
       // If we find a write that is a) removable (i.e., non-volatile), b) is
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.
Index: test/Transforms/DeadStoreElimination/simple.ll
===================================================================
--- test/Transforms/DeadStoreElimination/simple.ll
+++ test/Transforms/DeadStoreElimination/simple.ll
@@ -498,3 +498,14 @@
   ret i32 0
 }
 
+; Don't remove redundant store: unknown_func could unwind
+; CHECK-LABEL: @test34(
+; CHECK: store i32 1
+; CHECK: store i32 0
+; CHECK: ret
+define void @test34(i32* noalias %p) {
+  store i32 1, i32* %p
+  call void @unknown_func()
+  store i32 0, i32* %p
+  ret void
+}