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(ID: 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(Register Reg,
104 const TargetRegisterInfo &TRI) const {
105 assert(Reg.isPhysical() && "Reg must be a physreg");
106 const auto &RegRCIt = PhysRegMinimalRCs.find(Val: Reg);
107 if (RegRCIt != PhysRegMinimalRCs.end())
108 return RegRCIt->second;
109 const TargetRegisterClass *PhysRC = TRI.getMinimalPhysRegClassLLT(Reg, Ty: LLT());
110 PhysRegMinimalRCs[Reg] = PhysRC;
111 return PhysRC;
112}
113
114const 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: &TII, TRI);
122
123 if (!RC)
124 return nullptr;
125
126 Register Reg = MI.getOperand(i: OpIdx).getReg();
127 const RegisterBank &RegBank = getRegBankFromRegClass(RC: *RC, Ty: 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
134const 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 *>(Val: RegClassOrBank))
140 return MRI.constrainRegClass(Reg, RC: &RC);
141
142 const RegisterBank *RB = cast<const RegisterBank *>(Val: 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: &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.
158static bool isCopyLike(const MachineInstr &MI) {
159 return MI.isCopy() || MI.isPHI() ||
160 MI.getOpcode() == TargetOpcode::REG_SEQUENCE;
161}
162
163const RegisterBankInfo::InstructionMapping &
164RegisterBankInfo::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(i: 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(StartIdx: 0, Length: Size, RegBank: *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(Reg: MI.getOperand(i: 0).getReg(),
225 MRI, TRI);
226 OperandsMapping[0] = &getValueMapping(StartIdx: 0, Length: ResultSize, RegBank: *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(i: 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(Dst: *CurRegBank, Src: *AltRegBank, Size: 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 ID: DefaultMappingID, /*Cost*/ 1,
264 /*OperandsMapping*/ getOperandsMapping(OpdsMapping: OperandsMapping),
265 NumOperands: NumOperandsForMapping);
266}
267
268/// Hashing function for PartialMapping.
269static hash_code hashPartialMapping(unsigned StartIdx, unsigned Length,
270 const RegisterBank *RegBank) {
271 return hash_combine(args: StartIdx, args: Length, args: RegBank ? RegBank->getID() : 0);
272}
273
274/// Overloaded version of hash_value for a PartialMapping.
275hash_code
276llvm::hash_value(const RegisterBankInfo::PartialMapping &PartMapping) {
277 return hashPartialMapping(StartIdx: PartMapping.StartIdx, Length: PartMapping.Length,
278 RegBank: PartMapping.RegBank);
279}
280
281const RegisterBankInfo::PartialMapping &
282RegisterBankInfo::getPartialMapping(unsigned StartIdx, unsigned Length,
283 const RegisterBank &RegBank) const {
284 ++NumPartialMappingsAccessed;
285
286 hash_code Hash = hashPartialMapping(StartIdx, Length, RegBank: &RegBank);
287 const auto &It = MapOfPartialMappings.find(Val: 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>(args&: StartIdx, args&: Length, args: RegBank);
295 return *PartMapping;
296}
297
298const RegisterBankInfo::ValueMapping &
299RegisterBankInfo::getValueMapping(unsigned StartIdx, unsigned Length,
300 const RegisterBank &RegBank) const {
301 return getValueMapping(BreakDown: &getPartialMapping(StartIdx, Length, RegBank), NumBreakDowns: 1);
302}
303
304static hash_code
305hashValueMapping(const RegisterBankInfo::PartialMapping *BreakDown,
306 unsigned NumBreakDowns) {
307 if (LLVM_LIKELY(NumBreakDowns == 1))
308 return hash_value(PartMapping: *BreakDown);
309 SmallVector<size_t, 8> Hashes(NumBreakDowns);
310 for (unsigned Idx = 0; Idx != NumBreakDowns; ++Idx)
311 Hashes.push_back(Elt: hash_value(PartMapping: BreakDown[Idx]));
312 return hash_combine_range(first: Hashes.begin(), last: Hashes.end());
313}
314
315const RegisterBankInfo::ValueMapping &
316RegisterBankInfo::getValueMapping(const PartialMapping *BreakDown,
317 unsigned NumBreakDowns) const {
318 ++NumValueMappingsAccessed;
319
320 hash_code Hash = hashValueMapping(BreakDown, NumBreakDowns);
321 const auto &It = MapOfValueMappings.find(Val: 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>(args&: BreakDown, args&: NumBreakDowns);
329 return *ValMapping;
330}
331
332template <typename Iterator>
333const RegisterBankInfo::ValueMapping *
334RegisterBankInfo::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
363const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
364 const SmallVectorImpl<const RegisterBankInfo::ValueMapping *> &OpdsMapping)
365 const {
366 return getOperandsMapping(Begin: OpdsMapping.begin(), End: OpdsMapping.end());
367}
368
369const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
370 std::initializer_list<const RegisterBankInfo::ValueMapping *> OpdsMapping)
371 const {
372 return getOperandsMapping(Begin: OpdsMapping.begin(), End: OpdsMapping.end());
373}
374
375static hash_code
376hashInstructionMapping(unsigned ID, unsigned Cost,
377 const RegisterBankInfo::ValueMapping *OperandsMapping,
378 unsigned NumOperands) {
379 return hash_combine(args: ID, args: Cost, args: OperandsMapping, args: NumOperands);
380}
381
382const RegisterBankInfo::InstructionMapping &
383RegisterBankInfo::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(Val: 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 args&: ID, args&: Cost, args&: OperandsMapping, args&: NumOperands);
404 return *InstrMapping;
405}
406
407const RegisterBankInfo::InstructionMapping &
408RegisterBankInfo::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
415RegisterBankInfo::InstructionMappings
416RegisterBankInfo::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(Elt: &Mapping);
422 }
423
424 // Then the alternative mapping, if any.
425 InstructionMappings AltMappings = getInstrAlternativeMappings(MI);
426 append_range(C&: PossibleMappings, R&: 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
434RegisterBankInfo::InstructionMappings
435RegisterBankInfo::getInstrAlternativeMappings(const MachineInstr &MI) const {
436 // No alternative for MI.
437 return InstructionMappings();
438}
439
440void 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(i: 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(Reg: 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(Reg: OrigReg);
481 LLT NewTy = MRI.getType(Reg: 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(
488 TypeSize::isKnownLE(OrigTy.getSizeInBits(), NewTy.getSizeInBits()) &&
489 "Types with difference size cannot be handled by the default "
490 "mapping");
491 LLVM_DEBUG(dbgs() << "\nChange type of new opd from " << NewTy << " to "
492 << OrigTy);
493 MRI.setType(VReg: NewReg, Ty: OrigTy);
494 }
495 LLVM_DEBUG(dbgs() << '\n');
496 }
497}
498
499TypeSize RegisterBankInfo::getSizeInBits(Register Reg,
500 const MachineRegisterInfo &MRI,
501 const TargetRegisterInfo &TRI) const {
502 if (Reg.isPhysical()) {
503 // The size is not directly available for physical registers.
504 // Instead, we need to access a register class that contains Reg and
505 // get the size of that register class.
506 // Because this is expensive, we'll cache the register class by calling
507 auto *RC = getMinimalPhysRegClass(Reg, TRI);
508 assert(RC && "Expecting Register class");
509 return TRI.getRegSizeInBits(RC: *RC);
510 }
511 return TRI.getRegSizeInBits(Reg, MRI);
512}
513
514//------------------------------------------------------------------------------
515// Helper classes implementation.
516//------------------------------------------------------------------------------
517#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
518LLVM_DUMP_METHOD void RegisterBankInfo::PartialMapping::dump() const {
519 print(OS&: dbgs());
520 dbgs() << '\n';
521}
522#endif
523
524bool RegisterBankInfo::PartialMapping::verify(
525 const RegisterBankInfo &RBI) const {
526 assert(RegBank && "Register bank not set");
527 assert(Length && "Empty mapping");
528 assert((StartIdx <= getHighBitIdx()) && "Overflow, switch to APInt?");
529 // Check if the minimum width fits into RegBank.
530 assert(RBI.getMaximumSize(RegBank->getID()) >= Length &&
531 "Register bank too small for Mask");
532 return true;
533}
534
535void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const {
536 OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = ";
537 if (RegBank)
538 OS << *RegBank;
539 else
540 OS << "nullptr";
541}
542
543bool RegisterBankInfo::ValueMapping::partsAllUniform() const {
544 if (NumBreakDowns < 2)
545 return true;
546
547 const PartialMapping *First = begin();
548 for (const PartialMapping *Part = First + 1; Part != end(); ++Part) {
549 if (Part->Length != First->Length || Part->RegBank != First->RegBank)
550 return false;
551 }
552
553 return true;
554}
555
556bool RegisterBankInfo::ValueMapping::verify(const RegisterBankInfo &RBI,
557 TypeSize MeaningfulBitWidth) const {
558 assert(NumBreakDowns && "Value mapped nowhere?!");
559 unsigned OrigValueBitWidth = 0;
560 for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
561 // Check that each register bank is big enough to hold the partial value:
562 // this check is done by PartialMapping::verify
563 assert(PartMap.verify(RBI) && "Partial mapping is invalid");
564 // The original value should completely be mapped.
565 // Thus the maximum accessed index + 1 is the size of the original value.
566 OrigValueBitWidth =
567 std::max(a: OrigValueBitWidth, b: PartMap.getHighBitIdx() + 1);
568 }
569 assert((MeaningfulBitWidth.isScalable() ||
570 OrigValueBitWidth >= MeaningfulBitWidth) &&
571 "Meaningful bits not covered by the mapping");
572 APInt ValueMask(OrigValueBitWidth, 0);
573 for (const RegisterBankInfo::PartialMapping &PartMap : *this) {
574 // Check that the union of the partial mappings covers the whole value,
575 // without overlaps.
576 // The high bit is exclusive in the APInt API, thus getHighBitIdx + 1.
577 APInt PartMapMask = APInt::getBitsSet(numBits: OrigValueBitWidth, loBit: PartMap.StartIdx,
578 hiBit: PartMap.getHighBitIdx() + 1);
579 ValueMask ^= PartMapMask;
580 assert((ValueMask & PartMapMask) == PartMapMask &&
581 "Some partial mappings overlap");
582 }
583 assert(ValueMask.isAllOnes() && "Value is not fully mapped");
584 return true;
585}
586
587#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
588LLVM_DUMP_METHOD void RegisterBankInfo::ValueMapping::dump() const {
589 print(OS&: dbgs());
590 dbgs() << '\n';
591}
592#endif
593
594void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const {
595 OS << "#BreakDown: " << NumBreakDowns << " ";
596 bool IsFirst = true;
597 for (const PartialMapping &PartMap : *this) {
598 if (!IsFirst)
599 OS << ", ";
600 OS << '[' << PartMap << ']';
601 IsFirst = false;
602 }
603}
604
605bool RegisterBankInfo::InstructionMapping::verify(
606 const MachineInstr &MI) const {
607 // Check that all the register operands are properly mapped.
608 // Check the constructor invariant.
609 // For PHI, we only care about mapping the definition.
610 assert(NumOperands == (isCopyLike(MI) ? 1 : MI.getNumOperands()) &&
611 "NumOperands must match, see constructor");
612 assert(MI.getParent() && MI.getMF() &&
613 "MI must be connected to a MachineFunction");
614 const MachineFunction &MF = *MI.getMF();
615 const RegisterBankInfo *RBI = MF.getSubtarget().getRegBankInfo();
616 (void)RBI;
617 const MachineRegisterInfo &MRI = MF.getRegInfo();
618
619 for (unsigned Idx = 0; Idx < NumOperands; ++Idx) {
620 const MachineOperand &MO = MI.getOperand(i: Idx);
621 if (!MO.isReg()) {
622 assert(!getOperandMapping(Idx).isValid() &&
623 "We should not care about non-reg mapping");
624 continue;
625 }
626 Register Reg = MO.getReg();
627 if (!Reg)
628 continue;
629 LLT Ty = MRI.getType(Reg);
630 if (!Ty.isValid())
631 continue;
632 assert(getOperandMapping(Idx).isValid() &&
633 "We must have a mapping for reg operands");
634 const RegisterBankInfo::ValueMapping &MOMapping = getOperandMapping(i: Idx);
635 (void)MOMapping;
636 // Register size in bits.
637 // This size must match what the mapping expects.
638 assert(MOMapping.verify(*RBI, RBI->getSizeInBits(
639 Reg, MF.getRegInfo(),
640 *MF.getSubtarget().getRegisterInfo())) &&
641 "Value mapping is invalid");
642 }
643 return true;
644}
645
646#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
647LLVM_DUMP_METHOD void RegisterBankInfo::InstructionMapping::dump() const {
648 print(OS&: dbgs());
649 dbgs() << '\n';
650}
651#endif
652
653void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const {
654 OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: ";
655
656 for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
657 const ValueMapping &ValMapping = getOperandMapping(i: OpIdx);
658 if (OpIdx)
659 OS << ", ";
660 OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}';
661 }
662}
663
664const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1;
665
666RegisterBankInfo::OperandsMapper::OperandsMapper(
667 MachineInstr &MI, const InstructionMapping &InstrMapping,
668 MachineRegisterInfo &MRI)
669 : MRI(MRI), MI(MI), InstrMapping(InstrMapping) {
670 unsigned NumOpds = InstrMapping.getNumOperands();
671 OpToNewVRegIdx.resize(N: NumOpds, NV: OperandsMapper::DontKnowIdx);
672 assert(InstrMapping.verify(MI) && "Invalid mapping for MI");
673}
674
675iterator_range<SmallVectorImpl<Register>::iterator>
676RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) {
677 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
678 unsigned NumPartialVal =
679 getInstrMapping().getOperandMapping(i: OpIdx).NumBreakDowns;
680 int StartIdx = OpToNewVRegIdx[OpIdx];
681
682 if (StartIdx == OperandsMapper::DontKnowIdx) {
683 // This is the first time we try to access OpIdx.
684 // Create the cells that will hold all the partial values at the
685 // end of the list of NewVReg.
686 StartIdx = NewVRegs.size();
687 OpToNewVRegIdx[OpIdx] = StartIdx;
688 for (unsigned i = 0; i < NumPartialVal; ++i)
689 NewVRegs.push_back(Elt: 0);
690 }
691 SmallVectorImpl<Register>::iterator End =
692 getNewVRegsEnd(StartIdx, NumVal: NumPartialVal);
693
694 return make_range(x: &NewVRegs[StartIdx], y: End);
695}
696
697SmallVectorImpl<Register>::const_iterator
698RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
699 unsigned NumVal) const {
700 return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal);
701}
702SmallVectorImpl<Register>::iterator
703RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
704 unsigned NumVal) {
705 assert((NewVRegs.size() == StartIdx + NumVal ||
706 NewVRegs.size() > StartIdx + NumVal) &&
707 "NewVRegs too small to contain all the partial mapping");
708 return NewVRegs.size() <= StartIdx + NumVal ? NewVRegs.end()
709 : &NewVRegs[StartIdx + NumVal];
710}
711
712void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) {
713 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
714 iterator_range<SmallVectorImpl<Register>::iterator> NewVRegsForOpIdx =
715 getVRegsMem(OpIdx);
716 const ValueMapping &ValMapping = getInstrMapping().getOperandMapping(i: OpIdx);
717 const PartialMapping *PartMap = ValMapping.begin();
718 for (Register &NewVReg : NewVRegsForOpIdx) {
719 assert(PartMap != ValMapping.end() && "Out-of-bound access");
720 assert(NewVReg == 0 && "Register has already been created");
721 // The new registers are always bound to scalar with the right size.
722 // The actual type has to be set when the target does the mapping
723 // of the instruction.
724 // The rationale is that this generic code cannot guess how the
725 // target plans to split the input type.
726 NewVReg = MRI.createGenericVirtualRegister(Ty: LLT::scalar(SizeInBits: PartMap->Length));
727 MRI.setRegBank(Reg: NewVReg, RegBank: *PartMap->RegBank);
728 ++PartMap;
729 }
730}
731
732void RegisterBankInfo::OperandsMapper::setVRegs(unsigned OpIdx,
733 unsigned PartialMapIdx,
734 Register NewVReg) {
735 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
736 assert(getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns >
737 PartialMapIdx &&
738 "Out-of-bound access for partial mapping");
739 // Make sure the memory is initialized for that operand.
740 (void)getVRegsMem(OpIdx);
741 assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 &&
742 "This value is already set");
743 NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg;
744}
745
746iterator_range<SmallVectorImpl<Register>::const_iterator>
747RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx,
748 bool ForDebug) const {
749 (void)ForDebug;
750 assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
751 int StartIdx = OpToNewVRegIdx[OpIdx];
752
753 if (StartIdx == OperandsMapper::DontKnowIdx)
754 return make_range(x: NewVRegs.end(), y: NewVRegs.end());
755
756 unsigned PartMapSize =
757 getInstrMapping().getOperandMapping(i: OpIdx).NumBreakDowns;
758 SmallVectorImpl<Register>::const_iterator End =
759 getNewVRegsEnd(StartIdx, NumVal: PartMapSize);
760 iterator_range<SmallVectorImpl<Register>::const_iterator> Res =
761 make_range(x: &NewVRegs[StartIdx], y: End);
762#ifndef NDEBUG
763 for (Register VReg : Res)
764 assert((VReg || ForDebug) && "Some registers are uninitialized");
765#endif
766 return Res;
767}
768
769#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
770LLVM_DUMP_METHOD void RegisterBankInfo::OperandsMapper::dump() const {
771 print(OS&: dbgs(), ForDebug: true);
772 dbgs() << '\n';
773}
774#endif
775
776void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS,
777 bool ForDebug) const {
778 unsigned NumOpds = getInstrMapping().getNumOperands();
779 if (ForDebug) {
780 OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n';
781 // Print out the internal state of the index table.
782 OS << "Populated indices (CellNumber, IndexInNewVRegs): ";
783 bool IsFirst = true;
784 for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
785 if (OpToNewVRegIdx[Idx] != DontKnowIdx) {
786 if (!IsFirst)
787 OS << ", ";
788 OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')';
789 IsFirst = false;
790 }
791 }
792 OS << '\n';
793 } else
794 OS << "Mapping ID: " << getInstrMapping().getID() << ' ';
795
796 OS << "Operand Mapping: ";
797 // If we have a function, we can pretty print the name of the registers.
798 // Otherwise we will print the raw numbers.
799 const TargetRegisterInfo *TRI =
800 getMI().getParent() && getMI().getMF()
801 ? getMI().getMF()->getSubtarget().getRegisterInfo()
802 : nullptr;
803 bool IsFirst = true;
804 for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
805 if (OpToNewVRegIdx[Idx] == DontKnowIdx)
806 continue;
807 if (!IsFirst)
808 OS << ", ";
809 IsFirst = false;
810 OS << '(' << printReg(Reg: getMI().getOperand(i: Idx).getReg(), TRI) << ", [";
811 bool IsFirstNewVReg = true;
812 for (Register VReg : getVRegs(OpIdx: Idx)) {
813 if (!IsFirstNewVReg)
814 OS << ", ";
815 IsFirstNewVReg = false;
816 OS << printReg(Reg: VReg, TRI);
817 }
818 OS << "])";
819 }
820}
821

source code of llvm/lib/CodeGen/RegisterBankInfo.cpp