Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- RDFDeadCode.cpp --------------------------------------------------===//
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
// RDF-based generic dead code elimination.
10
11
#include "RDFDeadCode.h"
12
#include "RDFGraph.h"
13
#include "RDFLiveness.h"
14
15
#include "llvm/ADT/SetVector.h"
16
#include "llvm/CodeGen/MachineBasicBlock.h"
17
#include "llvm/CodeGen/MachineFunction.h"
18
#include "llvm/CodeGen/MachineRegisterInfo.h"
19
20
#include <queue>
21
22
using namespace llvm;
23
using namespace rdf;
24
25
// This drastically improves execution time in "collect" over using
26
// SetVector as a work queue, and popping the first element from it.
27
template<typename T> struct DeadCodeElimination::SetQueue {
28
3.34k
  SetQueue() : Set(), Queue() {}
29
30
93.0k
  bool empty() const {
31
93.0k
    return Queue.empty();
32
93.0k
  }
33
89.6k
  T pop_front() {
34
89.6k
    T V = Queue.front();
35
89.6k
    Queue.pop();
36
89.6k
    Set.erase(V);
37
89.6k
    return V;
38
89.6k
  }
39
125k
  void push_back(T V) {
40
125k
    if (Set.count(V))
41
36.3k
      return;
42
89.6k
    Queue.push(V);
43
89.6k
    Set.insert(V);
44
89.6k
  }
45
46
private:
47
  DenseSet<T> Set;
48
  std::queue<T> Queue;
49
};
50
51
52
// Check if the given instruction has observable side-effects, i.e. if
53
// it should be considered "live". It is safe for this function to be
54
// overly conservative (i.e. return "true" for all instructions), but it
55
// is not safe to return "false" for an instruction that should not be
56
// considered removable.
57
59.1k
bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
58
59.1k
  if (MI->mayStore() || 
MI->isBranch()52.6k
||
MI->isCall()41.6k
||
MI->isReturn()40.2k
)
59
18.9k
    return true;
60
40.2k
  if (MI->hasOrderedMemoryRef() || 
MI->hasUnmodeledSideEffects()38.3k
||
61
40.2k
      
MI->isPosition()38.3k
)
62
1.90k
    return true;
63
38.3k
  if (MI->isPHI())
64
0
    return false;
65
111k
  
for (auto &Op : MI->operands())38.3k
{
66
111k
    if (Op.isReg() && 
MRI.isReserved(Op.getReg())85.6k
)
67
4.39k
      return true;
68
107k
    if (Op.isRegMask()) {
69
0
      const uint32_t *BM = Op.getRegMask();
70
0
      for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN; ++R) {
71
0
        if (BM[R/32] & (1u << (R%32)))
72
0
          continue;
73
0
        if (MRI.isReserved(R))
74
0
          return true;
75
0
      }
76
0
    }
77
107k
  }
78
38.3k
  
return false33.9k
;
79
38.3k
}
80
81
void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
82
41.3k
      SetQueue<NodeId> &WorkQ) {
83
41.3k
  if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
84
11.8k
    return;
85
29.5k
  if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
86
16.9k
    return;
87
36.0k
  
for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))12.6k
{
88
36.0k
    if (!LiveNodes.count(RA.Id))
89
36.0k
      WorkQ.push_back(RA.Id);
90
36.0k
  }
91
12.6k
}
92
93
void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
94
41.4k
      SetQueue<NodeId> &WorkQ) {
95
41.4k
  NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
96
59.1k
  for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
97
59.1k
    if (!LiveNodes.count(UA.Id))
98
58.9k
      WorkQ.push_back(UA.Id);
99
59.1k
  }
100
41.4k
  for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
101
51.0k
    LiveNodes.insert(TA.Id);
102
41.4k
}
103
104
void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
105
48.2k
      SetQueue<NodeId> &WorkQ) {
106
48.2k
  for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
107
46.8k
    if (!LiveNodes.count(DA.Id))
108
31.0k
      WorkQ.push_back(DA.Id);
109
46.8k
  }
