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
@@ -40,6 +40,7 @@
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
@@ -73,6 +74,7 @@
 #include <utility>
 
 using namespace llvm;
+using namespace PatternMatch;
 
 #define DEBUG_TYPE "dse"
 
@@ -1395,6 +1397,7 @@
 // by those below).
 
 /// Container for state required for MemorySSA-driven DSE and related functions.
+
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
@@ -1426,6 +1429,8 @@
   // All MemoryDef stores
   SmallVector<MemoryDef *, 4> Stores;
 
+  SmallVector<Instruction *, 16> MemTerminators;
+
   void init() {
     // Any that should be skipped as they are already deleted
     unsigned PO = 0;
@@ -1442,6 +1447,9 @@
 
         BlockMap[&I] = ThrowingCnt;
 
+        if (isMemTerminatorInst(&I))
+          MemTerminators.push_back(&I);
+
         auto *MD = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(&I));
         if (MD && hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
           Stores.push_back(MD);
@@ -1555,7 +1563,7 @@
     }
   }
 
-  enum class WalkType { Bad, Next };
+  enum class WalkType { Bad, Next, Terminated };
   struct WalkResult {
     WalkType Type;
     MemoryDef *Next;
@@ -1588,6 +1596,41 @@
     return MemoryLocation::getOrNone(I);
   }
 
+Optional<MemoryLocation> getLocForTerminator(Instruction *I) {
+  uint64_t Len;
+  Value *Ptr;
+  if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
+                                                    m_Value(Ptr))))
+    return {MemoryLocation(Ptr, Len)};
+
+  if (auto CS = CallSite(I)) {
+    if (isFreeCall(I, &TLI))
+      return {MemoryLocation(CS.getArgument(0))};
+  }
+
+  return None;
+}
+
+  bool isMemTerminatorInst(Instruction *I) const {
+    IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
+    return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
+           isFreeCall(I, &TLI);
+  }
+
+  bool isMemTerminator(MemoryLocation DefLoc, Instruction *MaybeTerm) {
+    Optional<MemoryLocation> MaybeTermLoc = getLocForTerminator(MaybeTerm);
+
+    if (!MaybeTermLoc)
+      return false;
+
+    if (isFreeCall(MaybeTerm, &TLI)) {
+      DataLayout DL = MaybeTerm->getParent()->getModule()->getDataLayout();
+      DefLoc = MemoryLocation(GetUnderlyingObject(DefLoc.Ptr, DL));
+    }
+    return AA.isMustAlias(*MaybeTermLoc, DefLoc);
+  }
+
+
   // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
     if (!UseInst->mayReadFromMemory())
@@ -1680,6 +1723,13 @@
       if (isa<FenceInst>(UseInst))
         continue;
 
+      if (isMemTerminatorInst(UseInst)) {
+        if (NextAccess)
+          return {WalkType::Bad, nullptr};
+        NextAccess = UseAccess;
+        continue;
+      }
+
       // We cannot eliminate stores to locations visible to the caller across
       // throwing instructions. We can also eliminate stores across throwing
       // calls for alloc-like objects that do not escape before the current
@@ -1720,7 +1770,10 @@
     if (NextAccess) {
       if (auto *NextDef = dyn_cast<MemoryDef>(NextAccess)) {
         if (!isNoopIntrinsic(NextDef)) {
-          if (isWriteClobber(DefLoc, NextDef->getMemoryInst()))
+          if (isMemTerminatorInst(NextDef->getMemoryInst())) {
+            if (isMemTerminator(DefLoc, NextDef->getMemoryInst()))
+              return {WalkType::Terminated, NextDef};
+          } else if (isWriteClobber(DefLoc, NextDef->getMemoryInst()))
             return {WalkType::Next, NextDef};
         }
       }
@@ -1732,6 +1785,61 @@
     // No aliasing definition found, we reached the end of the walk.
     return {WalkType::Bad, nullptr};
   }
