X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBasicAliasAnalysis.cpp;h=fe71f04098b13061a0b04c4dcf2a99bc3fd7f9dd;hb=002ec1482c83003c6aef841395271aa5993d916a;hp=944d0e0d375669b205f0d67fc56b24bda1ef9fe8;hpb=20d6f0982ad33818cfa141f80157ac13e36d5550;p=oota-llvm.git diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 944d0e0d375..fe71f04098b 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/Passes.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" @@ -35,47 +36,6 @@ using namespace llvm; // Useful predicates //===----------------------------------------------------------------------===// -// Determine if an AllocationInst instruction escapes from the function it is -// contained in. If it does not escape, there is no way for another function to -// mod/ref it. We do this by looking at its uses and determining if the uses -// can escape (recursively). -static bool AddressMightEscape(const Value *V) { - for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); - UI != E; ++UI) { - const Instruction *I = cast(*UI); - switch (I->getOpcode()) { - case Instruction::Load: - break; //next use. - case Instruction::Store: - if (I->getOperand(0) == V) - return true; // Escapes if the pointer is stored. - break; // next use. - case Instruction::GetElementPtr: - if (AddressMightEscape(I)) - return true; - break; // next use. - case Instruction::BitCast: - if (AddressMightEscape(I)) - return true; - break; // next use - case Instruction::Ret: - // If returned, the address will escape to calling functions, but no - // callees could modify it. - break; // next use - case Instruction::Call: - // If the call is to a few known safe intrinsics, we know that it does - // not escape. - // TODO: Eventually just check the 'nocapture' attribute. - if (!isa(I)) - return true; - break; // next use - default: - return true; - } - } - return false; -} - static const User *isGEP(const Value *V) { if (isa(V) || (isa(V) && @@ -85,7 +45,7 @@ static const User *isGEP(const Value *V) { } static const Value *GetGEPOperands(const Value *V, - SmallVector &GEPOps){ + SmallVector &GEPOps) { assert(GEPOps.empty() && "Expect empty list to populate!"); GEPOps.insert(GEPOps.end(), cast(V)->op_begin()+1, cast(V)->op_end()); @@ -104,30 +64,6 @@ static const Value *GetGEPOperands(const Value *V, return V; } -/// isNoAliasCall - Return true if this pointer is returned by a noalias -/// function. -static bool isNoAliasCall(const Value *V) { - if (isa(V) || isa(V)) - return CallSite(const_cast(cast(V))) - .paramHasAttr(0, Attribute::NoAlias); - return false; -} - -/// isIdentifiedObject - Return true if this pointer refers to a distinct and -/// identifiable object. This returns true for: -/// Global Variables and Functions -/// Allocas and Mallocs -/// ByVal and NoAlias Arguments -/// NoAlias returns -/// -static bool isIdentifiedObject(const Value *V) { - if (isa(V) || isa(V) || isNoAliasCall(V)) - return true; - if (const Argument *A = dyn_cast(V)) - return A->hasNoAliasAttr() || A->hasByValAttr(); - return false; -} - /// isKnownNonNull - Return true if we know that the specified value is never /// null. static bool isKnownNonNull(const Value *V) { @@ -149,13 +85,18 @@ static bool isKnownNonNull(const Value *V) { static bool isNonEscapingLocalObject(const Value *V) { // If this is a local allocation, check to see if it escapes. if (isa(V) || isNoAliasCall(V)) - return !AddressMightEscape(V); - + return !PointerMayBeCaptured(V, false); + // If this is an argument that corresponds to a byval or noalias argument, - // it can't escape either. + // then it has not escaped before entering the function. Check if it escapes + // inside the function. if (const Argument *A = dyn_cast(V)) - if (A->hasByValAttr() || A->hasNoAliasAttr()) - return !AddressMightEscape(V); + if (A->hasByValAttr() || A->hasNoAliasAttr()) { + // Don't bother analyzing arguments already known not to escape. + if (A->hasNoCaptureAttr()) + return true; + return !PointerMayBeCaptured(V, false); + } return false; } @@ -182,7 +123,7 @@ static bool isObjectSmallerThan(const Value *V, unsigned Size, } if (AccessTy->isSized()) - return TD.getABITypeSize(AccessTy) < Size; + return TD.getTypePaddedSize(AccessTy) < Size; return false; } @@ -214,11 +155,6 @@ namespace { return MayAlias; } - virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, - std::vector *Info) { - return UnknownModRefBehavior; - } - virtual void getArgumentAccesses(Function *F, CallSite CS, std::vector &Info) { assert(0 && "This method may not be called on this function!"); @@ -265,7 +201,7 @@ namespace { ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); - + /// hasNoModRefInfoForCalls - We can provide mod/ref information against /// non-escaping allocations. virtual bool hasNoModRefInfoForCalls() const { return false; } @@ -308,6 +244,7 @@ bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { return false; } + // getModRefInfo - Check to see if the specified callsite can clobber the // specified memory object. Since we only look at local properties of this // function, we really can't say much about this query. We do, however, use @@ -331,7 +268,7 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { // 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 // argument without capturing it. - if (isNonEscapingLocalObject(Object)) { + if (isNonEscapingLocalObject(Object) && CS.getInstruction() != Object) { bool passedAsArg = false; // TODO: Eventually only check 'nocapture' arguments. for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); @@ -369,8 +306,7 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such -// as array references. Note that this function is heavily tail recursive. -// Hopefully we have a smart C++ compiler. :) +// as array references. // AliasAnalysis::AliasResult BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, @@ -389,13 +325,14 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, if (!isa(V1->getType()) || !isa(V2->getType())) return NoAlias; // Scalars cannot alias each other - // Strip off cast instructions... + // 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... + // Figure out what objects these things are pointing to if we can. const Value *O1 = V1->getUnderlyingObject(); const Value *O2 = V2->getUnderlyingObject(); @@ -426,10 +363,10 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, // 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)) + isNonEscapingLocalObject(O2) && O1 != O2) return NoAlias; if ((isa(O2) || isa(O2)) && - isNonEscapingLocalObject(O1)) + isNonEscapingLocalObject(O1) && O1 != O2) return NoAlias; // If we have two gep instructions with must-alias'ing base pointers, figure @@ -438,21 +375,35 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, // constant expression getelementptrs here. // if (isGEP(V1) && isGEP(V2)) { + const User *GEP1 = cast(V1); + const User *GEP2 = cast(V2); + + // If V1 and V2 are identical GEPs, just recurse down on both of them. + // This allows us to analyze things like: + // P = gep A, 0, i, 1 + // Q = gep B, 0, i, 1 + // by just analyzing A and B. This is even safe for variable indices. + if (GEP1->getType() == GEP2->getType() && + GEP1->getNumOperands() == GEP2->getNumOperands() && + GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() && + // All operands are the same, ignoring the base. + std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1)) + return alias(GEP1->getOperand(0), V1Size, GEP2->getOperand(0), V2Size); + + // Drill down into the first non-gep value, to test for must-aliasing of // the base pointers. - const User *G = cast(V1); - while (isGEP(G->getOperand(0)) && - G->getOperand(1) == - Constant::getNullValue(G->getOperand(1)->getType())) - G = cast(G->getOperand(0)); - const Value *BasePtr1 = G->getOperand(0); - - G = cast(V2); - while (isGEP(G->getOperand(0)) && - G->getOperand(1) == - Constant::getNullValue(G->getOperand(1)->getType())) - G = cast(G->getOperand(0)); - const Value *BasePtr2 = G->getOperand(0); + while (isGEP(GEP1->getOperand(0)) && + GEP1->getOperand(1) == + Constant::getNullValue(GEP1->getOperand(1)->getType())) + GEP1 = cast(GEP1->getOperand(0)); + const Value *BasePtr1 = GEP1->getOperand(0); + + while (isGEP(GEP2->getOperand(0)) && + GEP2->getOperand(1) == + Constant::getNullValue(GEP2->getOperand(1)->getType())) + GEP2 = cast(GEP2->getOperand(0)); + const Value *BasePtr2 = GEP2->getOperand(0); // Do the base pointers alias? AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);