Index: llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp
===================================================================
--- llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -423,7 +423,9 @@
   }
 
   // Walk backwards through the basic block, looking for dependencies.
-  while (ScanIt != BB->begin()) {
+  // We can stop before processing PHIs or dbg intrinsics.
+  const BasicBlock::iterator Begin(BB->getFirstNonPHIOrDbg());
+  while (ScanIt != Begin) {
     Instruction *Inst = --ScanIt;
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))