Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonBitSimplify.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonBitSimplify.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 "BitTracker.h"
10
#include "HexagonBitTracker.h"
11
#include "HexagonInstrInfo.h"
12
#include "HexagonRegisterInfo.h"
13
#include "HexagonSubtarget.h"
14
#include "llvm/ADT/BitVector.h"
15
#include "llvm/ADT/DenseMap.h"
16
#include "llvm/ADT/GraphTraits.h"
17
#include "llvm/ADT/STLExtras.h"
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/ADT/StringRef.h"
20
#include "llvm/CodeGen/MachineBasicBlock.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/MachineInstrBuilder.h"
26
#include "llvm/CodeGen/MachineOperand.h"
27
#include "llvm/CodeGen/MachineRegisterInfo.h"
28
#include "llvm/CodeGen/TargetRegisterInfo.h"
29
#include "llvm/IR/DebugLoc.h"
30
#include "llvm/MC/MCInstrDesc.h"
31
#include "llvm/Pass.h"
32
#include "llvm/Support/CommandLine.h"
33
#include "llvm/Support/Compiler.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/ErrorHandling.h"
36
#include "llvm/Support/MathExtras.h"
37
#include "llvm/Support/raw_ostream.h"
38
#include <algorithm>
39
#include <cassert>
40
#include <cstdint>
41
#include <iterator>
42
#include <limits>
43
#include <utility>
44
#include <vector>
45
46
#define DEBUG_TYPE "hexbit"
47
48
using namespace llvm;
49
50
static cl::opt<bool> PreserveTiedOps("hexbit-keep-tied", cl::Hidden,
51
  cl::init(true), cl::desc("Preserve subregisters in tied operands"));
52
static cl::opt<bool> GenExtract("hexbit-extract", cl::Hidden,
53
  cl::init(true), cl::desc("Generate extract instructions"));
54
static cl::opt<bool> GenBitSplit("hexbit-bitsplit", cl::Hidden,
55
  cl::init(true), cl::desc("Generate bitsplit instructions"));
56
57
static cl::opt<unsigned> MaxExtract("hexbit-max-extract", cl::Hidden,
58
  cl::init(std::numeric_limits<unsigned>::max()));
59
static unsigned CountExtract = 0;
60
static cl::opt<unsigned> MaxBitSplit("hexbit-max-bitsplit", cl::Hidden,
61
  cl::init(std::numeric_limits<unsigned>::max()));
62
static unsigned CountBitSplit = 0;
63
64
namespace llvm {
65
66
  void initializeHexagonBitSimplifyPass(PassRegistry& Registry);
67
  FunctionPass *createHexagonBitSimplify();
68
69
} // end namespace llvm
70
71
namespace {
72
73
  // Set of virtual registers, based on BitVector.
74
  struct RegisterSet : private BitVector {
75
73.7k
    RegisterSet() = default;
76
0
    explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
77
34.7k
    RegisterSet(const RegisterSet &RS) = default;
78
79
    using BitVector::clear;
80
    using BitVector::count;
81
82
71.8k
    unsigned find_first() const {
83
71.8k
      int First = BitVector::find_first();
84
71.8k
      if (First < 0)
85
10.5k
        return 0;
86
61.3k
      return x2v(First);
87
61.3k
    }
88
89
1.25M
    unsigned find_next(unsigned Prev) const {
90
1.25M
      int Next = BitVector::find_next(v2x(Prev));
91
1.25M
      if (Next < 0)
92
33.1k
        return 0;
93
1.22M
      return x2v(Next);
94
1.22M
    }
95
96
241k
    RegisterSet &insert(unsigned R) {
97
241k
      unsigned Idx = v2x(R);
98
241k
      ensure(Idx);
99
241k
      return static_cast<RegisterSet&>(BitVector::set(Idx));
100
241k
    }
101
0
    RegisterSet &remove(unsigned R) {
102
0
      unsigned Idx = v2x(R);
103
0
      if (Idx >= size())
104
0
        return *this;
105
0
      return static_cast<RegisterSet&>(BitVector::reset(Idx));
106
0
    }
107
108
105k
    RegisterSet &insert(const RegisterSet &Rs) {
109
105k
      return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
110
105k
    }
111
6
    RegisterSet &remove(const RegisterSet &Rs) {
112
6
      return static_cast<RegisterSet&>(BitVector::reset(Rs));
113
6
    }
114
115
1.20M
    reference operator[](unsigned R) {
116
1.20M
      unsigned Idx = v2x(R);
117
1.20M
      ensure(Idx);
118
1.20M
      return BitVector::operator[](Idx);
119
1.20M
    }
120
0
    bool operator[](unsigned R) const {
121
0
      unsigned Idx = v2x(R);
122
0
      assert(Idx < size());
123
0
      return BitVector::operator[](Idx);
124
0
    }
125
13.5k
    bool has(unsigned R) const {
126
13.5k
      unsigned Idx = v2x(R);
127
13.5k
      if (Idx >= size())
128
12.3k
        return false;
129
1.16k
      return BitVector::test(Idx);
130
1.16k
    }
131
132
0
    bool empty() const {
133
0
      return !BitVector::any();
134
0
    }
135
0
    bool includes(const RegisterSet &Rs) const {
136
0
      // A.BitVector::test(B)  <=>  A-B != {}
137
0
      return !Rs.BitVector::test(*this);
138
0
    }
139
20
    bool intersects(const RegisterSet &Rs) const {
140
20
      return BitVector::anyCommon(Rs);
141
20
    }
142
143
  private:
144
1.44M
    void ensure(unsigned Idx) {
145
1.44M
      if (size() <= Idx)
146
146k
        resize(std::max(Idx+1, 32U));
147
1.44M
    }
148
149
2.71M
    static inline unsigned v2x(unsigned v) {
150
2.71M
      return TargetRegisterInfo::virtReg2Index(v);
151
2.71M
    }
152
153
1.28M
    static inline unsigned x2v(unsigned x) {
154
1.28M
      return TargetRegisterInfo::index2VirtReg(x);
155
1.28M
    }
156
  };
157
158
  struct PrintRegSet {
159
    PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
160
0
      : RS(S), TRI(RI) {}
161
162
    friend raw_ostream &operator<< (raw_ostream &OS,
163
          const PrintRegSet &P);
164
165
  private:
166
    const RegisterSet &RS;
167
    const TargetRegisterInfo *TRI;
168
  };
169
170
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P)
171
    LLVM_ATTRIBUTE_UNUSED;
172
0
  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
173
0
    OS << '{';
174
0
    for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
175
0
      OS << ' ' << printReg(R, P.TRI);
176
0
    OS << " }";
177
0
    return OS;
178
0
  }
179
180
  class Transformation;
181
182
  class HexagonBitSimplify : public MachineFunctionPass {
183
  public:
184
    static char ID;
185
186
858
    HexagonBitSimplify() : MachineFunctionPass(ID) {}
187
188
3.35k
    StringRef getPassName() const override {
189
3.35k
      return "Hexagon bit simplification";
190
3.35k
    }
191
192
851
    void getAnalysisUsage(AnalysisUsage &AU) const override {
193
851
      AU.addRequired<MachineDominatorTree>();
194
851
      AU.addPreserved<MachineDominatorTree>();
195
851
      MachineFunctionPass::getAnalysisUsage(AU);
196
851
    }
197
198
    bool runOnMachineFunction(MachineFunction &MF) override;
199
200
    static void getInstrDefs(const MachineInstr &MI, RegisterSet &Defs);
201
    static void getInstrUses(const MachineInstr &MI, RegisterSet &Uses);
202
    static bool isEqual(const BitTracker::RegisterCell &RC1, uint16_t B1,
203
        const BitTracker::RegisterCell &RC2, uint16_t B2, uint16_t W);
204
    static bool isZero(const BitTracker::RegisterCell &RC, uint16_t B,
205
        uint16_t W);
206
    static bool getConst(const BitTracker::RegisterCell &RC, uint16_t B,
207
        uint16_t W, uint64_t &U);
208
    static bool replaceReg(unsigned OldR, unsigned NewR,
209
        MachineRegisterInfo &MRI);
210
    static bool getSubregMask(const BitTracker::RegisterRef &RR,
211
        unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI);
212
    static bool replaceRegWithSub(unsigned OldR, unsigned NewR,
213
        unsigned NewSR, MachineRegisterInfo &MRI);
214
    static bool replaceSubWithSub(unsigned OldR, unsigned OldSR,
215
        unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI);
216
    static bool parseRegSequence(const MachineInstr &I,
217
        BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
218
        const MachineRegisterInfo &MRI);
219
220
    static bool getUsedBitsInStore(unsigned Opc, BitVector &Bits,
221
        uint16_t Begin);
222
    static bool getUsedBits(unsigned Opc, unsigned OpN, BitVector &Bits,
223
        uint16_t Begin, const HexagonInstrInfo &HII);
224
225
    static const TargetRegisterClass *getFinalVRegClass(
226
        const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI);
227
    static bool isTransparentCopy(const BitTracker::RegisterRef &RD,
228
        const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI);
229
230
  private:
231
    MachineDominatorTree *MDT = nullptr;
232
233
    bool visitBlock(MachineBasicBlock &B, Transformation &T, RegisterSet &AVs);
234
    static bool hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
235
        unsigned NewSub = Hexagon::NoSubRegister);
236
  };
237
238
  using HBS = HexagonBitSimplify;
239
240
  // The purpose of this class is to provide a common facility to traverse
241
  // the function top-down or bottom-up via the dominator tree, and keep
242
  // track of the available registers.
243
  class Transformation {
244
  public:
245
    bool TopDown;
246
247
16.7k
    Transformation(bool TD) : TopDown(TD) {}
248
16.7k
    virtual ~Transformation() = default;
249
250
    virtual bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) = 0;
251
  };
252
253
} // end anonymous namespace
254
255
char HexagonBitSimplify::ID = 0;
256
257
101k
INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexagon-bit-simplify",
258
101k
      "Hexagon bit simplification", false, false)
259
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
260
101k
INITIALIZE_PASS_END(HexagonBitSimplify, "hexagon-bit-simplify",
261
      "Hexagon bit simplification", false, false)
262
263
bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
264
24.8k
      RegisterSet &AVs) {
265
24.8k
  bool Changed = false;
266
24.8k
267
24.8k
  if (T.TopDown)
268
19.8k
    Changed = T.processBlock(B, AVs);
269
24.8k
270
24.8k
  RegisterSet Defs;
271
24.8k
  for (auto &I : B)
272
211k
    getInstrDefs(I, Defs);
273
24.8k
  RegisterSet NewAVs = AVs;
274
24.8k
  NewAVs.insert(Defs);
275
24.8k
276
24.8k
  for (auto *DTN : children<MachineDomTreeNode*>(MDT->getNode(&B)))
277
8.13k
    Changed |= visitBlock(*(DTN->getBlock()), T, NewAVs);
278
24.8k
279
24.8k
  if (!T.TopDown)
280
4.96k
    Changed |= T.processBlock(B, AVs);
281
24.8k
282
24.8k
  return Changed;
283
24.8k
}
284
285
//
286
// Utility functions:
287
//
288
void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI,
289
334k
      RegisterSet &Defs) {
290
980k
  for (auto &Op : MI.operands()) {
291
980k
    if (!Op.isReg() || 
!Op.isDef()776k
)
292
636k
      continue;
293
344k
    unsigned R = Op.getReg();
294
344k
    if (!TargetRegisterInfo::isVirtualRegister(R))
295
116k
      continue;
296
227k
    Defs.insert(R);
297
227k
  }
298
334k
}
299
300
void HexagonBitSimplify::getInstrUses(const MachineInstr &MI,
301
22
      RegisterSet &Uses) {
302
52
  for (auto &Op : MI.operands()) {
303
52
    if (!Op.isReg() || 
!Op.isUse()44
)
304
30
      continue;
305
22
    unsigned R = Op.getReg();
306
22
    if (!TargetRegisterInfo::isVirtualRegister(R))
307
6
      continue;
308
16
    Uses.insert(R);
309
16
  }
310
22
}
311
312
// Check if all the bits in range [B, E) in both cells are equal.
313
bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1,
314
      uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2,
315
1.45M
      uint16_t W) {
316
1.61M
  for (uint16_t i = 0; i < W; 
++i159k
) {
317
1.61M
    // If RC1[i] is "bottom", it cannot be proven equal to RC2[i].
318
1.61M
    if (RC1[B1+i].Type == BitTracker::BitValue::Ref && 
RC1[B1+i].RefI.Reg == 01.39M
)
319
0
      return false;
320
1.61M
    // Same for RC2[i].
321
1.61M
    if (RC2[B2+i].Type == BitTracker::BitValue::Ref && 
RC2[B2+i].RefI.Reg == 01.43M
)
322
0
      return false;
323
1.61M
    if (RC1[B1+i] != RC2[B2+i])
324
1.45M
      return false;
325
1.61M
  }
326
1.45M
  
return true672
;
327
1.45M
}
328
329
bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC,
330
166
      uint16_t B, uint16_t W) {
331
166
  assert(B < RC.width() && B+W <= RC.width());
332
951
  for (uint16_t i = B; i < B+W; 
++i785
)
333
902
    if (!RC[i].is(0))
334
117
      return false;
335
166
  
return true49
;
336
166
}
337
338
bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC,
339
26.1k
        uint16_t B, uint16_t W, uint64_t &U) {
340
26.1k
  assert(B < RC.width() && B+W <= RC.width());
341
26.1k
  int64_t T = 0;
342
111k
  for (uint16_t i = B+W; i > B; 
--i85.2k
) {
343
111k
    const BitTracker::BitValue &BV = RC[i-1];
344
111k
    T <<= 1;
345
111k
    if (BV.is(1))
346
13.1k
      T |= 1;
347
98.0k
    else if (!BV.is(0))
348
25.9k
      return false;
349
111k
  }
350
26.1k
  U = T;
351
231
  return true;
352
26.1k
}
353
354
bool HexagonBitSimplify::replaceReg(unsigned OldR, unsigned NewR,
355
1.33k
      MachineRegisterInfo &MRI) {
356
1.33k
  if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
357
1.33k
      !TargetRegisterInfo::isVirtualRegister(NewR))
358
0
    return false;
359
1.33k
  auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
360
1.33k
  decltype(End) NextI;
361
2.72k
  for (auto I = Begin; I != End; 
I = NextI1.39k
) {
362
1.39k
    NextI = std::next(I);
363
1.39k
    I->setReg(NewR);
364
1.39k
  }
365
1.33k
  return Begin != End;
366
1.33k
}
367
368
bool HexagonBitSimplify::replaceRegWithSub(unsigned OldR, unsigned NewR,
369
3.87k
      unsigned NewSR, MachineRegisterInfo &MRI) {
370
3.87k
  if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
371
3.87k
      !TargetRegisterInfo::isVirtualRegister(NewR))
372
0
    return false;
373
3.87k
  if (hasTiedUse(OldR, MRI, NewSR))
374
25
    return false;
375
3.84k
  auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
376
3.84k
  decltype(End) NextI;
377
10.4k
  for (auto I = Begin; I != End; 
I = NextI6.63k
) {
378
6.63k
    NextI = std::next(I);
379
6.63k
    I->setReg(NewR);
380
6.63k
    I->setSubReg(NewSR);
381
6.63k
  }
382
3.84k
  return Begin != End;
383
3.84k
}
384
385
bool HexagonBitSimplify::replaceSubWithSub(unsigned OldR, unsigned OldSR,
386
3.38k
      unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI) {
387
3.38k
  if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
388
3.38k
      !TargetRegisterInfo::isVirtualRegister(NewR))
389
0
    return false;
390
3.38k
  if (OldSR != NewSR && 
hasTiedUse(OldR, MRI, NewSR)3.17k
)
391
2
    return false;
392
3.38k
  auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
393
3.38k
  decltype(End) NextI;
394
9.38k
  for (auto I = Begin; I != End; 
I = NextI6.00k
) {
395
6.00k
    NextI = std::next(I);
396
6.00k
    if (I->getSubReg() != OldSR)
397
2.90k
      continue;
398
3.10k
    I->setReg(NewR);
399
3.10k
    I->setSubReg(NewSR);
400
3.10k
  }
401
3.38k
  return Begin != End;
402
3.38k
}
403
404
// For a register ref (pair Reg:Sub), set Begin to the position of the LSB
405
// of Sub in Reg, and set Width to the size of Sub in bits. Return true,
406
// if this succeeded, otherwise return false.
407
bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR,
408
68.9k
      unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) {
409
68.9k
  const TargetRegisterClass *RC = MRI.getRegClass(RR.Reg);
410
68.9k
  if (RR.Sub == 0) {
411
65.7k
    Begin = 0;
412
65.7k
    Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(*RC);
413
65.7k
    return true;
414
65.7k
  }
415
3.18k
416
3.18k
  Begin = 0;
417
3.18k
418
3.18k
  switch (RC->getID()) {
419
3.18k
    case Hexagon::DoubleRegsRegClassID:
420
3.18k
    case Hexagon::HvxWRRegClassID:
421
3.18k
      Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(*RC) / 2;
422
3.18k
      if (RR.Sub == Hexagon::isub_hi || 
RR.Sub == Hexagon::vsub_hi3.03k
)
423
481
        Begin = Width;
424
3.18k
      break;
425
3.18k
    default:
426
0
      return false;
427
3.18k
  }
428
3.18k
  return true;
429
3.18k
}
430
431
432
// For a REG_SEQUENCE, set SL to the low subregister and SH to the high
433
// subregister.
434
bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I,
435
      BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
436
1.50k
      const MachineRegisterInfo &MRI) {
437
1.50k
  assert(I.getOpcode() == TargetOpcode::REG_SEQUENCE);
438
1.50k
  unsigned Sub1 = I.getOperand(2).getImm(), Sub2 = I.getOperand(4).getImm();
439
1.50k
  auto &DstRC = *MRI.getRegClass(I.getOperand(0).getReg());
440
1.50k
  auto &HRI = static_cast<const HexagonRegisterInfo&>(
441
1.50k
                  *MRI.getTargetRegisterInfo());
442
1.50k
  unsigned SubLo = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_lo);
443
1.50k
  unsigned SubHi = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_hi);
444
1.50k
  assert((Sub1 == SubLo && Sub2 == SubHi) || (Sub1 == SubHi && Sub2 == SubLo));
445
1.50k
  if (Sub1 == SubLo && 
Sub2 == SubHi1.17k
) {
446
1.17k
    SL = I.getOperand(1);
447
1.17k
    SH = I.getOperand(3);
448
1.17k
    return true;
449
1.17k
  }
450
337
  if (Sub1 == SubHi && Sub2 == SubLo) {
451
337
    SH = I.getOperand(1);
452
337
    SL = I.getOperand(3);
453
337
    return true;
454
337
  }
455
0
  return false;
