summaryrefslogtreecommitdiff
path: root/lib/Analysis/BasicAliasAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/BasicAliasAnalysis.cpp')
-rw-r--r--lib/Analysis/BasicAliasAnalysis.cpp340
1 files changed, 201 insertions, 139 deletions
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 1a24ae3dba15..332eeaa00e73 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -31,7 +31,6 @@
#include "llvm/Analysis/PhiValues.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
-#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
@@ -68,6 +67,16 @@ using namespace llvm;
/// Enable analysis of recursive PHI nodes.
static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
cl::init(false));
+
+/// By default, even on 32-bit architectures we use 64-bit integers for
+/// calculations. This will allow us to more-aggressively decompose indexing
+/// expressions calculated using i64 values (e.g., long long in C) which is
+/// common enough to worry about.
+static cl::opt<bool> ForceAtLeast64Bits("basicaa-force-at-least-64b",
+ cl::Hidden, cl::init(true));
+static cl::opt<bool> DoubleCalcBits("basicaa-double-calc-bits",
+ 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.
@@ -134,7 +143,7 @@ static bool isNonEscapingLocalObject(const Value *V) {
/// Returns true if the pointer is one which would have been considered an
/// escape by isNonEscapingLocalObject.
static bool isEscapeSource(const Value *V) {
- if (ImmutableCallSite(V))
+ if (isa<CallBase>(V))
return true;
if (isa<Argument>(V))
@@ -381,13 +390,22 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
}
/// 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;
+/// (in bits) when that size is smaller than the maximum pointer size. This is
+/// an issue, for example, in particular for 32b pointers with negative indices
+/// that rely on two's complement wrap-arounds for precise alias information
+/// where the maximum pointer size is 64b.
+static APInt adjustToPointerSize(APInt Offset, unsigned PointerSize) {
+ assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!");
+ unsigned ShiftBits = Offset.getBitWidth() - PointerSize;
+ return (Offset << ShiftBits).ashr(ShiftBits);
+}
+
+static unsigned getMaxPointerSize(const DataLayout &DL) {
+ unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
+ if (MaxPointerSize < 64 && ForceAtLeast64Bits) MaxPointerSize = 64;
+ if (DoubleCalcBits) MaxPointerSize *= 2;
+
+ return MaxPointerSize;
}
/// If V is a symbolic pointer expression, decompose it into a base pointer
@@ -410,8 +428,7 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
unsigned MaxLookup = MaxLookupSearchDepth;
SearchTimes++;
- Decomposed.StructOffset = 0;
- Decomposed.OtherOffset = 0;
+ unsigned MaxPointerSize = getMaxPointerSize(DL);
Decomposed.VarIndices.clear();
do {
// See if this is a bitcast or GEP.
@@ -436,7 +453,7 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
if (!GEPOp) {
- if (auto CS = ImmutableCallSite(V)) {
+ if (const auto *Call = dyn_cast<CallBase>(V)) {
// CaptureTracking can know about special capturing properties of some
// intrinsics like launder.invariant.group, that can't be expressed with
// the attributes, but have properties like returning aliasing pointer.
@@ -446,7 +463,7 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
// because it should be in sync with CaptureTracking. Not using it may
// cause weird miscompilations where 2 aliasing pointers are assumed to
// noalias.
- if (auto *RP = getArgumentAliasingToReturnedPointer(CS)) {
+ if (auto *RP = getArgumentAliasingToReturnedPointer(Call)) {
V = RP;
continue;
}
@@ -501,13 +518,15 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
if (CIdx->isZero())
continue;
Decomposed.OtherOffset +=
- DL.getTypeAllocSize(GTI.getIndexedType()) * CIdx->getSExtValue();
+ (DL.getTypeAllocSize(GTI.getIndexedType()) *
+ CIdx->getValue().sextOrSelf(MaxPointerSize))
+ .sextOrTrunc(MaxPointerSize);
continue;
}
GepHasConstantOffset = false;
- uint64_t Scale = DL.getTypeAllocSize(GTI.getIndexedType());
+ APInt Scale(MaxPointerSize, DL.getTypeAllocSize(GTI.getIndexedType()));
unsigned ZExtBits = 0, SExtBits = 0;
// If the integer type is smaller than the pointer size, it is implicitly
@@ -519,20 +538,34 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
// Use GetLinearExpression to decompose the index into a C1*V+C2 form.
APInt IndexScale(Width, 0), IndexOffset(Width, 0);
bool NSW = true, NUW = true;
+ const Value *OrigIndex = Index;
Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
SExtBits, DL, 0, AC, DT, NSW, NUW);
- // All GEP math happens in the width of the pointer type,
- // so we can truncate the value to 64-bits as we don't handle
- // currently pointers larger than 64 bits and we would crash
- // later. TODO: Make `Scale` an APInt to avoid this problem.
- if (IndexScale.getBitWidth() > 64)
- IndexScale = IndexScale.sextOrTrunc(64);
-
// 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.
- Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
- Scale *= IndexScale.getSExtValue();
+
+ // It can be the case that, even through C1*V+C2 does not overflow for
+ // relevant values of V, (C2*Scale) can overflow. In that case, we cannot
+ // decompose the expression in this way.
+ //
+ // FIXME: C1*Scale and the other operations in the decomposed
+ // (C1*Scale)*V+C2*Scale can also overflow. We should check for this
+ // possibility.
+ APInt WideScaledOffset = IndexOffset.sextOrTrunc(MaxPointerSize*2) *
+ Scale.sext(MaxPointerSize*2);
+ if (WideScaledOffset.getMinSignedBits() > MaxPointerSize) {
+ Index = OrigIndex;
+ IndexScale = 1;
+ IndexOffset = 0;
+
+ ZExtBits = SExtBits = 0;
+ if (PointerSize > Width)
+ SExtBits += PointerSize - Width;
+ } else {
+ Decomposed.OtherOffset += IndexOffset.sextOrTrunc(MaxPointerSize) * Scale;
+ Scale *= IndexScale.sextOrTrunc(MaxPointerSize);
+ }
// If we already had an occurrence of this index variable, merge this
// scale into it. For example, we want to handle:
@@ -552,9 +585,8 @@ bool BasicAAResult::DecomposeGEPExpression(const Value *V,
// pointer size.
Scale = adjustToPointerSize(Scale, PointerSize);
- if (Scale) {
- VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
- static_cast<int64_t>(Scale)};
+ if (!!Scale) {
+ VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale};
Decomposed.VarIndices.push_back(Entry);
}
}
@@ -640,8 +672,8 @@ bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
}
/// Returns the behavior when calling the given call site.
-FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
- if (CS.doesNotAccessMemory())
+FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) {
+ if (Call->doesNotAccessMemory())
// Can't do better than this.
return FMRB_DoesNotAccessMemory;
@@ -649,23 +681,23 @@ FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
// If the callsite knows it only reads memory, don't return worse
// than that.
- if (CS.onlyReadsMemory())
+ if (Call->onlyReadsMemory())
Min = FMRB_OnlyReadsMemory;
- else if (CS.doesNotReadMemory())
+ else if (Call->doesNotReadMemory())
Min = FMRB_DoesNotReadMemory;
- if (CS.onlyAccessesArgMemory())
+ if (Call->onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- else if (CS.onlyAccessesInaccessibleMemory())
+ else if (Call->onlyAccessesInaccessibleMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem);
- else if (CS.onlyAccessesInaccessibleMemOrArgMem())
+ else if (Call->onlyAccessesInaccessibleMemOrArgMem())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem);
- // 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())
+ // If the call has operand bundles then aliasing attributes from the function
+ // it calls do not directly apply to the call. This can be made more precise
+ // in the future.
+ if (!Call->hasOperandBundles())
+ if (const Function *F = Call->getCalledFunction())
Min =
FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F));
@@ -698,9 +730,9 @@ FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
}
/// Returns true if this is a writeonly (i.e Mod only) parameter.
-static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
+static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx,
const TargetLibraryInfo &TLI) {
- if (CS.paramHasAttr(ArgIdx, Attribute::WriteOnly))
+ if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly))
return true;
// We can bound the aliasing properties of memset_pattern16 just as we can
@@ -710,7 +742,8 @@ static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
// FIXME Consider handling this in InferFunctionAttr.cpp together with other
// attributes.
LibFunc F;
- if (CS.getCalledFunction() && TLI.getLibFunc(*CS.getCalledFunction(), F) &&
+ if (Call->getCalledFunction() &&
+ TLI.getLibFunc(*Call->getCalledFunction(), F) &&
F == LibFunc_memset_pattern16 && TLI.has(F))
if (ArgIdx == 0)
return true;
@@ -722,23 +755,23 @@ static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
return false;
}
-ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
+ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call,
unsigned ArgIdx) {
// Checking for known builtin intrinsics and target library functions.
- if (isWriteOnlyParam(CS, ArgIdx, TLI))
+ if (isWriteOnlyParam(Call, ArgIdx, TLI))
return ModRefInfo::Mod;
- if (CS.paramHasAttr(ArgIdx, Attribute::ReadOnly))
+ if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly))
return ModRefInfo::Ref;
- if (CS.paramHasAttr(ArgIdx, Attribute::ReadNone))
+ if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone))
return ModRefInfo::NoModRef;
- return AAResultBase::getArgModRefInfo(CS, ArgIdx);
+ return AAResultBase::getArgModRefInfo(Call, ArgIdx);
}
-static bool isIntrinsicCall(ImmutableCallSite CS, Intrinsic::ID IID) {
- const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
+static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) {
+ const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call);
return II && II->getIntrinsicID() == IID;
}
@@ -794,27 +827,34 @@ AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
/// 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 BasicAAResult::getModRefInfo(ImmutableCallSite CS,
+ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
const MemoryLocation &Loc) {
- assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
+ assert(notDifferentParent(Call, Loc.Ptr) &&
"AliasAnalysis query involving multiple functions!");
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.
- // We cannot exclude byval arguments here; these belong to the caller of
- // the current function not to the current function, and a tail callee
- // may reference them.
+ // Calls marked 'tail' cannot read or write allocas from the current frame
+ // because the current frame might be destroyed by the time they run. However,
+ // a tail call may use an alloca with byval. Calling with byval copies the
+ // contents of the alloca into argument registers or stack slots, so there is
+ // no lifetime issue.
if (isa<AllocaInst>(Object))
- if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
- if (CI->isTailCall())
+ if (const CallInst *CI = dyn_cast<CallInst>(Call))
+ if (CI->isTailCall() &&
+ !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
return ModRefInfo::NoModRef;
+ // Stack restore is able to modify unescaped dynamic allocas. Assume it may
+ // modify them even though the alloca is not escaped.
+ if (auto *AI = dyn_cast<AllocaInst>(Object))
+ if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore))
+ return ModRefInfo::Mod;
+
// If the pointer is to a locally allocated object that does not escape,
// then the call can not mod/ref the pointer unless the call takes the pointer
// as an argument, and itself doesn't capture it.
- if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
+ if (!isa<Constant>(Object) && Call != Object &&
isNonEscapingLocalObject(Object)) {
// Optimistically assume that call doesn't touch Object and check this
@@ -823,19 +863,20 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
bool IsMustAlias = true;
unsigned OperandNo = 0;
- for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
+ for (auto CI = Call->data_operands_begin(), CE = Call->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(OperandNo) &&
- OperandNo < CS.getNumArgOperands() && !CS.isByValArgument(OperandNo)))
+ (!Call->doesNotCapture(OperandNo) &&
+ OperandNo < Call->getNumArgOperands() &&
+ !Call->isByValArgument(OperandNo)))
continue;
// Call doesn't access memory through this operand, so we don't care
// if it aliases with Object.
- if (CS.doesNotAccessMemory(OperandNo))
+ if (Call->doesNotAccessMemory(OperandNo))
continue;
// If this is a no-capture pointer argument, see if we can tell that it
@@ -849,12 +890,12 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
continue;
// Operand aliases 'Object', but call doesn't modify it. Strengthen
// initial assumption and keep looking in case if there are more aliases.
- if (CS.onlyReadsMemory(OperandNo)) {
+ if (Call->onlyReadsMemory(OperandNo)) {
Result = setRef(Result);
continue;
}
// Operand aliases 'Object' but call only writes into it.
- if (CS.doesNotReadMemory(OperandNo)) {
+ if (Call->doesNotReadMemory(OperandNo)) {
Result = setMod(Result);
continue;
}
@@ -878,17 +919,16 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
}
}
- // If the CallSite is to malloc or calloc, we can assume that it doesn't
+ // If the call 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 (isMallocOrCallocLikeFn(Inst, &TLI)) {
+ if (isMallocOrCallocLikeFn(Call, &TLI)) {
// Be conservative if the accessed pointer may alias the allocation -
// fallback to the generic handling below.
- if (getBestAAResults().alias(MemoryLocation(Inst), Loc) == NoAlias)
+ if (getBestAAResults().alias(MemoryLocation(Call), Loc) == NoAlias)
return ModRefInfo::NoModRef;
}
@@ -896,7 +936,7 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
// operands, i.e., source and destination of any given memcpy must no-alias.
// If Loc must-aliases either one of these two locations, then it necessarily
// no-aliases the other.
- if (auto *Inst = dyn_cast<AnyMemCpyInst>(CS.getInstruction())) {
+ if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) {
AliasResult SrcAA, DestAA;
if ((SrcAA = getBestAAResults().alias(MemoryLocation::getForSource(Inst),
@@ -920,7 +960,7 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
// 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 (isIntrinsicCall(CS, Intrinsic::assume))
+ if (isIntrinsicCall(Call, Intrinsic::assume))
return ModRefInfo::NoModRef;
// Like assumes, guard intrinsics are also marked as arbitrarily writing so
@@ -930,7 +970,7 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
// *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))
+ if (isIntrinsicCall(Call, Intrinsic::experimental_guard))
return ModRefInfo::Ref;
// Like assumes, invariant.start intrinsics were also marked as arbitrarily
@@ -956,20 +996,20 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
// The transformation will cause the second store to be ignored (based on
// rules of invariant.start) and print 40, while the first program always
// prints 50.
- if (isIntrinsicCall(CS, Intrinsic::invariant_start))
+ if (isIntrinsicCall(Call, Intrinsic::invariant_start))
return ModRefInfo::Ref;
// The AAResultBase base class has some smarts, lets use them.
- return AAResultBase::getModRefInfo(CS, Loc);
+ return AAResultBase::getModRefInfo(Call, Loc);
}
-ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
- ImmutableCallSite CS2) {
+ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1,
+ const CallBase *Call2) {
// 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 (isIntrinsicCall(CS1, Intrinsic::assume) ||
- isIntrinsicCall(CS2, Intrinsic::assume))
+ if (isIntrinsicCall(Call1, Intrinsic::assume) ||
+ isIntrinsicCall(Call2, Intrinsic::assume))
return ModRefInfo::NoModRef;
// Like assumes, guard intrinsics are also marked as arbitrarily writing so
@@ -983,26 +1023,26 @@ ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
// NB! This function is *not* commutative, so we specical case two
// possibilities for guard intrinsics.
- if (isIntrinsicCall(CS1, Intrinsic::experimental_guard))
- return isModSet(createModRefInfo(getModRefBehavior(CS2)))
+ if (isIntrinsicCall(Call1, Intrinsic::experimental_guard))
+ return isModSet(createModRefInfo(getModRefBehavior(Call2)))
? ModRefInfo::Ref
: ModRefInfo::NoModRef;
- if (isIntrinsicCall(CS2, Intrinsic::experimental_guard))
- return isModSet(createModRefInfo(getModRefBehavior(CS1)))
+ if (isIntrinsicCall(Call2, Intrinsic::experimental_guard))
+ return isModSet(createModRefInfo(getModRefBehavior(Call1)))
? ModRefInfo::Mod
: ModRefInfo::NoModRef;
// The AAResultBase base class has some smarts, lets use them.
- return AAResultBase::getModRefInfo(CS1, CS2);
+ return AAResultBase::getModRefInfo(Call1, Call2);
}
/// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
/// both having the exact same pointer operand.
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
- LocationSize V1Size,
+ LocationSize MaybeV1Size,
const GEPOperator *GEP2,
- LocationSize V2Size,
+ LocationSize MaybeV2Size,
const DataLayout &DL) {
assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
@@ -1018,10 +1058,13 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
// If we don't know the size of the accesses through both GEPs, we can't
// determine whether the struct fields accessed can't alias.
- if (V1Size == MemoryLocation::UnknownSize ||
- V2Size == MemoryLocation::UnknownSize)
+ if (MaybeV1Size == LocationSize::unknown() ||
+ MaybeV2Size == LocationSize::unknown())
return MayAlias;
+ const uint64_t V1Size = MaybeV1Size.getValue();
+ const uint64_t V2Size = MaybeV2Size.getValue();
+
ConstantInt *C1 =
dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
ConstantInt *C2 =
@@ -1029,8 +1072,12 @@ 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->getSExtValue() == C2->getSExtValue())
- return MayAlias;
+ if (C1 && C2) {
+ unsigned BitWidth = std::max(C1->getBitWidth(), C2->getBitWidth());
+ if (C1->getValue().sextOrSelf(BitWidth) ==
+ C2->getValue().sextOrSelf(BitWidth))
+ return MayAlias;
+ }
// Find the last-indexed type of the GEP, i.e., the type you'd get if
// you stripped the last index.
@@ -1113,6 +1160,10 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
return MayAlias;
}
+ if (C1->getValue().getActiveBits() > 64 ||
+ C2->getValue().getActiveBits() > 64)
+ return MayAlias;
+
// We know that:
// - both GEPs begin indexing from the exact same pointer;
// - the last indices in both GEPs are constants, indexing into a struct;
@@ -1178,11 +1229,13 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
// than (%alloca - 1), and so is not inbounds, a contradiction.
bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
- LocationSize ObjectAccessSize) {
+ LocationSize MaybeObjectAccessSize) {
// If the object access size is unknown, or the GEP isn't inbounds, bail.
- if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
+ if (MaybeObjectAccessSize == LocationSize::unknown() || !GEPOp->isInBounds())
return false;
+ const uint64_t ObjectAccessSize = MaybeObjectAccessSize.getValue();
+
// 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.
@@ -1191,8 +1244,8 @@ bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
!DecompObject.VarIndices.empty())
return false;
- int64_t ObjectBaseOffset = DecompObject.StructOffset +
- DecompObject.OtherOffset;
+ APInt 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,
@@ -1200,10 +1253,11 @@ bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
// false in that case.
if (!DecompGEP.VarIndices.empty())
return false;
- int64_t GEPBaseOffset = DecompGEP.StructOffset;
+
+ APInt GEPBaseOffset = DecompGEP.StructOffset;
GEPBaseOffset += DecompGEP.OtherOffset;
- return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
+ return GEPBaseOffset.sge(ObjectBaseOffset + (int64_t)ObjectAccessSize);
}
/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
@@ -1218,13 +1272,17 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
LocationSize V2Size, const AAMDNodes &V2AAInfo,
const Value *UnderlyingV1, const Value *UnderlyingV2) {
DecomposedGEP DecompGEP1, DecompGEP2;
+ unsigned MaxPointerSize = getMaxPointerSize(DL);
+ DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
+ DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
+
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;
+ APInt GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
+ APInt GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
"DecomposeGEPExpression returned a result different from "
@@ -1247,8 +1305,8 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
return NoAlias;
// Do the base pointers alias?
AliasResult BaseAlias =
- aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
- UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes());
+ aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(),
+ UnderlyingV2, LocationSize::unknown(), AAMDNodes());
// Check for geps of non-aliasing underlying pointers where the offsets are
// identical.
@@ -1307,13 +1365,12 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// pointer, we know they cannot alias.
// If both accesses are unknown size, we can't do anything useful here.
- if (V1Size == MemoryLocation::UnknownSize &&
- V2Size == MemoryLocation::UnknownSize)
+ if (V1Size == LocationSize::unknown() && V2Size == LocationSize::unknown())
return MayAlias;
- AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
- AAMDNodes(), V2, MemoryLocation::UnknownSize,
- V2AAInfo, nullptr, UnderlyingV2);
+ AliasResult R =
+ aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(), V2,
+ LocationSize::unknown(), V2AAInfo, nullptr, UnderlyingV2);
if (R != MustAlias) {
// If V2 may alias GEP base pointer, conservatively returns MayAlias.
// If V2 is known not to alias GEP base pointer, then the two values
@@ -1343,9 +1400,9 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// that the objects are partially overlapping. If the difference is
// greater, we know they do not overlap.
if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
- if (GEP1BaseOffset >= 0) {
- if (V2Size != MemoryLocation::UnknownSize) {
- if ((uint64_t)GEP1BaseOffset < V2Size)
+ if (GEP1BaseOffset.sge(0)) {
+ if (V2Size != LocationSize::unknown()) {
+ if (GEP1BaseOffset.ult(V2Size.getValue()))
return PartialAlias;
return NoAlias;
}
@@ -1358,9 +1415,9 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// GEP1 V2
// We need to know that V2Size is not unknown, otherwise we might have
// stripped a gep with negative index ('gep <ptr>, -1, ...).
- if (V1Size != MemoryLocation::UnknownSize &&
- V2Size != MemoryLocation::UnknownSize) {
- if (-(uint64_t)GEP1BaseOffset < V1Size)
+ if (V1Size != LocationSize::unknown() &&
+ V2Size != LocationSize::unknown()) {
+ if ((-GEP1BaseOffset).ult(V1Size.getValue()))
return PartialAlias;
return NoAlias;
}
@@ -1368,7 +1425,7 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
}
if (!DecompGEP1.VarIndices.empty()) {
- uint64_t Modulo = 0;
+ APInt Modulo(MaxPointerSize, 0);
bool AllPositive = true;
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
@@ -1376,7 +1433,7 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// 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)DecompGEP1.VarIndices[i].Scale;
+ Modulo |= DecompGEP1.VarIndices[i].Scale;
if (AllPositive) {
// If the Value could change between cycles, then any reasoning about
@@ -1397,9 +1454,9 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// 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 = DecompGEP1.VarIndices[i].Scale;
+ APInt Scale = DecompGEP1.VarIndices[i].Scale;
AllPositive =
- (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
+ (SignKnownZero && Scale.sge(0)) || (SignKnownOne && Scale.slt(0));
}
}
@@ -1408,16 +1465,18 @@ BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
// We can compute the difference between the two addresses
// mod Modulo. Check whether that difference guarantees that the
// two locations do not alias.
- uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
- if (V1Size != MemoryLocation::UnknownSize &&
- V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
- V1Size <= Modulo - ModOffset)
+ APInt ModOffset = GEP1BaseOffset & (Modulo - 1);
+ if (V1Size != LocationSize::unknown() &&
+ V2Size != LocationSize::unknown() && ModOffset.uge(V2Size.getValue()) &&
+ (Modulo - ModOffset).uge(V1Size.getValue()))
return NoAlias;
// If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
// If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
// don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
- if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
+ if (AllPositive && GEP1BaseOffset.sgt(0) &&
+ V2Size != LocationSize::unknown() &&
+ GEP1BaseOffset.uge(V2Size.getValue()))
return NoAlias;
if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
@@ -1597,7 +1656,7 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
// unknown to represent all the possible values the GEP could advance the
// pointer to.
if (isRecursive)
- PNSize = MemoryLocation::UnknownSize;
+ PNSize = LocationSize::unknown();
AliasResult Alias =
aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0],
@@ -1631,7 +1690,7 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
const Value *O1, const Value *O2) {
// If either of the memory references is empty, it doesn't matter what the
// pointer values are.
- if (V1Size == 0 || V2Size == 0)
+ if (V1Size.isZero() || V2Size.isZero())
return NoAlias;
// Strip off any casts if they exist.
@@ -1705,10 +1764,10 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize 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.
bool NullIsValidLocation = NullPointerIsDefined(&F);
- if ((V1Size != MemoryLocation::UnknownSize &&
- isObjectSmallerThan(O2, V1Size, DL, TLI, NullIsValidLocation)) ||
- (V2Size != MemoryLocation::UnknownSize &&
- isObjectSmallerThan(O1, V2Size, DL, TLI, NullIsValidLocation)))
+ if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI,
+ NullIsValidLocation)) ||
+ (V2Size.isPrecise() && isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI,
+ NullIsValidLocation)))
return NoAlias;
// Check the cache before climbing up use-def chains. This also terminates
@@ -1766,10 +1825,9 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
// If both pointers are pointing into the same object and one of them
// accesses the entire object, then the accesses must overlap in some way.
if (O1 == O2)
- if (V1Size != MemoryLocation::UnknownSize &&
- V2Size != MemoryLocation::UnknownSize &&
- (isObjectSize(O1, V1Size, DL, TLI, NullIsValidLocation) ||
- isObjectSize(O2, V2Size, DL, TLI, NullIsValidLocation)))
+ if (V1Size.isPrecise() && V2Size.isPrecise() &&
+ (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) ||
+ isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation)))
return AliasCache[Locs] = PartialAlias;
// Recurse back into the best AA results we have, potentially with refined
@@ -1824,7 +1882,7 @@ void BasicAAResult::GetIndexDifference(
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
const Value *V = Src[i].V;
unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
- int64_t Scale = Src[i].Scale;
+ APInt Scale = Src[i].Scale;
// Find V in Dest. This is N^2, but pointer indices almost never have more
// than a few variable indexes.
@@ -1844,7 +1902,7 @@ void BasicAAResult::GetIndexDifference(
}
// If we didn't consume this entry, add it to the end of the Dest list.
- if (Scale) {
+ if (!!Scale) {
VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
Dest.push_back(Entry);
}
@@ -1852,13 +1910,16 @@ void BasicAAResult::GetIndexDifference(
}
bool BasicAAResult::constantOffsetHeuristic(
- const SmallVectorImpl<VariableGEPIndex> &VarIndices, LocationSize V1Size,
- LocationSize V2Size, int64_t BaseOffset, AssumptionCache *AC,
- DominatorTree *DT) {
- if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
- V2Size == MemoryLocation::UnknownSize)
+ const SmallVectorImpl<VariableGEPIndex> &VarIndices,
+ LocationSize MaybeV1Size, LocationSize MaybeV2Size, APInt BaseOffset,
+ AssumptionCache *AC, DominatorTree *DT) {
+ if (VarIndices.size() != 2 || MaybeV1Size == LocationSize::unknown() ||
+ MaybeV2Size == LocationSize::unknown())
return false;
+ const uint64_t V1Size = MaybeV1Size.getValue();
+ const uint64_t V2Size = MaybeV2Size.getValue();
+
const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
@@ -1895,14 +1956,15 @@ bool BasicAAResult::constantOffsetHeuristic(
// the minimum distance between %i and %i + 5 is 3.
APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
MinDiff = APIntOps::umin(MinDiff, Wrapped);
- uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
+ APInt MinDiffBytes =
+ MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs();
// We can't definitely say whether GEP1 is before or after V2 due to wrapping
// arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
// values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
// V2Size can fit in the MinDiffBytes gap.
- return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
- V2Size + std::abs(BaseOffset) <= MinDiffBytes;
+ return MinDiffBytes.uge(V1Size + BaseOffset.abs()) &&
+ MinDiffBytes.uge(V2Size + BaseOffset.abs());
}
//===----------------------------------------------------------------------===//
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-17 23:53:02 +0000