Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- RDFDeadCode.cpp --------------------------------------------------===//
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
// RDF-based generic dead code elimination.
11
12
#include "RDFDeadCode.h"
13
#include "RDFGraph.h"
14
#include "RDFLiveness.h"
15
16
#include "llvm/ADT/SetVector.h"
17
#include "llvm/CodeGen/MachineBasicBlock.h"
18
#include "llvm/CodeGen/MachineFunction.h"
19
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
21
#include <queue>
22
23
using namespace llvm;
24
using namespace rdf;
25
26
// This drastically improves execution time in "collect" over using
27
// SetVector as a work queue, and popping the first element from it.
28
template<typename T> struct DeadCodeElimination::SetQueue {
29
859
  SetQueue() : Set(), Queue() {}
30
31
31.5k
  bool empty() const {
32
31.5k
    return Queue.empty();
33
31.5k
  }
34
30.7k
  T pop_front() {
35
30.7k
    T V = Queue.front();
36
30.7k
    Queue.pop();
37
30.7k
    Set.erase(V);
38
30.7k
    return V;
39
30.7k
  }
40
42.4k
  void push_back(T V) {
41
42.4k
    if (Set.count(V))
42
11.7k
      return;
43
30.7k
    Queue.push(V);
44
30.7k
    Set.insert(V);
45
30.7k
  }
46
47
private:
48
  DenseSet<T> Set;
49
  std::queue<T> Queue;
50
};
51
52
53
// Check if the given instruction has observable side-effects, i.e. if
54
// it should be considered "live". It is safe for this function to be
55
// overly conservative (i.e. return "true" for all instructions), but it
56
// is not safe to return "false" for an instruction that should not be
57
// considered removable.
58
23.4k
bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
59
23.4k
  if (
MI->mayStore() || 23.4k
MI->isBranch()19.2k
||
MI->isCall()15.0k
||
MI->isReturn()14.6k
)
60
8.81k
    return true;
61
14.6k
  
if (14.6k
MI->hasOrderedMemoryRef() || 14.6k
MI->hasUnmodeledSideEffects()13.2k
)
62
1.37k
    return true;
63
13.2k
  
if (13.2k
MI->isPHI()13.2k
)
64
0
    return false;
65
13.2k
  
for (auto &Op : MI->operands()) 13.2k
{
66
38.7k
    if (
Op.isReg() && 38.7k
MRI.isReserved(Op.getReg())27.5k
)
67
1.41k
      return true;
68
37.3k
    
if (37.3k
Op.isRegMask()37.3k
) {
69
0
      const uint32_t *BM = Op.getRegMask();
70
0
      for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); 
R != RN0
;
++R0
) {
71
0
        if (BM[R/32] & (1u << (R%32)))
72
0
          continue;
73
0
        
if (0
MRI.isReserved(R)0
)
74
0
          return true;
75
0
      }
76
0
    }
77
38.7k
  }
78
11.8k
  return false;
79
23.4k
}
80
81
void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
82
15.8k
      SetQueue<NodeId> &WorkQ) {
83
15.8k
  if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
84
4.14k
    return;
85
11.7k
  
if (11.7k
!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())11.7k
)
86
5.92k
    return;
87
5.80k
  
for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 5.80k
{
88
13.6k
    if (!LiveNodes.count(RA.Id))
89
13.6k
      WorkQ.push_back(RA.Id);
90
13.6k
  }
91
15.8k
}
92
93
void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
94
14.3k
      SetQueue<NodeId> &WorkQ) {
95
14.3k
  NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
96
18.3k
  for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
97
18.3k
    if (!LiveNodes.count(UA.Id))
98
18.2k
      WorkQ.push_back(UA.Id);
99
18.3k
  }
100
14.3k
  for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
101
17.3k
    LiveNodes.insert(TA.Id);
102
14.3k
}
103
104
void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
105
16.3k
      SetQueue<NodeId> &WorkQ) {
106
15.5k
  for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
107
15.5k
    if (!LiveNodes.count(DA.Id))
108
10.6k
      WorkQ.push_back(DA.Id);
109
15.5k
  }
