lib/Target/Hexagon/HexagonGenInsert.cpp

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