[BasicAA] Don't pass through AA metadata (NFCI)

[nikic]

Summary

BasicAA itself doesn't make use of AA metadata, but passes it through to recursive queries and makes it part of the cache key. Aliasing decisions that are based on AA metadata (i.e. TBAA and ScopedAA) are based *only* on AA metadata, so checking them with different pointer values or sizes is not useful, the result will always be the same.

By itself, this change is a mild compile-time improvement (https://llvm-compile-time-tracker.com/compare.php?from=93127a4d7350261ed9ee2ccaa9c369eda2b60198&to=f4d0c5f01dc446f0c40e8dd81e6b9e9b02217c4d&stat=instructions). However, the actual goal here is to remove the AA metadata from the cache key and thus reduce it's size significantly (from 96 to 32 bytes), which will be the more impactful change. I plan to do that as a followup, but could also include it here.

[asbirlea]

This is an interesting point. IIUC, your argument is that the entry point into AA is always through AAResults and can rely on the invocation result for TBAA or ScopedAA from there, while the recursive invocations into these same analyses cannot yield stricter results. I cannot think of a case when this is not true.

[jeroen.dobbelaere]

I am wondering how this will interact with the ptr_provenance changes/full restrict changes. In the full restrict version, V1AAInfo and V2AAInfo are used in BasicAAResult::aliasCheck to decide if we can see trough noalias intrinsics or not.

[nikic]

@jeroen.dobbelaere I'm not sure on the details, but it may be necessary to pass through just the ptr_provenance information with full restrict and include it in the cache key (while omitting all the other metadata).

[jeroen.dobbelaere]

In D90098#2673969, @nikic wrote:

@jeroen.dobbelaere I'm not sure on the details, but it may be necessary to pass through just the ptr_provenance information with full restrict and include it in the cache key (while omitting all the other metadata).

Yes, that might be a valid path.

[jeroen.dobbelaere]

In D90098#2673996, @jeroen.dobbelaere wrote:

In D90098#2673969, @nikic wrote:

@jeroen.dobbelaere I'm not sure on the details, but it may be necessary to pass through just the ptr_provenance information with full restrict and include it in the cache key (while omitting all the other metadata).

Yes, that might be a valid path.

On the other hand, a ptr_provenance path skips pointer computations. We might need to refactor this code to separate the 'based on' part, so we can first check the ptr_provenance path (if available), and when that is not conclusive,
we can fall back to the original pointers (that also contain GEP information etc).

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
                           DominatorTree *DT);
 
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                           const SmallVectorImpl<VariableGEPIndex> &Src);
 
   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
-                       const AAMDNodes &V1AAInfo, const Value *V2,
-                       LocationSize V2Size, const AAMDNodes &V2AAInfo,
+                       const Value *V2, LocationSize V2Size,
                        const Value *UnderlyingV1, const Value *UnderlyingV2,
                        AAQueryInfo &AAQI);
 
   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
-                       const AAMDNodes &PNAAInfo, const Value *V2,
-                       LocationSize V2Size, const AAMDNodes &V2AAInfo,
-                       AAQueryInfo &AAQI);
+                       const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
 
   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
-                          const AAMDNodes &SIAAInfo, const Value *V2,
-                          LocationSize V2Size, const AAMDNodes &V2AAInfo,
+                          const Value *V2, LocationSize V2Size,
                           AAQueryInfo &AAQI);
 
   AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
-                         const AAMDNodes &V1AATag, const Value *V2,
-                         LocationSize V2Size, const AAMDNodes &V2AATag,
+                         const Value *V2, LocationSize V2Size,
                          AAQueryInfo &AAQI);
 
   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
-                                  const AAMDNodes &V1AATag, const Value *V2,
-                                  LocationSize V2Size, const AAMDNodes &V2AATag,
+                                  const Value *V2, LocationSize V2Size,
                                   AAQueryInfo &AAQI, const Value *O1,
                                   const Value *O2);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class BasicAA : public AnalysisInfoMixin<BasicAA> {
   friend AnalysisInfoMixin<BasicAA>;
 

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 }
 #endif
 
 AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
                                  const MemoryLocation &LocB,
                                  AAQueryInfo &AAQI) {
   assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
          "BasicAliasAnalysis doesn't support interprocedural queries.");
