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 (Reg.isPhysical()) { 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(Reg.isPhysical() && "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 LLT Ty = MRI.getType(MO.getReg()); 453 if (!Ty.isValid()) 454 continue; 455 assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns != 456 0 && 457 "Invalid mapping"); 458 assert(OpdMapper.getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns == 459 1 && 460 "This mapping is too complex for this function"); 461 iterator_range<SmallVectorImpl<Register>::const_iterator> NewRegs = 462 OpdMapper.getVRegs(OpIdx); 463 if (NewRegs.empty()) { 464 LLVM_DEBUG(dbgs() << " has not been repaired, nothing to be done\n"); 465 continue; 466 } 467 Register OrigReg = MO.getReg(); 468 Register NewReg = *NewRegs.begin(); 469 LLVM_DEBUG(dbgs() << " changed, replace " << printReg(OrigReg, nullptr)); 470 MO.setReg(NewReg); 471 LLVM_DEBUG(dbgs() << " with " << printReg(NewReg, nullptr)); 472 473 // The OperandsMapper creates plain scalar, we may have to fix that. 474 // Check if the types match and if not, fix that. 475 LLT OrigTy = MRI.getType(OrigReg); 476 LLT NewTy = MRI.getType(NewReg); 477 if (OrigTy != NewTy) { 478 // The default mapping is not supposed to change the size of 479 // the storage. However, right now we don't necessarily bump all 480 // the types to storage size. For instance, we can consider 481 // s16 G_AND legal whereas the storage size is going to be 32. 482 assert(OrigTy.getSizeInBits() <= NewTy.getSizeInBits() && 483 "Types with difference size cannot be handled by the default " 484 "mapping"); 485 LLVM_DEBUG(dbgs() << "\nChange type of new opd from " << NewTy << " to " 486 << OrigTy); 487 MRI.setType(NewReg, OrigTy); 488 } 489 LLVM_DEBUG(dbgs() << '\n'); 490 } 491 } 492 493 unsigned RegisterBankInfo::getSizeInBits(Register Reg, 494 const MachineRegisterInfo &MRI, 495 const TargetRegisterInfo &TRI) const { 496 if (Reg.isPhysical()) { 497 // The size is not directly available for physical registers. 498 // Instead, we need to access a register class that contains Reg and 499 // get the size of that register class. 500 // Because this is expensive, we'll cache the register class by calling 501 auto *RC = &getMinimalPhysRegClass(Reg, TRI); 502 assert(RC && "Expecting Register class"); 503 return TRI.getRegSizeInBits(*RC); 504 } 505 return TRI.getRegSizeInBits(Reg, MRI); 506 } 507 508 //------------------------------------------------------------------------------ 509 // Helper classes implementation. 510 //------------------------------------------------------------------------------ 511 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 512 LLVM_DUMP_METHOD void RegisterBankInfo::PartialMapping::dump() const { 513 print(dbgs()); 514 dbgs() << '\n'; 515 } 516 #endif 517 518 bool RegisterBankInfo::PartialMapping::verify() const { 519 assert(RegBank && "Register bank not set"); 520 assert(Length && "Empty mapping"); 521 assert((StartIdx <= getHighBitIdx()) && "Overflow, switch to APInt?"); 522 // Check if the minimum width fits into RegBank. 523 assert(RegBank->getSize() >= Length && "Register bank too small for Mask"); 524 return true; 525 } 526 527 void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const { 528 OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = "; 529 if (RegBank) 530 OS << *RegBank; 531 else 532 OS << "nullptr"; 533 } 534 535 bool RegisterBankInfo::ValueMapping::partsAllUniform() const { 536 if (NumBreakDowns < 2) 537 return true; 538 539 const PartialMapping *First = begin(); 540 for (const PartialMapping *Part = First + 1; Part != end(); ++Part) { 541 if (Part->Length != First->Length || Part->RegBank != First->RegBank) 542 return false; 543 } 544 545 return true; 546 } 547 548 bool RegisterBankInfo::ValueMapping::verify(unsigned MeaningfulBitWidth) const { 549 assert(NumBreakDowns && "Value mapped nowhere?!"); 550 unsigned OrigValueBitWidth = 0; 551 for (const RegisterBankInfo::PartialMapping &PartMap : *this) { 552 // Check that each register bank is big enough to hold the partial value: 553 // this check is done by PartialMapping::verify 554 assert(PartMap.verify() && "Partial mapping is invalid"); 555 // The original value should completely be mapped. 556 // Thus the maximum accessed index + 1 is the size of the original value. 557 OrigValueBitWidth = 558 std::max(OrigValueBitWidth, PartMap.getHighBitIdx() + 1); 559 } 560 assert(OrigValueBitWidth >= MeaningfulBitWidth && 561 "Meaningful bits not covered by the mapping"); 562 APInt ValueMask(OrigValueBitWidth, 0); 563 for (const RegisterBankInfo::PartialMapping &PartMap : *this) { 564 // Check that the union of the partial mappings covers the whole value, 565 // without overlaps. 566 // The high bit is exclusive in the APInt API, thus getHighBitIdx + 1. 567 APInt PartMapMask = APInt::getBitsSet(OrigValueBitWidth, PartMap.StartIdx, 568 PartMap.getHighBitIdx() + 1); 569 ValueMask ^= PartMapMask; 570 assert((ValueMask & PartMapMask) == PartMapMask && 571 "Some partial mappings overlap"); 572 } 573 assert(ValueMask.isAllOnes() && "Value is not fully mapped"); 574 return true; 575 } 576 577 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 578 LLVM_DUMP_METHOD void RegisterBankInfo::ValueMapping::dump() const { 579 print(dbgs()); 580 dbgs() << '\n'; 581 } 582 #endif 583 584 void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const { 585 OS << "#BreakDown: " << NumBreakDowns << " "; 586 bool IsFirst = true; 587 for (const PartialMapping &PartMap : *this) { 588 if (!IsFirst) 589 OS << ", "; 590 OS << '[' << PartMap << ']'; 591 IsFirst = false; 592 } 593 } 594 595 bool RegisterBankInfo::InstructionMapping::verify( 596 const MachineInstr &MI) const { 597 // Check that all the register operands are properly mapped. 598 // Check the constructor invariant. 599 // For PHI, we only care about mapping the definition. 600 assert(NumOperands == (isCopyLike(MI) ? 1 : MI.getNumOperands()) && 601 "NumOperands must match, see constructor"); 602 assert(MI.getParent() && MI.getMF() && 603 "MI must be connected to a MachineFunction"); 604 const MachineFunction &MF = *MI.getMF(); 605 const RegisterBankInfo *RBI = MF.getSubtarget().getRegBankInfo(); 606 (void)RBI; 607 const MachineRegisterInfo &MRI = MF.getRegInfo(); 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 LLT Ty = MRI.getType(Reg); 620 if (!Ty.isValid()) 621 continue; 622 assert(getOperandMapping(Idx).isValid() && 623 "We must have a mapping for reg operands"); 624 const RegisterBankInfo::ValueMapping &MOMapping = getOperandMapping(Idx); 625 (void)MOMapping; 626 // Register size in bits. 627 // This size must match what the mapping expects. 628 assert(MOMapping.verify(RBI->getSizeInBits( 629 Reg, MF.getRegInfo(), *MF.getSubtarget().getRegisterInfo())) && 630 "Value mapping is invalid"); 631 } 632 return true; 633 } 634 635 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 636 LLVM_DUMP_METHOD void RegisterBankInfo::InstructionMapping::dump() const { 637 print(dbgs()); 638 dbgs() << '\n'; 639 } 640 #endif 641 642 void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const { 643 OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: "; 644 645 for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) { 646 const ValueMapping &ValMapping = getOperandMapping(OpIdx); 647 if (OpIdx) 648 OS << ", "; 649 OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}'; 650 } 651 } 652 653 const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1; 654 655 RegisterBankInfo::OperandsMapper::OperandsMapper( 656 MachineInstr &MI, const InstructionMapping &InstrMapping, 657 MachineRegisterInfo &MRI) 658 : MRI(MRI), MI(MI), InstrMapping(InstrMapping) { 659 unsigned NumOpds = InstrMapping.getNumOperands(); 660 OpToNewVRegIdx.resize(NumOpds, OperandsMapper::DontKnowIdx); 661 assert(InstrMapping.verify(MI) && "Invalid mapping for MI"); 662 } 663 664 iterator_range<SmallVectorImpl<Register>::iterator> 665 RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) { 666 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access"); 667 unsigned NumPartialVal = 668 getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns; 669 int StartIdx = OpToNewVRegIdx[OpIdx]; 670 671 if (StartIdx == OperandsMapper::DontKnowIdx) { 672 // This is the first time we try to access OpIdx. 673 // Create the cells that will hold all the partial values at the 674 // end of the list of NewVReg. 675 StartIdx = NewVRegs.size(); 676 OpToNewVRegIdx[OpIdx] = StartIdx; 677 for (unsigned i = 0; i < NumPartialVal; ++i) 678 NewVRegs.push_back(0); 679 } 680 SmallVectorImpl<Register>::iterator End = 681 getNewVRegsEnd(StartIdx, NumPartialVal); 682 683 return make_range(&NewVRegs[StartIdx], End); 684 } 685 686 SmallVectorImpl<Register>::const_iterator 687 RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx, 688 unsigned NumVal) const { 689 return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal); 690 } 691 SmallVectorImpl<Register>::iterator 692 RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx, 693 unsigned NumVal) { 694 assert((NewVRegs.size() == StartIdx + NumVal || 695 NewVRegs.size() > StartIdx + NumVal) && 696 "NewVRegs too small to contain all the partial mapping"); 697 return NewVRegs.size() <= StartIdx + NumVal ? NewVRegs.end() 698 : &NewVRegs[StartIdx + NumVal]; 699 } 700 701 void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) { 702 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access"); 703 iterator_range<SmallVectorImpl<Register>::iterator> NewVRegsForOpIdx = 704 getVRegsMem(OpIdx); 705 const ValueMapping &ValMapping = getInstrMapping().getOperandMapping(OpIdx); 706 const PartialMapping *PartMap = ValMapping.begin(); 707 for (Register &NewVReg : NewVRegsForOpIdx) { 708 assert(PartMap != ValMapping.end() && "Out-of-bound access"); 709 assert(NewVReg == 0 && "Register has already been created"); 710 // The new registers are always bound to scalar with the right size. 711 // The actual type has to be set when the target does the mapping 712 // of the instruction. 713 // The rationale is that this generic code cannot guess how the 714 // target plans to split the input type. 715 NewVReg = MRI.createGenericVirtualRegister(LLT::scalar(PartMap->Length)); 716 MRI.setRegBank(NewVReg, *PartMap->RegBank); 717 ++PartMap; 718 } 719 } 720 721 void RegisterBankInfo::OperandsMapper::setVRegs(unsigned OpIdx, 722 unsigned PartialMapIdx, 723 Register NewVReg) { 724 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access"); 725 assert(getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns > 726 PartialMapIdx && 727 "Out-of-bound access for partial mapping"); 728 // Make sure the memory is initialized for that operand. 729 (void)getVRegsMem(OpIdx); 730 assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 && 731 "This value is already set"); 732 NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg; 733 } 734 735 iterator_range<SmallVectorImpl<Register>::const_iterator> 736 RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx, 737 bool ForDebug) const { 738 (void)ForDebug; 739 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access"); 740 int StartIdx = OpToNewVRegIdx[OpIdx]; 741 742 if (StartIdx == OperandsMapper::DontKnowIdx) 743 return make_range(NewVRegs.end(), NewVRegs.end()); 744 745 unsigned PartMapSize = 746 getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns; 747 SmallVectorImpl<Register>::const_iterator End = 748 getNewVRegsEnd(StartIdx, PartMapSize); 749 iterator_range<SmallVectorImpl<Register>::const_iterator> Res = 750 make_range(&NewVRegs[StartIdx], End); 751 #ifndef NDEBUG 752 for (Register VReg : Res) 753 assert((VReg || ForDebug) && "Some registers are uninitialized"); 754 #endif 755 return Res; 756 } 757 758 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 759 LLVM_DUMP_METHOD void RegisterBankInfo::OperandsMapper::dump() const { 760 print(dbgs(), true); 761 dbgs() << '\n'; 762 } 763 #endif 764 765 void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS, 766 bool ForDebug) const { 767 unsigned NumOpds = getInstrMapping().getNumOperands(); 768 if (ForDebug) { 769 OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n'; 770 // Print out the internal state of the index table. 771 OS << "Populated indices (CellNumber, IndexInNewVRegs): "; 772 bool IsFirst = true; 773 for (unsigned Idx = 0; Idx != NumOpds; ++Idx) { 774 if (OpToNewVRegIdx[Idx] != DontKnowIdx) { 775 if (!IsFirst) 776 OS << ", "; 777 OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')'; 778 IsFirst = false; 779 } 780 } 781 OS << '\n'; 782 } else 783 OS << "Mapping ID: " << getInstrMapping().getID() << ' '; 784 785 OS << "Operand Mapping: "; 786 // If we have a function, we can pretty print the name of the registers. 787 // Otherwise we will print the raw numbers. 788 const TargetRegisterInfo *TRI = 789 getMI().getParent() && getMI().getMF() 790 ? getMI().getMF()->getSubtarget().getRegisterInfo() 791 : nullptr; 792 bool IsFirst = true; 793 for (unsigned Idx = 0; Idx != NumOpds; ++Idx) { 794 if (OpToNewVRegIdx[Idx] == DontKnowIdx) 795 continue; 796 if (!IsFirst) 797 OS << ", "; 798 IsFirst = false; 799 OS << '(' << printReg(getMI().getOperand(Idx).getReg(), TRI) << ", ["; 800 bool IsFirstNewVReg = true; 801 for (Register VReg : getVRegs(Idx)) { 802 if (!IsFirstNewVReg) 803 OS << ", "; 804 IsFirstNewVReg = false; 805 OS << printReg(VReg, TRI); 806 } 807 OS << "])"; 808 } 809 } 810