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 @@ -346,19 +346,21 @@ class AAQueryInfo { public: using LocPair = std::pair; - using AliasCacheT = SmallDenseMap; + struct CacheEntry { + AliasResult Result; + /// Number of times a NoAlias assumption has been used. + /// 0 for assumptions that have not been used, -1 for definitive results. + int NumAssumptionUses; + /// Whether this is a definitive (non-assumption) result. + bool isDefinitive() const { return NumAssumptionUses < 0; } + }; + using AliasCacheT = SmallDenseMap; AliasCacheT AliasCache; using IsCapturedCacheT = SmallDenseMap; IsCapturedCacheT IsCapturedCache; AAQueryInfo() : AliasCache(), IsCapturedCache() {} - - AliasResult updateResult(const LocPair &Locs, AliasResult Result) { - auto It = AliasCache.find(Locs); - assert(It != AliasCache.end() && "Entry must have existed"); - return It->second = Result; - } }; class BatchAAResults; diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h --- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h @@ -190,6 +190,14 @@ /// Tracks instructions visited by pointsToConstantMemory. SmallPtrSet Visited; + /// How many active NoAlias assumption uses there are. + int NumAssumptionUses = 0; + + /// Location pairs for which an assumption based result is currently stored. + /// Used to remove all potentially incorrect results from the cache if an + /// assumption is disproven. + SmallVector AssumptionBasedResults; + static const Value * GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, unsigned &SExtBits, @@ -244,6 +252,12 @@ LocationSize V2Size, const AAMDNodes &V2AATag, AAQueryInfo &AAQI, const Value *O1 = nullptr, const Value *O2 = nullptr); + + AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size, + const AAMDNodes &V1AATag, const Value *V2, + LocationSize V2Size, const AAMDNodes &V2AATag, + AAQueryInfo &AAQI, const Value *O1, + const Value *O2); }; /// Analysis pass providing a never-invalidated alias analysis result. 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 @@ -806,8 +806,12 @@ if (Locs.first.Ptr > Locs.second.Ptr) std::swap(Locs.first, Locs.second); auto CacheIt = AAQI.AliasCache.find(Locs); - if (CacheIt != AAQI.AliasCache.end()) - return CacheIt->second; + if (CacheIt != AAQI.AliasCache.end()) { + // This code exists to skip a second BasicAA call while recursing into + // BestAA. Don't make use of assumptions here. + const auto &Entry = CacheIt->second; + return Entry.isDefinitive() ? Entry.Result : MayAlias; + } AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, LocB.Size, LocB.AATags, AAQI); @@ -1376,42 +1380,20 @@ // on corresponding edges. if (const PHINode *PN2 = dyn_cast(V2)) if (PN2->getParent() == PN->getParent()) { - AAQueryInfo::LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), - MemoryLocation(V2, V2Size, V2AAInfo)); - if (PN > V2) - std::swap(Locs.first, Locs.second); - // Analyse the PHIs' inputs under the assumption that the PHIs are - // NoAlias. - // If the PHIs are May/MustAlias there must be (recursively) an input - // operand from outside the PHIs' cycle that is MayAlias/MustAlias or - // there must be an operation on the PHIs within the PHIs' value cycle - // that causes a MayAlias. - // Pretend the phis do not alias. - AliasResult Alias = NoAlias; - AliasResult OrigAliasResult; - { - // Limited lifetime iterator invalidated by the aliasCheck call below. - auto CacheIt = AAQI.AliasCache.find(Locs); - assert((CacheIt != AAQI.AliasCache.end()) && - "There must exist an entry for the phi node"); - OrigAliasResult = CacheIt->second; - CacheIt->second = NoAlias; - } - + Optional Alias; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { AliasResult ThisAlias = aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size, V2AAInfo, AAQI); - Alias = MergeAliasResults(ThisAlias, Alias); - if (Alias == MayAlias) + if (Alias) + *Alias = MergeAliasResults(*Alias, ThisAlias); + else + Alias = ThisAlias; + if (*Alias == MayAlias) break; } - - // Reset if speculation failed. - if (Alias != NoAlias) - AAQI.updateResult(Locs, OrigAliasResult); - return Alias; + return *Alias; } SmallVector V1Srcs; @@ -1630,64 +1612,106 @@ MemoryLocation(V2, V2Size, V2AAInfo)); if (V1 > V2) std::swap(Locs.first, Locs.second); - std::pair Pair = - AAQI.AliasCache.try_emplace(Locs, MayAlias); - if (!Pair.second) - return Pair.first->second; + const auto &Pair = AAQI.AliasCache.try_emplace( + Locs, AAQueryInfo::CacheEntry{NoAlias, 0}); + if (!Pair.second) { + auto &Entry = Pair.first->second; + if (!Entry.isDefinitive()) { + // Remember that we used an assumption. + ++Entry.NumAssumptionUses; + ++NumAssumptionUses; + } + return Entry.Result; + } + int OrigNumAssumptionUses = NumAssumptionUses; + unsigned OrigNumAssumptionBasedResults = AssumptionBasedResults.size(); + AliasResult Result = aliasCheckRecursive(V1, V1Size, V1AAInfo, V2, V2Size, + V2AAInfo, AAQI, O1, O2); + + auto It = AAQI.AliasCache.find(Locs); + assert(It != AAQI.AliasCache.end() && "Must be in cache"); + auto &Entry = It->second; + + // Check whether a NoAlias assumption has been used, but disproven. + bool AssumptionDisproven = Entry.NumAssumptionUses > 0 && Result != NoAlias; + if (AssumptionDisproven) + Result = MayAlias; + + // This is a definitive result now, when considered as a root query. + NumAssumptionUses -= Entry.NumAssumptionUses; + Entry.Result = Result; + Entry.NumAssumptionUses = -1; + + // If the assumption has been disproven, remove any results that may have + // been based on this assumption. Do this after the Entry updates above to + // avoid iterator invalidation. + if (AssumptionDisproven) + while (AssumptionBasedResults.size() > OrigNumAssumptionBasedResults) + AAQI.AliasCache.erase(AssumptionBasedResults.pop_back_val()); + + // The result may still be based on assumptions higher up in the chain. + // Remember it, so it can be purged from the cache later. + if (OrigNumAssumptionUses != NumAssumptionUses && Result != MayAlias) + AssumptionBasedResults.push_back(Locs); + return Result; +} + +AliasResult BasicAAResult::aliasCheckRecursive( + const Value *V1, LocationSize V1Size, const AAMDNodes &V1AAInfo, + const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, + AAQueryInfo &AAQI, const Value *O1, const Value *O2) { if (const GEPOperator *GV1 = dyn_cast(V1)) { AliasResult Result = aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } else if (const GEPOperator *GV2 = dyn_cast(V2)) { AliasResult Result = aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } if (const PHINode *PN = dyn_cast(V1)) { AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } else if (const PHINode *PN = dyn_cast(V2)) { AliasResult Result = aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } if (const SelectInst *S1 = dyn_cast(V1)) { AliasResult Result = aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } else if (const SelectInst *S2 = dyn_cast(V2)) { AliasResult Result = aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O1, AAQI); if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); + return Result; } // If both pointers are pointing into the same object and one of them // accesses the entire object, then the accesses must overlap in some way. - if (O1 == O2) + if (O1 == O2) { + bool NullIsValidLocation = NullPointerIsDefined(&F); if (V1Size.isPrecise() && V2Size.isPrecise() && (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) - return AAQI.updateResult(Locs, PartialAlias); + return PartialAlias; + } // Recurse back into the best AA results we have, potentially with refined // memory locations. We have already ensured that BasicAA has a MayAlias // cache result for these, so any recursion back into BasicAA won't loop. - AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second, AAQI); - if (Result != MayAlias) - return AAQI.updateResult(Locs, Result); - - // MayAlias is already in the cache. - return MayAlias; + return getBestAAResults().alias(MemoryLocation(V1, V1Size, V1AAInfo), + MemoryLocation(V2, V2Size, V2AAInfo), AAQI); } /// Check whether two Values can be considered equivalent. diff --git a/llvm/test/Analysis/BasicAA/phi-speculation.ll b/llvm/test/Analysis/BasicAA/phi-speculation.ll --- a/llvm/test/Analysis/BasicAA/phi-speculation.ll +++ b/llvm/test/Analysis/BasicAA/phi-speculation.ll @@ -6,8 +6,7 @@ ; ptr_phi and ptr2_phi do not alias. ; CHECK: test_noalias_1 ; CHECK: NoAlias: i32* %ptr2_phi, i32* %ptr_phi -; CHECK: MayAlias: i32* %ptr2_inc, i32* %ptr_inc -; TODO: The incs should also be NoAlias. +; CHECK: NoAlias: i32* %ptr2_inc, i32* %ptr_inc define i32 @test_noalias_1(i32* %ptr2, i32 %count, i32* %coeff) { entry: %ptr = getelementptr inbounds i32, i32* %ptr2, i64 1 @@ -36,10 +35,9 @@ ; CHECK: test_noalias_2 ; CHECK: NoAlias: i32* %ptr_outer_phi, i32* %ptr_outer_phi2 -; CHECK: MayAlias: i32* %ptr2_inc_outer, i32* %ptr_inc_outer +; CHECK: NoAlias: i32* %ptr2_inc_outer, i32* %ptr_inc_outer ; CHECK: NoAlias: i32* %ptr2_phi, i32* %ptr_phi -; CHECK: MayAlias: i32* %ptr2_inc, i32* %ptr_inc -; TODO: The incs should also be NoAlias. +; CHECK: NoAlias: i32* %ptr2_inc, i32* %ptr_inc define i32 @test_noalias_2(i32* %ptr2, i32 %count, i32* %coeff) { entry: %ptr = getelementptr inbounds i32, i32* %ptr2, i64 1 @@ -118,8 +116,7 @@ } ; CHECK-LABEL: test_no_loop_mustalias -; CHECK: MayAlias: i16* %z16, i8* %z8 -; TODO: (z8, z16) could be MustAlias +; CHECK: MustAlias: i16* %z16, i8* %z8 define void @test_no_loop_mustalias(i1 %c, i8* noalias %x8, i8* noalias %y8) { br i1 %c, label %if, label %else diff --git a/llvm/unittests/Analysis/AliasAnalysisTest.cpp b/llvm/unittests/Analysis/AliasAnalysisTest.cpp --- a/llvm/unittests/Analysis/AliasAnalysisTest.cpp +++ b/llvm/unittests/Analysis/AliasAnalysisTest.cpp @@ -295,8 +295,7 @@ BatchAAResults BatchAA(AA); EXPECT_EQ(MayAlias, BatchAA.alias(ALoc, BLoc)); - // TODO: This is incorrect. - EXPECT_EQ(NoAlias, BatchAA.alias(ANextLoc, BNextLoc)); + EXPECT_EQ(MayAlias, BatchAA.alias(ANextLoc, BNextLoc)); } class AAPassInfraTest : public testing::Test {