1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements dead inst elimination and dead code elimination.
11 //
12 // Dead Inst Elimination performs a single pass over the function removing
13 // instructions that are obviously dead. Dead Code Elimination is similar, but
14 // it rechecks instructions that were used by removed instructions to see if
15 // they are newly dead.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "llvm/Transforms/Scalar/DCE.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/TargetLibraryInfo.h"
23 #include "llvm/Transforms/Utils/Local.h"
24 #include "llvm/IR/InstIterator.h"
25 #include "llvm/IR/Instruction.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
28 using namespace llvm;
29
30 #define DEBUG_TYPE "dce"
31
32 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
33 STATISTIC(DCEEliminated, "Number of insts removed");
34
35 namespace {
36 //===--------------------------------------------------------------------===//
37 // DeadInstElimination pass implementation
38 //
39 struct DeadInstElimination : public BasicBlockPass {
40 static char ID; // Pass identification, replacement for typeid
DeadInstElimination__anonbb223b620111::DeadInstElimination41 DeadInstElimination() : BasicBlockPass(ID) {
42 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
43 }
runOnBasicBlock__anonbb223b620111::DeadInstElimination44 bool runOnBasicBlock(BasicBlock &BB) override {
45 if (skipBasicBlock(BB))
46 return false;
47 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
48 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
49 bool Changed = false;
50 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
51 Instruction *Inst = &*DI++;
52 if (isInstructionTriviallyDead(Inst, TLI)) {
53 salvageDebugInfo(*Inst);
54 Inst->eraseFromParent();
55 Changed = true;
56 ++DIEEliminated;
57 }
58 }
59 return Changed;
60 }
61
getAnalysisUsage__anonbb223b620111::DeadInstElimination62 void getAnalysisUsage(AnalysisUsage &AU) const override {
63 AU.setPreservesCFG();
64 }
65 };
66 }
67
68 char DeadInstElimination::ID = 0;
69 INITIALIZE_PASS(DeadInstElimination, "die",
70 "Dead Instruction Elimination", false, false)
71
createDeadInstEliminationPass()72 Pass *llvm::createDeadInstEliminationPass() {
73 return new DeadInstElimination();
74 }
75
DCEInstruction(Instruction * I,SmallSetVector<Instruction *,16> & WorkList,const TargetLibraryInfo * TLI)76 static bool DCEInstruction(Instruction *I,
77 SmallSetVector<Instruction *, 16> &WorkList,
78 const TargetLibraryInfo *TLI) {
79 if (isInstructionTriviallyDead(I, TLI)) {
80 salvageDebugInfo(*I);
81
82 // Null out all of the instruction's operands to see if any operand becomes
83 // dead as we go.
84 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
85 Value *OpV = I->getOperand(i);
86 I->setOperand(i, nullptr);
87
88 if (!OpV->use_empty() || I == OpV)
89 continue;
90
91 // If the operand is an instruction that became dead as we nulled out the
92 // operand, and if it is 'trivially' dead, delete it in a future loop
93 // iteration.
94 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
95 if (isInstructionTriviallyDead(OpI, TLI))
96 WorkList.insert(OpI);
97 }
98
99 I->eraseFromParent();
100 ++DCEEliminated;
101 return true;
102 }
103 return false;
104 }
105
eliminateDeadCode(Function & F,TargetLibraryInfo * TLI)106 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
107 bool MadeChange = false;
108 SmallSetVector<Instruction *, 16> WorkList;
109 // Iterate over the original function, only adding insts to the worklist
110 // if they actually need to be revisited. This avoids having to pre-init
111 // the worklist with the entire function's worth of instructions.
112 for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
113 Instruction *I = &*FI;
114 ++FI;
115
116 // We're visiting this instruction now, so make sure it's not in the
117 // worklist from an earlier visit.
118 if (!WorkList.count(I))
119 MadeChange |= DCEInstruction(I, WorkList, TLI);
120 }
121
122 while (!WorkList.empty()) {
123 Instruction *I = WorkList.pop_back_val();
124 MadeChange |= DCEInstruction(I, WorkList, TLI);
125 }
126 return MadeChange;
127 }
128
run(Function & F,FunctionAnalysisManager & AM)129 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
130 if (!eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
131 return PreservedAnalyses::all();
132
133 PreservedAnalyses PA;
134 PA.preserveSet<CFGAnalyses>();
135 return PA;
136 }
137
138 namespace {
139 struct DCELegacyPass : public FunctionPass {
140 static char ID; // Pass identification, replacement for typeid
DCELegacyPass__anonbb223b620211::DCELegacyPass141 DCELegacyPass() : FunctionPass(ID) {
142 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
143 }
144
runOnFunction__anonbb223b620211::DCELegacyPass145 bool runOnFunction(Function &F) override {
146 if (skipFunction(F))
147 return false;
148
149 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
150 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
151
152 return eliminateDeadCode(F, TLI);
153 }
154
getAnalysisUsage__anonbb223b620211::DCELegacyPass155 void getAnalysisUsage(AnalysisUsage &AU) const override {
156 AU.setPreservesCFG();
157 }
158 };
159 }
160
161 char DCELegacyPass::ID = 0;
162 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
163
createDeadCodeEliminationPass()164 FunctionPass *llvm::createDeadCodeEliminationPass() {
165 return new DCELegacyPass();
166 }
167