456
0
}
457
458
// All stores (except 64-bit stores) take a 32-bit register as the source
459
// of the value to be stored. If the instruction stores into a location
460
// that is shorter than 32 bits, some bits of the source register are not
461
// used. For each store instruction, calculate the set of used bits in
462
// the source register, and set appropriate bits in Bits. Return true if
463
// the bits are calculated, false otherwise.
464
bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits,
465
1.58k
      uint16_t Begin) {
466
1.58k
  using namespace Hexagon;
467
1.58k
468
1.58k
  switch (Opc) {
469
1.58k
    // Store byte
470
1.58k
    case S2_storerb_io:           // memb(Rs32+#s11:0)=Rt32
471
51
    case S2_storerbnew_io:        // memb(Rs32+#s11:0)=Nt8.new
472
51
    case S2_pstorerbt_io:         // if (Pv4) memb(Rs32+#u6:0)=Rt32
473
51
    case S2_pstorerbf_io:         // if (!Pv4) memb(Rs32+#u6:0)=Rt32
474
51
    case S4_pstorerbtnew_io:      // if (Pv4.new) memb(Rs32+#u6:0)=Rt32
475
51
    case S4_pstorerbfnew_io:      // if (!Pv4.new) memb(Rs32+#u6:0)=Rt32
476
51
    case S2_pstorerbnewt_io:      // if (Pv4) memb(Rs32+#u6:0)=Nt8.new
477
51
    case S2_pstorerbnewf_io:      // if (!Pv4) memb(Rs32+#u6:0)=Nt8.new
478
51
    case S4_pstorerbnewtnew_io:   // if (Pv4.new) memb(Rs32+#u6:0)=Nt8.new
479
51
    case S4_pstorerbnewfnew_io:   // if (!Pv4.new) memb(Rs32+#u6:0)=Nt8.new
480
51
    case S2_storerb_pi:           // memb(Rx32++#s4:0)=Rt32
481
51
    case S2_storerbnew_pi:        // memb(Rx32++#s4:0)=Nt8.new
482
51
    case S2_pstorerbt_pi:         // if (Pv4) memb(Rx32++#s4:0)=Rt32
483
51
    case S2_pstorerbf_pi:         // if (!Pv4) memb(Rx32++#s4:0)=Rt32
484
51
    case S2_pstorerbtnew_pi:      // if (Pv4.new) memb(Rx32++#s4:0)=Rt32
485
51
    case S2_pstorerbfnew_pi:      // if (!Pv4.new) memb(Rx32++#s4:0)=Rt32
486
51
    case S2_pstorerbnewt_pi:      // if (Pv4) memb(Rx32++#s4:0)=Nt8.new
487
51
    case S2_pstorerbnewf_pi:      // if (!Pv4) memb(Rx32++#s4:0)=Nt8.new
488
51
    case S2_pstorerbnewtnew_pi:   // if (Pv4.new) memb(Rx32++#s4:0)=Nt8.new
489
51
    case S2_pstorerbnewfnew_pi:   // if (!Pv4.new) memb(Rx32++#s4:0)=Nt8.new
490
51
    case S4_storerb_ap:           // memb(Re32=#U6)=Rt32
491
51
    case S4_storerbnew_ap:        // memb(Re32=#U6)=Nt8.new
492
51
    case S2_storerb_pr:           // memb(Rx32++Mu2)=Rt32
493
51
    case S2_storerbnew_pr:        // memb(Rx32++Mu2)=Nt8.new
494
51
    case S4_storerb_ur:           // memb(Ru32<<#u2+#U6)=Rt32
495
51
    case S4_storerbnew_ur:        // memb(Ru32<<#u2+#U6)=Nt8.new
496
51
    case S2_storerb_pbr:          // memb(Rx32++Mu2:brev)=Rt32
497
51
    case S2_storerbnew_pbr:       // memb(Rx32++Mu2:brev)=Nt8.new
498
51
    case S2_storerb_pci:          // memb(Rx32++#s4:0:circ(Mu2))=Rt32
499
51
    case S2_storerbnew_pci:       // memb(Rx32++#s4:0:circ(Mu2))=Nt8.new
500
51
    case S2_storerb_pcr:          // memb(Rx32++I:circ(Mu2))=Rt32
501
51
    case S2_storerbnew_pcr:       // memb(Rx32++I:circ(Mu2))=Nt8.new
502
51
    case S4_storerb_rr:           // memb(Rs32+Ru32<<#u2)=Rt32
503
51
    case S4_storerbnew_rr:        // memb(Rs32+Ru32<<#u2)=Nt8.new
504
51
    case S4_pstorerbt_rr:         // if (Pv4) memb(Rs32+Ru32<<#u2)=Rt32
505
51
    case S4_pstorerbf_rr:         // if (!Pv4) memb(Rs32+Ru32<<#u2)=Rt32
506
51
    case S4_pstorerbtnew_rr:      // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
507
51
    case S4_pstorerbfnew_rr:      // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
508
51
    case S4_pstorerbnewt_rr:      // if (Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
509
51
    case S4_pstorerbnewf_rr:      // if (!Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
510
51
    case S4_pstorerbnewtnew_rr:   // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
511
51
    case S4_pstorerbnewfnew_rr:   // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
512
51
    case S2_storerbgp:            // memb(gp+#u16:0)=Rt32
513
51
    case S2_storerbnewgp:         // memb(gp+#u16:0)=Nt8.new
514
51
    case S4_pstorerbt_abs:        // if (Pv4) memb(#u6)=Rt32
515
51
    case S4_pstorerbf_abs:        // if (!Pv4) memb(#u6)=Rt32
516
51
    case S4_pstorerbtnew_abs:     // if (Pv4.new) memb(#u6)=Rt32
517
51
    case S4_pstorerbfnew_abs:     // if (!Pv4.new) memb(#u6)=Rt32
518
51
    case S4_pstorerbnewt_abs:     // if (Pv4) memb(#u6)=Nt8.new
519
51
    case S4_pstorerbnewf_abs:     // if (!Pv4) memb(#u6)=Nt8.new
520
51
    case S4_pstorerbnewtnew_abs:  // if (Pv4.new) memb(#u6)=Nt8.new
521
51
    case S4_pstorerbnewfnew_abs:  // if (!Pv4.new) memb(#u6)=Nt8.new
522
51
      Bits.set(Begin, Begin+8);
523
51
      return true;
524
51
525
51
    // Store low half
526
56
    case S2_storerh_io:           // memh(Rs32+#s11:1)=Rt32
527
56
    case S2_storerhnew_io:        // memh(Rs32+#s11:1)=Nt8.new
528
56
    case S2_pstorerht_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt32
529
56
    case S2_pstorerhf_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt32
530
56
    case S4_pstorerhtnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt32
531
56
    case S4_pstorerhfnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt32
532
56
    case S2_pstorerhnewt_io:      // if (Pv4) memh(Rs32+#u6:1)=Nt8.new
533
56
    case S2_pstorerhnewf_io:      // if (!Pv4) memh(Rs32+#u6:1)=Nt8.new
534
56
    case S4_pstorerhnewtnew_io:   // if (Pv4.new) memh(Rs32+#u6:1)=Nt8.new
535
56
    case S4_pstorerhnewfnew_io:   // if (!Pv4.new) memh(Rs32+#u6:1)=Nt8.new
536
56
    case S2_storerh_pi:           // memh(Rx32++#s4:1)=Rt32
537
56
    case S2_storerhnew_pi:        // memh(Rx32++#s4:1)=Nt8.new
538
56
    case S2_pstorerht_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt32
539
56
    case S2_pstorerhf_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt32
540
56
    case S2_pstorerhtnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt32
541
56
    case S2_pstorerhfnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt32
542
56
    case S2_pstorerhnewt_pi:      // if (Pv4) memh(Rx32++#s4:1)=Nt8.new
543
56
    case S2_pstorerhnewf_pi:      // if (!Pv4) memh(Rx32++#s4:1)=Nt8.new
544
56
    case S2_pstorerhnewtnew_pi:   // if (Pv4.new) memh(Rx32++#s4:1)=Nt8.new
545
56
    case S2_pstorerhnewfnew_pi:   // if (!Pv4.new) memh(Rx32++#s4:1)=Nt8.new
546
56
    case S4_storerh_ap:           // memh(Re32=#U6)=Rt32
547
56
    case S4_storerhnew_ap:        // memh(Re32=#U6)=Nt8.new
548
56
    case S2_storerh_pr:           // memh(Rx32++Mu2)=Rt32
549
56
    case S2_storerhnew_pr:        // memh(Rx32++Mu2)=Nt8.new
550
56
    case S4_storerh_ur:           // memh(Ru32<<#u2+#U6)=Rt32
551
56
    case S4_storerhnew_ur:        // memh(Ru32<<#u2+#U6)=Nt8.new
552
56
    case S2_storerh_pbr:          // memh(Rx32++Mu2:brev)=Rt32
553
56
    case S2_storerhnew_pbr:       // memh(Rx32++Mu2:brev)=Nt8.new
554
56
    case S2_storerh_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt32
555
56
    case S2_storerhnew_pci:       // memh(Rx32++#s4:1:circ(Mu2))=Nt8.new
556
56
    case S2_storerh_pcr:          // memh(Rx32++I:circ(Mu2))=Rt32
557
56
    case S2_storerhnew_pcr:       // memh(Rx32++I:circ(Mu2))=Nt8.new
558
56
    case S4_storerh_rr:           // memh(Rs32+Ru32<<#u2)=Rt32
559
56
    case S4_pstorerht_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt32
560
56
    case S4_pstorerhf_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt32
561
56
    case S4_pstorerhtnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
562
56
    case S4_pstorerhfnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
563
56
    case S4_storerhnew_rr:        // memh(Rs32+Ru32<<#u2)=Nt8.new
564
56
    case S4_pstorerhnewt_rr:      // if (Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
565
56
    case S4_pstorerhnewf_rr:      // if (!Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
566
56
    case S4_pstorerhnewtnew_rr:   // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
567
56
    case S4_pstorerhnewfnew_rr:   // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
568
56
    case S2_storerhgp:            // memh(gp+#u16:1)=Rt32
569
56
    case S2_storerhnewgp:         // memh(gp+#u16:1)=Nt8.new
570
56
    case S4_pstorerht_abs:        // if (Pv4) memh(#u6)=Rt32
571
56
    case S4_pstorerhf_abs:        // if (!Pv4) memh(#u6)=Rt32
572
56
    case S4_pstorerhtnew_abs:     // if (Pv4.new) memh(#u6)=Rt32
573
56
    case S4_pstorerhfnew_abs:     // if (!Pv4.new) memh(#u6)=Rt32
574
56
    case S4_pstorerhnewt_abs:     // if (Pv4) memh(#u6)=Nt8.new
575
56
    case S4_pstorerhnewf_abs:     // if (!Pv4) memh(#u6)=Nt8.new
576
56
    case S4_pstorerhnewtnew_abs:  // if (Pv4.new) memh(#u6)=Nt8.new
577
56
    case S4_pstorerhnewfnew_abs:  // if (!Pv4.new) memh(#u6)=Nt8.new
578
56
      Bits.set(Begin, Begin+16);
579
56
      return true;
580
56
581
56
    // Store high half
582
56
    case S2_storerf_io:           // memh(Rs32+#s11:1)=Rt.H32
583
1
    case S2_pstorerft_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt.H32
584
1
    case S2_pstorerff_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt.H32
585
1
    case S4_pstorerftnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt.H32
586
1
    case S4_pstorerffnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt.H32
587
1
    case S2_storerf_pi:           // memh(Rx32++#s4:1)=Rt.H32
588
1
    case S2_pstorerft_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt.H32
589
1
    case S2_pstorerff_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt.H32
590
1
    case S2_pstorerftnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt.H32
591
1
    case S2_pstorerffnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt.H32
592
1
    case S4_storerf_ap:           // memh(Re32=#U6)=Rt.H32
593
1
    case S2_storerf_pr:           // memh(Rx32++Mu2)=Rt.H32
594
1
    case S4_storerf_ur:           // memh(Ru32<<#u2+#U6)=Rt.H32
595
1
    case S2_storerf_pbr:          // memh(Rx32++Mu2:brev)=Rt.H32
596
1
    case S2_storerf_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt.H32
597
1
    case S2_storerf_pcr:          // memh(Rx32++I:circ(Mu2))=Rt.H32
598
1
    case S4_storerf_rr:           // memh(Rs32+Ru32<<#u2)=Rt.H32
599
1
    case S4_pstorerft_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
600
1
    case S4_pstorerff_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
601
1
    case S4_pstorerftnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
602
1
    case S4_pstorerffnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
603
1
    case S2_storerfgp:            // memh(gp+#u16:1)=Rt.H32
604
1
    case S4_pstorerft_abs:        // if (Pv4) memh(#u6)=Rt.H32
605
1
    case S4_pstorerff_abs:        // if (!Pv4) memh(#u6)=Rt.H32
606
1
    case S4_pstorerftnew_abs:     // if (Pv4.new) memh(#u6)=Rt.H32
607
1
    case S4_pstorerffnew_abs:     // if (!Pv4.new) memh(#u6)=Rt.H32
608
1
      Bits.set(Begin+16, Begin+32);
609
1
      return true;
610
1.47k
  }
611
1.47k
612
1.47k
  return false;
613
1.47k
}
614
615
// For an instruction with opcode Opc, calculate the set of bits that it
616
// uses in a register in operand OpN. This only calculates the set of used
617
// bits for cases where it does not depend on any operands (as is the case
618
// in shifts, for example). For concrete instructions from a program, the
619
// operand may be a subregister of a larger register, while Bits would
620
// correspond to the larger register in its entirety. Because of that,
621
// the parameter Begin can be used to indicate which bit of Bits should be
622
// considered the LSB of the operand.
623
bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN,
624
9.95k
      BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) {
625
9.95k
  using namespace Hexagon;
626
9.95k
627
9.95k
  const MCInstrDesc &D = HII.get(Opc);
628
9.95k
  if (D.mayStore()) {
629
2.07k
    if (OpN == D.getNumOperands()-1)
630
1.58k
      return getUsedBitsInStore(Opc, Bits, Begin);
631
492
    return false;
632
492
  }
633
7.87k
634
7.87k
  switch (Opc) {
635
7.87k
    // One register source. Used bits: R1[0-7].
636
7.87k
    case A2_sxtb:
637
40
    case A2_zxtb:
638
40
    case A4_cmpbeqi:
639
40
    case A4_cmpbgti:
640
40
    case A4_cmpbgtui:
641
40
      if (OpN == 1) {
642
40
        Bits.set(Begin, Begin+8);
643
40
        return true;
644
40
      }
645
0
      break;
646
0
647
0
    // One register source. Used bits: R1[0-15].
648
89
    case A2_aslh:
649
89
    case A2_sxth:
650
89
    case A2_zxth:
651
89
    case A4_cmpheqi:
652
89
    case A4_cmphgti:
653
89
    case A4_cmphgtui:
654
89
      if (OpN == 1) {
655
89
        Bits.set(Begin, Begin+16);
656
89
        return true;
657
89
      }
658
0
      break;
659
0
660
0
    // One register source. Used bits: R1[16-31].
661
6
    case A2_asrh:
662
6
      if (OpN == 1) {
663
6
        Bits.set(Begin+16, Begin+32);
664
6
        return true;
665
6
      }
666
0
      break;
667
0
668
0
    // Two register sources. Used bits: R1[0-7], R2[0-7].
669
0
    case A4_cmpbeq:
670
0
    case A4_cmpbgt:
671
0
    case A4_cmpbgtu:
672
0
      if (OpN == 1) {
673
0
        Bits.set(Begin, Begin+8);
674
0
        return true;
675
0
      }
676
0
      break;
677
0
678
0
    // Two register sources. Used bits: R1[0-15], R2[0-15].
679
133
    case A4_cmpheq:
680
133
    case A4_cmphgt:
681
133
    case A4_cmphgtu:
682
133
    case A2_addh_h16_ll:
683
133
    case A2_addh_h16_sat_ll:
684
133
    case A2_addh_l16_ll:
685
133
    case A2_addh_l16_sat_ll:
686
133
    case A2_combine_ll:
687
133
    case A2_subh_h16_ll:
688
133
    case A2_subh_h16_sat_ll:
689
133
    case A2_subh_l16_ll:
690
133
    case A2_subh_l16_sat_ll:
691
133
    case M2_mpy_acc_ll_s0:
692
133
    case M2_mpy_acc_ll_s1:
693
133
    case M2_mpy_acc_sat_ll_s0:
694
133
    case M2_mpy_acc_sat_ll_s1:
695
133
    case M2_mpy_ll_s0:
696
133
    case M2_mpy_ll_s1:
697
133
    case M2_mpy_nac_ll_s0:
698
133
    case M2_mpy_nac_ll_s1:
699
133
    case M2_mpy_nac_sat_ll_s0:
700
133
    case M2_mpy_nac_sat_ll_s1:
701
133
    case M2_mpy_rnd_ll_s0:
702
133
    case M2_mpy_rnd_ll_s1:
703
133
    case M2_mpy_sat_ll_s0:
704
133
    case M2_mpy_sat_ll_s1:
705
133
    case M2_mpy_sat_rnd_ll_s0:
706
133
    case M2_mpy_sat_rnd_ll_s1:
707
133
    case M2_mpyd_acc_ll_s0:
708
133
    case M2_mpyd_acc_ll_s1:
709
133
    case M2_mpyd_ll_s0:
710
133
    case M2_mpyd_ll_s1:
711
133
    case M2_mpyd_nac_ll_s0:
712
133
    case M2_mpyd_nac_ll_s1:
713
133
    case M2_mpyd_rnd_ll_s0:
714
133
    case M2_mpyd_rnd_ll_s1:
715
133
    case M2_mpyu_acc_ll_s0:
716
133
    case M2_mpyu_acc_ll_s1:
717
133
    case M2_mpyu_ll_s0:
718
133
    case M2_mpyu_ll_s1:
719
133
    case M2_mpyu_nac_ll_s0:
720
133
    case M2_mpyu_nac_ll_s1:
721
133
    case M2_mpyud_acc_ll_s0:
722
133
    case M2_mpyud_acc_ll_s1:
723
133
    case M2_mpyud_ll_s0:
724
133
    case M2_mpyud_ll_s1:
725
133
    case M2_mpyud_nac_ll_s0:
726
133
    case M2_mpyud_nac_ll_s1:
727
133
      if (OpN == 1 || 
OpN == 263
) {
728
131
        Bits.set(Begin, Begin+16);
729
131
        return true;
730
131
      }
731
2
      break;
732
2
733
2
    // Two register sources. Used bits: R1[0-15], R2[16-31].
734
2
    case A2_addh_h16_lh:
735
0
    case A2_addh_h16_sat_lh:
736
0
    case A2_combine_lh:
737
0
    case A2_subh_h16_lh:
738
0
    case A2_subh_h16_sat_lh:
739
0
    case M2_mpy_acc_lh_s0:
740
0
    case M2_mpy_acc_lh_s1:
741
0
    case M2_mpy_acc_sat_lh_s0:
742
0
    case M2_mpy_acc_sat_lh_s1:
743
0
    case M2_mpy_lh_s0:
744
0
    case M2_mpy_lh_s1:
745
0
    case M2_mpy_nac_lh_s0:
746
0
    case M2_mpy_nac_lh_s1:
747
0
    case M2_mpy_nac_sat_lh_s0:
748
0
    case M2_mpy_nac_sat_lh_s1:
749
0
    case M2_mpy_rnd_lh_s0:
750
0
    case M2_mpy_rnd_lh_s1:
751
0
    case M2_mpy_sat_lh_s0:
752
0
    case M2_mpy_sat_lh_s1:
753
0
    case M2_mpy_sat_rnd_lh_s0:
754
0
    case M2_mpy_sat_rnd_lh_s1:
755
0
    case M2_mpyd_acc_lh_s0:
756
0
    case M2_mpyd_acc_lh_s1:
757
0
    case M2_mpyd_lh_s0:
758
0
    case M2_mpyd_lh_s1:
759
0
    case M2_mpyd_nac_lh_s0:
760
0
    case M2_mpyd_nac_lh_s1:
761
0
    case M2_mpyd_rnd_lh_s0:
762
0
    case M2_mpyd_rnd_lh_s1:
763
0
    case M2_mpyu_acc_lh_s0:
764
0
    case M2_mpyu_acc_lh_s1:
765
0
    case M2_mpyu_lh_s0:
766
0
    case M2_mpyu_lh_s1:
767
0
    case M2_mpyu_nac_lh_s0:
768
0
    case M2_mpyu_nac_lh_s1:
769
0
    case M2_mpyud_acc_lh_s0:
770
0
    case M2_mpyud_acc_lh_s1:
771
0
    case M2_mpyud_lh_s0:
772
0
    case M2_mpyud_lh_s1:
773
0
    case M2_mpyud_nac_lh_s0:
774
0
    case M2_mpyud_nac_lh_s1:
775
0
    // These four are actually LH.
776
0
    case A2_addh_l16_hl:
777
0
    case A2_addh_l16_sat_hl:
778
0
    case A2_subh_l16_hl:
779
0
    case A2_subh_l16_sat_hl:
780
0
      if (OpN == 1) {
781
0
        Bits.set(Begin, Begin+16);
782
0
        return true;
783
0
      }
784
0
      if (OpN == 2) {
785
0
        Bits.set(Begin+16, Begin+32);
786
0
        return true;
787
0
      }
788
0
      break;
789
0
790
0
    // Two register sources, used bits: R1[16-31], R2[0-15].
791
0
    case A2_addh_h16_hl:
792
0
    case A2_addh_h16_sat_hl:
793
0
    case A2_combine_hl:
794
0
    case A2_subh_h16_hl:
795
0
    case A2_subh_h16_sat_hl:
796
0
    case M2_mpy_acc_hl_s0:
797
0
    case M2_mpy_acc_hl_s1:
798
0
    case M2_mpy_acc_sat_hl_s0:
799
0
    case M2_mpy_acc_sat_hl_s1:
800
0
    case M2_mpy_hl_s0:
801
0
    case M2_mpy_hl_s1:
802
0
    case M2_mpy_nac_hl_s0:
803
0
    case M2_mpy_nac_hl_s1:
804
0
    case M2_mpy_nac_sat_hl_s0:
805
0
    case M2_mpy_nac_sat_hl_s1:
806
0
    case M2_mpy_rnd_hl_s0:
807
0
    case M2_mpy_rnd_hl_s1:
808
0
    case M2_mpy_sat_hl_s0:
809
0
    case M2_mpy_sat_hl_s1:
810
0
    case M2_mpy_sat_rnd_hl_s0:
811
0
    case M2_mpy_sat_rnd_hl_s1:
812
0
    case M2_mpyd_acc_hl_s0:
813
0
    case M2_mpyd_acc_hl_s1:
814
0
    case M2_mpyd_hl_s0:
815
0
    case M2_mpyd_hl_s1:
816
0
    case M2_mpyd_nac_hl_s0:
817
0
    case M2_mpyd_nac_hl_s1:
818
0
    case M2_mpyd_rnd_hl_s0:
819
0
    case M2_mpyd_rnd_hl_s1:
820
0
    case M2_mpyu_acc_hl_s0:
821
0
    case M2_mpyu_acc_hl_s1:
822
0
    case M2_mpyu_hl_s0:
823
0
    case M2_mpyu_hl_s1:
824
0
    case M2_mpyu_nac_hl_s0:
825
0
    case M2_mpyu_nac_hl_s1:
826
0
    case M2_mpyud_acc_hl_s0:
827
0
    case M2_mpyud_acc_hl_s1:
828
0
    case M2_mpyud_hl_s0:
829
0
    case M2_mpyud_hl_s1:
830
0
    case M2_mpyud_nac_hl_s0:
831
0
    case M2_mpyud_nac_hl_s1:
832
0
      if (OpN == 1) {
833
0
        Bits.set(Begin+16, Begin+32);
834
0
        return true;
835
0
      }
836
0
      if (OpN == 2) {
837
0
        Bits.set(Begin, Begin+16);
838
0
        return true;
839
0
      }
840
0
      break;
841
0
842
0
    // Two register sources, used bits: R1[16-31], R2[16-31].
843
0
    case A2_addh_h16_hh:
844
0
    case A2_addh_h16_sat_hh:
845
0
    case A2_combine_hh:
846
0
    case A2_subh_h16_hh:
847
0
    case A2_subh_h16_sat_hh:
848
0
    case M2_mpy_acc_hh_s0:
849
0
    case M2_mpy_acc_hh_s1:
850
0
    case M2_mpy_acc_sat_hh_s0:
851
0
    case M2_mpy_acc_sat_hh_s1:
852
0
    case M2_mpy_hh_s0:
853
0
    case M2_mpy_hh_s1:
854
0
    case M2_mpy_nac_hh_s0:
855
0
    case M2_mpy_nac_hh_s1:
856
0
    case M2_mpy_nac_sat_hh_s0:
857
0
    case M2_mpy_nac_sat_hh_s1:
858
0
    case M2_mpy_rnd_hh_s0:
859
0
    case M2_mpy_rnd_hh_s1:
860
0
    case M2_mpy_sat_hh_s0:
861
0
    case M2_mpy_sat_hh_s1:
862
0
    case M2_mpy_sat_rnd_hh_s0:
863
0
    case M2_mpy_sat_rnd_hh_s1:
864
0
    case M2_mpyd_acc_hh_s0:
865
0
    case M2_mpyd_acc_hh_s1:
866
0
    case M2_mpyd_hh_s0:
867
0
    case M2_mpyd_hh_s1:
868
0
    case M2_mpyd_nac_hh_s0:
869
0
    case M2_mpyd_nac_hh_s1:
870
0
    case M2_mpyd_rnd_hh_s0:
871
0
    case M2_mpyd_rnd_hh_s1:
872
0
    case M2_mpyu_acc_hh_s0:
873
0
    case M2_mpyu_acc_hh_s1:
874
0
    case M2_mpyu_hh_s0:
875
0
    case M2_mpyu_hh_s1:
876
0
    case M2_mpyu_nac_hh_s0:
877
0
    case M2_mpyu_nac_hh_s1:
878
0
    case M2_mpyud_acc_hh_s0:
879
0
    case M2_mpyud_acc_hh_s1:
880
0
    case M2_mpyud_hh_s0:
881
0
    case M2_mpyud_hh_s1:
882
0
    case M2_mpyud_nac_hh_s0:
883
0
    case M2_mpyud_nac_hh_s1:
884
0
      if (OpN == 1 || OpN == 2) {
885
0
        Bits.set(Begin+16, Begin+32);
886
0
        return true;
887
0
      }
888
0
      break;
889
7.61k
  }
890
7.61k
891
7.61k
  return false;
892
7.61k
}
893
894
// Calculate the register class that matches Reg:Sub. For example, if
895
// %1 is a double register, then %1:isub_hi would match the "int"
896
// register class.
897
const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass(
898
1.57M
      const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) {
899
1.57M
  if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
900
0
    return nullptr;
901
1.57M
  auto *RC = MRI.getRegClass(RR.Reg);
902
1.57M
  if (RR.Sub == 0)
903
1.47M
    return RC;
904
102k
  auto &HRI = static_cast<const HexagonRegisterInfo&>(
905
102k
                  *MRI.getTargetRegisterInfo());
906
102k
907
102k
  auto VerifySR = [&HRI] (const TargetRegisterClass *RC, unsigned Sub) -> void {
908
102k
    (void)HRI;
909
102k
    assert(Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_lo) ||
910
102k
           Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_hi));
