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