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