1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements dead inst elimination and dead code elimination.
10 //
11 // Dead Inst Elimination performs a single pass over the function removing
12 // instructions that are obviously dead. Dead Code Elimination is similar, but
13 // it rechecks instructions that were used by removed instructions to see if
14 // they are newly dead.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/Transforms/Scalar/DCE.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/TargetLibraryInfo.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/DebugCounter.h"
27 #include "llvm/Transforms/Scalar.h"
28 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
29 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
30 #include "llvm/Transforms/Utils/Local.h"
31 using namespace llvm;
32
33 #define DEBUG_TYPE "dce"
34
35 STATISTIC(DCEEliminated, "Number of insts removed");
36 DEBUG_COUNTER(DCECounter, "dce-transform",
37 "Controls which instructions are eliminated");
38
39 //===--------------------------------------------------------------------===//
40 // RedundantDbgInstElimination pass implementation
41 //
42
43 namespace {
44 struct RedundantDbgInstElimination : public FunctionPass {
45 static char ID; // Pass identification, replacement for typeid
RedundantDbgInstElimination__anonc2c145c00111::RedundantDbgInstElimination46 RedundantDbgInstElimination() : FunctionPass(ID) {
47 initializeRedundantDbgInstEliminationPass(*PassRegistry::getPassRegistry());
48 }
runOnFunction__anonc2c145c00111::RedundantDbgInstElimination49 bool runOnFunction(Function &F) override {
50 if (skipFunction(F))
51 return false;
52 bool Changed = false;
53 for (auto &BB : F)
54 Changed |= RemoveRedundantDbgInstrs(&BB);
55 return Changed;
56 }
57
getAnalysisUsage__anonc2c145c00111::RedundantDbgInstElimination58 void getAnalysisUsage(AnalysisUsage &AU) const override {
59 AU.setPreservesCFG();
60 }
61 };
62 }
63
64 char RedundantDbgInstElimination::ID = 0;
65 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
66 "Redundant Dbg Instruction Elimination", false, false)
67
createRedundantDbgInstEliminationPass()68 Pass *llvm::createRedundantDbgInstEliminationPass() {
69 return new RedundantDbgInstElimination();
70 }
71
72 PreservedAnalyses
run(Function & F,FunctionAnalysisManager & AM)73 RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) {
74 bool Changed = false;
75 for (auto &BB : F)
76 Changed |= RemoveRedundantDbgInstrs(&BB);
77 if (!Changed)
78 return PreservedAnalyses::all();
79 PreservedAnalyses PA;
80 PA.preserveSet<CFGAnalyses>();
81 return PA;
82 }
83
84 //===--------------------------------------------------------------------===//
85 // DeadCodeElimination pass implementation
86 //
87
DCEInstruction(Instruction * I,SmallSetVector<Instruction *,16> & WorkList,const TargetLibraryInfo * TLI)88 static bool DCEInstruction(Instruction *I,
89 SmallSetVector<Instruction *, 16> &WorkList,
90 const TargetLibraryInfo *TLI) {
91 if (isInstructionTriviallyDead(I, TLI)) {
92 if (!DebugCounter::shouldExecute(DCECounter))
93 return false;
94
95 salvageDebugInfo(*I);
96 salvageKnowledge(I);
97
98 // Null out all of the instruction's operands to see if any operand becomes
99 // dead as we go.
100 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
101 Value *OpV = I->getOperand(i);
102 I->setOperand(i, nullptr);
103
104 if (!OpV->use_empty() || I == OpV)
105 continue;
106
107 // If the operand is an instruction that became dead as we nulled out the
108 // operand, and if it is 'trivially' dead, delete it in a future loop
109 // iteration.
110 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
111 if (isInstructionTriviallyDead(OpI, TLI))
112 WorkList.insert(OpI);
113 }
114
115 I->eraseFromParent();
116 ++DCEEliminated;
117 return true;
118 }
119 return false;
120 }
121
eliminateDeadCode(Function & F,TargetLibraryInfo * TLI)122 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
123 bool MadeChange = false;
124 SmallSetVector<Instruction *, 16> WorkList;
125 // Iterate over the original function, only adding insts to the worklist
126 // if they actually need to be revisited. This avoids having to pre-init
127 // the worklist with the entire function's worth of instructions.
128 for (Instruction &I : llvm::make_early_inc_range(instructions(F))) {
129 // We're visiting this instruction now, so make sure it's not in the
130 // worklist from an earlier visit.
131 if (!WorkList.count(&I))
132 MadeChange |= DCEInstruction(&I, WorkList, TLI);
133 }
134
135 while (!WorkList.empty()) {
136 Instruction *I = WorkList.pop_back_val();
137 MadeChange |= DCEInstruction(I, WorkList, TLI);
138 }
139 return MadeChange;
140 }
141
run(Function & F,FunctionAnalysisManager & AM)142 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
143 if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F)))
144 return PreservedAnalyses::all();
145
146 PreservedAnalyses PA;
147 PA.preserveSet<CFGAnalyses>();
148 return PA;
149 }
150
151 namespace {
152 struct DCELegacyPass : public FunctionPass {
153 static char ID; // Pass identification, replacement for typeid
DCELegacyPass__anonc2c145c00211::DCELegacyPass154 DCELegacyPass() : FunctionPass(ID) {
155 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
156 }
157
runOnFunction__anonc2c145c00211::DCELegacyPass158 bool runOnFunction(Function &F) override {
159 if (skipFunction(F))
160 return false;
161
162 TargetLibraryInfo *TLI =
163 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
164
165 return eliminateDeadCode(F, TLI);
166 }
167
getAnalysisUsage__anonc2c145c00211::DCELegacyPass168 void getAnalysisUsage(AnalysisUsage &AU) const override {
169 AU.addRequired<TargetLibraryInfoWrapperPass>();
170 AU.setPreservesCFG();
171 }
172 };
173 }
174
175 char DCELegacyPass::ID = 0;
176 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
177
createDeadCodeEliminationPass()178 FunctionPass *llvm::createDeadCodeEliminationPass() {
179 return new DCELegacyPass();
180 }
181