Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonRDFOpt.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
#include "HexagonInstrInfo.h"
10
#include "HexagonSubtarget.h"
11
#include "MCTargetDesc/HexagonBaseInfo.h"
12
#include "RDFCopy.h"
13
#include "RDFDeadCode.h"
14
#include "RDFGraph.h"
15
#include "RDFLiveness.h"
16
#include "RDFRegisters.h"
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/STLExtras.h"
19
#include "llvm/ADT/SetVector.h"
20
#include "llvm/CodeGen/MachineDominanceFrontier.h"
21
#include "llvm/CodeGen/MachineDominators.h"
22
#include "llvm/CodeGen/MachineFunction.h"
23
#include "llvm/CodeGen/MachineFunctionPass.h"
24
#include "llvm/CodeGen/MachineInstr.h"
25
#include "llvm/CodeGen/MachineOperand.h"
26
#include "llvm/CodeGen/MachineRegisterInfo.h"
27
#include "llvm/Pass.h"
28
#include "llvm/Support/CommandLine.h"
29
#include "llvm/Support/Compiler.h"
30
#include "llvm/Support/Debug.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Support/raw_ostream.h"
33
#include <cassert>
34
#include <limits>
35
#include <utility>
36
37
using namespace llvm;
38
using namespace rdf;
39
40
namespace llvm {
41
42
  void initializeHexagonRDFOptPass(PassRegistry&);
43
  FunctionPass *createHexagonRDFOpt();
44
45
} // end namespace llvm
46
47
static unsigned RDFCount = 0;
48
49
static cl::opt<unsigned> RDFLimit("rdf-limit",
50
    cl::init(std::numeric_limits<unsigned>::max()));
51
static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
52
53
namespace {
54
55
  class HexagonRDFOpt : public MachineFunctionPass {
56
  public:
57
860
    HexagonRDFOpt() : MachineFunctionPass(ID) {}
58
59
853
    void getAnalysisUsage(AnalysisUsage &AU) const override {
60
853
      AU.addRequired<MachineDominatorTree>();
61
853
      AU.addRequired<MachineDominanceFrontier>();
62
853
      AU.setPreservesAll();
63
853
      MachineFunctionPass::getAnalysisUsage(AU);
64
853
    }
65
66
4.21k
    StringRef getPassName() const override {
67
4.21k
      return "Hexagon RDF optimizations";
68
4.21k
    }
69
70
    bool runOnMachineFunction(MachineFunction &MF) override;
71
72
853
    MachineFunctionProperties getRequiredProperties() const override {
73
853
      return MachineFunctionProperties().set(
74
853
          MachineFunctionProperties::Property::NoVRegs);
75
853
    }
76
77
    static char ID;
78
79
  private:
80
    MachineDominatorTree *MDT;
81
    MachineRegisterInfo *MRI;
82
  };
83
84
struct HexagonCP : public CopyPropagation {
85
3.34k
  HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
86
87
  bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
88
};
89
90
struct HexagonDCE : public DeadCodeElimination {
91
  HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
92
3.34k
    : DeadCodeElimination(G, MRI) {}
93
94
  bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
95
  void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
96
97
  bool run();
98
};
99
100
} // end anonymous namespace
101
102
char HexagonRDFOpt::ID = 0;
103
104
101k
INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
105
101k
      "Hexagon RDF optimizations", false, false)
106
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
107
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
108
101k
INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
109
      "Hexagon RDF optimizations", false, false)
110
111
29.5k
bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
112
29.5k
  auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
113
2
    EM.insert(std::make_pair(DstR, SrcR));
114
2
  };
115
29.5k
116
29.5k
  DataFlowGraph &DFG = getDFG();
117
29.5k
  unsigned Opc = MI->getOpcode();
118
29.5k
  switch (Opc) {
119
29.5k
    case Hexagon::A2_combinew: {
120
1
      const MachineOperand &DstOp = MI->getOperand(0);
121
1
      const MachineOperand &HiOp = MI->getOperand(1);
122
1
      const MachineOperand &LoOp = MI->getOperand(2);
123
1
      assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
124
1
      mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
125
1
              DFG.makeRegRef(HiOp.getReg(),  HiOp.getSubReg()));
126
1
      mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
127
1
              DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
128
1
      return true;
129
29.5k
    }