911
102k
  };
912
102k
913
102k
  switch (RC->getID()) {
914
102k
    case Hexagon::DoubleRegsRegClassID:
915
15.6k
      VerifySR(RC, RR.Sub);
916
15.6k
      return &Hexagon::IntRegsRegClass;
917
102k
    case Hexagon::HvxWRRegClassID:
918
86.5k
      VerifySR(RC, RR.Sub);
919
86.5k
      return &Hexagon::HvxVRRegClass;
920
364
  }
921
364
  return nullptr;
922
364
}
923
924
// Check if RD could be replaced with RS at any possible use of RD.
925
// For example a predicate register cannot be replaced with a integer
926
// register, but a 64-bit register with a subregister can be replaced
927
// with a 32-bit register.
928
bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD,
929
766k
      const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) {
930
766k
  if (!TargetRegisterInfo::isVirtualRegister(RD.Reg) ||
931
766k
      
!TargetRegisterInfo::isVirtualRegister(RS.Reg)762k
)
932
8.59k
    return false;
933
757k
  // Return false if one (or both) classes are nullptr.
934
757k
  auto *DRC = getFinalVRegClass(RD, MRI);
935
757k
  if (!DRC)
936
0
    return false;
937
757k
938
757k
  return DRC == getFinalVRegClass(RS, MRI);
939
757k
}
940
941
bool HexagonBitSimplify::hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
942
7.04k
      unsigned NewSub) {
943
7.04k
  if (!PreserveTiedOps)
944
0
    return false;
945
7.04k
  return llvm::any_of(MRI.use_operands(Reg),
946
12.5k
                      [NewSub] (const MachineOperand &Op) -> bool {
947
12.5k
                        return Op.getSubReg() != NewSub && 
Op.isTied()11.0k
;
948
12.5k
                      });
949
7.04k
}
950
951
namespace {
952
953
  class DeadCodeElimination {
954
  public:
955
    DeadCodeElimination(MachineFunction &mf, MachineDominatorTree &mdt)
956
      : MF(mf), HII(*MF.getSubtarget<HexagonSubtarget>().getInstrInfo()),
957
11.2k
        MDT(mdt), MRI(mf.getRegInfo()) {}
958
959
11.2k
    bool run() {
960
11.2k
      return runOnNode(MDT.getRootNode());
961
11.2k
    }
962
963
  private:
964
    bool isDead(unsigned R) const;
965
    bool runOnNode(MachineDomTreeNode *N);
966
967
    MachineFunction &MF;
968
    const HexagonInstrInfo &HII;
969
    MachineDominatorTree &MDT;
970
    MachineRegisterInfo &MRI;
971
  };
972
973
} // end anonymous namespace
974
975
93.4k
bool DeadCodeElimination::isDead(unsigned R) const {
976
93.4k
  for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; 
++I3
) {
977
86.6k
    MachineInstr *UseI = I->getParent();
978
86.6k
    if (UseI->isDebugValue())
979
3
      continue;
980
86.6k
    if (UseI->isPHI()) {
981
4.64k
      assert(!UseI->getOperand(0).getSubReg());
982
4.64k
      unsigned DR = UseI->getOperand(0).getReg();
983
4.64k
      if (DR == R)
984
0
        continue;
985
86.6k
    }
986
86.6k
    return false;
987
86.6k
  }
988
93.4k
  
return true6.80k
;
989
93.4k
}
990
991
16.9k
bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) {
992
16.9k
  bool Changed = false;
993
16.9k
994
16.9k
  for (auto *DTN : children<MachineDomTreeNode*>(N))
995
5.74k
    Changed |= runOnNode(DTN);
996
16.9k
997
16.9k
  MachineBasicBlock *B = N->getBlock();
998
16.9k
  std::vector<MachineInstr*> Instrs;
999
162k
  for (auto I = B->rbegin(), E = B->rend(); I != E; 
++I145k
)
1000
145k
    Instrs.push_back(&*I);
1001
16.9k
1002
145k
  for (auto MI : Instrs) {
1003
145k
    unsigned Opc = MI->getOpcode();
1004
145k
    // Do not touch lifetime markers. This is why the target-independent DCE
1005
145k
    // cannot be used.
1006
145k
    if (Opc == TargetOpcode::LIFETIME_START ||
1007
145k
        
Opc == TargetOpcode::LIFETIME_END145k
)
1008
240
      continue;
1009
145k
    bool Store = false;
1010
145k
    if (MI->isInlineAsm())
1011
120
      continue;
1012
145k
    // Delete PHIs if possible.
1013
145k
    if (!MI->isPHI() && 
!MI->isSafeToMove(nullptr, Store)141k
)
1014
35.1k
      continue;
1015
110k
1016
110k
    bool AllDead = true;
1017
110k
    SmallVector<unsigned,2> Regs;
1018
130k
    for (auto &Op : MI->operands()) {
1019
130k
      if (!Op.isReg() || 
!Op.isDef()117k
)
1020
20.0k
        continue;
1021
110k
      unsigned R = Op.getReg();
1022
110k
      if (!TargetRegisterInfo::isVirtualRegister(R) || 
!isDead(R)93.4k
) {
1023
103k
        AllDead = false;
1024
103k
        break;
1025
103k
      }
1026
6.80k
      Regs.push_back(R);
1027
6.80k
    }
1028
110k
    if (!AllDead)
1029
103k
      continue;
1030
6.76k
1031
6.76k
    B->erase(MI);
1032
13.5k
    for (unsigned i = 0, n = Regs.size(); i != n; 
++i6.76k
)
1033
6.76k
      MRI.markUsesInDebugValueAsUndef(Regs[i]);
1034
6.76k
    Changed = true;
1035
6.76k
  }
1036
16.9k
1037
16.9k
  return Changed;
1038
16.9k
}
1039
1040
namespace {
1041
1042
// Eliminate redundant instructions
1043
//
1044
// This transformation will identify instructions where the output register
1045
// is the same as one of its input registers. This only works on instructions
1046
// that define a single register (unlike post-increment loads, for example).
1047
// The equality check is actually more detailed: the code calculates which
1048
// bits of the output are used, and only compares these bits with the input
1049
// registers.
1050
// If the output matches an input, the instruction is replaced with COPY.
1051
// The copies will be removed by another transformation.
1052
  class RedundantInstrElimination : public Transformation {
1053
  public:
1054
    RedundantInstrElimination(BitTracker &bt, const HexagonInstrInfo &hii,
1055
          const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1056
3.34k
        : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1057
1058
    bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1059
1060
  private:
1061
    bool isLossyShiftLeft(const MachineInstr &MI, unsigned OpN,
1062
          unsigned &LostB, unsigned &LostE);
1063
    bool isLossyShiftRight(const MachineInstr &MI, unsigned OpN,
1064
          unsigned &LostB, unsigned &LostE);
1065
    bool computeUsedBits(unsigned Reg, BitVector &Bits);
1066
    bool computeUsedBits(const MachineInstr &MI, unsigned OpN, BitVector &Bits,
1067
          uint16_t Begin);
1068
    bool usedBitsEqual(BitTracker::RegisterRef RD, BitTracker::RegisterRef RS);
1069
1070
    const HexagonInstrInfo &HII;
1071
    const HexagonRegisterInfo &HRI;
1072
    MachineRegisterInfo &MRI;
1073
    BitTracker &BT;
1074
  };
1075
1076
} // end anonymous namespace
1077
1078
// Check if the instruction is a lossy shift left, where the input being
1079
// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1080
// of bit indices that are lost.
1081
bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI,
1082
9.95k
      unsigned OpN, unsigned &LostB, unsigned &LostE) {
1083
9.95k
  using namespace Hexagon;
1084
9.95k
1085
9.95k
  unsigned Opc = MI.getOpcode();
1086
9.95k
  unsigned ImN, RegN, Width;
1087
9.95k
  switch (Opc) {
1088
9.95k
    case S2_asl_i_p:
1089
1
      ImN = 2;
1090
1
      RegN = 1;
1091
1
      Width = 64;
1092
1
      break;
1093
9.95k
    case S2_asl_i_p_acc:
1094
3
    case S2_asl_i_p_and:
1095
3
    case S2_asl_i_p_nac:
1096
3
    case S2_asl_i_p_or:
1097
3
    case S2_asl_i_p_xacc:
1098
3
      ImN = 3;
1099
3
      RegN = 2;
1100
3
      Width = 64;
1101
3
      break;
1102
23
    case S2_asl_i_r:
1103
23
      ImN = 2;
1104
23
      RegN = 1;
1105
23
      Width = 32;
1106
23
      break;
1107
291
    case S2_addasl_rrri:
1108
291
    case S4_andi_asl_ri:
1109
291
    case S4_ori_asl_ri:
1110
291
    case S4_addi_asl_ri:
1111
291
    case S4_subi_asl_ri:
1112
291
    case S2_asl_i_r_acc:
1113
291
    case S2_asl_i_r_and:
1114
291
    case S2_asl_i_r_nac:
1115
291
    case S2_asl_i_r_or:
1116
291
    case S2_asl_i_r_sat:
1117
291
    case S2_asl_i_r_xacc:
1118
291
      ImN = 3;
1119
291
      RegN = 2;
1120
291
      Width = 32;
1121
291
      break;
1122
9.63k
    default:
1123
9.63k
      return false;
1124
318
  }
1125
318
1126
318
  if (RegN != OpN)
1127
136
    return false;
1128
182
1129
182
  assert(MI.getOperand(ImN).isImm());
1130
182
  unsigned S = MI.getOperand(ImN).getImm();
1131
182
  if (S == 0)
1132
0
    return false;
1133
182
  LostB = Width-S;
1134
182
  LostE = Width;
1135
182
  return true;
1136
182
}
1137
1138
// Check if the instruction is a lossy shift right, where the input being
1139
// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1140
// of bit indices that are lost.
1141
bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI,
1142
9.77k
      unsigned OpN, unsigned &LostB, unsigned &LostE) {
1143
9.77k
  using namespace Hexagon;
1144
9.77k
1145
9.77k
  unsigned Opc = MI.getOpcode();
1146
9.77k
  unsigned ImN, RegN;
1147
9.77k
  switch (Opc) {
1148
9.77k
    case S2_asr_i_p:
1149
16
    case S2_lsr_i_p:
1150
16
      ImN = 2;
1151
16
      RegN = 1;
1152
16
      break;
1153
16
    case S2_asr_i_p_acc:
1154
1
    case S2_asr_i_p_and:
1155
1
    case S2_asr_i_p_nac:
1156
1
    case S2_asr_i_p_or:
1157
1
    case S2_lsr_i_p_acc:
1158
1
    case S2_lsr_i_p_and:
1159
1
    case S2_lsr_i_p_nac:
1160
1
    case S2_lsr_i_p_or:
1161
1
    case S2_lsr_i_p_xacc:
1162
1
      ImN = 3;
1163
1
      RegN = 2;
1164
1
      break;
1165
93
    case S2_asr_i_r:
1166
93
    case S2_lsr_i_r:
1167
93
      ImN = 2;
1168
93
      RegN = 1;
1169
93
      break;
1170
93
    case S4_andi_lsr_ri:
1171
50
    case S4_ori_lsr_ri:
1172
50
    case S4_addi_lsr_ri:
1173
50
    case S4_subi_lsr_ri:
1174
50
    case S2_asr_i_r_acc:
1175
50
    case S2_asr_i_r_and:
1176
50
    case S2_asr_i_r_nac:
1177
50
    case S2_asr_i_r_or:
1178
50
    case S2_lsr_i_r_acc:
1179
50
    case S2_lsr_i_r_and:
1180
50
    case S2_lsr_i_r_nac:
1181
50
    case S2_lsr_i_r_or:
1182
50
    case S2_lsr_i_r_xacc:
1183
50
      ImN = 3;
1184
50
      RegN = 2;
1185
50
      break;
1186
50
1187
9.61k
    default:
1188
9.61k
      return false;
1189
160
  }
1190
160
1191
160
  if (RegN != OpN)
1192
28
    return false;
1193
132
1194
132
  assert(MI.getOperand(ImN).isImm());
1195
132
  unsigned S = MI.getOperand(ImN).getImm();
1196
132
  LostB = 0;
1197
132
  LostE = S;
1198
132
  return true;
1199
132
}
1200
1201
// Calculate the bit vector that corresponds to the used bits of register Reg.
1202
// The vector Bits has the same size, as the size of Reg in bits. If the cal-
1203
// culation fails (i.e. the used bits are unknown), it returns false. Other-
1204
// wise, it returns true and sets the corresponding bits in Bits.
1205
11.9k
bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) {
1206
11.9k
  BitVector Used(Bits.size());
1207
11.9k
  RegisterSet Visited;
1208
11.9k
  std::vector<unsigned> Pending;
1209
11.9k
  Pending.push_back(Reg);
1210
11.9k
1211
14.1k
  for (unsigned i = 0; i < Pending.size(); 
++i2.18k
) {
1212
13.5k
    unsigned R = Pending[i];
1213
13.5k
    if (Visited.has(R))
1214
0
      continue;
1215
13.5k
    Visited.insert(R);
1216
16.5k
    for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; 
++I2.98k
) {
1217
14.3k
      BitTracker::RegisterRef UR = *I;
1218
14.3k
      unsigned B, W;
1219
14.3k
      if (!HBS::getSubregMask(UR, B, W, MRI))
1220
0
        return false;
1221
14.3k
      MachineInstr &UseI = *I->getParent();
1222
14.3k
      if (UseI.isPHI() || 
UseI.isCopy()12.9k
) {
1223
4.37k
        unsigned DefR = UseI.getOperand(0).getReg();
1224
4.37k
        if (!TargetRegisterInfo::isVirtualRegister(DefR))
1225
2.07k
          return false;
1226
2.29k
        Pending.push_back(DefR);
1227
9.95k
      } else {
1228
9.95k
        if (!computeUsedBits(UseI, I.getOperandNo(), Used, B))
1229
9.26k
          return false;
1230
9.95k
      }
1231
14.3k
    }
1232
13.5k
  }
1233
11.9k
  Bits |= Used;
1234
608
  return true;
