From 8e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Wed, 29 Aug 2012 15:32:21 +0000 Subject: Make MemoryBuiltins aware of TargetLibraryInfo. This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) (limited to 'lib/Analysis/BasicAliasAnalysis.cpp') diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 1d028c2..e3476ac 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -85,9 +85,10 @@ static bool isEscapeSource(const Value *V) { /// getObjectSize - Return the size of the object specified by V, or /// UnknownSize if unknown. static uint64_t getObjectSize(const Value *V, const TargetData &TD, + const TargetLibraryInfo &TLI, bool RoundToAlign = false) { uint64_t Size; - if (getObjectSize(V, Size, &TD, RoundToAlign)) + if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) return Size; return AliasAnalysis::UnknownSize; } @@ -95,10 +96,11 @@ static uint64_t getObjectSize(const Value *V, const TargetData &TD, /// isObjectSmallerThan - Return true if we can prove that the object specified /// by V is smaller than Size. static bool isObjectSmallerThan(const Value *V, uint64_t Size, - const TargetData &TD) { + const TargetData &TD, + const TargetLibraryInfo &TLI) { // This function needs to use the aligned object size because we allow // reads a bit past the end given sufficient alignment. - uint64_t ObjectSize = getObjectSize(V, TD, /*RoundToAlign*/true); + uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; } @@ -106,8 +108,8 @@ static bool isObjectSmallerThan(const Value *V, uint64_t Size, /// isObjectSize - Return true if we can prove that the object specified /// by V has size Size. static bool isObjectSize(const Value *V, uint64_t Size, - const TargetData &TD) { - uint64_t ObjectSize = getObjectSize(V, TD); + const TargetData &TD, const TargetLibraryInfo &TLI) { + uint64_t ObjectSize = getObjectSize(V, TD, TLI); return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; } @@ -1133,8 +1135,8 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, // If the size of one access is larger than the entire object on the other // side, then we know such behavior is undefined and can assume no alias. if (TD) - if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD)) || - (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD))) + if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || + (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) return NoAlias; // Check the cache before climbing up use-def chains. This also terminates @@ -1184,8 +1186,8 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, // accesses is accessing the entire object, then the accesses must // overlap in some way. if (TD && O1 == O2) - if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD)) || - (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD))) + if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || + (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) return AliasCache[Locs] = PartialAlias; AliasResult Result = -- cgit v1.1 From 998d3cca2937393d91b04d4d6105d9e67dd3b1b6 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Wed, 5 Sep 2012 16:49:37 +0000 Subject: Switch BasicAliasAnalysis' cache to SmallDenseMap. It relies on clear() being fast and the cache rarely has more than 1 or 2 elements, so give it an inline capacity and always shrink it back down in case it grows. DenseMap will grow to 64 buckets which makes clear() a lot slower. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163215 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'lib/Analysis/BasicAliasAnalysis.cpp') diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index e3476ac..a3e6575 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -419,13 +419,7 @@ namespace { /// BasicAliasAnalysis - This is the primary alias analysis implementation. struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { static char ID; // Class identification, replacement for typeinfo - BasicAliasAnalysis() : ImmutablePass(ID), - // AliasCache rarely has more than 1 or 2 elements, - // so start it off fairly small so that clear() - // doesn't have to tromp through 64 (the default) - // elements on each alias query. This really wants - // something like a SmallDenseMap. - AliasCache(8) { + BasicAliasAnalysis() : ImmutablePass(ID) { initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); } @@ -445,7 +439,11 @@ namespace { "BasicAliasAnalysis doesn't support interprocedural queries."); AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, LocB.Ptr, LocB.Size, LocB.TBAATag); - AliasCache.clear(); + // AliasCache rarely has more than 1 or 2 elements, always use + // shrink_and_clear so it quickly returns to the inline capacity of the + // SmallDenseMap if it ever grows larger. + // FIXME: This should really be shrink_to_inline_capacity_and_clear(). + AliasCache.shrink_and_clear(); return Alias; } @@ -483,7 +481,7 @@ namespace { private: // AliasCache - Track alias queries to guard against recursion. typedef std::pair LocPair; - typedef DenseMap AliasCacheTy; + typedef SmallDenseMap AliasCacheTy; AliasCacheTy AliasCache; // Visited - Track instructions visited by pointsToConstantMemory. -- cgit v1.1 From 029032693fdb065b6edfff6d68df188f98bee8ac Mon Sep 17 00:00:00 2001 From: Arnold Schwaighofer Date: Thu, 6 Sep 2012 14:31:51 +0000 Subject: BasicAA: GEPs of NoAlias'ing base ptr with equivalent indices are NoAlias If we can show that the base pointers of two GEPs don't alias each other using precise analysis and the indices and base offset are equal then the two GEPs also don't alias each other. This is primarily needed for the follow up patch that analyses NoAlias'ing PHI nodes. Part 1/2 of fix for PR13564. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163317 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 74 ++++++++++++++++++++++++++++++++----- 1 file changed, 65 insertions(+), 9 deletions(-) (limited to 'lib/Analysis/BasicAliasAnalysis.cpp') diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index a3e6575..d537d63 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -128,6 +128,15 @@ namespace { const Value *V; ExtensionKind Extension; int64_t Scale; + + bool operator==(const VariableGEPIndex &Other) const { + return V == Other.V && Extension == Other.Extension && + Scale == Other.Scale; + } + + bool operator!=(const VariableGEPIndex &Other) const { + return !operator==(Other); + } }; } @@ -490,6 +499,7 @@ namespace { // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP // instruction against another. AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, + const MDNode *V1TBAAInfo, const Value *V2, uint64_t V2Size, const MDNode *V2TBAAInfo, const Value *UnderlyingV1, const Value *UnderlyingV2); @@ -807,6 +817,21 @@ BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); } +static bool areVarIndicesEqual(SmallVector &Indices1, + SmallVector &Indices2) { + unsigned Size1 = Indices1.size(); + unsigned Size2 = Indices2.size(); + + if (Size1 != Size2) + return false; + + for (unsigned I = 0; I != Size1; ++I) + if (Indices1[I] != Indices2[I]) + return false; + + return true; +} + /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction /// against another pointer. We know that V1 is a GEP, but we don't know /// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), @@ -814,6 +839,7 @@ BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, /// AliasAnalysis::AliasResult BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, + const MDNode *V1TBAAInfo, const Value *V2, uint64_t V2Size, const MDNode *V2TBAAInfo, const Value *UnderlyingV1, @@ -821,9 +847,41 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, int64_t GEP1BaseOffset; SmallVector GEP1VariableIndices; - // If we have two gep instructions with must-alias'ing base pointers, figure - // out if the indexes to the GEP tell us anything about the derived pointer. + // If we have two gep instructions with must-alias or not-alias'ing base + // pointers, figure out if the indexes to the GEP tell us anything about the + // derived pointer. if (const GEPOperator *GEP2 = dyn_cast(V2)) { + // Check for geps of non-aliasing underlying pointers where the offsets are + // identical. + if (V1Size == V2Size) { + // Do the base pointers alias assuming type and size. + AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, + V1TBAAInfo, UnderlyingV2, + V2Size, V2TBAAInfo); + if (PreciseBaseAlias == NoAlias) { + // See if the computed offset from the common pointer tells us about the + // relation of the resulting pointer. + int64_t GEP2BaseOffset; + SmallVector GEP2VariableIndices; + const Value *GEP2BasePtr = + DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); + const Value *GEP1BasePtr = + DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); + // DecomposeGEPExpression and GetUnderlyingObject should return the + // same result except when DecomposeGEPExpression has no TargetData. + if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { + assert(TD == 0 && + "DecomposeGEPExpression and GetUnderlyingObject disagree!"); + return MayAlias; + } + // Same offsets. + if (GEP1BaseOffset == GEP2BaseOffset && + areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) + return NoAlias; + GEP1VariableIndices.clear(); + } + } + // Do the base pointers alias? AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, UnderlyingV2, UnknownSize, 0); @@ -843,9 +901,8 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, const Value *GEP2BasePtr = DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); - // If DecomposeGEPExpression isn't able to look all the way through the - // addressing operation, we must not have TD and this is too complex for us - // to handle without it. + // DecomposeGEPExpression and GetUnderlyingObject should return the + // same result except when DecomposeGEPExpression has no TargetData. if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { assert(TD == 0 && "DecomposeGEPExpression and GetUnderlyingObject disagree!"); @@ -879,9 +936,8 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, const Value *GEP1BasePtr = DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); - // If DecomposeGEPExpression isn't able to look all the way through the - // addressing operation, we must not have TD and this is too complex for us - // to handle without it. + // DecomposeGEPExpression and GetUnderlyingObject should return the + // same result except when DecomposeGEPExpression has no TargetData. if (GEP1BasePtr != UnderlyingV1) { assert(TD == 0 && "DecomposeGEPExpression and GetUnderlyingObject disagree!"); @@ -1156,7 +1212,7 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, std::swap(O1, O2); } if (const GEPOperator *GV1 = dyn_cast(V1)) { - AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, V2TBAAInfo, O1, O2); + AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); if (Result != MayAlias) return AliasCache[Locs] = Result; } -- cgit v1.1 From 3d5f96ee1bf5189e324089976026ed09b6be9e58 Mon Sep 17 00:00:00 2001 From: Arnold Schwaighofer Date: Thu, 6 Sep 2012 14:41:53 +0000 Subject: BasicAA: Recognize cyclic NoAlias phis Enhances basic alias analysis to recognize phis whose first incoming values are NoAlias and whose other incoming values are just the phi node itself through some amount of recursion. Example: With this change basicaa reports that ptr_phi and ptr_phi2 do not alias each other. bb: ptr = ptr2 + 1 loop: ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] ... ptr_plus_one = gep ptr_phi, 1 ptr2_plus_one = gep ptr2_phi, 1 This enables the elimination of one load in code like the following: extern int foo; int test_noalias(int *ptr, int num, int* coeff) { int *ptr2 = ptr; int result = (*ptr++) * (*coeff--); while (num--) { *ptr2++ = *ptr; result += (*coeff--) * (*ptr++); } *ptr = foo; return result; } Part 2/2 of fix for PR13564. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163319 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) (limited to 'lib/Analysis/BasicAliasAnalysis.cpp') diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index d537d63..a3bc06a 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -1060,12 +1060,42 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, // on corresponding edges. if (const PHINode *PN2 = dyn_cast(V2)) if (PN2->getParent() == PN->getParent()) { + LocPair Locs(Location(PN, PNSize, PNTBAAInfo), + Location(V2, V2Size, V2TBAAInfo)); + if (PN > V2) + std::swap(Locs.first, Locs.second); + AliasResult Alias = aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo, PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), V2Size, V2TBAAInfo); if (Alias == MayAlias) return MayAlias; + + // If the first source of the PHI nodes NoAlias and the other inputs are + // the PHI node itself through some amount of recursion this does not add + // any new information so just return NoAlias. + // bb: + // ptr = ptr2 + 1 + // loop: + // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] + // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] + // ... + // ptr_plus_one = gep ptr_phi, 1 + // ptr2_plus_one = gep ptr2_phi, 1 + // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do + // not alias each other. + bool ArePhisAssumedNoAlias = false; + AliasResult OrigAliasResult; + if (Alias == NoAlias) { + // Pretend the phis do not alias. + assert(AliasCache.count(Locs) && + "There must exist an entry for the phi node"); + OrigAliasResult = AliasCache[Locs]; + AliasCache[Locs] = NoAlias; + ArePhisAssumedNoAlias = true; + } + for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { AliasResult ThisAlias = aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, @@ -1075,6 +1105,11 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, if (Alias == MayAlias) break; } + + // Reset if speculation failed. + if (ArePhisAssumedNoAlias && Alias != NoAlias) + AliasCache[Locs] = OrigAliasResult; + return Alias; } -- cgit v1.1