LLVM  12.0.0git
DCE.cpp
Go to the documentation of this file.
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 
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "dce"
34 
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");
39 
40 namespace {
41  //===--------------------------------------------------------------------===//
42  // DeadInstElimination pass implementation
43  //
44 struct DeadInstElimination : public FunctionPass {
45  static char ID; // Pass identification, replacement for typeid
46  DeadInstElimination() : FunctionPass(ID) {
48  }
49  bool runOnFunction(Function &F) override {
50  if (skipFunction(F))
51  return false;
52  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
53  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
54 
55  bool Changed = false;
56  for (auto &BB : F) {
57  for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
58  Instruction *Inst = &*DI++;
59  if (isInstructionTriviallyDead(Inst, TLI)) {
60  if (!DebugCounter::shouldExecute(DCECounter))
61  continue;
62  salvageDebugInfo(*Inst);
63  Inst->eraseFromParent();
64  Changed = true;
65  ++DIEEliminated;
66  }
67  }
68  }
69  return Changed;
70  }
71 
72  void getAnalysisUsage(AnalysisUsage &AU) const override {
73  AU.setPreservesCFG();
74  }
75 };
76 }
77 
79 INITIALIZE_PASS(DeadInstElimination, "die",
80  "Dead Instruction Elimination", false, false)
81 
83  return new DeadInstElimination();
84 }
85 
86 //===--------------------------------------------------------------------===//
87 // RedundantDbgInstElimination pass implementation
88 //
89 
90 namespace {
91 struct RedundantDbgInstElimination : public FunctionPass {
92  static char ID; // Pass identification, replacement for typeid
93  RedundantDbgInstElimination() : FunctionPass(ID) {
95  }
96  bool runOnFunction(Function &F) override {
97  if (skipFunction(F))
98  return false;
99  bool Changed = false;
100  for (auto &BB : F)
101  Changed |= RemoveRedundantDbgInstrs(&BB);
102  return Changed;
103  }
104 
105  void getAnalysisUsage(AnalysisUsage &AU) const override {
106  AU.setPreservesCFG();
107  }
108 };
109 }
110 
112 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
113  "Redundant Dbg Instruction Elimination", false, false)
114 
116  return new RedundantDbgInstElimination();
117 }
118 
119 //===--------------------------------------------------------------------===//
120 // DeadCodeElimination pass implementation
121 //
122 
125  const TargetLibraryInfo *TLI) {
126  if (isInstructionTriviallyDead(I, TLI)) {
127  if (!DebugCounter::shouldExecute(DCECounter))
128  return false;
129 
130  salvageDebugInfo(*I);
131  salvageKnowledge(I);
132 
133  // Null out all of the instruction's operands to see if any operand becomes
134  // dead as we go.
135  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
136  Value *OpV = I->getOperand(i);
137  I->setOperand(i, nullptr);
138 
139  if (!OpV->use_empty() || I == OpV)
140  continue;
141 
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
144  // iteration.
145  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
146  if (isInstructionTriviallyDead(OpI, TLI))
147  WorkList.insert(OpI);
148  }
149 
150  I->eraseFromParent();
151  ++DCEEliminated;
152  return true;
153  }
154  return false;
155 }
156 
158  bool MadeChange = false;
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;
165  ++FI;
166 
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);
171  }
172 
173  while (!WorkList.empty()) {
174  Instruction *I = WorkList.pop_back_val();
175  MadeChange |= DCEInstruction(I, WorkList, TLI);
176  }
177  return MadeChange;
178 }
179 
182  return PreservedAnalyses::all();
183 
185  PA.preserveSet<CFGAnalyses>();
186  return PA;
187 }
188 
189 namespace {
190 struct DCELegacyPass : public FunctionPass {
191  static char ID; // Pass identification, replacement for typeid
192  DCELegacyPass() : FunctionPass(ID) {
194  }
195 
196  bool runOnFunction(Function &F) override {
197  if (skipFunction(F))
198  return false;
199 
200  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
201  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
202 
203  return eliminateDeadCode(F, TLI);
204  }
205 
206  void getAnalysisUsage(AnalysisUsage &AU) const override {
207  AU.setPreservesCFG();
208  }
209 };
210 }
211 
212 char DCELegacyPass::ID = 0;
213 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
214 
216  return new DCELegacyPass();
217 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:77
void initializeDCELegacyPassPass(PassRegistry &)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:80
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Pass * createDeadInstEliminationPass()
void initializeRedundantDbgInstEliminationPass(PassRegistry &)
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(DeadInstElimination, "die", "Dead Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:79
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
This file provides an implementation of debug counters.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
FunctionPass * createDeadCodeEliminationPass()
Definition: DCE.cpp:215
Pass * createRedundantDbgInstEliminationPass()
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1641
Value * getOperand(unsigned i) const
Definition: User.h:169
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
static bool runOnFunction(Function &F, bool PostInlining)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI)
Definition: DCE.cpp:157
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:58
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:302
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
Provides information about what library functions are available for the current target.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:115
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I...
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
static bool DCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const TargetLibraryInfo *TLI)
Definition: DCE.cpp:123
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:180
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
#define I(x, y, z)
Definition: MD5.cpp:59
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:788
DEBUG_COUNTER(DCECounter, "dce-transform", "Controls which instructions are eliminated")
Analysis pass providing the TargetLibraryInfo.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:360
LLVM Value Representation.
Definition: Value.h:74
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
A container for analyses that lazily runs them and caches their results.
bool use_empty() const
Definition: Value.h:341
void initializeDeadInstEliminationPass(PassRegistry &)