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/Transforms/Utils/Local.h" 23 #include "llvm/IR/InstIterator.h" 24 #include "llvm/IR/Instruction.h" 25 #include "llvm/Pass.h" 26 #include "llvm/Support/DebugCounter.h" 27 #include "llvm/Transforms/Scalar.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "dce" 31 32 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 33 STATISTIC(DCEEliminated, "Number of insts removed"); 34 DEBUG_COUNTER(DCECounter, "dce-transform", 35 "Controls which instructions are eliminated"); 36 37 namespace { 38 //===--------------------------------------------------------------------===// 39 // DeadInstElimination pass implementation 40 // 41 struct DeadInstElimination : public BasicBlockPass { 42 static char ID; // Pass identification, replacement for typeid 43 DeadInstElimination() : BasicBlockPass(ID) { 44 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry()); 45 } 46 bool runOnBasicBlock(BasicBlock &BB) override { 47 if (skipBasicBlock(BB)) 48 return false; 49 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 50 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr; 51 bool Changed = false; 52 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 53 Instruction *Inst = &*DI++; 54 if (isInstructionTriviallyDead(Inst, TLI)) { 55 if (!DebugCounter::shouldExecute(DCECounter)) 56 continue; 57 salvageDebugInfo(*Inst); 58 Inst->eraseFromParent(); 59 Changed = true; 60 ++DIEEliminated; 61 } 62 } 63 return Changed; 64 } 65 66 void getAnalysisUsage(AnalysisUsage &AU) const override { 67 AU.setPreservesCFG(); 68 } 69 }; 70 } 71 72 char DeadInstElimination::ID = 0; 73 INITIALIZE_PASS(DeadInstElimination, "die", 74 "Dead Instruction Elimination", false, false) 75 76 Pass *llvm::createDeadInstEliminationPass() { 77 return new DeadInstElimination(); 78 } 79 80 static bool DCEInstruction(Instruction *I, 81 SmallSetVector<Instruction *, 16> &WorkList, 82 const TargetLibraryInfo *TLI) { 83 if (isInstructionTriviallyDead(I, TLI)) { 84 if (!DebugCounter::shouldExecute(DCECounter)) 85 return false; 86 87 salvageDebugInfo(*I); 88 89 // Null out all of the instruction's operands to see if any operand becomes 90 // dead as we go. 91 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 92 Value *OpV = I->getOperand(i); 93 I->setOperand(i, nullptr); 94 95 if (!OpV->use_empty() || I == OpV) 96 continue; 97 98 // If the operand is an instruction that became dead as we nulled out the 99 // operand, and if it is 'trivially' dead, delete it in a future loop 100 // iteration. 101 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 102 if (isInstructionTriviallyDead(OpI, TLI)) 103 WorkList.insert(OpI); 104 } 105 106 I->eraseFromParent(); 107 ++DCEEliminated; 108 return true; 109 } 110 return false; 111 } 112 113 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) { 114 bool MadeChange = false; 115 SmallSetVector<Instruction *, 16> WorkList; 116 // Iterate over the original function, only adding insts to the worklist 117 // if they actually need to be revisited. This avoids having to pre-init 118 // the worklist with the entire function's worth of instructions. 119 for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) { 120 Instruction *I = &*FI; 121 ++FI; 122 123 // We're visiting this instruction now, so make sure it's not in the 124 // worklist from an earlier visit. 125 if (!WorkList.count(I)) 126 MadeChange |= DCEInstruction(I, WorkList, TLI); 127 } 128 129 while (!WorkList.empty()) { 130 Instruction *I = WorkList.pop_back_val(); 131 MadeChange |= DCEInstruction(I, WorkList, TLI); 132 } 133 return MadeChange; 134 } 135 136 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) { 137 if (!eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F))) 138 return PreservedAnalyses::all(); 139 140 PreservedAnalyses PA; 141 PA.preserveSet<CFGAnalyses>(); 142 return PA; 143 } 144 145 namespace { 146 struct DCELegacyPass : public FunctionPass { 147 static char ID; // Pass identification, replacement for typeid 148 DCELegacyPass() : FunctionPass(ID) { 149 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry()); 150 } 151 152 bool runOnFunction(Function &F) override { 153 if (skipFunction(F)) 154 return false; 155 156 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 157 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr; 158 159 return eliminateDeadCode(F, TLI); 160 } 161 162 void getAnalysisUsage(AnalysisUsage &AU) const override { 163 AU.setPreservesCFG(); 164 } 165 }; 166 } 167 168 char DCELegacyPass::ID = 0; 169 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false) 170 171 FunctionPass *llvm::createDeadCodeEliminationPass() { 172 return new DCELegacyPass(); 173 } 174