CodeGenRegisters.cpp revision 7c788888872233748da10a8177a9a1eb176c1bc8
1f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===// 2f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// 3f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// 5f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// 8f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// 10f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// This file defines structures to encapsulate information gleaned from the 11f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// target register and register class definitions. 12f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// 13f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 14f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 15f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen#include "CodeGenRegisters.h" 16f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen#include "CodeGenTarget.h" 177c788888872233748da10a8177a9a1eb176c1bc8Peter Collingbourne#include "llvm/TableGen/Error.h" 18b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 197dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 20f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen#include "llvm/ADT/StringExtras.h" 21f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 22f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesenusing namespace llvm; 23f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 24f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 25f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// CodeGenRegister 26f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 27f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 28b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenCodeGenRegister::CodeGenRegister(Record *R, unsigned Enum) 29b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen : TheDef(R), 30b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen EnumValue(Enum), 31b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CostPerUse(R->getValueAsInt("CostPerUse")), 32b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegsComplete(false) 33b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen{} 34f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 35f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesenconst std::string &CodeGenRegister::getName() const { 36f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen return TheDef->getName(); 37f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 38f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 39b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesennamespace { 40b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen struct Orphan { 41b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *SubReg; 42b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Record *First, *Second; 43b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Orphan(CodeGenRegister *r, Record *a, Record *b) 44b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen : SubReg(r), First(a), Second(b) {} 45b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen }; 46b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 47b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 48b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenconst CodeGenRegister::SubRegMap & 49b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenCodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) { 50b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Only compute this map once. 51b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (SubRegsComplete) 52b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return SubRegs; 53b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegsComplete = true; 54b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 55b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::vector<Record*> SubList = TheDef->getValueAsListOfDefs("SubRegs"); 56b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::vector<Record*> Indices = TheDef->getValueAsListOfDefs("SubRegIndices"); 57b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (SubList.size() != Indices.size()) 58b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "Register " + getName() + 59b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen " SubRegIndices doesn't match SubRegs"); 60b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 61b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // First insert the direct subregs and make sure they are fully indexed. 62b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = SubList.size(); i != e; ++i) { 63b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *SR = RegBank.getReg(SubList[i]); 64b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!SubRegs.insert(std::make_pair(Indices[i], SR)).second) 65b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "SubRegIndex " + Indices[i]->getName() + 66b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen " appears twice in Register " + getName()); 67b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 68b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 69b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Keep track of inherited subregs and how they can be reached. 70b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SmallVector<Orphan, 8> Orphans; 71b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 72b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Clone inherited subregs and place duplicate entries on Orphans. 73b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Here the order is important - earlier subregs take precedence. 74b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = SubList.size(); i != e; ++i) { 75b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *SR = RegBank.getReg(SubList[i]); 76b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const SubRegMap &Map = SR->getSubRegs(RegBank); 77026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 78026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Add this as a super-register of SR now all sub-registers are in the list. 79026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // This creates a topological ordering, the exact order depends on the 80026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // order getSubRegs is called on all registers. 81026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen SR->SuperRegs.push_back(this); 82026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 83b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE; 84026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen ++SI) { 85b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!SubRegs.insert(*SI).second) 86b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Orphans.push_back(Orphan(SI->second, Indices[i], SI->first)); 87026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 88026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Noop sub-register indexes are possible, so avoid duplicates. 89026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen if (SI->second != SR) 90026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen SI->second->SuperRegs.push_back(this); 91026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 92b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 93b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 94b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Process the composites. 9505bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *Comps = TheDef->getValueAsListInit("CompositeIndices"); 96b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Comps->size(); i != e; ++i) { 9705bce0beee87512e52428d4b80f5a8e79a949576David Greene DagInit *Pat = dynamic_cast<DagInit*>(Comps->getElement(i)); 98b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!Pat) 99b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "Invalid dag '" + 100b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Comps->getElement(i)->getAsString() + 101b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen "' in CompositeIndices"); 10205bce0beee87512e52428d4b80f5a8e79a949576David Greene DefInit *BaseIdxInit = dynamic_cast<DefInit*>(Pat->getOperator()); 103b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!BaseIdxInit || !BaseIdxInit->getDef()->isSubClassOf("SubRegIndex")) 104b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + 105b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Pat->getAsString()); 106b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 107b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Resolve list of subreg indices into R2. 108b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *R2 = this; 109b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (DagInit::const_arg_iterator di = Pat->arg_begin(), 110b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen de = Pat->arg_end(); di != de; ++di) { 11105bce0beee87512e52428d4b80f5a8e79a949576David Greene DefInit *IdxInit = dynamic_cast<DefInit*>(*di); 112b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!IdxInit || !IdxInit->getDef()->isSubClassOf("SubRegIndex")) 113b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + 114b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Pat->getAsString()); 115b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen const SubRegMap &R2Subs = R2->getSubRegs(RegBank); 116b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegMap::const_iterator ni = R2Subs.find(IdxInit->getDef()); 117b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (ni == R2Subs.end()) 118b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen throw TGError(TheDef->getLoc(), "Composite " + Pat->getAsString() + 119b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen " refers to bad index in " + R2->getName()); 120b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen R2 = ni->second; 121b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 122b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 123b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Insert composite index. Allow overriding inherited indices etc. 124b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegs[BaseIdxInit->getDef()] = R2; 125b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 126b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // R2 is no longer an orphan. 127b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned j = 0, je = Orphans.size(); j != je; ++j) 128b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Orphans[j].SubReg == R2) 129b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Orphans[j].SubReg = 0; 130b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 131b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 132b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Now Orphans contains the inherited subregisters without a direct index. 133b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Create inferred indexes for all missing entries. 134b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Orphans.size(); i != e; ++i) { 135b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Orphan &O = Orphans[i]; 136b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!O.SubReg) 137b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen continue; 138b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegs[RegBank.getCompositeSubRegIndex(O.First, O.Second, true)] = 139b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen O.SubReg; 140b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 141b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return SubRegs; 142b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 143b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 144026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesenvoid 145026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund OlesenCodeGenRegister::addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const { 146026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen assert(SubRegsComplete && "Must precompute sub-registers"); 147026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen std::vector<Record*> Indices = TheDef->getValueAsListOfDefs("SubRegIndices"); 148026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen for (unsigned i = 0, e = Indices.size(); i != e; ++i) { 149026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister *SR = SubRegs.find(Indices[i])->second; 150026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen if (OSet.insert(SR)) 151026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen SR->addSubRegsPreOrder(OSet); 152026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 153026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen} 154026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 155f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 1564ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// RegisterTuples 1574ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1584ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 1594ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// A RegisterTuples def is used to generate pseudo-registers from lists of 1604ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// sub-registers. We provide a SetTheory expander class that returns the new 1614ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// registers. 1624ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesennamespace { 1634ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesenstruct TupleExpander : SetTheory::Expander { 1644ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) { 1654ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::vector<Record*> Indices = Def->getValueAsListOfDefs("SubRegIndices"); 1664ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned Dim = Indices.size(); 16705bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *SubRegs = Def->getValueAsListInit("SubRegs"); 1684ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Dim != SubRegs->getSize()) 1694ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen throw TGError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); 1704ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Dim < 2) 1714ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen throw TGError(Def->getLoc(), "Tuples must have at least 2 sub-registers"); 1724ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 1734ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Evaluate the sub-register lists to be zipped. 1744ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned Length = ~0u; 1754ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen SmallVector<SetTheory::RecSet, 4> Lists(Dim); 1764ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0; i != Dim; ++i) { 1774ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen ST.evaluate(SubRegs->getElement(i), Lists[i]); 1784ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Length = std::min(Length, unsigned(Lists[i].size())); 1794ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 1804ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 1814ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Length == 0) 1824ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen return; 1834ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 1844ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Precompute some types. 1854ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *RegisterCl = Def->getRecords().getClass("Register"); 18677f8274c7d4bfb5e2a449eb49dc78dcae37e5457Jakob Stoklund Olesen RecTy *RegisterRecTy = RecordRecTy::get(RegisterCl); 18705bce0beee87512e52428d4b80f5a8e79a949576David Greene StringInit *BlankName = StringInit::get(""); 1884ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 1894ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Zip them up. 1904ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned n = 0; n != Length; ++n) { 1914ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::string Name; 1924ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *Proto = Lists[0][n]; 19305bce0beee87512e52428d4b80f5a8e79a949576David Greene std::vector<Init*> Tuple; 1944ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned CostPerUse = 0; 1954ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0; i != Dim; ++i) { 1964ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *Reg = Lists[i][n]; 1974ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (i) Name += '_'; 1984ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Name += Reg->getName(); 19977f8274c7d4bfb5e2a449eb49dc78dcae37e5457Jakob Stoklund Olesen Tuple.push_back(DefInit::get(Reg)); 2004ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen CostPerUse = std::max(CostPerUse, 2014ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned(Reg->getValueAsInt("CostPerUse"))); 2024ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2034ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2044ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Create a new Record representing the synthesized register. This record 2054ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // is only for consumption by CodeGenRegister, it is not added to the 2064ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // RecordKeeper. 2074ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *NewReg = new Record(Name, Def->getLoc(), Def->getRecords()); 2084ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Elts.insert(NewReg); 2094ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2104ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy Proto super-classes. 2114ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0, e = Proto->getSuperClasses().size(); i != e; ++i) 2124ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen NewReg->addSuperClass(Proto->getSuperClasses()[i]); 2134ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2144ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy Proto fields. 2154ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) { 2164ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RecordVal RV = Proto->getValues()[i]; 2174ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2184ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Replace the sub-register list with Tuple. 2194ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (RV.getName() == "SubRegs") 220dcd35c797d458d8b1dbc36cf7f1504166d5b2f16David Greene RV.setValue(ListInit::get(Tuple, RegisterRecTy)); 2214ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2224ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Provide a blank AsmName. MC hacks are required anyway. 2234ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (RV.getName() == "AsmName") 2244ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RV.setValue(BlankName); 2254ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2264ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // CostPerUse is aggregated from all Tuple members. 2274ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (RV.getName() == "CostPerUse") 228dcd35c797d458d8b1dbc36cf7f1504166d5b2f16David Greene RV.setValue(IntInit::get(CostPerUse)); 2294ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2304ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy fields from the RegisterTuples def. 2314ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (RV.getName() == "SubRegIndices" || 2324ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RV.getName() == "CompositeIndices") { 2334ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen NewReg->addValue(*Def->getValue(RV.getName())); 2344ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen continue; 2354ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2364ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2374ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Some fields get their default uninitialized value. 2384ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (RV.getName() == "DwarfNumbers" || 2394ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RV.getName() == "DwarfAlias" || 2404ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RV.getName() == "Aliases") { 2419b718e88642963bfb519c47b70d1daf5d2126325Jakob Stoklund Olesen if (const RecordVal *DefRV = RegisterCl->getValue(RV.getName())) 2429b718e88642963bfb519c47b70d1daf5d2126325Jakob Stoklund Olesen NewReg->addValue(*DefRV); 2434ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen continue; 2444ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2454ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2464ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Everything else is copied from Proto. 2474ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen NewReg->addValue(RV); 2484ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2494ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2504ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 2514ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen}; 2524ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen} 2534ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 2544ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 255f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// CodeGenRegisterClass 256f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 257f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 258ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund OlesenCodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) 2597dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen : TheDef(R), EnumValue(-1) { 260f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // Rename anonymous register classes. 261f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (R->getName().size() > 9 && R->getName()[9] == '.') { 262f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen static unsigned AnonCounter = 0; 263f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen R->setName("AnonRegClass_"+utostr(AnonCounter++)); 264f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 265f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 266f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes"); 267f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen for (unsigned i = 0, e = TypeList.size(); i != e; ++i) { 268f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Record *Type = TypeList[i]; 269f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!Type->isSubClassOf("ValueType")) 270f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen throw "RegTypes list member '" + Type->getName() + 271f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen "' does not derive from the ValueType class!"; 272f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen VTs.push_back(getValueType(Type)); 273f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 274f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!"); 275f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 276b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Default allocation order always contains all registers. 27759f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen Elements = RegBank.getSets().expand(R); 27859f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen for (unsigned i = 0, e = Elements->size(); i != e; ++i) 27959f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen Members.insert(RegBank.getReg((*Elements)[i])); 280f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 281b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Alternative allocation orders may be subsets. 28205bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *Alts = R->getValueAsListInit("AltOrders"); 283b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen AltOrders.resize(Alts->size()); 284b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen SetTheory::RecSet Order; 285b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen for (unsigned i = 0, e = Alts->size(); i != e; ++i) { 286b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen RegBank.getSets().evaluate(Alts->getElement(i), Order); 287b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen AltOrders[i].append(Order.begin(), Order.end()); 288b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Verify that all altorder members are regclass members. 289b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen while (!Order.empty()) { 290b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen CodeGenRegister *Reg = RegBank.getReg(Order.back()); 291b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen Order.pop_back(); 292b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen if (!contains(Reg)) 293b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen throw TGError(R->getLoc(), " AltOrder register " + Reg->getName() + 294b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen " is not a class member"); 295b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen } 296b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen } 297b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen 298f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // SubRegClasses is a list<dag> containing (RC, subregindex, ...) dags. 29905bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *SRC = R->getValueAsListInit("SubRegClasses"); 300f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen for (ListInit::const_iterator i = SRC->begin(), e = SRC->end(); i != e; ++i) { 30105bce0beee87512e52428d4b80f5a8e79a949576David Greene DagInit *DAG = dynamic_cast<DagInit*>(*i); 302f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!DAG) throw "SubRegClasses must contain DAGs"; 30305bce0beee87512e52428d4b80f5a8e79a949576David Greene DefInit *DAGOp = dynamic_cast<DefInit*>(DAG->getOperator()); 304f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Record *RCRec; 305f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!DAGOp || !(RCRec = DAGOp->getDef())->isSubClassOf("RegisterClass")) 306f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen throw "Operator '" + DAG->getOperator()->getAsString() + 307f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen "' in SubRegClasses is not a RegisterClass"; 308f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // Iterate over args, all SubRegIndex instances. 309f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen for (DagInit::const_arg_iterator ai = DAG->arg_begin(), ae = DAG->arg_end(); 310f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen ai != ae; ++ai) { 31105bce0beee87512e52428d4b80f5a8e79a949576David Greene DefInit *Idx = dynamic_cast<DefInit*>(*ai); 312f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Record *IdxRec; 313f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!Idx || !(IdxRec = Idx->getDef())->isSubClassOf("SubRegIndex")) 314f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen throw "Argument '" + (*ai)->getAsString() + 315f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen "' in SubRegClasses is not a SubRegIndex"; 316f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!SubRegClasses.insert(std::make_pair(IdxRec, RCRec)).second) 317f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen throw "SubRegIndex '" + IdxRec->getName() + "' mentioned twice"; 318f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 319f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 320f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 321f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // Allow targets to override the size in bits of the RegisterClass. 322f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen unsigned Size = R->getValueAsInt("Size"); 323f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 324f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Namespace = R->getValueAsString("Namespace"); 325f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen SpillSize = Size ? Size : EVT(VTs[0]).getSizeInBits(); 326f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen SpillAlignment = R->getValueAsInt("Alignment"); 327f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen CopyCost = R->getValueAsInt("CopyCost"); 328f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Allocatable = R->getValueAsBit("isAllocatable"); 329b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen AltOrderSelect = R->getValueAsCode("AltOrderSelect"); 330f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 331f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 332ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesenbool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const { 333ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen return Members.count(Reg); 334ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen} 335ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen 336ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// Returns true if RC is a strict subclass. 337ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// RC is a sub-class of this class if it is a valid replacement for any 338ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// instruction operand where a register of this classis required. It must 339ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// satisfy these conditions: 340ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 341ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 1. All RC registers are also in this. 342ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 2. The RC spill size must not be smaller than our spill size. 343ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 3. RC spill alignment must be compatible with ours. 344ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 34552e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesenstatic bool testSubClass(const CodeGenRegisterClass *A, 34652e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen const CodeGenRegisterClass *B) { 34752e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen return A->SpillAlignment && B->SpillAlignment % A->SpillAlignment == 0 && 34852e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen A->SpillSize <= B->SpillSize && 34952e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen std::includes(A->getMembers().begin(), A->getMembers().end(), 35052e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen B->getMembers().begin(), B->getMembers().end(), 351c6596e2edc406298ff65d27633bd898613533c0bJakob Stoklund Olesen CodeGenRegister::Less()); 352ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen} 353ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen 3547dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// Sorting predicate for register classes. This provides a topological 3557dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// ordering that arranges all register classes before their sub-classes. 3567dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// 3577dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// Register classes with the same registers, spill size, and alignment form a 3587dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// clique. They will be ordered alphabetically. 3597dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// 3607dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesenstatic int TopoOrderRC(const void *PA, const void *PB) { 3617dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen const CodeGenRegisterClass *A = *(const CodeGenRegisterClass* const*)PA; 3627dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen const CodeGenRegisterClass *B = *(const CodeGenRegisterClass* const*)PB; 3637dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A == B) 3647dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 0; 3657dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 3667dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order by descending set size. 3677dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->getOrder().size() > B->getOrder().size()) 3687dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return -1; 3697dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->getOrder().size() < B->getOrder().size()) 3707dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 1; 3717dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 3727dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order by ascending spill size. 3737dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillSize < B->SpillSize) 3747dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return -1; 3757dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillSize > B->SpillSize) 3767dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 1; 3777dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 3787dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order by ascending spill alignment. 3797dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillAlignment < B->SpillAlignment) 3807dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return -1; 3817dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillAlignment > B->SpillAlignment) 3827dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 1; 3837dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 3847dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Finally order by name as a tie breaker. 3857dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return A->getName() < B->getName(); 3867dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen} 3877dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 388f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesenconst std::string &CodeGenRegisterClass::getName() const { 389f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen return TheDef->getName(); 390f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 391f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 392203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen// Compute sub-classes of all register classes. 393203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen// Assume the classes are ordered topologically. 394203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesenvoid CodeGenRegisterClass:: 395203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund OlesencomputeSubClasses(ArrayRef<CodeGenRegisterClass*> RegClasses) { 396203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // Visit backwards so sub-classes are seen first. 397203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen for (unsigned rci = RegClasses.size(); rci; --rci) { 398203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen CodeGenRegisterClass &RC = *RegClasses[rci - 1]; 399203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.resize(RegClasses.size()); 400203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.set(RC.EnumValue); 401203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 402203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // Normally, all subclasses have IDs >= rci, unless RC is part of a clique. 403203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen for (unsigned s = rci; s != RegClasses.size(); ++s) { 404203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen if (RC.SubClasses.test(s)) 405203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen continue; 406203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen CodeGenRegisterClass *SubRC = RegClasses[s]; 40752e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen if (!testSubClass(&RC, SubRC)) 408203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen continue; 409203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // SubRC is a sub-class. Grap all its sub-classes so we won't have to 410203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // check them again. 411203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses |= SubRC->SubClasses; 412203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen } 413203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 414203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // Sweep up missed clique members. They will be immediately preceeding RC. 41552e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen for (unsigned s = rci - 1; s && testSubClass(&RC, RegClasses[s - 1]); --s) 416203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.set(s - 1); 417203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen } 418f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen 419f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen // Compute the SuperClasses lists from the SubClasses vectors. 420f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { 421f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen const BitVector &SC = RegClasses[rci]->getSubClasses(); 422f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen for (int s = SC.find_first(); s >= 0; s = SC.find_next(s)) { 423f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen if (unsigned(s) == rci) 424f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen continue; 425f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen RegClasses[s]->SuperClasses.push_back(RegClasses[rci]); 426f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen } 427f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen } 428203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen} 429203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 430dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 431dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen// CodeGenRegBank 432dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 433dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 434dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund OlesenCodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { 4354ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Configure register Sets to understand register classes and tuples. 43659f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen Sets.addFieldExpander("RegisterClass", "MemberList"); 4374ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Sets.addExpander("RegisterTuples", new TupleExpander()); 43859f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen 439b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Read in the user-defined (named) sub-register indices. 440b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // More indices will be synthesized later. 441dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen SubRegIndices = Records.getAllDerivedDefinitions("SubRegIndex"); 442dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::sort(SubRegIndices.begin(), SubRegIndices.end(), LessRecord()); 443dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen NumNamedIndices = SubRegIndices.size(); 444b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 445b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Read in the register definitions. 446b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register"); 447b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::sort(Regs.begin(), Regs.end(), LessRecord()); 448b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Registers.reserve(Regs.size()); 449b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Assign the enumeration values. 450b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Regs.size(); i != e; ++i) 451abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen getReg(Regs[i]); 4527b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 4534ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Expand tuples and number the new registers. 4544ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::vector<Record*> Tups = 4554ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Records.getAllDerivedDefinitions("RegisterTuples"); 4564ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0, e = Tups.size(); i != e; ++i) { 4574ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen const std::vector<Record*> *TupRegs = Sets.expand(Tups[i]); 4584ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned j = 0, je = TupRegs->size(); j != je; ++j) 4594ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen getReg((*TupRegs)[j]); 4604ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 4614ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 4627b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Read in register class definitions. 4637b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass"); 4647b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (RCs.empty()) 4657b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen throw std::string("No 'RegisterClass' subclasses defined!"); 4667b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 4677b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen RegClasses.reserve(RCs.size()); 46829f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen for (unsigned i = 0, e = RCs.size(); i != e; ++i) { 46929f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen CodeGenRegisterClass *RC = new CodeGenRegisterClass(*this, RCs[i]); 47029f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen RegClasses.push_back(RC); 47129f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen Def2RC[RCs[i]] = RC; 47229f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen } 4737dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order register classes topologically and assign enum values. 4747dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen array_pod_sort(RegClasses.begin(), RegClasses.end(), TopoOrderRC); 4757dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen for (unsigned i = 0, e = RegClasses.size(); i != e; ++i) 4767dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen RegClasses[i]->EnumValue = i; 477203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen CodeGenRegisterClass::computeSubClasses(RegClasses); 478dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen} 479dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 480b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenCodeGenRegister *CodeGenRegBank::getReg(Record *Def) { 481abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *&Reg = Def2Reg[Def]; 482abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen if (Reg) 483b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Reg; 484abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen Reg = new CodeGenRegister(Def, Registers.size() + 1); 485abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen Registers.push_back(Reg); 486abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen return Reg; 487b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 488b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 4897b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund OlesenCodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { 4907b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (CodeGenRegisterClass *RC = Def2RC[Def]) 4917b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return RC; 4927b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 4937b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen throw TGError(Def->getLoc(), "Not a known RegisterClass!"); 4947b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen} 4957b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 496b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenRecord *CodeGenRegBank::getCompositeSubRegIndex(Record *A, Record *B, 497b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen bool create) { 498b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Look for an existing entry. 499b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Record *&Comp = Composite[std::make_pair(A, B)]; 500b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Comp || !create) 501b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Comp; 502b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 503b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // None exists, synthesize one. 504dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::string Name = A->getName() + "_then_" + B->getName(); 505b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Comp = new Record(Name, SMLoc(), Records); 506b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Records.addDef(Comp); 507b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegIndices.push_back(Comp); 508b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Comp; 509dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen} 510dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 511dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesenunsigned CodeGenRegBank::getSubRegIndexNo(Record *idx) { 512dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::vector<Record*>::const_iterator i = 513dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::find(SubRegIndices.begin(), SubRegIndices.end(), idx); 514dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen assert(i != SubRegIndices.end() && "Not a SubRegIndex"); 515dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen return (i - SubRegIndices.begin()) + 1; 516dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen} 517dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 518b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenvoid CodeGenRegBank::computeComposites() { 519b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Precompute all sub-register maps. This will create Composite entries for 520b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // all inferred sub-register indices. 521b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) 522abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen Registers[i]->getSubRegs(*this); 523b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 524b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 525abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *Reg1 = Registers[i]; 526026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(); 527b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(), 528b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen e1 = SRM1.end(); i1 != e1; ++i1) { 529b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Record *Idx1 = i1->first; 530b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *Reg2 = i1->second; 531b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Ignore identity compositions. 532b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Reg1 == Reg2) 533b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen continue; 534026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs(); 535b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Try composing Idx1 with another SubRegIndex. 536b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM2.begin(), 537b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen e2 = SRM2.end(); i2 != e2; ++i2) { 538b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::pair<Record*, Record*> IdxPair(Idx1, i2->first); 539b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *Reg3 = i2->second; 540b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Ignore identity compositions. 541b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Reg2 == Reg3) 542b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen continue; 543b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3. 544b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i1d = SRM1.begin(), 545b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen e1d = SRM1.end(); i1d != e1d; ++i1d) { 546b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (i1d->second == Reg3) { 547b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::pair<CompositeMap::iterator, bool> Ins = 548b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Composite.insert(std::make_pair(IdxPair, i1d->first)); 549b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Conflicting composition? Emit a warning but allow it. 550b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!Ins.second && Ins.first->second != i1d->first) { 551b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen errs() << "Warning: SubRegIndex " << getQualifiedName(Idx1) 552b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen << " and " << getQualifiedName(IdxPair.second) 553b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen << " compose ambiguously as " 554b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen << getQualifiedName(Ins.first->second) << " or " 555b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen << getQualifiedName(i1d->first) << "\n"; 556b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 557b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 558b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 559b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 560b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 561b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 562b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 563b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // We don't care about the difference between (Idx1, Idx2) -> Idx2 and invalid 564b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // compositions, so remove any mappings of that form. 565b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CompositeMap::iterator i = Composite.begin(), e = Composite.end(); 566b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen i != e;) { 567b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CompositeMap::iterator j = i; 568b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen ++i; 569b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (j->first.second == j->second) 570b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Composite.erase(j); 571b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 572b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 573b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 574026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// Compute sets of overlapping registers. 575026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 576026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// The standard set is all super-registers and all sub-registers, but the 577026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// target description can add arbitrary overlapping registers via the 'Aliases' 578026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// field. This complicates things, but we can compute overlapping sets using 579026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// the following rules: 580026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 581026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 1. The relation overlap(A, B) is reflexive and symmetric but not transitive. 582026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 583026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 2. overlap(A, B) implies overlap(A, S) for all S in supers(B). 584026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 585026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// Alternatively: 586026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 587026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// overlap(A, B) iff there exists: 588026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// A' in { A, subregs(A) } and B' in { B, subregs(B) } such that: 589026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// A' = B' or A' in aliases(B') or B' in aliases(A'). 590026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 591026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// Here subregs(A) is the full flattened sub-register set returned by 592026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// A.getSubRegs() while aliases(A) is simply the special 'Aliases' field in the 593026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// description of register A. 594026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 595026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// This also implies that registers with a common sub-register are considered 596026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// overlapping. This can happen when forming register pairs: 597026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 598026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// P0 = (R0, R1) 599026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// P1 = (R1, R2) 600026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// P2 = (R2, R3) 601026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 602026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// In this case, we will infer an overlap between P0 and P1 because of the 603026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// shared sub-register R1. There is no overlap between P0 and P2. 604026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen// 605026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesenvoid CodeGenRegBank:: 606026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund OlesencomputeOverlaps(std::map<const CodeGenRegister*, CodeGenRegister::Set> &Map) { 607026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen assert(Map.empty()); 608026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 609026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Collect overlaps that don't follow from rule 2. 610026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 611abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *Reg = Registers[i]; 612026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister::Set &Overlaps = Map[Reg]; 613026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 614026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Reg overlaps itself. 615026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps.insert(Reg); 616026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 617026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // All super-registers overlap. 618026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SuperRegList &Supers = Reg->getSuperRegs(); 619026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps.insert(Supers.begin(), Supers.end()); 620026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 621026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Form symmetrical relations from the special Aliases[] lists. 622026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen std::vector<Record*> RegList = Reg->TheDef->getValueAsListOfDefs("Aliases"); 623026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen for (unsigned i2 = 0, e2 = RegList.size(); i2 != e2; ++i2) { 624026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister *Reg2 = getReg(RegList[i2]); 625026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister::Set &Overlaps2 = Map[Reg2]; 626026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SuperRegList &Supers2 = Reg2->getSuperRegs(); 627026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Reg overlaps Reg2 which implies it overlaps supers(Reg2). 628026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps.insert(Reg2); 629026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps.insert(Supers2.begin(), Supers2.end()); 630026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps2.insert(Reg); 631026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps2.insert(Supers.begin(), Supers.end()); 632026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 633026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 634026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 635026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen // Apply rule 2. and inherit all sub-register overlaps. 636026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 637abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *Reg = Registers[i]; 638026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister::Set &Overlaps = Map[Reg]; 639026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs(); 640026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM.begin(), 641026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen e2 = SRM.end(); i2 != e2; ++i2) { 642026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen CodeGenRegister::Set &Overlaps2 = Map[i2->second]; 643026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen Overlaps.insert(Overlaps2.begin(), Overlaps2.end()); 644026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 645026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 646026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen} 647026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 648b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenvoid CodeGenRegBank::computeDerivedInfo() { 649b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen computeComposites(); 650b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 651b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 6527b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// getRegisterClassForRegister - Find the register class that contains the 6537b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// specified physical register. If the register is not in a register class, 6547b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// return null. If the register is in multiple classes, and the classes have a 6557b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// superset-subset relationship and the same set of types, return the 6567b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// superclass. Otherwise return null. 6577b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesenconst CodeGenRegisterClass* 6587b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund OlesenCodeGenRegBank::getRegClassForRegister(Record *R) { 659ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen const CodeGenRegister *Reg = getReg(R); 66029f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen ArrayRef<CodeGenRegisterClass*> RCs = getRegClasses(); 6617b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen const CodeGenRegisterClass *FoundRC = 0; 6627b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen for (unsigned i = 0, e = RCs.size(); i != e; ++i) { 66329f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen const CodeGenRegisterClass &RC = *RCs[i]; 664ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (!RC.contains(Reg)) 6657b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 6667b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 6677b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // If this is the first class that contains the register, 6687b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // make a note of it and go on to the next class. 6697b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (!FoundRC) { 6707b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen FoundRC = &RC; 6717b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 6727b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 6737b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 6747b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // If a register's classes have different types, return null. 6757b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (RC.getValueTypes() != FoundRC->getValueTypes()) 6767b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return 0; 6777b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 6787b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Check to see if the previously found class that contains 6797b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // the register is a subclass of the current class. If so, 6807b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // prefer the superclass. 681ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (RC.hasSubClass(FoundRC)) { 6827b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen FoundRC = &RC; 6837b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 6847b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 6857b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 6867b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Check to see if the previously found class that contains 6877b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // the register is a superclass of the current class. If so, 6887b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // prefer the superclass. 689ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (FoundRC->hasSubClass(&RC)) 6907b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 6917b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 6927b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Multiple classes, and neither is a superclass of the other. 6937b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Return null. 6947b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return 0; 6957b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 6967b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return FoundRC; 6977b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen} 698