Go to the documentation of this file.
17 #include "llvm/Config/llvm-config.h"
39 cl::desc(
"The maximum number of pointers may-alias "
40 "sets may contain before degradation"));
45 assert(!AS.Forward &&
"Alias set is already forwarding!");
46 assert(!Forward &&
"This set is a forwarding set!!");
48 bool WasMustAlias = (Alias == SetMustAlias);
53 if (Alias == SetMustAlias) {
58 PointerRec *L = getSomePointer();
59 PointerRec *R = AS.getSomePointer();
68 if (Alias == SetMayAlias) {
70 AST.TotalMayAliasSetSize +=
size();
71 if (AS.Alias == SetMustAlias)
72 AST.TotalMayAliasSetSize += AS.
size();
75 bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
76 if (UnknownInsts.empty()) {
77 if (ASHadUnknownInsts) {
81 }
else if (ASHadUnknownInsts) {
83 AS.UnknownInsts.clear();
93 *PtrListEnd = AS.PtrList;
94 AS.PtrList->setPrevInList(PtrListEnd);
95 PtrListEnd = AS.PtrListEnd;
98 AS.PtrListEnd = &AS.PtrList;
99 assert(*AS.PtrListEnd ==
nullptr &&
"End of list is not null?");
101 if (ASHadUnknownInsts)
105 void AliasSetTracker::removeAliasSet(
AliasSet *AS) {
108 AS->Forward =
nullptr;
110 if (AS->Alias == AliasSet::SetMayAlias)
111 TotalMayAliasSetSize -= AS->
size();
116 if (AS == AliasAnyAS) {
117 AliasAnyAS =
nullptr;
118 assert(AliasSets.empty() &&
"Tracker not empty");
123 assert(RefCount == 0 &&
"Cannot remove non-dead alias set from tracker!");
124 AST.removeAliasSet(
this);
129 bool KnownMustAlias,
bool SkipSizeUpdate) {
130 assert(!Entry.hasAliasSet() &&
"Entry already in set!");
134 if (PointerRec *
P = getSomePointer()) {
135 if (!KnownMustAlias) {
142 AST.TotalMayAliasSetSize +=
size();
145 }
else if (!SkipSizeUpdate)
146 P->updateSizeAndAAInfo(Size, AAInfo);
149 Entry.setAliasSet(
this);
150 Entry.updateSizeAndAAInfo(Size, AAInfo);
154 assert(*PtrListEnd ==
nullptr &&
"End of list is not null?");
155 *PtrListEnd = &Entry;
156 PtrListEnd = Entry.setPrevInList(PtrListEnd);
157 assert(*PtrListEnd ==
nullptr &&
"End of list is not null?");
161 if (Alias == SetMayAlias)
162 AST.TotalMayAliasSetSize++;
166 if (UnknownInsts.empty())
168 UnknownInsts.emplace_back(
I);
172 using namespace PatternMatch;
173 bool MayWriteMemory =
I->mayWriteToMemory() && !
isGuard(
I) &&
174 !(
I->use_empty() &&
match(
I, m_Intrinsic<Intrinsic::invariant_start>()));
175 if (!MayWriteMemory) {
183 Access = ModRefAccess;
196 if (Alias == SetMustAlias) {
197 assert(UnknownInsts.empty() &&
"Illegal must alias set!");
201 PointerRec *SomePtr = getSomePointer();
202 assert(SomePtr &&
"Empty must-alias set??");
204 SomePtr->getAAInfo()),
219 if (!UnknownInsts.empty()) {
220 for (
unsigned i = 0,
e = UnknownInsts.size();
i !=
e; ++
i)
221 if (
auto *Inst = getUnknownInst(
i))
237 "Instruction must either read or write memory.");
239 for (
unsigned i = 0,
e = UnknownInsts.size();
i !=
e; ++
i) {
240 if (
auto *UnknownInst = getUnknownInst(
i)) {
241 const auto *
C1 = dyn_cast<CallBase>(UnknownInst);
242 const auto *C2 = dyn_cast<CallBase>(Inst);
262 if (!UnknownInsts.empty())
270 "where's the instruction which added this pointer?");
271 if (std::next(
Addr->user_begin()) !=
Addr->user_end())
275 return cast<Instruction>(*(
Addr->user_begin()));
277 if (1 != UnknownInsts.size())
279 return cast<Instruction>(UnknownInsts[0]);
284 for (
auto &
I : PointerMap)
285 I.second->eraseFromList();
297 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(
const Value *Ptr,
300 bool &MustAliasAll) {
312 MustAliasAll =
false;
348 AliasSet::PointerRec &Entry = getEntryFor(Pointer);
356 if (Entry.hasAliasSet()) {
357 Entry.updateSizeAndAAInfo(Size, AAInfo);
358 assert(Entry.getAliasSet(*
this) == AliasAnyAS &&
359 "Entry in saturated AST must belong to only alias set");
361 AliasAnyAS->addPointer(*
this, Entry, Size, AAInfo);
366 bool MustAliasAll =
false;
368 if (Entry.hasAliasSet()) {
374 if (Entry.updateSizeAndAAInfo(Size, AAInfo))
375 mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll);
377 return *Entry.getAliasSet(*this)->getForwardedTarget(*
this);
381 mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll)) {
383 AS->addPointer(*
this, Entry, Size, AAInfo, MustAliasAll);
388 AliasSets.push_back(
new AliasSet());
389 AliasSets.back().addPointer(*
this, Entry, Size, AAInfo,
true);
390 return AliasSets.back();
395 addPointer(
MemoryLocation(Ptr, Size, AAInfo), AliasSet::NoAccess);
400 return addUnknown(LI);
406 return addUnknown(
SI);
424 if (isa<DbgInfoIntrinsic>(Inst))
427 if (
auto *II = dyn_cast<IntrinsicInst>(Inst)) {
430 switch (II->getIntrinsicID()) {
434 case Intrinsic::assume:
435 case Intrinsic::experimental_noalias_scope_decl:
436 case Intrinsic::sideeffect:
437 case Intrinsic::pseudoprobe:
444 if (
AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
445 AS->addUnknownInst(Inst,
AA);
448 AliasSets.push_back(
new AliasSet());
449 AliasSets.back().addUnknownInst(Inst,
AA);
454 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
466 if (
auto *Call = dyn_cast<CallBase>(
I))
467 if (Call->onlyAccessesArgMemory()) {
470 return AliasSet::ModRefAccess;
472 return AliasSet::ModAccess;
474 return AliasSet::RefAccess;
476 return AliasSet::NoAccess;
484 using namespace PatternMatch;
485 if (Call->use_empty() &&
486 match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
489 for (
auto IdxArgPair :
enumerate(Call->args())) {
490 int ArgIdx = IdxArgPair.index();
491 const Value *
Arg = IdxArgPair.value();
492 if (!
Arg->getType()->isPointerTy())
499 addPointer(ArgLoc, getAccessFromModRef(ArgMask));
504 return addUnknown(
I);
514 "Merging AliasSetTracker objects with different Alias Analyses!");
524 for (
unsigned i = 0,
e = AS.UnknownInsts.size();
i !=
e; ++
i)
525 if (
auto *Inst = AS.getUnknownInst(
i))
532 (AliasSet::AccessLattice)AS.Access);
544 if (
I == PointerMap.end())
return;
547 AliasSet::PointerRec *PtrValEnt =
I->second;
548 AliasSet *AS = PtrValEnt->getAliasSet(*
this);
551 PtrValEnt->eraseFromList();
553 if (AS->Alias == AliasSet::SetMayAlias) {
555 TotalMayAliasSetSize--;
572 if (
I == PointerMap.end())
574 assert(
I->second->hasAliasSet() &&
"Dead entry?");
576 AliasSet::PointerRec &Entry = getEntryFor(To);
577 if (Entry.hasAliasSet())
return;
580 I = PointerMap.find_as(
From);
582 AliasSet *AS =
I->second->getAliasSet(*
this);
583 AS->addPointer(*
this, Entry,
I->second->getSize(),
I->second->getAAInfo(),
587 AliasSet &AliasSetTracker::mergeAllAliasSets() {
589 "Full merge should happen once, when the saturation threshold is "
594 std::vector<AliasSet *> ASVector;
597 ASVector.push_back(&AS);
601 AliasSets.push_back(
new AliasSet());
602 AliasAnyAS = &AliasSets.back();
603 AliasAnyAS->Alias = AliasSet::SetMayAlias;
604 AliasAnyAS->Access = AliasSet::ModRefAccess;
605 AliasAnyAS->AliasAny =
true;
607 for (
auto Cur : ASVector) {
611 Cur->Forward = AliasAnyAS;
612 AliasAnyAS->addRef();
613 FwdTo->dropRef(*
this);
618 AliasAnyAS->mergeSetIn(*Cur, *
this);
625 AliasSet::AccessLattice
E) {
632 return mergeAllAliasSets();
643 OS <<
" AliasSet[" << (
const void*)
this <<
", " << RefCount <<
"] ";
644 OS << (Alias == SetMustAlias ?
"must" :
"may") <<
" alias, ";
646 case NoAccess: OS <<
"No access ";
break;
647 case RefAccess: OS <<
"Ref ";
break;
648 case ModAccess: OS <<
"Mod ";
break;
649 case ModRefAccess: OS <<
"Mod/Ref ";
break;
653 OS <<
" forwarding to " << (
void*)Forward;
658 if (
I !=
begin()) OS <<
", ";
659 I.getPointer()->printAsOperand(OS <<
"(");
661 OS <<
", unknown after)";
663 OS <<
", unknown before-or-after)";
665 OS <<
", " <<
I.getSize() <<
")";
668 if (!UnknownInsts.empty()) {
669 OS <<
"\n " << UnknownInsts.size() <<
" Unknown instructions: ";
670 for (
unsigned i = 0,
e = UnknownInsts.size();
i !=
e; ++
i) {
672 if (
auto *
I = getUnknownInst(
i)) {
674 I->printAsOperand(OS);
684 OS <<
"Alias Set Tracker: " << AliasSets.size();
686 OS <<
" (Saturated)";
687 OS <<
" alias sets for " << PointerMap.size() <<
" pointer values.\n";
693 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
702 void AliasSetTracker::ASTCallbackVH::deleted() {
703 assert(AST &&
"ASTCallbackVH called with a null AliasSetTracker!");
708 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(
Value *V) {
715 AliasSetTracker::ASTCallbackVH &
716 AliasSetTracker::ASTCallbackVH::operator=(
Value *V) {
717 return *
this = ASTCallbackVH(V, AST);
740 auto &AAWP = getAnalysis<AAResultsWrapperPass>();
742 errs() <<
"Alias sets for function '" <<
F.getName() <<
"':\n";
745 Tracker.print(
errs());
755 "Alias Set Printer",
false,
true)
766 OS <<
"Alias sets for function '" <<
F.getName() <<
"':\n";
A set of analyses that are preserved following a run of a transformation pass.
void addUnknown(Instruction *I)
A manager for alias analyses.
@ MayAlias
The two locations may or may not alias.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
This is an optimization pass for GlobalISel generic memory operations.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
const Value * Ptr
The address of the start of the location.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
instcombine should handle this C2 when C1
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
void print(raw_ostream &OS) const
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
The possible results of an alias query.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void print(raw_ostream &OS) const
LLVM Basic Block Representation.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
print alias Alias Set Printer
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
bool match(Val *V, const Pattern &P)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This class implements an extremely fast bulk output stream that can only output to a stream.
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
LLVM_NODISCARD ModRefInfo clearMod(const ModRefInfo MRI)
inst_range instructions(Function *F)
An instruction for storing to memory.
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
initializer< Ty > init(const Ty &Val)
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...
AAResults & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
StandardInstrumentations SI(Debug, VerifyEach)
AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)
Return the alias set which contains the specified memory location.
Define an iterator for alias sets... this is just a forward iterator.
AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo, AAResults &AA) const
If the specified pointer "may" (or must) alias one of the members in the set return the appropriate A...
void copyValue(Value *From, Value *To)
This method should be used whenever a preexisting value in the program is copied or cloned,...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ NoAlias
The two locations do not alias at all.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
@ MustAlias
The two locations precisely alias each other.
static cl::opt< unsigned > SaturationThreshold("alias-set-saturation-threshold", cl::Hidden, cl::init(250), cl::desc("The maximum number of pointers may-alias " "sets may contain before degradation"))
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
An instruction for reading from memory.
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
unsigned const MachineRegisterInfo * MRI
void initializeAliasSetPrinterPass(PassRegistry &)
static bool runOnFunction(Function &F, bool PostInlining)
void setPreservesAll()
Set by analyses that do not transform their input at all.
This class represents any memset intrinsic.
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Value handle with callbacks on RAUW and destruction.
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bool isStrongerThanMonotonic(AtomicOrdering AO)
Instruction * getUniqueInstruction()
If this alias set is known to contain a single instruction and only a single unique instruction,...
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
AnalysisUsage & addRequired()
BlockVerifier::State From
INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", "Alias Set Printer", false, true) INITIALIZE_PASS_END(AliasSetPrinter
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
LLVM Value Representation.
Representation for a specific memory location.
bool aliasesUnknownInst(const Instruction *Inst, AAResults &AA) const