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