[AST] Make AliasSetTracker work on BatchAA

[nikic]

Summary

Switch AliasSetTracker to use BatchAAResults instead of AAResults. This means that AliasSetTracker can only be used on IR that does not change (at least without further justification). The last user of AST with changing IR was LICM and has since been removed. Everything else just needs it in a separate analysis phase.

The primary motivation for this change is to have a single BatchAA instance on which everything in AST works, which makes a followup patch simpler.

[nikic]

D137958 is the patch that makes use of this. Consistently using BatchAA and enabling it for the whole BatchAA instance was the nicest way I found to expose this functionality.

[reames]

I have no problem with the idea of the patch, but I think this needs to be split into two patches.

The first simply removes support for ASTs over mutating IR, and makes the API changes required. (Note the suggestion about asserting value handl inline.) This should land on it's own so that if we missed a remaining mutation point, we get a chance to smoke out the failure without reasoning about potential confusing AA results at the same time.

The second actually uses batch-aa.

llvm/lib/Analysis/AliasSetTracker.cpp

616–617

This bit really doesn't look right.

I suspect that the ASTCallbackVH should now be a AssertingVH. At a minimum, this needs to be a well written assert or fatal error, not an unreachable.

[nikic]

Split patch.

[nikic]

In D137955#3925704, @reames wrote:

I have no problem with the idea of the patch, but I think this needs to be split into two patches.

The first simply removes support for ASTs over mutating IR, and makes the API changes required. (Note the suggestion about asserting value handl inline.) This should land on it's own so that if we missed a remaining mutation point, we get a chance to smoke out the failure without reasoning about potential confusing AA results at the same time.

That's a good point! I've split the patch up into two parts now, and replaced the CallbackVH use with AssertVH as well.

[reames]

LGTM

[asbirlea]

+1 on making the AST only work on immutable IR.

The only nit from me: allow the constructor to receive AAResults and build the BatchAA instance internally? It would simplify most instantiation sites modified in the patch. It still makes sense to define the BatchAA in some cases (LoopReroll), but I don't see the purpose of keeping the instance in LoopAccessAnalysis. Downside: allocation - which might make it not worth it.

[asbirlea]

Missed the dependent patch on LoopAccessAnalysis, now it makes sense :-)

llvm/include/llvm/Analysis/AliasSetTracker.h

 #include "llvm/IR/ValueHandle.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <vector>
 
 namespace llvm {
 
-class AAResults;
 class AliasResult;
 class AliasSetTracker;
 class AnyMemSetInst;
 class AnyMemTransferInst;
 class BasicBlock;
 class BatchAAResults;
 class LoadInst;
 class raw_ostream;
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, AAResults &AA);
+  void addUnknownInst(Instruction *I, BatchAAResults &AA);
 
 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, 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 {
-  AAResults &AA;
+  BatchAAResults &AA;
   ilist<AliasSet> AliasSets;
 
   using PointerMapType = DenseMap<AssertingVH<Value>, AliasSet::PointerRec *>;
 
   // 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(AAResults &AA) : AA(AA) {}
+  explicit AliasSetTracker(BatchAAResults &AA) : AA(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.
-  AAResults &getAliasAnalysis() const { return AA; }
+  BatchAAResults &getAliasAnalysis() const { return AA; }
 
   using iterator = ilist<AliasSet>::iterator;
   using const_iterator = ilist<AliasSet>::const_iterator;
 
   const_iterator begin() const { return AliasSets.begin(); }
   const_iterator end()   const { return AliasSets.end(); }
 
   iterator begin() { return AliasSets.begin(); }

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolutionWrapperPass();
       llvm::Function::Create(nullptr, llvm::GlobalValue::ExternalLinkage)->viewCFGOnly();
       llvm::RGPassManager RGM;
       llvm::TargetLibraryInfoImpl TLII;
       llvm::TargetLibraryInfo TLI(TLII);
       llvm::AliasAnalysis AA(TLI);
-      llvm::AliasSetTracker X(AA);
+      llvm::BatchAAResults BAA(AA);
+      llvm::AliasSetTracker X(BAA);
       X.add(nullptr, llvm::LocationSize::beforeOrAfterPointer(),
             llvm::AAMDNodes()); // for -print-alias-sets
       (void) llvm::AreStatisticsEnabled();
       (void) llvm::sys::RunningOnValgrind();
     }
   } ForcePassLinking; // Force link by creating a global definition.
 }
 
 #endif

