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