LLVM  10.0.0svn
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"
23 #include "llvm/IR/InstIterator.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "dce"
31 
32 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
33 STATISTIC(DCEEliminated, "Number of insts removed");
34 DEBUG_COUNTER(DCECounter, "dce-transform",
35  "Controls which instructions are eliminated");
36 
37 namespace {
38  //===--------------------------------------------------------------------===//
39  // DeadInstElimination pass implementation
40  //
41 struct DeadInstElimination : public FunctionPass {
42  static char ID; // Pass identification, replacement for typeid
43  DeadInstElimination() : FunctionPass(ID) {
45  }
46  bool runOnFunction(Function &F) override {
47  if (skipFunction(F))
48  return false;
49  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
50  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
51 
52  bool Changed = false;
53  for (auto &BB : F) {
54  for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
55  Instruction *Inst = &*DI++;
56  if (isInstructionTriviallyDead(Inst, TLI)) {
57  if (!DebugCounter::shouldExecute(DCECounter))
58  continue;
59  salvageDebugInfo(*Inst);
60  Inst->eraseFromParent();
61  Changed = true;
62  ++DIEEliminated;
63  }
64  }
65  }
66  return Changed;
67  }
68 
69  void getAnalysisUsage(AnalysisUsage &AU) const override {
70  AU.setPreservesCFG();
71  }
72 };
73 }
74 
76 INITIALIZE_PASS(DeadInstElimination, "die",
77  "Dead Instruction Elimination", false, false)
78 
80  return new DeadInstElimination();
81 }
82 
85  const TargetLibraryInfo *TLI) {
86  if (isInstructionTriviallyDead(I, TLI)) {
87  if (!DebugCounter::shouldExecute(DCECounter))
88  return false;
89 
90  salvageDebugInfo(*I);
91 
92  // Null out all of the instruction's operands to see if any operand becomes
93  // dead as we go.
94  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
95  Value *OpV = I->getOperand(i);
96  I->setOperand(i, nullptr);
97 
98  if (!OpV->use_empty() || I == OpV)
99  continue;
100 
101  // If the operand is an instruction that became dead as we nulled out the
102  // operand, and if it is 'trivially' dead, delete it in a future loop
103  // iteration.
104  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
105  if (isInstructionTriviallyDead(OpI, TLI))
106  WorkList.insert(OpI);
107  }
108 
109  I->eraseFromParent();
110  ++DCEEliminated;
111  return true;
112  }
113  return false;
114 }
115 
117  bool MadeChange = false;
119  // Iterate over the original function, only adding insts to the worklist
120  // if they actually need to be revisited. This avoids having to pre-init
121  // the worklist with the entire function's worth of instructions.
122  for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
123  Instruction *I = &*FI;
124  ++FI;
125 
126  // We're visiting this instruction now, so make sure it's not in the
127  // worklist from an earlier visit.
128  if (!WorkList.count(I))
129  MadeChange |= DCEInstruction(I, WorkList, TLI);
130  }
131 
132  while (!WorkList.empty()) {
133  Instruction *I = WorkList.pop_back_val();
134  MadeChange |= DCEInstruction(I, WorkList, TLI);
135  }
136  return MadeChange;
137 }
138 
141  return PreservedAnalyses::all();
142 
144  PA.preserveSet<CFGAnalyses>();
145  return PA;
146 }
147 
148 namespace {
149 struct DCELegacyPass : public FunctionPass {
150  static char ID; // Pass identification, replacement for typeid
151  DCELegacyPass() : FunctionPass(ID) {
153  }
154 
155  bool runOnFunction(Function &F) override {
156  if (skipFunction(F))
157  return false;
158 
159  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
160  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
161 
162  return eliminateDeadCode(F, TLI);
163  }
164 
165  void getAnalysisUsage(AnalysisUsage &AU) const override {
166  AU.setPreservesCFG();
167  }
168 };
169 }
170 
171 char DCELegacyPass::ID = 0;
172 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
173 
175  return new DCELegacyPass();
176 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
void initializeDCELegacyPassPass(PassRegistry &)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
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()
bool 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:1605
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(DeadInstElimination, "die", "Dead Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:76
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:174
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:153
static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI)
Definition: DCE.cpp:116
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
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:301
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
static bool DCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const TargetLibraryInfo *TLI)
Definition: DCE.cpp:83
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:139
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
#define I(x, y, z)
Definition: MD5.cpp:58
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:795
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:359
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:343
void initializeDeadInstEliminationPass(PassRegistry &)