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