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
@@ -1928,7 +1928,14 @@
       if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def) ||
           !isRemovable(Def->getMemoryInst()))
         continue;
-      auto *UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
+      MemoryDef *UpperDef;
+      // To conserve compile-time, we avoid walking to the next clobbering def.
+      // Instead, we just try to get the optimized access, if it exists. DSE
+      // will try to optimize defs during the earlier traversal.
+      if (Def->isOptimized())
+        UpperDef = dyn_cast<MemoryDef>(Def->getOptimized());
+      else
+        UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
       if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))
         continue;
 
diff --git a/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll b/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll
--- a/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll
@@ -1,5 +1,7 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -basic-aa -dse -S %s | FileCheck %s
+; RUN: opt -basic-aa -dse -dse-optimize-memoryssa=false -S %s | FileCheck --check-prefixes=CHECK,UNOPT %s
+; RUN: opt -basic-aa -dse -dse-optimize-memoryssa -S %s | FileCheck --check-prefixes=CHECK,OPT %s
+; RUN: opt -basic-aa -dse -S %s | FileCheck --check-prefixes=CHECK,UNOPT %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
@@ -315,17 +317,28 @@
 
 ; The store in bb3 can be eliminated, because the store in bb1 cannot alias it.
 define void @test10(i32* noalias %P, i32* %Q, i1 %c) {
-; CHECK-LABEL: @test10(
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    store i32 10, i32* [[Q:%.*]], align 4
-; CHECK-NEXT:    br label [[BB3:%.*]]
-; CHECK:       bb2:
-; CHECK-NEXT:    ret void
-; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
-; CHECK-NEXT:    ret void
+; UNOPT-LABEL: @test10(
+; UNOPT-NEXT:    store i32 0, i32* [[P:%.*]], align 4
+; UNOPT-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; UNOPT:       bb1:
+; UNOPT-NEXT:    store i32 10, i32* [[Q:%.*]], align 4
+; UNOPT-NEXT:    br label [[BB3:%.*]]
+; UNOPT:       bb2:
+; UNOPT-NEXT:    ret void
+; UNOPT:       bb3:
+; UNOPT-NEXT:    store i32 0, i32* [[P]], align 4
+; UNOPT-NEXT:    ret void
+;
+; OPT-LABEL: @test10(
+; OPT-NEXT:    store i32 0, i32* [[P:%.*]], align 4
+; OPT-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; OPT:       bb1:
+; OPT-NEXT:    store i32 10, i32* [[Q:%.*]], align 4
+; OPT-NEXT:    br label [[BB3:%.*]]
+; OPT:       bb2:
+; OPT-NEXT:    ret void
+; OPT:       bb3:
+; OPT-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 %c, label %bb1, label %bb2
@@ -412,13 +425,19 @@
 }
 
 define void @test12_memset_other_store_in_between(i8* %ptr) {
-; CHECK-LABEL: @test12_memset_other_store_in_between(
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[PTR:%.*]], i8 0, i64 10, i1 false)
-; CHECK-NEXT:    [[PTR_4:%.*]] = getelementptr i8, i8* [[PTR]], i64 4
-; CHECK-NEXT:    store i8 8, i8* [[PTR_4]], align 1
-; CHECK-NEXT:    [[PTR_5:%.*]] = getelementptr i8, i8* [[PTR]], i64 5
-; CHECK-NEXT:    store i8 0, i8* [[PTR_5]], align 1
-; CHECK-NEXT:    ret void
+; UNOPT-LABEL: @test12_memset_other_store_in_between(
+; UNOPT-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[PTR:%.*]], i8 0, i64 10, i1 false)
+; UNOPT-NEXT:    [[PTR_4:%.*]] = getelementptr i8, i8* [[PTR]], i64 4
+; UNOPT-NEXT:    store i8 8, i8* [[PTR_4]], align 1
+; UNOPT-NEXT:    [[PTR_5:%.*]] = getelementptr i8, i8* [[PTR]], i64 5
+; UNOPT-NEXT:    store i8 0, i8* [[PTR_5]], align 1
+; UNOPT-NEXT:    ret void
+;
+; OPT-LABEL: @test12_memset_other_store_in_between(
+; OPT-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[PTR:%.*]], i8 0, i64 10, i1 false)
+; OPT-NEXT:    [[PTR_4:%.*]] = getelementptr i8, i8* [[PTR]], i64 4
+; OPT-NEXT:    store i8 8, i8* [[PTR_4]], align 1
+; OPT-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* %ptr, i8 0, i64 10, i1 false)
   %ptr.4 = getelementptr i8, i8* %ptr, i64 4
@@ -525,8 +544,8 @@
 
 define void @test14_strcat(i8* noalias %P, i8* noalias %Q) {
 ; CHECK-LABEL: @test14_strcat(
-; CHECK-NEXT:    call i8* @strcat(i8* [[P:%.*]], i8* [[Q:%.*]])
-; CHECK-NEXT:    call i8* @strcat(i8* [[P]], i8* [[Q]])
+; CHECK-NEXT:    [[CALL1:%.*]] = call i8* @strcat(i8* [[P:%.*]], i8* [[Q:%.*]])
+; CHECK-NEXT:    [[CALL2:%.*]] = call i8* @strcat(i8* [[P]], i8* [[Q]])
 ; CHECK-NEXT:    ret void
 ;
   %call1 = call i8* @strcat(i8* %P, i8* %Q)