[BasicAA] Add depth limit

[nikic]

Summary

This patch adds a depth limit for the recursive alias analysis queries in BasicAA. Unfortunately, this is pretty tricky, because we need to think about how this interacts with BatchAA. Just doing a naive cutoff means that BatchAA can produce worse or better results depending on the order of queries, which is something we want to avoid. For this reason, this patch tracks the starting depth and maximum depth for cache entries, to determine whether a cached result can be used at a given depth.

For the depth limit of 8 used here, we get the following stats differences at O3:

aa.NumMayAlias | 5010256 | 5010623
aa.NumNoAlias | 27200820 | 27200306

This is also a minor compile-time regression: https://llvm-compile-time-tracker.com/compare.php?from=20cb6c7cebb5a3566640a9bf0da4729993ce6020&to=5e9effe146ed5d2a3934484db2493ffd66b0b5df&stat=instructions You can also see that with ThinLTO mafft regresses (0.87% codesize increase).

This addresses https://bugs.llvm.org/show_bug.cgi?id=49151, where BasicAA recurses enough to overflow the stack. Possibly D92401 could be reapplied, as it ran into exponential complexity in some cases.

[lebedev.ri]

Since this is (only?) about avoiding stack overflows (with which stack size?),
i'd think we should go with some much safer and less controversial value;
16, and even 64 should be plenty good still.

[nikic]

@lebedev.ri As mentioned in the summary, this is not just about stack overflows, but also about exponential queries, with an eye on D92401. The restriction on phi-of-phis without PhiValues analysis is also something that may be relaxed if we have sensible cutoffs. I would expect those things to be much more valuable in terms of analysis power than the ability to handle very deep queries.

Though now that I think on it, it might make more sense to restrict the total number of recursive queries rather than the query depth in particular, which could allow either a deep linear query, or a shallow branching one.

If we want to address stack overflows only (which may well make sense as an intermediate step), then it would probably be good enough to introduce a cutoff at a very high depth (like 512) and not bother with BatchAA consistency at all. The problematic test case reaches a maximum depth of 2507, which is a bit excessive :)

[nikic]

I plan to experiment a bit more in this area.

[asbirlea]

I tested this with 512 threshold and I'm only seeing a notable runtime regression in the testsuite multisource in MallocBench. I would not block on that, the stack overflow issue is a larger concern.

[nikic]

I've opened D96996 to just add a simple 512 depth limit, without all the extra complexity in this patch. That provides a quick fix for the immediate issue, while leaving a more comprehensive limit for later.

[reames]

In D96647#2561923, @nikic wrote:

Though now that I think on it, it might make more sense to restrict the total number of recursive queries rather than the query depth in particular, which could allow either a deep linear query, or a shallow branching one.

+1 to this thought. Are you working on a patch in this direction? I'm interested in seeing this resolved so that D92401 can be reapplied. I've got a test case that needs something along the lines of D92401 to get decent results, and I don't see any good workarounds. If you need help or motivated review, let me know.

[nikic]

While changing this to limit number of recursive queries instead of depth, I ran into some issues trying to keep BatchAA consistency. My assumption was that if a recursive query hits the limit and returns MayAlias, the whole query will be MayAlias. However, while this is true for BasicAA in isolation, it isn't true when combined with e.g. GlobalsAA. This means we can't accurately emulate the result of a query as if it weren't cached, or at least I don't see any obvious way. Possibly we need to relax this to "BatchAA should not produce worse results than AA" rather than "BatchAA should produce the same results as AA".

