Index: lib/Transforms/Scalar/MemCpyOptimizer.cpp
===================================================================
--- lib/Transforms/Scalar/MemCpyOptimizer.cpp
+++ lib/Transforms/Scalar/MemCpyOptimizer.cpp
@@ -710,19 +710,31 @@
         bool CpyDestIsLocal = isa<AllocaInst>(CpyDest);
         AliasAnalysis &AA = LookupAliasAnalysis();
         MemoryLocation StoreLoc = MemoryLocation::get(SI);
-        for (BasicBlock::iterator I = --SI->getIterator(), E = C->getIterator();
-             I != E; --I) {
-          if (isModOrRefSet(AA.getModRefInfo(&*I, StoreLoc))) {
-            C = nullptr;
-            break;
-          }
-          // The store to dest may never happen if an exception can be thrown
-          // between the load and the store.
-          if (I->mayThrow() && !CpyDestIsLocal) {
-            C = nullptr;
-            break;
+        BasicBlock::iterator BBBegin = SI->getParent()->begin();
+        if (SI->getIterator() == BBBegin)
+          // SI is first in BB, so we can't search backwards to find C unless we
+          // examine the predecessors. Simply bail out.
+          C = nullptr;
+        else
+          for (BasicBlock::iterator I = --SI->getIterator(),
+                                    E = C->getIterator();
+               I != E; --I) {
+            if (I == BBBegin) {
+              // We reached the beginning of the BB without finding C.
+              C = nullptr;
+              break;
+            }
+            if (isModOrRefSet(AA.getModRefInfo(&*I, StoreLoc))) {
+              C = nullptr;
+              break;
+            }
+            // The store to dest may never happen if an exception can be thrown
+            // between the load and the store.
+            if (I->mayThrow() && !CpyDestIsLocal) {
+              C = nullptr;
+              break;
+            }
           }
-        }
       }
 
       if (C) {
Index: test/Transforms/MemCpyOpt/process_store.ll
===================================================================
--- /dev/null
+++ test/Transforms/MemCpyOpt/process_store.ll
@@ -0,0 +1,39 @@
+; RUN: opt < %s -memcpyopt -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@b = common dso_local local_unnamed_addr global i32 0, align 4
+@a = common dso_local local_unnamed_addr global i32 0, align 4
+
+declare dso_local i32 @f1()
+
+; Do not crash due to store first in BB.
+define dso_local void @f2() {
+for.end:
+  %0 = load i32, i32* @b, align 4
+  ret void
+
+for.body:
+  store i32 %1, i32* @a, align 4
+  %call = call i32 @f1()
+  %cmp = icmp sge i32 %call, 0
+  %1 = load i32, i32* @b, align 4
+  br label %for.body
+}
+
+; Do not crash due to call not before store in BB.
+define dso_local void @f3() {
+for.end:
+  %0 = load i32, i32* @b, align 4
+  ret void
+
+for.body:
+  %t = add i32 %t2, 1
+  store i32 %1, i32* @a, align 4
+  %call = call i32 @f1()
+  %cmp = icmp sge i32 %call, 0
+  %1 = load i32, i32* @b, align 4
+  %t2 = xor i32 %t, 5
+  br label %for.body
+}