//
//===----------------------------------------------------------------------===//
-#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/GlobalAlias.h"
-#include "llvm/GlobalVariable.h"
-#include "llvm/Instructions.h"
-#include "llvm/IntrinsicInst.h"
-#include "llvm/LLVMContext.h"
-#include "llvm/Operator.h"
-#include "llvm/Pass.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CaptureTracking.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Target/TargetLibraryInfo.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GetElementPtrTypeIterator.h"
+#include "llvm/IR/GlobalAlias.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/Pass.h"
#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>
using namespace llvm;
+/// 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
+/// careful with value equivalence. We use reachability to make sure a value
+/// cannot be involved in a cycle.
+const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
+
+// The max limit of the search depth in DecomposeGEPExpression() and
+// GetUnderlyingObject(), both functions need to use the same search
+// depth otherwise the algorithm in aliasGEP will assert.
+static const unsigned MaxLookupSearchDepth = 6;
+
//===----------------------------------------------------------------------===//
// Useful predicates
//===----------------------------------------------------------------------===//
// then it has not escaped before entering the function. Check if it escapes
// inside the function.
if (const Argument *A = dyn_cast<Argument>(V))
- if (A->hasByValAttr() || A->hasNoAliasAttr()) {
- // Don't bother analyzing arguments already known not to escape.
- if (A->hasNoCaptureAttr())
- return true;
+ if (A->hasByValAttr() || A->hasNoAliasAttr())
+ // 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);
- }
+
return false;
}
/// getObjectSize - Return the size of the object specified by V, or
/// UnknownSize if unknown.
-static uint64_t getObjectSize(const Value *V, const TargetData &TD,
+static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
const TargetLibraryInfo &TLI,
bool RoundToAlign = false) {
uint64_t Size;
- if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign))
+ if (getObjectSize(V, Size, &DL, &TLI, RoundToAlign))
return Size;
return AliasAnalysis::UnknownSize;
}
/// isObjectSmallerThan - Return true if we can prove that the object specified
/// by V is smaller than Size.
static bool isObjectSmallerThan(const Value *V, uint64_t Size,
- const TargetData &TD,
+ const DataLayout &DL,
const TargetLibraryInfo &TLI) {
+ // Note that the meanings of the "object" are slightly different in the
+ // following contexts:
+ // c1: llvm::getObjectSize()
+ // c2: llvm.objectsize() intrinsic
+ // c3: isObjectSmallerThan()
+ // c1 and c2 share the same meaning; however, the meaning of "object" in c3
+ // refers to the "entire object".
+ //
+ // Consider this example:
+ // char *p = (char*)malloc(100)
+ // char *q = p+80;
+ //
+ // In the context of c1 and c2, the "object" pointed by q refers to the
+ // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
+ //
+ // However, in the context of c3, the "object" refers to the chunk of memory
+ // being allocated. So, the "object" has 100 bytes, and q points to the middle
+ // the "object". In case q is passed to isObjectSmallerThan() as the 1st
+ // parameter, before the llvm::getObjectSize() is called to get the size of
+ // entire object, we should:
+ // - either rewind the pointer q to the base-address of the object in
+ // question (in this case rewind to p), or
+ // - just give up. It is up to caller to make sure the pointer is pointing
+ // to the base address the object.
+ //
+ // We go for 2nd option for simplicity.
+ if (!isIdentifiedObject(V))
+ return false;
+
// This function needs to use the aligned object size because we allow
// reads a bit past the end given sufficient alignment.
- uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true);
-
+ uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/true);
+
return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size;
}
/// isObjectSize - Return true if we can prove that the object specified
/// by V has size Size.
static bool isObjectSize(const Value *V, uint64_t Size,
- const TargetData &TD, const TargetLibraryInfo &TLI) {
- uint64_t ObjectSize = getObjectSize(V, TD, TLI);
+ const DataLayout &DL, const TargetLibraryInfo &TLI) {
+ uint64_t ObjectSize = getObjectSize(V, DL, TLI);
return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size;
}
+/// isIdentifiedFunctionLocal - Return true if V is umabigously identified
+/// at the function-level. Different IdentifiedFunctionLocals can't alias.
+/// Further, an IdentifiedFunctionLocal can not alias with any function
+/// arguments other than itself, which is not necessarily true for
+/// IdentifiedObjects.
+static bool isIdentifiedFunctionLocal(const Value *V)
+{
+ return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
+}
+
+
//===----------------------------------------------------------------------===//
// GetElementPtr Instruction Decomposition and Analysis
//===----------------------------------------------------------------------===//
EK_SignExt,
EK_ZeroExt
};
-
+
struct VariableGEPIndex {
const Value *V;
ExtensionKind Extension;
/// represented in the result.
static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
ExtensionKind &Extension,
- const TargetData &TD, unsigned Depth) {
+ const DataLayout &DL, unsigned Depth) {
assert(V->getType()->isIntegerTy() && "Not an integer value");
// Limit our recursion depth.
Offset = 0;
return V;
}
-
+
if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
switch (BOp->getOpcode()) {
case Instruction::Or:
// X|C == X+C if all the bits in C are unset in X. Otherwise we can't
// analyze it.
- if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD))
+ if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &DL))
break;
// FALL THROUGH.
case Instruction::Add:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
- TD, Depth+1);
+ DL, Depth+1);
Offset += RHSC->getValue();
return V;
case Instruction::Mul:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
- TD, Depth+1);
+ DL, Depth+1);
Offset *= RHSC->getValue();
Scale *= RHSC->getValue();
return V;
case Instruction::Shl:
V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
- TD, Depth+1);
+ DL, Depth+1);
Offset <<= RHSC->getValue().getLimitedValue();
Scale <<= RHSC->getValue().getLimitedValue();
return V;
}
}
}
-
+
// Since GEP indices are sign extended anyway, we don't care about the high
// bits of a sign or zero extended value - just scales and offsets. The
// extensions have to be consistent though.
Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension,
- TD, Depth+1);
+ DL, Depth+1);
Scale = Scale.zext(OldWidth);
Offset = Offset.zext(OldWidth);
-
+
return Result;
}
-
+
Scale = 1;
Offset = 0;
return V;
/// specified amount, but which may have other unrepresented high bits. As such,
/// the gep cannot necessarily be reconstructed from its decomposed form.
///
-/// When TargetData is around, this function is capable of analyzing everything
-/// that GetUnderlyingObject can look through. When not, it just looks
-/// through pointer casts.
+/// When DataLayout is around, this function is capable of analyzing everything
+/// that GetUnderlyingObject can look through. To be able to do that
+/// GetUnderlyingObject and DecomposeGEPExpression must use the same search
+/// depth (MaxLookupSearchDepth).
+/// When DataLayout not is around, it just looks through pointer casts.
///
static const Value *
DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
SmallVectorImpl<VariableGEPIndex> &VarIndices,
- const TargetData *TD) {
+ bool &MaxLookupReached, const DataLayout *DL) {
// Limit recursion depth to limit compile time in crazy cases.
- unsigned MaxLookup = 6;
-
+ unsigned MaxLookup = MaxLookupSearchDepth;
+ MaxLookupReached = false;
+
BaseOffs = 0;
do {
// See if this is a bitcast or GEP.
const Operator *Op = dyn_cast<Operator>(V);
- if (Op == 0) {
+ if (!Op) {
// The only non-operator case we can handle are GlobalAliases.
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (!GA->mayBeOverridden()) {
}
return V;
}
-
+
if (Op->getOpcode() == Instruction::BitCast) {
V = Op->getOperand(0);
continue;
}
const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
- if (GEPOp == 0) {
+ if (!GEPOp) {
// 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))
// TODO: Get a DominatorTree and use it here.
if (const Value *Simplified =
- SimplifyInstruction(const_cast<Instruction *>(I), TD)) {
+ SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
V = Simplified;
continue;
}
-
+
return V;
}
-
+
// Don't attempt to analyze GEPs over unsized objects.
- if (!cast<PointerType>(GEPOp->getOperand(0)->getType())
- ->getElementType()->isSized())
+ if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
return V;
-
- // If we are lacking TargetData information, we can't compute the offets of
+
+ // If we are lacking DataLayout information, we can't compute the offets of
// elements computed by GEPs. However, we can handle bitcast equivalent
// GEPs.
- if (TD == 0) {
+ if (!DL) {
if (!GEPOp->hasAllZeroIndices())
return V;
V = GEPOp->getOperand(0);
continue;
}
-
+
+ unsigned AS = GEPOp->getPointerAddressSpace();
// Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
gep_type_iterator GTI = gep_type_begin(GEPOp);
for (User::const_op_iterator I = GEPOp->op_begin()+1,
// For a struct, add the member offset.
unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
if (FieldNo == 0) continue;
-
- BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo);
+
+ BaseOffs += DL->getStructLayout(STy)->getElementOffset(FieldNo);
continue;
}
-
+
// For an array/pointer, add the element offset, explicitly scaled.
if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
if (CIdx->isZero()) continue;
- BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue();
+ BaseOffs += DL->getTypeAllocSize(*GTI)*CIdx->getSExtValue();
continue;
}
-
- uint64_t Scale = TD->getTypeAllocSize(*GTI);
+
+ uint64_t Scale = DL->getTypeAllocSize(*GTI);
ExtensionKind Extension = EK_NotExtended;
-
+
// If the integer type is smaller than the pointer size, it is implicitly
// sign extended to pointer size.
- unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
- if (TD->getPointerSizeInBits() > Width)
+ unsigned Width = Index->getType()->getIntegerBitWidth();
+ if (DL->getPointerSizeInBits(AS) > Width)
Extension = EK_SignExt;
-
+
// Use GetLinearExpression to decompose the index into a C1*V+C2 form.
APInt IndexScale(Width, 0), IndexOffset(Width, 0);
Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension,
- *TD, 0);
-
+ *DL, 0);
+
// 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;
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
break;
}
}
-
+
// Make sure that we have a scale that makes sense for this target's
// pointer size.
- if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) {
+ if (unsigned ShiftBits = 64 - DL->getPointerSizeInBits(AS)) {
Scale <<= ShiftBits;
Scale = (int64_t)Scale >> ShiftBits;
}
-
+
if (Scale) {
VariableGEPIndex Entry = {Index, Extension,
static_cast<int64_t>(Scale)};
VarIndices.push_back(Entry);
}
}
-
+
// Analyze the base pointer next.
V = GEPOp->getOperand(0);
} while (--MaxLookup);
-
+
// If the chain of expressions is too deep, just return early.
+ MaxLookupReached = true;
return V;
}
-/// GetIndexDifference - Dest and Src are the variable indices from two
-/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
-/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
-/// difference between the two pointers.
-static void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
- const SmallVectorImpl<VariableGEPIndex> &Src) {
- if (Src.empty()) return;
-
- for (unsigned i = 0, e = Src.size(); i != e; ++i) {
- const Value *V = Src[i].V;
- ExtensionKind Extension = Src[i].Extension;
- int64_t Scale = Src[i].Scale;
-
- // Find V in Dest. This is N^2, but pointer indices almost never have more
- // than a few variable indexes.
- for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
- if (Dest[j].V != V || Dest[j].Extension != Extension) continue;
-
- // If we found it, subtract off Scale V's from the entry in Dest. If it
- // goes to zero, remove the entry.
- if (Dest[j].Scale != Scale)
- Dest[j].Scale -= Scale;
- else
- Dest.erase(Dest.begin()+j);
- Scale = 0;
- break;
- }
-
- // If we didn't consume this entry, add it to the end of the Dest list.
- if (Scale) {
- VariableGEPIndex Entry = { V, Extension, -Scale };
- Dest.push_back(Entry);
- }
- }
-}
-
//===----------------------------------------------------------------------===//
// BasicAliasAnalysis Pass
//===----------------------------------------------------------------------===//
if (const Argument *arg = dyn_cast<Argument>(V))
return arg->getParent();
- return NULL;
+ return nullptr;
}
static bool notDifferentParent(const Value *O1, const Value *O2) {
initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry());
}
- virtual void initializePass() {
+ void initializePass() override {
InitializeAliasAnalysis(this);
}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AliasAnalysis>();
AU.addRequired<TargetLibraryInfo>();
}
- virtual AliasResult alias(const Location &LocA,
- const Location &LocB) {
+ AliasResult alias(const Location &LocA, const Location &LocB) override {
assert(AliasCache.empty() && "AliasCache must be cleared after use!");
assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
"BasicAliasAnalysis doesn't support interprocedural queries.");
// SmallDenseMap if it ever grows larger.
// FIXME: This should really be shrink_to_inline_capacity_and_clear().
AliasCache.shrink_and_clear();
+ VisitedPhiBBs.clear();
return Alias;
}
- virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
- const Location &Loc);
+ ModRefResult getModRefInfo(ImmutableCallSite CS,
+ const Location &Loc) override;
- virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
- ImmutableCallSite CS2) {
+ ModRefResult getModRefInfo(ImmutableCallSite CS1,
+ ImmutableCallSite CS2) override {
// The AliasAnalysis base class has some smarts, lets use them.
return AliasAnalysis::getModRefInfo(CS1, CS2);
}
/// pointsToConstantMemory - Chase pointers until we find a (constant
/// global) or not.
- virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal);
+ bool pointsToConstantMemory(const Location &Loc, bool OrLocal) override;
/// getModRefBehavior - Return the behavior when calling the given
/// call site.
- virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
+ ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override;
/// getModRefBehavior - Return the behavior when calling the given function.
/// For use when the call site is not known.
- virtual ModRefBehavior getModRefBehavior(const Function *F);
+ ModRefBehavior getModRefBehavior(const Function *F) override;
/// getAdjustedAnalysisPointer - This method is used when a pass implements
/// an analysis interface through multiple inheritance. If needed, it
/// should override this to adjust the this pointer as needed for the
/// specified pass info.
- virtual void *getAdjustedAnalysisPointer(const void *ID) {
+ void *getAdjustedAnalysisPointer(const void *ID) override {
if (ID == &AliasAnalysis::ID)
return (AliasAnalysis*)this;
return this;
}
-
+
private:
// AliasCache - Track alias queries to guard against recursion.
typedef std::pair<Location, Location> LocPair;
typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy;
AliasCacheTy AliasCache;
+ /// \brief Track phi nodes we have visited. When interpret "Value" pointer
+ /// equality as value equality we need to make sure that the "Value" is not
+ /// part of a cycle. Otherwise, two uses could come from different
+ /// "iterations" of a cycle and see different values for the same "Value"
+ /// pointer.
+ /// The following example shows the problem:
+ /// %p = phi(%alloca1, %addr2)
+ /// %l = load %ptr
+ /// %addr1 = gep, %alloca2, 0, %l
+ /// %addr2 = gep %alloca2, 0, (%l + 1)
+ /// alias(%p, %addr1) -> MayAlias !
+ /// store %l, ...
+ SmallPtrSet<const BasicBlock*, 8> VisitedPhiBBs;
+
// Visited - Track instructions visited by pointsToConstantMemory.
SmallPtrSet<const Value*, 16> Visited;
+ /// \brief Check whether two Values can be considered equivalent.
+ ///
+ /// In addition to pointer equivalence of \p V1 and \p V2 this checks
+ /// whether they can not be part of a cycle in the value graph by looking at
+ /// all 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 isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
+
+ /// \brief Dest and Src are the variable indices from two decomposed
+ /// GetElementPtr instructions GEP1 and GEP2 which have common base
+ /// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
+ /// difference between the two pointers.
+ void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
+ const SmallVectorImpl<VariableGEPIndex> &Src);
+
// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
// instruction against another.
AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
SmallVector<const Value *, 16> Worklist;
Worklist.push_back(Loc.Ptr);
do {
- const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD);
+ const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
if (!Visited.insert(V)) {
Visited.clear();
return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal);
// For intrinsics, we can check the table.
if (unsigned iid = F->getIntrinsicID()) {
#define GET_INTRINSIC_MODREF_BEHAVIOR
-#include "llvm/Intrinsics.gen"
+#include "llvm/IR/Intrinsics.gen"
#undef GET_INTRINSIC_MODREF_BEHAVIOR
}
assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
"AliasAnalysis query involving multiple functions!");
- const Value *Object = GetUnderlyingObject(Loc.Ptr, TD);
-
+ 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
if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
if (CI->isTailCall())
return NoModRef;
-
+
// 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 (!(*CI)->getType()->isPointerTy() ||
(!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
continue;
-
+
// If this is a no-capture pointer argument, see if we can tell that it
// 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
break;
}
}
-
+
if (!PassedAsArg)
return NoModRef;
}
// Finally, handle specific knowledge of intrinsics.
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
- if (II != 0)
+ if (II != nullptr)
switch (II->getIntrinsicID()) {
default: break;
case Intrinsic::memcpy:
// LLVM's vld1 and vst1 intrinsics currently only support a single
// vector register.
uint64_t Size =
- TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize;
+ DL ? DL->getTypeStoreSize(II->getType()) : UnknownSize;
if (isNoAlias(Location(II->getArgOperand(0), Size,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
}
case Intrinsic::arm_neon_vst1: {
uint64_t Size =
- TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize;
+ DL ? DL->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize;
if (isNoAlias(Location(II->getArgOperand(0), Size,
II->getMetadata(LLVMContext::MD_tbaa)),
Loc))
}
// We can bound the aliasing properties of memset_pattern16 just as we can
- // for memcpy/memset. This is particularly important because the
+ // for memcpy/memset. This is particularly important because the
// LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
// whenever possible.
else if (TLI.has(LibFunc::memset_pattern16) &&
return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min);
}
-static bool areVarIndicesEqual(SmallVector<VariableGEPIndex, 4> &Indices1,
- SmallVector<VariableGEPIndex, 4> &Indices2) {
- unsigned Size1 = Indices1.size();
- unsigned Size2 = Indices2.size();
-
- if (Size1 != Size2)
- return false;
-
- for (unsigned I = 0; I != Size1; ++I)
- if (Indices1[I] != Indices2[I])
- return false;
-
- return true;
-}
-
/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
/// against another pointer. We know that V1 is a GEP, but we don't know
-/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD),
+/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, DL),
/// UnderlyingV2 is the same for V2.
///
AliasAnalysis::AliasResult
const Value *UnderlyingV1,
const Value *UnderlyingV2) {
int64_t GEP1BaseOffset;
+ bool GEP1MaxLookupReached;
SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
// 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)) {
+ // Do the base pointers alias?
+ AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, nullptr,
+ UnderlyingV2, UnknownSize, nullptr);
+
// Check for geps of non-aliasing underlying pointers where the offsets are
// identical.
- if (V1Size == V2Size) {
+ if ((BaseAlias == MayAlias) && V1Size == V2Size) {
// Do the base pointers alias assuming type and size.
AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size,
V1TBAAInfo, UnderlyingV2,
// 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, TD);
+ DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
+ GEP2MaxLookupReached, DL);
const Value *GEP1BasePtr =
- DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
+ DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
+ GEP1MaxLookupReached, DL);
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
- assert(TD == 0 &&
- "DecomposeGEPExpression and GetUnderlyingObject disagree!");
+ assert(!DL &&
+ "DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
+ // If the max search depth is reached the result is undefined
+ if (GEP2MaxLookupReached || GEP1MaxLookupReached)
+ return MayAlias;
+
// Same offsets.
if (GEP1BaseOffset == GEP2BaseOffset &&
- areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices))
+ GEP1VariableIndices == GEP2VariableIndices)
return NoAlias;
GEP1VariableIndices.clear();
}
}
- // Do the base pointers alias?
- AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0,
- UnderlyingV2, UnknownSize, 0);
-
// If we get a No or May, then return it immediately, no amount of analysis
// will improve this situation.
if (BaseAlias != MustAlias) return BaseAlias;
-
+
// 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, TD);
-
+ DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
+ GEP1MaxLookupReached, DL);
+
int64_t GEP2BaseOffset;
+ bool GEP2MaxLookupReached;
SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
- DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
-
+ DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices,
+ GEP2MaxLookupReached, DL);
+
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
- assert(TD == 0 &&
+ assert(!DL &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
-
+ // 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);
-
+
} else {
// Check to see if these two pointers are related by the getelementptr
// instruction. If one pointer is a GEP with a non-zero index of the other
if (V1Size == UnknownSize && V2Size == UnknownSize)
return MayAlias;
- AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0,
+ AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, nullptr,
V2, V2Size, V2TBAAInfo);
if (R != MustAlias)
// If V2 may alias GEP base pointer, conservatively returns MayAlias.
return R;
const Value *GEP1BasePtr =
- DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
-
+ DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices,
+ GEP1MaxLookupReached, DL);
+
// DecomposeGEPExpression and GetUnderlyingObject should return the
- // same result except when DecomposeGEPExpression has no TargetData.
+ // same result except when DecomposeGEPExpression has no DataLayout.
if (GEP1BasePtr != UnderlyingV1) {
- assert(TD == 0 &&
+ assert(!DL &&
"DecomposeGEPExpression and GetUnderlyingObject disagree!");
return MayAlias;
}
+ // If the max search depth is reached the result is undefined
+ if (GEP1MaxLookupReached)
+ return MayAlias;
}
-
+
// 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).
return NoAlias;
}
} else {
- if (V1Size != UnknownSize) {
+ // We have the situation where:
+ // + +
+ // | BaseOffset |
+ // ---------------->|
+ // |-->V1Size |-------> V2Size
+ // 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 != UnknownSize && V2Size != UnknownSize) {
if (-(uint64_t)GEP1BaseOffset < V1Size)
return PartialAlias;
return NoAlias;
const MDNode *PNTBAAInfo,
const Value *V2, uint64_t V2Size,
const MDNode *V2TBAAInfo) {
+ // Track phi nodes we have visited. We use this information when we determine
+ // value equivalence.
+ VisitedPhiBBs.insert(PN->getParent());
+
// If the values are PHIs in the same block, we can do a more precise
// as well as efficient check: just check for aliases between the values
// on corresponding edges.
Location(V2, V2Size, V2TBAAInfo));
if (PN > V2)
std::swap(Locs.first, Locs.second);
-
- AliasResult Alias =
- aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
- PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
- V2Size, V2TBAAInfo);
- if (Alias == MayAlias)
- return MayAlias;
-
- // If the first source of the PHI nodes NoAlias and the other inputs are
- // the PHI node itself through some amount of recursion this does not add
- // any new information so just return NoAlias.
- // bb:
- // ptr = ptr2 + 1
- // loop:
- // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one]
- // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one]
- // ...
- // ptr_plus_one = gep ptr_phi, 1
- // ptr2_plus_one = gep ptr2_phi, 1
- // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do
- // not alias each other.
- bool ArePhisAssumedNoAlias = false;
- AliasResult OrigAliasResult;
- if (Alias == NoAlias) {
- // Pretend the phis do not alias.
- assert(AliasCache.count(Locs) &&
- "There must exist an entry for the phi node");
- OrigAliasResult = AliasCache[Locs];
- AliasCache[Locs] = NoAlias;
- ArePhisAssumedNoAlias = true;
- }
-
- for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
+ // Analyse the PHIs' inputs under the assumption that the PHIs are
+ // NoAlias.
+ // If the PHIs are May/MustAlias there must be (recursively) an input
+ // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
+ // there must be an operation on the PHIs within the PHIs' value cycle
+ // that causes a MayAlias.
+ // Pretend the phis do not alias.
+ AliasResult Alias = NoAlias;
+ assert(AliasCache.count(Locs) &&
+ "There must exist an entry for the phi node");
+ AliasResult OrigAliasResult = AliasCache[Locs];
+ AliasCache[Locs] = NoAlias;
+
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
AliasResult ThisAlias =
aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
}
// Reset if speculation failed.
- if (ArePhisAssumedNoAlias && Alias != NoAlias)
+ if (Alias != NoAlias)
AliasCache[Locs] = OrigAliasResult;
return Alias;
V2 = V2->stripPointerCasts();
// Are we checking for alias of the same value?
- if (V1 == V2) return MustAlias;
+ // 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
+ // reach the value.
+ if (isValueEqualInPotentialCycles(V1, V2))
+ return MustAlias;
if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
return NoAlias; // Scalars cannot alias each other
// Figure out what objects these things are pointing to if we can.
- const Value *O1 = GetUnderlyingObject(V1, TD);
- const Value *O2 = GetUnderlyingObject(V2, TD);
+ 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.
(isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
return NoAlias;
- // Arguments can't alias with local allocations or noalias calls
- // in the same function.
- if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) ||
- (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1)))))
+ // Function arguments can't alias with things that are known to be
+ // unambigously identified at the function level.
+ if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
+ (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
return NoAlias;
// Most objects can't alias null.
if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
(isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
return NoAlias;
-
+
// If one pointer is the result of a call/invoke or load and the other is a
// non-escaping local object within the same function, then we know the
// object couldn't escape to a point where the call could return it.
// If the size of one access is larger than the entire object on the other
// side, then we know such behavior is undefined and can assume no alias.
- if (TD)
- if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) ||
- (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI)))
+ if (DL)
+ if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *DL, *TLI)) ||
+ (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *DL, *TLI)))
return NoAlias;
-
+
// Check the cache before climbing up use-def chains. This also terminates
// otherwise infinitely recursive queries.
LocPair Locs(Location(V1, V1Size, V1TBAAInfo),
std::swap(V1, V2);
std::swap(V1Size, V2Size);
std::swap(O1, O2);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2);
if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo,
if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
std::swap(V1, V2);
std::swap(V1Size, V2Size);
+ std::swap(V1TBAAInfo, V2TBAAInfo);
}
if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo,
// 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 (TD && O1 == O2)
- if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) ||
- (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI)))
+ if (DL && O1 == O2)
+ if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *DL, *TLI)) ||
+ (V2Size != UnknownSize && isObjectSize(O2, V2Size, *DL, *TLI)))
return AliasCache[Locs] = PartialAlias;
AliasResult Result =
Location(V2, V2Size, V2TBAAInfo));
return AliasCache[Locs] = Result;
}
+
+bool BasicAliasAnalysis::isValueEqualInPotentialCycles(const Value *V,
+ const Value *V2) {
+ if (V != V2)
+ return false;
+
+ const Instruction *Inst = dyn_cast<Instruction>(V);
+ if (!Inst)
+ return true;
+
+ if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
+ return false;
+
+ // Use dominance or loop info if available.
+ DominatorTreeWrapperPass *DTWP =
+ getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+ DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
+ LoopInfo *LI = getAnalysisIfAvailable<LoopInfo>();
+
+ // 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.
+ for (SmallPtrSet<const BasicBlock *, 8>::iterator PI = VisitedPhiBBs.begin(),
+ PE = VisitedPhiBBs.end();
+ PI != PE; ++PI)
+ if (isPotentiallyReachable((*PI)->begin(), Inst, DT, LI))
+ return false;
+
+ return true;
+}
+
+/// GetIndexDifference - Dest and Src are the variable indices from two
+/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
+/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
+/// difference between the two pointers.
+void BasicAliasAnalysis::GetIndexDifference(
+ SmallVectorImpl<VariableGEPIndex> &Dest,
+ const SmallVectorImpl<VariableGEPIndex> &Src) {
+ if (Src.empty())
+ return;
+
+ for (unsigned i = 0, e = Src.size(); i != e; ++i) {
+ const Value *V = Src[i].V;
+ ExtensionKind Extension = Src[i].Extension;
+ int64_t Scale = Src[i].Scale;
+
+ // Find V in Dest. This is N^2, but pointer indices almost never have more
+ // than a few variable indexes.
+ for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
+ if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
+ Dest[j].Extension != Extension)
+ continue;
+
+ // If we found it, subtract off Scale V's from the entry in Dest. If it
+ // goes to zero, remove the entry.
+ if (Dest[j].Scale != Scale)
+ Dest[j].Scale -= Scale;
+ else
+ Dest.erase(Dest.begin() + j);
+ Scale = 0;
+ break;
+ }
+
+ // If we didn't consume this entry, add it to the end of the Dest list.
+ if (Scale) {
+ VariableGEPIndex Entry = { V, Extension, -Scale };
+ Dest.push_back(Entry);
+ }
+ }
+}