LLVM 19.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"
23#include "llvm/IR/Instruction.h"
25#include "llvm/Pass.h"
31using namespace llvm;
32
33#define DEBUG_TYPE "dce"
34
35STATISTIC(DCEEliminated, "Number of insts removed");
36DEBUG_COUNTER(DCECounter, "dce-transform",
37 "Controls which instructions are eliminated");
38
41 bool Changed = false;
42 for (auto &BB : F)
43 Changed |= RemoveRedundantDbgInstrs(&BB);
44 if (!Changed)
48 return PA;
49}
50
51//===--------------------------------------------------------------------===//
52// DeadCodeElimination pass implementation
53//
54
57 const TargetLibraryInfo *TLI) {
58 if (isInstructionTriviallyDead(I, TLI)) {
59 if (!DebugCounter::shouldExecute(DCECounter))
60 return false;
61
64
65 // Null out all of the instruction's operands to see if any operand becomes
66 // dead as we go.
67 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
68 Value *OpV = I->getOperand(i);
69 I->setOperand(i, nullptr);
70
71 if (!OpV->use_empty() || I == OpV)
72 continue;
73
74 // If the operand is an instruction that became dead as we nulled out the
75 // operand, and if it is 'trivially' dead, delete it in a future loop
76 // iteration.
77 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
78 if (isInstructionTriviallyDead(OpI, TLI))
79 WorkList.insert(OpI);
80 }
81
82 I->eraseFromParent();
83 ++DCEEliminated;
84 return true;
85 }
86 return false;
87}
88
90 bool MadeChange = false;
92 // Iterate over the original function, only adding insts to the worklist
93 // if they actually need to be revisited. This avoids having to pre-init
94 // the worklist with the entire function's worth of instructions.
96 // We're visiting this instruction now, so make sure it's not in the
97 // worklist from an earlier visit.
98 if (!WorkList.count(&I))
99 MadeChange |= DCEInstruction(&I, WorkList, TLI);
100 }
101
102 while (!WorkList.empty()) {
103 Instruction *I = WorkList.pop_back_val();
104 MadeChange |= DCEInstruction(I, WorkList, TLI);
105 }
106 return MadeChange;
107}
108
111 return PreservedAnalyses::all();
112
115 return PA;
116}
117
118namespace {
119struct DCELegacyPass : public FunctionPass {
120 static char ID; // Pass identification, replacement for typeid
121 DCELegacyPass() : FunctionPass(ID) {
123 }
124
125 bool runOnFunction(Function &F) override {
126 if (skipFunction(F))
127 return false;
128
129 TargetLibraryInfo *TLI =
130 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
131
132 return eliminateDeadCode(F, TLI);
133 }
134
135 void getAnalysisUsage(AnalysisUsage &AU) const override {
137 AU.setPreservesCFG();
138 }
139};
140}
141
142char DCELegacyPass::ID = 0;
143INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
144
146 return new DCELegacyPass();
147}
Expand Atomic instructions
static bool DCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const TargetLibraryInfo *TLI)
Definition: DCE.cpp:55
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
static bool runOnFunction(Function &F, bool PostInlining)
static void eliminateDeadCode(Function &F)
Definition: IRMutator.cpp:81
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file implements a set that has insertion order iteration characteristics.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:109
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: DCE.cpp:40
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
value_type pop_back_val()
Definition: SetVector.h:285
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
LLVM Value Representation.
Definition: Value.h:74
bool use_empty() const
Definition: Value.h:344
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1581
FunctionPass * createDeadCodeEliminationPass()
Definition: DCE.cpp:145
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:665
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:399
void initializeDCELegacyPassPass(PassRegistry &)
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.