[BasicAA] Handle recursive queries more efficiently (NFCI)

[nikic]

Summary

An alias query currently works out roughly like this:

• Look up location pair in cache.
• Perform BasicAA logic (including cache lookup and insertion...)
• Perform a recursive query using BestAAResults.
  • Look up location pair in cache (and thus do not recurse into BasicAA)
  • Query all the other AA providers.
• Query all the other AA providers.

This is a lot of unnecessary work, all ultimately caused by the BestAAResults query at the end of aliasCheck(). The reason we perform it, is that aliasCheck() is getting called recursively, and we of course want those recursive queries to also make use of other AA providers, not just BasicAA. We can solve this by making the recursive queries directly use BestAAResults (which will check both BasicAA and other providers), rather than recursing into aliasCheck().

There are some tradeoffs:

• We can no longer pass through the precomputed underlying object to aliasCheck(). This is not a major concern, because nowadays getUnderlyingObject() is quite cheap.
• Results from other AA providers are no longer cached inside BasicAA. The way this worked was already a bit iffy, in that a result could be cached, but if it was MayAlias, we'd still end up re-querying other providers anyway. If we want to cache non-BasicAA results, we should do that in a more principled manner.

In any case, despite those tradeoffs, this works out to be a decent compile-time improvment: https://llvm-compile-time-tracker.com/compare.php?from=1a7a9efec3cf872dcf3e1a6e6fe39e797c4d9fc6&to=93127a4d7350261ed9ee2ccaa9c369eda2b60198&stat=instructions I think it also simplifies the mental model of how BasicAA works. It took me quite a while to fully understand how these things interact.

[asbirlea]

This looks like a nice approach to clean up the recursion, thank you for working on this!

The issue I'd like to bring up is what is the impact on the actual AA results provided with this change. For compile time this is a clear gain, even if small.
But for run time, I'm seeing a regression of 22% in singlesource/dhrystone_fldry (optimized build on haswell), and a 31% on another non-public benchmark.
I'm also seeing a few nice gains, which may offset these regressions. So I'm trying to understand here, what's the difference in processing that leads to these discrepancies?

[nikic]

In D90094#2369633, @asbirlea wrote:

The issue I'd like to bring up is what is the impact on the actual AA results provided with this change. For compile time this is a clear gain, even if small.
But for run time, I'm seeing a regression of 22% in singlesource/dhrystone_fldry (optimized build on haswell), and a 31% on another non-public benchmark.
I'm also seeing a few nice gains, which may offset these regressions. So I'm trying to understand here, what's the difference in processing that leads to these discrepancies?

Thanks for running those tests! I'm trying to reproduce the Dhrystone fldry results, but wasn't able to produce a binary hash difference before/after this patch after trying various flag combinations (including -fexperimental-new-pass-manager and -farch=haswell). Would it be possible to share the CMake configuration that is being used?

[nikic]

I've been staring at this code for a while, but can't spot the pathway which would produce different results. At least under the assumption that BasicAA is the first AA provider, which is the case for standard pipelines.

I've also tried to collect some AliasResults stats (using this hack: https://gist.github.com/nikic/101258f96b9973d63ab2fb92acbca028) in the hope that I can find a difference somewhere, but came up empty.

[nikic]

Strip pointer casts in GlobalsModRef. This *might* be the cause for observed differences, as previously the call from BasicAA would have been performed with casts stripped.

[nikic]

Rebase

[nikic]

Rebase

[dmgreen]

Hello. I tried running our downstream benchmarks with this patch and it did not appear to have any effect, either in performance or codesize. (That doesn't mean that nothing is effected, but it's at least a good sign).

[asbirlea]

lgtm.
Runtime impact results look good.

[nikic]

Thank you @dmgreen and @asbirlea for testing!

[rnk]

I reverted this, it caused crashes while compiling harfbuzz in Chromium: https://bugs.chromium.org/p/chromium/issues/detail?id=1167305

