contrib/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp

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