1235
11.9k
}
1236
1237
// Calculate the bits used by instruction MI in a register in operand OpN.
1238
// Return true/false if the calculation succeeds/fails. If is succeeds, set
1239
// used bits in Bits. This function does not reset any bits in Bits, so
1240
// subsequent calls over different instructions will result in the union
1241
// of the used bits in all these instructions.
1242
// The register in question may be used with a sub-register, whereas Bits
1243
// holds the bits for the entire register. To keep track of that, the
1244
// argument Begin indicates where in Bits is the lowest-significant bit
1245
// of the register used in operand OpN. For example, in instruction:
1246
//   %1 = S2_lsr_i_r %2:isub_hi, 10
1247
// the operand 1 is a 32-bit register, which happens to be a subregister
1248
// of the 64-bit register %2, and that subregister starts at position 32.
1249
// In this case Begin=32, since Bits[32] would be the lowest-significant bit
1250
// of %2:isub_hi.
1251
bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI,
1252
9.95k
      unsigned OpN, BitVector &Bits, uint16_t Begin) {
1253
9.95k
  unsigned Opc = MI.getOpcode();
1254
9.95k
  BitVector T(Bits.size());
1255
9.95k
  bool GotBits = HBS::getUsedBits(Opc, OpN, T, Begin, HII);
1256
9.95k
  // Even if we don't have bits yet, we could still provide some information
1257
9.95k
  // if the instruction is a lossy shift: the lost bits will be marked as
1258
9.95k
  // not used.
1259
9.95k
  unsigned LB, LE;
1260
9.95k
  if (isLossyShiftLeft(MI, OpN, LB, LE) || 
isLossyShiftRight(MI, OpN, LB, LE)9.77k
) {
1261
314
    assert(MI.getOperand(OpN).isReg());
1262
314
    BitTracker::RegisterRef RR = MI.getOperand(OpN);
1263
314
    const TargetRegisterClass *RC = HBS::getFinalVRegClass(RR, MRI);
1264
314
    uint16_t Width = HRI.getRegSizeInBits(*RC);
1265
314
1266
314
    if (!GotBits)
1267
314
      T.set(Begin, Begin+Width);
1268
314
    assert(LB <= LE && LB < Width && LE <= Width);
1269
314
    T.reset(Begin+LB, Begin+LE);
1270
314
    GotBits = true;
1271
314
  }
1272
9.95k
  if (GotBits)
1273
688
    Bits |= T;
1274
9.95k
  return GotBits;
1275
9.95k
}
1276
1277
// Calculates the used bits in RD ("defined register"), and checks if these
1278
// bits in RS ("used register") and RD are identical.
1279
bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD,
1280
11.9k
      BitTracker::RegisterRef RS) {
1281
11.9k
  const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1282
11.9k
  const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1283
11.9k
1284
11.9k
  unsigned DB, DW;
1285
11.9k
  if (!HBS::getSubregMask(RD, DB, DW, MRI))
1286
0
    return false;
1287
11.9k
  unsigned SB, SW;
1288
11.9k
  if (!HBS::getSubregMask(RS, SB, SW, MRI))
1289
0
    return false;
1290
11.9k
  if (SW != DW)
1291
0
    return false;
1292
11.9k
1293
11.9k
  BitVector Used(DC.width());
1294
11.9k
  if (!computeUsedBits(RD.Reg, Used))
1295
11.3k
    return false;
1296
608
1297
4.74k
  
for (unsigned i = 0; 608
i != DW;
++i4.14k
)
1298
4.66k
    if (Used[i+DB] && 
DC[DB+i] != SC[SB+i]1.27k
)
1299
521
      return false;
1300
608
  
return true87
;
1301
608
}
1302
1303
bool RedundantInstrElimination::processBlock(MachineBasicBlock &B,
1304
4.96k
      const RegisterSet&) {
1305
4.96k
  if (!BT.reached(&B))
1306
0
    return false;
1307
4.96k
  bool Changed = false;
1308
4.96k
1309
48.2k
  for (auto I = B.begin(), E = B.end(), NextI = I; I != E; 
++I43.2k
) {
1310
43.2k
    NextI = std::next(I);
1311
43.2k
    MachineInstr *MI = &*I;
1312
43.2k
1313
43.2k
    if (MI->getOpcode() == TargetOpcode::COPY)
1314
13.0k
      continue;
1315
30.1k
    if (MI->isPHI() || 
MI->hasUnmodeledSideEffects()29.0k
||
MI->isInlineAsm()28.3k
)
1316
1.85k
      continue;
1317
28.3k
    unsigned NumD = MI->getDesc().getNumDefs();
1318
28.3k
    if (NumD != 1)
1319
9.67k
      continue;
1320
18.6k
1321
18.6k
    BitTracker::RegisterRef RD = MI->getOperand(0);
1322
18.6k
    if (!BT.has(RD.Reg))
1323
0
      continue;
1324
18.6k
    const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1325
18.6k
    auto At = MachineBasicBlock::iterator(MI);
1326
18.6k
1327
18.6k
    // Find a source operand that is equal to the result.
1328
37.2k
    for (auto &Op : MI->uses()) {
1329
37.2k
      if (!Op.isReg())
1330
13.3k
        continue;
1331
23.8k
      BitTracker::RegisterRef RS = Op;
1332
23.8k
      if (!BT.has(RS.Reg))
1333
600
        continue;
1334
23.2k
      if (!HBS::isTransparentCopy(RD, RS, MRI))
1335
11.2k
        continue;
1336
11.9k
1337
11.9k
      unsigned BN, BW;
1338
11.9k
      if (!HBS::getSubregMask(RS, BN, BW, MRI))
1339
0
        continue;
1340
11.9k
1341
11.9k
      const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1342
11.9k
      if (!usedBitsEqual(RD, RS) && 
!HBS::isEqual(DC, 0, SC, BN, BW)11.8k
)
1343
11.7k
        continue;
1344
171
1345
171
      // If found, replace the instruction with a COPY.
1346
171
      const DebugLoc &DL = MI->getDebugLoc();
1347
171
      const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
1348
171
      unsigned NewR = MRI.createVirtualRegister(FRC);
1349
171
      MachineInstr *CopyI =
1350
171
          BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1351
171
            .addReg(RS.Reg, 0, RS.Sub);
1352
171
      HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1353
171
      // This pass can create copies between registers that don't have the
1354
171
      // exact same values. Updating the tracker has to involve updating
1355
171
      // all dependent cells. Example:
1356
171
      //   %1  = inst %2     ; %1 != %2, but used bits are equal
1357
171
      //
1358
171
      //   %3  = copy %2     ; <- inserted
1359
171
      //   ... = %3          ; <- replaced from %2
1360
171
      // Indirectly, we can create a "copy" between %1 and %2 even
1361
171
      // though their exact values do not match.
1362
171
      BT.visit(*CopyI);
1363
171
      Changed = true;
1364
171
      break;
1365
171
    }
1366
18.6k
  }
1367
4.96k
1368
4.96k
  return Changed;
1369
4.96k
}
1370
1371
namespace {
1372
1373
// Recognize instructions that produce constant values known at compile-time.
1374
// Replace them with register definitions that load these constants directly.
1375
  class ConstGeneration : public Transformation {
1376
  public:
1377
    ConstGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1378
        MachineRegisterInfo &mri)
1379
3.34k
      : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1380
1381
    bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1382
    static bool isTfrConst(const MachineInstr &MI);
1383
1384
  private:
1385
    unsigned genTfrConst(const TargetRegisterClass *RC, int64_t C,
1386
        MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL);
1387
1388
    const HexagonInstrInfo &HII;
1389
    MachineRegisterInfo &MRI;
1390
    BitTracker &BT;
1391
  };
1392
1393
} // end anonymous namespace
1394
1395
71.7k
bool ConstGeneration::isTfrConst(const MachineInstr &MI) {
1396
71.7k
  unsigned Opc = MI.getOpcode();
1397
71.7k
  switch (Opc) {
1398
71.7k
    case Hexagon::A2_combineii:
1399
6.82k
    case Hexagon::A4_combineii:
1400
6.82k
    case Hexagon::A2_tfrsi:
1401
6.82k
    case Hexagon::A2_tfrpi:
1402
6.82k
    case Hexagon::PS_true:
1403
6.82k
    case Hexagon::PS_false:
1404
6.82k
    case Hexagon::CONST32:
1405
6.82k
    case Hexagon::CONST64:
1406
6.82k
      return true;
1407
64.9k
  }
1408
64.9k
  return false;
1409
64.9k
}
1410
1411
// Generate a transfer-immediate instruction that is appropriate for the
1412
// register class and the actual value being transferred.
1413
unsigned ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C,
1414
230
      MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL) {
1415
230
  unsigned Reg = MRI.createVirtualRegister(RC);
1416
230
  if (RC == &Hexagon::IntRegsRegClass) {
1417
107
    BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), Reg)
1418
107
        .addImm(int32_t(C));
1419
107
    return Reg;
1420
107
  }
1421
123
1422
123
  if (RC == &Hexagon::DoubleRegsRegClass) {
1423
94
    if (isInt<8>(C)) {
1424
74
      BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrpi), Reg)
1425
74
          .addImm(C);
1426
74
      return Reg;
1427
74
    }
1428
20
1429
20
    unsigned Lo = Lo_32(C), Hi = Hi_32(C);
1430
20
    if (isInt<8>(Lo) || 
isInt<8>(Hi)7
) {
1431
15
      unsigned Opc = isInt<8>(Lo) ? 
Hexagon::A2_combineii13
1432
15
                                  : 
Hexagon::A4_combineii2
;
1433
15
      BuildMI(B, At, DL, HII.get(Opc), Reg)
1434
15
          .addImm(int32_t(Hi))
1435
15
          .addImm(int32_t(Lo));
1436
15
      return Reg;
1437
15
    }
1438
5
1439
5
    BuildMI(B, At, DL, HII.get(Hexagon::CONST64), Reg)
1440
5
        .addImm(C);
1441
5
    return Reg;
1442
5
  }
1443
29
1444
29
  if (RC == &Hexagon::PredRegsRegClass) {
1445
15
    unsigned Opc;
1446
15
    if (C == 0)
1447
15
      Opc = Hexagon::PS_false;
1448
0
    else if ((C & 0xFF) == 0xFF)
1449
0
      Opc = Hexagon::PS_true;
1450
0
    else
1451
0
      return 0;
1452
15
    BuildMI(B, At, DL, HII.get(Opc), Reg);
1453
15
    return Reg;
1454
15
  }
1455
14
1456
14
  return 0;
1457
14
}
1458
1459
4.96k
bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1460
4.96k
  if (!BT.reached(&B))
1461
0
    return false;
1462
4.96k
  bool Changed = false;
1463
4.96k
  RegisterSet Defs;
1464
4.96k
1465
48.0k
  for (auto I = B.begin(), E = B.end(); I != E; 
++I43.0k
) {
1466
43.0k
    if (isTfrConst(*I))
1467
3.30k
      continue;
1468
39.7k
    Defs.clear();
1469
39.7k
    HBS::getInstrDefs(*I, Defs);
1470
39.7k
    if (Defs.count() != 1)
1471
13.8k
      continue;
1472
25.9k
    unsigned DR = Defs.find_first();
1473
25.9k
    if (!TargetRegisterInfo::isVirtualRegister(DR))
1474
0
      continue;
1475
25.9k
    uint64_t U;
1476
25.9k
    const BitTracker::RegisterCell &DRC = BT.lookup(DR);
1477
25.9k
    if (HBS::getConst(DRC, 0, DRC.width(), U)) {
1478
230
      int64_t C = U;
1479
230
      DebugLoc DL = I->getDebugLoc();
1480
230
      auto At = I->isPHI() ? 
B.getFirstNonPHI()9
:
I221
;
1481
230
      unsigned ImmReg = genTfrConst(MRI.getRegClass(DR), C, B, At, DL);
1482
230
      if (ImmReg) {
1483
216
        HBS::replaceReg(DR, ImmReg, MRI);
1484
216
        BT.put(ImmReg, DRC);
1485
216
        Changed = true;
1486
216
      }
1487
230
    }
1488
25.9k
  }
1489
4.96k
  return Changed;
1490
4.96k
}
1491
1492
namespace {
1493
1494
// Identify pairs of available registers which hold identical values.
1495
// In such cases, only one of them needs to be calculated, the other one
1496
// will be defined as a copy of the first.
1497
  class CopyGeneration : public Transformation {
1498
  public:
1499
    CopyGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1500
        const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1501
3.34k
      : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1502
1503
    bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1504
1505
  private:
1506
    bool findMatch(const BitTracker::RegisterRef &Inp,
1507
        BitTracker::RegisterRef &Out, const RegisterSet &AVs);
1508
1509
    const HexagonInstrInfo &HII;
1510
    const HexagonRegisterInfo &HRI;
1511
    MachineRegisterInfo &MRI;
1512
    BitTracker &BT;
1513
    RegisterSet Forbidden;
1514
  };
1515
1516
// Eliminate register copies RD = RS, by replacing the uses of RD with
1517
// with uses of RS.
1518
  class CopyPropagation : public Transformation {
1519
  public:
1520
    CopyPropagation(const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1521
3.34k
        : Transformation(false), HRI(hri), MRI(mri) {}
1522
1523
    bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1524
1525
    static bool isCopyReg(unsigned Opc, bool NoConv);
1526
1527
  private:
1528
    bool propagateRegCopy(MachineInstr &MI);
1529
1530
    const HexagonRegisterInfo &HRI;
1531
    MachineRegisterInfo &MRI;
1532
  };
1533
1534
} // end anonymous namespace
1535
1536
/// Check if there is a register in AVs that is identical to Inp. If so,
1537
/// set Out to the found register. The output may be a pair Reg:Sub.
1538
bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp,
1539
17.6k
      BitTracker::RegisterRef &Out, const RegisterSet &AVs) {
1540
17.6k
  if (!BT.has(Inp.Reg))
1541
0
    return false;
1542
17.6k
  const BitTracker::RegisterCell &InpRC = BT.lookup(Inp.Reg);
1543
17.6k
  auto *FRC = HBS::getFinalVRegClass(Inp, MRI);
1544
17.6k
  unsigned B, W;
1545
17.6k
  if (!HBS::getSubregMask(Inp, B, W, MRI))
1546
0
    return false;
1547
17.6k
1548
1.22M
  
for (unsigned R = AVs.find_first(); 17.6k
R;
R = AVs.find_next(R)1.20M
) {
1549
1.20M
    if (!BT.has(R) || Forbidden[R])
1550
5.51k
      continue;
1551
1.19M
    const BitTracker::RegisterCell &RC = BT.lookup(R);
1552
1.19M
    unsigned RW = RC.width();
1553
1.19M
    if (W == RW) {
1554
876k
      if (FRC != MRI.getRegClass(R))
1555
147k
        continue;
1556
729k
      if (!HBS::isTransparentCopy(R, Inp, MRI))
1557
0
        continue;
1558
729k
      if (!HBS::isEqual(InpRC, B, RC, 0, W))
1559
729k
        continue;
1560
283
      Out.Reg = R;
1561
283
      Out.Sub = 0;
1562
283
      return true;
1563
283
    }
1564
321k
    // Check if there is a super-register, whose part (with a subregister)
1565
321k
    // is equal to the input.
1566
321k
    // Only do double registers for now.
1567
321k
    if (W*2 != RW)
1568
216k
      continue;
1569
104k
    if (MRI.getRegClass(R) != &Hexagon::DoubleRegsRegClass)
1570
34.4k
      continue;
1571
70.1k
1572
70.1k
    if (HBS::isEqual(InpRC, B, RC, 0, W))
1573
19
      Out.Sub = Hexagon::isub_lo;
1574
70.1k
    else if (HBS::isEqual(InpRC, B, RC, W, W))
1575
44
      Out.Sub = Hexagon::isub_hi;
1576
70.1k
    else
1577
70.1k
      continue;
1578
63
    Out.Reg = R;
1579
63
    if (HBS::isTransparentCopy(Out, Inp, MRI))
1580
63
      return true;
1581
63
  }
1582
17.6k
  
return false17.3k
;
1583
17.6k
}
1584
1585
bool CopyGeneration::processBlock(MachineBasicBlock &B,
1586
4.96k
      const RegisterSet &AVs) {
1587
4.96k
  if (!BT.reached(&B))
1588
0
    return false;
1589
4.96k
  RegisterSet AVB(AVs);
1590
4.96k
  bool Changed = false;
1591
4.96k
  RegisterSet Defs;
1592
4.96k
1593
48.3k
  for (auto I = B.begin(), E = B.end(), NextI = I; I != E;
1594
43.4k
       ++I, AVB.insert(Defs)) {
1595
43.4k
    NextI = std::next(I);
1596
43.4k
    Defs.clear();
1597
43.4k
    HBS::getInstrDefs(*I, Defs);
1598
43.4k
1599
43.4k
    unsigned Opc = I->getOpcode();
1600
43.4k
    if (CopyPropagation::isCopyReg(Opc, false) ||
1601
43.4k
        
ConstGeneration::isTfrConst(*I)28.7k
)
1602
18.2k
      continue;
1603
25.2k
1604
25.2k
    DebugLoc DL = I->getDebugLoc();
1605
25.2k
    auto At = I->isPHI() ? 
B.getFirstNonPHI()1.11k
:
I24.1k
;
1606
25.2k
1607
40.4k
    for (unsigned R = Defs.find_first(); R; 
R = Defs.find_next(R)15.2k
) {
1608
15.2k
      BitTracker::RegisterRef MR;
1609
15.2k
      auto *FRC = HBS::getFinalVRegClass(R, MRI);
1610
15.2k
1611
15.2k
      if (findMatch(R, MR, AVB)) {
1612
159
        unsigned NewR = MRI.createVirtualRegister(FRC);
1613
159
        BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1614
159
          .addReg(MR.Reg, 0, MR.Sub);
1615
159
        BT.put(BitTracker::RegisterRef(NewR), BT.get(MR));
1616
159
        HBS::replaceReg(R, NewR, MRI);
1617
159
        Forbidden.insert(R);
1618
159
        continue;
1619
159
      }
1620
15.1k
1621
15.1k
      if (FRC == &Hexagon::DoubleRegsRegClass ||
1622
15.1k
          
FRC == &Hexagon::HvxWRRegClass13.8k
) {
1623
2.28k
        // Try to generate REG_SEQUENCE.
1624
2.28k
        unsigned SubLo = HRI.getHexagonSubRegIndex(*FRC, Hexagon::ps_sub_lo);
1625
2.28k
        unsigned SubHi = HRI.getHexagonSubRegIndex(*FRC, Hexagon::ps_sub_hi);
1626
2.28k
        BitTracker::RegisterRef TL = { R, SubLo };
1627
2.28k
        BitTracker::RegisterRef TH = { R, SubHi };
1628
2.28k
        BitTracker::RegisterRef ML, MH;
1629
2.28k
        if (findMatch(TL, ML, AVB) && 
findMatch(TH, MH, AVB)98
) {
1630
89
          auto *FRC = HBS::getFinalVRegClass(R, MRI);
1631
89
          unsigned NewR = MRI.createVirtualRegister(FRC);
1632
89
          BuildMI(B, At, DL, HII.get(TargetOpcode::REG_SEQUENCE), NewR)
1633
89
            .addReg(ML.Reg, 0, ML.Sub)
1634
89
            .addImm(SubLo)
1635
89
            .addReg(MH.Reg, 0, MH.Sub)
1636
89
            .addImm(SubHi);
1637
89
          BT.put(BitTracker::RegisterRef(NewR), BT.get(R));
1638
89
          HBS::replaceReg(R, NewR, MRI);
1639
89
          Forbidden.insert(R);
1640
89
        }
1641
2.28k
      }
1642
15.1k
    }
1643
25.2k
  }
1644
4.96k
1645
4.96k
  return Changed;
1646
4.96k
}
1647
1648
87.0k
bool CopyPropagation::isCopyReg(unsigned Opc, bool NoConv) {
1649
87.0k
  switch (Opc) {
1650
87.0k
    case TargetOpcode::COPY:
1651
29.6k
    case TargetOpcode::REG_SEQUENCE:
1652
29.6k
    case Hexagon::A4_combineir:
1653
29.6k
    case Hexagon::A4_combineri:
1654
29.6k
      return true;
1655
29.6k
    case Hexagon::A2_tfr:
1656
158
    case Hexagon::A2_tfrp:
1657
158
    case Hexagon::A2_combinew:
1658
158
    case Hexagon::V6_vcombine:
1659
158
      return NoConv;
1660
57.3k
    default:
1661
57.3k
      break;
1662
57.3k
  }
1663
57.3k
  return false;
1664
57.3k
}
1665
1666
15.0k
bool CopyPropagation::propagateRegCopy(MachineInstr &MI) {
1667
15.0k
  bool Changed = false;
1668
15.0k
  unsigned Opc = MI.getOpcode();
1669
15.0k
  BitTracker::RegisterRef RD = MI.getOperand(0);
1670
15.0k
  assert(MI.getOperand(0).getSubReg() == 0);
1671
15.0k
1672
15.0k
  switch (Opc) {
1673
15.0k
    case TargetOpcode::COPY:
1674
13.4k
    case Hexagon::A2_tfr:
1675
13.4k
    case Hexagon::A2_tfrp: {
1676
13.4k
      BitTracker::RegisterRef RS = MI.getOperand(1);
1677
13.4k
      if (!HBS::isTransparentCopy(RD, RS, MRI))
1678
8.77k
        break;
1679
4.64k
      if (RS.Sub != 0)
1680
3.86k
        Changed = HBS::replaceRegWithSub(RD.Reg, RS.Reg, RS.Sub, MRI);
1681
778
      else
1682
778
        Changed = HBS::replaceReg(RD.Reg, RS.Reg, MRI);
1683
4.64k
      break;
1684
4.64k
    }
1685
4.64k
    case TargetOpcode::REG_SEQUENCE: {
1686
1.50k
      BitTracker::RegisterRef SL, SH;
1687
1.50k
      if (HBS::parseRegSequence(MI, SL, SH, MRI)) {
1688
1.50k
        const TargetRegisterClass &RC = *MRI.getRegClass(RD.Reg);
1689
1.50k
        unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo);
1690
1.50k
        unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi);
1691
1.50k
        Changed  = HBS::replaceSubWithSub(RD.Reg, SubLo, SL.Reg, SL.Sub, MRI);
1692
1.50k
        Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, SH.Reg, SH.Sub, MRI);
1693
1.50k
      }
