CodeGenRegisters.h revision 026dc223aeef2579d63f395007491e37d6cde3a0
18dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner//===- CodeGenRegisters.h - Register and RegisterClass Info -----*- C++ -*-===// 23da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman// 38dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// The LLVM Compiler Infrastructure 48dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// 53060910e290949a9ac5eda8726d030790c4d60ffChris Lattner// This file is distributed under the University of Illinois Open Source 63060910e290949a9ac5eda8726d030790c4d60ffChris Lattner// License. See LICENSE.TXT for details. 73da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman// 88dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner//===----------------------------------------------------------------------===// 98dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// 108dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// This file defines structures to encapsulate information gleaned from the 118dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// target register and register class definitions. 128dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner// 138dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner//===----------------------------------------------------------------------===// 148dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 158dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner#ifndef CODEGEN_REGISTERS_H 168dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner#define CODEGEN_REGISTERS_H 178dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 18b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen#include "Record.h" 19ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov#include "llvm/CodeGen/ValueTypes.h" 2009bc0298650c76db1a06e20ca84c1dcb34071600Jakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 21026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 22b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen#include <cstdlib> 23b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen#include <map> 248dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner#include <string> 25a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher#include <set> 26b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen#include <vector> 278dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 288dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattnernamespace llvm { 29b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen class CodeGenRegBank; 308dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 318dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner /// CodeGenRegister - Represents a register definition. 328dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner struct CodeGenRegister { 338dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner Record *TheDef; 3417fad045cccf34822d3163ada9e70a8f4528746eJim Grosbach unsigned EnumValue; 356bfba2e5af163442a1c6b11fe14aa9df9101cfd7Jakob Stoklund Olesen unsigned CostPerUse; 36b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 37b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Map SubRegIndex -> Register. 38b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen typedef std::map<Record*, CodeGenRegister*, LessRecord> SubRegMap; 39b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 40b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister(Record *R, unsigned Enum); 41b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 42b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const std::string &getName() const; 43b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 44b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Get a map of sub-registers computed lazily. 45b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // This includes unique entries for all sub-sub-registers. 46b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const SubRegMap &getSubRegs(CodeGenRegBank&); 47b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 48b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const SubRegMap &getSubRegs() const { 49b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen assert(SubRegsComplete && "Must precompute sub-registers"); 50b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return SubRegs; 51b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 52b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 53026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Add sub-registers to OSet following a pre-order defined by the .td file. 54026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen void addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const; 55026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 56026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // List of super-registers in topological order, small to large. 57026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen typedef std::vector<CodeGenRegister*> SuperRegList; 58026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 59026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Get the list of super-registers. 60026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // This is only valid after computeDerivedInfo has visited all registers. 61026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const SuperRegList &getSuperRegs() const { 62026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen assert(SubRegsComplete && "Must precompute sub-registers"); 63026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen return SuperRegs; 64026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 65026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 66026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Order CodeGenRegister pointers by EnumValue. 67026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen struct Less { 68026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen bool operator()(const CodeGenRegister *A, const CodeGenRegister *B) { 69026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen return A->EnumValue < B->EnumValue; 70026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 71026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen }; 72026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 73026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Canonically ordered set. 74026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen typedef std::set<CodeGenRegister*, Less> Set; 75026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 76b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen private: 77b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen bool SubRegsComplete; 78b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegMap SubRegs; 79026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen SuperRegList SuperRegs; 808dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner }; 818dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 828dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 838dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner struct CodeGenRegisterClass { 84056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner Record *TheDef; 85c67c18fd2378fd2394c42f12b67897e7eba02d5cChris Lattner std::string Namespace; 86056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner std::vector<Record*> Elements; 87825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson std::vector<MVT::SimpleValueType> VTs; 88056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner unsigned SpillSize; 89056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner unsigned SpillAlignment; 90a3ca3149f2b59c512c50aab330b5a0d8efddeffaEvan Cheng int CopyCost; 91f462e3fac7ac67503657d63dc35330d0b19359b3Jakob Stoklund Olesen bool Allocatable; 9209bc0298650c76db1a06e20ca84c1dcb34071600Jakob Stoklund Olesen // Map SubRegIndex -> RegisterClass 9309bc0298650c76db1a06e20ca84c1dcb34071600Jakob Stoklund Olesen DenseMap<Record*,Record*> SubRegClasses; 94ac46893e246748876d1155bb0c9e8892e52acab7Chris Lattner std::string MethodProtos, MethodBodies; 95056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner 96056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner const std::string &getName() const; 97825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson const std::vector<MVT::SimpleValueType> &getValueTypes() const {return VTs;} 985c4736a3da04795ba8d04e152e151afd6942e2f1Chris Lattner unsigned getNumValueTypes() const { return VTs.size(); } 995d4314ef720630e6547fe41efec1608d4c14c78eJim Grosbach 100825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson MVT::SimpleValueType getValueTypeNum(unsigned VTNum) const { 1016510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman if (VTNum < VTs.size()) 1026510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman return VTs[VTNum]; 1036510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman assert(0 && "VTNum greater than number of ValueTypes in RegClass!"); 1046510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman abort(); 1056510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman } 1065d4314ef720630e6547fe41efec1608d4c14c78eJim Grosbach 10790fd797dc739319347861d4f3984bc8952ae9a29Chris Lattner bool containsRegister(Record *R) const { 10890fd797dc739319347861d4f3984bc8952ae9a29Chris Lattner for (unsigned i = 0, e = Elements.size(); i != e; ++i) 10990fd797dc739319347861d4f3984bc8952ae9a29Chris Lattner if (Elements[i] == R) return true; 11090fd797dc739319347861d4f3984bc8952ae9a29Chris Lattner return false; 11190fd797dc739319347861d4f3984bc8952ae9a29Chris Lattner } 1125d4314ef720630e6547fe41efec1608d4c14c78eJim Grosbach 113a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // Returns true if RC is a strict subclass. 114a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // RC is a sub-class of this class if it is a valid replacement for any 1155d4314ef720630e6547fe41efec1608d4c14c78eJim Grosbach // instruction operand where a register of this classis required. It must 116a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // satisfy these conditions: 117a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // 118a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // 1. All RC registers are also in this. 119a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // 2. The RC spill size must not be smaller than our spill size. 120a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // 3. RC spill alignment must be compatible with ours. 121a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher // 122a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher bool hasSubClass(const CodeGenRegisterClass *RC) const { 123a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher 124a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher if (RC->Elements.size() > Elements.size() || 125a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher (SpillAlignment && RC->SpillAlignment % SpillAlignment) || 126a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher SpillSize > RC->SpillSize) 127a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher return false; 128a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher 129a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher std::set<Record*> RegSet; 130a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher for (unsigned i = 0, e = Elements.size(); i != e; ++i) { 131a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher Record *Reg = Elements[i]; 132a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher RegSet.insert(Reg); 133a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher } 134a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher 135a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher for (unsigned i = 0, e = RC->Elements.size(); i != e; ++i) { 136a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher Record *Reg = RC->Elements[i]; 137a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher if (!RegSet.count(Reg)) 138a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher return false; 139a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher } 140a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher 141a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher return true; 142a2c9188560eb9a7d494960fefd28cf0998d9a78fEric Christopher } 1436510b22cec7de4f0acc9965ec24c3668a6a8a87eNate Begeman 144056afeface2ac98664ed8fa4799b46178a4a6fe3Chris Lattner CodeGenRegisterClass(Record *R); 1458dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner }; 146dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 147dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen // CodeGenRegBank - Represent a target's registers and the relations between 148dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen // them. 149dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen class CodeGenRegBank { 150dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen RecordKeeper &Records; 151dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::vector<Record*> SubRegIndices; 152dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen unsigned NumNamedIndices; 153b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::vector<CodeGenRegister> Registers; 154b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen DenseMap<Record*, CodeGenRegister*> Def2Reg; 155b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 156b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Composite SubRegIndex instances. 157b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Map (SubRegIndex, SubRegIndex) -> SubRegIndex. 158b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen typedef DenseMap<std::pair<Record*, Record*>, Record*> CompositeMap; 159b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CompositeMap Composite; 160b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 161b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Populate the Composite map from sub-register relationships. 162b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen void computeComposites(); 163dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 164dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen public: 165dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen CodeGenRegBank(RecordKeeper&); 166dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 167b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Sub-register indices. The first NumNamedIndices are defined by the user 168b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // in the .td files. The rest are synthesized such that all sub-registers 169b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // have a unique name. 170dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen const std::vector<Record*> &getSubRegIndices() { return SubRegIndices; } 171dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen unsigned getNumNamedIndices() { return NumNamedIndices; } 172dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 173dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen // Map a SubRegIndex Record to its enum value. 174dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen unsigned getSubRegIndexNo(Record *idx); 175dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 176b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Find or create a sub-register index representing the A+B composition. 177b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Record *getCompositeSubRegIndex(Record *A, Record *B, bool create = false); 178b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 179b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const std::vector<CodeGenRegister> &getRegisters() { return Registers; } 180b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 181b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Find a register from its Record def. 182b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *getReg(Record*); 183b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 184b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Computed derived records such as missing sub-register indices. 185b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen void computeDerivedInfo(); 186026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 187026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Compute full overlap sets for every register. These sets include the 188026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // rarely used aliases that are neither sub nor super-registers. 189026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // 190026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Map[R1].count(R2) is reflexive and symmetric, but not transitive. 191026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // 192026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2]. 193026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen void computeOverlaps(std::map<const CodeGenRegister*, 194026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister::Set> &Map); 195dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen }; 1968dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner} 1978dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner 1988dab6ca9c638709e7b60b942107ab88b3ef7d06dChris Lattner#endif 199