Improve caching scheme in ProvenanceAnalysis.

[mzolotukhin]

Summary

ProvenanceAnalysis::related(A, B) currently memoizes its results, and on big
tests the cache grows too large, and we're spending most of the time
growing/looking through DenseMap.

This patch reduces the size of the cache by normalizing keys first: we do that
by calling GetUnderlyingObjCPtr on the input values. The results of
GetUnderlyingObjCPtr are also memoized in a separate cache.

The patch doesn't bring noticable changes to compile time on CTMark, however
significantly helps one of our internal tests.

[pete]

This all looks reasonable. Its a nice localized change to this pass. LGTM.

llvm/trunk/include/llvm/Analysis/ObjCARCAnalysisUtils.h

for (;;) {
     if (!IsForwarding(GetBasicARCInstKind(V)))
       break;
     V = cast<CallInst>(V)->getArgOperand(0);
   }
 
   return V;
 }
 
+/// A wrapper for GetUnderlyingObjCPtr used for results memoization.
+inline const Value *
+GetUnderlyingObjCPtrCached(const Value *V, const DataLayout &DL,
+                           DenseMap<const Value *, const Value *> &Cache) {
+  if (auto InCache = Cache.lookup(V))
+    return InCache;
+
+  return Cache[V] = GetUnderlyingObjCPtr(V, DL);
+}
+
 /// The RCIdentity root of a value \p V is a dominating value U for which
 /// retaining or releasing U is equivalent to retaining or releasing V. In other
 /// words, ARC operations on \p V are equivalent to ARC operations on \p U.
 ///
 /// We use this in the ARC optimizer to make it easier to match up ARC
 /// operations by always mapping ARC operations to RCIdentityRoots instead of
 /// pointers themselves.
 ///

llvm/trunk/lib/Transforms/ObjCARC/ProvenanceAnalysis.h

 class ProvenanceAnalysis {
   AliasAnalysis *AA;
 
   using ValuePairTy = std::pair<const Value *, const Value *>;
   using CachedResultsTy = DenseMap<ValuePairTy, bool>;
 
   CachedResultsTy CachedResults;
 
+  DenseMap<const Value *, const Value *> UnderlyingObjCPtrCache;
+
   bool relatedCheck(const Value *A, const Value *B, const DataLayout &DL);
   bool relatedSelect(const SelectInst *A, const Value *B);
   bool relatedPHI(const PHINode *A, const Value *B);
 
 public:
   ProvenanceAnalysis() = default;
   ProvenanceAnalysis(const ProvenanceAnalysis &) = delete;
   ProvenanceAnalysis &operator=(const ProvenanceAnalysis &) = delete;
 
   void setAA(AliasAnalysis *aa) { AA = aa; }
 
   AliasAnalysis *getAA() const { return AA; }
 
   bool related(const Value *A, const Value *B, const DataLayout &DL);
 
   void clear() {
     CachedResults.clear();
+    UnderlyingObjCPtrCache.clear();
   }
 };
 
 } // end namespace objcarc
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TRANSFORMS_OBJCARC_PROVENANCEANALYSIS_H

llvm/trunk/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp

static bool IsStoredObjCPointer(const Value *P) {
   } while (!Worklist.empty());
 
   // Everything checked out.
   return false;
 }
 
 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
                                       const DataLayout &DL) {
-  // Skip past provenance pass-throughs.
-  A = GetUnderlyingObjCPtr(A, DL);
-  B = GetUnderlyingObjCPtr(B, DL);
-
-  // Quick check.
-  if (A == B)
-    return true;
-
   // Ask regular AliasAnalysis, for a first approximation.
   switch (AA->alias(A, B)) {
   case NoAlias:
     return false;
   case MustAlias:
   case PartialAlias:
     return true;
   case MayAlias:
if (const SelectInst *S = dyn_cast<SelectInst>(B))
     return relatedSelect(S, A);
 
   // Conservative.
   return true;
 }
 
 bool ProvenanceAnalysis::related(const Value *A, const Value *B,
                                  const DataLayout &DL) {
+  A = GetUnderlyingObjCPtrCached(A, DL, UnderlyingObjCPtrCache);
+  B = GetUnderlyingObjCPtrCached(B, DL, UnderlyingObjCPtrCache);
+
+  // Quick check.
+  if (A == B)
+    return true;
+
   // Begin by inserting a conservative value into the map. If the insertion
   // fails, we have the answer already. If it succeeds, leave it there until we
   // compute the real answer to guard against recursive queries.
   if (A > B) std::swap(A, B);
   std::pair<CachedResultsTy::iterator, bool> Pair =
     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
   if (!Pair.second)
     return Pair.first->second;
 
   bool Result = relatedCheck(A, B, DL);
   CachedResults[ValuePairTy(A, B)] = Result;
   return Result;
 }