1//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- 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//
9// This file defines structures to encapsulate information gleaned from the
10// target register and register class definitions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H
15#define LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H
16
17#include "CodeGenHwModes.h"
18#include "InfoByHwMode.h"
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/SparseBitVector.h"
26#include "llvm/ADT/StringMap.h"
27#include "llvm/ADT/StringRef.h"
28#include "llvm/ADT/StringSet.h"
29#include "llvm/MC/LaneBitmask.h"
30#include "llvm/Support/ErrorHandling.h"
31#include "llvm/TableGen/Record.h"
32#include "llvm/TableGen/SetTheory.h"
33#include <cassert>
34#include <cstdint>
35#include <deque>
36#include <functional>
37#include <list>
38#include <map>
39#include <memory>
40#include <optional>
41#include <string>
42#include <utility>
43#include <vector>
44
45namespace llvm {
46
47class CodeGenRegBank;
48
49/// Used to encode a step in a register lane mask transformation.
50/// Mask the bits specified in Mask, then rotate them Rol bits to the left
51/// assuming a wraparound at 32bits.
52struct MaskRolPair {
53 LaneBitmask Mask;
54 uint8_t RotateLeft;
55
56 bool operator==(const MaskRolPair Other) const {
57 return Mask == Other.Mask && RotateLeft == Other.RotateLeft;
58 }
59 bool operator!=(const MaskRolPair Other) const {
60 return Mask != Other.Mask || RotateLeft != Other.RotateLeft;
61 }
62};
63
64/// CodeGenSubRegIndex - Represents a sub-register index.
65class CodeGenSubRegIndex {
66 const Record *const TheDef;
67 std::string Name;
68 std::string Namespace;
69
70public:
71 SubRegRangeByHwMode Range;
72 const unsigned EnumValue;
73 mutable LaneBitmask LaneMask;
74 mutable SmallVector<MaskRolPair, 1> CompositionLaneMaskTransform;
75
76 /// A list of subregister indexes concatenated resulting in this
77 /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx.
78 SmallVector<CodeGenSubRegIndex *, 4> ConcatenationOf;
79
80 // Are all super-registers containing this SubRegIndex covered by their
81 // sub-registers?
82 bool AllSuperRegsCovered;
83 // A subregister index is "artificial" if every subregister obtained
84 // from applying this index is artificial. Artificial subregister
85 // indexes are not used to create new register classes.
86 bool Artificial;
87
88 CodeGenSubRegIndex(const Record *R, unsigned Enum, const CodeGenHwModes &CGH);
89 CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum);
90 CodeGenSubRegIndex(CodeGenSubRegIndex &) = delete;
91
92 const std::string &getName() const { return Name; }
93 const std::string &getNamespace() const { return Namespace; }
94 std::string getQualifiedName() const;
95
96 // Map of composite subreg indices.
97 using CompMap =
98 std::map<CodeGenSubRegIndex *, CodeGenSubRegIndex *, deref<std::less<>>>;
99
100 // Returns the subreg index that results from composing this with Idx.
101 // Returns NULL if this and Idx don't compose.
102 CodeGenSubRegIndex *compose(const CodeGenSubRegIndex *Idx) const {
103 return Idx->EnumValue < ComposedByIdx.size() ? ComposedByIdx[Idx->EnumValue]
104 : nullptr;
105 }
106
107 // Add a composite subreg index: this+A = B.
108 // Return a conflicting composite, or NULL
109 CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, CodeGenSubRegIndex *B,
110 const CodeGenHwModes &CGH) {
111 assert(A && B);
112 unsigned NumModes = CGH.getNumModeIds();
113
114 CodeGenSubRegIndex *Prev = compose(Idx: A);
115 if (Prev == B) {
116 // An earlier identical call already added the ranges for every mode, so
117 // there is nothing left to do once B has an offset in all of them.
118 if (B->hasOffsetInAllModes(NumModes))
119 return nullptr;
120 } else {
121 // Keep an existing conflicting composition, and return it.
122 if (Prev)
123 return Prev;
124
125 if (!Composed.try_emplace(k: A, args&: B).second)
126 llvm_unreachable("ComposedByIdx out of sync with Composed");
127 if (ComposedByIdx.size() <= A->EnumValue)
128 ComposedByIdx.resize(N: A->EnumValue + 1);
129 ComposedByIdx[A->EnumValue] = B;
130 }
131
132 // Synthetic subreg indices that aren't contiguous (for instance ARM
133 // register tuples) don't have a bit range, so it's OK to let
134 // B->Offset == -1. For the other cases, accumulate the offset and set
135 // the size here. Only do so if there is no offset yet though.
136 // Skip default mode.
137 for (unsigned M = 0; M < NumModes; ++M) {
138 // Handle DefaultMode last.
139 if (M == DefaultMode)
140 continue;
141 SubRegRange &Range = this->Range.get(Mode: M);
142 SubRegRange &ARange = A->Range.get(Mode: M);
143 SubRegRange &BRange = B->Range.get(Mode: M);
144
145 if (Range.Offset != (uint32_t)-1 && ARange.Offset != (uint32_t)-1 &&
146 BRange.Offset == (uint32_t)-1) {
147 BRange.Offset = Range.Offset + ARange.Offset;
148 BRange.Size = ARange.Size;
149 }
150 }
151
152 // Now handle default.
153 SubRegRange &Range = this->Range.get(Mode: DefaultMode);
154 SubRegRange &ARange = A->Range.get(Mode: DefaultMode);
155 SubRegRange &BRange = B->Range.get(Mode: DefaultMode);
156 if (Range.Offset != (uint32_t)-1 && ARange.Offset != (uint32_t)-1 &&
157 BRange.Offset == (uint32_t)-1) {
158 BRange.Offset = Range.Offset + ARange.Offset;
159 BRange.Size = ARange.Size;
160 }
161
162 return nullptr;
163 }
164
165 // Update the composite maps of components specified in 'ComposedOf'.
166 void updateComponents(CodeGenRegBank &);
167
168 // Return the map of composites.
169 const CompMap &getComposites() const { return Composed; }
170
171 // Compute LaneMask from Composed. Return LaneMask.
172 LaneBitmask computeLaneMask() const;
173
174 void setConcatenationOf(ArrayRef<CodeGenSubRegIndex *> Parts);
175
176 /// Replaces subregister indexes in the `ConcatenationOf` list with
177 /// list of subregisters they are composed of (if any). Do this recursively.
178 void computeConcatTransitiveClosure();
179
180 bool operator<(const CodeGenSubRegIndex &RHS) const {
181 return this->EnumValue < RHS.EnumValue;
182 }
183
184 // Return true if Range has an offset in all NumModes modes. Offsets are
185 // never cleared once set, so cache a true result.
186 bool hasOffsetInAllModes(unsigned NumModes) {
187 if (OffsetInAllModes)
188 return true;
189
190 OffsetInAllModes =
191 Range.size() == NumModes && all_of(Range, P: [](const auto &P) {
192 return P.second.Offset != (uint32_t)-1;
193 });
194 return OffsetInAllModes;
195 }
196
197private:
198 bool OffsetInAllModes = false;
199 CompMap Composed;
200 // Composed indexed by the EnumValue of the first index, for compose().
201 SmallVector<CodeGenSubRegIndex *, 0> ComposedByIdx;
202};
203
204/// CodeGenRegister - Represents a register definition.
205class CodeGenRegister {
206 friend class CodeGenRegBank;
207
208public:
209 const Record *TheDef;
210 unsigned EnumValue;
211 std::vector<int64_t> CostPerUse;
212 bool CoveredBySubRegs = true;
213 bool HasDisjunctSubRegs = false;
214 bool Artificial = true;
215 bool Constant = false;
216
217 // Map SubRegIndex -> Register, used while computing the sub-registers.
218 using SubRegMap =
219 std::map<CodeGenSubRegIndex *, CodeGenRegister *, deref<std::less<>>>;
220
221 // A reference to the final sub-registers, sorted by sub-register index.
222 using SubRegArrayRef =
223 ArrayRef<std::pair<CodeGenSubRegIndex *, CodeGenRegister *>>;
224
225 CodeGenRegister(const Record *R, unsigned Enum);
226
227 StringRef getName() const {
228 assert(TheDef && "no def");
229 return TheDef->getName();
230 }
231
232 // Extract more information from TheDef. This is used to build an object
233 // graph after all CodeGenRegister objects have been created.
234 void buildObjectGraph(CodeGenRegBank &);
235
236 // Lazily compute a map of all sub-registers.
237 // This includes unique entries for all sub-sub-registers.
238 const SubRegMap &computeSubRegs(CodeGenRegBank &);
239
240 // Compute extra sub-registers by combining the existing sub-registers.
241 void computeSecondarySubRegs(CodeGenRegBank &);
242
243 // Add this as a super-register to all sub-registers after the sub-register
244 // graph has been built.
245 void computeSuperRegs(CodeGenRegBank &);
246
247 // Diagnose an explicit SubRegIndex whose declared size makes a sub-register
248 // extend past the register that contains it (an oversized lane mask that
249 // silently corrupts sub-register liveness and spilling). ParentSize is the
250 // size of the register, or 0 if it is unknown. See the definition.
251 void checkSubRegIndexSizes(unsigned ParentSize) const;
252
253 SubRegArrayRef getSubRegs() const {
254 assert(SuperRegsComplete && "Must precompute super-registers");
255 return FinalSubRegs;
256 }
257
258 // Add sub-registers to OSet following a pre-order defined by the .td file.
259 void addSubRegsPreOrder(SetVector<const CodeGenRegister *> &OSet,
260 CodeGenRegBank &) const;
261
262 // Return the sub-register index naming Reg as a sub-register of this
263 // register. Returns NULL if Reg is not a sub-register.
264 CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const {
265 return SubReg2Idx.lookup(Val: Reg);
266 }
267
268 // Return the sub-register at Idx, or NULL if there is none. Only valid after
269 // computeSuperRegs(). Check position Hint first, and update it to the
270 // position of Idx. Registers with the same sub-register indices store Idx at
271 // the same position, so this avoids the search when looking up the same
272 // index in many similar registers.
273 CodeGenRegister *getSubReg(const CodeGenSubRegIndex *Idx,
274 unsigned &Hint) const;
275
276 using SuperRegList = std::vector<const CodeGenRegister *>;
277
278 // Get the list of super-registers in topological order, small to large.
279 // This is valid after computeSubRegs visits all registers during RegBank
280 // construction.
281 const SuperRegList &getSuperRegs() const {
282 assert(SubRegsComplete && "Must precompute sub-registers");
283 return SuperRegs;
284 }
285
286 // Get the list of ad hoc aliases. The graph is symmetric, so the list
287 // contains all registers in 'Aliases', and all registers that mention this
288 // register in 'Aliases'.
289 ArrayRef<CodeGenRegister *> getExplicitAliases() const {
290 return ExplicitAliases;
291 }
292
293 // Get the topological signature of this register. This is a small integer
294 // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have
295 // identical sub-register structure. That is, they support the same set of
296 // sub-register indices mapping to the same kind of sub-registers
297 // (TopoSig-wise).
298 unsigned getTopoSig() const {
299 assert(SuperRegsComplete && "TopoSigs haven't been computed yet.");
300 return TopoSig;
301 }
302
303 // List of register units in ascending order.
304 using RegUnitList = SparseBitVector<>;
305 using RegUnitLaneMaskList = SmallVector<LaneBitmask, 16>;
306
307 // How many entries in RegUnitList are native?
308 RegUnitList NativeRegUnits;
309
310 // Get the list of register units.
311 // This is only valid after computeSubRegs() completes.
312 const RegUnitList &getRegUnits() const { return RegUnits; }
313
314 void setNewRegUnits(const RegUnitList &NewRegUnits) {
315 RegUnits = NewRegUnits;
316 }
317
318 ArrayRef<LaneBitmask> getRegUnitLaneMasks() const {
319 return ArrayRef(RegUnitLaneMasks).slice(N: 0, M: NativeRegUnits.count());
320 }
321
322 // Get the native register units. This is a prefix of getRegUnits().
323 RegUnitList getNativeRegUnits() const { return NativeRegUnits; }
324
325 void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) {
326 RegUnitLaneMasks = LaneMasks;
327 }
328
329 // Inherit register units from subregisters.
330 // Return true if the RegUnits changed.
331 bool inheritRegUnits(CodeGenRegBank &RegBank);
332
333 // Adopt a register unit for pressure tracking.
334 // A unit is adopted iff its unit number is >= NativeRegUnits.count().
335 void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); }
336
337 // Get the sum of this register's register unit weights.
338 unsigned getWeight(const CodeGenRegBank &RegBank) const;
339
340 // Canonically ordered set.
341 using Vec = std::vector<const CodeGenRegister *>;
342
343private:
344 bool SubRegsComplete;
345 bool SuperRegsComplete;
346 unsigned TopoSig;
347
348 // The sub-registers explicit in the .td file form a tree.
349 SmallVector<CodeGenSubRegIndex *, 8> ExplicitSubRegIndices;
350 SmallVector<CodeGenRegister *, 8> ExplicitSubRegs;
351
352 // Explicit ad hoc aliases, symmetrized to form an undirected graph.
353 SmallVector<CodeGenRegister *, 8> ExplicitAliases;
354
355 // Super-registers where this is the first explicit sub-register.
356 SuperRegList LeadingSuperRegs;
357
358 // Built by computeSubRegs(); copied to FinalSubRegs and freed by
359 // computeSuperRegs().
360 SubRegMap SubRegs;
361 SuperRegList SuperRegs;
362 DenseMap<const CodeGenRegister *, CodeGenSubRegIndex *> SubReg2Idx;
363 SmallVector<std::pair<CodeGenSubRegIndex *, CodeGenRegister *>, 0>
364 FinalSubRegs;
365 RegUnitList RegUnits;
366 RegUnitLaneMaskList RegUnitLaneMasks;
367};
368
369inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) {
370 return A.EnumValue < B.EnumValue;
371}
372
373inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) {
374 return A.EnumValue == B.EnumValue;
375}
376
377inline bool operator!=(const CodeGenRegister &A, const CodeGenRegister &B) {
378 return !(A == B);
379}
380
381class CodeGenRegisterClass {
382 CodeGenRegister::Vec Members;
383 // Bit mask of members, indexed by getRegIndex.
384 BitVector MemberBV;
385 // Allocation orders. Order[0] always contains all registers in Members.
386 std::vector<SmallVector<const Record *, 16>> Orders;
387 // Bit mask of sub-classes including this, indexed by their EnumValue.
388 BitVector SubClasses;
389 // List of super-classes, topologocally ordered to have the larger classes
390 // first. This is the same as sorting by EnumValue.
391 SmallVector<CodeGenRegisterClass *, 4> SuperClasses;
392 const Record *TheDef;
393 std::string Name;
394
395 // For a synthesized class, inherit missing properties from the nearest
396 // super-class.
397 void inheritProperties(CodeGenRegBank &);
398
399 // Map SubRegIndex -> sub-class. This is the largest sub-class where all
400 // registers have a SubRegIndex sub-register.
401 DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *>
402 SubClassWithSubReg;
403
404 // Map SubRegIndex -> set of super-reg classes. This is all register
405 // classes SuperRC such that:
406 //
407 // R:SubRegIndex in this RC for all R in SuperRC.
408 //
409 // The sets are indexed by CreationIndex.
410 DenseMap<CodeGenSubRegIndex *, BitVector> SuperRegClasses;
411
412 // Bit vector of TopoSigs for the registers with super registers in this
413 // class. This will be very sparse on regular architectures.
414 BitVector RegsWithSuperRegsTopoSigs;
415
416 // If the register class was inferred for getMatchingSuperRegClass, this
417 // holds the subregister index and subregister class for which the register
418 // class was created.
419 CodeGenSubRegIndex *InferredFromSubRegIdx = nullptr;
420 CodeGenRegisterClass *InferredFromRC = nullptr;
421
422public:
423 unsigned EnumValue;
424 // Position in creation order, see CodeGenRegBank::getRegClassByCreationIndex.
425 // Unlike EnumValue, this is known while classes are being inferred.
426 unsigned CreationIndex = ~0u;
427 StringRef Namespace;
428 SmallVector<ValueTypeByHwMode, 4> VTs;
429 RegSizeInfoByHwMode RSI;
430 uint8_t CopyCost;
431 bool Allocatable;
432 StringRef AltOrderSelect;
433 uint8_t AllocationPriority;
434 bool GlobalPriority;
435 uint8_t TSFlags;
436 uint8_t SpillStackID;
437 /// Contains the combination of the lane masks of all subregisters.
438 LaneBitmask LaneMask;
439 /// True if there are at least 2 subregisters which do not interfere.
440 bool HasDisjunctSubRegs;
441 bool CoveredBySubRegs;
442 /// A register class is artificial if all its members are artificial.
443 bool Artificial;
444 /// Generate register pressure set for this register class and any class
445 /// synthesized from it.
446 bool GeneratePressureSet;
447
448 // Return the Record that defined this class, or NULL if the class was
449 // created by TableGen.
450 const Record *getDef() const { return TheDef; }
451
452 std::string getNamespaceQualification() const;
453 const std::string &getName() const { return Name; }
454 std::string getQualifiedName() const;
455 std::string getIdName() const;
456 std::string getQualifiedIdName() const;
457 ArrayRef<ValueTypeByHwMode> getValueTypes() const { return VTs; }
458 unsigned getNumValueTypes() const { return VTs.size(); }
459 bool hasType(const ValueTypeByHwMode &VT) const;
460
461 const ValueTypeByHwMode &getValueTypeNum(unsigned VTNum) const {
462 if (VTNum < VTs.size())
463 return VTs[VTNum];
464 llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!");
465 }
466
467 // Return true if this class contains the register.
468 bool contains(const CodeGenRegister *) const;
469
470 // Returns true if RC is a subclass.
471 // RC is a sub-class of this class if it is a valid replacement for any
472 // instruction operand where a register of this classis required. It must
473 // satisfy these conditions:
474 //
475 // 1. All RC registers are also in this.
476 // 2. The RC spill size must not be smaller than our spill size.
477 // 3. RC spill alignment must be compatible with ours.
478 //
479 bool hasSubClass(const CodeGenRegisterClass *RC) const {
480 return SubClasses.test(Idx: RC->EnumValue);
481 }
482
483 // getSubClassWithSubReg - Returns the largest sub-class where all
484 // registers have a SubIdx sub-register.
485 CodeGenRegisterClass *
486 getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const {
487 return SubClassWithSubReg.lookup(Val: SubIdx);
488 }
489
490 /// Find largest subclass where all registers have SubIdx subregisters in
491 /// SubRegClass and the largest subregister class that contains those
492 /// subregisters without (as far as possible) also containing additional
493 /// registers.
494 ///
495 /// This can be used to find a suitable pair of classes for subregister
496 /// copies. \return std::pair<SubClass, SubRegClass> where SubClass is a
497 /// SubClass is a class where every register has SubIdx and SubRegClass is a
498 /// class where every register is covered by the SubIdx subregister of
499 /// SubClass.
500 std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
501 getMatchingSubClassWithSubRegs(CodeGenRegBank &RegBank,
502 const CodeGenSubRegIndex *SubIdx) const;
503
504 void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx,
505 CodeGenRegisterClass *SubRC) {
506 SubClassWithSubReg[SubIdx] = SubRC;
507 }
508
509 /// Checks if there are any super-register classes for this SubIdx of this
510 /// class.
511 bool hasAnySuperRegClasses(const CodeGenSubRegIndex *SubIdx) const;
512
513 /// Checks if there is a super-register class for this SubIdx of this
514 /// class containing RC register class.
515 bool hasSuperRegClass(const CodeGenSubRegIndex *SubIdx,
516 const CodeGenRegisterClass *RC) const;
517
518 /// Checks if there is a super-register class for any SubIdx of this class
519 /// containing RC register class.
520 bool hasSuperRegClass(const CodeGenRegisterClass *RC) const;
521
522 // getSuperRegClasses - Returns a bit vector of all register classes
523 // containing only SubIdx super-registers of this class.
524 void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,
525 const CodeGenRegBank &RegBank, BitVector &Out) const;
526
527 // addSuperRegClass - Add a class containing only SubIdx super-registers.
528 void addSuperRegClass(CodeGenSubRegIndex *SubIdx,
529 CodeGenRegisterClass *SuperRC) {
530 assert(SuperRC->CreationIndex != ~0u && "CreationIndex is not set");
531 BitVector &Supers = SuperRegClasses[SubIdx];
532 if (Supers.size() <= SuperRC->CreationIndex)
533 Supers.resize(N: SuperRC->CreationIndex + 1);
534 Supers.set(SuperRC->CreationIndex);
535 }
536
537 void extendSuperRegClasses(CodeGenSubRegIndex *SubIdx,
538 const CodeGenRegBank &RegBank);
539
540 // getSubClasses - Returns a constant BitVector of subclasses indexed by
541 // EnumValue.
542 // The SubClasses vector includes an entry for this class.
543 const BitVector &getSubClasses() const { return SubClasses; }
544
545 // getSuperClasses - Returns a list of super classes ordered by EnumValue.
546 // The array does not include an entry for this class.
547 ArrayRef<CodeGenRegisterClass *> getSuperClasses() const {
548 return SuperClasses;
549 }
550
551 // Returns an ordered list of class members.
552 // The order of registers is the same as in the .td file.
553 // No = 0 is the default allocation order, No = 1 is the first alternative.
554 ArrayRef<const Record *> getOrder(unsigned No = 0) const {
555 return Orders[No];
556 }
557
558 // Return the total number of allocation orders available.
559 unsigned getNumOrders() const { return Orders.size(); }
560
561 // Get the set of registers. This set contains the same registers as
562 // getOrder(0).
563 const CodeGenRegister::Vec &getMembers() const { return Members; }
564
565 // The members as a bit vector indexed by CodeGenRegBank::getRegIndex().
566 const BitVector &getMemberBV() const { return MemberBV; }
567
568 // Get a bit vector of TopoSigs of registers with super registers in this
569 // register class.
570 const BitVector &getRegsWithSuperRegsTopoSigs() const {
571 return RegsWithSuperRegsTopoSigs;
572 }
573
574 // Get a weight of this register class.
575 unsigned getWeight(const CodeGenRegBank &) const;
576
577 // Populate a unique sorted list of units from a register set.
578 void buildRegUnitSet(const CodeGenRegBank &RegBank,
579 std::vector<unsigned> &RegUnits) const;
580
581 CodeGenRegisterClass(CodeGenRegBank &, const Record *R);
582 CodeGenRegisterClass(CodeGenRegisterClass &) = delete;
583
584 // A key representing the parts of a register class used for forming
585 // sub-classes. Note the ordering provided by this key is not the same as
586 // the topological order used for the EnumValues.
587 struct Key {
588 const CodeGenRegister::Vec *Members;
589 RegSizeInfoByHwMode RSI;
590
591 // Ignore artificial registers when comparing classes. We use this
592 // to find existing classes that contain the same non-artificial
593 // members, but may differ in presence of artificial ones, thus
594 // avoiding creating extra register classes for codegen needs.
595 bool IgnoreArtificialMembers;
596
597 Key(const CodeGenRegister::Vec *M, const RegSizeInfoByHwMode &I,
598 bool IgnoreArtificialMembers = false)
599 : Members(M), RSI(I), IgnoreArtificialMembers(IgnoreArtificialMembers) {
600 }
601
602 Key(const CodeGenRegisterClass &RC, bool IgnoreArtificialMembers = false)
603 : Members(&RC.getMembers()), RSI(RC.RSI),
604 IgnoreArtificialMembers(IgnoreArtificialMembers) {}
605
606 // Lexicographical order of (Members, RegSizeInfoByHwMode).
607 bool operator<(const Key &) const;
608 };
609
610 // Create a non-user defined register class.
611 CodeGenRegisterClass(CodeGenRegBank &, StringRef Name, Key Props);
612
613 // Called by CodeGenRegBank::CodeGenRegBank().
614 static void computeSubClasses(CodeGenRegBank &);
615
616 // Get ordering value among register base classes.
617 std::optional<int> getBaseClassOrder() const {
618 if (TheDef && !TheDef->isValueUnset(FieldName: "BaseClassOrder"))
619 return TheDef->getValueAsInt(FieldName: "BaseClassOrder");
620 return {};
621 }
622
623 void setInferredFrom(CodeGenSubRegIndex *Idx, CodeGenRegisterClass *RC) {
624 assert(Idx && RC);
625 assert(!InferredFromSubRegIdx);
626
627 InferredFromSubRegIdx = Idx;
628 InferredFromRC = RC;
629 }
630
631 CodeGenSubRegIndex *getInferredFromSubRegIdx() const {
632 return InferredFromSubRegIdx;
633 }
634
635 CodeGenRegisterClass *getInferredFromRC() const { return InferredFromRC; }
636};
637
638// Register categories are used when we need to deterine the category a
639// register falls into (GPR, vector, fixed, etc.) without having to know
640// specific information about the target architecture.
641class CodeGenRegisterCategory {
642 const Record *TheDef;
643 std::string Name;
644 std::list<CodeGenRegisterClass *> Classes;
645
646public:
647 CodeGenRegisterCategory(CodeGenRegBank &, const Record *R);
648 CodeGenRegisterCategory(CodeGenRegisterCategory &) = delete;
649
650 // Return the Record that defined this class, or NULL if the class was
651 // created by TableGen.
652 const Record *getDef() const { return TheDef; }
653
654 std::string getName() const { return Name; }
655 std::list<CodeGenRegisterClass *> getClasses() const { return Classes; }
656};
657
658// Register units are used to model interference and register pressure.
659// Every register is assigned one or more register units such that two
660// registers overlap if and only if they have a register unit in common.
661//
662// Normally, one register unit is created per leaf register. Non-leaf
663// registers inherit the units of their sub-registers.
664struct RegUnit {
665 // Weight assigned to this RegUnit for estimating register pressure.
666 // This is useful when equalizing weights in register classes with mixed
667 // register topologies.
668 unsigned Weight = 0;
669
670 // Each native RegUnit corresponds to one or two root registers. The full
671 // set of registers containing this unit can be computed as the union of
672 // these two registers and their super-registers.
673 const CodeGenRegister *Roots[2];
674
675 // Index into RegClassUnitSets where we can find the list of UnitSets that
676 // contain this unit.
677 unsigned RegClassUnitSetsIdx = 0;
678 // A register unit is artificial if at least one of its roots is
679 // artificial.
680 bool Artificial = false;
681
682 RegUnit() { Roots[0] = Roots[1] = nullptr; }
683
684 ArrayRef<const CodeGenRegister *> getRoots() const {
685 assert(!(Roots[1] && !Roots[0]) && "Invalid roots array");
686 return ArrayRef(Roots, !!Roots[0] + !!Roots[1]);
687 }
688};
689
690// Each RegUnitSet is a sorted vector with a name.
691struct RegUnitSet {
692 using iterator = std::vector<unsigned>::const_iterator;
693
694 std::string Name;
695 std::vector<unsigned> Units;
696 unsigned Weight = 0; // Cache the sum of all unit weights.
697 unsigned Order = 0; // Cache the sort key.
698
699 RegUnitSet(std::string Name) : Name(std::move(Name)) {}
700};
701
702// Base vector for identifying TopoSigs. The contents uniquely identify a
703// TopoSig, only computeSuperRegs needs to know how.
704using TopoSigId = SmallVector<unsigned, 16>;
705
706// CodeGenRegBank - Represent a target's registers and the relations between
707// them.
708class CodeGenRegBank {
709 const RecordKeeper &Records;
710
711 SetTheory Sets;
712
713 const CodeGenHwModes &CGH;
714
715 const bool RegistersAreIntervals;
716
717 std::deque<CodeGenSubRegIndex> SubRegIndices;
718 DenseMap<const Record *, CodeGenSubRegIndex *> Def2SubRegIdx;
719
720 // Subregister indices sorted topologically by composition.
721 std::vector<CodeGenSubRegIndex *> SubRegIndicesRPOT;
722
723 CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace);
724
725 using ConcatIdxMap =
726 std::map<SmallVector<CodeGenSubRegIndex *, 8>, CodeGenSubRegIndex *>;
727 ConcatIdxMap ConcatIdx;
728
729 // Registers.
730 std::deque<CodeGenRegister> Registers;
731 StringMap<CodeGenRegister *> RegistersByName;
732 DenseMap<const Record *, CodeGenRegister *> Def2Reg;
733 unsigned NumNativeRegUnits;
734
735 std::map<TopoSigId, unsigned> TopoSigs;
736
737 // Includes native (0..NumNativeRegUnits-1) and adopted register units.
738 SmallVector<RegUnit, 8> RegUnits;
739
740 // Register classes.
741 std::list<CodeGenRegisterClass> RegClasses;
742 // RegClasses in creation order, indexed by CreationIndex.
743 std::vector<CodeGenRegisterClass *> RegClassesByCreationIndex;
744 StringSet<> RegClassNames;
745 DenseMap<const Record *, CodeGenRegisterClass *> Def2RC;
746 // Key2RC is ordered like CodeGenRegisterClass::Key, ignoring artificial
747 // members. The keys hold the EnumValues of the members rather than the
748 // registers, so lookups don't load the members of the classes in the map.
749 struct RCKey {
750 std::vector<unsigned> Regs;
751 RegSizeInfoByHwMode RSI;
752 };
753
754 struct RCKeyRef {
755 ArrayRef<unsigned> Regs;
756 const RegSizeInfoByHwMode *RSI;
757 };
758
759 struct RCKeyLess {
760 using is_transparent = void;
761
762 static RCKeyRef ref(const RCKey &K) { return {.Regs: K.Regs, .RSI: &K.RSI}; }
763 static RCKeyRef ref(const RCKeyRef &K) { return K; }
764
765 template <typename L, typename R>
766 bool operator()(const L &LHS, const R &RHS) const {
767 RCKeyRef A = ref(LHS), B = ref(RHS);
768 if (A.Regs != B.Regs)
769 return std::lexicographical_compare(first1: A.Regs.begin(), last1: A.Regs.end(),
770 first2: B.Regs.begin(), last2: B.Regs.end());
771 return *A.RSI < *B.RSI;
772 }
773 };
774
775 using RCKeyMap = std::map<RCKey, CodeGenRegisterClass *, RCKeyLess>;
776 RCKeyMap Key2RC;
777
778 // Return the EnumValues of the non-artificial registers in Members.
779 static std::vector<unsigned>
780 getNonArtificialEnumValues(const CodeGenRegister::Vec &Members);
781
782 // Register categories.
783 std::list<CodeGenRegisterCategory> RegCategories;
784
785 // Remember each unique set of register units. Initially, this contains a
786 // unique set for each register class. Simliar sets are coalesced with
787 // pruneUnitSets and new supersets are inferred during computeRegUnitSets.
788 std::vector<RegUnitSet> RegUnitSets;
789
790 // Map RegisterClass index to the index of the RegUnitSet that contains the
791 // class's units and any inferred RegUnit supersets.
792 //
793 // NOTE: This could grow beyond the number of register classes when we map
794 // register units to lists of unit sets. If the list of unit sets does not
795 // already exist for a register class, we create a new entry in this vector.
796 std::vector<std::vector<unsigned>> RegClassUnitSets;
797
798 // Give each register unit set an order based on sorting criteria.
799 std::vector<unsigned> RegUnitSetOrder;
800
801 // Keep track of synthesized definitions generated in TupleExpander.
802 std::vector<std::unique_ptr<Record>> SynthDefs;
803
804 // Add RC to *2RC maps.
805 void addToMaps(CodeGenRegisterClass *);
806
807 // Set the CreationIndex of the newest register class.
808 void setCreationIndex(CodeGenRegisterClass &RC) {
809 RC.CreationIndex = RegClassesByCreationIndex.size();
810 RegClassesByCreationIndex.push_back(x: &RC);
811 }
812
813 // Create a synthetic sub-class if it is missing. Returns (RC, inserted).
814 std::pair<CodeGenRegisterClass *, bool>
815 getOrCreateSubClass(const CodeGenRegisterClass *RC,
816 const CodeGenRegister::Vec *Membs, StringRef Name);
817
818 // Infer missing register classes.
819 void computeInferredRegisterClasses();
820 void inferCommonSubClass(CodeGenRegisterClass *RC);
821 void inferSubClassWithSubReg(CodeGenRegisterClass *RC);
822
823 void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) {
824 inferMatchingSuperRegClass(RC, FirstSubRegRC: RegClasses.begin());
825 }
826
827 void inferMatchingSuperRegClass(
828 CodeGenRegisterClass *RC,
829 std::list<CodeGenRegisterClass>::iterator FirstSubRegRC);
830
831 // Iteratively prune unit sets.
832 void pruneUnitSets();
833
834 // Compute a weight for each register unit created during getSubRegs.
835 void computeRegUnitWeights();
836
837 // Enforce that all registers are intervals of regunits if requested.
838 void enforceRegUnitIntervals();
839
840 // Create a RegUnitSet for each RegClass and infer superclasses.
841 void computeRegUnitSets();
842
843 // Populate the Composite map from sub-register relationships.
844 void computeComposites();
845
846 // Compute a lane mask for each sub-register index.
847 void computeSubRegLaneMasks();
848
849 // Compute RPOT of subregister indices by composition.
850 void computeSubRegIndicesRPOT();
851
852 /// Computes a lane mask for each register unit enumerated by a physical
853 /// register.
854 void computeRegUnitLaneMasks();
855
856 // Helper function for printing debug information. Handles artificial
857 // (non-native) reg units.
858 void printRegUnitNames(ArrayRef<unsigned> Units) const;
859
860public:
861 CodeGenRegBank(const RecordKeeper &, const CodeGenHwModes &,
862 const bool RegistersAreIntervals);
863 CodeGenRegBank(CodeGenRegBank &) = delete;
864
865 SetTheory &getSets() { return Sets; }
866
867 const CodeGenHwModes &getHwModes() const { return CGH; }
868
869 // Sub-register indices. The first NumNamedIndices are defined by the user
870 // in the .td files. The rest are synthesized such that all sub-registers
871 // have a unique name.
872 const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const {
873 return SubRegIndices;
874 }
875
876 // Find a SubRegIndex from its Record def or add to the list if it does
877 // not exist there yet.
878 CodeGenSubRegIndex *getSubRegIdx(const Record *);
879
880 // Find a SubRegIndex from its Record def.
881 const CodeGenSubRegIndex *findSubRegIdx(const Record *Def) const;
882
883 // Find or create a sub-register index representing the A+B composition.
884 CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,
885 CodeGenSubRegIndex *B);
886
887 // Find or create a sub-register index representing the concatenation of
888 // non-overlapping sibling indices.
889 CodeGenSubRegIndex *
890 getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts,
891 const CodeGenHwModes &CGH);
892
893 const std::deque<CodeGenRegister> &getRegisters() const { return Registers; }
894
895 const StringMap<CodeGenRegister *> &getRegistersByName() const {
896 return RegistersByName;
897 }
898
899 // Find a register from its Record def.
900 CodeGenRegister *getReg(const Record *);
901
902 // Get a Register's index into the Registers array.
903 static unsigned getRegIndex(const CodeGenRegister *Reg) {
904 return Reg->EnumValue - 1;
905 }
906
907 // Return the number of allocated TopoSigs. The first TopoSig representing
908 // leaf registers is allocated number 0.
909 unsigned getNumTopoSigs() const { return TopoSigs.size(); }
910
911 // Find or create a TopoSig for the given TopoSigId.
912 // This function is only for use by CodeGenRegister::computeSuperRegs().
913 // Others should simply use Reg->getTopoSig().
914 unsigned getTopoSig(const TopoSigId &Id) {
915 return TopoSigs.try_emplace(k: Id, args: TopoSigs.size()).first->second;
916 }
917
918 // Create a native register unit that is associated with one or two root
919 // registers.
920 unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) {
921 RegUnit &RU = RegUnits.emplace_back();
922 RU.Roots[0] = R0;
923 RU.Roots[1] = R1;
924 RU.Artificial = R0->Artificial;
925 if (R1)
926 RU.Artificial |= R1->Artificial;
927 return RegUnits.size() - 1;
928 }
929
930 // Create a new non-native register unit that can be adopted by a register
931 // to increase its pressure. Note that NumNativeRegUnits is not increased.
932 unsigned newRegUnit(unsigned Weight) {
933 RegUnit &RU = RegUnits.emplace_back();
934 RU.Weight = Weight;
935 return RegUnits.size() - 1;
936 }
937
938 // Native units are the singular unit of a leaf register. Register aliasing
939 // is completely characterized by native units. Adopted units exist to give
940 // register additional weight but don't affect aliasing.
941 bool isNativeUnit(unsigned RUID) const { return RUID < NumNativeRegUnits; }
942
943 unsigned getNumNativeRegUnits() const { return NumNativeRegUnits; }
944
945 RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; }
946 const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; }
947
948 std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; }
949
950 const std::list<CodeGenRegisterClass> &getRegClasses() const {
951 return RegClasses;
952 }
953
954 CodeGenRegisterClass *getRegClassByCreationIndex(unsigned Idx) const {
955 return RegClassesByCreationIndex[Idx];
956 }
957
958 std::list<CodeGenRegisterCategory> &getRegCategories() {
959 return RegCategories;
960 }
961
962 const std::list<CodeGenRegisterCategory> &getRegCategories() const {
963 return RegCategories;
964 }
965
966 // Find a register class from its def.
967 CodeGenRegisterClass *getRegClass(const Record *,
968 ArrayRef<SMLoc> Loc = {}) const;
969
970 /// getRegisterClassForRegister - Find the register class that contains the
971 /// specified physical register. If the register is not in a register
972 /// class, return null. If the register is in multiple classes, and the
973 /// classes have a superset-subset relationship and the same set of types,
974 /// return the superclass. Otherwise return null.
975 const CodeGenRegisterClass *getRegClassForRegister(const Record *R);
976
977 /// Returns whether \p RegClass contains register \p Reg, handling
978 /// RegClassByHwMode and RegisterByHwMode correctly.
979 /// This should be preferred instead of
980 /// `RegBank.getRegClass(RC).contains(RegBank.getReg(R))`.
981 bool regClassContainsReg(const Record *RegClass, const Record *RegDef,
982 ArrayRef<SMLoc> Loc = {});
983
984 // Analog of TargetRegisterInfo::getMinimalPhysRegClass. Unlike
985 // getRegClassForRegister, this tries to find the smallest class containing
986 // the physical register. If \p VT is specified, it will only find classes
987 // with a matching type
988 const CodeGenRegisterClass *
989 getMinimalPhysRegClass(const Record *RegRecord,
990 ValueTypeByHwMode *VT = nullptr);
991
992 /// Return the largest register class which supports \p Ty and covers \p
993 /// SubIdx if it exists.
994 const CodeGenRegisterClass *
995 getSuperRegForSubReg(const ValueTypeByHwMode &Ty,
996 const CodeGenSubRegIndex *SubIdx,
997 bool MustBeAllocatable = false) const;
998
999 // Get the sum of unit weights.
1000 unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const {
1001 unsigned Weight = 0;
1002 for (unsigned Unit : Units)
1003 Weight += getRegUnit(RUID: Unit).Weight;
1004 return Weight;
1005 }
1006
1007 unsigned getRegSetIDAt(unsigned Order) const {
1008 return RegUnitSetOrder[Order];
1009 }
1010
1011 const RegUnitSet &getRegSetAt(unsigned Order) const {
1012 return RegUnitSets[RegUnitSetOrder[Order]];
1013 }
1014
1015 // Increase a RegUnitWeight.
1016 void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {
1017 getRegUnit(RUID).Weight += Inc;
1018 }
1019
1020 // Get the number of register pressure dimensions.
1021 unsigned getNumRegPressureSets() const { return RegUnitSets.size(); }
1022
1023 // Get a set of register unit IDs for a given dimension of pressure.
1024 const RegUnitSet &getRegPressureSet(unsigned Idx) const {
1025 return RegUnitSets[Idx];
1026 }
1027
1028 // The number of pressure set lists may be larget than the number of
1029 // register classes if some register units appeared in a list of sets that
1030 // did not correspond to an existing register class.
1031 unsigned getNumRegClassPressureSetLists() const {
1032 return RegClassUnitSets.size();
1033 }
1034
1035 // Get a list of pressure set IDs for a register class. Liveness of a
1036 // register in this class impacts each pressure set in this list by the
1037 // weight of the register. An exact solution requires all registers in a
1038 // class to have the same class, but it is not strictly guaranteed.
1039 ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const {
1040 return RegClassUnitSets[RCIdx];
1041 }
1042
1043 // Computed derived records such as missing sub-register indices.
1044 void computeDerivedInfo();
1045
1046 // Compute the set of registers completely covered by the registers in Regs.
1047 // The returned BitVector will have a bit set for each register in Regs,
1048 // all sub-registers, and all super-registers that are covered by the
1049 // registers in Regs.
1050 //
1051 // This is used to compute the mask of call-preserved registers from a list
1052 // of callee-saves.
1053 BitVector computeCoveredRegisters(ArrayRef<const Record *> Regs);
1054
1055 // Bit mask of lanes that cover their registers. A sub-register index whose
1056 // LaneMask is contained in CoveringLanes will be completely covered by
1057 // another sub-register with the same or larger lane mask.
1058 LaneBitmask CoveringLanes;
1059};
1060
1061} // end namespace llvm
1062
1063#endif // LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H
1064