X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasAnalysis.cpp;h=c5523ec4634d8e4a83aa33d4afcbb1cf91acf18a;hb=ef4cfc749a61d0d0252196c957697436ba7ec068;hp=3562e33b250c341c3e391b957646a14723719764;hpb=14ac877e0a898ab46eeba1b0b72b8e5a9918179f;p=oota-llvm.git diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index 3562e33b250..c5523ec4634 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -1,5 +1,12 @@ //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// // +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// // This file implements the generic AliasAnalysis interface which is used as the // common interface used by all clients and implementations of alias analysis. // @@ -17,33 +24,147 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Pass.h" #include "llvm/BasicBlock.h" -#include "llvm/iMemory.h" -#include "llvm/iOther.h" -#include "llvm/Constants.h" -#include "llvm/ConstantHandling.h" -#include "llvm/GlobalValue.h" -#include "llvm/DerivedTypes.h" +#include "llvm/Function.h" +#include "llvm/IntrinsicInst.h" +#include "llvm/Instructions.h" +#include "llvm/Type.h" #include "llvm/Target/TargetData.h" +using namespace llvm; // Register the AliasAnalysis interface, providing a nice name to refer to. -namespace { - RegisterAnalysisGroup Z("Alias Analysis"); +static RegisterAnalysisGroup Z("Alias Analysis"); +char AliasAnalysis::ID = 0; + +//===----------------------------------------------------------------------===// +// Default chaining methods +//===----------------------------------------------------------------------===// + +AliasAnalysis::AliasResult +AliasAnalysis::alias(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size) { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + return AA->alias(V1, V1Size, V2, V2Size); +} + +void AliasAnalysis::getMustAliases(Value *P, std::vector &RetVals) { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + return AA->getMustAliases(P, RetVals); +} + +bool AliasAnalysis::pointsToConstantMemory(const Value *P) { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + return AA->pointsToConstantMemory(P); +} + +bool AliasAnalysis::hasNoModRefInfoForCalls() const { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + return AA->hasNoModRefInfoForCalls(); +} + +void AliasAnalysis::deleteValue(Value *V) { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + AA->deleteValue(V); +} + +void AliasAnalysis::copyValue(Value *From, Value *To) { + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + AA->copyValue(From, To); } +AliasAnalysis::ModRefResult +AliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { + // FIXME: we can do better. + assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); + return AA->getModRefInfo(CS1, CS2); +} + + +//===----------------------------------------------------------------------===// +// AliasAnalysis non-virtual helper method implementation +//===----------------------------------------------------------------------===// + AliasAnalysis::ModRefResult AliasAnalysis::getModRefInfo(LoadInst *L, Value *P, unsigned Size) { - return alias(L->getOperand(0), TD->getTypeSize(L->getType()), + return alias(L->getOperand(0), TD->getTypeStoreSize(L->getType()), P, Size) ? Ref : NoModRef; } AliasAnalysis::ModRefResult AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) { - return alias(S->getOperand(1), TD->getTypeSize(S->getOperand(0)->getType()), - P, Size) ? Mod : NoModRef; + // If the stored address cannot alias the pointer in question, then the + // pointer cannot be modified by the store. + if (!alias(S->getOperand(1), + TD->getTypeStoreSize(S->getOperand(0)->getType()), P, Size)) + return NoModRef; + + // If the pointer is a pointer to constant memory, then it could not have been + // modified by this store. + return pointsToConstantMemory(P) ? NoModRef : Mod; } +AliasAnalysis::ModRefBehavior +AliasAnalysis::getModRefBehavior(CallSite CS, + std::vector *Info) { + if (CS.doesNotAccessMemory()) + // Can't do better than this. + return DoesNotAccessMemory; + ModRefBehavior MRB = getModRefBehavior(CS.getCalledFunction(), Info); + if (MRB != DoesNotAccessMemory && CS.onlyReadsMemory()) + return OnlyReadsMemory; + return MRB; +} + +AliasAnalysis::ModRefBehavior +AliasAnalysis::getModRefBehavior(Function *F, + std::vector *Info) { + if (F) { + if (F->doesNotAccessMemory()) + // Can't do better than this. + return DoesNotAccessMemory; + if (F->onlyReadsMemory()) + return OnlyReadsMemory; + if (unsigned id = F->getIntrinsicID()) { +#define GET_INTRINSIC_MODREF_BEHAVIOR +#include "llvm/Intrinsics.gen" +#undef GET_INTRINSIC_MODREF_BEHAVIOR + } + } + return UnknownModRefBehavior; +} + +AliasAnalysis::ModRefResult +AliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { + ModRefResult Mask = ModRef; + ModRefBehavior MRB = getModRefBehavior(CS); + if (MRB == DoesNotAccessMemory) + return NoModRef; + else if (MRB == OnlyReadsMemory) + Mask = Ref; + else if (MRB == AliasAnalysis::AccessesArguments) { + bool doesAlias = false; + for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); + AI != AE; ++AI) + if (alias(*AI, ~0U, P, Size) != NoAlias) { + doesAlias = true; + break; + } + + if (!doesAlias) + return NoModRef; + } + + if (!AA) return Mask; + + // If P points to a constant memory location, the call definitely could not + // modify the memory location. + if ((Mask & Mod) && AA->pointsToConstantMemory(P)) + Mask = ModRefResult(Mask & ~Mod); + + return ModRefResult(Mask & AA->getModRefInfo(CS, P, Size)); +} // AliasAnalysis destructor: DO NOT move this to the header file for // AliasAnalysis or else clients of the AliasAnalysis class may not depend on @@ -52,11 +173,12 @@ AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) { // AliasAnalysis::~AliasAnalysis() {} -/// setTargetData - Subclasses must call this method to initialize the +/// InitializeAliasAnalysis - Subclasses must call this method to initialize the /// AliasAnalysis interface before any other methods are called. /// void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { TD = &P->getAnalysis(); + AA = &P->getAnalysis(); } // getAnalysisUsage - All alias analysis implementations should invoke this @@ -64,6 +186,7 @@ void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { // TargetData is required by the pass. void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); // All AA's need TargetData. + AU.addRequired(); // All AA's chain } /// canBasicBlockModify - Return true if it is possible for execution of the @@ -94,257 +217,32 @@ bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, return false; } -//===----------------------------------------------------------------------===// -// BasicAliasAnalysis Pass Implementation -//===----------------------------------------------------------------------===// -// -// Because of the way .a files work, the implementation of the -// BasicAliasAnalysis class MUST be in the AliasAnalysis file itself, or else we -// run the risk of AliasAnalysis being used, but the default implementation not -// being linked into the tool that uses it. As such, we register and implement -// the class here. -// -namespace { - // Register this pass... - RegisterOpt - X("basicaa", "Basic Alias Analysis (default AA impl)"); - - // Declare that we implement the AliasAnalysis interface - RegisterAnalysisGroup Y; -} // End of anonymous namespace - -void BasicAliasAnalysis::initializePass() { - InitializeAliasAnalysis(this); -} - - - -// hasUniqueAddress - Return true if the -static inline bool hasUniqueAddress(const Value *V) { - return isa(V) || isa(V) || isa(V); -} - -static const Value *getUnderlyingObject(const Value *V) { - if (!isa(V->getType())) return 0; - - // If we are at some type of object... return it. - if (hasUniqueAddress(V)) return V; - - // Traverse through different addressing mechanisms... - if (const Instruction *I = dyn_cast(V)) { - if (isa(I) || isa(I)) - return getUnderlyingObject(I->getOperand(0)); - } - return 0; -} - - -// 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. :) -// -AliasAnalysis::AliasResult -BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - // Strip off constant pointer refs if they exist - if (const ConstantPointerRef *CPR = dyn_cast(V1)) - V1 = CPR->getValue(); - if (const ConstantPointerRef *CPR = dyn_cast(V2)) - V2 = CPR->getValue(); - - // Are we checking for alias of the same value? - if (V1 == V2) return MustAlias; - - if ((!isa(V1->getType()) || !isa(V2->getType())) && - V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) - return NoAlias; // Scalars cannot alias each other - - // Strip off cast instructions... - if (const Instruction *I = dyn_cast(V1)) - return alias(I->getOperand(0), V1Size, V2, V2Size); - if (const Instruction *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 = getUnderlyingObject(V1); - const Value *O2 = getUnderlyingObject(V2); - - // Pointing at a discernable object? - if (O1 && O2) { - // If they are two different objects, we know that we have no alias... - if (O1 != O2) return NoAlias; - - // If they are the same object, they we can look at the indexes. If they - // index off of the object is the same for both pointers, they must alias. - // If they are provably different, they must not alias. Otherwise, we can't - // tell anything. - } else if (O1 && isa(V2)) { - return NoAlias; // Unique values don't alias null - } else if (O2 && isa(V1)) { - return NoAlias; // Unique values don't alias null - } - - // If we have two gep instructions with identical indices, return an alias - // result equal to the alias result of the original pointer... - // - if (const GetElementPtrInst *GEP1 = dyn_cast(V1)) - if (const GetElementPtrInst *GEP2 = dyn_cast(V2)) - if (GEP1->getNumOperands() == GEP2->getNumOperands() && - GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) { - AliasResult GAlias = - CheckGEPInstructions((GetElementPtrInst*)GEP1, V1Size, - (GetElementPtrInst*)GEP2, V2Size); - if (GAlias != MayAlias) - return GAlias; - } - - // Check to see if these two pointers are related by a getelementptr - // instruction. If one pointer is a GEP with a non-zero index of the other - // pointer, we know they cannot alias. - // - if (isa(V2)) { - std::swap(V1, V2); - std::swap(V1Size, V2Size); - } - - if (const GetElementPtrInst *GEP = dyn_cast(V1)) - if (GEP->getOperand(0) == V2) { - // If there is at least one non-zero constant index, we know they cannot - // alias. - for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) - if (const Constant *C = dyn_cast(GEP->getOperand(i))) - if (!C->isNullValue()) - return NoAlias; - } - - return MayAlias; +/// isNoAliasCall - Return true if this pointer is returned by a noalias +/// function. +bool llvm::isNoAliasCall(const Value *V) { + if (isa(V) || isa(V)) + return CallSite(const_cast(cast(V))) + .paramHasAttr(0, Attribute::NoAlias); + return false; } -// CheckGEPInstructions - Check two GEP instructions of compatible types and -// equal number of arguments. This checks to see if the index expressions -// preclude the pointers from aliasing... -// -AliasAnalysis::AliasResult -BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S, - GetElementPtrInst *GEP2, unsigned G2S){ - // Do the base pointers alias? - AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S, - GEP2->getOperand(0), G2S); - if (BaseAlias != MustAlias) // No or May alias: We cannot add anything... - return BaseAlias; - - // Find the (possibly empty) initial sequence of equal values... - unsigned NumGEPOperands = GEP1->getNumOperands(); - unsigned UnequalOper = 1; - while (UnequalOper != NumGEPOperands && - GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper)) - ++UnequalOper; - - // If all operands equal each other, then the derived pointers must - // alias each other... - if (UnequalOper == NumGEPOperands) return MustAlias; - - // So now we know that the indexes derived from the base pointers, - // which are known to alias, are different. We can still determine a - // no-alias result if there are differing constant pairs in the index - // chain. For example: - // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) - // - unsigned SizeMax = std::max(G1S, G2S); - if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... - - // Scan for the first operand that is constant and unequal in the - // two getelemenptrs... - unsigned FirstConstantOper = UnequalOper; - for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) { - const Value *G1Oper = GEP1->getOperand(FirstConstantOper); - const Value *G2Oper = GEP2->getOperand(FirstConstantOper); - if (G1Oper != G2Oper && // Found non-equal constant indexes... - isa(G1Oper) && isa(G2Oper)) { - // Make sure they are comparable... and make sure the GEP with - // the smaller leading constant is GEP1. - ConstantBool *Compare = - *cast(GEP1->getOperand(FirstConstantOper)) > - *cast(GEP2->getOperand(FirstConstantOper)); - if (Compare) { // If they are comparable... - if (Compare->getValue()) - std::swap(GEP1, GEP2); // Make GEP1 < GEP2 - break; - } - } - } - - // No constant operands, we cannot tell anything... - if (FirstConstantOper == NumGEPOperands) return MayAlias; - - // If there are non-equal constants arguments, then we can figure - // out a minimum known delta between the two index expressions... at - // this point we know that the first constant index of GEP1 is less - // than the first constant index of GEP2. - // - std::vector Indices1; - Indices1.reserve(NumGEPOperands-1); - for (unsigned i = 1; i != FirstConstantOper; ++i) - Indices1.push_back(Constant::getNullValue(GEP1->getOperand(i) - ->getType())); - std::vector Indices2; - Indices2.reserve(NumGEPOperands-1); - Indices2 = Indices1; // Copy the zeros prefix... - - // Add the two known constant operands... - Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper)); - Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper)); - - const Type *GEPPointerTy = GEP1->getOperand(0)->getType(); - - // Loop over the rest of the operands... - for (unsigned i = FirstConstantOper+1; i!=NumGEPOperands; ++i){ - const Value *Op1 = GEP1->getOperand(i); - const Value *Op2 = GEP1->getOperand(i); - if (Op1 == Op2) { // If they are equal, use a zero index... - Indices1.push_back(Constant::getNullValue(Op1->getType())); - Indices2.push_back(Indices1.back()); - } else { - if (isa(Op1)) - Indices1.push_back((Value*)Op1); - else { - // GEP1 is known to produce a value less than GEP2. To be - // conservatively correct, we must assume the largest - // possible constant is used in this position. This cannot - // be the initial index to the GEP instructions (because we - // know we have at least one element before this one with - // the different constant arguments), so we know that the - // current index must be into either a struct or array. - // Because of this, we can calculate the maximum value - // possible. - // - const Type *ElTy = GEP1->getIndexedType(GEPPointerTy, - Indices1, true); - if (const StructType *STy = dyn_cast(ElTy)) { - Indices1.push_back(ConstantUInt::get(Type::UByteTy, - STy->getNumContainedTypes())); - } else { - Indices1.push_back(ConstantSInt::get(Type::LongTy, - cast(ElTy)->getNumElements())); - } - } - - if (isa(Op2)) - Indices2.push_back((Value*)Op2); - else // Conservatively assume the minimum value for this index - Indices2.push_back(Constant::getNullValue(Op1->getType())); - } - } - - unsigned Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1); - unsigned Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2); - assert(Offset1 < Offset2 &&"There is at least one different constant here!"); - - if (Offset2-Offset1 >= SizeMax) { - //std::cerr << "Determined that these two GEP's don't alias [" - // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; - return NoAlias; - } - return MayAlias; +/// 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 +/// +bool llvm::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; } +// Because of the way .a files work, we must force the BasicAA implementation to +// be pulled in if the AliasAnalysis classes are pulled in. Otherwise we run +// the risk of AliasAnalysis being used, but the default implementation not +// being linked into the tool that uses it. +DEFINING_FILE_FOR(AliasAnalysis)