1694
1.50k
      break;
1695
4.64k
    }
1696
4.64k
    case Hexagon::A2_combinew:
1697
79
    case Hexagon::V6_vcombine: {
1698
79
      const TargetRegisterClass &RC = *MRI.getRegClass(RD.Reg);
1699
79
      unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo);
1700
79
      unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi);
1701
79
      BitTracker::RegisterRef RH = MI.getOperand(1), RL = MI.getOperand(2);
1702
79
      Changed  = HBS::replaceSubWithSub(RD.Reg, SubLo, RL.Reg, RL.Sub, MRI);
1703
79
      Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, RH.Reg, RH.Sub, MRI);
1704
79
      break;
1705
79
    }
1706
79
    case Hexagon::A4_combineir:
1707
9
    case Hexagon::A4_combineri: {
1708
9
      unsigned SrcX = (Opc == Hexagon::A4_combineir) ? 2 : 
10
;
1709
9
      unsigned Sub = (Opc == Hexagon::A4_combineir) ? Hexagon::isub_lo
1710
9
                                                    : 
Hexagon::isub_hi0
;
1711
9
      BitTracker::RegisterRef RS = MI.getOperand(SrcX);
1712
9
      Changed = HBS::replaceSubWithSub(RD.Reg, Sub, RS.Reg, RS.Sub, MRI);
1713
9
      break;
1714
15.0k
    }
1715
15.0k
  }
1716
15.0k
  return Changed;
1717
15.0k
}
1718
1719
4.96k
bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1720
4.96k
  std::vector<MachineInstr*> Instrs;
1721
48.6k
  for (auto I = B.rbegin(), E = B.rend(); I != E; 
++I43.6k
)
1722
43.6k
    Instrs.push_back(&*I);
1723
4.96k
1724
4.96k
  bool Changed = false;
1725
43.6k
  for (auto I : Instrs) {
1726
43.6k
    unsigned Opc = I->getOpcode();
1727
43.6k
    if (!CopyPropagation::isCopyReg(Opc, true))
1728
28.6k
      continue;
1729
15.0k
    Changed |= propagateRegCopy(*I);
1730
15.0k
  }
1731
4.96k
1732
4.96k
  return Changed;
1733
4.96k
}
1734
1735
namespace {
1736
1737
// Recognize patterns that can be simplified and replace them with the
1738
// simpler forms.
1739
// This is by no means complete
1740
  class BitSimplification : public Transformation {
1741
  public:
1742
    BitSimplification(BitTracker &bt, const MachineDominatorTree &mdt,
1743
        const HexagonInstrInfo &hii, const HexagonRegisterInfo &hri,
1744
        MachineRegisterInfo &mri, MachineFunction &mf)
1745
      : Transformation(true), MDT(mdt), HII(hii), HRI(hri), MRI(mri),
1746
3.34k
        MF(mf), BT(bt) {}
1747
1748
    bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1749
1750
  private:
1751
    struct RegHalf : public BitTracker::RegisterRef {
1752
      bool Low;  // Low/High halfword.
1753
    };
1754
1755
    bool matchHalf(unsigned SelfR, const BitTracker::RegisterCell &RC,
1756
          unsigned B, RegHalf &RH);
1757
    bool validateReg(BitTracker::RegisterRef R, unsigned Opc, unsigned OpNum);
1758
1759
    bool matchPackhl(unsigned SelfR, const BitTracker::RegisterCell &RC,
1760
          BitTracker::RegisterRef &Rs, BitTracker::RegisterRef &Rt);
1761
    unsigned getCombineOpcode(bool HLow, bool LLow);
1762
1763
    bool genStoreUpperHalf(MachineInstr *MI);
1764
    bool genStoreImmediate(MachineInstr *MI);
1765
    bool genPackhl(MachineInstr *MI, BitTracker::RegisterRef RD,
1766
          const BitTracker::RegisterCell &RC);
1767
    bool genExtractHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1768
          const BitTracker::RegisterCell &RC);
1769
    bool genCombineHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1770
          const BitTracker::RegisterCell &RC);
1771
    bool genExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1772
          const BitTracker::RegisterCell &RC);
1773
    bool genBitSplit(MachineInstr *MI, BitTracker::RegisterRef RD,
1774
          const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1775
    bool simplifyTstbit(MachineInstr *MI, BitTracker::RegisterRef RD,
1776
          const BitTracker::RegisterCell &RC);
1777
    bool simplifyExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1778
          const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1779
    bool simplifyRCmp0(MachineInstr *MI, BitTracker::RegisterRef RD);
1780
1781
    // Cache of created instructions to avoid creating duplicates.
1782
    // XXX Currently only used by genBitSplit.
1783
    std::vector<MachineInstr*> NewMIs;
1784
1785
    const MachineDominatorTree &MDT;
1786
    const HexagonInstrInfo &HII;
1787
    const HexagonRegisterInfo &HRI;
1788
    MachineRegisterInfo &MRI;
1789
    MachineFunction &MF;
1790
    BitTracker &BT;
1791
  };
1792
1793
} // end anonymous namespace
1794
1795
// Check if the bits [B..B+16) in register cell RC form a valid halfword,
1796
// i.e. [0..16), [16..32), etc. of some register. If so, return true and
1797
// set the information about the found register in RH.
1798
bool BitSimplification::matchHalf(unsigned SelfR,
1799
17.4k
      const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) {
1800
17.4k
  // XXX This could be searching in the set of available registers, in case
1801
17.4k
  // the match is not exact.
1802
17.4k
1803
17.4k
  // Match 16-bit chunks, where the RC[B..B+15] references exactly one
1804
17.4k
  // register and all the bits B..B+15 match between RC and the register.
1805
17.4k
  // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... },
1806
17.4k
  // and RC = { [0]:0 [1-15]:v1[1-15]... }.
1807
17.4k
  bool Low = false;
1808
17.4k
  unsigned I = B;
1809
65.0k
  while (I < B+16 && 
RC[I].num()62.3k
)
1810
47.6k
    I++;
1811
17.4k
  if (I == B+16)
1812
2.64k
    return false;
1813
14.7k
1814
14.7k
  unsigned Reg = RC[I].RefI.Reg;
1815
14.7k
  unsigned P = RC[I].RefI.Pos;    // The RefI.Pos will be advanced by I-B.
1816
14.7k
  if (P < I-B)
1817
147
    return false;
1818
14.6k
  unsigned Pos = P - (I-B);
1819
14.6k
1820
14.6k
  if (Reg == 0 || Reg == SelfR)    // Don't match "self".
1821
11.7k
    return false;
1822
2.87k
  if (!TargetRegisterInfo::isVirtualRegister(Reg))
1823
0
    return false;
1824
2.87k
  if (!BT.has(Reg))
1825
0
    return false;
1826
2.87k
1827
2.87k
  const BitTracker::RegisterCell &SC = BT.lookup(Reg);
1828
2.87k
  if (Pos+16 > SC.width())
1829
85
    return false;
1830
2.78k
1831
20.3k
  
for (unsigned i = 0; 2.78k
i < 16;
++i17.5k
) {
1832
19.7k
    const BitTracker::BitValue &RV = RC[i+B];
1833
19.7k
    if (RV.Type == BitTracker::BitValue::Ref) {
1834
18.1k
      if (RV.RefI.Reg != Reg)
1835
1.57k
        return false;
1836
16.6k
      if (RV.RefI.Pos != i+Pos)
1837
76
        return false;
1838
16.5k
      continue;
1839
16.5k
    }
1840
1.54k
    if (RC[i+B] != SC[i+Pos])
1841
512
      return false;
1842
1.54k
  }
1843
2.78k
1844
2.78k
  unsigned Sub = 0;
1845
631
  switch (Pos) {
1846
631
    case 0:
1847
328
      Sub = Hexagon::isub_lo;
1848
328
      Low = true;
1849
328
      break;
1850
631
    case 16:
1851
94
      Sub = Hexagon::isub_lo;
1852
94
      Low = false;
1853
94
      break;
1854
631
    case 32:
1855
24
      Sub = Hexagon::isub_hi;
1856
24
      Low = true;
1857
24
      break;
1858
631
    case 48:
1859
21
      Sub = Hexagon::isub_hi;
1860
21
      Low = false;
1861
21
      break;
1862
631
    default:
1863
164
      return false;
1864
467
  }
1865
467
1866
467
  RH.Reg = Reg;
1867
467
  RH.Sub = Sub;
1868
467
  RH.Low = Low;
1869
467
  // If the subregister is not valid with the register, set it to 0.
1870
467
  if (!HBS::getFinalVRegClass(RH, MRI))
1871
364
    RH.Sub = 0;
1872
467
1873
467
  return true;
1874
467
}
1875
1876
bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc,
1877
306
      unsigned OpNum) {
1878
306
  auto *OpRC = HII.getRegClass(HII.get(Opc), OpNum, &HRI, MF);
1879
306
  auto *RRC = HBS::getFinalVRegClass(R, MRI);
1880
306
  return OpRC->hasSubClassEq(RRC);
1881
306
}
1882
1883
// Check if RC matches the pattern of a S2_packhl. If so, return true and
1884
// set the inputs Rs and Rt.
1885
bool BitSimplification::matchPackhl(unsigned SelfR,
1886
      const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs,
1887
1.29k
      BitTracker::RegisterRef &Rt) {
1888
1.29k
  RegHalf L1, H1, L2, H2;
1889
1.29k
1890
1.29k
  if (!matchHalf(SelfR, RC, 0, L2)  || 
!matchHalf(SelfR, RC, 16, L1)29
)
1891
1.28k
    return false;
1892
10
  if (!matchHalf(SelfR, RC, 32, H2) || 
!matchHalf(SelfR, RC, 48, H1)4
)
1893
8
    return false;
1894
2
1895
2
  // Rs = H1.L1, Rt = H2.L2
1896
2
  if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || 
H1.Low0
||
!L1.Low0
)
1897
2
    return false;
1898
0
  if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low)
1899
0
    return false;
1900
0
1901
0
  Rs = H1;
1902
0
  Rt = H2;
1903
0
  return true;
1904
0
}
1905
1906
37
unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) {
1907
37
  return HLow ? 
LLow 35
?
Hexagon::A2_combine_ll34
1908
35
                     : 
Hexagon::A2_combine_lh1
1909
37
              : 
LLow 2
?
Hexagon::A2_combine_hl0
1910
2
                     : Hexagon::A2_combine_hh;
1911
37
}
1912
1913
// If MI stores the upper halfword of a register (potentially obtained via
1914
// shifts or extracts), replace it with a storerf instruction. This could
1915
// cause the "extraction" code to become dead.
1916
3.02k
bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) {
1917
3.02k
  unsigned Opc = MI->getOpcode();
1918
3.02k
  if (Opc != Hexagon::S2_storerh_io)
1919
2.96k
    return false;
1920
60
1921
60
  MachineOperand &ValOp = MI->getOperand(2);
1922
60
  BitTracker::RegisterRef RS = ValOp;
1923
60
  if (!BT.has(RS.Reg))
1924
0
    return false;
1925
60
  const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1926
60
  RegHalf H;
1927
60
  if (!matchHalf(0, RC, 0, H))
1928
5
    return false;
1929
55
  if (H.Low)
1930
41
    return false;
1931
14
  MI->setDesc(HII.get(Hexagon::S2_storerf_io));
1932
14
  ValOp.setReg(H.Reg);
1933
14
  ValOp.setSubReg(H.Sub);
1934
14
  return true;
1935
14
}
1936
1937
// If MI stores a value known at compile-time, and the value is within a range
1938
// that avoids using constant-extenders, replace it with a store-immediate.
1939
3.01k
bool BitSimplification::genStoreImmediate(MachineInstr *MI) {
1940
3.01k
  unsigned Opc = MI->getOpcode();
1941
3.01k
  unsigned Align = 0;
1942
3.01k
  switch (Opc) {
1943
3.01k
    case Hexagon::S2_storeri_io:
1944
475
      Align++;
1945
475
      LLVM_FALLTHROUGH;
1946
521
    case Hexagon::S2_storerh_io:
1947
521
      Align++;
1948
521
      LLVM_FALLTHROUGH;
1949
578
    case Hexagon::S2_storerb_io:
1950
578
      break;
1951
2.43k
    default:
1952
2.43k
      return false;
1953
578
  }
1954
578
1955
578
  // Avoid stores to frame-indices (due to an unknown offset).
1956
578
  if (!MI->getOperand(0).isReg())
1957
263
    return false;
1958
315
  MachineOperand &OffOp = MI->getOperand(1);
1959
315
  if (!OffOp.isImm())
1960
3
    return false;
1961
312
1962
312
  int64_t Off = OffOp.getImm();
1963
312
  // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x).
1964
312
  if (!isUIntN(6+Align, Off) || 
(Off & ((1<<Align)-1))256
)
1965
56
    return false;
1966
256
  // Source register:
1967
256
  BitTracker::RegisterRef RS = MI->getOperand(2);
1968
256
  if (!BT.has(RS.Reg))
1969
0
    return false;
1970
256
  const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1971
256
  uint64_t U;
1972
256
  if (!HBS::getConst(RC, 0, RC.width(), U))
1973
255
    return false;
1974
1
1975
1
  // Only consider 8-bit values to avoid constant-extenders.
1976
1
  int V;
1977
1
  switch (Opc) {
1978
1
    case Hexagon::S2_storerb_io:
1979
0
      V = int8_t(U);
1980
0
      break;
1981
1
    case Hexagon::S2_storerh_io:
1982
0
      V = int16_t(U);
1983
0
      break;
1984
1
    case Hexagon::S2_storeri_io:
1985
1
      V = int32_t(U);
1986
1
      break;
1987
1
    default:
1988
0
      // Opc is already checked above to be one of the three store instructions.
1989
0
      // This silences a -Wuninitialized false positive on GCC 5.4.
1990
0
      llvm_unreachable("Unexpected store opcode");
1991
1
  }
1992
1
  if (!isInt<8>(V))
1993
1
    return false;
1994
0
1995
0
  MI->RemoveOperand(2);
1996
0
  switch (Opc) {
1997
0
    case Hexagon::S2_storerb_io:
1998
0
      MI->setDesc(HII.get(Hexagon::S4_storeirb_io));
1999
0
      break;
2000
0
    case Hexagon::S2_storerh_io:
2001
0
      MI->setDesc(HII.get(Hexagon::S4_storeirh_io));
2002
0
      break;
2003
0
    case Hexagon::S2_storeri_io:
2004
0
      MI->setDesc(HII.get(Hexagon::S4_storeiri_io));
2005
0
      break;
2006
0
  }
2007
0
  MI->addOperand(MachineOperand::CreateImm(V));
2008
0
  return true;
2009
0
}
2010
2011
// If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
2012
// last instruction in a sequence that results in something equivalent to
2013
// the pack-halfwords. The intent is to cause the entire sequence to become
2014
// dead.
2015
bool BitSimplification::genPackhl(MachineInstr *MI,
2016
1.30k
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2017
1.30k
  unsigned Opc = MI->getOpcode();
2018
1.30k
  if (Opc == Hexagon::S2_packhl)
2019
2
    return false;
2020
1.29k
  BitTracker::RegisterRef Rs, Rt;
2021
1.29k
  if (!matchPackhl(RD.Reg, RC, Rs, Rt))
2022
1.29k
    return false;
2023
0
  if (!validateReg(Rs, Hexagon::S2_packhl, 1) ||
2024
0
      !validateReg(Rt, Hexagon::S2_packhl, 2))
2025
0
    return false;
2026
0
2027
0
  MachineBasicBlock &B = *MI->getParent();
2028
0
  unsigned NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2029
0
  DebugLoc DL = MI->getDebugLoc();
2030
0
  auto At = MI->isPHI() ? B.getFirstNonPHI()
2031
0
                        : MachineBasicBlock::iterator(MI);
2032
0
  BuildMI(B, At, DL, HII.get(Hexagon::S2_packhl), NewR)
2033
0
      .addReg(Rs.Reg, 0, Rs.Sub)
2034
0
      .addReg(Rt.Reg, 0, Rt.Sub);
2035
0
  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2036
0
  BT.put(BitTracker::RegisterRef(NewR), RC);
2037
0
  return true;
2038
0
}
2039
2040
// If MI produces halfword of the input in the low half of the output,
2041
// replace it with zero-extend or extractu.
2042
bool BitSimplification::genExtractHalf(MachineInstr *MI,
2043
7.91k
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2044
7.91k
  RegHalf L;
2045
7.91k
  // Check for halfword in low 16 bits, zeros elsewhere.
2046
7.91k
  if (!matchHalf(RD.Reg, RC, 0, L) || 
!HBS::isZero(RC, 16, 16)166
)
2047
7.87k
    return false;
2048
49
2049
49
  unsigned Opc = MI->getOpcode();
2050
49
  MachineBasicBlock &B = *MI->getParent();
2051
49
  DebugLoc DL = MI->getDebugLoc();
2052
49
2053
49
  // Prefer zxth, since zxth can go in any slot, while extractu only in
2054
49
  // slots 2 and 3.
2055
49
  unsigned NewR = 0;
2056
49
  auto At = MI->isPHI() ? 
B.getFirstNonPHI()0
2057
49
                        : MachineBasicBlock::iterator(MI);
2058
49
  if (L.Low && 
Opc != Hexagon::A2_zxth23
) {
2059
6
    if (validateReg(L, Hexagon::A2_zxth, 1)) {
2060
0
      NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2061
0
      BuildMI(B, At, DL, HII.get(Hexagon::A2_zxth), NewR)
2062
0
          .addReg(L.Reg, 0, L.Sub);
2063
0
    }
2064
43
  } else if (!L.Low && 
Opc != Hexagon::S2_lsr_i_r26
) {
2065
2
    if (validateReg(L, Hexagon::S2_lsr_i_r, 1)) {
2066
2
      NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2067
2
      BuildMI(B, MI, DL, HII.get(Hexagon::S2_lsr_i_r), NewR)
2068
2
          .addReg(L.Reg, 0, L.Sub)
2069
2
          .addImm(16);
2070
2
    }
2071
2
  }
2072
49
  if (NewR == 0)
2073
47
    return false;
2074
2
  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2075
2
  BT.put(BitTracker::RegisterRef(NewR), RC);
2076
2
  return true;
2077
2
}
2078
2079
// If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
2080
// combine.
2081
bool BitSimplification::genCombineHalf(MachineInstr *MI,
2082
7.91k
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2083
7.91k
  RegHalf L, H;
2084
7.91k
  // Check for combine h/l
2085
7.91k
  if (!matchHalf(RD.Reg, RC, 0, L) || 
!matchHalf(RD.Reg, RC, 16, H)164
)
2086
7.88k
    return false;
2087
37
  // Do nothing if this is just a reg copy.
2088
37
  if (L.Reg == H.Reg && 
L.Sub == H.Sub14
&&
!H.Low9
&&
L.Low2
)
2089
0
    return false;
2090
37
2091
37
  unsigned Opc = MI->getOpcode();
2092
37
  unsigned COpc = getCombineOpcode(H.Low, L.Low);
2093
37
  if (COpc == Opc)
2094
11
    return false;
2095
26
  if (!validateReg(H, COpc, 1) || !validateReg(L, COpc, 2))
2096
0
    return false;
2097
26
2098
26
  MachineBasicBlock &B = *MI->getParent();
2099
26
  DebugLoc DL = MI->getDebugLoc();
2100
26
  unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2101
26
  auto At = MI->isPHI() ? 
B.getFirstNonPHI()0
2102
26
                        : MachineBasicBlock::iterator(MI);
2103
26
  BuildMI(B, At, DL, HII.get(COpc), NewR)
2104
26
      .addReg(H.Reg, 0, H.Sub)
2105
26
      .addReg(L.Reg, 0, L.Sub);
2106
26
  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2107
26
  BT.put(BitTracker::RegisterRef(NewR), RC);
2108
26
  return true;
2109
26
}
2110
2111
// If MI resets high bits of a register and keeps the lower ones, replace it
2112
// with zero-extend byte/half, and-immediate, or extractu, as appropriate.
2113
bool BitSimplification::genExtractLow(MachineInstr *MI,
2114
7.89k
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2115
7.89k
  unsigned Opc = MI->getOpcode();
2116
7.89k
  switch (Opc) {
2117
7.89k
    case Hexagon::A2_zxtb:
2118
76
    case Hexagon::A2_zxth:
2119
76
    case Hexagon::S2_extractu:
2120
76
      return false;
2121
7.81k
  }
2122
7.81k
  if (Opc == Hexagon::A2_andir && 
MI->getOperand(2).isImm()56
) {
2123
56
    int32_t Imm = MI->getOperand(2).getImm();
2124
56
    if (isInt<10>(Imm))
2125
43
      return false;
2126
7.77k
  }
2127
7.77k
2128
7.77k
  if (MI->hasUnmodeledSideEffects() || 
MI->isInlineAsm()7.76k
)
2129
4
    return false;
2130
7.76k
  unsigned W = RC.width();
2131
52.9k
  while (W > 0 && 
RC[W-1].is(0)52.5k
)
2132
45.1k
    W--;
2133
7.76k
  if (W == 0 || 
W == RC.width()7.35k
)
2134
6.19k
    return false;
2135
1.57k
  unsigned NewOpc = (W == 8)  ? 
Hexagon::A2_zxtb346
2136
1.57k
                  : 
(W == 16) 1.23k
?
Hexagon::A2_zxth218
2137
1.23k
                  : 
(W < 10) 1.01k
?
Hexagon::A2_andir599
2138
1.01k
                  : 
Hexagon::S2_extractu415
;
2139
1.57k
  MachineBasicBlock &B = *MI->getParent();
2140
1.57k
  DebugLoc DL = MI->getDebugLoc();
2141
1.57k
2142
2.72k
  for (auto &Op : MI->uses()) {
2143
2.72k
    if (!Op.isReg())
2144
1.67k
      continue;
2145
1.05k
    BitTracker::RegisterRef RS = Op;
2146
1.05k
    if (!BT.has(RS.Reg))
2147
41
      continue;
2148
1.01k
    const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2149
1.01k
    unsigned BN, BW;
2150
1.01k
    if (!HBS::getSubregMask(RS, BN, BW, MRI))
2151
0
      continue;
2152
1.01k
    if (BW < W || !HBS::isEqual(RC, 0, SC, BN, W))
2153
1.01k
      continue;
2154
6
    if (!validateReg(RS, NewOpc, 1))
2155
6
      continue;
2156
0
2157
0
    unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2158
0
    auto At = MI->isPHI() ? B.getFirstNonPHI()
2159
0
                          : MachineBasicBlock::iterator(MI);
2160
0
    auto MIB = BuildMI(B, At, DL, HII.get(NewOpc), NewR)
2161
0
                  .addReg(RS.Reg, 0, RS.Sub);
2162
0
    if (NewOpc == Hexagon::A2_andir)
2163
0
      MIB.addImm((1 << W) - 1);
2164
0
    else if (NewOpc == Hexagon::S2_extractu)
2165
0
      MIB.addImm(W).addImm(0);
2166
0
    HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2167
0
    BT.put(BitTracker::RegisterRef(NewR), RC);
2168
0
    return true;
2169
0
  }
2170
1.57k
  return false;
2171
1.57k
}
2172
2173
bool BitSimplification::genBitSplit(MachineInstr *MI,
2174
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2175
7.96k
      const RegisterSet &AVs) {
2176
7.96k
  if (!GenBitSplit)
2177
0
    return false;
2178
7.96k
  if (MaxBitSplit.getNumOccurrences()) {
2179
0
    if (CountBitSplit >= MaxBitSplit)
2180
0
      return false;
2181
7.96k
  }
2182
7.96k
2183
7.96k
  unsigned Opc = MI->getOpcode();
2184
7.96k
  switch (Opc) {
2185
7.96k
    case Hexagon::A4_bitsplit:
2186
0
    case Hexagon::A4_bitspliti:
2187
0
      return false;
2188
7.96k
  }
2189
7.96k
2190
7.96k
  unsigned W = RC.width();
2191
7.96k
  if (W != 32)
2192
0
    return false;
2193
7.96k
2194
26.1k
  
auto ctlz = [] (const BitTracker::RegisterCell &C) -> unsigned 7.96k
{
2195
26.1k
    unsigned Z = C.width();
2196
329k
    while (Z > 0 && 
C[Z-1].is(0)328k
)
2197
303k
      --Z;
2198
26.1k
    return C.width() - Z;
2199
26.1k
  };
2200
7.96k
2201
7.96k
  // Count the number of leading zeros in the target RC.
2202
7.96k
  unsigned Z = ctlz(RC);
2203
7.96k
  if (Z == 0 || 
Z == W2.12k
)
2204
6.25k
    return false;
2205
1.71k
2206
1.71k
  // A simplistic analysis: assume the source register (the one being split)
2207
1.71k
  // is fully unknown, and that all its bits are self-references.
2208
1.71k
  const BitTracker::BitValue &B0 = RC[0];
2209
1.71k
  if (B0.Type != BitTracker::BitValue::Ref)
2210
855
    return false;
2211
860
2212
860
  unsigned SrcR = B0.RefI.Reg;
2213
860
  unsigned SrcSR = 0;
2214
860
  unsigned Pos = B0.RefI.Pos;
2215
860
2216
860
  // All the non-zero bits should be consecutive bits from the same register.
2217
7.67k
  for (unsigned i = 1; i < W-Z; 
++i6.81k
) {
2218
6.99k
    const BitTracker::BitValue &V = RC[i];
2219
6.99k
    if (V.Type != BitTracker::BitValue::Ref)
2220
86
      return false;
2221
6.90k
    if (V.RefI.Reg != SrcR || 
V.RefI.Pos != Pos+i6.81k
)
2222
93
      return false;
2223
6.90k
  }
2224
860
2225
860
  // Now, find the other bitfield among AVs.
2226
20.8k
  
for (unsigned S = AVs.find_first(); 681
S;
S = AVs.find_next(S)20.1k
) {
2227
20.1k
    // The number of leading zeros here should be the number of trailing
2228
20.1k
    // non-zeros in RC.
2229
20.1k
    unsigned SRC = MRI.getRegClass(S)->getID();
2230
20.1k
    if (SRC != Hexagon::IntRegsRegClassID &&
2231
20.1k
        
SRC != Hexagon::DoubleRegsRegClassID1.92k
)
2232
1.43k
      continue;
2233
18.6k
    if (!BT.has(S))
2234
17
      continue;
2235
18.6k
    const BitTracker::RegisterCell &SC = BT.lookup(S);
2236
18.6k
    if (SC.width() != W || 
ctlz(SC) != W-Z18.2k
)
2237
18.3k
      continue;
2238
304
    // The Z lower bits should now match SrcR.
2239
304
    const BitTracker::BitValue &S0 = SC[0];
2240
304
    if (S0.Type != BitTracker::BitValue::Ref || 
S0.RefI.Reg != SrcR291
)
2241
296
      continue;
2242
8
    unsigned P = S0.RefI.Pos;
2243
8
2244
8
    if (Pos <= P && 
(Pos + W-Z) != P6
)
2245
4
      continue;
2246
4
    if (P < Pos && 
(P + Z) != Pos2
)
2247
0
      continue;
2248
4
    // The starting bitfield position must be at a subregister boundary.
2249
4
    if (std::min(P, Pos) != 0 && 
std::min(P, Pos) != 320
)
2250
0
      continue;
2251
4
2252
4
    unsigned I;
2253
50
    for (I = 1; I < Z; 
++I46
) {
2254
46
      const BitTracker::BitValue &V = SC[I];
2255
46
      if (V.Type != BitTracker::BitValue::Ref)
2256
0
        break;
2257
46
      if (V.RefI.Reg != SrcR || V.RefI.Pos != P+I)
2258
0
        break;
2259
46
    }
2260
4
    if (I != Z)
2261
0
      continue;
2262
4
2263
4
    // Generate bitsplit where S is defined.
2264
4
    if (MaxBitSplit.getNumOccurrences())
2265
0
      CountBitSplit++;
2266
4
    MachineInstr *DefS = MRI.getVRegDef(S);
2267
4
    assert(DefS != nullptr);
2268
4
    DebugLoc DL = DefS->getDebugLoc();
2269
4
    MachineBasicBlock &B = *DefS->getParent();
2270
4
    auto At = DefS->isPHI() ? 
B.getFirstNonPHI()0
2271
4
                            : MachineBasicBlock::iterator(DefS);
2272
4
    if (MRI.getRegClass(SrcR)->getID() == Hexagon::DoubleRegsRegClassID)
2273
0
      SrcSR = (std::min(Pos, P) == 32) ? Hexagon::isub_hi : Hexagon::isub_lo;
2274
4
    if (!validateReg({SrcR,SrcSR}, Hexagon::A4_bitspliti, 1))
2275
0
      continue;
2276
4
    unsigned ImmOp = Pos <= P ? 
W-Z2
:
Z2
;
2277
4
2278
4
    // Find an existing bitsplit instruction if one already exists.
2279
4
    unsigned NewR = 0;
2280
4
    for (MachineInstr *In : NewMIs) {
2281
0
      if (In->getOpcode() != Hexagon::A4_bitspliti)
2282
0
        continue;
2283
0
      MachineOperand &Op1 = In->getOperand(1);
2284
0
      if (Op1.getReg() != SrcR || Op1.getSubReg() != SrcSR)
2285
0
        continue;
2286
0
      if (In->getOperand(2).getImm() != ImmOp)
2287
0
        continue;
2288
0
      // Check if the target register is available here.
2289
0
      MachineOperand &Op0 = In->getOperand(0);
2290
0
      MachineInstr *DefI = MRI.getVRegDef(Op0.getReg());
2291
0
      assert(DefI != nullptr);
2292
0
      if (!MDT.dominates(DefI, &*At))
2293
0
        continue;
2294
0
2295
0
      // Found one that can be reused.
2296
0
      assert(Op0.getSubReg() == 0);
2297
0
      NewR = Op0.getReg();
2298
0
      break;
2299
0
    }
2300
4
    if (!NewR) {
2301
4
      NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2302
4
      auto NewBS = BuildMI(B, At, DL, HII.get(Hexagon::A4_bitspliti), NewR)
2303
4
                      .addReg(SrcR, 0, SrcSR)
2304
4
                      .addImm(ImmOp);
2305
4
      NewMIs.push_back(NewBS);
2306
4
    }
2307
4
    if (Pos <= P) {
2308
2
      HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_lo, MRI);
2309
2
      HBS::replaceRegWithSub(S,      NewR, Hexagon::isub_hi, MRI);
2310
2
    } else {
2311
2
      HBS::replaceRegWithSub(S,      NewR, Hexagon::isub_lo, MRI);
2312
2
      HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_hi, MRI);
2313
2
    }
