Index: lib/Analysis/BasicAliasAnalysis.cpp
===================================================================
--- lib/Analysis/BasicAliasAnalysis.cpp
+++ lib/Analysis/BasicAliasAnalysis.cpp
@@ -1508,16 +1508,19 @@
       return Alias;
     }
 
-  SmallPtrSet<Value *, 4> UniqueSrc;
+  // Look at the incoming values of the PHI to collect the set of values that
+  // it could have.
+  SmallVector<Value *, 4> Worklist(PN->incoming_values());
+  SmallPtrSet<const Value *, 4> UniqueSrc = { PN };
   SmallVector<Value *, 4> V1Srcs;
   bool isRecursive = false;
-  for (Value *PV1 : PN->incoming_values()) {
-    if (isa<PHINode>(PV1))
-      // If any of the source itself is a PHI, return MayAlias conservatively
-      // to avoid compile time explosion. The worst possible case is if both
-      // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
-      // and 'n' are the number of PHI sources.
-      return MayAlias;
+  unsigned PhiCount = 0;
+  do {
+    Value *PV1 = Worklist.pop_back_val();
+
+    // Record that we've seen this value and skip it if we've seen it before.
+    if (!UniqueSrc.insert(PV1).second)
+      continue;
 
     if (EnableRecPhiAnalysis)
       if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
@@ -1532,9 +1535,32 @@
         }
       }
 
-    if (UniqueSrc.insert(PV1).second)
-      V1Srcs.push_back(PV1);
-  }
+    if (PHINode *PV1PHI = dyn_cast<PHINode>(PV1)) {
+      // If we've looked through too many PHI nodes already then give up and
+      // conservatively return MayAlias.
+      if (++PhiCount >= MaxLookupSearchDepth)
+        return MayAlias;
+      // Add the incoming values of this PHI to the work list.
+      for (Value *Incoming : PV1PHI->incoming_values())
+        Worklist.push_back(Incoming);
+      continue;
+    }
+
+    // If we've looked through at least one phi and already seen another value
+    // then return MayAlias conservatively to avoid compile time explosion. The
+    // worst possible case is if both sides are PHI nodes. In which case, this
+    // is O(m x n) time where 'm' and 'n' are the number of PHI sources.
+    if (PhiCount > 0 && !V1Srcs.empty())
+      return MayAlias;
+
+    V1Srcs.push_back(PV1);
+  } while (!Worklist.empty());
+
+  // If V1Srcs is empty then that means that the phi has no underlying non-phi
+  // value. This should only be possible in blocks unreachable from the entry
+  // block, but return MayAlias just in case.
+  if (V1Srcs.empty())
+    return MayAlias;
 
   // If this PHI node is recursive, set the size of the accessed memory to
   // unknown to represent all the possible values the GEP could advance the
Index: test/Analysis/BasicAA/phi-aa.ll
===================================================================
--- test/Analysis/BasicAA/phi-aa.ll
+++ test/Analysis/BasicAA/phi-aa.ll
@@ -77,4 +77,39 @@
 
 declare void @inc(i32*)
 
-
+; When we have a chain of phis in nested loops we should recognise if there's
+; actually only one underlying value.
+; CHECK-LABEL: loop_phi_chain
+; CHECK: NoAlias: i32* %val1, i32* @Y
+; CHECK: NoAlias: i32* %val2, i32* @Y
+; CHECK: NoAlias: i32* %val3, i32* @Y
+define void @loop_phi_chain(i32 %a, i32 %b, i32 %c) {
+entry:
+  br label %loop1
+
+loop1:
+  %n1 = phi i32 [ 0, %entry ], [ %add1, %loop2 ]
+  %val1 = phi i32* [ @X, %entry ], [ %val2, %loop2 ]
+  %add1 = add i32 %n1, 1
+  %cmp1 = icmp ne i32 %n1, 32
+  br i1 %cmp1, label %loop2, label %end
+
+loop2:
+  %n2 = phi i32 [ 0, %loop1 ], [ %add2, %loop3 ]
+  %val2 = phi i32* [ %val1, %loop1 ], [ %val3, %loop3 ]
+  %add2 = add i32 %n2, 1
+  %cmp2 = icmp ne i32 %n2, 32
+  br i1 %cmp2, label %loop3, label %loop1
+
+loop3:
+  %n3 = phi i32 [ 0, %loop2 ], [ %add3, %loop3 ]
+  %val3 = phi i32* [ %val2, %loop2 ], [ %val3, %loop3 ]
+  store i32 0, i32* %val3, align 4
+  store i32 0, i32* @Y, align 4
+  %add3 = add i32 %n3, 1
+  %cmp3 = icmp ne i32 %n3, 32
+  br i1 %cmp3, label %loop3, label %loop2
+
+end:
+  ret void
+}
Index: test/Transforms/GVN/pre-after-rle.ll
===================================================================
--- /dev/null
+++ test/Transforms/GVN/pre-after-rle.ll
@@ -0,0 +1,36 @@
+; RUN: opt -gvn -S < %s | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+
+; Detecting that %s is fully redundant should let us detect that %w is partially
+; redundant.
+define void @fn(i32** noalias %start, i32* %width, i32 %h) {
+entry:
+  %call = tail call noalias i8* @malloc(i64 1024)
+  %call.cast = bitcast i8* %call to i32*
+  store i32* %call.cast, i32** %start, align 8
+  br label %preheader
+
+preheader:
+  %cmp = icmp slt i32 1, %h
+  br i1 %cmp, label %body, label %exit
+
+; CHECK-LABEL: preheader.body_crit_edge:
+; CHECK: load i32, i32* %width, align 8
+
+; CHECK-LABEL: body:
+; CHECK-NOT: load i32*, i32** %start, align 8
+; CHECK-NOT: load i32, i32* %width, align 8
+body:
+  %j = phi i32 [ 0, %preheader ], [ %j.next, %body ]
+  %s = load i32*, i32** %start, align 8
+  %idx = getelementptr inbounds i32, i32* %s, i64 0
+  store i32 0, i32* %idx, align 4
+  %j.next = add nuw nsw i32 %j, 1
+  %w = load i32, i32* %width, align 8
+  %cmp3 = icmp slt i32 %j.next, %w
+  br i1 %cmp3, label %body, label %preheader
+
+exit:
+  ret void
+}