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 //===--------------------------------------------------------------------===//
73 // DeadCodeElimination pass implementation
74 //
75 
76 static bool DCEInstruction(Instruction *I,
77                            SmallSetVector<Instruction *, 16> &WorkList,
78                            const TargetLibraryInfo *TLI) {
79   if (isInstructionTriviallyDead(I, TLI)) {
80     if (!DebugCounter::shouldExecute(DCECounter))
81       return false;
82 
83     salvageDebugInfo(*I);
84     salvageKnowledge(I);
85 
86     // Null out all of the instruction's operands to see if any operand becomes
87     // dead as we go.
88     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
89       Value *OpV = I->getOperand(i);
90       I->setOperand(i, nullptr);
91 
92       if (!OpV->use_empty() || I == OpV)
93         continue;
94 
95       // If the operand is an instruction that became dead as we nulled out the
96       // operand, and if it is 'trivially' dead, delete it in a future loop
97       // iteration.
98       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
99         if (isInstructionTriviallyDead(OpI, TLI))
100           WorkList.insert(OpI);
101     }
102 
103     I->eraseFromParent();
104     ++DCEEliminated;
105     return true;
106   }
107   return false;
108 }
109 
110 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
111   bool MadeChange = false;
112   SmallSetVector<Instruction *, 16> WorkList;
113   // Iterate over the original function, only adding insts to the worklist
114   // if they actually need to be revisited. This avoids having to pre-init
115   // the worklist with the entire function's worth of instructions.
116   for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
117     Instruction *I = &*FI;
118     ++FI;
119 
120     // We're visiting this instruction now, so make sure it's not in the
121     // worklist from an earlier visit.
122     if (!WorkList.count(I))
123       MadeChange |= DCEInstruction(I, WorkList, TLI);
124   }
125 
126   while (!WorkList.empty()) {
127     Instruction *I = WorkList.pop_back_val();
128     MadeChange |= DCEInstruction(I, WorkList, TLI);
129   }
130   return MadeChange;
131 }
132 
133 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
134   if (!eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
135     return PreservedAnalyses::all();
136 
137   PreservedAnalyses PA;
138   PA.preserveSet<CFGAnalyses>();
139   return PA;
140 }
141 
142 namespace {
143 struct DCELegacyPass : public FunctionPass {
144   static char ID; // Pass identification, replacement for typeid
145   DCELegacyPass() : FunctionPass(ID) {
146     initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
147   }
148 
149   bool runOnFunction(Function &F) override {
150     if (skipFunction(F))
151       return false;
152 
153     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
154     TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
155 
156     return eliminateDeadCode(F, TLI);
157   }
158 
159   void getAnalysisUsage(AnalysisUsage &AU) const override {
160     AU.setPreservesCFG();
161   }
162 };
163 }
164 
165 char DCELegacyPass::ID = 0;
166 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
167 
168 FunctionPass *llvm::createDeadCodeEliminationPass() {
169   return new DCELegacyPass();
170 }
171