I have the reproducer and am starting creduce soon.

[rnk]

CReduce on plain C code is lightning fast, no template goo grind away. I got this reduced test case that crashes when this patch is applied:

char b, c;
void d(char *e, char *__restrict h, long j) {
  char *a = e + j;
  for (; e < a; e++, h++)
    b = *e, *e = *h;
}
int f;
char *g;
void m(long e) {
  char *i, *k;
  char l;
  g = i = k = &l;
  while (k)
    for (; i < k;) {
      if (i)
        d(g, i, e);
      g += e;
      if (f) {
        d(k, &c, e);
        i += e;
      }
    }
}

Compile like so:
clang -cc1 -triple aarch64-unknown-linux-android21 -O3 -emit-llvm hb-ot-map-6508fc.reduced.cpp

[nikic]

@rnk Thanks the the reproducer! Unfortunately I'm not seeing the crash. I'm at a1be47b4771467998d7549dcd1b9f9cebdaa9af9 directly before your revert using a Release+Asserts build.

[rnk]

I see. Maybe ASLR matters? I have the full stack trace if it helps:
https://reviews.llvm.org/P8253

[nikic]

@rnk Sorry, I got my binaries mixed up again... I can reproduce the crash now.

[nikic]

I've fixed the issue in b1c2f1282a237e9bc60f1b0020bc7535ca019739 and reapplied this change. The problem was introduced by D91936 and exposed here.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
                        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,
-                       const Value *UnderV2, AAQueryInfo &AAQI);
+                       AAQueryInfo &AAQI);
 
   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
                           const AAMDNodes &SIAAInfo, const Value *V2,
                           LocationSize V2Size, const AAMDNodes &V2AAInfo,
-                          const Value *UnderV2, AAQueryInfo &AAQI);
+                          AAQueryInfo &AAQI);
 
   AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
                          const AAMDNodes &V1AATag, const Value *V2,
                          LocationSize V2Size, const AAMDNodes &V2AATag,