llvm/lib/Analysis/AliasSetTracker.cpp

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 != AliasResult::MustAlias) {
           Alias = SetMayAlias;
           AST.TotalMayAliasSetSize += size();
         }
         assert(Result != AliasResult::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) &&

 /// the pointer was found. MustAliasAll is updated to true/false if the pointer
 /// is found to MustAlias all the sets it merged.
 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
                                                     LocationSize Size,
                                                     const AAMDNodes &AAInfo,
                                                     bool &MustAliasAll) {
   AliasSet *FoundSet = nullptr;
   MustAliasAll = true;
-  BatchAAResults BatchAA(AA);
   for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
     if (AS.Forward)
       continue;
 
-    AliasResult AR = AS.aliasesPointer(Ptr, Size, AAInfo, BatchAA);
+    AliasResult AR = AS.aliasesPointer(Ptr, Size, AAInfo, AA);
     if (AR == AliasResult::NoAlias)
       continue;
 
     if (AR != AliasResult::MustAlias)
       MustAliasAll = false;
 
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &AS;
     } else {
       // Otherwise, we must merge the sets.
-      FoundSet->mergeSetIn(AS, *this, BatchAA);
+      FoundSet->mergeSetIn(AS, *this, AA);
     }
   }
 
   return FoundSet;
 }
 
 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
-  BatchAAResults BatchAA(AA);
   AliasSet *FoundSet = nullptr;
   for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
-    if (AS.Forward || !AS.aliasesUnknownInst(Inst, BatchAA))
+    if (AS.Forward || !AS.aliasesUnknownInst(Inst, AA))
       continue;
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &AS;
     } else {
       // Otherwise, we must merge the sets.
-      FoundSet->mergeSetIn(AS, *this, BatchAA);
+      FoundSet->mergeSetIn(AS, *this, AA);
     }
   }
   return FoundSet;
 }
 
 AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
 
   Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