2314
4
    return true;
2315
4
  }
2316
681
2317
681
  
return false677
;
2318
681
}
2319
2320
// Check for tstbit simplification opportunity, where the bit being checked
2321
// can be tracked back to another register. For example:
2322
//   %2 = S2_lsr_i_r  %1, 5
2323
//   %3 = S2_tstbit_i %2, 0
2324
// =>
2325
//   %3 = S2_tstbit_i %1, 5
2326
bool BitSimplification::simplifyTstbit(MachineInstr *MI,
2327
1.79k
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2328
1.79k
  unsigned Opc = MI->getOpcode();
2329
1.79k
  if (Opc != Hexagon::S2_tstbit_i)
2330
1.75k
    return false;
2331
41
2332
41
  unsigned BN = MI->getOperand(2).getImm();
2333
41
  BitTracker::RegisterRef RS = MI->getOperand(1);
2334
41
  unsigned F, W;
2335
41
  DebugLoc DL = MI->getDebugLoc();
2336
41
  if (!BT.has(RS.Reg) || !HBS::getSubregMask(RS, F, W, MRI))
2337
0
    return false;
2338
41
  MachineBasicBlock &B = *MI->getParent();
2339
41
  auto At = MI->isPHI() ? 
B.getFirstNonPHI()0
2340
41
                        : MachineBasicBlock::iterator(MI);
2341
41
2342
41
  const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2343
41
  const BitTracker::BitValue &V = SC[F+BN];
2344
41
  if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) {
2345
2
    const TargetRegisterClass *TC = MRI.getRegClass(V.RefI.Reg);
2346
2
    // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is
2347
2
    // a double register, need to use a subregister and adjust bit
2348
2
    // number.
2349
2
    unsigned P = std::numeric_limits<unsigned>::max();
2350
2
    BitTracker::RegisterRef RR(V.RefI.Reg, 0);
2351
2
    if (TC == &Hexagon::DoubleRegsRegClass) {
2352
0
      P = V.RefI.Pos;
2353
0
      RR.Sub = Hexagon::isub_lo;
2354
0
      if (P >= 32) {
2355
0
        P -= 32;
2356
0
        RR.Sub = Hexagon::isub_hi;
2357
0
      }
2358
2
    } else if (TC == &Hexagon::IntRegsRegClass) {
2359
1
      P = V.RefI.Pos;
2360
1
    }
2361
2
    if (P != std::numeric_limits<unsigned>::max()) {
2362
1
      unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2363
1
      BuildMI(B, At, DL, HII.get(Hexagon::S2_tstbit_i), NewR)
2364
1
          .addReg(RR.Reg, 0, RR.Sub)
2365
1
          .addImm(P);
2366
1
      HBS::replaceReg(RD.Reg, NewR, MRI);
2367
1
      BT.put(NewR, RC);
2368
1
      return true;
2369
1
    }
2370
39
  } else if (V.is(0) || V.is(1)) {
2371
0
    unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2372
0
    unsigned NewOpc = V.is(0) ? Hexagon::PS_false : Hexagon::PS_true;
2373
0
    BuildMI(B, At, DL, HII.get(NewOpc), NewR);
2374
0
    HBS::replaceReg(RD.Reg, NewR, MRI);
2375
0
    return true;
2376
0
  }
2377
40
2378
40
  return false;
2379
40
}
2380
2381
// Detect whether RD is a bitfield extract (sign- or zero-extended) of
2382
// some register from the AVs set. Create a new corresponding instruction
2383
// at the location of MI. The intent is to recognize situations where
2384
// a sequence of instructions performs an operation that is equivalent to
2385
// an extract operation, such as a shift left followed by a shift right.
2386
bool BitSimplification::simplifyExtractLow(MachineInstr *MI,
2387
      BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2388
9.26k
      const RegisterSet &AVs) {
2389
9.26k
  if (!GenExtract)
2390
6
    return false;
2391
9.26k
  if (MaxExtract.getNumOccurrences()) {
2392
0
    if (CountExtract >= MaxExtract)
2393
0
      return false;
2394
0
    CountExtract++;
2395
0
  }
2396
9.26k
2397
9.26k
  unsigned W = RC.width();
2398
9.26k
  unsigned RW = W;
2399
9.26k
  unsigned Len;
2400
9.26k
  bool Signed;
2401
9.26k
2402
9.26k
  // The code is mostly class-independent, except for the part that generates
2403
9.26k
  // the extract instruction, and establishes the source register (in case it
2404
9.26k
  // needs to use a subregister).
2405
9.26k
  const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2406
9.26k
  if (FRC != &Hexagon::IntRegsRegClass && 
FRC != &Hexagon::DoubleRegsRegClass1.30k
)
2407
0
    return false;
2408
9.26k
  assert(RD.Sub == 0);
2409
9.26k
2410
9.26k
  // Observation:
2411
9.26k
  // If the cell has a form of 00..0xx..x with k zeros and n remaining
2412
9.26k
  // bits, this could be an extractu of the n bits, but it could also be
2413
9.26k
  // an extractu of a longer field which happens to have 0s in the top
2414
9.26k
  // bit positions.
2415
9.26k
  // The same logic applies to sign-extended fields.
2416
9.26k
  //
2417
9.26k
  // Do not check for the extended extracts, since it would expand the
2418
9.26k
  // search space quite a bit. The search may be expensive as it is.
2419
9.26k
2420
9.26k
  const BitTracker::BitValue &TopV = RC[W-1];
2421
9.26k
2422
9.26k
  // Eliminate candidates that have self-referential bits, since they
2423
9.26k
  // cannot be extracts from other registers. Also, skip registers that
2424
9.26k
  // have compile-time constant values.
2425
9.26k
  bool IsConst = true;
2426
91.3k
  for (unsigned I = 0; I != W; 
++I82.0k
) {
2427
89.1k
    const BitTracker::BitValue &V = RC[I];
2428
89.1k
    if (V.Type == BitTracker::BitValue::Ref && 
V.RefI.Reg == RD.Reg27.1k
)
2429
7.06k
      return false;
2430
82.0k
    IsConst = IsConst && 
(51.8k
V.is(0)51.8k
||
V.is(1)7.40k
);
2431
82.0k
  }
2432
9.26k
  
if (2.19k
IsConst2.19k
)
2433
1.33k
    return false;
2434
864
2435
864
  if (TopV.is(0) || 
TopV.is(1)398
) {
2436
468
    bool S = TopV.is(1);
2437
10.5k
    for (--W; W > 0 && RC[W-1].is(S); 
--W10.0k
)
2438
10.0k
      ;
2439
468
    Len = W;
2440
468
    Signed = S;
2441
468
    // The sign bit must be a part of the field being extended.
2442
468
    if (Signed)
2443
2
      ++Len;
2444
468
  } else {
2445
396
    // This could still be a sign-extended extract.
2446
396
    assert(TopV.Type == BitTracker::BitValue::Ref);
2447
396
    if (TopV.RefI.Reg == RD.Reg || TopV.RefI.Pos == W-1)
2448
169
      return false;
2449
1.92k
    
for (--W; 227
W > 0 &&
RC[W-1] == TopV1.91k
;
--W1.70k
)
2450
1.70k
      ;
2451
227
    // The top bits of RC are copies of TopV. One occurrence of TopV will
2452
227
    // be a part of the field.
2453
227
    Len = W + 1;
2454
227
    Signed = true;
2455
227
  }
2456
864
2457
864
  // This would be just a copy. It should be handled elsewhere.
2458
864
  
if (695
Len == RW695
)
2459
145
    return false;
2460
550
2461
550
  LLVM_DEBUG({
2462
550
    dbgs() << __func__ << " on reg: " << printReg(RD.Reg, &HRI, RD.Sub)
2463
550
           << ", MI: " << *MI;
2464
550
    dbgs() << "Cell: " << RC << '\n';
2465
550
    dbgs() << "Expected bitfield size: " << Len << " bits, "
2466
550
           << (Signed ? "sign" : "zero") << "-extended\n";
2467
550
  });
2468
550
2469
550
  bool Changed = false;
2470
550
2471
17.1k
  for (unsigned R = AVs.find_first(); R != 0; 
R = AVs.find_next(R)16.6k
) {
2472
16.7k
    if (!BT.has(R))
2473
3
      continue;
2474
16.7k
    const BitTracker::RegisterCell &SC = BT.lookup(R);
2475
16.7k
    unsigned SW = SC.width();
2476
16.7k
2477
16.7k
    // The source can be longer than the destination, as long as its size is
2478
16.7k
    // a multiple of the size of the destination. Also, we would need to be
2479
16.7k
    // able to refer to the subregister in the source that would be of the
2480
16.7k
    // same size as the destination, but only check the sizes here.
2481
16.7k
    if (SW < RW || 
(SW % RW) != 015.2k
)
2482
1.45k
      continue;
2483
15.2k
2484
15.2k
    // The field can start at any offset in SC as long as it contains Len
2485
15.2k
    // bits and does not cross subregister boundary (if the source register
2486
15.2k
    // is longer than the destination).
2487
15.2k
    unsigned Off = 0;
2488
615k
    while (Off <= SW-Len) {
2489
600k
      unsigned OE = (Off+Len)/RW;
2490
600k
      if (OE != Off/RW) {
2491
26.5k
        // The assumption here is that if the source (R) is longer than the
2492
26.5k
        // destination, then the destination is a sequence of words of
2493
26.5k
        // size RW, and each such word in R can be accessed via a subregister.
2494
26.5k
        //
2495
26.5k
        // If the beginning and the end of the field cross the subregister
2496
26.5k
        // boundary, advance to the next subregister.
2497
26.5k
        Off = OE*RW;
2498
26.5k
        continue;
2499
26.5k
      }
2500
574k
      if (HBS::isEqual(RC, 0, SC, Off, Len))
2501
236
        break;
2502
574k
      ++Off;
2503
574k
    }
2504
15.2k
2505
15.2k
    if (Off > SW-Len)
2506
15.0k
      continue;
2507
236
2508
236
    // Found match.
2509
236
    unsigned ExtOpc = 0;
2510
236
    if (Off == 0) {
2511
147
      if (Len == 8)
2512
57
        ExtOpc = Signed ? 
Hexagon::A2_sxtb17
:
Hexagon::A2_zxtb40
;
2513
90
      else if (Len == 16)
2514
55
        ExtOpc = Signed ? 
Hexagon::A2_sxth38
:
Hexagon::A2_zxth17
;
2515
35
      else if (Len < 10 && 
!Signed26
)
2516
26
        ExtOpc = Hexagon::A2_andir;
2517
147
    }
2518
236
    if (ExtOpc == 0) {
2519
98
      ExtOpc =
2520
98
          Signed ? 
(RW == 32 18
?
Hexagon::S4_extract18
:
Hexagon::S4_extractp0
)
2521
98
                 : 
(RW == 32 80
?
Hexagon::S2_extractu43
:
Hexagon::S2_extractup37
);
2522
98
    }
2523
236
    unsigned SR = 0;
2524
236
    // This only recognizes isub_lo and isub_hi.
2525
236
    if (RW != SW && 
RW*2 != SW29
)
2526
0
      continue;
2527
236
    if (RW != SW)
2528
29
      SR = (Off/RW == 0) ? 
Hexagon::isub_lo21
:
Hexagon::isub_hi8
;
2529
236
    Off = Off % RW;
2530
236
2531
236
    if (!validateReg({R,SR}, ExtOpc, 1))
2532
6
      continue;
2533
230
2534
230
    // Don't generate the same instruction as the one being optimized.
2535
230
    if (MI->getOpcode() == ExtOpc) {
2536
188
      // All possible ExtOpc's have the source in operand(1).
2537
188
      const MachineOperand &SrcOp = MI->getOperand(1);
2538
188
      if (SrcOp.getReg() == R)
2539
155
        continue;
2540
75
    }
2541
75
2542
75
    DebugLoc DL = MI->getDebugLoc();
2543
75
    MachineBasicBlock &B = *MI->getParent();
2544
75
    unsigned NewR = MRI.createVirtualRegister(FRC);
2545
75
    auto At = MI->isPHI() ? 
B.getFirstNonPHI()0
2546
75
                          : MachineBasicBlock::iterator(MI);
2547
75
    auto MIB = BuildMI(B, At, DL, HII.get(ExtOpc), NewR)
2548
75
                  .addReg(R, 0, SR);
2549
75
    switch (ExtOpc) {
2550
75
      case Hexagon::A2_sxtb:
2551
2
      case Hexagon::A2_zxtb:
2552
2
      case Hexagon::A2_sxth:
2553
2
      case Hexagon::A2_zxth:
2554
2
        break;
2555
5
      case Hexagon::A2_andir:
2556
5
        MIB.addImm((1u << Len) - 1);
2557
5
        break;
2558
68
      case Hexagon::S4_extract:
2559
68
      case Hexagon::S2_extractu:
2560
68
      case Hexagon::S4_extractp:
2561
68
      case Hexagon::S2_extractup:
2562
68
        MIB.addImm(Len)
2563
68
           .addImm(Off);
2564
68
        break;
2565
68
      default:
2566
0
        llvm_unreachable("Unexpected opcode");
2567
75
    }
2568
75
2569
75
    HBS::replaceReg(RD.Reg, NewR, MRI);
2570
75
    BT.put(BitTracker::RegisterRef(NewR), RC);
2571
75
    Changed = true;
2572
75
    break;
2573
75
  }
2574
550
2575
550
  return Changed;
2576
550
}
2577
2578
bool BitSimplification::simplifyRCmp0(MachineInstr *MI,
2579
7.89k
      BitTracker::RegisterRef RD) {
2580
7.89k
  unsigned Opc = MI->getOpcode();
2581
7.89k
  if (Opc != Hexagon::A4_rcmpeqi && 
Opc != Hexagon::A4_rcmpneqi7.88k
)
2582
7.87k
    return false;
2583
19
  MachineOperand &CmpOp = MI->getOperand(2);
2584
19
  if (!CmpOp.isImm() || CmpOp.getImm() != 0)
2585
10
    return false;
2586
9
2587
9
  const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2588
9
  if (FRC != &Hexagon::IntRegsRegClass && 
FRC != &Hexagon::DoubleRegsRegClass0
)
2589
0
    return false;
2590
9
  assert(RD.Sub == 0);
2591
9
2592
9
  MachineBasicBlock &B = *MI->getParent();
2593
9
  const DebugLoc &DL = MI->getDebugLoc();
2594
9
  auto At = MI->isPHI() ? 
B.getFirstNonPHI()0
2595
9
                        : MachineBasicBlock::iterator(MI);
2596
9
  bool KnownZ = true;
2597
9
  bool KnownNZ = false;
2598
9
2599
9
  BitTracker::RegisterRef SR = MI->getOperand(1);
2600
9
  if (!BT.has(SR.Reg))
2601
0
    return false;
2602
9
  const BitTracker::RegisterCell &SC = BT.lookup(SR.Reg);
2603
9
  unsigned F, W;
2604
9
  if (!HBS::getSubregMask(SR, F, W, MRI))
2605
0
    return false;
2606
9
2607
297
  
for (uint16_t I = F; 9
I != F+W;
++I288
) {
2608
288
    const BitTracker::BitValue &V = SC[I];
2609
288
    if (!V.is(0))
2610
46
      KnownZ = false;
2611
288
    if (V.is(1))
2612
2
      KnownNZ = true;
2613
288
  }
2614
9
2615
9
  auto ReplaceWithConst = [&] (int C) {
2616
6
    unsigned NewR = MRI.createVirtualRegister(FRC);
2617
6
    BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), NewR)
