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