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