19#include "llvm/Config/llvm-config.h"
40 cl::desc(
"The maximum total number of memory locations alias "
41 "sets may contain before degradation"));
46 assert(!AS.Forward &&
"Alias set is already forwarding!");
47 assert(!Forward &&
"This set is a forwarding set!!");
53 if (Alias == SetMustAlias) {
58 return BatchAA.isMustAlias(MemLoc, ASMemLoc);
65 if (MemoryLocs.empty()) {
69 AS.MemoryLocs.clear();
72 bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
73 if (UnknownInsts.empty()) {
74 if (ASHadUnknownInsts) {
78 }
else if (ASHadUnknownInsts) {
80 AS.UnknownInsts.clear();
86 if (ASHadUnknownInsts)
90void AliasSetTracker::removeAliasSet(
AliasSet *AS) {
93 AS->Forward =
nullptr;
95 TotalAliasSetSize -= AS->
size();
100 if (AS == AliasAnyAS) {
101 AliasAnyAS =
nullptr;
102 assert(AliasSets.empty() &&
"Tracker not empty");
107 assert(RefCount == 0 &&
"Cannot remove non-dead alias set from tracker!");
108 AST.removeAliasSet(
this);
113 bool KnownMustAlias) {
124 MemoryLocs.push_back(MemLoc);
126 AST.TotalAliasSetSize++;
130 if (UnknownInsts.empty())
132 UnknownInsts.emplace_back(
I);
136 using namespace PatternMatch;
137 bool MayWriteMemory =
I->mayWriteToMemory() && !
isGuard(
I) &&
138 !(
I->use_empty() &&
match(
I, m_Intrinsic<Intrinsic::invariant_start>()));
139 if (!MayWriteMemory) {
147 Access = ModRefAccess;
160 for (
const auto &ASMemLoc : MemoryLocs) {
184 const auto *C1 = dyn_cast<CallBase>(UnknownInst);
185 const auto *C2 = dyn_cast<CallBase>(Inst);
194 for (
const auto &ASMemLoc : MemoryLocs) {
221AliasSet *AliasSetTracker::mergeAliasSetsForMemoryLocation(
241 MustAliasAll =
false;
278 collapseForwardingIn(MapEntry);
284 bool MustAliasAll =
false;
292 }
else if (
AliasSet *AliasAS = mergeAliasSetsForMemoryLocation(
293 MemLoc, MapEntry, MustAliasAll)) {
298 AliasSets.push_back(AS =
new AliasSet());
303 AS->addMemoryLocation(*
this, MemLoc, MustAliasAll);
307 collapseForwardingIn(MapEntry);
308 assert(MapEntry == AS &&
"Memory locations with same pointer value cannot "
309 "be in different alias sets");
318 addMemoryLocation(Loc, AliasSet::NoAccess);
347 if (isa<DbgInfoIntrinsic>(Inst))
350 if (
auto *II = dyn_cast<IntrinsicInst>(Inst)) {
353 switch (II->getIntrinsicID()) {
357 case Intrinsic::assume:
358 case Intrinsic::experimental_noalias_scope_decl:
359 case Intrinsic::sideeffect:
360 case Intrinsic::pseudoprobe:
367 if (
AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
368 AS->addUnknownInst(Inst, AA);
371 AliasSets.push_back(
new AliasSet());
372 AliasSets.back().addUnknownInst(Inst, AA);
377 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
389 if (
auto *Call = dyn_cast<CallBase>(
I))
390 if (Call->onlyAccessesArgMemory()) {
393 return AliasSet::ModRefAccess;
395 return AliasSet::ModAccess;
397 return AliasSet::RefAccess;
399 return AliasSet::NoAccess;
407 using namespace PatternMatch;
408 if (Call->use_empty() &&
409 match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
412 for (
auto IdxArgPair :
enumerate(Call->args())) {
413 int ArgIdx = IdxArgPair.index();
414 const Value *Arg = IdxArgPair.value();
422 addMemoryLocation(ArgLoc, getAccessFromModRef(ArgMask));
437 "Merging AliasSetTracker objects with different Alias Analyses!");
452 addMemoryLocation(ASMemLoc, (AliasSet::AccessLattice)AS.Access);
456AliasSet &AliasSetTracker::mergeAllAliasSets() {
458 "Full merge should happen once, when the saturation threshold is "
463 std::vector<AliasSet *> ASVector;
466 ASVector.push_back(&AS);
470 AliasSets.push_back(
new AliasSet());
471 AliasAnyAS = &AliasSets.back();
472 AliasAnyAS->Alias = AliasSet::SetMayAlias;
473 AliasAnyAS->Access = AliasSet::ModRefAccess;
474 AliasAnyAS->AliasAny =
true;
476 for (
auto *Cur : ASVector) {
480 Cur->Forward = AliasAnyAS;
481 AliasAnyAS->addRef();
482 FwdTo->dropRef(*
this);
494 AliasSet::AccessLattice
E) {
501 return mergeAllAliasSets();
512 OS <<
" AliasSet[" << (
const void*)
this <<
", " << RefCount <<
"] ";
513 OS << (Alias == SetMustAlias ?
"must" :
"may") <<
" alias, ";
515 case NoAccess:
OS <<
"No access ";
break;
516 case RefAccess:
OS <<
"Ref ";
break;
517 case ModAccess:
OS <<
"Mod ";
break;
518 case ModRefAccess:
OS <<
"Mod/Ref ";
break;
522 OS <<
" forwarding to " << (
void*)Forward;
524 if (!MemoryLocs.empty()) {
526 OS <<
"Memory locations: ";
531 OS <<
", unknown after)";
533 OS <<
", unknown before-or-after)";
535 OS <<
", " << MemLoc.
Size <<
")";
538 if (!UnknownInsts.empty()) {
540 OS <<
"\n " << UnknownInsts.size() <<
" Unknown instructions: ";
544 I->printAsOperand(
OS);
553 OS <<
"Alias Set Tracker: " << AliasSets.size();
555 OS <<
" (Saturated)";
556 OS <<
" alias sets for " << PointerMap.
size() <<
" pointer values.\n";
562#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
578 OS <<
"Alias sets for function '" <<
F.getName() <<
"':\n";
unsigned const MachineRegisterInfo * MRI
static cl::opt< unsigned > SaturationThreshold("alias-set-saturation-threshold", cl::Hidden, cl::init(250), cl::desc("The maximum total number of memory locations alias " "sets may contain before degradation"))
Expand Atomic instructions
Atomic ordering constants.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file provides utility analysis objects describing memory locations.
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
A manager for alias analyses.
The possible results of an alias query.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ MustAlias
The two locations precisely alias each other.
BatchAAResults & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)
Return the alias set which contains the specified memory location.
void addUnknown(Instruction *I)
void print(raw_ostream &OS) const
void add(const MemoryLocation &Loc)
These methods are used to add different types of instructions to the alias sets.
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, BatchAAResults &BatchAA)
Merge the specified alias set into this alias set.
void print(raw_ostream &OS) const
ModRefInfo aliasesUnknownInst(const Instruction *Inst, BatchAAResults &AA) const
AliasResult aliasesMemoryLocation(const MemoryLocation &MemLoc, BatchAAResults &AA) const
If the specified memory location "may" (or must) alias one of the members in the set return the appro...
PointerVector getPointers() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
AliasSetsPrinterPass(raw_ostream &OS)
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents any memset intrinsic.
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)
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
MemoryEffects getMemoryEffects(const CallBase *Call)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
An instruction for reading from memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
static constexpr LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
static constexpr LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
const Value * Ptr
The address of the start of the location.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Vector takeVector()
Clear the SetVector and return the underlying vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
bool isPointerTy() const
True if this is an instance of PointerType.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool match(Val *V, const Pattern &P)
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
bool isStrongerThanMonotonic(AtomicOrdering AO)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool isModSet(const ModRefInfo MRI)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isModOrRefSet(const ModRefInfo MRI)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ Ref
The access may reference the value stored in memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
bool isModAndRefSet(const ModRefInfo MRI)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool isNoModRef(const ModRefInfo MRI)
bool isRefSet(const ModRefInfo MRI)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.