AliasAnalysis.cpp revision 280031
1341825Sdim//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 2199482Srdivacky// 3353358Sdim// The LLVM Compiler Infrastructure 4353358Sdim// 5353358Sdim// This file is distributed under the University of Illinois Open Source 6199482Srdivacky// License. See LICENSE.TXT for details. 7199482Srdivacky// 8199482Srdivacky//===----------------------------------------------------------------------===// 9199482Srdivacky// 10199482Srdivacky// This file implements the generic AliasAnalysis interface which is used as the 11199482Srdivacky// common interface used by all clients and implementations of alias analysis. 12353358Sdim// 13360784Sdim// This file also implements the default version of the AliasAnalysis interface 14199482Srdivacky// that is to be used when no other implementation is specified. This does some 15360784Sdim// simple tests that detect obvious cases: two different global pointers cannot 16296417Sdim// alias, a global cannot alias a malloc, two different mallocs cannot alias, 17199482Srdivacky// etc. 18341825Sdim// 19341825Sdim// This alias analysis implementation really isn't very good for anything, but 20199482Srdivacky// it is very fast, and makes a nice clean default implementation. Because it 21360784Sdim// handles lots of little corner cases, other, more complex, alias analysis 22199482Srdivacky// implementations may choose to rely on this pass to resolve these simple and 23199482Srdivacky// easy cases. 24243830Sdim// 25341825Sdim//===----------------------------------------------------------------------===// 26243830Sdim 27243830Sdim#include "llvm/Analysis/AliasAnalysis.h" 28341825Sdim#include "llvm/Analysis/CFG.h" 29341825Sdim#include "llvm/Analysis/CaptureTracking.h" 30199482Srdivacky#include "llvm/Analysis/ValueTracking.h" 31199482Srdivacky#include "llvm/IR/BasicBlock.h" 32199482Srdivacky#include "llvm/IR/DataLayout.h" 33199482Srdivacky#include "llvm/IR/Dominators.h" 34341825Sdim#include "llvm/IR/Function.h" 35341825Sdim#include "llvm/IR/Instructions.h" 36341825Sdim#include "llvm/IR/IntrinsicInst.h" 37341825Sdim#include "llvm/IR/LLVMContext.h" 38341825Sdim#include "llvm/IR/Type.h" 39341825Sdim#include "llvm/Pass.h" 40341825Sdim#include "llvm/Target/TargetLibraryInfo.h" 41341825Sdimusing namespace llvm; 42341825Sdim 43341825Sdim// Register the AliasAnalysis interface, providing a nice name to refer to. 44341825SdimINITIALIZE_ANALYSIS_GROUP(AliasAnalysis, "Alias Analysis", NoAA) 45341825Sdimchar AliasAnalysis::ID = 0; 46341825Sdim 47341825Sdim//===----------------------------------------------------------------------===// 48341825Sdim// Default chaining methods 49341825Sdim//===----------------------------------------------------------------------===// 50341825Sdim 51341825SdimAliasAnalysis::AliasResult 52341825SdimAliasAnalysis::alias(const Location &LocA, const Location &LocB) { 53341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54341825Sdim return AA->alias(LocA, LocB); 55341825Sdim} 56341825Sdim 57341825Sdimbool AliasAnalysis::pointsToConstantMemory(const Location &Loc, 58341825Sdim bool OrLocal) { 59341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 60341825Sdim return AA->pointsToConstantMemory(Loc, OrLocal); 61341825Sdim} 62341825Sdim 63341825SdimAliasAnalysis::Location 64341825SdimAliasAnalysis::getArgLocation(ImmutableCallSite CS, unsigned ArgIdx, 65341825Sdim AliasAnalysis::ModRefResult &Mask) { 66341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 67341825Sdim return AA->getArgLocation(CS, ArgIdx, Mask); 68341825Sdim} 69341825Sdim 70341825Sdimvoid AliasAnalysis::deleteValue(Value *V) { 71341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 72341825Sdim AA->deleteValue(V); 73341825Sdim} 74341825Sdim 75341825Sdimvoid AliasAnalysis::copyValue(Value *From, Value *To) { 76341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 77341825Sdim AA->copyValue(From, To); 78341825Sdim} 79341825Sdim 80341825Sdimvoid AliasAnalysis::addEscapingUse(Use &U) { 81341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 82341825Sdim AA->addEscapingUse(U); 83341825Sdim} 84341825Sdim 85341825Sdim 86344779SdimAliasAnalysis::ModRefResult 87344779SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 88344779Sdim const Location &Loc) { 89341825Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 90341825Sdim 91341825Sdim ModRefBehavior MRB = getModRefBehavior(CS); 92353358Sdim if (MRB == DoesNotAccessMemory) 93360784Sdim return NoModRef; 94353358Sdim 95341825Sdim ModRefResult Mask = ModRef; 96341825Sdim if (onlyReadsMemory(MRB)) 97341825Sdim Mask = Ref; 98341825Sdim 99341825Sdim if (onlyAccessesArgPointees(MRB)) { 100341825Sdim bool doesAlias = false; 101341825Sdim ModRefResult AllArgsMask = NoModRef; 102341825Sdim if (doesAccessArgPointees(MRB)) { 103341825Sdim for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 104341825Sdim AI != AE; ++AI) { 105341825Sdim const Value *Arg = *AI; 106341825Sdim if (!Arg->getType()->isPointerTy()) 107341825Sdim continue; 108341825Sdim ModRefResult ArgMask; 109341825Sdim Location CSLoc = 110341825Sdim getArgLocation(CS, (unsigned) std::distance(CS.arg_begin(), AI), 111341825Sdim ArgMask); 112341825Sdim if (!isNoAlias(CSLoc, Loc)) { 113341825Sdim doesAlias = true; 114341825Sdim AllArgsMask = ModRefResult(AllArgsMask | ArgMask); 115341825Sdim } 116341825Sdim } 117341825Sdim } 118341825Sdim if (!doesAlias) 119341825Sdim return NoModRef; 120341825Sdim Mask = ModRefResult(Mask & AllArgsMask); 121341825Sdim } 122341825Sdim 123341825Sdim // If Loc is a constant memory location, the call definitely could not 124341825Sdim // modify the memory location. 125341825Sdim if ((Mask & Mod) && pointsToConstantMemory(Loc)) 126341825Sdim Mask = ModRefResult(Mask & ~Mod); 127341825Sdim 128341825Sdim // If this is the end of the chain, don't forward. 129341825Sdim if (!AA) return Mask; 130341825Sdim 131341825Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 132341825Sdim // in any mask we've managed to compute. 133341825Sdim return ModRefResult(AA->getModRefInfo(CS, Loc) & Mask); 134341825Sdim} 135353358Sdim 136353358SdimAliasAnalysis::ModRefResult 137353358SdimAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 138353358Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 139341825Sdim 140341825Sdim // If CS1 or CS2 are readnone, they don't interact. 141341825Sdim ModRefBehavior CS1B = getModRefBehavior(CS1); 142341825Sdim if (CS1B == DoesNotAccessMemory) return NoModRef; 143321369Sdim 144321369Sdim ModRefBehavior CS2B = getModRefBehavior(CS2); 145321369Sdim if (CS2B == DoesNotAccessMemory) return NoModRef; 146360784Sdim 147321369Sdim // If they both only read from memory, there is no dependence. 148321369Sdim if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B)) 149321369Sdim return NoModRef; 150321369Sdim 151321369Sdim AliasAnalysis::ModRefResult Mask = ModRef; 152321369Sdim 153321369Sdim // If CS1 only reads memory, the only dependence on CS2 can be 154321369Sdim // from CS1 reading memory written by CS2. 155321369Sdim if (onlyReadsMemory(CS1B)) 156321369Sdim Mask = ModRefResult(Mask & Ref); 157321369Sdim 158360784Sdim // If CS2 only access memory through arguments, accumulate the mod/ref 159321369Sdim // information from CS1's references to the memory referenced by 160321369Sdim // CS2's arguments. 161321369Sdim if (onlyAccessesArgPointees(CS2B)) { 162321369Sdim AliasAnalysis::ModRefResult R = NoModRef; 163321369Sdim if (doesAccessArgPointees(CS2B)) { 164321369Sdim for (ImmutableCallSite::arg_iterator 165321369Sdim I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { 166321369Sdim const Value *Arg = *I; 167360784Sdim if (!Arg->getType()->isPointerTy()) 168321369Sdim continue; 169321369Sdim ModRefResult ArgMask; 170360784Sdim Location CS2Loc = 171360784Sdim getArgLocation(CS2, (unsigned) std::distance(CS2.arg_begin(), I), 172360784Sdim ArgMask); 173321369Sdim // ArgMask indicates what CS2 might do to CS2Loc, and the dependence of 174321369Sdim // CS1 on that location is the inverse. 175321369Sdim if (ArgMask == Mod) 176321369Sdim ArgMask = ModRef; 177341825Sdim else if (ArgMask == Ref) 178321369Sdim ArgMask = Mod; 179321369Sdim 180321369Sdim R = ModRefResult((R | (getModRefInfo(CS1, CS2Loc) & ArgMask)) & Mask); 181234353Sdim if (R == Mask) 182234353Sdim break; 183341825Sdim } 184243830Sdim } 185341825Sdim return R; 186234353Sdim } 187234353Sdim 188327952Sdim // If CS1 only accesses memory through arguments, check if CS2 references 189327952Sdim // any of the memory referenced by CS1's arguments. If not, return NoModRef. 190327952Sdim if (onlyAccessesArgPointees(CS1B)) { 191353358Sdim AliasAnalysis::ModRefResult R = NoModRef; 192243830Sdim if (doesAccessArgPointees(CS1B)) { 193341825Sdim for (ImmutableCallSite::arg_iterator 194234353Sdim I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { 195234353Sdim const Value *Arg = *I; 196341825Sdim if (!Arg->getType()->isPointerTy()) 197327952Sdim continue; 198243830Sdim ModRefResult ArgMask; 199243830Sdim Location CS1Loc = getArgLocation( 200341825Sdim CS1, (unsigned)std::distance(CS1.arg_begin(), I), ArgMask); 201234353Sdim // ArgMask indicates what CS1 might do to CS1Loc; if CS1 might Mod 202341825Sdim // CS1Loc, then we care about either a Mod or a Ref by CS2. If CS1 203353358Sdim // might Ref, then we care only about a Mod by CS2. 204243830Sdim ModRefResult ArgR = getModRefInfo(CS2, CS1Loc); 205341825Sdim if (((ArgMask & Mod) != NoModRef && (ArgR & ModRef) != NoModRef) || 206243830Sdim ((ArgMask & Ref) != NoModRef && (ArgR & Mod) != NoModRef)) 207243830Sdim R = ModRefResult((R | ArgMask) & Mask); 208243830Sdim 209243830Sdim if (R == Mask) 210276479Sdim break; 211243830Sdim } 212276479Sdim } 213321369Sdim return R; 214243830Sdim } 215243830Sdim 216243830Sdim // If this is the end of the chain, don't forward. 217243830Sdim if (!AA) return Mask; 218243830Sdim 219341825Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 220353358Sdim // in any mask we've managed to compute. 221243830Sdim return ModRefResult(AA->getModRefInfo(CS1, CS2) & Mask); 222243830Sdim} 223243830Sdim 224234353SdimAliasAnalysis::ModRefBehavior 225239462SdimAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 226199482Srdivacky assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 227199482Srdivacky 228199482Srdivacky ModRefBehavior Min = UnknownModRefBehavior; 229341825Sdim 230341825Sdim // Call back into the alias analysis with the other form of getModRefBehavior 231199482Srdivacky // to see if it can give a better response. 232341825Sdim if (const Function *F = CS.getCalledFunction()) 233341825Sdim Min = getModRefBehavior(F); 234341825Sdim 235341825Sdim // If this is the end of the chain, don't forward. 236341825Sdim if (!AA) return Min; 237341825Sdim 238341825Sdim // Otherwise, fall back to the next AA in the chain. But we can merge 239341825Sdim // in any result we've managed to compute. 240341825Sdim return ModRefBehavior(AA->getModRefBehavior(CS) & Min); 241341825Sdim} 242341825Sdim 243341825SdimAliasAnalysis::ModRefBehavior 244341825SdimAliasAnalysis::getModRefBehavior(const Function *F) { 245353358Sdim assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 246353358Sdim return AA->getModRefBehavior(F); 247353358Sdim} 248353358Sdim 249353358Sdim//===----------------------------------------------------------------------===// 250353358Sdim// AliasAnalysis non-virtual helper method implementation 251341825Sdim//===----------------------------------------------------------------------===// 252341825Sdim 253341825SdimAliasAnalysis::Location AliasAnalysis::getLocation(const LoadInst *LI) { 254341825Sdim AAMDNodes AATags; 255341825Sdim LI->getAAMetadata(AATags); 256341825Sdim 257341825Sdim return Location(LI->getPointerOperand(), 258341825Sdim getTypeStoreSize(LI->getType()), AATags); 259341825Sdim} 260341825Sdim 261341825SdimAliasAnalysis::Location AliasAnalysis::getLocation(const StoreInst *SI) { 262341825Sdim AAMDNodes AATags; 263341825Sdim SI->getAAMetadata(AATags); 264341825Sdim 265341825Sdim return Location(SI->getPointerOperand(), 266341825Sdim getTypeStoreSize(SI->getValueOperand()->getType()), AATags); 267341825Sdim} 268341825Sdim 269341825SdimAliasAnalysis::Location AliasAnalysis::getLocation(const VAArgInst *VI) { 270341825Sdim AAMDNodes AATags; 271341825Sdim VI->getAAMetadata(AATags); 272341825Sdim 273341825Sdim return Location(VI->getPointerOperand(), UnknownSize, AATags); 274341825Sdim} 275341825Sdim 276341825SdimAliasAnalysis::Location 277341825SdimAliasAnalysis::getLocation(const AtomicCmpXchgInst *CXI) { 278341825Sdim AAMDNodes AATags; 279341825Sdim CXI->getAAMetadata(AATags); 280341825Sdim 281341825Sdim return Location(CXI->getPointerOperand(), 282341825Sdim getTypeStoreSize(CXI->getCompareOperand()->getType()), 283341825Sdim AATags); 284341825Sdim} 285341825Sdim 286341825SdimAliasAnalysis::Location 287341825SdimAliasAnalysis::getLocation(const AtomicRMWInst *RMWI) { 288341825Sdim AAMDNodes AATags; 289341825Sdim RMWI->getAAMetadata(AATags); 290341825Sdim 291341825Sdim return Location(RMWI->getPointerOperand(), 292341825Sdim getTypeStoreSize(RMWI->getValOperand()->getType()), AATags); 293341825Sdim} 294341825Sdim 295341825SdimAliasAnalysis::Location 296341825SdimAliasAnalysis::getLocationForSource(const MemTransferInst *MTI) { 297360784Sdim uint64_t Size = UnknownSize; 298360784Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 299360784Sdim Size = C->getValue().getZExtValue(); 300239462Sdim 301239462Sdim // memcpy/memmove can have AA tags. For memcpy, they apply 302353358Sdim // to both the source and the destination. 303353358Sdim AAMDNodes AATags; 304353358Sdim MTI->getAAMetadata(AATags); 305224145Sdim 306224145Sdim return Location(MTI->getRawSource(), Size, AATags); 307224145Sdim} 308224145Sdim 309224145SdimAliasAnalysis::Location 310341825SdimAliasAnalysis::getLocationForDest(const MemIntrinsic *MTI) { 311224145Sdim uint64_t Size = UnknownSize; 312234353Sdim if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength())) 313234353Sdim Size = C->getValue().getZExtValue(); 314341825Sdim 315341825Sdim // memcpy/memmove can have AA tags. For memcpy, they apply 316234353Sdim // to both the source and the destination. 317341825Sdim AAMDNodes AATags; 318341825Sdim MTI->getAAMetadata(AATags); 319261991Sdim 320341825Sdim return Location(MTI->getRawDest(), Size, AATags); 321341825Sdim} 322261991Sdim 323341825Sdim 324341825Sdim 325261991SdimAliasAnalysis::ModRefResult 326341825SdimAliasAnalysis::getModRefInfo(const LoadInst *L, const Location &Loc) { 327341825Sdim // Be conservative in the face of volatile/atomic. 328261991Sdim if (!L->isUnordered()) 329341825Sdim return ModRef; 330341825Sdim 331261991Sdim // If the load address doesn't alias the given address, it doesn't read 332341825Sdim // or write the specified memory. 333341825Sdim if (!alias(getLocation(L), Loc)) 334261991Sdim return NoModRef; 335341825Sdim 336341825Sdim // Otherwise, a load just reads. 337261991Sdim return Ref; 338341825Sdim} 339341825Sdim 340261991SdimAliasAnalysis::ModRefResult 341341825SdimAliasAnalysis::getModRefInfo(const StoreInst *S, const Location &Loc) { 342341825Sdim // Be conservative in the face of volatile/atomic. 343261991Sdim if (!S->isUnordered()) 344341825Sdim return ModRef; 345341825Sdim 346261991Sdim // If the store address cannot alias the pointer in question, then the 347341825Sdim // specified memory cannot be modified by the store. 348341825Sdim if (!alias(getLocation(S), Loc)) 349261991Sdim return NoModRef; 350341825Sdim 351341825Sdim // If the pointer is a pointer to constant memory, then it could not have been 352276479Sdim // modified by this store. 353341825Sdim if (pointsToConstantMemory(Loc)) 354341825Sdim return NoModRef; 355280031Sdim 356341825Sdim // Otherwise, a store just writes. 357261991Sdim return Mod; 358261991Sdim} 359261991Sdim 360276479SdimAliasAnalysis::ModRefResult 361276479SdimAliasAnalysis::getModRefInfo(const VAArgInst *V, const Location &Loc) { 362280031Sdim // If the va_arg address cannot alias the pointer in question, then the 363280031Sdim // specified memory cannot be accessed by the va_arg. 364234353Sdim if (!alias(getLocation(V), Loc)) 365341825Sdim return NoModRef; 366261991Sdim 367234353Sdim // If the pointer is a pointer to constant memory, then it could not have been 368234353Sdim // modified by this va_arg. 369226633Sdim if (pointsToConstantMemory(Loc)) 370224145Sdim return NoModRef; 371199482Srdivacky 372360784Sdim // Otherwise, a va_arg reads and writes. 373199482Srdivacky return ModRef; 374321369Sdim} 375321369Sdim 376321369SdimAliasAnalysis::ModRefResult 377321369SdimAliasAnalysis::getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc) { 378199482Srdivacky // Acquire/Release cmpxchg has properties that matter for arbitrary addresses. 379199482Srdivacky if (CX->getSuccessOrdering() > Monotonic) 380199482Srdivacky return ModRef; 381207619Srdivacky 382207619Srdivacky // If the cmpxchg address does not alias the location, it does not access it. 383199482Srdivacky if (!alias(getLocation(CX), Loc)) 384239462Sdim return NoModRef; 385239462Sdim 386239462Sdim return ModRef; 387199482Srdivacky} 388199482Srdivacky 389199482SrdivackyAliasAnalysis::ModRefResult 390199482SrdivackyAliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) { 391341825Sdim // Acquire/Release atomicrmw has properties that matter for arbitrary addresses. 392199482Srdivacky if (RMW->getOrdering() > Monotonic) 393199482Srdivacky return ModRef; 394199482Srdivacky 395199482Srdivacky // If the atomicrmw address does not alias the location, it does not access it. 396309124Sdim if (!alias(getLocation(RMW), Loc)) 397309124Sdim return NoModRef; 398210299Sed 399218893Sdim return ModRef; 400218893Sdim} 401218893Sdim 402200583Srdivacky// FIXME: this is really just shoring-up a deficiency in alias analysis. 403200583Srdivacky// BasicAA isn't willing to spend linear time determining whether an alloca 404200583Srdivacky// was captured before or after this particular call, while we are. However, 405296417Sdim// with a smarter AA in place, this test is just wasting compile time. 406314564SdimAliasAnalysis::ModRefResult 407296417SdimAliasAnalysis::callCapturesBefore(const Instruction *I, 408341825Sdim const AliasAnalysis::Location &MemLoc, 409280031Sdim DominatorTree *DT) { 410280031Sdim if (!DT || !DL) return AliasAnalysis::ModRef; 411341825Sdim 412280031Sdim const Value *Object = GetUnderlyingObject(MemLoc.Ptr, DL); 413280031Sdim if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) || 414280031Sdim isa<Constant>(Object)) 415341825Sdim return AliasAnalysis::ModRef; 416296417Sdim 417296417Sdim ImmutableCallSite CS(I); 418341825Sdim if (!CS.getInstruction() || CS.getInstruction() == Object) 419203955Srdivacky return AliasAnalysis::ModRef; 420203955Srdivacky 421341825Sdim if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true, 422207619Srdivacky /* StoreCaptures */ true, I, DT, 423207619Srdivacky /* include Object */ true)) 424207619Srdivacky return AliasAnalysis::ModRef; 425341825Sdim 426234353Sdim unsigned ArgNo = 0; 427234353Sdim AliasAnalysis::ModRefResult R = AliasAnalysis::NoModRef; 428296417Sdim for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 429341825Sdim CI != CE; ++CI, ++ArgNo) { 430296417Sdim // Only look at the no-capture or byval pointer arguments. If this 431296417Sdim // pointer were passed to arguments that were neither of these, then it 432314564Sdim // couldn't be no-capture. 433314564Sdim if (!(*CI)->getType()->isPointerTy() || 434314564Sdim (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo))) 435360784Sdim continue; 436360784Sdim 437360784Sdim // If this is a no-capture pointer argument, see if we can tell that it 438199482Srdivacky // is impossible to alias the pointer we're checking. If not, we have to 439341825Sdim // assume that the call could touch the pointer, even though it doesn't 440341825Sdim // escape. 441353358Sdim if (isNoAlias(AliasAnalysis::Location(*CI), 442353358Sdim AliasAnalysis::Location(Object))) 443353358Sdim continue; 444353358Sdim if (CS.doesNotAccessMemory(ArgNo)) 445353358Sdim continue; 446353358Sdim if (CS.onlyReadsMemory(ArgNo)) { 447353358Sdim R = AliasAnalysis::Ref; 448360784Sdim continue; 449199482Srdivacky } 450199482Srdivacky return AliasAnalysis::ModRef; 451360784Sdim } 452199482Srdivacky return R; 453360784Sdim} 454321369Sdim 455226633Sdim// AliasAnalysis destructor: DO NOT move this to the header file for 456199482Srdivacky// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 457199482Srdivacky// the AliasAnalysis.o file in the current .a file, causing alias analysis 458341825Sdim// support to not be included in the tool correctly! 459199482Srdivacky// 460341825SdimAliasAnalysis::~AliasAnalysis() {} 461 462/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 463/// AliasAnalysis interface before any other methods are called. 464/// 465void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 466 DataLayoutPass *DLP = P->getAnalysisIfAvailable<DataLayoutPass>(); 467 DL = DLP ? &DLP->getDataLayout() : nullptr; 468 TLI = P->getAnalysisIfAvailable<TargetLibraryInfo>(); 469 AA = &P->getAnalysis<AliasAnalysis>(); 470} 471 472// getAnalysisUsage - All alias analysis implementations should invoke this 473// directly (using AliasAnalysis::getAnalysisUsage(AU)). 474void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 475 AU.addRequired<AliasAnalysis>(); // All AA's chain 476} 477 478/// getTypeStoreSize - Return the DataLayout store size for the given type, 479/// if known, or a conservative value otherwise. 480/// 481uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) { 482 return DL ? DL->getTypeStoreSize(Ty) : UnknownSize; 483} 484 485/// canBasicBlockModify - Return true if it is possible for execution of the 486/// specified basic block to modify the location Loc. 487/// 488bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 489 const Location &Loc) { 490 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod); 491} 492 493/// canInstructionRangeModRef - Return true if it is possible for the 494/// execution of the specified instructions to mod\ref (according to the 495/// mode) the location Loc. The instructions to consider are all 496/// of the instructions in the range of [I1,I2] INCLUSIVE. 497/// I1 and I2 must be in the same basic block. 498bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1, 499 const Instruction &I2, 500 const Location &Loc, 501 const ModRefResult Mode) { 502 assert(I1.getParent() == I2.getParent() && 503 "Instructions not in same basic block!"); 504 BasicBlock::const_iterator I = &I1; 505 BasicBlock::const_iterator E = &I2; 506 ++E; // Convert from inclusive to exclusive range. 507 508 for (; I != E; ++I) // Check every instruction in range 509 if (getModRefInfo(I, Loc) & Mode) 510 return true; 511 return false; 512} 513 514/// isNoAliasCall - Return true if this pointer is returned by a noalias 515/// function. 516bool llvm::isNoAliasCall(const Value *V) { 517 if (isa<CallInst>(V) || isa<InvokeInst>(V)) 518 return ImmutableCallSite(cast<Instruction>(V)) 519 .paramHasAttr(0, Attribute::NoAlias); 520 return false; 521} 522 523/// isNoAliasArgument - Return true if this is an argument with the noalias 524/// attribute. 525bool llvm::isNoAliasArgument(const Value *V) 526{ 527 if (const Argument *A = dyn_cast<Argument>(V)) 528 return A->hasNoAliasAttr(); 529 return false; 530} 531 532/// isIdentifiedObject - Return true if this pointer refers to a distinct and 533/// identifiable object. This returns true for: 534/// Global Variables and Functions (but not Global Aliases) 535/// Allocas and Mallocs 536/// ByVal and NoAlias Arguments 537/// NoAlias returns 538/// 539bool llvm::isIdentifiedObject(const Value *V) { 540 if (isa<AllocaInst>(V)) 541 return true; 542 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 543 return true; 544 if (isNoAliasCall(V)) 545 return true; 546 if (const Argument *A = dyn_cast<Argument>(V)) 547 return A->hasNoAliasAttr() || A->hasByValAttr(); 548 return false; 549} 550 551/// isIdentifiedFunctionLocal - Return true if V is umabigously identified 552/// at the function-level. Different IdentifiedFunctionLocals can't alias. 553/// Further, an IdentifiedFunctionLocal can not alias with any function 554/// arguments other than itself, which is not necessarily true for 555/// IdentifiedObjects. 556bool llvm::isIdentifiedFunctionLocal(const Value *V) 557{ 558 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V); 559} 560