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