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 BasicBlockPass {
42  static char ID; // Pass identification, replacement for typeid
43  DeadInstElimination() : BasicBlockPass(ID) {
45  }
46  bool runOnBasicBlock(BasicBlock &BB) override {
47  if (skipBasicBlock(BB))
48  return false;
49  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
50  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(*BB.getParent()) : nullptr;
51  bool Changed = false;
52  for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
53  Instruction *Inst = &*DI++;
54  if (isInstructionTriviallyDead(Inst, TLI)) {
55  if (!DebugCounter::shouldExecute(DCECounter))
56  continue;
57  salvageDebugInfo(*Inst);
58  Inst->eraseFromParent();
59  Changed = true;
60  ++DIEEliminated;
61  }
62  }
63  return Changed;
64  }
65 
66  void getAnalysisUsage(AnalysisUsage &AU) const override {
67  AU.setPreservesCFG();
68  }
69  };
70 }
71 
73 INITIALIZE_PASS(DeadInstElimination, "die",
74  "Dead Instruction Elimination", false, false)
75 
77  return new DeadInstElimination();
78 }
79 
82  const TargetLibraryInfo *TLI) {
83  if (isInstructionTriviallyDead(I, TLI)) {
84  if (!DebugCounter::shouldExecute(DCECounter))
85  return false;
86 
87  salvageDebugInfo(*I);
88 
89  // Null out all of the instruction's operands to see if any operand becomes
90  // dead as we go.
91  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
92  Value *OpV = I->getOperand(i);
93  I->setOperand(i, nullptr);
94 
95  if (!OpV->use_empty() || I == OpV)
96  continue;
97 
98  // If the operand is an instruction that became dead as we nulled out the
99  // operand, and if it is 'trivially' dead, delete it in a future loop
100  // iteration.
101  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
102  if (isInstructionTriviallyDead(OpI, TLI))
103  WorkList.insert(OpI);
104  }
105 
106  I->eraseFromParent();
107  ++DCEEliminated;
108  return true;
109  }
110  return false;
111 }
112 
114  bool MadeChange = false;
116  // Iterate over the original function, only adding insts to the worklist
117  // if they actually need to be revisited. This avoids having to pre-init
118  // the worklist with the entire function's worth of instructions.
119  for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
120  Instruction *I = &*FI;
121  ++FI;
122 
123  // We're visiting this instruction now, so make sure it's not in the
124  // worklist from an earlier visit.
125  if (!WorkList.count(I))
126  MadeChange |= DCEInstruction(I, WorkList, TLI);
127  }
128 
129  while (!WorkList.empty()) {
130  Instruction *I = WorkList.pop_back_val();
131  MadeChange |= DCEInstruction(I, WorkList, TLI);
132  }
133  return MadeChange;
134 }
135 
138  return PreservedAnalyses::all();
139 
141  PA.preserveSet<CFGAnalyses>();
142  return PA;
143 }
144 
145 namespace {
146 struct DCELegacyPass : public FunctionPass {
147  static char ID; // Pass identification, replacement for typeid
148  DCELegacyPass() : FunctionPass(ID) {
150  }
151 
152  bool runOnFunction(Function &F) override {
153  if (skipFunction(F))
154  return false;
155 
156  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
157  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
158 
159  return eliminateDeadCode(F, TLI);
160  }
161 
162  void getAnalysisUsage(AnalysisUsage &AU) const override {
163  AU.setPreservesCFG();
164  }
165 };
166 }
167 
168 char DCELegacyPass::ID = 0;
169 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
170 
172  return new DCELegacyPass();
173 }
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:73
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
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:171
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:113
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Represent the analysis usage information of a pass.
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
BasicBlockPass class - This class is used to implement most local optimizations.
Definition: Pass.h:318
static bool runOnBasicBlock(MachineBasicBlock *MBB, std::vector< StringRef > &bbNames, unsigned &basicBlockNum, NamedVRegCursor &NVC)
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
iterator end()
Definition: BasicBlock.h:275
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:80
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:136
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#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:73
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:342
void initializeDeadInstEliminationPass(PassRegistry &)