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.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"
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "dce"
  30
  31 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
  32 STATISTIC(DCEEliminated, "Number of insts removed");
  33
  34 namespace {
  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
  66 char DeadInstElimination::ID = 0;
  67 INITIALIZE_PASS(DeadInstElimination, "die",
  68                 "Dead Instruction Elimination", false, false)
  69
  70 Pass *llvm::createDeadInstEliminationPass() {
  71   return new DeadInstElimination();
  72 }
  73
  74
  75 namespace {
  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
  93 char DCE::ID = 0;
  94 INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false)
  95
  96 static 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
 124 bool 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
 153 FunctionPass *llvm::createDeadCodeEliminationPass() {
 154   return new DCE();
 155 }
 156