[BasicAA] Fix caching in the presence of phi cycles

[nikic]

Summary

Any time we insert a block into VisitedPhiBBs, previously cached values may no longer be valid for the recursive alias queries. As such, perform them using an empty AAQueryInfo. (Note that if we recurse to the same phi, the block will already be inserted, so we reuse the old AAQueryInfo, and thus still protect against infinite recursion.)

This is a different approach to fixing this problem than D90062, I'm not sure what the tradeoffs are yet.

[asbirlea]

Thank you for this patch, I think this is a better general direction.

1. Did you happen to test the compile-time impact for this? (it's a correctness fix, and needed, but it would be good to note on what to expect)

2. I think the IsCapturedCache cache can be reused in the new AAQI. Ideally the new AAQI would use a reference to it, not a copy, which would need a bit of a re-write but may be worth as far as performance.

3. Could you add to the test something like this (this was defeating my patch):

BatchAAResults BatchAA2(AA);
EXPECT_EQ(NoAlias, BatchAA2.alias(A1Loc, A2Loc));
EXPECT_EQ(MayAlias, BatchAA2.alias(S1Loc, S2Loc));
EXPECT_EQ(MayAlias, BatchAA2.alias(PhiLoc, A1Loc));

Looking further to see if there's anything I missed.

[nikic]

Here are the compile-time numbers for this patch: https://llvm-compile-time-tracker.com/compare.php?from=1b65a51af80a9375ef85cb8fa6ec9ec3c68b3549&to=6bd243feb2dddd58c51a919806bfea175b0b04a0&stat=instructions The impact actually seems pretty low, so I think this is a viable approach.

[nikic]

Add additional BatchAA test with different query order.

[nikic]

I've now added the additional test.

Regarding the IsCapturedCache, I agree that this is safe to reuse. I thought we might get away with just temporarily swapping out the AliasCache and keeping the rest (https://github.com/llvm/llvm-project/commit/8815a0174d93fb8eadac9c4d82b09edfd1f34319), but it turns out this has worse performance impact (https://llvm-compile-time-tracker.com/compare.php?from=1b65a51af80a9375ef85cb8fa6ec9ec3c68b3549&to=8815a0174d93fb8eadac9c4d82b09edfd1f34319&stat=instructions). Probably because swapping out a SmallDenseSet of MemoryLocation pairs is expensive -- these are large structures.

For efficient reuse we'd want to convert the capture cache into a pointer that either points into an owned cache in AAQueryInfo, or into a separate cache. However, that introduces a self-reference, so we'd also have to deal with custom move/copy constructors/assignments. Given that the impact doesn't seem so large, I'm not sure it's worth the bother.

[nikic]

Here's how retaining the capture cache could look like (on top of this patch): https://github.com/llvm/llvm-project/commit/20a6f50ffcbae9ff53792ce87f97abd4a41453d5
Doing this does improve things a little bit: http://llvm-compile-time-tracker.com/compare.php?from=1b65a51af80a9375ef85cb8fa6ec9ec3c68b3549&to=20a6f50ffcbae9ff53792ce87f97abd4a41453d5&stat=instructions (The small tramp3d-v4 ReleaseThinLTO regression is no longer present.)
But maybe not enough to justify the complexity.

[asbirlea]

Thank you for the numbers and the additional variants. I agree it's good to move forward with this approach as is.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
   // unknown to represent all the possible values the GEP could advance the
   // pointer to.
   if (isRecursive)
     PNSize = LocationSize::unknown();
 
   // 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.
   if (Alias == MayAlias)
     return MayAlias;
   // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
   // remain valid to all elements and needs to conservatively return MayAlias.
   if (isRecursive && Alias != NoAlias)
     return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   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;
   }
 
   return Alias;
 }
 

llvm/unittests/Analysis/AliasAnalysisTest.cpp

TEST_F(AliasAnalysisTest, BatchAAPhiCycles) {
   MemoryLocation A1Loc(A1, LocationSize::precise(1));
   MemoryLocation A2Loc(A2, LocationSize::precise(1));
   MemoryLocation S1Loc(S1, LocationSize::precise(1));
   MemoryLocation S2Loc(S2, LocationSize::precise(1));
 
   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 {
 protected:
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M;