Index: llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
+++ llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
@@ -869,8 +869,13 @@
     return false;
   }
 
-  assert(TheLoop->getHeader() == Phi->getParent() &&
-         "PHI is an AddRec for a different loop?!");
+  if (AR->getLoop() != TheLoop) {
+    // FIXME: We should treat this as a uniform. Unfortunately, we
+    // don't currently know how to handled uniform PHIs.
+    DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
+    return false;    
+  }
+
   Value *StartValue =
     Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
   const SCEV *Step = AR->getStepRecurrence(*SE);
Index: llvm/trunk/test/Transforms/LoopVectorize/pr31190.ll
===================================================================
--- llvm/trunk/test/Transforms/LoopVectorize/pr31190.ll
+++ llvm/trunk/test/Transforms/LoopVectorize/pr31190.ll
@@ -0,0 +1,64 @@
+; RUN: opt -passes='loop-vectorize' -debug -S < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+; This checks we don't crash when the inner loop we're trying to vectorize
+; is a SCEV AddRec with respect to an outer loop.
+
+; In this case, the problematic PHI is:
+; %0 = phi i32 [ undef, %for.cond1.preheader ], [ %inc54, %for.body3 ]
+; Since %inc54 is the IV of the outer loop, and %0 equivalent to it,
+; we get the situation described above.
+
+; This test uses the new PM, because with the old PM, running loop-vectorize
+; would explicitly run loop-simplify. Even though this loop is already in
+; simplified form, loop-simplify would still clean up the phi.
+; The reason this matters is that in a real optimizer pipeline, LICM can create
+; such PHIs, and since it preserves loop simplified form, the cleanup has
+; no chance to run.
+
+; Code that leads to this situation can look something like:
+;
+; int a, b[1], c;
+; void fn1 ()
+; {
+;  for (; c; c++)
+;    for (a = 0; a; a++)
+;      b[c] = 4;
+; }
+;
+; The PHI is an artifact of the register promotion of c.
+
+@c = external global i32, align 4
+@a = external global i32, align 4
+@b = external global [1 x i32], align 4
+
+; CHECK: LV: PHI is a recurrence with respect to an outer loop.
+; CHECK: LV: Not vectorizing: Cannot prove legality.
+; CHECK-LABEL: @test
+define void @test() {
+entry:
+  %a.promoted2 = load i32, i32* @a, align 1
+  %c.promoted = load i32, i32* @c, align 1
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond1.for.inc4_crit_edge, %entry
+  %inc54 = phi i32 [ %inc5, %for.cond1.for.inc4_crit_edge ], [ %c.promoted, %entry ]
+  %inc.lcssa3 = phi i32 [ %inc.lcssa, %for.cond1.for.inc4_crit_edge ], [ %a.promoted2, %entry ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.cond1.preheader
+  %inc1 = phi i32 [ %inc.lcssa3, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %0 = phi i32 [ undef, %for.cond1.preheader ], [ %inc54, %for.body3 ]
+  %idxprom = sext i32 %0 to i64
+  %arrayidx = getelementptr inbounds [1 x i32], [1 x i32]* @b, i64 0, i64 %idxprom
+  store i32 4, i32* %arrayidx, align 4
+  %inc = add nsw i32 %inc1, 1
+  %tobool2 = icmp eq i32 %inc, 0
+  br i1 %tobool2, label %for.cond1.for.inc4_crit_edge, label %for.body3
+
+for.cond1.for.inc4_crit_edge:                     ; preds = %for.body3
+  %inc.lcssa = phi i32 [ %inc, %for.body3 ]
+  %.lcssa = phi i32 [ %inc54, %for.body3 ]
+  %inc5 = add nsw i32 %.lcssa, 1
+  br label %for.cond1.preheader
+}