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