2618
6
      .addImm(C);
2619
6
    HBS::replaceReg(RD.Reg, NewR, MRI);
2620
6
    BitTracker::RegisterCell NewRC(W);
2621
198
    for (uint16_t I = 0; I != W; 
++I192
) {
2622
192
      NewRC[I] = BitTracker::BitValue(C & 1);
2623
192
      C = unsigned(C) >> 1;
2624
192
    }
2625
6
    BT.put(BitTracker::RegisterRef(NewR), NewRC);
2626
6
    return true;
2627
6
  };
2628
9
2629
9
  auto IsNonZero = [] (const MachineOperand &Op) {
2630
8
    if (Op.isGlobal() || 
Op.isBlockAddress()7
)
2631
1
      return true;
2632
7
    if (Op.isImm())
2633
7
      return Op.getImm() != 0;
2634
0
    if (Op.isCImm())
2635
0
      return !Op.getCImm()->isZero();
2636
0
    if (Op.isFPImm())
2637
0
      return !Op.getFPImm()->isZero();
2638
0
    return false;
2639
0
  };
2640
9
2641
9
  auto IsZero = [] (const MachineOperand &Op) {
2642
4
    if (Op.isGlobal() || Op.isBlockAddress())
2643
0
      return false;
2644
4
    if (Op.isImm())
2645
4
      return Op.getImm() == 0;
2646
0
    if (Op.isCImm())
2647
0
      return Op.getCImm()->isZero();
2648
0
    if (Op.isFPImm())
2649
0
      return Op.getFPImm()->isZero();
2650
0
    return false;
2651
0
  };
2652
9
2653
9
  // If the source register is known to be 0 or non-0, the comparison can
2654
9
  // be folded to a load of a constant.
2655
9
  if (KnownZ || 
KnownNZ7
) {
2656
4
    assert(KnownZ != KnownNZ && "Register cannot be both 0 and non-0");
2657
4
    return ReplaceWithConst(KnownZ == (Opc == Hexagon::A4_rcmpeqi));
2658
4
  }
2659
5
2660
5
  // Special case: if the compare comes from a C2_muxii, then we know the
2661
5
  // two possible constants that can be the source value.
2662
5
  MachineInstr *InpDef = MRI.getVRegDef(SR.Reg);
2663
5
  if (!InpDef)
2664
0
    return false;
2665
5
  if (SR.Sub == 0 && InpDef->getOpcode() == Hexagon::C2_muxii) {
2666
4
    MachineOperand &Src1 = InpDef->getOperand(2);
2667
4
    MachineOperand &Src2 = InpDef->getOperand(3);
2668
4
    // Check if both are non-zero.
2669
4
    bool KnownNZ1 = IsNonZero(Src1), KnownNZ2 = IsNonZero(Src2);
2670
4
    if (KnownNZ1 && 
KnownNZ23
)
2671
2
      return ReplaceWithConst(Opc == Hexagon::A4_rcmpneqi);
2672
2
    // Check if both are zero.
2673
2
    bool KnownZ1 = IsZero(Src1), KnownZ2 = IsZero(Src2);
2674
2
    if (KnownZ1 && 
KnownZ21
)
2675
0
      return ReplaceWithConst(Opc == Hexagon::A4_rcmpeqi);
2676
2
2677
2
    // If for both operands we know that they are either 0 or non-0,
2678
2
    // replace the comparison with a C2_muxii, using the same predicate
2679
2
    // register, but with operands substituted with 0/1 accordingly.
2680
2
    if ((KnownZ1 || 
KnownNZ11
) && (KnownZ2 ||
KnownNZ21
)) {
2681
2
      unsigned NewR = MRI.createVirtualRegister(FRC);
2682
2
      BuildMI(B, At, DL, HII.get(Hexagon::C2_muxii), NewR)
2683
2
        .addReg(InpDef->getOperand(1).getReg())
2684
2
        .addImm(KnownZ1 == (Opc == Hexagon::A4_rcmpeqi))
2685
2
        .addImm(KnownZ2 == (Opc == Hexagon::A4_rcmpeqi));
2686
2
      HBS::replaceReg(RD.Reg, NewR, MRI);
2687
2
      // Create a new cell with only the least significant bit unknown.
2688
2
      BitTracker::RegisterCell NewRC(W);
2689
2
      NewRC[0] = BitTracker::BitValue::self();
2690
2
      NewRC.fill(1, W, BitTracker::BitValue::Zero);
2691
2
      BT.put(BitTracker::RegisterRef(NewR), NewRC);
2692
2
      return true;
2693
2
    }
2694
1
  }
2695
1
2696
1
  return false;
2697
1
}
2698
2699
bool BitSimplification::processBlock(MachineBasicBlock &B,
2700
4.96k
      const RegisterSet &AVs) {
2701
4.96k
  if (!BT.reached(&B))
2702
0
    return false;
2703
4.96k
  bool Changed = false;
2704
4.96k
  RegisterSet AVB = AVs;
2705
4.96k
  RegisterSet Defs;
2706
4.96k
2707
42.4k
  for (auto I = B.begin(), E = B.end(); I != E; 
++I, AVB.insert(Defs)37.5k
) {
2708
37.5k
    MachineInstr *MI = &*I;
2709
37.5k
    Defs.clear();
2710
37.5k
    HBS::getInstrDefs(*MI, Defs);
2711
37.5k
2712
37.5k
    unsigned Opc = MI->getOpcode();
2713
37.5k
    if (Opc == TargetOpcode::COPY || 
Opc == TargetOpcode::REG_SEQUENCE28.7k
)
2714
9.46k
      continue;
2715
28.0k
2716
28.0k
    if (MI->mayStore()) {
2717
3.02k
      bool T = genStoreUpperHalf(MI);
2718
3.02k
      T = T || 
genStoreImmediate(MI)3.01k
;
2719
3.02k
      Changed |= T;
2720
3.02k
      continue;
2721
3.02k
    }
2722
25.0k
2723
25.0k
    if (Defs.count() != 1)
2724
7.71k
      continue;
2725
17.3k
    const MachineOperand &Op0 = MI->getOperand(0);
2726
17.3k
    if (!Op0.isReg() || 
!Op0.isDef()17.3k
)
2727
3
      continue;
2728
17.3k
    BitTracker::RegisterRef RD = Op0;
2729
17.3k
    if (!BT.has(RD.Reg))
2730
0
      continue;
2731
17.3k
    const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2732
17.3k
    const BitTracker::RegisterCell &RC = BT.lookup(RD.Reg);
2733
17.3k
2734
17.3k
    if (FRC->getID() == Hexagon::DoubleRegsRegClassID) {
2735
1.30k
      bool T = genPackhl(MI, RD, RC);
2736
1.30k
      T = T || simplifyExtractLow(MI, RD, RC, AVB);
2737
1.30k
      Changed |= T;
2738
1.30k
      continue;
2739
1.30k
    }
2740
16.0k
2741
16.0k
    if (FRC->getID() == Hexagon::IntRegsRegClassID) {
2742
7.96k
      bool T = genBitSplit(MI, RD, RC, AVB);
2743
7.96k
      T = T || 
simplifyExtractLow(MI, RD, RC, AVB)7.96k
;
2744
7.96k
      T = T || 
genExtractHalf(MI, RD, RC)7.91k
;
2745
7.96k
      T = T || 
genCombineHalf(MI, RD, RC)7.91k
;
2746
7.96k
      T = T || 
genExtractLow(MI, RD, RC)7.89k
;
2747
7.96k
      T = T || 
simplifyRCmp0(MI, RD)7.89k
;
2748
7.96k
      Changed |= T;
2749
7.96k
      continue;
2750
7.96k
    }
2751
8.06k
2752
8.06k
    if (FRC->getID() == Hexagon::PredRegsRegClassID) {
2753
1.79k
      bool T = simplifyTstbit(MI, RD, RC);
2754
1.79k
      Changed |= T;
2755
1.79k
      continue;
2756
1.79k
    }
2757
8.06k
  }
2758
4.96k
  return Changed;
2759
4.96k
}
2760
2761
3.35k
bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) {
2762
3.35k
  if (skipFunction(MF.getFunction()))
2763
10
    return false;
2764
3.34k
2765
3.34k
  auto &HST = MF.getSubtarget<HexagonSubtarget>();
2766
3.34k
  auto &HRI = *HST.getRegisterInfo();
2767
3.34k
  auto &HII = *HST.getInstrInfo();
2768
3.34k
2769
3.34k
  MDT = &getAnalysis<MachineDominatorTree>();
2770
3.34k
  MachineRegisterInfo &MRI = MF.getRegInfo();
2771
3.34k
  bool Changed;
2772
3.34k
2773
3.34k
  Changed = DeadCodeElimination(MF, *MDT).run();
2774
3.34k
2775
3.34k
  const HexagonEvaluator HE(HRI, MRI, HII, MF);
2776
3.34k
  BitTracker BT(HE, MF);
2777
3.34k
  LLVM_DEBUG(BT.trace(true));
2778
3.34k
  BT.run();
2779
3.34k
2780
3.34k
  MachineBasicBlock &Entry = MF.front();
2781
3.34k
2782
3.34k
  RegisterSet AIG;  // Available registers for IG.
2783
3.34k
  ConstGeneration ImmG(BT, HII, MRI);
2784
3.34k
  Changed |= visitBlock(Entry, ImmG, AIG);
2785
3.34k
2786
3.34k
  RegisterSet ARE;  // Available registers for RIE.
2787
3.34k
  RedundantInstrElimination RIE(BT, HII, HRI, MRI);
2788
3.34k
  bool Ried = visitBlock(Entry, RIE, ARE);
2789
3.34k
  if (Ried) {
2790
83
    Changed = true;
2791
83
    BT.run();
2792
83
  }
2793
3.34k
2794
3.34k
  RegisterSet ACG;  // Available registers for CG.
2795
3.34k
  CopyGeneration CopyG(BT, HII, HRI, MRI);
2796
3.34k
  Changed |= visitBlock(Entry, CopyG, ACG);
2797
3.34k
2798
3.34k
  RegisterSet ACP;  // Available registers for CP.
2799
3.34k
  CopyPropagation CopyP(HRI, MRI);
2800
3.34k
  Changed |= visitBlock(Entry, CopyP, ACP);
2801
3.34k
2802
3.34k
  Changed = DeadCodeElimination(MF, *MDT).run() || 
Changed2.23k
;
2803
3.34k
2804
3.34k
  BT.run();
2805
3.34k
  RegisterSet ABS;  // Available registers for BS.
2806
3.34k
  BitSimplification BitS(BT, *MDT, HII, HRI, MRI, MF);
2807
3.34k
  Changed |= visitBlock(Entry, BitS, ABS);
2808
3.34k
2809
3.34k
  Changed = DeadCodeElimination(MF, *MDT).run() || 
Changed3.28k
;
2810
3.34k
2811
3.34k
  if (Changed) {
2812
1.20k
    for (auto &B : MF)
2813
2.07k
      for (auto &I : B)
2814
21.1k
        I.clearKillInfo();
2815
1.20k
    DeadCodeElimination(MF, *MDT).run();
2816
1.20k
  }
2817
3.34k
  return Changed;
2818
3.34k
}
2819
2820
// Recognize loops where the code at the end of the loop matches the code
2821
// before the entry of the loop, and the matching code is such that is can
2822
// be simplified. This pass relies on the bit simplification above and only
2823
// prepares code in a way that can be handled by the bit simplifcation.
2824
//
2825
// This is the motivating testcase (and explanation):
2826
//
2827
// {
2828
//   loop0(.LBB0_2, r1)      // %for.body.preheader
2829
//   r5:4 = memd(r0++#8)
2830
// }
2831
// {
2832
//   r3 = lsr(r4, #16)
2833
//   r7:6 = combine(r5, r5)
2834
// }
2835
// {
2836
//   r3 = insert(r5, #16, #16)
2837
//   r7:6 = vlsrw(r7:6, #16)
2838
// }
2839
// .LBB0_2:
2840
// {
2841
//   memh(r2+#4) = r5
2842
//   memh(r2+#6) = r6            # R6 is really R5.H
2843
// }
2844
// {
2845
//   r2 = add(r2, #8)
2846
//   memh(r2+#0) = r4
2847
//   memh(r2+#2) = r3            # R3 is really R4.H
2848
// }
2849
// {
2850
//   r5:4 = memd(r0++#8)
2851
// }
2852
// {                             # "Shuffling" code that sets up R3 and R6
2853
//   r3 = lsr(r4, #16)           # so that their halves can be stored in the
2854
//   r7:6 = combine(r5, r5)      # next iteration. This could be folded into
2855
// }                             # the stores if the code was at the beginning
2856
// {                             # of the loop iteration. Since the same code
2857
//   r3 = insert(r5, #16, #16)   # precedes the loop, it can actually be moved
2858
//   r7:6 = vlsrw(r7:6, #16)     # there.
2859
// }:endloop0
2860
//
2861
//
2862
// The outcome:
2863
//
2864
// {
2865
//   loop0(.LBB0_2, r1)
2866
//   r5:4 = memd(r0++#8)
2867
// }
2868
// .LBB0_2:
2869
// {
2870
//   memh(r2+#4) = r5
2871
//   memh(r2+#6) = r5.h
2872
// }
2873
// {
2874
//   r2 = add(r2, #8)
2875
//   memh(r2+#0) = r4
2876
//   memh(r2+#2) = r4.h
2877
// }
2878
// {
2879
//   r5:4 = memd(r0++#8)
2880
// }:endloop0
2881
2882
namespace llvm {
2883
2884
  FunctionPass *createHexagonLoopRescheduling();
2885
  void initializeHexagonLoopReschedulingPass(PassRegistry&);
2886
2887
} // end namespace llvm
2888
2889
namespace {
2890
2891
  class HexagonLoopRescheduling : public MachineFunctionPass {
2892
  public:
2893
    static char ID;
2894
2895
862
    HexagonLoopRescheduling() : MachineFunctionPass(ID) {
2896
862
      initializeHexagonLoopReschedulingPass(*PassRegistry::getPassRegistry());
2897
862
    }
2898
2899
    bool runOnMachineFunction(MachineFunction &MF) override;
2900
2901
  private:
2902
    const HexagonInstrInfo *HII = nullptr;
2903
    const HexagonRegisterInfo *HRI = nullptr;
2904
    MachineRegisterInfo *MRI = nullptr;
2905
    BitTracker *BTP = nullptr;
2906
2907
    struct LoopCand {
2908
      LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb,
2909
323
            MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {}
2910
2911
      MachineBasicBlock *LB, *PB, *EB;
2912
    };
2913
    using InstrList = std::vector<MachineInstr *>;
2914
    struct InstrGroup {
2915
      BitTracker::RegisterRef Inp, Out;
2916
      InstrList Ins;
2917
    };
2918
    struct PhiInfo {
2919
      PhiInfo(MachineInstr &P, MachineBasicBlock &B);
2920
2921
      unsigned DefR;
2922
      BitTracker::RegisterRef LR, PR; // Loop Register, Preheader Register
2923
      MachineBasicBlock *LB, *PB;     // Loop Block, Preheader Block
2924
    };
2925
2926
    static unsigned getDefReg(const MachineInstr *MI);
2927
    bool isConst(unsigned Reg) const;
2928
    bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const;
2929
    bool isStoreInput(const MachineInstr *MI, unsigned DefR) const;
2930
    bool isShuffleOf(unsigned OutR, unsigned InpR) const;
2931
    bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2,
2932
        unsigned &InpR2) const;
2933
    void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB,
2934
        MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR);
2935
    bool processLoop(LoopCand &C);
2936
  };
