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 (Instruction &I : llvm::make_early_inc_range(instructions(F))) { 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 142 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) { 143 if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F))) 144 return PreservedAnalyses::all(); 145 146 PreservedAnalyses PA; 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) { 155 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry()); 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 { 169 AU.addRequired<TargetLibraryInfoWrapperPass>(); 170 AU.setPreservesCFG(); 171 } 172 }; 173 } 174 175 char DCELegacyPass::ID = 0; 176 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false) 177 178 FunctionPass *llvm::createDeadCodeEliminationPass() { 179 return new DCELegacyPass(); 180 } 181