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