[BasicAA] Cache nonEscapingLocalObjects for alias() calls.

[asbirlea]

Summary

Use a small cache for Values tested by nonEscapingLocalObject().
Since the calls to PointerMayBeCaptured are fairly expensive, this saves
a good amount of compile time for anything relying heavily on
BasicAA.alias() calls.

This uses the same approach as the AliasCache, i.e. the cache is reset
after each alias() call. The cache is not used or updated by modRefInfo
calls since it's harder to know when to reset the cache.

Testcases that show improvements with this patch are too large to
include. Example compile time improvement: 7s to 6s.

[chandlerc]

lib/Analysis/BasicAliasAnalysis.cpp

122–126

Can this function ever be re-entered? It seems unlikely given the structure.

If not, hoist the CacheIt iterator out, use insert, and then update it below rather than doing another lookup?

154–157

Why not cache this too?

[asbirlea]

Address comments.

[asbirlea]

Also wondered if the duplicated 4 lines are worth adding a lambda. Didn't seem worth it, but if you feel differently, I'll be happy to update it.

lib/Analysis/BasicAliasAnalysis.cpp

122–126

IIUC, insert doesn't do a lookup. So using insert below (instead of []) should be equivalent to your suggestion? We are guaranteed we need to insert if we reached that point..

154–157

I debated between sinking the cache search into each of the above ifs, or caching this.

Performance-wise, I see no difference between the cache search on all queries vs the checks inside the above ifs. So, sure, let's cache this too :)

If other folks find that querying the cache is more expensive when all conditions (isa+isNoAliasCall+ dyn_cast+attributes check) are false, then I can refactor this.

[chandlerc]

Just think we can poke the map a bit better here.

lib/Analysis/BasicAliasAnalysis.cpp

122–126

Er, insert does do a lookup?

auto CacheIt;
if (IsCapturedCache) {
  bool Inserted;
  std::tie(CacheIt, Inserted) = IsCapturedCache->insert({V, false});
  if (!Inserted)
    // Found cached result, return it!
    return CacheIt->second;
}
...
bool Ret = !PointerMayBeCaptured(...);
if (IsCapturedCache)
  CacheIt->second = Ret;
return Ret;

This kind of code pattern should do a single lookup into the map instead of doing two.

154–157

Sure, but will have to pull this all the way before the initial query to the cache. =D

Anyways, this makes sense to me.

[asbirlea]

Address comment.

lib/Analysis/BasicAliasAnalysis.cpp

122–126

Ah, you're right! Not sure why I was thinking that if *I* know the value is not in the set, the *set* will magically know too...

Thanks, updated.

[chandlerc]

LGTM!

include/llvm/Analysis/BasicAliasAnalysis.h

struct DecomposedGEP {
     // Scaled variable (non-constant) indices.
     SmallVector<VariableGEPIndex, 4> VarIndices;
   };
 
   /// Track alias queries to guard against recursion.
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheTy AliasCache;
+  using IsCapturedCacheTy = SmallDenseMap<const Value *, bool, 8>;
+  IsCapturedCacheTy IsCapturedCache;
 
   /// Tracks phi nodes we have visited.
   ///
   /// When interpret "Value" pointer equality as value equality we need to make
   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
   /// come from different "iterations" of a cycle and see different values for
   /// the same "Value" pointer.
   ///

lib/Analysis/BasicAliasAnalysis.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // Useful predicates
 //===----------------------------------------------------------------------===//
 
 /// Returns true if the pointer is to a function-local object that never
 /// escapes from the function.
-static bool isNonEscapingLocalObject(const Value *V) {
+static bool isNonEscapingLocalObject(
+    const Value *V,
+    SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr) {
+  if (IsCapturedCache) {
+    auto CacheIt = IsCapturedCache->find(V);
+    if (CacheIt != IsCapturedCache->end())
+      return CacheIt->second;
+  }
+
   // If this is a local allocation, check to see if it escapes.
-  if (isa<AllocaInst>(V) || isNoAliasCall(V))
+  if (isa<AllocaInst>(V) || isNoAliasCall(V)) {
     // Set StoreCaptures to True so that we can assume in our callers that the
     // pointer is not the result of a load instruction. Currently
     // PointerMayBeCaptured doesn't have any special analysis for the
     // StoreCaptures=false case; if it did, our callers could be refined to be
     // more precise.
-    return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
+    auto Ret = !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
+    if (IsCapturedCache)
+      IsCapturedCache->insert({V, Ret});
+    return Ret;
+  }
 
   // If this is an argument that corresponds to a byval or noalias argument,
   // then it has not escaped before entering the function.  Check if it escapes
   // inside the function.
   if (const Argument *A = dyn_cast<Argument>(V))
-    if (A->hasByValAttr() || A->hasNoAliasAttr())
+    if (A->hasByValAttr() || A->hasNoAliasAttr()) {
       // Note even if the argument is marked nocapture, we still need to check
       // for copies made inside the function. The nocapture attribute only
       // specifies that there are no copies made that outlive the function.
-      return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
+      auto Ret = !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
+      if (IsCapturedCache)
+        IsCapturedCache->insert({V, Ret});
+      return Ret;
+    }
 
+  if (IsCapturedCache)
+    IsCapturedCache->insert({V, false});
   return false;
 }
 
 /// Returns true if the pointer is one which would have been considered an
 /// escape by isNonEscapingLocalObject.
 static bool isEscapeSource(const Value *V) {
   if (isa<CallBase>(V))
     return true;
 
AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
 
   AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
                                  LocB.Size, LocB.AATags);
   // AliasCache rarely has more than 1 or 2 elements, always use
   // shrink_and_clear so it quickly returns to the inline capacity of the
   // SmallDenseMap if it ever grows larger.
   // FIXME: This should really be shrink_to_inline_capacity_and_clear().
   AliasCache.shrink_and_clear();
+  IsCapturedCache.shrink_and_clear();
   VisitedPhiBBs.clear();
   return Alias;
 }
 
 /// 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
if (O1 != O2) {
     // non-escaping local object within the same function, then we know the
     // object couldn't escape to a point where the call could return it.
     //
     // Note that if the pointers are in different functions, there are a
     // variety of complications. A call with a nocapture argument may still
     // temporary store the nocapture argument's value in a temporary memory
     // location if that memory location doesn't escape. Or it may pass a
     // nocapture value to other functions as long as they don't capture it.
-    if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
+    if (isEscapeSource(O1) && isNonEscapingLocalObject(O2, &IsCapturedCache))
       return NoAlias;
-    if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
+    if (isEscapeSource(O2) && isNonEscapingLocalObject(O1, &IsCapturedCache))
       return NoAlias;
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
   bool NullIsValidLocation = NullPointerIsDefined(&F);
   if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI,
                                                  NullIsValidLocation)) ||