130
29.5k
    case Hexagon::A2_addi: {
131
959
      const MachineOperand &A = MI->getOperand(2);
132
959
      if (!A.isImm() || 
A.getImm() != 0948
)
133
959
        return false;
134
0
      LLVM_FALLTHROUGH;
135
0
    }
136
0
    case Hexagon::A2_tfr: {
137
0
      const MachineOperand &DstOp = MI->getOperand(0);
138
0
      const MachineOperand &SrcOp = MI->getOperand(1);
139
0
      mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
140
0
              DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
141
0
      return true;
142
28.6k
    }
143
28.6k
  }
144
28.6k
145
28.6k
  return CopyPropagation::interpretAsCopy(MI, EM);
146
28.6k
}
147
148
3.34k
bool HexagonDCE::run() {
149
3.34k
  bool Collected = collect();
150
3.34k
  if (!Collected)
151
2.93k
    return false;
152
410
153
410
  const SetVector<NodeId> &DeadNodes = getDeadNodes();
154
410
  const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
155
410
156
410
  using RefToInstrMap = DenseMap<NodeId, NodeId>;
157
410
158
410
  RefToInstrMap R2I;
159
410
  SetVector<NodeId> PartlyDead;
160
410
  DataFlowGraph &DFG = getDFG();
161
410
162
2.30k
  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
163
12.4k
    for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
164
12.4k
      NodeAddr<StmtNode*> SA = TA;
165
31.9k
      for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
166
31.9k
        R2I.insert(std::make_pair(RA.Id, SA.Id));
167
31.9k
        if (DFG.IsDef(RA) && 
DeadNodes.count(RA.Id)15.8k
)
168
60
          if (!DeadInstrs.count(SA.Id))
169
29
            PartlyDead.insert(SA.Id);
170
31.9k
      }
171
12.4k
    }
172
2.30k
  }
173
410
174
410
  // Nodes to remove.
175
410
  SetVector<NodeId> Remove = DeadInstrs;
176
410
177
410
  bool Changed = false;
178
410
  for (NodeId N : PartlyDead) {
179
29
    auto SA = DFG.addr<StmtNode*>(N);
180
29
    if (trace())
181
0
      dbgs() << "Partly dead: " << *SA.Addr->getCode();
182
29
    Changed |= rewrite(SA, Remove);
183
29
  }
184
410
185
410
  return erase(Remove) || 
Changed18
;
186
410
}
187
188
9
void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
189
9
  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
190
9
191
27
  auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
192
54
    for (unsigned i = 0, n = MI->getNumOperands(); i != n; 
++i27
)
193
54
      if (&MI->getOperand(i) == &Op)
194
27
        return i;
195
27
    
llvm_unreachable0
("Invalid operand");
196
27
  };
197
9
  DenseMap<NodeId,unsigned> OpMap;
198
9
  DataFlowGraph &DFG = getDFG();
199
9
  NodeList Refs = IA.Addr->members(DFG);
200
9
  for (NodeAddr<RefNode*> RA : Refs)
201
27
    OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
202
9
203
9
  MI->RemoveOperand(OpNum);
204
9
205
27
  for (NodeAddr<RefNode*> RA : Refs) {
206
27
    unsigned N = OpMap[RA.Id];
207
27
    if (N < OpNum)
208
9
      RA.Addr->setRegRef(&MI->getOperand(N), DFG);
209
18
    else if (N > OpNum)
210
9
      RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
211
27
  }
212
9
}
213
214
29
bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
215
29
  if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
216
0
    return false;
217
29
  DataFlowGraph &DFG = getDFG();
218
29
  MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
219
29
  auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
220
29
  if (HII.getAddrMode(MI) != HexagonII::PostInc)
221
6
    return false;
222
23
  unsigned Opc = MI.getOpcode();
223
23
  unsigned OpNum, NewOpc;
