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