AliasSet &AliasSetTracker::mergeAllAliasSets() {
   // Copy all instructions and pointers into a new set, and forward all other
   // sets to it.
   AliasSets.push_back(new AliasSet());
   AliasAnyAS = &AliasSets.back();
   AliasAnyAS->Alias = AliasSet::SetMayAlias;
   AliasAnyAS->Access = AliasSet::ModRefAccess;
   AliasAnyAS->AliasAny = true;
 
-  BatchAAResults BatchAA(AA);
   for (auto *Cur : ASVector) {
     // If Cur was already forwarding, just forward to the new AS instead.
     AliasSet *FwdTo = Cur->Forward;
     if (FwdTo) {
       Cur->Forward = AliasAnyAS;
       AliasAnyAS->addRef();
       FwdTo->dropRef(*this);
       continue;
     }
 
     // Otherwise, perform the actual merge.
-    AliasAnyAS->mergeSetIn(*Cur, *this, BatchAA);
+    AliasAnyAS->mergeSetIn(*Cur, *this, AA);
   }
 
   return *AliasAnyAS;
 }
 
 AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
                                       AliasSet::AccessLattice E) {
   AliasSet &AS = getAliasSetFor(Loc);
void AliasSetTracker::print(raw_ostream &OS) const {
   OS << "\n";
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
 LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
 #endif
 
 //===----------------------------------------------------------------------===//
 //                            AliasSetPrinter Pass
 //===----------------------------------------------------------------------===//
 
 AliasSetsPrinterPass::AliasSetsPrinterPass(raw_ostream &OS) : OS(OS) {}
 
 PreservedAnalyses AliasSetsPrinterPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
   auto &AA = AM.getResult<AAManager>(F);
-  AliasSetTracker Tracker(AA);
+  BatchAAResults BatchAA(AA);
+  AliasSetTracker Tracker(BatchAA);
   OS << "Alias sets for function '" << F.getName() << "':\n";
   for (Instruction &I : instructions(F))
     Tracker.add(&I);
   Tracker.print(OS);
   return PreservedAnalyses::all();
 }

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 public:
   /// Read or write access location.
   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
 
   AccessAnalysis(Loop *TheLoop, AAResults *AA, LoopInfo *LI,
                  MemoryDepChecker::DepCandidates &DA,
                  PredicatedScalarEvolution &PSE)
-      : TheLoop(TheLoop), AST(*AA), LI(LI), DepCands(DA), PSE(PSE) {}
+      : TheLoop(TheLoop), BAA(*AA), AST(BAA), LI(LI), DepCands(DA), PSE(PSE) {}
 
   /// Register a load  and whether it is only read from.
   void addLoad(MemoryLocation &Loc, Type *AccessTy, bool IsReadOnly) {
     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     AST.add(Ptr, LocationSize::beforeOrAfterPointer(), Loc.AATags);
     Accesses[MemAccessInfo(Ptr, false)].insert(AccessTy);
     if (IsReadOnly)
       ReadOnlyPtr.insert(Ptr);
private:
   const Loop *TheLoop;
 
   /// List of accesses that need a further dependence check.
   MemAccessInfoList CheckDeps;
 
   /// Set of pointers that are read only.
   SmallPtrSet<Value*, 16> ReadOnlyPtr;
 
+  /// Batched alias analysis results.
+  BatchAAResults BAA;
+
   /// An alias set tracker to partition the access set by underlying object and
   //intrinsic property (such as TBAA metadata).
   AliasSetTracker AST;
 
   LoopInfo *LI;
 
   /// Sets of potentially dependent accesses - members of one set share an
   /// underlying pointer. The set "CheckDeps" identfies which sets really need a

llvm/lib/Transforms/Scalar/LICM.cpp

for (const BasicBlock *BB : L->blocks())
     if (const auto *Accesses = MSSA->getBlockAccesses(BB))
       for (const auto &Access : *Accesses)
         if (const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
           Fn(MUD->getMemoryInst());
 }
 
 static SmallVector<SmallSetVector<Value *, 8>, 0>
 collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L) {
-  AliasSetTracker AST(*AA);
+  BatchAAResults BatchAA(*AA);
+  AliasSetTracker AST(BatchAA);
 
   auto IsPotentiallyPromotable = [L](const Instruction *I) {
     if (const auto *SI = dyn_cast<StoreInst>(I))
       return L->isLoopInvariant(SI->getPointerOperand());
     if (const auto *LI = dyn_cast<LoadInst>(I))
       return L->isLoopInvariant(LI->getPointerOperand());
     return false;
   };
collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L) {
   for (AliasSet &AS : AST)
     if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
       Sets.push_back(&AS);
 
   if (Sets.empty())
     return {}; // Nothing to promote...
 
   // Discard any sets for which there is an aliasing non-promotable access.
-  BatchAAResults BatchAA(*AA);
   foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
     if (AttemptingPromotion.contains(I))
       return;
 
     llvm::erase_if(Sets, [&](const AliasSet *AS) {
       return AS->aliasesUnknownInst(I, BatchAA);
     });
   });

llvm/lib/Transforms/Scalar/LoopRerollPass.cpp

for (auto &KV : Uses) {
     }
   }
 
   LLVM_DEBUG(for (auto &KV
                   : Uses) {
     dbgs() << "LRR: " << KV.second.find_first() << "\t" << *KV.first << "\n";
   });
 
+  BatchAAResults BatchAA(*AA);
   for (unsigned Iter = 1; Iter < Scale; ++Iter) {
     // In addition to regular aliasing information, we need to look for
     // instructions from later (future) iterations that have side effects
     // preventing us from reordering them past other instructions with side
     // effects.
     bool FutureSideEffects = false;
-    AliasSetTracker AST(*AA);
+    AliasSetTracker AST(BatchAA);
     // The map between instructions in f(%iv.(i+1)) and f(%iv).
     DenseMap<Value *, Value *> BaseMap;
 
     // Compare iteration Iter to the base.
     SmallInstructionSet Visited;
     auto BaseIt = nextInstr(0, Uses, Visited);
     auto RootIt = nextInstr(Iter, Uses, Visited);
     auto LastRootIt = Uses.begin();
while (BaseIt != Uses.end() && RootIt != Uses.end()) {
                           << " vs. " << *RootInst << " (prev. case overlap)\n");
         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()) {
-        BatchAAResults BatchAA(*AA);
         for (auto &K : AST) {
           if (K.aliasesUnknownInst(RootInst, BatchAA)) {
             LLVM_DEBUG(dbgs() << "LRR: iteration root match failed at "
                               << *BaseInst << " vs. " << *RootInst
                               << " (depends on future store)\n");
             return false;
           }
         }

llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp

bool LoopVersioningLICM::legalLoopStructure() {
   }
   return true;
 }
 
 /// Check memory accesses in loop and confirms it's good for
 /// LoopVersioningLICM.
 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
   // Loop over the body of this loop, construct AST.
