LLVM  8.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  bool simplifyRCmp0(MachineInstr *MI, BitTracker::RegisterRef RD);
1781 
1782  // Cache of created instructions to avoid creating duplicates.
1783  // XXX Currently only used by genBitSplit.
1784  std::vector<MachineInstr*> NewMIs;
1785 
1786  const MachineDominatorTree &MDT;
1787  const HexagonInstrInfo &HII;
1788  const HexagonRegisterInfo &HRI;
1790  MachineFunction &MF;
1791  BitTracker &BT;
1792  };
1793 
1794 } // end anonymous namespace
1795 
1796 // Check if the bits [B..B+16) in register cell RC form a valid halfword,
1797 // i.e. [0..16), [16..32), etc. of some register. If so, return true and
1798 // set the information about the found register in RH.
1799 bool BitSimplification::matchHalf(unsigned SelfR,
1800  const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) {
1801  // XXX This could be searching in the set of available registers, in case
1802  // the match is not exact.
1803 
1804  // Match 16-bit chunks, where the RC[B..B+15] references exactly one
1805  // register and all the bits B..B+15 match between RC and the register.
1806  // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... },
1807  // and RC = { [0]:0 [1-15]:v1[1-15]... }.
1808  bool Low = false;
1809  unsigned I = B;
1810  while (I < B+16 && RC[I].num())
1811  I++;
1812  if (I == B+16)
1813  return false;
1814 
1815  unsigned Reg = RC[I].RefI.Reg;
1816  unsigned P = RC[I].RefI.Pos; // The RefI.Pos will be advanced by I-B.
1817  if (P < I-B)
1818  return false;
1819  unsigned Pos = P - (I-B);
1820 
1821  if (Reg == 0 || Reg == SelfR) // Don't match "self".
1822  return false;
1824  return false;
1825  if (!BT.has(Reg))
1826  return false;
1827 
1828  const BitTracker::RegisterCell &SC = BT.lookup(Reg);
1829  if (Pos+16 > SC.width())
1830  return false;
1831 
1832  for (unsigned i = 0; i < 16; ++i) {
1833  const BitTracker::BitValue &RV = RC[i+B];
1834  if (RV.Type == BitTracker::BitValue::Ref) {
1835  if (RV.RefI.Reg != Reg)
1836  return false;
1837  if (RV.RefI.Pos != i+Pos)
1838  return false;
1839  continue;
1840  }
1841  if (RC[i+B] != SC[i+Pos])
1842  return false;
1843  }
1844 
1845  unsigned Sub = 0;
1846  switch (Pos) {
1847  case 0:
1848  Sub = Hexagon::isub_lo;
1849  Low = true;
1850  break;
1851  case 16:
1852  Sub = Hexagon::isub_lo;
1853  Low = false;
1854  break;
1855  case 32:
1856  Sub = Hexagon::isub_hi;
1857  Low = true;
1858  break;
1859  case 48:
1860  Sub = Hexagon::isub_hi;
1861  Low = false;
1862  break;
1863  default:
1864  return false;
1865  }
1866 
1867  RH.Reg = Reg;
1868  RH.Sub = Sub;
1869  RH.Low = Low;
1870  // If the subregister is not valid with the register, set it to 0.
1871  if (!HBS::getFinalVRegClass(RH, MRI))
1872  RH.Sub = 0;
1873 
1874  return true;
1875 }
1876 
1877 bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc,
1878  unsigned OpNum) {
1879  auto *OpRC = HII.getRegClass(HII.get(Opc), OpNum, &HRI, MF);
1880  auto *RRC = HBS::getFinalVRegClass(R, MRI);
1881  return OpRC->hasSubClassEq(RRC);
1882 }
1883 
1884 // Check if RC matches the pattern of a S2_packhl. If so, return true and
1885 // set the inputs Rs and Rt.
1886 bool BitSimplification::matchPackhl(unsigned SelfR,
1889  RegHalf L1, H1, L2, H2;
1890 
1891  if (!matchHalf(SelfR, RC, 0, L2) || !matchHalf(SelfR, RC, 16, L1))
1892  return false;
1893  if (!matchHalf(SelfR, RC, 32, H2) || !matchHalf(SelfR, RC, 48, H1))
1894  return false;
1895 
1896  // Rs = H1.L1, Rt = H2.L2
1897  if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || H1.Low || !L1.Low)
1898  return false;
1899  if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low)
1900  return false;
1901 
1902  Rs = H1;
1903  Rt = H2;
1904  return true;
1905 }
1906 
1907 unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) {
1908  return HLow ? LLow ? Hexagon::A2_combine_ll
1909  : Hexagon::A2_combine_lh
1910  : LLow ? Hexagon::A2_combine_hl
1911  : Hexagon::A2_combine_hh;
1912 }
1913 
1914 // If MI stores the upper halfword of a register (potentially obtained via
1915 // shifts or extracts), replace it with a storerf instruction. This could
1916 // cause the "extraction" code to become dead.
1917 bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) {
1918  unsigned Opc = MI->getOpcode();
1919  if (Opc != Hexagon::S2_storerh_io)
1920  return false;
1921 
1922  MachineOperand &ValOp = MI->getOperand(2);
1923  BitTracker::RegisterRef RS = ValOp;
1924  if (!BT.has(RS.Reg))
1925  return false;
1926  const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1927  RegHalf H;
1928  if (!matchHalf(0, RC, 0, H))
1929  return false;
1930  if (H.Low)
1931  return false;
1932  MI->setDesc(HII.get(Hexagon::S2_storerf_io));
1933  ValOp.setReg(H.Reg);
1934  ValOp.setSubReg(H.Sub);
1935  return true;
1936 }
1937 
1938 // If MI stores a value known at compile-time, and the value is within a range
1939 // that avoids using constant-extenders, replace it with a store-immediate.
1940 bool BitSimplification::genStoreImmediate(MachineInstr *MI) {
1941  unsigned Opc = MI->getOpcode();
1942  unsigned Align = 0;
1943  switch (Opc) {
1944  case Hexagon::S2_storeri_io:
1945  Align++;
1947  case Hexagon::S2_storerh_io:
1948  Align++;
1950  case Hexagon::S2_storerb_io:
1951  break;
1952  default:
1953  return false;
1954  }
1955 
1956  // Avoid stores to frame-indices (due to an unknown offset).
1957  if (!MI->getOperand(0).isReg())
1958  return false;
1959  MachineOperand &OffOp = MI->getOperand(1);
1960  if (!OffOp.isImm())
1961  return false;
1962 
1963  int64_t Off = OffOp.getImm();
1964  // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x).
1965  if (!isUIntN(6+Align, Off) || (Off & ((1<<Align)-1)))
1966  return false;
1967  // Source register:
1968  BitTracker::RegisterRef RS = MI->getOperand(2);
1969  if (!BT.has(RS.Reg))
1970  return false;
1971  const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1972  uint64_t U;
1973  if (!HBS::getConst(RC, 0, RC.width(), U))
1974  return false;
1975 
1976  // Only consider 8-bit values to avoid constant-extenders.
1977  int V;
1978  switch (Opc) {
1979  case Hexagon::S2_storerb_io:
1980  V = int8_t(U);
1981  break;
1982  case Hexagon::S2_storerh_io:
1983  V = int16_t(U);
1984  break;
1985  case Hexagon::S2_storeri_io:
1986  V = int32_t(U);
1987  break;
1988  default:
1989  // Opc is already checked above to be one of the three store instructions.
1990  // This silences a -Wuninitialized false positive on GCC 5.4.
1991  llvm_unreachable("Unexpected store opcode");
1992  }
1993  if (!isInt<8>(V))
1994  return false;
1995 
1996  MI->RemoveOperand(2);
1997  switch (Opc) {
1998  case Hexagon::S2_storerb_io:
1999  MI->setDesc(HII.get(Hexagon::S4_storeirb_io));
2000  break;
2001  case Hexagon::S2_storerh_io:
2002  MI->setDesc(HII.get(Hexagon::S4_storeirh_io));
2003  break;
2004  case Hexagon::S2_storeri_io:
2005  MI->setDesc(HII.get(Hexagon::S4_storeiri_io));
2006  break;
2007  }
2009  return true;
2010 }
2011 
2012 // If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
2013 // last instruction in a sequence that results in something equivalent to
2014 // the pack-halfwords. The intent is to cause the entire sequence to become
2015 // dead.
2016 bool BitSimplification::genPackhl(MachineInstr *MI,
2018  unsigned Opc = MI->getOpcode();
2019  if (Opc == Hexagon::S2_packhl)
2020  return false;
2021  BitTracker::RegisterRef Rs, Rt;
2022  if (!matchPackhl(RD.Reg, RC, Rs, Rt))
2023  return false;
2024  if (!validateReg(Rs, Hexagon::S2_packhl, 1) ||
2025  !validateReg(Rt, Hexagon::S2_packhl, 2))
2026  return false;
2027 
2028  MachineBasicBlock &B = *MI->getParent();
2029  unsigned NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2030  DebugLoc DL = MI->getDebugLoc();
2031  auto At = MI->isPHI() ? B.getFirstNonPHI()
2033  BuildMI(B, At, DL, HII.get(Hexagon::S2_packhl), NewR)
2034  .addReg(Rs.Reg, 0, Rs.Sub)
2035  .addReg(Rt.Reg, 0, Rt.Sub);
2036  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2037  BT.put(BitTracker::RegisterRef(NewR), RC);
2038  return true;
2039 }
2040 
2041 // If MI produces halfword of the input in the low half of the output,
2042 // replace it with zero-extend or extractu.
2043 bool BitSimplification::genExtractHalf(MachineInstr *MI,
2045  RegHalf L;
2046  // Check for halfword in low 16 bits, zeros elsewhere.
2047  if (!matchHalf(RD.Reg, RC, 0, L) || !HBS::isZero(RC, 16, 16))
2048  return false;
2049 
2050  unsigned Opc = MI->getOpcode();
2051  MachineBasicBlock &B = *MI->getParent();
2052  DebugLoc DL = MI->getDebugLoc();
2053 
2054  // Prefer zxth, since zxth can go in any slot, while extractu only in
2055  // slots 2 and 3.
2056  unsigned NewR = 0;
2057  auto At = MI->isPHI() ? B.getFirstNonPHI()
2059  if (L.Low && Opc != Hexagon::A2_zxth) {
2060  if (validateReg(L, Hexagon::A2_zxth, 1)) {
2061  NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2062  BuildMI(B, At, DL, HII.get(Hexagon::A2_zxth), NewR)
2063  .addReg(L.Reg, 0, L.Sub);
2064  }
2065  } else if (!L.Low && Opc != Hexagon::S2_lsr_i_r) {
2066  if (validateReg(L, Hexagon::S2_lsr_i_r, 1)) {
2067  NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2068  BuildMI(B, MI, DL, HII.get(Hexagon::S2_lsr_i_r), NewR)
2069  .addReg(L.Reg, 0, L.Sub)
2070  .addImm(16);
2071  }
2072  }
2073  if (NewR == 0)
2074  return false;
2075  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2076  BT.put(BitTracker::RegisterRef(NewR), RC);
2077  return true;
2078 }
2079 
2080 // If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
2081 // combine.
2082 bool BitSimplification::genCombineHalf(MachineInstr *MI,
2084  RegHalf L, H;
2085  // Check for combine h/l
2086  if (!matchHalf(RD.Reg, RC, 0, L) || !matchHalf(RD.Reg, RC, 16, H))
2087  return false;
2088  // Do nothing if this is just a reg copy.
2089  if (L.Reg == H.Reg && L.Sub == H.Sub && !H.Low && L.Low)
2090  return false;
2091 
2092  unsigned Opc = MI->getOpcode();
2093  unsigned COpc = getCombineOpcode(H.Low, L.Low);
2094  if (COpc == Opc)
2095  return false;
2096  if (!validateReg(H, COpc, 1) || !validateReg(L, COpc, 2))
2097  return false;
2098 
2099  MachineBasicBlock &B = *MI->getParent();
2100  DebugLoc DL = MI->getDebugLoc();
2101  unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2102  auto At = MI->isPHI() ? B.getFirstNonPHI()
2104  BuildMI(B, At, DL, HII.get(COpc), NewR)
2105  .addReg(H.Reg, 0, H.Sub)
2106  .addReg(L.Reg, 0, L.Sub);
2107  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2108  BT.put(BitTracker::RegisterRef(NewR), RC);
2109  return true;
2110 }
2111 
2112 // If MI resets high bits of a register and keeps the lower ones, replace it
2113 // with zero-extend byte/half, and-immediate, or extractu, as appropriate.
2114 bool BitSimplification::genExtractLow(MachineInstr *MI,
2116  unsigned Opc = MI->getOpcode();
2117  switch (Opc) {
2118  case Hexagon::A2_zxtb:
2119  case Hexagon::A2_zxth:
2120  case Hexagon::S2_extractu:
2121  return false;
2122  }
2123  if (Opc == Hexagon::A2_andir && MI->getOperand(2).isImm()) {
2124  int32_t Imm = MI->getOperand(2).getImm();
2125  if (isInt<10>(Imm))
2126  return false;
2127  }
2128 
2129  if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
2130  return false;
2131  unsigned W = RC.width();
2132  while (W > 0 && RC[W-1].is(0))
2133  W--;
2134  if (W == 0 || W == RC.width())
2135  return false;
2136  unsigned NewOpc = (W == 8) ? Hexagon::A2_zxtb
2137  : (W == 16) ? Hexagon::A2_zxth
2138  : (W < 10) ? Hexagon::A2_andir
2139  : Hexagon::S2_extractu;
2140  MachineBasicBlock &B = *MI->getParent();
2141  DebugLoc DL = MI->getDebugLoc();
2142 
2143  for (auto &Op : MI->uses()) {
2144  if (!Op.isReg())
2145  continue;
2147  if (!BT.has(RS.Reg))
2148  continue;
2149  const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2150  unsigned BN, BW;
2151  if (!HBS::getSubregMask(RS, BN, BW, MRI))
2152  continue;
2153  if (BW < W || !HBS::isEqual(RC, 0, SC, BN, W))
2154  continue;
2155  if (!validateReg(RS, NewOpc, 1))
2156  continue;
2157 
2158  unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2159  auto At = MI->isPHI() ? B.getFirstNonPHI()
2161  auto MIB = BuildMI(B, At, DL, HII.get(NewOpc), NewR)
2162  .addReg(RS.Reg, 0, RS.Sub);
2163  if (NewOpc == Hexagon::A2_andir)
2164  MIB.addImm((1 << W) - 1);
2165  else if (NewOpc == Hexagon::S2_extractu)
2166  MIB.addImm(W).addImm(0);
2167  HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2168  BT.put(BitTracker::RegisterRef(NewR), RC);
2169  return true;
2170  }
2171  return false;
2172 }
2173 
2174 bool BitSimplification::genBitSplit(MachineInstr *MI,
2176  const RegisterSet &AVs) {
2177  if (!GenBitSplit)
2178  return false;
2179  if (MaxBitSplit.getNumOccurrences()) {
2180  if (CountBitSplit >= MaxBitSplit)
2181  return false;
2182  }
2183 
2184  unsigned Opc = MI->getOpcode();
2185  switch (Opc) {
2186  case Hexagon::A4_bitsplit:
2187  case Hexagon::A4_bitspliti:
2188  return false;
2189  }
2190 
2191  unsigned W = RC.width();
2192  if (W != 32)
2193  return false;
2194 
2195  auto ctlz = [] (const BitTracker::RegisterCell &C) -> unsigned {
2196  unsigned Z = C.width();
2197  while (Z > 0 && C[Z-1].is(0))
2198  --Z;
2199  return C.width() - Z;
2200  };
2201 
2202  // Count the number of leading zeros in the target RC.
2203  unsigned Z = ctlz(RC);
2204  if (Z == 0 || Z == W)
2205  return false;
2206 
2207  // A simplistic analysis: assume the source register (the one being split)
2208  // is fully unknown, and that all its bits are self-references.
2209  const BitTracker::BitValue &B0 = RC[0];
2210  if (B0.Type != BitTracker::BitValue::Ref)
2211  return false;
2212 
2213  unsigned SrcR = B0.RefI.Reg;
2214  unsigned SrcSR = 0;
2215  unsigned Pos = B0.RefI.Pos;
2216 
2217  // All the non-zero bits should be consecutive bits from the same register.
2218  for (unsigned i = 1; i < W-Z; ++i) {
2219  const BitTracker::BitValue &V = RC[i];
2221  return false;
2222  if (V.RefI.Reg != SrcR || V.RefI.Pos != Pos+i)
2223  return false;
2224  }
2225 
2226  // Now, find the other bitfield among AVs.
2227  for (unsigned S = AVs.find_first(); S; S = AVs.find_next(S)) {
2228  // The number of leading zeros here should be the number of trailing
2229  // non-zeros in RC.
2230  unsigned SRC = MRI.getRegClass(S)->getID();
2231  if (SRC != Hexagon::IntRegsRegClassID &&
2232  SRC != Hexagon::DoubleRegsRegClassID)
2233  continue;
2234  if (!BT.has(S))
2235  continue;
2236  const BitTracker::RegisterCell &SC = BT.lookup(S);
2237  if (SC.width() != W || ctlz(SC) != W-Z)
2238  continue;
2239  // The Z lower bits should now match SrcR.
2240  const BitTracker::BitValue &S0 = SC[0];
2241  if (S0.Type != BitTracker::BitValue::Ref || S0.RefI.Reg != SrcR)
2242  continue;
2243  unsigned P = S0.RefI.Pos;
2244 
2245  if (Pos <= P && (Pos + W-Z) != P)
2246  continue;
2247  if (P < Pos && (P + Z) != Pos)
2248  continue;
2249  // The starting bitfield position must be at a subregister boundary.
2250  if (std::min(P, Pos) != 0 && std::min(P, Pos) != 32)
2251  continue;
2252 
2253  unsigned I;
2254  for (I = 1; I < Z; ++I) {
2255  const BitTracker::BitValue &V = SC[I];
2257  break;
2258  if (V.RefI.Reg != SrcR || V.RefI.Pos != P+I)
2259  break;
2260  }
2261  if (I != Z)
2262  continue;
2263 
2264  // Generate bitsplit where S is defined.
2265  if (MaxBitSplit.getNumOccurrences())
2266  CountBitSplit++;
2267  MachineInstr *DefS = MRI.getVRegDef(S);
2268  assert(DefS != nullptr);
2269  DebugLoc DL = DefS->getDebugLoc();
2270  MachineBasicBlock &B = *DefS->getParent();
2271  auto At = DefS->isPHI() ? B.getFirstNonPHI()
2273  if (MRI.getRegClass(SrcR)->getID() == Hexagon::DoubleRegsRegClassID)
2274  SrcSR = (std::min(Pos, P) == 32) ? Hexagon::isub_hi : Hexagon::isub_lo;
2275  if (!validateReg({SrcR,SrcSR}, Hexagon::A4_bitspliti, 1))
2276  continue;
2277  unsigned ImmOp = Pos <= P ? W-Z : Z;
2278 
2279  // Find an existing bitsplit instruction if one already exists.
2280  unsigned NewR = 0;
2281  for (MachineInstr *In : NewMIs) {
2282  if (In->getOpcode() != Hexagon::A4_bitspliti)
2283  continue;
2284  MachineOperand &Op1 = In->getOperand(1);
2285  if (Op1.getReg() != SrcR || Op1.getSubReg() != SrcSR)
2286  continue;
2287  if (In->getOperand(2).getImm() != ImmOp)
2288  continue;
2289  // Check if the target register is available here.
2290  MachineOperand &Op0 = In->getOperand(0);
2291  MachineInstr *DefI = MRI.getVRegDef(Op0.getReg());
2292  assert(DefI != nullptr);
2293  if (!MDT.dominates(DefI, &*At))
2294  continue;
2295 
2296  // Found one that can be reused.
2297  assert(Op0.getSubReg() == 0);
2298  NewR = Op0.getReg();
2299  break;
2300  }
2301  if (!NewR) {
2302  NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2303  auto NewBS = BuildMI(B, At, DL, HII.get(Hexagon::A4_bitspliti), NewR)
2304  .addReg(SrcR, 0, SrcSR)
2305  .addImm(ImmOp);
2306  NewMIs.push_back(NewBS);
2307  }
2308  if (Pos <= P) {
2309  HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_lo, MRI);
2310  HBS::replaceRegWithSub(S, NewR, Hexagon::isub_hi, MRI);
2311  } else {
2312  HBS::replaceRegWithSub(S, NewR, Hexagon::isub_lo, MRI);
2313  HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_hi, MRI);
2314  }
2315  return true;
2316  }
2317 
2318  return false;
2319 }
2320 
2321 // Check for tstbit simplification opportunity, where the bit being checked
2322 // can be tracked back to another register. For example:
2323 // %2 = S2_lsr_i_r %1, 5
2324 // %3 = S2_tstbit_i %2, 0
2325 // =>
2326 // %3 = S2_tstbit_i %1, 5
2327 bool BitSimplification::simplifyTstbit(MachineInstr *MI,
2329  unsigned Opc = MI->getOpcode();
2330  if (Opc != Hexagon::S2_tstbit_i)
2331  return false;
2332 
2333  unsigned BN = MI->getOperand(2).getImm();
2334  BitTracker::RegisterRef RS = MI->getOperand(1);
2335  unsigned F, W;
2336  DebugLoc DL = MI->getDebugLoc();
2337  if (!BT.has(RS.Reg) || !HBS::getSubregMask(RS, F, W, MRI))
2338  return false;
2339  MachineBasicBlock &B = *MI->getParent();
2340  auto At = MI->isPHI() ? B.getFirstNonPHI()
2342 
2343  const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2344  const BitTracker::BitValue &V = SC[F+BN];
2345  if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) {
2346  const TargetRegisterClass *TC = MRI.getRegClass(V.RefI.Reg);
2347  // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is
2348  // a double register, need to use a subregister and adjust bit
2349  // number.
2351  BitTracker::RegisterRef RR(V.RefI.Reg, 0);
2352  if (TC == &Hexagon::DoubleRegsRegClass) {
2353  P = V.RefI.Pos;
2354  RR.Sub = Hexagon::isub_lo;
2355  if (P >= 32) {
2356  P -= 32;
2357  RR.Sub = Hexagon::isub_hi;
2358  }
2359  } else if (TC == &Hexagon::IntRegsRegClass) {
2360  P = V.RefI.Pos;
2361  }
2363  unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2364  BuildMI(B, At, DL, HII.get(Hexagon::S2_tstbit_i), NewR)
2365  .addReg(RR.Reg, 0, RR.Sub)
2366  .addImm(P);
2367  HBS::replaceReg(RD.Reg, NewR, MRI);
2368  BT.put(NewR, RC);
2369  return true;
2370  }
2371  } else if (V.is(0) || V.is(1)) {
2372  unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2373  unsigned NewOpc = V.is(0) ? Hexagon::PS_false : Hexagon::PS_true;
2374  BuildMI(B, At, DL, HII.get(NewOpc), NewR);
2375  HBS::replaceReg(RD.Reg, NewR, MRI);
2376  return true;
2377  }
2378 
2379  return false;
2380 }
2381 
2382 // Detect whether RD is a bitfield extract (sign- or zero-extended) of
2383 // some register from the AVs set. Create a new corresponding instruction
2384 // at the location of MI. The intent is to recognize situations where
2385 // a sequence of instructions performs an operation that is equivalent to
2386 // an extract operation, such as a shift left followed by a shift right.
2387 bool BitSimplification::simplifyExtractLow(MachineInstr *MI,
2389  const RegisterSet &AVs) {
2390  if (!GenExtract)
2391  return false;
2392  if (MaxExtract.getNumOccurrences()) {
2393  if (CountExtract >= MaxExtract)
2394  return false;
2395  CountExtract++;
2396  }
2397 
2398  unsigned W = RC.width();
2399  unsigned RW = W;
2400  unsigned Len;
2401  bool Signed;
2402 
2403  // The code is mostly class-independent, except for the part that generates
2404  // the extract instruction, and establishes the source register (in case it
2405  // needs to use a subregister).
2406  const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2407  if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2408  return false;
2409  assert(RD.Sub == 0);
2410 
2411  // Observation:
2412  // If the cell has a form of 00..0xx..x with k zeros and n remaining
2413  // bits, this could be an extractu of the n bits, but it could also be
2414  // an extractu of a longer field which happens to have 0s in the top
2415  // bit positions.
2416  // The same logic applies to sign-extended fields.
2417  //
2418  // Do not check for the extended extracts, since it would expand the
2419  // search space quite a bit. The search may be expensive as it is.
2420 
2421  const BitTracker::BitValue &TopV = RC[W-1];
2422 
2423  // Eliminate candidates that have self-referential bits, since they
2424  // cannot be extracts from other registers. Also, skip registers that
2425  // have compile-time constant values.
2426  bool IsConst = true;
2427  for (unsigned I = 0; I != W; ++I) {
2428  const BitTracker::BitValue &V = RC[I];
2429  if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == RD.Reg)
2430  return false;
2431  IsConst = IsConst && (V.is(0) || V.is(1));
2432  }
2433  if (IsConst)
2434  return false;
2435 
2436  if (TopV.is(0) || TopV.is(1)) {
2437  bool S = TopV.is(1);
2438  for (--W; W > 0 && RC[W-1].is(S); --W)
2439  ;
2440  Len = W;
2441  Signed = S;
2442  // The sign bit must be a part of the field being extended.
2443  if (Signed)
2444  ++Len;
2445  } else {
2446  // This could still be a sign-extended extract.
2448  if (TopV.RefI.Reg == RD.Reg || TopV.RefI.Pos == W-1)
2449  return false;
2450  for (--W; W > 0 && RC[W-1] == TopV; --W)
2451  ;
2452  // The top bits of RC are copies of TopV. One occurrence of TopV will
2453  // be a part of the field.
2454  Len = W + 1;
2455  Signed = true;
2456  }
2457 
2458  // This would be just a copy. It should be handled elsewhere.
2459  if (Len == RW)
2460  return false;
2461 
2462  LLVM_DEBUG({
2463  dbgs() << __func__ << " on reg: " << printReg(RD.Reg, &HRI, RD.Sub)
2464  << ", MI: " << *MI;
2465  dbgs() << "Cell: " << RC << '\n';
2466  dbgs() << "Expected bitfield size: " << Len << " bits, "
2467  << (Signed ? "sign" : "zero") << "-extended\n";
2468  });
2469 
2470  bool Changed = false;
2471 
2472  for (unsigned R = AVs.find_first(); R != 0; R = AVs.find_next(R)) {
2473  if (!BT.has(R))
2474  continue;
2475  const BitTracker::RegisterCell &SC = BT.lookup(R);
2476  unsigned SW = SC.width();
2477 
2478  // The source can be longer than the destination, as long as its size is
2479  // a multiple of the size of the destination. Also, we would need to be
2480  // able to refer to the subregister in the source that would be of the
2481  // same size as the destination, but only check the sizes here.
2482  if (SW < RW || (SW % RW) != 0)
2483  continue;
2484 
2485  // The field can start at any offset in SC as long as it contains Len
2486  // bits and does not cross subregister boundary (if the source register
2487  // is longer than the destination).
2488  unsigned Off = 0;
2489  while (Off <= SW-Len) {
2490  unsigned OE = (Off+Len)/RW;
2491  if (OE != Off/RW) {
2492  // The assumption here is that if the source (R) is longer than the
2493  // destination, then the destination is a sequence of words of
2494  // size RW, and each such word in R can be accessed via a subregister.
2495  //
2496  // If the beginning and the end of the field cross the subregister
2497  // boundary, advance to the next subregister.
2498  Off = OE*RW;
2499  continue;
2500  }
2501  if (HBS::isEqual(RC, 0, SC, Off, Len))
2502  break;
2503  ++Off;
2504  }
2505 
2506  if (Off > SW-Len)
2507  continue;
2508 
2509  // Found match.
2510  unsigned ExtOpc = 0;
2511  if (Off == 0) {
2512  if (Len == 8)
2513  ExtOpc = Signed ? Hexagon::A2_sxtb : Hexagon::A2_zxtb;
2514  else if (Len == 16)
2515  ExtOpc = Signed ? Hexagon::A2_sxth : Hexagon::A2_zxth;
2516  else if (Len < 10 && !Signed)
2517  ExtOpc = Hexagon::A2_andir;
2518  }
2519  if (ExtOpc == 0) {
2520  ExtOpc =
2521  Signed ? (RW == 32 ? Hexagon::S4_extract : Hexagon::S4_extractp)
2522  : (RW == 32 ? Hexagon::S2_extractu : Hexagon::S2_extractup);
2523  }
2524  unsigned SR = 0;
2525  // This only recognizes isub_lo and isub_hi.
2526  if (RW != SW && RW*2 != SW)
2527  continue;
2528  if (RW != SW)
2529  SR = (Off/RW == 0) ? Hexagon::isub_lo : Hexagon::isub_hi;
2530  Off = Off % RW;
2531 
2532  if (!validateReg({R,SR}, ExtOpc, 1))
2533  continue;
2534 
2535  // Don't generate the same instruction as the one being optimized.
2536  if (MI->getOpcode() == ExtOpc) {
2537  // All possible ExtOpc's have the source in operand(1).
2538  const MachineOperand &SrcOp = MI->getOperand(1);
2539  if (SrcOp.getReg() == R)
2540  continue;
2541  }
2542 
2543  DebugLoc DL = MI->getDebugLoc();
2544  MachineBasicBlock &B = *MI->getParent();
2545  unsigned NewR = MRI.createVirtualRegister(FRC);
2546  auto At = MI->isPHI() ? B.getFirstNonPHI()
2548  auto MIB = BuildMI(B, At, DL, HII.get(ExtOpc), NewR)
2549  .addReg(R, 0, SR);
2550  switch (ExtOpc) {
2551  case Hexagon::A2_sxtb:
2552  case Hexagon::A2_zxtb:
2553  case Hexagon::A2_sxth:
2554  case Hexagon::A2_zxth:
2555  break;
2556  case Hexagon::A2_andir:
2557  MIB.addImm((1u << Len) - 1);
2558  break;
2559  case Hexagon::S4_extract:
2560  case Hexagon::S2_extractu:
2561  case Hexagon::S4_extractp:
2562  case Hexagon::S2_extractup:
2563  MIB.addImm(Len)
2564  .addImm(Off);
2565  break;
2566  default:
2567  llvm_unreachable("Unexpected opcode");
2568  }
2569 
2570  HBS::replaceReg(RD.Reg, NewR, MRI);
2571  BT.put(BitTracker::RegisterRef(NewR), RC);
2572  Changed = true;
2573  break;
2574  }
2575 
2576  return Changed;
2577 }
2578 
2579 bool BitSimplification::simplifyRCmp0(MachineInstr *MI,
2581  unsigned Opc = MI->getOpcode();
2582  if (Opc != Hexagon::A4_rcmpeqi && Opc != Hexagon::A4_rcmpneqi)
2583  return false;
2584  MachineOperand &CmpOp = MI->getOperand(2);
2585  if (!CmpOp.isImm() || CmpOp.getImm() != 0)
2586  return false;
2587 
2588  const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2589  if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2590  return false;
2591  assert(RD.Sub == 0);
2592 
2593  MachineBasicBlock &B = *MI->getParent();
2594  const DebugLoc &DL = MI->getDebugLoc();
2595  auto At = MI->isPHI() ? B.getFirstNonPHI()
2597  bool KnownZ = true;
2598  bool KnownNZ = false;
2599 
2600  BitTracker::RegisterRef SR = MI->getOperand(1);
2601  if (!BT.has(SR.Reg))
2602  return false;
2603  const BitTracker::RegisterCell &SC = BT.lookup(SR.Reg);
2604  unsigned F, W;
2605  if (!HBS::getSubregMask(SR, F, W, MRI))
2606  return false;
2607 
2608  for (uint16_t I = F; I != F+W; ++I) {
2609  const BitTracker::BitValue &V = SC[I];
2610  if (!V.is(0))
2611  KnownZ = false;
2612  if (V.is(1))
2613  KnownNZ = true;
2614  }
2615 
2616  auto ReplaceWithConst = [&] (int C) {
2617  unsigned NewR = MRI.createVirtualRegister(FRC);
2618  BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), NewR)
2619  .addImm(C);
2620  HBS::replaceReg(RD.Reg, NewR, MRI);
2621  BitTracker::RegisterCell NewRC(W);
2622  for (uint16_t I = 0; I != W; ++I) {
2623  NewRC[I] = BitTracker::BitValue(C & 1);
2624  C = unsigned(C) >> 1;
2625  }
2626  BT.put(BitTracker::RegisterRef(NewR), NewRC);
2627  return true;
2628  };
2629 
2630  auto IsNonZero = [] (const MachineOperand &Op) {
2631  if (Op.isGlobal() || Op.isBlockAddress())
2632  return true;
2633  if (Op.isImm())
2634  return Op.getImm() != 0;
2635  if (Op.isCImm())
2636  return !Op.getCImm()->isZero();
2637  if (Op.isFPImm())
2638  return !Op.getFPImm()->isZero();
2639  return false;
2640  };
2641 
2642  auto IsZero = [] (const MachineOperand &Op) {
2643  if (Op.isGlobal() || Op.isBlockAddress())
2644  return false;
2645  if (Op.isImm())
2646  return Op.getImm() == 0;
2647  if (Op.isCImm())
2648  return Op.getCImm()->isZero();
2649  if (Op.isFPImm())
2650  return Op.getFPImm()->isZero();
2651  return false;
2652  };
2653 
2654  // If the source register is known to be 0 or non-0, the comparison can
2655  // be folded to a load of a constant.
2656  if (KnownZ || KnownNZ) {
2657  assert(KnownZ != KnownNZ && "Register cannot be both 0 and non-0");
2658  return ReplaceWithConst(KnownZ == (Opc == Hexagon::A4_rcmpeqi));
2659  }
2660 
2661  // Special case: if the compare comes from a C2_muxii, then we know the
2662  // two possible constants that can be the source value.
2663  MachineInstr *InpDef = MRI.getVRegDef(SR.Reg);
2664  if (!InpDef)
2665  return false;
2666  if (SR.Sub == 0 && InpDef->getOpcode() == Hexagon::C2_muxii) {
2667  MachineOperand &Src1 = InpDef->getOperand(2);
2668  MachineOperand &Src2 = InpDef->getOperand(3);
2669  // Check if both are non-zero.
2670  bool KnownNZ1 = IsNonZero(Src1), KnownNZ2 = IsNonZero(Src2);
2671  if (KnownNZ1 && KnownNZ2)
2672  return ReplaceWithConst(Opc == Hexagon::A4_rcmpneqi);
2673  // Check if both are zero.
2674  bool KnownZ1 = IsZero(Src1), KnownZ2 = IsZero(Src2);
2675  if (KnownZ1 && KnownZ2)
2676  return ReplaceWithConst(Opc == Hexagon::A4_rcmpeqi);
2677 
2678  // If for both operands we know that they are either 0 or non-0,
2679  // replace the comparison with a C2_muxii, using the same predicate
2680  // register, but with operands substituted with 0/1 accordingly.
2681  if ((KnownZ1 || KnownNZ1) && (KnownZ2 || KnownNZ2)) {
2682  unsigned NewR = MRI.createVirtualRegister(FRC);
2683  BuildMI(B, At, DL, HII.get(Hexagon::C2_muxii), NewR)
2684  .addReg(InpDef->getOperand(1).getReg())
2685  .addImm(KnownZ1 == (Opc == Hexagon::A4_rcmpeqi))
2686  .addImm(KnownZ2 == (Opc == Hexagon::A4_rcmpeqi));
2687  HBS::replaceReg(RD.Reg, NewR, MRI);
2688  // Create a new cell with only the least significant bit unknown.
2689  BitTracker::RegisterCell NewRC(W);
2690  NewRC[0] = BitTracker::BitValue::self();
2691  NewRC.fill(1, W, BitTracker::BitValue::Zero);
2692  BT.put(BitTracker::RegisterRef(NewR), NewRC);
2693  return true;
2694  }
2695  }
2696 
2697  return false;
2698 }
2699 
2700 bool BitSimplification::processBlock(MachineBasicBlock &B,
2701  const RegisterSet &AVs) {
2702  if (!BT.reached(&B))
2703  return false;
2704  bool Changed = false;
2705  RegisterSet AVB = AVs;
2706  RegisterSet Defs;
2707 
2708  for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Defs)) {
2709  MachineInstr *MI = &*I;
2710  Defs.clear();
2711  HBS::getInstrDefs(*MI, Defs);
2712 
2713  unsigned Opc = MI->getOpcode();
2714  if (Opc == TargetOpcode::COPY || Opc == TargetOpcode::REG_SEQUENCE)
2715  continue;
2716 
2717  if (MI->mayStore()) {
2718  bool T = genStoreUpperHalf(MI);
2719  T = T || genStoreImmediate(MI);
2720  Changed |= T;
2721  continue;
2722  }
2723 
2724  if (Defs.count() != 1)
2725  continue;
2726  const MachineOperand &Op0 = MI->getOperand(0);
2727  if (!Op0.isReg() || !Op0.isDef())
2728  continue;
2729  BitTracker::RegisterRef RD = Op0;
2730  if (!BT.has(RD.Reg))
2731  continue;
2732  const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2733  const BitTracker::RegisterCell &RC = BT.lookup(RD.Reg);
2734 
2735  if (FRC->getID() == Hexagon::DoubleRegsRegClassID) {
2736  bool T = genPackhl(MI, RD, RC);
2737  T = T || simplifyExtractLow(MI, RD, RC, AVB);
2738  Changed |= T;
2739  continue;
2740  }
2741 
2742  if (FRC->getID() == Hexagon::IntRegsRegClassID) {
2743  bool T = genBitSplit(MI, RD, RC, AVB);
2744  T = T || simplifyExtractLow(MI, RD, RC, AVB);
2745  T = T || genExtractHalf(MI, RD, RC);
2746  T = T || genCombineHalf(MI, RD, RC);
2747  T = T || genExtractLow(MI, RD, RC);
2748  T = T || simplifyRCmp0(MI, RD);
2749  Changed |= T;
2750  continue;
2751  }
2752 
2753  if (FRC->getID() == Hexagon::PredRegsRegClassID) {
2754  bool T = simplifyTstbit(MI, RD, RC);
2755  Changed |= T;
2756  continue;
2757  }
2758  }
2759  return Changed;
2760 }
2761 
2762 bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) {
2763  if (skipFunction(MF.getFunction()))
2764  return false;
2765 
2766  auto &HST = MF.getSubtarget<HexagonSubtarget>();
2767  auto &HRI = *HST.getRegisterInfo();
2768  auto &HII = *HST.getInstrInfo();
2769 
2770  MDT = &getAnalysis<MachineDominatorTree>();
2771  MachineRegisterInfo &MRI = MF.getRegInfo();
2772  bool Changed;
2773 
2774  Changed = DeadCodeElimination(MF, *MDT).run();
2775 
2776  const HexagonEvaluator HE(HRI, MRI, HII, MF);
2777  BitTracker BT(HE, MF);
2778  LLVM_DEBUG(BT.trace(true));
2779  BT.run();
2780 
2781  MachineBasicBlock &Entry = MF.front();
2782 
2783  RegisterSet AIG; // Available registers for IG.
2784  ConstGeneration ImmG(BT, HII, MRI);
2785  Changed |= visitBlock(Entry, ImmG, AIG);
2786 
2787  RegisterSet ARE; // Available registers for RIE.
2788  RedundantInstrElimination RIE(BT, HII, HRI, MRI);
2789  bool Ried = visitBlock(Entry, RIE, ARE);
2790  if (Ried) {
2791  Changed = true;
2792  BT.run();
2793  }
2794 
2795  RegisterSet ACG; // Available registers for CG.
2796  CopyGeneration CopyG(BT, HII, HRI, MRI);
2797  Changed |= visitBlock(Entry, CopyG, ACG);
2798 
2799  RegisterSet ACP; // Available registers for CP.
2800  CopyPropagation CopyP(HRI, MRI);
2801  Changed |= visitBlock(Entry, CopyP, ACP);
2802 
2803  Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2804 
2805  BT.run();
2806  RegisterSet ABS; // Available registers for BS.
2807  BitSimplification BitS(BT, *MDT, HII, HRI, MRI, MF);
2808  Changed |= visitBlock(Entry, BitS, ABS);
2809 
2810  Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2811 
2812  if (Changed) {
2813  for (auto &B : MF)
2814  for (auto &I : B)
2815  I.clearKillInfo();
2816  DeadCodeElimination(MF, *MDT).run();
2817  }
2818  return Changed;
2819 }
2820 
2821 // Recognize loops where the code at the end of the loop matches the code
2822 // before the entry of the loop, and the matching code is such that is can
2823 // be simplified. This pass relies on the bit simplification above and only
2824 // prepares code in a way that can be handled by the bit simplifcation.
2825 //
2826 // This is the motivating testcase (and explanation):
2827 //
2828 // {
2829 // loop0(.LBB0_2, r1) // %for.body.preheader
2830 // r5:4 = memd(r0++#8)
2831 // }
2832 // {
2833 // r3 = lsr(r4, #16)
2834 // r7:6 = combine(r5, r5)
2835 // }
2836 // {
2837 // r3 = insert(r5, #16, #16)
2838 // r7:6 = vlsrw(r7:6, #16)
2839 // }
2840 // .LBB0_2:
2841 // {
2842 // memh(r2+#4) = r5
2843 // memh(r2+#6) = r6 # R6 is really R5.H
2844 // }
2845 // {
2846 // r2 = add(r2, #8)
2847 // memh(r2+#0) = r4
2848 // memh(r2+#2) = r3 # R3 is really R4.H
2849 // }
2850 // {
2851 // r5:4 = memd(r0++#8)
2852 // }
2853 // { # "Shuffling" code that sets up R3 and R6
2854 // r3 = lsr(r4, #16) # so that their halves can be stored in the
2855 // r7:6 = combine(r5, r5) # next iteration. This could be folded into
2856 // } # the stores if the code was at the beginning
2857 // { # of the loop iteration. Since the same code
2858 // r3 = insert(r5, #16, #16) # precedes the loop, it can actually be moved
2859 // r7:6 = vlsrw(r7:6, #16) # there.
2860 // }:endloop0
2861 //
2862 //
2863 // The outcome:
2864 //
2865 // {
2866 // loop0(.LBB0_2, r1)
2867 // r5:4 = memd(r0++#8)
2868 // }
2869 // .LBB0_2:
2870 // {
2871 // memh(r2+#4) = r5
2872 // memh(r2+#6) = r5.h
2873 // }
2874 // {
2875 // r2 = add(r2, #8)
2876 // memh(r2+#0) = r4
2877 // memh(r2+#2) = r4.h
2878 // }
2879 // {
2880 // r5:4 = memd(r0++#8)
2881 // }:endloop0
2882 
2883 namespace llvm {
2884 
2887 
2888 } // end namespace llvm
2889 
2890 namespace {
2891 
2892  class HexagonLoopRescheduling : public MachineFunctionPass {
2893  public:
2894  static char ID;
2895 
2896  HexagonLoopRescheduling() : MachineFunctionPass(ID) {
2898  }
2899 
2900  bool runOnMachineFunction(MachineFunction &MF) override;
2901 
2902  private:
2903  const HexagonInstrInfo *HII = nullptr;
2904  const HexagonRegisterInfo *HRI = nullptr;
2905  MachineRegisterInfo *MRI = nullptr;
2906  BitTracker *BTP = nullptr;
2907 
2908  struct LoopCand {
2909  LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb,
2910  MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {}
2911 
2912  MachineBasicBlock *LB, *PB, *EB;
2913  };
2914  using InstrList = std::vector<MachineInstr *>;
2915  struct InstrGroup {
2916  BitTracker::RegisterRef Inp, Out;
2917  InstrList Ins;
2918  };
2919  struct PhiInfo {
2920  PhiInfo(MachineInstr &P, MachineBasicBlock &B);
2921 
2922  unsigned DefR;
2923  BitTracker::RegisterRef LR, PR; // Loop Register, Preheader Register
2924  MachineBasicBlock *LB, *PB; // Loop Block, Preheader Block
2925  };
2926 
2927  static unsigned getDefReg(const MachineInstr *MI);
2928  bool isConst(unsigned Reg) const;
2929  bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const;
2930  bool isStoreInput(const MachineInstr *MI, unsigned DefR) const;
2931  bool isShuffleOf(unsigned OutR, unsigned InpR) const;
2932  bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2,
2933  unsigned &InpR2) const;
2934  void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB,
2935  MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR);
2936  bool processLoop(LoopCand &C);
2937  };
2938 
2939 } // end anonymous namespace
2940 
2942 
2943 INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched",
2944  "Hexagon Loop Rescheduling", false, false)
2945 
2946 HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
2947  MachineBasicBlock &B) {
2948  DefR = HexagonLoopRescheduling::getDefReg(&P);
2949  LB = &B;
2950  PB = nullptr;
2951  for (unsigned i = 1, n = P.getNumOperands(); i < n; i += 2) {
2952  const MachineOperand &OpB = P.getOperand(i+1);
2953  if (OpB.getMBB() == &B) {
2954  LR = P.getOperand(i);
2955  continue;
2956  }
2957  PB = OpB.getMBB();
2958  PR = P.getOperand(i);
2959  }
2960 }
2961 
2962 unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) {
2963  RegisterSet Defs;
2964  HBS::getInstrDefs(*MI, Defs);
2965  if (Defs.count() != 1)
2966  return 0;
2967  return Defs.find_first();
2968 }
2969 
2970 bool HexagonLoopRescheduling::isConst(unsigned Reg) const {
2971  if (!BTP->has(Reg))
2972  return false;
2973  const BitTracker::RegisterCell &RC = BTP->lookup(Reg);
2974  for (unsigned i = 0, w = RC.width(); i < w; ++i) {
2975  const BitTracker::BitValue &V = RC[i];
2976  if (!V.is(0) && !V.is(1))
2977  return false;
2978  }
2979  return true;
2980 }
2981 
2982 bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
2983  unsigned DefR) const {
2984  unsigned Opc = MI->getOpcode();
2985  switch (Opc) {
2986  case TargetOpcode::COPY:
2987  case Hexagon::S2_lsr_i_r:
2988  case Hexagon::S2_asr_i_r:
2989  case Hexagon::S2_asl_i_r:
2990  case Hexagon::S2_lsr_i_p:
2991  case Hexagon::S2_asr_i_p:
2992  case Hexagon::S2_asl_i_p:
2993  case Hexagon::S2_insert:
2994  case Hexagon::A2_or:
2995  case Hexagon::A2_orp:
2996  case Hexagon::A2_and:
2997  case Hexagon::A2_andp:
2998  case Hexagon::A2_combinew:
2999  case Hexagon::A4_combineri:
3000  case Hexagon::A4_combineir:
3001  case Hexagon::A2_combineii:
3002  case Hexagon::A4_combineii:
3003  case Hexagon::A2_combine_ll:
3004  case Hexagon::A2_combine_lh:
3005  case Hexagon::A2_combine_hl:
3006  case Hexagon::A2_combine_hh:
3007  return true;
3008  }
3009  return false;
3010 }
3011 
3012 bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
3013  unsigned InpR) const {
3014  for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
3015  const MachineOperand &Op = MI->getOperand(i);
3016  if (!Op.isReg())
3017  continue;
3018  if (Op.getReg() == InpR)
3019  return i == n-1;
3020  }
3021  return false;
3022 }
3023 
3024 bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const {
3025  if (!BTP->has(OutR) || !BTP->has(InpR))
3026  return false;
3027  const BitTracker::RegisterCell &OutC = BTP->lookup(OutR);
3028  for (unsigned i = 0, w = OutC.width(); i < w; ++i) {
3029  const BitTracker::BitValue &V = OutC[i];
3031  continue;
3032  if (V.RefI.Reg != InpR)
3033  return false;
3034  }
3035  return true;
3036 }
3037 
3038 bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
3039  unsigned OutR2, unsigned &InpR2) const {
3040  if (!BTP->has(OutR1) || !BTP->has(InpR1) || !BTP->has(OutR2))
3041  return false;
3042  const BitTracker::RegisterCell &OutC1 = BTP->lookup(OutR1);
3043  const BitTracker::RegisterCell &OutC2 = BTP->lookup(OutR2);
3044  unsigned W = OutC1.width();
3045  unsigned MatchR = 0;
3046  if (W != OutC2.width())
3047  return false;
3048  for (unsigned i = 0; i < W; ++i) {
3049  const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i];
3050  if (V1.Type != V2.Type || V1.Type == BitTracker::BitValue::One)
3051  return false;
3052  if (V1.Type != BitTracker::BitValue::Ref)
3053  continue;
3054  if (V1.RefI.Pos != V2.RefI.Pos)
3055  return false;
3056  if (V1.RefI.Reg != InpR1)
3057  return false;
3058  if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2)
3059  return false;
3060  if (!MatchR)
3061  MatchR = V2.RefI.Reg;
3062  else if (V2.RefI.Reg != MatchR)
3063  return false;
3064  }
3065  InpR2 = MatchR;
3066  return true;
3067 }
3068 
3069 void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
3070  MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
3071  unsigned NewPredR) {
3073 
3074  const TargetRegisterClass *PhiRC = MRI->getRegClass(NewPredR);
3075  unsigned PhiR = MRI->createVirtualRegister(PhiRC);
3076  BuildMI(LB, At, At->getDebugLoc(), HII->get(TargetOpcode::PHI), PhiR)
3077  .addReg(NewPredR)
3078  .addMBB(&PB)
3079  .addReg(G.Inp.Reg)
3080  .addMBB(&LB);
3081  RegMap.insert(std::make_pair(G.Inp.Reg, PhiR));
3082 
3083  for (unsigned i = G.Ins.size(); i > 0; --i) {
3084  const MachineInstr *SI = G.Ins[i-1];
3085  unsigned DR = getDefReg(SI);
3086  const TargetRegisterClass *RC = MRI->getRegClass(DR);
3087  unsigned NewDR = MRI->createVirtualRegister(RC);
3088  DebugLoc DL = SI->getDebugLoc();
3089 
3090  auto MIB = BuildMI(LB, At, DL, HII->get(SI->getOpcode()), NewDR);
3091  for (unsigned j = 0, m = SI->getNumOperands(); j < m; ++j) {
3092  const MachineOperand &Op = SI->getOperand(j);
3093  if (!Op.isReg()) {
3094  MIB.add(Op);
3095  continue;
3096  }
3097  if (!Op.isUse())
3098  continue;
3099  unsigned UseR = RegMap[Op.getReg()];
3100  MIB.addReg(UseR, 0, Op.getSubReg());
3101  }
3102  RegMap.insert(std::make_pair(DR, NewDR));
3103  }
3104 
3105  HBS::replaceReg(OldPhiR, RegMap[G.Out.Reg], *MRI);
3106 }
3107 
3108 bool HexagonLoopRescheduling::processLoop(LoopCand &C) {
3109  LLVM_DEBUG(dbgs() << "Processing loop in " << printMBBReference(*C.LB)
3110  << "\n");
3111  std::vector<PhiInfo> Phis;
3112  for (auto &I : *C.LB) {
3113  if (!I.isPHI())
3114  break;
3115  unsigned PR = getDefReg(&I);
3116  if (isConst(PR))
3117  continue;
3118  bool BadUse = false, GoodUse = false;
3119  for (auto UI = MRI->use_begin(PR), UE = MRI->use_end(); UI != UE; ++UI) {
3120  MachineInstr *UseI = UI->getParent();
3121  if (UseI->getParent() != C.LB) {
3122  BadUse = true;
3123  break;
3124  }
3125  if (isBitShuffle(UseI, PR) || isStoreInput(UseI, PR))
3126  GoodUse = true;
3127  }
3128  if (BadUse || !GoodUse)
3129  continue;
3130 
3131  Phis.push_back(PhiInfo(I, *C.LB));
3132  }
3133 
3134  LLVM_DEBUG({
3135  dbgs() << "Phis: {";
3136  for (auto &I : Phis) {
3137  dbgs() << ' ' << printReg(I.DefR, HRI) << "=phi("
3138  << printReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber()
3139  << ',' << printReg(I.LR.Reg, HRI, I.LR.Sub) << ":b"
3140  << I.LB->getNumber() << ')';
3141  }
3142  dbgs() << " }\n";
3143  });
3144 
3145  if (Phis.empty())
3146  return false;
3147 
3148  bool Changed = false;
3149  InstrList ShufIns;
3150 
3151  // Go backwards in the block: for each bit shuffling instruction, check
3152  // if that instruction could potentially be moved to the front of the loop:
3153  // the output of the loop cannot be used in a non-shuffling instruction
3154  // in this loop.
3155  for (auto I = C.LB->rbegin(), E = C.LB->rend(); I != E; ++I) {
3156  if (I->isTerminator())
3157  continue;
3158  if (I->isPHI())
3159  break;
3160 
3161  RegisterSet Defs;
3162  HBS::getInstrDefs(*I, Defs);
3163  if (Defs.count() != 1)
3164  continue;
3165  unsigned DefR = Defs.find_first();
3167  continue;
3168  if (!isBitShuffle(&*I, DefR))
3169  continue;
3170 
3171  bool BadUse = false;
3172  for (auto UI = MRI->use_begin(DefR), UE = MRI->use_end(); UI != UE; ++UI) {
3173  MachineInstr *UseI = UI->getParent();
3174  if (UseI->getParent() == C.LB) {
3175  if (UseI->isPHI()) {
3176  // If the use is in a phi node in this loop, then it should be
3177  // the value corresponding to the back edge.
3178  unsigned Idx = UI.getOperandNo();
3179  if (UseI->getOperand(Idx+1).getMBB() != C.LB)
3180  BadUse = true;
3181  } else {
3182  auto F = find(ShufIns, UseI);
3183  if (F == ShufIns.end())
3184  BadUse = true;
3185  }
3186  } else {
3187  // There is a use outside of the loop, but there is no epilog block
3188  // suitable for a copy-out.
3189  if (C.EB == nullptr)
3190  BadUse = true;
3191  }
3192  if (BadUse)
3193  break;
3194  }
3195 
3196  if (BadUse)
3197  continue;
3198  ShufIns.push_back(&*I);
3199  }
3200 
3201  // Partition the list of shuffling instructions into instruction groups,
3202  // where each group has to be moved as a whole (i.e. a group is a chain of
3203  // dependent instructions). A group produces a single live output register,
3204  // which is meant to be the input of the loop phi node (although this is
3205  // not checked here yet). It also uses a single register as its input,
3206  // which is some value produced in the loop body. After moving the group
3207  // to the beginning of the loop, that input register would need to be
3208  // the loop-carried register (through a phi node) instead of the (currently
3209  // loop-carried) output register.
3210  using InstrGroupList = std::vector<InstrGroup>;
3211  InstrGroupList Groups;
3212 
3213  for (unsigned i = 0, n = ShufIns.size(); i < n; ++i) {
3214  MachineInstr *SI = ShufIns[i];
3215  if (SI == nullptr)
3216  continue;
3217 
3218  InstrGroup G;
3219  G.Ins.push_back(SI);
3220  G.Out.Reg = getDefReg(SI);
3221  RegisterSet Inputs;
3222  HBS::getInstrUses(*SI, Inputs);
3223 
3224  for (unsigned j = i+1; j < n; ++j) {
3225  MachineInstr *MI = ShufIns[j];
3226  if (MI == nullptr)
3227  continue;
3228  RegisterSet Defs;
3229  HBS::getInstrDefs(*MI, Defs);
3230  // If this instruction does not define any pending inputs, skip it.
3231  if (!Defs.intersects(Inputs))
3232  continue;
3233  // Otherwise, add it to the current group and remove the inputs that
3234  // are defined by MI.
3235  G.Ins.push_back(MI);
3236  Inputs.remove(Defs);
3237  // Then add all registers used by MI.
3238  HBS::getInstrUses(*MI, Inputs);
3239  ShufIns[j] = nullptr;
3240  }
3241 
3242  // Only add a group if it requires at most one register.
3243  if (Inputs.count() > 1)
3244  continue;
3245  auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3246  return G.Out.Reg == P.LR.Reg;
3247  };
3248  if (llvm::find_if(Phis, LoopInpEq) == Phis.end())
3249  continue;
3250 
3251  G.Inp.Reg = Inputs.find_first();
3252  Groups.push_back(G);
3253  }
3254 
3255  LLVM_DEBUG({
3256  for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3257  InstrGroup &G = Groups[i];
3258  dbgs() << "Group[" << i << "] inp: "
3259  << printReg(G.Inp.Reg, HRI, G.Inp.Sub)
3260  << " out: " << printReg(G.Out.Reg, HRI, G.Out.Sub) << "\n";
3261  for (unsigned j = 0, m = G.Ins.size(); j < m; ++j)
3262  dbgs() << " " << *G.Ins[j];
3263  }
3264  });
3265 
3266  for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3267  InstrGroup &G = Groups[i];
3268  if (!isShuffleOf(G.Out.Reg, G.Inp.Reg))
3269  continue;
3270  auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3271  return G.Out.Reg == P.LR.Reg;
3272  };
3273  auto F = llvm::find_if(Phis, LoopInpEq);
3274  if (F == Phis.end())
3275  continue;
3276  unsigned PrehR = 0;
3277  if (!isSameShuffle(G.Out.Reg, G.Inp.Reg, F->PR.Reg, PrehR)) {
3278  const MachineInstr *DefPrehR = MRI->getVRegDef(F->PR.Reg);
3279  unsigned Opc = DefPrehR->getOpcode();
3280  if (Opc != Hexagon::A2_tfrsi && Opc != Hexagon::A2_tfrpi)
3281  continue;
3282  if (!DefPrehR->getOperand(1).isImm())
3283  continue;
3284  if (DefPrehR->getOperand(1).getImm() != 0)
3285  continue;
3286  const TargetRegisterClass *RC = MRI->getRegClass(G.Inp.Reg);
3287  if (RC != MRI->getRegClass(F->PR.Reg)) {
3288  PrehR = MRI->createVirtualRegister(RC);
3289  unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi
3290  : Hexagon::A2_tfrpi;
3291  auto T = C.PB->getFirstTerminator();
3292  DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc();
3293  BuildMI(*C.PB, T, DL, HII->get(TfrI), PrehR)
3294  .addImm(0);
3295  } else {
3296  PrehR = F->PR.Reg;
3297  }
3298  }
3299  // isSameShuffle could match with PrehR being of a wider class than
3300  // G.Inp.Reg, for example if G shuffles the low 32 bits of its input,
3301  // it would match for the input being a 32-bit register, and PrehR
3302  // being a 64-bit register (where the low 32 bits match). This could
3303  // be handled, but for now skip these cases.
3304  if (MRI->getRegClass(PrehR) != MRI->getRegClass(G.Inp.Reg))
3305  continue;
3306  moveGroup(G, *F->LB, *F->PB, F->LB->getFirstNonPHI(), F->DefR, PrehR);
3307  Changed = true;
3308  }
3309 
3310  return Changed;
3311 }
3312 
3313 bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) {
3314  if (skipFunction(MF.getFunction()))
3315  return false;
3316 
3317  auto &HST = MF.getSubtarget<HexagonSubtarget>();
3318  HII = HST.getInstrInfo();
3319  HRI = HST.getRegisterInfo();
3320  MRI = &MF.getRegInfo();
3321  const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
3322  BitTracker BT(HE, MF);
3323  LLVM_DEBUG(BT.trace(true));
3324  BT.run();
3325  BTP = &BT;
3326 
3327  std::vector<LoopCand> Cand;
3328 
3329  for (auto &B : MF) {
3330  if (B.pred_size() != 2 || B.succ_size() != 2)
3331  continue;
3332  MachineBasicBlock *PB = nullptr;
3333  bool IsLoop = false;
3334  for (auto PI = B.pred_begin(), PE = B.pred_end(); PI != PE; ++PI) {
3335  if (*PI != &B)
3336  PB = *PI;
3337  else
3338  IsLoop = true;
3339  }
3340  if (!IsLoop)
3341  continue;
3342 
3343  MachineBasicBlock *EB = nullptr;
3344  for (auto SI = B.succ_begin(), SE = B.succ_end(); SI != SE; ++SI) {
3345  if (*SI == &B)
3346  continue;
3347  // Set EP to the epilog block, if it has only 1 predecessor (i.e. the
3348  // edge from B to EP is non-critical.
3349  if ((*SI)->pred_size() == 1)
3350  EB = *SI;
3351  break;
3352  }
3353 
3354  Cand.push_back(LoopCand(&B, PB, EB));
3355  }
3356 
3357  bool Changed = false;
3358  for (auto &C : Cand)
3359  Changed |= processLoop(C);
3360 
3361  return Changed;
3362 }
3363 
3364 //===----------------------------------------------------------------------===//
3365 // Public Constructor Functions
3366 //===----------------------------------------------------------------------===//
3367 
3369  return new HexagonLoopRescheduling();
3370 }
3371 
3373  return new HexagonBitSimplify();
3374 }
uint64_t CallInst * C
void push_back(const T &Elt)
Definition: SmallVector.h:218
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.
RegisterCell & fill(uint16_t B, uint16_t E, const BitValue &V)
Definition: BitTracker.cpp:275
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:492
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
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:383
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
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:509
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
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:459
bool isPHI() const
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:196
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:210
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
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:377
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:649
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
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:406
static bool isEqual(const Function &Caller, const Function &Callee)
BitVector & operator|=(const BitVector &RHS)
Definition: BitVector.h:603
#define T
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:813
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:820
#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:524
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:1049
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:1070
FunctionPass * createHexagonLoopRescheduling()
bool isCopy() const
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:1063
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:1023
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
static BitValue self(const BitRef &Self=BitRef())
Definition: BitTracker.h:280
void initializeHexagonBitSimplifyPass(PassRegistry &Registry)
static unsigned CountExtract
iterator_range< use_iterator > use_operands(unsigned Reg) const
bool isDebugValue() const
Definition: MachineInstr.h:997
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:225
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:399
unsigned succ_size() const
INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched", "Hexagon Loop Rescheduling", false, false) HexagonLoopRescheduling
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
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:64
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:2033
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
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.
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:160
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:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
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...