37#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
38#define LLVM_ANALYSIS_ALIASANALYSIS_H
56class AtomicCmpXchgInst;
64class PreservedAnalyses;
65class TargetLibraryInfo;
67template <
typename>
class SmallPtrSetImpl;
84 static const int OffsetBits = 23;
85 static const int AliasBits = 8;
86 static_assert(AliasBits + 1 + OffsetBits <= 32,
87 "AliasResult size is intended to be 4 bytes!");
89 unsigned int Alias : AliasBits;
90 unsigned int HasOffset : 1;
91 signed int Offset : OffsetBits;
109 static_assert(
MustAlias < (1 << AliasBits),
110 "Not enough bit field size for the enum!");
114 : Alias(Alias), HasOffset(
false), Offset(0) {}
116 operator Kind()
const {
return static_cast<Kind>(Alias); }
119 return Alias ==
Other.Alias && HasOffset ==
Other.HasOffset &&
120 Offset ==
Other.Offset;
129 assert(HasOffset &&
"No offset!");
133 if (isInt<OffsetBits>(NewOffset)) {
140 void swap(
bool DoSwap =
true) {
146static_assert(
sizeof(AliasResult) == 4,
147 "AliasResult size is intended to be 4 bytes!");
150raw_ostream &
operator<<(raw_ostream &
OS, AliasResult AR);
192 : DT(DT), LI(LI), EphValues(EphValues) {}
243 using LocPair = std::pair<AACacheLoc, AACacheLoc>;
311 template <
typename AAResultT>
void addAAResult(AAResultT &AAResult) {
315 AAs.emplace_back(
new Model<AAResultT>(AAResult, *
this));
409 bool IgnoreLocals =
false);
497 const std::optional<MemoryLocation> &OptLoc) {
565 bool OrLocal =
false);
567 bool IgnoreLocals =
false);
591 const std::optional<MemoryLocation> &OptLoc,
601 template <
typename T>
class Model;
607 std::vector<std::unique_ptr<Concept>> AAs;
609 std::vector<AnalysisKey *> AADeps;
630 return AA.
alias(LocA, LocB, AAQI);
636 bool IgnoreLocals =
false) {
640 const std::optional<MemoryLocation> &OptLoc) {
712 bool IgnoreLocals) = 0;
720 unsigned ArgIdx) = 0;
750template <
typename AAResultT>
class AAResults::Model final :
public Concept {
754 explicit Model(AAResultT &Result,
AAResults &AAR) : Result(Result) {}
755 ~Model()
override =
default;
759 return Result.alias(LocA, LocB, AAQI, CtxI);
762 ModRefInfo getModRefInfoMask(
const MemoryLocation &Loc, AAQueryInfo &AAQI,
763 bool IgnoreLocals)
override {
764 return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals);
767 ModRefInfo getArgModRefInfo(
const CallBase *Call,
unsigned ArgIdx)
override {
768 return Result.getArgModRefInfo(Call, ArgIdx);
772 AAQueryInfo &AAQI)
override {
773 return Result.getMemoryEffects(Call, AAQI);
777 return Result.getMemoryEffects(
F);
780 ModRefInfo getModRefInfo(
const CallBase *Call,
const MemoryLocation &Loc,
781 AAQueryInfo &AAQI)
override {
782 return Result.getModRefInfo(Call, Loc, AAQI);
785 ModRefInfo getModRefInfo(
const CallBase *Call1,
const CallBase *Call2,
786 AAQueryInfo &AAQI)
override {
787 return Result.getModRefInfo(Call1, Call2, AAQI);
874 bool &RequiresNoCaptureBeforeUnwind);
906 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
911 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
925 template <
typename AnalysisT>
926 static void getFunctionAAResultImpl(
Function &
F,
933 template <
typename AnalysisT>
935 AAResults &AAResults) {
938 MAMProxy.template getCachedResult<AnalysisT>(*
F.getParent())) {
939 AAResults.addAAResult(*R);
941 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
949 std::unique_ptr<AAResults> AAR;
This file defines the DenseMap class.
This file provides utility analysis objects describing memory locations.
This header defines various interfaces for pass management in LLVM.
static cl::opt< RegAllocEvictionAdvisorAnalysis::AdvisorMode > Mode("regalloc-enable-advisor", cl::Hidden, cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default), cl::desc("Enable regalloc advisor mode"), cl::values(clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default, "default", "Default"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release, "release", "precompiled"), clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development, "development", "for training")))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallVector class.
A manager for alias analyses.
void registerFunctionAnalysis()
Register a specific AA result.
Result run(Function &F, FunctionAnalysisManager &AM)
void registerModuleAnalysis()
Register a specific AA result.
This class stores info we want to provide to or retain within an alias query.
SmallVector< AAQueryInfo::LocPair, 4 > AssumptionBasedResults
Location pairs for which an assumption based result is currently stored.
unsigned Depth
Query depth used to distinguish recursive queries.
int NumAssumptionUses
How many active NoAlias assumption uses there are.
std::pair< AACacheLoc, AACacheLoc > LocPair
AAQueryInfo(AAResults &AAR, CaptureInfo *CI)
bool MayBeCrossIteration
Tracks whether the accesses may be on different cycle iterations.
A base class to help implement the function alias analysis results concept.
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI)
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals)
MemoryEffects getMemoryEffects(const Function *F)
AAResultBase(const AAResultBase &Arg)
AAResultBase(AAResultBase &&Arg)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *I)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
const AAResults & getAAResults() const
bool runOnFunction(Function &F) override
Run the wrapper pass to rebuild an aggregation over known AA passes.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
AAResults & getAAResults()
A private abstract base class describing the concept of an individual alias analysis implementation.
virtual AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)=0
The main low level interface to the alias analysis implementation.
virtual MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)=0
Return the behavior of the given call site.
virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI)=0
Return information about whether two call sites may refer to the same set of memory locations.
virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals)=0
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
virtual ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)=0
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
virtual ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)=0
Get the ModRef info associated with a pointer argument of a callsite.
virtual MemoryEffects getMemoryEffects(const Function *F)=0
Return the behavior when calling the given function.
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const Value *Ptr, LocationSize Size, const ModRefInfo Mode)
A convenience wrapper synthesizing a memory location.
bool pointsToConstantMemory(const Value *P, bool OrLocal=false)
A convenience wrapper around the primary pointsToConstantMemory interface.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
Checks whether the given location points to constant memory, or if OrLocal is true whether it points ...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal=false)
bool doesNotAccessMemory(const Function *F)
Checks if the specified function is known to never read or write memory.
AliasResult alias(const Value *V1, const Value *V2)
A convenience wrapper around the primary alias interface.
AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, LocationSize V2Size)
A convenience wrapper around the primary alias interface.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, LocationSize V2Size)
A convenience wrapper around the isNoAlias helper interface.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
ModRefInfo getModRefInfo(const Instruction *I, const Value *P, LocationSize Size)
A convenience wrapper for constructing the memory location.
bool canBasicBlockModify(const BasicBlock &BB, const Value *P, LocationSize Size)
A convenience wrapper synthesizing a memory location.
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
bool isNoAlias(const Value *V1, const Value *V2)
A convenience wrapper around the isNoAlias helper interface.
bool onlyReadsMemory(const Function *F)
Checks if the specified function is known to only read from non-volatile memory (or not access memory...
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Return information about whether a particular call site modifies or reads the specified memory locati...
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
ModRefInfo getModRefInfoMask(const Value *P, bool IgnoreLocals=false)
A convenience wrapper around the primary getModRefInfoMask interface.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
AAResults(const TargetLibraryInfo &TLI)
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)
Check if it is possible for the execution of the specified instructions to mod(according to the mode)...
bool isMustAlias(const Value *V1, const Value *V2)
A convenience wrapper around the isMustAlias helper interface.
void addAAResult(AAResultT &AAResult)
Register a specific AA result.
void addAADependencyID(AnalysisKey *ID)
Register a function analysis ID that the results aggregation depends on.
ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, LocationSize Size, DominatorTree *DT)
A convenience wrapper to synthesize a memory location.
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc.
The possible results of an alias query.
constexpr AliasResult(const Kind &Alias)
bool operator==(const AliasResult &Other) const
bool operator!=(Kind K) const
void swap(bool DoSwap=true)
Helper for processing AliasResult for swapped memory location pairs.
bool operator==(Kind K) const
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
void setOffset(int32_t NewOffset)
bool operator!=(const AliasResult &Other) const
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
An instruction that atomically checks whether a specified value is in a memory location,...
an instruction that atomically reads a memory location, combines it with another value,...
LLVM Basic Block Representation.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
BatchAAResults(AAResults &AAR)
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
BatchAAResults(AAResults &AAR, CaptureInfo *CI)
void enableCrossIterationMode()
Assume that values may come from different cycle iterations.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2)
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal=false)
MemoryEffects getMemoryEffects(const CallBase *Call)
bool isMustAlias(const Value *V1, const Value *V2)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Context-sensitive CaptureInfo provider, which computes and caches the earliest common dominator closu...
bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I) override
EarliestEscapeInfo(DominatorTree &DT, const LoopInfo &LI, const SmallPtrSetImpl< const Value * > &EphValues)
void removeInstruction(Instruction *I)
An instruction for ordering other memory operations.
FunctionPass class - This class is used to implement most global optimizations.
ImmutablePass class - This class is used to provide information that does not need to be run.
An instruction for reading from memory.
static LocationSize precise(uint64_t Value)
bool doesNotAccessMemory() const
Whether this function accesses no memory.
bool onlyReadsMemory() const
Whether this function only (at most) reads memory.
static MemoryEffectsBase unknown()
Create MemoryEffectsBase that can read and write any memory.
Representation for a specific memory location.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
Pass interface - Implemented by all 'passes'.
A set of analyses that are preserved following a run of a transformation pass.
AAQueryInfo that uses SimpleCaptureInfo.
SimpleAAQueryInfo(AAResults &AAR)
Context-free CaptureInfo provider, which computes and caches whether an object is captured in the fun...
bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I) override
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Provides information about what library functions are available for the current target.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
MemoryEffectsBase< IRMemLocation > MemoryEffects
Summary of how a function affects memory in the program.
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ ModRef
The access may reference and may modify the value stored in memory.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...
ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)
A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...
bool isNoModRef(const ModRefInfo MRI)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool isWritableObject(const Value *Object)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
Cache key for BasicAA results.
AACacheLoc(const Value *Ptr, LocationSize Size, bool MayBeCrossIteration)
AACacheLoc(PtrTy Ptr, LocationSize Size)
bool isDefinitive() const
Whether this is a definitive (non-assumption) result.
int NumAssumptionUses
Number of times a NoAlias assumption has been used.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Virtual base class for providers of capture information.
virtual bool isNotCapturedBeforeOrAt(const Value *Object, const Instruction *I)=0
static AACacheLoc getEmptyKey()
static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS)
static unsigned getHashValue(const AACacheLoc &Val)
static AACacheLoc getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
A wrapper pass for external alias analyses.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
std::function< void(Pass &, Function &, AAResults &)> CallbackT