+
+  /// For all memory terminators in \p MemTerminators, traverse the users and
+  /// try to eliminate stores to terminated objects, until we reach the end of
+  /// the function or a lifetime.start.
+  bool eliminateStoresAfterTerminators() {
+    SmallPtrSet<MemoryDef *, 1> SkipStores;
+    InstOverlapIntervalsTy IOL;
+    bool Changed = false;
+
+    for (Instruction *Terminator : MemTerminators) {
+      SmallVector<MemoryAccess *, 8> WorkList;
+      auto *T = MSSA.getMemoryAccess(Terminator);
+
+      auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
+        for (Use &U : Acc->uses())
+          WorkList.push_back(cast<MemoryAccess>(U.getUser()));
+      };
+      PushMemUses(T);
+
+      MemoryLocation TermLoc = *getLocForTerminator(Terminator);
+      while (!WorkList.empty()) {
+        MemoryAccess *C = WorkList.back();
+        WorkList.pop_back();
+        if (isa<MemoryUse>(C))
+          continue;
+        if (isa<MemoryPhi>(C))
+          break;
+
+        Instruction *CInst = cast<MemoryDef>(C)->getMemoryInst();
+        Optional<MemoryLocation> MaybeCLoc = getLocForWriteEx(CInst);
+        if (!MaybeCLoc)
+          break;
+        if (AA.isNoAlias(*MaybeCLoc, TermLoc)) {
+          PushMemUses(C);
+          continue;
+        }
+
+        if (match(CInst, m_Intrinsic<Intrinsic::lifetime_start>()))
+          break;
+
+        if (AA.isMustAlias(*MaybeCLoc, TermLoc) &&
+            PDT.dominates(Terminator->getParent(), CInst->getParent())) {
+          Changed = true;
+          LLVM_DEBUG(dbgs() << "DSE: Store " << *CInst
+                            << " is dead because it is after terminator: "
+                            << *Terminator << "\n");
+          deleteDeadInstruction(CInst);
+          ++NumFastStores;
+        }
+
+        PushMemUses(C);
+      }
+    }
+    return Changed;
+  }
 };
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
@@ -1763,6 +1871,25 @@
     DSEState::WalkResult Next;
     while ((Next = State.getNextMemoryDef(
                 SIMD, SILoc, DefObj, LocVisibleToCaller, MemorySSAScanLimit))) {
+
+      if (Next.Type == DSEState::WalkType::Terminated) {
+        Instruction *TermI = cast<MemoryUseOrDef>(Next.Next)->getMemoryInst();
+        if (State.mayThrowBetween(SI, TermI, SILocUnd))
+          break;
+
+        if (!DebugCounter::shouldExecute(MemorySSACounter))
+          break;
+
+        MadeChange = true;
+        State.SkipStores.insert(SIMD);
+        LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *SI
+                          << "\n  KILLER: " << *TermI << '\n');
+
+        State.deleteDeadInstruction(SIMD->getMemoryInst());
+        ++NumFastStores;
+        break;
+      }
+
       MemoryAccess *NextAccess = Next.Next;
       LLVM_DEBUG(dbgs() << " Checking " << *NextAccess << "\n");
       MemoryDef *ND = dyn_cast<MemoryDef>(NextAccess);
@@ -1814,6 +1941,7 @@
     }
   }
 
+  MadeChange |= State.eliminateStoresAfterTerminators();
   return MadeChange;
 }
 } // end anonymous namespace
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/2016-07-17-UseAfterFree.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/2016-07-17-UseAfterFree.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/2016-07-17-UseAfterFree.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/2016-07-17-UseAfterFree.ll
@@ -1,5 +1,4 @@
-; XFAIL: *
-; RUN: opt < %s -basicaa -dse-enable-dse-memoryssa  -S -enable-dse-partial-overwrite-tracking | FileCheck %s
+; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 ; PR28588
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/free.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/free.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/free.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/free.ll
@@ -1,4 +1,3 @@
-; XFAIL: *
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64"
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/lifetime.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/lifetime.ll
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/lifetime.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/lifetime.ll
@@ -1,4 +1,3 @@
-; XFAIL: *
 ; RUN: opt -S -basicaa -dse -enable-dse-memoryssa < %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"
@@ -30,9 +29,38 @@
 ; CHECK: lifetime.start
   store i32 0, i32* %Q  ;; This store is dead.
 ; CHECK-NOT: store
-  call void @llvm.lifetime.end.p0i8(i64 4, i8* %R)
+  call void @llvm.lifetime.end.p0i8(i64 8, i8* %R)
+; CHECK: lifetime.end
+  ret void
+}
+
+define void @test3(i32* %P) {
+; CHECK: test3
+  %Q = getelementptr i32, i32* %P, i32 1
+  %R = bitcast i32* %Q to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %R)
+; CHECK: lifetime.start
+  store i32 0, i32* %Q  ;; This store is dead.
+  %S = getelementptr i32, i32* %P, i32 1
+  %S.cast = bitcast i32* %S to i8*
+; CHECK-NOT: store
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %S.cast)
 ; CHECK: lifetime.end
   ret void
 }
 
 
+define void @test4(i32* noalias %P, i32* noalias %Q) {
+; CHECK-LABEL: @test4
+; CHECK-NOT: store
+; CHECK: call void @llvm.lifetime.end
+; CHECK-NEXT: store i32 3, i32* %Q
+;
+  store i32 1, i32* %Q  ;; This store is dead.
+  %P.cast = bitcast i32* %P to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %P.cast)
+  store i32 0, i32* %P  ;; This store is dead.
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %P.cast)
+  store i32 3, i32* %Q
+  ret void
+}
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
@@ -379,7 +379,6 @@
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    call void @unknown_func()
-; CHECK-NEXT:    store i32 2, i32* [[P]]
 ; CHECK-NEXT:    call void @free(i8* [[P2]])
 ; CHECK-NEXT:    ret void
 ;