llvm/lib/CodeGen/RegisterBankInfo.cpp

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