diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h
--- a/llvm/include/llvm/Analysis/AliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/AliasAnalysis.h
@@ -348,8 +348,19 @@
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   IsCapturedCacheT IsCapturedCache;
 
+  bool BatchMode = false;
+  bool Reset = false;
+
   AAQueryInfo() : AliasCache(), IsCapturedCache() {}
 
+  AAQueryInfo(bool BatchMode) : AliasCache(), IsCapturedCache() {
+    this->BatchMode = BatchMode;
+  }
+
+  void erase(const MemoryLocation &LocA, const MemoryLocation &LocB) {
+    AliasCache.erase(LocPair(LocA, LocB));
+  }
+
   AliasResult updateResult(const LocPair &Locs, AliasResult Result) {
     auto It = AliasCache.find(Locs);
     assert(It != AliasCache.end() && "Entry must have existed");
@@ -827,7 +838,7 @@
   AAQueryInfo AAQI;
 
 public:
-  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
+  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(true) {}
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return AA.alias(LocA, LocB, AAQI);
   }
diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
--- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
@@ -190,12 +190,14 @@
   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
                           LocationSize V1Size, LocationSize V2Size,
                           const APInt &BaseOffset, AssumptionCache *AC,
-                          DominatorTree *DT);
+                          DominatorTree *DT, AAQueryInfo &AAQI);
 
-  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
+  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
+                                     AAQueryInfo &AAQI);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
-                          const SmallVectorImpl<VariableGEPIndex> &Src);
+                          const SmallVectorImpl<VariableGEPIndex> &Src,
+                          AAQueryInfo &AAQI);
 
   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
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
@@ -814,6 +814,8 @@
 
   AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
                                  LocB.Size, LocB.AATags, AAQI);
+  if (AAQI.Reset)
+    AAQI.erase(LocA, LocB);
 
   assert(VisitedPhiBBs.empty());
   return Alias;
@@ -1263,6 +1265,7 @@
     const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
+
   DecomposedGEP DecompGEP1, DecompGEP2;
   unsigned MaxPointerSize = getMaxPointerSize(DL);
   DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
@@ -1349,7 +1352,7 @@
     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
     // symbolic difference.
     GEP1BaseOffset -= GEP2BaseOffset;
-    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
+    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices, AAQI);
 
   } else {
     // Check to see if these two pointers are related by the getelementptr
@@ -1473,7 +1476,7 @@
       return NoAlias;
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
-                                GEP1BaseOffset, &AC, DT))
+                                GEP1BaseOffset, &AC, DT, AAQI))
       return NoAlias;
   }
 
@@ -1716,7 +1719,7 @@
   // case. The function isValueEqualInPotentialCycles ensures that this cannot
   // happen by looking at the visited phi nodes and making sure they cannot
   // reach the value.
-  if (isValueEqualInPotentialCycles(V1, V2))
+  if (isValueEqualInPotentialCycles(V1, V2, AAQI))
     return MustAlias;
 
   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
@@ -1854,7 +1857,8 @@
 /// have to do this because we are looking through phi nodes (That is we say
 /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
 bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
-                                                  const Value *V2) {
+                                                  const Value *V2,
+                                                  AAQueryInfo &AAQI) {
   if (V != V2)
     return false;
 
@@ -1862,6 +1866,9 @@
   if (!Inst)
     return true;
 
+  if (AAQI.BatchMode)
+    AAQI.Reset = true;
+
   if (VisitedPhiBBs.empty())
     return true;
 
@@ -1884,7 +1891,7 @@
 /// instructions GEP1 and GEP2 which have common base pointers.
 void BasicAAResult::GetIndexDifference(
     SmallVectorImpl<VariableGEPIndex> &Dest,
-    const SmallVectorImpl<VariableGEPIndex> &Src) {
+    const SmallVectorImpl<VariableGEPIndex> &Src, AAQueryInfo &AAQI) {
   if (Src.empty())
     return;
 
@@ -1896,7 +1903,7 @@
     // Find V in Dest.  This is N^2, but pointer indices almost never have more
     // than a few variable indexes.
     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
-      if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
+      if (!isValueEqualInPotentialCycles(Dest[j].V, V, AAQI) ||
           Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
         continue;
 
@@ -1921,7 +1928,7 @@
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices,
     LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset,
-    AssumptionCache *AC, DominatorTree *DT) {
+    AssumptionCache *AC, DominatorTree *DT, AAQueryInfo &AAQI) {
   if (VarIndices.size() != 2 || MaybeV1Size == LocationSize::unknown() ||
       MaybeV2Size == LocationSize::unknown())
     return false;
@@ -1953,7 +1960,7 @@
                                         V1SExtBits, DL, 0, AC, DT, NSW, NUW);
 
   if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
-      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
+      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1, AAQI))
     return false;
 
   // We have a hit - Var0 and Var1 only differ by a constant offset!
diff --git a/llvm/unittests/Analysis/AliasAnalysisTest.cpp b/llvm/unittests/Analysis/AliasAnalysisTest.cpp
--- a/llvm/unittests/Analysis/AliasAnalysisTest.cpp
+++ b/llvm/unittests/Analysis/AliasAnalysisTest.cpp
@@ -246,7 +246,7 @@
 
   BatchAAResults BatchAA(AA);
   EXPECT_EQ(NoAlias, BatchAA.alias(A1Loc, A2Loc));
-  EXPECT_EQ(NoAlias, BatchAA.alias(PhiLoc, A1Loc)); // TODO: This is wrong.
+  EXPECT_EQ(MayAlias, BatchAA.alias(PhiLoc, A1Loc));
 }
 
 class AAPassInfraTest : public testing::Test {