LLVM  13.0.0git
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"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "dce"
34 
35 STATISTIC(DCEEliminated, "Number of insts removed");
36 DEBUG_COUNTER(DCECounter, "dce-transform",
37  "Controls which instructions are eliminated");
38 
39 //===--------------------------------------------------------------------===//
40 // RedundantDbgInstElimination pass implementation
41 //
42 
43 namespace {
44 struct RedundantDbgInstElimination : public FunctionPass {
45  static char ID; // Pass identification, replacement for typeid
46  RedundantDbgInstElimination() : FunctionPass(ID) {
48  }
49  bool runOnFunction(Function &F) override {
50  if (skipFunction(F))
51  return false;
52  bool Changed = false;
53  for (auto &BB : F)
54  Changed |= RemoveRedundantDbgInstrs(&BB);
55  return Changed;
56  }
57 
58  void getAnalysisUsage(AnalysisUsage &AU) const override {
59  AU.setPreservesCFG();
60  }
61 };
62 }
63 
65 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
66  "Redundant Dbg Instruction Elimination", false, false)
67 
69  return new RedundantDbgInstElimination();
70 }
71 
74  bool Changed = false;
75  for (auto &BB : F)
76  Changed |= RemoveRedundantDbgInstrs(&BB);
77  if (!Changed)
78  return PreservedAnalyses::all();
81  return PA;
82 }
83 
84 //===--------------------------------------------------------------------===//
85 // DeadCodeElimination pass implementation
86 //
87 
90  const TargetLibraryInfo *TLI) {
91  if (isInstructionTriviallyDead(I, TLI)) {
92  if (!DebugCounter::shouldExecute(DCECounter))
93  return false;
94 
97 
98  // Null out all of the instruction's operands to see if any operand becomes
99  // dead as we go.
100  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
101  Value *OpV = I->getOperand(i);
102  I->setOperand(i, nullptr);
103 
104  if (!OpV->use_empty() || I == OpV)
105  continue;
106 
107  // If the operand is an instruction that became dead as we nulled out the
108  // operand, and if it is 'trivially' dead, delete it in a future loop
109  // iteration.
110  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
111  if (isInstructionTriviallyDead(OpI, TLI))
112  WorkList.insert(OpI);
113  }
114 
115  I->eraseFromParent();
116  ++DCEEliminated;
117  return true;
118  }
119  return false;
120 }
121 
123  bool MadeChange = false;
125  // Iterate over the original function, only adding insts to the worklist
126  // if they actually need to be revisited. This avoids having to pre-init
127  // the worklist with the entire function's worth of instructions.
129  // We're visiting this instruction now, so make sure it's not in the
130  // worklist from an earlier visit.
131  if (!WorkList.count(&I))
132  MadeChange |= DCEInstruction(&I, WorkList, TLI);
133  }
134 
135  while (!WorkList.empty()) {
136  Instruction *I = WorkList.pop_back_val();
137  MadeChange |= DCEInstruction(I, WorkList, TLI);
138  }
139  return MadeChange;
140 }
141 
144  return PreservedAnalyses::all();
145 
147  PA.preserveSet<CFGAnalyses>();
148  return PA;
149 }
150 
151 namespace {
152 struct DCELegacyPass : public FunctionPass {
153  static char ID; // Pass identification, replacement for typeid
154  DCELegacyPass() : FunctionPass(ID) {
156  }
157 
158  bool runOnFunction(Function &F) override {
159  if (skipFunction(F))
160  return false;
161 
162  TargetLibraryInfo *TLI =
163  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
164 
165  return eliminateDeadCode(F, TLI);
166  }
167 
168  void getAnalysisUsage(AnalysisUsage &AU) const override {
170  AU.setPreservesCFG();
171  }
172 };
173 }
174 
175 char DCELegacyPass::ID = 0;
176 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
177 
179  return new DCELegacyPass();
180 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::DCEPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:142
DCEInstruction
static bool DCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const TargetLibraryInfo *TLI)
Definition: DCE.cpp:88
llvm
Definition: AllocatorList.h:23
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
Scalar.h
InstIterator.h
llvm::Function
Definition: Function.h:61
Pass.h
Statistic.h
Local.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
Instruction.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TargetLibraryInfo.h
AssumeBundleBuilder.h
llvm::Instruction
Definition: Instruction.h:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
llvm::createRedundantDbgInstEliminationPass
Pass * createRedundantDbgInstEliminationPass()
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:572
INITIALIZE_PASS
INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim", "Redundant Dbg Instruction Elimination", false, false) Pass *llvm
Definition: DCE.cpp:65
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:293
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::isInstructionTriviallyDead
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:398
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::initializeDCELegacyPassPass
void initializeDCELegacyPassPass(PassRegistry &)
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
DEBUG_COUNTER
DEBUG_COUNTER(DCECounter, "dce-transform", "Controls which instructions are eliminated")
DebugCounter.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::salvageDebugInfo
void 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:1719
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::initializeRedundantDbgInstEliminationPass
void initializeRedundantDbgInstEliminationPass(PassRegistry &)
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB, bool RemovePseudoOp=false)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:432
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
DCE.h
llvm::createDeadCodeEliminationPass
FunctionPass * createDeadCodeEliminationPass()
Definition: DCE.cpp:178
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::RedundantDbgInstEliminationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:73
BasicBlockUtils.h
InitializePasses.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
eliminateDeadCode
static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI)
Definition: DCE.cpp:122
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
SetVector.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38