diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h --- a/llvm/include/llvm/Analysis/AliasAnalysis.h +++ b/llvm/include/llvm/Analysis/AliasAnalysis.h @@ -458,6 +458,8 @@ } }; +class AAResults; + /// This class stores info we want to provide to or retain within an alias /// query. By default, the root query is stateless and starts with a freshly /// constructed info object. Specific alias analyses can use this query info to @@ -477,6 +479,11 @@ /// Whether this is a definitive (non-assumption) result. bool isDefinitive() const { return NumAssumptionUses < 0; } }; + + // Alias analysis result aggregration using which this query is performed. + // Can be used to perform recursive queries. + AAResults &AAR; + using AliasCacheT = SmallDenseMap; AliasCacheT AliasCache; @@ -493,13 +500,13 @@ /// assumption is disproven. SmallVector AssumptionBasedResults; - AAQueryInfo(CaptureInfo *CI) : CI(CI) {} + AAQueryInfo(AAResults &AAR, CaptureInfo *CI) : AAR(AAR), CI(CI) {} /// Create a new AAQueryInfo based on this one, but with the cache cleared. /// This is used for recursive queries across phis, where cache results may /// not be valid. AAQueryInfo withEmptyCache() { - AAQueryInfo NewAAQI(CI); + AAQueryInfo NewAAQI(AAR, CI); NewAAQI.Depth = Depth; return NewAAQI; } @@ -510,7 +517,7 @@ SimpleCaptureInfo CI; public: - SimpleAAQueryInfo() : AAQueryInfo(&CI) {} + SimpleAAQueryInfo(AAResults &AAR) : AAQueryInfo(AAR, &CI) {} }; class BatchAAResults; @@ -784,7 +791,7 @@ /// helpers above. ModRefInfo getModRefInfo(const Instruction *I, const Optional &OptLoc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(I, OptLoc, AAQIP); } @@ -809,7 +816,7 @@ ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return callCapturesBefore(I, MemLoc, DT, AAQIP); } @@ -850,7 +857,6 @@ return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); } -private: AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI); bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, @@ -886,6 +892,7 @@ FunctionModRefBehavior getModRefBehavior(const CallBase *Call, AAQueryInfo &AAQI); +private: class Concept; template class Model; @@ -913,8 +920,8 @@ SimpleCaptureInfo SimpleCI; public: - BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(&SimpleCI) {} - BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(CI) {} + BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {} + BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {} AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { return AA.alias(LocA, LocB, AAQI); @@ -973,10 +980,6 @@ public: virtual ~Concept() = 0; - /// An update API used internally by the AAResults to provide - /// a handle back to the top level aggregation. - virtual void setAAResults(AAResults *NewAAR) = 0; - //===--------------------------------------------------------------------===// /// \name Alias Queries /// @{ @@ -1038,13 +1041,9 @@ AAResultT &Result; public: - explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { - Result.setAAResults(&AAR); - } + explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {} ~Model() override = default; - void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } - AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI) override { return Result.alias(LocA, LocB, AAQI); @@ -1093,74 +1092,7 @@ /// use virtual anywhere, the CRTP base class does static dispatch to the /// derived type passed into it. template class AAResultBase { - // Expose some parts of the interface only to the AAResults::Model - // for wrapping. Specifically, this allows the model to call our - // setAAResults method without exposing it as a fully public API. - friend class AAResults::Model; - - /// A pointer to the AAResults object that this AAResult is - /// aggregated within. May be null if not aggregated. - AAResults *AAR = nullptr; - - /// Helper to dispatch calls back through the derived type. - DerivedT &derived() { return static_cast(*this); } - - /// A setter for the AAResults pointer, which is used to satisfy the - /// AAResults::Model contract. - void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } - protected: - /// This proxy class models a common pattern where we delegate to either the - /// top-level \c AAResults aggregation if one is registered, or to the - /// current result if none are registered. - class AAResultsProxy { - AAResults *AAR; - DerivedT &CurrentResult; - - public: - AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) - : AAR(AAR), CurrentResult(CurrentResult) {} - - AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, - AAQueryInfo &AAQI) { - return AAR ? AAR->alias(LocA, LocB, AAQI) - : CurrentResult.alias(LocA, LocB, AAQI); - } - - bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, - bool OrLocal) { - return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal) - : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal); - } - - ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { - return AAR ? AAR->getArgModRefInfo(Call, ArgIdx) - : CurrentResult.getArgModRefInfo(Call, ArgIdx); - } - - FunctionModRefBehavior getModRefBehavior(const CallBase *Call, - AAQueryInfo &AAQI) { - return AAR ? AAR->getModRefBehavior(Call, AAQI) - : CurrentResult.getModRefBehavior(Call, AAQI); - } - - FunctionModRefBehavior getModRefBehavior(const Function *F) { - return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); - } - - ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, - AAQueryInfo &AAQI) { - return AAR ? AAR->getModRefInfo(Call, Loc, AAQI) - : CurrentResult.getModRefInfo(Call, Loc, AAQI); - } - - ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, - AAQueryInfo &AAQI) { - return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI) - : CurrentResult.getModRefInfo(Call1, Call2, AAQI); - } - }; - explicit AAResultBase() = default; // Provide all the copy and move constructors so that derived types aren't @@ -1168,18 +1100,6 @@ AAResultBase(const AAResultBase &Arg) {} AAResultBase(AAResultBase &&Arg) {} - /// Get a proxy for the best AA result set to query at this time. - /// - /// When this result is part of a larger aggregation, this will proxy to that - /// aggregation. When this result is used in isolation, it will just delegate - /// back to the derived class's implementation. - /// - /// Note that callers of this need to take considerable care to not cause - /// performance problems when they use this routine, in the case of a large - /// number of alias analyses being aggregated, it can be expensive to walk - /// back across the chain. - AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } - public: AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI) { diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp --- a/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/llvm/lib/Analysis/AliasAnalysis.cpp @@ -76,21 +76,9 @@ #endif AAResults::AAResults(AAResults &&Arg) - : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) { - for (auto &AA : AAs) - AA->setAAResults(this); -} + : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {} -AAResults::~AAResults() { -// FIXME; It would be nice to at least clear out the pointers back to this -// aggregation here, but we end up with non-nesting lifetimes in the legacy -// pass manager that prevent this from working. In the legacy pass manager -// we'll end up with dangling references here in some cases. -#if 0 - for (auto &AA : AAs) - AA->setAAResults(nullptr); -#endif -} +AAResults::~AAResults() {} bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv) { @@ -118,7 +106,7 @@ AliasResult AAResults::alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return alias(LocA, LocB, AAQIP); } @@ -161,7 +149,7 @@ bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return pointsToConstantMemory(Loc, AAQIP, OrLocal); } @@ -189,7 +177,7 @@ } ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(I, Call2, AAQIP); } @@ -216,7 +204,7 @@ ModRefInfo AAResults::getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(Call, Loc, AAQIP); } @@ -276,7 +264,7 @@ ModRefInfo AAResults::getModRefInfo(const CallBase *Call1, const CallBase *Call2) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(Call1, Call2, AAQIP); } @@ -403,7 +391,7 @@ } FunctionModRefBehavior AAResults::getModRefBehavior(const CallBase *Call) { - SimpleAAQueryInfo AAQI; + SimpleAAQueryInfo AAQI(*this); return getModRefBehavior(Call, AAQI); } @@ -484,7 +472,7 @@ ModRefInfo AAResults::getModRefInfo(const LoadInst *L, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(L, Loc, AAQIP); } ModRefInfo AAResults::getModRefInfo(const LoadInst *L, @@ -507,7 +495,7 @@ ModRefInfo AAResults::getModRefInfo(const StoreInst *S, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(S, Loc, AAQIP); } ModRefInfo AAResults::getModRefInfo(const StoreInst *S, @@ -534,8 +522,9 @@ return ModRefInfo::Mod; } -ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; +ModRefInfo AAResults::getModRefInfo(const FenceInst *S, + const MemoryLocation &Loc) { + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(S, Loc, AAQIP); } @@ -551,7 +540,7 @@ ModRefInfo AAResults::getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(V, Loc, AAQIP); } @@ -577,7 +566,7 @@ ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(CatchPad, Loc, AAQIP); } @@ -597,7 +586,7 @@ ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(CatchRet, Loc, AAQIP); } @@ -617,7 +606,7 @@ ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(CX, Loc, AAQIP); } @@ -641,7 +630,7 @@ ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc) { - SimpleAAQueryInfo AAQIP; + SimpleAAQueryInfo AAQIP(*this); return getModRefInfo(RMW, Loc, AAQIP); } diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -766,7 +766,7 @@ getModRefBehaviorFromAttrs(Call->getAttributes().getFnAttrs()); if (const Function *F = dyn_cast(Call->getCalledOperand())) { - FunctionModRefBehavior FMRB = getBestAAResults().getModRefBehavior(F); + FunctionModRefBehavior FMRB = AAQI.AAR.getModRefBehavior(F); // Operand bundles on the call may also read or write memory, in addition // to the behavior of the called function. if (Call->hasReadingOperandBundles()) @@ -925,9 +925,9 @@ // If this is a no-capture pointer argument, see if we can tell that it // is impossible to alias the pointer we're checking. - AliasResult AR = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(*CI), - MemoryLocation::getBeforeOrAfter(Object), AAQI); + AliasResult AR = + AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(*CI), + MemoryLocation::getBeforeOrAfter(Object), AAQI); // Operand doesn't alias 'Object', continue looking for other aliases if (AR == AliasResult::NoAlias) continue; @@ -963,8 +963,8 @@ if (isMallocOrCallocLikeFn(Call, &TLI)) { // Be conservative if the accessed pointer may alias the allocation - // fallback to the generic handling below. - if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), Loc, - AAQI) == AliasResult::NoAlias) + if (AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(Call), Loc, AAQI) == + AliasResult::NoAlias) return ModRefInfo::NoModRef; } @@ -1057,9 +1057,9 @@ // If both accesses have unknown size, we can only check whether the base // objects don't alias. - AliasResult BaseAlias = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(UnderlyingV1), - MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); + AliasResult BaseAlias = + AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(UnderlyingV1), + MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias : AliasResult::MayAlias; } @@ -1093,14 +1093,13 @@ // For GEPs with identical offsets, we can preserve the size and AAInfo // when performing the alias check on the underlying objects. if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) - return getBestAAResults().alias(MemoryLocation(DecompGEP1.Base, V1Size), - MemoryLocation(DecompGEP2.Base, V2Size), - AAQI); + return AAQI.AAR.alias(MemoryLocation(DecompGEP1.Base, V1Size), + MemoryLocation(DecompGEP2.Base, V2Size), AAQI); // Do the base pointers alias? - AliasResult BaseAlias = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(DecompGEP1.Base), - MemoryLocation::getBeforeOrAfter(DecompGEP2.Base), AAQI); + AliasResult BaseAlias = + AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(DecompGEP1.Base), + MemoryLocation::getBeforeOrAfter(DecompGEP2.Base), AAQI); // If we get a No or May, then return it immediately, no amount of analysis // will improve this situation. @@ -1305,28 +1304,27 @@ // check: just check for aliases between the values on corresponding arms. if (const SelectInst *SI2 = dyn_cast(V2)) if (SI->getCondition() == SI2->getCondition()) { - AliasResult Alias = getBestAAResults().alias( - MemoryLocation(SI->getTrueValue(), SISize), - MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); + AliasResult Alias = + AAQI.AAR.alias(MemoryLocation(SI->getTrueValue(), SISize), + MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); if (Alias == AliasResult::MayAlias) return AliasResult::MayAlias; - AliasResult ThisAlias = getBestAAResults().alias( - MemoryLocation(SI->getFalseValue(), SISize), - MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); + AliasResult ThisAlias = + AAQI.AAR.alias(MemoryLocation(SI->getFalseValue(), SISize), + MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); return MergeAliasResults(ThisAlias, Alias); } // If both arms of the Select node NoAlias or MustAlias V2, then returns // NoAlias / MustAlias. Otherwise, returns MayAlias. - AliasResult Alias = - getBestAAResults().alias(MemoryLocation(SI->getTrueValue(), SISize), - MemoryLocation(V2, V2Size), AAQI); + AliasResult Alias = AAQI.AAR.alias(MemoryLocation(SI->getTrueValue(), SISize), + MemoryLocation(V2, V2Size), AAQI); if (Alias == AliasResult::MayAlias) return AliasResult::MayAlias; AliasResult ThisAlias = - getBestAAResults().alias(MemoryLocation(SI->getFalseValue(), SISize), - MemoryLocation(V2, V2Size), AAQI); + AAQI.AAR.alias(MemoryLocation(SI->getFalseValue(), SISize), + MemoryLocation(V2, V2Size), AAQI); return MergeAliasResults(ThisAlias, Alias); } @@ -1344,7 +1342,7 @@ if (PN2->getParent() == PN->getParent()) { Optional Alias; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - AliasResult ThisAlias = getBestAAResults().alias( + AliasResult ThisAlias = AAQI.AAR.alias( MemoryLocation(PN->getIncomingValue(i), PNSize), MemoryLocation( PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size), @@ -1447,8 +1445,8 @@ AAQueryInfo NewAAQI = AAQI.withEmptyCache(); AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI; - AliasResult Alias = getBestAAResults().alias( - MemoryLocation(V1Srcs[0], PNSize), MemoryLocation(V2, V2Size), *UseAAQI); + AliasResult Alias = AAQI.AAR.alias(MemoryLocation(V1Srcs[0], PNSize), + MemoryLocation(V2, V2Size), *UseAAQI); // Early exit if the check of the first PHI source against V2 is MayAlias. // Other results are not possible. @@ -1464,7 +1462,7 @@ for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { Value *V = V1Srcs[i]; - AliasResult ThisAlias = getBestAAResults().alias( + AliasResult ThisAlias = AAQI.AAR.alias( MemoryLocation(V, PNSize), MemoryLocation(V2, V2Size), *UseAAQI); Alias = MergeAliasResults(ThisAlias, Alias); if (Alias == AliasResult::MayAlias) diff --git a/llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp b/llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp --- a/llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp +++ b/llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp @@ -46,11 +46,14 @@ DominatorTree DT; AssumptionCache AC; BasicAAResult BAA; + AAResults AAR; SimpleAAQueryInfo AAQI; TestAnalyses(BasicAATest &Test) : DT(*Test.F), AC(*Test.F), BAA(Test.DL, *Test.F, Test.TLI, AC, &DT), - AAQI() {} + AAR(Test.TLI), AAQI(AAR) { + AAR.addAAResult(BAA); + } }; llvm::Optional Analyses;