[TypeBasedAliasAnalysis] Cache TBAA results in BatchAA.

[asbirlea]

Summary

Add cached TBAA results to the AAQueryInfo, to be used when using BatchAA.
Currently this is used wen enabling MemorySSA, during MemorySSA build.

include/llvm/Analysis/AliasAnalysis.h

 public:
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheT = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheT AliasCache;
 
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   IsCapturedCacheT IsCapturedCache;
 
-  AAQueryInfo() : AliasCache(), IsCapturedCache() {}
+  using MDNodePair = std::pair<const MDNode *, const MDNode *>;
+  using TBAACacheT = SmallDenseMap<MDNodePair, bool, 8>;
+  TBAACacheT TBAACache;
+
+  AAQueryInfo() : AliasCache(), IsCapturedCache(), TBAACache() {}
 };
 
 class BatchAAResults;
 
 class AAResults {
 public:
   // Make these results default constructable and movable. We have to spell
   // these out because MSVC won't synthesize them.

include/llvm/Analysis/TypeBasedAliasAnalysis.h

public:
   FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
   FunctionModRefBehavior getModRefBehavior(const Function *F);
   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
                            AAQueryInfo &AAQI);
   ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                            AAQueryInfo &AAQI);
 
 private:
-  bool Aliases(const MDNode *A, const MDNode *B) const;
+  bool Aliases(const MDNode *A, const MDNode *B, AAQueryInfo &AAQI);
   bool PathAliases(const MDNode *A, const MDNode *B) const;
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class TypeBasedAA : public AnalysisInfoMixin<TypeBasedAA> {
   friend AnalysisInfoMixin<TypeBasedAA>;
 
   static AnalysisKey Key;

lib/Analysis/TypeBasedAliasAnalysis.cpp

 
 AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
                                      const MemoryLocation &LocB,
                                      AAQueryInfo &AAQI) {
   if (!EnableTBAA)
     return AAResultBase::alias(LocA, LocB, AAQI);
 
   // If accesses may alias, chain to the next AliasAnalysis.
-  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
+  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA, AAQI))
     return AAResultBase::alias(LocA, LocB, AAQI);
 
   // Otherwise return a definitive result.
   return NoAlias;
 }
 
 bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
                                                AAQueryInfo &AAQI,

 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call,
                                             const MemoryLocation &Loc,
                                             AAQueryInfo &AAQI) {
   if (!EnableTBAA)
     return AAResultBase::getModRefInfo(Call, Loc, AAQI);
 
   if (const MDNode *L = Loc.AATags.TBAA)
     if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
-      if (!Aliases(L, M))
+      if (!Aliases(L, M, AAQI))
         return ModRefInfo::NoModRef;
 
   return AAResultBase::getModRefInfo(Call, Loc, AAQI);
 }
 
 ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1,
                                             const CallBase *Call2,
                                             AAQueryInfo &AAQI) {
   if (!EnableTBAA)
     return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
 
   if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
     if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
-      if (!Aliases(M1, M2))
+      if (!Aliases(M1, M2, AAQI))
         return ModRefInfo::NoModRef;
 
   return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
 }
 
 bool MDNode::isTBAAVtableAccess() const {
   if (!isStructPathTBAA(this)) {
     if (getNumOperands() < 1)
bool MDNode::isTBAAVtableAccess() const {
   TBAAStructTypeNode AccessType(Tag.getAccessType());
   if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
     if (Id->getString() == "vtable pointer")
       return true;
   return false;
 }
 
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
-                            const MDNode **GenericTag = nullptr);
+                            const MDNode **GenericTag = nullptr,
+                            AAQueryInfo *AAQI = nullptr);
 
 MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
   const MDNode *GenericTag;
   matchAccessTags(A, B, &GenericTag);
   return const_cast<MDNode*>(GenericTag);
 }
 
 static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
 
   return false;
 }
 
 /// matchTags - Return true if the given couple of accesses are allowed to
 /// overlap. If \arg GenericTag is not null, then on return it points to the
 /// most generic access descriptor for the given two.
 static bool matchAccessTags(const MDNode *A, const MDNode *B,
-                            const MDNode **GenericTag) {
+                            const MDNode **GenericTag, AAQueryInfo *AAQI) {
+  if (GenericTag)
+    assert(!AAQI && "Cannot use BatchAA in TBAA when doing updates");
+
   if (A == B) {
     if (GenericTag)
       *GenericTag = A;
     return true;
   }
 
   // Accesses with no TBAA information may alias with any other accesses.
   if (!A || !B) {
     if (GenericTag)
       *GenericTag = nullptr;
     return true;
   }
 
+  std::pair<AAQueryInfo::TBAACacheT::iterator, bool> Pair;
+  if (AAQI) {
+    AAQueryInfo::MDNodePair MDNodes(A, B);
+    Pair = AAQI->TBAACache.insert(std::make_pair(MDNodes, true));
+    if (!Pair.second)
+      return Pair.first->second;
+  }
+
   // Verify that both input nodes are struct-path aware.  Auto-upgrade should
   // have taken care of this.
   assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
   assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
 
   TBAAStructTagNode TagA(A), TagB(B);
   const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
                                                 TagB.getAccessType());
 
   // If the final access types have different roots, they're part of different
   // potentially unrelated type systems, so we must be conservative.
   if (!CommonType) {
     if (GenericTag)
       *GenericTag = nullptr;
     return true;
   }
 
   // If one of the accessed objects may be a subobject of the other, then such
   // accesses may alias.
   bool MayAlias;
   if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
                                CommonType, GenericTag, MayAlias) ||
       mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
-                               CommonType, GenericTag, MayAlias))
+                               CommonType, GenericTag, MayAlias)) {
+    if (AAQI)
+      Pair.first->second = MayAlias;
     return MayAlias;
+  }
 
   // Otherwise, we've proved there's no alias.
   if (GenericTag)
     *GenericTag = createAccessTag(CommonType);
+
+  if (AAQI)
+    Pair.first->second = false;
   return false;
 }
 
 /// Aliases - Test whether the access represented by tag A may alias the
 /// access represented by tag B.
-bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
-  return matchAccessTags(A, B);
+bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B,
+                                AAQueryInfo &AAQI) {
+  return matchAccessTags(A, B, nullptr, &AAQI);
 }
 
 AnalysisKey TypeBasedAA::Key;
 
 TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
   return TypeBasedAAResult();
 }