-                         AAQueryInfo &AAQI, const Value *O1 = nullptr,
-                         const Value *O2 = nullptr);
+                         AAQueryInfo &AAQI);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class BasicAA : public AnalysisInfoMixin<BasicAA> {
   friend AnalysisInfoMixin<BasicAA>;
 
   static AnalysisKey Key;
 

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.");
-
-  // If we have a directly cached entry for these locations, we have recursed
-  // through this once, so just return the cached results. Notably, when this
-  // happens, we don't clear the cache.
-  AAQueryInfo::LocPair Locs(LocA, LocB);
-  if (Locs.first.Ptr > Locs.second.Ptr)
-    std::swap(Locs.first, Locs.second);
-  auto CacheIt = AAQI.AliasCache.find(Locs);
-  if (CacheIt != AAQI.AliasCache.end())
-    return CacheIt->second;
-
-  AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
-                                 LocB.Size, LocB.AATags, AAQI);
-
-  assert(VisitedPhiBBs.empty());
-  return Alias;
+  return aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, LocB.Size,
+                    LocB.AATags, 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.
AliasResult BasicAAResult::aliasGEP(
   // derived pointer.
   if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
     // Check for the GEP base being at a negative offset, this time in the other
     // direction.
     if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
         isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
       return NoAlias;
     // Do the base pointers alias?
-    AliasResult BaseAlias =
-        aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(),
-                   UnderlyingV2, LocationSize::unknown(), AAMDNodes(), AAQI);
+    AliasResult BaseAlias = getBestAAResults().alias(
+        MemoryLocation(UnderlyingV1), MemoryLocation(UnderlyingV2), AAQI);
 
     // For GEPs with identical sizes and offsets, we can preserve the size
     // and AAInfo when performing the alias check on the underlying objects.
     if (BaseAlias == MayAlias && V1Size == V2Size &&
         GEP1BaseOffset == GEP2BaseOffset &&
         DecompGEP1.VarIndices == DecompGEP2.VarIndices &&
         !GEP1MaxLookupReached && !GEP2MaxLookupReached) {
-      AliasResult PreciseBaseAlias = aliasCheck(
-          UnderlyingV1, V1Size, V1AAInfo, UnderlyingV2, V2Size, V2AAInfo, AAQI);
+      AliasResult PreciseBaseAlias = getBestAAResults().alias(
+          MemoryLocation(UnderlyingV1, V1Size, V1AAInfo),
+          MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI);
       if (PreciseBaseAlias == NoAlias)
         return NoAlias;
     }
 
     // If we get a No or May, then return it immediately, no amount of analysis
     // will improve this situation.
     if (BaseAlias != MustAlias) {
       assert(BaseAlias == NoAlias || BaseAlias == MayAlias);
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
     // Check to see if these two pointers are related by the getelementptr
     // instruction.  If one pointer is a GEP with a non-zero index of the other
     // pointer, we know they cannot alias.
 
     // If both accesses are unknown size, we can't do anything useful here.
     if (V1Size == LocationSize::unknown() && V2Size == LocationSize::unknown())
       return MayAlias;
 
-    AliasResult R = aliasCheck(UnderlyingV1, LocationSize::unknown(),
-                               AAMDNodes(), V2, LocationSize::unknown(),
-                               V2AAInfo, AAQI, nullptr, UnderlyingV2);
+    AliasResult R = getBestAAResults().alias(
+        MemoryLocation(UnderlyingV1),
+        MemoryLocation(V2, LocationSize::unknown(), V2AAInfo), AAQI);
     if (R != MustAlias) {
       // If V2 may alias GEP base pointer, conservatively returns MayAlias.
       // If V2 is known not to alias GEP base pointer, then the two values
       // cannot alias per GEP semantics: "Any memory access must be done through
       // a pointer value associated with an address range of the memory access,
       // otherwise the behavior is undefined.".
       assert(R == NoAlias || R == MayAlias);
       return R;
if ((A == PartialAlias && B == MustAlias) ||
       (B == PartialAlias && A == MustAlias))
     return PartialAlias;
   // 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 *UnderV2, AAQueryInfo &AAQI) {
+                           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 =
-          aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, SI2->getTrueValue(),
-                     V2Size, V2AAInfo, AAQI);
+      AliasResult Alias = getBestAAResults().alias(
+          MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo),
+          MemoryLocation(SI2->getTrueValue(), V2Size, V2AAInfo), AAQI);
       if (Alias == MayAlias)
         return MayAlias;
-      AliasResult ThisAlias =
-          aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
-                     SI2->getFalseValue(), V2Size, V2AAInfo, AAQI);
+      AliasResult ThisAlias = getBestAAResults().alias(
+          MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo),
+          MemoryLocation(SI2->getFalseValue(), V2Size, V2AAInfo), 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 = aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(),
-                                 SISize, SIAAInfo, AAQI, UnderV2);
+  AliasResult Alias = getBestAAResults().alias(
+      MemoryLocation(V2, V2Size, V2AAInfo),
+      MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo), AAQI);
   if (Alias == MayAlias)
     return MayAlias;
 
-  AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(),
-                                     SISize, SIAAInfo, AAQI, UnderV2);
+  AliasResult ThisAlias = getBestAAResults().alias(
+      MemoryLocation(V2, V2Size, V2AAInfo),
+      MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo), 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 *UnderV2, AAQueryInfo &AAQI) {
+                                    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()) {
       AAQueryInfo::LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
                                 MemoryLocation(V2, V2Size, V2AAInfo));
       if (PN > V2)
