diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1724,6 +1724,10 @@
   // Other results are not possible.
   if (Alias == MayAlias)
     return MayAlias;
+  // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
+  // remain valid to all elements and needs to conservatively return MayAlias.
+  if (isRecursive && Alias != NoAlias)
+    return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
diff --git a/llvm/test/Analysis/BasicAA/recphi.ll b/llvm/test/Analysis/BasicAA/recphi.ll
--- a/llvm/test/Analysis/BasicAA/recphi.ll
+++ b/llvm/test/Analysis/BasicAA/recphi.ll
@@ -3,9 +3,9 @@
 ; CHECK-LABEL: Function: simple: 5 pointers, 0 call sites
 ; CHECK:         NoAlias:      float* %src1, float* %src2
 ; CHECK:         NoAlias:      float* %phi, float* %src1
-; CHECK:         MustAlias:    float* %phi, float* %src2
+; CHECK:         MayAlias:     float* %phi, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %src1
-; CHECK:         NoAlias:      float* %next, float* %src2
+; CHECK:         MayAlias:     float* %next, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %phi
 ; CHECK:         NoAlias:      float* %g, float* %src1
 ; CHECK:         NoAlias:      float* %g, float* %src2
@@ -38,13 +38,13 @@
 ; CHECK:        MustAlias:    [2 x i32]* %tab, i32* %arrayidx1
 ; CHECK:        MustAlias:    i32* %arrayidx1, i8* %0
 ; CHECK:        NoAlias:      i32* %arrayidx, i32* %arrayidx1
-; CHECK:        MustAlias:    [2 x i32]* %tab, i32* %p.addr.05.i
-; CHECK:        MustAlias:    i32* %p.addr.05.i, i8* %0
-; CHECK:        NoAlias:      i32* %arrayidx, i32* %p.addr.05.i
-; CHECK:        MustAlias:    i32* %arrayidx1, i32* %p.addr.05.i
-; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %incdec.ptr.i
+; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %p.addr.05.i
+; CHECK:        MayAlias:     i32* %p.addr.05.i, i8* %0
+; CHECK:        MayAlias:     i32* %arrayidx, i32* %p.addr.05.i
+; CHECK:        MayAlias:     i32* %arrayidx1, i32* %p.addr.05.i
+; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i8* %0
-; CHECK:        MustAlias:    i32* %arrayidx, i32* %incdec.ptr.i
+; CHECK:        MayAlias:     i32* %arrayidx, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %arrayidx1, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i32* %p.addr.05.i
 define i32 @notmust() nounwind {