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