907 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines structures to encapsulate information gleaned from the10// target register and register class definitions.11//12//===----------------------------------------------------------------------===//13 14#ifndef LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H15#define LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H16 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 left50/// 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 this76 /// 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 their80 // sub-registers?81 bool AllSuperRegsCovered;82 // A subregister index is "artificial" if every subregister obtained83 // from applying this index is artificial. Artificial subregister84 // 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(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 NULL108 CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A, CodeGenSubRegIndex *B,109 const CodeGenHwModes &CGH) {110 assert(A && B);111 std::pair<CompMap::iterator, bool> Ins = Composed.try_emplace(A, B);112 113 // Synthetic subreg indices that aren't contiguous (for instance ARM114 // register tuples) don't have a bit range, so it's OK to let115 // B->Offset == -1. For the other cases, accumulate the offset and set116 // 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(M);124 SubRegRange &ARange = A->Range.get(M);125 SubRegRange &BRange = B->Range.get(M);126 127 if (Range.Offset != (uint16_t)-1 && ARange.Offset != (uint16_t)-1 &&128 BRange.Offset == (uint16_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(DefaultMode);136 SubRegRange &ARange = A->Range.get(DefaultMode);137 SubRegRange &BRange = B->Range.get(DefaultMode);138 if (Range.Offset != (uint16_t)-1 && ARange.Offset != (uint16_t)-1 &&139 BRange.Offset == (uint16_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 with159 /// 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 {172public:173 const Record *TheDef;174 unsigned EnumValue;175 std::vector<int64_t> CostPerUse;176 bool CoveredBySubRegs = true;177 bool HasDisjunctSubRegs = false;178 bool Artificial = true;179 bool Constant = false;180 181 // Map SubRegIndex -> Register.182 using SubRegMap =183 std::map<CodeGenSubRegIndex *, CodeGenRegister *, deref<std::less<>>>;184 185 CodeGenRegister(const Record *R, unsigned Enum);186 187 StringRef getName() const {188 assert(TheDef && "no def");189 return TheDef->getName();190 }191 192 // Extract more information from TheDef. This is used to build an object193 // graph after all CodeGenRegister objects have been created.194 void buildObjectGraph(CodeGenRegBank &);195 196 // Lazily compute a map of all sub-registers.197 // This includes unique entries for all sub-sub-registers.198 const SubRegMap &computeSubRegs(CodeGenRegBank &);199 200 // Compute extra sub-registers by combining the existing sub-registers.201 void computeSecondarySubRegs(CodeGenRegBank &);202 203 // Add this as a super-register to all sub-registers after the sub-register204 // graph has been built.205 void computeSuperRegs(CodeGenRegBank &);206 207 const SubRegMap &getSubRegs() const {208 assert(SubRegsComplete && "Must precompute sub-registers");209 return SubRegs;210 }211 212 // Add sub-registers to OSet following a pre-order defined by the .td file.213 void addSubRegsPreOrder(SetVector<const CodeGenRegister *> &OSet,214 CodeGenRegBank &) const;215 216 // Return the sub-register index naming Reg as a sub-register of this217 // register. Returns NULL if Reg is not a sub-register.218 CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const {219 return SubReg2Idx.lookup(Reg);220 }221 222 using SuperRegList = std::vector<const CodeGenRegister *>;223 224 // Get the list of super-registers in topological order, small to large.225 // This is valid after computeSubRegs visits all registers during RegBank226 // construction.227 const SuperRegList &getSuperRegs() const {228 assert(SubRegsComplete && "Must precompute sub-registers");229 return SuperRegs;230 }231 232 // Get the list of ad hoc aliases. The graph is symmetric, so the list233 // contains all registers in 'Aliases', and all registers that mention this234 // register in 'Aliases'.235 ArrayRef<CodeGenRegister *> getExplicitAliases() const {236 return ExplicitAliases;237 }238 239 // Get the topological signature of this register. This is a small integer240 // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have241 // identical sub-register structure. That is, they support the same set of242 // sub-register indices mapping to the same kind of sub-registers243 // (TopoSig-wise).244 unsigned getTopoSig() const {245 assert(SuperRegsComplete && "TopoSigs haven't been computed yet.");246 return TopoSig;247 }248 249 // List of register units in ascending order.250 using RegUnitList = SparseBitVector<>;251 using RegUnitLaneMaskList = SmallVector<LaneBitmask, 16>;252 253 // How many entries in RegUnitList are native?254 RegUnitList NativeRegUnits;255 256 // Get the list of register units.257 // This is only valid after computeSubRegs() completes.258 const RegUnitList &getRegUnits() const { return RegUnits; }259 260 ArrayRef<LaneBitmask> getRegUnitLaneMasks() const {261 return ArrayRef(RegUnitLaneMasks).slice(0, NativeRegUnits.count());262 }263 264 // Get the native register units. This is a prefix of getRegUnits().265 RegUnitList getNativeRegUnits() const { return NativeRegUnits; }266 267 void setRegUnitLaneMasks(const RegUnitLaneMaskList &LaneMasks) {268 RegUnitLaneMasks = LaneMasks;269 }270 271 // Inherit register units from subregisters.272 // Return true if the RegUnits changed.273 bool inheritRegUnits(CodeGenRegBank &RegBank);274 275 // Adopt a register unit for pressure tracking.276 // A unit is adopted iff its unit number is >= NativeRegUnits.count().277 void adoptRegUnit(unsigned RUID) { RegUnits.set(RUID); }278 279 // Get the sum of this register's register unit weights.280 unsigned getWeight(const CodeGenRegBank &RegBank) const;281 282 // Canonically ordered set.283 using Vec = std::vector<const CodeGenRegister *>;284 285private:286 bool SubRegsComplete;287 bool SuperRegsComplete;288 unsigned TopoSig;289 290 // The sub-registers explicit in the .td file form a tree.291 SmallVector<CodeGenSubRegIndex *, 8> ExplicitSubRegIndices;292 SmallVector<CodeGenRegister *, 8> ExplicitSubRegs;293 294 // Explicit ad hoc aliases, symmetrized to form an undirected graph.295 SmallVector<CodeGenRegister *, 8> ExplicitAliases;296 297 // Super-registers where this is the first explicit sub-register.298 SuperRegList LeadingSuperRegs;299 300 SubRegMap SubRegs;301 SuperRegList SuperRegs;302 DenseMap<const CodeGenRegister *, CodeGenSubRegIndex *> SubReg2Idx;303 RegUnitList RegUnits;304 RegUnitLaneMaskList RegUnitLaneMasks;305};306 307inline bool operator<(const CodeGenRegister &A, const CodeGenRegister &B) {308 return A.EnumValue < B.EnumValue;309}310 311inline bool operator==(const CodeGenRegister &A, const CodeGenRegister &B) {312 return A.EnumValue == B.EnumValue;313}314 315class CodeGenRegisterClass {316 CodeGenRegister::Vec Members;317 // Bit mask of members, indexed by getRegIndex.318 BitVector MemberBV;319 // Allocation orders. Order[0] always contains all registers in Members.320 std::vector<SmallVector<const Record *, 16>> Orders;321 // Bit mask of sub-classes including this, indexed by their EnumValue.322 BitVector SubClasses;323 // List of super-classes, topologocally ordered to have the larger classes324 // first. This is the same as sorting by EnumValue.325 SmallVector<CodeGenRegisterClass *, 4> SuperClasses;326 const Record *TheDef;327 std::string Name;328 329 // For a synthesized class, inherit missing properties from the nearest330 // super-class.331 void inheritProperties(CodeGenRegBank &);332 333 // Map SubRegIndex -> sub-class. This is the largest sub-class where all334 // registers have a SubRegIndex sub-register.335 DenseMap<const CodeGenSubRegIndex *, CodeGenRegisterClass *>336 SubClassWithSubReg;337 338 // Map SubRegIndex -> set of super-reg classes. This is all register339 // classes SuperRC such that:340 //341 // R:SubRegIndex in this RC for all R in SuperRC.342 //343 DenseMap<CodeGenSubRegIndex *, DenseSet<CodeGenRegisterClass *>>344 SuperRegClasses;345 346 // Bit vector of TopoSigs for the registers with super registers in this347 // class. This will be very sparse on regular architectures.348 BitVector RegsWithSuperRegsTopoSigs;349 350 // If the register class was inferred for getMatchingSuperRegClass, this351 // holds the subregister index and subregister class for which the register352 // class was created.353 CodeGenSubRegIndex *InferredFromSubRegIdx = nullptr;354 CodeGenRegisterClass *InferredFromRC = nullptr;355 356public:357 unsigned EnumValue;358 StringRef Namespace;359 SmallVector<ValueTypeByHwMode, 4> VTs;360 RegSizeInfoByHwMode RSI;361 uint8_t CopyCost;362 bool Allocatable;363 StringRef AltOrderSelect;364 uint8_t AllocationPriority;365 bool GlobalPriority;366 uint8_t TSFlags;367 /// Contains the combination of the lane masks of all subregisters.368 LaneBitmask LaneMask;369 /// True if there are at least 2 subregisters which do not interfere.370 bool HasDisjunctSubRegs;371 bool CoveredBySubRegs;372 /// A register class is artificial if all its members are artificial.373 bool Artificial;374 /// Generate register pressure set for this register class and any class375 /// synthesized from it.376 bool GeneratePressureSet;377 378 // Return the Record that defined this class, or NULL if the class was379 // created by TableGen.380 const Record *getDef() const { return TheDef; }381 382 std::string getNamespaceQualification() const;383 const std::string &getName() const { return Name; }384 std::string getQualifiedName() const;385 std::string getIdName() const;386 std::string getQualifiedIdName() const;387 ArrayRef<ValueTypeByHwMode> getValueTypes() const { return VTs; }388 unsigned getNumValueTypes() const { return VTs.size(); }389 bool hasType(const ValueTypeByHwMode &VT) const;390 391 const ValueTypeByHwMode &getValueTypeNum(unsigned VTNum) const {392 if (VTNum < VTs.size())393 return VTs[VTNum];394 llvm_unreachable("VTNum greater than number of ValueTypes in RegClass!");395 }396 397 // Return true if this class contains the register.398 bool contains(const CodeGenRegister *) const;399 400 // Returns true if RC is a subclass.401 // RC is a sub-class of this class if it is a valid replacement for any402 // instruction operand where a register of this classis required. It must403 // satisfy these conditions:404 //405 // 1. All RC registers are also in this.406 // 2. The RC spill size must not be smaller than our spill size.407 // 3. RC spill alignment must be compatible with ours.408 //409 bool hasSubClass(const CodeGenRegisterClass *RC) const {410 return SubClasses.test(RC->EnumValue);411 }412 413 // getSubClassWithSubReg - Returns the largest sub-class where all414 // registers have a SubIdx sub-register.415 CodeGenRegisterClass *416 getSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx) const {417 return SubClassWithSubReg.lookup(SubIdx);418 }419 420 /// Find largest subclass where all registers have SubIdx subregisters in421 /// SubRegClass and the largest subregister class that contains those422 /// subregisters without (as far as possible) also containing additional423 /// registers.424 ///425 /// This can be used to find a suitable pair of classes for subregister426 /// copies. \return std::pair<SubClass, SubRegClass> where SubClass is a427 /// SubClass is a class where every register has SubIdx and SubRegClass is a428 /// class where every register is covered by the SubIdx subregister of429 /// SubClass.430 std::optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>431 getMatchingSubClassWithSubRegs(CodeGenRegBank &RegBank,432 const CodeGenSubRegIndex *SubIdx) const;433 434 void setSubClassWithSubReg(const CodeGenSubRegIndex *SubIdx,435 CodeGenRegisterClass *SubRC) {436 SubClassWithSubReg[SubIdx] = SubRC;437 }438 439 // getSuperRegClasses - Returns a bit vector of all register classes440 // containing only SubIdx super-registers of this class.441 void getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,442 BitVector &Out) const;443 444 // addSuperRegClass - Add a class containing only SubIdx super-registers.445 void addSuperRegClass(CodeGenSubRegIndex *SubIdx,446 CodeGenRegisterClass *SuperRC) {447 SuperRegClasses[SubIdx].insert(SuperRC);448 }449 450 void extendSuperRegClasses(CodeGenSubRegIndex *SubIdx);451 452 // getSubClasses - Returns a constant BitVector of subclasses indexed by453 // EnumValue.454 // The SubClasses vector includes an entry for this class.455 const BitVector &getSubClasses() const { return SubClasses; }456 457 // getSuperClasses - Returns a list of super classes ordered by EnumValue.458 // The array does not include an entry for this class.459 ArrayRef<CodeGenRegisterClass *> getSuperClasses() const {460 return SuperClasses;461 }462 463 // Returns an ordered list of class members.464 // The order of registers is the same as in the .td file.465 // No = 0 is the default allocation order, No = 1 is the first alternative.466 ArrayRef<const Record *> getOrder(unsigned No = 0) const {467 return Orders[No];468 }469 470 // Return the total number of allocation orders available.471 unsigned getNumOrders() const { return Orders.size(); }472 473 // Get the set of registers. This set contains the same registers as474 // getOrder(0).475 const CodeGenRegister::Vec &getMembers() const { return Members; }476 477 // Get a bit vector of TopoSigs of registers with super registers in this478 // register class.479 const BitVector &getRegsWithSuperRegsTopoSigs() const {480 return RegsWithSuperRegsTopoSigs;481 }482 483 // Get a weight of this register class.484 unsigned getWeight(const CodeGenRegBank &) const;485 486 // Populate a unique sorted list of units from a register set.487 void buildRegUnitSet(const CodeGenRegBank &RegBank,488 std::vector<unsigned> &RegUnits) const;489 490 CodeGenRegisterClass(CodeGenRegBank &, const Record *R);491 CodeGenRegisterClass(CodeGenRegisterClass &) = delete;492 493 // A key representing the parts of a register class used for forming494 // sub-classes. Note the ordering provided by this key is not the same as495 // the topological order used for the EnumValues.496 struct Key {497 const CodeGenRegister::Vec *Members;498 RegSizeInfoByHwMode RSI;499 500 Key(const CodeGenRegister::Vec *M, const RegSizeInfoByHwMode &I)501 : Members(M), RSI(I) {}502 503 Key(const CodeGenRegisterClass &RC)504 : Members(&RC.getMembers()), RSI(RC.RSI) {}505 506 // Lexicographical order of (Members, RegSizeInfoByHwMode).507 bool operator<(const Key &) const;508 };509 510 // Create a non-user defined register class.511 CodeGenRegisterClass(CodeGenRegBank &, StringRef Name, Key Props);512 513 // Called by CodeGenRegBank::CodeGenRegBank().514 static void computeSubClasses(CodeGenRegBank &);515 516 // Get ordering value among register base classes.517 std::optional<int> getBaseClassOrder() const {518 if (TheDef && !TheDef->isValueUnset("BaseClassOrder"))519 return TheDef->getValueAsInt("BaseClassOrder");520 return {};521 }522 523 void setInferredFrom(CodeGenSubRegIndex *Idx, CodeGenRegisterClass *RC) {524 assert(Idx && RC);525 assert(!InferredFromSubRegIdx);526 527 InferredFromSubRegIdx = Idx;528 InferredFromRC = RC;529 }530 531 CodeGenSubRegIndex *getInferredFromSubRegIdx() const {532 return InferredFromSubRegIdx;533 }534 535 CodeGenRegisterClass *getInferredFromRC() const { return InferredFromRC; }536};537 538// Register categories are used when we need to deterine the category a539// register falls into (GPR, vector, fixed, etc.) without having to know540// specific information about the target architecture.541class CodeGenRegisterCategory {542 const Record *TheDef;543 std::string Name;544 std::list<CodeGenRegisterClass *> Classes;545 546public:547 CodeGenRegisterCategory(CodeGenRegBank &, const Record *R);548 CodeGenRegisterCategory(CodeGenRegisterCategory &) = delete;549 550 // Return the Record that defined this class, or NULL if the class was551 // created by TableGen.552 const Record *getDef() const { return TheDef; }553 554 std::string getName() const { return Name; }555 std::list<CodeGenRegisterClass *> getClasses() const { return Classes; }556};557 558// Register units are used to model interference and register pressure.559// Every register is assigned one or more register units such that two560// registers overlap if and only if they have a register unit in common.561//562// Normally, one register unit is created per leaf register. Non-leaf563// registers inherit the units of their sub-registers.564struct RegUnit {565 // Weight assigned to this RegUnit for estimating register pressure.566 // This is useful when equalizing weights in register classes with mixed567 // register topologies.568 unsigned Weight = 0;569 570 // Each native RegUnit corresponds to one or two root registers. The full571 // set of registers containing this unit can be computed as the union of572 // these two registers and their super-registers.573 const CodeGenRegister *Roots[2];574 575 // Index into RegClassUnitSets where we can find the list of UnitSets that576 // contain this unit.577 unsigned RegClassUnitSetsIdx = 0;578 // A register unit is artificial if at least one of its roots is579 // artificial.580 bool Artificial = false;581 582 RegUnit() { Roots[0] = Roots[1] = nullptr; }583 584 ArrayRef<const CodeGenRegister *> getRoots() const {585 assert(!(Roots[1] && !Roots[0]) && "Invalid roots array");586 return ArrayRef(Roots, !!Roots[0] + !!Roots[1]);587 }588};589 590// Each RegUnitSet is a sorted vector with a name.591struct RegUnitSet {592 using iterator = std::vector<unsigned>::const_iterator;593 594 std::string Name;595 std::vector<unsigned> Units;596 unsigned Weight = 0; // Cache the sum of all unit weights.597 unsigned Order = 0; // Cache the sort key.598 599 RegUnitSet(std::string Name) : Name(std::move(Name)) {}600};601 602// Base vector for identifying TopoSigs. The contents uniquely identify a603// TopoSig, only computeSuperRegs needs to know how.604using TopoSigId = SmallVector<unsigned, 16>;605 606// CodeGenRegBank - Represent a target's registers and the relations between607// them.608class CodeGenRegBank {609 const RecordKeeper &Records;610 611 SetTheory Sets;612 613 const CodeGenHwModes &CGH;614 615 std::deque<CodeGenSubRegIndex> SubRegIndices;616 DenseMap<const Record *, CodeGenSubRegIndex *> Def2SubRegIdx;617 618 // Subregister indices sorted topologically by composition.619 std::vector<CodeGenSubRegIndex *> SubRegIndicesRPOT;620 621 CodeGenSubRegIndex *createSubRegIndex(StringRef Name, StringRef NameSpace);622 623 using ConcatIdxMap =624 std::map<SmallVector<CodeGenSubRegIndex *, 8>, CodeGenSubRegIndex *>;625 ConcatIdxMap ConcatIdx;626 627 // Registers.628 std::deque<CodeGenRegister> Registers;629 StringMap<CodeGenRegister *> RegistersByName;630 DenseMap<const Record *, CodeGenRegister *> Def2Reg;631 unsigned NumNativeRegUnits;632 633 std::map<TopoSigId, unsigned> TopoSigs;634 635 // Includes native (0..NumNativeRegUnits-1) and adopted register units.636 SmallVector<RegUnit, 8> RegUnits;637 638 // Register classes.639 std::list<CodeGenRegisterClass> RegClasses;640 DenseMap<const Record *, CodeGenRegisterClass *> Def2RC;641 using RCKeyMap = std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass *>;642 RCKeyMap Key2RC;643 644 // Register categories.645 std::list<CodeGenRegisterCategory> RegCategories;646 using RCatKeyMap =647 std::map<CodeGenRegisterClass::Key, CodeGenRegisterCategory *>;648 RCatKeyMap Key2RCat;649 650 // Remember each unique set of register units. Initially, this contains a651 // unique set for each register class. Simliar sets are coalesced with652 // pruneUnitSets and new supersets are inferred during computeRegUnitSets.653 std::vector<RegUnitSet> RegUnitSets;654 655 // Map RegisterClass index to the index of the RegUnitSet that contains the656 // class's units and any inferred RegUnit supersets.657 //658 // NOTE: This could grow beyond the number of register classes when we map659 // register units to lists of unit sets. If the list of unit sets does not660 // already exist for a register class, we create a new entry in this vector.661 std::vector<std::vector<unsigned>> RegClassUnitSets;662 663 // Give each register unit set an order based on sorting criteria.664 std::vector<unsigned> RegUnitSetOrder;665 666 // Keep track of synthesized definitions generated in TupleExpander.667 std::vector<std::unique_ptr<Record>> SynthDefs;668 669 // Add RC to *2RC maps.670 void addToMaps(CodeGenRegisterClass *);671 672 // Create a synthetic sub-class if it is missing. Returns (RC, inserted).673 std::pair<CodeGenRegisterClass *, bool>674 getOrCreateSubClass(const CodeGenRegisterClass *RC,675 const CodeGenRegister::Vec *Membs, StringRef Name);676 677 // Infer missing register classes.678 void computeInferredRegisterClasses();679 void inferCommonSubClass(CodeGenRegisterClass *RC);680 void inferSubClassWithSubReg(CodeGenRegisterClass *RC);681 682 void inferMatchingSuperRegClass(CodeGenRegisterClass *RC) {683 inferMatchingSuperRegClass(RC, RegClasses.begin());684 }685 686 void inferMatchingSuperRegClass(687 CodeGenRegisterClass *RC,688 std::list<CodeGenRegisterClass>::iterator FirstSubRegRC);689 690 // Iteratively prune unit sets.691 void pruneUnitSets();692 693 // Compute a weight for each register unit created during getSubRegs.694 void computeRegUnitWeights();695 696 // Create a RegUnitSet for each RegClass and infer superclasses.697 void computeRegUnitSets();698 699 // Populate the Composite map from sub-register relationships.700 void computeComposites();701 702 // Compute a lane mask for each sub-register index.703 void computeSubRegLaneMasks();704 705 // Compute RPOT of subregister indices by composition.706 void computeSubRegIndicesRPOT();707 708 /// Computes a lane mask for each register unit enumerated by a physical709 /// register.710 void computeRegUnitLaneMasks();711 712 // Helper function for printing debug information. Handles artificial713 // (non-native) reg units.714 void printRegUnitNames(ArrayRef<unsigned> Units) const;715 716public:717 CodeGenRegBank(const RecordKeeper &, const CodeGenHwModes &);718 CodeGenRegBank(CodeGenRegBank &) = delete;719 720 SetTheory &getSets() { return Sets; }721 722 const CodeGenHwModes &getHwModes() const { return CGH; }723 724 // Sub-register indices. The first NumNamedIndices are defined by the user725 // in the .td files. The rest are synthesized such that all sub-registers726 // have a unique name.727 const std::deque<CodeGenSubRegIndex> &getSubRegIndices() const {728 return SubRegIndices;729 }730 731 // Find a SubRegIndex from its Record def or add to the list if it does732 // not exist there yet.733 CodeGenSubRegIndex *getSubRegIdx(const Record *);734 735 // Find a SubRegIndex from its Record def.736 const CodeGenSubRegIndex *findSubRegIdx(const Record *Def) const;737 738 // Find or create a sub-register index representing the A+B composition.739 CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,740 CodeGenSubRegIndex *B);741 742 // Find or create a sub-register index representing the concatenation of743 // non-overlapping sibling indices.744 CodeGenSubRegIndex *745 getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts,746 const CodeGenHwModes &CGH);747 748 const std::deque<CodeGenRegister> &getRegisters() const { return Registers; }749 750 const StringMap<CodeGenRegister *> &getRegistersByName() const {751 return RegistersByName;752 }753 754 // Find a register from its Record def.755 CodeGenRegister *getReg(const Record *);756 757 // Get a Register's index into the Registers array.758 static unsigned getRegIndex(const CodeGenRegister *Reg) {759 return Reg->EnumValue - 1;760 }761 762 // Return the number of allocated TopoSigs. The first TopoSig representing763 // leaf registers is allocated number 0.764 unsigned getNumTopoSigs() const { return TopoSigs.size(); }765 766 // Find or create a TopoSig for the given TopoSigId.767 // This function is only for use by CodeGenRegister::computeSuperRegs().768 // Others should simply use Reg->getTopoSig().769 unsigned getTopoSig(const TopoSigId &Id) {770 return TopoSigs.try_emplace(Id, TopoSigs.size()).first->second;771 }772 773 // Create a native register unit that is associated with one or two root774 // registers.775 unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = nullptr) {776 RegUnit &RU = RegUnits.emplace_back();777 RU.Roots[0] = R0;778 RU.Roots[1] = R1;779 RU.Artificial = R0->Artificial;780 if (R1)781 RU.Artificial |= R1->Artificial;782 return RegUnits.size() - 1;783 }784 785 // Create a new non-native register unit that can be adopted by a register786 // to increase its pressure. Note that NumNativeRegUnits is not increased.787 unsigned newRegUnit(unsigned Weight) {788 RegUnit &RU = RegUnits.emplace_back();789 RU.Weight = Weight;790 return RegUnits.size() - 1;791 }792 793 // Native units are the singular unit of a leaf register. Register aliasing794 // is completely characterized by native units. Adopted units exist to give795 // register additional weight but don't affect aliasing.796 bool isNativeUnit(unsigned RUID) const { return RUID < NumNativeRegUnits; }797 798 unsigned getNumNativeRegUnits() const { return NumNativeRegUnits; }799 800 RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; }801 const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; }802 803 std::list<CodeGenRegisterClass> &getRegClasses() { return RegClasses; }804 805 const std::list<CodeGenRegisterClass> &getRegClasses() const {806 return RegClasses;807 }808 809 std::list<CodeGenRegisterCategory> &getRegCategories() {810 return RegCategories;811 }812 813 const std::list<CodeGenRegisterCategory> &getRegCategories() const {814 return RegCategories;815 }816 817 // Find a register class from its def.818 CodeGenRegisterClass *getRegClass(const Record *) const;819 820 /// getRegisterClassForRegister - Find the register class that contains the821 /// specified physical register. If the register is not in a register822 /// class, return null. If the register is in multiple classes, and the823 /// classes have a superset-subset relationship and the same set of types,824 /// return the superclass. Otherwise return null.825 const CodeGenRegisterClass *getRegClassForRegister(const Record *R);826 827 // Analog of TargetRegisterInfo::getMinimalPhysRegClass. Unlike828 // getRegClassForRegister, this tries to find the smallest class containing829 // the physical register. If \p VT is specified, it will only find classes830 // with a matching type831 const CodeGenRegisterClass *832 getMinimalPhysRegClass(const Record *RegRecord,833 ValueTypeByHwMode *VT = nullptr);834 835 /// Return the largest register class which supports \p Ty and covers \p836 /// SubIdx if it exists.837 const CodeGenRegisterClass *838 getSuperRegForSubReg(const ValueTypeByHwMode &Ty,839 const CodeGenSubRegIndex *SubIdx,840 bool MustBeAllocatable = false) const;841 842 // Get the sum of unit weights.843 unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const {844 unsigned Weight = 0;845 for (unsigned Unit : Units)846 Weight += getRegUnit(Unit).Weight;847 return Weight;848 }849 850 unsigned getRegSetIDAt(unsigned Order) const {851 return RegUnitSetOrder[Order];852 }853 854 const RegUnitSet &getRegSetAt(unsigned Order) const {855 return RegUnitSets[RegUnitSetOrder[Order]];856 }857 858 // Increase a RegUnitWeight.859 void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {860 getRegUnit(RUID).Weight += Inc;861 }862 863 // Get the number of register pressure dimensions.864 unsigned getNumRegPressureSets() const { return RegUnitSets.size(); }865 866 // Get a set of register unit IDs for a given dimension of pressure.867 const RegUnitSet &getRegPressureSet(unsigned Idx) const {868 return RegUnitSets[Idx];869 }870 871 // The number of pressure set lists may be larget than the number of872 // register classes if some register units appeared in a list of sets that873 // did not correspond to an existing register class.874 unsigned getNumRegClassPressureSetLists() const {875 return RegClassUnitSets.size();876 }877 878 // Get a list of pressure set IDs for a register class. Liveness of a879 // register in this class impacts each pressure set in this list by the880 // weight of the register. An exact solution requires all registers in a881 // class to have the same class, but it is not strictly guaranteed.882 ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const {883 return RegClassUnitSets[RCIdx];884 }885 886 // Computed derived records such as missing sub-register indices.887 void computeDerivedInfo();888 889 // Compute the set of registers completely covered by the registers in Regs.890 // The returned BitVector will have a bit set for each register in Regs,891 // all sub-registers, and all super-registers that are covered by the892 // registers in Regs.893 //894 // This is used to compute the mask of call-preserved registers from a list895 // of callee-saves.896 BitVector computeCoveredRegisters(ArrayRef<const Record *> Regs);897 898 // Bit mask of lanes that cover their registers. A sub-register index whose899 // LaneMask is contained in CoveringLanes will be completely covered by900 // another sub-register with the same or larger lane mask.901 LaneBitmask CoveringLanes;902};903 904} // end namespace llvm905 906#endif // LLVM_UTILS_TABLEGEN_COMMON_CODEGENREGISTERS_H907