BasicAliasAnalysis.cpp revision 243830
151078Speter//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===// 251078Speter// 351078Speter// The LLVM Compiler Infrastructure 451078Speter// 551078Speter// This file is distributed under the University of Illinois Open Source 651078Speter// License. See LICENSE.TXT for details. 751078Speter// 851078Speter//===----------------------------------------------------------------------===// 951078Speter// 1051078Speter// This file defines the primary stateless implementation of the 1151078Speter// Alias Analysis interface that implements identities (two different 1251078Speter// globals cannot alias, etc), but does no stateful analysis. 1351078Speter// 1451078Speter//===----------------------------------------------------------------------===// 1551078Speter 1651078Speter#include "llvm/Analysis/AliasAnalysis.h" 1751078Speter#include "llvm/Analysis/Passes.h" 1851078Speter#include "llvm/Constants.h" 1951078Speter#include "llvm/DerivedTypes.h" 2051078Speter#include "llvm/Function.h" 2151078Speter#include "llvm/GlobalAlias.h" 2251078Speter#include "llvm/GlobalVariable.h" 2351078Speter#include "llvm/Instructions.h" 2451078Speter#include "llvm/IntrinsicInst.h" 2551078Speter#include "llvm/LLVMContext.h" 2651078Speter#include "llvm/Operator.h" 2751078Speter#include "llvm/Pass.h" 2851078Speter#include "llvm/Analysis/CaptureTracking.h" 2951078Speter#include "llvm/Analysis/MemoryBuiltins.h" 3051078Speter#include "llvm/Analysis/InstructionSimplify.h" 3151078Speter#include "llvm/Analysis/ValueTracking.h" 3251078Speter#include "llvm/DataLayout.h" 3351078Speter#include "llvm/Target/TargetLibraryInfo.h" 3451078Speter#include "llvm/ADT/SmallPtrSet.h" 3551078Speter#include "llvm/ADT/SmallVector.h" 3651078Speter#include "llvm/Support/ErrorHandling.h" 37119419Sobrien#include "llvm/Support/GetElementPtrTypeIterator.h" 38119419Sobrien#include <algorithm> 39119419Sobrienusing namespace llvm; 4051078Speter 4151078Speter//===----------------------------------------------------------------------===// 4251078Speter// Useful predicates 4351078Speter//===----------------------------------------------------------------------===// 4451078Speter 4551078Speter/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 4651078Speter/// object that never escapes from the function. 4751078Speterstatic bool isNonEscapingLocalObject(const Value *V) { 4851078Speter // If this is a local allocation, check to see if it escapes. 4951078Speter if (isa<AllocaInst>(V) || isNoAliasCall(V)) 5051078Speter // Set StoreCaptures to True so that we can assume in our callers that the 5151078Speter // pointer is not the result of a load instruction. Currently 5251078Speter // PointerMayBeCaptured doesn't have any special analysis for the 5351078Speter // StoreCaptures=false case; if it did, our callers could be refined to be 5451078Speter // more precise. 5576166Smarkm return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 5665822Sjhb 5751078Speter // If this is an argument that corresponds to a byval or noalias argument, 5851078Speter // then it has not escaped before entering the function. Check if it escapes 5951078Speter // inside the function. 6051078Speter if (const Argument *A = dyn_cast<Argument>(V)) 61114216Skan if (A->hasByValAttr() || A->hasNoAliasAttr()) 6276166Smarkm // Note even if the argument is marked nocapture we still need to check 6376166Smarkm // for copies made inside the function. The nocapture attribute only 6476166Smarkm // specifies that there are no copies made that outlive the function. 6576166Smarkm return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 6676166Smarkm 6776166Smarkm return false; 6876166Smarkm} 6951078Speter 7076166Smarkm/// isEscapeSource - Return true if the pointer is one which would have 7160471Snyan/// been considered an escape by isNonEscapingLocalObject. 7251078Speterstatic bool isEscapeSource(const Value *V) { 7351078Speter if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 7451078Speter return true; 7593466Sbde 76119485Snjl // The load case works because isNonEscapingLocalObject considers all 77119485Snjl // stores to be escapes (it passes true for the StoreCaptures argument 78119485Snjl // to PointerMayBeCaptured). 79119485Snjl if (isa<LoadInst>(V)) 8051078Speter return true; 8186909Simp 8286909Simp return false; 8351078Speter} 8451078Speter 8585302Simp/// getObjectSize - Return the size of the object specified by V, or 8685365Simp/// UnknownSize if unknown. 8751078Speterstatic uint64_t getObjectSize(const Value *V, const DataLayout &TD, 8851078Speter const TargetLibraryInfo &TLI, 8977726Sjoerg bool RoundToAlign = false) { 9051078Speter uint64_t Size; 9177726Sjoerg if (getObjectSize(V, Size, &TD, &TLI, RoundToAlign)) 9251078Speter return Size; 9351078Speter return AliasAnalysis::UnknownSize; 9451078Speter} 9551078Speter 9651078Speter/// isObjectSmallerThan - Return true if we can prove that the object specified 9751078Speter/// by V is smaller than Size. 9851078Speterstatic bool isObjectSmallerThan(const Value *V, uint64_t Size, 9951078Speter const DataLayout &TD, 10093470Sbde const TargetLibraryInfo &TLI) { 10193470Sbde // This function needs to use the aligned object size because we allow 10293470Sbde // reads a bit past the end given sufficient alignment. 10393470Sbde uint64_t ObjectSize = getObjectSize(V, TD, TLI, /*RoundToAlign*/true); 10451078Speter 10551078Speter return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize < Size; 10651078Speter} 10751078Speter 10851078Speter/// isObjectSize - Return true if we can prove that the object specified 10951078Speter/// by V has size Size. 11051078Speterstatic bool isObjectSize(const Value *V, uint64_t Size, 11151078Speter const DataLayout &TD, const TargetLibraryInfo &TLI) { 112104067Sphk uint64_t ObjectSize = getObjectSize(V, TD, TLI); 113104067Sphk return ObjectSize != AliasAnalysis::UnknownSize && ObjectSize == Size; 11451078Speter} 11551078Speter 116120175Sbde//===----------------------------------------------------------------------===// 11751078Speter// GetElementPtr Instruction Decomposition and Analysis 118120175Sbde//===----------------------------------------------------------------------===// 119120175Sbde 12051078Speternamespace { 121120175Sbde enum ExtensionKind { 12251078Speter EK_NotExtended, 12351078Speter EK_SignExt, 124120175Sbde EK_ZeroExt 125120175Sbde }; 126120175Sbde 127111613Sphk struct VariableGEPIndex { 128120175Sbde const Value *V; 129112384Ssobomax ExtensionKind Extension; 13051078Speter int64_t Scale; 13160471Snyan 13260471Snyan bool operator==(const VariableGEPIndex &Other) const { 13360471Snyan return V == Other.V && Extension == Other.Extension && 13460471Snyan Scale == Other.Scale; 13560471Snyan } 13651078Speter 13751078Speter bool operator!=(const VariableGEPIndex &Other) const { 13851078Speter return !operator==(Other); 13951078Speter } 14051078Speter }; 14151078Speter} 14251078Speter 14351078Speter 14453344Speter/// GetLinearExpression - Analyze the specified value as a linear expression: 14551078Speter/// "A*V + B", where A and B are constant integers. Return the scale and offset 14651078Speter/// values as APInts and return V as a Value*, and return whether we looked 14751078Speter/// through any sign or zero extends. The incoming Value is known to have 14851078Speter/// IntegerType and it may already be sign or zero extended. 14951078Speter/// 15051078Speter/// Note that this looks through extends, so the high bits may not be 15151078Speter/// represented in the result. 15251078Speterstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 15351078Speter ExtensionKind &Extension, 15451078Speter const DataLayout &TD, unsigned Depth) { 15551078Speter assert(V->getType()->isIntegerTy() && "Not an integer value"); 15651078Speter 15751078Speter // Limit our recursion depth. 15851078Speter if (Depth == 6) { 15951078Speter Scale = 1; 16051078Speter Offset = 0; 16151078Speter return V; 16251078Speter } 16351078Speter 16451078Speter if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 16551078Speter if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 16651078Speter switch (BOp->getOpcode()) { 16751078Speter default: break; 16851078Speter case Instruction::Or: 16951078Speter // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 17051078Speter // analyze it. 17186909Simp if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 17251078Speter break; 17351078Speter // FALL THROUGH. 17486909Simp case Instruction::Add: 17586909Simp V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 17686909Simp TD, Depth+1); 17786909Simp Offset += RHSC->getValue(); 17886909Simp return V; 17986909Simp case Instruction::Mul: 18086909Simp V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 18186909Simp TD, Depth+1); 18286909Simp Offset *= RHSC->getValue(); 18386909Simp Scale *= RHSC->getValue(); 18486909Simp return V; 18586909Simp case Instruction::Shl: 18686909Simp V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 18786909Simp TD, Depth+1); 18886909Simp Offset <<= RHSC->getValue().getLimitedValue(); 18986909Simp Scale <<= RHSC->getValue().getLimitedValue(); 19086909Simp return V; 19186909Simp } 19251078Speter } 19386909Simp } 19486909Simp 19586909Simp // Since GEP indices are sign extended anyway, we don't care about the high 19686909Simp // bits of a sign or zero extended value - just scales and offsets. The 19786909Simp // extensions have to be consistent though. 19886909Simp if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 19986909Simp (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 20086909Simp Value *CastOp = cast<CastInst>(V)->getOperand(0); 20186909Simp unsigned OldWidth = Scale.getBitWidth(); 20286909Simp unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 20386909Simp Scale = Scale.trunc(SmallWidth); 20486909Simp Offset = Offset.trunc(SmallWidth); 20586909Simp Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 20686909Simp 207120175Sbde Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 20886909Simp TD, Depth+1); 20986909Simp Scale = Scale.zext(OldWidth); 21086909Simp Offset = Offset.zext(OldWidth); 21186909Simp 21286909Simp return Result; 21386909Simp } 21486909Simp 21586909Simp Scale = 1; 21686909Simp Offset = 0; 21786909Simp return V; 21886909Simp} 21986909Simp 22086909Simp/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 22186909Simp/// into a base pointer with a constant offset and a number of scaled symbolic 22286909Simp/// offsets. 22386909Simp/// 22486909Simp/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 22586909Simp/// the VarIndices vector) are Value*'s that are known to be scaled by the 22686909Simp/// specified amount, but which may have other unrepresented high bits. As such, 22786909Simp/// the gep cannot necessarily be reconstructed from its decomposed form. 22886909Simp/// 22986909Simp/// When DataLayout is around, this function is capable of analyzing everything 23086909Simp/// that GetUnderlyingObject can look through. When not, it just looks 23186909Simp/// through pointer casts. 23286909Simp/// 23386909Simpstatic const Value * 23486909SimpDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 23586909Simp SmallVectorImpl<VariableGEPIndex> &VarIndices, 23686909Simp const DataLayout *TD) { 23786909Simp // Limit recursion depth to limit compile time in crazy cases. 23886909Simp unsigned MaxLookup = 6; 23986909Simp 24086909Simp BaseOffs = 0; 24186909Simp do { 24286909Simp // See if this is a bitcast or GEP. 24386909Simp const Operator *Op = dyn_cast<Operator>(V); 24486909Simp if (Op == 0) { 24586909Simp // The only non-operator case we can handle are GlobalAliases. 24686909Simp if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 24786909Simp if (!GA->mayBeOverridden()) { 24886909Simp V = GA->getAliasee(); 24986909Simp continue; 25086909Simp } 25186909Simp } 25286909Simp return V; 25386909Simp } 25486909Simp 25586909Simp if (Op->getOpcode() == Instruction::BitCast) { 25686909Simp V = Op->getOperand(0); 25786909Simp continue; 25886909Simp } 25986909Simp 26086909Simp const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 26186909Simp if (GEPOp == 0) { 262111613Sphk // If it's not a GEP, hand it off to SimplifyInstruction to see if it 263119485Snjl // can come up with something. This matches what GetUnderlyingObject does. 264119485Snjl if (const Instruction *I = dyn_cast<Instruction>(V)) 265119485Snjl // TODO: Get a DominatorTree and use it here. 26686909Simp if (const Value *Simplified = 26786909Simp SimplifyInstruction(const_cast<Instruction *>(I), TD)) { 26886909Simp V = Simplified; 26986909Simp continue; 27086909Simp } 27186909Simp 27289986Sjhay return V; 27389986Sjhay } 27486909Simp 27586909Simp // Don't attempt to analyze GEPs over unsized objects. 276116120Sscottl if (!cast<PointerType>(GEPOp->getOperand(0)->getType()) 277116120Sscottl ->getElementType()->isSized()) 278116120Sscottl return V; 27986909Simp 28086909Simp // If we are lacking DataLayout information, we can't compute the offets of 28186909Simp // elements computed by GEPs. However, we can handle bitcast equivalent 28286909Simp // GEPs. 28386909Simp if (TD == 0) { 28486909Simp if (!GEPOp->hasAllZeroIndices()) 28586909Simp return V; 28686909Simp V = GEPOp->getOperand(0); 28786909Simp continue; 28886909Simp } 28993010Sbde 29051078Speter // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 29151078Speter gep_type_iterator GTI = gep_type_begin(GEPOp); 29251078Speter for (User::const_op_iterator I = GEPOp->op_begin()+1, 29393010Sbde E = GEPOp->op_end(); I != E; ++I) { 29451078Speter Value *Index = *I; 29593010Sbde // Compute the (potentially symbolic) offset in bytes for this index. 29693010Sbde if (StructType *STy = dyn_cast<StructType>(*GTI++)) { 29793010Sbde // For a struct, add the member offset. 29893010Sbde unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 29993010Sbde if (FieldNo == 0) continue; 30093010Sbde 30193010Sbde BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 30293010Sbde continue; 30393010Sbde } 30493010Sbde 30593010Sbde // For an array/pointer, add the element offset, explicitly scaled. 30651078Speter if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 30793010Sbde if (CIdx->isZero()) continue; 30893010Sbde BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 30951078Speter continue; 31085365Simp } 31170174Sjhb 31270174Sjhb uint64_t Scale = TD->getTypeAllocSize(*GTI); 31351078Speter ExtensionKind Extension = EK_NotExtended; 31451078Speter 31585365Simp // If the integer type is smaller than the pointer size, it is implicitly 31651078Speter // sign extended to pointer size. 31786909Simp unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth(); 31851078Speter if (TD->getPointerSizeInBits() > Width) 31951078Speter Extension = EK_SignExt; 32051078Speter 32151078Speter // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 32251078Speter APInt IndexScale(Width, 0), IndexOffset(Width, 0); 32351078Speter Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 32451078Speter *TD, 0); 32551078Speter 32651078Speter // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 327111815Sphk // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 328111815Sphk BaseOffs += IndexOffset.getSExtValue()*Scale; 329111815Sphk Scale *= IndexScale.getSExtValue(); 330111815Sphk 331111815Sphk 332111815Sphk // If we already had an occurrence of this index variable, merge this 333111815Sphk // scale into it. For example, we want to handle: 334111815Sphk // A[x][x] -> x*16 + x*4 -> x*20 335111821Sphk // This also ensures that 'x' only appears in the index list once. 336111815Sphk for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 33751078Speter if (VarIndices[i].V == Index && 33851078Speter VarIndices[i].Extension == Extension) { 339114722Sobrien Scale += VarIndices[i].Scale; 34051078Speter VarIndices.erase(VarIndices.begin()+i); 34189986Sjhay break; 34289986Sjhay } 34398401Sn_hibma } 34498401Sn_hibma 34598401Sn_hibma // Make sure that we have a scale that makes sense for this target's 34651078Speter // pointer size. 34751078Speter if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) { 34898401Sn_hibma Scale <<= ShiftBits; 34951078Speter Scale = (int64_t)Scale >> ShiftBits; 35051078Speter } 35172238Sjhb 35272238Sjhb if (Scale) { 35351078Speter VariableGEPIndex Entry = {Index, Extension, 35451078Speter static_cast<int64_t>(Scale)}; 35551078Speter VarIndices.push_back(Entry); 35651078Speter } 35753344Speter } 35851078Speter 35951078Speter // Analyze the base pointer next. 36051078Speter V = GEPOp->getOperand(0); 36186909Simp } while (--MaxLookup); 36251078Speter 36351078Speter // If the chain of expressions is too deep, just return early. 36451078Speter return V; 36551078Speter} 36651078Speter 36751078Speter/// GetIndexDifference - Dest and Src are the variable indices from two 36851078Speter/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 36951078Speter/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 37051078Speter/// difference between the two pointers. 37151078Speterstatic void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 37251078Speter const SmallVectorImpl<VariableGEPIndex> &Src) { 37351078Speter if (Src.empty()) return; 37451078Speter 37551078Speter for (unsigned i = 0, e = Src.size(); i != e; ++i) { 37651078Speter const Value *V = Src[i].V; 37762573Sphk ExtensionKind Extension = Src[i].Extension; 37851078Speter int64_t Scale = Src[i].Scale; 37951078Speter 38051078Speter // Find V in Dest. This is N^2, but pointer indices almost never have more 38151078Speter // than a few variable indexes. 38251078Speter for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 38351078Speter if (Dest[j].V != V || Dest[j].Extension != Extension) continue; 38451078Speter 38551078Speter // If we found it, subtract off Scale V's from the entry in Dest. If it 38651078Speter // goes to zero, remove the entry. 38751078Speter if (Dest[j].Scale != Scale) 38851078Speter Dest[j].Scale -= Scale; 38951078Speter else 39051078Speter Dest.erase(Dest.begin()+j); 39151078Speter Scale = 0; 39251078Speter break; 39351078Speter } 39451078Speter 39551078Speter // If we didn't consume this entry, add it to the end of the Dest list. 39657915Simp if (Scale) { 39751078Speter VariableGEPIndex Entry = { V, Extension, -Scale }; 39851078Speter Dest.push_back(Entry); 39951078Speter } 40051078Speter } 40151078Speter} 40251078Speter 40351078Speter//===----------------------------------------------------------------------===// 40451078Speter// BasicAliasAnalysis Pass 40551078Speter//===----------------------------------------------------------------------===// 40651078Speter 40751078Speter#ifndef NDEBUG 40851078Speterstatic const Function *getParent(const Value *V) { 40951078Speter if (const Instruction *inst = dyn_cast<Instruction>(V)) 41051078Speter return inst->getParent()->getParent(); 41151078Speter 41251078Speter if (const Argument *arg = dyn_cast<Argument>(V)) 41351078Speter return arg->getParent(); 41451078Speter 41551078Speter return NULL; 41651078Speter} 41751078Speter 41851078Speterstatic bool notDifferentParent(const Value *O1, const Value *O2) { 41951078Speter 42051078Speter const Function *F1 = getParent(O1); 42151078Speter const Function *F2 = getParent(O2); 42251078Speter 42351078Speter return !F1 || !F2 || F1 == F2; 42451078Speter} 42591280Simp#endif 42651078Speter 42786909Simpnamespace { 42886909Simp /// BasicAliasAnalysis - This is the primary alias analysis implementation. 42986909Simp struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis { 43086909Simp static char ID; // Class identification, replacement for typeinfo 43186909Simp BasicAliasAnalysis() : ImmutablePass(ID) { 43286909Simp initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 43386909Simp } 43486909Simp 435104933Simp virtual void initializePass() { 43686909Simp InitializeAliasAnalysis(this); 43786909Simp } 43886909Simp 43986909Simp virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44085365Simp AU.addRequired<AliasAnalysis>(); 44185365Simp AU.addRequired<TargetLibraryInfo>(); 44252471Simp } 44351078Speter 44451078Speter virtual AliasResult alias(const Location &LocA, 44565131Sphk const Location &LocB) { 44651078Speter assert(AliasCache.empty() && "AliasCache must be cleared after use!"); 44752471Simp assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 44857915Simp "BasicAliasAnalysis doesn't support interprocedural queries."); 44952471Simp AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 45054386Simp LocB.Ptr, LocB.Size, LocB.TBAATag); 45151078Speter // AliasCache rarely has more than 1 or 2 elements, always use 452120175Sbde // shrink_and_clear so it quickly returns to the inline capacity of the 45365131Sphk // SmallDenseMap if it ever grows larger. 45465131Sphk // FIXME: This should really be shrink_to_inline_capacity_and_clear(). 45554386Simp AliasCache.shrink_and_clear(); 45654386Simp return Alias; 45754386Simp } 45854386Simp 45954386Simp virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 460116120Sscottl const Location &Loc); 461116120Sscottl 46251078Speter virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 46357915Simp ImmutableCallSite CS2) { 46477750Simp // The AliasAnalysis base class has some smarts, lets use them. 46551078Speter return AliasAnalysis::getModRefInfo(CS1, CS2); 46651078Speter } 46751078Speter 46851078Speter /// pointsToConstantMemory - Chase pointers until we find a (constant 46951078Speter /// global) or not. 47051078Speter virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); 47151078Speter 47286909Simp /// getModRefBehavior - Return the behavior when calling the given 47386909Simp /// call site. 47451078Speter virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 47553978Simp 47651078Speter /// getModRefBehavior - Return the behavior when calling the given function. 47751078Speter /// For use when the call site is not known. 47885365Simp virtual ModRefBehavior getModRefBehavior(const Function *F); 47989986Sjhay 48058885Simp /// getAdjustedAnalysisPointer - This method is used when a pass implements 48158885Simp /// an analysis interface through multiple inheritance. If needed, it 48289986Sjhay /// should override this to adjust the this pointer as needed for the 48385365Simp /// specified pass info. 48451078Speter virtual void *getAdjustedAnalysisPointer(const void *ID) { 48553344Speter if (ID == &AliasAnalysis::ID) 48651078Speter return (AliasAnalysis*)this; 48753344Speter return this; 48853344Speter } 48960471Snyan 49089986Sjhay private: 49151078Speter // AliasCache - Track alias queries to guard against recursion. 49251078Speter typedef std::pair<Location, Location> LocPair; 49351078Speter typedef SmallDenseMap<LocPair, AliasResult, 8> AliasCacheTy; 49451078Speter AliasCacheTy AliasCache; 49551078Speter 49651078Speter // Visited - Track instructions visited by pointsToConstantMemory. 49751078Speter SmallPtrSet<const Value*, 16> Visited; 49851078Speter 49954206Speter // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 50051088Speter // instruction against another. 50151078Speter AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size, 50251078Speter const MDNode *V1TBAAInfo, 50351078Speter const Value *V2, uint64_t V2Size, 50458885Simp const MDNode *V2TBAAInfo, 50551078Speter const Value *UnderlyingV1, const Value *UnderlyingV2); 50651078Speter 50751078Speter // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 50857915Simp // instruction against another. 50951078Speter AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize, 51086909Simp const MDNode *PNTBAAInfo, 51186909Simp const Value *V2, uint64_t V2Size, 51286909Simp const MDNode *V2TBAAInfo); 51386909Simp 51460471Snyan /// aliasSelect - Disambiguate a Select instruction against another value. 51560471Snyan AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize, 51689986Sjhay const MDNode *SITBAAInfo, 51789986Sjhay const Value *V2, uint64_t V2Size, 51889986Sjhay const MDNode *V2TBAAInfo); 51960471Snyan 52085209Sjhb AliasResult aliasCheck(const Value *V1, uint64_t V1Size, 52185209Sjhb const MDNode *V1TBAATag, 52293818Sjhb const Value *V2, uint64_t V2Size, 52393818Sjhb const MDNode *V2TBAATag); 52485209Sjhb }; 52585209Sjhb} // End of anonymous namespace 52685209Sjhb 52770174Sjhb// Register this pass... 52853344Speterchar BasicAliasAnalysis::ID = 0; 52953344SpeterINITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", 53053344Speter "Basic Alias Analysis (stateless AA impl)", 53153344Speter false, true, false) 53253344SpeterINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 53353344SpeterINITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", 53453344Speter "Basic Alias Analysis (stateless AA impl)", 53553344Speter false, true, false) 53651078Speter 53751078Speter 53851078SpeterImmutablePass *llvm::createBasicAliasAnalysisPass() { 53951078Speter return new BasicAliasAnalysis(); 54051078Speter} 54151078Speter 54251078Speter/// pointsToConstantMemory - Returns whether the given pointer value 54351078Speter/// points to memory that is local to the function, with global constants being 54453344Speter/// considered local to all functions. 54551078Speterbool 54651078SpeterBasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { 54751078Speter assert(Visited.empty() && "Visited must be cleared after use!"); 54851078Speter 54954194Speter unsigned MaxLookup = 8; 55054194Speter SmallVector<const Value *, 16> Worklist; 55154194Speter Worklist.push_back(Loc.Ptr); 55253344Speter do { 55351078Speter const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), TD); 55451078Speter if (!Visited.insert(V)) { 55551078Speter Visited.clear(); 55651078Speter return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 55753344Speter } 55851078Speter 55951078Speter // An alloca instruction defines local memory. 56051078Speter if (OrLocal && isa<AllocaInst>(V)) 56151078Speter continue; 56256788Sbde 56386909Simp // A global constant counts as local memory for our purposes. 56486909Simp if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 56551078Speter // Note: this doesn't require GV to be "ODR" because it isn't legal for a 56651078Speter // global to be marked constant in some modules and non-constant in 56751078Speter // others. GV may even be a declaration, not a definition. 56851078Speter if (!GV->isConstant()) { 56951078Speter Visited.clear(); 57051078Speter return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 57151078Speter } 57251078Speter continue; 57351078Speter } 57451078Speter 57551078Speter // If both select values point to local memory, then so does the select. 57651078Speter if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { 57751078Speter Worklist.push_back(SI->getTrueValue()); 57851078Speter Worklist.push_back(SI->getFalseValue()); 57957234Sbde continue; 58054206Speter } 58154206Speter 58254206Speter // If all values incoming to a phi node point to local memory, then so does 58351078Speter // the phi. 58451078Speter if (const PHINode *PN = dyn_cast<PHINode>(V)) { 58551078Speter // Don't bother inspecting phi nodes with many operands. 58651078Speter if (PN->getNumIncomingValues() > MaxLookup) { 58751078Speter Visited.clear(); 58851078Speter return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 58957234Sbde } 59057234Sbde for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 59157234Sbde Worklist.push_back(PN->getIncomingValue(i)); 59257234Sbde continue; 59357234Sbde } 59457234Sbde 59557234Sbde // Otherwise be conservative. 59657234Sbde Visited.clear(); 59757234Sbde return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); 59857234Sbde 59957234Sbde } while (!Worklist.empty() && --MaxLookup); 60051078Speter 60151078Speter Visited.clear(); 60251078Speter return Worklist.empty(); 60354194Speter} 60451078Speter 60551078Speter/// getModRefBehavior - Return the behavior when calling the given call site. 60651078SpeterAliasAnalysis::ModRefBehavior 60751078SpeterBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 60851078Speter if (CS.doesNotAccessMemory()) 60951078Speter // Can't do better than this. 61051078Speter return DoesNotAccessMemory; 61151078Speter 61251078Speter ModRefBehavior Min = UnknownModRefBehavior; 61351078Speter 61451078Speter // If the callsite knows it only reads memory, don't return worse 61572200Sbmilekic // than that. 61651078Speter if (CS.onlyReadsMemory()) 61751078Speter Min = OnlyReadsMemory; 61851078Speter 619112384Ssobomax // The AliasAnalysis base class has some smarts, lets use them. 620112384Ssobomax return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 621112270Ssobomax} 622112270Ssobomax 623112270Ssobomax/// getModRefBehavior - Return the behavior when calling the given function. 624112384Ssobomax/// For use when the call site is not known. 625112270SsobomaxAliasAnalysis::ModRefBehavior 626112384SsobomaxBasicAliasAnalysis::getModRefBehavior(const Function *F) { 627112384Ssobomax // If the function declares it doesn't access memory, we can't do better. 628112384Ssobomax if (F->doesNotAccessMemory()) 629112384Ssobomax return DoesNotAccessMemory; 630112384Ssobomax 631112384Ssobomax // For intrinsics, we can check the table. 632112384Ssobomax if (unsigned iid = F->getIntrinsicID()) { 633112384Ssobomax#define GET_INTRINSIC_MODREF_BEHAVIOR 634112384Ssobomax#include "llvm/Intrinsics.gen" 635112384Ssobomax#undef GET_INTRINSIC_MODREF_BEHAVIOR 636112384Ssobomax } 637112384Ssobomax 638112384Ssobomax ModRefBehavior Min = UnknownModRefBehavior; 639112270Ssobomax 640112384Ssobomax // If the function declares it only reads memory, go with that. 641112270Ssobomax if (F->onlyReadsMemory()) 64251078Speter Min = OnlyReadsMemory; 64351078Speter 64451078Speter // Otherwise be conservative. 64551078Speter return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 64651078Speter} 64751078Speter 64851078Speter/// getModRefInfo - Check to see if the specified callsite can clobber the 64951078Speter/// specified memory object. Since we only look at local properties of this 65051078Speter/// function, we really can't say much about this query. We do, however, use 65151078Speter/// simple "address taken" analysis on local objects. 65251078SpeterAliasAnalysis::ModRefResult 65351078SpeterBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 65460471Snyan const Location &Loc) { 65589986Sjhay assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 65689986Sjhay "AliasAnalysis query involving multiple functions!"); 65789986Sjhay 65860471Snyan const Value *Object = GetUnderlyingObject(Loc.Ptr, TD); 65951078Speter 66051078Speter // If this is a tail call and Loc.Ptr points to a stack location, we know that 66151078Speter // the tail call cannot access or modify the local stack. 66251078Speter // We cannot exclude byval arguments here; these belong to the caller of 66351078Speter // the current function not to the current function, and a tail callee 66451078Speter // may reference them. 66551078Speter if (isa<AllocaInst>(Object)) 66651078Speter if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 66751078Speter if (CI->isTailCall()) 66860471Snyan return NoModRef; 66960471Snyan 67051078Speter // If the pointer is to a locally allocated object that does not escape, 67151078Speter // then the call can not mod/ref the pointer unless the call takes the pointer 67251078Speter // as an argument, and itself doesn't capture it. 67351078Speter if (!isa<Constant>(Object) && CS.getInstruction() != Object && 67451078Speter isNonEscapingLocalObject(Object)) { 67551078Speter bool PassedAsArg = false; 67651078Speter unsigned ArgNo = 0; 67751078Speter for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 67860471Snyan CI != CE; ++CI, ++ArgNo) { 67951078Speter // Only look at the no-capture or byval pointer arguments. If this 68051078Speter // pointer were passed to arguments that were neither of these, then it 68151078Speter // couldn't be no-capture. 68251078Speter if (!(*CI)->getType()->isPointerTy() || 68351078Speter (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 68451078Speter continue; 68551078Speter 68651078Speter // If this is a no-capture pointer argument, see if we can tell that it 68751078Speter // is impossible to alias the pointer we're checking. If not, we have to 68860471Snyan // assume that the call could touch the pointer, even though it doesn't 68951078Speter // escape. 69051078Speter if (!isNoAlias(Location(*CI), Location(Object))) { 69151078Speter PassedAsArg = true; 69251078Speter break; 69351078Speter } 69451078Speter } 69551078Speter 69660471Snyan if (!PassedAsArg) 69751078Speter return NoModRef; 69851078Speter } 69951078Speter 70051078Speter const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfo>(); 70151078Speter ModRefResult Min = ModRef; 70251078Speter 70351078Speter // Finally, handle specific knowledge of intrinsics. 70451078Speter const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 70551078Speter if (II != 0) 70651078Speter switch (II->getIntrinsicID()) { 70760471Snyan default: break; 70892401Simp case Intrinsic::memcpy: 70992401Simp case Intrinsic::memmove: { 71092401Simp uint64_t Len = UnknownSize; 71192401Simp if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 71292401Simp Len = LenCI->getZExtValue(); 71392401Simp Value *Dest = II->getArgOperand(0); 71492401Simp Value *Src = II->getArgOperand(1); 71551078Speter // If it can't overlap the source dest, then it doesn't modref the loc. 71651078Speter if (isNoAlias(Location(Dest, Len), Loc)) { 71752471Simp if (isNoAlias(Location(Src, Len), Loc)) 71851078Speter return NoModRef; 71951078Speter // If it can't overlap the dest, then worst case it reads the loc. 72085365Simp Min = Ref; 72153370Speter } else if (isNoAlias(Location(Src, Len), Loc)) { 72253370Speter // If it can't overlap the source, then worst case it mutates the loc. 72353370Speter Min = Mod; 72460471Snyan } 72553370Speter break; 72653370Speter } 72753370Speter case Intrinsic::memset: 72853370Speter // Since memset is 'accesses arguments' only, the AliasAnalysis base class 72992401Simp // will handle it for the variable length case. 73060471Snyan if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 73160471Snyan uint64_t Len = LenCI->getZExtValue(); 73292401Simp Value *Dest = II->getArgOperand(0); 73353370Speter if (isNoAlias(Location(Dest, Len), Loc)) 73453370Speter return NoModRef; 73553370Speter } 73653370Speter // We know that memset doesn't load anything. 73781793Simp Min = Mod; 73853370Speter break; 73951078Speter case Intrinsic::lifetime_start: 74053370Speter case Intrinsic::lifetime_end: 74153370Speter case Intrinsic::invariant_start: { 74251078Speter uint64_t PtrSize = 74381793Simp cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 74460471Snyan if (isNoAlias(Location(II->getArgOperand(1), 74572200Sbmilekic PtrSize, 74653344Speter II->getMetadata(LLVMContext::MD_tbaa)), 74786909Simp Loc)) 74886909Simp return NoModRef; 74986909Simp break; 75086909Simp } 75186909Simp case Intrinsic::invariant_end: { 75286909Simp uint64_t PtrSize = 75386909Simp cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 75453344Speter if (isNoAlias(Location(II->getArgOperand(2), 75553344Speter PtrSize, 75651078Speter II->getMetadata(LLVMContext::MD_tbaa)), 75751078Speter Loc)) 75851078Speter return NoModRef; 75951078Speter break; 76051078Speter } 76151078Speter case Intrinsic::arm_neon_vld1: { 76251078Speter // LLVM's vld1 and vst1 intrinsics currently only support a single 76351078Speter // vector register. 76451078Speter uint64_t Size = 76560471Snyan TD ? TD->getTypeStoreSize(II->getType()) : UnknownSize; 76660471Snyan if (isNoAlias(Location(II->getArgOperand(0), Size, 767112270Ssobomax II->getMetadata(LLVMContext::MD_tbaa)), 76851078Speter Loc)) 76951078Speter return NoModRef; 77060471Snyan break; 77151078Speter } 77251078Speter case Intrinsic::arm_neon_vst1: { 77360471Snyan uint64_t Size = 77451078Speter TD ? TD->getTypeStoreSize(II->getArgOperand(1)->getType()) : UnknownSize; 77551078Speter if (isNoAlias(Location(II->getArgOperand(0), Size, 77651078Speter II->getMetadata(LLVMContext::MD_tbaa)), 77751078Speter Loc)) 77851078Speter return NoModRef; 77951078Speter break; 78051078Speter } 78151078Speter } 78251078Speter 78351078Speter // We can bound the aliasing properties of memset_pattern16 just as we can 78460471Snyan // for memcpy/memset. This is particularly important because the 78560471Snyan // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 78660471Snyan // whenever possible. 78751078Speter else if (TLI.has(LibFunc::memset_pattern16) && 78851078Speter CS.getCalledFunction() && 78960471Snyan CS.getCalledFunction()->getName() == "memset_pattern16") { 79051078Speter const Function *MS = CS.getCalledFunction(); 79172200Sbmilekic FunctionType *MemsetType = MS->getFunctionType(); 79251078Speter if (!MemsetType->isVarArg() && MemsetType->getNumParams() == 3 && 79351078Speter isa<PointerType>(MemsetType->getParamType(0)) && 79454194Speter isa<PointerType>(MemsetType->getParamType(1)) && 79589463Simp isa<IntegerType>(MemsetType->getParamType(2))) { 79651078Speter uint64_t Len = UnknownSize; 79754206Speter if (const ConstantInt *LenCI = dyn_cast<ConstantInt>(CS.getArgument(2))) 79853344Speter Len = LenCI->getZExtValue(); 79989447Sbmah const Value *Dest = CS.getArgument(0); 80089470Sbmah const Value *Src = CS.getArgument(1); 80189447Sbmah // If it can't overlap the source dest, then it doesn't modref the loc. 80289463Simp if (isNoAlias(Location(Dest, Len), Loc)) { 80351078Speter // Always reads 16 bytes of the source. 80451078Speter if (isNoAlias(Location(Src, 16), Loc)) 80551078Speter return NoModRef; 80651078Speter // If it can't overlap the dest, then worst case it reads the loc. 80751078Speter Min = Ref; 80851078Speter // Always reads 16 bytes of the source. 80951078Speter } else if (isNoAlias(Location(Src, 16), Loc)) { 81051078Speter // If it can't overlap the source, then worst case it mutates the loc. 81160471Snyan Min = Mod; 81251078Speter } 81351078Speter } 81451078Speter } 81551078Speter 81651078Speter // The AliasAnalysis base class has some smarts, lets use them. 81751078Speter return ModRefResult(AliasAnalysis::getModRefInfo(CS, Loc) & Min); 81851078Speter} 81951078Speter 82051078Speterstatic bool areVarIndicesEqual(SmallVector<VariableGEPIndex, 4> &Indices1, 82151078Speter SmallVector<VariableGEPIndex, 4> &Indices2) { 82251078Speter unsigned Size1 = Indices1.size(); 82351078Speter unsigned Size2 = Indices2.size(); 82486909Simp 82586909Simp if (Size1 != Size2) 82686909Simp return false; 82786909Simp 82886909Simp for (unsigned I = 0; I != Size1; ++I) 82986909Simp if (Indices1[I] != Indices2[I]) 83086909Simp return false; 83151078Speter 83251078Speter return true; 83351078Speter} 83451078Speter 83551078Speter/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 83651078Speter/// against another pointer. We know that V1 is a GEP, but we don't know 83751078Speter/// anything about V2. UnderlyingV1 is GetUnderlyingObject(GEP1, TD), 83851078Speter/// UnderlyingV2 is the same for V2. 83951078Speter/// 84051078SpeterAliasAnalysis::AliasResult 84151078SpeterBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, 84251078Speter const MDNode *V1TBAAInfo, 84351078Speter const Value *V2, uint64_t V2Size, 84451078Speter const MDNode *V2TBAAInfo, 84551078Speter const Value *UnderlyingV1, 84651078Speter const Value *UnderlyingV2) { 84751078Speter int64_t GEP1BaseOffset; 84851078Speter SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 84951078Speter 85051078Speter // If we have two gep instructions with must-alias or not-alias'ing base 85151078Speter // pointers, figure out if the indexes to the GEP tell us anything about the 85251078Speter // derived pointer. 85351078Speter if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 85451078Speter // Check for geps of non-aliasing underlying pointers where the offsets are 85551078Speter // identical. 85651078Speter if (V1Size == V2Size) { 85751078Speter // Do the base pointers alias assuming type and size. 85851078Speter AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, 85951078Speter V1TBAAInfo, UnderlyingV2, 86051078Speter V2Size, V2TBAAInfo); 86151078Speter if (PreciseBaseAlias == NoAlias) { 86251078Speter // See if the computed offset from the common pointer tells us about the 86360471Snyan // relation of the resulting pointer. 86451078Speter int64_t GEP2BaseOffset; 86551078Speter SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 86651078Speter const Value *GEP2BasePtr = 86751078Speter DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 86851078Speter const Value *GEP1BasePtr = 86951078Speter DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 87051078Speter // DecomposeGEPExpression and GetUnderlyingObject should return the 87151078Speter // same result except when DecomposeGEPExpression has no DataLayout. 87251078Speter if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 87351078Speter assert(TD == 0 && 87451078Speter "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 87551078Speter return MayAlias; 87651078Speter } 87751078Speter // Same offsets. 87851078Speter if (GEP1BaseOffset == GEP2BaseOffset && 87951078Speter areVarIndicesEqual(GEP1VariableIndices, GEP2VariableIndices)) 88051078Speter return NoAlias; 88151078Speter GEP1VariableIndices.clear(); 88251078Speter } 88351078Speter } 88451078Speter 88551078Speter // Do the base pointers alias? 88651078Speter AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 88751078Speter UnderlyingV2, UnknownSize, 0); 88851078Speter 88951078Speter // If we get a No or May, then return it immediately, no amount of analysis 89051078Speter // will improve this situation. 89151078Speter if (BaseAlias != MustAlias) return BaseAlias; 89251078Speter 89351078Speter // Otherwise, we have a MustAlias. Since the base pointers alias each other 89451078Speter // exactly, see if the computed offset from the common pointer tells us 89551078Speter // about the relation of the resulting pointer. 89651078Speter const Value *GEP1BasePtr = 89751078Speter DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 89885365Simp 89989986Sjhay int64_t GEP2BaseOffset; 90051078Speter SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 90158885Simp const Value *GEP2BasePtr = 90289986Sjhay DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 90351078Speter 90451078Speter // DecomposeGEPExpression and GetUnderlyingObject should return the 90551078Speter // same result except when DecomposeGEPExpression has no DataLayout. 90651078Speter if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 90751078Speter assert(TD == 0 && 90851078Speter "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 90993470Sbde return MayAlias; 91051078Speter } 91153344Speter 91251078Speter // Subtract the GEP2 pointer from the GEP1 pointer to find out their 91351078Speter // symbolic difference. 91453344Speter GEP1BaseOffset -= GEP2BaseOffset; 91551078Speter GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 91658885Simp 91751078Speter } else { 91851078Speter // Check to see if these two pointers are related by the getelementptr 91951078Speter // instruction. If one pointer is a GEP with a non-zero index of the other 92057915Simp // pointer, we know they cannot alias. 92151078Speter 92251078Speter // If both accesses are unknown size, we can't do anything useful here. 92351078Speter if (V1Size == UnknownSize && V2Size == UnknownSize) 92451078Speter return MayAlias; 92553344Speter 92651078Speter AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 92753344Speter V2, V2Size, V2TBAAInfo); 92853344Speter if (R != MustAlias) 92951078Speter // If V2 may alias GEP base pointer, conservatively returns MayAlias. 93051078Speter // If V2 is known not to alias GEP base pointer, then the two values 93151078Speter // cannot alias per GEP semantics: "A pointer value formed from a 93251078Speter // getelementptr instruction is associated with the addresses associated 93351078Speter // with the first operand of the getelementptr". 93451078Speter return R; 93551078Speter 93651078Speter const Value *GEP1BasePtr = 93751078Speter DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 93851078Speter 93951078Speter // DecomposeGEPExpression and GetUnderlyingObject should return the 94051078Speter // same result except when DecomposeGEPExpression has no DataLayout. 94151078Speter if (GEP1BasePtr != UnderlyingV1) { 94251078Speter assert(TD == 0 && 94351078Speter "DecomposeGEPExpression and GetUnderlyingObject disagree!"); 944116120Sscottl return MayAlias; 94560471Snyan } 94660471Snyan } 94751078Speter 94851078Speter // In the two GEP Case, if there is no difference in the offsets of the 94951078Speter // computed pointers, the resultant pointers are a must alias. This 95057234Sbde // hapens when we have two lexically identical GEP's (for example). 95151078Speter // 95251078Speter // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 95351078Speter // must aliases the GEP, the end result is a must alias also. 95451078Speter if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 95551078Speter return MustAlias; 95651078Speter 95751078Speter // If there is a constant difference between the pointers, but the difference 95851078Speter // is less than the size of the associated memory object, then we know 95951078Speter // that the objects are partially overlapping. If the difference is 96051078Speter // greater, we know they do not overlap. 96151078Speter if (GEP1BaseOffset != 0 && GEP1VariableIndices.empty()) { 96251078Speter if (GEP1BaseOffset >= 0) { 96389986Sjhay if (V2Size != UnknownSize) { 96489986Sjhay if ((uint64_t)GEP1BaseOffset < V2Size) 96589986Sjhay return PartialAlias; 96689986Sjhay return NoAlias; 96751078Speter } 96851078Speter } else { 96951078Speter if (V1Size != UnknownSize) { 97051078Speter if (-(uint64_t)GEP1BaseOffset < V1Size) 97151078Speter return PartialAlias; 97251078Speter return NoAlias; 97351078Speter } 97451078Speter } 97551078Speter } 97651078Speter 97751078Speter // Try to distinguish something like &A[i][1] against &A[42][0]. 97851078Speter // Grab the least significant bit set in any of the scales. 97951078Speter if (!GEP1VariableIndices.empty()) { 98051078Speter uint64_t Modulo = 0; 98151078Speter for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) 98251078Speter Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; 98351078Speter Modulo = Modulo ^ (Modulo & (Modulo - 1)); 98451078Speter 98551078Speter // We can compute the difference between the two addresses 98651078Speter // mod Modulo. Check whether that difference guarantees that the 98751078Speter // two locations do not alias. 98865605Sjhb uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1); 98972200Sbmilekic if (V1Size != UnknownSize && V2Size != UnknownSize && 99056788Sbde ModOffset >= V2Size && V1Size <= Modulo - ModOffset) 99156788Sbde return NoAlias; 99256788Sbde } 99356788Sbde 99456788Sbde // Statically, we can see that the base objects are the same, but the 99556788Sbde // pointers have dynamic offsets which we can't resolve. And none of our 99656788Sbde // little tricks above worked. 99751078Speter // 99872200Sbmilekic // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the 99951078Speter // practical effect of this is protecting TBAA in the case of dynamic 100051078Speter // indices into arrays of unions or malloc'd memory. 100151078Speter return PartialAlias; 100251078Speter} 100351078Speter 100451078Speterstatic AliasAnalysis::AliasResult 100551078SpeterMergeAliasResults(AliasAnalysis::AliasResult A, AliasAnalysis::AliasResult B) { 1006104067Sphk // If the results agree, take it. 1007104067Sphk if (A == B) 100851078Speter return A; 100951078Speter // A mix of PartialAlias and MustAlias is PartialAlias. 101051078Speter if ((A == AliasAnalysis::PartialAlias && B == AliasAnalysis::MustAlias) || 101151078Speter (B == AliasAnalysis::PartialAlias && A == AliasAnalysis::MustAlias)) 101260471Snyan return AliasAnalysis::PartialAlias; 101360471Snyan // Otherwise, we don't know anything. 101460471Snyan return AliasAnalysis::MayAlias; 101560471Snyan} 101660471Snyan 101760471Snyan/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 101851078Speter/// instruction against another. 101989447SbmahAliasAnalysis::AliasResult 102051078SpeterBasicAliasAnalysis::aliasSelect(const SelectInst *SI, uint64_t SISize, 102151078Speter const MDNode *SITBAAInfo, 102251078Speter const Value *V2, uint64_t V2Size, 102360471Snyan const MDNode *V2TBAAInfo) { 102451078Speter // If the values are Selects with the same condition, we can do a more precise 102551078Speter // check: just check for aliases between the values on corresponding arms. 102651078Speter if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 102751078Speter if (SI->getCondition() == SI2->getCondition()) { 102851078Speter AliasResult Alias = 102951078Speter aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 103051078Speter SI2->getTrueValue(), V2Size, V2TBAAInfo); 103151078Speter if (Alias == MayAlias) 103251078Speter return MayAlias; 103351078Speter AliasResult ThisAlias = 103451078Speter aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 103551078Speter SI2->getFalseValue(), V2Size, V2TBAAInfo); 103651078Speter return MergeAliasResults(ThisAlias, Alias); 103751078Speter } 1038120173Sbde 103951078Speter // If both arms of the Select node NoAlias or MustAlias V2, then returns 1040120173Sbde // NoAlias / MustAlias. Otherwise, returns MayAlias. 1041120173Sbde AliasResult Alias = 1042120173Sbde aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 1043120173Sbde if (Alias == MayAlias) 1044120173Sbde return MayAlias; 1045120173Sbde 1046120173Sbde AliasResult ThisAlias = 1047120173Sbde aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 1048120173Sbde return MergeAliasResults(ThisAlias, Alias); 1049120173Sbde} 1050120173Sbde 1051120173Sbde// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 1052120173Sbde// against another. 105351078SpeterAliasAnalysis::AliasResult 105451078SpeterBasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 105551078Speter const MDNode *PNTBAAInfo, 105651078Speter const Value *V2, uint64_t V2Size, 105751078Speter const MDNode *V2TBAAInfo) { 105851078Speter // If the values are PHIs in the same block, we can do a more precise 1059120173Sbde // as well as efficient check: just check for aliases between the values 1060120173Sbde // on corresponding edges. 106151078Speter if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 1062120173Sbde if (PN2->getParent() == PN->getParent()) { 1063120173Sbde LocPair Locs(Location(PN, PNSize, PNTBAAInfo), 1064120173Sbde Location(V2, V2Size, V2TBAAInfo)); 1065120173Sbde if (PN > V2) 1066120173Sbde std::swap(Locs.first, Locs.second); 1067120173Sbde 106851078Speter AliasResult Alias = 106951078Speter aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo, 107051078Speter PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 1071120173Sbde V2Size, V2TBAAInfo); 107251078Speter if (Alias == MayAlias) 107351078Speter return MayAlias; 107451078Speter 107551078Speter // If the first source of the PHI nodes NoAlias and the other inputs are 107651078Speter // the PHI node itself through some amount of recursion this does not add 107751078Speter // any new information so just return NoAlias. 107851078Speter // bb: 107951078Speter // ptr = ptr2 + 1 108051078Speter // loop: 108151078Speter // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] 108251078Speter // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] 108351078Speter // ... 108451078Speter // ptr_plus_one = gep ptr_phi, 1 108551078Speter // ptr2_plus_one = gep ptr2_phi, 1 108651078Speter // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do 108751078Speter // not alias each other. 108851078Speter bool ArePhisAssumedNoAlias = false; 108951078Speter AliasResult OrigAliasResult = NoAlias; 109051078Speter if (Alias == NoAlias) { 109151078Speter // Pretend the phis do not alias. 109251078Speter assert(AliasCache.count(Locs) && 109351078Speter "There must exist an entry for the phi node"); 109451078Speter OrigAliasResult = AliasCache[Locs]; 109560471Snyan AliasCache[Locs] = NoAlias; 109651078Speter ArePhisAssumedNoAlias = true; 109751078Speter } 109851078Speter 109951078Speter for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 110053344Speter AliasResult ThisAlias = 110153344Speter aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 110251078Speter PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 110351078Speter V2Size, V2TBAAInfo); 110451078Speter Alias = MergeAliasResults(ThisAlias, Alias); 110551078Speter if (Alias == MayAlias) 110651078Speter break; 110753344Speter } 110853344Speter 110957234Sbde // Reset if speculation failed. 111057234Sbde if (ArePhisAssumedNoAlias && Alias != NoAlias) 111151078Speter AliasCache[Locs] = OrigAliasResult; 111251078Speter 111351078Speter return Alias; 111451078Speter } 111553344Speter 111651078Speter SmallPtrSet<Value*, 4> UniqueSrc; 111751078Speter SmallVector<Value*, 4> V1Srcs; 111851078Speter for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 111967551Sjhb Value *PV1 = PN->getIncomingValue(i); 112072238Sjhb if (isa<PHINode>(PV1)) 112172238Sjhb // If any of the source itself is a PHI, return MayAlias conservatively 112272238Sjhb // to avoid compile time explosion. The worst possible case is if both 112372238Sjhb // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 112451078Speter // and 'n' are the number of PHI sources. 112593470Sbde return MayAlias; 112693470Sbde if (UniqueSrc.insert(PV1)) 112751078Speter V1Srcs.push_back(PV1); 112893470Sbde } 112951078Speter 113093470Sbde AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 113151078Speter V1Srcs[0], PNSize, PNTBAAInfo); 113293470Sbde // Early exit if the check of the first PHI source against V2 is MayAlias. 113351078Speter // Other results are not possible. 113465131Sphk if (Alias == MayAlias) 113593470Sbde return MayAlias; 113651078Speter 113765131Sphk // If all sources of the PHI node NoAlias or MustAlias V2, then returns 113893470Sbde // NoAlias / MustAlias. Otherwise, returns MayAlias. 113951078Speter for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 1140110249Sphk Value *V = V1Srcs[i]; 1141110249Sphk 114251078Speter AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 114351078Speter V, PNSize, PNTBAAInfo); 1144111613Sphk Alias = MergeAliasResults(ThisAlias, Alias); 1145111613Sphk if (Alias == MayAlias) 1146111613Sphk break; 1147111613Sphk } 1148111613Sphk 114951078Speter return Alias; 115051078Speter} 115151078Speter 115251078Speter// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 115353344Speter// such as array references. 115453344Speter// 115553344SpeterAliasAnalysis::AliasResult 115665557SjasoneBasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size, 115754386Simp const MDNode *V1TBAAInfo, 115854194Speter const Value *V2, uint64_t V2Size, 115954194Speter const MDNode *V2TBAAInfo) { 116054194Speter // If either of the memory references is empty, it doesn't matter what the 116154386Simp // pointer values are. 116254194Speter if (V1Size == 0 || V2Size == 0) 116383246Sdd return NoAlias; 116454194Speter 116553344Speter // Strip off any casts if they exist. 116653344Speter V1 = V1->stripPointerCasts(); 116778504Siedowse V2 = V2->stripPointerCasts(); 116878504Siedowse 116978504Siedowse // Are we checking for alias of the same value? 117078504Siedowse if (V1 == V2) return MustAlias; 117178504Siedowse 117278504Siedowse if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 117378504Siedowse return NoAlias; // Scalars cannot alias each other 117478504Siedowse 117578504Siedowse // Figure out what objects these things are pointing to if we can. 117678504Siedowse const Value *O1 = GetUnderlyingObject(V1, TD); 117753344Speter const Value *O2 = GetUnderlyingObject(V2, TD); 117851078Speter 117951078Speter // Null values in the default address space don't point to any object, so they 118051078Speter // don't alias any other pointer. 118151078Speter if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 118251078Speter if (CPN->getType()->getAddressSpace() == 0) 118383366Sjulian return NoAlias; 118451078Speter if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 118551078Speter if (CPN->getType()->getAddressSpace() == 0) 118651078Speter return NoAlias; 118783366Sjulian 118851078Speter if (O1 != O2) { 118951078Speter // If V1/V2 point to two different objects we know that we have no alias. 119051078Speter if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 119151078Speter return NoAlias; 119251078Speter 119351078Speter // Constant pointers can't alias with non-const isIdentifiedObject objects. 119451078Speter if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 119551078Speter (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 119651078Speter return NoAlias; 119751078Speter 119853344Speter // Arguments can't alias with local allocations or noalias calls 119953344Speter // in the same function. 120051078Speter if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 120151078Speter (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) 120251078Speter return NoAlias; 120351078Speter 120451078Speter // Most objects can't alias null. 120551078Speter if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 120651078Speter (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 120751078Speter return NoAlias; 120851078Speter 120951078Speter // If one pointer is the result of a call/invoke or load and the other is a 121051078Speter // non-escaping local object within the same function, then we know the 121151078Speter // object couldn't escape to a point where the call could return it. 121251078Speter // 121351078Speter // Note that if the pointers are in different functions, there are a 121451078Speter // variety of complications. A call with a nocapture argument may still 121551078Speter // temporary store the nocapture argument's value in a temporary memory 121651078Speter // location if that memory location doesn't escape. Or it may pass a 121751078Speter // nocapture value to other functions as long as they don't capture it. 121851078Speter if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 121951078Speter return NoAlias; 122051078Speter if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 122151078Speter return NoAlias; 122251078Speter } 122351078Speter 122451078Speter // If the size of one access is larger than the entire object on the other 122551078Speter // side, then we know such behavior is undefined and can assume no alias. 122651078Speter if (TD) 122751078Speter if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD, *TLI)) || 122851078Speter (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD, *TLI))) 122951078Speter return NoAlias; 123051078Speter 123151078Speter // Check the cache before climbing up use-def chains. This also terminates 123251078Speter // otherwise infinitely recursive queries. 123351078Speter LocPair Locs(Location(V1, V1Size, V1TBAAInfo), 123451078Speter Location(V2, V2Size, V2TBAAInfo)); 123551078Speter if (V1 > V2) 123651078Speter std::swap(Locs.first, Locs.second); 123751078Speter std::pair<AliasCacheTy::iterator, bool> Pair = 123851078Speter AliasCache.insert(std::make_pair(Locs, MayAlias)); 123951078Speter if (!Pair.second) 124051078Speter return Pair.first->second; 124151078Speter 124251078Speter // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 124351078Speter // GEP can't simplify, we don't even look at the PHI cases. 124451078Speter if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 124593593Sjhb std::swap(V1, V2); 124651078Speter std::swap(V1Size, V2Size); 124751078Speter std::swap(O1, O2); 124851078Speter std::swap(V1TBAAInfo, V2TBAAInfo); 124951078Speter } 125051078Speter if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 125151078Speter AliasResult Result = aliasGEP(GV1, V1Size, V1TBAAInfo, V2, V2Size, V2TBAAInfo, O1, O2); 125251078Speter if (Result != MayAlias) return AliasCache[Locs] = Result; 125351078Speter } 125451078Speter 125551078Speter if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 125651078Speter std::swap(V1, V2); 125751078Speter std::swap(V1Size, V2Size); 125851654Sphk std::swap(V1TBAAInfo, V2TBAAInfo); 125951078Speter } 126051078Speter if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 126151078Speter AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 126251078Speter V2, V2Size, V2TBAAInfo); 126351078Speter if (Result != MayAlias) return AliasCache[Locs] = Result; 126451078Speter } 126551078Speter 126651078Speter if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 126751078Speter std::swap(V1, V2); 126851078Speter std::swap(V1Size, V2Size); 126951078Speter std::swap(V1TBAAInfo, V2TBAAInfo); 127051078Speter } 127151078Speter if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 127251078Speter AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 127351078Speter V2, V2Size, V2TBAAInfo); 1274102542Sphk if (Result != MayAlias) return AliasCache[Locs] = Result; 127551078Speter } 127651078Speter 127751078Speter // If both pointers are pointing into the same object and one of them 127851078Speter // accesses is accessing the entire object, then the accesses must 127951078Speter // overlap in some way. 128051078Speter if (TD && O1 == O2) 128151078Speter if ((V1Size != UnknownSize && isObjectSize(O1, V1Size, *TD, *TLI)) || 128251078Speter (V2Size != UnknownSize && isObjectSize(O2, V2Size, *TD, *TLI))) 128351078Speter return AliasCache[Locs] = PartialAlias; 128451078Speter 128551078Speter AliasResult Result = 1286102542Sphk AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 128760471Snyan Location(V2, V2Size, V2TBAAInfo)); 128860471Snyan return AliasCache[Locs] = Result; 128960471Snyan} 129051078Speter