Index: lib/Transforms/Scalar/DeadStoreElimination.cpp
===================================================================
--- lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -724,15 +724,36 @@
 
   const DataLayout &DL = BB.getModule()->getDataLayout();
 
+  bool removeLifetimeEnds = true;
+
   // Scan the basic block backwards
   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
     --BBI;
 
-    // If we find a store, check to see if it points into a dead stack value.
-    if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) {
+    Value *V = nullptr;
+    // In terminating blocks, we can remove lifetime intrinsics for dead
+    // objects until we hit the first lifetime start for a live object. From
+    // then on, lifetimes are interesting for stack coloring and must be kept
+    bool isLifetimeStart = false;
+    if (removeLifetimeEnds)
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
+        switch (II->getIntrinsicID()) {
+          default: break;
+          case Intrinsic::lifetime_start:
+            isLifetimeStart = true;
+          case Intrinsic::lifetime_end:
+            V = II->getArgOperand(1);
+            break;
+        }
+
+    if (!V && hasMemoryWrite(BBI, TLI) && isRemovable(BBI))
+      V = getStoredPointerOperand(BBI);
+
+    // If we found a store, check to see if it points into a dead stack value.
+    if (V) {
       // See through pointer-to-pointer bitcasts
       SmallVector<Value *, 4> Pointers;
-      GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers, DL);
+      GetUnderlyingObjects(V, Pointers, DL);
 
       // Stores to stack values are valid candidates for removal.
       bool AllDead = true;
@@ -761,6 +782,10 @@
         ++NumFastStores;
         MadeChange = true;
         continue;
+      } else if (isLifetimeStart) {
+        // We found a lifetime start that we can't remove, so lifetime ends
+        // that come before it are interesting again and must be kept
+        removeLifetimeEnds = false;
       }
     }
 
Index: test/Transforms/DeadStoreElimination/lifetime.ll
===================================================================
--- test/Transforms/DeadStoreElimination/lifetime.ll
+++ test/Transforms/DeadStoreElimination/lifetime.ll
@@ -2,9 +2,11 @@
 
 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"
 
+declare i32 @__gxx_personality_v0(...)
 declare void @llvm.lifetime.start(i64, i8* nocapture) nounwind
 declare void @llvm.lifetime.end(i64, i8* nocapture) nounwind
 declare void @llvm.memset.p0i8.i8(i8* nocapture, i8, i8, i32, i1) nounwind
+declare void @callee(i8*)
 
 define void @test1() {
 ; CHECK-LABEL: @test1(
@@ -12,7 +14,7 @@
 
   store i8 0, i8* %A  ;; Written to by memset
   call void @llvm.lifetime.end(i64 1, i8* %A)
-; CHECK: lifetime.end
+; CHECK-NOT: lifetime.end
 
   call void @llvm.memset.p0i8.i8(i8* %A, i8 0, i8 -1, i32 0, i1 false)
 ; CHECK-NOT: memset
@@ -22,7 +24,7 @@
 }
 
 define void @test2(i32* %P) {
-; CHECK: test2
+; CHECK-LABEL: test2
   %Q = getelementptr i32, i32* %P, i32 1
   %R = bitcast i32* %Q to i8*
   call void @llvm.lifetime.start(i64 4, i8* %R)
@@ -34,4 +36,61 @@
   ret void
 }
 
+define void @test3() personality i32 (...)* @__gxx_personality_v0 {
+; CHECK-LABEL: test3
+  %a = alloca i8
+  invoke void @callee(i8* undef)
+    to label %normal unwind label %unwind
+
+normal:
+; CHECK-LABEL: normal
+  call void @llvm.lifetime.start(i64 1, i8* %a)
+; CHECK-NOT: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %a)
+; CHECK-NOT: lifetime.end
+  ret void
+
+unwind:
+; CHECK-LABEL: unwind
+  %exn = landingpad {i8*, i32} catch i8* null
+  call void @llvm.lifetime.start(i64 1, i8* %a)
+; CHECK-NOT: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %a)
+; CHECK-NOT: lifetime.end
+  resume { i8*, i32 } %exn
+}
 
+define void @test4(i8*) {
+; CHECK-LABEL: test4
+  %a = alloca i8
+  call void @llvm.lifetime.start(i64 1, i8* %a)
+; CHECK: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %a)
+; CHECK: lifetime.end
+  call void @llvm.lifetime.start(i64 1, i8* %0)
+; CHECK: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %0)
+; CHECK: lifetime.end
+  call void @llvm.lifetime.start(i64 1, i8* %a)
+; CHECK-NOT: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %a)
+; CHECK-NOT: lifetime.end
+  ret void
+}
+
+define void @test5() {
+; CHECK-LABEL: test5
+  %a = alloca i8
+  %b = alloca i8
+  call void @llvm.lifetime.start(i64 1, i8* %a)
+; CHECK: lifetime.start
+  call void @llvm.lifetime.end(i64 1, i8* %a)
+; CHECK: lifetime.end
+  call void @llvm.lifetime.start(i64 1, i8* %b)
+; CHECK: lifetime.start
+  call void @callee(i8* %b)
+; CHECK: call void @callee
+  call void @llvm.lifetime.end(i64 1, i8* %b)
+; CHECK-NOT: lifetime.end
+  ret void
+}