[AliasAnalysis] Use batch AA in AliasSetTracker.

[asbirlea]

Summary

Make AliasSetTracker use an internal batch alias analysis.
With this patch, it is no longer correct to make IR changes and then add instructions to the AST.
The caching done in LICM is correct provided we create a new batch AA when reusing (moving) the AST from an inner loop (this is done with setAliasAnalysis).

[asbirlea]

Minor updates.

include/llvm/Analysis/AliasSetTracker.h

AliasSet *getForwardedTarget(AliasSetTracker &AST) {
     return Dest;
   }
 
   void removeFromTracker(AliasSetTracker &AST);
 
   void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
                   const AAMDNodes &AAInfo, bool KnownMustAlias = false,
                   bool SkipSizeUpdate = false);
-  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
+  void addUnknownInst(Instruction *I, BatchAAResults &AA);
 
   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     bool WasEmpty = UnknownInsts.empty();
     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
       if (UnknownInsts[i] == I) {
         UnknownInsts[i] = UnknownInsts.back();
         UnknownInsts.pop_back();
         --i; --e;  // Revisit the moved entry.
       }
     if (!WasEmpty && UnknownInsts.empty())
       dropRef(AST);
   }
 
 public:
   /// If the specified pointer "may" (or must) alias one of the members in the
   /// set return the appropriate AliasResult. Otherwise return NoAlias.
   AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
-                             const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
-  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
+                             const AAMDNodes &AAInfo, BatchAAResults &AA) const;
+  bool aliasesUnknownInst(const Instruction *Inst, BatchAAResults &AA) const;
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
   AS.print(OS);
   return OS;
 }
 
 class AliasSetTracker {
public:
     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
 
     ASTCallbackVH &operator=(Value *V);
   };
   /// Traits to tell DenseMap that tell us how to compare and hash the value
   /// handle.
   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
 
-  AliasAnalysis &AA;
+  std::unique_ptr<BatchAAResults> AA;
   MemorySSA *MSSA;
   Loop *L;
   ilist<AliasSet> AliasSets;
 
   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
                                   ASTCallbackVHDenseMapInfo>;
 
   // Map from pointers to their node
   PointerMapType PointerMap;
 
 public:
   /// Create an empty collection of AliasSets, and use the specified alias
   /// analysis object to disambiguate load and store addresses.
-  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
+  explicit AliasSetTracker(AliasAnalysis &aa) {
+    AA = make_unique<BatchAAResults>(aa);
+  }
   explicit AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l)
-      : AA(aa), MSSA(mssa), L(l) {}
+      : MSSA(mssa), L(l) {
+    AA = make_unique<BatchAAResults>(aa);
+  }
   ~AliasSetTracker() { clear(); }
 
   /// These methods are used to add different types of instructions to the alias
   /// sets. Adding a new instruction can result in one of three actions
   /// happening:
   ///
   ///   1. If the instruction doesn't alias any other sets, create a new set.
   ///   2. If the instruction aliases exactly one set, add it to the set
public:
 
   /// Return the alias set which contains the specified memory location.  If
   /// the memory location aliases two or more existing alias sets, will have
   /// the effect of merging those alias sets before the single resulting alias
   /// set is returned.
   AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
 
   /// Return the underlying alias analysis object used by this tracker.
-  AliasAnalysis &getAliasAnalysis() const { return AA; }
+  BatchAAResults &getAliasAnalysis() const { return *AA.get(); }
+  void setAliasAnalysis(AliasAnalysis &AA) {
+    this->AA = make_unique<BatchAAResults>(AA);
+  }
 
   /// This method is used to remove a pointer value from the AliasSetTracker
   /// entirely. It should be used when an instruction is deleted from the
   /// program to update the AST. If you don't use this, you would have dangling
   /// pointers to deleted instructions.
   void deleteValue(Value *PtrVal);
 
   /// This method should be used whenever a preexisting value in the program is

lib/Analysis/AliasSetTracker.cpp

