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.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Analysis/TargetLibraryInfo.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 using namespace llvm;
28
29 #define DEBUG_TYPE "dce"
30
31 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
32 STATISTIC(DCEEliminated, "Number of insts removed");
33
34 namespace {
35 //===--------------------------------------------------------------------===//
36 // DeadInstElimination pass implementation
37 //
38 struct DeadInstElimination : public BasicBlockPass {
39 static char ID; // Pass identification, replacement for typeid
DeadInstElimination__anon30533d610111::DeadInstElimination40 DeadInstElimination() : BasicBlockPass(ID) {
41 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
42 }
runOnBasicBlock__anon30533d610111::DeadInstElimination43 bool runOnBasicBlock(BasicBlock &BB) override {
44 if (skipOptnoneFunction(BB))
45 return false;
46 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
47 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
48 bool Changed = false;
49 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
50 Instruction *Inst = &*DI++;
51 if (isInstructionTriviallyDead(Inst, TLI)) {
52 Inst->eraseFromParent();
53 Changed = true;
54 ++DIEEliminated;
55 }
56 }
57 return Changed;
58 }
59
getAnalysisUsage__anon30533d610111::DeadInstElimination60 void getAnalysisUsage(AnalysisUsage &AU) const override {
61 AU.setPreservesCFG();
62 }
63 };
64 }
65
66 char DeadInstElimination::ID = 0;
67 INITIALIZE_PASS(DeadInstElimination, "die",
68 "Dead Instruction Elimination", false, false)
69
createDeadInstEliminationPass()70 Pass *llvm::createDeadInstEliminationPass() {
71 return new DeadInstElimination();
72 }
73
74
75 namespace {
76 //===--------------------------------------------------------------------===//
77 // DeadCodeElimination pass implementation
78 //
79 struct DCE : public FunctionPass {
80 static char ID; // Pass identification, replacement for typeid
DCE__anon30533d610211::DCE81 DCE() : FunctionPass(ID) {
82 initializeDCEPass(*PassRegistry::getPassRegistry());
83 }
84
85 bool runOnFunction(Function &F) override;
86
getAnalysisUsage__anon30533d610211::DCE87 void getAnalysisUsage(AnalysisUsage &AU) const override {
88 AU.setPreservesCFG();
89 }
90 };
91 }
92
93 char DCE::ID = 0;
94 INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false)
95
DCEInstruction(Instruction * I,SmallSetVector<Instruction *,16> & WorkList,const TargetLibraryInfo * TLI)96 static bool DCEInstruction(Instruction *I,
97 SmallSetVector<Instruction *, 16> &WorkList,
98 const TargetLibraryInfo *TLI) {
99 if (isInstructionTriviallyDead(I, TLI)) {
100 // Null out all of the instruction's operands to see if any operand becomes
101 // dead as we go.
102 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
103 Value *OpV = I->getOperand(i);
104 I->setOperand(i, nullptr);
105
106 if (!OpV->use_empty() || I == OpV)
107 continue;
108
109 // If the operand is an instruction that became dead as we nulled out the
110 // operand, and if it is 'trivially' dead, delete it in a future loop
111 // iteration.
112 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
113 if (isInstructionTriviallyDead(OpI, TLI))
114 WorkList.insert(OpI);
115 }
116
117 I->eraseFromParent();
118 ++DCEEliminated;
119 return true;
120 }
121 return false;
122 }
123
runOnFunction(Function & F)124 bool DCE::runOnFunction(Function &F) {
125 if (skipOptnoneFunction(F))
126 return false;
127
128 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
129 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
130
131 bool MadeChange = false;
132 SmallSetVector<Instruction *, 16> WorkList;
133 // Iterate over the original function, only adding insts to the worklist
134 // if they actually need to be revisited. This avoids having to pre-init
135 // the worklist with the entire function's worth of instructions.
136 for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
137 Instruction *I = &*FI;
138 ++FI;
139
140 // We're visiting this instruction now, so make sure it's not in the
141 // worklist from an earlier visit.
142 if (!WorkList.count(I))
143 MadeChange |= DCEInstruction(I, WorkList, TLI);
144 }
145
146 while (!WorkList.empty()) {
147 Instruction *I = WorkList.pop_back_val();
148 MadeChange |= DCEInstruction(I, WorkList, TLI);
149 }
150 return MadeChange;
151 }
152
createDeadCodeEliminationPass()153 FunctionPass *llvm::createDeadCodeEliminationPass() {
154 return new DCE();
155 }
156
157