224
23
  switch (Opc) {
225
23
    case Hexagon::L2_loadri_pi:
226
3
      NewOpc = Hexagon::L2_loadri_io;
227
3
      OpNum = 1;
228
3
      break;
229
23
    case Hexagon::L2_loadrd_pi:
230
0
      NewOpc = Hexagon::L2_loadrd_io;
231
0
      OpNum = 1;
232
0
      break;
233
23
    case Hexagon::V6_vL32b_pi:
234
6
      NewOpc = Hexagon::V6_vL32b_ai;
235
6
      OpNum = 1;
236
6
      break;
237
23
    case Hexagon::S2_storeri_pi:
238
0
      NewOpc = Hexagon::S2_storeri_io;
239
0
      OpNum = 0;
240
0
      break;
241
23
    case Hexagon::S2_storerd_pi:
242
0
      NewOpc = Hexagon::S2_storerd_io;
243
0
      OpNum = 0;
244
0
      break;
245
23
    case Hexagon::V6_vS32b_pi:
246
0
      NewOpc = Hexagon::V6_vS32b_ai;
247
0
      OpNum = 0;
248
0
      break;
249
23
    default:
250
14
      return false;
251
9
  }
252
9
  auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
253
9
    return getDeadNodes().count(DA.Id);
254
9
  };
255
9
  NodeList Defs;
256
9
  MachineOperand &Op = MI.getOperand(OpNum);
257
18
  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
258
18
    if (&DA.Addr->getOp() != &Op)
259
9
      continue;
260
9
    Defs = DFG.getRelatedRefs(IA, DA);
261
9
    if (!llvm::all_of(Defs, IsDead))
262
0
      return false;
263
9
    break;
264
9
  }
265
9
266
9
  // Mark all nodes in Defs for removal.
267
9
  for (auto D : Defs)
268
9
    Remove.insert(D.Id);
269
9
270
9
  if (trace())
271
0
    dbgs() << "Rewriting: " << MI;
272
9
  MI.setDesc(HII.get(NewOpc));
273
9
  MI.getOperand(OpNum+2).setImm(0);
274
9
  removeOperand(IA, OpNum);
275
9
  if (trace())
276
0
    dbgs() << "       to: " << MI;
277
9
278
9
  return true;
279
9
}
280
281
3.35k
bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
282
3.35k
  if (skipFunction(MF.getFunction()))
283
10
    return false;
284
3.34k
285
3.34k
  if (RDFLimit.getPosition()) {
286
0
    if (RDFCount >= RDFLimit)
287
0
      return false;
288
0
    RDFCount++;
289
0
  }
290
3.34k
291
3.34k
  MDT = &getAnalysis<MachineDominatorTree>();
292
3.34k
  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
293
3.34k
  const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
294
3.34k
  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
295
3.34k
  MRI = &MF.getRegInfo();
296
3.34k
  bool Changed;
297
3.34k
298
3.34k
  if (RDFDump)
299
0
    MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
300
3.34k
301
3.34k
  TargetOperandInfo TOI(HII);
302
3.34k
  DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI);
303
3.34k
  // Dead phi nodes are necessary for copy propagation: we can add a use
304
3.34k
  // of a register in a block where it would need a phi node, but which
305
3.34k
  // was dead (and removed) during the graph build time.
306
3.34k
  G.build(BuildOptions::KeepDeadPhis);
307
3.34k
308
3.34k
  if (RDFDump)
309
0
    dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
310
0
           << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
311
3.34k
  HexagonCP CP(G);
312
3.34k
  CP.trace(RDFDump);
313
3.34k
  Changed = CP.run();
314
3.34k
315
3.34k
  if (RDFDump)
316
0
    dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
317
0
           << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
318
3.34k
  HexagonDCE DCE(G, *MRI);
319
3.34k
  DCE.trace(RDFDump);
320
3.34k
  Changed |= DCE.run();
321
3.34k
322
3.34k
  if (Changed) {
323
394
    if (RDFDump)
324
0
      dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
325
394
    Liveness LV(*MRI, G);
326
394
    LV.trace(RDFDump);
327
394
    LV.computeLiveIns();
328
394
    LV.resetLiveIns();
329
394
    LV.resetKills();
330
394
  }
331
3.34k
332
3.34k
  if (RDFDump)
333
0
    MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
334
3.34k
335
3.34k
  return false;
336
3.34k
}
337
338
858
FunctionPass *llvm::createHexagonRDFOpt() {
339
858
  return new HexagonRDFOpt();
340
858
}