CodeGenRegisters.h revision 226633
118334Speter//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===// 290075Sobrien// 3169689Skan// The LLVM Compiler Infrastructure 418334Speter// 590075Sobrien// This file is distributed under the University of Illinois Open Source 618334Speter// License. See LICENSE.TXT for details. 790075Sobrien// 890075Sobrien//===----------------------------------------------------------------------===// 990075Sobrien// 1090075Sobrien// This file defines structures to encapsulate information gleaned from the 1118334Speter// target register and register class definitions. 1290075Sobrien// 1390075Sobrien//===----------------------------------------------------------------------===// 1490075Sobrien 1590075Sobrien#ifndef CODEGEN_REGISTERS_H 1618334Speter#define CODEGEN_REGISTERS_H 1718334Speter 1890075Sobrien#include "SetTheory.h" 19169689Skan#include "llvm/TableGen/Record.h" 20169689Skan#include "llvm/CodeGen/ValueTypes.h" 2118334Speter#include "llvm/ADT/ArrayRef.h" 2218334Speter#include "llvm/ADT/BitVector.h" 23132718Skan#include "llvm/ADT/DenseMap.h" 2450397Sobrien#include "llvm/ADT/SetVector.h" 25132718Skan#include <cstdlib> 26132718Skan#include <map> 2718334Speter#include <string> 2890075Sobrien#include <set> 2990075Sobrien#include <vector> 3018334Speter 3118334Speternamespace llvm { 3218334Speter class CodeGenRegBank; 3318334Speter 3418334Speter /// CodeGenRegister - Represents a register definition. 3518334Speter struct CodeGenRegister { 3618334Speter Record *TheDef; 3718334Speter unsigned EnumValue; 3818334Speter unsigned CostPerUse; 3918334Speter 4018334Speter // Map SubRegIndex -> Register. 4118334Speter typedef std::map<Record*, CodeGenRegister*, LessRecord> SubRegMap; 4218334Speter 4318334Speter CodeGenRegister(Record *R, unsigned Enum); 4418334Speter 4518334Speter const std::string &getName() const; 4618334Speter 4718334Speter // Get a map of sub-registers computed lazily. 4818334Speter // This includes unique entries for all sub-sub-registers. 4918334Speter const SubRegMap &getSubRegs(CodeGenRegBank&); 5018334Speter 5118334Speter const SubRegMap &getSubRegs() const { 5218334Speter assert(SubRegsComplete && "Must precompute sub-registers"); 5318334Speter return SubRegs; 5418334Speter } 5518334Speter 56132718Skan // Add sub-registers to OSet following a pre-order defined by the .td file. 57132718Skan void addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const; 58132718Skan 59132718Skan // List of super-registers in topological order, small to large. 6018334Speter typedef std::vector<CodeGenRegister*> SuperRegList; 6118334Speter 62132718Skan // Get the list of super-registers. 6318334Speter // This is only valid after computeDerivedInfo has visited all registers. 6418334Speter const SuperRegList &getSuperRegs() const { 6518334Speter assert(SubRegsComplete && "Must precompute sub-registers"); 6618334Speter return SuperRegs; 6718334Speter } 6818334Speter 6918334Speter // Order CodeGenRegister pointers by EnumValue. 7018334Speter struct Less { 7118334Speter bool operator()(const CodeGenRegister *A, 7218334Speter const CodeGenRegister *B) const { 7318334Speter assert(A && B); 7418334Speter return A->EnumValue < B->EnumValue; 7518334Speter } 7618334Speter }; 7718334Speter 78169689Skan // Canonically ordered set. 79169689Skan typedef std::set<const CodeGenRegister*, Less> Set; 8018334Speter 8118334Speter private: 8218334Speter bool SubRegsComplete; 83169689Skan SubRegMap SubRegs; 84169689Skan SuperRegList SuperRegs; 85132718Skan }; 8618334Speter 8718334Speter 8818334Speter class CodeGenRegisterClass { 8918334Speter CodeGenRegister::Set Members; 9018334Speter // Allocation orders. Order[0] always contains all registers in Members. 9118334Speter std::vector<SmallVector<Record*, 16> > Orders; 9218334Speter // Bit mask of sub-classes including this, indexed by their EnumValue. 9390075Sobrien BitVector SubClasses; 9418334Speter // List of super-classes, topologocally ordered to have the larger classes 9518334Speter // first. This is the same as sorting by EnumValue. 9618334Speter SmallVector<CodeGenRegisterClass*, 4> SuperClasses; 9718334Speter Record *TheDef; 9818334Speter std::string Name; 9918334Speter 10018334Speter // For a synthesized class, inherit missing properties from the nearest 10118334Speter // super-class. 10218334Speter void inheritProperties(CodeGenRegBank&); 10318334Speter 10418334Speter // Map SubRegIndex -> sub-class 10518334Speter DenseMap<Record*, CodeGenRegisterClass*> SubClassWithSubReg; 10618334Speter 10718334Speter public: 10818334Speter unsigned EnumValue; 10950397Sobrien std::string Namespace; 11018334Speter std::vector<MVT::SimpleValueType> VTs; 11118334Speter unsigned SpillSize; 11218334Speter unsigned SpillAlignment; 11318334Speter int CopyCost; 11418334Speter bool Allocatable; 11518334Speter // Map SubRegIndex -> RegisterClass 11618334Speter DenseMap<Record*,Record*> SubRegClasses; 11718334Speter std::string AltOrderSelect; 11818334Speter 11918334Speter // Return the Record that defined this class, or NULL if the class was 12018334Speter // created by TableGen. 12118334Speter Record *getDef() const { return TheDef; } 12218334Speter 12318334Speter const std::string &getName() const { return Name; } 12418334Speter std::string getQualifiedName() const; 12518334Speter const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;} 12618334Speter unsigned getNumValueTypes() const { return VTs.size(); } 12718334Speter 128132718Skan MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const { 12918334Speter if (VTNum < VTs.size()) 13090075Sobrien return VTs[VTNum]; 13190075Sobrien assert(0 && "VTNum greater than number of ValueTypes in RegClass!"); 13290075Sobrien abort(); 13390075Sobrien } 13418334Speter 13518334Speter // Return true if this this class contains the register. 13618334Speter bool contains(const CodeGenRegister*) const; 13718334Speter 13818334Speter // Returns true if RC is a subclass. 13918334Speter // RC is a sub-class of this class if it is a valid replacement for any 14018334Speter // instruction operand where a register of this classis required. It must 14118334Speter // satisfy these conditions: 14218334Speter // 14318334Speter // 1. All RC registers are also in this. 14418334Speter // 2. The RC spill size must not be smaller than our spill size. 14518334Speter // 3. RC spill alignment must be compatible with ours. 14618334Speter // 14718334Speter bool hasSubClass(const CodeGenRegisterClass *RC) const { 14818334Speter return SubClasses.test(RC->EnumValue); 14918334Speter } 15018334Speter 15118334Speter // getSubClassWithSubReg - Returns the largest sub-class where all 15218334Speter // registers have a SubIdx sub-register. 15318334Speter CodeGenRegisterClass *getSubClassWithSubReg(Record *SubIdx) const { 15418334Speter return SubClassWithSubReg.lookup(SubIdx); 15518334Speter } 15618334Speter 15718334Speter void setSubClassWithSubReg(Record *SubIdx, CodeGenRegisterClass *SubRC) { 15818334Speter SubClassWithSubReg[SubIdx] = SubRC; 15918334Speter } 16018334Speter 16118334Speter // getSubClasses - Returns a constant BitVector of subclasses indexed by 16218334Speter // EnumValue. 16318334Speter // The SubClasses vector includs an entry for this class. 16418334Speter const BitVector &getSubClasses() const { return SubClasses; } 16518334Speter 16618334Speter // getSuperClasses - Returns a list of super classes ordered by EnumValue. 16718334Speter // The array does not include an entry for this class. 16818334Speter ArrayRef<CodeGenRegisterClass*> getSuperClasses() const { 16918334Speter return SuperClasses; 17018334Speter } 17118334Speter 17218334Speter // Returns an ordered list of class members. 17318334Speter // The order of registers is the same as in the .td file. 17418334Speter // No = 0 is the default allocation order, No = 1 is the first alternative. 17518334Speter ArrayRef<Record*> getOrder(unsigned No = 0) const { 17618334Speter return Orders[No]; 17718334Speter } 17818334Speter 17918334Speter // Return the total number of allocation orders available. 18018334Speter unsigned getNumOrders() const { return Orders.size(); } 18118334Speter 18218334Speter // Get the set of registers. This set contains the same registers as 18318334Speter // getOrder(0). 18418334Speter const CodeGenRegister::Set &getMembers() const { return Members; } 18518334Speter 18618334Speter CodeGenRegisterClass(CodeGenRegBank&, Record *R); 18718334Speter 18818334Speter // A key representing the parts of a register class used for forming 18918334Speter // sub-classes. Note the ordering provided by this key is not the same as 19018334Speter // the topological order used for the EnumValues. 19118334Speter struct Key { 19218334Speter const CodeGenRegister::Set *Members; 19318334Speter unsigned SpillSize; 19418334Speter unsigned SpillAlignment; 19518334Speter 19618334Speter Key(const Key &O) 19718334Speter : Members(O.Members), 19818334Speter SpillSize(O.SpillSize), 19918334Speter SpillAlignment(O.SpillAlignment) {} 20018334Speter 20118334Speter Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0) 20218334Speter : Members(M), SpillSize(S), SpillAlignment(A) {} 20318334Speter 20418334Speter Key(const CodeGenRegisterClass &RC) 20518334Speter : Members(&RC.getMembers()), 20618334Speter SpillSize(RC.SpillSize), 20718334Speter SpillAlignment(RC.SpillAlignment) {} 20818334Speter 20918334Speter // Lexicographical order of (Members, SpillSize, SpillAlignment). 21018334Speter bool operator<(const Key&) const; 21118334Speter }; 21218334Speter 21318334Speter // Create a non-user defined register class. 21418334Speter CodeGenRegisterClass(StringRef Name, Key Props); 21518334Speter 21618334Speter // Called by CodeGenRegBank::CodeGenRegBank(). 21718334Speter static void computeSubClasses(CodeGenRegBank&); 21818334Speter }; 21918334Speter 22018334Speter // CodeGenRegBank - Represent a target's registers and the relations between 22118334Speter // them. 22218334Speter class CodeGenRegBank { 22318334Speter RecordKeeper &Records; 22418334Speter SetTheory Sets; 22518334Speter 22618334Speter std::vector<Record*> SubRegIndices; 22718334Speter unsigned NumNamedIndices; 22818334Speter std::vector<CodeGenRegister*> Registers; 22918334Speter DenseMap<Record*, CodeGenRegister*> Def2Reg; 23018334Speter 23118334Speter // Register classes. 23218334Speter std::vector<CodeGenRegisterClass*> RegClasses; 23318334Speter DenseMap<Record*, CodeGenRegisterClass*> Def2RC; 23418334Speter typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap; 23518334Speter RCKeyMap Key2RC; 23618334Speter 23718334Speter // Add RC to *2RC maps. 238132718Skan void addToMaps(CodeGenRegisterClass*); 23950397Sobrien 24050397Sobrien // Infer missing register classes. 24118334Speter void computeInferredRegisterClasses(); 24218334Speter 24318334Speter // Composite SubRegIndex instances. 24418334Speter // Map (SubRegIndex, SubRegIndex) -> SubRegIndex. 24518334Speter typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap; 24618334Speter CompositeMap Composite; 24718334Speter 24818334Speter // Populate the Composite map from sub-register relationships. 24918334Speter void computeComposites(); 25018334Speter 25118334Speter public: 25218334Speter CodeGenRegBank(RecordKeeper&); 25318334Speter 25418334Speter SetTheory &getSets() { return Sets; } 25518334Speter 25618334Speter // Sub-register indices. The first NumNamedIndices are defined by the user 25718334Speter // in the .td files. The rest are synthesized such that all sub-registers 25818334Speter // have a unique name. 25918334Speter const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; } 26018334Speter unsigned getNumNamedIndices() { return NumNamedIndices; } 26118334Speter 26218334Speter // Map a SubRegIndex Record to its enum value. 26318334Speter unsigned getSubRegIndexNo(Record *idx); 26418334Speter 26518334Speter // Find or create a sub-register index representing the A+B composition. 26618334Speter Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false); 26718334Speter 26818334Speter const std::vector<CodeGenRegister*> &getRegisters() { return Registers; } 26918334Speter 27018334Speter // Find a register from its Record def. 27118334Speter CodeGenRegister *getReg(Record*); 27218334Speter 27318334Speter ArrayRef<CodeGenRegisterClass*> getRegClasses() const { 27418334Speter return RegClasses; 27518334Speter } 27618334Speter 27718334Speter // Find a register class from its def. 27818334Speter CodeGenRegisterClass *getRegClass(Record*); 27918334Speter 28018334Speter /// getRegisterClassForRegister - Find the register class that contains the 28118334Speter /// specified physical register. If the register is not in a register 28218334Speter /// class, return null. If the register is in multiple classes, and the 28318334Speter /// classes have a superset-subset relationship and the same set of types, 28418334Speter /// return the superclass. Otherwise return null. 28518334Speter const CodeGenRegisterClass* getRegClassForRegister(Record *R); 28618334Speter 28718334Speter // Computed derived records such as missing sub-register indices. 28818334Speter void computeDerivedInfo(); 28918334Speter 29018334Speter // Compute full overlap sets for every register. These sets include the 29118334Speter // rarely used aliases that are neither sub nor super-registers. 29218334Speter // 29318334Speter // Map[R1].count(R2) is reflexive and symmetric, but not transitive. 29418334Speter // 29518334Speter // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2]. 29618334Speter void computeOverlaps(std::map<const CodeGenRegister*, 29718334Speter CodeGenRegister::Set> &Map); 29818334Speter }; 29918334Speter} 30050397Sobrien 30150397Sobrien#endif 30250397Sobrien