lib/CodeGen/GlobalISel/RegisterBankInfo.cpp

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