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