2937
2938
} // end anonymous namespace
2939
2940
char HexagonLoopRescheduling::ID = 0;
2941
2942
INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched",
2943
  "Hexagon Loop Rescheduling", false, false)
2944
2945
HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
2946
139
      MachineBasicBlock &B) {
2947
139
  DefR = HexagonLoopRescheduling::getDefReg(&P);
2948
139
  LB = &B;
2949
139
  PB = nullptr;
2950
417
  for (unsigned i = 1, n = P.getNumOperands(); i < n; 
i += 2278
) {
2951
278
    const MachineOperand &OpB = P.getOperand(i+1);
2952
278
    if (OpB.getMBB() == &B) {
2953
139
      LR = P.getOperand(i);
2954
139
      continue;
2955
139
    }
2956
139
    PB = OpB.getMBB();
2957
139
    PR = P.getOperand(i);
2958
139
  }
2959
139
}
2960
2961
829
unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) {
2962
829
  RegisterSet Defs;
2963
829
  HBS::getInstrDefs(*MI, Defs);
2964
829
  if (Defs.count() != 1)
2965
0
    return 0;
2966
829
  return Defs.find_first();
2967
829
}
2968
2969
667
bool HexagonLoopRescheduling::isConst(unsigned Reg) const {
2970
667
  if (!BTP->has(Reg))
2971
0
    return false;
2972
667
  const BitTracker::RegisterCell &RC = BTP->lookup(Reg);
2973
819
  for (unsigned i = 0, w = RC.width(); i < w; 
++i152
) {
2974
819
    const BitTracker::BitValue &V = RC[i];
2975
819
    if (!V.is(0) && 
!V.is(1)684
)
2976
667
      return false;
2977
819
  }
2978
667
  
return true0
;
2979
667
}
2980
2981
bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
2982
2.10k
      unsigned DefR) const {
2983
2.10k
  unsigned Opc = MI->getOpcode();
2984
2.10k
  switch (Opc) {
2985
2.10k
    case TargetOpcode::COPY:
2986
148
    case Hexagon::S2_lsr_i_r:
2987
148
    case Hexagon::S2_asr_i_r:
2988
148
    case Hexagon::S2_asl_i_r:
2989
148
    case Hexagon::S2_lsr_i_p:
2990
148
    case Hexagon::S2_asr_i_p:
2991
148
    case Hexagon::S2_asl_i_p:
2992
148
    case Hexagon::S2_insert:
2993
148
    case Hexagon::A2_or:
2994
148
    case Hexagon::A2_orp:
2995
148
    case Hexagon::A2_and:
2996
148
    case Hexagon::A2_andp:
2997
148
    case Hexagon::A2_combinew:
2998
148
    case Hexagon::A4_combineri:
2999
148
    case Hexagon::A4_combineir:
3000
148
    case Hexagon::A2_combineii:
3001
148
    case Hexagon::A4_combineii:
3002
148
    case Hexagon::A2_combine_ll:
3003
148
    case Hexagon::A2_combine_lh:
3004
148
    case Hexagon::A2_combine_hl:
3005
148
    case Hexagon::A2_combine_hh:
3006
148
      return true;
3007
1.95k
  }
3008
1.95k
  return false;
3009
1.95k
}
3010
3011
bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
3012
1.04k
      unsigned InpR) const {
3013
2.39k
  for (unsigned i = 0, n = MI->getNumOperands(); i < n; 
++i1.35k
) {
3014
2.39k
    const MachineOperand &Op = MI->getOperand(i);
3015
2.39k
    if (!Op.isReg())
3016
42
      continue;
3017
2.35k
    if (Op.getReg() == InpR)
3018
1.04k
      return i == n-1;
3019
2.35k
  }
3020
1.04k
  
return false0
;
3021
1.04k
}
3022
3023
12
bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const {
3024
12
  if (!BTP->has(OutR) || !BTP->has(InpR))
3025
3
    return false;
3026
9
  const BitTracker::RegisterCell &OutC = BTP->lookup(OutR);
3027
361
  for (unsigned i = 0, w = OutC.width(); i < w; 
++i352
) {
3028
352
    const BitTracker::BitValue &V = OutC[i];
3029
352
    if (V.Type != BitTracker::BitValue::Ref)
3030
147
      continue;
3031
205
    if (V.RefI.Reg != InpR)
3032
0
      return false;
3033
205
  }
3034
9
  return true;
3035
9
}
3036
3037
bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
3038
9
      unsigned OutR2, unsigned &InpR2) const {
3039
9
  if (!BTP->has(OutR1) || !BTP->has(InpR1) || !BTP->has(OutR2))
3040
0
    return false;
3041
9
  const BitTracker::RegisterCell &OutC1 = BTP->lookup(OutR1);
3042
9
  const BitTracker::RegisterCell &OutC2 = BTP->lookup(OutR2);
3043
9
  unsigned W = OutC1.width();
3044
9
  unsigned MatchR = 0;
3045
9
  if (W != OutC2.width())
3046
0
    return false;
3047
138
  
for (unsigned i = 0; 9
i < W;
++i129
) {
3048
134
    const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i];
3049
134
    if (V1.Type != V2.Type || 
V1.Type == BitTracker::BitValue::One131
)
3050
3
      return false;
3051
131
    if (V1.Type != BitTracker::BitValue::Ref)
3052
17
      continue;
3053
114
    if (V1.RefI.Pos != V2.RefI.Pos)
3054
2
      return false;
3055
112
    if (V1.RefI.Reg != InpR1)
3056
0
      return false;
3057
112
    if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2)
3058
0
      return false;
3059
112
    if (!MatchR)
3060
4
      MatchR = V2.RefI.Reg;
3061
108
    else if (V2.RefI.Reg != MatchR)
3062
0
      return false;
3063
112
  }
3064
9
  InpR2 = MatchR;
3065
4
  return true;
3066
9
}
3067
3068
void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
3069
      MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
3070
4
      unsigned NewPredR) {
3071
4
  DenseMap<unsigned,unsigned> RegMap;
3072
4
3073
4
  const TargetRegisterClass *PhiRC = MRI->getRegClass(NewPredR);
3074
4
  unsigned PhiR = MRI->createVirtualRegister(PhiRC);
3075
4
  BuildMI(LB, At, At->getDebugLoc(), HII->get(TargetOpcode::PHI), PhiR)
3076
4
    .addReg(NewPredR)
3077
4
    .addMBB(&PB)
3078
4
    .addReg(G.Inp.Reg)
3079
4
    .addMBB(&LB);
3080
4
  RegMap.insert(std::make_pair(G.Inp.Reg, PhiR));
3081
4
3082
11
  for (unsigned i = G.Ins.size(); i > 0; 
--i7
) {
3083
7
    const MachineInstr *SI = G.Ins[i-1];
3084
7
    unsigned DR = getDefReg(SI);
3085
7
    const TargetRegisterClass *RC = MRI->getRegClass(DR);
3086
7
    unsigned NewDR = MRI->createVirtualRegister(RC);
3087
7
    DebugLoc DL = SI->getDebugLoc();
3088
7
3089
7
    auto MIB = BuildMI(LB, At, DL, HII->get(SI->getOpcode()), NewDR);
3090
24
    for (unsigned j = 0, m = SI->getNumOperands(); j < m; 
++j17
) {
3091
17
      const MachineOperand &Op = SI->getOperand(j);
3092
17
      if (!Op.isReg()) {
3093
3
        MIB.add(Op);
3094
3
        continue;
3095
3
      }
3096
14
      if (!Op.isUse())
3097
7
        continue;
3098
7
      unsigned UseR = RegMap[Op.getReg()];
3099
7
      MIB.addReg(UseR, 0, Op.getSubReg());
3100
7
    }
3101
7
    RegMap.insert(std::make_pair(DR, NewDR));
3102
7
  }
3103
4
3104
4
  HBS::replaceReg(OldPhiR, RegMap[G.Out.Reg], *MRI);
3105
4
}
3106
3107
323
bool HexagonLoopRescheduling::processLoop(LoopCand &C) {
3108
323
  LLVM_DEBUG(dbgs() << "Processing loop in " << printMBBReference(*C.LB)
3109
323
                    << "\n");
3110
323
  std::vector<PhiInfo> Phis;
3111
990
  for (auto &I : *C.LB) {
3112
990
    if (!I.isPHI())
3113
323
      break;
3114
667
    unsigned PR = getDefReg(&I);
3115
667
    if (isConst(PR))
3116
0
      continue;
3117
667
    bool BadUse = false, GoodUse = false;
3118
1.74k
    for (auto UI = MRI->use_begin(PR), UE = MRI->use_end(); UI != UE; 
++UI1.08k
) {
3119
1.09k
      MachineInstr *UseI = UI->getParent();
3120
1.09k
      if (UseI->getParent() != C.LB) {
3121
10
        BadUse = true;
3122
10
        break;
3123
10
      }
3124
1.08k
      if (isBitShuffle(UseI, PR) || 
isStoreInput(UseI, PR)1.04k
)
3125
167
        GoodUse = true;
3126
1.08k
    }
3127
667
    if (BadUse || 
!GoodUse657
)
3128
528
      continue;
3129
139
3130
139
    Phis.push_back(PhiInfo(I, *C.LB));
3131
139
  }
3132
323
3133
323
  LLVM_DEBUG({
3134
323
    dbgs() << "Phis: {";
3135
323
    for (auto &I : Phis) {
3136
323
      dbgs() << ' ' << printReg(I.DefR, HRI) << "=phi("
3137
323
             << printReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber()
3138
323
             << ',' << printReg(I.LR.Reg, HRI, I.LR.Sub) << ":b"
3139
323
             << I.LB->getNumber() << ')';
3140
323
    }
3141
323
    dbgs() << " }\n";
3142
323
  });
3143
323
3144
323
  if (Phis.empty())
3145
228
    return false;
3146
95
3147
95
  bool Changed = false;
3148
95
  InstrList ShufIns;
3149
95
3150
95
  // Go backwards in the block: for each bit shuffling instruction, check
3151
95
  // if that instruction could potentially be moved to the front of the loop:
3152
95
  // the output of the loop cannot be used in a non-shuffling instruction
3153
95
  // in this loop.
3154
1.45k
  for (auto I = C.LB->rbegin(), E = C.LB->rend(); I != E; 
++I1.35k
) {
3155
1.45k
    if (I->isTerminator())
3156
190
      continue;
3157
1.26k
    if (I->isPHI())
3158
95
      break;
3159
1.16k
3160
1.16k
    RegisterSet Defs;
3161
1.16k
    HBS::getInstrDefs(*I, Defs);
3162
1.16k
    if (Defs.count() != 1)
3163
144
      continue;
3164
1.02k
    unsigned DefR = Defs.find_first();
3165
1.02k
    if (!TargetRegisterInfo::isVirtualRegister(DefR))
3166
0
      continue;
3167
1.02k
    if (!isBitShuffle(&*I, DefR))
3168
914
      continue;
3169
108
3170
108
    bool BadUse = false;
3171
129
    for (auto UI = MRI->use_begin(DefR), UE = MRI->use_end(); UI != UE; 
++UI21
) {
3172
107
      MachineInstr *UseI = UI->getParent();
3173
107
      if (UseI->getParent() == C.LB) {
3174
103
        if (UseI->isPHI()) {
3175
12
          // If the use is in a phi node in this loop, then it should be
3176
12
          // the value corresponding to the back edge.
3177
12
          unsigned Idx = UI.getOperandNo();
3178
12
          if (UseI->getOperand(Idx+1).getMBB() != C.LB)
3179
0
            BadUse = true;
3180
91
        } else {
3181
91
          auto F = find(ShufIns, UseI);
3182
91
          if (F == ShufIns.end())
3183
85
            BadUse = true;
3184
91
        }
3185
103
      } else {
3186
4
        // There is a use outside of the loop, but there is no epilog block
3187
4
        // suitable for a copy-out.
3188
4
        if (C.EB == nullptr)
3189
1
          BadUse = true;
3190
4
      }
3191
107
      if (BadUse)
3192
86
        break;
3193
107
    }
3194
108
3195
108
    if (BadUse)
3196
86
      continue;
3197
22
    ShufIns.push_back(&*I);
3198
22
  }
3199
95
3200
95
  // Partition the list of shuffling instructions into instruction groups,
3201
95
  // where each group has to be moved as a whole (i.e. a group is a chain of
3202
95
  // dependent instructions). A group produces a single live output register,
3203
95
  // which is meant to be the input of the loop phi node (although this is
3204
95
  // not checked here yet). It also uses a single register as its input,
3205
95
  // which is some value produced in the loop body. After moving the group
3206
95
  // to the beginning of the loop, that input register would need to be
3207
95
  // the loop-carried register (through a phi node) instead of the (currently
3208
95
  // loop-carried) output register.
3209
95
  using InstrGroupList = std::vector<InstrGroup>;
3210
95
  InstrGroupList Groups;
3211
95
3212
117
  for (unsigned i = 0, n = ShufIns.size(); i < n; 
++i22
) {
3213
22
    MachineInstr *SI = ShufIns[i];
3214
22
    if (SI == nullptr)
3215
6
      continue;
3216
16
3217
16
    InstrGroup G;
3218
16
    G.Ins.push_back(SI);
3219
16
    G.Out.Reg = getDefReg(SI);
3220
16
    RegisterSet Inputs;
3221
16
    HBS::getInstrUses(*SI, Inputs);
3222
16
3223
36
    for (unsigned j = i+1; j < n; 
++j20
) {
3224
20
      MachineInstr *MI = ShufIns[j];
3225
20
      if (MI == nullptr)
3226
0
        continue;
3227
20
      RegisterSet Defs;
3228
20
      HBS::getInstrDefs(*MI, Defs);
3229
20
      // If this instruction does not define any pending inputs, skip it.
3230
20
      if (!Defs.intersects(Inputs))
3231
14
        continue;
3232
6
      // Otherwise, add it to the current group and remove the inputs that
3233
6
      // are defined by MI.
3234
6
      G.Ins.push_back(MI);
3235
6
      Inputs.remove(Defs);
3236
6
      // Then add all registers used by MI.
3237
6
      HBS::getInstrUses(*MI, Inputs);
3238
6
      ShufIns[j] = nullptr;
3239
6
    }
3240
16
3241
16
    // Only add a group if it requires at most one register.
3242
16
    if (Inputs.count() > 1)
3243
0
      continue;
3244
28
    
auto LoopInpEq = [G] (const PhiInfo &P) -> bool 16
{
3245
28
      return G.Out.Reg == P.LR.Reg;
3246
28
    };
3247
16
    if (llvm::find_if(Phis, LoopInpEq) == Phis.end())
3248
4
      continue;
3249
12
3250
12
    G.Inp.Reg = Inputs.find_first();
3251
12
    Groups.push_back(G);
3252
12
  }
3253
95
3254
95
  LLVM_DEBUG({
3255
95
    for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3256
95
      InstrGroup &G = Groups[i];
3257
95
      dbgs() << "Group[" << i << "] inp: "
3258
95
             << printReg(G.Inp.Reg, HRI, G.Inp.Sub)
3259
95
             << "  out: " << printReg(G.Out.Reg, HRI, G.Out.Sub) << "\n";
3260
95
      for (unsigned j = 0, m = G.Ins.size(); j < m; ++j)
3261
95
        dbgs() << "  " << *G.Ins[j];
3262
95
    }
3263
95
  });
3264
95
3265
107
  for (unsigned i = 0, n = Groups.size(); i < n; 
++i12
) {
3266
12
    InstrGroup &G = Groups[i];
3267
12
    if (!isShuffleOf(G.Out.Reg, G.Inp.Reg))
3268
3
      continue;
3269
20
    
auto LoopInpEq = [G] (const PhiInfo &P) -> bool 9
{
3270
20
      return G.Out.Reg == P.LR.Reg;
3271
20
    };
3272
9
    auto F = llvm::find_if(Phis, LoopInpEq);
3273
9
    if (F == Phis.end())
3274
0
      continue;
3275
9
    unsigned PrehR = 0;
3276
9
    if (!isSameShuffle(G.Out.Reg, G.Inp.Reg, F->PR.Reg, PrehR)) {
3277
5
      const MachineInstr *DefPrehR = MRI->getVRegDef(F->PR.Reg);
3278
5
      unsigned Opc = DefPrehR->getOpcode();
3279
5
      if (Opc != Hexagon::A2_tfrsi && 
Opc != Hexagon::A2_tfrpi2
)
3280
2
        continue;
3281
3
      if (!DefPrehR->getOperand(1).isImm())
3282
0
        continue;
3283
3
      if (DefPrehR->getOperand(1).getImm() != 0)
3284
3
        continue;
3285
0
      const TargetRegisterClass *RC = MRI->getRegClass(G.Inp.Reg);
3286
0
      if (RC != MRI->getRegClass(F->PR.Reg)) {
3287
0
        PrehR = MRI->createVirtualRegister(RC);
3288
0
        unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi
3289
0
                                                          : Hexagon::A2_tfrpi;
3290
0
        auto T = C.PB->getFirstTerminator();
3291
0
        DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc();
3292
0
        BuildMI(*C.PB, T, DL, HII->get(TfrI), PrehR)
3293
0
          .addImm(0);
3294
0
      } else {
3295
0
        PrehR = F->PR.Reg;
3296
0
      }
3297
0
    }
3298
9
    // isSameShuffle could match with PrehR being of a wider class than
3299
9
    // G.Inp.Reg, for example if G shuffles the low 32 bits of its input,
3300
9
    // it would match for the input being a 32-bit register, and PrehR
3301
9
    // being a 64-bit register (where the low 32 bits match). This could
3302
9
    // be handled, but for now skip these cases.
3303
9
    
if (4
MRI->getRegClass(PrehR) != MRI->getRegClass(G.Inp.Reg)4
)
3304
0
      continue;
3305
4
    moveGroup(G, *F->LB, *F->PB, F->LB->getFirstNonPHI(), F->DefR, PrehR);
3306
4
    Changed = true;
3307
4
  }
3308
95
3309
95
  return Changed;
3310
95
}
3311
3312
3.36k
bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) {
3313
3.36k
  if (skipFunction(MF.getFunction()))
3314
10
    return false;
3315
3.35k
3316
3.35k
  auto &HST = MF.getSubtarget<HexagonSubtarget>();
3317
3.35k
  HII = HST.getInstrInfo();
3318
3.35k
  HRI = HST.getRegisterInfo();
3319
3.35k
  MRI = &MF.getRegInfo();
3320
3.35k
  const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
3321
3.35k
  BitTracker BT(HE, MF);
3322
3.35k
  LLVM_DEBUG(BT.trace(true));
3323
3.35k
  BT.run();
3324
3.35k
  BTP = &BT;
3325
3.35k
3326
3.35k
  std::vector<LoopCand> Cand;
3327
3.35k
3328
4.98k
  for (auto &B : MF) {
3329
4.98k
    if (B.pred_size() != 2 || 
B.succ_size() != 2725
)
3330
4.51k
      continue;
3331
464
    MachineBasicBlock *PB = nullptr;
3332
464
    bool IsLoop = false;
3333
1.39k
    for (auto PI = B.pred_begin(), PE = B.pred_end(); PI != PE; 
++PI928
) {
3334
928
      if (*PI != &B)
3335
605
        PB = *PI;
3336
323
      else
3337
323
        IsLoop = true;
3338
928
    }
3339
464
    if (!IsLoop)
3340
141
      continue;
3341
323
3342
323
    MachineBasicBlock *EB = nullptr;
3343
528
    for (auto SI = B.succ_begin(), SE = B.succ_end(); SI != SE; 
++SI205
) {
3344
528
      if (*SI == &B)
3345
205
        continue;
3346
323
      // Set EP to the epilog block, if it has only 1 predecessor (i.e. the
3347
323
      // edge from B to EP is non-critical.
3348
323
      if ((*SI)->pred_size() == 1)
3349
194
        EB = *SI;
3350
323
      break;
3351
323
    }
3352
323
3353
323
    Cand.push_back(LoopCand(&B, PB, EB));
3354
323
  }
3355
3.35k
3356
3.35k
  bool Changed = false;
3357
3.35k
  for (auto &C : Cand)
3358
323
    Changed |= processLoop(C);
3359
3.35k
3360
3.35k
  return Changed;
3361
3.35k
}
3362
3363
//===----------------------------------------------------------------------===//
3364
//                         Public Constructor Functions
3365
//===----------------------------------------------------------------------===//
3366
3367
862
FunctionPass *llvm::createHexagonLoopRescheduling() {
3368
862
  return new HexagonLoopRescheduling();
3369
862
}
3370
3371
856
FunctionPass *llvm::createHexagonBitSimplify() {
3372
856
  return new HexagonBitSimplify();
3373
856
}