Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -2514,6 +2514,48 @@
   return isKnownNonZero(V, DemandedElts, Depth, Q);
 }
 
+static bool isNonEqualPHIs(const PHINode *PN1, const PHINode *PN2,
+                           unsigned Depth, const Query &Q) {
+  // Check two PHIs are in same block.
+  if (PN1->getParent() != PN2->getParent())
+    return false;
+
+  // Now the two PHIs have same incoming blocks. Let's compare incoming
+  // values with same incoming block.
+  SmallPtrSet<const BasicBlock *, 8> VisitedBBs;
+  for (const BasicBlock *Pred : predecessors(PN1->getParent())) {
+    if (!VisitedBBs.insert(Pred).second)
+      continue; // Don't reprocess blocks that we have dealt with already.
+    const Value *IV1 = PN1->getIncomingValueForBlock(Pred);
+    const Value *IV2 = PN2->getIncomingValueForBlock(Pred);
+    if (isKnownNonEqual(IV1, IV2, Depth + 1, Q))
+      continue;
+
+    // If it is not known NonEqual, check backedge from PHI's incoming block
+    // to the PHI's block.
+    if (Q.DT != nullptr && Q.DT->dominates(PN1->getParent(), Pred)) {
+      // loop:
+      //   %cmp.0 = phi i32 [ 3, %entry ], [ %inc, %loop ]
+      //   %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %loop ]
+      //   ...
+      //   %inc = add i32 %cmp.0, 1
+      //   br label %loop
+      //
+      // FIXME: On above example, %pos.0 uses previous iteration's %cmp.0 with
+      // backedge according to PHI's instruction's defintion. In this case, can
+      // we check %inc is not same with previous iteration's %inc?
+      if (PN1 == IV2 || PN2 == IV1) {
+        // FIXME: This is not good enough and just passes above example.
+        continue;
+      }
+    }
+
+    return false;
+  }
+
+  return true;
+}
+
 /// Return true if V2 == V1 + X, where X is known non-zero.
 static bool isAddOfNonZero(const Value *V1, const Value *V2, unsigned Depth,
                            const Query &Q) {
@@ -2582,12 +2624,20 @@
     case Instruction::SExt:
     case Instruction::ZExt:
       if (O1->getOperand(0)->getType() == O2->getOperand(0)->getType())
-        return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0),
-                               Depth + 1, Q);
+        return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0), Depth + 1,
+                               Q);
+      break;
+    case Instruction::PHI:
+      const PHINode *PN1 = cast<PHINode>(V1);
+      const PHINode *PN2 = cast<PHINode>(V2);
+      // FIXME: This is missing a generalization to handle the case where one is
+      // a PHI and another one isn't.
+      if (isNonEqualPHIs(PN1, PN2, Depth + 1, Q))
+        return true;
       break;
     };
   }
-  
+
   if (isAddOfNonZero(V1, V2, Depth, Q) || isAddOfNonZero(V2, V1, Depth, Q))
     return true;
 
Index: llvm/test/Analysis/BasicAA/alias-gep-phi.ll
===================================================================
--- /dev/null
+++ llvm/test/Analysis/BasicAA/alias-gep-phi.ll
@@ -0,0 +1,50 @@
+; RUN: opt < %s -basic-aa -instcombine -S 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+
+%struct.data = type { i32, i32 }
+
+define void @_Z11alias_issueP4datai(%struct.data* %data, i32 %max) {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %while.body ]
+  %cmp.0 = phi i32 [ 3, %entry ], [ %mul, %while.body ]
+  %cmp1 = icmp slt i32 %cmp.0, %max
+  br i1 %cmp1, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %sub = add nsw i32 %cmp.0, -1
+  %idxprom = sext i32 %sub to i64
+  %newVal = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom, i32 1
+
+; CHECK: [[LOAD0:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0
+  %0 = load i32, i32* %newVal, align 4, !tbaa !0
+  %sub2 = add nsw i32 %pos.0, -1
+  %idxprom3 = sext i32 %sub2 to i64
+  %arrayidx4 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3
+  %newVal5 = getelementptr inbounds %struct.data, %struct.data* %data, i64 %idxprom3, i32 1
+  store i32 %0, i32* %newVal5, align 4, !tbaa !0
+
+; Above store blocks to remove below load becasue MayAlias between %newVal and
+; %newVal5. The address %newVal has no alias with %newVal5. If BasicAA
+; recognizes it, below load should be removed with instcombine.
+
+; CHECK-NOT: [[LOAD1:%[a-zA-Z0-9_]+]] = load i32, i32* %newVal, align 4, !tbaa !0
+  %1 = load i32, i32* %newVal, align 4, !tbaa !0
+  %oldVal = getelementptr inbounds %struct.data, %struct.data* %arrayidx4, i32 0, i32 0
+  store i32 %1, i32* %oldVal, align 4, !tbaa !5
+  %mul = mul nsw i32 %cmp.0, 2
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}
+
+!0 = !{!1, !2, i64 4}
+!1 = !{!"_ZTS4data", !2, i64 0, !2, i64 4}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C++ TBAA"}
+!5 = !{!1, !2, i64 0}