1193323Sed//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 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 defines the generic AliasAnalysis interface, which is used as the 11193323Sed// common interface used by all clients of alias analysis information, and 12193323Sed// implemented by all alias analysis implementations. Mod/Ref information is 13193323Sed// also captured by this interface. 14193323Sed// 15193323Sed// Implementations of this interface must implement the various virtual methods, 16193323Sed// which automatically provides functionality for the entire suite of client 17193323Sed// APIs. 18193323Sed// 19218893Sdim// This API identifies memory regions with the Location class. The pointer 20218893Sdim// component specifies the base memory address of the region. The Size specifies 21218893Sdim// the maximum size (in address units) of the memory region, or UnknownSize if 22218893Sdim// the size is not known. The TBAA tag identifies the "type" of the memory 23218893Sdim// reference; see the TypeBasedAliasAnalysis class for details. 24193323Sed// 25218893Sdim// Some non-obvious details include: 26218893Sdim// - Pointers that point to two completely different objects in memory never 27218893Sdim// alias, regardless of the value of the Size component. 28218893Sdim// - NoAlias doesn't imply inequal pointers. The most obvious example of this 29218893Sdim// is two pointers to constant memory. Even if they are equal, constant 30218893Sdim// memory is never stored to, so there will never be any dependencies. 31218893Sdim// In this and other situations, the pointers may be both NoAlias and 32218893Sdim// MustAlias at the same time. The current API can only return one result, 33218893Sdim// though this is rarely a problem in practice. 34218893Sdim// 35193323Sed//===----------------------------------------------------------------------===// 36193323Sed 37252723Sdim#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H 38252723Sdim#define LLVM_ANALYSIS_ALIASANALYSIS_H 39193323Sed 40252723Sdim#include "llvm/ADT/DenseMap.h" 41193323Sed#include "llvm/Support/CallSite.h" 42193323Sed 43193323Sednamespace llvm { 44193323Sed 45193323Sedclass LoadInst; 46193323Sedclass StoreInst; 47193323Sedclass VAArgInst; 48245431Sdimclass DataLayout; 49245431Sdimclass TargetLibraryInfo; 50193323Sedclass Pass; 51193323Sedclass AnalysisUsage; 52218893Sdimclass MemTransferInst; 53218893Sdimclass MemIntrinsic; 54245431Sdimclass DominatorTree; 55193323Sed 56193323Sedclass AliasAnalysis { 57193323Sedprotected: 58245431Sdim const DataLayout *TD; 59245431Sdim const TargetLibraryInfo *TLI; 60212904Sdim 61212904Sdimprivate: 62193323Sed AliasAnalysis *AA; // Previous Alias Analysis to chain to. 63193323Sed 64212904Sdimprotected: 65193323Sed /// InitializeAliasAnalysis - Subclasses must call this method to initialize 66193323Sed /// the AliasAnalysis interface before any other methods are called. This is 67193323Sed /// typically called by the run* methods of these subclasses. This may be 68193323Sed /// called multiple times. 69193323Sed /// 70193323Sed void InitializeAliasAnalysis(Pass *P); 71193323Sed 72193323Sed /// getAnalysisUsage - All alias analysis implementations should invoke this 73198090Srdivacky /// directly (using AliasAnalysis::getAnalysisUsage(AU)). 74193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const; 75193323Sed 76193323Sedpublic: 77193323Sed static char ID; // Class identification, replacement for typeinfo 78245431Sdim AliasAnalysis() : TD(0), TLI(0), AA(0) {} 79193323Sed virtual ~AliasAnalysis(); // We want to be subclassed 80193323Sed 81212904Sdim /// UnknownSize - This is a special value which can be used with the 82212904Sdim /// size arguments in alias queries to indicate that the caller does not 83212904Sdim /// know the sizes of the potential memory references. 84218893Sdim static uint64_t const UnknownSize = ~UINT64_C(0); 85212904Sdim 86245431Sdim /// getDataLayout - Return a pointer to the current DataLayout object, or 87245431Sdim /// null if no DataLayout object is available. 88193323Sed /// 89245431Sdim const DataLayout *getDataLayout() const { return TD; } 90193323Sed 91245431Sdim /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo 92245431Sdim /// object, or null if no TargetLibraryInfo object is available. 93245431Sdim /// 94245431Sdim const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } 95245431Sdim 96245431Sdim /// getTypeStoreSize - Return the DataLayout store size for the given type, 97198090Srdivacky /// if known, or a conservative value otherwise. 98198090Srdivacky /// 99226890Sdim uint64_t getTypeStoreSize(Type *Ty); 100198090Srdivacky 101193323Sed //===--------------------------------------------------------------------===// 102193323Sed /// Alias Queries... 103193323Sed /// 104193323Sed 105218893Sdim /// Location - A description of a memory location. 106218893Sdim struct Location { 107218893Sdim /// Ptr - The address of the start of the location. 108218893Sdim const Value *Ptr; 109218893Sdim /// Size - The maximum size of the location, in address-units, or 110218893Sdim /// UnknownSize if the size is not known. Note that an unknown size does 111218893Sdim /// not mean the pointer aliases the entire virtual address space, because 112218893Sdim /// there are restrictions on stepping out of one object and into another. 113218893Sdim /// See http://llvm.org/docs/LangRef.html#pointeraliasing 114218893Sdim uint64_t Size; 115218893Sdim /// TBAATag - The metadata node which describes the TBAA type of 116218893Sdim /// the location, or null if there is no known unique tag. 117218893Sdim const MDNode *TBAATag; 118218893Sdim 119218893Sdim explicit Location(const Value *P = 0, uint64_t S = UnknownSize, 120218893Sdim const MDNode *N = 0) 121218893Sdim : Ptr(P), Size(S), TBAATag(N) {} 122218893Sdim 123218893Sdim Location getWithNewPtr(const Value *NewPtr) const { 124218893Sdim Location Copy(*this); 125218893Sdim Copy.Ptr = NewPtr; 126218893Sdim return Copy; 127218893Sdim } 128218893Sdim 129218893Sdim Location getWithNewSize(uint64_t NewSize) const { 130218893Sdim Location Copy(*this); 131218893Sdim Copy.Size = NewSize; 132218893Sdim return Copy; 133218893Sdim } 134218893Sdim 135218893Sdim Location getWithoutTBAATag() const { 136218893Sdim Location Copy(*this); 137218893Sdim Copy.TBAATag = 0; 138218893Sdim return Copy; 139218893Sdim } 140218893Sdim }; 141218893Sdim 142218893Sdim /// getLocation - Fill in Loc with information about the memory reference by 143218893Sdim /// the given instruction. 144218893Sdim Location getLocation(const LoadInst *LI); 145218893Sdim Location getLocation(const StoreInst *SI); 146218893Sdim Location getLocation(const VAArgInst *VI); 147226890Sdim Location getLocation(const AtomicCmpXchgInst *CXI); 148226890Sdim Location getLocation(const AtomicRMWInst *RMWI); 149218893Sdim static Location getLocationForSource(const MemTransferInst *MTI); 150218893Sdim static Location getLocationForDest(const MemIntrinsic *MI); 151218893Sdim 152193323Sed /// Alias analysis result - Either we know for sure that it does not alias, we 153193323Sed /// know for sure it must alias, or we don't know anything: The two pointers 154193323Sed /// _might_ alias. This enum is designed so you can do things like: 155193323Sed /// if (AA.alias(P1, P2)) { ... } 156193323Sed /// to check to see if two pointers might alias. 157193323Sed /// 158212904Sdim /// See docs/AliasAnalysis.html for more information on the specific meanings 159212904Sdim /// of these values. 160212904Sdim /// 161218893Sdim enum AliasResult { 162218893Sdim NoAlias = 0, ///< No dependencies. 163218893Sdim MayAlias, ///< Anything goes. 164218893Sdim PartialAlias, ///< Pointers differ, but pointees overlap. 165218893Sdim MustAlias ///< Pointers are equal. 166218893Sdim }; 167193323Sed 168193323Sed /// alias - The main low level interface to the alias analysis implementation. 169218893Sdim /// Returns an AliasResult indicating whether the two pointers are aliased to 170218893Sdim /// each other. This is the interface that must be implemented by specific 171218893Sdim /// alias analysis implementations. 172218893Sdim virtual AliasResult alias(const Location &LocA, const Location &LocB); 173193323Sed 174218893Sdim /// alias - A convenience wrapper. 175218893Sdim AliasResult alias(const Value *V1, uint64_t V1Size, 176218893Sdim const Value *V2, uint64_t V2Size) { 177218893Sdim return alias(Location(V1, V1Size), Location(V2, V2Size)); 178218893Sdim } 179218893Sdim 180218893Sdim /// alias - A convenience wrapper. 181212904Sdim AliasResult alias(const Value *V1, const Value *V2) { 182212904Sdim return alias(V1, UnknownSize, V2, UnknownSize); 183212904Sdim } 184212904Sdim 185199989Srdivacky /// isNoAlias - A trivial helper function to check to see if the specified 186199989Srdivacky /// pointers are no-alias. 187218893Sdim bool isNoAlias(const Location &LocA, const Location &LocB) { 188218893Sdim return alias(LocA, LocB) == NoAlias; 189199989Srdivacky } 190193323Sed 191218893Sdim /// isNoAlias - A convenience wrapper. 192218893Sdim bool isNoAlias(const Value *V1, uint64_t V1Size, 193218893Sdim const Value *V2, uint64_t V2Size) { 194218893Sdim return isNoAlias(Location(V1, V1Size), Location(V2, V2Size)); 195218893Sdim } 196218893Sdim 197245431Sdim /// isNoAlias - A convenience wrapper. 198245431Sdim bool isNoAlias(const Value *V1, const Value *V2) { 199245431Sdim return isNoAlias(Location(V1), Location(V2)); 200245431Sdim } 201245431Sdim 202218893Sdim /// isMustAlias - A convenience wrapper. 203218893Sdim bool isMustAlias(const Location &LocA, const Location &LocB) { 204218893Sdim return alias(LocA, LocB) == MustAlias; 205218893Sdim } 206193323Sed 207218893Sdim /// isMustAlias - A convenience wrapper. 208218893Sdim bool isMustAlias(const Value *V1, const Value *V2) { 209218893Sdim return alias(V1, 1, V2, 1) == MustAlias; 210218893Sdim } 211218893Sdim 212218893Sdim /// pointsToConstantMemory - If the specified memory location is 213218893Sdim /// known to be constant, return true. If OrLocal is true and the 214218893Sdim /// specified memory location is known to be "local" (derived from 215218893Sdim /// an alloca), return true. Otherwise return false. 216218893Sdim virtual bool pointsToConstantMemory(const Location &Loc, 217218893Sdim bool OrLocal = false); 218218893Sdim 219218893Sdim /// pointsToConstantMemory - A convenient wrapper. 220218893Sdim bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 221218893Sdim return pointsToConstantMemory(Location(P), OrLocal); 222218893Sdim } 223218893Sdim 224193323Sed //===--------------------------------------------------------------------===// 225193323Sed /// Simple mod/ref information... 226193323Sed /// 227193323Sed 228193323Sed /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are 229193323Sed /// bits which may be or'd together. 230193323Sed /// 231193323Sed enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; 232193323Sed 233218893Sdim /// These values define additional bits used to define the 234218893Sdim /// ModRefBehavior values. 235218893Sdim enum { Nowhere = 0, ArgumentPointees = 4, Anywhere = 8 | ArgumentPointees }; 236193323Sed 237193323Sed /// ModRefBehavior - Summary of how a function affects memory in the program. 238193323Sed /// Loads from constant globals are not considered memory accesses for this 239193323Sed /// interface. Also, functions may freely modify stack space local to their 240193323Sed /// invocation without having to report it through these interfaces. 241193323Sed enum ModRefBehavior { 242218893Sdim /// DoesNotAccessMemory - This function does not perform any non-local loads 243218893Sdim /// or stores to memory. 244218893Sdim /// 245218893Sdim /// This property corresponds to the GCC 'const' attribute. 246218893Sdim /// This property corresponds to the LLVM IR 'readnone' attribute. 247218893Sdim /// This property corresponds to the IntrNoMem LLVM intrinsic flag. 248218893Sdim DoesNotAccessMemory = Nowhere | NoModRef, 249193323Sed 250218893Sdim /// OnlyReadsArgumentPointees - The only memory references in this function 251218893Sdim /// (if it has any) are non-volatile loads from objects pointed to by its 252218893Sdim /// pointer-typed arguments, with arbitrary offsets. 253218893Sdim /// 254218893Sdim /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. 255218893Sdim OnlyReadsArgumentPointees = ArgumentPointees | Ref, 256193323Sed 257218893Sdim /// OnlyAccessesArgumentPointees - The only memory references in this 258218893Sdim /// function (if it has any) are non-volatile loads and stores from objects 259218893Sdim /// pointed to by its pointer-typed arguments, with arbitrary offsets. 260218893Sdim /// 261218893Sdim /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag. 262218893Sdim OnlyAccessesArgumentPointees = ArgumentPointees | ModRef, 263193323Sed 264218893Sdim /// OnlyReadsMemory - This function does not perform any non-local stores or 265218893Sdim /// volatile loads, but may read from any memory location. 266218893Sdim /// 267218893Sdim /// This property corresponds to the GCC 'pure' attribute. 268218893Sdim /// This property corresponds to the LLVM IR 'readonly' attribute. 269218893Sdim /// This property corresponds to the IntrReadMem LLVM intrinsic flag. 270218893Sdim OnlyReadsMemory = Anywhere | Ref, 271193323Sed 272218893Sdim /// UnknownModRefBehavior - This indicates that the function could not be 273218893Sdim /// classified into one of the behaviors above. 274218893Sdim UnknownModRefBehavior = Anywhere | ModRef 275193323Sed }; 276193323Sed 277193323Sed /// getModRefBehavior - Return the behavior when calling the given call site. 278212904Sdim virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 279193323Sed 280193323Sed /// getModRefBehavior - Return the behavior when calling the given function. 281193323Sed /// For use when the call site is not known. 282212904Sdim virtual ModRefBehavior getModRefBehavior(const Function *F); 283193323Sed 284193323Sed /// doesNotAccessMemory - If the specified call is known to never read or 285193323Sed /// write memory, return true. If the call only reads from known-constant 286193323Sed /// memory, it is also legal to return true. Calls that unwind the stack 287193323Sed /// are legal for this predicate. 288193323Sed /// 289193323Sed /// Many optimizations (such as CSE and LICM) can be performed on such calls 290193323Sed /// without worrying about aliasing properties, and many calls have this 291193323Sed /// property (e.g. calls to 'sin' and 'cos'). 292193323Sed /// 293193323Sed /// This property corresponds to the GCC 'const' attribute. 294193323Sed /// 295212904Sdim bool doesNotAccessMemory(ImmutableCallSite CS) { 296193323Sed return getModRefBehavior(CS) == DoesNotAccessMemory; 297193323Sed } 298193323Sed 299193323Sed /// doesNotAccessMemory - If the specified function is known to never read or 300193323Sed /// write memory, return true. For use when the call site is not known. 301193323Sed /// 302212904Sdim bool doesNotAccessMemory(const Function *F) { 303193323Sed return getModRefBehavior(F) == DoesNotAccessMemory; 304193323Sed } 305193323Sed 306193323Sed /// onlyReadsMemory - If the specified call is known to only read from 307193323Sed /// non-volatile memory (or not access memory at all), return true. Calls 308193323Sed /// that unwind the stack are legal for this predicate. 309193323Sed /// 310193323Sed /// This property allows many common optimizations to be performed in the 311193323Sed /// absence of interfering store instructions, such as CSE of strlen calls. 312193323Sed /// 313193323Sed /// This property corresponds to the GCC 'pure' attribute. 314193323Sed /// 315212904Sdim bool onlyReadsMemory(ImmutableCallSite CS) { 316218893Sdim return onlyReadsMemory(getModRefBehavior(CS)); 317193323Sed } 318193323Sed 319193323Sed /// onlyReadsMemory - If the specified function is known to only read from 320193323Sed /// non-volatile memory (or not access memory at all), return true. For use 321193323Sed /// when the call site is not known. 322193323Sed /// 323212904Sdim bool onlyReadsMemory(const Function *F) { 324218893Sdim return onlyReadsMemory(getModRefBehavior(F)); 325193323Sed } 326193323Sed 327218893Sdim /// onlyReadsMemory - Return true if functions with the specified behavior are 328218893Sdim /// known to only read from non-volatile memory (or not access memory at all). 329218893Sdim /// 330218893Sdim static bool onlyReadsMemory(ModRefBehavior MRB) { 331218893Sdim return !(MRB & Mod); 332218893Sdim } 333193323Sed 334218893Sdim /// onlyAccessesArgPointees - Return true if functions with the specified 335218893Sdim /// behavior are known to read and write at most from objects pointed to by 336218893Sdim /// their pointer-typed arguments (with arbitrary offsets). 337218893Sdim /// 338218893Sdim static bool onlyAccessesArgPointees(ModRefBehavior MRB) { 339218893Sdim return !(MRB & Anywhere & ~ArgumentPointees); 340218893Sdim } 341218893Sdim 342218893Sdim /// doesAccessArgPointees - Return true if functions with the specified 343235633Sdim /// behavior are known to potentially read or write from objects pointed 344218893Sdim /// to be their pointer-typed arguments (with arbitrary offsets). 345218893Sdim /// 346218893Sdim static bool doesAccessArgPointees(ModRefBehavior MRB) { 347218893Sdim return (MRB & ModRef) && (MRB & ArgumentPointees); 348218893Sdim } 349218893Sdim 350193323Sed /// getModRefInfo - Return information about whether or not an instruction may 351218893Sdim /// read or write the specified memory location. An instruction 352193323Sed /// that doesn't read or write memory may be trivially LICM'd for example. 353218893Sdim ModRefResult getModRefInfo(const Instruction *I, 354218893Sdim const Location &Loc) { 355218893Sdim switch (I->getOpcode()) { 356218893Sdim case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); 357218893Sdim case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); 358218893Sdim case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); 359226890Sdim case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc); 360226890Sdim case Instruction::AtomicCmpXchg: 361226890Sdim return getModRefInfo((const AtomicCmpXchgInst*)I, Loc); 362226890Sdim case Instruction::AtomicRMW: 363226890Sdim return getModRefInfo((const AtomicRMWInst*)I, Loc); 364218893Sdim case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); 365218893Sdim case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); 366218893Sdim default: return NoModRef; 367218893Sdim } 368218893Sdim } 369193323Sed 370218893Sdim /// getModRefInfo - A convenience wrapper. 371218893Sdim ModRefResult getModRefInfo(const Instruction *I, 372218893Sdim const Value *P, uint64_t Size) { 373218893Sdim return getModRefInfo(I, Location(P, Size)); 374218893Sdim } 375218893Sdim 376252723Sdim /// getModRefInfo (for call sites) - Return information about whether 377218893Sdim /// a particular call site modifies or reads the specified memory location. 378212904Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 379218893Sdim const Location &Loc); 380193323Sed 381218893Sdim /// getModRefInfo (for call sites) - A convenience wrapper. 382218893Sdim ModRefResult getModRefInfo(ImmutableCallSite CS, 383218893Sdim const Value *P, uint64_t Size) { 384218893Sdim return getModRefInfo(CS, Location(P, Size)); 385218893Sdim } 386218893Sdim 387252723Sdim /// getModRefInfo (for calls) - Return information about whether 388218893Sdim /// a particular call modifies or reads the specified memory location. 389218893Sdim ModRefResult getModRefInfo(const CallInst *C, const Location &Loc) { 390218893Sdim return getModRefInfo(ImmutableCallSite(C), Loc); 391218893Sdim } 392218893Sdim 393218893Sdim /// getModRefInfo (for calls) - A convenience wrapper. 394218893Sdim ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { 395218893Sdim return getModRefInfo(C, Location(P, Size)); 396218893Sdim } 397218893Sdim 398252723Sdim /// getModRefInfo (for invokes) - Return information about whether 399218893Sdim /// a particular invoke modifies or reads the specified memory location. 400218893Sdim ModRefResult getModRefInfo(const InvokeInst *I, 401218893Sdim const Location &Loc) { 402218893Sdim return getModRefInfo(ImmutableCallSite(I), Loc); 403218893Sdim } 404218893Sdim 405218893Sdim /// getModRefInfo (for invokes) - A convenience wrapper. 406218893Sdim ModRefResult getModRefInfo(const InvokeInst *I, 407218893Sdim const Value *P, uint64_t Size) { 408218893Sdim return getModRefInfo(I, Location(P, Size)); 409218893Sdim } 410218893Sdim 411252723Sdim /// getModRefInfo (for loads) - Return information about whether 412218893Sdim /// a particular load modifies or reads the specified memory location. 413218893Sdim ModRefResult getModRefInfo(const LoadInst *L, const Location &Loc); 414218893Sdim 415218893Sdim /// getModRefInfo (for loads) - A convenience wrapper. 416218893Sdim ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { 417218893Sdim return getModRefInfo(L, Location(P, Size)); 418218893Sdim } 419218893Sdim 420252723Sdim /// getModRefInfo (for stores) - Return information about whether 421218893Sdim /// a particular store modifies or reads the specified memory location. 422218893Sdim ModRefResult getModRefInfo(const StoreInst *S, const Location &Loc); 423218893Sdim 424218893Sdim /// getModRefInfo (for stores) - A convenience wrapper. 425218893Sdim ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){ 426218893Sdim return getModRefInfo(S, Location(P, Size)); 427218893Sdim } 428218893Sdim 429252723Sdim /// getModRefInfo (for fences) - Return information about whether 430226890Sdim /// a particular store modifies or reads the specified memory location. 431226890Sdim ModRefResult getModRefInfo(const FenceInst *S, const Location &Loc) { 432226890Sdim // Conservatively correct. (We could possibly be a bit smarter if 433226890Sdim // Loc is a alloca that doesn't escape.) 434226890Sdim return ModRef; 435226890Sdim } 436226890Sdim 437226890Sdim /// getModRefInfo (for fences) - A convenience wrapper. 438226890Sdim ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){ 439226890Sdim return getModRefInfo(S, Location(P, Size)); 440226890Sdim } 441226890Sdim 442252723Sdim /// getModRefInfo (for cmpxchges) - Return information about whether 443226890Sdim /// a particular cmpxchg modifies or reads the specified memory location. 444226890Sdim ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc); 445226890Sdim 446226890Sdim /// getModRefInfo (for cmpxchges) - A convenience wrapper. 447226890Sdim ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, 448226890Sdim const Value *P, unsigned Size) { 449226890Sdim return getModRefInfo(CX, Location(P, Size)); 450226890Sdim } 451226890Sdim 452252723Sdim /// getModRefInfo (for atomicrmws) - Return information about whether 453226890Sdim /// a particular atomicrmw modifies or reads the specified memory location. 454226890Sdim ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc); 455226890Sdim 456226890Sdim /// getModRefInfo (for atomicrmws) - A convenience wrapper. 457226890Sdim ModRefResult getModRefInfo(const AtomicRMWInst *RMW, 458226890Sdim const Value *P, unsigned Size) { 459226890Sdim return getModRefInfo(RMW, Location(P, Size)); 460226890Sdim } 461226890Sdim 462252723Sdim /// getModRefInfo (for va_args) - Return information about whether 463218893Sdim /// a particular va_arg modifies or reads the specified memory location. 464218893Sdim ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); 465218893Sdim 466218893Sdim /// getModRefInfo (for va_args) - A convenience wrapper. 467218893Sdim ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){ 468218893Sdim return getModRefInfo(I, Location(P, Size)); 469218893Sdim } 470218893Sdim 471193323Sed /// getModRefInfo - Return information about whether two call sites may refer 472212904Sdim /// to the same set of memory locations. See 473212904Sdim /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 474212904Sdim /// for details. 475212904Sdim virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 476212904Sdim ImmutableCallSite CS2); 477193323Sed 478245431Sdim /// callCapturesBefore - Return information about whether a particular call 479245431Sdim /// site modifies or reads the specified memory location. 480245431Sdim ModRefResult callCapturesBefore(const Instruction *I, 481245431Sdim const AliasAnalysis::Location &MemLoc, 482245431Sdim DominatorTree *DT); 483245431Sdim 484245431Sdim /// callCapturesBefore - A convenience wrapper. 485245431Sdim ModRefResult callCapturesBefore(const Instruction *I, const Value *P, 486245431Sdim uint64_t Size, DominatorTree *DT) { 487245431Sdim return callCapturesBefore(I, Location(P, Size), DT); 488245431Sdim } 489245431Sdim 490193323Sed //===--------------------------------------------------------------------===// 491193323Sed /// Higher level methods for querying mod/ref information. 492193323Sed /// 493193323Sed 494193323Sed /// canBasicBlockModify - Return true if it is possible for execution of the 495193323Sed /// specified basic block to modify the value pointed to by Ptr. 496218893Sdim bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); 497193323Sed 498218893Sdim /// canBasicBlockModify - A convenience wrapper. 499218893Sdim bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){ 500218893Sdim return canBasicBlockModify(BB, Location(P, Size)); 501218893Sdim } 502218893Sdim 503193323Sed /// canInstructionRangeModify - Return true if it is possible for the 504193323Sed /// execution of the specified instructions to modify the value pointed to by 505193323Sed /// Ptr. The instructions to consider are all of the instructions in the 506193323Sed /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 507193323Sed bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 508218893Sdim const Location &Loc); 509193323Sed 510218893Sdim /// canInstructionRangeModify - A convenience wrapper. 511218893Sdim bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 512218893Sdim const Value *Ptr, uint64_t Size) { 513218893Sdim return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); 514218893Sdim } 515218893Sdim 516193323Sed //===--------------------------------------------------------------------===// 517193323Sed /// Methods that clients should call when they transform the program to allow 518193323Sed /// alias analyses to update their internal data structures. Note that these 519193323Sed /// methods may be called on any instruction, regardless of whether or not 520193323Sed /// they have pointer-analysis implications. 521193323Sed /// 522193323Sed 523193323Sed /// deleteValue - This method should be called whenever an LLVM Value is 524193323Sed /// deleted from the program, for example when an instruction is found to be 525193323Sed /// redundant and is eliminated. 526193323Sed /// 527193323Sed virtual void deleteValue(Value *V); 528193323Sed 529193323Sed /// copyValue - This method should be used whenever a preexisting value in the 530193323Sed /// program is copied or cloned, introducing a new value. Note that analysis 531193323Sed /// implementations should tolerate clients that use this method to introduce 532193323Sed /// the same value multiple times: if the analysis already knows about a 533193323Sed /// value, it should ignore the request. 534193323Sed /// 535193323Sed virtual void copyValue(Value *From, Value *To); 536193323Sed 537218893Sdim /// addEscapingUse - This method should be used whenever an escaping use is 538218893Sdim /// added to a pointer value. Analysis implementations may either return 539218893Sdim /// conservative responses for that value in the future, or may recompute 540218893Sdim /// some or all internal state to continue providing precise responses. 541218893Sdim /// 542218893Sdim /// Escaping uses are considered by anything _except_ the following: 543218893Sdim /// - GEPs or bitcasts of the pointer 544218893Sdim /// - Loads through the pointer 545218893Sdim /// - Stores through (but not of) the pointer 546218893Sdim virtual void addEscapingUse(Use &U); 547218893Sdim 548193323Sed /// replaceWithNewValue - This method is the obvious combination of the two 549193323Sed /// above, and it provided as a helper to simplify client code. 550193323Sed /// 551193323Sed void replaceWithNewValue(Value *Old, Value *New) { 552193323Sed copyValue(Old, New); 553193323Sed deleteValue(Old); 554193323Sed } 555193323Sed}; 556193323Sed 557223017Sdim// Specialize DenseMapInfo for Location. 558223017Sdimtemplate<> 559223017Sdimstruct DenseMapInfo<AliasAnalysis::Location> { 560223017Sdim static inline AliasAnalysis::Location getEmptyKey() { 561223017Sdim return 562223017Sdim AliasAnalysis::Location(DenseMapInfo<const Value *>::getEmptyKey(), 563223017Sdim 0, 0); 564223017Sdim } 565223017Sdim static inline AliasAnalysis::Location getTombstoneKey() { 566223017Sdim return 567223017Sdim AliasAnalysis::Location(DenseMapInfo<const Value *>::getTombstoneKey(), 568223017Sdim 0, 0); 569223017Sdim } 570223017Sdim static unsigned getHashValue(const AliasAnalysis::Location &Val) { 571223017Sdim return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ 572223017Sdim DenseMapInfo<uint64_t>::getHashValue(Val.Size) ^ 573223017Sdim DenseMapInfo<const MDNode *>::getHashValue(Val.TBAATag); 574223017Sdim } 575223017Sdim static bool isEqual(const AliasAnalysis::Location &LHS, 576223017Sdim const AliasAnalysis::Location &RHS) { 577223017Sdim return LHS.Ptr == RHS.Ptr && 578223017Sdim LHS.Size == RHS.Size && 579223017Sdim LHS.TBAATag == RHS.TBAATag; 580223017Sdim } 581223017Sdim}; 582223017Sdim 583193323Sed/// isNoAliasCall - Return true if this pointer is returned by a noalias 584193323Sed/// function. 585193323Sedbool isNoAliasCall(const Value *V); 586193323Sed 587263509Sdim/// isNoAliasArgument - Return true if this is an argument with the noalias 588263509Sdim/// attribute. 589263509Sdimbool isNoAliasArgument(const Value *V); 590263509Sdim 591193323Sed/// isIdentifiedObject - Return true if this pointer refers to a distinct and 592193323Sed/// identifiable object. This returns true for: 593198090Srdivacky/// Global Variables and Functions (but not Global Aliases) 594252723Sdim/// Allocas 595193323Sed/// ByVal and NoAlias Arguments 596252723Sdim/// NoAlias returns (e.g. calls to malloc) 597193323Sed/// 598193323Sedbool isIdentifiedObject(const Value *V); 599193323Sed 600193323Sed} // End llvm namespace 601193323Sed 602193323Sed#endif 603