31#define DEBUG_TYPE "globaldce"
35 cl::desc(
"Enable virtual function elimination"));
37STATISTIC(NumAliases ,
"Number of global aliases removed");
38STATISTIC(NumFunctions,
"Number of functions removed");
39STATISTIC(NumIFuncs,
"Number of indirect functions removed");
40STATISTIC(NumVariables,
"Number of global variables removed");
41STATISTIC(NumVFuncs,
"Number of virtual functions removed");
46 if (
F->isDeclaration())
49 for (
auto &
I : Entry) {
50 if (
I.isDebugOrPseudoInst())
52 if (
auto *RI = dyn_cast<ReturnInst>(&
I))
53 return !RI->getReturnValue();
61void GlobalDCEPass::ComputeDependencies(
Value *V,
63 if (
auto *
I = dyn_cast<Instruction>(V)) {
64 Function *Parent =
I->getParent()->getParent();
66 }
else if (
auto *GV = dyn_cast<GlobalValue>(V)) {
68 }
else if (
auto *CE = dyn_cast<Constant>(V)) {
70 auto Where = ConstantDependenciesCache.find(CE);
71 if (Where != ConstantDependenciesCache.end()) {
72 auto const &
K = Where->second;
76 for (
User *CEUser :
CE->users())
77 ComputeDependencies(CEUser, LocalDeps);
83void GlobalDCEPass::UpdateGVDependencies(
GlobalValue &GV) {
86 ComputeDependencies(
User, Deps);
93 if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
98 GVDependencies[GVU].insert(&GV);
105 auto const Ret = AliveGlobals.insert(&GV);
112 for (
auto &&CM :
make_range(ComdatMembers.equal_range(
C))) {
113 MarkLive(*CM.second, Updates);
119void GlobalDCEPass::ScanVTables(
Module &M) {
137 cast<ConstantAsMetadata>(
Type->getOperand(0))->getValue())
146 if (
auto GO = dyn_cast<GlobalObject>(&GV)) {
152 VFESafeVTables.insert(&GV);
160 for (
const auto &VTableInfo : TypeIdMap[TypeId]) {
162 uint64_t VTableOffset = VTableInfo.second;
166 *
Caller->getParent(), VTable);
169 VFESafeVTables.erase(VTable);
173 auto Callee = dyn_cast<Function>(
Ptr->stripPointerCasts());
176 VFESafeVTables.erase(VTable);
181 <<
Callee->getName() <<
"\n");
182 GVDependencies[
Caller].insert(Callee);
186void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(
Module &M) {
190 Function *TypeCheckedLoadRelativeFunc =
193 auto scan = [&](
Function *CheckedLoadFunc) {
194 if (!CheckedLoadFunc)
197 for (
auto *U : CheckedLoadFunc->users()) {
198 auto CI = dyn_cast<CallInst>(U);
202 auto *
Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
203 Value *TypeIdValue = CI->getArgOperand(2);
204 auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->
getMetadata();
207 ScanVTableLoad(CI->getFunction(), TypeId,
Offset->getZExtValue());
211 for (
const auto &VTableInfo : TypeIdMap[TypeId]) {
212 VFESafeVTables.erase(VTableInfo.first);
218 scan(TypeCheckedLoadFunc);
219 scan(TypeCheckedLoadRelativeFunc);
222void GlobalDCEPass::AddVirtualFunctionDependencies(
Module &M) {
230 auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
231 M.getModuleFlag(
"Virtual Function Elim"));
232 if (!Val || Val->isZero())
237 if (VFESafeVTables.empty())
240 ScanTypeCheckedLoadIntrinsics(M);
243 dbgs() <<
"VFE safe vtables:\n";
244 for (
auto *VTable : VFESafeVTables)
250 bool Changed =
false;
267 ComdatMembers.insert(std::make_pair(
C, &
F));
270 ComdatMembers.insert(std::make_pair(
C, &GV));
272 if (
Comdat *
C = GA.getComdat())
273 ComdatMembers.insert(std::make_pair(
C, &GA));
277 AddVirtualFunctionDependencies(M);
281 GO.removeDeadConstantUsers();
285 if (!GO.isDeclaration())
286 if (!GO.isDiscardableIfUnused())
289 UpdateGVDependencies(GO);
294 GA.removeDeadConstantUsers();
296 if (!GA.isDiscardableIfUnused())
299 UpdateGVDependencies(GA);
304 GIF.removeDeadConstantUsers();
306 if (!GIF.isDiscardableIfUnused())
309 UpdateGVDependencies(GIF);
316 while (!NewLiveGVs.empty()) {
318 for (
auto *GVD : GVDependencies[LGV])
319 MarkLive(*GVD, &NewLiveGVs);
327 std::vector<GlobalVariable *> DeadGlobalVars;
329 if (!AliveGlobals.count(&GV)) {
330 DeadGlobalVars.push_back(&GV);
331 if (GV.hasInitializer()) {
333 GV.setInitializer(
nullptr);
335 Init->destroyConstant();
340 std::vector<Function *> DeadFunctions;
342 if (!AliveGlobals.count(&
F)) {
343 DeadFunctions.push_back(&
F);
344 if (!
F.isDeclaration())
349 std::vector<GlobalAlias*> DeadAliases;
351 if (!AliveGlobals.count(&GA)) {
352 DeadAliases.push_back(&GA);
353 GA.setAliasee(
nullptr);
357 std::vector<GlobalIFunc*> DeadIFuncs;
359 if (!AliveGlobals.count(&GIF)) {
360 DeadIFuncs.push_back(&GIF);
361 GIF.setResolver(
nullptr);
366 auto EraseUnusedGlobalValue = [&](
GlobalValue *GV) {
372 NumFunctions += DeadFunctions.size();
374 if (!
F->use_empty()) {
392 EraseUnusedGlobalValue(
F);
395 NumVariables += DeadGlobalVars.size();
397 EraseUnusedGlobalValue(GV);
399 NumAliases += DeadAliases.size();
401 EraseUnusedGlobalValue(GA);
403 NumIFuncs += DeadIFuncs.size();
405 EraseUnusedGlobalValue(GIF);
408 AliveGlobals.clear();
409 ConstantDependenciesCache.clear();
410 GVDependencies.clear();
411 ComdatMembers.clear();
413 VFESafeVTables.clear();
423 OS, MapClassName2PassName);
425 OS <<
"<vfe-linkage-unit-visibility>";
static bool isEmptyFunction(Function *F)
Returns true if F is effectively empty.
static cl::opt< bool > ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::desc("Enable virtual function elimination"))
Module.h This file contains the declarations for the Module class.
ModuleAnalysisManager MAM
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)
A container for analyses that lazily runs them and caches their results.
LLVM Basic Block Representation.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This is an important base class in LLVM.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
@ VCallVisibilityLinkageUnit
@ VCallVisibilityTranslationUnit
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
const Comdat * getComdat() const
void eraseFromParent()
This method unlinks 'this' from the containing module and deletes it.
A Module instance is used to store all the information related to an LLVM module.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
The instances of the Type class are immutable: once they are created, they are never changed.
TypeID
Definitions of all of the base types for the Type system.
LLVM Value Representation.
iterator_range< user_iterator > users()
StringRef getName() const
Return a constant reference to the value's name.
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
bool optimizeGlobalCtorsList(Module &M, function_ref< bool(uint32_t, Function *)> ShouldRemove)
Call "ShouldRemove" for every entry in M's global_ctor list and remove the entries for which it retur...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void replaceRelativePointerUsersWithZero(Constant *C)
Finds the same "relative pointer" pattern as described above, where the target is C,...
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)
Processes a Constant recursively looking into elements of arrays, structs and expressions to find a t...
A CRTP mix-in to automatically provide informational APIs needed for passes.