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/Sequence.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 "llvm/Support/ModRef.h" 47 #include <cstdint> 48 #include <functional> 49 #include <memory> 50 #include <optional> 51 #include <vector> 52 53 namespace llvm { 54 55 class AnalysisUsage; 56 class AtomicCmpXchgInst; 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 bool operator==(const AliasResult &Other) const { 118 return Alias == Other.Alias && HasOffset == Other.HasOffset && 119 Offset == Other.Offset; 120 } 121 bool operator!=(const AliasResult &Other) const { return !(*this == Other); } 122 123 bool operator==(Kind K) const { return Alias == K; } 124 bool operator!=(Kind K) const { return !(*this == K); } 125 126 constexpr bool hasOffset() const { return HasOffset; } 127 constexpr int32_t getOffset() const { 128 assert(HasOffset && "No offset!"); 129 return Offset; 130 } 131 void setOffset(int32_t NewOffset) { 132 if (isInt<OffsetBits>(NewOffset)) { 133 HasOffset = true; 134 Offset = NewOffset; 135 } 136 } 137 138 /// Helper for processing AliasResult for swapped memory location pairs. 139 void swap(bool DoSwap = true) { 140 if (DoSwap && hasOffset()) 141 setOffset(-getOffset()); 142 } 143 }; 144 145 static_assert(sizeof(AliasResult) == 4, 146 "AliasResult size is intended to be 4 bytes!"); 147 148 /// << operator for AliasResult. 149 raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); 150 151 /// Virtual base class for providers of capture information. 152 struct CaptureInfo { 153 virtual ~CaptureInfo() = 0; 154 155 /// Check whether Object is not captured before instruction I. If OrAt is 156 /// true, captures by instruction I itself are also considered. 157 /// 158 /// If I is nullptr, then captures at any point will be considered. 159 virtual bool isNotCapturedBefore(const Value *Object, const Instruction *I, 160 bool OrAt) = 0; 161 }; 162 163 /// Context-free CaptureInfo provider, which computes and caches whether an 164 /// object is captured in the function at all, but does not distinguish whether 165 /// it was captured before or after the context instruction. 166 class SimpleCaptureInfo final : public CaptureInfo { 167 SmallDenseMap<const Value *, bool, 8> IsCapturedCache; 168 169 public: 170 bool isNotCapturedBefore(const Value *Object, const Instruction *I, 171 bool OrAt) override; 172 }; 173 174 /// Context-sensitive CaptureInfo provider, which computes and caches the 175 /// earliest common dominator closure of all captures. It provides a good 176 /// approximation to a precise "captures before" analysis. 177 class EarliestEscapeInfo final : public CaptureInfo { 178 DominatorTree &DT; 179 const LoopInfo *LI; 180 181 /// Map from identified local object to an instruction before which it does 182 /// not escape, or nullptr if it never escapes. The "earliest" instruction 183 /// may be a conservative approximation, e.g. the first instruction in the 184 /// function is always a legal choice. 185 DenseMap<const Value *, Instruction *> EarliestEscapes; 186 187 /// Reverse map from instruction to the objects it is the earliest escape for. 188 /// This is used for cache invalidation purposes. 189 DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj; 190 191 public: 192 EarliestEscapeInfo(DominatorTree &DT, const LoopInfo *LI = nullptr) 193 : DT(DT), LI(LI) {} 194 195 bool isNotCapturedBefore(const Value *Object, const Instruction *I, 196 bool OrAt) override; 197 198 void removeInstruction(Instruction *I); 199 }; 200 201 /// Cache key for BasicAA results. It only includes the pointer and size from 202 /// MemoryLocation, as BasicAA is AATags independent. Additionally, it includes 203 /// the value of MayBeCrossIteration, which may affect BasicAA results. 204 struct AACacheLoc { 205 using PtrTy = PointerIntPair<const Value *, 1, bool>; 206 PtrTy Ptr; 207 LocationSize Size; 208 209 AACacheLoc(PtrTy Ptr, LocationSize Size) : Ptr(Ptr), Size(Size) {} 210 AACacheLoc(const Value *Ptr, LocationSize Size, bool MayBeCrossIteration) 211 : Ptr(Ptr, MayBeCrossIteration), Size(Size) {} 212 }; 213 214 template <> struct DenseMapInfo<AACacheLoc> { 215 static inline AACacheLoc getEmptyKey() { 216 return {DenseMapInfo<AACacheLoc::PtrTy>::getEmptyKey(), 217 DenseMapInfo<LocationSize>::getEmptyKey()}; 218 } 219 static inline AACacheLoc getTombstoneKey() { 220 return {DenseMapInfo<AACacheLoc::PtrTy>::getTombstoneKey(), 221 DenseMapInfo<LocationSize>::getTombstoneKey()}; 222 } 223 static unsigned getHashValue(const AACacheLoc &Val) { 224 return DenseMapInfo<AACacheLoc::PtrTy>::getHashValue(Val.Ptr) ^ 225 DenseMapInfo<LocationSize>::getHashValue(Val.Size); 226 } 227 static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { 228 return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; 229 } 230 }; 231 232 class AAResults; 233 234 /// This class stores info we want to provide to or retain within an alias 235 /// query. By default, the root query is stateless and starts with a freshly 236 /// constructed info object. Specific alias analyses can use this query info to 237 /// store per-query state that is important for recursive or nested queries to 238 /// avoid recomputing. To enable preserving this state across multiple queries 239 /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. 240 /// The information stored in an `AAQueryInfo` is currently limitted to the 241 /// caches used by BasicAA, but can further be extended to fit other AA needs. 242 class AAQueryInfo { 243 public: 244 using LocPair = std::pair<AACacheLoc, AACacheLoc>; 245 struct CacheEntry { 246 AliasResult Result; 247 /// Number of times a NoAlias assumption has been used. 248 /// 0 for assumptions that have not been used, -1 for definitive results. 249 int NumAssumptionUses; 250 /// Whether this is a definitive (non-assumption) result. 251 bool isDefinitive() const { return NumAssumptionUses < 0; } 252 }; 253 254 // Alias analysis result aggregration using which this query is performed. 255 // Can be used to perform recursive queries. 256 AAResults &AAR; 257 258 using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; 259 AliasCacheT AliasCache; 260 261 CaptureInfo *CI; 262 263 /// Query depth used to distinguish recursive queries. 264 unsigned Depth = 0; 265 266 /// How many active NoAlias assumption uses there are. 267 int NumAssumptionUses = 0; 268 269 /// Location pairs for which an assumption based result is currently stored. 270 /// Used to remove all potentially incorrect results from the cache if an 271 /// assumption is disproven. 272 SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; 273 274 /// Tracks whether the accesses may be on different cycle iterations. 275 /// 276 /// When interpret "Value" pointer equality as value equality we need to make 277 /// sure that the "Value" is not part of a cycle. Otherwise, two uses could 278 /// come from different "iterations" of a cycle and see different values for 279 /// the same "Value" pointer. 280 /// 281 /// The following example shows the problem: 282 /// %p = phi(%alloca1, %addr2) 283 /// %l = load %ptr 284 /// %addr1 = gep, %alloca2, 0, %l 285 /// %addr2 = gep %alloca2, 0, (%l + 1) 286 /// alias(%p, %addr1) -> MayAlias ! 287 /// store %l, ... 288 bool MayBeCrossIteration = false; 289 290 /// Whether alias analysis is allowed to use the dominator tree, for use by 291 /// passes that lazily update the DT while performing AA queries. 292 bool UseDominatorTree = true; 293 294 AAQueryInfo(AAResults &AAR, CaptureInfo *CI) : AAR(AAR), CI(CI) {} 295 }; 296 297 /// AAQueryInfo that uses SimpleCaptureInfo. 298 class SimpleAAQueryInfo : public AAQueryInfo { 299 SimpleCaptureInfo CI; 300 301 public: 302 SimpleAAQueryInfo(AAResults &AAR) : AAQueryInfo(AAR, &CI) {} 303 }; 304 305 class BatchAAResults; 306 307 class AAResults { 308 public: 309 // Make these results default constructable and movable. We have to spell 310 // these out because MSVC won't synthesize them. 311 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} 312 AAResults(AAResults &&Arg); 313 ~AAResults(); 314 315 /// Register a specific AA result. 316 template <typename AAResultT> void addAAResult(AAResultT &AAResult) { 317 // FIXME: We should use a much lighter weight system than the usual 318 // polymorphic pattern because we don't own AAResult. It should 319 // ideally involve two pointers and no separate allocation. 320 AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); 321 } 322 323 /// Register a function analysis ID that the results aggregation depends on. 324 /// 325 /// This is used in the new pass manager to implement the invalidation logic 326 /// where we must invalidate the results aggregation if any of our component 327 /// analyses become invalid. 328 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } 329 330 /// Handle invalidation events in the new pass manager. 331 /// 332 /// The aggregation is invalidated if any of the underlying analyses is 333 /// invalidated. 334 bool invalidate(Function &F, const PreservedAnalyses &PA, 335 FunctionAnalysisManager::Invalidator &Inv); 336 337 //===--------------------------------------------------------------------===// 338 /// \name Alias Queries 339 /// @{ 340 341 /// The main low level interface to the alias analysis implementation. 342 /// Returns an AliasResult indicating whether the two pointers are aliased to 343 /// each other. This is the interface that must be implemented by specific 344 /// alias analysis implementations. 345 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); 346 347 /// A convenience wrapper around the primary \c alias interface. 348 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, 349 LocationSize V2Size) { 350 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 351 } 352 353 /// A convenience wrapper around the primary \c alias interface. 354 AliasResult alias(const Value *V1, const Value *V2) { 355 return alias(MemoryLocation::getBeforeOrAfter(V1), 356 MemoryLocation::getBeforeOrAfter(V2)); 357 } 358 359 /// A trivial helper function to check to see if the specified pointers are 360 /// no-alias. 361 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 362 return alias(LocA, LocB) == AliasResult::NoAlias; 363 } 364 365 /// A convenience wrapper around the \c isNoAlias helper interface. 366 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, 367 LocationSize V2Size) { 368 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); 369 } 370 371 /// A convenience wrapper around the \c isNoAlias helper interface. 372 bool isNoAlias(const Value *V1, const Value *V2) { 373 return isNoAlias(MemoryLocation::getBeforeOrAfter(V1), 374 MemoryLocation::getBeforeOrAfter(V2)); 375 } 376 377 /// A trivial helper function to check to see if the specified pointers are 378 /// must-alias. 379 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 380 return alias(LocA, LocB) == AliasResult::MustAlias; 381 } 382 383 /// A convenience wrapper around the \c isMustAlias helper interface. 384 bool isMustAlias(const Value *V1, const Value *V2) { 385 return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) == 386 AliasResult::MustAlias; 387 } 388 389 /// Checks whether the given location points to constant memory, or if 390 /// \p OrLocal is true whether it points to a local alloca. 391 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { 392 return isNoModRef(getModRefInfoMask(Loc, OrLocal)); 393 } 394 395 /// A convenience wrapper around the primary \c pointsToConstantMemory 396 /// interface. 397 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 398 return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal); 399 } 400 401 /// @} 402 //===--------------------------------------------------------------------===// 403 /// \name Simple mod/ref information 404 /// @{ 405 406 /// Returns a bitmask that should be unconditionally applied to the ModRef 407 /// info of a memory location. This allows us to eliminate Mod and/or Ref 408 /// from the ModRef info based on the knowledge that the memory location 409 /// points to constant and/or locally-invariant memory. 410 /// 411 /// If IgnoreLocals is true, then this method returns NoModRef for memory 412 /// that points to a local alloca. 413 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, 414 bool IgnoreLocals = false); 415 416 /// A convenience wrapper around the primary \c getModRefInfoMask 417 /// interface. 418 ModRefInfo getModRefInfoMask(const Value *P, bool IgnoreLocals = false) { 419 return getModRefInfoMask(MemoryLocation::getBeforeOrAfter(P), IgnoreLocals); 420 } 421 422 /// Get the ModRef info associated with a pointer argument of a call. The 423 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 424 /// that these bits do not necessarily account for the overall behavior of 425 /// the function, but rather only provide additional per-argument 426 /// information. 427 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); 428 429 /// Return the behavior of the given call site. 430 MemoryEffects getMemoryEffects(const CallBase *Call); 431 432 /// Return the behavior when calling the given function. 433 MemoryEffects getMemoryEffects(const Function *F); 434 435 /// Checks if the specified call is known to never read or write memory. 436 /// 437 /// Note that if the call only reads from known-constant memory, it is also 438 /// legal to return true. Also, calls that unwind the stack are legal for 439 /// this predicate. 440 /// 441 /// Many optimizations (such as CSE and LICM) can be performed on such calls 442 /// without worrying about aliasing properties, and many calls have this 443 /// property (e.g. calls to 'sin' and 'cos'). 444 /// 445 /// This property corresponds to the GCC 'const' attribute. 446 bool doesNotAccessMemory(const CallBase *Call) { 447 return getMemoryEffects(Call).doesNotAccessMemory(); 448 } 449 450 /// Checks if the specified function is known to never read or write memory. 451 /// 452 /// Note that if the function only reads from known-constant memory, it is 453 /// also legal to return true. Also, function that unwind the stack are legal 454 /// for this predicate. 455 /// 456 /// Many optimizations (such as CSE and LICM) can be performed on such calls 457 /// to such functions without worrying about aliasing properties, and many 458 /// functions have this property (e.g. 'sin' and 'cos'). 459 /// 460 /// This property corresponds to the GCC 'const' attribute. 461 bool doesNotAccessMemory(const Function *F) { 462 return getMemoryEffects(F).doesNotAccessMemory(); 463 } 464 465 /// Checks if the specified call is known to only read from non-volatile 466 /// memory (or not access memory at all). 467 /// 468 /// Calls that unwind the stack are legal for this predicate. 469 /// 470 /// This property allows many common optimizations to be performed in the 471 /// absence of interfering store instructions, such as CSE of strlen calls. 472 /// 473 /// This property corresponds to the GCC 'pure' attribute. 474 bool onlyReadsMemory(const CallBase *Call) { 475 return getMemoryEffects(Call).onlyReadsMemory(); 476 } 477 478 /// Checks if the specified function is known to only read from non-volatile 479 /// memory (or not access memory at all). 480 /// 481 /// Functions that unwind the stack are legal for this predicate. 482 /// 483 /// This property allows many common optimizations to be performed in the 484 /// absence of interfering store instructions, such as CSE of strlen calls. 485 /// 486 /// This property corresponds to the GCC 'pure' attribute. 487 bool onlyReadsMemory(const Function *F) { 488 return getMemoryEffects(F).onlyReadsMemory(); 489 } 490 491 /// Check whether or not an instruction may read or write the optionally 492 /// specified memory location. 493 /// 494 /// 495 /// An instruction that doesn't read or write memory may be trivially LICM'd 496 /// for example. 497 /// 498 /// For function calls, this delegates to the alias-analysis specific 499 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific 500 /// helpers above. 501 ModRefInfo getModRefInfo(const Instruction *I, 502 const std::optional<MemoryLocation> &OptLoc) { 503 SimpleAAQueryInfo AAQIP(*this); 504 return getModRefInfo(I, OptLoc, AAQIP); 505 } 506 507 /// A convenience wrapper for constructing the memory location. 508 ModRefInfo getModRefInfo(const Instruction *I, const Value *P, 509 LocationSize Size) { 510 return getModRefInfo(I, MemoryLocation(P, Size)); 511 } 512 513 /// Return information about whether a call and an instruction may refer to 514 /// the same memory locations. 515 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call); 516 517 /// Return information about whether a particular call site modifies 518 /// or reads the specified memory location \p MemLoc before instruction \p I 519 /// in a BasicBlock. 520 ModRefInfo callCapturesBefore(const Instruction *I, 521 const MemoryLocation &MemLoc, 522 DominatorTree *DT) { 523 SimpleAAQueryInfo AAQIP(*this); 524 return callCapturesBefore(I, MemLoc, DT, AAQIP); 525 } 526 527 /// A convenience wrapper to synthesize a memory location. 528 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, 529 LocationSize Size, DominatorTree *DT) { 530 return callCapturesBefore(I, MemoryLocation(P, Size), DT); 531 } 532 533 /// @} 534 //===--------------------------------------------------------------------===// 535 /// \name Higher level methods for querying mod/ref information. 536 /// @{ 537 538 /// Check if it is possible for execution of the specified basic block to 539 /// modify the location Loc. 540 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); 541 542 /// A convenience wrapper synthesizing a memory location. 543 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, 544 LocationSize Size) { 545 return canBasicBlockModify(BB, MemoryLocation(P, Size)); 546 } 547 548 /// Check if it is possible for the execution of the specified instructions 549 /// to mod\ref (according to the mode) the location Loc. 550 /// 551 /// The instructions to consider are all of the instructions in the range of 552 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 553 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 554 const MemoryLocation &Loc, 555 const ModRefInfo Mode); 556 557 /// A convenience wrapper synthesizing a memory location. 558 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, 559 const Value *Ptr, LocationSize Size, 560 const ModRefInfo Mode) { 561 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); 562 } 563 564 // CtxI can be nullptr, in which case the query is whether or not the aliasing 565 // relationship holds through the entire function. 566 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 567 AAQueryInfo &AAQI, const Instruction *CtxI = nullptr); 568 569 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, 570 bool OrLocal = false); 571 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, 572 bool IgnoreLocals = false); 573 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2, 574 AAQueryInfo &AAQIP); 575 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 576 AAQueryInfo &AAQI); 577 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 578 AAQueryInfo &AAQI); 579 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, 580 AAQueryInfo &AAQI); 581 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, 582 AAQueryInfo &AAQI); 583 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, 584 AAQueryInfo &AAQI); 585 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, 586 AAQueryInfo &AAQI); 587 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, 588 const MemoryLocation &Loc, AAQueryInfo &AAQI); 589 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, 590 AAQueryInfo &AAQI); 591 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, 592 AAQueryInfo &AAQI); 593 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, 594 AAQueryInfo &AAQI); 595 ModRefInfo getModRefInfo(const Instruction *I, 596 const std::optional<MemoryLocation> &OptLoc, 597 AAQueryInfo &AAQIP); 598 ModRefInfo callCapturesBefore(const Instruction *I, 599 const MemoryLocation &MemLoc, DominatorTree *DT, 600 AAQueryInfo &AAQIP); 601 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); 602 603 private: 604 class Concept; 605 606 template <typename T> class Model; 607 608 friend class AAResultBase; 609 610 const TargetLibraryInfo &TLI; 611 612 std::vector<std::unique_ptr<Concept>> AAs; 613 614 std::vector<AnalysisKey *> AADeps; 615 616 friend class BatchAAResults; 617 }; 618 619 /// This class is a wrapper over an AAResults, and it is intended to be used 620 /// only when there are no IR changes inbetween queries. BatchAAResults is 621 /// reusing the same `AAQueryInfo` to preserve the state across queries, 622 /// esentially making AA work in "batch mode". The internal state cannot be 623 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, 624 /// or create a new BatchAAResults. 625 class BatchAAResults { 626 AAResults &AA; 627 AAQueryInfo AAQI; 628 SimpleCaptureInfo SimpleCI; 629 630 public: 631 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {} 632 BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {} 633 634 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 635 return AA.alias(LocA, LocB, AAQI); 636 } 637 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { 638 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); 639 } 640 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, 641 bool IgnoreLocals = false) { 642 return AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals); 643 } 644 ModRefInfo getModRefInfo(const Instruction *I, 645 const std::optional<MemoryLocation> &OptLoc) { 646 return AA.getModRefInfo(I, OptLoc, AAQI); 647 } 648 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2) { 649 return AA.getModRefInfo(I, Call2, AAQI); 650 } 651 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 652 return AA.getArgModRefInfo(Call, ArgIdx); 653 } 654 MemoryEffects getMemoryEffects(const CallBase *Call) { 655 return AA.getMemoryEffects(Call, AAQI); 656 } 657 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 658 return alias(LocA, LocB) == AliasResult::MustAlias; 659 } 660 bool isMustAlias(const Value *V1, const Value *V2) { 661 return alias(MemoryLocation(V1, LocationSize::precise(1)), 662 MemoryLocation(V2, LocationSize::precise(1))) == 663 AliasResult::MustAlias; 664 } 665 ModRefInfo callCapturesBefore(const Instruction *I, 666 const MemoryLocation &MemLoc, 667 DominatorTree *DT) { 668 return AA.callCapturesBefore(I, MemLoc, DT, AAQI); 669 } 670 671 /// Assume that values may come from different cycle iterations. 672 void enableCrossIterationMode() { 673 AAQI.MayBeCrossIteration = true; 674 } 675 676 /// Disable the use of the dominator tree during alias analysis queries. 677 void disableDominatorTree() { AAQI.UseDominatorTree = false; } 678 }; 679 680 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis 681 /// pointer or reference. 682 using AliasAnalysis = AAResults; 683 684 /// A private abstract base class describing the concept of an individual alias 685 /// analysis implementation. 686 /// 687 /// This interface is implemented by any \c Model instantiation. It is also the 688 /// interface which a type used to instantiate the model must provide. 689 /// 690 /// All of these methods model methods by the same name in the \c 691 /// AAResults class. Only differences and specifics to how the 692 /// implementations are called are documented here. 693 class AAResults::Concept { 694 public: 695 virtual ~Concept() = 0; 696 697 //===--------------------------------------------------------------------===// 698 /// \name Alias Queries 699 /// @{ 700 701 /// The main low level interface to the alias analysis implementation. 702 /// Returns an AliasResult indicating whether the two pointers are aliased to 703 /// each other. This is the interface that must be implemented by specific 704 /// alias analysis implementations. 705 virtual AliasResult alias(const MemoryLocation &LocA, 706 const MemoryLocation &LocB, AAQueryInfo &AAQI, 707 const Instruction *CtxI) = 0; 708 709 /// @} 710 //===--------------------------------------------------------------------===// 711 /// \name Simple mod/ref information 712 /// @{ 713 714 /// Returns a bitmask that should be unconditionally applied to the ModRef 715 /// info of a memory location. This allows us to eliminate Mod and/or Ref from 716 /// the ModRef info based on the knowledge that the memory location points to 717 /// constant and/or locally-invariant memory. 718 virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, 719 AAQueryInfo &AAQI, 720 bool IgnoreLocals) = 0; 721 722 /// Get the ModRef info associated with a pointer argument of a callsite. The 723 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note 724 /// that these bits do not necessarily account for the overall behavior of 725 /// the function, but rather only provide additional per-argument 726 /// information. 727 virtual ModRefInfo getArgModRefInfo(const CallBase *Call, 728 unsigned ArgIdx) = 0; 729 730 /// Return the behavior of the given call site. 731 virtual MemoryEffects getMemoryEffects(const CallBase *Call, 732 AAQueryInfo &AAQI) = 0; 733 734 /// Return the behavior when calling the given function. 735 virtual MemoryEffects getMemoryEffects(const Function *F) = 0; 736 737 /// getModRefInfo (for call sites) - Return information about whether 738 /// a particular call site modifies or reads the specified memory location. 739 virtual ModRefInfo getModRefInfo(const CallBase *Call, 740 const MemoryLocation &Loc, 741 AAQueryInfo &AAQI) = 0; 742 743 /// Return information about whether two call sites may refer to the same set 744 /// of memory locations. See the AA documentation for details: 745 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 746 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 747 AAQueryInfo &AAQI) = 0; 748 749 /// @} 750 }; 751 752 /// A private class template which derives from \c Concept and wraps some other 753 /// type. 754 /// 755 /// This models the concept by directly forwarding each interface point to the 756 /// wrapped type which must implement a compatible interface. This provides 757 /// a type erased binding. 758 template <typename AAResultT> class AAResults::Model final : public Concept { 759 AAResultT &Result; 760 761 public: 762 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {} 763 ~Model() override = default; 764 765 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 766 AAQueryInfo &AAQI, const Instruction *CtxI) override { 767 return Result.alias(LocA, LocB, AAQI, CtxI); 768 } 769 770 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, 771 bool IgnoreLocals) override { 772 return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals); 773 } 774 775 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { 776 return Result.getArgModRefInfo(Call, ArgIdx); 777 } 778 779 MemoryEffects getMemoryEffects(const CallBase *Call, 780 AAQueryInfo &AAQI) override { 781 return Result.getMemoryEffects(Call, AAQI); 782 } 783 784 MemoryEffects getMemoryEffects(const Function *F) override { 785 return Result.getMemoryEffects(F); 786 } 787 788 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 789 AAQueryInfo &AAQI) override { 790 return Result.getModRefInfo(Call, Loc, AAQI); 791 } 792 793 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 794 AAQueryInfo &AAQI) override { 795 return Result.getModRefInfo(Call1, Call2, AAQI); 796 } 797 }; 798 799 /// A base class to help implement the function alias analysis results concept. 800 /// 801 /// Because of the nature of many alias analysis implementations, they often 802 /// only implement a subset of the interface. This base class will attempt to 803 /// implement the remaining portions of the interface in terms of simpler forms 804 /// of the interface where possible, and otherwise provide conservatively 805 /// correct fallback implementations. 806 /// 807 /// Implementors of an alias analysis should derive from this class, and then 808 /// override specific methods that they wish to customize. There is no need to 809 /// use virtual anywhere. 810 class AAResultBase { 811 protected: 812 explicit AAResultBase() = default; 813 814 // Provide all the copy and move constructors so that derived types aren't 815 // constrained. 816 AAResultBase(const AAResultBase &Arg) {} 817 AAResultBase(AAResultBase &&Arg) {} 818 819 public: 820 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 821 AAQueryInfo &AAQI, const Instruction *I) { 822 return AliasResult::MayAlias; 823 } 824 825 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, 826 bool IgnoreLocals) { 827 return ModRefInfo::ModRef; 828 } 829 830 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { 831 return ModRefInfo::ModRef; 832 } 833 834 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) { 835 return MemoryEffects::unknown(); 836 } 837 838 MemoryEffects getMemoryEffects(const Function *F) { 839 return MemoryEffects::unknown(); 840 } 841 842 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, 843 AAQueryInfo &AAQI) { 844 return ModRefInfo::ModRef; 845 } 846 847 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, 848 AAQueryInfo &AAQI) { 849 return ModRefInfo::ModRef; 850 } 851 }; 852 853 /// Return true if this pointer is returned by a noalias function. 854 bool isNoAliasCall(const Value *V); 855 856 /// Return true if this pointer refers to a distinct and identifiable object. 857 /// This returns true for: 858 /// Global Variables and Functions (but not Global Aliases) 859 /// Allocas 860 /// ByVal and NoAlias Arguments 861 /// NoAlias returns (e.g. calls to malloc) 862 /// 863 bool isIdentifiedObject(const Value *V); 864 865 /// Return true if V is umabigously identified at the function-level. 866 /// Different IdentifiedFunctionLocals can't alias. 867 /// Further, an IdentifiedFunctionLocal can not alias with any function 868 /// arguments other than itself, which is not necessarily true for 869 /// IdentifiedObjects. 870 bool isIdentifiedFunctionLocal(const Value *V); 871 872 /// Returns true if the pointer is one which would have been considered an 873 /// escape by isNonEscapingLocalObject. 874 bool isEscapeSource(const Value *V); 875 876 /// Return true if Object memory is not visible after an unwind, in the sense 877 /// that program semantics cannot depend on Object containing any particular 878 /// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set 879 /// to true, then the memory is only not visible if the object has not been 880 /// captured prior to the unwind. Otherwise it is not visible even if captured. 881 bool isNotVisibleOnUnwind(const Value *Object, 882 bool &RequiresNoCaptureBeforeUnwind); 883 884 /// Return true if the Object is writable, in the sense that any location based 885 /// on this pointer that can be loaded can also be stored to without trapping. 886 /// Additionally, at the point Object is declared, stores can be introduced 887 /// without data races. At later points, this is only the case if the pointer 888 /// can not escape to a different thread. 889 /// 890 /// If ExplicitlyDereferenceableOnly is set to true, this property only holds 891 /// for the part of Object that is explicitly marked as dereferenceable, e.g. 892 /// using the dereferenceable(N) attribute. It does not necessarily hold for 893 /// parts that are only known to be dereferenceable due to the presence of 894 /// loads. 895 bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly); 896 897 /// A manager for alias analyses. 898 /// 899 /// This class can have analyses registered with it and when run, it will run 900 /// all of them and aggregate their results into single AA results interface 901 /// that dispatches across all of the alias analysis results available. 902 /// 903 /// Note that the order in which analyses are registered is very significant. 904 /// That is the order in which the results will be aggregated and queried. 905 /// 906 /// This manager effectively wraps the AnalysisManager for registering alias 907 /// analyses. When you register your alias analysis with this manager, it will 908 /// ensure the analysis itself is registered with its AnalysisManager. 909 /// 910 /// The result of this analysis is only invalidated if one of the particular 911 /// aggregated AA results end up being invalidated. This removes the need to 912 /// explicitly preserve the results of `AAManager`. Note that analyses should no 913 /// longer be registered once the `AAManager` is run. 914 class AAManager : public AnalysisInfoMixin<AAManager> { 915 public: 916 using Result = AAResults; 917 918 /// Register a specific AA result. 919 template <typename AnalysisT> void registerFunctionAnalysis() { 920 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); 921 } 922 923 /// Register a specific AA result. 924 template <typename AnalysisT> void registerModuleAnalysis() { 925 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); 926 } 927 928 Result run(Function &F, FunctionAnalysisManager &AM); 929 930 private: 931 friend AnalysisInfoMixin<AAManager>; 932 933 static AnalysisKey Key; 934 935 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, 936 AAResults &AAResults), 937 4> ResultGetters; 938 939 template <typename AnalysisT> 940 static void getFunctionAAResultImpl(Function &F, 941 FunctionAnalysisManager &AM, 942 AAResults &AAResults) { 943 AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); 944 AAResults.addAADependencyID(AnalysisT::ID()); 945 } 946 947 template <typename AnalysisT> 948 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, 949 AAResults &AAResults) { 950 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); 951 if (auto *R = 952 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { 953 AAResults.addAAResult(*R); 954 MAMProxy 955 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); 956 } 957 } 958 }; 959 960 /// A wrapper pass to provide the legacy pass manager access to a suitably 961 /// prepared AAResults object. 962 class AAResultsWrapperPass : public FunctionPass { 963 std::unique_ptr<AAResults> AAR; 964 965 public: 966 static char ID; 967 968 AAResultsWrapperPass(); 969 970 AAResults &getAAResults() { return *AAR; } 971 const AAResults &getAAResults() const { return *AAR; } 972 973 bool runOnFunction(Function &F) override; 974 975 void getAnalysisUsage(AnalysisUsage &AU) const override; 976 }; 977 978 /// A wrapper pass for external alias analyses. This just squirrels away the 979 /// callback used to run any analyses and register their results. 980 struct ExternalAAWrapperPass : ImmutablePass { 981 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; 982 983 CallbackT CB; 984 985 static char ID; 986 987 ExternalAAWrapperPass(); 988 989 explicit ExternalAAWrapperPass(CallbackT CB); 990 991 void getAnalysisUsage(AnalysisUsage &AU) const override { 992 AU.setPreservesAll(); 993 } 994 }; 995 996 /// A wrapper pass around a callback which can be used to populate the 997 /// AAResults in the AAResultsWrapperPass from an external AA. 998 /// 999 /// The callback provided here will be used each time we prepare an AAResults 1000 /// object, and will receive a reference to the function wrapper pass, the 1001 /// function, and the AAResults object to populate. This should be used when 1002 /// setting up a custom pass pipeline to inject a hook into the AA results. 1003 ImmutablePass *createExternalAAWrapperPass( 1004 std::function<void(Pass &, Function &, AAResults &)> Callback); 1005 1006 } // end namespace llvm 1007 1008 #endif // LLVM_ANALYSIS_ALIASANALYSIS_H 1009