AliasAnalysis.cpp revision 243830
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" 28239462Sdim#include "llvm/Analysis/CaptureTracking.h" 29239462Sdim#include "llvm/Analysis/Dominators.h" 30239462Sdim#include "llvm/Analysis/ValueTracking.h" 31193323Sed#include "llvm/Pass.h" 32193323Sed#include "llvm/BasicBlock.h" 33193323Sed#include "llvm/Function.h" 34193323Sed#include "llvm/IntrinsicInst.h" 35193323Sed#include "llvm/Instructions.h" 36218893Sdim#include "llvm/LLVMContext.h" 37193323Sed#include "llvm/Type.h" 38243830Sdim#include "llvm/DataLayout.h" 39243830Sdim#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 244226633SdimAliasAnalysis::Location 245226633SdimAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 246226633Sdim return Location(CXI->getPointerOperand(), 247226633Sdim getTypeStoreSize(CXI->getCompareOperand()->getType()), 248226633Sdim CXI->getMetadata(LLVMContext::MD_tbaa)); 249226633Sdim} 250218893Sdim 251226633SdimAliasAnalysis::Location 252226633SdimAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 253226633Sdim return Location(RMWI->getPointerOperand(), 254226633Sdim getTypeStoreSize(RMWI->getValOperand()->getType()), 255226633Sdim RMWI->getMetadata(LLVMContext::MD_tbaa)); 256226633Sdim} 257226633Sdim 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) { 288226633Sdim // Be conservative in the face of volatile/atomic. 289226633Sdim 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) { 303226633Sdim // Be conservative in the face of volatile/atomic. 304226633Sdim 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 337226633SdimAliasAnalysis::ModRefResult 338226633SdimAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 339226633Sdim // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 340226633Sdim if (CX->getOrdering() > Monotonic) 341226633Sdim return ModRef; 342226633Sdim 343226633Sdim // If the cmpxchg address does not alias the location, it does not access it. 344226633Sdim if (!alias(getLocation(CX), Loc)) 345226633Sdim return NoModRef; 346226633Sdim 347226633Sdim return ModRef; 348226633Sdim} 349226633Sdim 350226633SdimAliasAnalysis::ModRefResult 351226633SdimAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 352226633Sdim // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 353226633Sdim if (RMW->getOrdering() > Monotonic) 354226633Sdim return ModRef; 355226633Sdim 356226633Sdim // If the atomicrmw address does not alias the location, it does not access it. 357226633Sdim if (!alias(getLocation(RMW), Loc)) 358226633Sdim return NoModRef; 359226633Sdim 360226633Sdim return ModRef; 361226633Sdim} 362226633Sdim 363239462Sdimnamespace { 364239462Sdim /// Only find pointer captures which happen before the given instruction. Uses 365239462Sdim /// the dominator tree to determine whether one instruction is before another. 366239462Sdim struct CapturesBefore : public CaptureTracker { 367239462Sdim CapturesBefore(const Instruction *I, DominatorTree *DT) 368239462Sdim : BeforeHere(I), DT(DT), Captured(false) {} 369226633Sdim 370239462Sdim void tooManyUses() { Captured = true; } 371239462Sdim 372239462Sdim bool shouldExplore(Use *U) { 373239462Sdim Instruction *I = cast<Instruction>(U->getUser()); 374239462Sdim BasicBlock *BB = I->getParent(); 375239462Sdim if (BeforeHere != I && 376239462Sdim (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) 377239462Sdim return false; 378239462Sdim return true; 379239462Sdim } 380239462Sdim 381239462Sdim bool captured(Use *U) { 382239462Sdim Instruction *I = cast<Instruction>(U->getUser()); 383239462Sdim BasicBlock *BB = I->getParent(); 384239462Sdim if (BeforeHere != I && 385239462Sdim (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I))) 386239462Sdim return false; 387239462Sdim Captured = true; 388239462Sdim return true; 389239462Sdim } 390239462Sdim 391239462Sdim const Instruction *BeforeHere; 392239462Sdim DominatorTree *DT; 393239462Sdim 394239462Sdim bool Captured; 395239462Sdim }; 396239462Sdim} 397239462Sdim 398239462Sdim// FIXME: this is really just shoring-up a deficiency in alias analysis. 399239462Sdim// BasicAA isn't willing to spend linear time determining whether an alloca 400239462Sdim// was captured before or after this particular call, while we are. However, 401239462Sdim// with a smarter AA in place, this test is just wasting compile time. 402239462SdimAliasAnalysis::ModRefResult 403239462SdimAliasAnalysis::callCapturesBefore(const Instruction *I, 404239462Sdim const AliasAnalysis::Location &MemLoc, 405239462Sdim DominatorTree *DT) { 406239462Sdim if (!DT || !TD) return AliasAnalysis::ModRef; 407239462Sdim 408239462Sdim const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD); 409239462Sdim if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 410239462Sdim isa<Constant>(Object)) 411239462Sdim return AliasAnalysis::ModRef; 412239462Sdim 413239462Sdim ImmutableCallSite CS(I); 414239462Sdim if (!CS.getInstruction() || CS.getInstruction() == Object) 415239462Sdim return AliasAnalysis::ModRef; 416239462Sdim 417239462Sdim CapturesBefore CB(I, DT); 418239462Sdim llvm::PointerMayBeCaptured(Object, &CB); 419239462Sdim if (CB.Captured) 420239462Sdim return AliasAnalysis::ModRef; 421239462Sdim 422239462Sdim unsigned ArgNo = 0; 423239462Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 424239462Sdim CI != CE; ++CI, ++ArgNo) { 425239462Sdim // Only look at the no-capture or byval pointer arguments. If this 426239462Sdim // pointer were passed to arguments that were neither of these, then it 427239462Sdim // couldn't be no-capture. 428239462Sdim if (!(*CI)->getType()->isPointerTy() || 429239462Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 430239462Sdim continue; 431239462Sdim 432239462Sdim // If this is a no-capture pointer argument, see if we can tell that it 433239462Sdim // is impossible to alias the pointer we're checking. If not, we have to 434239462Sdim // assume that the call could touch the pointer, even though it doesn't 435239462Sdim // escape. 436239462Sdim if (!isNoAlias(AliasAnalysis::Location(*CI), 437239462Sdim AliasAnalysis::Location(Object))) { 438239462Sdim return AliasAnalysis::ModRef; 439239462Sdim } 440239462Sdim } 441239462Sdim return AliasAnalysis::NoModRef; 442239462Sdim} 443239462Sdim 444193323Sed// AliasAnalysis destructor: DO NOT move this to the header file for 445193323Sed// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 446193323Sed// the AliasAnalysis.o file in the current .a file, causing alias analysis 447193323Sed// support to not be included in the tool correctly! 448193323Sed// 449193323SedAliasAnalysis::~AliasAnalysis() {} 450193323Sed 451193323Sed/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 452193323Sed/// AliasAnalysis interface before any other methods are called. 453193323Sed/// 454193323Sedvoid AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 455243830Sdim TD = P->getAnalysisIfAvailable<DataLayout>(); 456243830Sdim TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 457193323Sed AA = &P->getAnalysis<AliasAnalysis>(); 458193323Sed} 459193323Sed 460193323Sed// getAnalysisUsage - All alias analysis implementations should invoke this 461198090Srdivacky// directly (using AliasAnalysis::getAnalysisUsage(AU)). 462193323Sedvoid AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 463193323Sed AU.addRequired<AliasAnalysis>(); // All AA's chain 464193323Sed} 465193323Sed 466243830Sdim/// getTypeStoreSize - Return the DataLayout store size for the given type, 467198090Srdivacky/// if known, or a conservative value otherwise. 468198090Srdivacky/// 469226633Sdimuint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 470218893Sdim return TD ? TD->getTypeStoreSize(Ty) : UnknownSize; 471198090Srdivacky} 472198090Srdivacky 473193323Sed/// canBasicBlockModify - Return true if it is possible for execution of the 474193323Sed/// specified basic block to modify the value pointed to by Ptr. 475193323Sed/// 476193323Sedbool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 477218893Sdim const Location &Loc) { 478218893Sdim return canInstructionRangeModify(BB.front(), BB.back(), Loc); 479193323Sed} 480193323Sed 481193323Sed/// canInstructionRangeModify - Return true if it is possible for the execution 482193323Sed/// of the specified instructions to modify the value pointed to by Ptr. The 483193323Sed/// instructions to consider are all of the instructions in the range of [I1,I2] 484193323Sed/// INCLUSIVE. I1 and I2 must be in the same basic block. 485193323Sed/// 486193323Sedbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 487193323Sed const Instruction &I2, 488218893Sdim const Location &Loc) { 489193323Sed assert(I1.getParent() == I2.getParent() && 490193323Sed "Instructions not in same basic block!"); 491212904Sdim BasicBlock::const_iterator I = &I1; 492212904Sdim BasicBlock::const_iterator E = &I2; 493193323Sed ++E; // Convert from inclusive to exclusive range. 494193323Sed 495193323Sed for (; I != E; ++I) // Check every instruction in range 496218893Sdim if (getModRefInfo(I, Loc) & Mod) 497193323Sed return true; 498193323Sed return false; 499193323Sed} 500193323Sed 501193323Sed/// isNoAliasCall - Return true if this pointer is returned by a noalias 502193323Sed/// function. 503193323Sedbool llvm::isNoAliasCall(const Value *V) { 504193323Sed if (isa<CallInst>(V) || isa<InvokeInst>(V)) 505212904Sdim return ImmutableCallSite(cast<Instruction>(V)) 506243830Sdim .paramHasAttr(0, Attributes::NoAlias); 507193323Sed return false; 508193323Sed} 509193323Sed 510193323Sed/// isIdentifiedObject - Return true if this pointer refers to a distinct and 511193323Sed/// identifiable object. This returns true for: 512198090Srdivacky/// Global Variables and Functions (but not Global Aliases) 513193323Sed/// Allocas and Mallocs 514193323Sed/// ByVal and NoAlias Arguments 515193323Sed/// NoAlias returns 516193323Sed/// 517193323Sedbool llvm::isIdentifiedObject(const Value *V) { 518210299Sed if (isa<AllocaInst>(V)) 519193323Sed return true; 520198090Srdivacky if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 521198090Srdivacky return true; 522210299Sed if (isNoAliasCall(V)) 523210299Sed return true; 524193323Sed if (const Argument *A = dyn_cast<Argument>(V)) 525193323Sed return A->hasNoAliasAttr() || A->hasByValAttr(); 526193323Sed return false; 527193323Sed} 528234353Sdim 529234353Sdim/// isKnownNonNull - Return true if we know that the specified value is never 530234353Sdim/// null. 531234353Sdimbool llvm::isKnownNonNull(const Value *V) { 532234353Sdim // Alloca never returns null, malloc might. 533234353Sdim if (isa<AllocaInst>(V)) return true; 534234353Sdim 535234353Sdim // A byval argument is never null. 536234353Sdim if (const Argument *A = dyn_cast<Argument>(V)) 537234353Sdim return A->hasByValAttr(); 538234353Sdim 539234353Sdim // Global values are not null unless extern weak. 540234353Sdim if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 541234353Sdim return !GV->hasExternalWeakLinkage(); 542234353Sdim return false; 543234353Sdim} 544