#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/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/GetElementPtrTypeIterator.h"
#include <algorithm>
using namespace llvm;
return false;
}
+/// isEscapeSource - Return true if the pointer is one which would have
+/// been considered an escape by isNonEscapingLocalObject.
+static bool isEscapeSource(const Value *V) {
+ if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
+ return true;
+
+ // The load case works because isNonEscapingLocalObject considers all
+ // stores to be escapes (it passes true for the StoreCaptures argument
+ // to PointerMayBeCaptured).
+ if (isa<LoadInst>(V))
+ return true;
+
+ return false;
+}
/// isObjectSmallerThan - Return true if we can prove that the object specified
/// by V is smaller than Size.
} else if (const CallInst* CI = extractMallocCall(V)) {
if (!isArrayMalloc(V, &TD))
// The size is the argument to the malloc call.
- if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getOperand(1)))
+ if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0)))
return (C->getZExtValue() < Size);
return false;
} else if (const Argument *A = dyn_cast<Argument>(V)) {
virtual void deleteValue(Value *V) {}
virtual void copyValue(Value *From, Value *To) {}
+
+ /// 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 PassInfo *PI) {
+ if (PI->isPassID(&AliasAnalysis::ID))
+ return (AliasAnalysis*)this;
+ return this;
+ }
};
} // End of anonymous namespace
ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
//===----------------------------------------------------------------------===//
-// BasicAA Pass
+// BasicAliasAnalysis Pass
//===----------------------------------------------------------------------===//
+#ifndef NDEBUG
+static const Function *getParent(const Value *V) {
+ if (const Instruction *inst = dyn_cast<Instruction>(V))
+ return inst->getParent()->getParent();
+
+ if (const Argument *arg = dyn_cast<Argument>(V))
+ return arg->getParent();
+
+ return NULL;
+}
+
+static bool notDifferentParent(const Value *O1, const Value *O2) {
+
+ const Function *F1 = getParent(O1);
+ const Function *F2 = getParent(O2);
+
+ return !F1 || !F2 || F1 == F2;
+}
+#endif
+
namespace {
/// BasicAliasAnalysis - This is the default alias analysis implementation.
/// Because it doesn't chain to a previous alias analysis (like -no-aa), it
struct BasicAliasAnalysis : public NoAA {
static char ID; // Class identification, replacement for typeinfo
BasicAliasAnalysis() : NoAA(&ID) {}
+
AliasResult alias(const Value *V1, unsigned V1Size,
const Value *V2, unsigned V2Size) {
- assert(VisitedPHIs.empty() && "VisitedPHIs must be cleared after use!");
+ assert(Visited.empty() && "Visited must be cleared after use!");
+ assert(notDifferentParent(V1, V2) &&
+ "BasicAliasAnalysis doesn't support interprocedural queries.");
AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size);
- VisitedPHIs.clear();
+ Visited.clear();
return Alias;
}
/// global) or not.
bool pointsToConstantMemory(const Value *P);
+ /// 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 PassInfo *PI) {
+ if (PI->isPassID(&AliasAnalysis::ID))
+ return (AliasAnalysis*)this;
+ return this;
+ }
+
private:
- // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call.
- SmallPtrSet<const Value*, 16> VisitedPHIs;
+ // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP().
+ SmallPtrSet<const Value*, 16> Visited;
// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
// instruction against another.
/// simple "address taken" analysis on local objects.
AliasAnalysis::ModRefResult
BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
+ assert(notDifferentParent(CS.getInstruction(), P) &&
+ "AliasAnalysis query involving multiple functions!");
+
const Value *Object = P->getUnderlyingObject();
// If this is a tail call and P points to a stack location, we know that
for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
CI != CE; ++CI, ++ArgNo) {
// Only look at the no-capture pointer arguments.
- if (!isa<PointerType>((*CI)->getType()) ||
+ if (!(*CI)->getType()->isPointerTy() ||
!CS.paramHasAttr(ArgNo+1, Attribute::NoCapture))
continue;
case Intrinsic::memcpy:
case Intrinsic::memmove: {
unsigned Len = ~0U;
- if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3)))
+ if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2)))
Len = LenCI->getZExtValue();
- Value *Dest = II->getOperand(1);
- Value *Src = II->getOperand(2);
+ Value *Dest = II->getArgOperand(0);
+ Value *Src = II->getArgOperand(1);
if (isNoAlias(Dest, Len, P, Size)) {
if (isNoAlias(Src, Len, P, Size))
return NoModRef;
case Intrinsic::memset:
// Since memset is 'accesses arguments' only, the AliasAnalysis base class
// will handle it for the variable length case.
- if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) {
+ if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) {
unsigned Len = LenCI->getZExtValue();
- Value *Dest = II->getOperand(1);
+ Value *Dest = II->getArgOperand(0);
if (isNoAlias(Dest, Len, P, Size))
return NoModRef;
}
case Intrinsic::atomic_load_umax:
case Intrinsic::atomic_load_umin:
if (TD) {
- Value *Op1 = II->getOperand(1);
+ Value *Op1 = II->getArgOperand(0);
unsigned Op1Size = TD->getTypeStoreSize(Op1->getType());
if (isNoAlias(Op1, Op1Size, P, Size))
return NoModRef;
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::invariant_start: {
- unsigned PtrSize = cast<ConstantInt>(II->getOperand(1))->getZExtValue();
- if (isNoAlias(II->getOperand(2), PtrSize, P, Size))
+ unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
+ if (isNoAlias(II->getArgOperand(1), PtrSize, P, Size))
return NoModRef;
break;
}
case Intrinsic::invariant_end: {
- unsigned PtrSize = cast<ConstantInt>(II->getOperand(2))->getZExtValue();
- if (isNoAlias(II->getOperand(3), PtrSize, P, Size))
+ unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(1))->getZExtValue();
+ if (isNoAlias(II->getArgOperand(2), PtrSize, P, Size))
return NoModRef;
break;
}
return NoAA::getModRefInfo(CS1, CS2);
}
-/// GetLinearExpression - Analyze the specified value as a linear expression:
-/// "A*V + B". Return the scale and offset values as APInts and return V as a
-/// Value*. The incoming Value is known to be a scalar integer.
-static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
- const TargetData *TD) {
- assert(isa<IntegerType>(V->getType()) && "Not an integer value");
-
- if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
- if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
- switch (BOp->getOpcode()) {
- default: break;
- 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))
- break;
- // FALL THROUGH.
- case Instruction::Add:
- V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD);
- Offset += RHSC->getValue();
- return V;
- // TODO: SHL, MUL.
- }
- }
- }
-
- Scale = 1;
- Offset = 0;
- return V;
-}
-
-/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it
-/// into a base pointer with a constant offset and a number of scaled symbolic
-/// offsets.
-///
-/// When TargetData is around, this function is capable of analyzing everything
-/// that Value::getUnderlyingObject() can look through. When not, it just looks
-/// through pointer casts.
-///
-/// FIXME: Move this out to ValueTracking.cpp
-///
-static const Value *DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
- SmallVectorImpl<std::pair<const Value*, int64_t> > &VarIndices,
- const TargetData *TD) {
- // FIXME: Should limit depth like getUnderlyingObject?
- BaseOffs = 0;
- while (1) {
- // See if this is a bitcast or GEP.
- const Operator *Op = dyn_cast<Operator>(V);
- if (Op == 0) {
- // The only non-operator case we can handle are GlobalAliases.
- if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
- if (!GA->mayBeOverridden()) {
- V = GA->getAliasee();
- continue;
- }
- }
- return V;
- }
-
- if (Op->getOpcode() == Instruction::BitCast) {
- V = Op->getOperand(0);
- continue;
- }
-
- const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
- if (GEPOp == 0)
- return V;
-
- // Don't attempt to analyze GEPs over unsized objects.
- if (!cast<PointerType>(GEPOp->getOperand(0)->getType())
- ->getElementType()->isSized())
- return V;
-
- // If we are lacking TargetData information, we can't compute the offets of
- // elements computed by GEPs. However, we can handle bitcast equivalent
- // GEPs.
- if (!TD) {
- if (!GEPOp->hasAllZeroIndices())
- return V;
- V = GEPOp->getOperand(0);
- continue;
- }
-
- // 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 = next(GEPOp->op_begin()),
- E = GEPOp->op_end(); I != E; ++I) {
- Value *Index = *I;
- // Compute the (potentially symbolic) offset in bytes for this index.
- if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
- // For a struct, add the member offset.
- unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
- if (FieldNo == 0) continue;
-
- BaseOffs += TD->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();
- continue;
- }
-
- // TODO: Could handle linear expressions here like A[X+1], also A[X*4|1].
- uint64_t Scale = TD->getTypeAllocSize(*GTI);
-
- unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
- APInt IndexScale(Width, 0), IndexOffset(Width, 0);
- Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD);
-
- Scale *= IndexScale.getZExtValue();
- BaseOffs += IndexOffset.getZExtValue()*Scale;
-
-
- // If we already had an occurrance 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].first == Index) {
- Scale += VarIndices[i].second;
- VarIndices.erase(VarIndices.begin()+i);
- break;
- }
- }
-
- // Make sure that we have a scale that makes sense for this target's
- // pointer size.
- if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) {
- Scale <<= ShiftBits;
- Scale >>= ShiftBits;
- }
-
- if (Scale)
- VarIndices.push_back(std::make_pair(Index, Scale));
- }
-
- // Analyze the base pointer next.
- V = GEPOp->getOperand(0);
- }
-}
-
/// GetIndiceDifference - 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
const Value *V2, unsigned V2Size,
const Value *UnderlyingV1,
const Value *UnderlyingV2) {
+ // If this GEP has been visited before, we're on a use-def cycle.
+ // Such cycles are only valid when PHI nodes are involved or in unreachable
+ // code. The visitPHI function catches cycles containing PHIs, but there
+ // could still be a cycle without PHIs in unreachable code.
+ if (!Visited.insert(GEP1))
+ return MayAlias;
+
int64_t GEP1BaseOffset;
SmallVector<std::pair<const Value*, int64_t>, 4> GEP1VariableIndices;
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize,
const Value *V2, unsigned V2Size) {
+ // If this select has been visited before, we're on a use-def cycle.
+ // Such cycles are only valid when PHI nodes are involved or in unreachable
+ // code. The visitPHI function catches cycles containing PHIs, but there
+ // could still be a cycle without PHIs in unreachable code.
+ if (!Visited.insert(SI))
+ return MayAlias;
+
// If the values are Selects with the same condition, we can do a more precise
// check: just check for aliases between the values on corresponding arms.
if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
// If both arms of the Select node NoAlias or MustAlias V2, then returns
// NoAlias / MustAlias. Otherwise, returns MayAlias.
AliasResult Alias =
- aliasCheck(SI->getTrueValue(), SISize, V2, V2Size);
+ aliasCheck(V2, V2Size, SI->getTrueValue(), SISize);
if (Alias == MayAlias)
return MayAlias;
+
+ // If V2 is visited, the recursive case will have been caught in the
+ // above aliasCheck call, so these subsequent calls to aliasCheck
+ // don't need to assume that V2 is being visited recursively.
+ Visited.erase(V2);
+
AliasResult ThisAlias =
- aliasCheck(SI->getFalseValue(), SISize, V2, V2Size);
+ aliasCheck(V2, V2Size, SI->getFalseValue(), SISize);
if (ThisAlias != Alias)
return MayAlias;
return Alias;
BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize,
const Value *V2, unsigned V2Size) {
// The PHI node has already been visited, avoid recursion any further.
- if (!VisitedPHIs.insert(PN))
+ if (!Visited.insert(PN))
return MayAlias;
// If the values are PHIs in the same block, we can do a more precise
for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
Value *V = V1Srcs[i];
- // If V2 is a PHI, the recursive case will have been caught in the
+ // If V2 is visited, the recursive case will have been caught in the
// above aliasCheck call, so these subsequent calls to aliasCheck
// don't need to assume that V2 is being visited recursively.
- VisitedPHIs.erase(V2);
+ Visited.erase(V2);
AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize);
if (ThisAlias != Alias || ThisAlias == MayAlias)
AliasAnalysis::AliasResult
BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
const Value *V2, unsigned V2Size) {
+ // If either of the memory references is empty, it doesn't matter what the
+ // pointer values are.
+ if (V1Size == 0 || V2Size == 0)
+ return NoAlias;
+
// Strip off any casts if they exist.
V1 = V1->stripPointerCasts();
V2 = V2->stripPointerCasts();
// Are we checking for alias of the same value?
if (V1 == V2) return MustAlias;
- if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType()))
+ 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.
(isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
return NoAlias;
- // Arguments can't alias with local allocations or noalias calls.
- if ((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) ||
- (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))
+ // 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)))))
return NoAlias;
// Most objects can't alias null.
- if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) ||
- (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2)))
+ 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.
+ //
+ // Note that if the pointers are in different functions, there are a
+ // variety of complications. A call with a nocapture argument may still
+ // temporary store the nocapture argument's value in a temporary memory
+ // location if that memory location doesn't escape. Or it may pass a
+ // nocapture value to other functions as long as they don't capture it.
+ if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
+ return NoAlias;
+ if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
+ return NoAlias;
+ }
+
// 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)
(V2Size != ~0U && isObjectSmallerThan(O1, V2Size, *TD)))
return NoAlias;
- // If one pointer is the result of a call/invoke or load and the other is a
- // non-escaping local object, then we know the object couldn't escape to a
- // point where the call could return it. The load case works because
- // isNonEscapingLocalObject considers all stores to be escapes (it
- // passes true for the StoreCaptures argument to PointerMayBeCaptured).
- if (O1 != O2) {
- if ((isa<CallInst>(O1) || isa<InvokeInst>(O1) || isa<LoadInst>(O1) ||
- isa<Argument>(O1)) &&
- isNonEscapingLocalObject(O2))
- return NoAlias;
- if ((isa<CallInst>(O2) || isa<InvokeInst>(O2) || isa<LoadInst>(O2) ||
- isa<Argument>(O2)) &&
- isNonEscapingLocalObject(O1))
- return NoAlias;
- }
-
// FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
// GEP can't simplify, we don't even look at the PHI cases.
if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
projects / oota-llvm.git / blobdiff