Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/HexagonGenPredicate.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonGenPredicate.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
#include "HexagonInstrInfo.h"
11
#include "HexagonSubtarget.h"
12
#include "llvm/ADT/SetVector.h"
13
#include "llvm/ADT/StringRef.h"
14
#include "llvm/CodeGen/MachineBasicBlock.h"
15
#include "llvm/CodeGen/MachineDominators.h"
16
#include "llvm/CodeGen/MachineFunction.h"
17
#include "llvm/CodeGen/MachineFunctionPass.h"
18
#include "llvm/CodeGen/MachineInstr.h"
19
#include "llvm/CodeGen/MachineInstrBuilder.h"
20
#include "llvm/CodeGen/MachineOperand.h"
21
#include "llvm/CodeGen/MachineRegisterInfo.h"
22
#include "llvm/IR/DebugLoc.h"
23
#include "llvm/Pass.h"
24
#include "llvm/Support/Compiler.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/ErrorHandling.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include "llvm/Target/TargetRegisterInfo.h"
29
#include <cassert>
30
#include <iterator>
31
#include <map>
32
#include <queue>
33
#include <set>
34
#include <utility>
35
36
#define DEBUG_TYPE "gen-pred"
37
38
using namespace llvm;
39
40
namespace llvm {
41
42
  void initializeHexagonGenPredicatePass(PassRegistry& Registry);
43
  FunctionPass *createHexagonGenPredicate();
44
45
} // end namespace llvm
46
47
namespace {
48
49
  struct Register {
50
    unsigned R, S;
51
52
10
    Register(unsigned r = 0, unsigned s = 0) : R(r), S(s) {}
53
5.61k
    Register(const MachineOperand &MO) : R(MO.getReg()), S(MO.getSubReg()) {}
54
55
0
    bool operator== (const Register &Reg) const {
56
0
      return R == Reg.R && S == Reg.S;
57
0
    }
58
59
687
    bool operator< (const Register &Reg) const {
60
322
      return R < Reg.R || 
(R == Reg.R && 322
S < Reg.S78
);
61
687
    }
62
  };
63
64
  struct PrintRegister {
65
    friend raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR);
66
67
0
    PrintRegister(Register R, const TargetRegisterInfo &I) : Reg(R), TRI(I) {}
68
69
  private:
70
    Register Reg;
71
    const TargetRegisterInfo &TRI;
72
  };
73
74
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR)
75
    LLVM_ATTRIBUTE_UNUSED;
76
0
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegister &PR) {
77
0
    return OS << PrintReg(PR.Reg.R, &PR.TRI, PR.Reg.S);
78
0
  }
79
80
  class HexagonGenPredicate : public MachineFunctionPass {
81
  public:
82
    static char ID;
83
84
405
    HexagonGenPredicate() : MachineFunctionPass(ID) {
85
405
      initializeHexagonGenPredicatePass(*PassRegistry::getPassRegistry());
86
405
    }
87
88
0
    StringRef getPassName() const override {
89
0
      return "Hexagon generate predicate operations";
90
0
    }
91
92
401
    void getAnalysisUsage(AnalysisUsage &AU) const override {
93
401
      AU.addRequired<MachineDominatorTree>();
94
401
      AU.addPreserved<MachineDominatorTree>();
95
401
      MachineFunctionPass::getAnalysisUsage(AU);
96
401
    }
97
98
    bool runOnMachineFunction(MachineFunction &MF) override;
99
100
  private:
101
    using VectOfInst = SetVector<MachineInstr *>;
102
    using SetOfReg = std::set<Register>;
103
    using RegToRegMap = std::map<Register, Register>;
104
105
    const HexagonInstrInfo *TII = nullptr;
106
    const HexagonRegisterInfo *TRI = nullptr;
107
    MachineRegisterInfo *MRI = nullptr;
108
    SetOfReg PredGPRs;
109
    VectOfInst PUsers;
110
    RegToRegMap G2P;
111
112
    bool isPredReg(unsigned R);
113
    void collectPredicateGPR(MachineFunction &MF);
114
    void processPredicateGPR(const Register &Reg);
115
    unsigned getPredForm(unsigned Opc);
116
    bool isConvertibleToPredForm(const MachineInstr *MI);
117
    bool isScalarCmp(unsigned Opc);
118
    bool isScalarPred(Register PredReg);
119
    Register getPredRegFor(const Register &Reg);
120
    bool convertToPredForm(MachineInstr *MI);
121
    bool eliminatePredCopies(MachineFunction &MF);
122
  };
