1//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file defines the generic AliasAnalysis interface, which is used as the 10// common interface used by all clients of alias analysis information, and 11// implemented by all alias analysis implementations. Mod/Ref information is 12// also captured by this interface. 13// 14// Implementations of this interface must implement the various virtual methods, 15// which automatically provides functionality for the entire suite of client 16// APIs. 17// 18// This API identifies memory regions with the MemoryLocation class. The pointer 19// component specifies the base memory address of the region. The Size specifies 20// the maximum size (in address units) of the memory region, or 21// MemoryLocation::UnknownSize if the size is not known. The TBAA tag 22// identifies the "type" of the memory reference; see the 23// TypeBasedAliasAnalysis class for details. 24// 25// Some non-obvious details include: 26// - Pointers that point to two completely different objects in memory never 27// alias, regardless of the value of the Size component. 28// - NoAlias doesn't imply inequal pointers. The most obvious example of this 29// is two pointers to constant memory. Even if they are equal, constant 30// memory is never stored to, so there will never be any dependencies. 31// In this and other situations, the pointers may be both NoAlias and 32// MustAlias at the same time. The current API can only return one result, 33// though this is rarely a problem in practice. 34// 35//===----------------------------------------------------------------------===// 36 37#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H 38#define LLVM_ANALYSIS_ALIASANALYSIS_H 39 40#include "llvm/ADT/DenseMap.h" 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/IR/PassManager.h" 46#include "llvm/Pass.h" 47#include <cstdint> 48#include <functional> 49#include <memory> 50#include <vector> 51 52namespace llvm { 53 54class AnalysisUsage; 55class AtomicCmpXchgInst; 56class BasicAAResult; 57class BasicBlock; 58class CatchPadInst; 59class CatchReturnInst; 60class DominatorTree; 61class FenceInst; 62class Function; 63class InvokeInst; 64class PreservedAnalyses; 65class TargetLibraryInfo; 66class Value; 67 68/// The possible results of an alias query. 69/// 70/// These results are always computed between two MemoryLocation objects as 71/// a query to some alias analysis. 72/// 73/// Note that these are unscoped enumerations because we would like to support 74/// implicitly testing a result for the existence of any possible aliasing with 75/// a conversion to bool, but an "enum class" doesn't support this. The 76/// canonical names from the literature are suffixed and unique anyways, and so 77/// they serve as global constants in LLVM for these results. 78/// 79/// See docs/AliasAnalysis.html for more information on the specific meanings 80/// of these values. 81class AliasResult { 82private: 83 static const int OffsetBits = 23; 84 static const int AliasBits = 8; 85 static_assert(AliasBits + 1 + OffsetBits <= 32, 86 "AliasResult size is intended to be 4 bytes!"); 87 88 unsigned int Alias : AliasBits; 89 unsigned int HasOffset : 1; 90 signed int Offset : OffsetBits; 91 92public: 93 enum Kind : uint8_t { 94 /// The two locations do not alias at all. 95 /// 96 /// This value is arranged to convert to false, while all other values 97 /// convert to true. This allows a boolean context to convert the result to 98 /// a binary flag indicating whether there is the possibility of aliasing. 99 NoAlias = 0, 100 /// The two locations may or may not alias. This is the least precise 101 /// result. 102 MayAlias, 103 /// The two locations alias, but only due to a partial overlap. 104 PartialAlias, 105 /// The two locations precisely alias each other. 106 MustAlias, 107 }; 108 static_assert(MustAlias < (1 << AliasBits), 109 "Not enough bit field size for the enum!"); 110 111 explicit AliasResult() = delete; 112 constexpr AliasResult(const Kind &Alias) 113 : Alias(Alias), HasOffset(false), Offset(0) {} 114 115 operator Kind() const { return static_cast<Kind>(Alias); } 116 117 constexpr bool hasOffset() const { return HasOffset; } 118 constexpr int32_t getOffset() const { 119 assert(HasOffset && "No offset!"); 120 return Offset; 121 } 122 void setOffset(int32_t NewOffset) { 123 if (isInt<OffsetBits>(NewOffset)) { 124 HasOffset = true; 125 Offset = NewOffset; 126 } 127 } 128 129 /// Helper for processing AliasResult for swapped memory location pairs. 130 void swap(bool DoSwap = true) { 131 if (DoSwap && hasOffset()) 132 setOffset(-getOffset()); 133 } 134}; 135 136static_assert(sizeof(AliasResult) == 4, 137 "AliasResult size is intended to be 4 bytes!"); 138 139/// << operator for AliasResult. 140raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); 141 142/// Flags indicating whether a memory access modifies or references memory. 143/// 144/// This is no access at all, a modification, a reference, or both 145/// a modification and a reference. These are specifically structured such that 146/// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must' 147/// work with any of the possible values. 148enum class ModRefInfo : uint8_t { 149 /// Must is provided for completeness, but no routines will return only 150 /// Must today. See definition of Must below. 151 Must = 0, 152 /// The access may reference the value stored in memory, 153 /// a mustAlias relation was found, and no mayAlias or partialAlias found. 154 MustRef = 1, 155 /// The access may modify the value stored in memory, 156 /// a mustAlias relation was found, and no mayAlias or partialAlias found. 157 MustMod = 2, 158 /// The access may reference, modify or both the value stored in memory, 159 /// a mustAlias relation was found, and no mayAlias or partialAlias found. 160 MustModRef = MustRef | MustMod, 161 /// The access neither references nor modifies the value stored in memory. 162 NoModRef = 4, 163 /// The access may reference the value stored in memory. 164 Ref = NoModRef | MustRef, 165 /// The access may modify the value stored in memory. 166 Mod = NoModRef | MustMod, 167 /// The access may reference and may modify the value stored in memory. 168 ModRef = Ref | Mod, 169 170 /// About Must: 171 /// Must is set in a best effort manner. 172 /// We usually do not try our best to infer Must, instead it is merely 173 /// another piece of "free" information that is presented when available. 174 /// Must set means there was certainly a MustAlias found. For calls, 175 /// where multiple arguments are checked (argmemonly), this translates to 176 /// only MustAlias or NoAlias was found. 177 /// Must is not set for RAR accesses, even if the two locations must 178 /// alias. The reason is that two read accesses translate to an early return 179 /// of NoModRef. An additional alias check to set Must may be 180 /// expensive. Other cases may also not set Must(e.g. callCapturesBefore). 181 /// We refer to Must being *set* when the most significant bit is *cleared*. 182 /// Conversely we *clear* Must information by *setting* the Must bit to 1. 183}; 184 185LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) { 186 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == 187 static_cast<int>(ModRefInfo::Must); 188} 189LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { 190 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef); 191} 192LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) { 193 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == 194 static_cast<int>(ModRefInfo::MustModRef); 195} 196LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { 197 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod); 198} 199LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { 200 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef); 201} 202LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { 203 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef)); 204} 205 206LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { 207 return ModRefInfo(static_cast<int>(MRI) | 208 static_cast<int>(ModRefInfo::MustMod)); 209} 210LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { 211 return ModRefInfo(static_cast<int>(MRI) | 212 static_cast<int>(ModRefInfo::MustRef)); 213} 214LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { 215 return ModRefInfo(static_cast<int>(MRI) & 216 static_cast<int>(ModRefInfo::MustModRef)); 217} 218LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { 219 return ModRefInfo(static_cast<int>(MRI) | 220 static_cast<int>(ModRefInfo::MustModRef)); 221} 222LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { 223 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref)); 224} 225LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { 226 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod)); 227} 228LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { 229 return ModRefInfo(static_cast<int>(MRI) | 230 static_cast<int>(ModRefInfo::NoModRef)); 231} 232LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, 233 const ModRefInfo MRI2) { 234 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2)); 235} 236LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1, 237 const ModRefInfo MRI2) { 238 return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2)); 239} 240 241/// The locations at which a function might access memory. 242/// 243/// These are primarily used in conjunction with the \c AccessKind bits to 244/// describe both the nature of access and the locations of access for a 245/// function call. 246enum FunctionModRefLocation { 247 /// Base case is no access to memory. 248 FMRL_Nowhere = 0, 249 /// Access to memory via argument pointers. 250 FMRL_ArgumentPointees = 8, 251 /// Memory that is inaccessible via LLVM IR. 252 FMRL_InaccessibleMem = 16, 253 /// Access to any memory. 254 FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees 255}; 256 257/// Summary of how a function affects memory in the program. 258/// 259/// Loads from constant globals are not considered memory accesses for this 260/// interface. Also, functions may freely modify stack space local to their 261/// invocation without having to report it through these interfaces. 262enum FunctionModRefBehavior { 263 /// This function does not perform any non-local loads or stores to memory. 264 /// 265 /// This property corresponds to the GCC 'const' attribute. 266 /// This property corresponds to the LLVM IR 'readnone' attribute. 267 /// This property corresponds to the IntrNoMem LLVM intrinsic flag. 268 FMRB_DoesNotAccessMemory = 269 FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef), 270 271 /// The only memory references in this function (if it has any) are 272 /// non-volatile loads from objects pointed to by its pointer-typed 273 /// arguments, with arbitrary offsets. 274 /// 275 /// This property corresponds to the combination of the IntrReadMem 276 /// and IntrArgMemOnly LLVM intrinsic flags. 277 FMRB_OnlyReadsArgumentPointees = 278 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref), 279 280 /// The only memory references in this function (if it has any) are 281 /// non-volatile stores from objects pointed to by its pointer-typed 282 /// arguments, with arbitrary offsets. 283 /// 284 /// This property corresponds to the combination of the IntrWriteMem 285 /// and IntrArgMemOnly LLVM intrinsic flags. 286 FMRB_OnlyWritesArgumentPointees = 287 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod), 288 289 /// The only memory references in this function (if it has any) are 290 /// non-volatile loads and stores from objects pointed to by its 291 /// pointer-typed arguments, with arbitrary offsets. 292 /// 293 /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag. 294 FMRB_OnlyAccessesArgumentPointees = 295 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef), 296 297 /// The only memory references in this function (if it has any) are 298 /// reads of memory that is otherwise inaccessible via LLVM IR. 299 /// 300 /// This property corresponds to the LLVM IR inaccessiblememonly attribute. 301 FMRB_OnlyReadsInaccessibleMem = 302 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref), 303 304 /// The only memory references in this function (if it has any) are 305 /// writes to memory that is otherwise inaccessible via LLVM IR. 306 /// 307 /// This property corresponds to the LLVM IR inaccessiblememonly attribute. 308 FMRB_OnlyWritesInaccessibleMem = 309 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod), 310 311 /// The only memory references in this function (if it has any) are 312 /// references of memory that is otherwise inaccessible via LLVM IR. 313 /// 314 /// This property corresponds to the LLVM IR inaccessiblememonly attribute. 315 FMRB_OnlyAccessesInaccessibleMem = 316 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef), 317 318 /// The function may perform non-volatile loads from objects pointed 319 /// to by its pointer-typed arguments, with arbitrary offsets, and 320 /// it may also perform loads of memory that is otherwise 321 /// inaccessible via LLVM IR. 322 /// 323 /// This property corresponds to the LLVM IR 324 /// inaccessiblemem_or_argmemonly attribute. 325 FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem | 326 FMRL_ArgumentPointees | 327 static_cast<int>(ModRefInfo::Ref), 328 329 /// The function may perform non-volatile stores to objects pointed 330 /// to by its pointer-typed arguments, with arbitrary offsets, and 331 /// it may also perform stores of memory that is otherwise 332 /// inaccessible via LLVM IR. 333 /// 334 /// This property corresponds to the LLVM IR 335 /// inaccessiblemem_or_argmemonly attribute. 336 FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem | 337 FMRL_ArgumentPointees | 338 static_cast<int>(ModRefInfo::Mod), 339 340 /// The function may perform non-volatile loads and stores of objects 341 /// pointed to by its pointer-typed arguments, with arbitrary offsets, and 342 /// it may also perform loads and stores of memory that is otherwise 343 /// inaccessible via LLVM IR. 344 /// 345 /// This property corresponds to the LLVM IR 346 /// inaccessiblemem_or_argmemonly attribute. 347 FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem | 348 FMRL_ArgumentPointees | 349 static_cast<int>(ModRefInfo::ModRef), 350 351 /// This function does not perform any non-local stores or volatile loads, 352 /// but may read from any memory location. 353 /// 354 /// This property corresponds to the GCC 'pure' attribute. 355 /// This property corresponds to the LLVM IR 'readonly' attribute. 356 /// This property corresponds to the IntrReadMem LLVM intrinsic flag. 357 FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref), 358 359 // This function does not read from memory anywhere, but may write to any 360 // memory location. 361 // 362 // This property corresponds to the LLVM IR 'writeonly' attribute. 363 // This property corresponds to the IntrWriteMem LLVM intrinsic flag. 364 FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod), 365 366 /// This indicates that the function could not be classified into one of the 367 /// behaviors above. 368 FMRB_UnknownModRefBehavior = 369 FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef) 370}; 371 372// Wrapper method strips bits significant only in FunctionModRefBehavior, 373// to obtain a valid ModRefInfo. The benefit of using the wrapper is that if 374// ModRefInfo enum changes, the wrapper can be updated to & with the new enum 375// entry with all bits set to 1. 376LLVM_NODISCARD inline ModRefInfo 377createModRefInfo(const FunctionModRefBehavior FMRB) { 378 return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef)); 379} 380 381/// Reduced version of MemoryLocation that only stores a pointer and size. 382/// Used for caching AATags independent BasicAA results. 383struct AACacheLoc { 384 const Value *Ptr; 385 LocationSize Size; 386}; 387 388template <> struct DenseMapInfo<AACacheLoc> { 389 static inline AACacheLoc getEmptyKey() { 390 return {DenseMapInfo<const Value *>::getEmptyKey(), 391 DenseMapInfo<LocationSize>::getEmptyKey()}; 392 } 393 static inline AACacheLoc getTombstoneKey() { 394 return {DenseMapInfo<const Value *>::getTombstoneKey(), 395 DenseMapInfo<LocationSize>::getTombstoneKey()}; 396 } 397 static unsigned getHashValue(const AACacheLoc &Val) { 398 return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ 399 DenseMapInfo<LocationSize>::getHashValue(Val.Size); 400 } 401 static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { 402 return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; 403 } 404}; 405 406/// This class stores info we want to provide to or retain within an alias 407/// query. By default, the root query is stateless and starts with a freshly 408/// constructed info object. Specific alias analyses can use this query info to 409/// store per-query state that is important for recursive or nested queries to 410/// avoid recomputing. To enable preserving this state across multiple queries 411/// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. 412/// The information stored in an `AAQueryInfo` is currently limitted to the 413/// caches used by BasicAA, but can further be extended to fit other AA needs. 414class AAQueryInfo { 415public: 416 using LocPair = std::pair<AACacheLoc, AACacheLoc>; 417 struct CacheEntry { 418 AliasResult Result; 419 /// Number of times a NoAlias assumption has been used. 420 /// 0 for assumptions that have not been used, -1 for definitive results. 421 int NumAssumptionUses; 422 /// Whether this is a definitive (non-assumption) result. 423 bool isDefinitive() const { return NumAssumptionUses < 0; } 424 }; 425 using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; 426 AliasCacheT AliasCache; 427 428 using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>; 429 IsCapturedCacheT IsCapturedCache; 430 431 /// Query depth used to distinguish recursive queries. 432 unsigned Depth = 0; 433 434 /// How many active NoAlias assumption uses there are. 435 int NumAssumptionUses = 0; 436 437 /// Location pairs for which an assumption based result is currently stored. 438 /// Used to remove all potentially incorrect results from the cache if an 439 /// assumption is disproven. 440 SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; 441 442 AAQueryInfo() : AliasCache(), IsCapturedCache() {} 443 444 /// Create a new AAQueryInfo based on this one, but with the cache cleared. 445 /// This is used for recursive queries across phis, where cache results may 446 /// not be valid. 447 AAQueryInfo withEmptyCache() { 448 AAQueryInfo NewAAQI; 449 NewAAQI.Depth = Depth; 450 return NewAAQI; 451 } 452}; 453 454class BatchAAResults; 455 456class AAResults { 457public: 458 // Make these results default constructable and movable. We have to spell 459 // these out because MSVC won't synthesize them. 460 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} 461 AAResults(AAResults &&Arg); 462 ~AAResults(); 463 464 /// Register a specific AA result. 465 template <typename AAResultT> void addAAResult(AAResultT &AAResult) { 466 // FIXME: We should use a much lighter weight system than the usual 467 // polymorphic pattern because we don't own AAResult. It should 468 // ideally involve two pointers and no separate allocation. 469 AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); 470 } 471 472 /// Register a function analysis ID that the results aggregation depends on. 473 /// 474 /// This is used in the new pass manager to implement the invalidation logic 475 /// where we must invalidate the results aggregation if any of our component 476 /// analyses become invalid. 477 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } 478 479 /// Handle invalidation events in the new pass manager. 480 /// 481 /// The aggregation is invalidated if any of the underlying analyses is 482 /// invalidated. 483 bool invalidate(Function &F, const PreservedAnalyses &PA, 484 FunctionAnalysisManager::Invalidator &Inv); 485 486 //===--------------------------------------------------------------------===// 487 /// \name Alias Queries 488 /// @{ 489 490 /// The main low level interface to the alias analysis implementation. 491 /// Returns an AliasResult indicating whether the two pointers are aliased to 492 /// each other. This is the interface that must be implemented by specific 493 /// alias analysis implementations. 494 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); 495 496 /// A convenience wrapper around the primary \c alias interface. 497 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, 498 LocationSize V2Size) { 499 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 500 } 501 502 /// A convenience wrapper around the primary \c alias interface. 503 AliasResult alias(const Value *V1, const Value *V2) { 504 return alias(MemoryLocation::getBeforeOrAfter(V1), 505 MemoryLocation::getBeforeOrAfter(V2)); 506 } 507 508 /// A trivial helper function to check to see if the specified pointers are 509 /// no-alias. 510 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 511 return alias(LocA, LocB) == AliasResult::NoAlias; 512 } 513 514 /// A convenience wrapper around the \c isNoAlias helper interface. 515 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, 516 LocationSize V2Size) { 517 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 518 } 519 520 /// A convenience wrapper around the \c isNoAlias helper interface. 521 bool isNoAlias(const Value *V1, const Value *V2) { 522 return isNoAlias(MemoryLocation::getBeforeOrAfter(V1), 523 MemoryLocation::getBeforeOrAfter(V2)); 524 } 525 526 /// A trivial helper function to check to see if the specified pointers are 527 /// must-alias. 528 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 529 return alias(LocA, LocB) == AliasResult::MustAlias; 530 } 531 532 /// A convenience wrapper around the \c isMustAlias helper interface. 533 bool isMustAlias(const Value *V1, const Value *V2) { 534 return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) == 535 AliasResult::MustAlias; 536 } 537 538 /// Checks whether the given location points to constant memory, or if 539 /// \p OrLocal is true whether it points to a local alloca. 540 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); 541 542 /// A convenience wrapper around the primary \c pointsToConstantMemory 543 /// interface. 544 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 545 return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal); 546 } 547 548 /// @} 549 //===--------------------------------------------------------------------===// 550 /// \name Simple mod/ref information 551 /// @{ 552 553 /// Get the ModRef info associated with a pointer argument of a call. The 554 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 555 /// that these bits do not necessarily account for the overall behavior of 556 /// the function, but rather only provide additional per-argument 557 /// information. This never sets ModRefInfo::Must. 558 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); 559 560 /// Return the behavior of the given call site. 561 FunctionModRefBehavior getModRefBehavior(const CallBase *Call); 562 563 /// Return the behavior when calling the given function. 564 FunctionModRefBehavior getModRefBehavior(const Function *F); 565 566 /// Checks if the specified call is known to never read or write memory. 567 /// 568 /// Note that if the call only reads from known-constant memory, it is also 569 /// legal to return true. Also, calls that unwind the stack are legal for 570 /// this predicate. 571 /// 572 /// Many optimizations (such as CSE and LICM) can be performed on such calls 573 /// without worrying about aliasing properties, and many calls have this 574 /// property (e.g. calls to 'sin' and 'cos'). 575 /// 576 /// This property corresponds to the GCC 'const' attribute. 577 bool doesNotAccessMemory(const CallBase *Call) { 578 return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory; 579 } 580 581 /// Checks if the specified function is known to never read or write memory. 582 /// 583 /// Note that if the function only reads from known-constant memory, it is 584 /// also legal to return true. Also, function that unwind the stack are legal 585 /// for this predicate. 586 /// 587 /// Many optimizations (such as CSE and LICM) can be performed on such calls 588 /// to such functions without worrying about aliasing properties, and many 589 /// functions have this property (e.g. 'sin' and 'cos'). 590 /// 591 /// This property corresponds to the GCC 'const' attribute. 592 bool doesNotAccessMemory(const Function *F) { 593 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; 594 } 595 596 /// Checks if the specified call is known to only read from non-volatile 597 /// memory (or not access memory at all). 598 /// 599 /// Calls that unwind the stack are legal for this predicate. 600 /// 601 /// This property allows many common optimizations to be performed in the 602 /// absence of interfering store instructions, such as CSE of strlen calls. 603 /// 604 /// This property corresponds to the GCC 'pure' attribute. 605 bool onlyReadsMemory(const CallBase *Call) { 606 return onlyReadsMemory(getModRefBehavior(Call)); 607 } 608 609 /// Checks if the specified function is known to only read from non-volatile 610 /// memory (or not access memory at all). 611 /// 612 /// Functions that unwind the stack are legal for this predicate. 613 /// 614 /// This property allows many common optimizations to be performed in the 615 /// absence of interfering store instructions, such as CSE of strlen calls. 616 /// 617 /// This property corresponds to the GCC 'pure' attribute. 618 bool onlyReadsMemory(const Function *F) { 619 return onlyReadsMemory(getModRefBehavior(F)); 620 } 621 622 /// Checks if functions with the specified behavior are known to only read 623 /// from non-volatile memory (or not access memory at all). 624 static bool onlyReadsMemory(FunctionModRefBehavior MRB) { 625 return !isModSet(createModRefInfo(MRB)); 626 } 627 628 /// Checks if functions with the specified behavior are known to only write 629 /// memory (or not access memory at all). 630 static bool doesNotReadMemory(FunctionModRefBehavior MRB) { 631 return !isRefSet(createModRefInfo(MRB)); 632 } 633 634 /// Checks if functions with the specified behavior are known to read and 635 /// write at most from objects pointed to by their pointer-typed arguments 636 /// (with arbitrary offsets). 637 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { 638 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); 639 } 640 641 /// Checks if functions with the specified behavior are known to potentially 642 /// read or write from objects pointed to be their pointer-typed arguments 643 /// (with arbitrary offsets). 644 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { 645 return isModOrRefSet(createModRefInfo(MRB)) && 646 ((unsigned)MRB & FMRL_ArgumentPointees); 647 } 648 649 /// Checks if functions with the specified behavior are known to read and 650 /// write at most from memory that is inaccessible from LLVM IR. 651 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { 652 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); 653 } 654 655 /// Checks if functions with the specified behavior are known to potentially 656 /// read or write from memory that is inaccessible from LLVM IR. 657 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { 658 return isModOrRefSet(createModRefInfo(MRB)) && 659 ((unsigned)MRB & FMRL_InaccessibleMem); 660 } 661 662 /// Checks if functions with the specified behavior are known to read and 663 /// write at most from memory that is inaccessible from LLVM IR or objects 664 /// pointed to by their pointer-typed arguments (with arbitrary offsets). 665 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { 666 return !((unsigned)MRB & FMRL_Anywhere & 667 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); 668 } 669 670 /// getModRefInfo (for call sites) - Return information about whether 671 /// a particular call site modifies or reads the specified memory location. 672 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc); 673 674 /// getModRefInfo (for call sites) - A convenience wrapper. 675 ModRefInfo getModRefInfo(const CallBase *Call, const Value *P, 676 LocationSize Size) { 677 return getModRefInfo(Call, MemoryLocation(P, Size)); 678 } 679 680 /// getModRefInfo (for loads) - Return information about whether 681 /// a particular load modifies or reads the specified memory location. 682 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); 683 684 /// getModRefInfo (for loads) - A convenience wrapper. 685 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, 686 LocationSize Size) { 687 return getModRefInfo(L, MemoryLocation(P, Size)); 688 } 689 690 /// getModRefInfo (for stores) - Return information about whether 691 /// a particular store modifies or reads the specified memory location. 692 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); 693 694 /// getModRefInfo (for stores) - A convenience wrapper. 695 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, 696 LocationSize Size) { 697 return getModRefInfo(S, MemoryLocation(P, Size)); 698 } 699 700 /// getModRefInfo (for fences) - Return information about whether 701 /// a particular store modifies or reads the specified memory location. 702 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); 703 704 /// getModRefInfo (for fences) - A convenience wrapper. 705 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, 706 LocationSize Size) { 707 return getModRefInfo(S, MemoryLocation(P, Size)); 708 } 709 710 /// getModRefInfo (for cmpxchges) - Return information about whether 711 /// a particular cmpxchg modifies or reads the specified memory location. 712 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 713 const MemoryLocation &Loc); 714 715 /// getModRefInfo (for cmpxchges) - A convenience wrapper. 716 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, 717 LocationSize Size) { 718 return getModRefInfo(CX, MemoryLocation(P, Size)); 719 } 720 721 /// getModRefInfo (for atomicrmws) - Return information about whether 722 /// a particular atomicrmw modifies or reads the specified memory location. 723 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); 724 725 /// getModRefInfo (for atomicrmws) - A convenience wrapper. 726 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, 727 LocationSize Size) { 728 return getModRefInfo(RMW, MemoryLocation(P, Size)); 729 } 730 731 /// getModRefInfo (for va_args) - Return information about whether 732 /// a particular va_arg modifies or reads the specified memory location. 733 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); 734 735 /// getModRefInfo (for va_args) - A convenience wrapper. 736 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, 737 LocationSize Size) { 738 return getModRefInfo(I, MemoryLocation(P, Size)); 739 } 740 741 /// getModRefInfo (for catchpads) - Return information about whether 742 /// a particular catchpad modifies or reads the specified memory location. 743 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); 744 745 /// getModRefInfo (for catchpads) - A convenience wrapper. 746 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, 747 LocationSize Size) { 748 return getModRefInfo(I, MemoryLocation(P, Size)); 749 } 750 751 /// getModRefInfo (for catchrets) - Return information about whether 752 /// a particular catchret modifies or reads the specified memory location. 753 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); 754 755 /// getModRefInfo (for catchrets) - A convenience wrapper. 756 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, 757 LocationSize Size) { 758 return getModRefInfo(I, MemoryLocation(P, Size)); 759 } 760 761 /// Check whether or not an instruction may read or write the optionally 762 /// specified memory location. 763 /// 764 /// 765 /// An instruction that doesn't read or write memory may be trivially LICM'd 766 /// for example. 767 /// 768 /// For function calls, this delegates to the alias-analysis specific 769 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific 770 /// helpers above. 771 ModRefInfo getModRefInfo(const Instruction *I, 772 const Optional<MemoryLocation> &OptLoc) { 773 AAQueryInfo AAQIP; 774 return getModRefInfo(I, OptLoc, AAQIP); 775 } 776 777 /// A convenience wrapper for constructing the memory location. 778 ModRefInfo getModRefInfo(const Instruction *I, const Value *P, 779 LocationSize Size) { 780 return getModRefInfo(I, MemoryLocation(P, Size)); 781 } 782 783 /// Return information about whether a call and an instruction may refer to 784 /// the same memory locations. 785 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call); 786 787 /// Return information about whether two call sites may refer to the same set 788 /// of memory locations. See the AA documentation for details: 789 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 790 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); 791 792 /// Return information about whether a particular call site modifies 793 /// or reads the specified memory location \p MemLoc before instruction \p I 794 /// in a BasicBlock. 795 /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being 796 /// set. 797 ModRefInfo callCapturesBefore(const Instruction *I, 798 const MemoryLocation &MemLoc, 799 DominatorTree *DT) { 800 AAQueryInfo AAQIP; 801 return callCapturesBefore(I, MemLoc, DT, AAQIP); 802 } 803 804 /// A convenience wrapper to synthesize a memory location. 805 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, 806 LocationSize Size, DominatorTree *DT) { 807 return callCapturesBefore(I, MemoryLocation(P, Size), DT); 808 } 809 810 /// @} 811 //===--------------------------------------------------------------------===// 812 /// \name Higher level methods for querying mod/ref information. 813 /// @{ 814 815 /// Check if it is possible for execution of the specified basic block to 816 /// modify the location Loc. 817 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); 818 819 /// A convenience wrapper synthesizing a memory location. 820 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, 821 LocationSize Size) { 822 return canBasicBlockModify(BB, MemoryLocation(P, Size)); 823 } 824 825 /// Check if it is possible for the execution of the specified instructions 826 /// to mod\ref (according to the mode) the location Loc. 827 /// 828 /// The instructions to consider are all of the instructions in the range of 829 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 830 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 831 const MemoryLocation &Loc, 832 const ModRefInfo Mode); 833 834 /// A convenience wrapper synthesizing a memory location. 835 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 836 const Value *Ptr, LocationSize Size, 837 const ModRefInfo Mode) { 838 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); 839 } 840 841private: 842 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 843 AAQueryInfo &AAQI); 844 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 845 bool OrLocal = false); 846 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2, 847 AAQueryInfo &AAQIP); 848 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 849 AAQueryInfo &AAQI); 850 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 851 AAQueryInfo &AAQI); 852 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, 853 AAQueryInfo &AAQI); 854 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, 855 AAQueryInfo &AAQI); 856 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, 857 AAQueryInfo &AAQI); 858 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, 859 AAQueryInfo &AAQI); 860 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 861 const MemoryLocation &Loc, AAQueryInfo &AAQI); 862 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, 863 AAQueryInfo &AAQI); 864 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, 865 AAQueryInfo &AAQI); 866 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, 867 AAQueryInfo &AAQI); 868 ModRefInfo getModRefInfo(const Instruction *I, 869 const Optional<MemoryLocation> &OptLoc, 870 AAQueryInfo &AAQIP); 871 ModRefInfo callCapturesBefore(const Instruction *I, 872 const MemoryLocation &MemLoc, DominatorTree *DT, 873 AAQueryInfo &AAQIP); 874 875 class Concept; 876 877 template <typename T> class Model; 878 879 template <typename T> friend class AAResultBase; 880 881 const TargetLibraryInfo &TLI; 882 883 std::vector<std::unique_ptr<Concept>> AAs; 884 885 std::vector<AnalysisKey *> AADeps; 886 887 friend class BatchAAResults; 888}; 889 890/// This class is a wrapper over an AAResults, and it is intended to be used 891/// only when there are no IR changes inbetween queries. BatchAAResults is 892/// reusing the same `AAQueryInfo` to preserve the state across queries, 893/// esentially making AA work in "batch mode". The internal state cannot be 894/// cleared, so to go "out-of-batch-mode", the user must either use AAResults, 895/// or create a new BatchAAResults. 896class BatchAAResults { 897 AAResults &AA; 898 AAQueryInfo AAQI; 899 900public: 901 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {} 902 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 903 return AA.alias(LocA, LocB, AAQI); 904 } 905 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { 906 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); 907 } 908 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { 909 return AA.getModRefInfo(Call, Loc, AAQI); 910 } 911 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) { 912 return AA.getModRefInfo(Call1, Call2, AAQI); 913 } 914 ModRefInfo getModRefInfo(const Instruction *I, 915 const Optional<MemoryLocation> &OptLoc) { 916 return AA.getModRefInfo(I, OptLoc, AAQI); 917 } 918 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) { 919 return AA.getModRefInfo(I, Call2, AAQI); 920 } 921 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 922 return AA.getArgModRefInfo(Call, ArgIdx); 923 } 924 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 925 return AA.getModRefBehavior(Call); 926 } 927 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 928 return alias(LocA, LocB) == AliasResult::MustAlias; 929 } 930 bool isMustAlias(const Value *V1, const Value *V2) { 931 return alias(MemoryLocation(V1, LocationSize::precise(1)), 932 MemoryLocation(V2, LocationSize::precise(1))) == 933 AliasResult::MustAlias; 934 } 935 ModRefInfo callCapturesBefore(const Instruction *I, 936 const MemoryLocation &MemLoc, 937 DominatorTree *DT) { 938 return AA.callCapturesBefore(I, MemLoc, DT, AAQI); 939 } 940}; 941 942/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis 943/// pointer or reference. 944using AliasAnalysis = AAResults; 945 946/// A private abstract base class describing the concept of an individual alias 947/// analysis implementation. 948/// 949/// This interface is implemented by any \c Model instantiation. It is also the 950/// interface which a type used to instantiate the model must provide. 951/// 952/// All of these methods model methods by the same name in the \c 953/// AAResults class. Only differences and specifics to how the 954/// implementations are called are documented here. 955class AAResults::Concept { 956public: 957 virtual ~Concept() = 0; 958 959 /// An update API used internally by the AAResults to provide 960 /// a handle back to the top level aggregation. 961 virtual void setAAResults(AAResults *NewAAR) = 0; 962 963 //===--------------------------------------------------------------------===// 964 /// \name Alias Queries 965 /// @{ 966 967 /// The main low level interface to the alias analysis implementation. 968 /// Returns an AliasResult indicating whether the two pointers are aliased to 969 /// each other. This is the interface that must be implemented by specific 970 /// alias analysis implementations. 971 virtual AliasResult alias(const MemoryLocation &LocA, 972 const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0; 973 974 /// Checks whether the given location points to constant memory, or if 975 /// \p OrLocal is true whether it points to a local alloca. 976 virtual bool pointsToConstantMemory(const MemoryLocation &Loc, 977 AAQueryInfo &AAQI, bool OrLocal) = 0; 978 979 /// @} 980 //===--------------------------------------------------------------------===// 981 /// \name Simple mod/ref information 982 /// @{ 983 984 /// Get the ModRef info associated with a pointer argument of a callsite. The 985 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 986 /// that these bits do not necessarily account for the overall behavior of 987 /// the function, but rather only provide additional per-argument 988 /// information. 989 virtual ModRefInfo getArgModRefInfo(const CallBase *Call, 990 unsigned ArgIdx) = 0; 991 992 /// Return the behavior of the given call site. 993 virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0; 994 995 /// Return the behavior when calling the given function. 996 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; 997 998 /// getModRefInfo (for call sites) - Return information about whether 999 /// a particular call site modifies or reads the specified memory location. 1000 virtual ModRefInfo getModRefInfo(const CallBase *Call, 1001 const MemoryLocation &Loc, 1002 AAQueryInfo &AAQI) = 0; 1003 1004 /// Return information about whether two call sites may refer to the same set 1005 /// of memory locations. See the AA documentation for details: 1006 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 1007 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1008 AAQueryInfo &AAQI) = 0; 1009 1010 /// @} 1011}; 1012 1013/// A private class template which derives from \c Concept and wraps some other 1014/// type. 1015/// 1016/// This models the concept by directly forwarding each interface point to the 1017/// wrapped type which must implement a compatible interface. This provides 1018/// a type erased binding. 1019template <typename AAResultT> class AAResults::Model final : public Concept { 1020 AAResultT &Result; 1021 1022public: 1023 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { 1024 Result.setAAResults(&AAR); 1025 } 1026 ~Model() override = default; 1027 1028 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } 1029 1030 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1031 AAQueryInfo &AAQI) override { 1032 return Result.alias(LocA, LocB, AAQI); 1033 } 1034 1035 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1036 bool OrLocal) override { 1037 return Result.pointsToConstantMemory(Loc, AAQI, OrLocal); 1038 } 1039 1040 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { 1041 return Result.getArgModRefInfo(Call, ArgIdx); 1042 } 1043 1044 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override { 1045 return Result.getModRefBehavior(Call); 1046 } 1047 1048 FunctionModRefBehavior getModRefBehavior(const Function *F) override { 1049 return Result.getModRefBehavior(F); 1050 } 1051 1052 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1053 AAQueryInfo &AAQI) override { 1054 return Result.getModRefInfo(Call, Loc, AAQI); 1055 } 1056 1057 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1058 AAQueryInfo &AAQI) override { 1059 return Result.getModRefInfo(Call1, Call2, AAQI); 1060 } 1061}; 1062 1063/// A CRTP-driven "mixin" base class to help implement the function alias 1064/// analysis results concept. 1065/// 1066/// Because of the nature of many alias analysis implementations, they often 1067/// only implement a subset of the interface. This base class will attempt to 1068/// implement the remaining portions of the interface in terms of simpler forms 1069/// of the interface where possible, and otherwise provide conservatively 1070/// correct fallback implementations. 1071/// 1072/// Implementors of an alias analysis should derive from this CRTP, and then 1073/// override specific methods that they wish to customize. There is no need to 1074/// use virtual anywhere, the CRTP base class does static dispatch to the 1075/// derived type passed into it. 1076template <typename DerivedT> class AAResultBase { 1077 // Expose some parts of the interface only to the AAResults::Model 1078 // for wrapping. Specifically, this allows the model to call our 1079 // setAAResults method without exposing it as a fully public API. 1080 friend class AAResults::Model<DerivedT>; 1081 1082 /// A pointer to the AAResults object that this AAResult is 1083 /// aggregated within. May be null if not aggregated. 1084 AAResults *AAR = nullptr; 1085 1086 /// Helper to dispatch calls back through the derived type. 1087 DerivedT &derived() { return static_cast<DerivedT &>(*this); } 1088 1089 /// A setter for the AAResults pointer, which is used to satisfy the 1090 /// AAResults::Model contract. 1091 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } 1092 1093protected: 1094 /// This proxy class models a common pattern where we delegate to either the 1095 /// top-level \c AAResults aggregation if one is registered, or to the 1096 /// current result if none are registered. 1097 class AAResultsProxy { 1098 AAResults *AAR; 1099 DerivedT &CurrentResult; 1100 1101 public: 1102 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) 1103 : AAR(AAR), CurrentResult(CurrentResult) {} 1104 1105 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1106 AAQueryInfo &AAQI) { 1107 return AAR ? AAR->alias(LocA, LocB, AAQI) 1108 : CurrentResult.alias(LocA, LocB, AAQI); 1109 } 1110 1111 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1112 bool OrLocal) { 1113 return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal) 1114 : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal); 1115 } 1116 1117 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 1118 return AAR ? AAR->getArgModRefInfo(Call, ArgIdx) 1119 : CurrentResult.getArgModRefInfo(Call, ArgIdx); 1120 } 1121 1122 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 1123 return AAR ? AAR->getModRefBehavior(Call) 1124 : CurrentResult.getModRefBehavior(Call); 1125 } 1126 1127 FunctionModRefBehavior getModRefBehavior(const Function *F) { 1128 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); 1129 } 1130 1131 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1132 AAQueryInfo &AAQI) { 1133 return AAR ? AAR->getModRefInfo(Call, Loc, AAQI) 1134 : CurrentResult.getModRefInfo(Call, Loc, AAQI); 1135 } 1136 1137 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1138 AAQueryInfo &AAQI) { 1139 return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI) 1140 : CurrentResult.getModRefInfo(Call1, Call2, AAQI); 1141 } 1142 }; 1143 1144 explicit AAResultBase() = default; 1145 1146 // Provide all the copy and move constructors so that derived types aren't 1147 // constrained. 1148 AAResultBase(const AAResultBase &Arg) {} 1149 AAResultBase(AAResultBase &&Arg) {} 1150 1151 /// Get a proxy for the best AA result set to query at this time. 1152 /// 1153 /// When this result is part of a larger aggregation, this will proxy to that 1154 /// aggregation. When this result is used in isolation, it will just delegate 1155 /// back to the derived class's implementation. 1156 /// 1157 /// Note that callers of this need to take considerable care to not cause 1158 /// performance problems when they use this routine, in the case of a large 1159 /// number of alias analyses being aggregated, it can be expensive to walk 1160 /// back across the chain. 1161 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } 1162 1163public: 1164 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1165 AAQueryInfo &AAQI) { 1166 return AliasResult::MayAlias; 1167 } 1168 1169 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1170 bool OrLocal) { 1171 return false; 1172 } 1173 1174 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 1175 return ModRefInfo::ModRef; 1176 } 1177 1178 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 1179 return FMRB_UnknownModRefBehavior; 1180 } 1181 1182 FunctionModRefBehavior getModRefBehavior(const Function *F) { 1183 return FMRB_UnknownModRefBehavior; 1184 } 1185 1186 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1187 AAQueryInfo &AAQI) { 1188 return ModRefInfo::ModRef; 1189 } 1190 1191 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1192 AAQueryInfo &AAQI) { 1193 return ModRefInfo::ModRef; 1194 } 1195}; 1196 1197/// Return true if this pointer is returned by a noalias function. 1198bool isNoAliasCall(const Value *V); 1199 1200/// Return true if this pointer refers to a distinct and identifiable object. 1201/// This returns true for: 1202/// Global Variables and Functions (but not Global Aliases) 1203/// Allocas 1204/// ByVal and NoAlias Arguments 1205/// NoAlias returns (e.g. calls to malloc) 1206/// 1207bool isIdentifiedObject(const Value *V); 1208 1209/// Return true if V is umabigously identified at the function-level. 1210/// Different IdentifiedFunctionLocals can't alias. 1211/// Further, an IdentifiedFunctionLocal can not alias with any function 1212/// arguments other than itself, which is not necessarily true for 1213/// IdentifiedObjects. 1214bool isIdentifiedFunctionLocal(const Value *V); 1215 1216/// A manager for alias analyses. 1217/// 1218/// This class can have analyses registered with it and when run, it will run 1219/// all of them and aggregate their results into single AA results interface 1220/// that dispatches across all of the alias analysis results available. 1221/// 1222/// Note that the order in which analyses are registered is very significant. 1223/// That is the order in which the results will be aggregated and queried. 1224/// 1225/// This manager effectively wraps the AnalysisManager for registering alias 1226/// analyses. When you register your alias analysis with this manager, it will 1227/// ensure the analysis itself is registered with its AnalysisManager. 1228/// 1229/// The result of this analysis is only invalidated if one of the particular 1230/// aggregated AA results end up being invalidated. This removes the need to 1231/// explicitly preserve the results of `AAManager`. Note that analyses should no 1232/// longer be registered once the `AAManager` is run. 1233class AAManager : public AnalysisInfoMixin<AAManager> { 1234public: 1235 using Result = AAResults; 1236 1237 /// Register a specific AA result. 1238 template <typename AnalysisT> void registerFunctionAnalysis() { 1239 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); 1240 } 1241 1242 /// Register a specific AA result. 1243 template <typename AnalysisT> void registerModuleAnalysis() { 1244 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); 1245 } 1246 1247 Result run(Function &F, FunctionAnalysisManager &AM); 1248 1249private: 1250 friend AnalysisInfoMixin<AAManager>; 1251 1252 static AnalysisKey Key; 1253 1254 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, 1255 AAResults &AAResults), 1256 4> ResultGetters; 1257 1258 template <typename AnalysisT> 1259 static void getFunctionAAResultImpl(Function &F, 1260 FunctionAnalysisManager &AM, 1261 AAResults &AAResults) { 1262 AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); 1263 AAResults.addAADependencyID(AnalysisT::ID()); 1264 } 1265 1266 template <typename AnalysisT> 1267 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, 1268 AAResults &AAResults) { 1269 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); 1270 if (auto *R = 1271 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { 1272 AAResults.addAAResult(*R); 1273 MAMProxy 1274 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); 1275 } 1276 } 1277}; 1278 1279/// A wrapper pass to provide the legacy pass manager access to a suitably 1280/// prepared AAResults object. 1281class AAResultsWrapperPass : public FunctionPass { 1282 std::unique_ptr<AAResults> AAR; 1283 1284public: 1285 static char ID; 1286 1287 AAResultsWrapperPass(); 1288 1289 AAResults &getAAResults() { return *AAR; } 1290 const AAResults &getAAResults() const { return *AAR; } 1291 1292 bool runOnFunction(Function &F) override; 1293 1294 void getAnalysisUsage(AnalysisUsage &AU) const override; 1295}; 1296 1297/// A wrapper pass for external alias analyses. This just squirrels away the 1298/// callback used to run any analyses and register their results. 1299struct ExternalAAWrapperPass : ImmutablePass { 1300 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; 1301 1302 CallbackT CB; 1303 1304 static char ID; 1305 1306 ExternalAAWrapperPass(); 1307 1308 explicit ExternalAAWrapperPass(CallbackT CB); 1309 1310 void getAnalysisUsage(AnalysisUsage &AU) const override { 1311 AU.setPreservesAll(); 1312 } 1313}; 1314 1315FunctionPass *createAAResultsWrapperPass(); 1316 1317/// A wrapper pass around a callback which can be used to populate the 1318/// AAResults in the AAResultsWrapperPass from an external AA. 1319/// 1320/// The callback provided here will be used each time we prepare an AAResults 1321/// object, and will receive a reference to the function wrapper pass, the 1322/// function, and the AAResults object to populate. This should be used when 1323/// setting up a custom pass pipeline to inject a hook into the AA results. 1324ImmutablePass *createExternalAAWrapperPass( 1325 std::function<void(Pass &, Function &, AAResults &)> Callback); 1326 1327/// A helper for the legacy pass manager to create a \c AAResults 1328/// object populated to the best of our ability for a particular function when 1329/// inside of a \c ModulePass or a \c CallGraphSCCPass. 1330/// 1331/// If a \c ModulePass or a \c CallGraphSCCPass calls \p 1332/// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p 1333/// getAnalysisUsage. 1334AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); 1335 1336/// A helper for the legacy pass manager to populate \p AU to add uses to make 1337/// sure the analyses required by \p createLegacyPMAAResults are available. 1338void getAAResultsAnalysisUsage(AnalysisUsage &AU); 1339 1340} // end namespace llvm 1341 1342#endif // LLVM_ANALYSIS_ALIASANALYSIS_H 1343