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