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