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
@@ -770,6 +770,10 @@
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;
+  // Check if there are root nodes that are terminated by UnreachableInst.
+  // Those roots pessimize post-dominance queries. If there are such roots,
+  // fall back to CFG scan starting from all non-unreachable roots.
+  bool AnyUnreachableExit;
 
   // Class contains self-reference, make sure it's not copied/moved.
   DSEState(const DSEState &) = delete;
@@ -805,6 +809,10 @@
 
     // Collect whether there is any irreducible control flow in the function.
     ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);
+
+    AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) {
+      return isa<UnreachableInst>(E->getTerminator());
+    });
   }
 
   /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
@@ -1511,22 +1519,29 @@
       // If the common post-dominator does not post-dominate MaybeDeadAccess,
       // there is a path from MaybeDeadAccess to an exit not going through a
       // killing block.
-      if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock()))
-        return None;
+      if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
+        if (!AnyUnreachableExit)
+          return None;
+
+        // Fall back to CFG scan starting at all non-unreachable roots if not
+        // all paths to the exit go through CommonPred.
+        CommonPred = nullptr;
+      }
 
       // If CommonPred itself is in the set of killing blocks, we're done.
       if (KillingBlocks.count(CommonPred))
         return {MaybeDeadAccess};
 
       SetVector<BasicBlock *> WorkList;
-
       // If CommonPred is null, there are multiple exits from the function.
       // They all have to be added to the worklist.
       if (CommonPred)
         WorkList.insert(CommonPred);
       else
-        for (BasicBlock *R : PDT.roots())
-          WorkList.insert(R);
+        for (BasicBlock *R : PDT.roots()) {
+          if (!isa<UnreachableInst>(R->getTerminator()))
+            WorkList.insert(R);
+        }
 
       NumCFGTries++;
       // Check if all paths starting from an exit node go through one of the
diff --git a/llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll b/llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll
--- a/llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll
@@ -63,12 +63,11 @@
 define void @unreachable_exit_with_no_call(i64* noalias %ptr, i1 %c.1) {
 ; CHECK-LABEL: @unreachable_exit_with_no_call(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i64 1, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store i64 0, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
@@ -87,13 +86,12 @@
 define void @unreachable_exit_with_nounwind_call_pr53800(i64* noalias %ptr, i1 %c.1) {
 ; CHECK-LABEL: @unreachable_exit_with_nounwind_call_pr53800(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i64 1, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @exit() #[[ATTR0:[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store i64 0, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry: