| //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines the generic AliasAnalysis interface, which is used as the |
| // common interface used by all clients of alias analysis information, and |
| // implemented by all alias analysis implementations. Mod/Ref information is |
| // also captured by this interface. |
| // |
| // Implementations of this interface must implement the various virtual methods, |
| // which automatically provides functionality for the entire suite of client |
| // APIs. |
| // |
| // This API identifies memory regions with the MemoryLocation class. The pointer |
| // component specifies the base memory address of the region. The Size specifies |
| // the maximum size (in address units) of the memory region, or |
| // MemoryLocation::UnknownSize if the size is not known. The TBAA tag |
| // identifies the "type" of the memory reference; see the |
| // TypeBasedAliasAnalysis class for details. |
| // |
| // Some non-obvious details include: |
| // - Pointers that point to two completely different objects in memory never |
| // alias, regardless of the value of the Size component. |
| // - NoAlias doesn't imply inequal pointers. The most obvious example of this |
| // is two pointers to constant memory. Even if they are equal, constant |
| // memory is never stored to, so there will never be any dependencies. |
| // In this and other situations, the pointers may be both NoAlias and |
| // MustAlias at the same time. The current API can only return one result, |
| // though this is rarely a problem in practice. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H |
| #define LLVM_ANALYSIS_ALIASANALYSIS_H |
| |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Analysis/MemoryLocation.h" |
| #include "llvm/IR/PassManager.h" |
| #include "llvm/Pass.h" |
| #include <cstdint> |
| #include <functional> |
| #include <memory> |
| #include <vector> |
| |
| namespace llvm { |
| |
| class AnalysisUsage; |
| class AtomicCmpXchgInst; |
| class BasicAAResult; |
| class BasicBlock; |
| class CatchPadInst; |
| class CatchReturnInst; |
| class DominatorTree; |
| class FenceInst; |
| class Function; |
| class LoopInfo; |
| class PreservedAnalyses; |
| class TargetLibraryInfo; |
| class Value; |
| template <typename> class SmallPtrSetImpl; |
| |
| /// The possible results of an alias query. |
| /// |
| /// These results are always computed between two MemoryLocation objects as |
| /// a query to some alias analysis. |
| /// |
| /// Note that these are unscoped enumerations because we would like to support |
| /// implicitly testing a result for the existence of any possible aliasing with |
| /// a conversion to bool, but an "enum class" doesn't support this. The |
| /// canonical names from the literature are suffixed and unique anyways, and so |
| /// they serve as global constants in LLVM for these results. |
| /// |
| /// See docs/AliasAnalysis.html for more information on the specific meanings |
| /// of these values. |
| class AliasResult { |
| private: |
| static const int OffsetBits = 23; |
| static const int AliasBits = 8; |
| static_assert(AliasBits + 1 + OffsetBits <= 32, |
| "AliasResult size is intended to be 4 bytes!"); |
| |
| unsigned int Alias : AliasBits; |
| unsigned int HasOffset : 1; |
| signed int Offset : OffsetBits; |
| |
| public: |
| enum Kind : uint8_t { |
| /// The two locations do not alias at all. |
| /// |
| /// This value is arranged to convert to false, while all other values |
| /// convert to true. This allows a boolean context to convert the result to |
| /// a binary flag indicating whether there is the possibility of aliasing. |
| NoAlias = 0, |
| /// The two locations may or may not alias. This is the least precise |
| /// result. |
| MayAlias, |
| /// The two locations alias, but only due to a partial overlap. |
| PartialAlias, |
| /// The two locations precisely alias each other. |
| MustAlias, |
| }; |
| static_assert(MustAlias < (1 << AliasBits), |
| "Not enough bit field size for the enum!"); |
| |
| explicit AliasResult() = delete; |
| constexpr AliasResult(const Kind &Alias) |
| : Alias(Alias), HasOffset(false), Offset(0) {} |
| |
| operator Kind() const { return static_cast<Kind>(Alias); } |
| |
| constexpr bool hasOffset() const { return HasOffset; } |
| constexpr int32_t getOffset() const { |
| assert(HasOffset && "No offset!"); |
| return Offset; |
| } |
| void setOffset(int32_t NewOffset) { |
| if (isInt<OffsetBits>(NewOffset)) { |
| HasOffset = true; |
| Offset = NewOffset; |
| } |
| } |
| |
| /// Helper for processing AliasResult for swapped memory location pairs. |
| void swap(bool DoSwap = true) { |
| if (DoSwap && hasOffset()) |
| setOffset(-getOffset()); |
| } |
| }; |
| |
| static_assert(sizeof(AliasResult) == 4, |
| "AliasResult size is intended to be 4 bytes!"); |
| |
| /// << operator for AliasResult. |
| raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); |
| |
| /// Flags indicating whether a memory access modifies or references memory. |
| /// |
| /// This is no access at all, a modification, a reference, or both |
| /// a modification and a reference. These are specifically structured such that |
| /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must' |
| /// work with any of the possible values. |
| enum class ModRefInfo : uint8_t { |
| /// Must is provided for completeness, but no routines will return only |
| /// Must today. See definition of Must below. |
| Must = 0, |
| /// The access may reference the value stored in memory, |
| /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| MustRef = 1, |
| /// The access may modify the value stored in memory, |
| /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| MustMod = 2, |
| /// The access may reference, modify or both the value stored in memory, |
| /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| MustModRef = MustRef | MustMod, |
| /// The access neither references nor modifies the value stored in memory. |
| NoModRef = 4, |
| /// The access may reference the value stored in memory. |
| Ref = NoModRef | MustRef, |
| /// The access may modify the value stored in memory. |
| Mod = NoModRef | MustMod, |
| /// The access may reference and may modify the value stored in memory. |
| ModRef = Ref | Mod, |
| |
| /// About Must: |
| /// Must is set in a best effort manner. |
| /// We usually do not try our best to infer Must, instead it is merely |
| /// another piece of "free" information that is presented when available. |
| /// Must set means there was certainly a MustAlias found. For calls, |
| /// where multiple arguments are checked (argmemonly), this translates to |
| /// only MustAlias or NoAlias was found. |
| /// Must is not set for RAR accesses, even if the two locations must |
| /// alias. The reason is that two read accesses translate to an early return |
| /// of NoModRef. An additional alias check to set Must may be |
| /// expensive. Other cases may also not set Must(e.g. callCapturesBefore). |
| /// We refer to Must being *set* when the most significant bit is *cleared*. |
| /// Conversely we *clear* Must information by *setting* the Must bit to 1. |
| }; |
| |
| LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) { |
| return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
| static_cast<int>(ModRefInfo::Must); |
| } |
| LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { |
| return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef); |
| } |
| LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) { |
| return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
| static_cast<int>(ModRefInfo::MustModRef); |
| } |
| LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { |
| return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod); |
| } |
| LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { |
| return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef); |
| } |
| LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { |
| return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef)); |
| } |
| |
| LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) | |
| static_cast<int>(ModRefInfo::MustMod)); |
| } |
| LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) | |
| static_cast<int>(ModRefInfo::MustRef)); |
| } |
| LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) & |
| static_cast<int>(ModRefInfo::MustModRef)); |
| } |
| LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) | |
| static_cast<int>(ModRefInfo::MustModRef)); |
| } |
| LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref)); |
| } |
| LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod)); |
| } |
| LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { |
| return ModRefInfo(static_cast<int>(MRI) | |
| static_cast<int>(ModRefInfo::NoModRef)); |
| } |
| LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, |
| const ModRefInfo MRI2) { |
| return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2)); |
| } |
| LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1, |
| const ModRefInfo MRI2) { |
| return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2)); |
| } |
| |
| /// The locations at which a function might access memory. |
| /// |
| /// These are primarily used in conjunction with the \c AccessKind bits to |
| /// describe both the nature of access and the locations of access for a |
| /// function call. |
| enum FunctionModRefLocation { |
| /// Base case is no access to memory. |
| FMRL_Nowhere = 0, |
| /// Access to memory via argument pointers. |
| FMRL_ArgumentPointees = 8, |
| /// Memory that is inaccessible via LLVM IR. |
| FMRL_InaccessibleMem = 16, |
| /// Access to any memory. |
| FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees |
| }; |
| |
| /// Summary of how a function affects memory in the program. |
| /// |
| /// Loads from constant globals are not considered memory accesses for this |
| /// interface. Also, functions may freely modify stack space local to their |
| /// invocation without having to report it through these interfaces. |
| enum FunctionModRefBehavior { |
| /// This function does not perform any non-local loads or stores to memory. |
| /// |
| /// This property corresponds to the GCC 'const' attribute. |
| /// This property corresponds to the LLVM IR 'readnone' attribute. |
| /// This property corresponds to the IntrNoMem LLVM intrinsic flag. |
| FMRB_DoesNotAccessMemory = |
| FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef), |
| |
| /// The only memory references in this function (if it has any) are |
| /// non-volatile loads from objects pointed to by its pointer-typed |
| /// arguments, with arbitrary offsets. |
| /// |
| /// This property corresponds to the combination of the IntrReadMem |
| /// and IntrArgMemOnly LLVM intrinsic flags. |
| FMRB_OnlyReadsArgumentPointees = |
| FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref), |
| |
| /// The only memory references in this function (if it has any) are |
| /// non-volatile stores from objects pointed to by its pointer-typed |
| /// arguments, with arbitrary offsets. |
| /// |
| /// This property corresponds to the combination of the IntrWriteMem |
| /// and IntrArgMemOnly LLVM intrinsic flags. |
| FMRB_OnlyWritesArgumentPointees = |
| FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod), |
| |
| /// The only memory references in this function (if it has any) are |
| /// non-volatile loads and stores from objects pointed to by its |
| /// pointer-typed arguments, with arbitrary offsets. |
| /// |
| /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag. |
| FMRB_OnlyAccessesArgumentPointees = |
| FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef), |
| |
| /// The only memory references in this function (if it has any) are |
| /// reads of memory that is otherwise inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
| FMRB_OnlyReadsInaccessibleMem = |
| FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref), |
| |
| /// The only memory references in this function (if it has any) are |
| /// writes to memory that is otherwise inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
| FMRB_OnlyWritesInaccessibleMem = |
| FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod), |
| |
| /// The only memory references in this function (if it has any) are |
| /// references of memory that is otherwise inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
| FMRB_OnlyAccessesInaccessibleMem = |
| FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef), |
| |
| /// The function may perform non-volatile loads from objects pointed |
| /// to by its pointer-typed arguments, with arbitrary offsets, and |
| /// it may also perform loads of memory that is otherwise |
| /// inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR |
| /// inaccessiblemem_or_argmemonly attribute. |
| FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem | |
| FMRL_ArgumentPointees | |
| static_cast<int>(ModRefInfo::Ref), |
| |
| /// The function may perform non-volatile stores to objects pointed |
| /// to by its pointer-typed arguments, with arbitrary offsets, and |
| /// it may also perform stores of memory that is otherwise |
| /// inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR |
| /// inaccessiblemem_or_argmemonly attribute. |
| FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem | |
| FMRL_ArgumentPointees | |
| static_cast<int>(ModRefInfo::Mod), |
| |
| /// The function may perform non-volatile loads and stores of objects |
| /// pointed to by its pointer-typed arguments, with arbitrary offsets, and |
| /// it may also perform loads and stores of memory that is otherwise |
| /// inaccessible via LLVM IR. |
| /// |
| /// This property corresponds to the LLVM IR |
| /// inaccessiblemem_or_argmemonly attribute. |
| FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem | |
| FMRL_ArgumentPointees | |
| static_cast<int>(ModRefInfo::ModRef), |
| |
| /// This function does not perform any non-local stores or volatile loads, |
| /// but may read from any memory location. |
| /// |
| /// This property corresponds to the GCC 'pure' attribute. |
| /// This property corresponds to the LLVM IR 'readonly' attribute. |
| /// This property corresponds to the IntrReadMem LLVM intrinsic flag. |
| FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref), |
| |
| // This function does not read from memory anywhere, but may write to any |
| // memory location. |
| // |
| // This property corresponds to the LLVM IR 'writeonly' attribute. |
| // This property corresponds to the IntrWriteMem LLVM intrinsic flag. |
| FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod), |
| |
| /// This indicates that the function could not be classified into one of the |
| /// behaviors above. |
| FMRB_UnknownModRefBehavior = |
| FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef) |
| }; |
| |
| // Wrapper method strips bits significant only in FunctionModRefBehavior, |
| // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if |
| // ModRefInfo enum changes, the wrapper can be updated to & with the new enum |
| // entry with all bits set to 1. |
| LLVM_NODISCARD inline ModRefInfo |
| createModRefInfo(const FunctionModRefBehavior FMRB) { |
| return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef)); |
| } |
| |
| /// Virtual base class for providers of capture information. |
| struct CaptureInfo { |
| virtual ~CaptureInfo() = 0; |
| virtual bool isNotCapturedBeforeOrAt(const Value *Object, |
| const Instruction *I) = 0; |
| }; |
| |
| /// Context-free CaptureInfo provider, which computes and caches whether an |
| /// object is captured in the function at all, but does not distinguish whether |
| /// it was captured before or after the context instruction. |
| class SimpleCaptureInfo final : public CaptureInfo { |
| SmallDenseMap<const Value *, bool, 8> IsCapturedCache; |
| |
| public: |
| bool isNotCapturedBeforeOrAt(const Value *Object, |
| const Instruction *I) override; |
| }; |
| |
| /// Context-sensitive CaptureInfo provider, which computes and caches the |
| /// earliest common dominator closure of all captures. It provides a good |
| /// approximation to a precise "captures before" analysis. |
| class EarliestEscapeInfo final : public CaptureInfo { |
| DominatorTree &DT; |
| const LoopInfo &LI; |
| |
| /// Map from identified local object to an instruction before which it does |
| /// not escape, or nullptr if it never escapes. The "earliest" instruction |
| /// may be a conservative approximation, e.g. the first instruction in the |
| /// function is always a legal choice. |
| DenseMap<const Value *, Instruction *> EarliestEscapes; |
| |
| /// Reverse map from instruction to the objects it is the earliest escape for. |
| /// This is used for cache invalidation purposes. |
| DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj; |
| |
| const SmallPtrSetImpl<const Value *> &EphValues; |
| |
| public: |
| EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI, |
| const SmallPtrSetImpl<const Value *> &EphValues) |
| : DT(DT), LI(LI), EphValues(EphValues) {} |
| |
| bool isNotCapturedBeforeOrAt(const Value *Object, |
| const Instruction *I) override; |
| |
| void removeInstruction(Instruction *I); |
| }; |
| |
| /// Reduced version of MemoryLocation that only stores a pointer and size. |
| /// Used for caching AATags independent BasicAA results. |
| struct AACacheLoc { |
| const Value *Ptr; |
| LocationSize Size; |
| }; |
| |
| template <> struct DenseMapInfo<AACacheLoc> { |
| static inline AACacheLoc getEmptyKey() { |
| return {DenseMapInfo<const Value *>::getEmptyKey(), |
| DenseMapInfo<LocationSize>::getEmptyKey()}; |
| } |
| static inline AACacheLoc getTombstoneKey() { |
| return {DenseMapInfo<const Value *>::getTombstoneKey(), |
| DenseMapInfo<LocationSize>::getTombstoneKey()}; |
| } |
| static unsigned getHashValue(const AACacheLoc &Val) { |
| return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ |
| DenseMapInfo<LocationSize>::getHashValue(Val.Size); |
| } |
| static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { |
| return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; |
| } |
| }; |
| |
| /// This class stores info we want to provide to or retain within an alias |
| /// query. By default, the root query is stateless and starts with a freshly |
| /// constructed info object. Specific alias analyses can use this query info to |
| /// store per-query state that is important for recursive or nested queries to |
| /// avoid recomputing. To enable preserving this state across multiple queries |
| /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. |
| /// The information stored in an `AAQueryInfo` is currently limitted to the |
| /// caches used by BasicAA, but can further be extended to fit other AA needs. |
| class AAQueryInfo { |
| public: |
| using LocPair = std::pair<AACacheLoc, AACacheLoc>; |
| struct CacheEntry { |
| AliasResult Result; |
| /// Number of times a NoAlias assumption has been used. |
| /// 0 for assumptions that have not been used, -1 for definitive results. |
| int NumAssumptionUses; |
| /// Whether this is a definitive (non-assumption) result. |
| bool isDefinitive() const { return NumAssumptionUses < 0; } |
| }; |
| using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; |
| AliasCacheT AliasCache; |
| |
| CaptureInfo *CI; |
| |
| /// Query depth used to distinguish recursive queries. |
| unsigned Depth = 0; |
| |
| /// How many active NoAlias assumption uses there are. |
| int NumAssumptionUses = 0; |
| |
| /// Location pairs for which an assumption based result is currently stored. |
| /// Used to remove all potentially incorrect results from the cache if an |
| /// assumption is disproven. |
| SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; |
| |
| AAQueryInfo(CaptureInfo *CI) : CI(CI) {} |
| |
| /// Create a new AAQueryInfo based on this one, but with the cache cleared. |
| /// This is used for recursive queries across phis, where cache results may |
| /// not be valid. |
| AAQueryInfo withEmptyCache() { |
| AAQueryInfo NewAAQI(CI); |
| NewAAQI.Depth = Depth; |
| return NewAAQI; |
| } |
| }; |
| |
| /// AAQueryInfo that uses SimpleCaptureInfo. |
| class SimpleAAQueryInfo : public AAQueryInfo { |
| SimpleCaptureInfo CI; |
| |
| public: |
| SimpleAAQueryInfo() : AAQueryInfo(&CI) {} |
| }; |
| |
| class BatchAAResults; |
| |
| class AAResults { |
| public: |
| // Make these results default constructable and movable. We have to spell |
| // these out because MSVC won't synthesize them. |
| AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} |
| AAResults(AAResults &&Arg); |
| ~AAResults(); |
| |
| /// Register a specific AA result. |
| template <typename AAResultT> void addAAResult(AAResultT &AAResult) { |
| // FIXME: We should use a much lighter weight system than the usual |
| // polymorphic pattern because we don't own AAResult. It should |
| // ideally involve two pointers and no separate allocation. |
| AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); |
| } |
| |
| /// Register a function analysis ID that the results aggregation depends on. |
| /// |
| /// This is used in the new pass manager to implement the invalidation logic |
| /// where we must invalidate the results aggregation if any of our component |
| /// analyses become invalid. |
| void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } |
| |
| /// Handle invalidation events in the new pass manager. |
| /// |
| /// The aggregation is invalidated if any of the underlying analyses is |
| /// invalidated. |
| bool invalidate(Function &F, const PreservedAnalyses &PA, |
| FunctionAnalysisManager::Invalidator &Inv); |
| |
| //===--------------------------------------------------------------------===// |
| /// \name Alias Queries |
| /// @{ |
| |
| /// The main low level interface to the alias analysis implementation. |
| /// Returns an AliasResult indicating whether the two pointers are aliased to |
| /// each other. This is the interface that must be implemented by specific |
| /// alias analysis implementations. |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); |
| |
| /// A convenience wrapper around the primary \c alias interface. |
| AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, |
| LocationSize V2Size) { |
| return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
| } |
| |
| /// A convenience wrapper around the primary \c alias interface. |
| AliasResult alias(const Value *V1, const Value *V2) { |
| return alias(MemoryLocation::getBeforeOrAfter(V1), |
| MemoryLocation::getBeforeOrAfter(V2)); |
| } |
| |
| /// A trivial helper function to check to see if the specified pointers are |
| /// no-alias. |
| bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| return alias(LocA, LocB) == AliasResult::NoAlias; |
| } |
| |
| /// A convenience wrapper around the \c isNoAlias helper interface. |
| bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, |
| LocationSize V2Size) { |
| return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
| } |
| |
| /// A convenience wrapper around the \c isNoAlias helper interface. |
| bool isNoAlias(const Value *V1, const Value *V2) { |
| return isNoAlias(MemoryLocation::getBeforeOrAfter(V1), |
| MemoryLocation::getBeforeOrAfter(V2)); |
| } |
| |
| /// A trivial helper function to check to see if the specified pointers are |
| /// must-alias. |
| bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| return alias(LocA, LocB) == AliasResult::MustAlias; |
| } |
| |
| /// A convenience wrapper around the \c isMustAlias helper interface. |
| bool isMustAlias(const Value *V1, const Value *V2) { |
| return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) == |
| AliasResult::MustAlias; |
| } |
| |
| /// Checks whether the given location points to constant memory, or if |
| /// \p OrLocal is true whether it points to a local alloca. |
| bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); |
| |
| /// A convenience wrapper around the primary \c pointsToConstantMemory |
| /// interface. |
| bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { |
| return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal); |
| } |
| |
| /// @} |
| //===--------------------------------------------------------------------===// |
| /// \name Simple mod/ref information |
| /// @{ |
| |
| /// Get the ModRef info associated with a pointer argument of a call. The |
| /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
| /// that these bits do not necessarily account for the overall behavior of |
| /// the function, but rather only provide additional per-argument |
| /// information. This never sets ModRefInfo::Must. |
| ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
| |
| /// Return the behavior of the given call site. |
| FunctionModRefBehavior getModRefBehavior(const CallBase *Call); |
| |
| /// Return the behavior when calling the given function. |
| FunctionModRefBehavior getModRefBehavior(const Function *F); |
| |
| /// Checks if the specified call is known to never read or write memory. |
| /// |
| /// Note that if the call only reads from known-constant memory, it is also |
| /// legal to return true. Also, calls that unwind the stack are legal for |
| /// this predicate. |
| /// |
| /// Many optimizations (such as CSE and LICM) can be performed on such calls |
| /// without worrying about aliasing properties, and many calls have this |
| /// property (e.g. calls to 'sin' and 'cos'). |
| /// |
| /// This property corresponds to the GCC 'const' attribute. |
| bool doesNotAccessMemory(const CallBase *Call) { |
| return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory; |
| } |
| |
| /// Checks if the specified function is known to never read or write memory. |
| /// |
| /// Note that if the function only reads from known-constant memory, it is |
| /// also legal to return true. Also, function that unwind the stack are legal |
| /// for this predicate. |
| /// |
| /// Many optimizations (such as CSE and LICM) can be performed on such calls |
| /// to such functions without worrying about aliasing properties, and many |
| /// functions have this property (e.g. 'sin' and 'cos'). |
| /// |
| /// This property corresponds to the GCC 'const' attribute. |
| bool doesNotAccessMemory(const Function *F) { |
| return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; |
| } |
| |
| /// Checks if the specified call is known to only read from non-volatile |
| /// memory (or not access memory at all). |
| /// |
| /// Calls that unwind the stack are legal for this predicate. |
| /// |
| /// This property allows many common optimizations to be performed in the |
| /// absence of interfering store instructions, such as CSE of strlen calls. |
| /// |
| /// This property corresponds to the GCC 'pure' attribute. |
| bool onlyReadsMemory(const CallBase *Call) { |
| return onlyReadsMemory(getModRefBehavior(Call)); |
| } |
| |
| /// Checks if the specified function is known to only read from non-volatile |
| /// memory (or not access memory at all). |
| /// |
| /// Functions that unwind the stack are legal for this predicate. |
| /// |
| /// This property allows many common optimizations to be performed in the |
| /// absence of interfering store instructions, such as CSE of strlen calls. |
| /// |
| /// This property corresponds to the GCC 'pure' attribute. |
| bool onlyReadsMemory(const Function *F) { |
| return onlyReadsMemory(getModRefBehavior(F)); |
| } |
| |
| /// Checks if functions with the specified behavior are known to only read |
| /// from non-volatile memory (or not access memory at all). |
| static bool onlyReadsMemory(FunctionModRefBehavior MRB) { |
| return !isModSet(createModRefInfo(MRB)); |
| } |
| |
| /// Checks if functions with the specified behavior are known to only write |
| /// memory (or not access memory at all). |
| static bool onlyWritesMemory(FunctionModRefBehavior MRB) { |
| return !isRefSet(createModRefInfo(MRB)); |
| } |
| |
| /// Checks if functions with the specified behavior are known to read and |
| /// write at most from objects pointed to by their pointer-typed arguments |
| /// (with arbitrary offsets). |
| static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { |
| return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); |
| } |
| |
| /// Checks if functions with the specified behavior are known to potentially |
| /// read or write from objects pointed to be their pointer-typed arguments |
| /// (with arbitrary offsets). |
| static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { |
| return isModOrRefSet(createModRefInfo(MRB)) && |
| ((unsigned)MRB & FMRL_ArgumentPointees); |
| } |
| |
| /// Checks if functions with the specified behavior are known to read and |
| /// write at most from memory that is inaccessible from LLVM IR. |
| static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { |
| return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); |
| } |
| |
| /// Checks if functions with the specified behavior are known to potentially |
| /// read or write from memory that is inaccessible from LLVM IR. |
| static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { |
| return isModOrRefSet(createModRefInfo(MRB)) && |
| ((unsigned)MRB & FMRL_InaccessibleMem); |
| } |
| |
| /// Checks if functions with the specified behavior are known to read and |
| /// write at most from memory that is inaccessible from LLVM IR or objects |
| /// pointed to by their pointer-typed arguments (with arbitrary offsets). |
| static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { |
| return !((unsigned)MRB & FMRL_Anywhere & |
| ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); |
| } |
| |
| /// getModRefInfo (for call sites) - Return information about whether |
| /// a particular call site modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for call sites) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const CallBase *Call, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(Call, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for loads) - Return information about whether |
| /// a particular load modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for loads) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(L, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for stores) - Return information about whether |
| /// a particular store modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for stores) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(S, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for fences) - Return information about whether |
| /// a particular store modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for fences) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(S, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for cmpxchges) - Return information about whether |
| /// a particular cmpxchg modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
| const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for cmpxchges) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(CX, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for atomicrmws) - Return information about whether |
| /// a particular atomicrmw modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for atomicrmws) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(RMW, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for va_args) - Return information about whether |
| /// a particular va_arg modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for va_args) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(I, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for catchpads) - Return information about whether |
| /// a particular catchpad modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for catchpads) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(I, MemoryLocation(P, Size)); |
| } |
| |
| /// getModRefInfo (for catchrets) - Return information about whether |
| /// a particular catchret modifies or reads the specified memory location. |
| ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); |
| |
| /// getModRefInfo (for catchrets) - A convenience wrapper. |
| ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(I, MemoryLocation(P, Size)); |
| } |
| |
| /// Check whether or not an instruction may read or write the optionally |
| /// specified memory location. |
| /// |
| /// |
| /// An instruction that doesn't read or write memory may be trivially LICM'd |
| /// for example. |
| /// |
| /// For function calls, this delegates to the alias-analysis specific |
| /// call-site mod-ref behavior queries. Otherwise it delegates to the specific |
| /// helpers above. |
| ModRefInfo getModRefInfo(const Instruction *I, |
| const Optional<MemoryLocation> &OptLoc) { |
| SimpleAAQueryInfo AAQIP; |
| return getModRefInfo(I, OptLoc, AAQIP); |
| } |
| |
| /// A convenience wrapper for constructing the memory location. |
| ModRefInfo getModRefInfo(const Instruction *I, const Value *P, |
| LocationSize Size) { |
| return getModRefInfo(I, MemoryLocation(P, Size)); |
| } |
| |
| /// Return information about whether a call and an instruction may refer to |
| /// the same memory locations. |
| ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call); |
| |
| /// Return information about whether two call sites may refer to the same set |
| /// of memory locations. See the AA documentation for details: |
| /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); |
| |
| /// Return information about whether a particular call site modifies |
| /// or reads the specified memory location \p MemLoc before instruction \p I |
| /// in a BasicBlock. |
| /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being |
| /// set. |
| ModRefInfo callCapturesBefore(const Instruction *I, |
| const MemoryLocation &MemLoc, |
| DominatorTree *DT) { |
| SimpleAAQueryInfo AAQIP; |
| return callCapturesBefore(I, MemLoc, DT, AAQIP); |
| } |
| |
| /// A convenience wrapper to synthesize a memory location. |
| ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, |
| LocationSize Size, DominatorTree *DT) { |
| return callCapturesBefore(I, MemoryLocation(P, Size), DT); |
| } |
| |
| /// @} |
| //===--------------------------------------------------------------------===// |
| /// \name Higher level methods for querying mod/ref information. |
| /// @{ |
| |
| /// Check if it is possible for execution of the specified basic block to |
| /// modify the location Loc. |
| bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); |
| |
| /// A convenience wrapper synthesizing a memory location. |
| bool canBasicBlockModify(const BasicBlock &BB, const Value *P, |
| LocationSize Size) { |
| return canBasicBlockModify(BB, MemoryLocation(P, Size)); |
| } |
| |
| /// Check if it is possible for the execution of the specified instructions |
| /// to mod\ref (according to the mode) the location Loc. |
| /// |
| /// The instructions to consider are all of the instructions in the range of |
| /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. |
| bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
| const MemoryLocation &Loc, |
| const ModRefInfo Mode); |
| |
| /// A convenience wrapper synthesizing a memory location. |
| bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
| const Value *Ptr, LocationSize Size, |
| const ModRefInfo Mode) { |
| return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); |
| } |
| |
| private: |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
| AAQueryInfo &AAQI); |
| bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
| bool OrLocal = false); |
| ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2, |
| AAQueryInfo &AAQIP); |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
| const MemoryLocation &Loc, AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI); |
| ModRefInfo getModRefInfo(const Instruction *I, |
| const Optional<MemoryLocation> &OptLoc, |
| AAQueryInfo &AAQIP); |
| ModRefInfo callCapturesBefore(const Instruction *I, |
| const MemoryLocation &MemLoc, DominatorTree *DT, |
| AAQueryInfo &AAQIP); |
| |
| class Concept; |
| |
| template <typename T> class Model; |
| |
| template <typename T> friend class AAResultBase; |
| |
| const TargetLibraryInfo &TLI; |
| |
| std::vector<std::unique_ptr<Concept>> AAs; |
| |
| std::vector<AnalysisKey *> AADeps; |
| |
| friend class BatchAAResults; |
| }; |
| |
| /// This class is a wrapper over an AAResults, and it is intended to be used |
| /// only when there are no IR changes inbetween queries. BatchAAResults is |
| /// reusing the same `AAQueryInfo` to preserve the state across queries, |
| /// esentially making AA work in "batch mode". The internal state cannot be |
| /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, |
| /// or create a new BatchAAResults. |
| class BatchAAResults { |
| AAResults &AA; |
| AAQueryInfo AAQI; |
| SimpleCaptureInfo SimpleCI; |
| |
| public: |
| BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(&SimpleCI) {} |
| BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(CI) {} |
| |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| return AA.alias(LocA, LocB, AAQI); |
| } |
| bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { |
| return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); |
| } |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { |
| return AA.getModRefInfo(Call, Loc, AAQI); |
| } |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) { |
| return AA.getModRefInfo(Call1, Call2, AAQI); |
| } |
| ModRefInfo getModRefInfo(const Instruction *I, |
| const Optional<MemoryLocation> &OptLoc) { |
| return AA.getModRefInfo(I, OptLoc, AAQI); |
| } |
| ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) { |
| return AA.getModRefInfo(I, Call2, AAQI); |
| } |
| ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
| return AA.getArgModRefInfo(Call, ArgIdx); |
| } |
| FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
| return AA.getModRefBehavior(Call); |
| } |
| bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| return alias(LocA, LocB) == AliasResult::MustAlias; |
| } |
| bool isMustAlias(const Value *V1, const Value *V2) { |
| return alias(MemoryLocation(V1, LocationSize::precise(1)), |
| MemoryLocation(V2, LocationSize::precise(1))) == |
| AliasResult::MustAlias; |
| } |
| ModRefInfo callCapturesBefore(const Instruction *I, |
| const MemoryLocation &MemLoc, |
| DominatorTree *DT) { |
| return AA.callCapturesBefore(I, MemLoc, DT, AAQI); |
| } |
| }; |
| |
| /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis |
| /// pointer or reference. |
| using AliasAnalysis = AAResults; |
| |
| /// A private abstract base class describing the concept of an individual alias |
| /// analysis implementation. |
| /// |
| /// This interface is implemented by any \c Model instantiation. It is also the |
| /// interface which a type used to instantiate the model must provide. |
| /// |
| /// All of these methods model methods by the same name in the \c |
| /// AAResults class. Only differences and specifics to how the |
| /// implementations are called are documented here. |
| class AAResults::Concept { |
| public: |
| virtual ~Concept() = 0; |
| |
| /// An update API used internally by the AAResults to provide |
| /// a handle back to the top level aggregation. |
| virtual void setAAResults(AAResults *NewAAR) = 0; |
| |
| //===--------------------------------------------------------------------===// |
| /// \name Alias Queries |
| /// @{ |
| |
| /// The main low level interface to the alias analysis implementation. |
| /// Returns an AliasResult indicating whether the two pointers are aliased to |
| /// each other. This is the interface that must be implemented by specific |
| /// alias analysis implementations. |
| virtual AliasResult alias(const MemoryLocation &LocA, |
| const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0; |
| |
| /// Checks whether the given location points to constant memory, or if |
| /// \p OrLocal is true whether it points to a local alloca. |
| virtual bool pointsToConstantMemory(const MemoryLocation &Loc, |
| AAQueryInfo &AAQI, bool OrLocal) = 0; |
| |
| /// @} |
| //===--------------------------------------------------------------------===// |
| /// \name Simple mod/ref information |
| /// @{ |
| |
| /// Get the ModRef info associated with a pointer argument of a callsite. The |
| /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
| /// that these bits do not necessarily account for the overall behavior of |
| /// the function, but rather only provide additional per-argument |
| /// information. |
| virtual ModRefInfo getArgModRefInfo(const CallBase *Call, |
| unsigned ArgIdx) = 0; |
| |
| /// Return the behavior of the given call site. |
| virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0; |
| |
| /// Return the behavior when calling the given function. |
| virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; |
| |
| /// getModRefInfo (for call sites) - Return information about whether |
| /// a particular call site modifies or reads the specified memory location. |
| virtual ModRefInfo getModRefInfo(const CallBase *Call, |
| const MemoryLocation &Loc, |
| AAQueryInfo &AAQI) = 0; |
| |
| /// Return information about whether two call sites may refer to the same set |
| /// of memory locations. See the AA documentation for details: |
| /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
| virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
| AAQueryInfo &AAQI) = 0; |
| |
| /// @} |
| }; |
| |
| /// A private class template which derives from \c Concept and wraps some other |
| /// type. |
| /// |
| /// This models the concept by directly forwarding each interface point to the |
| /// wrapped type which must implement a compatible interface. This provides |
| /// a type erased binding. |
| template <typename AAResultT> class AAResults::Model final : public Concept { |
| AAResultT &Result; |
| |
| public: |
| explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { |
| Result.setAAResults(&AAR); |
| } |
| ~Model() override = default; |
| |
| void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } |
| |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
| AAQueryInfo &AAQI) override { |
| return Result.alias(LocA, LocB, AAQI); |
| } |
| |
| bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
| bool OrLocal) override { |
| return Result.pointsToConstantMemory(Loc, AAQI, OrLocal); |
| } |
| |
| ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { |
| return Result.getArgModRefInfo(Call, ArgIdx); |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override { |
| return Result.getModRefBehavior(Call); |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const Function *F) override { |
| return Result.getModRefBehavior(F); |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI) override { |
| return Result.getModRefInfo(Call, Loc, AAQI); |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
| AAQueryInfo &AAQI) override { |
| return Result.getModRefInfo(Call1, Call2, AAQI); |
| } |
| }; |
| |
| /// A CRTP-driven "mixin" base class to help implement the function alias |
| /// analysis results concept. |
| /// |
| /// Because of the nature of many alias analysis implementations, they often |
| /// only implement a subset of the interface. This base class will attempt to |
| /// implement the remaining portions of the interface in terms of simpler forms |
| /// of the interface where possible, and otherwise provide conservatively |
| /// correct fallback implementations. |
| /// |
| /// Implementors of an alias analysis should derive from this CRTP, and then |
| /// override specific methods that they wish to customize. There is no need to |
| /// use virtual anywhere, the CRTP base class does static dispatch to the |
| /// derived type passed into it. |
| template <typename DerivedT> class AAResultBase { |
| // Expose some parts of the interface only to the AAResults::Model |
| // for wrapping. Specifically, this allows the model to call our |
| // setAAResults method without exposing it as a fully public API. |
| friend class AAResults::Model<DerivedT>; |
| |
| /// A pointer to the AAResults object that this AAResult is |
| /// aggregated within. May be null if not aggregated. |
| AAResults *AAR = nullptr; |
| |
| /// Helper to dispatch calls back through the derived type. |
| DerivedT &derived() { return static_cast<DerivedT &>(*this); } |
| |
| /// A setter for the AAResults pointer, which is used to satisfy the |
| /// AAResults::Model contract. |
| void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } |
| |
| protected: |
| /// This proxy class models a common pattern where we delegate to either the |
| /// top-level \c AAResults aggregation if one is registered, or to the |
| /// current result if none are registered. |
| class AAResultsProxy { |
| AAResults *AAR; |
| DerivedT &CurrentResult; |
| |
| public: |
| AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) |
| : AAR(AAR), CurrentResult(CurrentResult) {} |
| |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
| AAQueryInfo &AAQI) { |
| return AAR ? AAR->alias(LocA, LocB, AAQI) |
| : CurrentResult.alias(LocA, LocB, AAQI); |
| } |
| |
| bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
| bool OrLocal) { |
| return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal) |
| : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal); |
| } |
| |
| ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
| return AAR ? AAR->getArgModRefInfo(Call, ArgIdx) |
| : CurrentResult.getArgModRefInfo(Call, ArgIdx); |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
| return AAR ? AAR->getModRefBehavior(Call) |
| : CurrentResult.getModRefBehavior(Call); |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const Function *F) { |
| return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI) { |
| return AAR ? AAR->getModRefInfo(Call, Loc, AAQI) |
| : CurrentResult.getModRefInfo(Call, Loc, AAQI); |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
| AAQueryInfo &AAQI) { |
| return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI) |
| : CurrentResult.getModRefInfo(Call1, Call2, AAQI); |
| } |
| }; |
| |
| explicit AAResultBase() = default; |
| |
| // Provide all the copy and move constructors so that derived types aren't |
| // constrained. |
| AAResultBase(const AAResultBase &Arg) {} |
| AAResultBase(AAResultBase &&Arg) {} |
| |
| /// Get a proxy for the best AA result set to query at this time. |
| /// |
| /// When this result is part of a larger aggregation, this will proxy to that |
| /// aggregation. When this result is used in isolation, it will just delegate |
| /// back to the derived class's implementation. |
| /// |
| /// Note that callers of this need to take considerable care to not cause |
| /// performance problems when they use this routine, in the case of a large |
| /// number of alias analyses being aggregated, it can be expensive to walk |
| /// back across the chain. |
| AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } |
| |
| public: |
| AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
| AAQueryInfo &AAQI) { |
| return AliasResult::MayAlias; |
| } |
| |
| bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
| bool OrLocal) { |
| return false; |
| } |
| |
| ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
| return ModRefInfo::ModRef; |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
| return FMRB_UnknownModRefBehavior; |
| } |
| |
| FunctionModRefBehavior getModRefBehavior(const Function *F) { |
| return FMRB_UnknownModRefBehavior; |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
| AAQueryInfo &AAQI) { |
| return ModRefInfo::ModRef; |
| } |
| |
| ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
| AAQueryInfo &AAQI) { |
| return ModRefInfo::ModRef; |
| } |
| }; |
| |
| /// Return true if this pointer is returned by a noalias function. |
| bool isNoAliasCall(const Value *V); |
| |
| /// Return true if this pointer refers to a distinct and identifiable object. |
| /// This returns true for: |
| /// Global Variables and Functions (but not Global Aliases) |
| /// Allocas |
| /// ByVal and NoAlias Arguments |
| /// NoAlias returns (e.g. calls to malloc) |
| /// |
| bool isIdentifiedObject(const Value *V); |
| |
| /// Return true if V is umabigously identified at the function-level. |
| /// Different IdentifiedFunctionLocals can't alias. |
| /// Further, an IdentifiedFunctionLocal can not alias with any function |
| /// arguments other than itself, which is not necessarily true for |
| /// IdentifiedObjects. |
| bool isIdentifiedFunctionLocal(const Value *V); |
| |
| /// Return true if Object memory is not visible after an unwind, in the sense |
| /// that program semantics cannot depend on Object containing any particular |
| /// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set |
| /// to true, then the memory is only not visible if the object has not been |
| /// captured prior to the unwind. Otherwise it is not visible even if captured. |
| bool isNotVisibleOnUnwind(const Value *Object, |
| bool &RequiresNoCaptureBeforeUnwind); |
| |
| /// A manager for alias analyses. |
| /// |
| /// This class can have analyses registered with it and when run, it will run |
| /// all of them and aggregate their results into single AA results interface |
| /// that dispatches across all of the alias analysis results available. |
| /// |
| /// Note that the order in which analyses are registered is very significant. |
| /// That is the order in which the results will be aggregated and queried. |
| /// |
| /// This manager effectively wraps the AnalysisManager for registering alias |
| /// analyses. When you register your alias analysis with this manager, it will |
| /// ensure the analysis itself is registered with its AnalysisManager. |
| /// |
| /// The result of this analysis is only invalidated if one of the particular |
| /// aggregated AA results end up being invalidated. This removes the need to |
| /// explicitly preserve the results of `AAManager`. Note that analyses should no |
| /// longer be registered once the `AAManager` is run. |
| class AAManager : public AnalysisInfoMixin<AAManager> { |
| public: |
| using Result = AAResults; |
| |
| /// Register a specific AA result. |
| template <typename AnalysisT> void registerFunctionAnalysis() { |
| ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); |
| } |
| |
| /// Register a specific AA result. |
| template <typename AnalysisT> void registerModuleAnalysis() { |
| ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); |
| } |
| |
| Result run(Function &F, FunctionAnalysisManager &AM); |
| |
| private: |
| friend AnalysisInfoMixin<AAManager>; |
| |
| static AnalysisKey Key; |
| |
| SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, |
| AAResults &AAResults), |
| 4> ResultGetters; |
| |
| template <typename AnalysisT> |
| static void getFunctionAAResultImpl(Function &F, |
| FunctionAnalysisManager &AM, |
| AAResults &AAResults) { |
| AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); |
| AAResults.addAADependencyID(AnalysisT::ID()); |
| } |
| |
| template <typename AnalysisT> |
| static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, |
| AAResults &AAResults) { |
| auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); |
| if (auto *R = |
| MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { |
| AAResults.addAAResult(*R); |
| MAMProxy |
| .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); |
| } |
| } |
| }; |
| |
| /// A wrapper pass to provide the legacy pass manager access to a suitably |
| /// prepared AAResults object. |
| class AAResultsWrapperPass : public FunctionPass { |
| std::unique_ptr<AAResults> AAR; |
| |
| public: |
| static char ID; |
| |
| AAResultsWrapperPass(); |
| |
| AAResults &getAAResults() { return *AAR; } |
| const AAResults &getAAResults() const { return *AAR; } |
| |
| bool runOnFunction(Function &F) override; |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override; |
| }; |
| |
| /// A wrapper pass for external alias analyses. This just squirrels away the |
| /// callback used to run any analyses and register their results. |
| struct ExternalAAWrapperPass : ImmutablePass { |
| using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; |
| |
| CallbackT CB; |
| |
| static char ID; |
| |
| ExternalAAWrapperPass(); |
| |
| explicit ExternalAAWrapperPass(CallbackT CB); |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.setPreservesAll(); |
| } |
| }; |
| |
| FunctionPass *createAAResultsWrapperPass(); |
| |
| /// A wrapper pass around a callback which can be used to populate the |
| /// AAResults in the AAResultsWrapperPass from an external AA. |
| /// |
| /// The callback provided here will be used each time we prepare an AAResults |
| /// object, and will receive a reference to the function wrapper pass, the |
| /// function, and the AAResults object to populate. This should be used when |
| /// setting up a custom pass pipeline to inject a hook into the AA results. |
| ImmutablePass *createExternalAAWrapperPass( |
| std::function<void(Pass &, Function &, AAResults &)> Callback); |
| |
| /// A helper for the legacy pass manager to create a \c AAResults |
| /// object populated to the best of our ability for a particular function when |
| /// inside of a \c ModulePass or a \c CallGraphSCCPass. |
| /// |
| /// If a \c ModulePass or a \c CallGraphSCCPass calls \p |
| /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p |
| /// getAnalysisUsage. |
| AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); |
| |
| /// A helper for the legacy pass manager to populate \p AU to add uses to make |
| /// sure the analyses required by \p createLegacyPMAAResults are available. |
| void getAAResultsAnalysisUsage(AnalysisUsage &AU); |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_ANALYSIS_ALIASANALYSIS_H |