110
48.2k
}
111
112
// Traverse the DFG and collect the set dead RefNodes and the set of
113
// dead instructions. Return "true" if any of these sets is non-empty,
114
// "false" otherwise.
115
3.34k
bool DeadCodeElimination::collect() {
116
3.34k
  // This function works by first finding all live nodes. The dead nodes
117
3.34k
  // are then the complement of the set of live nodes.
118
3.34k
  //
119
3.34k
  // Assume that all nodes are dead. Identify instructions which must be
120
3.34k
  // considered live, i.e. instructions with observable side-effects, such
121
3.34k
  // as calls and stores. All arguments of such instructions are considered
122
3.34k
  // live. For each live def, all operands used in the corresponding
123
3.34k
  // instruction are considered live. For each live use, all its reaching
124
3.34k
  // defs are considered live.
125
3.34k
  LiveNodes.clear();
126
3.34k
  SetQueue<NodeId> WorkQ;
127
3.34k
  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
128
5.54k
    for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
129
41.3k
      scanInstr(IA, WorkQ);
130
3.34k
131
93.0k
  while (!WorkQ.empty()) {
132
89.6k
    NodeId N = WorkQ.pop_front();
133
89.6k
    LiveNodes.insert(N);
134
89.6k
    auto RA = DFG.addr<RefNode*>(N);
135
89.6k
    if (DFG.IsDef(RA))
136
41.4k
      processDef(RA, WorkQ);
137
48.2k
    else
138
48.2k
      processUse(RA, WorkQ);
139
89.6k
  }
140
3.34k
141
3.34k
  if (trace()) {
142
0
    dbgs() << "Live nodes:\n";
143
0
    for (NodeId N : LiveNodes) {
144
0
      auto RA = DFG.addr<RefNode*>(N);
145
0
      dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
146
0
    }
147
0
  }
148
3.34k
149
28.7k
  auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
150
28.7k
    for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
151
28.7k
      if (LiveNodes.count(DA.Id))
152
24.6k
        return false;
153
28.7k
    
return true4.12k
;
154
28.7k
  };
155
3.34k
156
5.54k
  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
157
41.3k
    for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
158
41.3k
      for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
159
103k
        if (!LiveNodes.count(RA.Id))
160
13.0k
          DeadNodes.insert(RA.Id);
161
41.3k
      if (DFG.IsCode<NodeAttrs::Stmt>(IA))
162
29.5k
        if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
163
12.6k
          continue;
164
28.7k
      if (IsDead(IA)) {
165
4.12k
        DeadInstrs.insert(IA.Id);
166
4.12k
        if (trace())
167
0
          dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
168
4.12k
      }
169
28.7k
    }
170
5.54k
  }
171
3.34k
172
3.34k
  return !DeadNodes.empty();
173
3.34k
}
174
175
// Erase the nodes given in the Nodes set from DFG. In addition to removing
176
// them from the DFG, if a node corresponds to a statement, the corresponding
177
// machine instruction is erased from the function.
178
410
bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
179
410
  if (Nodes.empty())
180
18
    return false;
181
392
182
392
  // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
183
392
  // are included directly, for each InstrNode in Nodes, include the set
184
392
  // of all RefNodes from it.
185
392
  NodeList DRNs, DINs;
186
4.13k
  for (auto I : Nodes) {
187
4.13k
    auto BA = DFG.addr<NodeBase*>(I);
188
4.13k
    uint16_t Type = BA.Addr->getType();
189
4.13k
    if (Type == NodeAttrs::Ref) {
190
9
      DRNs.push_back(DFG.addr<RefNode*>(I));
191
9
      continue;
192
9
    }
193
4.12k
194
4.12k
    // If it's a code node, add all ref nodes from it.
195
4.12k
    uint16_t Kind = BA.Addr->getKind();
196
4.12k
    if (Kind == NodeAttrs::Stmt || 
Kind == NodeAttrs::Phi4.09k
) {
197
4.12k
      for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
198
13.0k
        DRNs.push_back(N);
199
4.12k
      DINs.push_back(DFG.addr<InstrNode*>(I));
200
4.12k
    } else {
201
0
      llvm_unreachable("Unexpected code node");
202
0
      return false;
203
0
    }
204
4.12k
  }
205
392
206
392
  // Sort the list so that use nodes are removed first. This makes the
207
392
  // "unlink" functions a bit faster.
208
91.5k
  
auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool 392
{
209
91.5k
    uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
210
91.5k
    if (KindA == NodeAttrs::Use && 
KindB == NodeAttrs::Def67.0k
)
211
8.83k
      return true;
212
82.6k
    if (KindA == NodeAttrs::Def && 
KindB == NodeAttrs::Use24.4k
)
213
1.71k
      return false;
214
80.9k
    return A.Id < B.Id;
215
80.9k
  };
216
392
  llvm::sort(DRNs, UsesFirst);
217
392
218
392
  if (trace())
219
0
    dbgs() << "Removing dead ref nodes:\n";
220
13.0k
  for (NodeAddr<RefNode*> RA : DRNs) {
221
13.0k
    if (trace())
222
0
      dbgs() << "  " << PrintNode<RefNode*>(RA, DFG) << '\n';
223
13.0k
    if (DFG.IsUse(RA))
224
8.88k
      DFG.unlinkUse(RA, true);
225
4.13k
    else if (DFG.IsDef(RA))
226
4.13k
      DFG.unlinkDef(RA, true);
227
13.0k
  }
228
392
229
392
  // Now, remove all dead instruction nodes.
230
4.12k
  for (NodeAddr<InstrNode*> IA : DINs) {
231
4.12k
    NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
232
4.12k
    BA.Addr->removeMember(IA, DFG);
233
4.12k
    if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
234
4.09k
      continue;
235
29
236
29
    MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
237
29
    if (trace())
238
0
      dbgs() << "erasing: " << *MI;
239
29
    MI->eraseFromParent();
240
29
  }
241
392
  return true;
242
392
}