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/Optional.h" 42 #include "llvm/ADT/SmallVector.h" 43 #include "llvm/Analysis/MemoryLocation.h" 44 #include "llvm/IR/PassManager.h" 45 #include "llvm/Pass.h" 46 #include <cstdint> 47 #include <functional> 48 #include <memory> 49 #include <vector> 50 51 namespace llvm { 52 53 class AnalysisUsage; 54 class AtomicCmpXchgInst; 55 class BasicAAResult; 56 class BasicBlock; 57 class CatchPadInst; 58 class CatchReturnInst; 59 class DominatorTree; 60 class FenceInst; 61 class Function; 62 class LoopInfo; 63 class PreservedAnalyses; 64 class TargetLibraryInfo; 65 class Value; 66 template <typename> class SmallPtrSetImpl; 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. 81 class AliasResult { 82 private: 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 92 public: 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 136 static_assert(sizeof(AliasResult) == 4, 137 "AliasResult size is intended to be 4 bytes!"); 138 139 /// << operator for AliasResult. 140 raw_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. 148 enum 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 185 LLVM_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 } 189 LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { 190 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef); 191 } 192 LLVM_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 } 196 LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { 197 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod); 198 } 199 LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { 200 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef); 201 } 202 LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { 203 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef)); 204 } 205 206 LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { 207 return ModRefInfo(static_cast<int>(MRI) | 208 static_cast<int>(ModRefInfo::MustMod)); 209 } 210 LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { 211 return ModRefInfo(static_cast<int>(MRI) | 212 static_cast<int>(ModRefInfo::MustRef)); 213 } 214 LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { 215 return ModRefInfo(static_cast<int>(MRI) & 216 static_cast<int>(ModRefInfo::MustModRef)); 217 } 218 LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { 219 return ModRefInfo(static_cast<int>(MRI) | 220 static_cast<int>(ModRefInfo::MustModRef)); 221 } 222 LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { 223 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref)); 224 } 225 LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { 226 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod)); 227 } 228 LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { 229 return ModRefInfo(static_cast<int>(MRI) | 230 static_cast<int>(ModRefInfo::NoModRef)); 231 } 232 LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, 233 const ModRefInfo MRI2) { 234 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2)); 235 } 236 LLVM_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. 246 enum 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. 262 enum 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. 376 LLVM_NODISCARD inline ModRefInfo 377 createModRefInfo(const FunctionModRefBehavior FMRB) { 378 return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef)); 379 } 380 381 /// Virtual base class for providers of capture information. 382 struct CaptureInfo { 383 virtual ~CaptureInfo() = 0; 384 virtual bool isNotCapturedBeforeOrAt(const Value *Object, 385 const Instruction *I) = 0; 386 }; 387 388 /// Context-free CaptureInfo provider, which computes and caches whether an 389 /// object is captured in the function at all, but does not distinguish whether 390 /// it was captured before or after the context instruction. 391 class SimpleCaptureInfo final : public CaptureInfo { 392 SmallDenseMap<const Value *, bool, 8> IsCapturedCache; 393 394 public: 395 bool isNotCapturedBeforeOrAt(const Value *Object, 396 const Instruction *I) override; 397 }; 398 399 /// Context-sensitive CaptureInfo provider, which computes and caches the 400 /// earliest common dominator closure of all captures. It provides a good 401 /// approximation to a precise "captures before" analysis. 402 class EarliestEscapeInfo final : public CaptureInfo { 403 DominatorTree &DT; 404 const LoopInfo &LI; 405 406 /// Map from identified local object to an instruction before which it does 407 /// not escape, or nullptr if it never escapes. The "earliest" instruction 408 /// may be a conservative approximation, e.g. the first instruction in the 409 /// function is always a legal choice. 410 DenseMap<const Value *, Instruction *> EarliestEscapes; 411 412 /// Reverse map from instruction to the objects it is the earliest escape for. 413 /// This is used for cache invalidation purposes. 414 DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj; 415 416 const SmallPtrSetImpl<const Value *> &EphValues; 417 418 public: 419 EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI, 420 const SmallPtrSetImpl<const Value *> &EphValues) 421 : DT(DT), LI(LI), EphValues(EphValues) {} 422 423 bool isNotCapturedBeforeOrAt(const Value *Object, 424 const Instruction *I) override; 425 426 void removeInstruction(Instruction *I); 427 }; 428 429 /// Reduced version of MemoryLocation that only stores a pointer and size. 430 /// Used for caching AATags independent BasicAA results. 431 struct AACacheLoc { 432 const Value *Ptr; 433 LocationSize Size; 434 }; 435 436 template <> struct DenseMapInfo<AACacheLoc> { 437 static inline AACacheLoc getEmptyKey() { 438 return {DenseMapInfo<const Value *>::getEmptyKey(), 439 DenseMapInfo<LocationSize>::getEmptyKey()}; 440 } 441 static inline AACacheLoc getTombstoneKey() { 442 return {DenseMapInfo<const Value *>::getTombstoneKey(), 443 DenseMapInfo<LocationSize>::getTombstoneKey()}; 444 } 445 static unsigned getHashValue(const AACacheLoc &Val) { 446 return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ 447 DenseMapInfo<LocationSize>::getHashValue(Val.Size); 448 } 449 static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { 450 return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; 451 } 452 }; 453 454 /// This class stores info we want to provide to or retain within an alias 455 /// query. By default, the root query is stateless and starts with a freshly 456 /// constructed info object. Specific alias analyses can use this query info to 457 /// store per-query state that is important for recursive or nested queries to 458 /// avoid recomputing. To enable preserving this state across multiple queries 459 /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. 460 /// The information stored in an `AAQueryInfo` is currently limitted to the 461 /// caches used by BasicAA, but can further be extended to fit other AA needs. 462 class AAQueryInfo { 463 public: 464 using LocPair = std::pair<AACacheLoc, AACacheLoc>; 465 struct CacheEntry { 466 AliasResult Result; 467 /// Number of times a NoAlias assumption has been used. 468 /// 0 for assumptions that have not been used, -1 for definitive results. 469 int NumAssumptionUses; 470 /// Whether this is a definitive (non-assumption) result. 471 bool isDefinitive() const { return NumAssumptionUses < 0; } 472 }; 473 using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; 474 AliasCacheT AliasCache; 475 476 CaptureInfo *CI; 477 478 /// Query depth used to distinguish recursive queries. 479 unsigned Depth = 0; 480 481 /// How many active NoAlias assumption uses there are. 482 int NumAssumptionUses = 0; 483 484 /// Location pairs for which an assumption based result is currently stored. 485 /// Used to remove all potentially incorrect results from the cache if an 486 /// assumption is disproven. 487 SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; 488 489 AAQueryInfo(CaptureInfo *CI) : CI(CI) {} 490 491 /// Create a new AAQueryInfo based on this one, but with the cache cleared. 492 /// This is used for recursive queries across phis, where cache results may 493 /// not be valid. 494 AAQueryInfo withEmptyCache() { 495 AAQueryInfo NewAAQI(CI); 496 NewAAQI.Depth = Depth; 497 return NewAAQI; 498 } 499 }; 500 501 /// AAQueryInfo that uses SimpleCaptureInfo. 502 class SimpleAAQueryInfo : public AAQueryInfo { 503 SimpleCaptureInfo CI; 504 505 public: 506 SimpleAAQueryInfo() : AAQueryInfo(&CI) {} 507 }; 508 509 class BatchAAResults; 510 511 class AAResults { 512 public: 513 // Make these results default constructable and movable. We have to spell 514 // these out because MSVC won't synthesize them. 515 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} 516 AAResults(AAResults &&Arg); 517 ~AAResults(); 518 519 /// Register a specific AA result. 520 template <typename AAResultT> void addAAResult(AAResultT &AAResult) { 521 // FIXME: We should use a much lighter weight system than the usual 522 // polymorphic pattern because we don't own AAResult. It should 523 // ideally involve two pointers and no separate allocation. 524 AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); 525 } 526 527 /// Register a function analysis ID that the results aggregation depends on. 528 /// 529 /// This is used in the new pass manager to implement the invalidation logic 530 /// where we must invalidate the results aggregation if any of our component 531 /// analyses become invalid. 532 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } 533 534 /// Handle invalidation events in the new pass manager. 535 /// 536 /// The aggregation is invalidated if any of the underlying analyses is 537 /// invalidated. 538 bool invalidate(Function &F, const PreservedAnalyses &PA, 539 FunctionAnalysisManager::Invalidator &Inv); 540 541 //===--------------------------------------------------------------------===// 542 /// \name Alias Queries 543 /// @{ 544 545 /// The main low level interface to the alias analysis implementation. 546 /// Returns an AliasResult indicating whether the two pointers are aliased to 547 /// each other. This is the interface that must be implemented by specific 548 /// alias analysis implementations. 549 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); 550 551 /// A convenience wrapper around the primary \c alias interface. 552 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, 553 LocationSize V2Size) { 554 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 555 } 556 557 /// A convenience wrapper around the primary \c alias interface. 558 AliasResult alias(const Value *V1, const Value *V2) { 559 return alias(MemoryLocation::getBeforeOrAfter(V1), 560 MemoryLocation::getBeforeOrAfter(V2)); 561 } 562 563 /// A trivial helper function to check to see if the specified pointers are 564 /// no-alias. 565 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 566 return alias(LocA, LocB) == AliasResult::NoAlias; 567 } 568 569 /// A convenience wrapper around the \c isNoAlias helper interface. 570 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, 571 LocationSize V2Size) { 572 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 573 } 574 575 /// A convenience wrapper around the \c isNoAlias helper interface. 576 bool isNoAlias(const Value *V1, const Value *V2) { 577 return isNoAlias(MemoryLocation::getBeforeOrAfter(V1), 578 MemoryLocation::getBeforeOrAfter(V2)); 579 } 580 581 /// A trivial helper function to check to see if the specified pointers are 582 /// must-alias. 583 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 584 return alias(LocA, LocB) == AliasResult::MustAlias; 585 } 586 587 /// A convenience wrapper around the \c isMustAlias helper interface. 588 bool isMustAlias(const Value *V1, const Value *V2) { 589 return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) == 590 AliasResult::MustAlias; 591 } 592 593 /// Checks whether the given location points to constant memory, or if 594 /// \p OrLocal is true whether it points to a local alloca. 595 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); 596 597 /// A convenience wrapper around the primary \c pointsToConstantMemory 598 /// interface. 599 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 600 return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal); 601 } 602 603 /// @} 604 //===--------------------------------------------------------------------===// 605 /// \name Simple mod/ref information 606 /// @{ 607 608 /// Get the ModRef info associated with a pointer argument of a call. The 609 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 610 /// that these bits do not necessarily account for the overall behavior of 611 /// the function, but rather only provide additional per-argument 612 /// information. This never sets ModRefInfo::Must. 613 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); 614 615 /// Return the behavior of the given call site. 616 FunctionModRefBehavior getModRefBehavior(const CallBase *Call); 617 618 /// Return the behavior when calling the given function. 619 FunctionModRefBehavior getModRefBehavior(const Function *F); 620 621 /// Checks if the specified call is known to never read or write memory. 622 /// 623 /// Note that if the call only reads from known-constant memory, it is also 624 /// legal to return true. Also, calls that unwind the stack are legal for 625 /// this predicate. 626 /// 627 /// Many optimizations (such as CSE and LICM) can be performed on such calls 628 /// without worrying about aliasing properties, and many calls have this 629 /// property (e.g. calls to 'sin' and 'cos'). 630 /// 631 /// This property corresponds to the GCC 'const' attribute. 632 bool doesNotAccessMemory(const CallBase *Call) { 633 return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory; 634 } 635 636 /// Checks if the specified function is known to never read or write memory. 637 /// 638 /// Note that if the function only reads from known-constant memory, it is 639 /// also legal to return true. Also, function that unwind the stack are legal 640 /// for this predicate. 641 /// 642 /// Many optimizations (such as CSE and LICM) can be performed on such calls 643 /// to such functions without worrying about aliasing properties, and many 644 /// functions have this property (e.g. 'sin' and 'cos'). 645 /// 646 /// This property corresponds to the GCC 'const' attribute. 647 bool doesNotAccessMemory(const Function *F) { 648 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; 649 } 650 651 /// Checks if the specified call is known to only read from non-volatile 652 /// memory (or not access memory at all). 653 /// 654 /// Calls that unwind the stack are legal for this predicate. 655 /// 656 /// This property allows many common optimizations to be performed in the 657 /// absence of interfering store instructions, such as CSE of strlen calls. 658 /// 659 /// This property corresponds to the GCC 'pure' attribute. 660 bool onlyReadsMemory(const CallBase *Call) { 661 return onlyReadsMemory(getModRefBehavior(Call)); 662 } 663 664 /// Checks if the specified function is known to only read from non-volatile 665 /// memory (or not access memory at all). 666 /// 667 /// Functions that unwind the stack are legal for this predicate. 668 /// 669 /// This property allows many common optimizations to be performed in the 670 /// absence of interfering store instructions, such as CSE of strlen calls. 671 /// 672 /// This property corresponds to the GCC 'pure' attribute. 673 bool onlyReadsMemory(const Function *F) { 674 return onlyReadsMemory(getModRefBehavior(F)); 675 } 676 677 /// Checks if functions with the specified behavior are known to only read 678 /// from non-volatile memory (or not access memory at all). 679 static bool onlyReadsMemory(FunctionModRefBehavior MRB) { 680 return !isModSet(createModRefInfo(MRB)); 681 } 682 683 /// Checks if functions with the specified behavior are known to only write 684 /// memory (or not access memory at all). 685 static bool onlyWritesMemory(FunctionModRefBehavior MRB) { 686 return !isRefSet(createModRefInfo(MRB)); 687 } 688 689 /// Checks if functions with the specified behavior are known to read and 690 /// write at most from objects pointed to by their pointer-typed arguments 691 /// (with arbitrary offsets). 692 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { 693 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); 694 } 695 696 /// Checks if functions with the specified behavior are known to potentially 697 /// read or write from objects pointed to be their pointer-typed arguments 698 /// (with arbitrary offsets). 699 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { 700 return isModOrRefSet(createModRefInfo(MRB)) && 701 ((unsigned)MRB & FMRL_ArgumentPointees); 702 } 703 704 /// Checks if functions with the specified behavior are known to read and 705 /// write at most from memory that is inaccessible from LLVM IR. 706 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { 707 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); 708 } 709 710 /// Checks if functions with the specified behavior are known to potentially 711 /// read or write from memory that is inaccessible from LLVM IR. 712 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { 713 return isModOrRefSet(createModRefInfo(MRB)) && 714 ((unsigned)MRB & FMRL_InaccessibleMem); 715 } 716 717 /// Checks if functions with the specified behavior are known to read and 718 /// write at most from memory that is inaccessible from LLVM IR or objects 719 /// pointed to by their pointer-typed arguments (with arbitrary offsets). 720 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { 721 return !((unsigned)MRB & FMRL_Anywhere & 722 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); 723 } 724 725 /// getModRefInfo (for call sites) - Return information about whether 726 /// a particular call site modifies or reads the specified memory location. 727 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc); 728 729 /// getModRefInfo (for call sites) - A convenience wrapper. 730 ModRefInfo getModRefInfo(const CallBase *Call, const Value *P, 731 LocationSize Size) { 732 return getModRefInfo(Call, MemoryLocation(P, Size)); 733 } 734 735 /// getModRefInfo (for loads) - Return information about whether 736 /// a particular load modifies or reads the specified memory location. 737 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); 738 739 /// getModRefInfo (for loads) - A convenience wrapper. 740 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, 741 LocationSize Size) { 742 return getModRefInfo(L, MemoryLocation(P, Size)); 743 } 744 745 /// getModRefInfo (for stores) - Return information about whether 746 /// a particular store modifies or reads the specified memory location. 747 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); 748 749 /// getModRefInfo (for stores) - A convenience wrapper. 750 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, 751 LocationSize Size) { 752 return getModRefInfo(S, MemoryLocation(P, Size)); 753 } 754 755 /// getModRefInfo (for fences) - Return information about whether 756 /// a particular store modifies or reads the specified memory location. 757 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); 758 759 /// getModRefInfo (for fences) - A convenience wrapper. 760 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, 761 LocationSize Size) { 762 return getModRefInfo(S, MemoryLocation(P, Size)); 763 } 764 765 /// getModRefInfo (for cmpxchges) - Return information about whether 766 /// a particular cmpxchg modifies or reads the specified memory location. 767 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 768 const MemoryLocation &Loc); 769 770 /// getModRefInfo (for cmpxchges) - A convenience wrapper. 771 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, 772 LocationSize Size) { 773 return getModRefInfo(CX, MemoryLocation(P, Size)); 774 } 775 776 /// getModRefInfo (for atomicrmws) - Return information about whether 777 /// a particular atomicrmw modifies or reads the specified memory location. 778 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); 779 780 /// getModRefInfo (for atomicrmws) - A convenience wrapper. 781 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, 782 LocationSize Size) { 783 return getModRefInfo(RMW, MemoryLocation(P, Size)); 784 } 785 786 /// getModRefInfo (for va_args) - Return information about whether 787 /// a particular va_arg modifies or reads the specified memory location. 788 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); 789 790 /// getModRefInfo (for va_args) - A convenience wrapper. 791 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, 792 LocationSize Size) { 793 return getModRefInfo(I, MemoryLocation(P, Size)); 794 } 795 796 /// getModRefInfo (for catchpads) - Return information about whether 797 /// a particular catchpad modifies or reads the specified memory location. 798 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); 799 800 /// getModRefInfo (for catchpads) - A convenience wrapper. 801 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, 802 LocationSize Size) { 803 return getModRefInfo(I, MemoryLocation(P, Size)); 804 } 805 806 /// getModRefInfo (for catchrets) - Return information about whether 807 /// a particular catchret modifies or reads the specified memory location. 808 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); 809 810 /// getModRefInfo (for catchrets) - A convenience wrapper. 811 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, 812 LocationSize Size) { 813 return getModRefInfo(I, MemoryLocation(P, Size)); 814 } 815 816 /// Check whether or not an instruction may read or write the optionally 817 /// specified memory location. 818 /// 819 /// 820 /// An instruction that doesn't read or write memory may be trivially LICM'd 821 /// for example. 822 /// 823 /// For function calls, this delegates to the alias-analysis specific 824 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific 825 /// helpers above. 826 ModRefInfo getModRefInfo(const Instruction *I, 827 const Optional<MemoryLocation> &OptLoc) { 828 SimpleAAQueryInfo AAQIP; 829 return getModRefInfo(I, OptLoc, AAQIP); 830 } 831 832 /// A convenience wrapper for constructing the memory location. 833 ModRefInfo getModRefInfo(const Instruction *I, const Value *P, 834 LocationSize Size) { 835 return getModRefInfo(I, MemoryLocation(P, Size)); 836 } 837 838 /// Return information about whether a call and an instruction may refer to 839 /// the same memory locations. 840 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call); 841 842 /// Return information about whether two call sites may refer to the same set 843 /// of memory locations. See the AA documentation for details: 844 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 845 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); 846 847 /// Return information about whether a particular call site modifies 848 /// or reads the specified memory location \p MemLoc before instruction \p I 849 /// in a BasicBlock. 850 /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being 851 /// set. 852 ModRefInfo callCapturesBefore(const Instruction *I, 853 const MemoryLocation &MemLoc, 854 DominatorTree *DT) { 855 SimpleAAQueryInfo AAQIP; 856 return callCapturesBefore(I, MemLoc, DT, AAQIP); 857 } 858 859 /// A convenience wrapper to synthesize a memory location. 860 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, 861 LocationSize Size, DominatorTree *DT) { 862 return callCapturesBefore(I, MemoryLocation(P, Size), DT); 863 } 864 865 /// @} 866 //===--------------------------------------------------------------------===// 867 /// \name Higher level methods for querying mod/ref information. 868 /// @{ 869 870 /// Check if it is possible for execution of the specified basic block to 871 /// modify the location Loc. 872 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); 873 874 /// A convenience wrapper synthesizing a memory location. 875 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, 876 LocationSize Size) { 877 return canBasicBlockModify(BB, MemoryLocation(P, Size)); 878 } 879 880 /// Check if it is possible for the execution of the specified instructions 881 /// to mod\ref (according to the mode) the location Loc. 882 /// 883 /// The instructions to consider are all of the instructions in the range of 884 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 885 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 886 const MemoryLocation &Loc, 887 const ModRefInfo Mode); 888 889 /// A convenience wrapper synthesizing a memory location. 890 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 891 const Value *Ptr, LocationSize Size, 892 const ModRefInfo Mode) { 893 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); 894 } 895 896 private: 897 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 898 AAQueryInfo &AAQI); 899 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 900 bool OrLocal = false); 901 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2, 902 AAQueryInfo &AAQIP); 903 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 904 AAQueryInfo &AAQI); 905 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 906 AAQueryInfo &AAQI); 907 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, 908 AAQueryInfo &AAQI); 909 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, 910 AAQueryInfo &AAQI); 911 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, 912 AAQueryInfo &AAQI); 913 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, 914 AAQueryInfo &AAQI); 915 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 916 const MemoryLocation &Loc, AAQueryInfo &AAQI); 917 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, 918 AAQueryInfo &AAQI); 919 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, 920 AAQueryInfo &AAQI); 921 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, 922 AAQueryInfo &AAQI); 923 ModRefInfo getModRefInfo(const Instruction *I, 924 const Optional<MemoryLocation> &OptLoc, 925 AAQueryInfo &AAQIP); 926 ModRefInfo callCapturesBefore(const Instruction *I, 927 const MemoryLocation &MemLoc, DominatorTree *DT, 928 AAQueryInfo &AAQIP); 929 930 class Concept; 931 932 template <typename T> class Model; 933 934 template <typename T> friend class AAResultBase; 935 936 const TargetLibraryInfo &TLI; 937 938 std::vector<std::unique_ptr<Concept>> AAs; 939 940 std::vector<AnalysisKey *> AADeps; 941 942 friend class BatchAAResults; 943 }; 944 945 /// This class is a wrapper over an AAResults, and it is intended to be used 946 /// only when there are no IR changes inbetween queries. BatchAAResults is 947 /// reusing the same `AAQueryInfo` to preserve the state across queries, 948 /// esentially making AA work in "batch mode". The internal state cannot be 949 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, 950 /// or create a new BatchAAResults. 951 class BatchAAResults { 952 AAResults &AA; 953 AAQueryInfo AAQI; 954 SimpleCaptureInfo SimpleCI; 955 956 public: 957 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(&SimpleCI) {} 958 BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(CI) {} 959 960 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 961 return AA.alias(LocA, LocB, AAQI); 962 } 963 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { 964 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); 965 } 966 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { 967 return AA.getModRefInfo(Call, Loc, AAQI); 968 } 969 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) { 970 return AA.getModRefInfo(Call1, Call2, AAQI); 971 } 972 ModRefInfo getModRefInfo(const Instruction *I, 973 const Optional<MemoryLocation> &OptLoc) { 974 return AA.getModRefInfo(I, OptLoc, AAQI); 975 } 976 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) { 977 return AA.getModRefInfo(I, Call2, AAQI); 978 } 979 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 980 return AA.getArgModRefInfo(Call, ArgIdx); 981 } 982 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 983 return AA.getModRefBehavior(Call); 984 } 985 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 986 return alias(LocA, LocB) == AliasResult::MustAlias; 987 } 988 bool isMustAlias(const Value *V1, const Value *V2) { 989 return alias(MemoryLocation(V1, LocationSize::precise(1)), 990 MemoryLocation(V2, LocationSize::precise(1))) == 991 AliasResult::MustAlias; 992 } 993 ModRefInfo callCapturesBefore(const Instruction *I, 994 const MemoryLocation &MemLoc, 995 DominatorTree *DT) { 996 return AA.callCapturesBefore(I, MemLoc, DT, AAQI); 997 } 998 }; 999 1000 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis 1001 /// pointer or reference. 1002 using AliasAnalysis = AAResults; 1003 1004 /// A private abstract base class describing the concept of an individual alias 1005 /// analysis implementation. 1006 /// 1007 /// This interface is implemented by any \c Model instantiation. It is also the 1008 /// interface which a type used to instantiate the model must provide. 1009 /// 1010 /// All of these methods model methods by the same name in the \c 1011 /// AAResults class. Only differences and specifics to how the 1012 /// implementations are called are documented here. 1013 class AAResults::Concept { 1014 public: 1015 virtual ~Concept() = 0; 1016 1017 /// An update API used internally by the AAResults to provide 1018 /// a handle back to the top level aggregation. 1019 virtual void setAAResults(AAResults *NewAAR) = 0; 1020 1021 //===--------------------------------------------------------------------===// 1022 /// \name Alias Queries 1023 /// @{ 1024 1025 /// The main low level interface to the alias analysis implementation. 1026 /// Returns an AliasResult indicating whether the two pointers are aliased to 1027 /// each other. This is the interface that must be implemented by specific 1028 /// alias analysis implementations. 1029 virtual AliasResult alias(const MemoryLocation &LocA, 1030 const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0; 1031 1032 /// Checks whether the given location points to constant memory, or if 1033 /// \p OrLocal is true whether it points to a local alloca. 1034 virtual bool pointsToConstantMemory(const MemoryLocation &Loc, 1035 AAQueryInfo &AAQI, bool OrLocal) = 0; 1036 1037 /// @} 1038 //===--------------------------------------------------------------------===// 1039 /// \name Simple mod/ref information 1040 /// @{ 1041 1042 /// Get the ModRef info associated with a pointer argument of a callsite. The 1043 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 1044 /// that these bits do not necessarily account for the overall behavior of 1045 /// the function, but rather only provide additional per-argument 1046 /// information. 1047 virtual ModRefInfo getArgModRefInfo(const CallBase *Call, 1048 unsigned ArgIdx) = 0; 1049 1050 /// Return the behavior of the given call site. 1051 virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0; 1052 1053 /// Return the behavior when calling the given function. 1054 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; 1055 1056 /// getModRefInfo (for call sites) - Return information about whether 1057 /// a particular call site modifies or reads the specified memory location. 1058 virtual ModRefInfo getModRefInfo(const CallBase *Call, 1059 const MemoryLocation &Loc, 1060 AAQueryInfo &AAQI) = 0; 1061 1062 /// Return information about whether two call sites may refer to the same set 1063 /// of memory locations. See the AA documentation for details: 1064 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 1065 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1066 AAQueryInfo &AAQI) = 0; 1067 1068 /// @} 1069 }; 1070 1071 /// A private class template which derives from \c Concept and wraps some other 1072 /// type. 1073 /// 1074 /// This models the concept by directly forwarding each interface point to the 1075 /// wrapped type which must implement a compatible interface. This provides 1076 /// a type erased binding. 1077 template <typename AAResultT> class AAResults::Model final : public Concept { 1078 AAResultT &Result; 1079 1080 public: 1081 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { 1082 Result.setAAResults(&AAR); 1083 } 1084 ~Model() override = default; 1085 1086 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } 1087 1088 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1089 AAQueryInfo &AAQI) override { 1090 return Result.alias(LocA, LocB, AAQI); 1091 } 1092 1093 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1094 bool OrLocal) override { 1095 return Result.pointsToConstantMemory(Loc, AAQI, OrLocal); 1096 } 1097 1098 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { 1099 return Result.getArgModRefInfo(Call, ArgIdx); 1100 } 1101 1102 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override { 1103 return Result.getModRefBehavior(Call); 1104 } 1105 1106 FunctionModRefBehavior getModRefBehavior(const Function *F) override { 1107 return Result.getModRefBehavior(F); 1108 } 1109 1110 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1111 AAQueryInfo &AAQI) override { 1112 return Result.getModRefInfo(Call, Loc, AAQI); 1113 } 1114 1115 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1116 AAQueryInfo &AAQI) override { 1117 return Result.getModRefInfo(Call1, Call2, AAQI); 1118 } 1119 }; 1120 1121 /// A CRTP-driven "mixin" base class to help implement the function alias 1122 /// analysis results concept. 1123 /// 1124 /// Because of the nature of many alias analysis implementations, they often 1125 /// only implement a subset of the interface. This base class will attempt to 1126 /// implement the remaining portions of the interface in terms of simpler forms 1127 /// of the interface where possible, and otherwise provide conservatively 1128 /// correct fallback implementations. 1129 /// 1130 /// Implementors of an alias analysis should derive from this CRTP, and then 1131 /// override specific methods that they wish to customize. There is no need to 1132 /// use virtual anywhere, the CRTP base class does static dispatch to the 1133 /// derived type passed into it. 1134 template <typename DerivedT> class AAResultBase { 1135 // Expose some parts of the interface only to the AAResults::Model 1136 // for wrapping. Specifically, this allows the model to call our 1137 // setAAResults method without exposing it as a fully public API. 1138 friend class AAResults::Model<DerivedT>; 1139 1140 /// A pointer to the AAResults object that this AAResult is 1141 /// aggregated within. May be null if not aggregated. 1142 AAResults *AAR = nullptr; 1143 1144 /// Helper to dispatch calls back through the derived type. 1145 DerivedT &derived() { return static_cast<DerivedT &>(*this); } 1146 1147 /// A setter for the AAResults pointer, which is used to satisfy the 1148 /// AAResults::Model contract. 1149 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } 1150 1151 protected: 1152 /// This proxy class models a common pattern where we delegate to either the 1153 /// top-level \c AAResults aggregation if one is registered, or to the 1154 /// current result if none are registered. 1155 class AAResultsProxy { 1156 AAResults *AAR; 1157 DerivedT &CurrentResult; 1158 1159 public: 1160 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) 1161 : AAR(AAR), CurrentResult(CurrentResult) {} 1162 1163 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1164 AAQueryInfo &AAQI) { 1165 return AAR ? AAR->alias(LocA, LocB, AAQI) 1166 : CurrentResult.alias(LocA, LocB, AAQI); 1167 } 1168 1169 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1170 bool OrLocal) { 1171 return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal) 1172 : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal); 1173 } 1174 1175 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 1176 return AAR ? AAR->getArgModRefInfo(Call, ArgIdx) 1177 : CurrentResult.getArgModRefInfo(Call, ArgIdx); 1178 } 1179 1180 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 1181 return AAR ? AAR->getModRefBehavior(Call) 1182 : CurrentResult.getModRefBehavior(Call); 1183 } 1184 1185 FunctionModRefBehavior getModRefBehavior(const Function *F) { 1186 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); 1187 } 1188 1189 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1190 AAQueryInfo &AAQI) { 1191 return AAR ? AAR->getModRefInfo(Call, Loc, AAQI) 1192 : CurrentResult.getModRefInfo(Call, Loc, AAQI); 1193 } 1194 1195 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1196 AAQueryInfo &AAQI) { 1197 return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI) 1198 : CurrentResult.getModRefInfo(Call1, Call2, AAQI); 1199 } 1200 }; 1201 1202 explicit AAResultBase() = default; 1203 1204 // Provide all the copy and move constructors so that derived types aren't 1205 // constrained. 1206 AAResultBase(const AAResultBase &Arg) {} 1207 AAResultBase(AAResultBase &&Arg) {} 1208 1209 /// Get a proxy for the best AA result set to query at this time. 1210 /// 1211 /// When this result is part of a larger aggregation, this will proxy to that 1212 /// aggregation. When this result is used in isolation, it will just delegate 1213 /// back to the derived class's implementation. 1214 /// 1215 /// Note that callers of this need to take considerable care to not cause 1216 /// performance problems when they use this routine, in the case of a large 1217 /// number of alias analyses being aggregated, it can be expensive to walk 1218 /// back across the chain. 1219 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } 1220 1221 public: 1222 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 1223 AAQueryInfo &AAQI) { 1224 return AliasResult::MayAlias; 1225 } 1226 1227 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 1228 bool OrLocal) { 1229 return false; 1230 } 1231 1232 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 1233 return ModRefInfo::ModRef; 1234 } 1235 1236 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { 1237 return FMRB_UnknownModRefBehavior; 1238 } 1239 1240 FunctionModRefBehavior getModRefBehavior(const Function *F) { 1241 return FMRB_UnknownModRefBehavior; 1242 } 1243 1244 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 1245 AAQueryInfo &AAQI) { 1246 return ModRefInfo::ModRef; 1247 } 1248 1249 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 1250 AAQueryInfo &AAQI) { 1251 return ModRefInfo::ModRef; 1252 } 1253 }; 1254 1255 /// Return true if this pointer is returned by a noalias function. 1256 bool isNoAliasCall(const Value *V); 1257 1258 /// Return true if this pointer refers to a distinct and identifiable object. 1259 /// This returns true for: 1260 /// Global Variables and Functions (but not Global Aliases) 1261 /// Allocas 1262 /// ByVal and NoAlias Arguments 1263 /// NoAlias returns (e.g. calls to malloc) 1264 /// 1265 bool isIdentifiedObject(const Value *V); 1266 1267 /// Return true if V is umabigously identified at the function-level. 1268 /// Different IdentifiedFunctionLocals can't alias. 1269 /// Further, an IdentifiedFunctionLocal can not alias with any function 1270 /// arguments other than itself, which is not necessarily true for 1271 /// IdentifiedObjects. 1272 bool isIdentifiedFunctionLocal(const Value *V); 1273 1274 /// Returns true if the pointer is one which would have been considered an 1275 /// escape by isNonEscapingLocalObject. 1276 bool isEscapeSource(const Value *V); 1277 1278 /// Return true if Object memory is not visible after an unwind, in the sense 1279 /// that program semantics cannot depend on Object containing any particular 1280 /// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set 1281 /// to true, then the memory is only not visible if the object has not been 1282 /// captured prior to the unwind. Otherwise it is not visible even if captured. 1283 bool isNotVisibleOnUnwind(const Value *Object, 1284 bool &RequiresNoCaptureBeforeUnwind); 1285 1286 /// A manager for alias analyses. 1287 /// 1288 /// This class can have analyses registered with it and when run, it will run 1289 /// all of them and aggregate their results into single AA results interface 1290 /// that dispatches across all of the alias analysis results available. 1291 /// 1292 /// Note that the order in which analyses are registered is very significant. 1293 /// That is the order in which the results will be aggregated and queried. 1294 /// 1295 /// This manager effectively wraps the AnalysisManager for registering alias 1296 /// analyses. When you register your alias analysis with this manager, it will 1297 /// ensure the analysis itself is registered with its AnalysisManager. 1298 /// 1299 /// The result of this analysis is only invalidated if one of the particular 1300 /// aggregated AA results end up being invalidated. This removes the need to 1301 /// explicitly preserve the results of `AAManager`. Note that analyses should no 1302 /// longer be registered once the `AAManager` is run. 1303 class AAManager : public AnalysisInfoMixin<AAManager> { 1304 public: 1305 using Result = AAResults; 1306 1307 /// Register a specific AA result. 1308 template <typename AnalysisT> void registerFunctionAnalysis() { 1309 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); 1310 } 1311 1312 /// Register a specific AA result. 1313 template <typename AnalysisT> void registerModuleAnalysis() { 1314 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); 1315 } 1316 1317 Result run(Function &F, FunctionAnalysisManager &AM); 1318 1319 private: 1320 friend AnalysisInfoMixin<AAManager>; 1321 1322 static AnalysisKey Key; 1323 1324 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, 1325 AAResults &AAResults), 1326 4> ResultGetters; 1327 1328 template <typename AnalysisT> 1329 static void getFunctionAAResultImpl(Function &F, 1330 FunctionAnalysisManager &AM, 1331 AAResults &AAResults) { 1332 AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); 1333 AAResults.addAADependencyID(AnalysisT::ID()); 1334 } 1335 1336 template <typename AnalysisT> 1337 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, 1338 AAResults &AAResults) { 1339 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); 1340 if (auto *R = 1341 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { 1342 AAResults.addAAResult(*R); 1343 MAMProxy 1344 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); 1345 } 1346 } 1347 }; 1348 1349 /// A wrapper pass to provide the legacy pass manager access to a suitably 1350 /// prepared AAResults object. 1351 class AAResultsWrapperPass : public FunctionPass { 1352 std::unique_ptr<AAResults> AAR; 1353 1354 public: 1355 static char ID; 1356 1357 AAResultsWrapperPass(); 1358 1359 AAResults &getAAResults() { return *AAR; } 1360 const AAResults &getAAResults() const { return *AAR; } 1361 1362 bool runOnFunction(Function &F) override; 1363 1364 void getAnalysisUsage(AnalysisUsage &AU) const override; 1365 }; 1366 1367 /// A wrapper pass for external alias analyses. This just squirrels away the 1368 /// callback used to run any analyses and register their results. 1369 struct ExternalAAWrapperPass : ImmutablePass { 1370 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; 1371 1372 CallbackT CB; 1373 1374 static char ID; 1375 1376 ExternalAAWrapperPass(); 1377 1378 explicit ExternalAAWrapperPass(CallbackT CB); 1379 1380 void getAnalysisUsage(AnalysisUsage &AU) const override { 1381 AU.setPreservesAll(); 1382 } 1383 }; 1384 1385 FunctionPass *createAAResultsWrapperPass(); 1386 1387 /// A wrapper pass around a callback which can be used to populate the 1388 /// AAResults in the AAResultsWrapperPass from an external AA. 1389 /// 1390 /// The callback provided here will be used each time we prepare an AAResults 1391 /// object, and will receive a reference to the function wrapper pass, the 1392 /// function, and the AAResults object to populate. This should be used when 1393 /// setting up a custom pass pipeline to inject a hook into the AA results. 1394 ImmutablePass *createExternalAAWrapperPass( 1395 std::function<void(Pass &, Function &, AAResults &)> Callback); 1396 1397 /// A helper for the legacy pass manager to create a \c AAResults 1398 /// object populated to the best of our ability for a particular function when 1399 /// inside of a \c ModulePass or a \c CallGraphSCCPass. 1400 /// 1401 /// If a \c ModulePass or a \c CallGraphSCCPass calls \p 1402 /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p 1403 /// getAnalysisUsage. 1404 AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); 1405 1406 /// A helper for the legacy pass manager to populate \p AU to add uses to make 1407 /// sure the analyses required by \p createLegacyPMAAResults are available. 1408 void getAAResultsAnalysisUsage(AnalysisUsage &AU); 1409 1410 } // end namespace llvm 1411 1412 #endif // LLVM_ANALYSIS_ALIASANALYSIS_H 1413