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