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"
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) {
47     initializeRedundantDbgInstEliminationPass(*PassRegistry::getPassRegistry());
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 
64 char RedundantDbgInstElimination::ID = 0;
65 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
66                 "Redundant Dbg Instruction Elimination", false, false)
67 
68 Pass *llvm::createRedundantDbgInstEliminationPass() {
69   return new RedundantDbgInstElimination();
70 }
71 
72 PreservedAnalyses
73 RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) {
74   bool Changed = false;
75   for (auto &BB : F)
76     Changed |= RemoveRedundantDbgInstrs(&BB);
77   if (!Changed)
78     return PreservedAnalyses::all();
79   PreservedAnalyses PA;
80   PA.preserveSet<CFGAnalyses>();
81   return PA;
82 }
83 
84 //===--------------------------------------------------------------------===//
85 // DeadCodeElimination pass implementation
86 //
87 
88 static bool DCEInstruction(Instruction *I,
89                            SmallSetVector<Instruction *, 16> &WorkList,
90                            const TargetLibraryInfo *TLI) {
91   if (isInstructionTriviallyDead(I, TLI)) {
92     if (!DebugCounter::shouldExecute(DCECounter))
93       return false;
94 
95     salvageDebugInfo(*I);
96     salvageKnowledge(I);
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 
122 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
123   bool MadeChange = false;
124   SmallSetVector<Instruction *, 16> WorkList;
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.
128   for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
129     Instruction *I = &*FI;
130     ++FI;
131 
132     // We're visiting this instruction now, so make sure it's not in the
133     // worklist from an earlier visit.
134     if (!WorkList.count(I))
135       MadeChange |= DCEInstruction(I, WorkList, TLI);
136   }
137 
138   while (!WorkList.empty()) {
139     Instruction *I = WorkList.pop_back_val();
140     MadeChange |= DCEInstruction(I, WorkList, TLI);
141   }
142   return MadeChange;
143 }
144 
145 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
146   if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F)))
147     return PreservedAnalyses::all();
148 
149   PreservedAnalyses PA;
150   PA.preserveSet<CFGAnalyses>();
151   return PA;
152 }
153 
154 namespace {
155 struct DCELegacyPass : public FunctionPass {
156   static char ID; // Pass identification, replacement for typeid
157   DCELegacyPass() : FunctionPass(ID) {
158     initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
159   }
160 
161   bool runOnFunction(Function &F) override {
162     if (skipFunction(F))
163       return false;
164 
165     TargetLibraryInfo *TLI =
166         &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
167 
168     return eliminateDeadCode(F, TLI);
169   }
170 
171   void getAnalysisUsage(AnalysisUsage &AU) const override {
172     AU.addRequired<TargetLibraryInfoWrapperPass>();
173     AU.setPreservesCFG();
174   }
175 };
176 }
177 
178 char DCELegacyPass::ID = 0;
179 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
180 
181 FunctionPass *llvm::createDeadCodeEliminationPass() {
182   return new DCELegacyPass();
183 }
184