X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBasicAliasAnalysis.cpp;h=900a5b61ee96e9a64bffc8535d1d3f489894943d;hb=497f61940a2b682bff79a0e2ada0caa65508f80c;hp=d0620456399b3a4159f83346b4f3d42f8c98461b;hpb=72776d219014f6b07485e7dcc5a818849904e720;p=oota-llvm.git diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index d0620456399..900a5b61ee9 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -15,6 +15,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/MallocHelper.h" #include "llvm/Analysis/Passes.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" @@ -22,13 +23,15 @@ #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/Target/TargetData.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GetElementPtrTypeIterator.h" -#include "llvm/Support/ManagedStatic.h" #include using namespace llvm; @@ -36,12 +39,8 @@ using namespace llvm; // Useful predicates //===----------------------------------------------------------------------===// -static const User *isGEP(const Value *V) { - if (isa(V) || - (isa(V) && - cast(V)->getOpcode() == Instruction::GetElementPtr)) - return cast(V); - return 0; +static const GEPOperator *isGEP(const Value *V) { + return dyn_cast(V); } static const Value *GetGEPOperands(const Value *V, @@ -104,7 +103,7 @@ static bool isNonEscapingLocalObject(const Value *V) { /// isObjectSmallerThan - Return true if we can prove that the object specified /// by V is smaller than Size. static bool isObjectSmallerThan(const Value *V, unsigned Size, - const TargetData &TD) { + LLVMContext &Context, const TargetData &TD) { const Type *AccessTy; if (const GlobalVariable *GV = dyn_cast(V)) { AccessTy = GV->getType()->getElementType(); @@ -113,6 +112,12 @@ static bool isObjectSmallerThan(const Value *V, unsigned Size, AccessTy = AI->getType()->getElementType(); else return false; + } else if (const CallInst* CI = extractMallocCall(V)) { + if (!isArrayMalloc(V, Context, &TD)) + // The size is the argument to the malloc call. + if (const ConstantInt* C = dyn_cast(CI->getOperand(1))) + return (C->getZExtValue() < Size); + return false; } else if (const Argument *A = dyn_cast(V)) { if (A->hasByValAttr()) AccessTy = cast(A->getType())->getElementType(); @@ -143,11 +148,10 @@ namespace { explicit NoAA(void *PID) : ImmutablePass(PID) { } virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); } virtual void initializePass() { - TD = &getAnalysis(); + TD = getAnalysisIfAvailable(); } virtual AliasResult alias(const Value *V1, unsigned V1Size, @@ -157,7 +161,7 @@ namespace { virtual void getArgumentAccesses(Function *F, CallSite CS, std::vector &Info) { - assert(0 && "This method may not be called on this function!"); + llvm_unreachable("This method may not be called on this function!"); } virtual void getMustAliases(Value *P, std::vector &RetVals) { } @@ -211,6 +215,11 @@ namespace { bool pointsToConstantMemory(const Value *P); private: + // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction + // against another. + AliasResult aliasGEP(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size); + // CheckGEPInstructions - Check two GEP instructions with known // must-aliasing base pointers. This checks to see if the index expressions // preclude the pointers from aliasing... @@ -280,6 +289,27 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { if (!passedAsArg) return NoModRef; } + + if (IntrinsicInst *II = dyn_cast(CS.getInstruction())) { + switch (II->getIntrinsicID()) { + default: break; + case Intrinsic::atomic_cmp_swap: + case Intrinsic::atomic_swap: + case Intrinsic::atomic_load_add: + case Intrinsic::atomic_load_sub: + case Intrinsic::atomic_load_and: + case Intrinsic::atomic_load_nand: + case Intrinsic::atomic_load_or: + case Intrinsic::atomic_load_xor: + case Intrinsic::atomic_load_max: + case Intrinsic::atomic_load_min: + case Intrinsic::atomic_load_umax: + case Intrinsic::atomic_load_umin: + if (alias(II->getOperand(1), Size, P, Size) == NoAlias) + return NoModRef; + break; + } + } } // The AliasAnalysis base class has some smarts, lets use them. @@ -304,71 +334,12 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { return NoAA::getModRefInfo(CS1, CS2); } - -// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such -// as array references. +// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction +// against another. // AliasAnalysis::AliasResult -BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - // Strip off any constant expression casts if they exist - if (const ConstantExpr *CE = dyn_cast(V1)) - if (CE->isCast() && isa(CE->getOperand(0)->getType())) - V1 = CE->getOperand(0); - if (const ConstantExpr *CE = dyn_cast(V2)) - if (CE->isCast() && isa(CE->getOperand(0)->getType())) - V2 = CE->getOperand(0); - - // Are we checking for alias of the same value? - if (V1 == V2) return MustAlias; - - if (!isa(V1->getType()) || !isa(V2->getType())) - return NoAlias; // Scalars cannot alias each other - - // Strip off cast instructions. Since V1 and V2 are pointers, they must be - // pointer<->pointer bitcasts. - if (const BitCastInst *I = dyn_cast(V1)) - return alias(I->getOperand(0), V1Size, V2, V2Size); - if (const BitCastInst *I = dyn_cast(V2)) - return alias(V1, V1Size, I->getOperand(0), V2Size); - - // Figure out what objects these things are pointing to if we can. - const Value *O1 = V1->getUnderlyingObject(); - const Value *O2 = V2->getUnderlyingObject(); - - if (O1 != O2) { - // If V1/V2 point to two different objects we know that we have no alias. - if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) - return NoAlias; - - // Arguments can't alias with local allocations or noalias calls. - if ((isa(O1) && (isa(O2) || isNoAliasCall(O2))) || - (isa(O2) && (isa(O1) || isNoAliasCall(O1)))) - return NoAlias; - - // Most objects can't alias null. - if ((isa(V2) && isKnownNonNull(O1)) || - (isa(V1) && isKnownNonNull(O2))) - 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. - const TargetData &TD = getTargetData(); - if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, TD)) || - (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, TD))) - return NoAlias; - - // If one pointer is the result of a call/invoke 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. - if ((isa(O1) || isa(O1)) && - isNonEscapingLocalObject(O2) && O1 != O2) - return NoAlias; - if ((isa(O2) || isa(O2)) && - isNonEscapingLocalObject(O1) && O1 != O2) - return NoAlias; - +BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size) { // If we have two gep instructions with must-alias'ing base pointers, figure // out if the indexes to the GEP tell us anything about the derived pointer. // Note that we also handle chains of getelementptr instructions as well as @@ -436,79 +407,137 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, // instruction. If one pointer is a GEP with a non-zero index of the other // pointer, we know they cannot alias. // - if (isGEP(V2)) { - std::swap(V1, V2); - std::swap(V1Size, V2Size); - } - - if (V1Size != ~0U && V2Size != ~0U) - if (isGEP(V1)) { - SmallVector GEPOperands; - const Value *BasePtr = GetGEPOperands(V1, GEPOperands); - - AliasResult R = alias(BasePtr, V1Size, V2, V2Size); - if (R == MustAlias) { - // If there is at least one non-zero constant index, we know they cannot - // alias. - bool ConstantFound = false; - bool AllZerosFound = true; - for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) - if (const Constant *C = dyn_cast(GEPOperands[i])) { - if (!C->isNullValue()) { - ConstantFound = true; - AllZerosFound = false; - break; - } - } else { - AllZerosFound = false; - } + if (V1Size == ~0U || V2Size == ~0U) + return MayAlias; - // If we have getelementptr , 0, 0, 0, 0, ... and V2 must aliases - // the ptr, the end result is a must alias also. - if (AllZerosFound) - return MustAlias; + SmallVector GEPOperands; + const Value *BasePtr = GetGEPOperands(V1, GEPOperands); + + AliasResult R = alias(BasePtr, V1Size, V2, V2Size); + if (R == MustAlias) { + // If there is at least one non-zero constant index, we know they cannot + // alias. + bool ConstantFound = false; + bool AllZerosFound = true; + for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) + if (const Constant *C = dyn_cast(GEPOperands[i])) { + if (!C->isNullValue()) { + ConstantFound = true; + AllZerosFound = false; + break; + } + } else { + AllZerosFound = false; + } - if (ConstantFound) { - if (V2Size <= 1 && V1Size <= 1) // Just pointer check? - return NoAlias; + // If we have getelementptr , 0, 0, 0, 0, ... and V2 must aliases + // the ptr, the end result is a must alias also. + if (AllZerosFound) + return MustAlias; - // Otherwise we have to check to see that the distance is more than - // the size of the argument... build an index vector that is equal to - // the arguments provided, except substitute 0's for any variable - // indexes we find... - if (cast( - BasePtr->getType())->getElementType()->isSized()) { - for (unsigned i = 0; i != GEPOperands.size(); ++i) - if (!isa(GEPOperands[i])) - GEPOperands[i] = - Constant::getNullValue(GEPOperands[i]->getType()); - int64_t Offset = - getTargetData().getIndexedOffset(BasePtr->getType(), - &GEPOperands[0], - GEPOperands.size()); - - if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) - return NoAlias; - } - } + if (ConstantFound) { + if (V2Size <= 1 && V1Size <= 1) // Just pointer check? + return NoAlias; + + // Otherwise we have to check to see that the distance is more than + // the size of the argument... build an index vector that is equal to + // the arguments provided, except substitute 0's for any variable + // indexes we find... + if (TD && + cast(BasePtr->getType())->getElementType()->isSized()) { + for (unsigned i = 0; i != GEPOperands.size(); ++i) + if (!isa(GEPOperands[i])) + GEPOperands[i] = Constant::getNullValue(GEPOperands[i]->getType()); + int64_t Offset = + TD->getIndexedOffset(BasePtr->getType(), + &GEPOperands[0], + GEPOperands.size()); + + if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) + return NoAlias; } } + } + + return MayAlias; +} + +// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such +// as array references. +// +AliasAnalysis::AliasResult +BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size) { + // 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(V1->getType()) || !isa(V2->getType())) + return NoAlias; // Scalars cannot alias each other + + // Figure out what objects these things are pointing to if we can. + const Value *O1 = V1->getUnderlyingObject(); + const Value *O2 = V2->getUnderlyingObject(); + + if (O1 != O2) { + // If V1/V2 point to two different objects we know that we have no alias. + if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) + return NoAlias; + + // Arguments can't alias with local allocations or noalias calls. + if ((isa(O1) && (isa(O2) || isNoAliasCall(O2))) || + (isa(O2) && (isa(O1) || isNoAliasCall(O1)))) + return NoAlias; + + // Most objects can't alias null. + if ((isa(V2) && isKnownNonNull(O1)) || + (isa(V1) && isKnownNonNull(O2))) + 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. + LLVMContext &Context = V1->getContext(); + if (TD) + if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, Context, *TD)) || + (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, Context, *TD))) + return NoAlias; + + // If one pointer is the result of a call/invoke 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. + if ((isa(O1) || isa(O1)) && + isNonEscapingLocalObject(O2) && O1 != O2) + return NoAlias; + if ((isa(O2) || isa(O2)) && + isNonEscapingLocalObject(O1) && O1 != O2) + return NoAlias; + + if (!isGEP(V1) && isGEP(V2)) { + std::swap(V1, V2); + std::swap(V1Size, V2Size); + } + if (isGEP(V1)) + return aliasGEP(V1, V1Size, V2, V2Size); return MayAlias; } // This function is used to determine if the indices of two GEP instructions are // equal. V1 and V2 are the indices. -static bool IndexOperandsEqual(Value *V1, Value *V2) { +static bool IndexOperandsEqual(Value *V1, Value *V2, LLVMContext &Context) { if (V1->getType() == V2->getType()) return V1 == V2; if (Constant *C1 = dyn_cast(V1)) if (Constant *C2 = dyn_cast(V2)) { // Sign extend the constants to long types, if necessary - if (C1->getType() != Type::Int64Ty) - C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); - if (C2->getType() != Type::Int64Ty) - C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); + if (C1->getType() != Type::getInt64Ty(Context)) + C1 = ConstantExpr::getSExt(C1, Type::getInt64Ty(Context)); + if (C2->getType() != Type::getInt64Ty(Context)) + C2 = ConstantExpr::getSExt(C2, Type::getInt64Ty(Context)); return C1 == C2; } return false; @@ -529,6 +558,8 @@ BasicAliasAnalysis::CheckGEPInstructions( const PointerType *GEPPointerTy = cast(BasePtr1Ty); + LLVMContext &Context = GEPPointerTy->getContext(); + // Find the (possibly empty) initial sequence of equal values... which are not // necessarily constants. unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; @@ -536,7 +567,8 @@ BasicAliasAnalysis::CheckGEPInstructions( unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); unsigned UnequalOper = 0; while (UnequalOper != MinOperands && - IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { + IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper], + Context)) { // Advance through the type as we go... ++UnequalOper; if (const CompositeType *CT = dyn_cast(BasePtr1Ty)) @@ -600,10 +632,10 @@ BasicAliasAnalysis::CheckGEPInstructions( if (Constant *G2OC = dyn_cast(const_cast(G2Oper))){ if (G1OC->getType() != G2OC->getType()) { // Sign extend both operands to long. - if (G1OC->getType() != Type::Int64Ty) - G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); - if (G2OC->getType() != Type::Int64Ty) - G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); + if (G1OC->getType() != Type::getInt64Ty(Context)) + G1OC = ConstantExpr::getSExt(G1OC, Type::getInt64Ty(Context)); + if (G2OC->getType() != Type::getInt64Ty(Context)) + G2OC = ConstantExpr::getSExt(G2OC, Type::getInt64Ty(Context)); GEP1Ops[FirstConstantOper] = G1OC; GEP2Ops[FirstConstantOper] = G2OC; } @@ -674,6 +706,10 @@ BasicAliasAnalysis::CheckGEPInstructions( // However, one GEP may have more operands than the other. If this is the // case, there may still be hope. Check this now. if (FirstConstantOper == MinOperands) { + // Without TargetData, we won't know what the offsets are. + if (!TD) + return MayAlias; + // Make GEP1Ops be the longer one if there is a longer one. if (NumGEP1Ops < NumGEP2Ops) { std::swap(GEP1Ops, GEP2Ops); @@ -693,13 +729,12 @@ BasicAliasAnalysis::CheckGEPInstructions( GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); // Okay, now get the offset. This is the relative offset for the full // instruction. - const TargetData &TD = getTargetData(); - int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, - NumGEP1Ops); + int64_t Offset1 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, + NumGEP1Ops); // Now check without any constants at the end. - int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, - MinOperands); + int64_t Offset2 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, + MinOperands); // Make sure we compare the absolute difference. if (Offset1 > Offset2) @@ -735,7 +770,8 @@ BasicAliasAnalysis::CheckGEPInstructions( const Type *ZeroIdxTy = GEPPointerTy; for (unsigned i = 0; i != FirstConstantOper; ++i) { if (!isa(ZeroIdxTy)) - GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); + GEP1Ops[i] = GEP2Ops[i] = + Constant::getNullValue(Type::getInt32Ty(Context)); if (const CompositeType *CT = dyn_cast(ZeroIdxTy)) ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); @@ -776,9 +812,13 @@ BasicAliasAnalysis::CheckGEPInstructions( // value possible. // if (const ArrayType *AT = dyn_cast(BasePtr1Ty)) - GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1); + GEP1Ops[i] = + ConstantInt::get(Type::getInt64Ty(Context), + AT->getNumElements()-1); else if (const VectorType *VT = dyn_cast(BasePtr1Ty)) - GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,VT->getNumElements()-1); + GEP1Ops[i] = + ConstantInt::get(Type::getInt64Ty(Context), + VT->getNumElements()-1); } } @@ -813,11 +853,11 @@ BasicAliasAnalysis::CheckGEPInstructions( } } - if (GEPPointerTy->getElementType()->isSized()) { + if (TD && GEPPointerTy->getElementType()->isSized()) { int64_t Offset1 = - getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); + TD->getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); int64_t Offset2 = - getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); + TD->getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); assert(Offset1 != Offset2 && "There is at least one different constant here!");