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