123
124
} // end anonymous namespace
125
126
char HexagonGenPredicate::ID = 0;
127
128
405
INITIALIZE_PASS_BEGIN405
(HexagonGenPredicate, "hexagon-gen-pred",
129
405
  "Hexagon generate predicate operations", false, false)
130
405
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
131
405
INITIALIZE_PASS_END(HexagonGenPredicate, "hexagon-gen-pred",
132
  "Hexagon generate predicate operations", false, false)
133
134
2.76k
bool HexagonGenPredicate::isPredReg(unsigned R) {
135
2.76k
  if (!TargetRegisterInfo::isVirtualRegister(R))
136
1.46k
    return false;
137
1.30k
  const TargetRegisterClass *RC = MRI->getRegClass(R);
138
1.30k
  return RC == &Hexagon::PredRegsRegClass;
139
1.30k
}
140
141
110
unsigned HexagonGenPredicate::getPredForm(unsigned Opc) {
142
110
  using namespace Hexagon;
143
110
144
110
  switch (Opc) {
145
0
    case A2_and:
146
0
    case A2_andp:
147
0
      return C2_and;
148
0
    case A4_andn:
149
0
    case A4_andnp:
150
0
      return C2_andn;
151
0
    case M4_and_and:
152
0
      return C4_and_and;
153
0
    case M4_and_andn:
154
0
      return C4_and_andn;
155
0
    case M4_and_or:
156
0
      return C4_and_or;
157
0
158
0
    case A2_or:
159
0
    case A2_orp:
160
0
      return C2_or;
161
0
    case A4_orn:
162
0
    case A4_ornp:
163
0
      return C2_orn;
164
4
    case M4_or_and:
165
4
      return C4_or_and;
166
0
    case M4_or_andn:
167
0
      return C4_or_andn;
168
0
    case M4_or_or:
169
0
      return C4_or_or;
170
0
171
0
    case A2_xor:
172
0
    case A2_xorp:
173
0
      return C2_xor;
174
0
175
16
    case C2_tfrrp:
176
16
      return COPY;
177
90
  }
178
90
  // The opcode corresponding to 0 is TargetOpcode::PHI. We can use 0 here
179
90
  // to denote "none", but we need to make sure that none of the valid opcodes
180
90
  // that we return will ever be 0.
181
90
  static_assert(PHI == 0, "Use different value for <none>");
182
90
  return 0;
183
90
}
184
185
73
bool HexagonGenPredicate::isConvertibleToPredForm(const MachineInstr *MI) {
186
73
  unsigned Opc = MI->getOpcode();
187
73
  if (getPredForm(Opc) != 0)
188
11
    return true;
189
62
190
62
  // Comparisons against 0 are also convertible. This does not apply to
191
62
  // A4_rcmpeqi or A4_rcmpneqi, since they produce values 0 or 1, which
192
62
  // may not match the value that the predicate register would have if
193
62
  // it was converted to a predicate form.
194
62
  switch (Opc) {
195
28
    case Hexagon::C2_cmpeqi:
196
28
    case Hexagon::C4_cmpneqi:
197
28
      if (
MI->getOperand(2).isImm() && 28
MI->getOperand(2).getImm() == 028
)
198
28
        return true;
199
0
      break;
200
34
  }
201
34
  return false;
202
34
}
203
204
860
void HexagonGenPredicate::collectPredicateGPR(MachineFunction &MF) {
205
2.69k
  for (MachineFunction::iterator A = MF.begin(), Z = MF.end(); 
A != Z2.69k
;
++A1.83k
) {
206
1.83k
    MachineBasicBlock &B = *A;
207
16.0k
    for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); 
I != E16.0k
;
++I14.2k
) {
208
14.2k
      MachineInstr *MI = &*I;
209
14.2k
      unsigned Opc = MI->getOpcode();
210
14.2k
      switch (Opc) {
211
2.75k
        case Hexagon::C2_tfrpr:
212
2.75k
        case TargetOpcode::COPY:
213
2.75k
          if (
isPredReg(MI->getOperand(1).getReg())2.75k
) {
214
83
            Register RD = MI->getOperand(0);
215
83
            if (TargetRegisterInfo::isVirtualRegister(RD.R))
216
73
              PredGPRs.insert(RD);
217
83
          }
218
2.75k
          break;
219
14.2k
      }
220
14.2k
    }
