1//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the generic AliasAnalysis interface, which is used as the 11// common interface used by all clients of alias analysis information, and 12// implemented by all alias analysis implementations. Mod/Ref information is 13// also captured by this interface. 14// 15// Implementations of this interface must implement the various virtual methods, 16// which automatically provides functionality for the entire suite of client 17// APIs. 18// 19// This API identifies memory regions with the MemoryLocation class. The pointer 20// component specifies the base memory address of the region. The Size specifies 21// the maximum size (in address units) of the memory region, or 22// MemoryLocation::UnknownSize if the size is not known. The TBAA tag 23// identifies the "type" of the memory reference; see the 24// TypeBasedAliasAnalysis class for details. 25// 26// Some non-obvious details include: 27// - Pointers that point to two completely different objects in memory never 28// alias, regardless of the value of the Size component. 29// - NoAlias doesn't imply inequal pointers. The most obvious example of this 30// is two pointers to constant memory. Even if they are equal, constant 31// memory is never stored to, so there will never be any dependencies. 32// In this and other situations, the pointers may be both NoAlias and 33// MustAlias at the same time. The current API can only return one result, 34// though this is rarely a problem in practice. 35// 36//===----------------------------------------------------------------------===// 37 38#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H 39#define LLVM_ANALYSIS_ALIASANALYSIS_H 40 41#include "llvm/Analysis/MemoryLocation.h" 42#include "llvm/Analysis/TargetLibraryInfo.h" 43#include "llvm/IR/CallSite.h" 44#include "llvm/IR/Metadata.h" 45#include "llvm/IR/PassManager.h" 46 47namespace llvm { 48class BasicAAResult; 49class LoadInst; 50class StoreInst; 51class VAArgInst; 52class DataLayout; 53class Pass; 54class AnalysisUsage; 55class MemTransferInst; 56class MemIntrinsic; 57class DominatorTree; 58class OrderedBasicBlock; 59 60/// The possible results of an alias query. 61/// 62/// These results are always computed between two MemoryLocation objects as 63/// a query to some alias analysis. 64/// 65/// Note that these are unscoped enumerations because we would like to support 66/// implicitly testing a result for the existence of any possible aliasing with 67/// a conversion to bool, but an "enum class" doesn't support this. The 68/// canonical names from the literature are suffixed and unique anyways, and so 69/// they serve as global constants in LLVM for these results. 70/// 71/// See docs/AliasAnalysis.html for more information on the specific meanings 72/// of these values. 73enum AliasResult { 74 /// The two locations do not alias at all. 75 /// 76 /// This value is arranged to convert to false, while all other values 77 /// convert to true. This allows a boolean context to convert the result to 78 /// a binary flag indicating whether there is the possibility of aliasing. 79 NoAlias = 0, 80 /// The two locations may or may not alias. This is the least precise result. 81 MayAlias, 82 /// The two locations alias, but only due to a partial overlap. 83 PartialAlias, 84 /// The two locations precisely alias each other. 85 MustAlias, 86}; 87 88/// Flags indicating whether a memory access modifies or references memory. 89/// 90/// This is no access at all, a modification, a reference, or both 91/// a modification and a reference. These are specifically structured such that 92/// they form a two bit matrix and bit-tests for 'mod' or 'ref' work with any 93/// of the possible values. 94enum ModRefInfo { 95 /// The access neither references nor modifies the value stored in memory. 96 MRI_NoModRef = 0, 97 /// The access references the value stored in memory. 98 MRI_Ref = 1, 99 /// The access modifies the value stored in memory. 100 MRI_Mod = 2, 101 /// The access both references and modifies the value stored in memory. 102 MRI_ModRef = MRI_Ref | MRI_Mod 103}; 104 105/// The locations at which a function might access memory. 106/// 107/// These are primarily used in conjunction with the \c AccessKind bits to 108/// describe both the nature of access and the locations of access for a 109/// function call. 110enum FunctionModRefLocation { 111 /// Base case is no access to memory. 112 FMRL_Nowhere = 0, 113 /// Access to memory via argument pointers. 114 FMRL_ArgumentPointees = 4, 115 /// Memory that is inaccessible via LLVM IR. 116 FMRL_InaccessibleMem = 8, 117 /// Access to any memory. 118 FMRL_Anywhere = 16 | FMRL_InaccessibleMem | FMRL_ArgumentPointees 119}; 120 121/// Summary of how a function affects memory in the program. 122/// 123/// Loads from constant globals are not considered memory accesses for this 124/// interface. Also, functions may freely modify stack space local to their 125/// invocation without having to report it through these interfaces. 126enum FunctionModRefBehavior { 127 /// This function does not perform any non-local loads or stores to memory. 128 /// 129 /// This property corresponds to the GCC 'const' attribute. 130 /// This property corresponds to the LLVM IR 'readnone' attribute. 131 /// This property corresponds to the IntrNoMem LLVM intrinsic flag. 132 FMRB_DoesNotAccessMemory = FMRL_Nowhere | MRI_NoModRef, 133 134 /// The only memory references in this function (if it has any) are 135 /// non-volatile loads from objects pointed to by its pointer-typed 136 /// arguments, with arbitrary offsets. 137 /// 138 /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. 139 FMRB_OnlyReadsArgumentPointees = FMRL_ArgumentPointees | MRI_Ref, 140 141 /// The only memory references in this function (if it has any) are 142 /// non-volatile loads and stores from objects pointed to by its 143 /// pointer-typed arguments, with arbitrary offsets. 144 /// 145 /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag. 146 FMRB_OnlyAccessesArgumentPointees = FMRL_ArgumentPointees | MRI_ModRef, 147 148 /// The only memory references in this function (if it has any) are 149 /// references of memory that is otherwise inaccessible via LLVM IR. 150 /// 151 /// This property corresponds to the LLVM IR inaccessiblememonly attribute. 152 FMRB_OnlyAccessesInaccessibleMem = FMRL_InaccessibleMem | MRI_ModRef, 153 154 /// The function may perform non-volatile loads and stores of objects 155 /// pointed to by its pointer-typed arguments, with arbitrary offsets, and 156 /// it may also perform loads and stores of memory that is otherwise 157 /// inaccessible via LLVM IR. 158 /// 159 /// This property corresponds to the LLVM IR 160 /// inaccessiblemem_or_argmemonly attribute. 161 FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem | 162 FMRL_ArgumentPointees | MRI_ModRef, 163 164 /// This function does not perform any non-local stores or volatile loads, 165 /// but may read from any memory location. 166 /// 167 /// This property corresponds to the GCC 'pure' attribute. 168 /// This property corresponds to the LLVM IR 'readonly' attribute. 169 /// This property corresponds to the IntrReadMem LLVM intrinsic flag. 170 FMRB_OnlyReadsMemory = FMRL_Anywhere | MRI_Ref, 171 172 // This function does not read from memory anywhere, but may write to any 173 // memory location. 174 // 175 // This property corresponds to the LLVM IR 'writeonly' attribute. 176 // This property corresponds to the IntrWriteMem LLVM intrinsic flag. 177 FMRB_DoesNotReadMemory = FMRL_Anywhere | MRI_Mod, 178 179 /// This indicates that the function could not be classified into one of the 180 /// behaviors above. 181 FMRB_UnknownModRefBehavior = FMRL_Anywhere | MRI_ModRef 182}; 183 184class AAResults { 185public: 186 // Make these results default constructable and movable. We have to spell 187 // these out because MSVC won't synthesize them. 188 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} 189 AAResults(AAResults &&Arg); 190 ~AAResults(); 191 192 /// Register a specific AA result. 193 template <typename AAResultT> void addAAResult(AAResultT &AAResult) { 194 // FIXME: We should use a much lighter weight system than the usual 195 // polymorphic pattern because we don't own AAResult. It should 196 // ideally involve two pointers and no separate allocation. 197 AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); 198 } 199 200 /// Register a function analysis ID that the results aggregation depends on. 201 /// 202 /// This is used in the new pass manager to implement the invalidation logic 203 /// where we must invalidate the results aggregation if any of our component 204 /// analyses become invalid. 205 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } 206 207 /// Handle invalidation events in the new pass manager. 208 /// 209 /// The aggregation is invalidated if any of the underlying analyses is 210 /// invalidated. 211 bool invalidate(Function &F, const PreservedAnalyses &PA, 212 FunctionAnalysisManager::Invalidator &Inv); 213 214 //===--------------------------------------------------------------------===// 215 /// \name Alias Queries 216 /// @{ 217 218 /// The main low level interface to the alias analysis implementation. 219 /// Returns an AliasResult indicating whether the two pointers are aliased to 220 /// each other. This is the interface that must be implemented by specific 221 /// alias analysis implementations. 222 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); 223 224 /// A convenience wrapper around the primary \c alias interface. 225 AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2, 226 uint64_t V2Size) { 227 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 228 } 229 230 /// A convenience wrapper around the primary \c alias interface. 231 AliasResult alias(const Value *V1, const Value *V2) { 232 return alias(V1, MemoryLocation::UnknownSize, V2, 233 MemoryLocation::UnknownSize); 234 } 235 236 /// A trivial helper function to check to see if the specified pointers are 237 /// no-alias. 238 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 239 return alias(LocA, LocB) == NoAlias; 240 } 241 242 /// A convenience wrapper around the \c isNoAlias helper interface. 243 bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2, 244 uint64_t V2Size) { 245 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 246 } 247 248 /// A convenience wrapper around the \c isNoAlias helper interface. 249 bool isNoAlias(const Value *V1, const Value *V2) { 250 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2)); 251 } 252 253 /// A trivial helper function to check to see if the specified pointers are 254 /// must-alias. 255 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 256 return alias(LocA, LocB) == MustAlias; 257 } 258 259 /// A convenience wrapper around the \c isMustAlias helper interface. 260 bool isMustAlias(const Value *V1, const Value *V2) { 261 return alias(V1, 1, V2, 1) == MustAlias; 262 } 263 264 /// Checks whether the given location points to constant memory, or if 265 /// \p OrLocal is true whether it points to a local alloca. 266 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); 267 268 /// A convenience wrapper around the primary \c pointsToConstantMemory 269 /// interface. 270 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 271 return pointsToConstantMemory(MemoryLocation(P), OrLocal); 272 } 273 274 /// @} 275 //===--------------------------------------------------------------------===// 276 /// \name Simple mod/ref information 277 /// @{ 278 279 /// Get the ModRef info associated with a pointer argument of a callsite. The 280 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 281 /// that these bits do not necessarily account for the overall behavior of 282 /// the function, but rather only provide additional per-argument 283 /// information. 284 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); 285 286 /// Return the behavior of the given call site. 287 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS); 288 289 /// Return the behavior when calling the given function. 290 FunctionModRefBehavior getModRefBehavior(const Function *F); 291 292 /// Checks if the specified call is known to never read or write memory. 293 /// 294 /// Note that if the call only reads from known-constant memory, it is also 295 /// legal to return true. Also, calls that unwind the stack are legal for 296 /// this predicate. 297 /// 298 /// Many optimizations (such as CSE and LICM) can be performed on such calls 299 /// without worrying about aliasing properties, and many calls have this 300 /// property (e.g. calls to 'sin' and 'cos'). 301 /// 302 /// This property corresponds to the GCC 'const' attribute. 303 bool doesNotAccessMemory(ImmutableCallSite CS) { 304 return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory; 305 } 306 307 /// Checks if the specified function is known to never read or write memory. 308 /// 309 /// Note that if the function only reads from known-constant memory, it is 310 /// also legal to return true. Also, function that unwind the stack are legal 311 /// for this predicate. 312 /// 313 /// Many optimizations (such as CSE and LICM) can be performed on such calls 314 /// to such functions without worrying about aliasing properties, and many 315 /// functions have this property (e.g. 'sin' and 'cos'). 316 /// 317 /// This property corresponds to the GCC 'const' attribute. 318 bool doesNotAccessMemory(const Function *F) { 319 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; 320 } 321 322 /// Checks if the specified call is known to only read from non-volatile 323 /// memory (or not access memory at all). 324 /// 325 /// Calls that unwind the stack are legal for this predicate. 326 /// 327 /// This property allows many common optimizations to be performed in the 328 /// absence of interfering store instructions, such as CSE of strlen calls. 329 /// 330 /// This property corresponds to the GCC 'pure' attribute. 331 bool onlyReadsMemory(ImmutableCallSite CS) { 332 return onlyReadsMemory(getModRefBehavior(CS)); 333 } 334 335 /// Checks if the specified function is known to only read from non-volatile 336 /// memory (or not access memory at all). 337 /// 338 /// Functions that unwind the stack are legal for this predicate. 339 /// 340 /// This property allows many common optimizations to be performed in the 341 /// absence of interfering store instructions, such as CSE of strlen calls. 342 /// 343 /// This property corresponds to the GCC 'pure' attribute. 344 bool onlyReadsMemory(const Function *F) { 345 return onlyReadsMemory(getModRefBehavior(F)); 346 } 347 348 /// Checks if functions with the specified behavior are known to only read 349 /// from non-volatile memory (or not access memory at all). 350 static bool onlyReadsMemory(FunctionModRefBehavior MRB) { 351 return !(MRB & MRI_Mod); 352 } 353 354 /// Checks if functions with the specified behavior are known to only write 355 /// memory (or not access memory at all). 356 static bool doesNotReadMemory(FunctionModRefBehavior MRB) { 357 return !(MRB & MRI_Ref); 358 } 359 360 /// Checks if functions with the specified behavior are known to read and 361 /// write at most from objects pointed to by their pointer-typed arguments 362 /// (with arbitrary offsets). 363 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { 364 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); 365 } 366 367 /// Checks if functions with the specified behavior are known to potentially 368 /// read or write from objects pointed to be their pointer-typed arguments 369 /// (with arbitrary offsets). 370 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { 371 return (MRB & MRI_ModRef) && (MRB & FMRL_ArgumentPointees); 372 } 373 374 /// Checks if functions with the specified behavior are known to read and 375 /// write at most from memory that is inaccessible from LLVM IR. 376 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { 377 return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); 378 } 379 380 /// Checks if functions with the specified behavior are known to potentially 381 /// read or write from memory that is inaccessible from LLVM IR. 382 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { 383 return (MRB & MRI_ModRef) && (MRB & FMRL_InaccessibleMem); 384 } 385 386 /// Checks if functions with the specified behavior are known to read and 387 /// write at most from memory that is inaccessible from LLVM IR or objects 388 /// pointed to by their pointer-typed arguments (with arbitrary offsets). 389 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { 390 return !(MRB & FMRL_Anywhere & 391 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); 392 } 393 394 /// getModRefInfo (for call sites) - Return information about whether 395 /// a particular call site modifies or reads the specified memory location. 396 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc); 397 398 /// getModRefInfo (for call sites) - A convenience wrapper. 399 ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P, 400 uint64_t Size) { 401 return getModRefInfo(CS, MemoryLocation(P, Size)); 402 } 403 404 /// getModRefInfo (for calls) - Return information about whether 405 /// a particular call modifies or reads the specified memory location. 406 ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) { 407 return getModRefInfo(ImmutableCallSite(C), Loc); 408 } 409 410 /// getModRefInfo (for calls) - A convenience wrapper. 411 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { 412 return getModRefInfo(C, MemoryLocation(P, Size)); 413 } 414 415 /// getModRefInfo (for invokes) - Return information about whether 416 /// a particular invoke modifies or reads the specified memory location. 417 ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) { 418 return getModRefInfo(ImmutableCallSite(I), Loc); 419 } 420 421 /// getModRefInfo (for invokes) - A convenience wrapper. 422 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) { 423 return getModRefInfo(I, MemoryLocation(P, Size)); 424 } 425 426 /// getModRefInfo (for loads) - Return information about whether 427 /// a particular load modifies or reads the specified memory location. 428 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); 429 430 /// getModRefInfo (for loads) - A convenience wrapper. 431 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { 432 return getModRefInfo(L, MemoryLocation(P, Size)); 433 } 434 435 /// getModRefInfo (for stores) - Return information about whether 436 /// a particular store modifies or reads the specified memory location. 437 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); 438 439 /// getModRefInfo (for stores) - A convenience wrapper. 440 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) { 441 return getModRefInfo(S, MemoryLocation(P, Size)); 442 } 443 444 /// getModRefInfo (for fences) - Return information about whether 445 /// a particular store modifies or reads the specified memory location. 446 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); 447 448 /// getModRefInfo (for fences) - A convenience wrapper. 449 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) { 450 return getModRefInfo(S, MemoryLocation(P, Size)); 451 } 452 453 /// getModRefInfo (for cmpxchges) - Return information about whether 454 /// a particular cmpxchg modifies or reads the specified memory location. 455 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 456 const MemoryLocation &Loc); 457 458 /// getModRefInfo (for cmpxchges) - A convenience wrapper. 459 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, 460 unsigned Size) { 461 return getModRefInfo(CX, MemoryLocation(P, Size)); 462 } 463 464 /// getModRefInfo (for atomicrmws) - Return information about whether 465 /// a particular atomicrmw modifies or reads the specified memory location. 466 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); 467 468 /// getModRefInfo (for atomicrmws) - A convenience wrapper. 469 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, 470 unsigned Size) { 471 return getModRefInfo(RMW, MemoryLocation(P, Size)); 472 } 473 474 /// getModRefInfo (for va_args) - Return information about whether 475 /// a particular va_arg modifies or reads the specified memory location. 476 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); 477 478 /// getModRefInfo (for va_args) - A convenience wrapper. 479 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) { 480 return getModRefInfo(I, MemoryLocation(P, Size)); 481 } 482 483 /// getModRefInfo (for catchpads) - Return information about whether 484 /// a particular catchpad modifies or reads the specified memory location. 485 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); 486 487 /// getModRefInfo (for catchpads) - A convenience wrapper. 488 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, 489 uint64_t Size) { 490 return getModRefInfo(I, MemoryLocation(P, Size)); 491 } 492 493 /// getModRefInfo (for catchrets) - Return information about whether 494 /// a particular catchret modifies or reads the specified memory location. 495 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); 496 497 /// getModRefInfo (for catchrets) - A convenience wrapper. 498 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, 499 uint64_t Size) { 500 return getModRefInfo(I, MemoryLocation(P, Size)); 501 } 502 503 /// Check whether or not an instruction may read or write memory (without 504 /// regard to a specific location). 505 /// 506 /// For function calls, this delegates to the alias-analysis specific 507 /// call-site mod-ref behavior queries. Otherwise it delegates to the generic 508 /// mod ref information query without a location. 509 ModRefInfo getModRefInfo(const Instruction *I) { 510 if (auto CS = ImmutableCallSite(I)) { 511 auto MRB = getModRefBehavior(CS); 512 if ((MRB & MRI_ModRef) == MRI_ModRef) 513 return MRI_ModRef; 514 if (MRB & MRI_Ref) 515 return MRI_Ref; 516 if (MRB & MRI_Mod) 517 return MRI_Mod; 518 return MRI_NoModRef; 519 } 520 521 return getModRefInfo(I, MemoryLocation()); 522 } 523 524 /// Check whether or not an instruction may read or write the specified 525 /// memory location. 526 /// 527 /// Note explicitly that getModRefInfo considers the effects of reading and 528 /// writing the memory location, and not the effect of ordering relative to 529 /// other instructions. Thus, a volatile load is considered to be Ref, 530 /// because it does not actually write memory, it just can't be reordered 531 /// relative to other volatiles (or removed). Atomic ordered loads/stores are 532 /// considered ModRef ATM because conservatively, the visible effect appears 533 /// as if memory was written, not just an ordering constraint. 534 /// 535 /// An instruction that doesn't read or write memory may be trivially LICM'd 536 /// for example. 537 /// 538 /// This primarily delegates to specific helpers above. 539 ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) { 540 switch (I->getOpcode()) { 541 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); 542 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); 543 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); 544 case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc); 545 case Instruction::AtomicCmpXchg: 546 return getModRefInfo((const AtomicCmpXchgInst*)I, Loc); 547 case Instruction::AtomicRMW: 548 return getModRefInfo((const AtomicRMWInst*)I, Loc); 549 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); 550 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); 551 case Instruction::CatchPad: 552 return getModRefInfo((const CatchPadInst *)I, Loc); 553 case Instruction::CatchRet: 554 return getModRefInfo((const CatchReturnInst *)I, Loc); 555 default: 556 return MRI_NoModRef; 557 } 558 } 559 560 /// A convenience wrapper for constructing the memory location. 561 ModRefInfo getModRefInfo(const Instruction *I, const Value *P, 562 uint64_t Size) { 563 return getModRefInfo(I, MemoryLocation(P, Size)); 564 } 565 566 /// Return information about whether a call and an instruction may refer to 567 /// the same memory locations. 568 ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call); 569 570 /// Return information about whether two call sites may refer to the same set 571 /// of memory locations. See the AA documentation for details: 572 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 573 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2); 574 575 /// \brief Return information about whether a particular call site modifies 576 /// or reads the specified memory location \p MemLoc before instruction \p I 577 /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up 578 /// instruction ordering queries inside the BasicBlock containing \p I. 579 ModRefInfo callCapturesBefore(const Instruction *I, 580 const MemoryLocation &MemLoc, DominatorTree *DT, 581 OrderedBasicBlock *OBB = nullptr); 582 583 /// \brief A convenience wrapper to synthesize a memory location. 584 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, 585 uint64_t Size, DominatorTree *DT, 586 OrderedBasicBlock *OBB = nullptr) { 587 return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB); 588 } 589 590 /// @} 591 //===--------------------------------------------------------------------===// 592 /// \name Higher level methods for querying mod/ref information. 593 /// @{ 594 595 /// Check if it is possible for execution of the specified basic block to 596 /// modify the location Loc. 597 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); 598 599 /// A convenience wrapper synthesizing a memory location. 600 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, 601 uint64_t Size) { 602 return canBasicBlockModify(BB, MemoryLocation(P, Size)); 603 } 604 605 /// Check if it is possible for the execution of the specified instructions 606 /// to mod\ref (according to the mode) the location Loc. 607 /// 608 /// The instructions to consider are all of the instructions in the range of 609 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 610 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 611 const MemoryLocation &Loc, 612 const ModRefInfo Mode); 613 614 /// A convenience wrapper synthesizing a memory location. 615 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 616 const Value *Ptr, uint64_t Size, 617 const ModRefInfo Mode) { 618 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); 619 } 620 621private: 622 class Concept; 623 template <typename T> class Model; 624 625 template <typename T> friend class AAResultBase; 626 627 const TargetLibraryInfo &TLI; 628 629 std::vector<std::unique_ptr<Concept>> AAs; 630 631 std::vector<AnalysisKey *> AADeps; 632}; 633 634/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis 635/// pointer or reference. 636typedef AAResults AliasAnalysis; 637 638/// A private abstract base class describing the concept of an individual alias 639/// analysis implementation. 640/// 641/// This interface is implemented by any \c Model instantiation. It is also the 642/// interface which a type used to instantiate the model must provide. 643/// 644/// All of these methods model methods by the same name in the \c 645/// AAResults class. Only differences and specifics to how the 646/// implementations are called are documented here. 647class AAResults::Concept { 648public: 649 virtual ~Concept() = 0; 650 651 /// An update API used internally by the AAResults to provide 652 /// a handle back to the top level aggregation. 653 virtual void setAAResults(AAResults *NewAAR) = 0; 654 655 //===--------------------------------------------------------------------===// 656 /// \name Alias Queries 657 /// @{ 658 659 /// The main low level interface to the alias analysis implementation. 660 /// Returns an AliasResult indicating whether the two pointers are aliased to 661 /// each other. This is the interface that must be implemented by specific 662 /// alias analysis implementations. 663 virtual AliasResult alias(const MemoryLocation &LocA, 664 const MemoryLocation &LocB) = 0; 665 666 /// Checks whether the given location points to constant memory, or if 667 /// \p OrLocal is true whether it points to a local alloca. 668 virtual bool pointsToConstantMemory(const MemoryLocation &Loc, 669 bool OrLocal) = 0; 670 671 /// @} 672 //===--------------------------------------------------------------------===// 673 /// \name Simple mod/ref information 674 /// @{ 675 676 /// Get the ModRef info associated with a pointer argument of a callsite. The 677 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 678 /// that these bits do not necessarily account for the overall behavior of 679 /// the function, but rather only provide additional per-argument 680 /// information. 681 virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS, 682 unsigned ArgIdx) = 0; 683 684 /// Return the behavior of the given call site. 685 virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) = 0; 686 687 /// Return the behavior when calling the given function. 688 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; 689 690 /// getModRefInfo (for call sites) - Return information about whether 691 /// a particular call site modifies or reads the specified memory location. 692 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS, 693 const MemoryLocation &Loc) = 0; 694 695 /// Return information about whether two call sites may refer to the same set 696 /// of memory locations. See the AA documentation for details: 697 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 698 virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1, 699 ImmutableCallSite CS2) = 0; 700 701 /// @} 702}; 703 704/// A private class template which derives from \c Concept and wraps some other 705/// type. 706/// 707/// This models the concept by directly forwarding each interface point to the 708/// wrapped type which must implement a compatible interface. This provides 709/// a type erased binding. 710template <typename AAResultT> class AAResults::Model final : public Concept { 711 AAResultT &Result; 712 713public: 714 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { 715 Result.setAAResults(&AAR); 716 } 717 ~Model() override {} 718 719 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } 720 721 AliasResult alias(const MemoryLocation &LocA, 722 const MemoryLocation &LocB) override { 723 return Result.alias(LocA, LocB); 724 } 725 726 bool pointsToConstantMemory(const MemoryLocation &Loc, 727 bool OrLocal) override { 728 return Result.pointsToConstantMemory(Loc, OrLocal); 729 } 730 731 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override { 732 return Result.getArgModRefInfo(CS, ArgIdx); 733 } 734 735 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override { 736 return Result.getModRefBehavior(CS); 737 } 738 739 FunctionModRefBehavior getModRefBehavior(const Function *F) override { 740 return Result.getModRefBehavior(F); 741 } 742 743 ModRefInfo getModRefInfo(ImmutableCallSite CS, 744 const MemoryLocation &Loc) override { 745 return Result.getModRefInfo(CS, Loc); 746 } 747 748 ModRefInfo getModRefInfo(ImmutableCallSite CS1, 749 ImmutableCallSite CS2) override { 750 return Result.getModRefInfo(CS1, CS2); 751 } 752}; 753 754/// A CRTP-driven "mixin" base class to help implement the function alias 755/// analysis results concept. 756/// 757/// Because of the nature of many alias analysis implementations, they often 758/// only implement a subset of the interface. This base class will attempt to 759/// implement the remaining portions of the interface in terms of simpler forms 760/// of the interface where possible, and otherwise provide conservatively 761/// correct fallback implementations. 762/// 763/// Implementors of an alias analysis should derive from this CRTP, and then 764/// override specific methods that they wish to customize. There is no need to 765/// use virtual anywhere, the CRTP base class does static dispatch to the 766/// derived type passed into it. 767template <typename DerivedT> class AAResultBase { 768 // Expose some parts of the interface only to the AAResults::Model 769 // for wrapping. Specifically, this allows the model to call our 770 // setAAResults method without exposing it as a fully public API. 771 friend class AAResults::Model<DerivedT>; 772 773 /// A pointer to the AAResults object that this AAResult is 774 /// aggregated within. May be null if not aggregated. 775 AAResults *AAR; 776 777 /// Helper to dispatch calls back through the derived type. 778 DerivedT &derived() { return static_cast<DerivedT &>(*this); } 779 780 /// A setter for the AAResults pointer, which is used to satisfy the 781 /// AAResults::Model contract. 782 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } 783 784protected: 785 /// This proxy class models a common pattern where we delegate to either the 786 /// top-level \c AAResults aggregation if one is registered, or to the 787 /// current result if none are registered. 788 class AAResultsProxy { 789 AAResults *AAR; 790 DerivedT &CurrentResult; 791 792 public: 793 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) 794 : AAR(AAR), CurrentResult(CurrentResult) {} 795 796 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 797 return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB); 798 } 799 800 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) { 801 return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal) 802 : CurrentResult.pointsToConstantMemory(Loc, OrLocal); 803 } 804 805 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) { 806 return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx); 807 } 808 809 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) { 810 return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS); 811 } 812 813 FunctionModRefBehavior getModRefBehavior(const Function *F) { 814 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); 815 } 816 817 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) { 818 return AAR ? AAR->getModRefInfo(CS, Loc) 819 : CurrentResult.getModRefInfo(CS, Loc); 820 } 821 822 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 823 return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2); 824 } 825 }; 826 827 explicit AAResultBase() {} 828 829 // Provide all the copy and move constructors so that derived types aren't 830 // constrained. 831 AAResultBase(const AAResultBase &Arg) {} 832 AAResultBase(AAResultBase &&Arg) {} 833 834 /// Get a proxy for the best AA result set to query at this time. 835 /// 836 /// When this result is part of a larger aggregation, this will proxy to that 837 /// aggregation. When this result is used in isolation, it will just delegate 838 /// back to the derived class's implementation. 839 /// 840 /// Note that callers of this need to take considerable care to not cause 841 /// performance problems when they use this routine, in the case of a large 842 /// number of alias analyses being aggregated, it can be expensive to walk 843 /// back across the chain. 844 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } 845 846public: 847 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 848 return MayAlias; 849 } 850 851 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) { 852 return false; 853 } 854 855 ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) { 856 return MRI_ModRef; 857 } 858 859 FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) { 860 return FMRB_UnknownModRefBehavior; 861 } 862 863 FunctionModRefBehavior getModRefBehavior(const Function *F) { 864 return FMRB_UnknownModRefBehavior; 865 } 866 867 ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) { 868 return MRI_ModRef; 869 } 870 871 ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { 872 return MRI_ModRef; 873 } 874}; 875 876 877/// Return true if this pointer is returned by a noalias function. 878bool isNoAliasCall(const Value *V); 879 880/// Return true if this is an argument with the noalias attribute. 881bool isNoAliasArgument(const Value *V); 882 883/// Return true if this pointer refers to a distinct and identifiable object. 884/// This returns true for: 885/// Global Variables and Functions (but not Global Aliases) 886/// Allocas 887/// ByVal and NoAlias Arguments 888/// NoAlias returns (e.g. calls to malloc) 889/// 890bool isIdentifiedObject(const Value *V); 891 892/// Return true if V is umabigously identified at the function-level. 893/// Different IdentifiedFunctionLocals can't alias. 894/// Further, an IdentifiedFunctionLocal can not alias with any function 895/// arguments other than itself, which is not necessarily true for 896/// IdentifiedObjects. 897bool isIdentifiedFunctionLocal(const Value *V); 898 899/// A manager for alias analyses. 900/// 901/// This class can have analyses registered with it and when run, it will run 902/// all of them and aggregate their results into single AA results interface 903/// that dispatches across all of the alias analysis results available. 904/// 905/// Note that the order in which analyses are registered is very significant. 906/// That is the order in which the results will be aggregated and queried. 907/// 908/// This manager effectively wraps the AnalysisManager for registering alias 909/// analyses. When you register your alias analysis with this manager, it will 910/// ensure the analysis itself is registered with its AnalysisManager. 911class AAManager : public AnalysisInfoMixin<AAManager> { 912public: 913 typedef AAResults Result; 914 915 /// Register a specific AA result. 916 template <typename AnalysisT> void registerFunctionAnalysis() { 917 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); 918 } 919 920 /// Register a specific AA result. 921 template <typename AnalysisT> void registerModuleAnalysis() { 922 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); 923 } 924 925 Result run(Function &F, FunctionAnalysisManager &AM) { 926 Result R(AM.getResult<TargetLibraryAnalysis>(F)); 927 for (auto &Getter : ResultGetters) 928 (*Getter)(F, AM, R); 929 return R; 930 } 931 932private: 933 friend AnalysisInfoMixin<AAManager>; 934 static AnalysisKey Key; 935 936 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, 937 AAResults &AAResults), 938 4> ResultGetters; 939 940 template <typename AnalysisT> 941 static void getFunctionAAResultImpl(Function &F, 942 FunctionAnalysisManager &AM, 943 AAResults &AAResults) { 944 AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); 945 AAResults.addAADependencyID(AnalysisT::ID()); 946 } 947 948 template <typename AnalysisT> 949 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, 950 AAResults &AAResults) { 951 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); 952 auto &MAM = MAMProxy.getManager(); 953 if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) { 954 AAResults.addAAResult(*R); 955 MAMProxy 956 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); 957 } 958 } 959}; 960 961/// A wrapper pass to provide the legacy pass manager access to a suitably 962/// prepared AAResults object. 963class AAResultsWrapperPass : public FunctionPass { 964 std::unique_ptr<AAResults> AAR; 965 966public: 967 static char ID; 968 969 AAResultsWrapperPass(); 970 971 AAResults &getAAResults() { return *AAR; } 972 const AAResults &getAAResults() const { return *AAR; } 973 974 bool runOnFunction(Function &F) override; 975 976 void getAnalysisUsage(AnalysisUsage &AU) const override; 977}; 978 979FunctionPass *createAAResultsWrapperPass(); 980 981/// A wrapper pass around a callback which can be used to populate the 982/// AAResults in the AAResultsWrapperPass from an external AA. 983/// 984/// The callback provided here will be used each time we prepare an AAResults 985/// object, and will receive a reference to the function wrapper pass, the 986/// function, and the AAResults object to populate. This should be used when 987/// setting up a custom pass pipeline to inject a hook into the AA results. 988ImmutablePass *createExternalAAWrapperPass( 989 std::function<void(Pass &, Function &, AAResults &)> Callback); 990 991/// A helper for the legacy pass manager to create a \c AAResults 992/// object populated to the best of our ability for a particular function when 993/// inside of a \c ModulePass or a \c CallGraphSCCPass. 994/// 995/// If a \c ModulePass or a \c CallGraphSCCPass calls \p 996/// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p 997/// getAnalysisUsage. 998AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); 999 1000/// A helper for the legacy pass manager to populate \p AU to add uses to make 1001/// sure the analyses required by \p createLegacyPMAAResults are available. 1002void getAAResultsAnalysisUsage(AnalysisUsage &AU); 1003 1004} // End llvm namespace 1005 1006#endif 1007