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