if (PN2->getParent() == PN->getParent()) {
         auto CacheIt = AAQI.AliasCache.find(Locs);
         assert((CacheIt != AAQI.AliasCache.end()) &&
                "There must exist an entry for the phi node");
         OrigAliasResult = CacheIt->second;
         CacheIt->second = NoAlias;
       }
 
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
-        AliasResult ThisAlias =
-            aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
-                       PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
-                       V2Size, V2AAInfo, AAQI);
+        AliasResult ThisAlias = getBestAAResults().alias(
+            MemoryLocation(PN->getIncomingValue(i), PNSize, PNAAInfo),
+            MemoryLocation(
+                PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size,
+                V2AAInfo), AAQI);
         Alias = MergeAliasResults(ThisAlias, Alias);
         if (Alias == MayAlias)
           break;
       }
 
       // Reset if speculation failed.
       if (Alias != NoAlias)
         AAQI.updateResult(Locs, OrigAliasResult);
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;
   AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
 
-  AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize,
-                                 PNAAInfo, *UseAAQI, UnderV2);
+  AliasResult Alias = getBestAAResults().alias(
+      MemoryLocation(V2, V2Size, V2AAInfo),
+      MemoryLocation(V1Srcs[0], PNSize, PNAAInfo), *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 = aliasCheck(V2, V2Size, V2AAInfo, V, PNSize,
-                                       PNAAInfo, *UseAAQI, UnderV2);
+    AliasResult ThisAlias = getBestAAResults().alias(
+        MemoryLocation(V2, V2Size, V2AAInfo),
+        MemoryLocation(V, PNSize, PNAAInfo), *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, const Value *O1,
-                                      const Value *O2) {
+                                      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->stripPointerCastsAndInvariantGroups();
   V2 = V2->stripPointerCastsAndInvariantGroups();
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // reach the value.
   if (isValueEqualInPotentialCycles(V1, V2))
     return MustAlias;
 
   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
     return NoAlias; // Scalars cannot alias each other
 
   // Figure out what objects these things are pointing to if we can.
-  if (O1 == nullptr)
-    O1 = getUnderlyingObject(V1, MaxLookupSearchDepth);
-
-  if (O2 == nullptr)
-    O2 = getUnderlyingObject(V2, MaxLookupSearchDepth);
+  const Value *O1 = getUnderlyingObject(V1, MaxLookupSearchDepth);
+  const Value *O2 = getUnderlyingObject(V2, MaxLookupSearchDepth);
 
   // Null values in the default address space don't point to any object, so they
   // don't alias any other pointer.
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
     if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
       return NoAlias;
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
     if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
     AliasResult Result =
         aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI);
     if (Result != MayAlias)
       return AAQI.updateResult(Locs, Result);
   }
 
   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
     AliasResult Result =
-        aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI);
+        aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
     if (Result != MayAlias)
       return AAQI.updateResult(Locs, Result);
   } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) {
     AliasResult Result =
-        aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI);
+        aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI);
     if (Result != MayAlias)
       return AAQI.updateResult(Locs, Result);
   }
 
   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
     AliasResult Result =
-        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI);
+        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
     if (Result != MayAlias)
       return AAQI.updateResult(Locs, Result);
   } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) {
     AliasResult Result =
-        aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI);
+        aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI);
     if (Result != MayAlias)
       return AAQI.updateResult(Locs, 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)
     if (V1Size.isPrecise() && V2Size.isPrecise() &&
         (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) ||
          isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation)))
       return AAQI.updateResult(Locs, PartialAlias);
 
-  // Recurse back into the best AA results we have, potentially with refined
-  // memory locations. We have already ensured that BasicAA has a MayAlias
-  // cache result for these, so any recursion back into BasicAA won't loop.
-  AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second, AAQI);
-  return AAQI.updateResult(Locs, Result);
+  return MayAlias;
 }
 
 /// Check whether two Values can be considered equivalent.
 ///
 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
 /// they can not be part of a cycle in the value graph by looking at all
 /// visited phi nodes an making sure that the phis cannot reach the value. We
 /// have to do this because we are looking through phi nodes (That is we say