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