[BasicAA] Include MayBeCrossIteration in cache key

[nikic]

Summary

Rather than switching to a new AAQI instance with empty cache when MayBeCrossIteration is toggled, include the value in the cache key.

The implementation redundantly include the information in both sides of the pair, but that seems simpler than trying to store it only on one side.

Depends on D136174.

[reames]

Can you add some explanatory comments into the code please? I'm not entirely sure I understand the caching protocol, and I doubt future readers will. I think this is correct, but I'm not 100% sure on that.

It would also help if you'd explicitly state the invariant relating results with and without the cycle flag. I *think* non-cyclic results should always be at least as precise as the potentially cyclic results. Right? If so, that feels like a valuable thing to note, and (maybe) assert?

llvm/include/llvm/Analysis/AliasAnalysis.h

191–192

Update comment please.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1409

This appears to have been only use of withEmptyCache, can you remove?

1541–1545

Can you comment this please?

[nikic]

Remove withEmptyCache(), adjust comments.

[nikic]

In D136175#3885870, @reames wrote:

Can you add some explanatory comments into the code please? I'm not entirely sure I understand the caching protocol, and I doubt future readers will. I think this is correct, but I'm not 100% sure on that.

I think for the purposes here, the only thing to know is that anything that influences BasicAA results should be part of the cache key.

It would also help if you'd explicitly state the invariant relating results with and without the cycle flag. I *think* non-cyclic results should always be at least as precise as the potentially cyclic results. Right? If so, that feels like a valuable thing to note, and (maybe) assert?

Conceptually, yes. In practice, this is likely not strictly true in some edge cases. E.g. it could be that the queries start at different depths and one of them hits a depth cutoff and returns a worse result because of that. As such, I don't think we can actually assert it.

Based on your comments, I had the idea that instead of including this in the cache key, we could instead store both Result and ResultInCycle and if we for example determine that Result is MayAlias, we can directly set ResultInCycle to MayAlias as well, because we know it's not going to be better than that. Conversely, if ResultInCycle is NoAlias/MustAlias, we can also set Result based on that. I thought this would be pretty nice, in that it might avoid some redundant calculation. However, we have some pretty complex machinery for invalidating cache entries based on disproven noalias assumptions, and I think getting the interaction there right would be pretty tricky.

[reames]

LGTM

llvm/include/llvm/Analysis/AliasAnalysis.h

EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI,
                      const SmallPtrSetImpl<const Value *> &EphValues)
       : DT(DT), LI(LI), EphValues(EphValues) {}
 
   bool isNotCapturedBeforeOrAt(const Value *Object,
                                const Instruction *I) override;
 
   void removeInstruction(Instruction *I);
 };
 
