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