BasicAliasAnalysis.cpp revision 198396
1169689Skan//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2169689Skan// 3169689Skan// The LLVM Compiler Infrastructure 4169689Skan// 5169689Skan// This file is distributed under the University of Illinois Open Source 6169689Skan// License. See LICENSE.TXT for details. 7169689Skan// 8169689Skan//===----------------------------------------------------------------------===// 9169689Skan// 10169689Skan// This file defines the default implementation of the Alias Analysis interface 11169689Skan// that simply implements a few identities (two different globals cannot alias, 12169689Skan// etc), but otherwise does no analysis. 13169689Skan// 14169689Skan//===----------------------------------------------------------------------===// 15169689Skan 16169689Skan#include "llvm/Analysis/AliasAnalysis.h" 17169689Skan#include "llvm/Analysis/CaptureTracking.h" 18169689Skan#include "llvm/Analysis/MallocHelper.h" 19169689Skan#include "llvm/Analysis/Passes.h" 20169689Skan#include "llvm/Constants.h" 21169689Skan#include "llvm/DerivedTypes.h" 22169689Skan#include "llvm/Function.h" 23169689Skan#include "llvm/GlobalVariable.h" 24169689Skan#include "llvm/Instructions.h" 25169689Skan#include "llvm/IntrinsicInst.h" 26169689Skan#include "llvm/LLVMContext.h" 27169689Skan#include "llvm/Operator.h" 28169689Skan#include "llvm/Pass.h" 29169689Skan#include "llvm/Target/TargetData.h" 30169689Skan#include "llvm/ADT/SmallSet.h" 31169689Skan#include "llvm/ADT/SmallVector.h" 32169689Skan#include "llvm/ADT/STLExtras.h" 33169689Skan#include "llvm/Support/Compiler.h" 34169689Skan#include "llvm/Support/ErrorHandling.h" 35169689Skan#include "llvm/Support/GetElementPtrTypeIterator.h" 36169689Skan#include <algorithm> 37169689Skanusing namespace llvm; 38169689Skan 39169689Skan//===----------------------------------------------------------------------===// 40169689Skan// Useful predicates 41169689Skan//===----------------------------------------------------------------------===// 42169689Skan 43169689Skanstatic const Value *GetGEPOperands(const Value *V, 44169689Skan SmallVector<Value*, 16> &GEPOps) { 45169689Skan assert(GEPOps.empty() && "Expect empty list to populate!"); 46169689Skan GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 47169689Skan cast<User>(V)->op_end()); 48169689Skan 49169689Skan // Accumulate all of the chained indexes into the operand array 50169689Skan V = cast<User>(V)->getOperand(0); 51169689Skan 52169689Skan while (const GEPOperator *G = dyn_cast<GEPOperator>(V)) { 53169689Skan if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 54169689Skan !cast<Constant>(GEPOps[0])->isNullValue()) 55169689Skan break; // Don't handle folding arbitrary pointer offsets yet... 56169689Skan GEPOps.erase(GEPOps.begin()); // Drop the zero index 57169689Skan GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 58169689Skan V = G->getOperand(0); 59169689Skan } 60169689Skan return V; 61169689Skan} 62169689Skan 63169689Skan/// isKnownNonNull - Return true if we know that the specified value is never 64169689Skan/// null. 65169689Skanstatic bool isKnownNonNull(const Value *V) { 66169689Skan // Alloca never returns null, malloc might. 67169689Skan if (isa<AllocaInst>(V)) return true; 68169689Skan 69169689Skan // A byval argument is never null. 70169689Skan if (const Argument *A = dyn_cast<Argument>(V)) 71169689Skan return A->hasByValAttr(); 72169689Skan 73169689Skan // Global values are not null unless extern weak. 74169689Skan if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 75169689Skan return !GV->hasExternalWeakLinkage(); 76169689Skan return false; 77169689Skan} 78169689Skan 79169689Skan/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 80169689Skan/// object that never escapes from the function. 81169689Skanstatic bool isNonEscapingLocalObject(const Value *V) { 82169689Skan // If this is a local allocation, check to see if it escapes. 83169689Skan if (isa<AllocationInst>(V) || isNoAliasCall(V)) 84169689Skan return !PointerMayBeCaptured(V, false); 85169689Skan 86169689Skan // If this is an argument that corresponds to a byval or noalias argument, 87169689Skan // then it has not escaped before entering the function. Check if it escapes 88169689Skan // inside the function. 89169689Skan if (const Argument *A = dyn_cast<Argument>(V)) 90169689Skan if (A->hasByValAttr() || A->hasNoAliasAttr()) { 91169689Skan // Don't bother analyzing arguments already known not to escape. 92169689Skan if (A->hasNoCaptureAttr()) 93169689Skan return true; 94169689Skan return !PointerMayBeCaptured(V, false); 95169689Skan } 96169689Skan return false; 97169689Skan} 98169689Skan 99169689Skan 100169689Skan/// isObjectSmallerThan - Return true if we can prove that the object specified 101169689Skan/// by V is smaller than Size. 102169689Skanstatic bool isObjectSmallerThan(const Value *V, unsigned Size, 103169689Skan LLVMContext &Context, const TargetData &TD) { 104169689Skan const Type *AccessTy; 105169689Skan if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 106169689Skan AccessTy = GV->getType()->getElementType(); 107169689Skan } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(V)) { 108169689Skan if (!AI->isArrayAllocation()) 109169689Skan AccessTy = AI->getType()->getElementType(); 110169689Skan else 111169689Skan return false; 112169689Skan } else if (const CallInst* CI = extractMallocCall(V)) { 113169689Skan if (!isArrayMalloc(V, Context, &TD)) 114169689Skan // The size is the argument to the malloc call. 115169689Skan if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getOperand(1))) 116169689Skan return (C->getZExtValue() < Size); 117169689Skan return false; 118169689Skan } else if (const Argument *A = dyn_cast<Argument>(V)) { 119169689Skan if (A->hasByValAttr()) 120169689Skan AccessTy = cast<PointerType>(A->getType())->getElementType(); 121169689Skan else 122169689Skan return false; 123169689Skan } else { 124169689Skan return false; 125169689Skan } 126169689Skan 127169689Skan if (AccessTy->isSized()) 128169689Skan return TD.getTypeAllocSize(AccessTy) < Size; 129169689Skan return false; 130169689Skan} 131169689Skan 132169689Skan//===----------------------------------------------------------------------===// 133169689Skan// NoAA Pass 134169689Skan//===----------------------------------------------------------------------===// 135169689Skan 136169689Skannamespace { 137169689Skan /// NoAA - This class implements the -no-aa pass, which always returns "I 138169689Skan /// don't know" for alias queries. NoAA is unlike other alias analysis 139169689Skan /// implementations, in that it does not chain to a previous analysis. As 140169689Skan /// such it doesn't follow many of the rules that other alias analyses must. 141169689Skan /// 142169689Skan struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 143169689Skan static char ID; // Class identification, replacement for typeinfo 144169689Skan NoAA() : ImmutablePass(&ID) {} 145169689Skan explicit NoAA(void *PID) : ImmutablePass(PID) { } 146169689Skan 147169689Skan virtual void getAnalysisUsage(AnalysisUsage &AU) const { 148169689Skan } 149169689Skan 150169689Skan virtual void initializePass() { 151169689Skan TD = getAnalysisIfAvailable<TargetData>(); 152169689Skan } 153169689Skan 154169689Skan virtual AliasResult alias(const Value *V1, unsigned V1Size, 155169689Skan const Value *V2, unsigned V2Size) { 156169689Skan return MayAlias; 157169689Skan } 158169689Skan 159169689Skan virtual void getArgumentAccesses(Function *F, CallSite CS, 160169689Skan std::vector<PointerAccessInfo> &Info) { 161169689Skan llvm_unreachable("This method may not be called on this function!"); 162169689Skan } 163169689Skan 164169689Skan virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 165169689Skan virtual bool pointsToConstantMemory(const Value *P) { return false; } 166169689Skan virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 167169689Skan return ModRef; 168169689Skan } 169169689Skan virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 170169689Skan return ModRef; 171169689Skan } 172169689Skan virtual bool hasNoModRefInfoForCalls() const { return true; } 173169689Skan 174169689Skan virtual void deleteValue(Value *V) {} 175169689Skan virtual void copyValue(Value *From, Value *To) {} 176169689Skan }; 177169689Skan} // End of anonymous namespace 178169689Skan 179169689Skan// Register this pass... 180169689Skanchar NoAA::ID = 0; 181169689Skanstatic RegisterPass<NoAA> 182169689SkanU("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 183169689Skan 184169689Skan// Declare that we implement the AliasAnalysis interface 185169689Skanstatic RegisterAnalysisGroup<AliasAnalysis> V(U); 186169689Skan 187169689SkanImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 188169689Skan 189169689Skan//===----------------------------------------------------------------------===// 190169689Skan// BasicAA Pass 191169689Skan//===----------------------------------------------------------------------===// 192169689Skan 193169689Skannamespace { 194169689Skan /// BasicAliasAnalysis - This is the default alias analysis implementation. 195169689Skan /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 196169689Skan /// derives from the NoAA class. 197169689Skan struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 198169689Skan static char ID; // Class identification, replacement for typeinfo 199169689Skan BasicAliasAnalysis() : NoAA(&ID) {} 200169689Skan AliasResult alias(const Value *V1, unsigned V1Size, 201169689Skan const Value *V2, unsigned V2Size) { 202169689Skan assert(VisitedPHIs.empty() && "VisitedPHIs must be cleared after use!"); 203169689Skan AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size); 204169689Skan VisitedPHIs.clear(); 205169689Skan return Alias; 206169689Skan } 207169689Skan 208169689Skan ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 209169689Skan ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); 210169689Skan 211169689Skan /// hasNoModRefInfoForCalls - We can provide mod/ref information against 212169689Skan /// non-escaping allocations. 213169689Skan virtual bool hasNoModRefInfoForCalls() const { return false; } 214169689Skan 215169689Skan /// pointsToConstantMemory - Chase pointers until we find a (constant 216169689Skan /// global) or not. 217169689Skan bool pointsToConstantMemory(const Value *P); 218169689Skan 219169689Skan private: 220169689Skan // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call. 221169689Skan SmallPtrSet<const PHINode*, 16> VisitedPHIs; 222169689Skan 223169689Skan // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 224169689Skan // against another. 225169689Skan AliasResult aliasGEP(const Value *V1, unsigned V1Size, 226169689Skan const Value *V2, unsigned V2Size); 227169689Skan 228169689Skan // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 229169689Skan // against another. 230169689Skan AliasResult aliasPHI(const PHINode *PN, unsigned PNSize, 231169689Skan const Value *V2, unsigned V2Size); 232169689Skan 233169689Skan AliasResult aliasCheck(const Value *V1, unsigned V1Size, 234169689Skan const Value *V2, unsigned V2Size); 235169689Skan 236169689Skan // CheckGEPInstructions - Check two GEP instructions with known 237169689Skan // must-aliasing base pointers. This checks to see if the index expressions 238169689Skan // preclude the pointers from aliasing... 239169689Skan AliasResult 240169689Skan CheckGEPInstructions(const Type* BasePtr1Ty, 241169689Skan Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 242169689Skan const Type *BasePtr2Ty, 243169689Skan Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 244169689Skan }; 245169689Skan} // End of anonymous namespace 246169689Skan 247169689Skan// Register this pass... 248169689Skanchar BasicAliasAnalysis::ID = 0; 249169689Skanstatic RegisterPass<BasicAliasAnalysis> 250169689SkanX("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 251169689Skan 252169689Skan// Declare that we implement the AliasAnalysis interface 253169689Skanstatic RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 254169689Skan 255169689SkanImmutablePass *llvm::createBasicAliasAnalysisPass() { 256169689Skan return new BasicAliasAnalysis(); 257169689Skan} 258169689Skan 259169689Skan 260169689Skan/// pointsToConstantMemory - Chase pointers until we find a (constant 261169689Skan/// global) or not. 262169689Skanbool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 263169689Skan if (const GlobalVariable *GV = 264169689Skan dyn_cast<GlobalVariable>(P->getUnderlyingObject())) 265169689Skan return GV->isConstant(); 266169689Skan return false; 267169689Skan} 268169689Skan 269169689Skan 270169689Skan// getModRefInfo - Check to see if the specified callsite can clobber the 271169689Skan// specified memory object. Since we only look at local properties of this 272169689Skan// function, we really can't say much about this query. We do, however, use 273169689Skan// simple "address taken" analysis on local objects. 274169689Skan// 275169689SkanAliasAnalysis::ModRefResult 276169689SkanBasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 277169689Skan if (!isa<Constant>(P)) { 278169689Skan const Value *Object = P->getUnderlyingObject(); 279169689Skan 280169689Skan // If this is a tail call and P points to a stack location, we know that 281169689Skan // the tail call cannot access or modify the local stack. 282169689Skan // We cannot exclude byval arguments here; these belong to the caller of 283169689Skan // the current function not to the current function, and a tail callee 284169689Skan // may reference them. 285169689Skan if (isa<AllocaInst>(Object)) 286169689Skan if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 287169689Skan if (CI->isTailCall()) 288169689Skan return NoModRef; 289169689Skan 290169689Skan // If the pointer is to a locally allocated object that does not escape, 291169689Skan // then the call can not mod/ref the pointer unless the call takes the 292169689Skan // argument without capturing it. 293169689Skan if (isNonEscapingLocalObject(Object) && CS.getInstruction() != Object) { 294169689Skan bool passedAsArg = false; 295169689Skan // TODO: Eventually only check 'nocapture' arguments. 296169689Skan for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 297169689Skan CI != CE; ++CI) 298169689Skan if (isa<PointerType>((*CI)->getType()) && 299169689Skan alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias) 300169689Skan passedAsArg = true; 301169689Skan 302169689Skan if (!passedAsArg) 303169689Skan return NoModRef; 304169689Skan } 305169689Skan 306169689Skan if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 307169689Skan switch (II->getIntrinsicID()) { 308169689Skan default: break; 309169689Skan case Intrinsic::memcpy: 310169689Skan case Intrinsic::memmove: { 311169689Skan unsigned Len = ~0U; 312169689Skan if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) 313169689Skan Len = LenCI->getZExtValue(); 314169689Skan Value *Dest = II->getOperand(1); 315169689Skan Value *Src = II->getOperand(2); 316169689Skan if (alias(Dest, Len, P, Size) == NoAlias) { 317169689Skan if (alias(Src, Len, P, Size) == NoAlias) 318169689Skan return NoModRef; 319169689Skan return Ref; 320169689Skan } 321169689Skan } 322169689Skan break; 323169689Skan case Intrinsic::memset: 324169689Skan if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getOperand(3))) { 325169689Skan unsigned Len = LenCI->getZExtValue(); 326169689Skan Value *Dest = II->getOperand(1); 327169689Skan if (alias(Dest, Len, P, Size) == NoAlias) 328169689Skan return NoModRef; 329169689Skan } 330169689Skan break; 331169689Skan case Intrinsic::atomic_cmp_swap: 332169689Skan case Intrinsic::atomic_swap: 333169689Skan case Intrinsic::atomic_load_add: 334169689Skan case Intrinsic::atomic_load_sub: 335169689Skan case Intrinsic::atomic_load_and: 336169689Skan case Intrinsic::atomic_load_nand: 337169689Skan case Intrinsic::atomic_load_or: 338169689Skan case Intrinsic::atomic_load_xor: 339169689Skan case Intrinsic::atomic_load_max: 340169689Skan case Intrinsic::atomic_load_min: 341169689Skan case Intrinsic::atomic_load_umax: 342169689Skan case Intrinsic::atomic_load_umin: 343169689Skan if (TD) { 344169689Skan Value *Op1 = II->getOperand(1); 345169689Skan unsigned Op1Size = TD->getTypeStoreSize(Op1->getType()); 346169689Skan if (alias(Op1, Op1Size, P, Size) == NoAlias) 347169689Skan return NoModRef; 348169689Skan } 349169689Skan break; 350169689Skan case Intrinsic::lifetime_start: 351169689Skan case Intrinsic::lifetime_end: 352169689Skan case Intrinsic::invariant_start: { 353169689Skan unsigned PtrSize = cast<ConstantInt>(II->getOperand(1))->getZExtValue(); 354169689Skan if (alias(II->getOperand(2), PtrSize, P, Size) == NoAlias) 355169689Skan return NoModRef; 356169689Skan } 357169689Skan break; 358169689Skan case Intrinsic::invariant_end: { 359169689Skan unsigned PtrSize = cast<ConstantInt>(II->getOperand(2))->getZExtValue(); 360169689Skan if (alias(II->getOperand(3), PtrSize, P, Size) == NoAlias) 361169689Skan return NoModRef; 362169689Skan } 363169689Skan break; 364169689Skan } 365169689Skan } 366169689Skan } 367169689Skan 368169689Skan // The AliasAnalysis base class has some smarts, lets use them. 369169689Skan return AliasAnalysis::getModRefInfo(CS, P, Size); 370169689Skan} 371169689Skan 372169689Skan 373169689SkanAliasAnalysis::ModRefResult 374169689SkanBasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 375169689Skan // If CS1 or CS2 are readnone, they don't interact. 376169689Skan ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); 377169689Skan if (CS1B == DoesNotAccessMemory) return NoModRef; 378169689Skan 379169689Skan ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); 380169689Skan if (CS2B == DoesNotAccessMemory) return NoModRef; 381169689Skan 382169689Skan // If they both only read from memory, just return ref. 383169689Skan if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 384169689Skan return Ref; 385169689Skan 386169689Skan // Otherwise, fall back to NoAA (mod+ref). 387169689Skan return NoAA::getModRefInfo(CS1, CS2); 388169689Skan} 389169689Skan 390169689Skan// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 391169689Skan// against another. 392169689Skan// 393169689SkanAliasAnalysis::AliasResult 394169689SkanBasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, 395169689Skan const Value *V2, unsigned V2Size) { 396169689Skan // If we have two gep instructions with must-alias'ing base pointers, figure 397169689Skan // out if the indexes to the GEP tell us anything about the derived pointer. 398169689Skan // Note that we also handle chains of getelementptr instructions as well as 399169689Skan // constant expression getelementptrs here. 400169689Skan // 401169689Skan if (isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 402169689Skan const User *GEP1 = cast<User>(V1); 403169689Skan const User *GEP2 = cast<User>(V2); 404169689Skan 405169689Skan // If V1 and V2 are identical GEPs, just recurse down on both of them. 406169689Skan // This allows us to analyze things like: 407169689Skan // P = gep A, 0, i, 1 408169689Skan // Q = gep B, 0, i, 1 409169689Skan // by just analyzing A and B. This is even safe for variable indices. 410169689Skan if (GEP1->getType() == GEP2->getType() && 411169689Skan GEP1->getNumOperands() == GEP2->getNumOperands() && 412169689Skan GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() && 413169689Skan // All operands are the same, ignoring the base. 414169689Skan std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1)) 415169689Skan return aliasCheck(GEP1->getOperand(0), V1Size, 416169689Skan GEP2->getOperand(0), V2Size); 417169689Skan 418169689Skan // Drill down into the first non-gep value, to test for must-aliasing of 419169689Skan // the base pointers. 420169689Skan while (isa<GEPOperator>(GEP1->getOperand(0)) && 421169689Skan GEP1->getOperand(1) == 422169689Skan Constant::getNullValue(GEP1->getOperand(1)->getType())) 423169689Skan GEP1 = cast<User>(GEP1->getOperand(0)); 424169689Skan const Value *BasePtr1 = GEP1->getOperand(0); 425169689Skan 426169689Skan while (isa<GEPOperator>(GEP2->getOperand(0)) && 427169689Skan GEP2->getOperand(1) == 428169689Skan Constant::getNullValue(GEP2->getOperand(1)->getType())) 429169689Skan GEP2 = cast<User>(GEP2->getOperand(0)); 430169689Skan const Value *BasePtr2 = GEP2->getOperand(0); 431169689Skan 432169689Skan // Do the base pointers alias? 433169689Skan AliasResult BaseAlias = aliasCheck(BasePtr1, ~0U, BasePtr2, ~0U); 434169689Skan if (BaseAlias == NoAlias) return NoAlias; 435169689Skan if (BaseAlias == MustAlias) { 436169689Skan // If the base pointers alias each other exactly, check to see if we can 437169689Skan // figure out anything about the resultant pointers, to try to prove 438169689Skan // non-aliasing. 439169689Skan 440169689Skan // Collect all of the chained GEP operands together into one simple place 441169689Skan SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 442169689Skan BasePtr1 = GetGEPOperands(V1, GEP1Ops); 443169689Skan BasePtr2 = GetGEPOperands(V2, GEP2Ops); 444169689Skan 445169689Skan // If GetGEPOperands were able to fold to the same must-aliased pointer, 446169689Skan // do the comparison. 447169689Skan if (BasePtr1 == BasePtr2) { 448169689Skan AliasResult GAlias = 449169689Skan CheckGEPInstructions(BasePtr1->getType(), 450169689Skan &GEP1Ops[0], GEP1Ops.size(), V1Size, 451169689Skan BasePtr2->getType(), 452169689Skan &GEP2Ops[0], GEP2Ops.size(), V2Size); 453169689Skan if (GAlias != MayAlias) 454 return GAlias; 455 } 456 } 457 } 458 459 // Check to see if these two pointers are related by a getelementptr 460 // instruction. If one pointer is a GEP with a non-zero index of the other 461 // pointer, we know they cannot alias. 462 // 463 if (V1Size == ~0U || V2Size == ~0U) 464 return MayAlias; 465 466 SmallVector<Value*, 16> GEPOperands; 467 const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 468 469 AliasResult R = aliasCheck(BasePtr, ~0U, V2, V2Size); 470 if (R != MustAlias) 471 // If V2 may alias GEP base pointer, conservatively returns MayAlias. 472 // If V2 is known not to alias GEP base pointer, then the two values 473 // cannot alias per GEP semantics: "A pointer value formed from a 474 // getelementptr instruction is associated with the addresses associated 475 // with the first operand of the getelementptr". 476 return R; 477 478 // If there is at least one non-zero constant index, we know they cannot 479 // alias. 480 bool ConstantFound = false; 481 bool AllZerosFound = true; 482 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 483 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 484 if (!C->isNullValue()) { 485 ConstantFound = true; 486 AllZerosFound = false; 487 break; 488 } 489 } else { 490 AllZerosFound = false; 491 } 492 493 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 494 // the ptr, the end result is a must alias also. 495 if (AllZerosFound) 496 return MustAlias; 497 498 if (ConstantFound) { 499 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 500 return NoAlias; 501 502 // Otherwise we have to check to see that the distance is more than 503 // the size of the argument... build an index vector that is equal to 504 // the arguments provided, except substitute 0's for any variable 505 // indexes we find... 506 if (TD && 507 cast<PointerType>(BasePtr->getType())->getElementType()->isSized()) { 508 for (unsigned i = 0; i != GEPOperands.size(); ++i) 509 if (!isa<ConstantInt>(GEPOperands[i])) 510 GEPOperands[i] = Constant::getNullValue(GEPOperands[i]->getType()); 511 int64_t Offset = TD->getIndexedOffset(BasePtr->getType(), 512 &GEPOperands[0], 513 GEPOperands.size()); 514 515 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 516 return NoAlias; 517 } 518 } 519 520 return MayAlias; 521} 522 523// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 524// against another. 525AliasAnalysis::AliasResult 526BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, 527 const Value *V2, unsigned V2Size) { 528 // The PHI node has already been visited, avoid recursion any further. 529 if (!VisitedPHIs.insert(PN)) 530 return MayAlias; 531 532 SmallPtrSet<Value*, 4> UniqueSrc; 533 SmallVector<Value*, 4> V1Srcs; 534 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 535 Value *PV1 = PN->getIncomingValue(i); 536 if (isa<PHINode>(PV1)) 537 // If any of the source itself is a PHI, return MayAlias conservatively 538 // to avoid compile time explosion. The worst possible case is if both 539 // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 540 // and 'n' are the number of PHI sources. 541 return MayAlias; 542 if (UniqueSrc.insert(PV1)) 543 V1Srcs.push_back(PV1); 544 } 545 546 AliasResult Alias = aliasCheck(V1Srcs[0], PNSize, V2, V2Size); 547 // Early exit if the check of the first PHI source against V2 is MayAlias. 548 // Other results are not possible. 549 if (Alias == MayAlias) 550 return MayAlias; 551 552 // If all sources of the PHI node NoAlias or MustAlias V2, then returns 553 // NoAlias / MustAlias. Otherwise, returns MayAlias. 554 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 555 Value *V = V1Srcs[i]; 556 AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize); 557 if (ThisAlias != Alias || ThisAlias == MayAlias) 558 return MayAlias; 559 } 560 561 return Alias; 562} 563 564// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 565// such as array references. 566// 567AliasAnalysis::AliasResult 568BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, 569 const Value *V2, unsigned V2Size) { 570 // Strip off any casts if they exist. 571 V1 = V1->stripPointerCasts(); 572 V2 = V2->stripPointerCasts(); 573 574 // Are we checking for alias of the same value? 575 if (V1 == V2) return MustAlias; 576 577 if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) 578 return NoAlias; // Scalars cannot alias each other 579 580 // Figure out what objects these things are pointing to if we can. 581 const Value *O1 = V1->getUnderlyingObject(); 582 const Value *O2 = V2->getUnderlyingObject(); 583 584 if (O1 != O2) { 585 // If V1/V2 point to two different objects we know that we have no alias. 586 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 587 return NoAlias; 588 589 // Arguments can't alias with local allocations or noalias calls. 590 if ((isa<Argument>(O1) && (isa<AllocationInst>(O2) || isNoAliasCall(O2))) || 591 (isa<Argument>(O2) && (isa<AllocationInst>(O1) || isNoAliasCall(O1)))) 592 return NoAlias; 593 594 // Most objects can't alias null. 595 if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || 596 (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) 597 return NoAlias; 598 } 599 600 // If the size of one access is larger than the entire object on the other 601 // side, then we know such behavior is undefined and can assume no alias. 602 LLVMContext &Context = V1->getContext(); 603 if (TD) 604 if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, Context, *TD)) || 605 (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, Context, *TD))) 606 return NoAlias; 607 608 // If one pointer is the result of a call/invoke and the other is a 609 // non-escaping local object, then we know the object couldn't escape to a 610 // point where the call could return it. 611 if ((isa<CallInst>(O1) || isa<InvokeInst>(O1)) && 612 isNonEscapingLocalObject(O2) && O1 != O2) 613 return NoAlias; 614 if ((isa<CallInst>(O2) || isa<InvokeInst>(O2)) && 615 isNonEscapingLocalObject(O1) && O1 != O2) 616 return NoAlias; 617 618 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 619 std::swap(V1, V2); 620 std::swap(V1Size, V2Size); 621 } 622 if (isa<GEPOperator>(V1)) 623 return aliasGEP(V1, V1Size, V2, V2Size); 624 625 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 626 std::swap(V1, V2); 627 std::swap(V1Size, V2Size); 628 } 629 if (const PHINode *PN = dyn_cast<PHINode>(V1)) 630 return aliasPHI(PN, V1Size, V2, V2Size); 631 632 return MayAlias; 633} 634 635// This function is used to determine if the indices of two GEP instructions are 636// equal. V1 and V2 are the indices. 637static bool IndexOperandsEqual(Value *V1, Value *V2, LLVMContext &Context) { 638 if (V1->getType() == V2->getType()) 639 return V1 == V2; 640 if (Constant *C1 = dyn_cast<Constant>(V1)) 641 if (Constant *C2 = dyn_cast<Constant>(V2)) { 642 // Sign extend the constants to long types, if necessary 643 if (C1->getType() != Type::getInt64Ty(Context)) 644 C1 = ConstantExpr::getSExt(C1, Type::getInt64Ty(Context)); 645 if (C2->getType() != Type::getInt64Ty(Context)) 646 C2 = ConstantExpr::getSExt(C2, Type::getInt64Ty(Context)); 647 return C1 == C2; 648 } 649 return false; 650} 651 652/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 653/// base pointers. This checks to see if the index expressions preclude the 654/// pointers from aliasing... 655AliasAnalysis::AliasResult 656BasicAliasAnalysis::CheckGEPInstructions( 657 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 658 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 659 // We currently can't handle the case when the base pointers have different 660 // primitive types. Since this is uncommon anyway, we are happy being 661 // extremely conservative. 662 if (BasePtr1Ty != BasePtr2Ty) 663 return MayAlias; 664 665 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 666 667 LLVMContext &Context = GEPPointerTy->getContext(); 668 669 // Find the (possibly empty) initial sequence of equal values... which are not 670 // necessarily constants. 671 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 672 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 673 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 674 unsigned UnequalOper = 0; 675 while (UnequalOper != MinOperands && 676 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper], 677 Context)) { 678 // Advance through the type as we go... 679 ++UnequalOper; 680 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 681 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 682 else { 683 // If all operands equal each other, then the derived pointers must 684 // alias each other... 685 BasePtr1Ty = 0; 686 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 687 "Ran out of type nesting, but not out of operands?"); 688 return MustAlias; 689 } 690 } 691 692 // If we have seen all constant operands, and run out of indexes on one of the 693 // getelementptrs, check to see if the tail of the leftover one is all zeros. 694 // If so, return mustalias. 695 if (UnequalOper == MinOperands) { 696 if (NumGEP1Ops < NumGEP2Ops) { 697 std::swap(GEP1Ops, GEP2Ops); 698 std::swap(NumGEP1Ops, NumGEP2Ops); 699 } 700 701 bool AllAreZeros = true; 702 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 703 if (!isa<Constant>(GEP1Ops[i]) || 704 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 705 AllAreZeros = false; 706 break; 707 } 708 if (AllAreZeros) return MustAlias; 709 } 710 711 712 // So now we know that the indexes derived from the base pointers, 713 // which are known to alias, are different. We can still determine a 714 // no-alias result if there are differing constant pairs in the index 715 // chain. For example: 716 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 717 // 718 // We have to be careful here about array accesses. In particular, consider: 719 // A[1][0] vs A[0][i] 720 // In this case, we don't *know* that the array will be accessed in bounds: 721 // the index could even be negative. Because of this, we have to 722 // conservatively *give up* and return may alias. We disregard differing 723 // array subscripts that are followed by a variable index without going 724 // through a struct. 725 // 726 unsigned SizeMax = std::max(G1S, G2S); 727 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 728 729 // Scan for the first operand that is constant and unequal in the 730 // two getelementptrs... 731 unsigned FirstConstantOper = UnequalOper; 732 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 733 const Value *G1Oper = GEP1Ops[FirstConstantOper]; 734 const Value *G2Oper = GEP2Ops[FirstConstantOper]; 735 736 if (G1Oper != G2Oper) // Found non-equal constant indexes... 737 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 738 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 739 if (G1OC->getType() != G2OC->getType()) { 740 // Sign extend both operands to long. 741 if (G1OC->getType() != Type::getInt64Ty(Context)) 742 G1OC = ConstantExpr::getSExt(G1OC, Type::getInt64Ty(Context)); 743 if (G2OC->getType() != Type::getInt64Ty(Context)) 744 G2OC = ConstantExpr::getSExt(G2OC, Type::getInt64Ty(Context)); 745 GEP1Ops[FirstConstantOper] = G1OC; 746 GEP2Ops[FirstConstantOper] = G2OC; 747 } 748 749 if (G1OC != G2OC) { 750 // Handle the "be careful" case above: if this is an array/vector 751 // subscript, scan for a subsequent variable array index. 752 if (const SequentialType *STy = 753 dyn_cast<SequentialType>(BasePtr1Ty)) { 754 const Type *NextTy = STy; 755 bool isBadCase = false; 756 757 for (unsigned Idx = FirstConstantOper; 758 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 759 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 760 if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 761 isBadCase = true; 762 break; 763 } 764 // If the array is indexed beyond the bounds of the static type 765 // at this level, it will also fall into the "be careful" case. 766 // It would theoretically be possible to analyze these cases, 767 // but for now just be conservatively correct. 768 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 769 if (cast<ConstantInt>(G1OC)->getZExtValue() >= 770 ATy->getNumElements() || 771 cast<ConstantInt>(G2OC)->getZExtValue() >= 772 ATy->getNumElements()) { 773 isBadCase = true; 774 break; 775 } 776 if (const VectorType *VTy = dyn_cast<VectorType>(STy)) 777 if (cast<ConstantInt>(G1OC)->getZExtValue() >= 778 VTy->getNumElements() || 779 cast<ConstantInt>(G2OC)->getZExtValue() >= 780 VTy->getNumElements()) { 781 isBadCase = true; 782 break; 783 } 784 STy = cast<SequentialType>(NextTy); 785 NextTy = cast<SequentialType>(NextTy)->getElementType(); 786 } 787 788 if (isBadCase) G1OC = 0; 789 } 790 791 // Make sure they are comparable (ie, not constant expressions), and 792 // make sure the GEP with the smaller leading constant is GEP1. 793 if (G1OC) { 794 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 795 G1OC, G2OC); 796 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 797 if (CV->getZExtValue()) { // If they are comparable and G2 > G1 798 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 799 std::swap(NumGEP1Ops, NumGEP2Ops); 800 } 801 break; 802 } 803 } 804 } 805 } 806 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 807 } 808 809 // No shared constant operands, and we ran out of common operands. At this 810 // point, the GEP instructions have run through all of their operands, and we 811 // haven't found evidence that there are any deltas between the GEP's. 812 // However, one GEP may have more operands than the other. If this is the 813 // case, there may still be hope. Check this now. 814 if (FirstConstantOper == MinOperands) { 815 // Without TargetData, we won't know what the offsets are. 816 if (!TD) 817 return MayAlias; 818 819 // Make GEP1Ops be the longer one if there is a longer one. 820 if (NumGEP1Ops < NumGEP2Ops) { 821 std::swap(GEP1Ops, GEP2Ops); 822 std::swap(NumGEP1Ops, NumGEP2Ops); 823 } 824 825 // Is there anything to check? 826 if (NumGEP1Ops > MinOperands) { 827 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 828 if (isa<ConstantInt>(GEP1Ops[i]) && 829 !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 830 // Yup, there's a constant in the tail. Set all variables to 831 // constants in the GEP instruction to make it suitable for 832 // TargetData::getIndexedOffset. 833 for (i = 0; i != MaxOperands; ++i) 834 if (!isa<ConstantInt>(GEP1Ops[i])) 835 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 836 // Okay, now get the offset. This is the relative offset for the full 837 // instruction. 838 int64_t Offset1 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, 839 NumGEP1Ops); 840 841 // Now check without any constants at the end. 842 int64_t Offset2 = TD->getIndexedOffset(GEPPointerTy, GEP1Ops, 843 MinOperands); 844 845 // Make sure we compare the absolute difference. 846 if (Offset1 > Offset2) 847 std::swap(Offset1, Offset2); 848 849 // If the tail provided a bit enough offset, return noalias! 850 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 851 return NoAlias; 852 // Otherwise break - we don't look for another constant in the tail. 853 break; 854 } 855 } 856 857 // Couldn't find anything useful. 858 return MayAlias; 859 } 860 861 // If there are non-equal constants arguments, then we can figure 862 // out a minimum known delta between the two index expressions... at 863 // this point we know that the first constant index of GEP1 is less 864 // than the first constant index of GEP2. 865 866 // Advance BasePtr[12]Ty over this first differing constant operand. 867 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 868 getTypeAtIndex(GEP2Ops[FirstConstantOper]); 869 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 870 getTypeAtIndex(GEP1Ops[FirstConstantOper]); 871 872 // We are going to be using TargetData::getIndexedOffset to determine the 873 // offset that each of the GEP's is reaching. To do this, we have to convert 874 // all variable references to constant references. To do this, we convert the 875 // initial sequence of array subscripts into constant zeros to start with. 876 const Type *ZeroIdxTy = GEPPointerTy; 877 for (unsigned i = 0; i != FirstConstantOper; ++i) { 878 if (!isa<StructType>(ZeroIdxTy)) 879 GEP1Ops[i] = GEP2Ops[i] = 880 Constant::getNullValue(Type::getInt32Ty(Context)); 881 882 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 883 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 884 } 885 886 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 887 888 // Loop over the rest of the operands... 889 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 890 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 891 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 892 // If they are equal, use a zero index... 893 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 894 if (!isa<ConstantInt>(Op1)) 895 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 896 // Otherwise, just keep the constants we have. 897 } else { 898 if (Op1) { 899 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 900 // If this is an array index, make sure the array element is in range. 901 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 902 if (Op1C->getZExtValue() >= AT->getNumElements()) 903 return MayAlias; // Be conservative with out-of-range accesses 904 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) { 905 if (Op1C->getZExtValue() >= VT->getNumElements()) 906 return MayAlias; // Be conservative with out-of-range accesses 907 } 908 909 } else { 910 // GEP1 is known to produce a value less than GEP2. To be 911 // conservatively correct, we must assume the largest possible 912 // constant is used in this position. This cannot be the initial 913 // index to the GEP instructions (because we know we have at least one 914 // element before this one with the different constant arguments), so 915 // we know that the current index must be into either a struct or 916 // array. Because we know it's not constant, this cannot be a 917 // structure index. Because of this, we can calculate the maximum 918 // value possible. 919 // 920 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 921 GEP1Ops[i] = 922 ConstantInt::get(Type::getInt64Ty(Context), 923 AT->getNumElements()-1); 924 else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) 925 GEP1Ops[i] = 926 ConstantInt::get(Type::getInt64Ty(Context), 927 VT->getNumElements()-1); 928 } 929 } 930 931 if (Op2) { 932 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 933 // If this is an array index, make sure the array element is in range. 934 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr2Ty)) { 935 if (Op2C->getZExtValue() >= AT->getNumElements()) 936 return MayAlias; // Be conservative with out-of-range accesses 937 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr2Ty)) { 938 if (Op2C->getZExtValue() >= VT->getNumElements()) 939 return MayAlias; // Be conservative with out-of-range accesses 940 } 941 } else { // Conservatively assume the minimum value for this index 942 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 943 } 944 } 945 } 946 947 if (BasePtr1Ty && Op1) { 948 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 949 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 950 else 951 BasePtr1Ty = 0; 952 } 953 954 if (BasePtr2Ty && Op2) { 955 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 956 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 957 else 958 BasePtr2Ty = 0; 959 } 960 } 961 962 if (TD && GEPPointerTy->getElementType()->isSized()) { 963 int64_t Offset1 = 964 TD->getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 965 int64_t Offset2 = 966 TD->getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 967 assert(Offset1 != Offset2 && 968 "There is at least one different constant here!"); 969 970 // Make sure we compare the absolute difference. 971 if (Offset1 > Offset2) 972 std::swap(Offset1, Offset2); 973 974 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 975 //cerr << "Determined that these two GEP's don't alias [" 976 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 977 return NoAlias; 978 } 979 } 980 return MayAlias; 981} 982 983// Make sure that anything that uses AliasAnalysis pulls in this file... 984DEFINING_FILE_FOR(BasicAliasAnalysis) 985