-  return aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, LocB.Size,
-                    LocB.AATags, AAQI);
+  return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI);
 }
 
 /// Checks to see if the specified callsite can clobber the specified memory
 /// object.
 ///
 /// Since we only look at local properties of this function, we really can't
 /// say much about this query.  We do, however, use simple "address taken"
 /// analysis on local objects.

 
 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
 /// another pointer.
 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
 /// V2.
 AliasResult BasicAAResult::aliasGEP(
-    const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
-    const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
+    const GEPOperator *GEP1, LocationSize V1Size,
+    const Value *V2, LocationSize V2Size,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
   if (!V1Size.hasValue() && !V2Size.hasValue()) {
     // TODO: This limitation exists for compile-time reasons. Relax it if we
     // can avoid exponential pathological cases.
     if (!isa<GEPOperator>(V2))
       return MayAlias;
 
     // If both accesses have unknown size, we can only check whether the base
if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() &&
         isBaseOfObject(DecompGEP1.Base))
     return NoAlias;
   }
 
   // For GEPs with identical offsets, we can preserve the size and AAInfo
   // when performing the alias check on the underlying objects.
   if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
     return getBestAAResults().alias(
-        MemoryLocation(UnderlyingV1, V1Size, V1AAInfo),
-        MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI);
+        MemoryLocation(UnderlyingV1, V1Size),
+        MemoryLocation(UnderlyingV2, V2Size), AAQI);
 
   // Do the base pointers alias?
   AliasResult BaseAlias = getBestAAResults().alias(
       MemoryLocation::getBeforeOrAfter(UnderlyingV1),
       MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
 
   // If we get a No or May, then return it immediately, no amount of analysis
   // will improve this situation.
static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
   // Otherwise, we don't know anything.
   return MayAlias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
 /// against another.
 AliasResult
 BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
-                           const AAMDNodes &SIAAInfo, const Value *V2,
-                           LocationSize V2Size, const AAMDNodes &V2AAInfo,
+                           const Value *V2, LocationSize V2Size,
                            AAQueryInfo &AAQI) {
   // If the values are Selects with the same condition, we can do a more precise
   // check: just check for aliases between the values on corresponding arms.
   if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
     if (SI->getCondition() == SI2->getCondition()) {
       AliasResult Alias = getBestAAResults().alias(
-          MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo),
-          MemoryLocation(SI2->getTrueValue(), V2Size, V2AAInfo), AAQI);
+          MemoryLocation(SI->getTrueValue(), SISize),
+          MemoryLocation(SI2->getTrueValue(), V2Size), AAQI);
       if (Alias == MayAlias)
         return MayAlias;
       AliasResult ThisAlias = getBestAAResults().alias(
-          MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo),
-          MemoryLocation(SI2->getFalseValue(), V2Size, V2AAInfo), AAQI);
+          MemoryLocation(SI->getFalseValue(), SISize),
+          MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
       return MergeAliasResults(ThisAlias, Alias);
     }
 
   // If both arms of the Select node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   AliasResult Alias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size, V2AAInfo),
-      MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo), AAQI);
+      MemoryLocation(V2, V2Size),
+      MemoryLocation(SI->getTrueValue(), SISize), AAQI);
   if (Alias == MayAlias)
     return MayAlias;
 
   AliasResult ThisAlias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size, V2AAInfo),
-      MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo), AAQI);
+      MemoryLocation(V2, V2Size),
+      MemoryLocation(SI->getFalseValue(), SISize), AAQI);
   return MergeAliasResults(ThisAlias, Alias);
 }
 
 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
 /// another.
 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
-                                    const AAMDNodes &PNAAInfo, const Value *V2,
-                                    LocationSize V2Size,
-                                    const AAMDNodes &V2AAInfo,
+                                    const Value *V2, LocationSize V2Size,
                                     AAQueryInfo &AAQI) {
   // If the values are PHIs in the same block, we can do a more precise
   // as well as efficient check: just check for aliases between the values
   // on corresponding edges.
   if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
     if (PN2->getParent() == PN->getParent()) {
       Optional<AliasResult> Alias;
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         AliasResult ThisAlias = getBestAAResults().alias(
-            MemoryLocation(PN->getIncomingValue(i), PNSize, PNAAInfo),
+            MemoryLocation(PN->getIncomingValue(i), PNSize),
             MemoryLocation(
-                PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size,
-                V2AAInfo),
+                PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size),
             AAQI);
         if (Alias)
           *Alias = MergeAliasResults(*Alias, ThisAlias);
         else
           Alias = ThisAlias;
         if (*Alias == MayAlias)
           break;
       }
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
 
   // 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 = AAQI.withEmptyCache();
   AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
 
   AliasResult Alias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size, V2AAInfo),
