Index: lib/Analysis/MemoryDependenceAnalysis.cpp
===================================================================
--- lib/Analysis/MemoryDependenceAnalysis.cpp
+++ lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -196,14 +196,17 @@
 
   // Walk backwards through the block, looking for dependencies.
   while (ScanIt != BB->begin()) {
+    Instruction *Inst = &*--ScanIt;
+    // Debug intrinsics don't cause dependences and should not affect Limit
+    if (isa<DbgInfoIntrinsic>(Inst))
+      continue;
+
     // Limit the amount of scanning we do so we don't end up with quadratic
     // running time on extreme testcases.
     --Limit;
     if (!Limit)
       return MemDepResult::getUnknown();
 
-    Instruction *Inst = &*--ScanIt;
-
     // If this inst is a memory op, get the pointer it accessed
     MemoryLocation Loc;
     ModRefInfo MR = GetLocation(Inst, Loc, TLI);
@@ -215,9 +218,6 @@
     }
 
     if (auto InstCS = CallSite(Inst)) {
-      // Debug intrinsics don't cause dependences.
-      if (isa<DbgInfoIntrinsic>(Inst))
-        continue;
       // If these two calls do not interfere, look past it.
       switch (AA.getModRefInfo(CS, InstCS)) {
       case MRI_NoModRef:
Index: test/Transforms/DeadStoreElimination/mda-with-dbg-values.ll
===================================================================
--- /dev/null
+++ test/Transforms/DeadStoreElimination/mda-with-dbg-values.ll
@@ -0,0 +1,50 @@
+; RUN: opt -S -dse -memdep-block-scan-limit=3 < %s | FileCheck %s
+; RUN: opt -S -strip-debug -dse -memdep-block-scan-limit=3 < %s | FileCheck %s
+
+; Test case to check that the memory dependency analysis gets the same
+; result even if we have a dbg value between the memcpy and
+; store. The memory dependency is then used by DSE to remove the store.
+
+; We use -memdep-block-scan-limit=3 to be able to create a small test case.
+; Without it, we would need to squeexe in 100 instructions since the default
+; limit is 100.
+
+
+@g = external global [1 x i8]
+
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i32, i1)
+
+define void @fn1() {
+  %1 = alloca i8
+  store i8 1, i8* %1
+  tail call void @llvm.dbg.value(metadata i32 0, i64 0, metadata !6, metadata !8), !dbg !7
+  %2 = bitcast [1 x i8]* @g to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %1, i8* %2, i32 1, i32 0, i1 false)
+  br label %bb2
+
+bb2:                                              ; preds = %0
+  ret void
+}
+
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3}
+!llvm.ident = !{!4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "My Compiler")
+!1 = !DIFile(filename: "foo.c", directory: "/bar")
+
+!2 = !{i32 2, !"Dwarf Version", i32 4}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{!"My Compiler"}
+!5 = distinct !DISubprogram(unit: !0)
+!6 = !DILocalVariable(scope: !5)
+!7 = !DILocation(scope: !5)
+!8 = !DIExpression(DW_OP_LLVM_fragment, 0, 8)
+
+; Check that the store is removed and that the memcpy is still there
+; CHECK-LABEL: fn1
+; CHECK-NOT:   store i8
+; CHECK:       call void @llvm.memcpy
+; CHECK:       ret void