BasicAliasAnalysis.cpp revision 199989
1254885Sdumbbell//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2254885Sdumbbell// 3254885Sdumbbell// The LLVM Compiler Infrastructure 4254885Sdumbbell// 5254885Sdumbbell// This file is distributed under the University of Illinois Open Source 6254885Sdumbbell// License. See LICENSE.TXT for details. 7254885Sdumbbell// 8254885Sdumbbell//===----------------------------------------------------------------------===// 9254885Sdumbbell// 10254885Sdumbbell// This file defines the default implementation of the Alias Analysis interface 11254885Sdumbbell// that simply implements a few identities (two different globals cannot alias, 12254885Sdumbbell// etc), but otherwise does no analysis. 13254885Sdumbbell// 14254885Sdumbbell//===----------------------------------------------------------------------===// 15254885Sdumbbell 16254885Sdumbbell#include "llvm/Analysis/AliasAnalysis.h" 17254885Sdumbbell#include "llvm/Analysis/Passes.h" 18254885Sdumbbell#include "llvm/Constants.h" 19254885Sdumbbell#include "llvm/DerivedTypes.h" 20254885Sdumbbell#include "llvm/Function.h" 21254885Sdumbbell#include "llvm/GlobalVariable.h" 22254885Sdumbbell#include "llvm/Instructions.h" 23254885Sdumbbell#include "llvm/IntrinsicInst.h" 24254885Sdumbbell#include "llvm/Operator.h" 25254885Sdumbbell#include "llvm/Pass.h" 26254885Sdumbbell#include "llvm/Analysis/CaptureTracking.h" 27254885Sdumbbell#include "llvm/Analysis/MemoryBuiltins.h" 28254885Sdumbbell#include "llvm/Analysis/ValueTracking.h" 29254885Sdumbbell#include "llvm/Target/TargetData.h" 30254885Sdumbbell#include "llvm/ADT/SmallPtrSet.h" 31254885Sdumbbell#include "llvm/ADT/SmallVector.h" 32254885Sdumbbell#include "llvm/Support/ErrorHandling.h" 33254885Sdumbbell#include <algorithm> 34254885Sdumbbellusing namespace llvm; 35254885Sdumbbell 36254885Sdumbbell//===----------------------------------------------------------------------===// 37254885Sdumbbell// Useful predicates 38254885Sdumbbell//===----------------------------------------------------------------------===// 39254885Sdumbbell 40254885Sdumbbell/// isKnownNonNull - Return true if we know that the specified value is never 41254885Sdumbbell/// null. 42254885Sdumbbellstatic bool isKnownNonNull(const Value *V) { 43254885Sdumbbell // Alloca never returns null, malloc might. 44254885Sdumbbell if (isa<AllocaInst>(V)) return true; 45254885Sdumbbell 46254885Sdumbbell // A byval argument is never null. 47254885Sdumbbell if (const Argument *A = dyn_cast<Argument>(V)) 48254885Sdumbbell return A->hasByValAttr(); 49254885Sdumbbell 50254885Sdumbbell // Global values are not null unless extern weak. 51254885Sdumbbell if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 52254885Sdumbbell return !GV->hasExternalWeakLinkage(); 53254885Sdumbbell return false; 54254885Sdumbbell} 55254885Sdumbbell 56254885Sdumbbell/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 57254885Sdumbbell/// object that never escapes from the function. 58254885Sdumbbellstatic bool isNonEscapingLocalObject(const Value *V) { 59254885Sdumbbell // If this is a local allocation, check to see if it escapes. 60254885Sdumbbell if (isa<AllocaInst>(V) || isNoAliasCall(V)) 61254885Sdumbbell // Set StoreCaptures to True so that we can assume in our callers that the 62254885Sdumbbell // pointer is not the result of a load instruction. Currently 63254885Sdumbbell // PointerMayBeCaptured doesn't have any special analysis for the 64254885Sdumbbell // StoreCaptures=false case; if it did, our callers could be refined to be 65254885Sdumbbell // more precise. 66254885Sdumbbell return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 67254885Sdumbbell 68254885Sdumbbell // If this is an argument that corresponds to a byval or noalias argument, 69254885Sdumbbell // then it has not escaped before entering the function. Check if it escapes 70254885Sdumbbell // inside the function. 71254885Sdumbbell if (const Argument *A = dyn_cast<Argument>(V)) 72254885Sdumbbell if (A->hasByValAttr() || A->hasNoAliasAttr()) { 73254885Sdumbbell // Don't bother analyzing arguments already known not to escape. 74254885Sdumbbell if (A->hasNoCaptureAttr()) 75254885Sdumbbell return true; 76254885Sdumbbell return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 77254885Sdumbbell } 78254885Sdumbbell return false; 79254885Sdumbbell} 80254885Sdumbbell 81254885Sdumbbell 82254885Sdumbbell/// isObjectSmallerThan - Return true if we can prove that the object specified 83254885Sdumbbell/// by V is smaller than Size. 84254885Sdumbbellstatic bool isObjectSmallerThan(const Value *V, unsigned Size, 85254885Sdumbbell const TargetData &TD) { 86254885Sdumbbell const Type *AccessTy; 87254885Sdumbbell if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 88254885Sdumbbell AccessTy = GV->getType()->getElementType(); 89254885Sdumbbell } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 90254885Sdumbbell if (!AI->isArrayAllocation()) 91254885Sdumbbell AccessTy = AI->getType()->getElementType(); 92254885Sdumbbell else 93254885Sdumbbell return false; 94254885Sdumbbell } else if (const CallInst* CI = extractMallocCall(V)) { 95254885Sdumbbell if (!isArrayMalloc(V, &TD)) 96254885Sdumbbell // The size is the argument to the malloc call. 97254885Sdumbbell if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getOperand(1))) 98254885Sdumbbell return (C->getZExtValue() < Size); 99254885Sdumbbell return false; 100254885Sdumbbell } else if (const Argument *A = dyn_cast<Argument>(V)) { 101254885Sdumbbell if (A->hasByValAttr()) 102254885Sdumbbell AccessTy = cast<PointerType>(A->getType())->getElementType(); 103254885Sdumbbell else 104254885Sdumbbell return false; 105254885Sdumbbell } else { 106254885Sdumbbell return false; 107254885Sdumbbell } 108254885Sdumbbell 109254885Sdumbbell if (AccessTy->isSized()) 110254885Sdumbbell return TD.getTypeAllocSize(AccessTy) < Size; 111254885Sdumbbell return false; 112254885Sdumbbell} 113254885Sdumbbell 114254885Sdumbbell//===----------------------------------------------------------------------===// 115254885Sdumbbell// NoAA Pass 116254885Sdumbbell//===----------------------------------------------------------------------===// 117254885Sdumbbell 118254885Sdumbbellnamespace { 119254885Sdumbbell /// NoAA - This class implements the -no-aa pass, which always returns "I 120254885Sdumbbell /// don't know" for alias queries. NoAA is unlike other alias analysis 121254885Sdumbbell /// implementations, in that it does not chain to a previous analysis. As 122254885Sdumbbell /// such it doesn't follow many of the rules that other alias analyses must. 123254885Sdumbbell /// 124254885Sdumbbell struct NoAA : public ImmutablePass, public AliasAnalysis { 125254885Sdumbbell static char ID; // Class identification, replacement for typeinfo 126254885Sdumbbell NoAA() : ImmutablePass(&ID) {} 127254885Sdumbbell explicit NoAA(void *PID) : ImmutablePass(PID) { } 128254885Sdumbbell 129254885Sdumbbell virtual void getAnalysisUsage(AnalysisUsage &AU) const { 130254885Sdumbbell } 131254885Sdumbbell 132254885Sdumbbell virtual void initializePass() { 133254885Sdumbbell TD = getAnalysisIfAvailable<TargetData>(); 134254885Sdumbbell } 135254885Sdumbbell 136254885Sdumbbell virtual AliasResult alias(const Value *V1, unsigned V1Size, 137254885Sdumbbell const Value *V2, unsigned V2Size) { 138254885Sdumbbell return MayAlias; 139254885Sdumbbell } 140254885Sdumbbell 141254885Sdumbbell virtual void getArgumentAccesses(Function *F, CallSite CS, 142254885Sdumbbell std::vector<PointerAccessInfo> &Info) { 143254885Sdumbbell llvm_unreachable("This method may not be called on this function!"); 144254885Sdumbbell } 145254885Sdumbbell 146254885Sdumbbell virtual bool pointsToConstantMemory(const Value *P) { return false; } 147254885Sdumbbell virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 148254885Sdumbbell return ModRef; 149254885Sdumbbell } 150254885Sdumbbell virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 151254885Sdumbbell return ModRef; 152254885Sdumbbell } 153254885Sdumbbell 154254885Sdumbbell virtual void deleteValue(Value *V) {} 155254885Sdumbbell virtual void copyValue(Value *From, Value *To) {} 156254885Sdumbbell }; 157254885Sdumbbell} // End of anonymous namespace 158254885Sdumbbell 159254885Sdumbbell// Register this pass... 160254885Sdumbbellchar NoAA::ID = 0; 161254885Sdumbbellstatic RegisterPass<NoAA> 162254885SdumbbellU("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 163254885Sdumbbell 164254885Sdumbbell// Declare that we implement the AliasAnalysis interface 165254885Sdumbbellstatic RegisterAnalysisGroup<AliasAnalysis> V(U); 166254885Sdumbbell 167254885SdumbbellImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 168254885Sdumbbell 169254885Sdumbbell//===----------------------------------------------------------------------===// 170254885Sdumbbell// BasicAA Pass 171254885Sdumbbell//===----------------------------------------------------------------------===// 172254885Sdumbbell 173254885Sdumbbellnamespace { 174254885Sdumbbell /// BasicAliasAnalysis - This is the default alias analysis implementation. 175254885Sdumbbell /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 176254885Sdumbbell /// derives from the NoAA class. 177254885Sdumbbell struct BasicAliasAnalysis : public NoAA { 178254885Sdumbbell static char ID; // Class identification, replacement for typeinfo 179254885Sdumbbell BasicAliasAnalysis() : NoAA(&ID) {} 180254885Sdumbbell AliasResult alias(const Value *V1, unsigned V1Size, 181254885Sdumbbell const Value *V2, unsigned V2Size) { 182254885Sdumbbell assert(VisitedPHIs.empty() && "VisitedPHIs must be cleared after use!"); 183254885Sdumbbell AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size); 184254885Sdumbbell VisitedPHIs.clear(); 185254885Sdumbbell return Alias; 186254885Sdumbbell } 187254885Sdumbbell 188254885Sdumbbell ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 189254885Sdumbbell ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); 190254885Sdumbbell 191254885Sdumbbell /// pointsToConstantMemory - Chase pointers until we find a (constant 192254885Sdumbbell /// global) or not. 193254885Sdumbbell bool pointsToConstantMemory(const Value *P); 194254885Sdumbbell 195254885Sdumbbell private: 196254885Sdumbbell // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call. 197254885Sdumbbell SmallPtrSet<const Value*, 16> VisitedPHIs; 198254885Sdumbbell 199254885Sdumbbell // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 200254885Sdumbbell // instruction against another. 201254885Sdumbbell AliasResult aliasGEP(const GEPOperator *V1, unsigned V1Size, 202254885Sdumbbell const Value *V2, unsigned V2Size, 203254885Sdumbbell const Value *UnderlyingV1, const Value *UnderlyingV2); 204254885Sdumbbell 205254885Sdumbbell // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 206254885Sdumbbell // instruction against another. 207254885Sdumbbell AliasResult aliasPHI(const PHINode *PN, unsigned PNSize, 208254885Sdumbbell const Value *V2, unsigned V2Size); 209254885Sdumbbell 210254885Sdumbbell /// aliasSelect - Disambiguate a Select instruction against another value. 211254885Sdumbbell AliasResult aliasSelect(const SelectInst *SI, unsigned SISize, 212254885Sdumbbell const Value *V2, unsigned V2Size); 213254885Sdumbbell 214254885Sdumbbell AliasResult aliasCheck(const Value *V1, unsigned V1Size, 215254885Sdumbbell const Value *V2, unsigned V2Size); 216254885Sdumbbell }; 217254885Sdumbbell} // End of anonymous namespace 218254885Sdumbbell 219254885Sdumbbell// Register this pass... 220254885Sdumbbellchar BasicAliasAnalysis::ID = 0; 221254885Sdumbbellstatic RegisterPass<BasicAliasAnalysis> 222254885SdumbbellX("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 223254885Sdumbbell 224254885Sdumbbell// Declare that we implement the AliasAnalysis interface 225254885Sdumbbellstatic RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 226254885Sdumbbell 227254885SdumbbellImmutablePass *llvm::createBasicAliasAnalysisPass() { 228254885Sdumbbell return new BasicAliasAnalysis(); 229254885Sdumbbell} 230254885Sdumbbell 231254885Sdumbbell 232254885Sdumbbell/// pointsToConstantMemory - Chase pointers until we find a (constant 233254885Sdumbbell/// global) or not. 234254885Sdumbbellbool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 235254885Sdumbbell if (const GlobalVariable *GV = 236254885Sdumbbell dyn_cast<GlobalVariable>(P->getUnderlyingObject())) 237254885Sdumbbell // Note: this doesn't require GV to be "ODR" because it isn't legal for a 238254885Sdumbbell // global to be marked constant in some modules and non-constant in others. 239254885Sdumbbell // GV may even be a declaration, not a definition. 240254885Sdumbbell return GV->isConstant(); 241254885Sdumbbell return false; 242254885Sdumbbell} 243254885Sdumbbell 244254885Sdumbbell 245254885Sdumbbell/// getModRefInfo - Check to see if the specified callsite can clobber the 246254885Sdumbbell/// specified memory object. Since we only look at local properties of this 247254885Sdumbbell/// function, we really can't say much about this query. We do, however, use 248254885Sdumbbell/// simple "address taken" analysis on local objects. 249254885SdumbbellAliasAnalysis::ModRefResult 250254885SdumbbellBasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 251254885Sdumbbell const Value *Object = P->getUnderlyingObject(); 252254885Sdumbbell 253254885Sdumbbell // If this is a tail call and P points to a stack location, we know that 254254885Sdumbbell // the tail call cannot access or modify the local stack. 255254885Sdumbbell // We cannot exclude byval arguments here; these belong to the caller of 256254885Sdumbbell // the current function not to the current function, and a tail callee 257254885Sdumbbell // may reference them. 258254885Sdumbbell if (isa<AllocaInst>(Object)) 259254885Sdumbbell if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 260254885Sdumbbell if (CI->isTailCall()) 261254885Sdumbbell return NoModRef; 262254885Sdumbbell 263254885Sdumbbell // If the pointer is to a locally allocated object that does not escape, 264254885Sdumbbell // then the call can not mod/ref the pointer unless the call takes the pointer 265254885Sdumbbell // as an argument, and itself doesn't capture it. 266254885Sdumbbell if (!isa<Constant>(Object) && CS.getInstruction() != Object && 267254885Sdumbbell isNonEscapingLocalObject(Object)) { 268254885Sdumbbell bool PassedAsArg = false; 269254885Sdumbbell unsigned ArgNo = 0; 270254885Sdumbbell for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 271254885Sdumbbell CI != CE; ++CI, ++ArgNo) { 272254885Sdumbbell // Only look at the no-capture pointer arguments. 273254885Sdumbbell if (!isa<PointerType>((*CI)->getType()) || 274254885Sdumbbell !CS.paramHasAttr(ArgNo+1, Attribute::NoCapture)) 275254885Sdumbbell continue; 276254885Sdumbbell 277254885Sdumbbell // If this is a no-capture pointer argument, see if we can tell that it 278254885Sdumbbell // is impossible to alias the pointer we're checking. If not, we have to 279254885Sdumbbell // assume that the call could touch the pointer, even though it doesn't 280254885Sdumbbell // escape. 281254885Sdumbbell if (!isNoAlias(cast<Value>(CI), ~0U, P, ~0U)) { 282254885Sdumbbell PassedAsArg = true; 283254885Sdumbbell break; 284254885Sdumbbell } 285254885Sdumbbell } 286254885Sdumbbell 287254885Sdumbbell if (!PassedAsArg) 288254885Sdumbbell return NoModRef; 289254885Sdumbbell } 290254885Sdumbbell 291254885Sdumbbell // Finally, handle specific knowledge of intrinsics. 292254885Sdumbbell IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 293254885Sdumbbell if (II == 0) 294254885Sdumbbell return AliasAnalysis::getModRefInfo(CS, P, Size); 295254885Sdumbbell 296254885Sdumbbell switch (II->getIntrinsicID()) { 297254885Sdumbbell default: break; 298254885Sdumbbell case Intrinsic::memcpy: 299254885Sdumbbell case Intrinsic::memmove: { 300254885Sdumbbell unsigned Len = ~0U; 301254885Sdumbbell if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) 302254885Sdumbbell Len = LenCI->getZExtValue(); 303254885Sdumbbell Value *Dest = II->getOperand(1); 304254885Sdumbbell Value *Src = II->getOperand(2); 305254885Sdumbbell if (isNoAlias(Dest, Len, P, Size)) { 306254885Sdumbbell if (isNoAlias(Src, Len, P, Size)) 307254885Sdumbbell return NoModRef; 308254885Sdumbbell return Ref; 309254885Sdumbbell } 310254885Sdumbbell break; 311254885Sdumbbell } 312254885Sdumbbell case Intrinsic::memset: 313254885Sdumbbell // Since memset is 'accesses arguments' only, the AliasAnalysis base class 314254885Sdumbbell // will handle it for the variable length case. 315254885Sdumbbell if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) { 316254885Sdumbbell unsigned Len = LenCI->getZExtValue(); 317254885Sdumbbell Value *Dest = II->getOperand(1); 318254885Sdumbbell if (isNoAlias(Dest, Len, P, Size)) 319254885Sdumbbell return NoModRef; 320254885Sdumbbell } 321254885Sdumbbell break; 322254885Sdumbbell case Intrinsic::atomic_cmp_swap: 323254885Sdumbbell case Intrinsic::atomic_swap: 324254885Sdumbbell case Intrinsic::atomic_load_add: 325254885Sdumbbell case Intrinsic::atomic_load_sub: 326254885Sdumbbell case Intrinsic::atomic_load_and: 327254885Sdumbbell case Intrinsic::atomic_load_nand: 328254885Sdumbbell case Intrinsic::atomic_load_or: 329254885Sdumbbell case Intrinsic::atomic_load_xor: 330254885Sdumbbell case Intrinsic::atomic_load_max: 331254885Sdumbbell case Intrinsic::atomic_load_min: 332254885Sdumbbell case Intrinsic::atomic_load_umax: 333254885Sdumbbell case Intrinsic::atomic_load_umin: 334254885Sdumbbell if (TD) { 335254885Sdumbbell Value *Op1 = II->getOperand(1); 336254885Sdumbbell unsigned Op1Size = TD->getTypeStoreSize(Op1->getType()); 337254885Sdumbbell if (isNoAlias(Op1, Op1Size, P, Size)) 338254885Sdumbbell return NoModRef; 339254885Sdumbbell } 340254885Sdumbbell break; 341254885Sdumbbell case Intrinsic::lifetime_start: 342254885Sdumbbell case Intrinsic::lifetime_end: 343254885Sdumbbell case Intrinsic::invariant_start: { 344254885Sdumbbell unsigned PtrSize = cast<ConstantInt>(II->getOperand(1))->getZExtValue(); 345254885Sdumbbell if (isNoAlias(II->getOperand(2), PtrSize, P, Size)) 346254885Sdumbbell return NoModRef; 347254885Sdumbbell break; 348254885Sdumbbell } 349254885Sdumbbell case Intrinsic::invariant_end: { 350254885Sdumbbell unsigned PtrSize = cast<ConstantInt>(II->getOperand(2))->getZExtValue(); 351254885Sdumbbell if (isNoAlias(II->getOperand(3), PtrSize, P, Size)) 352254885Sdumbbell return NoModRef; 353254885Sdumbbell break; 354254885Sdumbbell } 355254885Sdumbbell } 356254885Sdumbbell 357254885Sdumbbell // The AliasAnalysis base class has some smarts, lets use them. 358254885Sdumbbell return AliasAnalysis::getModRefInfo(CS, P, Size); 359254885Sdumbbell} 360254885Sdumbbell 361254885Sdumbbell 362254885SdumbbellAliasAnalysis::ModRefResult 363254885SdumbbellBasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 364254885Sdumbbell // If CS1 or CS2 are readnone, they don't interact. 365254885Sdumbbell ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); 366254885Sdumbbell if (CS1B == DoesNotAccessMemory) return NoModRef; 367254885Sdumbbell 368254885Sdumbbell ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); 369254885Sdumbbell if (CS2B == DoesNotAccessMemory) return NoModRef; 370254885Sdumbbell 371254885Sdumbbell // If they both only read from memory, just return ref. 372254885Sdumbbell if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 373254885Sdumbbell return Ref; 374254885Sdumbbell 375254885Sdumbbell // Otherwise, fall back to NoAA (mod+ref). 376254885Sdumbbell return NoAA::getModRefInfo(CS1, CS2); 377254885Sdumbbell} 378254885Sdumbbell 379254885Sdumbbell/// GetIndiceDifference - Dest and Src are the variable indices from two 380254885Sdumbbell/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 381254885Sdumbbell/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 382254885Sdumbbell/// difference between the two pointers. 383254885Sdumbbellstatic void GetIndiceDifference( 384254885Sdumbbell SmallVectorImpl<std::pair<const Value*, int64_t> > &Dest, 385254885Sdumbbell const SmallVectorImpl<std::pair<const Value*, int64_t> > &Src) { 386254885Sdumbbell if (Src.empty()) return; 387254885Sdumbbell 388254885Sdumbbell for (unsigned i = 0, e = Src.size(); i != e; ++i) { 389254885Sdumbbell const Value *V = Src[i].first; 390254885Sdumbbell int64_t Scale = Src[i].second; 391254885Sdumbbell 392254885Sdumbbell // Find V in Dest. This is N^2, but pointer indices almost never have more 393254885Sdumbbell // than a few variable indexes. 394254885Sdumbbell for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 395254885Sdumbbell if (Dest[j].first != V) continue; 396254885Sdumbbell 397254885Sdumbbell // If we found it, subtract off Scale V's from the entry in Dest. If it 398254885Sdumbbell // goes to zero, remove the entry. 399254885Sdumbbell if (Dest[j].second != Scale) 400254885Sdumbbell Dest[j].second -= Scale; 401254885Sdumbbell else 402254885Sdumbbell Dest.erase(Dest.begin()+j); 403254885Sdumbbell Scale = 0; 404254885Sdumbbell break; 405254885Sdumbbell } 406254885Sdumbbell 407254885Sdumbbell // If we didn't consume this entry, add it to the end of the Dest list. 408254885Sdumbbell if (Scale) 409254885Sdumbbell Dest.push_back(std::make_pair(V, -Scale)); 410254885Sdumbbell } 411254885Sdumbbell} 412254885Sdumbbell 413254885Sdumbbell/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 414254885Sdumbbell/// against another pointer. We know that V1 is a GEP, but we don't know 415254885Sdumbbell/// anything about V2. UnderlyingV1 is GEP1->getUnderlyingObject(), 416254885Sdumbbell/// UnderlyingV2 is the same for V2. 417254885Sdumbbell/// 418254885SdumbbellAliasAnalysis::AliasResult 419254885SdumbbellBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, 420254885Sdumbbell const Value *V2, unsigned V2Size, 421254885Sdumbbell const Value *UnderlyingV1, 422254885Sdumbbell const Value *UnderlyingV2) { 423254885Sdumbbell int64_t GEP1BaseOffset; 424254885Sdumbbell SmallVector<std::pair<const Value*, int64_t>, 4> GEP1VariableIndices; 425254885Sdumbbell 426254885Sdumbbell // If we have two gep instructions with must-alias'ing base pointers, figure 427254885Sdumbbell // out if the indexes to the GEP tell us anything about the derived pointer. 428254885Sdumbbell if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 429254885Sdumbbell // Do the base pointers alias? 430254885Sdumbbell AliasResult BaseAlias = aliasCheck(UnderlyingV1, ~0U, UnderlyingV2, ~0U); 431254885Sdumbbell 432254885Sdumbbell // If we get a No or May, then return it immediately, no amount of analysis 433254885Sdumbbell // will improve this situation. 434254885Sdumbbell if (BaseAlias != MustAlias) return BaseAlias; 435254885Sdumbbell 436254885Sdumbbell // Otherwise, we have a MustAlias. Since the base pointers alias each other 437254885Sdumbbell // exactly, see if the computed offset from the common pointer tells us 438254885Sdumbbell // about the relation of the resulting pointer. 439254885Sdumbbell const Value *GEP1BasePtr = 440254885Sdumbbell DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 441254885Sdumbbell 442254885Sdumbbell int64_t GEP2BaseOffset; 443254885Sdumbbell SmallVector<std::pair<const Value*, int64_t>, 4> GEP2VariableIndices; 444254885Sdumbbell const Value *GEP2BasePtr = 445254885Sdumbbell DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 446254885Sdumbbell 447254885Sdumbbell // If DecomposeGEPExpression isn't able to look all the way through the 448254885Sdumbbell // addressing operation, we must not have TD and this is too complex for us 449254885Sdumbbell // to handle without it. 450254885Sdumbbell if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 451254885Sdumbbell assert(TD == 0 && 452254885Sdumbbell "DecomposeGEPExpression and getUnderlyingObject disagree!"); 453254885Sdumbbell return MayAlias; 454254885Sdumbbell } 455254885Sdumbbell 456254885Sdumbbell // Subtract the GEP2 pointer from the GEP1 pointer to find out their 457254885Sdumbbell // symbolic difference. 458254885Sdumbbell GEP1BaseOffset -= GEP2BaseOffset; 459254885Sdumbbell GetIndiceDifference(GEP1VariableIndices, GEP2VariableIndices); 460254885Sdumbbell 461254885Sdumbbell } else { 462254885Sdumbbell // Check to see if these two pointers are related by the getelementptr 463254885Sdumbbell // instruction. If one pointer is a GEP with a non-zero index of the other 464254885Sdumbbell // pointer, we know they cannot alias. 465254885Sdumbbell 466254885Sdumbbell // If both accesses are unknown size, we can't do anything useful here. 467254885Sdumbbell if (V1Size == ~0U && V2Size == ~0U) 468254885Sdumbbell return MayAlias; 469254885Sdumbbell 470254885Sdumbbell AliasResult R = aliasCheck(UnderlyingV1, ~0U, V2, V2Size); 471254885Sdumbbell if (R != MustAlias) 472254885Sdumbbell // If V2 may alias GEP base pointer, conservatively returns MayAlias. 473254885Sdumbbell // If V2 is known not to alias GEP base pointer, then the two values 474254885Sdumbbell // cannot alias per GEP semantics: "A pointer value formed from a 475254885Sdumbbell // getelementptr instruction is associated with the addresses associated 476254885Sdumbbell // with the first operand of the getelementptr". 477254885Sdumbbell return R; 478254885Sdumbbell 479254885Sdumbbell const Value *GEP1BasePtr = 480254885Sdumbbell DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 481254885Sdumbbell 482254885Sdumbbell // If DecomposeGEPExpression isn't able to look all the way through the 483254885Sdumbbell // addressing operation, we must not have TD and this is too complex for us 484254885Sdumbbell // to handle without it. 485254885Sdumbbell if (GEP1BasePtr != UnderlyingV1) { 486254885Sdumbbell assert(TD == 0 && 487254885Sdumbbell "DecomposeGEPExpression and getUnderlyingObject disagree!"); 488254885Sdumbbell return MayAlias; 489254885Sdumbbell } 490254885Sdumbbell } 491254885Sdumbbell 492254885Sdumbbell // In the two GEP Case, if there is no difference in the offsets of the 493254885Sdumbbell // computed pointers, the resultant pointers are a must alias. This 494254885Sdumbbell // hapens when we have two lexically identical GEP's (for example). 495254885Sdumbbell // 496254885Sdumbbell // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 497254885Sdumbbell // must aliases the GEP, the end result is a must alias also. 498254885Sdumbbell if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 499254885Sdumbbell return MustAlias; 500254885Sdumbbell 501254885Sdumbbell // If we have a known constant offset, see if this offset is larger than the 502254885Sdumbbell // access size being queried. If so, and if no variable indices can remove 503254885Sdumbbell // pieces of this constant, then we know we have a no-alias. For example, 504254885Sdumbbell // &A[100] != &A. 505254885Sdumbbell 506254885Sdumbbell // In order to handle cases like &A[100][i] where i is an out of range 507254885Sdumbbell // subscript, we have to ignore all constant offset pieces that are a multiple 508254885Sdumbbell // of a scaled index. Do this by removing constant offsets that are a 509254885Sdumbbell // multiple of any of our variable indices. This allows us to transform 510254885Sdumbbell // things like &A[i][1] because i has a stride of (e.g.) 8 bytes but the 1 511254885Sdumbbell // provides an offset of 4 bytes (assuming a <= 4 byte access). 512254885Sdumbbell for (unsigned i = 0, e = GEP1VariableIndices.size(); 513254885Sdumbbell i != e && GEP1BaseOffset;++i) 514254885Sdumbbell if (int64_t RemovedOffset = GEP1BaseOffset/GEP1VariableIndices[i].second) 515254885Sdumbbell GEP1BaseOffset -= RemovedOffset*GEP1VariableIndices[i].second; 516254885Sdumbbell 517254885Sdumbbell // If our known offset is bigger than the access size, we know we don't have 518254885Sdumbbell // an alias. 519254885Sdumbbell if (GEP1BaseOffset) { 520254885Sdumbbell if (GEP1BaseOffset >= (int64_t)V2Size || 521254885Sdumbbell GEP1BaseOffset <= -(int64_t)V1Size) 522254885Sdumbbell return NoAlias; 523254885Sdumbbell } 524254885Sdumbbell 525254885Sdumbbell return MayAlias; 526254885Sdumbbell} 527254885Sdumbbell 528254885Sdumbbell/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 529254885Sdumbbell/// instruction against another. 530254885SdumbbellAliasAnalysis::AliasResult 531254885SdumbbellBasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, 532254885Sdumbbell const Value *V2, unsigned V2Size) { 533254885Sdumbbell // If the values are Selects with the same condition, we can do a more precise 534254885Sdumbbell // check: just check for aliases between the values on corresponding arms. 535254885Sdumbbell if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 536254885Sdumbbell if (SI->getCondition() == SI2->getCondition()) { 537254885Sdumbbell AliasResult Alias = 538254885Sdumbbell aliasCheck(SI->getTrueValue(), SISize, 539254885Sdumbbell SI2->getTrueValue(), V2Size); 540254885Sdumbbell if (Alias == MayAlias) 541254885Sdumbbell return MayAlias; 542254885Sdumbbell AliasResult ThisAlias = 543254885Sdumbbell aliasCheck(SI->getFalseValue(), SISize, 544254885Sdumbbell SI2->getFalseValue(), V2Size); 545254885Sdumbbell if (ThisAlias != Alias) 546254885Sdumbbell return MayAlias; 547254885Sdumbbell return Alias; 548254885Sdumbbell } 549254885Sdumbbell 550254885Sdumbbell // If both arms of the Select node NoAlias or MustAlias V2, then returns 551254885Sdumbbell // NoAlias / MustAlias. Otherwise, returns MayAlias. 552254885Sdumbbell AliasResult Alias = 553254885Sdumbbell aliasCheck(SI->getTrueValue(), SISize, V2, V2Size); 554254885Sdumbbell if (Alias == MayAlias) 555254885Sdumbbell return MayAlias; 556254885Sdumbbell AliasResult ThisAlias = 557254885Sdumbbell aliasCheck(SI->getFalseValue(), SISize, V2, V2Size); 558254885Sdumbbell if (ThisAlias != Alias) 559254885Sdumbbell return MayAlias; 560254885Sdumbbell return Alias; 561254885Sdumbbell} 562254885Sdumbbell 563254885Sdumbbell// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 564254885Sdumbbell// against another. 565254885SdumbbellAliasAnalysis::AliasResult 566254885SdumbbellBasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, 567254885Sdumbbell const Value *V2, unsigned V2Size) { 568254885Sdumbbell // The PHI node has already been visited, avoid recursion any further. 569254885Sdumbbell if (!VisitedPHIs.insert(PN)) 570254885Sdumbbell return MayAlias; 571254885Sdumbbell 572254885Sdumbbell // If the values are PHIs in the same block, we can do a more precise 573254885Sdumbbell // as well as efficient check: just check for aliases between the values 574254885Sdumbbell // on corresponding edges. 575254885Sdumbbell if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 576254885Sdumbbell if (PN2->getParent() == PN->getParent()) { 577254885Sdumbbell AliasResult Alias = 578254885Sdumbbell aliasCheck(PN->getIncomingValue(0), PNSize, 579254885Sdumbbell PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 580254885Sdumbbell V2Size); 581254885Sdumbbell if (Alias == MayAlias) 582254885Sdumbbell return MayAlias; 583254885Sdumbbell for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 584254885Sdumbbell AliasResult ThisAlias = 585254885Sdumbbell aliasCheck(PN->getIncomingValue(i), PNSize, 586254885Sdumbbell PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 587254885Sdumbbell V2Size); 588254885Sdumbbell if (ThisAlias != Alias) 589254885Sdumbbell return MayAlias; 590254885Sdumbbell } 591254885Sdumbbell return Alias; 592254885Sdumbbell } 593254885Sdumbbell 594254885Sdumbbell SmallPtrSet<Value*, 4> UniqueSrc; 595254885Sdumbbell SmallVector<Value*, 4> V1Srcs; 596254885Sdumbbell for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 597254885Sdumbbell Value *PV1 = PN->getIncomingValue(i); 598254885Sdumbbell if (isa<PHINode>(PV1)) 599254885Sdumbbell // If any of the source itself is a PHI, return MayAlias conservatively 600254885Sdumbbell // to avoid compile time explosion. The worst possible case is if both 601254885Sdumbbell // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 602254885Sdumbbell // and 'n' are the number of PHI sources. 603254885Sdumbbell return MayAlias; 604254885Sdumbbell if (UniqueSrc.insert(PV1)) 605254885Sdumbbell V1Srcs.push_back(PV1); 606254885Sdumbbell } 607254885Sdumbbell 608254885Sdumbbell AliasResult Alias = aliasCheck(V2, V2Size, V1Srcs[0], PNSize); 609254885Sdumbbell // Early exit if the check of the first PHI source against V2 is MayAlias. 610254885Sdumbbell // Other results are not possible. 611254885Sdumbbell if (Alias == MayAlias) 612254885Sdumbbell return MayAlias; 613254885Sdumbbell 614254885Sdumbbell // If all sources of the PHI node NoAlias or MustAlias V2, then returns 615254885Sdumbbell // NoAlias / MustAlias. Otherwise, returns MayAlias. 616254885Sdumbbell for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 617254885Sdumbbell Value *V = V1Srcs[i]; 618254885Sdumbbell 619254885Sdumbbell // If V2 is a PHI, the recursive case will have been caught in the 620254885Sdumbbell // above aliasCheck call, so these subsequent calls to aliasCheck 621254885Sdumbbell // don't need to assume that V2 is being visited recursively. 622254885Sdumbbell VisitedPHIs.erase(V2); 623254885Sdumbbell 624254885Sdumbbell AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize); 625254885Sdumbbell if (ThisAlias != Alias || ThisAlias == MayAlias) 626254885Sdumbbell return MayAlias; 627254885Sdumbbell } 628254885Sdumbbell 629254885Sdumbbell return Alias; 630254885Sdumbbell} 631254885Sdumbbell 632254885Sdumbbell// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 633254885Sdumbbell// such as array references. 634254885Sdumbbell// 635254885SdumbbellAliasAnalysis::AliasResult 636254885SdumbbellBasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, 637254885Sdumbbell const Value *V2, unsigned V2Size) { 638254885Sdumbbell // Strip off any casts if they exist. 639254885Sdumbbell V1 = V1->stripPointerCasts(); 640254885Sdumbbell V2 = V2->stripPointerCasts(); 641254885Sdumbbell 642254885Sdumbbell // Are we checking for alias of the same value? 643254885Sdumbbell if (V1 == V2) return MustAlias; 644254885Sdumbbell 645254885Sdumbbell if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) 646254885Sdumbbell return NoAlias; // Scalars cannot alias each other 647254885Sdumbbell 648254885Sdumbbell // Figure out what objects these things are pointing to if we can. 649254885Sdumbbell const Value *O1 = V1->getUnderlyingObject(); 650254885Sdumbbell const Value *O2 = V2->getUnderlyingObject(); 651254885Sdumbbell 652254885Sdumbbell // Null values in the default address space don't point to any object, so they 653254885Sdumbbell // don't alias any other pointer. 654254885Sdumbbell if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 655254885Sdumbbell if (CPN->getType()->getAddressSpace() == 0) 656254885Sdumbbell return NoAlias; 657254885Sdumbbell if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 658254885Sdumbbell if (CPN->getType()->getAddressSpace() == 0) 659254885Sdumbbell return NoAlias; 660254885Sdumbbell 661254885Sdumbbell if (O1 != O2) { 662254885Sdumbbell // If V1/V2 point to two different objects we know that we have no alias. 663254885Sdumbbell if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 664254885Sdumbbell return NoAlias; 665254885Sdumbbell 666254885Sdumbbell // Constant pointers can't alias with non-const isIdentifiedObject objects. 667254885Sdumbbell if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 668254885Sdumbbell (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 669254885Sdumbbell return NoAlias; 670254885Sdumbbell 671254885Sdumbbell // Arguments can't alias with local allocations or noalias calls. 672254885Sdumbbell if ((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 673254885Sdumbbell (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1)))) 674254885Sdumbbell return NoAlias; 675254885Sdumbbell 676254885Sdumbbell // Most objects can't alias null. 677254885Sdumbbell if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || 678254885Sdumbbell (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) 679254885Sdumbbell return NoAlias; 680254885Sdumbbell } 681254885Sdumbbell 682254885Sdumbbell // If the size of one access is larger than the entire object on the other 683254885Sdumbbell // side, then we know such behavior is undefined and can assume no alias. 684254885Sdumbbell if (TD) 685254885Sdumbbell if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, *TD)) || 686254885Sdumbbell (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, *TD))) 687254885Sdumbbell return NoAlias; 688254885Sdumbbell 689254885Sdumbbell // If one pointer is the result of a call/invoke or load and the other is a 690254885Sdumbbell // non-escaping local object, then we know the object couldn't escape to a 691254885Sdumbbell // point where the call could return it. The load case works because 692254885Sdumbbell // isNonEscapingLocalObject considers all stores to be escapes (it 693254885Sdumbbell // passes true for the StoreCaptures argument to PointerMayBeCaptured). 694254885Sdumbbell if (O1 != O2) { 695254885Sdumbbell if ((isa<CallInst>(O1) || isa<InvokeInst>(O1) || isa<LoadInst>(O1) || 696254885Sdumbbell isa<Argument>(O1)) && 697254885Sdumbbell isNonEscapingLocalObject(O2)) 698254885Sdumbbell return NoAlias; 699254885Sdumbbell if ((isa<CallInst>(O2) || isa<InvokeInst>(O2) || isa<LoadInst>(O2) || 700254885Sdumbbell isa<Argument>(O2)) && 701254885Sdumbbell isNonEscapingLocalObject(O1)) 702254885Sdumbbell return NoAlias; 703254885Sdumbbell } 704254885Sdumbbell 705254885Sdumbbell // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 706254885Sdumbbell // GEP can't simplify, we don't even look at the PHI cases. 707254885Sdumbbell if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 708254885Sdumbbell std::swap(V1, V2); 709254885Sdumbbell std::swap(V1Size, V2Size); 710254885Sdumbbell std::swap(O1, O2); 711254885Sdumbbell } 712254885Sdumbbell if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) 713254885Sdumbbell return aliasGEP(GV1, V1Size, V2, V2Size, O1, O2); 714254885Sdumbbell 715254885Sdumbbell if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 716254885Sdumbbell std::swap(V1, V2); 717254885Sdumbbell std::swap(V1Size, V2Size); 718254885Sdumbbell } 719254885Sdumbbell if (const PHINode *PN = dyn_cast<PHINode>(V1)) 720254885Sdumbbell return aliasPHI(PN, V1Size, V2, V2Size); 721254885Sdumbbell 722254885Sdumbbell if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 723254885Sdumbbell std::swap(V1, V2); 724254885Sdumbbell std::swap(V1Size, V2Size); 725254885Sdumbbell } 726254885Sdumbbell if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) 727254885Sdumbbell return aliasSelect(S1, V1Size, V2, V2Size); 728254885Sdumbbell 729254885Sdumbbell return MayAlias; 730254885Sdumbbell} 731254885Sdumbbell 732254885Sdumbbell// Make sure that anything that uses AliasAnalysis pulls in this file. 733254885SdumbbellDEFINING_FILE_FOR(BasicAliasAnalysis) 734254885Sdumbbell