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