void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
   // Update the alias and access types of this set...
   Access |= AS.Access;
   Alias  |= AS.Alias;
 
   if (Alias == SetMustAlias) {
     // Check that these two merged sets really are must aliases.  Since both
     // used to be must-alias sets, we can just check any pointer from each set
     // for aliasing.
-    AliasAnalysis &AA = AST.getAliasAnalysis();
+    BatchAAResults &AA = AST.getAliasAnalysis();
     PointerRec *L = getSomePointer();
     PointerRec *R = AS.getSomePointer();
 
     // If the pointers are not a must-alias pair, this set becomes a may alias.
     if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
                  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
         MustAlias)
       Alias = SetMayAlias;
void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
                           LocationSize Size, const AAMDNodes &AAInfo,
                           bool KnownMustAlias, bool SkipSizeUpdate) {
   assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias())
     if (PointerRec *P = getSomePointer()) {
       if (!KnownMustAlias) {
-        AliasAnalysis &AA = AST.getAliasAnalysis();
+        BatchAAResults &AA = AST.getAliasAnalysis();
         AliasResult Result = AA.alias(
             MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
             MemoryLocation(Entry.getValue(), Size, AAInfo));
         if (Result != MustAlias) {
           Alias = SetMayAlias;
           AST.TotalMayAliasSetSize += size();
         }
         assert(Result != NoAlias && "Cannot be part of must set!");
void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
   assert(*PtrListEnd == nullptr && "End of list is not null?");
   // Entry points to alias set.
   addRef();
 
   if (Alias == SetMayAlias)
     AST.TotalMayAliasSetSize++;
 }
 
-void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
+void AliasSet::addUnknownInst(Instruction *I, BatchAAResults &AA) {
   if (UnknownInsts.empty())
     addRef();
   UnknownInsts.emplace_back(I);
 
   // Guards are marked as modifying memory for control flow modelling purposes,
   // but don't actually modify any specific memory location.
   using namespace PatternMatch;
   bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&

 }
 
 /// aliasesPointer - If the specified pointer "may" (or must) alias one of the
 /// members in the set return the appropriate AliasResult. Otherwise return
 /// NoAlias.
 ///
 AliasResult AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
                                      const AAMDNodes &AAInfo,
-                                     AliasAnalysis &AA) const {
+                                     BatchAAResults &AA) const {
   if (AliasAny)
     return MayAlias;
 
   if (Alias == SetMustAlias) {
     assert(UnknownInsts.empty() && "Illegal must alias set!");
 
     // If this is a set of MustAliases, only check to see if the pointer aliases
     // SOME value in the set.
for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
                 AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
           return MayAlias;
   }
 
   return NoAlias;
 }
 
 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
-                                  AliasAnalysis &AA) const {
+                                  BatchAAResults &AA) const {
 
   if (AliasAny)
     return true;
 
   assert(Inst->mayReadOrWriteMemory() &&
          "Instruction must either read or write memory.");
 
   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
                                                     bool &MustAliasAll) {
   AliasSet *FoundSet = nullptr;
   AliasResult AllAR = MustAlias;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
     if (Cur->Forward)
       continue;
 
-    AliasResult AR = Cur->aliasesPointer(Ptr, Size, AAInfo, AA);
+    AliasResult AR = Cur->aliasesPointer(Ptr, Size, AAInfo, *AA);
     if (AR == NoAlias)
       continue;
 
     AllAR =
         AliasResult(AllAR & AR); // Possible downgrade to May/Partial, even No
 
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &*Cur;
     } else {
       // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);
     }
   }
 
   MustAliasAll = (AllAR == MustAlias);
   return FoundSet;
 }
 
 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
-    if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
+    if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, *AA))
       continue;
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &*Cur;
     } else {
       // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);
     }
if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
     case Intrinsic::sideeffect:
       return;
     }
   }
   if (!Inst->mayReadOrWriteMemory())
     return; // doesn't alias anything
 
   if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
-    AS->addUnknownInst(Inst, AA);
+    AS->addUnknownInst(Inst, *AA);
     return;
   }
   AliasSets.push_back(new AliasSet());
