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