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