-/// Reduced version of MemoryLocation that only stores a pointer and size.
-/// Used for caching AATags independent BasicAA results.
+/// Cache key for BasicAA results. It only includes the pointer and size from
+/// MemoryLocation, as BasicAA is AATags independent. Additionally, it includes
+/// the value of MayBeCrossIteration, which may affect BasicAA results.
 struct AACacheLoc {
-  const Value *Ptr;
+  using PtrTy = PointerIntPair<const Value *, 1, bool>;
+  PtrTy Ptr;
   LocationSize Size;
+
+  AACacheLoc(PtrTy Ptr, LocationSize Size) : Ptr(Ptr), Size(Size) {}
+  AACacheLoc(const Value *Ptr, LocationSize Size, bool MayBeCrossIteration)
+      : Ptr(Ptr, MayBeCrossIteration), Size(Size) {}
 };
 
 template <> struct DenseMapInfo<AACacheLoc> {
   static inline AACacheLoc getEmptyKey() {
-    return {DenseMapInfo<const Value *>::getEmptyKey(),
+    return {DenseMapInfo<AACacheLoc::PtrTy>::getEmptyKey(),
             DenseMapInfo<LocationSize>::getEmptyKey()};
   }
   static inline AACacheLoc getTombstoneKey() {
-    return {DenseMapInfo<const Value *>::getTombstoneKey(),
+    return {DenseMapInfo<AACacheLoc::PtrTy>::getTombstoneKey(),
             DenseMapInfo<LocationSize>::getTombstoneKey()};
   }
   static unsigned getHashValue(const AACacheLoc &Val) {
-    return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
+    return DenseMapInfo<AACacheLoc::PtrTy>::getHashValue(Val.Ptr) ^
            DenseMapInfo<LocationSize>::getHashValue(Val.Size);
   }
   static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) {
     return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size;
   }
 };
 
 class AAResults;
public:
   int NumAssumptionUses = 0;
 
   /// Location pairs for which an assumption based result is currently stored.
   /// Used to remove all potentially incorrect results from the cache if an
   /// assumption is disproven.
   SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;
 
   AAQueryInfo(AAResults &AAR, CaptureInfo *CI) : AAR(AAR), CI(CI) {}
-
-  /// Create a new AAQueryInfo based on this one, but with the cache cleared.
-  /// This is used for recursive queries across phis, where cache results may
-  /// not be valid.
-  AAQueryInfo withEmptyCache() {
-    AAQueryInfo NewAAQI(AAR, CI);
-    NewAAQI.Depth = Depth;
-    return NewAAQI;
-  }
 };
 
 /// AAQueryInfo that uses SimpleCaptureInfo.
 class SimpleAAQueryInfo : public AAQueryInfo {
   SimpleCaptureInfo CI;
 
 public:
   SimpleAAQueryInfo(AAResults &AAR) : AAQueryInfo(AAR, &CI) {}

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
   // objects are involved.
   if (isRecursive)
     PNSize = LocationSize::beforeOrAfterPointer();
 
   // In the recursive alias queries below, we may compare values from two
   // different loop iterations.
   SaveAndRestore<bool> SavedMayBeCrossIteration(MayBeCrossIteration, true);
 
-  // If we enabled the MayBeCrossIteration flag, alias analysis results that
-  // have been cached earlier may no longer be valid. Perform recursive queries
-  // with a new AAQueryInfo.
-  AAQueryInfo NewAAQI = AAQI.withEmptyCache();
-  AAQueryInfo *UseAAQI = !SavedMayBeCrossIteration.get() ? &NewAAQI : &AAQI;
-
   AliasResult Alias = AAQI.AAR.alias(MemoryLocation(V1Srcs[0], PNSize),
-                                     MemoryLocation(V2, V2Size), *UseAAQI);
+                                     MemoryLocation(V2, V2Size), AAQI);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == AliasResult::MayAlias)
     return AliasResult::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 != AliasResult::NoAlias)
     return AliasResult::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 = AAQI.AAR.alias(
-        MemoryLocation(V, PNSize), MemoryLocation(V2, V2Size), *UseAAQI);
+        MemoryLocation(V, PNSize), MemoryLocation(V2, V2Size), AAQI);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == AliasResult::MayAlias)
       break;
   }
 
   return Alias;
 }
 
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // FIXME: If this depth limit is hit, then we may cache sub-optimal results
   // for recursive queries. For this reason, this limit is chosen to be large
   // enough to be very rarely hit, while still being small enough to avoid
   // stack overflows.
   if (AAQI.Depth >= 512)
     return AliasResult::MayAlias;
 
   // Check the cache before climbing up use-def chains. This also terminates
-  // otherwise infinitely recursive queries.
-  AAQueryInfo::LocPair Locs({V1, V1Size}, {V2, V2Size});
+  // otherwise infinitely recursive queries. Include MayBeCrossIteration in the
+  // cache key, because some cases where MayBeCrossIteration==false returns
+  // MustAlias or NoAlias may become MayAlias under MayBeCrossIteration==true.
+  AAQueryInfo::LocPair Locs({V1, V1Size, MayBeCrossIteration},
+                            {V2, V2Size, MayBeCrossIteration});
   const bool Swapped = V1 > V2;
   if (Swapped)
     std::swap(Locs.first, Locs.second);
   const auto &Pair = AAQI.AliasCache.try_emplace(
       Locs, AAQueryInfo::CacheEntry{AliasResult::NoAlias, 0});
   if (!Pair.second) {
     auto &Entry = Pair.first->second;
     if (!Entry.isDefinitive()) {