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