-      MemoryLocation(V1Srcs[0], PNSize, PNAAInfo), *UseAAQI);
+      MemoryLocation(V2, V2Size),
+      MemoryLocation(V1Srcs[0], PNSize), *UseAAQI);
 
   // 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 = getBestAAResults().alias(
-        MemoryLocation(V2, V2Size, V2AAInfo),
-        MemoryLocation(V, PNSize, PNAAInfo), *UseAAQI);
+        MemoryLocation(V2, V2Size), MemoryLocation(V, PNSize), *UseAAQI);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == MayAlias)
       break;
   }
 
   return Alias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
 AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
-                                      const AAMDNodes &V1AAInfo,
                                       const Value *V2, LocationSize V2Size,
-                                      const AAMDNodes &V2AAInfo,
                                       AAQueryInfo &AAQI) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size.isZero() || V2Size.isZero())
     return NoAlias;
 
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCastsForAliasAnalysis();
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // 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 MayAlias;
 
   // Check the cache before climbing up use-def chains. This also terminates
   // otherwise infinitely recursive queries.
-  AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
-                            MemoryLocation(V2, V2Size, V2AAInfo));
+  AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size),
+                            MemoryLocation(V2, V2Size));
   if (V1 > V2)
     std::swap(Locs.first, Locs.second);
   const auto &Pair = AAQI.AliasCache.try_emplace(
       Locs, AAQueryInfo::CacheEntry{NoAlias, 0});
   if (!Pair.second) {
     auto &Entry = Pair.first->second;
     if (!Entry.isDefinitive()) {
       // Remember that we used an assumption.
       ++Entry.NumAssumptionUses;
       ++AAQI.NumAssumptionUses;
     }
     return Entry.Result;
   }
 
   int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
   unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
-  AliasResult Result = aliasCheckRecursive(V1, V1Size, V1AAInfo, V2, V2Size,
-                                           V2AAInfo, AAQI, O1, O2);
+  AliasResult Result =
+      aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
 
   auto It = AAQI.AliasCache.find(Locs);
   assert(It != AAQI.AliasCache.end() && "Must be in cache");
   auto &Entry = It->second;
 
   // Check whether a NoAlias assumption has been used, but disproven.
   bool AssumptionDisproven = Entry.NumAssumptionUses > 0 && Result != NoAlias;
   if (AssumptionDisproven)
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // The result may still be based on assumptions higher up in the chain.
   // Remember it, so it can be purged from the cache later.
   if (OrigNumAssumptionUses != AAQI.NumAssumptionUses && Result != MayAlias)
     AAQI.AssumptionBasedResults.push_back(Locs);
   return Result;
 }
 
 AliasResult BasicAAResult::aliasCheckRecursive(
-    const Value *V1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
-    const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
+    const Value *V1, LocationSize V1Size,
+    const Value *V2, LocationSize V2Size,
     AAQueryInfo &AAQI, const Value *O1, const Value *O2) {
   if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
-    AliasResult Result =
-        aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI);
+    AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, O1, O2, AAQI);
     if (Result != MayAlias)
       return Result;
   } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) {
-    AliasResult Result =
-        aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI);
+    AliasResult Result = aliasGEP(GV2, V2Size, V1, V1Size, O2, O1, AAQI);
     if (Result != MayAlias)
       return Result;
   }
 
   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
-    AliasResult Result =
-        aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
+    AliasResult Result = aliasPHI(PN, V1Size, V2, V2Size, AAQI);
     if (Result != MayAlias)
       return Result;
   } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) {
-    AliasResult Result =
-        aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI);
+    AliasResult Result = aliasPHI(PN, V2Size, V1, V1Size, AAQI);
     if (Result != MayAlias)
       return Result;
   }
 
   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
-    AliasResult Result =
-        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
+    AliasResult Result = aliasSelect(S1, V1Size, V2, V2Size, AAQI);
     if (Result != MayAlias)
       return Result;
   } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) {
-    AliasResult Result =
-        aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI);
+    AliasResult Result = aliasSelect(S2, V2Size, V1, V1Size, AAQI);
     if (Result != MayAlias)
       return Result;
   }
 
   // If both pointers are pointing into the same object and one of them
   // accesses the entire object, then the accesses must overlap in some way.
   if (O1 == O2) {
     bool NullIsValidLocation = NullPointerIsDefined(&F);