X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasAnalysis.cpp;h=1f2528fa560f24614ecb298b0f15c114f92c7223;hb=9f1fb42b7e6260bcc535cfd50df60b35e17672f8;hp=d5de2fe616acbc319abc18cbf5e96b40b3fbc99f;hpb=a5f81bba4ab18d6129774d4d67495f14b6f64375;p=oota-llvm.git diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index d5de2fe616a..1f2528fa560 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -28,6 +28,7 @@ #include "llvm/Pass.h" #include "llvm/BasicBlock.h" #include "llvm/Function.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Instructions.h" #include "llvm/Type.h" #include "llvm/Target/TargetData.h" @@ -48,28 +49,11 @@ AliasAnalysis::alias(const Value *V1, unsigned V1Size, 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); } -AliasAnalysis::ModRefBehavior -AliasAnalysis::getModRefBehavior(Function *F, CallSite CS, - std::vector *Info) { - assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); - return AA->getModRefBehavior(F, CS, Info); -} - -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); @@ -81,10 +65,127 @@ void AliasAnalysis::copyValue(Value *From, Value *To) { } AliasAnalysis::ModRefResult -AliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { - // FIXME: we can do better. +AliasAnalysis::getModRefInfo(ImmutableCallSite CS, + const Value *P, unsigned Size) { + // Don't assert AA because BasicAA calls us in order to make use of the + // logic here. + + ModRefBehavior MRB = getModRefBehavior(CS); + if (MRB == DoesNotAccessMemory) + return NoModRef; + + ModRefResult Mask = ModRef; + if (MRB == OnlyReadsMemory) + Mask = Ref; + else if (MRB == AliasAnalysis::AccessesArguments) { + bool doesAlias = false; + for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); + AI != AE; ++AI) + if (!isNoAlias(*AI, ~0U, P, Size)) { + doesAlias = true; + break; + } + + if (!doesAlias) + return NoModRef; + } + + // If P points to a constant memory location, the call definitely could not + // modify the memory location. + if ((Mask & Mod) && pointsToConstantMemory(P)) + Mask = ModRefResult(Mask & ~Mod); + + // If this is BasicAA, don't forward. + if (!AA) return Mask; + + // Otherwise, fall back to the next AA in the chain. But we can merge + // in any mask we've managed to compute. + return ModRefResult(AA->getModRefInfo(CS, P, Size) & Mask); +} + +AliasAnalysis::ModRefResult +AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { + // Don't assert AA because BasicAA calls us in order to make use of the + // logic here. + + // If CS1 or CS2 are readnone, they don't interact. + ModRefBehavior CS1B = getModRefBehavior(CS1); + if (CS1B == DoesNotAccessMemory) return NoModRef; + + ModRefBehavior CS2B = getModRefBehavior(CS2); + if (CS2B == DoesNotAccessMemory) return NoModRef; + + // If they both only read from memory, there is no dependence. + if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) + return NoModRef; + + AliasAnalysis::ModRefResult Mask = ModRef; + + // If CS1 only reads memory, the only dependence on CS2 can be + // from CS1 reading memory written by CS2. + if (CS1B == OnlyReadsMemory) + Mask = ModRefResult(Mask & Ref); + + // If CS2 only access memory through arguments, accumulate the mod/ref + // information from CS1's references to the memory referenced by + // CS2's arguments. + if (CS2B == AccessesArguments) { + AliasAnalysis::ModRefResult R = NoModRef; + for (ImmutableCallSite::arg_iterator + I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { + R = ModRefResult((R | getModRefInfo(CS1, *I, UnknownSize)) & Mask); + if (R == Mask) + break; + } + return R; + } + + // If CS1 only accesses memory through arguments, check if CS2 references + // any of the memory referenced by CS1's arguments. If not, return NoModRef. + if (CS1B == AccessesArguments) { + AliasAnalysis::ModRefResult R = NoModRef; + for (ImmutableCallSite::arg_iterator + I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) + if (getModRefInfo(CS2, *I, UnknownSize) != NoModRef) { + R = Mask; + break; + } + if (R == NoModRef) + return R; + } + + // If this is BasicAA, don't forward. + if (!AA) return Mask; + + // Otherwise, fall back to the next AA in the chain. But we can merge + // in any mask we've managed to compute. + return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); +} + +AliasAnalysis::ModRefBehavior +AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { + // Don't assert AA because BasicAA calls us in order to make use of the + // logic here. + + ModRefBehavior Min = UnknownModRefBehavior; + + // Call back into the alias analysis with the other form of getModRefBehavior + // to see if it can give a better response. + if (const Function *F = CS.getCalledFunction()) + Min = getModRefBehavior(F); + + // If this is BasicAA, don't forward. + if (!AA) return Min; + + // Otherwise, fall back to the next AA in the chain. But we can merge + // in any result we've managed to compute. + return std::min(AA->getModRefBehavior(CS), Min); +} + +AliasAnalysis::ModRefBehavior +AliasAnalysis::getModRefBehavior(const Function *F) { assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); - return AA->getModRefInfo(CS1, CS2); + return AA->getModRefBehavior(F); } @@ -93,67 +194,63 @@ AliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { //===----------------------------------------------------------------------===// AliasAnalysis::ModRefResult -AliasAnalysis::getModRefInfo(LoadInst *L, Value *P, unsigned Size) { - return alias(L->getOperand(0), TD->getTypeStoreSize(L->getType()), - P, Size) ? Ref : NoModRef; +AliasAnalysis::getModRefInfo(const LoadInst *L, const Value *P, unsigned Size) { + // Be conservative in the face of volatile. + if (L->isVolatile()) + return ModRef; + + // If the load address doesn't alias the given address, it doesn't read + // or write the specified memory. + if (!alias(L->getOperand(0), getTypeStoreSize(L->getType()), P, Size)) + return NoModRef; + + // Otherwise, a load just reads. + return Ref; } AliasAnalysis::ModRefResult -AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) { - // If the stored address cannot alias the pointer in question, then the - // pointer cannot be modified by the store. +AliasAnalysis::getModRefInfo(const StoreInst *S, const Value *P, unsigned Size) { + // Be conservative in the face of volatile. + if (S->isVolatile()) + return ModRef; + + // If the store address cannot alias the pointer in question, then the + // specified memory cannot be modified by the store. if (!alias(S->getOperand(1), - TD->getTypeStoreSize(S->getOperand(0)->getType()), P, Size)) + 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 = UnknownModRefBehavior; - if (Function *F = CS.getCalledFunction()) - MRB = getModRefBehavior(F, CS, Info); - if (MRB != DoesNotAccessMemory && CS.onlyReadsMemory()) - return OnlyReadsMemory; - return MRB; -} + if (pointsToConstantMemory(P)) + return NoModRef; -AliasAnalysis::ModRefBehavior -AliasAnalysis::getModRefBehavior(Function *F, - std::vector *Info) { - if (F->doesNotAccessMemory()) - // Can't do better than this. - return DoesNotAccessMemory; - ModRefBehavior MRB = getModRefBehavior(F, CallSite(), Info); - if (MRB != DoesNotAccessMemory && F->onlyReadsMemory()) - return OnlyReadsMemory; - return MRB; + // Otherwise, a store just writes. + return Mod; } AliasAnalysis::ModRefResult -AliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { - ModRefResult Mask = ModRef; - ModRefBehavior MRB = getModRefBehavior(CS); - if (MRB == OnlyReadsMemory) - Mask = Ref; - else if (MRB == DoesNotAccessMemory) +AliasAnalysis::getModRefInfo(const VAArgInst *V, const Value *P, unsigned Size) { + // If the va_arg address cannot alias the pointer in question, then the + // specified memory cannot be accessed by the va_arg. + if (!alias(V->getOperand(0), UnknownSize, P, Size)) return NoModRef; - if (!AA) return Mask; + // If the pointer is a pointer to constant memory, then it could not have been + // modified by this va_arg. + if (pointsToConstantMemory(P)) + return NoModRef; + + // Otherwise, a va_arg reads and writes. + return ModRef; +} - // 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::ModRefBehavior +AliasAnalysis::getIntrinsicModRefBehavior(unsigned iid) { +#define GET_INTRINSIC_MODREF_BEHAVIOR +#include "llvm/Intrinsics.gen" +#undef GET_INTRINSIC_MODREF_BEHAVIOR } // AliasAnalysis destructor: DO NOT move this to the header file for @@ -167,18 +264,23 @@ AliasAnalysis::~AliasAnalysis() {} /// AliasAnalysis interface before any other methods are called. /// void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { - TD = &P->getAnalysis(); + TD = P->getAnalysisIfAvailable(); AA = &P->getAnalysis(); } // getAnalysisUsage - All alias analysis implementations should invoke this -// directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that -// TargetData is required by the pass. +// directly (using AliasAnalysis::getAnalysisUsage(AU)). void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); // All AA's need TargetData. AU.addRequired(); // All AA's chain } +/// getTypeStoreSize - Return the TargetData store size for the given type, +/// if known, or a conservative value otherwise. +/// +unsigned AliasAnalysis::getTypeStoreSize(const Type *Ty) { + return TD ? TD->getTypeStoreSize(Ty) : ~0u; +} + /// canBasicBlockModify - Return true if it is possible for execution of the /// specified basic block to modify the value pointed to by Ptr. /// @@ -197,12 +299,12 @@ bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, const Value *Ptr, unsigned Size) { assert(I1.getParent() == I2.getParent() && "Instructions not in same basic block!"); - BasicBlock::iterator I = const_cast(&I1); - BasicBlock::iterator E = const_cast(&I2); + BasicBlock::const_iterator I = &I1; + BasicBlock::const_iterator E = &I2; ++E; // Convert from inclusive to exclusive range. for (; I != E; ++I) // Check every instruction in range - if (getModRefInfo(I, const_cast(Ptr), Size) & Mod) + if (getModRefInfo(I, Ptr, Size) & Mod) return true; return false; } @@ -211,20 +313,24 @@ bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, /// function. bool llvm::isNoAliasCall(const Value *V) { if (isa(V) || isa(V)) - return CallSite(const_cast(cast(V))) + return ImmutableCallSite(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 +/// Global Variables and Functions (but not Global Aliases) /// Allocas and Mallocs /// ByVal and NoAlias Arguments /// NoAlias returns /// bool llvm::isIdentifiedObject(const Value *V) { - if (isa(V) || isa(V) || isNoAliasCall(V)) + if (isa(V)) + return true; + if (isa(V) && !isa(V)) + return true; + if (isNoAliasCall(V)) return true; if (const Argument *A = dyn_cast(V)) return A->hasNoAliasAttr() || A->hasByValAttr();