-  AliasSetTracker AST(*AA);
+  BatchAAResults BAA(*AA);
+  AliasSetTracker AST(BAA);
   for (auto *Block : CurLoop->getBlocks()) {
     // Ignore blocks in subloops.
     if (LI.getLoopFor(Block) == CurLoop)
       AST.add(*Block);
   }
 
   // Memory check:
   // Transform phase will generate a versioned loop and also a runtime check to

llvm/unittests/Analysis/AliasSetTrackerTest.cpp

TEST(AliasSetTracker, AliasUnknownInst) {
   TargetLibraryInfo TLI(TLII);
   AAResults AA(TLI);
   TypeBasedAAResult TBAAR;
   AA.addAAResult(TBAAR);
 
   // Initialize the alias set tracker for the @test function.
   Function *Test = M->getFunction("test");
   ASSERT_NE(Test, nullptr);
-  AliasSetTracker AST(AA);
+  BatchAAResults BAA(AA);
+  AliasSetTracker AST(BAA);
   for (auto &BB : *Test)
     AST.add(BB);
   // There should be 2 disjoint alias sets. 1 from each call. 
   ASSERT_EQ((int)AST.getAliasSets().size(), 2);
 
   // Directly test aliasesUnknownInst.
   // Now every call instruction should only alias one alias set.
   BatchAAResults BatchAA(AA);

polly/include/polly/ScopDetection.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOPDETECTION_H
 #define POLLY_SCOPDETECTION_H
 
 #include "polly/ScopDetectionDiagnostic.h"
 #include "polly/Support/ScopHelper.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Pass.h"
 #include <set>
 
-namespace llvm {
-class AAResults;
-} // namespace llvm
-
 namespace polly {
 using llvm::AAResults;
 using llvm::AliasSetTracker;
 using llvm::AnalysisInfoMixin;
 using llvm::AnalysisKey;
 using llvm::AnalysisUsage;
+using llvm::BatchAAResults;
 using llvm::BranchInst;
 using llvm::CallInst;
 using llvm::DenseMap;
 using llvm::DominatorTree;
 using llvm::Function;
 using llvm::FunctionAnalysisManager;
 using llvm::FunctionPass;
 using llvm::IntrinsicInst;
public:
   using RegionSet = SetVector<const Region *>;
 
   // Remember the valid regions
   RegionSet ValidRegions;
 
   /// Context variables for SCoP detection.
   struct DetectionContext {
     Region &CurRegion;   // The region to check.
+    BatchAAResults BAA;  // The batched alias analysis results.
     AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
     bool Verifying;      // If we are in the verification phase?
 
     /// If this flag is set, the SCoP must eventually be rejected, even with
     /// KeepGoing.
     bool IsInvalid = false;
 
     /// Container to remember rejection reasons for this region.
struct DetectionContext {
     InvariantLoadsSetTy RequiredILS;
 
     /// Map to memory access description for the corresponding LLVM
     ///        instructions.
     MapInsnToMemAcc InsnToMemAcc;
 
     /// Initialize a DetectionContext from scratch.
     DetectionContext(Region &R, AAResults &AA, bool Verify)
-        : CurRegion(R), AST(AA), Verifying(Verify), Log(&R) {}
+        : CurRegion(R), BAA(AA), AST(BAA), Verifying(Verify), Log(&R) {}
   };
 
   /// Helper data structure to collect statistics about loop counts.
   struct LoopStats {
     int NumLoops;
     int MaxDepth;
   };
 

polly/lib/Analysis/ScopBuilder.cpp

bool ScopBuilder::buildAliasChecks() {
 
   LLVM_DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr()
                     << " could not be created. This SCoP has been dismissed.");
   return false;
 }
 
 std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
 ScopBuilder::buildAliasGroupsForAccesses() {
-  AliasSetTracker AST(AA);
+  BatchAAResults BAA(AA);
+  AliasSetTracker AST(BAA);
 
   DenseMap<Value *, MemoryAccess *> PtrToAcc;
   DenseSet<const ScopArrayInfo *> HasWriteAccess;
   for (ScopStmt &Stmt : *scop) {
 
     isl::set StmtDomain = Stmt.getDomain();
     bool StmtDomainEmpty = StmtDomain.is_empty();