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" 29263509Sdim#include "llvm/Analysis/CFG.h" 30245431Sdim#include "llvm/Analysis/Dominators.h" 31245431Sdim#include "llvm/Analysis/ValueTracking.h" 32252723Sdim#include "llvm/IR/BasicBlock.h" 33252723Sdim#include "llvm/IR/DataLayout.h" 34252723Sdim#include "llvm/IR/Function.h" 35252723Sdim#include "llvm/IR/Instructions.h" 36252723Sdim#include "llvm/IR/IntrinsicInst.h" 37252723Sdim#include "llvm/IR/LLVMContext.h" 38252723Sdim#include "llvm/IR/Type.h" 39193323Sed#include "llvm/Pass.h" 40245431Sdim#include "llvm/Target/TargetLibraryInfo.h" 41193323Sedusing namespace llvm; 42193323Sed 43193323Sed// Register the AliasAnalysis interface, providing a nice name to refer to. 44218893SdimINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 45193323Sedchar AliasAnalysis::ID = 0; 46193323Sed 47193323Sed//===----------------------------------------------------------------------===// 48193323Sed// Default chaining methods 49193323Sed//===----------------------------------------------------------------------===// 50193323Sed 51193323SedAliasAnalysis::AliasResult 52218893SdimAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 53193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54218893Sdim return AA->alias(LocA, LocB); 55193323Sed} 56193323Sed 57218893Sdimbool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 58218893Sdim bool OrLocal) { 59193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 60218893Sdim return AA->pointsToConstantMemory(Loc, OrLocal); 61193323Sed} 62193323Sed 63193323Sedvoid AliasAnalysis::deleteValue(Value *V) { 64193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 65193323Sed AA->deleteValue(V); 66193323Sed} 67193323Sed 68193323Sedvoid AliasAnalysis::copyValue(Value *From, Value *To) { 69193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 70193323Sed AA->copyValue(From, To); 71193323Sed} 72193323Sed 73218893Sdimvoid AliasAnalysis::addEscapingUse(Use &U) { 74218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 75218893Sdim AA->addEscapingUse(U); 76218893Sdim} 77218893Sdim 78218893Sdim 79193323SedAliasAnalysis::ModRefResult 80212904SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 81218893Sdim const Location &Loc) { 82218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 83212904Sdim 84212904Sdim ModRefBehavior MRB = getModRefBehavior(CS); 85212904Sdim if (MRB == DoesNotAccessMemory) 86212904Sdim return NoModRef; 87212904Sdim 88212904Sdim ModRefResult Mask = ModRef; 89218893Sdim if (onlyReadsMemory(MRB)) 90212904Sdim Mask = Ref; 91218893Sdim 92218893Sdim if (onlyAccessesArgPointees(MRB)) { 93212904Sdim bool doesAlias = false; 94221345Sdim if (doesAccessArgPointees(MRB)) { 95221345Sdim MDNode *CSTag = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 96218893Sdim for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 97221345Sdim AI != AE; ++AI) { 98221345Sdim const Value *Arg = *AI; 99221345Sdim if (!Arg->getType()->isPointerTy()) 100221345Sdim continue; 101221345Sdim Location CSLoc(Arg, UnknownSize, CSTag); 102221345Sdim if (!isNoAlias(CSLoc, Loc)) { 103218893Sdim doesAlias = true; 104218893Sdim break; 105218893Sdim } 106221345Sdim } 107221345Sdim } 108212904Sdim if (!doesAlias) 109212904Sdim return NoModRef; 110212904Sdim } 111212904Sdim 112218893Sdim // If Loc is a constant memory location, the call definitely could not 113212904Sdim // modify the memory location. 114218893Sdim if ((Mask & Mod) && pointsToConstantMemory(Loc)) 115212904Sdim Mask = ModRefResult(Mask & ~Mod); 116212904Sdim 117218893Sdim // If this is the end of the chain, don't forward. 118212904Sdim if (!AA) return Mask; 119212904Sdim 120212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 121212904Sdim // in any mask we've managed to compute. 122218893Sdim return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 123212904Sdim} 124212904Sdim 125212904SdimAliasAnalysis::ModRefResult 126212904SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 127218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 128212904Sdim 129212904Sdim // If CS1 or CS2 are readnone, they don't interact. 130212904Sdim ModRefBehavior CS1B = getModRefBehavior(CS1); 131212904Sdim if (CS1B == DoesNotAccessMemory) return NoModRef; 132212904Sdim 133212904Sdim ModRefBehavior CS2B = getModRefBehavior(CS2); 134212904Sdim if (CS2B == DoesNotAccessMemory) return NoModRef; 135212904Sdim 136212904Sdim // If they both only read from memory, there is no dependence. 137218893Sdim if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 138212904Sdim return NoModRef; 139212904Sdim 140212904Sdim AliasAnalysis::ModRefResult Mask = ModRef; 141212904Sdim 142212904Sdim // If CS1 only reads memory, the only dependence on CS2 can be 143212904Sdim // from CS1 reading memory written by CS2. 144218893Sdim if (onlyReadsMemory(CS1B)) 145212904Sdim Mask = ModRefResult(Mask & Ref); 146212904Sdim 147212904Sdim // If CS2 only access memory through arguments, accumulate the mod/ref 148212904Sdim // information from CS1's references to the memory referenced by 149212904Sdim // CS2's arguments. 150218893Sdim if (onlyAccessesArgPointees(CS2B)) { 151212904Sdim AliasAnalysis::ModRefResult R = NoModRef; 152221345Sdim if (doesAccessArgPointees(CS2B)) { 153221345Sdim MDNode *CS2Tag = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 154218893Sdim for (ImmutableCallSite::arg_iterator 155218893Sdim I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 156221345Sdim const Value *Arg = *I; 157221345Sdim if (!Arg->getType()->isPointerTy()) 158221345Sdim continue; 159221345Sdim Location CS2Loc(Arg, UnknownSize, CS2Tag); 160221345Sdim R = ModRefResult((R | getModRefInfo(CS1, CS2Loc)) & Mask); 161218893Sdim if (R == Mask) 162218893Sdim break; 163218893Sdim } 164221345Sdim } 165212904Sdim return R; 166212904Sdim } 167212904Sdim 168212904Sdim // If CS1 only accesses memory through arguments, check if CS2 references 169212904Sdim // any of the memory referenced by CS1's arguments. If not, return NoModRef. 170218893Sdim if (onlyAccessesArgPointees(CS1B)) { 171212904Sdim AliasAnalysis::ModRefResult R = NoModRef; 172221345Sdim if (doesAccessArgPointees(CS1B)) { 173221345Sdim MDNode *CS1Tag = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa); 174218893Sdim for (ImmutableCallSite::arg_iterator 175221345Sdim I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 176221345Sdim const Value *Arg = *I; 177221345Sdim if (!Arg->getType()->isPointerTy()) 178221345Sdim continue; 179221345Sdim Location CS1Loc(Arg, UnknownSize, CS1Tag); 180221345Sdim if (getModRefInfo(CS2, CS1Loc) != NoModRef) { 181218893Sdim R = Mask; 182218893Sdim break; 183218893Sdim } 184221345Sdim } 185221345Sdim } 186212904Sdim if (R == NoModRef) 187212904Sdim return R; 188212904Sdim } 189212904Sdim 190218893Sdim // If this is the end of the chain, don't forward. 191212904Sdim if (!AA) return Mask; 192212904Sdim 193212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 194212904Sdim // in any mask we've managed to compute. 195212904Sdim return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 196212904Sdim} 197212904Sdim 198212904SdimAliasAnalysis::ModRefBehavior 199212904SdimAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 200218893Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 201212904Sdim 202212904Sdim ModRefBehavior Min = UnknownModRefBehavior; 203212904Sdim 204212904Sdim // Call back into the alias analysis with the other form of getModRefBehavior 205212904Sdim // to see if it can give a better response. 206212904Sdim if (const Function *F = CS.getCalledFunction()) 207212904Sdim Min = getModRefBehavior(F); 208212904Sdim 209218893Sdim // If this is the end of the chain, don't forward. 210212904Sdim if (!AA) return Min; 211212904Sdim 212212904Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 213212904Sdim // in any result we've managed to compute. 214218893Sdim return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 215212904Sdim} 216212904Sdim 217212904SdimAliasAnalysis::ModRefBehavior 218212904SdimAliasAnalysis::getModRefBehavior(const Function *F) { 219193323Sed assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 220212904Sdim return AA->getModRefBehavior(F); 221193323Sed} 222193323Sed 223193323Sed//===----------------------------------------------------------------------===// 224193323Sed// AliasAnalysis non-virtual helper method implementation 225193323Sed//===----------------------------------------------------------------------===// 226193323Sed 227218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 228218893Sdim return Location(LI->getPointerOperand(), 229218893Sdim getTypeStoreSize(LI->getType()), 230218893Sdim LI->getMetadata(LLVMContext::MD_tbaa)); 231218893Sdim} 232218893Sdim 233218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 234218893Sdim return Location(SI->getPointerOperand(), 235218893Sdim getTypeStoreSize(SI->getValueOperand()->getType()), 236218893Sdim SI->getMetadata(LLVMContext::MD_tbaa)); 237218893Sdim} 238218893Sdim 239218893SdimAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 240218893Sdim return Location(VI->getPointerOperand(), 241218893Sdim UnknownSize, 242218893Sdim VI->getMetadata(LLVMContext::MD_tbaa)); 243218893Sdim} 244218893Sdim 245226890SdimAliasAnalysis::Location 246226890SdimAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 247226890Sdim return Location(CXI->getPointerOperand(), 248226890Sdim getTypeStoreSize(CXI->getCompareOperand()->getType()), 249226890Sdim CXI->getMetadata(LLVMContext::MD_tbaa)); 250226890Sdim} 251218893Sdim 252226890SdimAliasAnalysis::Location 253226890SdimAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 254226890Sdim return Location(RMWI->getPointerOperand(), 255226890Sdim getTypeStoreSize(RMWI->getValOperand()->getType()), 256226890Sdim RMWI->getMetadata(LLVMContext::MD_tbaa)); 257226890Sdim} 258226890Sdim 259218893SdimAliasAnalysis::Location 260218893SdimAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 261218893Sdim uint64_t Size = UnknownSize; 262218893Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 263218893Sdim Size = C->getValue().getZExtValue(); 264218893Sdim 265218893Sdim // memcpy/memmove can have TBAA tags. For memcpy, they apply 266218893Sdim // to both the source and the destination. 267218893Sdim MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 268218893Sdim 269218893Sdim return Location(MTI->getRawSource(), Size, TBAATag); 270218893Sdim} 271218893Sdim 272218893SdimAliasAnalysis::Location 273218893SdimAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 274218893Sdim uint64_t Size = UnknownSize; 275218893Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 276218893Sdim Size = C->getValue().getZExtValue(); 277218893Sdim 278218893Sdim // memcpy/memmove can have TBAA tags. For memcpy, they apply 279218893Sdim // to both the source and the destination. 280218893Sdim MDNode *TBAATag = MTI->getMetadata(LLVMContext::MD_tbaa); 281218893Sdim 282218893Sdim return Location(MTI->getRawDest(), Size, TBAATag); 283218893Sdim} 284218893Sdim 285218893Sdim 286218893Sdim 287193323SedAliasAnalysis::ModRefResult 288218893SdimAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 289226890Sdim // Be conservative in the face of volatile/atomic. 290226890Sdim if (!L->isUnordered()) 291212904Sdim return ModRef; 292212904Sdim 293212904Sdim // If the load address doesn't alias the given address, it doesn't read 294212904Sdim // or write the specified memory. 295218893Sdim if (!alias(getLocation(L), Loc)) 296212904Sdim return NoModRef; 297212904Sdim 298212904Sdim // Otherwise, a load just reads. 299212904Sdim return Ref; 300193323Sed} 301193323Sed 302193323SedAliasAnalysis::ModRefResult 303218893SdimAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 304226890Sdim // Be conservative in the face of volatile/atomic. 305226890Sdim if (!S->isUnordered()) 306212904Sdim return ModRef; 307212904Sdim 308212904Sdim // If the store address cannot alias the pointer in question, then the 309212904Sdim // specified memory cannot be modified by the store. 310218893Sdim if (!alias(getLocation(S), Loc)) 311193323Sed return NoModRef; 312193323Sed 313193323Sed // If the pointer is a pointer to constant memory, then it could not have been 314193323Sed // modified by this store. 315218893Sdim if (pointsToConstantMemory(Loc)) 316212904Sdim return NoModRef; 317193323Sed 318212904Sdim // Otherwise, a store just writes. 319212904Sdim return Mod; 320193323Sed} 321193323Sed 322193323SedAliasAnalysis::ModRefResult 323218893SdimAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 324212904Sdim // If the va_arg address cannot alias the pointer in question, then the 325212904Sdim // specified memory cannot be accessed by the va_arg. 326218893Sdim if (!alias(getLocation(V), Loc)) 327193323Sed return NoModRef; 328193323Sed 329212904Sdim // If the pointer is a pointer to constant memory, then it could not have been 330212904Sdim // modified by this va_arg. 331218893Sdim if (pointsToConstantMemory(Loc)) 332212904Sdim return NoModRef; 333193323Sed 334212904Sdim // Otherwise, a va_arg reads and writes. 335212904Sdim return ModRef; 336212904Sdim} 337193323Sed 338226890SdimAliasAnalysis::ModRefResult 339226890SdimAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 340226890Sdim // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 341226890Sdim if (CX->getOrdering() > Monotonic) 342226890Sdim return ModRef; 343226890Sdim 344226890Sdim // If the cmpxchg address does not alias the location, it does not access it. 345226890Sdim if (!alias(getLocation(CX), Loc)) 346226890Sdim return NoModRef; 347226890Sdim 348226890Sdim return ModRef; 349226890Sdim} 350226890Sdim 351226890SdimAliasAnalysis::ModRefResult 352226890SdimAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 353226890Sdim // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 354226890Sdim if (RMW->getOrdering() > Monotonic) 355226890Sdim return ModRef; 356226890Sdim 357226890Sdim // If the atomicrmw address does not alias the location, it does not access it. 358226890Sdim if (!alias(getLocation(RMW), Loc)) 359226890Sdim return NoModRef; 360226890Sdim 361226890Sdim return ModRef; 362226890Sdim} 363226890Sdim 364245431Sdimnamespace { 365245431Sdim /// Only find pointer captures which happen before the given instruction. Uses 366245431Sdim /// the dominator tree to determine whether one instruction is before another. 367252723Sdim /// Only support the case where the Value is defined in the same basic block 368252723Sdim /// as the given instruction and the use. 369245431Sdim struct CapturesBefore : public CaptureTracker { 370245431Sdim CapturesBefore(const Instruction *I, DominatorTree *DT) 371245431Sdim : BeforeHere(I), DT(DT), Captured(false) {} 372226890Sdim 373245431Sdim void tooManyUses() { Captured = true; } 374245431Sdim 375245431Sdim bool shouldExplore(Use *U) { 376245431Sdim Instruction *I = cast<Instruction>(U->getUser()); 377245431Sdim BasicBlock *BB = I->getParent(); 378252723Sdim // We explore this usage only if the usage can reach "BeforeHere". 379252723Sdim // If use is not reachable from entry, there is no need to explore. 380252723Sdim if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 381245431Sdim return false; 382252723Sdim // If the value is defined in the same basic block as use and BeforeHere, 383252723Sdim // there is no need to explore the use if BeforeHere dominates use. 384252723Sdim // Check whether there is a path from I to BeforeHere. 385252723Sdim if (BeforeHere != I && DT->dominates(BeforeHere, I) && 386263509Sdim !isPotentiallyReachable(I, BeforeHere, DT)) 387252723Sdim return false; 388245431Sdim return true; 389245431Sdim } 390245431Sdim 391245431Sdim bool captured(Use *U) { 392245431Sdim Instruction *I = cast<Instruction>(U->getUser()); 393245431Sdim BasicBlock *BB = I->getParent(); 394252723Sdim // Same logic as in shouldExplore. 395252723Sdim if (BeforeHere != I && !DT->isReachableFromEntry(BB)) 396245431Sdim return false; 397252723Sdim if (BeforeHere != I && DT->dominates(BeforeHere, I) && 398263509Sdim !isPotentiallyReachable(I, BeforeHere, DT)) 399252723Sdim return false; 400245431Sdim Captured = true; 401245431Sdim return true; 402245431Sdim } 403245431Sdim 404245431Sdim const Instruction *BeforeHere; 405245431Sdim DominatorTree *DT; 406245431Sdim 407245431Sdim bool Captured; 408245431Sdim }; 409245431Sdim} 410245431Sdim 411245431Sdim// FIXME: this is really just shoring-up a deficiency in alias analysis. 412245431Sdim// BasicAA isn't willing to spend linear time determining whether an alloca 413245431Sdim// was captured before or after this particular call, while we are. However, 414245431Sdim// with a smarter AA in place, this test is just wasting compile time. 415245431SdimAliasAnalysis::ModRefResult 416245431SdimAliasAnalysis::callCapturesBefore(const Instruction *I, 417245431Sdim const AliasAnalysis::Location &MemLoc, 418245431Sdim DominatorTree *DT) { 419245431Sdim if (!DT || !TD) return AliasAnalysis::ModRef; 420245431Sdim 421245431Sdim const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); 422245431Sdim if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 423245431Sdim isa<Constant>(Object)) 424245431Sdim return AliasAnalysis::ModRef; 425245431Sdim 426245431Sdim ImmutableCallSite CS(I); 427245431Sdim if (!CS.getInstruction() || CS.getInstruction() == Object) 428245431Sdim return AliasAnalysis::ModRef; 429245431Sdim 430245431Sdim CapturesBefore CB(I, DT); 431245431Sdim llvm::PointerMayBeCaptured(Object, &CB); 432245431Sdim if (CB.Captured) 433245431Sdim return AliasAnalysis::ModRef; 434245431Sdim 435245431Sdim unsigned ArgNo = 0; 436263509Sdim AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef; 437245431Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 438245431Sdim CI != CE; ++CI, ++ArgNo) { 439245431Sdim // Only look at the no-capture or byval pointer arguments. If this 440245431Sdim // pointer were passed to arguments that were neither of these, then it 441245431Sdim // couldn't be no-capture. 442245431Sdim if (!(*CI)->getType()->isPointerTy() || 443245431Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 444245431Sdim continue; 445245431Sdim 446245431Sdim // If this is a no-capture pointer argument, see if we can tell that it 447245431Sdim // is impossible to alias the pointer we're checking. If not, we have to 448245431Sdim // assume that the call could touch the pointer, even though it doesn't 449245431Sdim // escape. 450263509Sdim if (isNoAlias(AliasAnalysis::Location(*CI), 451263509Sdim AliasAnalysis::Location(Object))) 452263509Sdim continue; 453263509Sdim if (CS.doesNotAccessMemory(ArgNo)) 454263509Sdim continue; 455263509Sdim if (CS.onlyReadsMemory(ArgNo)) { 456263509Sdim R = AliasAnalysis::Ref; 457263509Sdim continue; 458245431Sdim } 459263509Sdim return AliasAnalysis::ModRef; 460245431Sdim } 461263509Sdim return R; 462245431Sdim} 463245431Sdim 464193323Sed// AliasAnalysis destructor: DO NOT move this to the header file for 465193323Sed// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 466193323Sed// the AliasAnalysis.o file in the current .a file, causing alias analysis 467193323Sed// support to not be included in the tool correctly! 468193323Sed// 469193323SedAliasAnalysis::~AliasAnalysis() {} 470193323Sed 471193323Sed/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 472193323Sed/// AliasAnalysis interface before any other methods are called. 473193323Sed/// 474193323Sedvoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 475245431Sdim TD = P->getAnalysisIfAvailable<DataLayout>(); 476245431Sdim TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 477193323Sed AA = &P->getAnalysis<AliasAnalysis>(); 478193323Sed} 479193323Sed 480193323Sed// getAnalysisUsage - All alias analysis implementations should invoke this 481198090Srdivacky// directly (using AliasAnalysis::getAnalysisUsage(AU)). 482193323Sedvoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 483193323Sed AU.addRequired<AliasAnalysis>(); // All AA's chain 484193323Sed} 485193323Sed 486245431Sdim/// getTypeStoreSize - Return the DataLayout store size for the given type, 487198090Srdivacky/// if known, or a conservative value otherwise. 488198090Srdivacky/// 489226890Sdimuint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 490218893Sdim return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 491198090Srdivacky} 492198090Srdivacky 493193323Sed/// canBasicBlockModify - Return true if it is possible for execution of the 494193323Sed/// specified basic block to modify the value pointed to by Ptr. 495193323Sed/// 496193323Sedbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 497218893Sdim const Location &Loc) { 498218893Sdim return canInstructionRangeModify(BB.front(), BB.back(), Loc); 499193323Sed} 500193323Sed 501193323Sed/// canInstructionRangeModify - Return true if it is possible for the execution 502193323Sed/// of the specified instructions to modify the value pointed to by Ptr. The 503193323Sed/// instructions to consider are all of the instructions in the range of [I1,I2] 504193323Sed/// INCLUSIVE. I1 and I2 must be in the same basic block. 505193323Sed/// 506193323Sedbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 507193323Sed const Instruction &I2, 508218893Sdim const Location &Loc) { 509193323Sed assert(I1.getParent() == I2.getParent() && 510193323Sed "Instructions not in same basic block!"); 511212904Sdim BasicBlock::const_iterator I = &I1; 512212904Sdim BasicBlock::const_iterator E = &I2; 513193323Sed ++E; // Convert from inclusive to exclusive range. 514193323Sed 515193323Sed for (; I != E; ++I) // Check every instruction in range 516218893Sdim if (getModRefInfo(I, Loc) & Mod) 517193323Sed return true; 518193323Sed return false; 519193323Sed} 520193323Sed 521193323Sed/// isNoAliasCall - Return true if this pointer is returned by a noalias 522193323Sed/// function. 523193323Sedbool llvm::isNoAliasCall(const Value *V) { 524193323Sed if (isa<CallInst>(V) || isa<InvokeInst>(V)) 525212904Sdim return ImmutableCallSite(cast<Instruction>(V)) 526252723Sdim .paramHasAttr(0, Attribute::NoAlias); 527193323Sed return false; 528193323Sed} 529193323Sed 530263509Sdim/// isNoAliasArgument - Return true if this is an argument with the noalias 531263509Sdim/// attribute. 532263509Sdimbool llvm::isNoAliasArgument(const Value *V) 533263509Sdim{ 534263509Sdim if (const Argument *A = dyn_cast<Argument>(V)) 535263509Sdim return A->hasNoAliasAttr(); 536263509Sdim return false; 537263509Sdim} 538263509Sdim 539193323Sed/// isIdentifiedObject - Return true if this pointer refers to a distinct and 540193323Sed/// identifiable object. This returns true for: 541198090Srdivacky/// Global Variables and Functions (but not Global Aliases) 542193323Sed/// Allocas and Mallocs 543193323Sed/// ByVal and NoAlias Arguments 544193323Sed/// NoAlias returns 545193323Sed/// 546193323Sedbool llvm::isIdentifiedObject(const Value *V) { 547210299Sed if (isa<AllocaInst>(V)) 548193323Sed return true; 549198090Srdivacky if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 550198090Srdivacky return true; 551210299Sed if (isNoAliasCall(V)) 552210299Sed return true; 553193323Sed if (const Argument *A = dyn_cast<Argument>(V)) 554193323Sed return A->hasNoAliasAttr() || A->hasByValAttr(); 555193323Sed return false; 556193323Sed} 557