34#define DEBUG_TYPE "globalsmodref-aa"
37 "Number of global vars without address taken");
38STATISTIC(NumNonAddrTakenFunctions,
"Number of functions without address taken");
39STATISTIC(NumNoMemFunctions,
"Number of functions that do not access memory");
40STATISTIC(NumReadMemFunctions,
"Number of functions that only read memory");
41STATISTIC(NumIndirectGlobalVars,
"Number of indirect global objects");
69 struct alignas(8) AlignedMap {
70 AlignedMap() =
default;
71 AlignedMap(
const AlignedMap &Arg) =
default;
76 struct AlignedMapPointerTraits {
77 static inline void *getAsVoidPointer(AlignedMap *
P) {
return P; }
78 static inline AlignedMap *getFromVoidPointer(
void *
P) {
79 return (AlignedMap *)
P;
81 static constexpr int NumLowBitsAvailable = 3;
82 static_assert(
alignof(AlignedMap) >= (1 << NumLowBitsAvailable),
83 "AlignedMap insufficiently aligned to have enough low bits.");
91 enum { MayReadAnyGlobal = 4 };
95 "ModRef and the MayReadAnyGlobal flag bits overlap.");
97 AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
98 "Insufficient low bits to store our flag and ModRef info.");
109 : Info(nullptr, Arg.Info.
getInt()) {
110 if (
const auto *ArgPtr = Arg.Info.
getPointer())
114 : Info(Arg.Info.getPointer(), Arg.Info.
getInt()) {
115 Arg.Info.setPointerAndInt(
nullptr, 0);
120 if (
const auto *RHSPtr =
RHS.Info.getPointer())
127 RHS.Info.setPointerAndInt(
nullptr, 0);
160 auto I =
P->Map.find(&GV);
161 if (
I !=
P->Map.end())
162 GlobalMRI |=
I->second;
176 for (
const auto &
G :
P->Map)
183 P =
new AlignedMap();
186 auto &GlobalMRI =
P->Map[&GV];
206void GlobalsAAResult::DeletionCallbackHandle::deleted() {
207 Value *V = getValPtr();
208 if (
auto *
F = dyn_cast<Function>(V))
209 GAR->FunctionInfos.erase(
F);
212 if (GAR->NonAddressTakenGlobals.erase(GV)) {
215 if (GAR->IndirectGlobals.erase(GV)) {
217 for (
auto I = GAR->AllocsForIndirectGlobals.begin(),
218 E = GAR->AllocsForIndirectGlobals.end();
221 GAR->AllocsForIndirectGlobals.erase(
I);
226 for (
auto &FIPair : GAR->FunctionInfos)
227 FIPair.second.eraseModRefInfoForGlobal(*GV);
232 GAR->AllocsForIndirectGlobals.erase(V);
236 GAR->Handles.erase(
I);
250GlobalsAAResult::getFunctionInfo(
const Function *
F) {
251 auto I = FunctionInfos.find(
F);
252 if (
I != FunctionInfos.end())
261void GlobalsAAResult::AnalyzeGlobals(
Module &M) {
264 if (
F.hasLocalLinkage()) {
265 if (!AnalyzeUsesOfPointer(&
F)) {
267 NonAddressTakenGlobals.insert(&
F);
269 Handles.emplace_front(*
this, &
F);
270 Handles.front().I = Handles.begin();
271 ++NumNonAddrTakenFunctions;
273 UnknownFunctionsWithLocalLinkage =
true;
278 if (GV.hasLocalLinkage()) {
279 if (!AnalyzeUsesOfPointer(&GV, &Readers,
280 GV.isConstant() ?
nullptr : &Writers)) {
282 NonAddressTakenGlobals.insert(&GV);
283 Handles.emplace_front(*
this, &GV);
284 Handles.front().I = Handles.begin();
287 if (TrackedFunctions.
insert(Reader).second) {
288 Handles.emplace_front(*
this, Reader);
289 Handles.front().I = Handles.begin();
294 if (!GV.isConstant())
296 if (TrackedFunctions.
insert(Writer).second) {
297 Handles.emplace_front(*
this, Writer);
298 Handles.front().I = Handles.begin();
302 ++NumNonAddrTakenGlobalVars;
305 if (GV.getValueType()->isPointerTy() &&
306 AnalyzeIndirectGlobalMemory(&GV))
307 ++NumIndirectGlobalVars;
320bool GlobalsAAResult::AnalyzeUsesOfPointer(
Value *V,
324 if (!
V->getType()->isPointerTy())
327 for (
Use &U :
V->uses()) {
329 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
331 Readers->
insert(LI->getParent()->getParent());
332 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
333 if (V ==
SI->getOperand(1)) {
335 Writers->
insert(
SI->getParent()->getParent());
336 }
else if (
SI->getOperand(1) != OkayStoreDest) {
340 if (AnalyzeUsesOfPointer(
I, Readers, Writers))
344 if (AnalyzeUsesOfPointer(
I, Readers, Writers, OkayStoreDest))
346 }
else if (
auto *Call = dyn_cast<CallBase>(
I)) {
349 if (
Call->isDataOperand(&U)) {
351 if (
Call->isArgOperand(&U) &&
354 Writers->
insert(
Call->getParent()->getParent());
359 auto *
F =
Call->getCalledFunction();
364 if (!
F || !
F->isDeclaration())
370 if (!
Call->hasFnAttr(Attribute::NoCallback) ||
371 !
Call->isArgOperand(&U) ||
372 !
Call->doesNotCapture(
Call->getArgOperandNo(&U)))
378 Readers->
insert(
Call->getParent()->getParent());
380 Writers->
insert(
Call->getParent()->getParent());
383 }
else if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I)) {
384 if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
386 }
else if (
Constant *
C = dyn_cast<Constant>(
I)) {
388 if (isa<GlobalValue>(
C) ||
C->isConstantUsed())
405bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(
GlobalVariable *GV) {
408 std::vector<Value *> AllocRelatedValues;
412 if (!
C->isNullValue())
418 if (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
422 if (AnalyzeUsesOfPointer(LI))
425 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
427 if (
SI->getOperand(0) == GV)
431 if (isa<ConstantPointerNull>(
SI->getOperand(0)))
442 if (AnalyzeUsesOfPointer(
Ptr,
nullptr,
nullptr,
447 AllocRelatedValues.push_back(
Ptr);
456 while (!AllocRelatedValues.empty()) {
457 AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
458 Handles.emplace_front(*
this, AllocRelatedValues.back());
459 Handles.front().I = Handles.begin();
460 AllocRelatedValues.pop_back();
462 IndirectGlobals.insert(GV);
463 Handles.emplace_front(*
this, GV);
464 Handles.front().I = Handles.begin();
468void GlobalsAAResult::CollectSCCMembership(
CallGraph &CG) {
473 const std::vector<CallGraphNode *> &
SCC = *
I;
474 assert(!
SCC.empty() &&
"SCC with no functions?");
476 for (
auto *CGN : SCC)
478 FunctionToSCCMap[
F] = SCCID;
491 const std::vector<CallGraphNode *> &
SCC = *
I;
492 assert(!
SCC.empty() &&
"SCC with no functions?");
496 if (!
F || !
F->isDefinitionExact()) {
500 for (
auto *
Node : SCC)
501 FunctionInfos.erase(
Node->getFunction());
505 FunctionInfo &FI = FunctionInfos[
F];
506 Handles.emplace_front(*
this,
F);
507 Handles.front().I = Handles.begin();
508 bool KnowNothing =
false;
517 auto MaySyncOrCallIntoModule = [](
const Function &
F) {
518 return !
F.isDeclaration() || !
F.hasNoSync() ||
519 !
F.hasFnAttribute(Attribute::NoCallback);
524 for (
unsigned i = 0, e =
SCC.size(); i !=
e && !KnowNothing; ++i) {
530 if (
F->isDeclaration() ||
F->hasOptNone()) {
532 if (
F->doesNotAccessMemory()) {
534 }
else if (
F->onlyReadsMemory()) {
536 if (!
F->onlyAccessesArgMemory() && MaySyncOrCallIntoModule(*
F))
539 FI.setMayReadAnyGlobal();
542 if (!
F->onlyAccessesArgMemory())
543 FI.setMayReadAnyGlobal();
544 if (MaySyncOrCallIntoModule(*
F)) {
553 CI !=
E && !KnowNothing; ++CI)
555 if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
557 FI.addFunctionInfo(*CalleeFI);
573 for (
auto *
Node : SCC)
574 FunctionInfos.erase(
Node->getFunction());
579 for (
auto *
Node : SCC) {
586 if (
Node->getFunction()->hasOptNone())
595 if (isa<CallBase>(&
I))
600 if (
I.mayReadFromMemory())
602 if (
I.mayWriteToMemory())
608 ++NumReadMemFunctions;
616 FunctionInfo CachedFI = FI;
617 for (
unsigned i = 1, e =
SCC.size(); i !=
e; ++i)
636 if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
637 isa<InvokeInst>(Input))
653 if (
auto *LI = dyn_cast<LoadInst>(Input)) {
657 if (
auto *SI = dyn_cast<SelectInst>(Input)) {
666 if (
auto *PN = dyn_cast<PHINode>(Input)) {
667 for (
const Value *
Op : PN->incoming_values()) {
676 }
while (!Inputs.
empty());
707bool GlobalsAAResult::isNonEscapingGlobalNoAlias(
const GlobalValue *GV,
723 if (
auto *InputGV = dyn_cast<GlobalValue>(Input)) {
731 auto *GVar = dyn_cast<GlobalVariable>(GV);
732 auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
733 if (GVar && InputGVar &&
734 !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
735 !GVar->isInterposable() && !InputGVar->isInterposable()) {
736 Type *GVType = GVar->getInitializer()->getType();
737 Type *InputGVType = InputGVar->getInitializer()->getType();
749 if (isa<Argument>(Input) || isa<CallInst>(Input) ||
750 isa<InvokeInst>(Input)) {
764 if (
auto *LI = dyn_cast<LoadInst>(Input)) {
774 if (
auto *SI = dyn_cast<SelectInst>(Input)) {
777 if (Visited.
insert(LHS).second)
779 if (Visited.
insert(RHS).second)
783 if (
auto *PN = dyn_cast<PHINode>(Input)) {
784 for (
const Value *
Op : PN->incoming_values()) {
796 }
while (!Inputs.
empty());
807 return !PAC.preservedWhenStateless();
824 const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
825 const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
829 if (GV1 && !NonAddressTakenGlobals.count(GV1))
831 if (GV2 && !NonAddressTakenGlobals.count(GV2))
836 if (GV1 && GV2 && GV1 != GV2)
843 if ((GV1 || GV2) && GV1 != GV2)
848 if ((GV1 || GV2) && GV1 != GV2) {
850 const Value *UV = GV1 ? UV2 : UV1;
851 if (isNonEscapingGlobalNoAlias(GV, UV))
863 if (
const LoadInst *LI = dyn_cast<LoadInst>(UV1))
864 if (
GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
865 if (IndirectGlobals.count(GV))
867 if (
const LoadInst *LI = dyn_cast<LoadInst>(UV2))
868 if (
const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
869 if (IndirectGlobals.count(GV))
875 GV1 = AllocsForIndirectGlobals.lookup(UV1);
877 GV2 = AllocsForIndirectGlobals.lookup(UV2);
882 if (GV1 && GV2 && GV1 != GV2)
889 if ((GV1 || GV2) && GV1 != GV2)
898 if (Call->doesNotAccessMemory())
905 for (
const auto &
A : Call->args()) {
917 return ConservativeResult;
920 return ConservativeResult;
939 if (
const Function *
F = Call->getCalledFunction())
940 if (NonAddressTakenGlobals.count(GV))
942 Known = FI->getModRefInfoForGlobal(*GV) |
943 getModRefInfoForArgument(Call, GV, AAQI);
948GlobalsAAResult::GlobalsAAResult(
955 NonAddressTakenGlobals(
std::
move(Arg.NonAddressTakenGlobals)),
956 IndirectGlobals(
std::
move(Arg.IndirectGlobals)),
957 AllocsForIndirectGlobals(
std::
move(Arg.AllocsForIndirectGlobals)),
958 FunctionInfos(
std::
move(Arg.FunctionInfos)),
959 Handles(
std::
move(Arg.Handles)) {
961 for (
auto &
H : Handles) {
975 Result.CollectSCCMembership(CG);
978 Result.AnalyzeGlobals(M);
981 Result.AnalyzeCallGraph(CG, M);
1002 G->NonAddressTakenGlobals.clear();
1003 G->UnknownFunctionsWithLocalLinkage =
false;
1004 G->IndirectGlobals.clear();
1005 G->AllocsForIndirectGlobals.clear();
1006 G->FunctionInfos.clear();
1007 G->FunctionToSCCMap.clear();
1009 G->CollectSCCMembership(CG);
1010 G->AnalyzeGlobals(M);
1011 G->AnalyzeCallGraph(CG, M);
1018 "Globals Alias Analysis",
false,
true)
1034 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1037 M, GetTLI, getAnalysis<CallGraphWrapperPass>().getCallGraph())));
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
block Block Frequency Analysis
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static Error getInt(StringRef R, IntTy &Result)
Get an unsigned integer, including error checks.
static Function * getFunction(Constant *C)
static cl::opt< bool > EnableUnsafeGlobalsModRefAliasResults("enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden)
static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV, const Value *V, int &Depth, const DataLayout &DL)
This is the interface for a simple mod/ref and alias analysis over globals.
Select target instructions out of generic instructions
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
The mod/ref information collected for a particular function.
FunctionInfo & operator=(FunctionInfo &&RHS)
void eraseModRefInfoForGlobal(const GlobalValue &GV)
Clear a global's ModRef info.
void setMayReadAnyGlobal()
Sets this function as potentially reading from any global.
void addModRefInfo(ModRefInfo NewMRI)
Adds new ModRefInfo for this function to its state.
void addFunctionInfo(const FunctionInfo &FI)
Add mod/ref info from another function into ours, saturating towards ModRef.
ModRefInfo getModRefInfo() const
Returns the ModRefInfo info for this function.
FunctionInfo()=default
Checks to document the invariants of the bit packing here.
FunctionInfo & operator=(const FunctionInfo &RHS)
void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI)
ModRefInfo globalClearMayReadAnyGlobal(int I) const
This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return the corresponding ModRefIn...
bool mayReadAnyGlobal() const
Returns whether this function may read any global variable, and we don't know which global.
FunctionInfo(FunctionInfo &&Arg)
FunctionInfo(const FunctionInfo &Arg)
ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const
Returns the ModRefInfo info for this function w.r.t.
This class stores info we want to provide to or retain within an alias query.
A base class to help implement the function alias analysis results concept.
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.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
An analysis pass to compute the CallGraph for a Module.
A node in the call graph for a module.
std::vector< CallRecord >::iterator iterator
The ModulePass which wraps up a CallGraph and the logic to build it.
The basic data container for the call graph of a Module of IR.
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
const Function & getFunction() const
bool hasLocalLinkage() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
An alias analysis result set for globals.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
bool invalidate(Module &M, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
static GlobalsAAResult analyzeModule(Module &M, std::function< const TargetLibraryInfo &(Function &F)> GetTLI, CallGraph &CG)
MemoryEffects getMemoryEffects(const Function *F)
getMemoryEffects - Return the behavior of the specified function if called from the specified call si...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)
alias - If one of the pointers is to a global that we are tracking, and the other is some random poin...
Legacy wrapper pass to provide the GlobalsAAResult object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Analysis pass providing a never-invalidated alias analysis result.
GlobalsAAResult run(Module &M, ModuleAnalysisManager &AM)
This instruction compares its operands according to the predicate given to the constructor.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
An instruction for reading from 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...
const Value * Ptr
The address of the start of the location.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
A Module instance is used to store all the information related to an LLVM module.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PointerIntPair - This class implements a pair of a pointer and small integer.
void setPointer(PointerTy PtrVal) &
void setInt(IntType IntVal) &
void setPointerAndInt(PointerTy PtrVal, IntType IntVal) &
PointerTy getPointer() const
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.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
iterator_range< user_iterator > users()
const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
ModulePass * createGlobalsAAWrapperPass()
bool isModSet(const ModRefInfo MRI)
MemoryEffectsBase< IRMemLocation > MemoryEffects
Summary of how a function affects memory in the program.
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.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
void initializeGlobalsAAWrapperPassPass(PassRegistry &)
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
bool isModAndRefSet(const ModRefInfo MRI)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Implement std::hash so that hash_code can be used in STL containers.
A special type used by analysis passes to provide an address that identifies that particular analysis...
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)