[PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatible
with the new pass manager, and no longer relying on analysis groups.
This builds essentially a ground-up new AA infrastructure stack for
LLVM. The core ideas are the same that are used throughout the new pass
manager: type erased polymorphism and direct composition. The design is
as follows:
- FunctionAAResults is a type-erasing alias analysis results aggregation
interface to walk a single query across a range of results from
different alias analyses. Currently this is function-specific as we
always assume that aliasing queries are *within* a function.
- AAResultBase is a CRTP utility providing stub implementations of
various parts of the alias analysis result concept, notably in several
cases in terms of other more general parts of the interface. This can
be used to implement only a narrow part of the interface rather than
the entire interface. This isn't really ideal, this logic should be
hoisted into FunctionAAResults as currently it will cause
a significant amount of redundant work, but it faithfully models the
behavior of the prior infrastructure.
- All the alias analysis passes are ported to be wrapper passes for the
legacy PM and new-style analysis passes for the new PM with a shared
result object. In some cases (most notably CFL), this is an extremely
naive approach that we should revisit when we can specialize for the
new pass manager.
- BasicAA has been restructured to reflect that it is much more
fundamentally a function analysis because it uses dominator trees and
loop info that need to be constructed for each function.
All of the references to getting alias analysis results have been
updated to use the new aggregation interface. All the preservation and
other pass management code has been updated accordingly.
The way the FunctionAAResultsWrapperPass works is to detect the
available alias analyses when run, and add them to the results object.
This means that we should be able to continue to respect when various
passes are added to the pipeline, for example adding CFL or adding TBAA
passes should just cause their results to be available and to get folded
into this. The exception to this rule is BasicAA which really needs to
be a function pass due to using dominator trees and loop info. As
a consequence, the FunctionAAResultsWrapperPass directly depends on
BasicAA and always includes it in the aggregation.
This has significant implications for preserving analyses. Generally,
most passes shouldn't bother preserving FunctionAAResultsWrapperPass
because rebuilding the results just updates the set of known AA passes.
The exception to this rule are LoopPass instances which need to preserve
all the function analyses that the loop pass manager will end up
needing. This means preserving both BasicAAWrapperPass and the
aggregating FunctionAAResultsWrapperPass.
Now, when preserving an alias analysis, you do so by directly preserving
that analysis. This is only necessary for non-immutable-pass-provided
alias analyses though, and there are only three of interest: BasicAA,
GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is
preserved when needed because it (like DominatorTree and LoopInfo) is
marked as a CFG-only pass. I've expanded GlobalsAA into the preserved
set everywhere we previously were preserving all of AliasAnalysis, and
I've added SCEVAA in the intersection of that with where we preserve
SCEV itself.
One significant challenge to all of this is that the CGSCC passes were
actually using the alias analysis implementations by taking advantage of
a pretty amazing set of loop holes in the old pass manager's analysis
management code which allowed analysis groups to slide through in many
cases. Moving away from analysis groups makes this problem much more
obvious. To fix it, I've leveraged the flexibility the design of the new
PM components provides to just directly construct the relevant alias
analyses for the relevant functions in the IPO passes that need them.
This is a bit hacky, but should go away with the new pass manager, and
is already in many ways cleaner than the prior state.
Another significant challenge is that various facilities of the old
alias analysis infrastructure just don't fit any more. The most
significant of these is the alias analysis 'counter' pass. That pass
relied on the ability to snoop on AA queries at different points in the
analysis group chain. Instead, I'm planning to build printing
functionality directly into the aggregation layer. I've not included
that in this patch merely to keep it smaller.
Note that all of this needs a nearly complete rewrite of the AA
documentation. I'm planning to do that, but I'd like to make sure the
new design settles, and to flesh out a bit more of what it looks like in
the new pass manager first.
Differential Revision: http://reviews.llvm.org/D12080
llvm-svn: 247167
diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index a6a25f9..04e6d98 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -23,6 +23,7 @@
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
@@ -177,7 +178,7 @@
///
/// Note that this looks through extends, so the high bits may not be
/// represented in the result.
-/*static*/ const Value *BasicAliasAnalysis::GetLinearExpression(
+/*static*/ const Value *BasicAAResult::GetLinearExpression(
const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) {
@@ -331,7 +332,7 @@
/// GetUnderlyingObject and DecomposeGEPExpression must use the same search
/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
/// through pointer casts.
-/*static*/ const Value *BasicAliasAnalysis::DecomposeGEPExpression(
+/*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
const Value *V, int64_t &BaseOffs,
SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached,
const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) {
@@ -466,40 +467,21 @@
return V;
}
-//===----------------------------------------------------------------------===//
-// BasicAliasAnalysis Pass
-//===----------------------------------------------------------------------===//
-
-// Register the pass...
-char BasicAliasAnalysis::ID = 0;
-INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa",
- "Basic Alias Analysis (stateless AA impl)", false,
- true, false)
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
-INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
-INITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa",
- "Basic Alias Analysis (stateless AA impl)", false, true,
- false)
-
-ImmutablePass *llvm::createBasicAliasAnalysisPass() {
- return new BasicAliasAnalysis();
-}
-
/// Returns whether the given pointer value points to memory that is local to
/// the function, with global constants being considered local to all
/// functions.
-bool BasicAliasAnalysis::pointsToConstantMemory(const MemoryLocation &Loc,
- bool OrLocal) {
+bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
+ bool OrLocal) {
assert(Visited.empty() && "Visited must be cleared after use!");
unsigned MaxLookup = 8;
SmallVector<const Value *, 16> Worklist;
Worklist.push_back(Loc.Ptr);
do {
- const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), *DL);
+ const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
if (!Visited.insert(V).second) {
Visited.clear();
- return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+ return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
}
// An alloca instruction defines local memory.
@@ -513,7 +495,7 @@
// others. GV may even be a declaration, not a definition.
if (!GV->isConstant()) {
Visited.clear();
- return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+ return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
}
continue;
}
@@ -531,7 +513,7 @@
// Don't bother inspecting phi nodes with many operands.
if (PN->getNumIncomingValues() > MaxLookup) {
Visited.clear();
- return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+ return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
}
for (Value *IncValue : PN->incoming_values())
Worklist.push_back(IncValue);
@@ -540,7 +522,7 @@
// Otherwise be conservative.
Visited.clear();
- return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
+ return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
} while (!Worklist.empty() && --MaxLookup);
@@ -566,8 +548,7 @@
}
/// Returns the behavior when calling the given call site.
-FunctionModRefBehavior
-BasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) {
+FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
if (CS.doesNotAccessMemory())
// Can't do better than this.
return FMRB_DoesNotAccessMemory;
@@ -582,14 +563,13 @@
if (CS.onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- // The AliasAnalysis base class has some smarts, lets use them.
- return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
+ // The AAResultBase base class has some smarts, lets use them.
+ return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
}
/// Returns the behavior when calling the given function. For use when the call
/// site is not known.
-FunctionModRefBehavior
-BasicAliasAnalysis::getModRefBehavior(const Function *F) {
+FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
// If the function declares it doesn't access memory, we can't do better.
if (F->doesNotAccessMemory())
return FMRB_DoesNotAccessMemory;
@@ -603,17 +583,15 @@
if (F->onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- const TargetLibraryInfo &TLI =
- getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
if (isMemsetPattern16(F, TLI))
Min = FMRB_OnlyAccessesArgumentPointees;
// Otherwise be conservative.
- return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
+ return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
}
-ModRefInfo BasicAliasAnalysis::getArgModRefInfo(ImmutableCallSite CS,
- unsigned ArgIdx) {
+ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
+ unsigned ArgIdx) {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()))
switch (II->getIntrinsicID()) {
default:
@@ -631,14 +609,14 @@
// LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
// whenever possible.
if (CS.getCalledFunction() &&
- isMemsetPattern16(CS.getCalledFunction(), *TLI)) {
+ isMemsetPattern16(CS.getCalledFunction(), TLI)) {
assert((ArgIdx == 0 || ArgIdx == 1) &&
"Invalid argument index for memset_pattern16");
return ArgIdx ? MRI_Ref : MRI_Mod;
}
// FIXME: Handle memset_pattern4 and memset_pattern8 also.
- return AliasAnalysis::getArgModRefInfo(CS, ArgIdx);
+ return AAResultBase::getArgModRefInfo(CS, ArgIdx);
}
static bool isAssumeIntrinsic(ImmutableCallSite CS) {
@@ -649,23 +627,18 @@
return false;
}
-bool BasicAliasAnalysis::doInitialization(Module &M) {
- InitializeAliasAnalysis(this, &M.getDataLayout());
- return true;
-}
-
/// Checks to see if the specified callsite can clobber the specified memory
/// object.
///
/// Since we only look at local properties of this function, we really can't
/// say much about this query. We do, however, use simple "address taken"
/// analysis on local objects.
-ModRefInfo BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS,
- const MemoryLocation &Loc) {
+ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
+ const MemoryLocation &Loc) {
assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
"AliasAnalysis query involving multiple functions!");
- const Value *Object = GetUnderlyingObject(Loc.Ptr, *DL);
+ const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
// If this is a tail call and Loc.Ptr points to a stack location, we know that
// the tail call cannot access or modify the local stack.
@@ -697,7 +670,9 @@
// is impossible to alias the pointer we're checking. If not, we have to
// assume that the call could touch the pointer, even though it doesn't
// escape.
- if (!isNoAlias(MemoryLocation(*CI), MemoryLocation(Object))) {
+ AliasResult AR =
+ getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object));
+ if (AR) {
PassedAsArg = true;
break;
}
@@ -713,20 +688,20 @@
if (isAssumeIntrinsic(CS))
return MRI_NoModRef;
- // The AliasAnalysis base class has some smarts, lets use them.
- return AliasAnalysis::getModRefInfo(CS, Loc);
+ // The AAResultBase base class has some smarts, lets use them.
+ return AAResultBase::getModRefInfo(CS, Loc);
}
-ModRefInfo BasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS1,
- ImmutableCallSite CS2) {
+ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
+ ImmutableCallSite CS2) {
// While the assume intrinsic is marked as arbitrarily writing so that
// proper control dependencies will be maintained, it never aliases any
// particular memory location.
if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2))
return MRI_NoModRef;
- // The AliasAnalysis base class has some smarts, lets use them.
- return AliasAnalysis::getModRefInfo(CS1, CS2);
+ // The AAResultBase base class has some smarts, lets use them.
+ return AAResultBase::getModRefInfo(CS1, CS2);
}
/// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
@@ -829,34 +804,15 @@
/// We know that V1 is a GEP, but we don't know anything about V2.
/// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
/// V2.
-AliasResult BasicAliasAnalysis::aliasGEP(
- const GEPOperator *GEP1, uint64_t V1Size, const AAMDNodes &V1AAInfo,
- const Value *V2, uint64_t V2Size, const AAMDNodes &V2AAInfo,
- const Value *UnderlyingV1, const Value *UnderlyingV2) {
+AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
+ const AAMDNodes &V1AAInfo, const Value *V2,
+ uint64_t V2Size, const AAMDNodes &V2AAInfo,
+ const Value *UnderlyingV1,
+ const Value *UnderlyingV2) {
int64_t GEP1BaseOffset;
bool GEP1MaxLookupReached;
SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
- // We have to get two AssumptionCaches here because GEP1 and V2 may be from
- // different functions.
- // FIXME: This really doesn't make any sense. We get a dominator tree below
- // that can only refer to a single function. But this function (aliasGEP) is
- // a method on an immutable pass that can be called when there *isn't*
- // a single function. The old pass management layer makes this "work", but
- // this isn't really a clean solution.
- AssumptionCacheTracker &ACT = getAnalysis<AssumptionCacheTracker>();
- AssumptionCache *AC1 = nullptr, *AC2 = nullptr;
- if (auto *GEP1I = dyn_cast<Instruction>(GEP1))
- AC1 = &ACT.getAssumptionCache(
- const_cast<Function &>(*GEP1I->getParent()->getParent()));
- if (auto *I2 = dyn_cast<Instruction>(V2))
- AC2 = &ACT.getAssumptionCache(
- const_cast<Function &>(*I2->getParent()->getParent()));
-
- DominatorTreeWrapperPass *DTWP =
- getAnalysisIfAvailable<DominatorTreeWrapperPass>();
- DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
-
// 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.
@@ -880,15 +836,15 @@
SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
- GEP2MaxLookupReached, *DL, AC2, DT);
+ GEP2MaxLookupReached, DL, &AC, DT);
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- GEP1MaxLookupReached, *DL, AC1, DT);
+ GEP1MaxLookupReached, DL, &AC, DT);
// DecomposeGEPExpression and GetUnderlyingObject should return the
// same result except when DecomposeGEPExpression has no DataLayout.
+ // FIXME: They always have a DataLayout so this should become an
+ // assert.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
- assert(!DL &&
- "DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
// If the max search depth is reached the result is undefined
@@ -913,27 +869,27 @@
// about the relation of the resulting pointer.
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- GEP1MaxLookupReached, *DL, AC1, DT);
+ GEP1MaxLookupReached, DL, &AC, DT);
int64_t GEP2BaseOffset;
bool GEP2MaxLookupReached;
SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
- GEP2MaxLookupReached, *DL, AC2, DT);
+ GEP2MaxLookupReached, DL, &AC, DT);
// DecomposeGEPExpression and GetUnderlyingObject should return the
// same result except when DecomposeGEPExpression has no DataLayout.
+ // FIXME: They always have a DataLayout so this should become an assert.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
- assert(!DL && "DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
// If we know the two GEPs are based off of the exact same pointer (and not
// just the same underlying object), see if that tells us anything about
// the resulting pointers.
- if (DL && GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
- AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, *DL);
+ if (GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
+ AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
// If we couldn't find anything interesting, don't abandon just yet.
if (R != MayAlias)
return R;
@@ -970,12 +926,12 @@
const Value *GEP1BasePtr =
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- GEP1MaxLookupReached, *DL, AC1, DT);
+ GEP1MaxLookupReached, DL, &AC, DT);
// DecomposeGEPExpression and GetUnderlyingObject should return the
// same result except when DecomposeGEPExpression has no DataLayout.
+ // FIXME: They always have a DataLayout so this should become an assert.
if (GEP1BasePtr != UnderlyingV1) {
- assert(!DL && "DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
// If the max search depth is reached the result is undefined
@@ -1039,8 +995,8 @@
const Value *V = GEP1VariableIndices[i].V;
bool SignKnownZero, SignKnownOne;
- ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, *DL,
- 0, AC1, nullptr, DT);
+ ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL,
+ 0, &AC, nullptr, DT);
// Zero-extension widens the variable, and so forces the sign
// bit to zero.
@@ -1075,7 +1031,7 @@
return NoAlias;
if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size,
- GEP1BaseOffset, DL, AC1, DT))
+ GEP1BaseOffset, &AC, DT))
return NoAlias;
}
@@ -1103,11 +1059,10 @@
/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
/// against another.
-AliasResult BasicAliasAnalysis::aliasSelect(const SelectInst *SI,
- uint64_t SISize,
- const AAMDNodes &SIAAInfo,
- const Value *V2, uint64_t V2Size,
- const AAMDNodes &V2AAInfo) {
+AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
+ const AAMDNodes &SIAAInfo,
+ const Value *V2, uint64_t V2Size,
+ const AAMDNodes &V2AAInfo) {
// 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<SelectInst>(V2))
@@ -1136,10 +1091,10 @@
/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
/// another.
-AliasResult BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
- const AAMDNodes &PNAAInfo,
- const Value *V2, uint64_t V2Size,
- const AAMDNodes &V2AAInfo) {
+AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
+ const AAMDNodes &PNAAInfo, const Value *V2,
+ uint64_t V2Size,
+ const AAMDNodes &V2AAInfo) {
// Track phi nodes we have visited. We use this information when we determine
// value equivalence.
VisitedPhiBBs.insert(PN->getParent());
@@ -1242,10 +1197,9 @@
/// Provideis a bunch of ad-hoc rules to disambiguate in common cases, such as
/// array references.
-AliasResult BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
- AAMDNodes V1AAInfo, const Value *V2,
- uint64_t V2Size,
- AAMDNodes V2AAInfo) {
+AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
+ AAMDNodes V1AAInfo, const Value *V2,
+ uint64_t V2Size, AAMDNodes V2AAInfo) {
// If either of the memory references is empty, it doesn't matter what the
// pointer values are.
if (V1Size == 0 || V2Size == 0)
@@ -1273,8 +1227,8 @@
return NoAlias; // Scalars cannot alias each other
// Figure out what objects these things are pointing to if we can.
- const Value *O1 = GetUnderlyingObject(V1, *DL, MaxLookupSearchDepth);
- const Value *O2 = GetUnderlyingObject(V2, *DL, MaxLookupSearchDepth);
+ const Value *O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
+ const Value *O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
// Null values in the default address space don't point to any object, so they
// don't alias any other pointer.
@@ -1323,12 +1277,11 @@
// 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 (DL)
- if ((V1Size != MemoryLocation::UnknownSize &&
- isObjectSmallerThan(O2, V1Size, *DL, *TLI)) ||
- (V2Size != MemoryLocation::UnknownSize &&
- isObjectSmallerThan(O1, V2Size, *DL, *TLI)))
- return NoAlias;
+ if ((V1Size != MemoryLocation::UnknownSize &&
+ isObjectSmallerThan(O2, V1Size, DL, TLI)) ||
+ (V2Size != MemoryLocation::UnknownSize &&
+ isObjectSmallerThan(O1, V2Size, DL, TLI)))
+ return NoAlias;
// Check the cache before climbing up use-def chains. This also terminates
// otherwise infinitely recursive queries.
@@ -1382,16 +1335,17 @@
// If both pointers are pointing into the same object and one of them
// accesses is accessing the entire object, then the accesses must
// overlap in some way.
- if (DL && O1 == O2)
+ if (O1 == O2)
if ((V1Size != MemoryLocation::UnknownSize &&
- isObjectSize(O1, V1Size, *DL, *TLI)) ||
+ isObjectSize(O1, V1Size, DL, TLI)) ||
(V2Size != MemoryLocation::UnknownSize &&
- isObjectSize(O2, V2Size, *DL, *TLI)))
+ isObjectSize(O2, V2Size, DL, TLI)))
return AliasCache[Locs] = PartialAlias;
- AliasResult Result =
- AliasAnalysis::alias(MemoryLocation(V1, V1Size, V1AAInfo),
- MemoryLocation(V2, V2Size, V2AAInfo));
+ // 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);
return AliasCache[Locs] = Result;
}
@@ -1402,8 +1356,8 @@
/// visited phi nodes an making sure that the phis cannot reach the value. We
/// have to do this because we are looking through phi nodes (That is we say
/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
-bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V,
- const Value *V2) {
+bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
+ const Value *V2) {
if (V != V2)
return false;
@@ -1417,13 +1371,6 @@
if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
return false;
- // Use dominance or loop info if available.
- DominatorTreeWrapperPass *DTWP =
- getAnalysisIfAvailable<DominatorTreeWrapperPass>();
- DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
- auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
- LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
-
// Make sure that the visited phis cannot reach the Value. This ensures that
// the Values cannot come from different iterations of a potential cycle the
// phi nodes could be involved in.
@@ -1438,7 +1385,7 @@
///
/// Dest and Src are the variable indices from two decomposed GetElementPtr
/// instructions GEP1 and GEP2 which have common base pointers.
-void BasicAliasAnalysis::GetIndexDifference(
+void BasicAAResult::GetIndexDifference(
SmallVectorImpl<VariableGEPIndex> &Dest,
const SmallVectorImpl<VariableGEPIndex> &Src) {
if (Src.empty())
@@ -1474,12 +1421,12 @@
}
}
-bool BasicAliasAnalysis::constantOffsetHeuristic(
+bool BasicAAResult::constantOffsetHeuristic(
const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size,
- uint64_t V2Size, int64_t BaseOffset, const DataLayout *DL,
- AssumptionCache *AC, DominatorTree *DT) {
+ uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC,
+ DominatorTree *DT) {
if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
- V2Size == MemoryLocation::UnknownSize || !DL)
+ V2Size == MemoryLocation::UnknownSize)
return false;
const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
@@ -1499,10 +1446,10 @@
bool NSW = true, NUW = true;
unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
- V0SExtBits, *DL, 0, AC, DT, NSW, NUW);
+ V0SExtBits, DL, 0, AC, DT, NSW, NUW);
NSW = true, NUW = true;
const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
- V1SExtBits, *DL, 0, AC, DT, NSW, NUW);
+ V1SExtBits, DL, 0, AC, DT, NSW, NUW);
if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
@@ -1527,3 +1474,58 @@
return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
V2Size + std::abs(BaseOffset) <= MinDiffBytes;
}
+
+//===----------------------------------------------------------------------===//
+// BasicAliasAnalysis Pass
+//===----------------------------------------------------------------------===//
+
+char BasicAA::PassID;
+
+BasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) {
+ return BasicAAResult(F.getParent()->getDataLayout(),
+ AM->getResult<TargetLibraryAnalysis>(F),
+ AM->getResult<AssumptionAnalysis>(F),
+ AM->getCachedResult<DominatorTreeAnalysis>(F),
+ AM->getCachedResult<LoopAnalysis>(F));
+}
+
+char BasicAAWrapperPass::ID = 0;
+void BasicAAWrapperPass::anchor() {}
+
+INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
+ "Basic Alias Analysis (stateless AA impl)", true, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
+ "Basic Alias Analysis (stateless AA impl)", true, true)
+
+FunctionPass *llvm::createBasicAAWrapperPass() {
+ return new BasicAAWrapperPass();
+}
+
+bool BasicAAWrapperPass::runOnFunction(Function &F) {
+ auto &ACT = getAnalysis<AssumptionCacheTracker>();
+ auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
+ auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+ auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
+
+ Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
+ ACT.getAssumptionCache(F),
+ DTWP ? &DTWP->getDomTree() : nullptr,
+ LIWP ? &LIWP->getLoopInfo() : nullptr));
+
+ return false;
+}
+
+void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<AssumptionCacheTracker>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
+}
+
+BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
+ return BasicAAResult(
+ F.getParent()->getDataLayout(),
+ P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+ P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
+}