Coverage Report

Created: 2019-07-24 05:18

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