#include "llvm/Transforms/IPO.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/Transforms/Utils/CtorUtils.h"
#include "llvm/Transforms/Utils/GlobalStatus.h"
#include "llvm/Pass.h"
#include <unordered_map>
using namespace llvm;
#define DEBUG_TYPE "globaldce"
STATISTIC(NumAliases , "Number of global aliases removed");
STATISTIC(NumFunctions, "Number of functions removed");
STATISTIC(NumVariables, "Number of global variables removed");
namespace {
struct GlobalDCE : public ModulePass {
static char ID; GlobalDCE() : ModulePass(ID) {
initializeGlobalDCEPass(*PassRegistry::getPassRegistry());
}
bool runOnModule(Module &M) override;
private:
SmallPtrSet<GlobalValue*, 32> AliveGlobals;
SmallPtrSet<Constant *, 8> SeenConstants;
std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
void GlobalIsNeeded(GlobalValue *GV);
void MarkUsedGlobalsAsNeeded(Constant *C);
bool RemoveUnusedGlobalValue(GlobalValue &GV);
};
}
static bool isEmptyFunction(Function *F) {
BasicBlock &Entry = F->getEntryBlock();
if (Entry.size() != 1 || !isa<ReturnInst>(Entry.front()))
return false;
ReturnInst &RI = cast<ReturnInst>(Entry.front());
return RI.getReturnValue() == nullptr;
}
char GlobalDCE::ID = 0;
INITIALIZE_PASS(GlobalDCE, "globaldce",
"Dead Global Elimination", false, false)
ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); }
bool GlobalDCE::runOnModule(Module &M) {
bool Changed = false;
Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
for (Function &F : M)
if (Comdat *C = F.getComdat())
ComdatMembers.insert(std::make_pair(C, &F));
for (GlobalVariable &GV : M.globals())
if (Comdat *C = GV.getComdat())
ComdatMembers.insert(std::make_pair(C, &GV));
for (GlobalAlias &GA : M.aliases())
if (Comdat *C = GA.getComdat())
ComdatMembers.insert(std::make_pair(C, &GA));
for (Function &F : M) {
Changed |= RemoveUnusedGlobalValue(F);
if (!F.isDeclaration() && !F.hasAvailableExternallyLinkage())
if (!F.isDiscardableIfUnused())
GlobalIsNeeded(&F);
}
for (GlobalVariable &GV : M.globals()) {
Changed |= RemoveUnusedGlobalValue(GV);
if (!GV.isDeclaration() && !GV.hasAvailableExternallyLinkage())
if (!GV.isDiscardableIfUnused())
GlobalIsNeeded(&GV);
}
for (GlobalAlias &GA : M.aliases()) {
Changed |= RemoveUnusedGlobalValue(GA);
if (!GA.isDiscardableIfUnused())
GlobalIsNeeded(&GA);
}
std::vector<GlobalVariable *> DeadGlobalVars; for (GlobalVariable &GV : M.globals())
if (!AliveGlobals.count(&GV)) {
DeadGlobalVars.push_back(&GV); if (GV.hasInitializer()) {
Constant *Init = GV.getInitializer();
GV.setInitializer(nullptr);
if (isSafeToDestroyConstant(Init))
Init->destroyConstant();
}
}
std::vector<Function *> DeadFunctions;
for (Function &F : M)
if (!AliveGlobals.count(&F)) {
DeadFunctions.push_back(&F); if (!F.isDeclaration())
F.deleteBody();
}
std::vector<GlobalAlias*> DeadAliases;
for (GlobalAlias &GA : M.aliases())
if (!AliveGlobals.count(&GA)) {
DeadAliases.push_back(&GA);
GA.setAliasee(nullptr);
}
if (!DeadFunctions.empty()) {
for (Function *F : DeadFunctions) {
RemoveUnusedGlobalValue(*F);
M.getFunctionList().erase(F);
}
NumFunctions += DeadFunctions.size();
Changed = true;
}
if (!DeadGlobalVars.empty()) {
for (GlobalVariable *GV : DeadGlobalVars) {
RemoveUnusedGlobalValue(*GV);
M.getGlobalList().erase(GV);
}
NumVariables += DeadGlobalVars.size();
Changed = true;
}
if (!DeadAliases.empty()) {
for (GlobalAlias *GA : DeadAliases) {
RemoveUnusedGlobalValue(*GA);
M.getAliasList().erase(GA);
}
NumAliases += DeadAliases.size();
Changed = true;
}
AliveGlobals.clear();
SeenConstants.clear();
ComdatMembers.clear();
return Changed;
}
void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
if (!AliveGlobals.insert(G).second)
return;
if (Comdat *C = G->getComdat()) {
for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
GlobalIsNeeded(CM.second);
}
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
if (GV->hasInitializer())
MarkUsedGlobalsAsNeeded(GV->getInitializer());
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(G)) {
MarkUsedGlobalsAsNeeded(GA->getAliasee());
} else {
Function *F = cast<Function>(G);
if (F->hasPrefixData())
MarkUsedGlobalsAsNeeded(F->getPrefixData());
if (F->hasPrologueData())
MarkUsedGlobalsAsNeeded(F->getPrologueData());
if (F->hasPersonalityFn())
MarkUsedGlobalsAsNeeded(F->getPersonalityFn());
for (BasicBlock &BB : *F)
for (Instruction &I : BB)
for (Use &U : I.operands())
if (GlobalValue *GV = dyn_cast<GlobalValue>(U))
GlobalIsNeeded(GV);
else if (Constant *C = dyn_cast<Constant>(U))
MarkUsedGlobalsAsNeeded(C);
}
}
void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
return GlobalIsNeeded(GV);
for (Use &U : C->operands()) {
Constant *Op = dyn_cast<Constant>(U);
if (Op && SeenConstants.insert(Op).second)
MarkUsedGlobalsAsNeeded(Op);
}
}
bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) {
if (GV.use_empty())
return false;
GV.removeDeadConstantUsers();
return GV.use_empty();
}