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