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