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)) {
348 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address &&
349 V ==
II->getArgOperand(0)) {
350 if (AnalyzeUsesOfPointer(
II, Readers, Writers))
357 if (
Call->isDataOperand(&U)) {
359 if (
Call->isArgOperand(&U) &&
362 Writers->
insert(
Call->getParent()->getParent());
367 auto *
F =
Call->getCalledFunction();
372 if (!
F || !
F->isDeclaration())
378 if (!
Call->hasFnAttr(Attribute::NoCallback) ||
379 !
Call->isArgOperand(&U) ||
380 !
Call->doesNotCapture(
Call->getArgOperandNo(&U)))
386 Readers->
insert(
Call->getParent()->getParent());
388 Writers->
insert(
Call->getParent()->getParent());
391 }
else if (
ICmpInst *ICI = dyn_cast<ICmpInst>(
I)) {
392 if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
394 }
else if (
Constant *
C = dyn_cast<Constant>(
I)) {
396 if (isa<GlobalValue>(
C) ||
C->isConstantUsed())
413bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(
GlobalVariable *GV) {
416 std::vector<Value *> AllocRelatedValues;
420 if (!
C->isNullValue())
426 if (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
430 if (AnalyzeUsesOfPointer(LI))
433 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
435 if (
SI->getOperand(0) == GV)
439 if (isa<ConstantPointerNull>(
SI->getOperand(0)))
450 if (AnalyzeUsesOfPointer(
Ptr,
nullptr,
nullptr,
455 AllocRelatedValues.push_back(
Ptr);
464 while (!AllocRelatedValues.empty()) {
465 AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
466 Handles.emplace_front(*
this, AllocRelatedValues.back());
467 Handles.front().I = Handles.begin();
468 AllocRelatedValues.pop_back();
470 IndirectGlobals.insert(GV);
471 Handles.emplace_front(*
this, GV);
472 Handles.front().I = Handles.begin();
476void GlobalsAAResult::CollectSCCMembership(
CallGraph &CG) {
481 const std::vector<CallGraphNode *> &
SCC = *
I;
482 assert(!
SCC.empty() &&
"SCC with no functions?");
484 for (
auto *CGN : SCC)
486 FunctionToSCCMap[
F] = SCCID;
499 const std::vector<CallGraphNode *> &
SCC = *
I;
500 assert(!
SCC.empty() &&
"SCC with no functions?");
504 if (!
F || !
F->isDefinitionExact()) {
508 for (
auto *
Node : SCC)
509 FunctionInfos.erase(
Node->getFunction());
513 FunctionInfo &FI = FunctionInfos[
F];
514 Handles.emplace_front(*
this,
F);
515 Handles.front().I = Handles.begin();
516 bool KnowNothing =
false;
525 auto MaySyncOrCallIntoModule = [](
const Function &
F) {
526 return !
F.isDeclaration() || !
F.hasNoSync() ||
527 !
F.hasFnAttribute(Attribute::NoCallback);
532 for (
unsigned i = 0, e =
SCC.size(); i !=
e && !KnowNothing; ++i) {
538 if (
F->isDeclaration() ||
F->hasOptNone()) {
540 if (
F->doesNotAccessMemory()) {
542 }
else if (
F->onlyReadsMemory()) {
544 if (!
F->onlyAccessesArgMemory() && MaySyncOrCallIntoModule(*
F))
547 FI.setMayReadAnyGlobal();
550 if (!
F->onlyAccessesArgMemory())
551 FI.setMayReadAnyGlobal();
552 if (MaySyncOrCallIntoModule(*
F)) {
561 CI != E && !KnowNothing; ++CI)
563 if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
565 FI.addFunctionInfo(*CalleeFI);
581 for (
auto *
Node : SCC)
582 FunctionInfos.erase(
Node->getFunction());
587 for (
auto *
Node : SCC) {
594 if (
Node->getFunction()->hasOptNone())
603 if (isa<CallBase>(&
I))
608 if (
I.mayReadFromMemory())
610 if (
I.mayWriteToMemory())
616 ++NumReadMemFunctions;
624 FunctionInfo CachedFI = FI;
625 for (
unsigned i = 1, e =
SCC.size(); i !=
e; ++i)
644 if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
645 isa<InvokeInst>(Input))
661 if (
auto *LI = dyn_cast<LoadInst>(Input)) {
665 if (
auto *SI = dyn_cast<SelectInst>(Input)) {
674 if (
auto *PN = dyn_cast<PHINode>(Input)) {
675 for (
const Value *
Op : PN->incoming_values()) {
684 }
while (!Inputs.
empty());
715bool GlobalsAAResult::isNonEscapingGlobalNoAlias(
const GlobalValue *GV,
731 if (
auto *InputGV = dyn_cast<GlobalValue>(Input)) {
739 auto *GVar = dyn_cast<GlobalVariable>(GV);
740 auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
741 if (GVar && InputGVar &&
742 !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
743 !GVar->isInterposable() && !InputGVar->isInterposable()) {
744 Type *GVType = GVar->getInitializer()->getType();
745 Type *InputGVType = InputGVar->getInitializer()->getType();
757 if (isa<Argument>(Input) || isa<CallInst>(Input) ||
758 isa<InvokeInst>(Input)) {
772 if (
auto *LI = dyn_cast<LoadInst>(Input)) {
782 if (
auto *SI = dyn_cast<SelectInst>(Input)) {
785 if (Visited.
insert(LHS).second)
787 if (Visited.
insert(RHS).second)
791 if (
auto *PN = dyn_cast<PHINode>(Input)) {
792 for (
const Value *
Op : PN->incoming_values()) {
804 }
while (!Inputs.
empty());
815 return !PAC.preservedWhenStateless();
832 const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
833 const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
837 if (GV1 && !NonAddressTakenGlobals.count(GV1))
839 if (GV2 && !NonAddressTakenGlobals.count(GV2))
844 if (GV1 && GV2 && GV1 != GV2)
851 if ((GV1 || GV2) && GV1 != GV2)
856 if ((GV1 || GV2) && GV1 != GV2) {
858 const Value *UV = GV1 ? UV2 : UV1;
859 if (isNonEscapingGlobalNoAlias(GV, UV))
871 if (
const LoadInst *LI = dyn_cast<LoadInst>(UV1))
872 if (
GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
873 if (IndirectGlobals.count(GV))
875 if (
const LoadInst *LI = dyn_cast<LoadInst>(UV2))
876 if (
const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
877 if (IndirectGlobals.count(GV))
883 GV1 = AllocsForIndirectGlobals.lookup(UV1);
885 GV2 = AllocsForIndirectGlobals.lookup(UV2);
890 if (GV1 && GV2 && GV1 != GV2)
897 if ((GV1 || GV2) && GV1 != GV2)
906 if (Call->doesNotAccessMemory())
913 for (
const auto &
A : Call->args()) {
925 return ConservativeResult;
928 return ConservativeResult;
947 if (
const Function *
F = Call->getCalledFunction())
948 if (NonAddressTakenGlobals.count(GV))
950 Known = FI->getModRefInfoForGlobal(*GV) |
951 getModRefInfoForArgument(Call, GV, AAQI);
956GlobalsAAResult::GlobalsAAResult(
963 NonAddressTakenGlobals(
std::
move(Arg.NonAddressTakenGlobals)),
964 IndirectGlobals(
std::
move(Arg.IndirectGlobals)),
965 AllocsForIndirectGlobals(
std::
move(Arg.AllocsForIndirectGlobals)),
966 FunctionInfos(
std::
move(Arg.FunctionInfos)),
967 Handles(
std::
move(Arg.Handles)) {
969 for (
auto &
H : Handles) {
983 Result.CollectSCCMembership(CG);
986 Result.AnalyzeGlobals(M);
989 Result.AnalyzeCallGraph(CG, M);
1010 G->NonAddressTakenGlobals.clear();
1011 G->UnknownFunctionsWithLocalLinkage =
false;
1012 G->IndirectGlobals.clear();
1013 G->AllocsForIndirectGlobals.clear();
1014 G->FunctionInfos.clear();
1015 G->FunctionToSCCMap.clear();
1017 G->CollectSCCMembership(CG);
1018 G->AnalyzeGlobals(M);
1019 G->AnalyzeCallGraph(CG, M);
1026 "Globals Alias Analysis",
false,
true)
1042 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1045 M, GetTLI, getAnalysis<CallGraphWrapperPass>().getCallGraph())));
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
block Block Frequency Analysis
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
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.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
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...
A wrapper class for inspecting calls to intrinsic functions.
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, pointer casts or llvm.threadlocal....
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 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.
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, const LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
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)