110
16.3k
}
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
859
bool DeadCodeElimination::collect() {
116
859
  // This function works by first finding all live nodes. The dead nodes
117
859
  // are then the complement of the set of live nodes.
118
859
  //
119
859
  // Assume that all nodes are dead. Identify instructions which must be
120
859
  // considered live, i.e. instructions with observable side-effects, such
121
859
  // as calls and stores. All arguments of such instructions are considered
122
859
  // live. For each live def, all operands used in the corresponding
123
859
  // instruction are considered live. For each live use, all its reaching
124
859
  // defs are considered live.
125
859
  LiveNodes.clear();
126
859
  SetQueue<NodeId> WorkQ;
127
859
  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
128
2.05k
    for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
129
15.8k
      scanInstr(IA, WorkQ);
130
859
131
31.5k
  while (
!WorkQ.empty()31.5k
) {
132
30.7k
    NodeId N = WorkQ.pop_front();
133
30.7k
    LiveNodes.insert(N);
134
30.7k
    auto RA = DFG.addr<RefNode*>(N);
135
30.7k
    if (DFG.IsDef(RA))
136
14.3k
      processDef(RA, WorkQ);
137
30.7k
    else
138
16.3k
      processUse(RA, WorkQ);
139
30.7k
  }
140
859
141
859
  if (
trace()859
) {
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
859
149
10.0k
  auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
150
10.0k
    for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
151
10.0k
      
if (10.0k
LiveNodes.count(DA.Id)10.0k
)
152
8.11k
        return false;
153
1.94k
    return true;
154
1.94k
  };
155
859
156
2.05k
  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
157
15.8k
    for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
158
15.8k
      for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
159
36.9k
        
if (36.9k
!LiveNodes.count(RA.Id)36.9k
)
160
6.12k
          DeadNodes.insert(RA.Id);
161
15.8k
      if (DFG.IsCode<NodeAttrs::Stmt>(IA))
162
11.7k
        
if (11.7k
isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())11.7k
)
163
5.80k
          continue;
164
10.0k
      
if (10.0k
IsDead(IA)10.0k
) {
165
1.94k
        DeadInstrs.insert(IA.Id);
166
1.94k
        if (trace())
167
0
          dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
168
1.94k
      }
169
15.8k
    }
170
2.05k
  }
171
859
172
859
  return !DeadNodes.empty();
173
859
}
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
180
bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
179
180
  if (Nodes.empty())
180
0
    return false;
181
180
182
180
  // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
183
180
  // are included directly, for each InstrNode in Nodes, include the set
184
180
  // of all RefNodes from it.
185
180
  NodeList DRNs, DINs;
186
1.94k
  for (auto I : Nodes) {
187
1.94k
    auto BA = DFG.addr<NodeBase*>(I);
188
1.94k
    uint16_t Type = BA.Addr->getType();
189
1.94k
    if (
Type == NodeAttrs::Ref1.94k
) {
190
2
      DRNs.push_back(DFG.addr<RefNode*>(I));
191
2
      continue;
192
2
    }
193
1.94k
194
1.94k
    // If it's a code node, add all ref nodes from it.
195
1.94k
    uint16_t Kind = BA.Addr->getKind();
196
1.94k
    if (
Kind == NodeAttrs::Stmt || 1.94k
Kind == NodeAttrs::Phi1.88k
) {
197
1.94k
      for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
198
6.12k
        DRNs.push_back(N);
199
1.94k
      DINs.push_back(DFG.addr<InstrNode*>(I));
200
0
    } else {
201
0
      llvm_unreachable("Unexpected code node");
202
0
      return false;
203
180
    }
204
1.94k
  }
205
180
206
180
  // Sort the list so that use nodes are removed first. This makes the
207
180
  // "unlink" functions a bit faster.
208
180
  
auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool 180
{
209
40.7k
    uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
210
40.7k
    if (
KindA == NodeAttrs::Use && 40.7k
KindB == NodeAttrs::Def30.1k
)
211
4.57k
      return true;
212
36.1k
    
if (36.1k
KindA == NodeAttrs::Def && 36.1k
KindB == NodeAttrs::Use10.6k
)
213
745
      return false;
214
35.4k
    return A.Id < B.Id;
215
35.4k
  };
216
180
  std::sort(DRNs.begin(), DRNs.end(), UsesFirst);
217
180
218
180
  if (trace())
219
0
    dbgs() << "Removing dead ref nodes:\n";
220
6.12k
  for (NodeAddr<RefNode*> RA : DRNs) {
221
6.12k
    if (trace())
222
0
      dbgs() << "  " << PrintNode<RefNode*>(RA, DFG) << '\n';
223
6.12k
    if (DFG.IsUse(RA))
224
4.17k
      DFG.unlinkUse(RA, true);
225
1.95k
    else 
if (1.95k
DFG.IsDef(RA)1.95k
)
226
1.95k
      DFG.unlinkDef(RA, true);
227
6.12k
  }
228
180
229
180
  // Now, remove all dead instruction nodes.
230
1.94k
  for (NodeAddr<InstrNode*> IA : DINs) {
231
1.94k
    NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
232
1.94k
    BA.Addr->removeMember(IA, DFG);
233
1.94k
    if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
234
1.88k
      continue;
235
58
236
58
    MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
237
58
    if (trace())
238
0
      dbgs() << "erasing: " << *MI;
239
1.94k
    MI->eraseFromParent();
240
1.94k
  }
241
180
  return true;
242
180
}