AliasAnalysis.cpp revision 252723
1193323Sed//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the generic AliasAnalysis interface which is used as the 11193323Sed// common interface used by all clients and implementations of alias analysis. 12193323Sed// 13193323Sed// This file also implements the default version of the AliasAnalysis interface 14193323Sed// that is to be used when no other implementation is specified. This does some 15193323Sed// simple tests that detect obvious cases: two different global pointers cannot 16193323Sed// alias, a global cannot alias a malloc, two different mallocs cannot alias, 17193323Sed// etc. 18193323Sed// 19193323Sed// This alias analysis implementation really isn't very good for anything, but 20193323Sed// it is very fast, and makes a nice clean default implementation. Because it 21193323Sed// handles lots of little corner cases, other, more complex, alias analysis 22193323Sed// implementations may choose to rely on this pass to resolve these simple and 23193323Sed// easy cases. 24193323Sed// 25193323Sed//===----------------------------------------------------------------------===// 26193323Sed 27193323Sed#include "llvm/Analysis/AliasAnalysis.h" 28245431Sdim#include "llvm/Analysis/CaptureTracking.h" 29245431Sdim#include "llvm/Analysis/Dominators.h" 30245431Sdim#include "llvm/Analysis/ValueTracking.h" 31252723Sdim#include "llvm/IR/BasicBlock.h" 32252723Sdim#include "llvm/IR/DataLayout.h" 33252723Sdim#include "llvm/IR/Function.h" 34252723Sdim#include "llvm/IR/Instructions.h" 35252723Sdim#include "llvm/IR/IntrinsicInst.h" 36252723Sdim#include "llvm/IR/LLVMContext.h" 37252723Sdim#include "llvm/IR/Type.h" 38193323Sed#include "llvm/Pass.h" 39245431Sdim#include "llvm/Target/TargetLibraryInfo.h" 40193323Sedusing namespace llvm; 41193323Sed 42193323Sed// Register the AliasAnalysis interface, providing a nice name to refer to. 43218893SdimINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 44193323Sedchar AliasAnalysis::ID = 0; 45193323Sed 46193323Sed//===----------------------------------------------------------------------===// 47193323Sed// Default chaining methods 48193323Sed//===----------------------------------------------------------------------===// 49193323Sed 50193323SedAliasAnalysis::AliasResult 51218893SdimAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 52193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 53218893Sdim return AA->alias(LocA, LocB); 54193323Sed} 55193323Sed 56218893Sdimbool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 57218893Sdim bool OrLocal) { 58193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 59218893Sdim return AA->pointsToConstantMemory(Loc, OrLocal); 60193323Sed} 61193323Sed 62193323Sedvoid AliasAnalysis::deleteValue(Value *V) { 63193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 64193323Sed AA->deleteValue(V); 65193323Sed} 66193323Sed 67193323Sedvoid AliasAnalysis::copyValue(Value *From, Value *To) { 68193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 69193323Sed AA->copyValue(From, To); 70193323Sed} 71193323Sed 72218893Sdimvoid AliasAnalysis::addEscapingUse(Use &U) { 73218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 74218893Sdim AA->addEscapingUse(U); 75218893Sdim} 76218893Sdim 77218893Sdim 78193323SedAliasAnalysis::ModRefResult 79212904SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 80218893Sdim const Location &Loc) { 81218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 82212904Sdim 83212904Sdim ModRefBehavior MRB = getModRefBehavior(CS); 84212904Sdim if (MRB == DoesNotAccessMemory) 85212904Sdim return NoModRef; 86212904Sdim 87212904Sdim ModRefResult Mask = ModRef; 88218893Sdim if (onlyReadsMemory(MRB)) 89212904Sdim Mask = Ref; 90218893Sdim 91218893Sdim if (onlyAccessesArgPointees(MRB)) { 92212904Sdim bool doesAlias = false; 93221345Sdim if (doesAccessArgPointees(MRB)) { 94221345Sdim MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 95218893Sdim for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 96221345Sdim AI != AE; ++AI) { 97221345Sdim const Value *Arg = *AI; 98221345Sdim if (!Arg->getType()->isPointerTy()) 99221345Sdim continue; 100221345Sdim Location CSLoc(Arg, UnknownSize, CSTag); 101221345Sdim if (!isNoAlias(CSLoc, Loc)) { 102218893Sdim doesAlias = true; 103218893Sdim break; 104218893Sdim } 105221345Sdim } 106221345Sdim } 107212904Sdim if (!doesAlias) 108212904Sdim return NoModRef; 109212904Sdim } 110212904Sdim 111218893Sdim // If Loc is a constant memory location, the call definitely could not 112212904Sdim // modify the memory location. 113218893Sdim if ((Mask & Mod) && pointsToConstantMemory(Loc)) 114212904Sdim Mask = ModRefResult(Mask & ~Mod); 115212904Sdim 116218893Sdim // If this is the end of the chain, don't forward. 117212904Sdim if (!AA) return Mask; 118212904Sdim 119212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 120212904Sdim // in any mask we've managed to compute. 121218893Sdim return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 122212904Sdim} 123212904Sdim 124212904SdimAliasAnalysis::ModRefResult 125212904SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 126218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 127212904Sdim 128212904Sdim // If CS1 or CS2 are readnone, they don't interact. 129212904Sdim ModRefBehavior CS1B = getModRefBehavior(CS1); 130212904Sdim if (CS1B == DoesNotAccessMemory) return NoModRef; 131212904Sdim 132212904Sdim ModRefBehavior CS2B = getModRefBehavior(CS2); 133212904Sdim if (CS2B == DoesNotAccessMemory) return NoModRef; 134212904Sdim 135212904Sdim // If they both only read from memory, there is no dependence. 136218893Sdim if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 137212904Sdim return NoModRef; 138212904Sdim 139212904Sdim AliasAnalysis::ModRefResult Mask = ModRef; 140212904Sdim 141212904Sdim // If CS1 only reads memory, the only dependence on CS2 can be 142212904Sdim // from CS1 reading memory written by CS2. 143218893Sdim if (onlyReadsMemory(CS1B)) 144212904Sdim Mask = ModRefResult(Mask & Ref); 145212904Sdim 146212904Sdim // If CS2 only access memory through arguments, accumulate the mod/ref 147212904Sdim // information from CS1's references to the memory referenced by 148212904Sdim // CS2's arguments. 149218893Sdim if (onlyAccessesArgPointees(CS2B)) { 150212904Sdim AliasAnalysis::ModRefResult R = NoModRef; 151221345Sdim if (doesAccessArgPointees(CS2B)) { 152221345Sdim MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 153218893Sdim for (ImmutableCallSite::arg_iterator 154218893Sdim I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 155221345Sdim const Value *Arg = *I; 156221345Sdim if (!Arg->getType()->isPointerTy()) 157221345Sdim continue; 158221345Sdim Location CS2Loc(Arg, UnknownSize, CS2Tag); 159221345Sdim R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask); 160218893Sdim if (R == Mask) 161218893Sdim break; 162218893Sdim } 163221345Sdim } 164212904Sdim return R; 165212904Sdim } 166212904Sdim 167212904Sdim // If CS1 only accesses memory through arguments, check if CS2 references 168212904Sdim // any of the memory referenced by CS1's arguments. If not, return NoModRef. 169218893Sdim if (onlyAccessesArgPointees(CS1B)) { 170212904Sdim AliasAnalysis::ModRefResult R = NoModRef; 171221345Sdim if (doesAccessArgPointees(CS1B)) { 172221345Sdim MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 173218893Sdim for (ImmutableCallSite::arg_iterator 174221345Sdim I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 175221345Sdim const Value *Arg = *I; 176221345Sdim if (!Arg->getType()->isPointerTy()) 177221345Sdim continue; 178221345Sdim Location CS1Loc(Arg, UnknownSize, CS1Tag); 179221345Sdim if (getModRefInfo(CS2, CS1Loc) != NoModRef) { 180218893Sdim R = Mask; 181218893Sdim break; 182218893Sdim } 183221345Sdim } 184221345Sdim } 185212904Sdim if (R == NoModRef) 186212904Sdim return R; 187212904Sdim } 188212904Sdim 189218893Sdim // If this is the end of the chain, don't forward. 190212904Sdim if (!AA) return Mask; 191212904Sdim 192212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 193212904Sdim // in any mask we've managed to compute. 194212904Sdim return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 195212904Sdim} 196212904Sdim 197212904SdimAliasAnalysis::ModRefBehavior 198212904SdimAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 199218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 200212904Sdim 201212904Sdim ModRefBehavior Min = UnknownModRefBehavior; 202212904Sdim 203212904Sdim // Call back into the alias analysis with the other form of getModRefBehavior 204212904Sdim // to see if it can give a better response. 205212904Sdim if (const Function *F = CS.getCalledFunction()) 206212904Sdim Min = getModRefBehavior(F); 207212904Sdim 208218893Sdim // If this is the end of the chain, don't forward. 209212904Sdim if (!AA) return Min; 210212904Sdim 211212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 212212904Sdim // in any result we've managed to compute. 213218893Sdim return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 214212904Sdim} 215212904Sdim 216212904SdimAliasAnalysis::ModRefBehavior 217212904SdimAliasAnalysis::getModRefBehavior(const Function *F) { 218193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 219212904Sdim return AA->getModRefBehavior(F); 220193323Sed} 221193323Sed 222193323Sed//===----------------------------------------------------------------------===// 223193323Sed// AliasAnalysis non-virtual helper method implementation 224193323Sed//===----------------------------------------------------------------------===// 225193323Sed 226218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 227218893Sdim return Location(LI->getPointerOperand(), 228218893Sdim getTypeStoreSize(LI->getType()), 229218893Sdim LI->getMetadata(LLVMContext::MD_tbaa)); 230218893Sdim} 231218893Sdim 232218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 233218893Sdim return Location(SI->getPointerOperand(), 234218893Sdim getTypeStoreSize(SI->getValueOperand()->getType()), 235218893Sdim SI->getMetadata(LLVMContext::MD_tbaa)); 236218893Sdim} 237218893Sdim 238218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 239218893Sdim return Location(VI->getPointerOperand(), 240218893Sdim UnknownSize, 241218893Sdim VI->getMetadata(LLVMContext::MD_tbaa)); 242218893Sdim} 243218893Sdim 244226890SdimAliasAnalysis::Location 245226890SdimAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 246226890Sdim return Location(CXI->getPointerOperand(), 247226890Sdim getTypeStoreSize(CXI->getCompareOperand()->getType()), 248226890Sdim CXI->getMetadata(LLVMContext::MD_tbaa)); 249226890Sdim} 250218893Sdim 251226890SdimAliasAnalysis::Location 252226890SdimAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 253226890Sdim return Location(RMWI->getPointerOperand(), 254226890Sdim getTypeStoreSize(RMWI->getValOperand()->getType()), 255226890Sdim RMWI->getMetadata(LLVMContext::MD_tbaa)); 256226890Sdim} 257226890Sdim 258218893SdimAliasAnalysis::Location 259218893SdimAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 260218893Sdim uint64_t Size = UnknownSize; 261218893Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 262218893Sdim Size = C->getValue().getZExtValue(); 263218893Sdim 264218893Sdim // memcpy/memmove can have TBAA tags. For memcpy, they apply 265218893Sdim // to both the source and the destination. 266218893Sdim MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 267218893Sdim 268218893Sdim return Location(MTI->getRawSource(), Size, TBAATag); 269218893Sdim} 270218893Sdim 271218893SdimAliasAnalysis::Location 272218893SdimAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 273218893Sdim uint64_t Size = UnknownSize; 274218893Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 275218893Sdim Size = C->getValue().getZExtValue(); 276218893Sdim 277218893Sdim // memcpy/memmove can have TBAA tags. For memcpy, they apply 278218893Sdim // to both the source and the destination. 279218893Sdim MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 280218893Sdim 281218893Sdim return Location(MTI->getRawDest(), Size, TBAATag); 282218893Sdim} 283218893Sdim 284218893Sdim 285218893Sdim 286193323SedAliasAnalysis::ModRefResult 287218893SdimAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 288226890Sdim // Be conservative in the face of volatile/atomic. 289226890Sdim if (!L->isUnordered()) 290212904Sdim return ModRef; 291212904Sdim 292212904Sdim // If the load address doesn't alias the given address, it doesn't read 293212904Sdim // or write the specified memory. 294218893Sdim if (!alias(getLocation(L), Loc)) 295212904Sdim return NoModRef; 296212904Sdim 297212904Sdim // Otherwise, a load just reads. 298212904Sdim return Ref; 299193323Sed} 300193323Sed 301193323SedAliasAnalysis::ModRefResult 302218893SdimAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 303226890Sdim // Be conservative in the face of volatile/atomic. 304226890Sdim if (!S->isUnordered()) 305212904Sdim return ModRef; 306212904Sdim 307212904Sdim // If the store address cannot alias the pointer in question, then the 308212904Sdim // specified memory cannot be modified by the store. 309218893Sdim if (!alias(getLocation(S), Loc)) 310193323Sed return NoModRef; 311193323Sed 312193323Sed // If the pointer is a pointer to constant memory, then it could not have been 313193323Sed // modified by this store. 314218893Sdim if (pointsToConstantMemory(Loc)) 315212904Sdim return NoModRef; 316193323Sed 317212904Sdim // Otherwise, a store just writes. 318212904Sdim return Mod; 319193323Sed} 320193323Sed 321193323SedAliasAnalysis::ModRefResult 322218893SdimAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 323212904Sdim // If the va_arg address cannot alias the pointer in question, then the 324212904Sdim // specified memory cannot be accessed by the va_arg. 325218893Sdim if (!alias(getLocation(V), Loc)) 326193323Sed return NoModRef; 327193323Sed 328212904Sdim // If the pointer is a pointer to constant memory, then it could not have been 329212904Sdim // modified by this va_arg. 330218893Sdim if (pointsToConstantMemory(Loc)) 331212904Sdim return NoModRef; 332193323Sed 333212904Sdim // Otherwise, a va_arg reads and writes. 334212904Sdim return ModRef; 335212904Sdim} 336193323Sed 337226890SdimAliasAnalysis::ModRefResult 338226890SdimAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 339226890Sdim // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 340226890Sdim if (CX->getOrdering() > Monotonic) 341226890Sdim return ModRef; 342226890Sdim 343226890Sdim // If the cmpxchg address does not alias the location, it does not access it. 344226890Sdim if (!alias(getLocation(CX), Loc)) 345226890Sdim return NoModRef; 346226890Sdim 347226890Sdim return ModRef; 348226890Sdim} 349226890Sdim 350226890SdimAliasAnalysis::ModRefResult 351226890SdimAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 352226890Sdim // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 353226890Sdim if (RMW->getOrdering() > Monotonic) 354226890Sdim return ModRef; 355226890Sdim 356226890Sdim // If the atomicrmw address does not alias the location, it does not access it. 357226890Sdim if (!alias(getLocation(RMW), Loc)) 358226890Sdim return NoModRef; 359226890Sdim 360226890Sdim return ModRef; 361226890Sdim} 362226890Sdim 363245431Sdimnamespace { 364252723Sdim // Conservatively return true. Return false, if there is a single path 365252723Sdim // starting from "From" and the path does not reach "To". 366252723Sdim static bool hasPath(const BasicBlock *From, const BasicBlock *To) { 367252723Sdim const unsigned MaxCheck = 5; 368252723Sdim const BasicBlock *Current = From; 369252723Sdim for (unsigned I = 0; I < MaxCheck; I++) { 370252723Sdim unsigned NumSuccs = Current->getTerminator()->getNumSuccessors(); 371252723Sdim if (NumSuccs > 1) 372252723Sdim return true; 373252723Sdim if (NumSuccs == 0) 374252723Sdim return false; 375252723Sdim Current = Current->getTerminator()->getSuccessor(0); 376252723Sdim if (Current == To) 377252723Sdim return true; 378252723Sdim } 379252723Sdim return true; 380252723Sdim } 381252723Sdim 382245431Sdim /// Only find pointer captures which happen before the given instruction. Uses 383245431Sdim /// the dominator tree to determine whether one instruction is before another. 384252723Sdim /// Only support the case where the Value is defined in the same basic block 385252723Sdim /// as the given instruction and the use. 386245431Sdim struct CapturesBefore : public CaptureTracker { 387245431Sdim CapturesBefore(const Instruction *I, DominatorTree *DT) 388245431Sdim : BeforeHere(I), DT(DT), Captured(false) {} 389226890Sdim 390245431Sdim void tooManyUses() { Captured = true; } 391245431Sdim 392245431Sdim bool shouldExplore(Use *U) { 393245431Sdim Instruction *I = cast<Instruction>(U->getUser()); 394245431Sdim BasicBlock *BB = I->getParent(); 395252723Sdim // We explore this usage only if the usage can reach "BeforeHere". 396252723Sdim // If use is not reachable from entry, there is no need to explore. 397252723Sdim if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 398245431Sdim return false; 399252723Sdim // If the value is defined in the same basic block as use and BeforeHere, 400252723Sdim // there is no need to explore the use if BeforeHere dominates use. 401252723Sdim // Check whether there is a path from I to BeforeHere. 402252723Sdim if (BeforeHere != I && DT->dominates(BeforeHere, I) && 403252723Sdim !hasPath(BB, BeforeHere->getParent())) 404252723Sdim return false; 405245431Sdim return true; 406245431Sdim } 407245431Sdim 408245431Sdim bool captured(Use *U) { 409245431Sdim Instruction *I = cast<Instruction>(U->getUser()); 410245431Sdim BasicBlock *BB = I->getParent(); 411252723Sdim // Same logic as in shouldExplore. 412252723Sdim if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 413245431Sdim return false; 414252723Sdim if (BeforeHere != I && DT->dominates(BeforeHere, I) && 415252723Sdim !hasPath(BB, BeforeHere->getParent())) 416252723Sdim return false; 417245431Sdim Captured = true; 418245431Sdim return true; 419245431Sdim } 420245431Sdim 421245431Sdim const Instruction *BeforeHere; 422245431Sdim DominatorTree *DT; 423245431Sdim 424245431Sdim bool Captured; 425245431Sdim }; 426245431Sdim} 427245431Sdim 428245431Sdim// FIXME: this is really just shoring-up a deficiency in alias analysis. 429245431Sdim// BasicAA isn't willing to spend linear time determining whether an alloca 430245431Sdim// was captured before or after this particular call, while we are. However, 431245431Sdim// with a smarter AA in place, this test is just wasting compile time. 432245431SdimAliasAnalysis::ModRefResult 433245431SdimAliasAnalysis::callCapturesBefore(const Instruction *I, 434245431Sdim const AliasAnalysis::Location &MemLoc, 435245431Sdim DominatorTree *DT) { 436245431Sdim if (!DT || !TD) return AliasAnalysis::ModRef; 437245431Sdim 438245431Sdim const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); 439245431Sdim if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 440245431Sdim isa<Constant>(Object)) 441245431Sdim return AliasAnalysis::ModRef; 442245431Sdim 443245431Sdim ImmutableCallSite CS(I); 444245431Sdim if (!CS.getInstruction() || CS.getInstruction() == Object) 445245431Sdim return AliasAnalysis::ModRef; 446245431Sdim 447245431Sdim CapturesBefore CB(I, DT); 448245431Sdim llvm::PointerMayBeCaptured(Object, &CB); 449245431Sdim if (CB.Captured) 450245431Sdim return AliasAnalysis::ModRef; 451245431Sdim 452245431Sdim unsigned ArgNo = 0; 453245431Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 454245431Sdim CI != CE; ++CI, ++ArgNo) { 455245431Sdim // Only look at the no-capture or byval pointer arguments. If this 456245431Sdim // pointer were passed to arguments that were neither of these, then it 457245431Sdim // couldn't be no-capture. 458245431Sdim if (!(*CI)->getType()->isPointerTy() || 459245431Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 460245431Sdim continue; 461245431Sdim 462245431Sdim // If this is a no-capture pointer argument, see if we can tell that it 463245431Sdim // is impossible to alias the pointer we're checking. If not, we have to 464245431Sdim // assume that the call could touch the pointer, even though it doesn't 465245431Sdim // escape. 466245431Sdim if (!isNoAlias(AliasAnalysis::Location(*CI), 467245431Sdim AliasAnalysis::Location(Object))) { 468245431Sdim return AliasAnalysis::ModRef; 469245431Sdim } 470245431Sdim } 471245431Sdim return AliasAnalysis::NoModRef; 472245431Sdim} 473245431Sdim 474193323Sed// AliasAnalysis destructor: DO NOT move this to the header file for 475193323Sed// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 476193323Sed// the AliasAnalysis.o file in the current .a file, causing alias analysis 477193323Sed// support to not be included in the tool correctly! 478193323Sed// 479193323SedAliasAnalysis::~AliasAnalysis() {} 480193323Sed 481193323Sed/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 482193323Sed/// AliasAnalysis interface before any other methods are called. 483193323Sed/// 484193323Sedvoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 485245431Sdim TD = P->getAnalysisIfAvailable<DataLayout>(); 486245431Sdim TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 487193323Sed AA = &P->getAnalysis<AliasAnalysis>(); 488193323Sed} 489193323Sed 490193323Sed// getAnalysisUsage - All alias analysis implementations should invoke this 491198090Srdivacky// directly (using AliasAnalysis::getAnalysisUsage(AU)). 492193323Sedvoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 493193323Sed AU.addRequired<AliasAnalysis>(); // All AA's chain 494193323Sed} 495193323Sed 496245431Sdim/// getTypeStoreSize - Return the DataLayout store size for the given type, 497198090Srdivacky/// if known, or a conservative value otherwise. 498198090Srdivacky/// 499226890Sdimuint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 500218893Sdim return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 501198090Srdivacky} 502198090Srdivacky 503193323Sed/// canBasicBlockModify - Return true if it is possible for execution of the 504193323Sed/// specified basic block to modify the value pointed to by Ptr. 505193323Sed/// 506193323Sedbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 507218893Sdim const Location &Loc) { 508218893Sdim return canInstructionRangeModify(BB.front(), BB.back(), Loc); 509193323Sed} 510193323Sed 511193323Sed/// canInstructionRangeModify - Return true if it is possible for the execution 512193323Sed/// of the specified instructions to modify the value pointed to by Ptr. The 513193323Sed/// instructions to consider are all of the instructions in the range of [I1,I2] 514193323Sed/// INCLUSIVE. I1 and I2 must be in the same basic block. 515193323Sed/// 516193323Sedbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 517193323Sed const Instruction &I2, 518218893Sdim const Location &Loc) { 519193323Sed assert(I1.getParent() == I2.getParent() && 520193323Sed "Instructions not in same basic block!"); 521212904Sdim BasicBlock::const_iterator I = &I1; 522212904Sdim BasicBlock::const_iterator E = &I2; 523193323Sed ++E; // Convert from inclusive to exclusive range. 524193323Sed 525193323Sed for (; I != E; ++I) // Check every instruction in range 526218893Sdim if (getModRefInfo(I, Loc) & Mod) 527193323Sed return true; 528193323Sed return false; 529193323Sed} 530193323Sed 531193323Sed/// isNoAliasCall - Return true if this pointer is returned by a noalias 532193323Sed/// function. 533193323Sedbool llvm::isNoAliasCall(const Value *V) { 534193323Sed if (isa<CallInst>(V) || isa<InvokeInst>(V)) 535212904Sdim return ImmutableCallSite(cast<Instruction>(V)) 536252723Sdim .paramHasAttr(0, Attribute::NoAlias); 537193323Sed return false; 538193323Sed} 539193323Sed 540193323Sed/// isIdentifiedObject - Return true if this pointer refers to a distinct and 541193323Sed/// identifiable object. This returns true for: 542198090Srdivacky/// Global Variables and Functions (but not Global Aliases) 543193323Sed/// Allocas and Mallocs 544193323Sed/// ByVal and NoAlias Arguments 545193323Sed/// NoAlias returns 546193323Sed/// 547193323Sedbool llvm::isIdentifiedObject(const Value *V) { 548210299Sed if (isa<AllocaInst>(V)) 549193323Sed return true; 550198090Srdivacky if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 551198090Srdivacky return true; 552210299Sed if (isNoAliasCall(V)) 553210299Sed return true; 554193323Sed if (const Argument *A = dyn_cast<Argument>(V)) 555193323Sed return A->hasNoAliasAttr() || A->hasByValAttr(); 556193323Sed return false; 557193323Sed} 558