• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 //------------------------------------------------------------------------------
RegisterBankInfo(RegisterBank ** RegBanks,unsigned NumRegBanks)59 RegisterBankInfo::RegisterBankInfo(RegisterBank **RegBanks,
60                                    unsigned NumRegBanks)
61     : 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 }
69 
verify(const TargetRegisterInfo & TRI) const70 bool RegisterBankInfo::verify(const TargetRegisterInfo &TRI) const {
71 #ifndef NDEBUG
72   for (unsigned Idx = 0, End = getNumRegBanks(); Idx != End; ++Idx) {
73     const RegisterBank &RegBank = getRegBank(Idx);
74     assert(Idx == RegBank.getID() &&
75            "ID does not match the index in the array");
76     LLVM_DEBUG(dbgs() << "Verify " << RegBank << '\n');
77     assert(RegBank.verify(TRI) && "RegBank is invalid");
78   }
79 #endif // NDEBUG
80   return true;
81 }
82 
83 const RegisterBank *
getRegBank(unsigned Reg,const MachineRegisterInfo & MRI,const TargetRegisterInfo & TRI) const84 RegisterBankInfo::getRegBank(unsigned Reg, const MachineRegisterInfo &MRI,
85                              const TargetRegisterInfo &TRI) const {
86   if (TargetRegisterInfo::isPhysicalRegister(Reg))
87     return &getRegBankFromRegClass(getMinimalPhysRegClass(Reg, TRI));
88 
89   assert(Reg && "NoRegister does not have a register bank");
90   const RegClassOrRegBank &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
91   if (auto *RB = RegClassOrBank.dyn_cast<const RegisterBank *>())
92     return RB;
93   if (auto *RC = RegClassOrBank.dyn_cast<const TargetRegisterClass *>())
94     return &getRegBankFromRegClass(*RC);
95   return nullptr;
96 }
97 
98 const TargetRegisterClass &
getMinimalPhysRegClass(unsigned Reg,const TargetRegisterInfo & TRI) const99 RegisterBankInfo::getMinimalPhysRegClass(unsigned Reg,
100                                          const TargetRegisterInfo &TRI) const {
101   assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
102          "Reg must be a physreg");
103   const auto &RegRCIt = PhysRegMinimalRCs.find(Reg);
104   if (RegRCIt != PhysRegMinimalRCs.end())
105     return *RegRCIt->second;
106   const TargetRegisterClass *PhysRC = TRI.getMinimalPhysRegClass(Reg);
107   PhysRegMinimalRCs[Reg] = PhysRC;
108   return *PhysRC;
109 }
110 
getRegBankFromConstraints(const MachineInstr & MI,unsigned OpIdx,const TargetInstrInfo & TII,const TargetRegisterInfo & TRI) const111 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   const TargetRegisterClass *RC = MI.getRegClassConstraint(OpIdx, &TII, &TRI);
117 
118   if (!RC)
119     return nullptr;
120 
121   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   return &RegBank;
126 }
127 
constrainGenericRegister(unsigned Reg,const TargetRegisterClass & RC,MachineRegisterInfo & MRI)128 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   if (RegClassOrBank.is<const TargetRegisterClass *>())
134     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   if (RB && !RB->covers(RC))
139     return nullptr;
140 
141   // If nothing was set or the class is simply compatible, set it.
142   MRI.setRegClass(Reg, &RC);
143   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.
isCopyLike(const MachineInstr & MI)152 static bool isCopyLike(const MachineInstr &MI) {
153   return MI.isCopy() || MI.isPHI() ||
154          MI.getOpcode() == TargetOpcode::REG_SEQUENCE;
155 }
156 
157 const RegisterBankInfo::InstructionMapping &
getInstrMappingImpl(const MachineInstr & MI) const158 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   unsigned NumOperandsForMapping = IsCopyLike ? 1 : MI.getNumOperands();
166 
167   const MachineFunction &MF = *MI.getMF();
168   const TargetSubtargetInfo &STI = MF.getSubtarget();
169   const TargetRegisterInfo &TRI = *STI.getRegisterInfo();
170   const MachineRegisterInfo &MRI = MF.getRegInfo();
171   // We may need to query the instruction encoding to guess the mapping.
172   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   SmallVector<const ValueMapping *, 8> OperandsMapping(NumOperandsForMapping);
179   for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx;
180        ++OpIdx) {
181     const MachineOperand &MO = MI.getOperand(OpIdx);
182     if (!MO.isReg())
183       continue;
184     unsigned Reg = MO.getReg();
185     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     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     const RegisterBank *CurRegBank = IsCopyLike ? AltRegBank : nullptr;
197     if (!CurRegBank) {
198       // If this is a target specific instruction, we can deduce
199       // the register bank from the encoding constraints.
200       CurRegBank = getRegBankFromConstraints(MI, OpIdx, TII, TRI);
201       if (!CurRegBank) {
202         // All our attempts failed, give up.
203         CompleteMapping = false;
204 
205         if (!IsCopyLike)
206           // MI does not carry enough information to guess the mapping.
207           return getInvalidInstructionMapping();
208         continue;
209       }
210     }
211     const ValueMapping *ValMapping =
212         &getValueMapping(0, getSizeInBits(Reg, MRI, TRI), *CurRegBank);
213     if (IsCopyLike) {
214       OperandsMapping[0] = ValMapping;
215       CompleteMapping = true;
216       break;
217     }
218     OperandsMapping[OpIdx] = ValMapping;
219   }
220 
221   if (IsCopyLike && !CompleteMapping)
222     // No way to deduce the type from what we have.
223     return getInvalidInstructionMapping();
224 
225   assert(CompleteMapping && "Setting an uncomplete mapping");
226   return getInstructionMapping(
227       DefaultMappingID, /*Cost*/ 1,
228       /*OperandsMapping*/ getOperandsMapping(OperandsMapping),
229       NumOperandsForMapping);
230 }
231 
232 /// Hashing function for PartialMapping.
hashPartialMapping(unsigned StartIdx,unsigned Length,const RegisterBank * RegBank)233 static hash_code hashPartialMapping(unsigned StartIdx, unsigned Length,
234                                     const RegisterBank *RegBank) {
235   return hash_combine(StartIdx, Length, RegBank ? RegBank->getID() : 0);
236 }
237 
238 /// Overloaded version of hash_value for a PartialMapping.
239 hash_code
hash_value(const RegisterBankInfo::PartialMapping & PartMapping)240 llvm::hash_value(const RegisterBankInfo::PartialMapping &PartMapping) {
241   return hashPartialMapping(PartMapping.StartIdx, PartMapping.Length,
242                             PartMapping.RegBank);
243 }
244 
245 const RegisterBankInfo::PartialMapping &
getPartialMapping(unsigned StartIdx,unsigned Length,const RegisterBank & RegBank) const246 RegisterBankInfo::getPartialMapping(unsigned StartIdx, unsigned Length,
247                                     const RegisterBank &RegBank) const {
248   ++NumPartialMappingsAccessed;
249 
250   hash_code Hash = hashPartialMapping(StartIdx, Length, &RegBank);
251   const auto &It = MapOfPartialMappings.find(Hash);
252   if (It != MapOfPartialMappings.end())
253     return *It->second;
254 
255   ++NumPartialMappingsCreated;
256 
257   auto &PartMapping = MapOfPartialMappings[Hash];
258   PartMapping = llvm::make_unique<PartialMapping>(StartIdx, Length, RegBank);
259   return *PartMapping;
260 }
261 
262 const RegisterBankInfo::ValueMapping &
getValueMapping(unsigned StartIdx,unsigned Length,const RegisterBank & RegBank) const263 RegisterBankInfo::getValueMapping(unsigned StartIdx, unsigned Length,
264                                   const RegisterBank &RegBank) const {
265   return getValueMapping(&getPartialMapping(StartIdx, Length, RegBank), 1);
266 }
267 
268 static hash_code
hashValueMapping(const RegisterBankInfo::PartialMapping * BreakDown,unsigned NumBreakDowns)269 hashValueMapping(const RegisterBankInfo::PartialMapping *BreakDown,
270                  unsigned NumBreakDowns) {
271   if (LLVM_LIKELY(NumBreakDowns == 1))
272     return hash_value(*BreakDown);
273   SmallVector<size_t, 8> Hashes(NumBreakDowns);
274   for (unsigned Idx = 0; Idx != NumBreakDowns; ++Idx)
275     Hashes.push_back(hash_value(BreakDown[Idx]));
276   return hash_combine_range(Hashes.begin(), Hashes.end());
277 }
278 
279 const RegisterBankInfo::ValueMapping &
getValueMapping(const PartialMapping * BreakDown,unsigned NumBreakDowns) const280 RegisterBankInfo::getValueMapping(const PartialMapping *BreakDown,
281                                   unsigned NumBreakDowns) const {
282   ++NumValueMappingsAccessed;
283 
284   hash_code Hash = hashValueMapping(BreakDown, NumBreakDowns);
285   const auto &It = MapOfValueMappings.find(Hash);
286   if (It != MapOfValueMappings.end())
287     return *It->second;
288 
289   ++NumValueMappingsCreated;
290 
291   auto &ValMapping = MapOfValueMappings[Hash];
292   ValMapping = llvm::make_unique<ValueMapping>(BreakDown, NumBreakDowns);
293   return *ValMapping;
294 }
295 
296 template <typename Iterator>
297 const RegisterBankInfo::ValueMapping *
getOperandsMapping(Iterator Begin,Iterator End) const298 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   auto &Res = MapOfOperandsMappings[Hash];
306   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   Res = llvm::make_unique<ValueMapping[]>(std::distance(Begin, End));
317   unsigned Idx = 0;
318   for (Iterator It = Begin; It != End; ++It, ++Idx) {
319     const ValueMapping *ValMap = *It;
320     if (!ValMap)
321       continue;
322     Res[Idx] = *ValMap;
323   }
324   return Res.get();
325 }
326 
getOperandsMapping(const SmallVectorImpl<const RegisterBankInfo::ValueMapping * > & OpdsMapping) const327 const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
328     const SmallVectorImpl<const RegisterBankInfo::ValueMapping *> &OpdsMapping)
329     const {
330   return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
331 }
332 
getOperandsMapping(std::initializer_list<const RegisterBankInfo::ValueMapping * > OpdsMapping) const333 const RegisterBankInfo::ValueMapping *RegisterBankInfo::getOperandsMapping(
334     std::initializer_list<const RegisterBankInfo::ValueMapping *> OpdsMapping)
335     const {
336   return getOperandsMapping(OpdsMapping.begin(), OpdsMapping.end());
337 }
338 
339 static hash_code
hashInstructionMapping(unsigned ID,unsigned Cost,const RegisterBankInfo::ValueMapping * OperandsMapping,unsigned NumOperands)340 hashInstructionMapping(unsigned ID, unsigned Cost,
341                        const RegisterBankInfo::ValueMapping *OperandsMapping,
342                        unsigned NumOperands) {
343   return hash_combine(ID, Cost, OperandsMapping, NumOperands);
344 }
345 
346 const RegisterBankInfo::InstructionMapping &
getInstructionMappingImpl(bool IsInvalid,unsigned ID,unsigned Cost,const RegisterBankInfo::ValueMapping * OperandsMapping,unsigned NumOperands) const347 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       hashInstructionMapping(ID, Cost, OperandsMapping, NumOperands);
359   const auto &It = MapOfInstructionMappings.find(Hash);
360   if (It != MapOfInstructionMappings.end())
361     return *It->second;
362 
363   ++NumInstructionMappingsCreated;
364 
365   auto &InstrMapping = MapOfInstructionMappings[Hash];
366   if (IsInvalid)
367     InstrMapping = llvm::make_unique<InstructionMapping>();
368   else
369     InstrMapping = llvm::make_unique<InstructionMapping>(
370         ID, Cost, OperandsMapping, NumOperands);
371   return *InstrMapping;
372 }
373 
374 const RegisterBankInfo::InstructionMapping &
getInstrMapping(const MachineInstr & MI) const375 RegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
376   const RegisterBankInfo::InstructionMapping &Mapping = getInstrMappingImpl(MI);
377   if (Mapping.isValid())
378     return Mapping;
379   llvm_unreachable("The target must implement this");
380 }
381 
382 RegisterBankInfo::InstructionMappings
getInstrPossibleMappings(const MachineInstr & MI) const383 RegisterBankInfo::getInstrPossibleMappings(const MachineInstr &MI) const {
384   InstructionMappings PossibleMappings;
385   // Put the default mapping first.
386   PossibleMappings.push_back(&getInstrMapping(MI));
387   // Then the alternative mapping, if any.
388   InstructionMappings AltMappings = getInstrAlternativeMappings(MI);
389   for (const InstructionMapping *AltMapping : AltMappings)
390     PossibleMappings.push_back(AltMapping);
391 #ifndef NDEBUG
392   for (const InstructionMapping *Mapping : PossibleMappings)
393     assert(Mapping->verify(MI) && "Mapping is invalid");
394 #endif
395   return PossibleMappings;
396 }
397 
398 RegisterBankInfo::InstructionMappings
getInstrAlternativeMappings(const MachineInstr & MI) const399 RegisterBankInfo::getInstrAlternativeMappings(const MachineInstr &MI) const {
400   // No alternative for MI.
401   return InstructionMappings();
402 }
403 
applyDefaultMapping(const OperandsMapper & OpdMapper)404 void RegisterBankInfo::applyDefaultMapping(const OperandsMapper &OpdMapper) {
405   MachineInstr &MI = OpdMapper.getMI();
406   MachineRegisterInfo &MRI = OpdMapper.getMRI();
407   LLVM_DEBUG(dbgs() << "Applying default-like mapping\n");
408   for (unsigned OpIdx = 0,
409                 EndIdx = OpdMapper.getInstrMapping().getNumOperands();
410        OpIdx != EndIdx; ++OpIdx) {
411     LLVM_DEBUG(dbgs() << "OpIdx " << OpIdx);
412     MachineOperand &MO = MI.getOperand(OpIdx);
413     if (!MO.isReg()) {
414       LLVM_DEBUG(dbgs() << " is not a register, nothing to be done\n");
415       continue;
416     }
417     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         OpdMapper.getVRegs(OpIdx);
429     if (NewRegs.begin() == NewRegs.end()) {
430       LLVM_DEBUG(dbgs() << " has not been repaired, nothing to be done\n");
431       continue;
432     }
433     unsigned OrigReg = MO.getReg();
434     unsigned NewReg = *NewRegs.begin();
435     LLVM_DEBUG(dbgs() << " changed, replace " << printReg(OrigReg, nullptr));
436     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       MRI.setType(NewReg, OrigTy);
454     }
455     LLVM_DEBUG(dbgs() << '\n');
456   }
457 }
458 
getSizeInBits(unsigned Reg,const MachineRegisterInfo & MRI,const TargetRegisterInfo & TRI) const459 unsigned RegisterBankInfo::getSizeInBits(unsigned Reg,
460                                          const MachineRegisterInfo &MRI,
461                                          const TargetRegisterInfo &TRI) const {
462   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     auto *RC = &getMinimalPhysRegClass(Reg, TRI);
468     assert(RC && "Expecting Register class");
469     return TRI.getRegSizeInBits(*RC);
470   }
471   return TRI.getRegSizeInBits(Reg, MRI);
472 }
473 
474 //------------------------------------------------------------------------------
475 // Helper classes implementation.
476 //------------------------------------------------------------------------------
477 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const478 LLVM_DUMP_METHOD void RegisterBankInfo::PartialMapping::dump() const {
479   print(dbgs());
480   dbgs() << '\n';
481 }
482 #endif
483 
verify() const484 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   return true;
491 }
492 
print(raw_ostream & OS) const493 void RegisterBankInfo::PartialMapping::print(raw_ostream &OS) const {
494   OS << "[" << StartIdx << ", " << getHighBitIdx() << "], RegBank = ";
495   if (RegBank)
496     OS << *RegBank;
497   else
498     OS << "nullptr";
499 }
500 
verify(unsigned MeaningfulBitWidth) const501 bool RegisterBankInfo::ValueMapping::verify(unsigned MeaningfulBitWidth) const {
502   assert(NumBreakDowns && "Value mapped nowhere?!");
503   unsigned OrigValueBitWidth = 0;
504   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     OrigValueBitWidth =
511         std::max(OrigValueBitWidth, PartMap.getHighBitIdx() + 1);
512   }
513   assert(OrigValueBitWidth >= MeaningfulBitWidth &&
514          "Meaningful bits not covered by the mapping");
515   APInt ValueMask(OrigValueBitWidth, 0);
516   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                                           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   return true;
528 }
529 
530 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const531 LLVM_DUMP_METHOD void RegisterBankInfo::ValueMapping::dump() const {
532   print(dbgs());
533   dbgs() << '\n';
534 }
535 #endif
536 
print(raw_ostream & OS) const537 void RegisterBankInfo::ValueMapping::print(raw_ostream &OS) const {
538   OS << "#BreakDown: " << NumBreakDowns << " ";
539   bool IsFirst = true;
540   for (const PartialMapping &PartMap : *this) {
541     if (!IsFirst)
542       OS << ", ";
543     OS << '[' << PartMap << ']';
544     IsFirst = false;
545   }
546 }
547 
verify(const MachineInstr & MI) const548 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   const MachineFunction &MF = *MI.getMF();
558   const RegisterBankInfo *RBI = MF.getSubtarget().getRegBankInfo();
559   (void)RBI;
560 
561   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   return true;
582 }
583 
584 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const585 LLVM_DUMP_METHOD void RegisterBankInfo::InstructionMapping::dump() const {
586   print(dbgs());
587   dbgs() << '\n';
588 }
589 #endif
590 
print(raw_ostream & OS) const591 void RegisterBankInfo::InstructionMapping::print(raw_ostream &OS) const {
592   OS << "ID: " << getID() << " Cost: " << getCost() << " Mapping: ";
593 
594   for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
595     const ValueMapping &ValMapping = getOperandMapping(OpIdx);
596     if (OpIdx)
597       OS << ", ";
598     OS << "{ Idx: " << OpIdx << " Map: " << ValMapping << '}';
599   }
600 }
601 
602 const int RegisterBankInfo::OperandsMapper::DontKnowIdx = -1;
603 
OperandsMapper(MachineInstr & MI,const InstructionMapping & InstrMapping,MachineRegisterInfo & MRI)604 RegisterBankInfo::OperandsMapper::OperandsMapper(
605     MachineInstr &MI, const InstructionMapping &InstrMapping,
606     MachineRegisterInfo &MRI)
607     : MRI(MRI), MI(MI), InstrMapping(InstrMapping) {
608   unsigned NumOpds = InstrMapping.getNumOperands();
609   OpToNewVRegIdx.resize(NumOpds, OperandsMapper::DontKnowIdx);
610   assert(InstrMapping.verify(MI) && "Invalid mapping for MI");
611 }
612 
613 iterator_range<SmallVectorImpl<unsigned>::iterator>
getVRegsMem(unsigned OpIdx)614 RegisterBankInfo::OperandsMapper::getVRegsMem(unsigned OpIdx) {
615   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
616   unsigned NumPartialVal =
617       getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
618   int StartIdx = OpToNewVRegIdx[OpIdx];
619 
620   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     StartIdx = NewVRegs.size();
625     OpToNewVRegIdx[OpIdx] = StartIdx;
626     for (unsigned i = 0; i < NumPartialVal; ++i)
627       NewVRegs.push_back(0);
628   }
629   SmallVectorImpl<unsigned>::iterator End =
630       getNewVRegsEnd(StartIdx, NumPartialVal);
631 
632   return make_range(&NewVRegs[StartIdx], End);
633 }
634 
635 SmallVectorImpl<unsigned>::const_iterator
getNewVRegsEnd(unsigned StartIdx,unsigned NumVal) const636 RegisterBankInfo::OperandsMapper::getNewVRegsEnd(unsigned StartIdx,
637                                                  unsigned NumVal) const {
638   return const_cast<OperandsMapper *>(this)->getNewVRegsEnd(StartIdx, NumVal);
639 }
640 SmallVectorImpl<unsigned>::iterator
getNewVRegsEnd(unsigned StartIdx,unsigned NumVal)641 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   return NewVRegs.size() <= StartIdx + NumVal ? NewVRegs.end()
647                                               : &NewVRegs[StartIdx + NumVal];
648 }
649 
createVRegs(unsigned OpIdx)650 void RegisterBankInfo::OperandsMapper::createVRegs(unsigned OpIdx) {
651   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
652   iterator_range<SmallVectorImpl<unsigned>::iterator> NewVRegsForOpIdx =
653       getVRegsMem(OpIdx);
654   const ValueMapping &ValMapping = getInstrMapping().getOperandMapping(OpIdx);
655   const PartialMapping *PartMap = ValMapping.begin();
656   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     NewVReg = MRI.createGenericVirtualRegister(LLT::scalar(PartMap->Length));
665     MRI.setRegBank(NewVReg, *PartMap->RegBank);
666     ++PartMap;
667   }
668 }
669 
setVRegs(unsigned OpIdx,unsigned PartialMapIdx,unsigned NewVReg)670 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   (void)getVRegsMem(OpIdx);
679   assert(NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] == 0 &&
680          "This value is already set");
681   NewVRegs[OpToNewVRegIdx[OpIdx] + PartialMapIdx] = NewVReg;
682 }
683 
684 iterator_range<SmallVectorImpl<unsigned>::const_iterator>
getVRegs(unsigned OpIdx,bool ForDebug) const685 RegisterBankInfo::OperandsMapper::getVRegs(unsigned OpIdx,
686                                            bool ForDebug) const {
687   (void)ForDebug;
688   assert(OpIdx < getInstrMapping().getNumOperands() && "Out-of-bound access");
689   int StartIdx = OpToNewVRegIdx[OpIdx];
690 
691   if (StartIdx == OperandsMapper::DontKnowIdx)
692     return make_range(NewVRegs.end(), NewVRegs.end());
693 
694   unsigned PartMapSize =
695       getInstrMapping().getOperandMapping(OpIdx).NumBreakDowns;
696   SmallVectorImpl<unsigned>::const_iterator End =
697       getNewVRegsEnd(StartIdx, PartMapSize);
698   iterator_range<SmallVectorImpl<unsigned>::const_iterator> Res =
699       make_range(&NewVRegs[StartIdx], End);
700 #ifndef NDEBUG
701   for (unsigned VReg : Res)
702     assert((VReg || ForDebug) && "Some registers are uninitialized");
703 #endif
704   return Res;
705 }
706 
707 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const708 LLVM_DUMP_METHOD void RegisterBankInfo::OperandsMapper::dump() const {
709   print(dbgs(), true);
710   dbgs() << '\n';
711 }
712 #endif
713 
print(raw_ostream & OS,bool ForDebug) const714 void RegisterBankInfo::OperandsMapper::print(raw_ostream &OS,
715                                              bool ForDebug) const {
716   unsigned NumOpds = getInstrMapping().getNumOperands();
717   if (ForDebug) {
718     OS << "Mapping for " << getMI() << "\nwith " << getInstrMapping() << '\n';
719     // Print out the internal state of the index table.
720     OS << "Populated indices (CellNumber, IndexInNewVRegs): ";
721     bool IsFirst = true;
722     for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
723       if (OpToNewVRegIdx[Idx] != DontKnowIdx) {
724         if (!IsFirst)
725           OS << ", ";
726         OS << '(' << Idx << ", " << OpToNewVRegIdx[Idx] << ')';
727         IsFirst = false;
728       }
729     }
730     OS << '\n';
731   } else
732     OS << "Mapping ID: " << getInstrMapping().getID() << ' ';
733 
734   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       getMI().getParent() && getMI().getMF()
739           ? getMI().getMF()->getSubtarget().getRegisterInfo()
740           : nullptr;
741   bool IsFirst = true;
742   for (unsigned Idx = 0; Idx != NumOpds; ++Idx) {
743     if (OpToNewVRegIdx[Idx] == DontKnowIdx)
744       continue;
745     if (!IsFirst)
746       OS << ", ";
747     IsFirst = false;
748     OS << '(' << printReg(getMI().getOperand(Idx).getReg(), TRI) << ", [";
749     bool IsFirstNewVReg = true;
750     for (unsigned VReg : getVRegs(Idx)) {
751       if (!IsFirstNewVReg)
752         OS << ", ";
753       IsFirstNewVReg = false;
754       OS << printReg(VReg, TRI);
755     }
756     OS << "])";
757   }
758 }
759