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