LLVM  10.0.0svn
HexagonGenInsert.cpp
Go to the documentation of this file.
1 //===- HexagonGenInsert.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"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringRef.h"
31 #include "llvm/IR/DebugLoc.h"
32 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/Timer.h"
38 #include <algorithm>
39 #include <cassert>
40 #include <cstdint>
41 #include <iterator>
42 #include <utility>
43 #include <vector>
44 
45 #define DEBUG_TYPE "hexinsert"
46 
47 using namespace llvm;
48 
49 static cl::opt<unsigned> VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U),
50  cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg# cutoff for insert generation."));
51 // The distance cutoff is selected based on the precheckin-perf results:
52 // cutoffs 20, 25, 35, and 40 are worse than 30.
53 static cl::opt<unsigned> VRegDistCutoff("insert-dist-cutoff", cl::init(30U),
54  cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg distance cutoff for insert "
55  "generation."));
56 
57 // Limit the container sizes for extreme cases where we run out of memory.
58 static cl::opt<unsigned> MaxORLSize("insert-max-orl", cl::init(4096),
59  cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of OrderedRegisterList"));
60 static cl::opt<unsigned> MaxIFMSize("insert-max-ifmap", cl::init(1024),
61  cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of IFMap"));
62 
63 static cl::opt<bool> OptTiming("insert-timing", cl::init(false), cl::Hidden,
64  cl::ZeroOrMore, cl::desc("Enable timing of insert generation"));
65 static cl::opt<bool> OptTimingDetail("insert-timing-detail", cl::init(false),
66  cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert "
67  "generation"));
68 
69 static cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden,
71 static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden,
73 // Whether to construct constant values via "insert". Could eliminate constant
74 // extenders, but often not practical.
75 static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden,
77 
78 // The preprocessor gets confused when the DEBUG macro is passed larger
79 // chunks of code. Use this function to detect debugging.
80 inline static bool isDebug() {
81 #ifndef NDEBUG
83 #else
84  return false;
85 #endif
86 }
87 
88 namespace {
89 
90  // Set of virtual registers, based on BitVector.
91  struct RegisterSet : private BitVector {
92  RegisterSet() = default;
93  explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
94  RegisterSet(const RegisterSet &RS) : BitVector(RS) {}
95 
96  using BitVector::clear;
97 
98  unsigned find_first() const {
99  int First = BitVector::find_first();
100  if (First < 0)
101  return 0;
102  return x2v(First);
103  }
104 
105  unsigned find_next(unsigned Prev) const {
106  int Next = BitVector::find_next(v2x(Prev));
107  if (Next < 0)
108  return 0;
109  return x2v(Next);
110  }
111 
112  RegisterSet &insert(unsigned R) {
113  unsigned Idx = v2x(R);
114  ensure(Idx);
115  return static_cast<RegisterSet&>(BitVector::set(Idx));
116  }
117  RegisterSet &remove(unsigned R) {
118  unsigned Idx = v2x(R);
119  if (Idx >= size())
120  return *this;
121  return static_cast<RegisterSet&>(BitVector::reset(Idx));
122  }
123 
124  RegisterSet &insert(const RegisterSet &Rs) {
125  return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
126  }
127  RegisterSet &remove(const RegisterSet &Rs) {
128  return static_cast<RegisterSet&>(BitVector::reset(Rs));
129  }
130 
131  reference operator[](unsigned R) {
132  unsigned Idx = v2x(R);
133  ensure(Idx);
134  return BitVector::operator[](Idx);
135  }
136  bool operator[](unsigned R) const {
137  unsigned Idx = v2x(R);
138  assert(Idx < size());
139  return BitVector::operator[](Idx);
140  }
141  bool has(unsigned R) const {
142  unsigned Idx = v2x(R);
143  if (Idx >= size())
144  return false;
145  return BitVector::test(Idx);
146  }
147 
148  bool empty() const {
149  return !BitVector::any();
150  }
151  bool includes(const RegisterSet &Rs) const {
152  // A.BitVector::test(B) <=> A-B != {}
153  return !Rs.BitVector::test(*this);
154  }
155  bool intersects(const RegisterSet &Rs) const {
156  return BitVector::anyCommon(Rs);
157  }
158 
159  private:
160  void ensure(unsigned Idx) {
161  if (size() <= Idx)
162  resize(std::max(Idx+1, 32U));
163  }
164 
165  static inline unsigned v2x(unsigned v) {
166  return Register::virtReg2Index(v);
167  }
168 
169  static inline unsigned x2v(unsigned x) {
170  return Register::index2VirtReg(x);
171  }
172  };
173 
174  struct PrintRegSet {
175  PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
176  : RS(S), TRI(RI) {}
177 
178  friend raw_ostream &operator<< (raw_ostream &OS,
179  const PrintRegSet &P);
180 
181  private:
182  const RegisterSet &RS;
183  const TargetRegisterInfo *TRI;
184  };
185 
186  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
187  OS << '{';
188  for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
189  OS << ' ' << printReg(R, P.TRI);
190  OS << " }";
191  return OS;
192  }
193 
194  // A convenience class to associate unsigned numbers (such as virtual
195  // registers) with unsigned numbers.
196  struct UnsignedMap : public DenseMap<unsigned,unsigned> {
197  UnsignedMap() = default;
198 
199  private:
201  };
202 
203  // A utility to establish an ordering between virtual registers:
204  // VRegA < VRegB <=> RegisterOrdering[VRegA] < RegisterOrdering[VRegB]
205  // This is meant as a cache for the ordering of virtual registers defined
206  // by a potentially expensive comparison function, or obtained by a proce-
207  // dure that should not be repeated each time two registers are compared.
208  struct RegisterOrdering : public UnsignedMap {
209  RegisterOrdering() = default;
210 
211  unsigned operator[](unsigned VR) const {
212  const_iterator F = find(VR);
213  assert(F != end());
214  return F->second;
215  }
216 
217  // Add operator(), so that objects of this class can be used as
218  // comparators in std::sort et al.
219  bool operator() (unsigned VR1, unsigned VR2) const {
220  return operator[](VR1) < operator[](VR2);
221  }
222  };
223 
224  // Ordering of bit values. This class does not have operator[], but
225  // is supplies a comparison operator() for use in std:: algorithms.
226  // The order is as follows:
227  // - 0 < 1 < ref
228  // - ref1 < ref2, if ord(ref1.Reg) < ord(ref2.Reg),
229  // or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos.
230  struct BitValueOrdering {
231  BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {}
232 
233  bool operator() (const BitTracker::BitValue &V1,
234  const BitTracker::BitValue &V2) const;
235 
236  const RegisterOrdering &BaseOrd;
237  };
238 
239 } // end anonymous namespace
240 
241 bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
242  const BitTracker::BitValue &V2) const {
243  if (V1 == V2)
244  return false;
245  // V1==0 => true, V2==0 => false
246  if (V1.is(0) || V2.is(0))
247  return V1.is(0);
248  // Neither of V1,V2 is 0, and V1!=V2.
249  // V2==1 => false, V1==1 => true
250  if (V2.is(1) || V1.is(1))
251  return !V2.is(1);
252  // Both V1,V2 are refs.
253  unsigned Ind1 = BaseOrd[V1.RefI.Reg], Ind2 = BaseOrd[V2.RefI.Reg];
254  if (Ind1 != Ind2)
255  return Ind1 < Ind2;
256  // If V1.Pos==V2.Pos
257  assert(V1.RefI.Pos != V2.RefI.Pos && "Bit values should be different");
258  return V1.RefI.Pos < V2.RefI.Pos;
259 }
260 
261 namespace {
262 
263  // Cache for the BitTracker's cell map. Map lookup has a logarithmic
264  // complexity, this class will memoize the lookup results to reduce
265  // the access time for repeated lookups of the same cell.
266  struct CellMapShadow {
267  CellMapShadow(const BitTracker &T) : BT(T) {}
268 
269  const BitTracker::RegisterCell &lookup(unsigned VR) {
270  unsigned RInd = Register::virtReg2Index(VR);
271  // Grow the vector to at least 32 elements.
272  if (RInd >= CVect.size())
273  CVect.resize(std::max(RInd+16, 32U), nullptr);
274  const BitTracker::RegisterCell *CP = CVect[RInd];
275  if (CP == nullptr)
276  CP = CVect[RInd] = &BT.lookup(VR);
277  return *CP;
278  }
279 
280  const BitTracker &BT;
281 
282  private:
283  using CellVectType = std::vector<const BitTracker::RegisterCell *>;
284 
285  CellVectType CVect;
286  };
287 
288  // Comparator class for lexicographic ordering of virtual registers
289  // according to the corresponding BitTracker::RegisterCell objects.
290  struct RegisterCellLexCompare {
291  RegisterCellLexCompare(const BitValueOrdering &BO, CellMapShadow &M)
292  : BitOrd(BO), CM(M) {}
293 
294  bool operator() (unsigned VR1, unsigned VR2) const;
295 
296  private:
297  const BitValueOrdering &BitOrd;
298  CellMapShadow &CM;
299  };
300 
301  // Comparator class for lexicographic ordering of virtual registers
302  // according to the specified bits of the corresponding BitTracker::
303  // RegisterCell objects.
304  // Specifically, this class will be used to compare bit B of a register
305  // cell for a selected virtual register R with bit N of any register
306  // other than R.
307  struct RegisterCellBitCompareSel {
308  RegisterCellBitCompareSel(unsigned R, unsigned B, unsigned N,
309  const BitValueOrdering &BO, CellMapShadow &M)
310  : SelR(R), SelB(B), BitN(N), BitOrd(BO), CM(M) {}
311 
312  bool operator() (unsigned VR1, unsigned VR2) const;
313 
314  private:
315  const unsigned SelR, SelB;
316  const unsigned BitN;
317  const BitValueOrdering &BitOrd;
318  CellMapShadow &CM;
319  };
320 
321 } // end anonymous namespace
322 
323 bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
324  // Ordering of registers, made up from two given orderings:
325  // - the ordering of the register numbers, and
326  // - the ordering of register cells.
327  // Def. R1 < R2 if:
328  // - cell(R1) < cell(R2), or
329  // - cell(R1) == cell(R2), and index(R1) < index(R2).
330  //
331  // For register cells, the ordering is lexicographic, with index 0 being
332  // the most significant.
333  if (VR1 == VR2)
334  return false;
335 
336  const BitTracker::RegisterCell &RC1 = CM.lookup(VR1), &RC2 = CM.lookup(VR2);
337  uint16_t W1 = RC1.width(), W2 = RC2.width();
338  for (uint16_t i = 0, w = std::min(W1, W2); i < w; ++i) {
339  const BitTracker::BitValue &V1 = RC1[i], &V2 = RC2[i];
340  if (V1 != V2)
341  return BitOrd(V1, V2);
342  }
343  // Cells are equal up until the common length.
344  if (W1 != W2)
345  return W1 < W2;
346 
347  return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2];
348 }
349 
350 bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
351  if (VR1 == VR2)
352  return false;
353  const BitTracker::RegisterCell &RC1 = CM.lookup(VR1);
354  const BitTracker::RegisterCell &RC2 = CM.lookup(VR2);
355  uint16_t W1 = RC1.width(), W2 = RC2.width();
356  uint16_t Bit1 = (VR1 == SelR) ? SelB : BitN;
357  uint16_t Bit2 = (VR2 == SelR) ? SelB : BitN;
358  // If Bit1 exceeds the width of VR1, then:
359  // - return false, if at the same time Bit2 exceeds VR2, or
360  // - return true, otherwise.
361  // (I.e. "a bit value that does not exist is less than any bit value
362  // that does exist".)
363  if (W1 <= Bit1)
364  return Bit2 < W2;
365  // If Bit1 is within VR1, but Bit2 is not within VR2, return false.
366  if (W2 <= Bit2)
367  return false;
368 
369  const BitTracker::BitValue &V1 = RC1[Bit1], V2 = RC2[Bit2];
370  if (V1 != V2)
371  return BitOrd(V1, V2);
372  return false;
373 }
374 
375 namespace {
376 
377  class OrderedRegisterList {
378  using ListType = std::vector<unsigned>;
379  const unsigned MaxSize;
380 
381  public:
382  OrderedRegisterList(const RegisterOrdering &RO)
383  : MaxSize(MaxORLSize), Ord(RO) {}
384 
385  void insert(unsigned VR);
386  void remove(unsigned VR);
387 
388  unsigned operator[](unsigned Idx) const {
389  assert(Idx < Seq.size());
390  return Seq[Idx];
391  }
392 
393  unsigned size() const {
394  return Seq.size();
395  }
396 
397  using iterator = ListType::iterator;
398  using const_iterator = ListType::const_iterator;
399 
400  iterator begin() { return Seq.begin(); }
401  iterator end() { return Seq.end(); }
402  const_iterator begin() const { return Seq.begin(); }
403  const_iterator end() const { return Seq.end(); }
404 
405  // Convenience function to convert an iterator to the corresponding index.
406  unsigned idx(iterator It) const { return It-begin(); }
407 
408  private:
409  ListType Seq;
410  const RegisterOrdering &Ord;
411  };
412 
413  struct PrintORL {
414  PrintORL(const OrderedRegisterList &L, const TargetRegisterInfo *RI)
415  : RL(L), TRI(RI) {}
416 
417  friend raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P);
418 
419  private:
420  const OrderedRegisterList &RL;
421  const TargetRegisterInfo *TRI;
422  };
423 
424  raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) {
425  OS << '(';
426  OrderedRegisterList::const_iterator B = P.RL.begin(), E = P.RL.end();
427  for (OrderedRegisterList::const_iterator I = B; I != E; ++I) {
428  if (I != B)
429  OS << ", ";
430  OS << printReg(*I, P.TRI);
431  }
432  OS << ')';
433  return OS;
434  }
435 
436 } // end anonymous namespace
437 
438 void OrderedRegisterList::insert(unsigned VR) {
439  iterator L = llvm::lower_bound(Seq, VR, Ord);
440  if (L == Seq.end())
441  Seq.push_back(VR);
442  else
443  Seq.insert(L, VR);
444 
445  unsigned S = Seq.size();
446  if (S > MaxSize)
447  Seq.resize(MaxSize);
448  assert(Seq.size() <= MaxSize);
449 }
450 
451 void OrderedRegisterList::remove(unsigned VR) {
452  iterator L = llvm::lower_bound(Seq, VR, Ord);
453  if (L != Seq.end())
454  Seq.erase(L);
455 }
456 
457 namespace {
458 
459  // A record of the insert form. The fields correspond to the operands
460  // of the "insert" instruction:
461  // ... = insert(SrcR, InsR, #Wdh, #Off)
462  struct IFRecord {
463  IFRecord(unsigned SR = 0, unsigned IR = 0, uint16_t W = 0, uint16_t O = 0)
464  : SrcR(SR), InsR(IR), Wdh(W), Off(O) {}
465 
466  unsigned SrcR, InsR;
467  uint16_t Wdh, Off;
468  };
469 
470  struct PrintIFR {
471  PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI)
472  : IFR(R), TRI(RI) {}
473 
474  private:
475  friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P);
476 
477  const IFRecord &IFR;
478  const TargetRegisterInfo *TRI;
479  };
480 
481  raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) {
482  unsigned SrcR = P.IFR.SrcR, InsR = P.IFR.InsR;
483  OS << '(' << printReg(SrcR, P.TRI) << ',' << printReg(InsR, P.TRI)
484  << ",#" << P.IFR.Wdh << ",#" << P.IFR.Off << ')';
485  return OS;
486  }
487 
488  using IFRecordWithRegSet = std::pair<IFRecord, RegisterSet>;
489 
490 } // end anonymous namespace
491 
492 namespace llvm {
493 
496 
497 } // end namespace llvm
498 
499 namespace {
500 
501  class HexagonGenInsert : public MachineFunctionPass {
502  public:
503  static char ID;
504 
505  HexagonGenInsert() : MachineFunctionPass(ID) {
507  }
508 
509  StringRef getPassName() const override {
510  return "Hexagon generate \"insert\" instructions";
511  }
512 
513  void getAnalysisUsage(AnalysisUsage &AU) const override {
517  }
518 
519  bool runOnMachineFunction(MachineFunction &MF) override;
520 
521  private:
522  using PairMapType = DenseMap<std::pair<unsigned, unsigned>, unsigned>;
523 
524  void buildOrderingMF(RegisterOrdering &RO) const;
525  void buildOrderingBT(RegisterOrdering &RB, RegisterOrdering &RO) const;
526  bool isIntClass(const TargetRegisterClass *RC) const;
527  bool isConstant(unsigned VR) const;
528  bool isSmallConstant(unsigned VR) const;
529  bool isValidInsertForm(unsigned DstR, unsigned SrcR, unsigned InsR,
530  uint16_t L, uint16_t S) const;
531  bool findSelfReference(unsigned VR) const;
532  bool findNonSelfReference(unsigned VR) const;
533  void getInstrDefs(const MachineInstr *MI, RegisterSet &Defs) const;
534  void getInstrUses(const MachineInstr *MI, RegisterSet &Uses) const;
535  unsigned distance(const MachineBasicBlock *FromB,
536  const MachineBasicBlock *ToB, const UnsignedMap &RPO,
537  PairMapType &M) const;
538  unsigned distance(MachineBasicBlock::const_iterator FromI,
539  MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
540  PairMapType &M) const;
541  bool findRecordInsertForms(unsigned VR, OrderedRegisterList &AVs);
542  void collectInBlock(MachineBasicBlock *B, OrderedRegisterList &AVs);
543  void findRemovableRegisters(unsigned VR, IFRecord IF,
544  RegisterSet &RMs) const;
545  void computeRemovableRegisters();
546 
547  void pruneEmptyLists();
548  void pruneCoveredSets(unsigned VR);
549  void pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, PairMapType &M);
550  void pruneRegCopies(unsigned VR);
551  void pruneCandidates();
552  void selectCandidates();
553  bool generateInserts();
554 
555  bool removeDeadCode(MachineDomTreeNode *N);
556 
557  // IFRecord coupled with a set of potentially removable registers:
558  using IFListType = std::vector<IFRecordWithRegSet>;
559  using IFMapType = DenseMap<unsigned, IFListType>; // vreg -> IFListType
560 
561  void dump_map() const;
562 
563  const HexagonInstrInfo *HII = nullptr;
564  const HexagonRegisterInfo *HRI = nullptr;
565 
566  MachineFunction *MFN;
569  CellMapShadow *CMS;
570 
571  RegisterOrdering BaseOrd;
572  RegisterOrdering CellOrd;
573  IFMapType IFMap;
574  };
575 
576 } // end anonymous namespace
577 
578 char HexagonGenInsert::ID = 0;
579 
580 void HexagonGenInsert::dump_map() const {
581  using iterator = IFMapType::const_iterator;
582 
583  for (iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
584  dbgs() << " " << printReg(I->first, HRI) << ":\n";
585  const IFListType &LL = I->second;
586  for (unsigned i = 0, n = LL.size(); i < n; ++i)
587  dbgs() << " " << PrintIFR(LL[i].first, HRI) << ", "
588  << PrintRegSet(LL[i].second, HRI) << '\n';
589  }
590 }
591 
592 void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
593  unsigned Index = 0;
594 
595  using mf_iterator = MachineFunction::const_iterator;
596 
597  for (mf_iterator A = MFN->begin(), Z = MFN->end(); A != Z; ++A) {
598  const MachineBasicBlock &B = *A;
599  if (!CMS->BT.reached(&B))
600  continue;
601 
602  using mb_iterator = MachineBasicBlock::const_iterator;
603 
604  for (mb_iterator I = B.begin(), E = B.end(); I != E; ++I) {
605  const MachineInstr *MI = &*I;
606  for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
607  const MachineOperand &MO = MI->getOperand(i);
608  if (MO.isReg() && MO.isDef()) {
609  Register R = MO.getReg();
610  assert(MO.getSubReg() == 0 && "Unexpected subregister in definition");
612  RO.insert(std::make_pair(R, Index++));
613  }
614  }
615  }
616  }
617  // Since some virtual registers may have had their def and uses eliminated,
618  // they are no longer referenced in the code, and so they will not appear
619  // in the map.
620 }
621 
622 void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
623  RegisterOrdering &RO) const {
624  // Create a vector of all virtual registers (collect them from the base
625  // ordering RB), and then sort it using the RegisterCell comparator.
626  BitValueOrdering BVO(RB);
627  RegisterCellLexCompare LexCmp(BVO, *CMS);
628 
629  using SortableVectorType = std::vector<unsigned>;
630 
631  SortableVectorType VRs;
632  for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I)
633  VRs.push_back(I->first);
634  llvm::sort(VRs, LexCmp);
635  // Transfer the results to the outgoing register ordering.
636  for (unsigned i = 0, n = VRs.size(); i < n; ++i)
637  RO.insert(std::make_pair(VRs[i], i));
638 }
639 
640 inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const {
641  return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass;
642 }
643 
644 bool HexagonGenInsert::isConstant(unsigned VR) const {
645  const BitTracker::RegisterCell &RC = CMS->lookup(VR);
646  uint16_t W = RC.width();
647  for (uint16_t i = 0; i < W; ++i) {
648  const BitTracker::BitValue &BV = RC[i];
649  if (BV.is(0) || BV.is(1))
650  continue;
651  return false;
652  }
653  return true;
654 }
655 
656 bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
657  const BitTracker::RegisterCell &RC = CMS->lookup(VR);
658  uint16_t W = RC.width();
659  if (W > 64)
660  return false;
661  uint64_t V = 0, B = 1;
662  for (uint16_t i = 0; i < W; ++i) {
663  const BitTracker::BitValue &BV = RC[i];
664  if (BV.is(1))
665  V |= B;
666  else if (!BV.is(0))
667  return false;
668  B <<= 1;
669  }
670 
671  // For 32-bit registers, consider: Rd = #s16.
672  if (W == 32)
673  return isInt<16>(V);
674 
675  // For 64-bit registers, it's Rdd = #s8 or Rdd = combine(#s8,#s8)
676  return isInt<8>(Lo_32(V)) && isInt<8>(Hi_32(V));
677 }
678 
679 bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
680  unsigned InsR, uint16_t L, uint16_t S) const {
681  const TargetRegisterClass *DstRC = MRI->getRegClass(DstR);
682  const TargetRegisterClass *SrcRC = MRI->getRegClass(SrcR);
683  const TargetRegisterClass *InsRC = MRI->getRegClass(InsR);
684  // Only integet (32-/64-bit) register classes.
685  if (!isIntClass(DstRC) || !isIntClass(SrcRC) || !isIntClass(InsRC))
686  return false;
687  // The "source" register must be of the same class as DstR.
688  if (DstRC != SrcRC)
689  return false;
690  if (DstRC == InsRC)
691  return true;
692  // A 64-bit register can only be generated from other 64-bit registers.
693  if (DstRC == &Hexagon::DoubleRegsRegClass)
694  return false;
695  // Otherwise, the L and S cannot span 32-bit word boundary.
696  if (S < 32 && S+L > 32)
697  return false;
698  return true;
699 }
700 
701 bool HexagonGenInsert::findSelfReference(unsigned VR) const {
702  const BitTracker::RegisterCell &RC = CMS->lookup(VR);
703  for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
704  const BitTracker::BitValue &V = RC[i];
705  if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == VR)
706  return true;
707  }
708  return false;
709 }
710 
711 bool HexagonGenInsert::findNonSelfReference(unsigned VR) const {
712  BitTracker::RegisterCell RC = CMS->lookup(VR);
713  for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
714  const BitTracker::BitValue &V = RC[i];
715  if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != VR)
716  return true;
717  }
718  return false;
719 }
720 
721 void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
722  RegisterSet &Defs) const {
723  for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
724  const MachineOperand &MO = MI->getOperand(i);
725  if (!MO.isReg() || !MO.isDef())
726  continue;
727  Register R = MO.getReg();
729  continue;
730  Defs.insert(R);
731  }
732 }
733 
734 void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
735  RegisterSet &Uses) const {
736  for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
737  const MachineOperand &MO = MI->getOperand(i);
738  if (!MO.isReg() || !MO.isUse())
739  continue;
740  Register R = MO.getReg();
742  continue;
743  Uses.insert(R);
744  }
745 }
746 
747 unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
748  const MachineBasicBlock *ToB, const UnsignedMap &RPO,
749  PairMapType &M) const {
750  // Forward distance from the end of a block to the beginning of it does
751  // not make sense. This function should not be called with FromB == ToB.
752  assert(FromB != ToB);
753 
754  unsigned FromN = FromB->getNumber(), ToN = ToB->getNumber();
755  // If we have already computed it, return the cached result.
756  PairMapType::iterator F = M.find(std::make_pair(FromN, ToN));
757  if (F != M.end())
758  return F->second;
759  unsigned ToRPO = RPO.lookup(ToN);
760 
761  unsigned MaxD = 0;
762 
764 
765  for (pred_iterator I = ToB->pred_begin(), E = ToB->pred_end(); I != E; ++I) {
766  const MachineBasicBlock *PB = *I;
767  // Skip back edges. Also, if FromB is a predecessor of ToB, the distance
768  // along that path will be 0, and we don't need to do any calculations
769  // on it.
770  if (PB == FromB || RPO.lookup(PB->getNumber()) >= ToRPO)
771  continue;
772  unsigned D = PB->size() + distance(FromB, PB, RPO, M);
773  if (D > MaxD)
774  MaxD = D;
775  }
776 
777  // Memoize the result for later lookup.
778  M.insert(std::make_pair(std::make_pair(FromN, ToN), MaxD));
779  return MaxD;
780 }
781 
782 unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
783  MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
784  PairMapType &M) const {
785  const MachineBasicBlock *FB = FromI->getParent(), *TB = ToI->getParent();
786  if (FB == TB)
787  return std::distance(FromI, ToI);
788  unsigned D1 = std::distance(TB->begin(), ToI);
789  unsigned D2 = distance(FB, TB, RPO, M);
790  unsigned D3 = std::distance(FromI, FB->end());
791  return D1+D2+D3;
792 }
793 
794 bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
795  OrderedRegisterList &AVs) {
796  if (isDebug()) {
797  dbgs() << __func__ << ": " << printReg(VR, HRI)
798  << " AVs: " << PrintORL(AVs, HRI) << "\n";
799  }
800  if (AVs.size() == 0)
801  return false;
802 
803  using iterator = OrderedRegisterList::iterator;
804 
805  BitValueOrdering BVO(BaseOrd);
806  const BitTracker::RegisterCell &RC = CMS->lookup(VR);
807  uint16_t W = RC.width();
808 
809  using RSRecord = std::pair<unsigned, uint16_t>; // (reg,shift)
810  using RSListType = std::vector<RSRecord>;
811  // Have a map, with key being the matching prefix length, and the value
812  // being the list of pairs (R,S), where R's prefix matches VR at S.
813  // (DenseMap<uint16_t,RSListType> fails to instantiate.)
814  using LRSMapType = DenseMap<unsigned, RSListType>;
815  LRSMapType LM;
816 
817  // Conceptually, rotate the cell RC right (i.e. towards the LSB) by S,
818  // and find matching prefixes from AVs with the rotated RC. Such a prefix
819  // would match a string of bits (of length L) in RC starting at S.
820  for (uint16_t S = 0; S < W; ++S) {
821  iterator B = AVs.begin(), E = AVs.end();
822  // The registers in AVs are ordered according to the lexical order of
823  // the corresponding register cells. This means that the range of regis-
824  // ters in AVs that match a prefix of length L+1 will be contained in
825  // the range that matches a prefix of length L. This means that we can
826  // keep narrowing the search space as the prefix length goes up. This
827  // helps reduce the overall complexity of the search.
828  uint16_t L;
829  for (L = 0; L < W-S; ++L) {
830  // Compare against VR's bits starting at S, which emulates rotation
831  // of VR by S.
832  RegisterCellBitCompareSel RCB(VR, S+L, L, BVO, *CMS);
833  iterator NewB = std::lower_bound(B, E, VR, RCB);
834  iterator NewE = std::upper_bound(NewB, E, VR, RCB);
835  // For the registers that are eliminated from the next range, L is
836  // the longest prefix matching VR at position S (their prefixes
837  // differ from VR at S+L). If L>0, record this information for later
838  // use.
839  if (L > 0) {
840  for (iterator I = B; I != NewB; ++I)
841  LM[L].push_back(std::make_pair(*I, S));
842  for (iterator I = NewE; I != E; ++I)
843  LM[L].push_back(std::make_pair(*I, S));
844  }
845  B = NewB, E = NewE;
846  if (B == E)
847  break;
848  }
849  // Record the final register range. If this range is non-empty, then
850  // L=W-S.
851  assert(B == E || L == W-S);
852  if (B != E) {
853  for (iterator I = B; I != E; ++I)
854  LM[L].push_back(std::make_pair(*I, S));
855  // If B!=E, then we found a range of registers whose prefixes cover the
856  // rest of VR from position S. There is no need to further advance S.
857  break;
858  }
859  }
860 
861  if (isDebug()) {
862  dbgs() << "Prefixes matching register " << printReg(VR, HRI) << "\n";
863  for (LRSMapType::iterator I = LM.begin(), E = LM.end(); I != E; ++I) {
864  dbgs() << " L=" << I->first << ':';
865  const RSListType &LL = I->second;
866  for (unsigned i = 0, n = LL.size(); i < n; ++i)
867  dbgs() << " (" << printReg(LL[i].first, HRI) << ",@"
868  << LL[i].second << ')';
869  dbgs() << '\n';
870  }
871  }
872 
873  bool Recorded = false;
874 
875  for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) {
876  unsigned SrcR = *I;
877  int FDi = -1, LDi = -1; // First/last different bit.
878  const BitTracker::RegisterCell &AC = CMS->lookup(SrcR);
879  uint16_t AW = AC.width();
880  for (uint16_t i = 0, w = std::min(W, AW); i < w; ++i) {
881  if (RC[i] == AC[i])
882  continue;
883  if (FDi == -1)
884  FDi = i;
885  LDi = i;
886  }
887  if (FDi == -1)
888  continue; // TODO (future): Record identical registers.
889  // Look for a register whose prefix could patch the range [FD..LD]
890  // where VR and SrcR differ.
891  uint16_t FD = FDi, LD = LDi; // Switch to unsigned type.
892  uint16_t MinL = LD-FD+1;
893  for (uint16_t L = MinL; L < W; ++L) {
894  LRSMapType::iterator F = LM.find(L);
895  if (F == LM.end())
896  continue;
897  RSListType &LL = F->second;
898  for (unsigned i = 0, n = LL.size(); i < n; ++i) {
899  uint16_t S = LL[i].second;
900  // MinL is the minimum length of the prefix. Any length above MinL
901  // allows some flexibility as to where the prefix can start:
902  // given the extra length EL=L-MinL, the prefix must start between
903  // max(0,FD-EL) and FD.
904  if (S > FD) // Starts too late.
905  continue;
906  uint16_t EL = L-MinL;
907  uint16_t LowS = (EL < FD) ? FD-EL : 0;
908  if (S < LowS) // Starts too early.
909  continue;
910  unsigned InsR = LL[i].first;
911  if (!isValidInsertForm(VR, SrcR, InsR, L, S))
912  continue;
913  if (isDebug()) {
914  dbgs() << printReg(VR, HRI) << " = insert(" << printReg(SrcR, HRI)
915  << ',' << printReg(InsR, HRI) << ",#" << L << ",#"
916  << S << ")\n";
917  }
918  IFRecordWithRegSet RR(IFRecord(SrcR, InsR, L, S), RegisterSet());
919  IFMap[VR].push_back(RR);
920  Recorded = true;
921  }
922  }
923  }
924 
925  return Recorded;
926 }
927 
928 void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
929  OrderedRegisterList &AVs) {
930  if (isDebug())
931  dbgs() << "visiting block " << printMBBReference(*B) << "\n";
932 
933  // First, check if this block is reachable at all. If not, the bit tracker
934  // will not have any information about registers in it.
935  if (!CMS->BT.reached(B))
936  return;
937 
938  bool DoConst = OptConst;
939  // Keep a separate set of registers defined in this block, so that we
940  // can remove them from the list of available registers once all DT
941  // successors have been processed.
942  RegisterSet BlockDefs, InsDefs;
943  for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
944  MachineInstr *MI = &*I;
945  InsDefs.clear();
946  getInstrDefs(MI, InsDefs);
947  // Leave those alone. They are more transparent than "insert".
948  bool Skip = MI->isCopy() || MI->isRegSequence();
949 
950  if (!Skip) {
951  // Visit all defined registers, and attempt to find the corresponding
952  // "insert" representations.
953  for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) {
954  // Do not collect registers that are known to be compile-time cons-
955  // tants, unless requested.
956  if (!DoConst && isConstant(VR))
957  continue;
958  // If VR's cell contains a reference to VR, then VR cannot be defined
959  // via "insert". If VR is a constant that can be generated in a single
960  // instruction (without constant extenders), generating it via insert
961  // makes no sense.
962  if (findSelfReference(VR) || isSmallConstant(VR))
963  continue;
964 
965  findRecordInsertForms(VR, AVs);
966  // Stop if the map size is too large.
967  if (IFMap.size() > MaxIFMSize)
968  return;
969  }
970  }
971 
972  // Insert the defined registers into the list of available registers
973  // after they have been processed.
974  for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR))
975  AVs.insert(VR);
976  BlockDefs.insert(InsDefs);
977  }
978 
979  for (auto *DTN : children<MachineDomTreeNode*>(MDT->getNode(B))) {
980  MachineBasicBlock *SB = DTN->getBlock();
981  collectInBlock(SB, AVs);
982  }
983 
984  for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR))
985  AVs.remove(VR);
986 }
987 
988 void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
989  RegisterSet &RMs) const {
990  // For a given register VR and a insert form, find the registers that are
991  // used by the current definition of VR, and which would no longer be
992  // needed for it after the definition of VR is replaced with the insert
993  // form. These are the registers that could potentially become dead.
994  RegisterSet Regs[2];
995 
996  unsigned S = 0; // Register set selector.
997  Regs[S].insert(VR);
998 
999  while (!Regs[S].empty()) {
1000  // Breadth-first search.
1001  unsigned OtherS = 1-S;
1002  Regs[OtherS].clear();
1003  for (unsigned R = Regs[S].find_first(); R; R = Regs[S].find_next(R)) {
1004  Regs[S].remove(R);
1005  if (R == IF.SrcR || R == IF.InsR)
1006  continue;
1007  // Check if a given register has bits that are references to any other
1008  // registers. This is to detect situations where the instruction that
1009  // defines register R takes register Q as an operand, but R itself does
1010  // not contain any bits from Q. Loads are examples of how this could
1011  // happen:
1012  // R = load Q
1013  // In this case (assuming we do not have any knowledge about the loaded
1014  // value), we must not treat R as a "conveyance" of the bits from Q.
1015  // (The information in BT about R's bits would have them as constants,
1016  // in case of zero-extending loads, or refs to R.)
1017  if (!findNonSelfReference(R))
1018  continue;
1019  RMs.insert(R);
1020  const MachineInstr *DefI = MRI->getVRegDef(R);
1021  assert(DefI);
1022  // Do not iterate past PHI nodes to avoid infinite loops. This can
1023  // make the final set a bit less accurate, but the removable register
1024  // sets are an approximation anyway.
1025  if (DefI->isPHI())
1026  continue;
1027  getInstrUses(DefI, Regs[OtherS]);
1028  }
1029  S = OtherS;
1030  }
1031  // The register VR is added to the list as a side-effect of the algorithm,
1032  // but it is not "potentially removable". A potentially removable register
1033  // is one that may become unused (dead) after conversion to the insert form
1034  // IF, and obviously VR (or its replacement) will not become dead by apply-
1035  // ing IF.
1036  RMs.remove(VR);
1037 }
1038 
1039 void HexagonGenInsert::computeRemovableRegisters() {
1040  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1041  IFListType &LL = I->second;
1042  for (unsigned i = 0, n = LL.size(); i < n; ++i)
1043  findRemovableRegisters(I->first, LL[i].first, LL[i].second);
1044  }
1045 }
1046 
1047 void HexagonGenInsert::pruneEmptyLists() {
1048  // Remove all entries from the map, where the register has no insert forms
1049  // associated with it.
1050  using IterListType = SmallVector<IFMapType::iterator, 16>;
1051  IterListType Prune;
1052  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1053  if (I->second.empty())
1054  Prune.push_back(I);
1055  }
1056  for (unsigned i = 0, n = Prune.size(); i < n; ++i)
1057  IFMap.erase(Prune[i]);
1058 }
1059 
1060 void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
1061  IFMapType::iterator F = IFMap.find(VR);
1062  assert(F != IFMap.end());
1063  IFListType &LL = F->second;
1064 
1065  // First, examine the IF candidates for register VR whose removable-regis-
1066  // ter sets are empty. This means that a given candidate will not help eli-
1067  // minate any registers, but since "insert" is not a constant-extendable
1068  // instruction, using such a candidate may reduce code size if the defini-
1069  // tion of VR is constant-extended.
1070  // If there exists a candidate with a non-empty set, the ones with empty
1071  // sets will not be used and can be removed.
1072  MachineInstr *DefVR = MRI->getVRegDef(VR);
1073  bool DefEx = HII->isConstExtended(*DefVR);
1074  bool HasNE = false;
1075  for (unsigned i = 0, n = LL.size(); i < n; ++i) {
1076  if (LL[i].second.empty())
1077  continue;
1078  HasNE = true;
1079  break;
1080  }
1081  if (!DefEx || HasNE) {
1082  // The definition of VR is not constant-extended, or there is a candidate
1083  // with a non-empty set. Remove all candidates with empty sets.
1084  auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool {
1085  return IR.second.empty();
1086  };
1087  auto End = llvm::remove_if(LL, IsEmpty);
1088  if (End != LL.end())
1089  LL.erase(End, LL.end());
1090  } else {
1091  // The definition of VR is constant-extended, and all candidates have
1092  // empty removable-register sets. Pick the maximum candidate, and remove
1093  // all others. The "maximum" does not have any special meaning here, it
1094  // is only so that the candidate that will remain on the list is selec-
1095  // ted deterministically.
1096  IFRecord MaxIF = LL[0].first;
1097  for (unsigned i = 1, n = LL.size(); i < n; ++i) {
1098  // If LL[MaxI] < LL[i], then MaxI = i.
1099  const IFRecord &IF = LL[i].first;
1100  unsigned M0 = BaseOrd[MaxIF.SrcR], M1 = BaseOrd[MaxIF.InsR];
1101  unsigned R0 = BaseOrd[IF.SrcR], R1 = BaseOrd[IF.InsR];
1102  if (M0 > R0)
1103  continue;
1104  if (M0 == R0) {
1105  if (M1 > R1)
1106  continue;
1107  if (M1 == R1) {
1108  if (MaxIF.Wdh > IF.Wdh)
1109  continue;
1110  if (MaxIF.Wdh == IF.Wdh && MaxIF.Off >= IF.Off)
1111  continue;
1112  }
1113  }
1114  // MaxIF < IF.
1115  MaxIF = IF;
1116  }
1117  // Remove everything except the maximum candidate. All register sets
1118  // are empty, so no need to preserve anything.
1119  LL.clear();
1120  LL.push_back(std::make_pair(MaxIF, RegisterSet()));
1121  }
1122 
1123  // Now, remove those whose sets of potentially removable registers are
1124  // contained in another IF candidate for VR. For example, given these
1125  // candidates for %45,
1126  // %45:
1127  // (%44,%41,#9,#8), { %42 }
1128  // (%43,%41,#9,#8), { %42 %44 }
1129  // remove the first one, since it is contained in the second one.
1130  for (unsigned i = 0, n = LL.size(); i < n; ) {
1131  const RegisterSet &RMi = LL[i].second;
1132  unsigned j = 0;
1133  while (j < n) {
1134  if (j != i && LL[j].second.includes(RMi))
1135  break;
1136  j++;
1137  }
1138  if (j == n) { // RMi not contained in anything else.
1139  i++;
1140  continue;
1141  }
1142  LL.erase(LL.begin()+i);
1143  n = LL.size();
1144  }
1145 }
1146 
1147 void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
1148  PairMapType &M) {
1149  IFMapType::iterator F = IFMap.find(VR);
1150  assert(F != IFMap.end());
1151  IFListType &LL = F->second;
1152  unsigned Cutoff = VRegDistCutoff;
1153  const MachineInstr *DefV = MRI->getVRegDef(VR);
1154 
1155  for (unsigned i = LL.size(); i > 0; --i) {
1156  unsigned SR = LL[i-1].first.SrcR, IR = LL[i-1].first.InsR;
1157  const MachineInstr *DefS = MRI->getVRegDef(SR);
1158  const MachineInstr *DefI = MRI->getVRegDef(IR);
1159  unsigned DSV = distance(DefS, DefV, RPO, M);
1160  if (DSV < Cutoff) {
1161  unsigned DIV = distance(DefI, DefV, RPO, M);
1162  if (DIV < Cutoff)
1163  continue;
1164  }
1165  LL.erase(LL.begin()+(i-1));
1166  }
1167 }
1168 
1169 void HexagonGenInsert::pruneRegCopies(unsigned VR) {
1170  IFMapType::iterator F = IFMap.find(VR);
1171  assert(F != IFMap.end());
1172  IFListType &LL = F->second;
1173 
1174  auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool {
1175  return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32);
1176  };
1177  auto End = llvm::remove_if(LL, IsCopy);
1178  if (End != LL.end())
1179  LL.erase(End, LL.end());
1180 }
1181 
1182 void HexagonGenInsert::pruneCandidates() {
1183  // Remove candidates that are not beneficial, regardless of the final
1184  // selection method.
1185  // First, remove candidates whose potentially removable set is a subset
1186  // of another candidate's set.
1187  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1188  pruneCoveredSets(I->first);
1189 
1190  UnsignedMap RPO;
1191 
1193 
1194  RPOTType RPOT(MFN);
1195  unsigned RPON = 0;
1196  for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
1197  RPO[(*I)->getNumber()] = RPON++;
1198 
1199  PairMapType Memo; // Memoization map for distance calculation.
1200  // Remove candidates that would use registers defined too far away.
1201  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1202  pruneUsesTooFar(I->first, RPO, Memo);
1203 
1204  pruneEmptyLists();
1205 
1206  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1207  pruneRegCopies(I->first);
1208 }
1209 
1210 namespace {
1211 
1212  // Class for comparing IF candidates for registers that have multiple of
1213  // them. The smaller the candidate, according to this ordering, the better.
1214  // First, compare the number of zeros in the associated potentially remova-
1215  // ble register sets. "Zero" indicates that the register is very likely to
1216  // become dead after this transformation.
1217  // Second, compare "averages", i.e. use-count per size. The lower wins.
1218  // After that, it does not really matter which one is smaller. Resolve
1219  // the tie in some deterministic way.
1220  struct IFOrdering {
1221  IFOrdering(const UnsignedMap &UC, const RegisterOrdering &BO)
1222  : UseC(UC), BaseOrd(BO) {}
1223 
1224  bool operator() (const IFRecordWithRegSet &A,
1225  const IFRecordWithRegSet &B) const;
1226 
1227  private:
1228  void stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1229  unsigned &Sum) const;
1230 
1231  const UnsignedMap &UseC;
1232  const RegisterOrdering &BaseOrd;
1233  };
1234 
1235 } // end anonymous namespace
1236 
1237 bool IFOrdering::operator() (const IFRecordWithRegSet &A,
1238  const IFRecordWithRegSet &B) const {
1239  unsigned SizeA = 0, ZeroA = 0, SumA = 0;
1240  unsigned SizeB = 0, ZeroB = 0, SumB = 0;
1241  stats(A.second, SizeA, ZeroA, SumA);
1242  stats(B.second, SizeB, ZeroB, SumB);
1243 
1244  // We will pick the minimum element. The more zeros, the better.
1245  if (ZeroA != ZeroB)
1246  return ZeroA > ZeroB;
1247  // Compare SumA/SizeA with SumB/SizeB, lower is better.
1248  uint64_t AvgA = SumA*SizeB, AvgB = SumB*SizeA;
1249  if (AvgA != AvgB)
1250  return AvgA < AvgB;
1251 
1252  // The sets compare identical so far. Resort to comparing the IF records.
1253  // The actual values don't matter, this is only for determinism.
1254  unsigned OSA = BaseOrd[A.first.SrcR], OSB = BaseOrd[B.first.SrcR];
1255  if (OSA != OSB)
1256  return OSA < OSB;
1257  unsigned OIA = BaseOrd[A.first.InsR], OIB = BaseOrd[B.first.InsR];
1258  if (OIA != OIB)
1259  return OIA < OIB;
1260  if (A.first.Wdh != B.first.Wdh)
1261  return A.first.Wdh < B.first.Wdh;
1262  return A.first.Off < B.first.Off;
1263 }
1264 
1265 void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1266  unsigned &Sum) const {
1267  for (unsigned R = Rs.find_first(); R; R = Rs.find_next(R)) {
1268  UnsignedMap::const_iterator F = UseC.find(R);
1269  assert(F != UseC.end());
1270  unsigned UC = F->second;
1271  if (UC == 0)
1272  Zero++;
1273  Sum += UC;
1274  Size++;
1275  }
1276 }
1277 
1278 void HexagonGenInsert::selectCandidates() {
1279  // Some registers may have multiple valid candidates. Pick the best one
1280  // (or decide not to use any).
1281 
1282  // Compute the "removability" measure of R:
1283  // For each potentially removable register R, record the number of regis-
1284  // ters with IF candidates, where R appears in at least one set.
1285  RegisterSet AllRMs;
1286  UnsignedMap UseC, RemC;
1287  IFMapType::iterator End = IFMap.end();
1288 
1289  for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1290  const IFListType &LL = I->second;
1291  RegisterSet TT;
1292  for (unsigned i = 0, n = LL.size(); i < n; ++i)
1293  TT.insert(LL[i].second);
1294  for (unsigned R = TT.find_first(); R; R = TT.find_next(R))
1295  RemC[R]++;
1296  AllRMs.insert(TT);
1297  }
1298 
1299  for (unsigned R = AllRMs.find_first(); R; R = AllRMs.find_next(R)) {
1300  using use_iterator = MachineRegisterInfo::use_nodbg_iterator;
1301  using InstrSet = SmallSet<const MachineInstr *, 16>;
1302 
1303  InstrSet UIs;
1304  // Count as the number of instructions in which R is used, not the
1305  // number of operands.
1306  use_iterator E = MRI->use_nodbg_end();
1307  for (use_iterator I = MRI->use_nodbg_begin(R); I != E; ++I)
1308  UIs.insert(I->getParent());
1309  unsigned C = UIs.size();
1310  // Calculate a measure, which is the number of instructions using R,
1311  // minus the "removability" count computed earlier.
1312  unsigned D = RemC[R];
1313  UseC[R] = (C > D) ? C-D : 0; // doz
1314  }
1315 
1316  bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0;
1317  if (!SelectAll0 && !SelectHas0)
1318  SelectAll0 = true;
1319 
1320  // The smaller the number UseC for a given register R, the "less used"
1321  // R is aside from the opportunities for removal offered by generating
1322  // "insert" instructions.
1323  // Iterate over the IF map, and for those registers that have multiple
1324  // candidates, pick the minimum one according to IFOrdering.
1325  IFOrdering IFO(UseC, BaseOrd);
1326  for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1327  IFListType &LL = I->second;
1328  if (LL.empty())
1329  continue;
1330  // Get the minimum element, remember it and clear the list. If the
1331  // element found is adequate, we will put it back on the list, other-
1332  // wise the list will remain empty, and the entry for this register
1333  // will be removed (i.e. this register will not be replaced by insert).
1334  IFListType::iterator MinI = std::min_element(LL.begin(), LL.end(), IFO);
1335  assert(MinI != LL.end());
1336  IFRecordWithRegSet M = *MinI;
1337  LL.clear();
1338 
1339  // We want to make sure that this replacement will have a chance to be
1340  // beneficial, and that means that we want to have indication that some
1341  // register will be removed. The most likely registers to be eliminated
1342  // are the use operands in the definition of I->first. Accept/reject a
1343  // candidate based on how many of its uses it can potentially eliminate.
1344 
1345  RegisterSet Us;
1346  const MachineInstr *DefI = MRI->getVRegDef(I->first);
1347  getInstrUses(DefI, Us);
1348  bool Accept = false;
1349 
1350  if (SelectAll0) {
1351  bool All0 = true;
1352  for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1353  if (UseC[R] == 0)
1354  continue;
1355  All0 = false;
1356  break;
1357  }
1358  Accept = All0;
1359  } else if (SelectHas0) {
1360  bool Has0 = false;
1361  for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1362  if (UseC[R] != 0)
1363  continue;
1364  Has0 = true;
1365  break;
1366  }
1367  Accept = Has0;
1368  }
1369  if (Accept)
1370  LL.push_back(M);
1371  }
1372 
1373  // Remove candidates that add uses of removable registers, unless the
1374  // removable registers are among replacement candidates.
1375  // Recompute the removable registers, since some candidates may have
1376  // been eliminated.
1377  AllRMs.clear();
1378  for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1379  const IFListType &LL = I->second;
1380  if (!LL.empty())
1381  AllRMs.insert(LL[0].second);
1382  }
1383  for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1384  IFListType &LL = I->second;
1385  if (LL.empty())
1386  continue;
1387  unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR;
1388  if (AllRMs[SR] || AllRMs[IR])
1389  LL.clear();
1390  }
1391 
1392  pruneEmptyLists();
1393 }
1394 
1395 bool HexagonGenInsert::generateInserts() {
1396  // Create a new register for each one from IFMap, and store them in the
1397  // map.
1398  UnsignedMap RegMap;
1399  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1400  unsigned VR = I->first;
1401  const TargetRegisterClass *RC = MRI->getRegClass(VR);
1402  Register NewVR = MRI->createVirtualRegister(RC);
1403  RegMap[VR] = NewVR;
1404  }
1405 
1406  // We can generate the "insert" instructions using potentially stale re-
1407  // gisters: SrcR and InsR for a given VR may be among other registers that
1408  // are also replaced. This is fine, we will do the mass "rauw" a bit later.
1409  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1410  MachineInstr *MI = MRI->getVRegDef(I->first);
1411  MachineBasicBlock &B = *MI->getParent();
1412  DebugLoc DL = MI->getDebugLoc();
1413  unsigned NewR = RegMap[I->first];
1414  bool R32 = MRI->getRegClass(NewR) == &Hexagon::IntRegsRegClass;
1415  const MCInstrDesc &D = R32 ? HII->get(Hexagon::S2_insert)
1416  : HII->get(Hexagon::S2_insertp);
1417  IFRecord IF = I->second[0].first;
1418  unsigned Wdh = IF.Wdh, Off = IF.Off;
1419  unsigned InsS = 0;
1420  if (R32 && MRI->getRegClass(IF.InsR) == &Hexagon::DoubleRegsRegClass) {
1421  InsS = Hexagon::isub_lo;
1422  if (Off >= 32) {
1423  InsS = Hexagon::isub_hi;
1424  Off -= 32;
1425  }
1426  }
1427  // Advance to the proper location for inserting instructions. This could
1428  // be B.end().
1430  if (MI->isPHI())
1431  At = B.getFirstNonPHI();
1432 
1433  BuildMI(B, At, DL, D, NewR)
1434  .addReg(IF.SrcR)
1435  .addReg(IF.InsR, 0, InsS)
1436  .addImm(Wdh)
1437  .addImm(Off);
1438 
1439  MRI->clearKillFlags(IF.SrcR);
1440  MRI->clearKillFlags(IF.InsR);
1441  }
1442 
1443  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1444  MachineInstr *DefI = MRI->getVRegDef(I->first);
1445  MRI->replaceRegWith(I->first, RegMap[I->first]);
1446  DefI->eraseFromParent();
1447  }
1448 
1449  return true;
1450 }
1451 
1452 bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
1453  bool Changed = false;
1454 
1455  for (auto *DTN : children<MachineDomTreeNode*>(N))
1456  Changed |= removeDeadCode(DTN);
1457 
1458  MachineBasicBlock *B = N->getBlock();
1459  std::vector<MachineInstr*> Instrs;
1460  for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
1461  Instrs.push_back(&*I);
1462 
1463  for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) {
1464  MachineInstr *MI = *I;
1465  unsigned Opc = MI->getOpcode();
1466  // Do not touch lifetime markers. This is why the target-independent DCE
1467  // cannot be used.
1468  if (Opc == TargetOpcode::LIFETIME_START ||
1470  continue;
1471  bool Store = false;
1472  if (MI->isInlineAsm() || !MI->isSafeToMove(nullptr, Store))
1473  continue;
1474 
1475  bool AllDead = true;
1477  for (const MachineOperand &MO : MI->operands()) {
1478  if (!MO.isReg() || !MO.isDef())
1479  continue;
1480  Register R = MO.getReg();
1481  if (!Register::isVirtualRegister(R) || !MRI->use_nodbg_empty(R)) {
1482  AllDead = false;
1483  break;
1484  }
1485  Regs.push_back(R);
1486  }
1487  if (!AllDead)
1488  continue;
1489 
1490  B->erase(MI);
1491  for (unsigned I = 0, N = Regs.size(); I != N; ++I)
1492  MRI->markUsesInDebugValueAsUndef(Regs[I]);
1493  Changed = true;
1494  }
1495 
1496  return Changed;
1497 }
1498 
1499 bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
1500  if (skipFunction(MF.getFunction()))
1501  return false;
1502 
1503  bool Timing = OptTiming, TimingDetail = Timing && OptTimingDetail;
1504  bool Changed = false;
1505 
1506  // Sanity check: one, but not both.
1508 
1509  IFMap.clear();
1510  BaseOrd.clear();
1511  CellOrd.clear();
1512 
1513  const auto &ST = MF.getSubtarget<HexagonSubtarget>();
1514  HII = ST.getInstrInfo();
1515  HRI = ST.getRegisterInfo();
1516  MFN = &MF;
1517  MRI = &MF.getRegInfo();
1518  MDT = &getAnalysis<MachineDominatorTree>();
1519 
1520  // Clean up before any further processing, so that dead code does not
1521  // get used in a newly generated "insert" instruction. Have a custom
1522  // version of DCE that preserves lifetime markers. Without it, merging
1523  // of stack objects can fail to recognize and merge disjoint objects
1524  // leading to unnecessary stack growth.
1525  Changed = removeDeadCode(MDT->getRootNode());
1526 
1527  const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
1528  BitTracker BTLoc(HE, MF);
1529  BTLoc.trace(isDebug());
1530  BTLoc.run();
1531  CellMapShadow MS(BTLoc);
1532  CMS = &MS;
1533 
1534  buildOrderingMF(BaseOrd);
1535  buildOrderingBT(BaseOrd, CellOrd);
1536 
1537  if (isDebug()) {
1538  dbgs() << "Cell ordering:\n";
1539  for (RegisterOrdering::iterator I = CellOrd.begin(), E = CellOrd.end();
1540  I != E; ++I) {
1541  unsigned VR = I->first, Pos = I->second;
1542  dbgs() << printReg(VR, HRI) << " -> " << Pos << "\n";
1543  }
1544  }
1545 
1546  // Collect candidates for conversion into the insert forms.
1547  MachineBasicBlock *RootB = MDT->getRoot();
1548  OrderedRegisterList AvailR(CellOrd);
1549 
1550  const char *const TGName = "hexinsert";
1551  const char *const TGDesc = "Generate Insert Instructions";
1552 
1553  {
1554  NamedRegionTimer _T("collection", "collection", TGName, TGDesc,
1555  TimingDetail);
1556  collectInBlock(RootB, AvailR);
1557  // Complete the information gathered in IFMap.
1558  computeRemovableRegisters();
1559  }
1560 
1561  if (isDebug()) {
1562  dbgs() << "Candidates after collection:\n";
1563  dump_map();
1564  }
1565 
1566  if (IFMap.empty())
1567  return Changed;
1568 
1569  {
1570  NamedRegionTimer _T("pruning", "pruning", TGName, TGDesc, TimingDetail);
1571  pruneCandidates();
1572  }
1573 
1574  if (isDebug()) {
1575  dbgs() << "Candidates after pruning:\n";
1576  dump_map();
1577  }
1578 
1579  if (IFMap.empty())
1580  return Changed;
1581 
1582  {
1583  NamedRegionTimer _T("selection", "selection", TGName, TGDesc, TimingDetail);
1584  selectCandidates();
1585  }
1586 
1587  if (isDebug()) {
1588  dbgs() << "Candidates after selection:\n";
1589  dump_map();
1590  }
1591 
1592  // Filter out vregs beyond the cutoff.
1593  if (VRegIndexCutoff.getPosition()) {
1594  unsigned Cutoff = VRegIndexCutoff;
1595 
1596  using IterListType = SmallVector<IFMapType::iterator, 16>;
1597 
1598  IterListType Out;
1599  for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1600  unsigned Idx = Register::virtReg2Index(I->first);
1601  if (Idx >= Cutoff)
1602  Out.push_back(I);
1603  }
1604  for (unsigned i = 0, n = Out.size(); i < n; ++i)
1605  IFMap.erase(Out[i]);
1606  }
1607  if (IFMap.empty())
1608  return Changed;
1609 
1610  {
1611  NamedRegionTimer _T("generation", "generation", TGName, TGDesc,
1612  TimingDetail);
1613  generateInserts();
1614  }
1615 
1616  return true;
1617 }
1618 
1620  return new HexagonGenInsert();
1621 }
1622 
1623 //===----------------------------------------------------------------------===//
1624 // Public Constructor Functions
1625 //===----------------------------------------------------------------------===//
1626 
1627 INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert",
1628  "Hexagon generate \"insert\" instructions", false, false)
1630 INITIALIZE_PASS_END(HexagonGenInsert, "hexinsert",
1631  "Hexagon generate \"insert\" instructions", false, false)
auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1261
static cl::opt< bool > OptSelectHas0("insert-has0", cl::init(false), cl::Hidden, cl::ZeroOrMore)
uint64_t CallInst * C
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
BitVector & set()
Definition: BitVector.h:397
static bool isConstant(const MachineInstr &MI)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:76
void initializeHexagonGenInsertPass(PassRegistry &)
void trace(bool On=false)
Definition: BitTracker.h:50
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool isDebug()
static cl::opt< unsigned > VRegDistCutoff("insert-dist-cutoff", cl::init(30U), cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg distance cutoff for insert " "generation."))
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
Definition: MathExtras.h:288
void push_back(const T &Elt)
Definition: SmallVector.h:211
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
unsigned getSubReg() const
bool isInlineAsm() const
bool test(unsigned Idx) const
Definition: BitVector.h:501
bool isRegSequence() const
constexpr bool isInt< 8 >(int64_t x)
Definition: MathExtras.h:302
unsigned second
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:305
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
F(f)
MachineInstrBundleIterator< const MachineInstr > const_iterator
INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert", "Hexagon generate \nsert\instructions", false, false) INITIALIZE_PASS_END(HexagonGenInsert
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
std::vector< MachineBasicBlock * >::const_iterator const_pred_iterator
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:477
bool isPHI() const
BasicBlockListType::const_iterator const_iterator
static cl::opt< bool > OptTiming("insert-timing", cl::init(false), cl::Hidden, cl::ZeroOrMore, cl::desc("Enable timing of insert generation"))
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
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:331
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:160
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:339
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
static const uint16_t * lookup(unsigned opcode, unsigned domain, ArrayRef< uint16_t[3]> Table)
zlib style complession
defusechain_iterator< true, false, true, true, false, false > use_nodbg_iterator
use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the specified register...
BitVector & operator|=(const BitVector &RHS)
Definition: BitVector.h:602
static cl::opt< unsigned > MaxORLSize("insert-max-orl", cl::init(4096), cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of OrderedRegisterList"))
Base class for the actual dominator tree node.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
SmallSet< unsigned, 4 > RegisterSet
reverse_iterator rend()
reverse_iterator rbegin()
This corresponds to the llvm.lifetime.
Definition: ISDOpcodes.h:877
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
NodeT * getBlock() const
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:523
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const RegisterCell & lookup(unsigned Reg) const
Definition: BitTracker.h:356
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
bool any() const
any - Returns true if any bit is set.
Definition: BitVector.h:180
Represent the analysis usage information of a pass.
BitVector & reset()
Definition: BitVector.h:438
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
bool isCopy() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:52
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned first
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
static cl::opt< unsigned > MaxIFMSize("insert-max-ifmap", cl::init(1024), cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of IFMap"))
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
reference operator[](unsigned Idx)
Definition: BitVector.h:490
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool is(unsigned T) const
Definition: BitTracker.h:208
FunctionPass * createHexagonGenInsert()
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
block placement stats
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
BitTracker BT
Definition: BitTracker.cpp:73
static cl::opt< bool > OptConst("insert-const", cl::init(false), cl::Hidden, cl::ZeroOrMore)
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
uint32_t Size
Definition: Profile.cpp:46
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
static cl::opt< unsigned > VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U), cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg# cutoff for insert generation."))
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
Definition: MathExtras.h:283
#define DEBUG_TYPE
rpo Deduce function attributes in RPO
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
static cl::opt< bool > OptTimingDetail("insert-timing-detail", cl::init(false), cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert " "generation"))
static cl::opt< bool > OptSelectAll0("insert-all0", cl::init(false), cl::Hidden, cl::ZeroOrMore)
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
Statically lint checks LLVM IR
Definition: Lint.cpp:192
bool DebugFlag
This boolean is set to true if the &#39;-debug&#39; command line option is specified.
Definition: Debug.cpp:43
bool isCurrentDebugType(const char *Type)
isCurrentDebugType - Return true if the specified string is the debug type specified on the command l...
Definition: Debug.cpp:50
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1276