1 //==-- llvm/CodeGen/GlobalISel/RegisterBankInfo.h ----------------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// \file This file declares the API for the register bank info.
11 /// This API is responsible for handling the register banks.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKINFO_H
16 #define LLVM_CODEGEN_GLOBALISEL_REGBANKINFO_H
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
21 #include "llvm/CodeGen/MachineValueType.h" // For SimpleValueType.
22 #include "llvm/Support/ErrorHandling.h"
25 #include <memory> // For unique_ptr.
29 class MachineRegisterInfo;
30 class TargetInstrInfo;
31 class TargetRegisterInfo;
34 /// Holds all the information related to register banks.
35 class RegisterBankInfo {
37 /// Helper struct that represents how a value is partially mapped
39 /// The StartIdx and Length represent what region of the orginal
40 /// value this partial mapping covers.
41 /// This can be represented as a Mask of contiguous bit starting
42 /// at StartIdx bit and spanning Length bits.
43 /// StartIdx is the number of bits from the less significant bits.
44 struct PartialMapping {
45 /// Number of bits at which this partial mapping starts in the
46 /// original value. The bits are counted from less significant
47 /// bits to most significant bits.
49 /// Length of this mapping in bits. This is how many bits this
50 /// partial mapping covers in the original value:
51 /// from StartIdx to StartIdx + Length -1.
53 /// Register bank where the partial value lives.
54 const RegisterBank *RegBank;
56 PartialMapping() = default;
58 /// Provide a shortcut for quickly building PartialMapping.
59 PartialMapping(unsigned StartIdx, unsigned Length,
60 const RegisterBank &RegBank)
61 : StartIdx(StartIdx), Length(Length), RegBank(&RegBank) {}
63 /// \return the index of in the original value of the most
64 /// significant bit that this partial mapping covers.
65 unsigned getHighBitIdx() const { return StartIdx + Length - 1; }
67 /// Print this partial mapping on dbgs() stream.
70 /// Print this partial mapping on \p OS;
71 void print(raw_ostream &OS) const;
73 /// Check that the Mask is compatible with the RegBank.
74 /// Indeed, if the RegBank cannot accomadate the "active bits" of the mask,
75 /// there is no way this mapping is valid.
77 /// \note This method does not check anything when assertions are disabled.
79 /// \return True is the check was successful.
83 /// Helper struct that represents how a value is mapped through
84 /// different register banks.
86 /// How the value is broken down between the different register banks.
87 SmallVector<PartialMapping, 2> BreakDown;
89 /// Verify that this mapping makes sense for a value of \p ExpectedBitWidth.
90 /// \note This method does not check anything when assertions are disabled.
92 /// \return True is the check was successful.
93 bool verify(unsigned ExpectedBitWidth) const;
95 /// Print this on dbgs() stream.
98 /// Print this on \p OS;
99 void print(raw_ostream &OS) const;
102 /// Helper class that represents how the value of an instruction may be
103 /// mapped and what is the related cost of such mapping.
104 class InstructionMapping {
105 /// Identifier of the mapping.
106 /// This is used to communicate between the target and the optimizers
107 /// which mapping should be realized.
109 /// Cost of this mapping.
111 /// Mapping of all the operands.
112 std::unique_ptr<ValueMapping[]> OperandsMapping;
113 /// Number of operands.
114 unsigned NumOperands;
116 ValueMapping &getOperandMapping(unsigned i) {
117 assert(i < getNumOperands() && "Out of bound operand");
118 return OperandsMapping[i];
122 /// Constructor for the mapping of an instruction.
123 /// \p NumOperands must be equal to number of all the operands of
124 /// the related instruction.
125 /// The rationale is that it is more efficient for the optimizers
126 /// to be able to assume that the mapping of the ith operand is
129 /// \pre ID != InvalidMappingID
130 InstructionMapping(unsigned ID, unsigned Cost, unsigned NumOperands)
131 : ID(ID), Cost(Cost), NumOperands(NumOperands) {
132 assert(getID() != InvalidMappingID &&
133 "Use the default constructor for invalid mapping");
134 OperandsMapping.reset(new ValueMapping[getNumOperands()]);
137 /// Default constructor.
138 /// Use this constructor to express that the mapping is invalid.
139 InstructionMapping() : ID(InvalidMappingID), Cost(0), NumOperands(0) {}
142 unsigned getCost() const { return Cost; }
145 unsigned getID() const { return ID; }
147 /// Get the number of operands.
148 unsigned getNumOperands() const { return NumOperands; }
150 /// Get the value mapping of the ith operand.
151 const ValueMapping &getOperandMapping(unsigned i) const {
152 return const_cast<InstructionMapping *>(this)->getOperandMapping(i);
155 /// Get the value mapping of the ith operand.
156 void setOperandMapping(unsigned i, const ValueMapping &ValMapping) {
157 getOperandMapping(i) = ValMapping;
160 /// Check whether this object is valid.
161 /// This is a lightweight check for obvious wrong instance.
162 bool isValid() const { return getID() != InvalidMappingID; }
164 /// Set the operand mapping for the \p OpIdx-th operand.
165 /// The mapping will consist of only one element in the break down list.
166 /// This element will map to \p RegBank and fully define a mask, whose
167 /// bitwidth matches the size of \p MaskSize.
168 void setOperandMapping(unsigned OpIdx, unsigned MaskSize,
169 const RegisterBank &RegBank);
171 /// Verifiy that this mapping makes sense for \p MI.
172 /// \pre \p MI must be connected to a MachineFunction.
174 /// \note This method does not check anything when assertions are disabled.
176 /// \return True is the check was successful.
177 bool verify(const MachineInstr &MI) const;
179 /// Print this on dbgs() stream.
182 /// Print this on \p OS;
183 void print(raw_ostream &OS) const;
186 /// Convenient type to represent the alternatives for mapping an
188 /// \todo When we move to TableGen this should be an array ref.
189 typedef SmallVector<InstructionMapping, 4> InstructionMappings;
191 /// Helper class use to get/create the virtual registers that will be used
192 /// to replace the MachineOperand when applying a mapping.
193 class OperandsMapper {
194 /// The OpIdx-th cell contains the index in NewVRegs where the VRegs of the
195 /// OpIdx-th operand starts. -1 means we do not have such mapping yet.
196 std::unique_ptr<int[]> OpToNewVRegIdx;
197 /// Hold the registers that will be used to map MI with InstrMapping.
198 SmallVector<unsigned, 8> NewVRegs;
199 /// Current MachineRegisterInfo, used to create new virtual registers.
200 MachineRegisterInfo &MRI;
201 /// Instruction being remapped.
203 /// New mapping of the instruction.
204 const InstructionMapping &InstrMapping;
206 /// Constant value identifying that the index in OpToNewVRegIdx
207 /// for an operand has not been set yet.
208 static const int DontKnowIdx;
210 /// Get the range in NewVRegs to store all the partial
211 /// values for the \p OpIdx-th operand.
213 /// \return The iterator range for the space created.
215 /// \pre getMI().getOperand(OpIdx).isReg()
216 iterator_range<SmallVectorImpl<unsigned>::iterator>
217 getVRegsMem(unsigned OpIdx);
219 /// Get the end iterator for a range starting at \p StartIdx and
220 /// spannig \p NumVal in NewVRegs.
221 /// \pre StartIdx + NumVal <= NewVRegs.size()
222 SmallVectorImpl<unsigned>::const_iterator
223 getNewVRegsEnd(unsigned StartIdx, unsigned NumVal) const;
224 SmallVectorImpl<unsigned>::iterator getNewVRegsEnd(unsigned StartIdx,
228 /// Create an OperandsMapper that will hold the information to apply \p
229 /// InstrMapping to \p MI.
230 /// \pre InstrMapping.verify(MI)
231 OperandsMapper(MachineInstr &MI, const InstructionMapping &InstrMapping,
232 MachineRegisterInfo &MRI);
236 /// The MachineInstr being remapped.
237 MachineInstr &getMI() const { return MI; }
239 /// The final mapping of the instruction.
240 const InstructionMapping &getInstrMapping() const { return InstrMapping; }
243 /// Create as many new virtual registers as needed for the mapping of the \p
244 /// OpIdx-th operand.
245 /// The number of registers is determined by the number of breakdown for the
246 /// related operand in the instruction mapping.
248 /// \pre getMI().getOperand(OpIdx).isReg()
250 /// \post All the partial mapping of the \p OpIdx-th operand have been
251 /// assigned a new virtual register.
252 void createVRegs(unsigned OpIdx);
254 /// Set the virtual register of the \p PartialMapIdx-th partial mapping of
255 /// the OpIdx-th operand to \p NewVReg.
257 /// \pre getMI().getOperand(OpIdx).isReg()
258 /// \pre getInstrMapping().getOperandMapping(OpIdx).BreakDown.size() >
262 /// \post the \p PartialMapIdx-th register of the value mapping of the \p
263 /// OpIdx-th operand has been set.
264 void setVRegs(unsigned OpIdx, unsigned PartialMapIdx, unsigned NewVReg);
266 /// Get all the virtual registers required to map the \p OpIdx-th operand of
269 /// This return an empty range when createVRegs or setVRegs has not been
271 /// The iterator may be invalidated by a call to setVRegs or createVRegs.
273 /// When \p ForDebug is true, we will not check that the list of new virtual
274 /// registers does not contain uninitialized values.
276 /// \pre getMI().getOperand(OpIdx).isReg()
277 /// \pre ForDebug || All partial mappings have been set a register
278 iterator_range<SmallVectorImpl<unsigned>::const_iterator>
279 getVRegs(unsigned OpIdx, bool ForDebug = false) const;
281 /// Print this operands mapper on dbgs() stream.
284 /// Print this operands mapper on \p OS stream.
285 void print(raw_ostream &OS, bool ForDebug = false) const;
289 /// Hold the set of supported register banks.
290 std::unique_ptr<RegisterBank[]> RegBanks;
291 /// Total number of register banks.
292 unsigned NumRegBanks;
294 /// Mapping from MVT::SimpleValueType to register banks.
295 std::unique_ptr<const RegisterBank *[]> VTToRegBank;
297 /// Create a RegisterBankInfo that can accomodate up to \p NumRegBanks
298 /// RegisterBank instances.
300 /// \note For the verify method to succeed all the \p NumRegBanks
301 /// must be initialized by createRegisterBank and updated with
302 /// addRegBankCoverage RegisterBank.
303 RegisterBankInfo(unsigned NumRegBanks);
305 /// This constructor is meaningless.
306 /// It just provides a default constructor that can be used at link time
307 /// when GlobalISel is not built.
308 /// That way, targets can still inherit from this class without doing
309 /// crazy gymnastic to avoid link time failures.
310 /// \note That works because the constructor is inlined.
312 llvm_unreachable("This constructor should not be executed");
315 /// Create a new register bank with the given parameter and add it
317 /// \pre \p ID must not already be used.
318 /// \pre \p ID < NumRegBanks.
319 void createRegisterBank(unsigned ID, const char *Name);
321 /// Add \p RCId to the set of register class that the register bank,
322 /// identified \p ID, covers.
323 /// This method transitively adds all the sub classes and the subreg-classes
324 /// of \p RCId to the set of covered register classes.
325 /// It also adjusts the size of the register bank to reflect the maximal
326 /// size of a value that can be hold into that register bank.
328 /// If \p AddTypeMapping is true, this method also records what types can
329 /// be mapped to \p ID. Although this done by default, targets may want to
330 /// disable it, espicially if a given type may be mapped on different
331 /// register bank. Indeed, in such case, this method only records the
332 /// first register bank where the type matches.
333 /// This information is only used to provide default mapping
334 /// (see getInstrMappingImpl).
336 /// \note This method does *not* add the super classes of \p RCId.
337 /// The rationale is if \p ID covers the registers of \p RCId, that
338 /// does not necessarily mean that \p ID covers the set of registers
339 /// of RCId's superclasses.
340 /// This method does *not* add the superreg classes as well for consistents.
341 /// The expected use is to add the coverage top-down with respect to the
342 /// register hierarchy.
344 /// \todo TableGen should just generate the BitSet vector for us.
345 void addRegBankCoverage(unsigned ID, unsigned RCId,
346 const TargetRegisterInfo &TRI,
347 bool AddTypeMapping = true);
349 /// Get the register bank identified by \p ID.
350 RegisterBank &getRegBank(unsigned ID) {
351 assert(ID < getNumRegBanks() && "Accessing an unknown register bank");
355 /// Get the register bank that has been recorded to cover \p SVT.
356 const RegisterBank *getRegBankForType(MVT::SimpleValueType SVT) const {
359 assert(SVT < MVT::SimpleValueType::LAST_VALUETYPE && "Out-of-bound access");
360 return VTToRegBank.get()[SVT];
363 /// Record \p RegBank as the register bank that covers \p SVT.
364 /// If a record was already set for \p SVT, the mapping is not
365 /// updated, unless \p Force == true
367 /// \post if getRegBankForType(SVT)\@pre == nullptr then
368 /// getRegBankForType(SVT) == &RegBank
369 /// \post if Force == true then getRegBankForType(SVT) == &RegBank
370 void recordRegBankForType(const RegisterBank &RegBank,
371 MVT::SimpleValueType SVT, bool Force = false) {
374 new const RegisterBank *[MVT::SimpleValueType::LAST_VALUETYPE]);
375 std::fill(&VTToRegBank[0],
376 &VTToRegBank[MVT::SimpleValueType::LAST_VALUETYPE], nullptr);
378 assert(SVT < MVT::SimpleValueType::LAST_VALUETYPE && "Out-of-bound access");
379 // If we want to override the mapping or the mapping does not exits yet,
380 // set the register bank for SVT.
381 if (Force || !getRegBankForType(SVT))
382 VTToRegBank.get()[SVT] = &RegBank;
385 /// Try to get the mapping of \p MI.
386 /// See getInstrMapping for more details on what a mapping represents.
388 /// Unlike getInstrMapping the returned InstructionMapping may be invalid
389 /// (isValid() == false).
390 /// This means that the target independent code is not smart enough
391 /// to get the mapping of \p MI and thus, the target has to provide the
392 /// information for \p MI.
394 /// This implementation is able to get the mapping of:
395 /// - Target specific instructions by looking at the encoding constraints.
396 /// - Any instruction if all the register operands are already been assigned
397 /// a register, a register class, or a register bank.
398 /// - Copies and phis if at least one of the operand has been assigned a
399 /// register, a register class, or a register bank.
400 /// In other words, this method will likely fail to find a mapping for
401 /// any generic opcode that has not been lowered by target specific code.
402 InstructionMapping getInstrMappingImpl(const MachineInstr &MI) const;
404 /// Get the register bank for the \p OpIdx-th operand of \p MI form
405 /// the encoding constraints, if any.
407 /// \return A register bank that covers the register class of the
408 /// related encoding constraints or nullptr if \p MI did not provide
409 /// enough information to deduce it.
411 getRegBankFromConstraints(const MachineInstr &MI, unsigned OpIdx,
412 const TargetInstrInfo &TII,
413 const TargetRegisterInfo &TRI) const;
415 /// Helper method to apply something that is like the default mapping.
416 /// Basically, that means that \p OpdMapper.getMI() is left untouched
417 /// aside from the reassignment of the register operand that have been
419 /// If the mapping of one of the operand spans several registers, this
420 /// method will abort as this is not like a default mapping anymore.
422 /// \pre For OpIdx in {0..\p OpdMapper.getMI().getNumOperands())
423 /// the range OpdMapper.getVRegs(OpIdx) is empty or of size 1.
424 static void applyDefaultMapping(const OperandsMapper &OpdMapper);
426 /// See ::applyMapping.
427 virtual void applyMappingImpl(const OperandsMapper &OpdMapper) const {
428 llvm_unreachable("The target has to implement that part");
432 virtual ~RegisterBankInfo() {}
434 /// Get the register bank identified by \p ID.
435 const RegisterBank &getRegBank(unsigned ID) const {
436 return const_cast<RegisterBankInfo *>(this)->getRegBank(ID);
439 /// Get the register bank of \p Reg.
440 /// If Reg has not been assigned a register, a register class,
441 /// or a register bank, then this returns nullptr.
443 /// \pre Reg != 0 (NoRegister)
444 const RegisterBank *getRegBank(unsigned Reg, const MachineRegisterInfo &MRI,
445 const TargetRegisterInfo &TRI) const;
447 /// Get the total number of register banks.
448 unsigned getNumRegBanks() const { return NumRegBanks; }
450 /// Get a register bank that covers \p RC.
452 /// \pre \p RC is a user-defined register class (as opposed as one
453 /// generated by TableGen).
455 /// \note The mapping RC -> RegBank could be built while adding the
456 /// coverage for the register banks. However, we do not do it, because,
457 /// at least for now, we only need this information for register classes
458 /// that are used in the description of instruction. In other words,
459 /// there are just a handful of them and we do not want to waste space.
461 /// \todo This should be TableGen'ed.
462 virtual const RegisterBank &
463 getRegBankFromRegClass(const TargetRegisterClass &RC) const {
464 llvm_unreachable("The target must override this method");
467 /// Get the cost of a copy from \p B to \p A, or put differently,
468 /// get the cost of A = COPY B. Since register banks may cover
469 /// different size, \p Size specifies what will be the size in bits
470 /// that will be copied around.
472 /// \note Since this is a copy, both registers have the same size.
473 virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B,
474 unsigned Size) const {
475 // Optimistically assume that copies are coalesced. I.e., when
476 // they are on the same bank, they are free.
477 // Otherwise assume a non-zero cost of 1. The targets are supposed
478 // to override that properly anyway if they care.
482 /// Identifier used when the related instruction mapping instance
483 /// is generated by target independent code.
484 /// Make sure not to use that identifier to avoid possible collision.
485 static const unsigned DefaultMappingID;
487 /// Identifier used when the related instruction mapping instance
488 /// is generated by the default constructor.
489 /// Make sure not to use that identifier.
490 static const unsigned InvalidMappingID;
492 /// Get the mapping of the different operands of \p MI
493 /// on the register bank.
494 /// This mapping should be the direct translation of \p MI.
495 /// In other words, when \p MI is mapped with the returned mapping,
496 /// only the register banks of the operands of \p MI need to be updated.
497 /// In particular, neither the opcode or the type of \p MI needs to be
498 /// updated for this direct mapping.
500 /// The target independent implementation gives a mapping based on
501 /// the register classes for the target specific opcode.
502 /// It uses the ID RegisterBankInfo::DefaultMappingID for that mapping.
503 /// Make sure you do not use that ID for the alternative mapping
504 /// for MI. See getInstrAlternativeMappings for the alternative
507 /// For instance, if \p MI is a vector add, the mapping should
508 /// not be a scalarization of the add.
510 /// \post returnedVal.verify(MI).
512 /// \note If returnedVal does not verify MI, this would probably mean
513 /// that the target does not support that instruction.
514 virtual InstructionMapping getInstrMapping(const MachineInstr &MI) const;
516 /// Get the alternative mappings for \p MI.
517 /// Alternative in the sense different from getInstrMapping.
518 virtual InstructionMappings
519 getInstrAlternativeMappings(const MachineInstr &MI) const;
521 /// Get the possible mapping for \p MI.
522 /// A mapping defines where the different operands may live and at what cost.
523 /// For instance, let us consider:
524 /// v0(16) = G_ADD <2 x i8> v1, v2
525 /// The possible mapping could be:
527 /// {/*ID*/VectorAdd, /*Cost*/1, /*v0*/{(0xFFFF, VPR)}, /*v1*/{(0xFFFF, VPR)},
528 /// /*v2*/{(0xFFFF, VPR)}}
529 /// {/*ID*/ScalarAddx2, /*Cost*/2, /*v0*/{(0x00FF, GPR),(0xFF00, GPR)},
530 /// /*v1*/{(0x00FF, GPR),(0xFF00, GPR)},
531 /// /*v2*/{(0x00FF, GPR),(0xFF00, GPR)}}
533 /// \note The first alternative of the returned mapping should be the
534 /// direct translation of \p MI current form.
536 /// \post !returnedVal.empty().
537 InstructionMappings getInstrPossibleMappings(const MachineInstr &MI) const;
539 /// Apply \p OpdMapper.getInstrMapping() to \p OpdMapper.getMI().
540 /// After this call \p OpdMapper.getMI() may not be valid anymore.
541 /// \p OpdMapper.getInstrMapping().getID() carries the information of
542 /// what has been chosen to map \p OpdMapper.getMI(). This ID is set
543 /// by the various getInstrXXXMapping method.
545 /// Therefore, getting the mapping and applying it should be kept in
547 void applyMapping(const OperandsMapper &OpdMapper) const {
548 // The only mapping we know how to handle is the default mapping.
549 if (OpdMapper.getInstrMapping().getID() == DefaultMappingID)
550 return applyDefaultMapping(OpdMapper);
551 // For other mapping, the target needs to do the right thing.
552 // If that means calling applyDefaultMapping, fine, but this
553 // must be explicitly stated.
554 applyMappingImpl(OpdMapper);
557 /// Get the size in bits of \p Reg.
558 /// Utility method to get the size of any registers. Unlike
559 /// MachineRegisterInfo::getSize, the register does not need to be a
560 /// virtual register.
562 /// \pre \p Reg != 0 (NoRegister).
563 static unsigned getSizeInBits(unsigned Reg, const MachineRegisterInfo &MRI,
564 const TargetRegisterInfo &TRI);
566 /// Check that information hold by this instance make sense for the
569 /// \note This method does not check anything when assertions are disabled.
571 /// \return True is the check was successful.
572 bool verify(const TargetRegisterInfo &TRI) const;
576 operator<<(raw_ostream &OS,
577 const RegisterBankInfo::PartialMapping &PartMapping) {
578 PartMapping.print(OS);
583 operator<<(raw_ostream &OS, const RegisterBankInfo::ValueMapping &ValMapping) {
584 ValMapping.print(OS);
589 operator<<(raw_ostream &OS,
590 const RegisterBankInfo::InstructionMapping &InstrMapping) {
591 InstrMapping.print(OS);
596 operator<<(raw_ostream &OS, const RegisterBankInfo::OperandsMapper &OpdMapper) {
597 OpdMapper.print(OS, /*ForDebug*/ false);
600 } // End namespace llvm.