contrib/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp

   1 //===- llvm/CodeGen/GlobalISel/RegisterBankInfo.cpp --------------*- C++ -*-==//
   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 /// \file
  10 /// This file implements the RegisterBankInfo class.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
  14 #include "llvm/ADT/SmallString.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/ADT/iterator_range.h"
  18 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/IR/Type.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Target/TargetOpcodes.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetSubtargetInfo.h"
  29
  30 #include <algorithm> // For std::max.
  31
  32 #define DEBUG_TYPE "registerbankinfo"
  33
  34 using namespace llvm;
  35
  36 STATISTIC(NumPartialMappingsCreated,
  37           "Number of partial mappings dynamically created");
  38 STATISTIC(NumPartialMappingsAccessed,
  39           "Number of partial mappings dynamically accessed");
  40 STATISTIC(NumValueMappingsCreated,
  41           "Number of value mappings dynamically created");
  42 STATISTIC(NumValueMappingsAccessed,
  43           "Number of value mappings dynamically accessed");
  44 STATISTIC(NumOperandsMappingsCreated,
  45           "Number of operands mappings dynamically created");
  46 STATISTIC(NumOperandsMappingsAccessed,
  47           "Number of operands mappings dynamically accessed");
  48
  49 const unsigned RegisterBankInfo::DefaultMappingID = UINT_MAX;
  50 const unsigned RegisterBankInfo::InvalidMappingID = UINT_MAX - 1;
  51
  52 //------------------------------------------------------------------------------
  53 // RegisterBankInfo implementation.
  54 //------------------------------------------------------------------------------
  55 RegisterBankInfo::RegisterBankInfo(RegisterBank **RegBanks,
  56                                    unsigned NumRegBanks)
  57     : RegBanks(RegBanks), NumRegBanks(NumRegBanks) {
  58   DEBUG(for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) {
  59     assert(RegBanks[Idx] != nullptr && "Invalid RegisterBank");
  60     assert(!RegBanks[Idx]->isValid() &&
  61            "RegisterBank should be invalid before initialization");
  62   });
  63 }
  64
  65 RegisterBankInfo::~RegisterBankInfo() {
  66   for (auto It : MapOfPartialMappings)
  67     delete It.second;
  68   for (auto It : MapOfValueMappings)
  69     delete It.second;
  70 }
  71
  72 bool RegisterBankInfo::verify(const TargetRegisterInfo &TRI) const {
  73   DEBUG(for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) {
  74     const RegisterBank &RegBank = getRegBank(Idx);
  75     assert(Idx == RegBank.getID() &&
  76            "ID does not match the index in the array");
  77     dbgs() << "Verify " << RegBank << '\n';
  78     assert(RegBank.verify(TRI) && "RegBank is invalid");
  79   });
  80   return true;
  81 }
  82
  83 void RegisterBankInfo::createRegisterBank(unsigned ID, const char *Name) {
  84   DEBUG(dbgs() << "Create register bank: " << ID << " with name \"" << Name
  85                << "\"\n");
  86   RegisterBank &RegBank = getRegBank(ID);
  87   assert(RegBank.getID() == RegisterBank::InvalidID &&
  88          "A register bank should be created only once");
  89   RegBank.ID = ID;
  90   RegBank.Name = Name;
  91 }
  92
  93 void RegisterBankInfo::addRegBankCoverage(unsigned ID, unsigned RCId,
  94                                           const TargetRegisterInfo &TRI) {
  95   RegisterBank &RB = getRegBank(ID);
  96   unsigned NbOfRegClasses = TRI.getNumRegClasses();
  97
  98   DEBUG(dbgs() << "Add coverage for: " << RB << '\n');
  99
 100   // Check if RB is underconstruction.
 101   if (!RB.isValid())
 102     RB.ContainedRegClasses.resize(NbOfRegClasses);
 103   else if (RB.covers(*TRI.getRegClass(RCId)))
 104     // If RB already covers this register class, there is nothing
 105     // to do.
 106     return;
 107
 108   BitVector &Covered = RB.ContainedRegClasses;
 109   SmallVector<unsigned, 8> WorkList;
 110
 111   WorkList.push_back(RCId);
 112   Covered.set(RCId);
 113
 114   unsigned &MaxSize = RB.Size;
 115   do {
 116     unsigned RCId = WorkList.pop_back_val();
 117
 118     const TargetRegisterClass &CurRC = *TRI.getRegClass(RCId);
 119
 120     DEBUG(dbgs() << "Examine: " << TRI.getRegClassName(&CurRC)
 121                  << "(Size*8: " << (CurRC.getSize() * 8) << ")\n");
 122
 123     // Remember the biggest size in bits.
 124     MaxSize = std::max(MaxSize, CurRC.getSize() * 8);
 125
 126     // Walk through all sub register classes and push them into the worklist.
 127     bool First = true;
 128     for (BitMaskClassIterator It(CurRC.getSubClassMask(), TRI); It.isValid();
 129          ++It) {
 130       unsigned SubRCId = It.getID();
 131       if (!Covered.test(SubRCId)) {
 132         if (First)
 133           DEBUG(dbgs() << "  Enqueue sub-class: ");
 134         DEBUG(dbgs() << TRI.getRegClassName(TRI.getRegClass(SubRCId)) << ", ");
 135         WorkList.push_back(SubRCId);
 136         // Remember that we saw the sub class.
 137         Covered.set(SubRCId);
 138         First = false;
 139       }
 140     }
 141     if (!First)
 142       DEBUG(dbgs() << '\n');
 143
 144     // Push also all the register classes that can be accessed via a
 145     // subreg index, i.e., its subreg-class (which is different than
 146     // its subclass).
 147     //
 148     // Note: It would probably be faster to go the other way around
 149     // and have this method add only super classes, since this
 150     // information is available in a more efficient way. However, it
 151     // feels less natural for the client of this APIs plus we will
 152     // TableGen the whole bitset at some point, so compile time for
 153     // the initialization is not very important.
 154     First = true;
 155     for (unsigned SubRCId = 0; SubRCId < NbOfRegClasses; ++SubRCId) {
 156       if (Covered.test(SubRCId))
 157         continue;
 158       bool Pushed = false;
 159       const TargetRegisterClass *SubRC = TRI.getRegClass(SubRCId);
 160       for (SuperRegClassIterator SuperRCIt(SubRC, &TRI); SuperRCIt.isValid();
 161            ++SuperRCIt) {
 162         if (Pushed)
 163           break;
 164         for (BitMaskClassIterator It(SuperRCIt.getMask(), TRI); It.isValid();
 165              ++It) {
 166           unsigned SuperRCId = It.getID();
 167           if (SuperRCId == RCId) {
 168             if (First)
 169               DEBUG(dbgs() << "  Enqueue subreg-class: ");
 170             DEBUG(dbgs() << TRI.getRegClassName(SubRC) << ", ");
 171             WorkList.push_back(SubRCId);
 172             // Remember that we saw the sub class.
 173             Covered.set(SubRCId);
 174             Pushed = true;
 175             First = false;
 176             break;
 177           }
 178         }
 179       }
 180     }
 181     if (!First)
 182       DEBUG(dbgs() << '\n');
 183   } while (!WorkList.empty());
 184 }
 185
 186 const RegisterBank *
 187 RegisterBankInfo::getRegBank(unsigned Reg, const MachineRegisterInfo &MRI,
 188                              const TargetRegisterInfo &TRI) const {
 189   if (TargetRegisterInfo::isPhysicalRegister(Reg))
 190     return &getRegBankFromRegClass(*TRI.getMinimalPhysRegClass(Reg));
 191
 192   assert(Reg && "NoRegister does not have a register bank");
 193   const RegClassOrRegBank &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
 194   if (auto *RB = RegClassOrBank.dyn_cast<const RegisterBank *>())
 195     return RB;
 196   if (auto *RC = RegClassOrBank.dyn_cast<const TargetRegisterClass *>())
 197     return &getRegBankFromRegClass(*RC);
 198   return nullptr;
 199 }
 200
 201 const RegisterBank *RegisterBankInfo::getRegBankFromConstraints(
 202     const MachineInstr &MI, unsigned OpIdx, const TargetInstrInfo &TII,
 203     const TargetRegisterInfo &TRI) const {
 204   // The mapping of the registers may be available via the
 205   // register class constraints.
 206   const TargetRegisterClass *RC = MI.getRegClassConstraint(OpIdx, &TII, &TRI);
 207
 208   if (!RC)
 209     return nullptr;
 210
 211   const RegisterBank &RegBank = getRegBankFromRegClass(*RC);
 212   // Sanity check that the target properly implemented getRegBankFromRegClass.
 213   assert(RegBank.covers(*RC) &&
 214          "The mapping of the register bank does not make sense");
 215   return &RegBank;
 216 }
 217
 218 const TargetRegisterClass *RegisterBankInfo::constrainGenericRegister(
 219     unsigned Reg, const TargetRegisterClass &RC, MachineRegisterInfo &MRI) {
 220
 221   // If the register already has a class, fallback to MRI::constrainRegClass.
 222   auto &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
 223   if (RegClassOrBank.is<const TargetRegisterClass *>())
 224     return MRI.constrainRegClass(Reg, &RC);
 225
 226   const RegisterBank *RB = RegClassOrBank.get<const RegisterBank *>();
 227   // Otherwise, all we can do is ensure the bank covers the class, and set it.
 228   if (RB && !RB->covers(RC))
 229     return nullptr;
 230
 231   // If nothing was set or the class is simply compatible, set it.
 232   MRI.setRegClass(Reg, &RC);
 233   return &RC;
 234 }
 235
 236 RegisterBankInfo::InstructionMapping
 237 RegisterBankInfo::getInstrMappingImpl(const MachineInstr &MI) const {
 238   // For copies we want to walk over the operands and try to find one
 239   // that has a register bank since the instruction itself will not get
 240   // us any constraint.
 241   bool isCopyLike = MI.isCopy() || MI.isPHI();
 242   // For copy like instruction, only the mapping of the definition
 243   // is important. The rest is not constrained.
 244   unsigned NumOperandsForMapping = isCopyLike ? 1 : MI.getNumOperands();
 245
 246   RegisterBankInfo::InstructionMapping Mapping(DefaultMappingID, /*Cost*/ 1,
 247                                                /*OperandsMapping*/ nullptr,
 248                                                NumOperandsForMapping);
 249   const MachineFunction &MF = *MI.getParent()->getParent();
 250   const TargetSubtargetInfo &STI = MF.getSubtarget();
 251   const TargetRegisterInfo &TRI = *STI.getRegisterInfo();
 252   const MachineRegisterInfo &MRI = MF.getRegInfo();
 253   // We may need to query the instruction encoding to guess the mapping.
 254   const TargetInstrInfo &TII = *STI.getInstrInfo();
 255
 256   // Before doing anything complicated check if the mapping is not
 257   // directly available.
 258   bool CompleteMapping = true;
 259
 260   SmallVector<const ValueMapping *, 8> OperandsMapping(NumOperandsForMapping);
 261   for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx;
 262        ++OpIdx) {
 263     const MachineOperand &MO = MI.getOperand(OpIdx);
 264     if (!MO.isReg())
 265       continue;
 266     unsigned Reg = MO.getReg();
 267     if (!Reg)
 268       continue;
 269     // The register bank of Reg is just a side effect of the current
 270     // excution and in particular, there is no reason to believe this
 271     // is the best default mapping for the current instruction.  Keep
 272     // it as an alternative register bank if we cannot figure out
 273     // something.
 274     const RegisterBank *AltRegBank = getRegBank(Reg, MRI, TRI);
 275     // For copy-like instruction, we want to reuse the register bank
 276     // that is already set on Reg, if any, since those instructions do
 277     // not have any constraints.
 278     const RegisterBank *CurRegBank = isCopyLike ? AltRegBank : nullptr;
 279     if (!CurRegBank) {
 280       // If this is a target specific instruction, we can deduce
 281       // the register bank from the encoding constraints.
 282       CurRegBank = getRegBankFromConstraints(MI, OpIdx, TII, TRI);
 283       if (!CurRegBank) {
 284         // All our attempts failed, give up.
 285         CompleteMapping = false;
 286
 287         if (!isCopyLike)
 288           // MI does not carry enough information to guess the mapping.
 289           return InstructionMapping();
 290         continue;
 291       }
 292     }
 293     const ValueMapping *ValMapping =
 294         &getValueMapping(0, getSizeInBits(Reg, MRI, TRI), *CurRegBank);
 295     if (isCopyLike) {
 296       OperandsMapping[0] = ValMapping;
 297       CompleteMapping = true;
 298       break;
 299     }
 300     OperandsMapping[OpIdx] = ValMapping;
 301   }
 302
 303   if (isCopyLike && !CompleteMapping)
 304     // No way to deduce the type from what we have.
 305     return InstructionMapping();
 306
 307   assert(CompleteMapping && "Setting an uncomplete mapping");
 308   Mapping.setOperandsMapping(getOperandsMapping(OperandsMapping));
 309   return Mapping;
 310 }
 311
 312 /// Hashing function for PartialMapping.
 313 static hash_code hashPartialMapping(unsigned StartIdx, unsigned Length,
 314                                     const RegisterBank *RegBank) {
 315   return hash_combine(StartIdx, Length, RegBank ? RegBank->getID() : 0);
 316 }
 317
 318 /// Overloaded version of hash_value for a PartialMapping.
 319 hash_code
 320 llvm::hash_value(const RegisterBankInfo::PartialMapping &PartMapping) {
 321   return hashPartialMapping(PartMapping.StartIdx, PartMapping.Length,
 322                             PartMapping.RegBank);
 323 }
 324
 325 const RegisterBankInfo::PartialMapping &
 326 RegisterBankInfo::getPartialMapping(unsigned StartIdx, unsigned Length,
 327                                     const RegisterBank &RegBank) const {
 328   ++NumPartialMappingsAccessed;
 329
 330   hash_code Hash = hashPartialMapping(StartIdx, Length, &RegBank);
 331   const auto &It = MapOfPartialMappings.find(Hash);
 332   if (It != MapOfPartialMappings.end())
 333     return *It->second;
 334
 335   ++NumPartialMappingsCreated;
 336
 337   const PartialMapping *&PartMapping = MapOfPartialMappings[Hash];
 338   PartMapping = new PartialMapping{StartIdx, Length, RegBank};
 339   return *PartMapping;
 340 }
 341
 342 const RegisterBankInfo::ValueMapping &
 343 RegisterBankInfo::getValueMapping(unsigned StartIdx, unsigned Length,
 344                                   const RegisterBank &RegBank) const {
 345   return getValueMapping(&getPartialMapping(StartIdx, Length, RegBank), 1);
 346 }
 347
 348 static hash_code
 349 hashValueMapping(const RegisterBankInfo::PartialMapping *BreakDown,
 350                  unsigned NumBreakDowns) {
 351   if (LLVM_LIKELY(NumBreakDowns == 1))
 352     return hash_value(*BreakDown);
 353   SmallVector<size_t, 8> Hashes(NumBreakDowns);
 354   for (unsigned Idx = 0; Idx != NumBreakDowns; ++Idx)
 355     Hashes.push_back(hash_value(BreakDown[Idx]));
 356   return hash_combine_range(Hashes.begin(), Hashes.end());
 357 }
 358
 359 const RegisterBankInfo::ValueMapping &
 360 RegisterBankInfo::getValueMapping(const PartialMapping *BreakDown,
 361                                   unsigned NumBreakDowns) const {
 362   ++NumValueMappingsAccessed;
 363
 364   hash_code Hash = hashValueMapping(BreakDown, NumBreakDowns);
 365   const auto &It = MapOfValueMappings.find(Hash);
 366   if (It != MapOfValueMappings.end())
 367     return *It->second;
 368
 369   ++NumValueMappingsCreated;
 370
 371   const ValueMapping *&ValMapping = MapOfValueMappings[Hash];
 372   ValMapping = new ValueMapping{BreakDown, NumBreakDowns};
 373   return *ValMapping;
 374 }
 375
 376 template <typename Iterator>
 377 const RegisterBankInfo::ValueMapping *
 378 RegisterBankInfo::getOperandsMapping(Iterator Begin, Iterator End) const {
 379
 380   ++NumOperandsMappingsAccessed;
 381
 382   // The addresses of the value mapping are unique.
 383   // Therefore, we can use them directly to hash the operand mapping.
 384   hash_code Hash = hash_combine_range(Begin, End);
 385   const auto &It = MapOfOperandsMappings.find(Hash);
 386   if (It != MapOfOperandsMappings.end())
 387     return It->second;
 388
 389   ++NumOperandsMappingsCreated;
 390
 391   // Create the array of ValueMapping.
 392   // Note: this array will not hash to this instance of operands
 393   // mapping, because we use the pointer of the ValueMapping
 394   // to hash and we expect them to uniquely identify an instance
 395   // of value mapping.
 396   ValueMapping *&Res = MapOfOperandsMappings[Hash];
 397   Res = new ValueMapping[std::distance(Begin, End)];
 398   unsigned Idx = 0;
 399   for (Iterator It = Begin; It != End; ++It, ++Idx) {
 400     const ValueMapping *ValMap = *It;
 401     if (!ValMap)
 402       continue;
 403     Res[Idx] = *ValMap;
 404   }
 405   return Res;
 406 }
 407
 408 const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
 409     const SmallVectorImpl<const RegisterBankInfo::ValueMapping *> &OpdsMapping)
 410     const {
 411   return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
 412 }
 413
 414 const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
 415     std::initializer_list<const RegisterBankInfo::ValueMapping *> OpdsMapping)
 416     const {
 417   return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
 418 }
 419
 420 RegisterBankInfo::InstructionMapping
 421 RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
 422   RegisterBankInfo::InstructionMapping Mapping = getInstrMappingImpl(MI);
 423   if (Mapping.isValid())
 424     return Mapping;
 425   llvm_unreachable("The target must implement this");
 426 }
 427
 428 RegisterBankInfo::InstructionMappings
 429 RegisterBankInfo::getInstrPossibleMappings(const MachineInstr &MI) const {
 430   InstructionMappings PossibleMappings;
 431   // Put the default mapping first.
 432   PossibleMappings.push_back(getInstrMapping(MI));
 433   // Then the alternative mapping, if any.
 434   InstructionMappings AltMappings = getInstrAlternativeMappings(MI);
 435   for (InstructionMapping &AltMapping : AltMappings)
 436     PossibleMappings.emplace_back(std::move(AltMapping));
 437 #ifndef NDEBUG
 438   for (const InstructionMapping &Mapping : PossibleMappings)
 439     assert(Mapping.verify(MI) && "Mapping is invalid");
 440 #endif
 441   return PossibleMappings;
 442 }
 443
 444 RegisterBankInfo::InstructionMappings
 445 RegisterBankInfo::getInstrAlternativeMappings(const MachineInstr &MI) const {
 446   // No alternative for MI.
 447   return InstructionMappings();
 448 }
 449
 450 void RegisterBankInfo::applyDefaultMapping(const OperandsMapper &OpdMapper) {
 451   MachineInstr &MI = OpdMapper.getMI();
 452   DEBUG(dbgs() << "Applying default-like mapping\n");
 453   for (unsigned OpIdx = 0,
 454                 EndIdx = OpdMapper.getInstrMapping().getNumOperands();
 455        OpIdx != EndIdx; ++OpIdx) {
 456     DEBUG(dbgs() << "OpIdx " << OpIdx);
 457     MachineOperand &MO = MI.getOperand(OpIdx);
 458     if (!MO.isReg()) {
 459       DEBUG(dbgs() << " is not a register, nothing to be done\n");
 460       continue;
 461     }
 462     assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns ==
 463                1 &&
 464            "This mapping is too complex for this function");
 465     iterator_range<SmallVectorImpl<unsigned>::const_iterator> NewRegs =
 466         OpdMapper.getVRegs(OpIdx);
 467     if (NewRegs.begin() == NewRegs.end()) {
 468       DEBUG(dbgs() << " has not been repaired, nothing to be done\n");
 469       continue;
 470     }
 471     DEBUG(dbgs() << " changed, replace " << MO.getReg());
 472     MO.setReg(*NewRegs.begin());
 473     DEBUG(dbgs() << " with " << MO.getReg());
 474   }
 475 }
 476
 477 unsigned RegisterBankInfo::getSizeInBits(unsigned Reg,
 478                                          const MachineRegisterInfo &MRI,
 479                                          const TargetRegisterInfo &TRI) {
 480   const TargetRegisterClass *RC = nullptr;
 481   if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 482     // The size is not directly available for physical registers.
 483     // Instead, we need to access a register class that contains Reg and
 484     // get the size of that register class.
 485     RC = TRI.getMinimalPhysRegClass(Reg);
 486   } else {
 487     LLT Ty = MRI.getType(Reg);
 488     unsigned RegSize = Ty.isValid() ? Ty.getSizeInBits() : 0;
 489     // If Reg is not a generic register, query the register class to
 490     // get its size.
 491     if (RegSize)
 492       return RegSize;
 493     // Since Reg is not a generic register, it must have a register class.
 494     RC = MRI.getRegClass(Reg);
 495   }
 496   assert(RC && "Unable to deduce the register class");
 497   return RC->getSize() * 8;
 498 }
 499
 500 //------------------------------------------------------------------------------
 501 // Helper classes implementation.
 502 //------------------------------------------------------------------------------
 503 LLVM_DUMP_METHOD void RegisterBankInfo::PartialMapping::dump() const {
 504   print(dbgs());
 505   dbgs() << '\n';
 506 }
 507
 508 bool RegisterBankInfo::PartialMapping::verify() const {
 509   assert(RegBank && "Register bank not set");
 510   assert(Length && "Empty mapping");
 511   assert((StartIdx <= getHighBitIdx()) && "Overflow, switch to APInt?");
 512   // Check if the minimum width fits into RegBank.
 513   assert(RegBank->getSize() >= Length && "Register bank too small for Mask");
 514   return true;
 515 }
 516
 517 void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const {
 518   OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = ";
 519   if (RegBank)
 520     OS << *RegBank;
 521   else
 522     OS << "nullptr";
 523 }
 524
 525 bool RegisterBankInfo::ValueMapping::verify(unsigned MeaningfulBitWidth) const {
 526   assert(NumBreakDowns && "Value mapped nowhere?!");
 527   unsigned OrigValueBitWidth = 0;
 528   for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
 529     // Check that each register bank is big enough to hold the partial value:
 530     // this check is done by PartialMapping::verify
 531     assert(PartMap.verify() && "Partial mapping is invalid");
 532     // The original value should completely be mapped.
 533     // Thus the maximum accessed index + 1 is the size of the original value.
 534     OrigValueBitWidth =
 535         std::max(OrigValueBitWidth, PartMap.getHighBitIdx() + 1);
 536   }
 537   assert(OrigValueBitWidth >= MeaningfulBitWidth &&
 538          "Meaningful bits not covered by the mapping");
 539   APInt ValueMask(OrigValueBitWidth, 0);
 540   for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
 541     // Check that the union of the partial mappings covers the whole value,
 542     // without overlaps.
 543     // The high bit is exclusive in the APInt API, thus getHighBitIdx + 1.
 544     APInt PartMapMask = APInt::getBitsSet(OrigValueBitWidth, PartMap.StartIdx,
 545                                           PartMap.getHighBitIdx() + 1);
 546     ValueMask ^= PartMapMask;
 547     assert((ValueMask & PartMapMask) == PartMapMask &&
 548            "Some partial mappings overlap");
 549   }
 550   assert(ValueMask.isAllOnesValue() && "Value is not fully mapped");
 551   return true;
 552 }
 553
 554 LLVM_DUMP_METHOD void RegisterBankInfo::ValueMapping::dump() const {
 555   print(dbgs());
 556   dbgs() << '\n';
 557 }
 558
 559 void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const {
 560   OS << "#BreakDown: " << NumBreakDowns << " ";
 561   bool IsFirst = true;
 562   for (const PartialMapping &PartMap : *this) {
 563     if (!IsFirst)
 564       OS << ", ";
 565     OS << '[' << PartMap << ']';
 566     IsFirst = false;
 567   }
 568 }
 569
 570 bool RegisterBankInfo::InstructionMapping::verify(
 571     const MachineInstr &MI) const {
 572   // Check that all the register operands are properly mapped.
 573   // Check the constructor invariant.
 574   // For PHI, we only care about mapping the definition.
 575   assert(NumOperands ==
 576              ((MI.isCopy() || MI.isPHI()) ? 1 : MI.getNumOperands()) &&
 577          "NumOperands must match, see constructor");
 578   assert(MI.getParent() && MI.getParent()->getParent() &&
 579          "MI must be connected to a MachineFunction");
 580   const MachineFunction &MF = *MI.getParent()->getParent();
 581   (void)MF;
 582
 583   for (unsigned Idx = 0; Idx < NumOperands; ++Idx) {
 584     const MachineOperand &MO = MI.getOperand(Idx);
 585     if (!MO.isReg()) {
 586       assert(!getOperandMapping(Idx).isValid() &&
 587              "We should not care about non-reg mapping");
 588       continue;
 589     }
 590     unsigned Reg = MO.getReg();
 591     if (!Reg)
 592       continue;
 593     assert(getOperandMapping(Idx).isValid() &&
 594            "We must have a mapping for reg operands");
 595     const RegisterBankInfo::ValueMapping &MOMapping = getOperandMapping(Idx);
 596     (void)MOMapping;
 597     // Register size in bits.
 598     // This size must match what the mapping expects.
 599     assert(MOMapping.verify(getSizeInBits(
 600                Reg, MF.getRegInfo(), *MF.getSubtarget().getRegisterInfo())) &&
 601            "Value mapping is invalid");
 602   }
 603   return true;
 604 }
 605
 606 LLVM_DUMP_METHOD void RegisterBankInfo::InstructionMapping::dump() const {
 607   print(dbgs());
 608   dbgs() << '\n';
 609 }
 610
 611 void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const {
 612   OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: ";
 613
 614   for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
 615     const ValueMapping &ValMapping = getOperandMapping(OpIdx);
 616     if (OpIdx)
 617       OS << ", ";
 618     OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}';
 619   }
 620 }
 621
 622 const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1;
 623
 624 RegisterBankInfo::OperandsMapper::OperandsMapper(
 625     MachineInstr &MI, const InstructionMapping &InstrMapping,
 626     MachineRegisterInfo &MRI)
 627     : MRI(MRI), MI(MI), InstrMapping(InstrMapping) {
 628   unsigned NumOpds = InstrMapping.getNumOperands();
 629   OpToNewVRegIdx.resize(NumOpds, OperandsMapper::DontKnowIdx);
 630   assert(InstrMapping.verify(MI) && "Invalid mapping for MI");
 631 }
 632
 633 iterator_range<SmallVectorImpl<unsigned>::iterator>
 634 RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) {
 635   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
 636   unsigned NumPartialVal =
 637       getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
 638   int StartIdx = OpToNewVRegIdx[OpIdx];
 639
 640   if (StartIdx == OperandsMapper::DontKnowIdx) {
 641     // This is the first time we try to access OpIdx.
 642     // Create the cells that will hold all the partial values at the
 643     // end of the list of NewVReg.
 644     StartIdx = NewVRegs.size();
 645     OpToNewVRegIdx[OpIdx] = StartIdx;
 646     for (unsigned i = 0; i < NumPartialVal; ++i)
 647       NewVRegs.push_back(0);
 648   }
 649   SmallVectorImpl<unsigned>::iterator End =
 650       getNewVRegsEnd(StartIdx, NumPartialVal);
 651
 652   return make_range(&NewVRegs[StartIdx], End);
 653 }
 654
 655 SmallVectorImpl<unsigned>::const_iterator
 656 RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
 657                                                  unsigned NumVal) const {
 658   return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal);
 659 }
 660 SmallVectorImpl<unsigned>::iterator
 661 RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
 662                                                  unsigned NumVal) {
 663   assert((NewVRegs.size() == StartIdx + NumVal ||
 664           NewVRegs.size() > StartIdx + NumVal) &&
 665          "NewVRegs too small to contain all the partial mapping");
 666   return NewVRegs.size() <= StartIdx + NumVal ? NewVRegs.end()
 667                                               : &NewVRegs[StartIdx + NumVal];
 668 }
 669
 670 void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) {
 671   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
 672   iterator_range<SmallVectorImpl<unsigned>::iterator> NewVRegsForOpIdx =
 673       getVRegsMem(OpIdx);
 674   const ValueMapping &ValMapping = getInstrMapping().getOperandMapping(OpIdx);
 675   const PartialMapping *PartMap = ValMapping.begin();
 676   for (unsigned &NewVReg : NewVRegsForOpIdx) {
 677     assert(PartMap != ValMapping.end() && "Out-of-bound access");
 678     assert(NewVReg == 0 && "Register has already been created");
 679     NewVReg = MRI.createGenericVirtualRegister(LLT::scalar(PartMap->Length));
 680     MRI.setRegBank(NewVReg, *PartMap->RegBank);
 681     ++PartMap;
 682   }
 683 }
 684
 685 void RegisterBankInfo::OperandsMapper::setVRegs(unsigned OpIdx,
 686                                                 unsigned PartialMapIdx,
 687                                                 unsigned NewVReg) {
 688   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
 689   assert(getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns >
 690              PartialMapIdx &&
 691          "Out-of-bound access for partial mapping");
 692   // Make sure the memory is initialized for that operand.
 693   (void)getVRegsMem(OpIdx);
 694   assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 &&
 695          "This value is already set");
 696   NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg;
 697 }
 698
 699 iterator_range<SmallVectorImpl<unsigned>::const_iterator>
 700 RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx,
 701                                            bool ForDebug) const {
 702   (void)ForDebug;
 703   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
 704   int StartIdx = OpToNewVRegIdx[OpIdx];
 705
 706   if (StartIdx == OperandsMapper::DontKnowIdx)
 707     return make_range(NewVRegs.end(), NewVRegs.end());
 708
 709   unsigned PartMapSize =
 710       getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
 711   SmallVectorImpl<unsigned>::const_iterator End =
 712       getNewVRegsEnd(StartIdx, PartMapSize);
 713   iterator_range<SmallVectorImpl<unsigned>::const_iterator> Res =
 714       make_range(&NewVRegs[StartIdx], End);
 715 #ifndef NDEBUG
 716   for (unsigned VReg : Res)
 717     assert((VReg || ForDebug) && "Some registers are uninitialized");
 718 #endif
 719   return Res;
 720 }
 721
 722 LLVM_DUMP_METHOD void RegisterBankInfo::OperandsMapper::dump() const {
 723   print(dbgs(), true);
 724   dbgs() << '\n';
 725 }
 726
 727 void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS,
 728                                              bool ForDebug) const {
 729   unsigned NumOpds = getInstrMapping().getNumOperands();
 730   if (ForDebug) {
 731     OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n';
 732     // Print out the internal state of the index table.
 733     OS << "Populated indices (CellNumber, IndexInNewVRegs): ";
 734     bool IsFirst = true;
 735     for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
 736       if (OpToNewVRegIdx[Idx] != DontKnowIdx) {
 737         if (!IsFirst)
 738           OS << ", ";
 739         OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')';
 740         IsFirst = false;
 741       }
 742     }
 743     OS << '\n';
 744   } else
 745     OS << "Mapping ID: " << getInstrMapping().getID() << ' ';
 746
 747   OS << "Operand Mapping: ";
 748   // If we have a function, we can pretty print the name of the registers.
 749   // Otherwise we will print the raw numbers.
 750   const TargetRegisterInfo *TRI =
 751       getMI().getParent() && getMI().getParent()->getParent()
 752           ? getMI().getParent()->getParent()->getSubtarget().getRegisterInfo()
 753           : nullptr;
 754   bool IsFirst = true;
 755   for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
 756     if (OpToNewVRegIdx[Idx] == DontKnowIdx)
 757       continue;
 758     if (!IsFirst)
 759       OS << ", ";
 760     IsFirst = false;
 761     OS << '(' << PrintReg(getMI().getOperand(Idx).getReg(), TRI) << ", [";
 762     bool IsFirstNewVReg = true;
 763     for (unsigned VReg : getVRegs(Idx)) {
 764       if (!IsFirstNewVReg)
 765         OS << ", ";
 766       IsFirstNewVReg = false;
 767       OS << PrintReg(VReg, TRI);
 768     }
 769     OS << "])";
 770   }
 771 }