lib/Transforms/Scalar/DCE.cpp

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