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