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"
28 #include "llvm/Transforms/Scalar.h"
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "dce"
32 
33 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
34 STATISTIC(DCEEliminated, "Number of insts removed");
35 DEBUG_COUNTER(DCECounter, "dce-transform",
36  "Controls which instructions are eliminated");
37 
38 namespace {
39  //===--------------------------------------------------------------------===//
40  // DeadInstElimination pass implementation
41  //
42  struct DeadInstElimination : public BasicBlockPass {
43  static char ID; // Pass identification, replacement for typeid
44  DeadInstElimination() : BasicBlockPass(ID) {
46  }
47  bool runOnBasicBlock(BasicBlock &BB) override {
48  if (skipBasicBlock(BB))
49  return false;
50  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
51  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
52  bool Changed = false;
53  for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
54  Instruction *Inst = &*DI++;
55  if (isInstructionTriviallyDead(Inst, TLI)) {
56  if (!DebugCounter::shouldExecute(DCECounter))
57  continue;
58  salvageDebugInfo(*Inst);
59  Inst->eraseFromParent();
60  Changed = true;
61  ++DIEEliminated;
62  }
63  }
64  return Changed;
65  }
66 
67  void getAnalysisUsage(AnalysisUsage &AU) const override {
68  AU.setPreservesCFG();
69  }
70  };
71 }
72 
74 INITIALIZE_PASS(DeadInstElimination, "die",
75  "Dead Instruction Elimination", false, false)
76 
78  return new DeadInstElimination();
79 }
80 
83  const TargetLibraryInfo *TLI) {
84  if (isInstructionTriviallyDead(I, TLI)) {
85  if (!DebugCounter::shouldExecute(DCECounter))
86  return false;
87 
88  salvageDebugInfo(*I);
89 
90  // Null out all of the instruction's operands to see if any operand becomes
91  // dead as we go.
92  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
93  Value *OpV = I->getOperand(i);
94  I->setOperand(i, nullptr);
95 
96  if (!OpV->use_empty() || I == OpV)
97  continue;
98 
99  // If the operand is an instruction that became dead as we nulled out the
100  // operand, and if it is 'trivially' dead, delete it in a future loop
101  // iteration.
102  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
103  if (isInstructionTriviallyDead(OpI, TLI))
104  WorkList.insert(OpI);
105  }
106 
107  I->eraseFromParent();
108  ++DCEEliminated;
109  return true;
110  }
111  return false;
112 }
113 
115  bool MadeChange = false;
117  // Iterate over the original function, only adding insts to the worklist
118  // if they actually need to be revisited. This avoids having to pre-init
119  // the worklist with the entire function's worth of instructions.
120  for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
121  Instruction *I = &*FI;
122  ++FI;
123 
124  // We're visiting this instruction now, so make sure it's not in the
125  // worklist from an earlier visit.
126  if (!WorkList.count(I))
127  MadeChange |= DCEInstruction(I, WorkList, TLI);
128  }
129 
130  while (!WorkList.empty()) {
131  Instruction *I = WorkList.pop_back_val();
132  MadeChange |= DCEInstruction(I, WorkList, TLI);
133  }
134  return MadeChange;
135 }
136 
139  return PreservedAnalyses::all();
140 
142  PA.preserveSet<CFGAnalyses>();
143  return PA;
144 }
145 
146 namespace {
147 struct DCELegacyPass : public FunctionPass {
148  static char ID; // Pass identification, replacement for typeid
149  DCELegacyPass() : FunctionPass(ID) {
151  }
152 
153  bool runOnFunction(Function &F) override {
154  if (skipFunction(F))
155  return false;
156 
157  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
158  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
159 
160  return eliminateDeadCode(F, TLI);
161  }
162 
163  void getAnalysisUsage(AnalysisUsage &AU) const override {
164  AU.setPreservesCFG();
165  }
166 };
167 }
168 
169 char DCELegacyPass::ID = 0;
170 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
171 
173  return new DCELegacyPass();
174 }
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:1609
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(DeadInstElimination, "die", "Dead Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:74
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
This file provides an implementation of debug counters.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
FunctionPass * createDeadCodeEliminationPass()
Definition: DCE.cpp:172
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:154
static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI)
Definition: DCE.cpp:114
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 bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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:115
static bool DCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const TargetLibraryInfo *TLI)
Definition: DCE.cpp:81
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:137
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
#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:789
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:348
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 &)