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