From 1fc18d71deb0e23a9101c87bb7b1455098ce1c09 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Sat, 4 Jun 2011 00:31:50 +0000 Subject: Fix BasicAA's recursion detection so that it doesn't pessimize queries in the case of a DAG, where a query reaches a node visited earlier, but it's not on a cycle. This avoids MayAlias results in cases where BasicAA is expected to return MustAlias or PartialAlias in order to protect TBAA. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132609 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/AliasAnalysis.h | 27 +++++++++++++++ lib/Analysis/BasicAliasAnalysis.cpp | 64 +++++++++++++++-------------------- test/Analysis/BasicAA/dag.ll | 41 ++++++++++++++++++++++ 3 files changed, 95 insertions(+), 37 deletions(-) create mode 100644 test/Analysis/BasicAA/dag.ll diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 8f9708b..5d8edd1 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -38,6 +38,7 @@ #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H #include "llvm/Support/CallSite.h" +#include "llvm/ADT/DenseMap.h" namespace llvm { @@ -488,6 +489,32 @@ public: } }; +// Specialize DenseMapInfo for Location. +template<> +struct DenseMapInfo { + static inline AliasAnalysis::Location getEmptyKey() { + return + AliasAnalysis::Location(DenseMapInfo::getEmptyKey(), + 0, 0); + } + static inline AliasAnalysis::Location getTombstoneKey() { + return + AliasAnalysis::Location(DenseMapInfo::getTombstoneKey(), + 0, 0); + } + static unsigned getHashValue(const AliasAnalysis::Location &Val) { + return DenseMapInfo::getHashValue(Val.Ptr) ^ + DenseMapInfo::getHashValue(Val.Size) ^ + DenseMapInfo::getHashValue(Val.TBAATag); + } + static bool isEqual(const AliasAnalysis::Location &LHS, + const AliasAnalysis::Location &RHS) { + return LHS.Ptr == RHS.Ptr && + LHS.Size == RHS.Size && + LHS.TBAATag == RHS.TBAATag; + } +}; + /// isNoAliasCall - Return true if this pointer is returned by a noalias /// function. bool isNoAliasCall(const Value *V); diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index c292999..24297d4 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -465,12 +465,12 @@ namespace { virtual AliasResult alias(const Location &LocA, const Location &LocB) { - assert(Visited.empty() && "Visited must be cleared after use!"); + assert(AliasCache.empty() && "AliasCache must be cleared after use!"); assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries."); AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, LocB.Ptr, LocB.Size, LocB.TBAATag); - Visited.clear(); + AliasCache.clear(); return Alias; } @@ -506,7 +506,12 @@ namespace { } private: - // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP(). + // AliasCache - Track alias queries to guard against recursion. + typedef std::pair LocPair; + typedef DenseMap AliasCacheTy; + AliasCacheTy AliasCache; + + // Visited - Track instructions visited by pointsToConstantMemory. SmallPtrSet Visited; // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP @@ -822,13 +827,6 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, const MDNode *V2TBAAInfo, const Value *UnderlyingV1, const Value *UnderlyingV2) { - // If this GEP has been visited before, we're on a use-def cycle. - // Such cycles are only valid when PHI nodes are involved or in unreachable - // code. The visitPHI function catches cycles containing PHIs, but there - // could still be a cycle without PHIs in unreachable code. - if (!Visited.insert(GEP1)) - return MayAlias; - int64_t GEP1BaseOffset; SmallVector GEP1VariableIndices; @@ -969,13 +967,6 @@ BasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, const MDNode *SITBAAInfo, const Value *V2, uint64_t V2Size, const MDNode *V2TBAAInfo) { - // If this select has been visited before, we're on a use-def cycle. - // Such cycles are only valid when PHI nodes are involved or in unreachable - // code. The visitPHI function catches cycles containing PHIs, but there - // could still be a cycle without PHIs in unreachable code. - if (!Visited.insert(SI)) - return MayAlias; - // If the values are Selects with the same condition, we can do a more precise // check: just check for aliases between the values on corresponding arms. if (const SelectInst *SI2 = dyn_cast(V2)) @@ -998,11 +989,6 @@ BasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, if (Alias == MayAlias) return MayAlias; - // If V2 is visited, the recursive case will have been caught in the - // above aliasCheck call, so these subsequent calls to aliasCheck - // don't need to assume that V2 is being visited recursively. - Visited.erase(V2); - AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); return MergeAliasResults(ThisAlias, Alias); @@ -1015,10 +1001,6 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, const MDNode *PNTBAAInfo, const Value *V2, uint64_t V2Size, const MDNode *V2TBAAInfo) { - // The PHI node has already been visited, avoid recursion any further. - if (!Visited.insert(PN)) - return MayAlias; - // If the values are PHIs in the same block, we can do a more precise // as well as efficient check: just check for aliases between the values // on corresponding edges. @@ -1068,11 +1050,6 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { Value *V = V1Srcs[i]; - // If V2 is visited, the recursive case will have been caught in the - // above aliasCheck call, so these subsequent calls to aliasCheck - // don't need to assume that V2 is being visited recursively. - Visited.erase(V2); - AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, V, PNSize, PNTBAAInfo); Alias = MergeAliasResults(ThisAlias, Alias); @@ -1162,6 +1139,17 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD))) return NoAlias; + // Check the cache before climbing up use-def chains. This also terminates + // otherwise infinitely recursive queries. + LocPair Locs(Location(V1, V1Size, V1TBAAInfo), + Location(V2, V2Size, V2TBAAInfo)); + if (V1 > V2) + std::swap(Locs.first, Locs.second); + std::pair Pair = + AliasCache.insert(std::make_pair(Locs, MayAlias)); + if (!Pair.second) + return Pair.first->second; + // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the // GEP can't simplify, we don't even look at the PHI cases. if (!isa(V1) && isa(V2)) { @@ -1171,7 +1159,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, } if (const GEPOperator *GV1 = dyn_cast(V1)) { AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, V2TBAAInfo, O1, O2); - if (Result != MayAlias) return Result; + if (Result != MayAlias) return AliasCache[Locs] = Result; } if (isa(V2) && !isa(V1)) { @@ -1181,7 +1169,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, if (const PHINode *PN = dyn_cast(V1)) { AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo); - if (Result != MayAlias) return Result; + if (Result != MayAlias) return AliasCache[Locs] = Result; } if (isa(V2) && !isa(V1)) { @@ -1191,7 +1179,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, if (const SelectInst *S1 = dyn_cast(V1)) { AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo); - if (Result != MayAlias) return Result; + if (Result != MayAlias) return AliasCache[Locs] = Result; } // If both pointers are pointing into the same object and one of them @@ -1200,8 +1188,10 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, if (TD && O1 == O2) if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD)) || (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD))) - return PartialAlias; + return AliasCache[Locs] = PartialAlias; - return AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), - Location(V2, V2Size, V2TBAAInfo)); + AliasResult Result = + AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), + Location(V2, V2Size, V2TBAAInfo)); + return AliasCache[Locs] = Result; } diff --git a/test/Analysis/BasicAA/dag.ll b/test/Analysis/BasicAA/dag.ll new file mode 100644 index 0000000..501f4c3 --- /dev/null +++ b/test/Analysis/BasicAA/dag.ll @@ -0,0 +1,41 @@ +; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info |& FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" + +; BasicAA's guard against use-def cycles shouldn't prevent it from +; analyzing use-def dags. + +; CHECK: MustAlias: i8* %base, i8* %phi +; CHECK: MustAlias: i8* %phi, i8* %wwa +; CHECK: MustAlias: i8* %phi, i8* %wwb +; CHECK: MustAlias: i16* %bigbase, i8* %phi +define i8 @foo(i8* %base, i1 %x, i1 %w) { +entry: + br i1 %w, label %wa, label %wb +wa: + %wwa = bitcast i8* %base to i8* + br label %wc +wb: + %wwb = bitcast i8* %base to i8* + br label %wc +wc: + %first = phi i8* [ %wwa, %wa ], [ %wwb, %wb ] + %fc = bitcast i8* %first to i8* + br i1 %x, label %xa, label %xb +xa: + %xxa = bitcast i8* %fc to i8* + br label %xc +xb: + %xxb = bitcast i8* %fc to i8* + br label %xc +xc: + %phi = phi i8* [ %xxa, %xa ], [ %xxb, %xb ] + + store i8 0, i8* %phi + + %bigbase = bitcast i8* %base to i16* + store i16 -1, i16* %bigbase + + %loaded = load i8* %phi + ret i8 %loaded +} -- cgit v1.1