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