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