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