1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 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 implements the generic AliasAnalysis interface which is used as the 11 // common interface used by all clients and implementations of alias analysis. 12 // 13 // This file also implements the default version of the AliasAnalysis interface 14 // that is to be used when no other implementation is specified. This does some 15 // simple tests that detect obvious cases: two different global pointers cannot 16 // alias, a global cannot alias a malloc, two different mallocs cannot alias, 17 // etc. 18 // 19 // This alias analysis implementation really isn't very good for anything, but 20 // it is very fast, and makes a nice clean default implementation. Because it 21 // handles lots of little corner cases, other, more complex, alias analysis 22 // implementations may choose to rely on this pass to resolve these simple and 23 // easy cases. 24 // 25 //===----------------------------------------------------------------------===// 26 27 #include "llvm/Analysis/AliasAnalysis.h" 28 #include "llvm/Analysis/CFG.h" 29 #include "llvm/Analysis/CaptureTracking.h" 30 #include "llvm/Analysis/ValueTracking.h" 31 #include "llvm/IR/BasicBlock.h" 32 #include "llvm/IR/DataLayout.h" 33 #include "llvm/IR/Dominators.h" 34 #include "llvm/IR/Function.h" 35 #include "llvm/IR/Instructions.h" 36 #include "llvm/IR/IntrinsicInst.h" 37 #include "llvm/IR/LLVMContext.h" 38 #include "llvm/IR/Type.h" 39 #include "llvm/Pass.h" 40 #include "llvm/Target/TargetLibraryInfo.h" 41 using namespace llvm; 42 43 // Register the AliasAnalysis interface, providing a nice name to refer to. 44 INITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 45 char AliasAnalysis::ID = 0; 46 47 //===----------------------------------------------------------------------===// 48 // Default chaining methods 49 //===----------------------------------------------------------------------===// 50 51 AliasAnalysis::AliasResult 52 AliasAnalysis::alias(const Location &LocA, const Location &LocB) { 53 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54 return AA->alias(LocA, LocB); 55 } 56 57 bool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 58 bool OrLocal) { 59 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 60 return AA->pointsToConstantMemory(Loc, OrLocal); 61 } 62 63 AliasAnalysis::Location 64 AliasAnalysis::getArgLocation(ImmutableCallSite CS, unsigned ArgIdx, 65 AliasAnalysis::ModRefResult &Mask) { 66 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 67 return AA->getArgLocation(CS, ArgIdx, Mask); 68 } 69 70 void AliasAnalysis::deleteValue(Value *V) { 71 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 72 AA->deleteValue(V); 73 } 74 75 void AliasAnalysis::copyValue(Value *From, Value *To) { 76 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 77 AA->copyValue(From, To); 78 } 79 80 void AliasAnalysis::addEscapingUse(Use &U) { 81 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 82 AA->addEscapingUse(U); 83 } 84 85 86 AliasAnalysis::ModRefResult 87 AliasAnalysis::getModRefInfo(ImmutableCallSite CS, 88 const Location &Loc) { 89 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 90 91 ModRefBehavior MRB = getModRefBehavior(CS); 92 if (MRB == DoesNotAccessMemory) 93 return NoModRef; 94 95 ModRefResult Mask = ModRef; 96 if (onlyReadsMemory(MRB)) 97 Mask = Ref; 98 99 if (onlyAccessesArgPointees(MRB)) { 100 bool doesAlias = false; 101 ModRefResult AllArgsMask = NoModRef; 102 if (doesAccessArgPointees(MRB)) { 103 for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 104 AI != AE; ++AI) { 105 const Value *Arg = *AI; 106 if (!Arg->getType()->isPointerTy()) 107 continue; 108 ModRefResult ArgMask; 109 Location CSLoc = 110 getArgLocation(CS, (unsigned) std::distance(CS.arg_begin(), AI), 111 ArgMask); 112 if (!isNoAlias(CSLoc, Loc)) { 113 doesAlias = true; 114 AllArgsMask = ModRefResult(AllArgsMask | ArgMask); 115 } 116 } 117 } 118 if (!doesAlias) 119 return NoModRef; 120 Mask = ModRefResult(Mask & AllArgsMask); 121 } 122 123 // If Loc is a constant memory location, the call definitely could not 124 // modify the memory location. 125 if ((Mask & Mod) && pointsToConstantMemory(Loc)) 126 Mask = ModRefResult(Mask & ~Mod); 127 128 // If this is the end of the chain, don't forward. 129 if (!AA) return Mask; 130 131 // Otherwise, fall back to the next AA in the chain. But we can merge 132 // in any mask we've managed to compute. 133 return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 134 } 135 136 AliasAnalysis::ModRefResult 137 AliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 138 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 139 140 // If CS1 or CS2 are readnone, they don't interact. 141 ModRefBehavior CS1B = getModRefBehavior(CS1); 142 if (CS1B == DoesNotAccessMemory) return NoModRef; 143 144 ModRefBehavior CS2B = getModRefBehavior(CS2); 145 if (CS2B == DoesNotAccessMemory) return NoModRef; 146 147 // If they both only read from memory, there is no dependence. 148 if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 149 return NoModRef; 150 151 AliasAnalysis::ModRefResult Mask = ModRef; 152 153 // If CS1 only reads memory, the only dependence on CS2 can be 154 // from CS1 reading memory written by CS2. 155 if (onlyReadsMemory(CS1B)) 156 Mask = ModRefResult(Mask & Ref); 157 158 // If CS2 only access memory through arguments, accumulate the mod/ref 159 // information from CS1's references to the memory referenced by 160 // CS2's arguments. 161 if (onlyAccessesArgPointees(CS2B)) { 162 AliasAnalysis::ModRefResult R = NoModRef; 163 if (doesAccessArgPointees(CS2B)) { 164 for (ImmutableCallSite::arg_iterator 165 I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 166 const Value *Arg = *I; 167 if (!Arg->getType()->isPointerTy()) 168 continue; 169 ModRefResult ArgMask; 170 Location CS2Loc = 171 getArgLocation(CS2, (unsigned) std::distance(CS2.arg_begin(), I), 172 ArgMask); 173 // ArgMask indicates what CS2 might do to CS2Loc, and the dependence of 174 // CS1 on that location is the inverse. 175 if (ArgMask == Mod) 176 ArgMask = ModRef; 177 else if (ArgMask == Ref) 178 ArgMask = Mod; 179 180 R = ModRefResult((R | (getModRefInfo(CS1, CS2Loc) & ArgMask)) & Mask); 181 if (R == Mask) 182 break; 183 } 184 } 185 return R; 186 } 187 188 // If CS1 only accesses memory through arguments, check if CS2 references 189 // any of the memory referenced by CS1's arguments. If not, return NoModRef. 190 if (onlyAccessesArgPointees(CS1B)) { 191 AliasAnalysis::ModRefResult R = NoModRef; 192 if (doesAccessArgPointees(CS1B)) { 193 for (ImmutableCallSite::arg_iterator 194 I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 195 const Value *Arg = *I; 196 if (!Arg->getType()->isPointerTy()) 197 continue; 198 ModRefResult ArgMask; 199 Location CS1Loc = 200 getArgLocation(CS1, (unsigned) std::distance(CS1.arg_begin(), I), 201 ArgMask); 202 if ((getModRefInfo(CS2, CS1Loc) & ArgMask) != NoModRef) { 203 R = Mask; 204 break; 205 } 206 } 207 } 208 if (R == NoModRef) 209 return R; 210 } 211 212 // If this is the end of the chain, don't forward. 213 if (!AA) return Mask; 214 215 // Otherwise, fall back to the next AA in the chain. But we can merge 216 // in any mask we've managed to compute. 217 return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 218 } 219 220 AliasAnalysis::ModRefBehavior 221 AliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 222 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 223 224 ModRefBehavior Min = UnknownModRefBehavior; 225 226 // Call back into the alias analysis with the other form of getModRefBehavior 227 // to see if it can give a better response. 228 if (const Function *F = CS.getCalledFunction()) 229 Min = getModRefBehavior(F); 230 231 // If this is the end of the chain, don't forward. 232 if (!AA) return Min; 233 234 // Otherwise, fall back to the next AA in the chain. But we can merge 235 // in any result we've managed to compute. 236 return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 237 } 238 239 AliasAnalysis::ModRefBehavior 240 AliasAnalysis::getModRefBehavior(const Function *F) { 241 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 242 return AA->getModRefBehavior(F); 243 } 244 245 //===----------------------------------------------------------------------===// 246 // AliasAnalysis non-virtual helper method implementation 247 //===----------------------------------------------------------------------===// 248 249 AliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 250 return Location(LI->getPointerOperand(), 251 getTypeStoreSize(LI->getType()), 252 LI->getMetadata(LLVMContext::MD_tbaa)); 253 } 254 255 AliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 256 return Location(SI->getPointerOperand(), 257 getTypeStoreSize(SI->getValueOperand()->getType()), 258 SI->getMetadata(LLVMContext::MD_tbaa)); 259 } 260 261 AliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 262 return Location(VI->getPointerOperand(), 263 UnknownSize, 264 VI->getMetadata(LLVMContext::MD_tbaa)); 265 } 266 267 AliasAnalysis::Location 268 AliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 269 return Location(CXI->getPointerOperand(), 270 getTypeStoreSize(CXI->getCompareOperand()->getType()), 271 CXI->getMetadata(LLVMContext::MD_tbaa)); 272 } 273 274 AliasAnalysis::Location 275 AliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 276 return Location(RMWI->getPointerOperand(), 277 getTypeStoreSize(RMWI->getValOperand()->getType()), 278 RMWI->getMetadata(LLVMContext::MD_tbaa)); 279 } 280 281 AliasAnalysis::Location 282 AliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 283 uint64_t Size = UnknownSize; 284 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 285 Size = C->getValue().getZExtValue(); 286 287 // memcpy/memmove can have TBAA tags. For memcpy, they apply 288 // to both the source and the destination. 289 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 290 291 return Location(MTI->getRawSource(), Size, TBAATag); 292 } 293 294 AliasAnalysis::Location 295 AliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 296 uint64_t Size = UnknownSize; 297 if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 298 Size = C->getValue().getZExtValue(); 299 300 // memcpy/memmove can have TBAA tags. For memcpy, they apply 301 // to both the source and the destination. 302 MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 303 304 return Location(MTI->getRawDest(), Size, TBAATag); 305 } 306 307 308 309 AliasAnalysis::ModRefResult 310 AliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 311 // Be conservative in the face of volatile/atomic. 312 if (!L->isUnordered()) 313 return ModRef; 314 315 // If the load address doesn't alias the given address, it doesn't read 316 // or write the specified memory. 317 if (!alias(getLocation(L), Loc)) 318 return NoModRef; 319 320 // Otherwise, a load just reads. 321 return Ref; 322 } 323 324 AliasAnalysis::ModRefResult 325 AliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 326 // Be conservative in the face of volatile/atomic. 327 if (!S->isUnordered()) 328 return ModRef; 329 330 // If the store address cannot alias the pointer in question, then the 331 // specified memory cannot be modified by the store. 332 if (!alias(getLocation(S), Loc)) 333 return NoModRef; 334 335 // If the pointer is a pointer to constant memory, then it could not have been 336 // modified by this store. 337 if (pointsToConstantMemory(Loc)) 338 return NoModRef; 339 340 // Otherwise, a store just writes. 341 return Mod; 342 } 343 344 AliasAnalysis::ModRefResult 345 AliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 346 // If the va_arg address cannot alias the pointer in question, then the 347 // specified memory cannot be accessed by the va_arg. 348 if (!alias(getLocation(V), Loc)) 349 return NoModRef; 350 351 // If the pointer is a pointer to constant memory, then it could not have been 352 // modified by this va_arg. 353 if (pointsToConstantMemory(Loc)) 354 return NoModRef; 355 356 // Otherwise, a va_arg reads and writes. 357 return ModRef; 358 } 359 360 AliasAnalysis::ModRefResult 361 AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 362 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 363 if (CX->getSuccessOrdering() > Monotonic) 364 return ModRef; 365 366 // If the cmpxchg address does not alias the location, it does not access it. 367 if (!alias(getLocation(CX), Loc)) 368 return NoModRef; 369 370 return ModRef; 371 } 372 373 AliasAnalysis::ModRefResult 374 AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 375 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 376 if (RMW->getOrdering() > Monotonic) 377 return ModRef; 378 379 // If the atomicrmw address does not alias the location, it does not access it. 380 if (!alias(getLocation(RMW), Loc)) 381 return NoModRef; 382 383 return ModRef; 384 } 385 386 namespace { 387 /// Only find pointer captures which happen before the given instruction. Uses 388 /// the dominator tree to determine whether one instruction is before another. 389 /// Only support the case where the Value is defined in the same basic block 390 /// as the given instruction and the use. 391 struct CapturesBefore : public CaptureTracker { 392 CapturesBefore(const Instruction *I, DominatorTree *DT) 393 : BeforeHere(I), DT(DT), Captured(false) {} 394 395 void tooManyUses() override { Captured = true; } 396 397 bool shouldExplore(const Use *U) override { 398 Instruction *I = cast<Instruction>(U->getUser()); 399 BasicBlock *BB = I->getParent(); 400 // We explore this usage only if the usage can reach "BeforeHere". 401 // If use is not reachable from entry, there is no need to explore. 402 if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 403 return false; 404 // If the value is defined in the same basic block as use and BeforeHere, 405 // there is no need to explore the use if BeforeHere dominates use. 406 // Check whether there is a path from I to BeforeHere. 407 if (BeforeHere != I && DT->dominates(BeforeHere, I) && 408 !isPotentiallyReachable(I, BeforeHere, DT)) 409 return false; 410 return true; 411 } 412 413 bool captured(const Use *U) override { 414 Instruction *I = cast<Instruction>(U->getUser()); 415 BasicBlock *BB = I->getParent(); 416 // Same logic as in shouldExplore. 417 if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 418 return false; 419 if (BeforeHere != I && DT->dominates(BeforeHere, I) && 420 !isPotentiallyReachable(I, BeforeHere, DT)) 421 return false; 422 Captured = true; 423 return true; 424 } 425 426 const Instruction *BeforeHere; 427 DominatorTree *DT; 428 429 bool Captured; 430 }; 431 } 432 433 // FIXME: this is really just shoring-up a deficiency in alias analysis. 434 // BasicAA isn't willing to spend linear time determining whether an alloca 435 // was captured before or after this particular call, while we are. However, 436 // with a smarter AA in place, this test is just wasting compile time. 437 AliasAnalysis::ModRefResult 438 AliasAnalysis::callCapturesBefore(const Instruction *I, 439 const AliasAnalysis::Location &MemLoc, 440 DominatorTree *DT) { 441 if (!DT || !DL) return AliasAnalysis::ModRef; 442 443 const Value *Object = GetUnderlyingObject(MemLoc.Ptr, DL); 444 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 445 isa<Constant>(Object)) 446 return AliasAnalysis::ModRef; 447 448 ImmutableCallSite CS(I); 449 if (!CS.getInstruction() || CS.getInstruction() == Object) 450 return AliasAnalysis::ModRef; 451 452 CapturesBefore CB(I, DT); 453 llvm::PointerMayBeCaptured(Object, &CB); 454 if (CB.Captured) 455 return AliasAnalysis::ModRef; 456 457 unsigned ArgNo = 0; 458 AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef; 459 for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 460 CI != CE; ++CI, ++ArgNo) { 461 // Only look at the no-capture or byval pointer arguments. If this 462 // pointer were passed to arguments that were neither of these, then it 463 // couldn't be no-capture. 464 if (!(*CI)->getType()->isPointerTy() || 465 (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 466 continue; 467 468 // If this is a no-capture pointer argument, see if we can tell that it 469 // is impossible to alias the pointer we're checking. If not, we have to 470 // assume that the call could touch the pointer, even though it doesn't 471 // escape. 472 if (isNoAlias(AliasAnalysis::Location(*CI), 473 AliasAnalysis::Location(Object))) 474 continue; 475 if (CS.doesNotAccessMemory(ArgNo)) 476 continue; 477 if (CS.onlyReadsMemory(ArgNo)) { 478 R = AliasAnalysis::Ref; 479 continue; 480 } 481 return AliasAnalysis::ModRef; 482 } 483 return R; 484 } 485 486 // AliasAnalysis destructor: DO NOT move this to the header file for 487 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on 488 // the AliasAnalysis.o file in the current .a file, causing alias analysis 489 // support to not be included in the tool correctly! 490 // 491 AliasAnalysis::~AliasAnalysis() {} 492 493 /// InitializeAliasAnalysis - Subclasses must call this method to initialize the 494 /// AliasAnalysis interface before any other methods are called. 495 /// 496 void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 497 DataLayoutPass *DLP = P->getAnalysisIfAvailable<DataLayoutPass>(); 498 DL = DLP ? &DLP->getDataLayout() : nullptr; 499 TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 500 AA = &P->getAnalysis<AliasAnalysis>(); 501 } 502 503 // getAnalysisUsage - All alias analysis implementations should invoke this 504 // directly (using AliasAnalysis::getAnalysisUsage(AU)). 505 void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 506 AU.addRequired<AliasAnalysis>(); // All AA's chain 507 } 508 509 /// getTypeStoreSize - Return the DataLayout store size for the given type, 510 /// if known, or a conservative value otherwise. 511 /// 512 uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 513 return DL ? DL->getTypeStoreSize(Ty) : UnknownSize; 514 } 515 516 /// canBasicBlockModify - Return true if it is possible for execution of the 517 /// specified basic block to modify the value pointed to by Ptr. 518 /// 519 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 520 const Location &Loc) { 521 return canInstructionRangeModify(BB.front(), BB.back(), Loc); 522 } 523 524 /// canInstructionRangeModify - Return true if it is possible for the execution 525 /// of the specified instructions to modify the value pointed to by Ptr. The 526 /// instructions to consider are all of the instructions in the range of [I1,I2] 527 /// INCLUSIVE. I1 and I2 must be in the same basic block. 528 /// 529 bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 530 const Instruction &I2, 531 const Location &Loc) { 532 assert(I1.getParent() == I2.getParent() && 533 "Instructions not in same basic block!"); 534 BasicBlock::const_iterator I = &I1; 535 BasicBlock::const_iterator E = &I2; 536 ++E; // Convert from inclusive to exclusive range. 537 538 for (; I != E; ++I) // Check every instruction in range 539 if (getModRefInfo(I, Loc) & Mod) 540 return true; 541 return false; 542 } 543 544 /// isNoAliasCall - Return true if this pointer is returned by a noalias 545 /// function. 546 bool llvm::isNoAliasCall(const Value *V) { 547 if (isa<CallInst>(V) || isa<InvokeInst>(V)) 548 return ImmutableCallSite(cast<Instruction>(V)) 549 .paramHasAttr(0, Attribute::NoAlias); 550 return false; 551 } 552 553 /// isNoAliasArgument - Return true if this is an argument with the noalias 554 /// attribute. 555 bool llvm::isNoAliasArgument(const Value *V) 556 { 557 if (const Argument *A = dyn_cast<Argument>(V)) 558 return A->hasNoAliasAttr(); 559 return false; 560 } 561 562 /// isIdentifiedObject - Return true if this pointer refers to a distinct and 563 /// identifiable object. This returns true for: 564 /// Global Variables and Functions (but not Global Aliases) 565 /// Allocas and Mallocs 566 /// ByVal and NoAlias Arguments 567 /// NoAlias returns 568 /// 569 bool llvm::isIdentifiedObject(const Value *V) { 570 if (isa<AllocaInst>(V)) 571 return true; 572 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 573 return true; 574 if (isNoAliasCall(V)) 575 return true; 576 if (const Argument *A = dyn_cast<Argument>(V)) 577 return A->hasNoAliasAttr() || A->hasByValAttr(); 578 return false; 579 } 580