BasicAliasAnalysis.cpp revision 8be3291f5942e3ae4a5d66c480e7aabe2f771031
1//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the default implementation of the Alias Analysis interface 11// that simply implements a few identities (two different globals cannot alias, 12// etc), but otherwise does no analysis. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/AliasAnalysis.h" 17#include "llvm/Analysis/Passes.h" 18#include "llvm/Constants.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/Function.h" 21#include "llvm/GlobalVariable.h" 22#include "llvm/Instructions.h" 23#include "llvm/IntrinsicInst.h" 24#include "llvm/Operator.h" 25#include "llvm/Pass.h" 26#include "llvm/Analysis/CaptureTracking.h" 27#include "llvm/Analysis/MemoryBuiltins.h" 28#include "llvm/Analysis/ValueTracking.h" 29#include "llvm/Target/TargetData.h" 30#include "llvm/ADT/SmallPtrSet.h" 31#include "llvm/ADT/SmallVector.h" 32#include "llvm/Support/ErrorHandling.h" 33#include <algorithm> 34using namespace llvm; 35 36//===----------------------------------------------------------------------===// 37// Useful predicates 38//===----------------------------------------------------------------------===// 39 40/// isKnownNonNull - Return true if we know that the specified value is never 41/// null. 42static bool isKnownNonNull(const Value *V) { 43 // Alloca never returns null, malloc might. 44 if (isa<AllocaInst>(V)) return true; 45 46 // A byval argument is never null. 47 if (const Argument *A = dyn_cast<Argument>(V)) 48 return A->hasByValAttr(); 49 50 // Global values are not null unless extern weak. 51 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 52 return !GV->hasExternalWeakLinkage(); 53 return false; 54} 55 56/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 57/// object that never escapes from the function. 58static bool isNonEscapingLocalObject(const Value *V) { 59 // If this is a local allocation, check to see if it escapes. 60 if (isa<AllocaInst>(V) || isNoAliasCall(V)) 61 // Set StoreCaptures to True so that we can assume in our callers that the 62 // pointer is not the result of a load instruction. Currently 63 // PointerMayBeCaptured doesn't have any special analysis for the 64 // StoreCaptures=false case; if it did, our callers could be refined to be 65 // more precise. 66 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 67 68 // If this is an argument that corresponds to a byval or noalias argument, 69 // then it has not escaped before entering the function. Check if it escapes 70 // inside the function. 71 if (const Argument *A = dyn_cast<Argument>(V)) 72 if (A->hasByValAttr() || A->hasNoAliasAttr()) { 73 // Don't bother analyzing arguments already known not to escape. 74 if (A->hasNoCaptureAttr()) 75 return true; 76 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 77 } 78 return false; 79} 80 81/// isEscapeSource - Return true if the pointer is one which would have 82/// been considered an escape by isNonEscapingLocalObject. 83static bool isEscapeSource(const Value *V) { 84 if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 85 return true; 86 87 // The load case works because isNonEscapingLocalObject considers all 88 // stores to be escapes (it passes true for the StoreCaptures argument 89 // to PointerMayBeCaptured). 90 if (isa<LoadInst>(V)) 91 return true; 92 93 return false; 94} 95 96/// isObjectSmallerThan - Return true if we can prove that the object specified 97/// by V is smaller than Size. 98static bool isObjectSmallerThan(const Value *V, unsigned Size, 99 const TargetData &TD) { 100 const Type *AccessTy; 101 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 102 AccessTy = GV->getType()->getElementType(); 103 } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 104 if (!AI->isArrayAllocation()) 105 AccessTy = AI->getType()->getElementType(); 106 else 107 return false; 108 } else if (const CallInst* CI = extractMallocCall(V)) { 109 if (!isArrayMalloc(V, &TD)) 110 // The size is the argument to the malloc call. 111 if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) 112 return (C->getZExtValue() < Size); 113 return false; 114 } else if (const Argument *A = dyn_cast<Argument>(V)) { 115 if (A->hasByValAttr()) 116 AccessTy = cast<PointerType>(A->getType())->getElementType(); 117 else 118 return false; 119 } else { 120 return false; 121 } 122 123 if (AccessTy->isSized()) 124 return TD.getTypeAllocSize(AccessTy) < Size; 125 return false; 126} 127 128//===----------------------------------------------------------------------===// 129// NoAA Pass 130//===----------------------------------------------------------------------===// 131 132namespace { 133 /// NoAA - This class implements the -no-aa pass, which always returns "I 134 /// don't know" for alias queries. NoAA is unlike other alias analysis 135 /// implementations, in that it does not chain to a previous analysis. As 136 /// such it doesn't follow many of the rules that other alias analyses must. 137 /// 138 struct NoAA : public ImmutablePass, public AliasAnalysis { 139 static char ID; // Class identification, replacement for typeinfo 140 NoAA() : ImmutablePass(&ID) {} 141 explicit NoAA(void *PID) : ImmutablePass(PID) { } 142 143 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 144 } 145 146 virtual void initializePass() { 147 TD = getAnalysisIfAvailable<TargetData>(); 148 } 149 150 virtual AliasResult alias(const Value *V1, unsigned V1Size, 151 const Value *V2, unsigned V2Size) { 152 return MayAlias; 153 } 154 155 virtual void getArgumentAccesses(Function *F, CallSite CS, 156 std::vector<PointerAccessInfo> &Info) { 157 llvm_unreachable("This method may not be called on this function!"); 158 } 159 160 virtual bool pointsToConstantMemory(const Value *P) { return false; } 161 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 162 return ModRef; 163 } 164 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 165 return ModRef; 166 } 167 168 virtual void deleteValue(Value *V) {} 169 virtual void copyValue(Value *From, Value *To) {} 170 171 /// getAdjustedAnalysisPointer - This method is used when a pass implements 172 /// an analysis interface through multiple inheritance. If needed, it should 173 /// override this to adjust the this pointer as needed for the specified pass 174 /// info. 175 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 176 if (PI->isPassID(&AliasAnalysis::ID)) 177 return (AliasAnalysis*)this; 178 return this; 179 } 180 }; 181} // End of anonymous namespace 182 183// Register this pass... 184char NoAA::ID = 0; 185static RegisterPass<NoAA> 186U("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 187 188// Declare that we implement the AliasAnalysis interface 189static RegisterAnalysisGroup<AliasAnalysis> V(U); 190 191ImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 192 193//===----------------------------------------------------------------------===// 194// BasicAliasAnalysis Pass 195//===----------------------------------------------------------------------===// 196 197#ifndef NDEBUG 198static const Function *getParent(const Value *V) { 199 if (const Instruction *inst = dyn_cast<Instruction>(V)) 200 return inst->getParent()->getParent(); 201 202 if (const Argument *arg = dyn_cast<Argument>(V)) 203 return arg->getParent(); 204 205 return NULL; 206} 207 208static bool notDifferentParent(const Value *O1, const Value *O2) { 209 210 const Function *F1 = getParent(O1); 211 const Function *F2 = getParent(O2); 212 213 return !F1 || !F2 || F1 == F2; 214} 215#endif 216 217namespace { 218 /// BasicAliasAnalysis - This is the default alias analysis implementation. 219 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 220 /// derives from the NoAA class. 221 struct BasicAliasAnalysis : public NoAA { 222 static char ID; // Class identification, replacement for typeinfo 223 BasicAliasAnalysis() : NoAA(&ID) {} 224 225 AliasResult alias(const Value *V1, unsigned V1Size, 226 const Value *V2, unsigned V2Size) { 227 assert(Visited.empty() && "Visited must be cleared after use!"); 228 assert(notDifferentParent(V1, V2) && 229 "BasicAliasAnalysis doesn't support interprocedural queries."); 230 AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size); 231 Visited.clear(); 232 return Alias; 233 } 234 235 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 236 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); 237 238 /// pointsToConstantMemory - Chase pointers until we find a (constant 239 /// global) or not. 240 bool pointsToConstantMemory(const Value *P); 241 242 /// getAdjustedAnalysisPointer - This method is used when a pass implements 243 /// an analysis interface through multiple inheritance. If needed, it should 244 /// override this to adjust the this pointer as needed for the specified pass 245 /// info. 246 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 247 if (PI->isPassID(&AliasAnalysis::ID)) 248 return (AliasAnalysis*)this; 249 return this; 250 } 251 252 private: 253 // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP(). 254 SmallPtrSet<const Value*, 16> Visited; 255 256 // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 257 // instruction against another. 258 AliasResult aliasGEP(const GEPOperator *V1, unsigned V1Size, 259 const Value *V2, unsigned V2Size, 260 const Value *UnderlyingV1, const Value *UnderlyingV2); 261 262 // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 263 // instruction against another. 264 AliasResult aliasPHI(const PHINode *PN, unsigned PNSize, 265 const Value *V2, unsigned V2Size); 266 267 /// aliasSelect - Disambiguate a Select instruction against another value. 268 AliasResult aliasSelect(const SelectInst *SI, unsigned SISize, 269 const Value *V2, unsigned V2Size); 270 271 AliasResult aliasCheck(const Value *V1, unsigned V1Size, 272 const Value *V2, unsigned V2Size); 273 }; 274} // End of anonymous namespace 275 276// Register this pass... 277char BasicAliasAnalysis::ID = 0; 278static RegisterPass<BasicAliasAnalysis> 279X("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 280 281// Declare that we implement the AliasAnalysis interface 282static RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 283 284ImmutablePass *llvm::createBasicAliasAnalysisPass() { 285 return new BasicAliasAnalysis(); 286} 287 288 289/// pointsToConstantMemory - Chase pointers until we find a (constant 290/// global) or not. 291bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 292 if (const GlobalVariable *GV = 293 dyn_cast<GlobalVariable>(P->getUnderlyingObject())) 294 // Note: this doesn't require GV to be "ODR" because it isn't legal for a 295 // global to be marked constant in some modules and non-constant in others. 296 // GV may even be a declaration, not a definition. 297 return GV->isConstant(); 298 return false; 299} 300 301 302/// getModRefInfo - Check to see if the specified callsite can clobber the 303/// specified memory object. Since we only look at local properties of this 304/// function, we really can't say much about this query. We do, however, use 305/// simple "address taken" analysis on local objects. 306AliasAnalysis::ModRefResult 307BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 308 assert(notDifferentParent(CS.getInstruction(), P) && 309 "AliasAnalysis query involving multiple functions!"); 310 311 const Value *Object = P->getUnderlyingObject(); 312 313 // If this is a tail call and P points to a stack location, we know that 314 // the tail call cannot access or modify the local stack. 315 // We cannot exclude byval arguments here; these belong to the caller of 316 // the current function not to the current function, and a tail callee 317 // may reference them. 318 if (isa<AllocaInst>(Object)) 319 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 320 if (CI->isTailCall()) 321 return NoModRef; 322 323 // If the pointer is to a locally allocated object that does not escape, 324 // then the call can not mod/ref the pointer unless the call takes the pointer 325 // as an argument, and itself doesn't capture it. 326 if (!isa<Constant>(Object) && CS.getInstruction() != Object && 327 isNonEscapingLocalObject(Object)) { 328 bool PassedAsArg = false; 329 unsigned ArgNo = 0; 330 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 331 CI != CE; ++CI, ++ArgNo) { 332 // Only look at the no-capture pointer arguments. 333 if (!(*CI)->getType()->isPointerTy() || 334 !CS.paramHasAttr(ArgNo+1, Attribute::NoCapture)) 335 continue; 336 337 // If this is a no-capture pointer argument, see if we can tell that it 338 // is impossible to alias the pointer we're checking. If not, we have to 339 // assume that the call could touch the pointer, even though it doesn't 340 // escape. 341 if (!isNoAlias(cast<Value>(CI), ~0U, P, ~0U)) { 342 PassedAsArg = true; 343 break; 344 } 345 } 346 347 if (!PassedAsArg) 348 return NoModRef; 349 } 350 351 // Finally, handle specific knowledge of intrinsics. 352 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 353 if (II == 0) 354 return AliasAnalysis::getModRefInfo(CS, P, Size); 355 356 switch (II->getIntrinsicID()) { 357 default: break; 358 case Intrinsic::memcpy: 359 case Intrinsic::memmove: { 360 unsigned Len = ~0U; 361 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 362 Len = LenCI->getZExtValue(); 363 Value *Dest = II->getArgOperand(0); 364 Value *Src = II->getArgOperand(1); 365 if (isNoAlias(Dest, Len, P, Size)) { 366 if (isNoAlias(Src, Len, P, Size)) 367 return NoModRef; 368 return Ref; 369 } 370 break; 371 } 372 case Intrinsic::memset: 373 // Since memset is 'accesses arguments' only, the AliasAnalysis base class 374 // will handle it for the variable length case. 375 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 376 unsigned Len = LenCI->getZExtValue(); 377 Value *Dest = II->getArgOperand(0); 378 if (isNoAlias(Dest, Len, P, Size)) 379 return NoModRef; 380 } 381 break; 382 case Intrinsic::atomic_cmp_swap: 383 case Intrinsic::atomic_swap: 384 case Intrinsic::atomic_load_add: 385 case Intrinsic::atomic_load_sub: 386 case Intrinsic::atomic_load_and: 387 case Intrinsic::atomic_load_nand: 388 case Intrinsic::atomic_load_or: 389 case Intrinsic::atomic_load_xor: 390 case Intrinsic::atomic_load_max: 391 case Intrinsic::atomic_load_min: 392 case Intrinsic::atomic_load_umax: 393 case Intrinsic::atomic_load_umin: 394 if (TD) { 395 Value *Op1 = II->getArgOperand(0); 396 unsigned Op1Size = TD->getTypeStoreSize(Op1->getType()); 397 if (isNoAlias(Op1, Op1Size, P, Size)) 398 return NoModRef; 399 } 400 break; 401 case Intrinsic::lifetime_start: 402 case Intrinsic::lifetime_end: 403 case Intrinsic::invariant_start: { 404 unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 405 if (isNoAlias(II->getArgOperand(1), PtrSize, P, Size)) 406 return NoModRef; 407 break; 408 } 409 case Intrinsic::invariant_end: { 410 unsigned PtrSize = cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 411 if (isNoAlias(II->getArgOperand(2), PtrSize, P, Size)) 412 return NoModRef; 413 break; 414 } 415 } 416 417 // The AliasAnalysis base class has some smarts, lets use them. 418 return AliasAnalysis::getModRefInfo(CS, P, Size); 419} 420 421 422AliasAnalysis::ModRefResult 423BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 424 // If CS1 or CS2 are readnone, they don't interact. 425 ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); 426 if (CS1B == DoesNotAccessMemory) return NoModRef; 427 428 ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); 429 if (CS2B == DoesNotAccessMemory) return NoModRef; 430 431 // If they both only read from memory, just return ref. 432 if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 433 return Ref; 434 435 // Otherwise, fall back to NoAA (mod+ref). 436 return NoAA::getModRefInfo(CS1, CS2); 437} 438 439/// GetIndiceDifference - Dest and Src are the variable indices from two 440/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 441/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 442/// difference between the two pointers. 443static void GetIndiceDifference( 444 SmallVectorImpl<std::pair<const Value*, int64_t> > &Dest, 445 const SmallVectorImpl<std::pair<const Value*, int64_t> > &Src) { 446 if (Src.empty()) return; 447 448 for (unsigned i = 0, e = Src.size(); i != e; ++i) { 449 const Value *V = Src[i].first; 450 int64_t Scale = Src[i].second; 451 452 // Find V in Dest. This is N^2, but pointer indices almost never have more 453 // than a few variable indexes. 454 for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 455 if (Dest[j].first != V) continue; 456 457 // If we found it, subtract off Scale V's from the entry in Dest. If it 458 // goes to zero, remove the entry. 459 if (Dest[j].second != Scale) 460 Dest[j].second -= Scale; 461 else 462 Dest.erase(Dest.begin()+j); 463 Scale = 0; 464 break; 465 } 466 467 // If we didn't consume this entry, add it to the end of the Dest list. 468 if (Scale) 469 Dest.push_back(std::make_pair(V, -Scale)); 470 } 471} 472 473/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 474/// against another pointer. We know that V1 is a GEP, but we don't know 475/// anything about V2. UnderlyingV1 is GEP1->getUnderlyingObject(), 476/// UnderlyingV2 is the same for V2. 477/// 478AliasAnalysis::AliasResult 479BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, 480 const Value *V2, unsigned V2Size, 481 const Value *UnderlyingV1, 482 const Value *UnderlyingV2) { 483 // If this GEP has been visited before, we're on a use-def cycle. 484 // Such cycles are only valid when PHI nodes are involved or in unreachable 485 // code. The visitPHI function catches cycles containing PHIs, but there 486 // could still be a cycle without PHIs in unreachable code. 487 if (!Visited.insert(GEP1)) 488 return MayAlias; 489 490 int64_t GEP1BaseOffset; 491 SmallVector<std::pair<const Value*, int64_t>, 4> GEP1VariableIndices; 492 493 // If we have two gep instructions with must-alias'ing base pointers, figure 494 // out if the indexes to the GEP tell us anything about the derived pointer. 495 if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 496 // Do the base pointers alias? 497 AliasResult BaseAlias = aliasCheck(UnderlyingV1, ~0U, UnderlyingV2, ~0U); 498 499 // If we get a No or May, then return it immediately, no amount of analysis 500 // will improve this situation. 501 if (BaseAlias != MustAlias) return BaseAlias; 502 503 // Otherwise, we have a MustAlias. Since the base pointers alias each other 504 // exactly, see if the computed offset from the common pointer tells us 505 // about the relation of the resulting pointer. 506 const Value *GEP1BasePtr = 507 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 508 509 int64_t GEP2BaseOffset; 510 SmallVector<std::pair<const Value*, int64_t>, 4> GEP2VariableIndices; 511 const Value *GEP2BasePtr = 512 DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 513 514 // If DecomposeGEPExpression isn't able to look all the way through the 515 // addressing operation, we must not have TD and this is too complex for us 516 // to handle without it. 517 if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 518 assert(TD == 0 && 519 "DecomposeGEPExpression and getUnderlyingObject disagree!"); 520 return MayAlias; 521 } 522 523 // Subtract the GEP2 pointer from the GEP1 pointer to find out their 524 // symbolic difference. 525 GEP1BaseOffset -= GEP2BaseOffset; 526 GetIndiceDifference(GEP1VariableIndices, GEP2VariableIndices); 527 528 } else { 529 // Check to see if these two pointers are related by the getelementptr 530 // instruction. If one pointer is a GEP with a non-zero index of the other 531 // pointer, we know they cannot alias. 532 533 // If both accesses are unknown size, we can't do anything useful here. 534 if (V1Size == ~0U && V2Size == ~0U) 535 return MayAlias; 536 537 AliasResult R = aliasCheck(UnderlyingV1, ~0U, V2, V2Size); 538 if (R != MustAlias) 539 // If V2 may alias GEP base pointer, conservatively returns MayAlias. 540 // If V2 is known not to alias GEP base pointer, then the two values 541 // cannot alias per GEP semantics: "A pointer value formed from a 542 // getelementptr instruction is associated with the addresses associated 543 // with the first operand of the getelementptr". 544 return R; 545 546 const Value *GEP1BasePtr = 547 DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 548 549 // If DecomposeGEPExpression isn't able to look all the way through the 550 // addressing operation, we must not have TD and this is too complex for us 551 // to handle without it. 552 if (GEP1BasePtr != UnderlyingV1) { 553 assert(TD == 0 && 554 "DecomposeGEPExpression and getUnderlyingObject disagree!"); 555 return MayAlias; 556 } 557 } 558 559 // In the two GEP Case, if there is no difference in the offsets of the 560 // computed pointers, the resultant pointers are a must alias. This 561 // hapens when we have two lexically identical GEP's (for example). 562 // 563 // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 564 // must aliases the GEP, the end result is a must alias also. 565 if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 566 return MustAlias; 567 568 // If we have a known constant offset, see if this offset is larger than the 569 // access size being queried. If so, and if no variable indices can remove 570 // pieces of this constant, then we know we have a no-alias. For example, 571 // &A[100] != &A. 572 573 // In order to handle cases like &A[100][i] where i is an out of range 574 // subscript, we have to ignore all constant offset pieces that are a multiple 575 // of a scaled index. Do this by removing constant offsets that are a 576 // multiple of any of our variable indices. This allows us to transform 577 // things like &A[i][1] because i has a stride of (e.g.) 8 bytes but the 1 578 // provides an offset of 4 bytes (assuming a <= 4 byte access). 579 for (unsigned i = 0, e = GEP1VariableIndices.size(); 580 i != e && GEP1BaseOffset;++i) 581 if (int64_t RemovedOffset = GEP1BaseOffset/GEP1VariableIndices[i].second) 582 GEP1BaseOffset -= RemovedOffset*GEP1VariableIndices[i].second; 583 584 // If our known offset is bigger than the access size, we know we don't have 585 // an alias. 586 if (GEP1BaseOffset) { 587 if (GEP1BaseOffset >= (int64_t)V2Size || 588 GEP1BaseOffset <= -(int64_t)V1Size) 589 return NoAlias; 590 } 591 592 return MayAlias; 593} 594 595/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 596/// instruction against another. 597AliasAnalysis::AliasResult 598BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, 599 const Value *V2, unsigned V2Size) { 600 // If this select has been visited before, we're on a use-def cycle. 601 // Such cycles are only valid when PHI nodes are involved or in unreachable 602 // code. The visitPHI function catches cycles containing PHIs, but there 603 // could still be a cycle without PHIs in unreachable code. 604 if (!Visited.insert(SI)) 605 return MayAlias; 606 607 // If the values are Selects with the same condition, we can do a more precise 608 // check: just check for aliases between the values on corresponding arms. 609 if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 610 if (SI->getCondition() == SI2->getCondition()) { 611 AliasResult Alias = 612 aliasCheck(SI->getTrueValue(), SISize, 613 SI2->getTrueValue(), V2Size); 614 if (Alias == MayAlias) 615 return MayAlias; 616 AliasResult ThisAlias = 617 aliasCheck(SI->getFalseValue(), SISize, 618 SI2->getFalseValue(), V2Size); 619 if (ThisAlias != Alias) 620 return MayAlias; 621 return Alias; 622 } 623 624 // If both arms of the Select node NoAlias or MustAlias V2, then returns 625 // NoAlias / MustAlias. Otherwise, returns MayAlias. 626 AliasResult Alias = 627 aliasCheck(V2, V2Size, SI->getTrueValue(), SISize); 628 if (Alias == MayAlias) 629 return MayAlias; 630 631 // If V2 is visited, the recursive case will have been caught in the 632 // above aliasCheck call, so these subsequent calls to aliasCheck 633 // don't need to assume that V2 is being visited recursively. 634 Visited.erase(V2); 635 636 AliasResult ThisAlias = 637 aliasCheck(V2, V2Size, SI->getFalseValue(), SISize); 638 if (ThisAlias != Alias) 639 return MayAlias; 640 return Alias; 641} 642 643// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 644// against another. 645AliasAnalysis::AliasResult 646BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, 647 const Value *V2, unsigned V2Size) { 648 // The PHI node has already been visited, avoid recursion any further. 649 if (!Visited.insert(PN)) 650 return MayAlias; 651 652 // If the values are PHIs in the same block, we can do a more precise 653 // as well as efficient check: just check for aliases between the values 654 // on corresponding edges. 655 if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 656 if (PN2->getParent() == PN->getParent()) { 657 AliasResult Alias = 658 aliasCheck(PN->getIncomingValue(0), PNSize, 659 PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 660 V2Size); 661 if (Alias == MayAlias) 662 return MayAlias; 663 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 664 AliasResult ThisAlias = 665 aliasCheck(PN->getIncomingValue(i), PNSize, 666 PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 667 V2Size); 668 if (ThisAlias != Alias) 669 return MayAlias; 670 } 671 return Alias; 672 } 673 674 SmallPtrSet<Value*, 4> UniqueSrc; 675 SmallVector<Value*, 4> V1Srcs; 676 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 677 Value *PV1 = PN->getIncomingValue(i); 678 if (isa<PHINode>(PV1)) 679 // If any of the source itself is a PHI, return MayAlias conservatively 680 // to avoid compile time explosion. The worst possible case is if both 681 // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 682 // and 'n' are the number of PHI sources. 683 return MayAlias; 684 if (UniqueSrc.insert(PV1)) 685 V1Srcs.push_back(PV1); 686 } 687 688 AliasResult Alias = aliasCheck(V2, V2Size, V1Srcs[0], PNSize); 689 // Early exit if the check of the first PHI source against V2 is MayAlias. 690 // Other results are not possible. 691 if (Alias == MayAlias) 692 return MayAlias; 693 694 // If all sources of the PHI node NoAlias or MustAlias V2, then returns 695 // NoAlias / MustAlias. Otherwise, returns MayAlias. 696 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 697 Value *V = V1Srcs[i]; 698 699 // If V2 is visited, the recursive case will have been caught in the 700 // above aliasCheck call, so these subsequent calls to aliasCheck 701 // don't need to assume that V2 is being visited recursively. 702 Visited.erase(V2); 703 704 AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize); 705 if (ThisAlias != Alias || ThisAlias == MayAlias) 706 return MayAlias; 707 } 708 709 return Alias; 710} 711 712// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 713// such as array references. 714// 715AliasAnalysis::AliasResult 716BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, 717 const Value *V2, unsigned V2Size) { 718 // If either of the memory references is empty, it doesn't matter what the 719 // pointer values are. 720 if (V1Size == 0 || V2Size == 0) 721 return NoAlias; 722 723 // Strip off any casts if they exist. 724 V1 = V1->stripPointerCasts(); 725 V2 = V2->stripPointerCasts(); 726 727 // Are we checking for alias of the same value? 728 if (V1 == V2) return MustAlias; 729 730 if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 731 return NoAlias; // Scalars cannot alias each other 732 733 // Figure out what objects these things are pointing to if we can. 734 const Value *O1 = V1->getUnderlyingObject(); 735 const Value *O2 = V2->getUnderlyingObject(); 736 737 // Null values in the default address space don't point to any object, so they 738 // don't alias any other pointer. 739 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 740 if (CPN->getType()->getAddressSpace() == 0) 741 return NoAlias; 742 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 743 if (CPN->getType()->getAddressSpace() == 0) 744 return NoAlias; 745 746 if (O1 != O2) { 747 // If V1/V2 point to two different objects we know that we have no alias. 748 if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 749 return NoAlias; 750 751 // Constant pointers can't alias with non-const isIdentifiedObject objects. 752 if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 753 (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 754 return NoAlias; 755 756 // Arguments can't alias with local allocations or noalias calls 757 // in the same function. 758 if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 759 (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) 760 return NoAlias; 761 762 // Most objects can't alias null. 763 if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 764 (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 765 return NoAlias; 766 767 // If one pointer is the result of a call/invoke or load and the other is a 768 // non-escaping local object within the same function, then we know the 769 // object couldn't escape to a point where the call could return it. 770 // 771 // Note that if the pointers are in different functions, there are a 772 // variety of complications. A call with a nocapture argument may still 773 // temporary store the nocapture argument's value in a temporary memory 774 // location if that memory location doesn't escape. Or it may pass a 775 // nocapture value to other functions as long as they don't capture it. 776 if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 777 return NoAlias; 778 if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 779 return NoAlias; 780 } 781 782 // If the size of one access is larger than the entire object on the other 783 // side, then we know such behavior is undefined and can assume no alias. 784 if (TD) 785 if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, *TD)) || 786 (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, *TD))) 787 return NoAlias; 788 789 // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 790 // GEP can't simplify, we don't even look at the PHI cases. 791 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 792 std::swap(V1, V2); 793 std::swap(V1Size, V2Size); 794 std::swap(O1, O2); 795 } 796 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) 797 return aliasGEP(GV1, V1Size, V2, V2Size, O1, O2); 798 799 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 800 std::swap(V1, V2); 801 std::swap(V1Size, V2Size); 802 } 803 if (const PHINode *PN = dyn_cast<PHINode>(V1)) 804 return aliasPHI(PN, V1Size, V2, V2Size); 805 806 if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 807 std::swap(V1, V2); 808 std::swap(V1Size, V2Size); 809 } 810 if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) 811 return aliasSelect(S1, V1Size, V2, V2Size); 812 813 return MayAlias; 814} 815 816// Make sure that anything that uses AliasAnalysis pulls in this file. 817DEFINING_FILE_FOR(BasicAliasAnalysis) 818