LLVM  8.0.0svn
DCE.cpp
Go to the documentation of this file.
1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements dead inst elimination and dead code elimination.
11 //
12 // Dead Inst Elimination performs a single pass over the function removing
13 // instructions that are obviously dead. Dead Code Elimination is similar, but
14 // it rechecks instructions that were used by removed instructions to see if
15 // they are newly dead.
16 //
17 //===----------------------------------------------------------------------===//
18 
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/Statistic.h"
24 #include "llvm/IR/InstIterator.h"
25 #include "llvm/IR/Instruction.h"
26 #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 
35 namespace {
36  //===--------------------------------------------------------------------===//
37  // DeadInstElimination pass implementation
38  //
39  struct DeadInstElimination : public BasicBlockPass {
40  static char ID; // Pass identification, replacement for typeid
41  DeadInstElimination() : BasicBlockPass(ID) {
43  }
44  bool runOnBasicBlock(BasicBlock &BB) override {
45  if (skipBasicBlock(BB))
46  return false;
47  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
48  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
49  bool Changed = false;
50  for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
51  Instruction *Inst = &*DI++;
52  if (isInstructionTriviallyDead(Inst, TLI)) {
53  salvageDebugInfo(*Inst);
54  Inst->eraseFromParent();
55  Changed = true;
56  ++DIEEliminated;
57  }
58  }
59  return Changed;
60  }
61 
62  void getAnalysisUsage(AnalysisUsage &AU) const override {
63  AU.setPreservesCFG();
64  }
65  };
66 }
67 
69 INITIALIZE_PASS(DeadInstElimination, "die",
70  "Dead Instruction Elimination", false, false)
71 
73  return new DeadInstElimination();
74 }
75 
78  const TargetLibraryInfo *TLI) {
79  if (isInstructionTriviallyDead(I, TLI)) {
80  salvageDebugInfo(*I);
81 
82  // Null out all of the instruction's operands to see if any operand becomes
83  // dead as we go.
84  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
85  Value *OpV = I->getOperand(i);
86  I->setOperand(i, nullptr);
87 
88  if (!OpV->use_empty() || I == OpV)
89  continue;
90 
91  // If the operand is an instruction that became dead as we nulled out the
92  // operand, and if it is 'trivially' dead, delete it in a future loop
93  // iteration.
94  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
95  if (isInstructionTriviallyDead(OpI, TLI))
96  WorkList.insert(OpI);
97  }
98 
99  I->eraseFromParent();
100  ++DCEEliminated;
101  return true;
102  }
103  return false;
104 }
105 
107  bool MadeChange = false;
109  // Iterate over the original function, only adding insts to the worklist
110  // if they actually need to be revisited. This avoids having to pre-init
111  // the worklist with the entire function's worth of instructions.
112  for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
113  Instruction *I = &*FI;
114  ++FI;
115 
116  // We're visiting this instruction now, so make sure it's not in the
117  // worklist from an earlier visit.
118  if (!WorkList.count(I))
119  MadeChange |= DCEInstruction(I, WorkList, TLI);
120  }
121 
122  while (!WorkList.empty()) {
123  Instruction *I = WorkList.pop_back_val();
124  MadeChange |= DCEInstruction(I, WorkList, TLI);
125  }
126  return MadeChange;
127 }
128 
131  return PreservedAnalyses::all();
132 
134  PA.preserveSet<CFGAnalyses>();
135  return PA;
136 }
137 
138 namespace {
139 struct DCELegacyPass : public FunctionPass {
140  static char ID; // Pass identification, replacement for typeid
141  DCELegacyPass() : FunctionPass(ID) {
143  }
144 
145  bool runOnFunction(Function &F) override {
146  if (skipFunction(F))
147  return false;
148 
149  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
150  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
151 
152  return eliminateDeadCode(F, TLI);
153  }
154 
155  void getAnalysisUsage(AnalysisUsage &AU) const override {
156  AU.setPreservesCFG();
157  }
158 };
159 }
160 
161 char DCELegacyPass::ID = 0;
162 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
163 
165  return new DCELegacyPass();
166 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
void initializeDCELegacyPassPass(PassRegistry &)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:1606
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(DeadInstElimination, "die", "Dead Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:69
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
FunctionPass * createDeadCodeEliminationPass()
Definition: DCE.cpp:164
Value * getOperand(unsigned i) const
Definition: User.h:170
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
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:106
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
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:319
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
iterator end()
Definition: BasicBlock.h:266
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:286
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
static bool runOnBasicBlock(MachineBasicBlock *MBB, std::vector< StringRef > &bbNames, std::vector< unsigned > &renamedInOtherBB, unsigned &basicBlockNum, unsigned &VRegGapIndex, NamedVRegCursor &NVC)
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:76
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:129
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:73
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:706
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:347
LLVM Value Representation.
Definition: Value.h:73
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
bool use_empty() const
Definition: Value.h:323
void initializeDeadInstEliminationPass(PassRegistry &)