llvm/include/llvm/Analysis/AliasAnalysis.h

 /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
 /// The information stored in an `AAQueryInfo` is currently limitted to the
 /// caches used by BasicAA, but can further be extended to fit other AA needs.
 class AAQueryInfo {
 public:
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   struct CacheEntry {
     AliasResult Result;
+    /// The starting depth at which this entry has been cached.
+    unsigned Depth;
+    /// The maximum depth reached during the computation of this result.
+    unsigned MaxDepth;
     /// Number of times a NoAlias assumption has been used.
     /// 0 for assumptions that have not been used, -1 for definitive results.
     int NumAssumptionUses;
     /// Whether this is a definitive (non-assumption) result.
     bool isDefinitive() const { return NumAssumptionUses < 0; }
   };
   using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>;
   AliasCacheT AliasCache;
 
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   IsCapturedCacheT IsCapturedCache;
 
-  /// Query depth used to distinguish recursive queries.
+  /// Current query depth.
   unsigned Depth = 0;
+  /// Maximum depth reached in recursive queries.
+  unsigned MaxDepth = 0;
 
   /// How many active NoAlias assumption uses there are.
   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() : AliasCache(), IsCapturedCache() {}
 
   /// 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;
     NewAAQI.Depth = Depth;
+    NewAAQI.MaxDepth = MaxDepth;
     return NewAAQI;
   }
 };
 
 class BatchAAResults;
 
 class AAResults {
 public:

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
 
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
+/// Maximum depth of recursive alias analysis queries.
+static const unsigned MaxQueryDepth = 8;
+
 // The max limit of the search depth in DecomposeGEPExpression() and
 // getUnderlyingObject(), both functions need to use the same search
 // depth otherwise the algorithm in aliasGEP will assert.
 static const unsigned MaxLookupSearchDepth = 6;
 
 bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
   // 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);
+  AAQI.MaxDepth = UseAAQI->MaxDepth;
 
   // 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);
+    AAQI.MaxDepth = UseAAQI->MaxDepth;
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == MayAlias)
       break;
   }
 
   return Alias;
 }
 
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   if ((isObjectSmallerThan(
           O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
           TLI, NullIsValidLocation)) ||
       (isObjectSmallerThan(
           O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL,
           TLI, NullIsValidLocation)))
     return NoAlias;
 
+  // Don't perform recursive queries if depth limit has been reached.
+  unsigned OrigMaxDepth = AAQI.MaxDepth;
+  AAQI.MaxDepth = AAQI.Depth;
+  if (AAQI.Depth > MaxQueryDepth)
+    return MayAlias;
+
   // If one the accesses may be before the accessed pointer, canonicalize this
   // by using unknown after-pointer sizes for both accesses. This is
   // equivalent, because regardless of which pointer is lower, one of them
   // will always came after the other, as long as the underlying objects aren't
   // disjoint. We do this so that the rest of BasicAA does not have to deal
   // with accesses before the base pointer, and to improve cache utilization by
   // merging equivalent states.
   if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) {
     V1Size = LocationSize::afterPointer();
     V2Size = LocationSize::afterPointer();
   }
 
   // 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));
   if (V1 > V2)
     std::swap(Locs.first, Locs.second);
   const auto &Pair = AAQI.AliasCache.try_emplace(
-      Locs, AAQueryInfo::CacheEntry{NoAlias, 0});
+      Locs, AAQueryInfo::CacheEntry{NoAlias, AAQI.Depth,
+                                    /* MaxDepth */ 0,
+                                    /* NumAssumptionUses */ 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;
     }
+
+    if (Entry.Depth < AAQI.Depth) {
+      // The query has been cached at a lower depth, which means that the
+      // result may be better than what we would get starting from the current
+      // depth. Using such a result would make AA query results order-dependent
+      // if BatchAA is used. Check whether we could compute this result from
+      // the current depth without reaching the limit. Otherwise return
+      // MayAlias, as we would definitely hit the limit.
+      if (AAQI.Depth + (Entry.MaxDepth - Entry.Depth) <= MaxQueryDepth)
+        return Entry.Result;
+      return MayAlias;
+    } else if (Entry.Depth > AAQI.Depth) {
+      // If the entry has been cached at a higher depth and hit the depth limit
+      // we might get a better result starting at a lower depth. Clear the old
+      // cache entry and try again.
+      if (Entry.MaxDepth <= MaxQueryDepth)
+        return Entry.Result;
+
+      Entry.Result = NoAlias;
+      Entry.Depth = AAQI.Depth;
+      Entry.NumAssumptionUses = 0;
+    } else {
+      // Cached at same depth, this result is certainly valid.
       return Entry.Result;
     }
+  }
 
   int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
   unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
   AliasResult Result = aliasCheckRecursive(V1, V1Size, V1AAInfo, V2, V2Size,
                                            V2AAInfo, 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)
     Result = MayAlias;
 
   // This is a definitive result now, when considered as a root query.
-  AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
   Entry.Result = Result;
+  Entry.MaxDepth = AAQI.MaxDepth;
   Entry.NumAssumptionUses = -1;
+  AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
+  AAQI.MaxDepth = std::max(AAQI.MaxDepth, OrigMaxDepth);
 
   // If the assumption has been disproven, remove any results that may have
   // been based on this assumption. Do this after the Entry updates above to
   // avoid iterator invalidation.
   if (AssumptionDisproven)
     while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults)
       AAQI.AliasCache.erase(AAQI.AssumptionBasedResults.pop_back_val());