1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This transform is designed to eliminate unreachable internal globals from the
11 // program. It uses an aggressive algorithm, searching out globals that are
12 // known to be alive. After it finds all of the globals which are needed, it
13 // deletes whatever is left over. This allows it to delete recursive chunks of
14 // the program which are unreachable.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Transforms/IPO/GlobalDCE.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Transforms/IPO.h"
26 #include "llvm/Transforms/Utils/CtorUtils.h"
27 #include "llvm/Transforms/Utils/GlobalStatus.h"
28 #include <unordered_map>
31 #define DEBUG_TYPE "globaldce"
33 STATISTIC(NumAliases , "Number of global aliases removed");
34 STATISTIC(NumFunctions, "Number of functions removed");
35 STATISTIC(NumIFuncs, "Number of indirect functions removed");
36 STATISTIC(NumVariables, "Number of global variables removed");
39 class GlobalDCELegacyPass : public ModulePass {
41 static char ID; // Pass identification, replacement for typeid
42 GlobalDCELegacyPass() : ModulePass(ID) {
43 initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
46 // run - Do the GlobalDCE pass on the specified module, optionally updating
47 // the specified callgraph to reflect the changes.
49 bool runOnModule(Module &M) override {
53 ModuleAnalysisManager DummyMAM;
54 auto PA = Impl.run(M, DummyMAM);
55 return !PA.areAllPreserved();
63 char GlobalDCELegacyPass::ID = 0;
64 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
65 "Dead Global Elimination", false, false)
67 // Public interface to the GlobalDCEPass.
68 ModulePass *llvm::createGlobalDCEPass() {
69 return new GlobalDCELegacyPass();
72 /// Returns true if F contains only a single "ret" instruction.
73 static bool isEmptyFunction(Function *F) {
74 BasicBlock &Entry = F->getEntryBlock();
75 if (Entry.size() != 1 || !isa<ReturnInst>(Entry.front()))
77 ReturnInst &RI = cast<ReturnInst>(Entry.front());
78 return RI.getReturnValue() == nullptr;
81 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &) {
84 // Remove empty functions from the global ctors list.
85 Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
87 // Collect the set of members for each comdat.
89 if (Comdat *C = F.getComdat())
90 ComdatMembers.insert(std::make_pair(C, &F));
91 for (GlobalVariable &GV : M.globals())
92 if (Comdat *C = GV.getComdat())
93 ComdatMembers.insert(std::make_pair(C, &GV));
94 for (GlobalAlias &GA : M.aliases())
95 if (Comdat *C = GA.getComdat())
96 ComdatMembers.insert(std::make_pair(C, &GA));
98 // Loop over the module, adding globals which are obviously necessary.
99 for (GlobalObject &GO : M.global_objects()) {
100 Changed |= RemoveUnusedGlobalValue(GO);
101 // Functions with external linkage are needed if they have a body.
102 // Externally visible & appending globals are needed, if they have an
104 if (!GO.isDeclaration() && !GO.hasAvailableExternallyLinkage())
105 if (!GO.isDiscardableIfUnused())
109 for (GlobalAlias &GA : M.aliases()) {
110 Changed |= RemoveUnusedGlobalValue(GA);
111 // Externally visible aliases are needed.
112 if (!GA.isDiscardableIfUnused())
116 for (GlobalIFunc &GIF : M.ifuncs()) {
117 Changed |= RemoveUnusedGlobalValue(GIF);
118 // Externally visible ifuncs are needed.
119 if (!GIF.isDiscardableIfUnused())
120 GlobalIsNeeded(&GIF);
123 // Now that all globals which are needed are in the AliveGlobals set, we loop
124 // through the program, deleting those which are not alive.
127 // The first pass is to drop initializers of global variables which are dead.
128 std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
129 for (GlobalVariable &GV : M.globals())
130 if (!AliveGlobals.count(&GV)) {
131 DeadGlobalVars.push_back(&GV); // Keep track of dead globals
132 if (GV.hasInitializer()) {
133 Constant *Init = GV.getInitializer();
134 GV.setInitializer(nullptr);
135 if (isSafeToDestroyConstant(Init))
136 Init->destroyConstant();
140 // The second pass drops the bodies of functions which are dead...
141 std::vector<Function *> DeadFunctions;
142 for (Function &F : M)
143 if (!AliveGlobals.count(&F)) {
144 DeadFunctions.push_back(&F); // Keep track of dead globals
145 if (!F.isDeclaration())
149 // The third pass drops targets of aliases which are dead...
150 std::vector<GlobalAlias*> DeadAliases;
151 for (GlobalAlias &GA : M.aliases())
152 if (!AliveGlobals.count(&GA)) {
153 DeadAliases.push_back(&GA);
154 GA.setAliasee(nullptr);
157 // The third pass drops targets of ifuncs which are dead...
158 std::vector<GlobalIFunc*> DeadIFuncs;
159 for (GlobalIFunc &GIF : M.ifuncs())
160 if (!AliveGlobals.count(&GIF)) {
161 DeadIFuncs.push_back(&GIF);
162 GIF.setResolver(nullptr);
165 // Now that all interferences have been dropped, delete the actual objects
167 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
168 RemoveUnusedGlobalValue(*GV);
169 GV->eraseFromParent();
173 NumFunctions += DeadFunctions.size();
174 for (Function *F : DeadFunctions)
175 EraseUnusedGlobalValue(F);
177 NumVariables += DeadGlobalVars.size();
178 for (GlobalVariable *GV : DeadGlobalVars)
179 EraseUnusedGlobalValue(GV);
181 NumAliases += DeadAliases.size();
182 for (GlobalAlias *GA : DeadAliases)
183 EraseUnusedGlobalValue(GA);
185 NumIFuncs += DeadIFuncs.size();
186 for (GlobalIFunc *GIF : DeadIFuncs)
187 EraseUnusedGlobalValue(GIF);
189 // Make sure that all memory is released
190 AliveGlobals.clear();
191 SeenConstants.clear();
192 ComdatMembers.clear();
195 return PreservedAnalyses::none();
196 return PreservedAnalyses::all();
199 /// GlobalIsNeeded - the specific global value as needed, and
200 /// recursively mark anything that it uses as also needed.
201 void GlobalDCEPass::GlobalIsNeeded(GlobalValue *G) {
202 // If the global is already in the set, no need to reprocess it.
203 if (!AliveGlobals.insert(G).second)
206 if (Comdat *C = G->getComdat()) {
207 for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
208 GlobalIsNeeded(CM.second);
211 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
212 // If this is a global variable, we must make sure to add any global values
213 // referenced by the initializer to the alive set.
214 if (GV->hasInitializer())
215 MarkUsedGlobalsAsNeeded(GV->getInitializer());
216 } else if (GlobalIndirectSymbol *GIS = dyn_cast<GlobalIndirectSymbol>(G)) {
217 // The target of a global alias or ifunc is needed.
218 MarkUsedGlobalsAsNeeded(GIS->getIndirectSymbol());
220 // Otherwise this must be a function object. We have to scan the body of
221 // the function looking for constants and global values which are used as
222 // operands. Any operands of these types must be processed to ensure that
223 // any globals used will be marked as needed.
224 Function *F = cast<Function>(G);
226 for (Use &U : F->operands())
227 MarkUsedGlobalsAsNeeded(cast<Constant>(U.get()));
229 for (BasicBlock &BB : *F)
230 for (Instruction &I : BB)
231 for (Use &U : I.operands())
232 if (GlobalValue *GV = dyn_cast<GlobalValue>(U))
234 else if (Constant *C = dyn_cast<Constant>(U))
235 MarkUsedGlobalsAsNeeded(C);
239 void GlobalDCEPass::MarkUsedGlobalsAsNeeded(Constant *C) {
240 if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
241 return GlobalIsNeeded(GV);
243 // Loop over all of the operands of the constant, adding any globals they
244 // use to the list of needed globals.
245 for (Use &U : C->operands()) {
246 // If we've already processed this constant there's no need to do it again.
247 Constant *Op = dyn_cast<Constant>(U);
248 if (Op && SeenConstants.insert(Op).second)
249 MarkUsedGlobalsAsNeeded(Op);
253 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
254 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
255 // If found, check to see if the constant pointer ref is safe to destroy, and if
256 // so, nuke it. This will reduce the reference count on the global value, which
257 // might make it deader.
259 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
262 GV.removeDeadConstantUsers();
263 return GV.use_empty();