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