lib/Transforms/Scalar/DCE.cpp

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