contrib/llvm-project/llvm/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/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"
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "dce"
  33
  34 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
  35 STATISTIC(DCEEliminated, "Number of insts removed");
  36 DEBUG_COUNTER(DCECounter, "dce-transform",
  37               "Controls which instructions are eliminated");
  38
  39 namespace {
  40   //===--------------------------------------------------------------------===//
  41   // DeadInstElimination pass implementation
  42   //
  43 struct 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
  77 char DeadInstElimination::ID = 0;
  78 INITIALIZE_PASS(DeadInstElimination, "die",
  79                 "Dead Instruction Elimination", false, false)
  80
  81 Pass *llvm::createDeadInstEliminationPass() {
  82   return new DeadInstElimination();
  83 }
  84
  85 //===--------------------------------------------------------------------===//
  86 // RedundantDbgInstElimination pass implementation
  87 //
  88
  89 namespace {
  90 struct 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
 110 char RedundantDbgInstElimination::ID = 0;
 111 INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim",
 112                 "Redundant Dbg Instruction Elimination", false, false)
 113
 114 Pass *llvm::createRedundantDbgInstEliminationPass() {
 115   return new RedundantDbgInstElimination();
 116 }
 117
 118 //===--------------------------------------------------------------------===//
 119 // DeadCodeElimination pass implementation
 120 //
 121
 122 static 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
 155 static 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
 178 PreservedAnalyses 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
 187 namespace {
 188 struct 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
 210 char DCELegacyPass::ID = 0;
 211 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
 212
 213 FunctionPass *llvm::createDeadCodeEliminationPass() {
 214   return new DCELegacyPass();
 215 }