summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp
diff options
context:
space:
mode:
authordim <dim@FreeBSD.org>2016-12-26 20:36:37 +0000
committerdim <dim@FreeBSD.org>2016-12-26 20:36:37 +0000
commit06210ae42d418d50d8d9365d5c9419308ae9e7ee (patch)
treeab60b4cdd6e430dda1f292a46a77ddb744723f31 /contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp
parent2dd166267f53df1c3748b4325d294b9b839de74b (diff)
downloadFreeBSD-src-06210ae42d418d50d8d9365d5c9419308ae9e7ee.zip
FreeBSD-src-06210ae42d418d50d8d9365d5c9419308ae9e7ee.tar.gz
MFC r309124:
Upgrade our copies of clang, llvm, lldb, compiler-rt and libc++ to 3.9.0 release, and add lld 3.9.0. Also completely revamp the build system for clang, llvm, lldb and their related tools. Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11 support to build; see UPDATING for more information. Release notes for llvm, clang and lld are available here: <http://llvm.org/releases/3.9.0/docs/ReleaseNotes.html> <http://llvm.org/releases/3.9.0/tools/clang/docs/ReleaseNotes.html> <http://llvm.org/releases/3.9.0/tools/lld/docs/ReleaseNotes.html> Thanks to Ed Maste, Bryan Drewery, Andrew Turner, Antoine Brodin and Jan Beich for their help. Relnotes: yes MFC r309147: Pull in r282174 from upstream llvm trunk (by Krzysztof Parzyszek): [PPC] Set SP after loading data from stack frame, if no red zone is present Follow-up to r280705: Make sure that the SP is only restored after all data is loaded from the stack frame, if there is no red zone. This completes the fix for https://llvm.org/bugs/show_bug.cgi?id=26519. Differential Revision: https://reviews.llvm.org/D24466 Reported by: Mark Millard PR: 214433 MFC r309149: Pull in r283060 from upstream llvm trunk (by Hal Finkel): [PowerPC] Refactor soft-float support, and enable PPC64 soft float This change enables soft-float for PowerPC64, and also makes soft-float disable all vector instruction sets for both 32-bit and 64-bit modes. This latter part is necessary because the PPC backend canonicalizes many Altivec vector types to floating-point types, and so soft-float breaks scalarization support for many operations. Both for embedded targets and for operating-system kernels desiring soft-float support, it seems reasonable that disabling hardware floating-point also disables vector instructions (embedded targets without hardware floating point support are unlikely to have Altivec, etc. and operating system kernels desiring not to use floating-point registers to lower syscall cost are unlikely to want to use vector registers either). If someone needs this to work, we'll need to change the fact that we promote many Altivec operations to act on v4f32. To make it possible to disable Altivec when soft-float is enabled, hardware floating-point support needs to be expressed as a positive feature, like the others, and not a negative feature, because target features cannot have dependencies on the disabling of some other feature. So +soft-float has now become -hard-float. Fixes PR26970. Pull in r283061 from upstream clang trunk (by Hal Finkel): [PowerPC] Enable soft-float for PPC64, and +soft-float -> -hard-float Enable soft-float support on PPC64, as the backend now supports it. Also, the backend now uses -hard-float instead of +soft-float, so set the target features accordingly. Fixes PR26970. Reported by: Mark Millard PR: 214433 MFC r309212: Add a few missed clang 3.9.0 files to OptionalObsoleteFiles. MFC r309262: Fix packaging for clang, lldb and lld 3.9.0 During the upgrade of clang/llvm etc to 3.9.0 in r309124, the PACKAGE directive in the usr.bin/clang/*.mk files got dropped accidentally. Restore it, with a few minor changes and additions: * Correct license in clang.ucl to NCSA * Add PACKAGE=clang for clang and most of the "ll" tools * Put lldb in its own package * Put lld in its own package Reviewed by: gjb, jmallett Differential Revision: https://reviews.freebsd.org/D8666 MFC r309656: During the bootstrap phase, when building the minimal llvm library on PowerPC, add lib/Support/Atomic.cpp. This is needed because upstream llvm revision r271821 disabled the use of std::call_once, which causes some fallback functions from Atomic.cpp to be used instead. Reported by: Mark Millard PR: 214902 MFC r309835: Tentatively apply https://reviews.llvm.org/D18730 to work around gcc PR 70528 (bogus error: constructor required before non-static data member). This should fix buildworld with the external gcc package. Reported by: https://jenkins.freebsd.org/job/FreeBSD_HEAD_amd64_gcc/ MFC r310194: Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to 3.9.1 release. Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11 support to build; see UPDATING for more information. Release notes for llvm, clang and lld will be available here: <http://releases.llvm.org/3.9.1/docs/ReleaseNotes.html> <http://releases.llvm.org/3.9.1/tools/clang/docs/ReleaseNotes.html> <http://releases.llvm.org/3.9.1/tools/lld/docs/ReleaseNotes.html> Relnotes: yes
Diffstat (limited to 'contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp')
-rw-r--r--contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp425
1 files changed, 259 insertions, 166 deletions
diff --git a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index c3d2803..43d5c3c 100644
--- a/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/contrib/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -37,22 +37,23 @@
#include "llvm/Pass.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
+
+#define DEBUG_TYPE "basicaa"
+
using namespace llvm;
/// Enable analysis of recursive PHI nodes.
static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
cl::init(false));
-
/// SearchLimitReached / SearchTimes shows how often the limit of
/// to decompose GEPs is reached. It will affect the precision
/// of basic alias analysis.
-#define DEBUG_TYPE "basicaa"
STATISTIC(SearchLimitReached, "Number of times the limit to "
"decompose GEPs is reached");
STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
/// Cutoff after which to stop analysing a set of phi nodes potentially involved
-/// in a cycle. Because we are analysing 'through' phi nodes we need to be
+/// in a cycle. Because we are analysing 'through' phi nodes, we need to be
/// careful with value equivalence. We use reachability to make sure a value
/// cannot be involved in a cycle.
const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
@@ -83,7 +84,7 @@ static bool isNonEscapingLocalObject(const Value *V) {
// inside the function.
if (const Argument *A = dyn_cast<Argument>(V))
if (A->hasByValAttr() || A->hasNoAliasAttr())
- // Note even if the argument is marked nocapture we still need to check
+ // Note even if the argument is marked nocapture, we still need to check
// for copies made inside the function. The nocapture attribute only
// specifies that there are no copies made that outlive the function.
return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
@@ -106,7 +107,7 @@ static bool isEscapeSource(const Value *V) {
return false;
}
-/// Returns the size of the object specified by V, or UnknownSize if unknown.
+/// Returns the size of the object specified by V or UnknownSize if unknown.
static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
const TargetLibraryInfo &TLI,
bool RoundToAlign = false) {
@@ -173,7 +174,7 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
///
/// Returns the scale and offset values as APInts and return V as a Value*, and
/// return whether we looked through any sign or zero extends. The incoming
-/// Value is known to have IntegerType and it may already be sign or zero
+/// Value is known to have IntegerType, and it may already be sign or zero
/// extended.
///
/// Note that this looks through extends, so the high bits may not be
@@ -192,8 +193,8 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
}
if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
- // if it's a constant, just convert it to an offset and remove the variable.
- // If we've been called recursively the Offset bit width will be greater
+ // If it's a constant, just convert it to an offset and remove the variable.
+ // If we've been called recursively, the Offset bit width will be greater
// than the constant's (the Offset's always as wide as the outermost call),
// so we'll zext here and process any extension in the isa<SExtInst> &
// isa<ZExtInst> cases below.
@@ -205,8 +206,8 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
- // If we've been called recursively then Offset and Scale will be wider
- // that the BOp operands. We'll always zext it here as we'll process sign
+ // If we've been called recursively, then Offset and Scale will be wider
+ // than the BOp operands. We'll always zext it here as we'll process sign
// extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
@@ -319,6 +320,16 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
return V;
}
+/// To ensure a pointer offset fits in an integer of size PointerSize
+/// (in bits) when that size is smaller than 64. This is an issue in
+/// particular for 32b programs with negative indices that rely on two's
+/// complement wrap-arounds for precise alias information.
+static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
+ assert(PointerSize <= 64 && "Invalid PointerSize!");
+ unsigned ShiftBits = 64 - PointerSize;
+ return (int64_t)((uint64_t)Offset << ShiftBits) >> ShiftBits;
+}
+
/// If V is a symbolic pointer expression, decompose it into a base pointer
/// with a constant offset and a number of scaled symbolic offsets.
///
@@ -332,28 +343,29 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
/// GetUnderlyingObject and DecomposeGEPExpression must use the same search
/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
/// through pointer casts.
-/*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
- const Value *V, int64_t &BaseOffs,
- SmallVectorImpl<VariableGEPIndex> &VarIndices, bool &MaxLookupReached,
- const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) {
+bool BasicAAResult::DecomposeGEPExpression(const Value *V,
+ DecomposedGEP &Decomposed, const DataLayout &DL, AssumptionCache *AC,
+ DominatorTree *DT) {
// Limit recursion depth to limit compile time in crazy cases.
unsigned MaxLookup = MaxLookupSearchDepth;
- MaxLookupReached = false;
SearchTimes++;
- BaseOffs = 0;
+ Decomposed.StructOffset = 0;
+ Decomposed.OtherOffset = 0;
+ Decomposed.VarIndices.clear();
do {
// See if this is a bitcast or GEP.
const Operator *Op = dyn_cast<Operator>(V);
if (!Op) {
// The only non-operator case we can handle are GlobalAliases.
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
- if (!GA->mayBeOverridden()) {
+ if (!GA->isInterposable()) {
V = GA->getAliasee();
continue;
}
}
- return V;
+ Decomposed.Base = V;
+ return false;
}
if (Op->getOpcode() == Instruction::BitCast ||
@@ -364,6 +376,12 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
if (!GEPOp) {
+ if (auto CS = ImmutableCallSite(V))
+ if (const Value *RV = CS.getReturnedArgOperand()) {
+ V = RV;
+ continue;
+ }
+
// If it's not a GEP, hand it off to SimplifyInstruction to see if it
// can come up with something. This matches what GetUnderlyingObject does.
if (const Instruction *I = dyn_cast<Instruction>(V))
@@ -377,16 +395,20 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
continue;
}
- return V;
+ Decomposed.Base = V;
+ return false;
}
// Don't attempt to analyze GEPs over unsized objects.
- if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
- return V;
+ if (!GEPOp->getSourceElementType()->isSized()) {
+ Decomposed.Base = V;
+ return false;
+ }
unsigned AS = GEPOp->getPointerAddressSpace();
// Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
gep_type_iterator GTI = gep_type_begin(GEPOp);
+ unsigned PointerSize = DL.getPointerSizeInBits(AS);
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
I != E; ++I) {
const Value *Index = *I;
@@ -397,7 +419,8 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
if (FieldNo == 0)
continue;
- BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo);
+ Decomposed.StructOffset +=
+ DL.getStructLayout(STy)->getElementOffset(FieldNo);
continue;
}
@@ -405,7 +428,8 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
if (CIdx->isZero())
continue;
- BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
+ Decomposed.OtherOffset +=
+ DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
continue;
}
@@ -415,7 +439,6 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
// If the integer type is smaller than the pointer size, it is implicitly
// sign extended to pointer size.
unsigned Width = Index->getType()->getIntegerBitWidth();
- unsigned PointerSize = DL.getPointerSizeInBits(AS);
if (PointerSize > Width)
SExtBits += PointerSize - Width;
@@ -427,44 +450,48 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
// The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
// This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
- BaseOffs += IndexOffset.getSExtValue() * Scale;
+ Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
Scale *= IndexScale.getSExtValue();
// If we already had an occurrence of this index variable, merge this
// scale into it. For example, we want to handle:
// A[x][x] -> x*16 + x*4 -> x*20
// This also ensures that 'x' only appears in the index list once.
- for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
- if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits &&
- VarIndices[i].SExtBits == SExtBits) {
- Scale += VarIndices[i].Scale;
- VarIndices.erase(VarIndices.begin() + i);
+ for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
+ if (Decomposed.VarIndices[i].V == Index &&
+ Decomposed.VarIndices[i].ZExtBits == ZExtBits &&
+ Decomposed.VarIndices[i].SExtBits == SExtBits) {
+ Scale += Decomposed.VarIndices[i].Scale;
+ Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
break;
}
}
// Make sure that we have a scale that makes sense for this target's
// pointer size.
- if (unsigned ShiftBits = 64 - PointerSize) {
- Scale <<= ShiftBits;
- Scale = (int64_t)Scale >> ShiftBits;
- }
+ Scale = adjustToPointerSize(Scale, PointerSize);
if (Scale) {
VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
static_cast<int64_t>(Scale)};
- VarIndices.push_back(Entry);
+ Decomposed.VarIndices.push_back(Entry);
}
}
+ // Take care of wrap-arounds
+ Decomposed.StructOffset =
+ adjustToPointerSize(Decomposed.StructOffset, PointerSize);
+ Decomposed.OtherOffset =
+ adjustToPointerSize(Decomposed.OtherOffset, PointerSize);
+
// Analyze the base pointer next.
V = GEPOp->getOperand(0);
} while (--MaxLookup);
// If the chain of expressions is too deep, just return early.
- MaxLookupReached = true;
+ Decomposed.Base = V;
SearchLimitReached++;
- return V;
+ return true;
}
/// Returns whether the given pointer value points to memory that is local to
@@ -530,22 +557,6 @@ bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
return Worklist.empty();
}
-// FIXME: This code is duplicated with MemoryLocation and should be hoisted to
-// some common utility location.
-static bool isMemsetPattern16(const Function *MS,
- const TargetLibraryInfo &TLI) {
- if (TLI.has(LibFunc::memset_pattern16) &&
- MS->getName() == "memset_pattern16") {
- FunctionType *MemsetType = MS->getFunctionType();
- if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 &&
- isa<PointerType>(MemsetType->getParamType(0)) &&
- isa<PointerType>(MemsetType->getParamType(1)) &&
- isa<IntegerType>(MemsetType->getParamType(2)))
- return true;
- }
- return false;
-}
-
/// Returns the behavior when calling the given call site.
FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
if (CS.doesNotAccessMemory())
@@ -558,12 +569,21 @@ FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
// than that.
if (CS.onlyReadsMemory())
Min = FMRB_OnlyReadsMemory;
+ else if (CS.doesNotReadMemory())
+ Min = FMRB_DoesNotReadMemory;
if (CS.onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- // The AAResultBase base class has some smarts, lets use them.
- return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
+ // If CS has operand bundles then aliasing attributes from the function it
+ // calls do not directly apply to the CallSite. This can be made more
+ // precise in the future.
+ if (!CS.hasOperandBundles())
+ if (const Function *F = CS.getCalledFunction())
+ Min =
+ FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F));
+
+ return Min;
}
/// Returns the behavior when calling the given function. For use when the call
@@ -578,41 +598,30 @@ FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
// If the function declares it only reads memory, go with that.
if (F->onlyReadsMemory())
Min = FMRB_OnlyReadsMemory;
+ else if (F->doesNotReadMemory())
+ Min = FMRB_DoesNotReadMemory;
if (F->onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- // Otherwise be conservative.
- return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
+ return Min;
}
-/// Returns true if this is a writeonly (i.e Mod only) parameter. Currently,
-/// we don't have a writeonly attribute, so this only knows about builtin
-/// intrinsics and target library functions. We could consider adding a
-/// writeonly attribute in the future and moving all of these facts to either
-/// Intrinsics.td or InferFunctionAttr.cpp
+/// Returns true if this is a writeonly (i.e Mod only) parameter.
static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
const TargetLibraryInfo &TLI) {
- if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()))
- switch (II->getIntrinsicID()) {
- default:
- break;
- case Intrinsic::memset:
- case Intrinsic::memcpy:
- case Intrinsic::memmove:
- // We don't currently have a writeonly attribute. All other properties
- // of these intrinsics are nicely described via attributes in
- // Intrinsics.td and handled generically.
- if (ArgIdx == 0)
- return true;
- }
+ if (CS.paramHasAttr(ArgIdx + 1, Attribute::WriteOnly))
+ return true;
// We can bound the aliasing properties of memset_pattern16 just as we can
// for memcpy/memset. This is particularly important because the
// LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
- // whenever possible. Note that all but the missing writeonly attribute are
- // handled via InferFunctionAttr.
- if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI))
+ // whenever possible.
+ // FIXME Consider handling this in InferFunctionAttr.cpp together with other
+ // attributes.
+ LibFunc::Func F;
+ if (CS.getCalledFunction() && TLI.getLibFunc(*CS.getCalledFunction(), F) &&
+ F == LibFunc::memset_pattern16 && TLI.has(F))
if (ArgIdx == 0)
return true;
@@ -626,8 +635,7 @@ static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
unsigned ArgIdx) {
- // Emulate the missing writeonly attribute by checking for known builtin
- // intrinsics and target library functions.
+ // Checking for known builtin intrinsics and target library functions.
if (isWriteOnlyParam(CS, ArgIdx, TLI))
return MRI_Mod;
@@ -640,9 +648,9 @@ ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
return AAResultBase::getArgModRefInfo(CS, ArgIdx);
}
-static bool isAssumeIntrinsic(ImmutableCallSite CS) {
+static bool isIntrinsicCall(ImmutableCallSite CS, Intrinsic::ID IID) {
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
- return II && II->getIntrinsicID() == Intrinsic::assume;
+ return II && II->getIntrinsicID() == IID;
}
#ifndef NDEBUG
@@ -717,14 +725,14 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
isNonEscapingLocalObject(Object)) {
bool PassedAsArg = false;
- unsigned ArgNo = 0;
- for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
- CI != CE; ++CI, ++ArgNo) {
+ unsigned OperandNo = 0;
+ for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
+ CI != CE; ++CI, ++OperandNo) {
// Only look at the no-capture or byval pointer arguments. If this
// pointer were passed to arguments that were neither of these, then it
// couldn't be no-capture.
if (!(*CI)->getType()->isPointerTy() ||
- (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
+ (!CS.doesNotCapture(OperandNo) && !CS.isByValArgument(OperandNo)))
continue;
// If this is a no-capture pointer argument, see if we can tell that it
@@ -743,12 +751,36 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
return MRI_NoModRef;
}
+ // If the CallSite is to malloc or calloc, we can assume that it doesn't
+ // modify any IR visible value. This is only valid because we assume these
+ // routines do not read values visible in the IR. TODO: Consider special
+ // casing realloc and strdup routines which access only their arguments as
+ // well. Or alternatively, replace all of this with inaccessiblememonly once
+ // that's implemented fully.
+ auto *Inst = CS.getInstruction();
+ if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI)) {
+ // Be conservative if the accessed pointer may alias the allocation -
+ // fallback to the generic handling below.
+ if (getBestAAResults().alias(MemoryLocation(Inst), Loc) == NoAlias)
+ return MRI_NoModRef;
+ }
+
// 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(CS))
+ if (isIntrinsicCall(CS, Intrinsic::assume))
return MRI_NoModRef;
+ // Like assumes, guard intrinsics are also marked as arbitrarily writing so
+ // that proper control dependencies are maintained but they never mods any
+ // particular memory location.
+ //
+ // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
+ // heap state at the point the guard is issued needs to be consistent in case
+ // the guard invokes the "deopt" continuation.
+ if (isIntrinsicCall(CS, Intrinsic::experimental_guard))
+ return MRI_Ref;
+
// The AAResultBase base class has some smarts, lets use them.
return AAResultBase::getModRefInfo(CS, Loc);
}
@@ -758,9 +790,27 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
// 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))
+ if (isIntrinsicCall(CS1, Intrinsic::assume) ||
+ isIntrinsicCall(CS2, Intrinsic::assume))
return MRI_NoModRef;
+ // Like assumes, guard intrinsics are also marked as arbitrarily writing so
+ // that proper control dependencies are maintained but they never mod any
+ // particular memory location.
+ //
+ // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
+ // heap state at the point the guard is issued needs to be consistent in case
+ // the guard invokes the "deopt" continuation.
+
+ // NB! This function is *not* commutative, so we specical case two
+ // possibilities for guard intrinsics.
+
+ if (isIntrinsicCall(CS1, Intrinsic::experimental_guard))
+ return getModRefBehavior(CS2) & MRI_Mod ? MRI_Ref : MRI_NoModRef;
+
+ if (isIntrinsicCall(CS2, Intrinsic::experimental_guard))
+ return getModRefBehavior(CS1) & MRI_Mod ? MRI_Mod : MRI_NoModRef;
+
// The AAResultBase base class has some smarts, lets use them.
return AAResultBase::getModRefInfo(CS1, CS2);
}
@@ -773,7 +823,10 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
uint64_t V2Size,
const DataLayout &DL) {
- assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() &&
+ assert(GEP1->getPointerOperand()->stripPointerCasts() ==
+ GEP2->getPointerOperand()->stripPointerCasts() &&
+ GEP1->getPointerOperand()->getType() ==
+ GEP2->getPointerOperand()->getType() &&
"Expected GEPs with the same pointer operand");
// Try to determine whether GEP1 and GEP2 index through arrays, into structs,
@@ -796,7 +849,7 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
// If the last (struct) indices are constants and are equal, the other indices
// might be also be dynamically equal, so the GEPs can alias.
- if (C1 && C2 && C1 == C2)
+ if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
return MayAlias;
// Find the last-indexed type of the GEP, i.e., the type you'd get if
@@ -895,6 +948,67 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
return MayAlias;
}
+// If a we have (a) a GEP and (b) a pointer based on an alloca, and the
+// beginning of the object the GEP points would have a negative offset with
+// repsect to the alloca, that means the GEP can not alias pointer (b).
+// Note that the pointer based on the alloca may not be a GEP. For
+// example, it may be the alloca itself.
+// The same applies if (b) is based on a GlobalVariable. Note that just being
+// based on isIdentifiedObject() is not enough - we need an identified object
+// that does not permit access to negative offsets. For example, a negative
+// offset from a noalias argument or call can be inbounds w.r.t the actual
+// underlying object.
+//
+// For example, consider:
+//
+// struct { int f0, int f1, ...} foo;
+// foo alloca;
+// foo* random = bar(alloca);
+// int *f0 = &alloca.f0
+// int *f1 = &random->f1;
+//
+// Which is lowered, approximately, to:
+//
+// %alloca = alloca %struct.foo
+// %random = call %struct.foo* @random(%struct.foo* %alloca)
+// %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
+// %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
+//
+// Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
+// by %alloca. Since the %f1 GEP is inbounds, that means %random must also
+// point into the same object. But since %f0 points to the beginning of %alloca,
+// the highest %f1 can be is (%alloca + 3). This means %random can not be higher
+// than (%alloca - 1), and so is not inbounds, a contradiction.
+bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
+ const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
+ uint64_t ObjectAccessSize) {
+ // If the object access size is unknown, or the GEP isn't inbounds, bail.
+ if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
+ return false;
+
+ // We need the object to be an alloca or a globalvariable, and want to know
+ // the offset of the pointer from the object precisely, so no variable
+ // indices are allowed.
+ if (!(isa<AllocaInst>(DecompObject.Base) ||
+ isa<GlobalVariable>(DecompObject.Base)) ||
+ !DecompObject.VarIndices.empty())
+ return false;
+
+ int64_t ObjectBaseOffset = DecompObject.StructOffset +
+ DecompObject.OtherOffset;
+
+ // If the GEP has no variable indices, we know the precise offset
+ // from the base, then use it. If the GEP has variable indices, we're in
+ // a bit more trouble: we can't count on the constant offsets that come
+ // from non-struct sources, since these can be "rewound" by a negative
+ // variable offset. So use only offsets that came from structs.
+ int64_t GEPBaseOffset = DecompGEP.StructOffset;
+ if (DecompGEP.VarIndices.empty())
+ GEPBaseOffset += DecompGEP.OtherOffset;
+
+ return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
+}
+
/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
/// another pointer.
///
@@ -906,14 +1020,34 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
uint64_t V2Size, const AAMDNodes &V2AAInfo,
const Value *UnderlyingV1,
const Value *UnderlyingV2) {
- int64_t GEP1BaseOffset;
- bool GEP1MaxLookupReached;
- SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
-
+ DecomposedGEP DecompGEP1, DecompGEP2;
+ bool GEP1MaxLookupReached =
+ DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
+ bool GEP2MaxLookupReached =
+ DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
+
+ int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
+ int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
+
+ assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
+ "DecomposeGEPExpression returned a result different from "
+ "GetUnderlyingObject");
+
+ // If the GEP's offset relative to its base is such that the base would
+ // fall below the start of the object underlying V2, then the GEP and V2
+ // cannot alias.
+ if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
+ isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
+ return NoAlias;
// 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<GEPOperator>(V2)) {
+ // Check for the GEP base being at a negative offset, this time in the other
+ // direction.
+ if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
+ isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
+ return NoAlias;
// Do the base pointers alias?
AliasResult BaseAlias =
aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
@@ -928,31 +1062,14 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
if (PreciseBaseAlias == NoAlias) {
// See if the computed offset from the common pointer tells us about the
// relation of the resulting pointer.
- int64_t GEP2BaseOffset;
- bool GEP2MaxLookupReached;
- SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
- const Value *GEP2BasePtr =
- DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
- GEP2MaxLookupReached, DL, &AC, DT);
- const Value *GEP1BasePtr =
- DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- 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) {
- return MayAlias;
- }
// If the max search depth is reached the result is undefined
if (GEP2MaxLookupReached || GEP1MaxLookupReached)
return MayAlias;
// Same offsets.
if (GEP1BaseOffset == GEP2BaseOffset &&
- GEP1VariableIndices == GEP2VariableIndices)
+ DecompGEP1.VarIndices == DecompGEP2.VarIndices)
return NoAlias;
- GEP1VariableIndices.clear();
}
}
@@ -964,42 +1081,27 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// Otherwise, we have a MustAlias. Since the base pointers alias each other
// exactly, see if the computed offset from the common pointer tells us
// about the relation of the resulting pointer.
- const Value *GEP1BasePtr =
- DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- GEP1MaxLookupReached, DL, &AC, DT);
-
- int64_t GEP2BaseOffset;
- bool GEP2MaxLookupReached;
- SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
- const Value *GEP2BasePtr =
- DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
- 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) {
- 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 (GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
+ if (GEP1->getPointerOperand()->stripPointerCasts() ==
+ GEP2->getPointerOperand()->stripPointerCasts() &&
+ GEP1->getPointerOperand()->getType() ==
+ GEP2->getPointerOperand()->getType()) {
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;
}
- // If the max search depth is reached the result is undefined
+ // If the max search depth is reached, the result is undefined
if (GEP2MaxLookupReached || GEP1MaxLookupReached)
return MayAlias;
// Subtract the GEP2 pointer from the GEP1 pointer to find out their
// symbolic difference.
GEP1BaseOffset -= GEP2BaseOffset;
- GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices);
+ GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
} else {
// Check to see if these two pointers are related by the getelementptr
@@ -1021,16 +1123,6 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// with the first operand of the getelementptr".
return R;
- const Value *GEP1BasePtr =
- DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
- 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) {
- return MayAlias;
- }
// If the max search depth is reached the result is undefined
if (GEP1MaxLookupReached)
return MayAlias;
@@ -1038,18 +1130,18 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// In the two GEP Case, if there is no difference in the offsets of the
// computed pointers, the resultant pointers are a must alias. This
- // hapens when we have two lexically identical GEP's (for example).
+ // happens when we have two lexically identical GEP's (for example).
//
// In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
// must aliases the GEP, the end result is a must alias also.
- if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty())
+ if (GEP1BaseOffset == 0 && DecompGEP1.VarIndices.empty())
return MustAlias;
// If there is a constant difference between the pointers, but the difference
// is less than the size of the associated memory object, then we know
// that the objects are partially overlapping. If the difference is
// greater, we know they do not overlap.
- if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) {
+ if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
if (GEP1BaseOffset >= 0) {
if (V2Size != MemoryLocation::UnknownSize) {
if ((uint64_t)GEP1BaseOffset < V2Size)
@@ -1074,22 +1166,22 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
}
}
- if (!GEP1VariableIndices.empty()) {
+ if (!DecompGEP1.VarIndices.empty()) {
uint64_t Modulo = 0;
bool AllPositive = true;
- for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
+ for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
// Try to distinguish something like &A[i][1] against &A[42][0].
// Grab the least significant bit set in any of the scales. We
// don't need std::abs here (even if the scale's negative) as we'll
// be ^'ing Modulo with itself later.
- Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
+ Modulo |= (uint64_t)DecompGEP1.VarIndices[i].Scale;
if (AllPositive) {
// If the Value could change between cycles, then any reasoning about
// the Value this cycle may not hold in the next cycle. We'll just
// give up if we can't determine conditions that hold for every cycle:
- const Value *V = GEP1VariableIndices[i].V;
+ const Value *V = DecompGEP1.VarIndices[i].V;
bool SignKnownZero, SignKnownOne;
ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL,
@@ -1097,14 +1189,14 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
// Zero-extension widens the variable, and so forces the sign
// bit to zero.
- bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
+ bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
SignKnownZero |= IsZExt;
SignKnownOne &= !IsZExt;
// If the variable begins with a zero then we know it's
// positive, regardless of whether the value is signed or
// unsigned.
- int64_t Scale = GEP1VariableIndices[i].Scale;
+ int64_t Scale = DecompGEP1.VarIndices[i].Scale;
AllPositive =
(SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
}
@@ -1127,7 +1219,7 @@ AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
return NoAlias;
- if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size,
+ if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
GEP1BaseOffset, &AC, DT))
return NoAlias;
}
@@ -1312,7 +1404,7 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
return NoAlias;
// Are we checking for alias of the same value?
- // Because we look 'through' phi nodes we could look at "Value" pointers from
+ // Because we look 'through' phi nodes, we could look at "Value" pointers from
// different iterations. We must therefore make sure that this is not the
// case. The function isValueEqualInPotentialCycles ensures that this cannot
// happen by looking at the visited phi nodes and making sure they cannot
@@ -1337,7 +1429,7 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
return NoAlias;
if (O1 != O2) {
- // If V1/V2 point to two different objects we know that we have no alias.
+ // If V1/V2 point to two different objects, we know that we have no alias.
if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
return NoAlias;
@@ -1430,8 +1522,7 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
}
// 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.
+ // accesses the entire object, then the accesses must overlap in some way.
if (O1 == O2)
if ((V1Size != MemoryLocation::UnknownSize &&
isObjectSize(O1, V1Size, DL, TLI)) ||
@@ -1544,7 +1635,8 @@ bool BasicAAResult::constantOffsetHeuristic(
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);
- NSW = true, NUW = true;
+ NSW = true;
+ NUW = true;
const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
V1SExtBits, DL, 0, AC, DT, NSW, NUW);
@@ -1577,12 +1669,12 @@ bool BasicAAResult::constantOffsetHeuristic(
char BasicAA::PassID;
-BasicAAResult BasicAA::run(Function &F, AnalysisManager<Function> *AM) {
+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));
+ AM.getResult<TargetLibraryAnalysis>(F),
+ AM.getResult<AssumptionAnalysis>(F),
+ &AM.getResult<DominatorTreeAnalysis>(F),
+ AM.getCachedResult<LoopAnalysis>(F));
}
BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
@@ -1595,6 +1687,7 @@ void BasicAAWrapperPass::anchor() {}
INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
"Basic Alias Analysis (stateless AA impl)", true, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
"Basic Alias Analysis (stateless AA impl)", true, true)
@@ -1606,12 +1699,11 @@ FunctionPass *llvm::createBasicAAWrapperPass() {
bool BasicAAWrapperPass::runOnFunction(Function &F) {
auto &ACT = getAnalysis<AssumptionCacheTracker>();
auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
- auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+ auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
- ACT.getAssumptionCache(F),
- DTWP ? &DTWP->getDomTree() : nullptr,
+ ACT.getAssumptionCache(F), &DTWP.getDomTree(),
LIWP ? &LIWP->getLoopInfo() : nullptr));
return false;
@@ -1620,6 +1712,7 @@ bool BasicAAWrapperPass::runOnFunction(Function &F) {
void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<AssumptionCacheTracker>();
+ AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
}
OpenPOWER on IntegriCloud