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