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