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 PreservedAnalyses 40 RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) { 41 bool Changed = false; 42 for (auto &BB : F) 43 Changed |= RemoveRedundantDbgInstrs(&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 55 static bool DCEInstruction(Instruction *I, 56 SmallSetVector<Instruction *, 16> &WorkList, 57 const TargetLibraryInfo *TLI) { 58 if (isInstructionTriviallyDead(I, TLI)) { 59 if (!DebugCounter::shouldExecute(DCECounter)) 60 return false; 61 62 salvageDebugInfo(*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, 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 89 static 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(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(&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 109 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) { 110 if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F))) 111 return PreservedAnalyses::all(); 112 113 PreservedAnalyses PA; 114 PA.preserveSet<CFGAnalyses>(); 115 return PA; 116 } 117 118 namespace { 119 struct 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 142 char DCELegacyPass::ID = 0; 143 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false) 144 145 FunctionPass *llvm::createDeadCodeEliminationPass() { 146 return new DCELegacyPass(); 147 } 148