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