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