-  AliasSets.back().addUnknownInst(Inst, AA);
+  AliasSets.back().addUnknownInst(Inst, *AA);
 }
 
 void AliasSetTracker::add(Instruction *I) {
   // Dispatch to one of the other add methods.
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     return add(LI);
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     return add(SI);
if (Call->onlyAccessesArgMemory()) {
         else if (isModSet(MRI))
           return AliasSet::ModAccess;
         else if (isRefSet(MRI))
           return AliasSet::RefAccess;
         else
           return AliasSet::NoAccess;
       };
 
-      ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(Call));
+      ModRefInfo CallMask = createModRefInfo(AA->getModRefBehavior(Call));
 
       // Some intrinsics are marked as modifying memory for control flow
       // modelling purposes, but don't actually modify any specific memory
       // location.
       using namespace PatternMatch;
       if (Call->use_empty() &&
           match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
         CallMask = clearMod(CallMask);
 
       for (auto IdxArgPair : enumerate(Call->args())) {
         int ArgIdx = IdxArgPair.index();
         const Value *Arg = IdxArgPair.value();
         if (!Arg->getType()->isPointerTy())
           continue;
         MemoryLocation ArgLoc =
             MemoryLocation::getForArgument(Call, ArgIdx, nullptr);
-        ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);
+        ModRefInfo ArgMask = AA->getArgModRefInfo(Call, ArgIdx);
         ArgMask = intersectModRef(CallMask, ArgMask);
         if (!isNoModRef(ArgMask))
           addPointer(ArgLoc, getAccessFromModRef(ArgMask));
       }
       return;
     }
 
   return addUnknown(I);
 }
 
 void AliasSetTracker::add(BasicBlock &BB) {
   for (auto &I : BB)
     add(&I);
 }
 
 void AliasSetTracker::add(const AliasSetTracker &AST) {
-  assert(&AA == &AST.AA &&
-         "Merging AliasSetTracker objects with different Alias Analyses!");
-
   // Loop over all of the alias sets in AST, adding the pointers contained
   // therein into the current alias sets.  This can cause alias sets to be
   // merged together in the current AST.
   for (const AliasSet &AS : AST) {
     if (AS.Forward)
       continue; // Ignore forwarding alias sets
 
     // If there are any call sites in the alias set, add them to this AST.

lib/Transforms/Scalar/LICM.cpp

for (Loop *InnerL : L->getSubLoops()) {
 
     if (CurAST) {
       // What if InnerLoop was modified by other passes ?
       // Once we've incorporated the inner loop's AST into ours, we don't need
       // the subloop's anymore.
       CurAST->add(*InnerAST);
     } else {
       CurAST = std::move(InnerAST);
+      CurAST->setAliasAnalysis(*AA);
     }
     LoopToAliasSetMap.erase(MapI);
   }
   if (!CurAST)
     CurAST = make_unique<AliasSetTracker>(*AA);
 
   // Add everything from the sub loops that are no longer directly available.
   for (Loop *InnerL : RecomputeLoops)

lib/Transforms/Scalar/LoopRerollPass.cpp

while (BaseIt != Uses.end() && RootIt != Uses.end()) {
         return false;
       }
 
       // Make sure that we don't alias with any instruction in the alias set
       // tracker. If we do, then we depend on a future iteration, and we
       // can't reroll.
       if (RootInst->mayReadFromMemory())
         for (auto &K : AST) {
-          if (K.aliasesUnknownInst(RootInst, *AA)) {
+          if (K.aliasesUnknownInst(RootInst, AST.getAliasAnalysis())) {
             LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
                               << *BaseInst << " vs. " << *RootInst
                               << " (depends on future store)\n");
             return false;
           }
         }
 
       // If we've past an instruction from a future iteration that may have

unittests/Analysis/AliasSetTrackerTest.cpp

TEST(AliasSetTracker, AliasUnknownInst) {
 
   // Directly test aliasesUnknownInst.
   // Now every call instruction should only alias one alias set.
   for (auto &Inst : *Test->begin()) {
     bool FoundAS = false;
     for (AliasSet &AS : AST) {
       if (!Inst.mayReadOrWriteMemory())
         continue;
-      if (!AS.aliasesUnknownInst(&Inst, AA))
+      if (!AS.aliasesUnknownInst(&Inst, AST.getAliasAnalysis()))
         continue;
       ASSERT_NE(FoundAS, true);
       FoundAS = true;
     }
   }
 }