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