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