1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements dead inst elimination and dead code elimination.
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.
16 //===----------------------------------------------------------------------===//
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"
33 #define DEBUG_TYPE "dce"
35 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
36 STATISTIC(DCEEliminated, "Number of insts removed");
37 DEBUG_COUNTER(DCECounter, "dce-transform",
38 "Controls which instructions are eliminated");
41 //===--------------------------------------------------------------------===//
42 // DeadInstElimination pass implementation
44 struct DeadInstElimination : public FunctionPass {
45 static char ID; // Pass identification, replacement for typeid
46 DeadInstElimination() : FunctionPass(ID) {
47 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
49 bool runOnFunction(Function &F) override {
52 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
53 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
57 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
58 Instruction *Inst = &*DI++;
59 if (isInstructionTriviallyDead(Inst, TLI)) {
60 if (!DebugCounter::shouldExecute(DCECounter))
62 salvageDebugInfo(*Inst);
63 Inst->eraseFromParent();
72 void getAnalysisUsage(AnalysisUsage &AU) const override {
78 char DeadInstElimination::ID = 0;
79 INITIALIZE_PASS(DeadInstElimination, "die",
80 "Dead Instruction Elimination", false, false)
82 Pass *llvm::createDeadInstEliminationPass() {
83 return new DeadInstElimination();
86 //===--------------------------------------------------------------------===//
87 // RedundantDbgInstElimination pass implementation
91 struct RedundantDbgInstElimination : public FunctionPass {
92 static char ID; // Pass identification, replacement for typeid
93 RedundantDbgInstElimination() : FunctionPass(ID) {
94 initializeRedundantDbgInstEliminationPass(*PassRegistry::getPassRegistry());
96 bool runOnFunction(Function &F) override {
101 Changed |= RemoveRedundantDbgInstrs(&BB);
105 void getAnalysisUsage(AnalysisUsage &AU) const override {
106 AU.setPreservesCFG();
111 char RedundantDbgInstElimination::ID = 0;
112 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
113 "Redundant Dbg Instruction Elimination", false, false)
115 Pass *llvm::createRedundantDbgInstEliminationPass() {
116 return new RedundantDbgInstElimination();
119 //===--------------------------------------------------------------------===//
120 // DeadCodeElimination pass implementation
123 static bool DCEInstruction(Instruction *I,
124 SmallSetVector<Instruction *, 16> &WorkList,
125 const TargetLibraryInfo *TLI) {
126 if (isInstructionTriviallyDead(I, TLI)) {
127 if (!DebugCounter::shouldExecute(DCECounter))
130 salvageDebugInfo(*I);
133 // Null out all of the instruction's operands to see if any operand becomes
135 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
136 Value *OpV = I->getOperand(i);
137 I->setOperand(i, nullptr);
139 if (!OpV->use_empty() || I == OpV)
142 // If the operand is an instruction that became dead as we nulled out the
143 // operand, and if it is 'trivially' dead, delete it in a future loop
145 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
146 if (isInstructionTriviallyDead(OpI, TLI))
147 WorkList.insert(OpI);
150 I->eraseFromParent();
157 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
158 bool MadeChange = false;
159 SmallSetVector<Instruction *, 16> WorkList;
160 // Iterate over the original function, only adding insts to the worklist
161 // if they actually need to be revisited. This avoids having to pre-init
162 // the worklist with the entire function's worth of instructions.
163 for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
164 Instruction *I = &*FI;
167 // We're visiting this instruction now, so make sure it's not in the
168 // worklist from an earlier visit.
169 if (!WorkList.count(I))
170 MadeChange |= DCEInstruction(I, WorkList, TLI);
173 while (!WorkList.empty()) {
174 Instruction *I = WorkList.pop_back_val();
175 MadeChange |= DCEInstruction(I, WorkList, TLI);
180 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
181 if (!eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
182 return PreservedAnalyses::all();
184 PreservedAnalyses PA;
185 PA.preserveSet<CFGAnalyses>();
190 struct DCELegacyPass : public FunctionPass {
191 static char ID; // Pass identification, replacement for typeid
192 DCELegacyPass() : FunctionPass(ID) {
193 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
196 bool runOnFunction(Function &F) override {
200 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
201 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
203 return eliminateDeadCode(F, TLI);
206 void getAnalysisUsage(AnalysisUsage &AU) const override {
207 AU.setPreservesCFG();
212 char DCELegacyPass::ID = 0;
213 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
215 FunctionPass *llvm::createDeadCodeEliminationPass() {
216 return new DCELegacyPass();