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