LLVM  6.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"
23 #include "llvm/IR/InstIterator.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/Pass.h"
26 #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  Inst->eraseFromParent();
54  Changed = true;
55  ++DIEEliminated;
56  }
57  }
58  return Changed;
59  }
60 
61  void getAnalysisUsage(AnalysisUsage &AU) const override {
62  AU.setPreservesCFG();
63  }
64  };
65 }
66 
68 INITIALIZE_PASS(DeadInstElimination, "die",
69  "Dead Instruction Elimination", false, false)
70 
72  return new DeadInstElimination();
73 }
74 
77  const TargetLibraryInfo *TLI) {
78  if (isInstructionTriviallyDead(I, TLI)) {
79  // Null out all of the instruction's operands to see if any operand becomes
80  // dead as we go.
81  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
82  Value *OpV = I->getOperand(i);
83  I->setOperand(i, nullptr);
84 
85  if (!OpV->use_empty() || I == OpV)
86  continue;
87 
88  // If the operand is an instruction that became dead as we nulled out the
89  // operand, and if it is 'trivially' dead, delete it in a future loop
90  // iteration.
91  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
92  if (isInstructionTriviallyDead(OpI, TLI))
93  WorkList.insert(OpI);
94  }
95 
96  I->eraseFromParent();
97  ++DCEEliminated;
98  return true;
99  }
100  return false;
101 }
102 
104  bool MadeChange = false;
106  // Iterate over the original function, only adding insts to the worklist
107  // if they actually need to be revisited. This avoids having to pre-init
108  // the worklist with the entire function's worth of instructions.
109  for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
110  Instruction *I = &*FI;
111  ++FI;
112 
113  // We're visiting this instruction now, so make sure it's not in the
114  // worklist from an earlier visit.
115  if (!WorkList.count(I))
116  MadeChange |= DCEInstruction(I, WorkList, TLI);
117  }
118 
119  while (!WorkList.empty()) {
120  Instruction *I = WorkList.pop_back_val();
121  MadeChange |= DCEInstruction(I, WorkList, TLI);
122  }
123  return MadeChange;
124 }
125 
128  return PreservedAnalyses::all();
129 
131  PA.preserveSet<CFGAnalyses>();
132  return PA;
133 }
134 
135 namespace {
136 struct DCELegacyPass : public FunctionPass {
137  static char ID; // Pass identification, replacement for typeid
138  DCELegacyPass() : FunctionPass(ID) {
140  }
141 
142  bool runOnFunction(Function &F) override {
143  if (skipFunction(F))
144  return false;
145 
146  auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
147  TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
148 
149  return eliminateDeadCode(F, TLI);
150  }
151 
152  void getAnalysisUsage(AnalysisUsage &AU) const override {
153  AU.setPreservesCFG();
154  }
155 };
156 }
157 
158 char DCELegacyPass::ID = 0;
159 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
160 
162  return new DCELegacyPass();
163 }
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:69
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()
STATISTIC(NumFunctions, "Total number of functions")
F(f)
INITIALIZE_PASS(DeadInstElimination, "die", "Dead Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:68
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
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:161
Value * getOperand(unsigned i) const
Definition: User.h:154
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)
static bool runOnBasicBlock(MachineBasicBlock *MBB, std::vector< StringRef > &bbNames, std::vector< unsigned > &renamedInOtherBB, unsigned &basicBlockNum, unsigned &VRegGapIndex)
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:103
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:176
iterator end()
Definition: BasicBlock.h:254
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:285
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
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:75
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:126
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:324
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:328
void initializeDeadInstEliminationPass(PassRegistry &)