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.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/IR/InstIterator.h" 22 #include "llvm/IR/Instruction.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Analysis/TargetLibraryInfo.h" 25 #include "llvm/Transforms/Utils/Local.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "dce" 29 30 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 31 STATISTIC(DCEEliminated, "Number of insts removed"); 32 33 namespace { 34 //===--------------------------------------------------------------------===// 35 // DeadInstElimination pass implementation 36 // 37 struct DeadInstElimination : public BasicBlockPass { 38 static char ID; // Pass identification, replacement for typeid 39 DeadInstElimination() : BasicBlockPass(ID) { 40 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry()); 41 } 42 bool runOnBasicBlock(BasicBlock &BB) override { 43 if (skipOptnoneFunction(BB)) 44 return false; 45 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 46 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr; 47 bool Changed = false; 48 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 49 Instruction *Inst = DI++; 50 if (isInstructionTriviallyDead(Inst, TLI)) { 51 Inst->eraseFromParent(); 52 Changed = true; 53 ++DIEEliminated; 54 } 55 } 56 return Changed; 57 } 58 59 void getAnalysisUsage(AnalysisUsage &AU) const override { 60 AU.setPreservesCFG(); 61 } 62 }; 63 } // namespace 64 65 char DeadInstElimination::ID = 0; 66 INITIALIZE_PASS(DeadInstElimination, "die", 67 "Dead Instruction Elimination", false, false) 68 69 Pass *llvm::createDeadInstEliminationPass() { 70 return new DeadInstElimination(); 71 } 72 73 74 namespace { 75 //===--------------------------------------------------------------------===// 76 // DeadCodeElimination pass implementation 77 // 78 struct DCE : public FunctionPass { 79 static char ID; // Pass identification, replacement for typeid 80 DCE() : FunctionPass(ID) { 81 initializeDCEPass(*PassRegistry::getPassRegistry()); 82 } 83 84 bool runOnFunction(Function &F) override; 85 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 AU.setPreservesCFG(); 88 } 89 }; 90 } // namespace 91 92 char DCE::ID = 0; 93 INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false) 94 95 bool DCE::runOnFunction(Function &F) { 96 if (skipOptnoneFunction(F)) 97 return false; 98 99 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 100 TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr; 101 102 // Start out with all of the instructions in the worklist... 103 std::vector<Instruction*> WorkList; 104 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 105 WorkList.push_back(&*i); 106 107 // Loop over the worklist finding instructions that are dead. If they are 108 // dead make them drop all of their uses, making other instructions 109 // potentially dead, and work until the worklist is empty. 110 // 111 bool MadeChange = false; 112 while (!WorkList.empty()) { 113 Instruction *I = WorkList.back(); 114 WorkList.pop_back(); 115 116 if (isInstructionTriviallyDead(I, TLI)) { // If the instruction is dead. 117 // Loop over all of the values that the instruction uses, if there are 118 // instructions being used, add them to the worklist, because they might 119 // go dead after this one is removed. 120 // 121 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 122 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 123 WorkList.push_back(Used); 124 125 // Remove the instruction. 126 I->eraseFromParent(); 127 128 // Remove the instruction from the worklist if it still exists in it. 129 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I), 130 WorkList.end()); 131 132 MadeChange = true; 133 ++DCEEliminated; 134 } 135 } 136 return MadeChange; 137 } 138 139 FunctionPass *llvm::createDeadCodeEliminationPass() { 140 return new DCE(); 141 } 142 143