Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -2514,6 +2514,66 @@
   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 and they have same incoming blocks.
+  bool HasSameIncomingBB = true;
+  if (PN1 && PN2 && PN1->getParent() == PN2->getParent() && Q.DT != nullptr) {
+    // Check the incoming blocks of two PHIs are same.
+    for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
+      const BasicBlock *IncomingBB = PN1->getIncomingBlock(i);
+      if (PN2->getBasicBlockIndex(IncomingBB) == -1) {
+        HasSameIncomingBB = false;
+        break;
+      }
+    }
+  } else
+    HasSameIncomingBB = false;
+
+  if (HasSameIncomingBB) {
+    // Now the two PHIs have same incoming blocks. Let's compare incoming
+    // values with same incoming block.
+    SmallPtrSet<const BasicBlock *, 8> VisitedBBs;
+    bool IsNonEqual = true;
+    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->dominates(PN1->getParent(), Pred)) {
+        // loop:
+        //   %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %loop ]
+        //   %cmp.0 = phi i32 [ 3, %entry ], [ %mul, %loop ]
+        //   ...
+        //   %inc = add i32 %cmp.0, 1
+        //   br label %loop
+        //
+        // On above example, %pos.0 uses previous iteration's %cmp.0 with
+        // backedge according to PHI's instruction's defintion. As a result,
+        // we can say %pos.0 is not same with %cmp.0. Let's check this
+        // pattern.
+        if (PN1 == IV2 || PN2 == IV1) {
+          // FIXME: Do we have to check the IdxVal is not constant in detail?
+          continue;
+        }
+      }
+
+      IsNonEqual = false;
+      break;
+    }
+
+    if (IsNonEqual)
+      return true;
+  }
+
+  return false;
+}
+
 /// 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 +2642,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}