221
1.83k
  }
222
860
}
223
224
74
void HexagonGenPredicate::processPredicateGPR(const Register &Reg) {
225
74
  DEBUG(dbgs() << __func__ << ": "
226
74
               << PrintReg(Reg.R, TRI, Reg.S) << "\n");
227
74
  using use_iterator = MachineRegisterInfo::use_iterator;
228
74
229
74
  use_iterator I = MRI->use_begin(Reg.R), E = MRI->use_end();
230
74
  if (
I == E74
) {
231
1
    DEBUG(dbgs() << "Dead reg: " << PrintReg(Reg.R, TRI, Reg.S) << '\n');
232
1
    MachineInstr *DefI = MRI->getVRegDef(Reg.R);
233
1
    DefI->eraseFromParent();
234
1
    return;
235
1
  }
236
73
237
146
  
for (; 73
I != E146
;
++I73
) {
238
73
    MachineInstr *UseI = I->getParent();
239
73
    if (isConvertibleToPredForm(UseI))
240
39
      PUsers.insert(UseI);
241
73
  }
242
74
}
243
244
39
Register HexagonGenPredicate::getPredRegFor(const Register &Reg) {
245
39
  // Create a predicate register for a given Reg. The newly created register
246
39
  // will have its value copied from Reg, so that it can be later used as
247
39
  // an operand in other instructions.
248
39
  assert(TargetRegisterInfo::isVirtualRegister(Reg.R));
249
39
  RegToRegMap::iterator F = G2P.find(Reg);
250
39
  if (F != G2P.end())
251
0
    return F->second;
252
39
253
39
  
DEBUG39
(dbgs() << __func__ << ": " << PrintRegister(Reg, *TRI));
254
39
  MachineInstr *DefI = MRI->getVRegDef(Reg.R);
255
39
  assert(DefI);
256
39
  unsigned Opc = DefI->getOpcode();
257
39
  if (
Opc == Hexagon::C2_tfrpr || 39
Opc == TargetOpcode::COPY0
) {
258
39
    assert(DefI->getOperand(0).isDef() && DefI->getOperand(1).isUse());
259
39
    Register PR = DefI->getOperand(1);
260
39
    G2P.insert(std::make_pair(Reg, PR));
261
39
    DEBUG(dbgs() << " -> " << PrintRegister(PR, *TRI) << '\n');
262
39
    return PR;
263
39
  }
264
0
265
0
  MachineBasicBlock &B = *DefI->getParent();
266
0
  DebugLoc DL = DefI->getDebugLoc();
267
0
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
268
0
  unsigned NewPR = MRI->createVirtualRegister(PredRC);
269
0
270
0
  // For convertible instructions, do not modify them, so that they can
271
0
  // be converted later.  Generate a copy from Reg to NewPR.
272
0
  if (
isConvertibleToPredForm(DefI)0
) {
273
0
    MachineBasicBlock::iterator DefIt = DefI;
274
0
    BuildMI(B, std::next(DefIt), DL, TII->get(TargetOpcode::COPY), NewPR)
275
0
      .addReg(Reg.R, 0, Reg.S);
276
0
    G2P.insert(std::make_pair(Reg, Register(NewPR)));
277
0
    DEBUG(dbgs() << " -> !" << PrintRegister(Register(NewPR), *TRI) << '\n');
278
0
    return Register(NewPR);
279
0
  }
280
0
281
0
  
llvm_unreachable0
("Invalid argument");
282
0
}
283
284
28
bool HexagonGenPredicate::isScalarCmp(unsigned Opc) {
285
28
  switch (Opc) {
286
0
    case Hexagon::C2_cmpeq:
287
0
    case Hexagon::C2_cmpgt:
288
0
    case Hexagon::C2_cmpgtu:
289
0
    case Hexagon::C2_cmpeqp:
290
0
    case Hexagon::C2_cmpgtp:
291
0
    case Hexagon::C2_cmpgtup:
292
0
    case Hexagon::C2_cmpeqi:
293
0
    case Hexagon::C2_cmpgti:
294
0
    case Hexagon::C2_cmpgtui:
295
0
    case Hexagon::C2_cmpgei:
296
0
    case Hexagon::C2_cmpgeui:
297
0
    case Hexagon::C4_cmpneqi:
298
0
    case Hexagon::C4_cmpltei:
299
0
    case Hexagon::C4_cmplteui:
300
0
    case Hexagon::C4_cmpneq:
301
0
    case Hexagon::C4_cmplte:
302
0
    case Hexagon::C4_cmplteu:
303
0
    case Hexagon::A4_cmpbeq:
304
0
    case Hexagon::A4_cmpbeqi:
305
0
    case Hexagon::A4_cmpbgtu:
306
0
    case Hexagon::A4_cmpbgtui:
307
0
    case Hexagon::A4_cmpbgt:
308
0
    case Hexagon::A4_cmpbgti:
309
0
    case Hexagon::A4_cmpheq:
310
0
    case Hexagon::A4_cmphgt:
311
0
    case Hexagon::A4_cmphgtu:
312
0
    case Hexagon::A4_cmpheqi:
313
0
    case Hexagon::A4_cmphgti:
314
0
    case Hexagon::A4_cmphgtui:
315
0
      return true;
316
28
  }
317
28
  return false;
318
28
}
319
320
28
bool HexagonGenPredicate::isScalarPred(Register PredReg) {
321
28
  std::queue<Register> WorkQ;
322
28
  WorkQ.push(PredReg);
323
28
324
28
  while (
!WorkQ.empty()28
) {
325
28
    Register PR = WorkQ.front();
326
28
    WorkQ.pop();
327
28
    const MachineInstr *DefI = MRI->getVRegDef(PR.R);
328
28
    if (!DefI)
329
0
      return false;
330
28
    unsigned DefOpc = DefI->getOpcode();
331
28
    switch (DefOpc) {
332
0
      case TargetOpcode::COPY: {
333
0
        const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
334
0
        if (MRI->getRegClass(PR.R) != PredRC)
335
0
          return false;
336
0
        // If it is a copy between two predicate registers, fall through.
337
0
        
LLVM_FALLTHROUGH0
;
338
0
      }
339
0
      case Hexagon::C2_and:
340
0
      case Hexagon::C2_andn:
341
0
      case Hexagon::C4_and_and:
342
0
      case Hexagon::C4_and_andn:
343
0
      case Hexagon::C4_and_or:
344
0
      case Hexagon::C2_or:
345
0
      case Hexagon::C2_orn:
346
0
      case Hexagon::C4_or_and:
347
0
      case Hexagon::C4_or_andn:
348
0
      case Hexagon::C4_or_or:
349
0
      case Hexagon::C4_or_orn:
350
0
      case Hexagon::C2_xor:
351
0
        // Add operands to the queue.
352
0
        for (const MachineOperand &MO : DefI->operands())
353
0
          
if (0
MO.isReg() && 0
MO.isUse()0
)
354
0
            WorkQ.push(Register(MO.getReg()));
355
0
        break;
356
0
357
0
      // All non-vector compares are ok, everything else is bad.
358
28
      default:
359
28
        return isScalarCmp(DefOpc);
360
28
    }
361
28
  }
362
28
363
0
  return true;
364
28
}
365
366
37
bool HexagonGenPredicate::convertToPredForm(MachineInstr *MI) {
367
37
  DEBUG(dbgs() << __func__ << ": " << MI << " " << *MI);
368
37
369
37
  unsigned Opc = MI->getOpcode();
370
37
  assert(isConvertibleToPredForm(MI));
371
37
  unsigned NumOps = MI->getNumOperands();
372
141
  for (unsigned i = 0; 
i < NumOps141
;
++i104
) {
373
104
    MachineOperand &MO = MI->getOperand(i);
374
104
    if (
!MO.isReg() || 104
!MO.isUse()76
)
375
65
      continue;
376
39
    Register Reg(MO);
377
39
    if (
Reg.S && 39
Reg.S != Hexagon::isub_lo0
)
378
0
      return false;
379
39
    
if (39
!PredGPRs.count(Reg)39
)
380
0
      return false;
381
104
  }
382
37
383
37
  MachineBasicBlock &B = *MI->getParent();
384
37
  DebugLoc DL = MI->getDebugLoc();
385
37
386
37
  unsigned NewOpc = getPredForm(Opc);
387
37
  // Special case for comparisons against 0.
388
37
  if (
NewOpc == 037
) {
389
28
    switch (Opc) {
390
28
      case Hexagon::C2_cmpeqi:
391
28
        NewOpc = Hexagon::C2_not;
392
28
        break;
393
0
      case Hexagon::C4_cmpneqi:
394
0
        NewOpc = TargetOpcode::COPY;
395
0
        break;
396
0
      default:
397
0
        return false;
398
28
    }
399
28
400
28
    // If it's a scalar predicate register, then all bits in it are
401
28
    // the same. Otherwise, to determine whether all bits are 0 or not
402
28
    // we would need to use any8.
403
28
    Register PR = getPredRegFor(MI->getOperand(1));
404
28
    if (!isScalarPred(PR))
405
28
      return false;
406
0
    // This will skip the immediate argument when creating the predicate
407
0
    // version instruction.
408
0
    NumOps = 2;
409
0
  }
410
37
411
37
  // Some sanity: check that def is in operand #0.
412
9
  MachineOperand &Op0 = MI->getOperand(0);
413
9
  assert(Op0.isDef());
414
9
  Register OutR(Op0);
415
9
416
9
  // Don't use getPredRegFor, since it will create an association between
417
9
  // the argument and a created predicate register (i.e. it will insert a
418
9
  // copy if a new predicate register is created).
419
9
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
420
9
  Register NewPR = MRI->createVirtualRegister(PredRC);
421
9
  MachineInstrBuilder MIB = BuildMI(B, MI, DL, TII->get(NewOpc), NewPR.R);
422
9
423
9
  // Add predicate counterparts of the GPRs.
424
20
  for (unsigned i = 1; 
i < NumOps20
;
++i11
) {
425
11
    Register GPR = MI->getOperand(i);
426
11
    Register Pred = getPredRegFor(GPR);
427
11
    MIB.addReg(Pred.R, 0, Pred.S);
428
11
  }
429
9
  DEBUG(dbgs() << "generated: " << *MIB);
430
9
431
9
  // Generate a copy-out: NewGPR = NewPR, and replace all uses of OutR
432
9
  // with NewGPR.
433
9
  const TargetRegisterClass *RC = MRI->getRegClass(OutR.R);
434
9
  unsigned NewOutR = MRI->createVirtualRegister(RC);
435
9
  BuildMI(B, MI, DL, TII->get(TargetOpcode::COPY), NewOutR)
436
9
    .addReg(NewPR.R, 0, NewPR.S);
437
9
  MRI->replaceRegWith(OutR.R, NewOutR);
438
9
  MI->eraseFromParent();
439
9
440
9
  // If the processed instruction was C2_tfrrp (i.e. Rn = Pm; Pk = Rn),
441
9
  // then the output will be a predicate register.  Do not visit the
442
9
  // users of it.
443
9
  if (
!isPredReg(NewOutR)9
) {
444
1
    Register R(NewOutR);
445
1
    PredGPRs.insert(R);
446
1
    processPredicateGPR(R);
447
1
  }
448
9
  return true;
449
37
}
450
451
860
bool HexagonGenPredicate::eliminatePredCopies(MachineFunction &MF) {
452
860
  DEBUG(dbgs() << __func__ << "\n");
453
860
  const TargetRegisterClass *PredRC = &Hexagon::PredRegsRegClass;
454
860
  bool Changed = false;
455
860
  VectOfInst Erase;
456
860
457
860
  // First, replace copies
458
860
  //   IntR = PredR1
459
860
  //   PredR2 = IntR
460
860
  // with
461
860
  //   PredR2 = PredR1
462
860
  // Such sequences can be generated when a copy-into-pred is generated from
463
860
  // a gpr register holding a result of a convertible instruction. After
464
860
  // the convertible instruction is converted, its predicate result will be
465
860
  // copied back into the original gpr.
466
860
467
1.83k
  for (MachineBasicBlock &MBB : MF) {
468
14.2k
    for (MachineInstr &MI : MBB) {
469
14.2k
      if (MI.getOpcode() != TargetOpcode::COPY)
470
11.5k
        continue;
471
2.70k
      Register DR = MI.getOperand(0);
472
2.70k
      Register SR = MI.getOperand(1);
473
2.70k
      if (!TargetRegisterInfo::isVirtualRegister(DR.R))
474
786
        continue;
475
1.91k
      
if (1.91k
!TargetRegisterInfo::isVirtualRegister(SR.R)1.91k
)
476
1.46k
        continue;
477
451
      
if (451
MRI->getRegClass(DR.R) != PredRC451
)
478
433
        continue;
479
18
      
if (18
MRI->getRegClass(SR.R) != PredRC18
)
480
0
        continue;
481
18
      assert(!DR.S && !SR.S && "Unexpected subregister");
482
18
      MRI->replaceRegWith(DR.R, SR.R);
483
18
      Erase.insert(&MI);
484
18
      Changed = true;
485
18
    }
486
1.83k
  }
487
860
488
878
  for (VectOfInst::iterator I = Erase.begin(), E = Erase.end(); 
I != E878
;
++I18
)
489
18
    (*I)->eraseFromParent();
490
860
491
860
  return Changed;
492
860
}
493
494
860
bool HexagonGenPredicate::runOnMachineFunction(MachineFunction &MF) {
495
860
  if (skipFunction(*MF.getFunction()))
496
0
    return false;
497
860
498
860
  TII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
499
860
  TRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
500
860
  MRI = &MF.getRegInfo();
501
860
  PredGPRs.clear();
502
860
  PUsers.clear();
503
860
  G2P.clear();
504
860
505
860
  bool Changed = false;
506
860
  collectPredicateGPR(MF);
507
933
  for (SetOfReg::iterator I = PredGPRs.begin(), E = PredGPRs.end(); 
I != E933
;
++I73
)
508
73
    processPredicateGPR(*I);
509
860
510
860
  bool Again;
511
862
  do {
512
862
    Again = false;
513
862
    VectOfInst Processed, Copy;
514
862
515
862
    using iterator = VectOfInst::iterator;
516
862
517
862
    Copy = PUsers;
518
899
    for (iterator I = Copy.begin(), E = Copy.end(); 
I != E899
;
++I37
) {
519
37
      MachineInstr *MI = *I;
520
37
      bool Done = convertToPredForm(MI);
521
37
      if (
Done37
) {
522
9
        Processed.insert(MI);
523
9
        Again = true;
524
9
      }
525
37
    }
526
862
    Changed |= Again;
527
862
528
37
    auto Done = [Processed] (MachineInstr *MI) -> bool {
529
37
      return Processed.count(MI);
530
37
    };
531
862
    PUsers.remove_if(Done);
532
862
  } while (Again);
533
860
534
860
  Changed |= eliminatePredCopies(MF);
535
860
  return Changed;
536
860
}
537
538
405
FunctionPass *llvm::createHexagonGenPredicate() {
539
405
  return new HexagonGenPredicate();
540
405
}