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