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