LLVM  7.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.begin(), VRs.end(), 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
void push_back(const T &Elt)
Definition: SmallVector.h:213
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
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:241
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
static bool isDebug()
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
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:281
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:285
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:161
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
Definition: MachineInstr.h:867
bool test(unsigned Idx) const
Definition: BitVector.h:502
bool isRegSequence() const
Definition: MachineInstr.h:884
constexpr bool isInt< 8 >(int64_t x)
Definition: MathExtras.h:295
unsigned second
constexpr bool isInt< 16 >(int64_t x)
Definition: MathExtras.h:298
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:361
bool isPHI() const
Definition: MachineInstr.h:861
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
Access to explicit operands of the instruction.
Definition: MachineInstr.h:314
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:311
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:241
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:586
const RegList & Regs
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:1004
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:796
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:410
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:507
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:36
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
static const unsigned End
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:948
bool isCopy() const
Definition: MachineInstr.h:892
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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:929
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:859
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:1032
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:861
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:156
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:60
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
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:2023
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:276
#define DEBUG_TYPE
rpo Deduce function attributes in RPO
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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:316
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