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
18#include "llvm/Transforms/Scalar/DCE.h"
19#include "llvm/ADT/SetVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/TargetLibraryInfo.h"
22#include "llvm/IR/InstIterator.h"
23#include "llvm/IR/Instruction.h"
24#include "llvm/InitializePasses.h"
25#include "llvm/Pass.h"
26#include "llvm/Support/DebugCounter.h"
27#include "llvm/Transforms/Scalar.h"
28#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
29#include "llvm/Transforms/Utils/BasicBlockUtils.h"
30#include "llvm/Transforms/Utils/Local.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
39PreservedAnalyses
40RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) {
41 bool Changed = false;
42 for (auto &BB : F)
43 Changed |= RemoveRedundantDbgInstrs(BB: &BB);
44 if (!Changed)
45 return PreservedAnalyses::all();
46 PreservedAnalyses PA;
47 PA.preserveSet<CFGAnalyses>();
48 return PA;
49}
50
51//===--------------------------------------------------------------------===//
52// DeadCodeElimination pass implementation
53//
54
55static bool DCEInstruction(Instruction *I,
56 SmallSetVector<Instruction *, 16> &WorkList,
57 const TargetLibraryInfo *TLI) {
58 if (isInstructionTriviallyDead(I, TLI)) {
59 if (!DebugCounter::shouldExecute(CounterName: DCECounter))
60 return false;
61
62 salvageDebugInfo(I&: *I);
63 salvageKnowledge(I);
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, Val: 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>(Val: OpV))
78 if (isInstructionTriviallyDead(I: OpI, TLI))
79 WorkList.insert(X: OpI);
80 }
81
82 I->eraseFromParent();
83 ++DCEEliminated;
84 return true;
85 }
86 return false;
87}
88
89static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
90 bool MadeChange = false;
91 SmallSetVector<Instruction *, 16> WorkList;
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.
95 for (Instruction &I : llvm::make_early_inc_range(Range: instructions(F))) {
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(key: &I))
99 MadeChange |= DCEInstruction(I: &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
109PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
110 if (!eliminateDeadCode(F, TLI: &AM.getResult<TargetLibraryAnalysis>(IR&: F)))
111 return PreservedAnalyses::all();
112
113 PreservedAnalyses PA;
114 PA.preserveSet<CFGAnalyses>();
115 return PA;
116}
117
118namespace {
119struct DCELegacyPass : public FunctionPass {
120 static char ID; // Pass identification, replacement for typeid
121 DCELegacyPass() : FunctionPass(ID) {
122 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
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 {
136 AU.addRequired<TargetLibraryInfoWrapperPass>();
137 AU.setPreservesCFG();
138 }
139};
140}
141
142char DCELegacyPass::ID = 0;
143INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
144
145FunctionPass *llvm::createDeadCodeEliminationPass() {
146 return new DCELegacyPass();
147}
148