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