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
@@ -1655,14 +1655,20 @@
   // In the recursive alias queries below, we may compare values from two
   // different loop iterations. Keep track of visited phi blocks, which will
   // be used when determining value equivalence.
-  auto Pair = VisitedPhiBBs.insert(PN->getParent());
+  bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second;
   auto _ = make_scope_exit([&]() {
-    if (Pair.second)
+    if (BlockInserted)
       VisitedPhiBBs.erase(PN->getParent());
   });
 
+  // If we inserted a block into VisitedPhiBBs, alias analysis results that
+  // have been cached earlier may no longer be valid. Perform recursive queries
+  // with a new AAQueryInfo.
+  AAQueryInfo NewAAQI;
+  AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
+
   AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize,
-                                 PNAAInfo, AAQI, UnderV2);
+                                 PNAAInfo, *UseAAQI, UnderV2);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
@@ -1678,8 +1684,8 @@
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
     Value *V = V1Srcs[i];
 
-    AliasResult ThisAlias =
-        aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, AAQI, UnderV2);
+    AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, V, PNSize,
+                                       PNAAInfo, *UseAAQI, UnderV2);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == MayAlias)
       break;
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
@@ -249,12 +249,17 @@
   auto &AA = getAAResults(*F);
   EXPECT_EQ(NoAlias, AA.alias(A1Loc, A2Loc));
   EXPECT_EQ(MayAlias, AA.alias(PhiLoc, A1Loc));
-  EXPECT_EQ(NoAlias, AA.alias(S1Loc, S2Loc)); // TODO: This is wrong
+  EXPECT_EQ(MayAlias, AA.alias(S1Loc, S2Loc));
 
   BatchAAResults BatchAA(AA);
   EXPECT_EQ(NoAlias, BatchAA.alias(A1Loc, A2Loc));
-  EXPECT_EQ(NoAlias, BatchAA.alias(PhiLoc, A1Loc)); // TODO: This is wrong.
-  EXPECT_EQ(NoAlias, BatchAA.alias(S1Loc, S2Loc)); // TODO: This is wrong
+  EXPECT_EQ(MayAlias, BatchAA.alias(PhiLoc, A1Loc));
+  EXPECT_EQ(MayAlias, BatchAA.alias(S1Loc, S2Loc));
+
+  BatchAAResults BatchAA2(AA);
+  EXPECT_EQ(NoAlias, BatchAA2.alias(A1Loc, A2Loc));
+  EXPECT_EQ(MayAlias, BatchAA2.alias(S1Loc, S2Loc));
+  EXPECT_EQ(MayAlias, BatchAA2.alias(PhiLoc, A1Loc));
 }
 
 class AAPassInfraTest : public testing::Test {