Index: llvm/include/llvm/Analysis/AliasSetTracker.h =================================================================== --- llvm/include/llvm/Analysis/AliasSetTracker.h +++ llvm/include/llvm/Analysis/AliasSetTracker.h @@ -11,6 +11,8 @@ // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker // object refers to memory disjoint from the other sets. // +// An AliasSetTracker can only be used on immutable IR. +// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H @@ -31,7 +33,6 @@ namespace llvm { -class AAResults; class AliasResult; class AliasSetTracker; class AnyMemSetInst; @@ -293,7 +294,7 @@ 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); void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { bool WasEmpty = UnknownInsts.empty(); @@ -338,7 +339,7 @@ /// handle. struct ASTCallbackVHDenseMapInfo : public DenseMapInfo {}; - AAResults &AA; + BatchAAResults &AA; ilist AliasSets; using PointerMapType = DenseMap::iterator; using const_iterator = ilist::const_iterator; Index: llvm/include/llvm/LinkAllPasses.h =================================================================== --- llvm/include/llvm/LinkAllPasses.h +++ llvm/include/llvm/LinkAllPasses.h @@ -229,7 +229,8 @@ 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(); Index: llvm/lib/Analysis/AliasSetTracker.cpp =================================================================== --- llvm/lib/Analysis/AliasSetTracker.cpp +++ llvm/lib/Analysis/AliasSetTracker.cpp @@ -132,7 +132,7 @@ 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)); @@ -161,7 +161,7 @@ AST.TotalMayAliasSetSize++; } -void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { +void AliasSet::addUnknownInst(Instruction *I, BatchAAResults &AA) { if (UnknownInsts.empty()) addRef(); UnknownInsts.emplace_back(I); @@ -274,12 +274,11 @@ 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; @@ -291,7 +290,7 @@ FoundSet = &AS; } else { // Otherwise, we must merge the sets. - FoundSet->mergeSetIn(AS, *this, BatchAA); + FoundSet->mergeSetIn(AS, *this, AA); } } @@ -299,17 +298,16 @@ } 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; @@ -509,57 +507,6 @@ } } -// deleteValue method - 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 AliasSetTracker::deleteValue(Value *PtrVal) { - // First, look up the PointerRec for this pointer. - PointerMapType::iterator I = PointerMap.find_as(PtrVal); - if (I == PointerMap.end()) return; // Noop - - // If we found one, remove the pointer from the alias set it is in. - AliasSet::PointerRec *PtrValEnt = I->second; - AliasSet *AS = PtrValEnt->getAliasSet(*this); - - // Unlink and delete from the list of values. - PtrValEnt->eraseFromList(); - - if (AS->Alias == AliasSet::SetMayAlias) { - AS->SetSize--; - TotalMayAliasSetSize--; - } - - // Stop using the alias set. - AS->dropRef(*this); - - PointerMap.erase(I); -} - -// copyValue - This method should be used whenever a preexisting value in the -// program is copied or cloned, introducing a new value. Note that it is ok for -// clients that use this method to introduce the same value multiple times: if -// the tracker already knows about a value, it will ignore the request. -// -void AliasSetTracker::copyValue(Value *From, Value *To) { - // First, look up the PointerRec for this pointer. - PointerMapType::iterator I = PointerMap.find_as(From); - if (I == PointerMap.end()) - return; // Noop - assert(I->second->hasAliasSet() && "Dead entry?"); - - AliasSet::PointerRec &Entry = getEntryFor(To); - if (Entry.hasAliasSet()) return; // Already in the tracker! - - // getEntryFor above may invalidate iterator \c I, so reinitialize it. - I = PointerMap.find_as(From); - // Add it to the alias set it aliases... - AliasSet *AS = I->second->getAliasSet(*this); - AS->addPointer(*this, Entry, I->second->getSize(), I->second->getAAInfo(), - true, true); -} - AliasSet &AliasSetTracker::mergeAllAliasSets() { assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) && "Full merge should happen once, when the saturation threshold is " @@ -580,7 +527,6 @@ 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; @@ -592,7 +538,7 @@ } // Otherwise, perform the actual merge. - AliasAnyAS->mergeSetIn(*Cur, *this, BatchAA); + AliasAnyAS->mergeSetIn(*Cur, *this, AA); } return *AliasAnyAS; @@ -677,13 +623,11 @@ //===----------------------------------------------------------------------===// void AliasSetTracker::ASTCallbackVH::deleted() { - assert(AST && "ASTCallbackVH called with a null AliasSetTracker!"); - AST->deleteValue(getValPtr()); - // this now dangles! + llvm_unreachable("AliasSetTracker must work on immutable IR"); } void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) { - AST->copyValue(getValPtr(), V); + llvm_unreachable("AliasSetTracker must work on immutable IR"); } AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) @@ -703,7 +647,8 @@ PreservedAnalyses AliasSetsPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { auto &AA = AM.getResult(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); Index: llvm/lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -622,7 +622,7 @@ 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) { @@ -704,6 +704,9 @@ /// Set of pointers that are read only. SmallPtrSet 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; Index: llvm/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LICM.cpp +++ llvm/lib/Transforms/Scalar/LICM.cpp @@ -2251,7 +2251,8 @@ static SmallVector, 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(I)) @@ -2280,7 +2281,6 @@ 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; Index: llvm/lib/Transforms/Scalar/LoopRerollPass.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopRerollPass.cpp +++ llvm/lib/Transforms/Scalar/LoopRerollPass.cpp @@ -1224,13 +1224,14 @@ 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 BaseMap; @@ -1327,7 +1328,6 @@ // 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 " Index: llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp +++ llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp @@ -256,7 +256,8 @@ /// 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) Index: llvm/unittests/Analysis/AliasSetTrackerTest.cpp =================================================================== --- llvm/unittests/Analysis/AliasSetTrackerTest.cpp +++ llvm/unittests/Analysis/AliasSetTrackerTest.cpp @@ -68,7 +68,8 @@ // 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. Index: polly/include/polly/ScopDetection.h =================================================================== --- polly/include/polly/ScopDetection.h +++ polly/include/polly/ScopDetection.h @@ -48,22 +48,20 @@ #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 -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; @@ -142,6 +140,7 @@ /// 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? @@ -189,7 +188,7 @@ /// 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. Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -3205,7 +3205,8 @@ std::tuple> ScopBuilder::buildAliasGroupsForAccesses() { - AliasSetTracker AST(AA); + BatchAAResults BAA(AA); + AliasSetTracker AST(BAA); DenseMap PtrToAcc; DenseSet HasWriteAccess;