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