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