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" 17d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick#include "llvm/ADT/IntEqClasses.h" 187dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 194ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include "llvm/ADT/SmallVector.h" 20f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen#include "llvm/ADT/StringExtras.h" 21bfb4327baa5bbab78f0da4c8c069482878660a04Jim Grosbach#include "llvm/ADT/Twine.h" 22bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick#include "llvm/Support/Debug.h" 234ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include "llvm/TableGen/Error.h" 24f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 25f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesenusing namespace llvm; 26f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "regalloc-emitter" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 29f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 305fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen// CodeGenSubRegIndex 315fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen//===----------------------------------------------------------------------===// 325fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen 335fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund OlesenCodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum) 34997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen : TheDef(R), EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { 35c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen Name = R->getName(); 36c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen if (R->getValue("Namespace")) 37c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen Namespace = R->getValueAsString("Namespace"); 38bed23081860275c79137f65d592920e7991b8198Ahmed Bougacha Size = R->getValueAsInt("Size"); 39bed23081860275c79137f65d592920e7991b8198Ahmed Bougacha Offset = R->getValueAsInt("Offset"); 405fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen} 415fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen 42c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund OlesenCodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace, 43c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen unsigned Enum) 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TheDef(nullptr), Name(N), Namespace(Nspace), Size(-1), Offset(-1), 45bed23081860275c79137f65d592920e7991b8198Ahmed Bougacha EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { 465fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen} 475fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen 485fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesenstd::string CodeGenSubRegIndex::getQualifiedName() const { 495fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen std::string N = getNamespace(); 505fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen if (!N.empty()) 515fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen N += "::"; 525fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen N += getName(); 535fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen return N; 545fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen} 555fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen 56b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesenvoid CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) { 57c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen if (!TheDef) 58c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen return; 59d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen 60b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf"); 61d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen if (!Comps.empty()) { 62d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen if (Comps.size() != 2) 6361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), 6461131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger "ComposedOf must have exactly two entries"); 65d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]); 66d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]); 67d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen CodeGenSubRegIndex *X = A->addComposite(B, this); 68d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen if (X) 6961131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries"); 70d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen } 71d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen 72d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen std::vector<Record*> Parts = 73d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen TheDef->getValueAsListOfDefs("CoveringSubRegIndices"); 74d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen if (!Parts.empty()) { 75d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen if (Parts.size() < 2) 7661131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), 77bed23081860275c79137f65d592920e7991b8198Ahmed Bougacha "CoveredBySubRegs must have two or more entries"); 78d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen SmallVector<CodeGenSubRegIndex*, 8> IdxParts; 79d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen for (unsigned i = 0, e = Parts.size(); i != e; ++i) 80d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen IdxParts.push_back(RegBank.getSubRegIdx(Parts[i])); 81d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen RegBank.addConcatSubRegIndex(IdxParts, this); 82d024a20bf78086e2bbe7f03ceecbe26c095d7a31Jakob Stoklund Olesen } 83b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen} 84b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen 85a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesenunsigned CodeGenSubRegIndex::computeLaneMask() { 86a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // Already computed? 87a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen if (LaneMask) 88a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen return LaneMask; 89a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 90a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // Recursion guard, shouldn't be required. 91a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen LaneMask = ~0u; 92a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 93a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // The lane mask is simply the union of all sub-indices. 94a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen unsigned M = 0; 95a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen for (CompMap::iterator I = Composed.begin(), E = Composed.end(); I != E; ++I) 96a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen M |= I->second->computeLaneMask(); 97a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen assert(M && "Missing lane mask, sub-register cycle?"); 98a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen LaneMask = M; 99a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen return LaneMask; 100a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen} 101a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 1025fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen//===----------------------------------------------------------------------===// 103f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// CodeGenRegister 104f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 105f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 106b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenCodeGenRegister::CodeGenRegister(Record *R, unsigned Enum) 107b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen : TheDef(R), 108b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen EnumValue(Enum), 109b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CostPerUse(R->getValueAsInt("CostPerUse")), 11031867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")), 111f52baf72c116d9cf8680d25a8e751ce354c7d44bJakob Stoklund Olesen NumNativeRegUnits(0), 11279e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen SubRegsComplete(false), 113b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen SuperRegsComplete(false), 114b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSig(~0u) 115b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen{} 116f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 117148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesenvoid CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { 118148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen std::vector<Record*> SRIs = TheDef->getValueAsListOfDefs("SubRegIndices"); 119148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen std::vector<Record*> SRs = TheDef->getValueAsListOfDefs("SubRegs"); 120148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen 121148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen if (SRIs.size() != SRs.size()) 12261131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), 12361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger "SubRegs and SubRegIndices must have the same size"); 124148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen 125148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen for (unsigned i = 0, e = SRIs.size(); i != e; ++i) { 126148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i])); 127148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen ExplicitSubRegs.push_back(RegBank.getReg(SRs[i])); 128148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen } 129fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 130fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Also compute leading super-registers. Each register has a list of 131fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // covered-by-subregs super-registers where it appears as the first explicit 132fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // sub-register. 133fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // 134fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // This is used by computeSecondarySubRegs() to find candidates. 135fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (CoveredBySubRegs && !ExplicitSubRegs.empty()) 136fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this); 13731d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen 138d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Add ad hoc alias links. This is a symmetric relationship between two 13931d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen // registers, so build a symmetric graph by adding links in both ends. 14031d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen std::vector<Record*> Aliases = TheDef->getValueAsListOfDefs("Aliases"); 14131d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen for (unsigned i = 0, e = Aliases.size(); i != e; ++i) { 14231d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen CodeGenRegister *Reg = RegBank.getReg(Aliases[i]); 14331d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen ExplicitAliases.push_back(Reg); 14431d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen Reg->ExplicitAliases.push_back(this); 14531d938a6b1173c642f975d78417459d4d8cd3677Jakob Stoklund Olesen } 146148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen} 147148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen 148f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesenconst std::string &CodeGenRegister::getName() const { 149f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen return TheDef->getName(); 150f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 151f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 152d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Tricknamespace { 153d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Iterate over all register units in a set of registers. 154d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickclass RegUnitIterator { 155d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::Set::const_iterator RegI, RegE; 156d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::RegUnitList::const_iterator UnitI, UnitE; 157d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 158d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickpublic: 159d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegUnitIterator(const CodeGenRegister::Set &Regs): 160d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegI(Regs.begin()), RegE(Regs.end()), UnitI(), UnitE() { 161d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 162d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (RegI != RegE) { 163d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UnitI = (*RegI)->getRegUnits().begin(); 164d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UnitE = (*RegI)->getRegUnits().end(); 165d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick advance(); 166d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 167d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 168d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 169d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick bool isValid() const { return UnitI != UnitE; } 170d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1719df5ec3984c6197939e5a9b1d3b893e909ca0632Bill Wendling unsigned operator* () const { assert(isValid()); return *UnitI; } 172d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 173d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick const CodeGenRegister *getReg() const { assert(isValid()); return *RegI; } 174d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 175d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick /// Preincrement. Move to the next unit. 176d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick void operator++() { 177d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick assert(isValid() && "Cannot advance beyond the last operand"); 178d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick ++UnitI; 179d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick advance(); 180d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 181d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 182d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickprotected: 183d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick void advance() { 184d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick while (UnitI == UnitE) { 185d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (++RegI == RegE) 186d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick break; 187d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UnitI = (*RegI)->getRegUnits().begin(); 188d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UnitE = (*RegI)->getRegUnits().end(); 189d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 190d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 191d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick}; 192d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} // namespace 193d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1949f2a9d741f58f0a2a591ec16e5e038c905142dbcAndrew Trick// Merge two RegUnitLists maintaining the order and removing duplicates. 195dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick// Overwrites MergedRU in the process. 196dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trickstatic void mergeRegUnits(CodeGenRegister::RegUnitList &MergedRU, 197f1275959b2b6ac5212e8b5547251b0303168b0b1Andrew Trick const CodeGenRegister::RegUnitList &RRU) { 198dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick CodeGenRegister::RegUnitList LRU = MergedRU; 199dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick MergedRU.clear(); 200f1275959b2b6ac5212e8b5547251b0303168b0b1Andrew Trick std::set_union(LRU.begin(), LRU.end(), RRU.begin(), RRU.end(), 2015aeda3f07684e555f19813e41b7fc101434cfe64Andrew Trick std::back_inserter(MergedRU)); 202dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick} 203dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick 204d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Return true of this unit appears in RegUnits. 205d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickstatic bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) { 206d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick return std::count(RegUnits.begin(), RegUnits.end(), Unit); 207d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 208d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 209d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Inherit register units from subregisters. 210d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Return true if the RegUnits changed. 211d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickbool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) { 212d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned OldNumUnits = RegUnits.size(); 213d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); 214d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick I != E; ++I) { 215d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister *SR = I->second; 216d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Merge the subregister's units into this register's RegUnits. 217d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick mergeRegUnits(RegUnits, SR->RegUnits); 218d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 219d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick return OldNumUnits != RegUnits.size(); 220d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 221d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 222b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenconst CodeGenRegister::SubRegMap & 223da2be824346c316c6fc840de7b8493e3d587e785Jakob Stoklund OlesenCodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { 224b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Only compute this map once. 225b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (SubRegsComplete) 226b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return SubRegs; 227b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen SubRegsComplete = true; 228b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 229148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen // First insert the explicit subregs and make sure they are fully indexed. 230148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { 231148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen CodeGenRegister *SR = ExplicitSubRegs[i]; 232148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i]; 2335fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen if (!SubRegs.insert(std::make_pair(Idx, SR)).second) 23461131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() + 23561131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger " appears twice in Register " + getName()); 236ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen // Map explicit sub-registers first, so the names take precedence. 237ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen // The inherited sub-registers are mapped below. 238ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen SubReg2Idx.insert(std::make_pair(SR, Idx)); 239b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 240b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 241b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Keep track of inherited subregs and how they can be reached. 242b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen SmallPtrSet<CodeGenRegister*, 8> Orphans; 243b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 244b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Clone inherited subregs and place duplicate entries in Orphans. 245b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Here the order is important - earlier subregs take precedence. 246148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { 247148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen CodeGenRegister *SR = ExplicitSubRegs[i]; 248da2be824346c316c6fc840de7b8493e3d587e785Jakob Stoklund Olesen const SubRegMap &Map = SR->computeSubRegs(RegBank); 249026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 250b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE; 251026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen ++SI) { 252b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (!SubRegs.insert(*SI).second) 253b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen Orphans.insert(SI->second); 254026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 255b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 256b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 257b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Expand any composed subreg indices. 258b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // If dsub_2 has ComposedOf = [qsub_1, dsub_0], and this register has a 259b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // qsub_1 subreg, add a dsub_2 subreg. Keep growing Indices and process 260b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // expanded subreg indices recursively. 261148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen SmallVector<CodeGenSubRegIndex*, 8> Indices = ExplicitSubRegIndices; 262b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen for (unsigned i = 0; i != Indices.size(); ++i) { 263b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen CodeGenSubRegIndex *Idx = Indices[i]; 264b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen const CodeGenSubRegIndex::CompMap &Comps = Idx->getComposites(); 265b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen CodeGenRegister *SR = SubRegs[Idx]; 266da2be824346c316c6fc840de7b8493e3d587e785Jakob Stoklund Olesen const SubRegMap &Map = SR->computeSubRegs(RegBank); 267b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen 268b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Look at the possible compositions of Idx. 269b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // They may not all be supported by SR. 270b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen for (CodeGenSubRegIndex::CompMap::const_iterator I = Comps.begin(), 271b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen E = Comps.end(); I != E; ++I) { 272b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen SubRegMap::const_iterator SRI = Map.find(I->first); 273b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen if (SRI == Map.end()) 274b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen continue; // Idx + I->first doesn't exist in SR. 275b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Add I->second as a name for the subreg SRI->second, assuming it is 276b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // orphaned, and the name isn't already used for something else. 277b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen if (SubRegs.count(I->second) || !Orphans.erase(SRI->second)) 278b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen continue; 279b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // We found a new name for the orphaned sub-register. 280b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen SubRegs.insert(std::make_pair(I->second, SRI->second)); 281b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen Indices.push_back(I->second); 282b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen } 283b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen } 284b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen 285b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Now Orphans contains the inherited subregisters without a direct index. 286b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Create inferred indexes for all missing entries. 287b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Work backwards in the Indices vector in order to compose subregs bottom-up. 288b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Consider this subreg sequence: 289b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // 290b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // qsub_1 -> dsub_0 -> ssub_0 291b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // 292b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // The qsub_1 -> dsub_0 composition becomes dsub_2, so the ssub_0 register 293b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // can be reached in two different ways: 294b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // 295b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // qsub_1 -> ssub_0 296b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // dsub_2 -> ssub_0 297b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // 298b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // We pick the latter composition because another register may have [dsub_0, 299d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The 300b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // dsub_2 -> ssub_0 composition can be shared. 301b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen while (!Indices.empty() && !Orphans.empty()) { 302b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen CodeGenSubRegIndex *Idx = Indices.pop_back_val(); 303b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen CodeGenRegister *SR = SubRegs[Idx]; 304da2be824346c316c6fc840de7b8493e3d587e785Jakob Stoklund Olesen const SubRegMap &Map = SR->computeSubRegs(RegBank); 305b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE; 306b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen ++SI) 307b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen if (Orphans.erase(SI->second)) 308b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen SubRegs[RegBank.getCompositeSubRegIndex(Idx, SI->first)] = SI->second; 309b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 310dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick 311ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen // Compute the inverse SubReg -> Idx map. 312ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen for (SubRegMap::const_iterator SI = SubRegs.begin(), SE = SubRegs.end(); 313ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen SI != SE; ++SI) { 3142ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen if (SI->second == this) { 315376a8a773e38fdcd9102a40e08ab1e0661d645d9Jakob Stoklund Olesen ArrayRef<SMLoc> Loc; 3162ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen if (TheDef) 3172ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen Loc = TheDef->getLoc(); 31861131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Register " + getName() + 31961131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger " has itself as a sub-register"); 3202ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen } 321997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen 322997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // Compute AllSuperRegsCovered. 323997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen if (!CoveredBySubRegs) 324997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen SI->first->AllSuperRegsCovered = false; 325997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen 3262ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen // Ensure that every sub-register has a unique name. 3272ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*>::iterator Ins = 3282ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen SubReg2Idx.insert(std::make_pair(SI->second, SI->first)).first; 3292ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen if (Ins->second == SI->first) 330ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen continue; 3312ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen // Trouble: Two different names for SI->second. 332376a8a773e38fdcd9102a40e08ab1e0661d645d9Jakob Stoklund Olesen ArrayRef<SMLoc> Loc; 3332ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen if (TheDef) 3342ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen Loc = TheDef->getLoc(); 33561131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Sub-register can't have two names: " + 3362ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen SI->second->getName() + " available as " + 3372ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen SI->first->getName() + " and " + Ins->second->getName()); 338ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen } 339ca313e1efa98910a7a5e7f4bf2ac1a70adb6e4feJakob Stoklund Olesen 340fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Derive possible names for sub-register concatenations from any explicit 341fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // sub-registers. By doing this before computeSecondarySubRegs(), we ensure 342fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // that getConcatSubRegIndex() won't invent any concatenated indices that the 343fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // user already specified. 344fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { 345fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenRegister *SR = ExplicitSubRegs[i]; 346fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (!SR->CoveredBySubRegs || SR->ExplicitSubRegs.size() <= 1) 347fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen continue; 348fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 349fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // SR is composed of multiple sub-regs. Find their names in this register. 350fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen SmallVector<CodeGenSubRegIndex*, 8> Parts; 351fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned j = 0, e = SR->ExplicitSubRegs.size(); j != e; ++j) 352fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Parts.push_back(getSubRegIndex(SR->ExplicitSubRegs[j])); 353fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 354fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Offer this as an existing spelling for the concatenation of Parts. 355fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen RegBank.addConcatSubRegIndex(Parts, ExplicitSubRegIndices[i]); 356fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 357fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 358f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Initialize RegUnitList. Because getSubRegs is called recursively, this 359f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // processes the register hierarchy in postorder. 360dd9a50196cd75dbcb2bd604754cd62f8c1f30357Andrew Trick // 361f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Inherit all sub-register units. It is good enough to look at the explicit 362f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // sub-registers, the other registers won't contribute any more units. 363f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { 364f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen CodeGenRegister *SR = ExplicitSubRegs[i]; 365f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Explicit sub-registers are usually disjoint, so this is a good way of 366f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // computing the union. We may pick up a few duplicates that will be 367f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // eliminated below. 368f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen unsigned N = RegUnits.size(); 369f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen RegUnits.append(SR->RegUnits.begin(), SR->RegUnits.end()); 370f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen std::inplace_merge(RegUnits.begin(), RegUnits.begin() + N, RegUnits.end()); 371f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen } 372f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen RegUnits.erase(std::unique(RegUnits.begin(), RegUnits.end()), RegUnits.end()); 373f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen 374f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Absent any ad hoc aliasing, we create one register unit per leaf register. 375f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // These units correspond to the maximal cliques in the register overlap 376f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // graph which is optimal. 377f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // 378f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // When there is ad hoc aliasing, we simply create one unit per edge in the 379f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // undirected ad hoc aliasing graph. Technically, we could do better by 380f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // identifying maximal cliques in the ad hoc graph, but cliques larger than 2 381f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // are extremely rare anyway (I've never seen one), so we don't bother with 382f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // the added complexity. 383f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitAliases.size(); i != e; ++i) { 384f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen CodeGenRegister *AR = ExplicitAliases[i]; 385f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Only visit each edge once. 386f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen if (AR->SubRegsComplete) 387f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen continue; 388f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Create a RegUnit representing this alias edge, and add it to both 389f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // registers. 39040c6fb397d1e485aef8b4e1729ba9804784990c1Jakob Stoklund Olesen unsigned Unit = RegBank.newRegUnit(this, AR); 391f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen RegUnits.push_back(Unit); 392f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen AR->RegUnits.push_back(Unit); 393f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen } 394f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen 395f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // Finally, create units for leaf registers without ad hoc aliases. Note that 396f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // a leaf register with ad hoc aliases doesn't get its own unit - it isn't 397f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen // necessary. This means the aliasing leaf registers can share a single unit. 398f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen if (RegUnits.empty()) 39940c6fb397d1e485aef8b4e1729ba9804784990c1Jakob Stoklund Olesen RegUnits.push_back(RegBank.newRegUnit(this)); 400f402602199a3fc875bb9b6887869e647d0b49df2Jakob Stoklund Olesen 401f52baf72c116d9cf8680d25a8e751ce354c7d44bJakob Stoklund Olesen // We have now computed the native register units. More may be adopted later 402f52baf72c116d9cf8680d25a8e751ce354c7d44bJakob Stoklund Olesen // for balancing purposes. 403f52baf72c116d9cf8680d25a8e751ce354c7d44bJakob Stoklund Olesen NumNativeRegUnits = RegUnits.size(); 404f52baf72c116d9cf8680d25a8e751ce354c7d44bJakob Stoklund Olesen 405b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return SubRegs; 406b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 407b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 408fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// In a register that is covered by its sub-registers, try to find redundant 409fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// sub-registers. For example: 410fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// 411fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// QQ0 = {Q0, Q1} 412fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// Q0 = {D0, D1} 413fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// Q1 = {D2, D3} 414fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// 415fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// We can infer that D1_D2 is also a sub-register, even if it wasn't named in 416fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// the register definition. 417fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// 418fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// The explicitly specified registers form a tree. This function discovers 419fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// sub-register relationships that would force a DAG. 420fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen// 421fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesenvoid CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) { 422fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Collect new sub-registers first, add them later. 423fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen SmallVector<SubRegMap::value_type, 8> NewSubRegs; 424fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 425fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Look at the leading super-registers of each sub-register. Those are the 426fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // candidates for new sub-registers, assuming they are fully contained in 427fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // this register. 428fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (SubRegMap::iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I){ 429fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen const CodeGenRegister *SubReg = I->second; 430fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs; 431fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 0, e = Leads.size(); i != e; ++i) { 432fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenRegister *Cand = const_cast<CodeGenRegister*>(Leads[i]); 433fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Already got this sub-register? 434fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (Cand == this || getSubRegIndex(Cand)) 435fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen continue; 436fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Check if each component of Cand is already a sub-register. 437fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // We know that the first component is I->second, and is present with the 438fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // name I->first. 439fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen SmallVector<CodeGenSubRegIndex*, 8> Parts(1, I->first); 440fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen assert(!Cand->ExplicitSubRegs.empty() && 441fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen "Super-register has no sub-registers"); 442fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned j = 1, e = Cand->ExplicitSubRegs.size(); j != e; ++j) { 443fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (CodeGenSubRegIndex *Idx = getSubRegIndex(Cand->ExplicitSubRegs[j])) 444fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Parts.push_back(Idx); 445fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen else { 446fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Sub-register doesn't exist. 447fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Parts.clear(); 448fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen break; 449fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 450fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 451fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // If some Cand sub-register is not part of this register, or if Cand only 452fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // has one sub-register, there is nothing to do. 453fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (Parts.size() <= 1) 454fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen continue; 455fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 456fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Each part of Cand is a sub-register of this. Make the full Cand also 457fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // a sub-register with a concatenated sub-register index. 458fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenSubRegIndex *Concat= RegBank.getConcatSubRegIndex(Parts); 459fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen NewSubRegs.push_back(std::make_pair(Concat, Cand)); 460fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 461fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 462fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 463fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Now add all the new sub-registers. 464fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) { 465fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Don't add Cand if another sub-register is already using the index. 466fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (!SubRegs.insert(NewSubRegs[i]).second) 467fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen continue; 468fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 469fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first; 470fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenRegister *NewSubReg = NewSubRegs[i].second; 471fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen SubReg2Idx.insert(std::make_pair(NewSubReg, NewIdx)); 472fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 473fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 474fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Create sub-register index composition maps for the synthesized indices. 475fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) { 476fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first; 477fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenRegister *NewSubReg = NewSubRegs[i].second; 478fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (SubRegMap::const_iterator SI = NewSubReg->SubRegs.begin(), 479fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) { 480fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second); 481fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (!SubIdx) 48261131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " + 48361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger SI->second->getName() + " in " + getName()); 484fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen NewIdx->addComposite(SI->first, SubIdx); 485fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 486fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 487fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen} 488fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 489b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesenvoid CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) { 49079e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // Only visit each register once. 49179e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen if (SuperRegsComplete) 49279e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen return; 49379e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen SuperRegsComplete = true; 49479e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen 49579e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // Make sure all sub-registers have been visited first, so the super-reg 49679e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // lists will be topologically ordered. 49779e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); 49879e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen I != E; ++I) 499b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen I->second->computeSuperRegs(RegBank); 50079e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen 50179e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // Now add this as a super-register on all sub-registers. 502b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Also compute the TopoSigId in post-order. 503b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigId Id; 50479e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); 50579e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen I != E; ++I) { 506b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Topological signature computed from SubIdx, TopoId(SubReg). 507b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Loops and idempotent indices have TopoSig = ~0u. 508b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen Id.push_back(I->first->EnumValue); 509b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen Id.push_back(I->second->TopoSig); 510b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen 51179e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // Don't add duplicate entries. 51279e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this) 51379e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen continue; 51479e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen I->second->SuperRegs.push_back(this); 51579e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen } 516b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSig = RegBank.getTopoSig(Id); 51779e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen} 51879e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen 519026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesenvoid 520c6a96ff6aeeb77e1007364e5603b72f3ab4cc7bdJakob Stoklund OlesenCodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet, 5215fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenRegBank &RegBank) const { 522026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen assert(SubRegsComplete && "Must precompute sub-registers"); 523148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { 524148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen CodeGenRegister *SR = ExplicitSubRegs[i]; 525026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen if (OSet.insert(SR)) 5265fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen SR->addSubRegsPreOrder(OSet, RegBank); 527026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen } 528fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Add any secondary sub-registers that weren't part of the explicit tree. 529fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); 530fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen I != E; ++I) 5312ca6b3c37498eebf1f729f85cee03aa38ea5bc65Jakob Stoklund Olesen OSet.insert(I->second); 532026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen} 533026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen 534d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Get the sum of this register's unit weights. 535d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickunsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const { 536d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned Weight = 0; 537d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (RegUnitList::const_iterator I = RegUnits.begin(), E = RegUnits.end(); 538d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick I != E; ++I) { 53940c6fb397d1e485aef8b4e1729ba9804784990c1Jakob Stoklund Olesen Weight += RegBank.getRegUnit(*I).Weight; 540d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 541d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick return Weight; 542d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 543d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 544f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 5454ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// RegisterTuples 5464ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5474ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5484ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// A RegisterTuples def is used to generate pseudo-registers from lists of 5494ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// sub-registers. We provide a SetTheory expander class that returns the new 5504ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen// registers. 5514ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesennamespace { 5524ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesenstruct TupleExpander : SetTheory::Expander { 55336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) override { 5544ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::vector<Record*> Indices = Def->getValueAsListOfDefs("SubRegIndices"); 5554ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned Dim = Indices.size(); 55605bce0beee87512e52428d4b80f5a8e79a949576David Greene ListInit *SubRegs = Def->getValueAsListInit("SubRegs"); 5574ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Dim != SubRegs->getSize()) 55861131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); 5594ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Dim < 2) 56061131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Def->getLoc(), 56161131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger "Tuples must have at least 2 sub-registers"); 5624ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5634ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Evaluate the sub-register lists to be zipped. 5644ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned Length = ~0u; 5654ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen SmallVector<SetTheory::RecSet, 4> Lists(Dim); 5664ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0; i != Dim; ++i) { 5672c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc()); 5684ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Length = std::min(Length, unsigned(Lists[i].size())); 5694ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 5704ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5714ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (Length == 0) 5724ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen return; 5734ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5744ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Precompute some types. 5754ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *RegisterCl = Def->getRecords().getClass("Register"); 57677f8274c7d4bfb5e2a449eb49dc78dcae37e5457Jakob Stoklund Olesen RecTy *RegisterRecTy = RecordRecTy::get(RegisterCl); 57705bce0beee87512e52428d4b80f5a8e79a949576David Greene StringInit *BlankName = StringInit::get(""); 5784ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5794ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Zip them up. 5804ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned n = 0; n != Length; ++n) { 5814ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::string Name; 5824ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *Proto = Lists[0][n]; 58305bce0beee87512e52428d4b80f5a8e79a949576David Greene std::vector<Init*> Tuple; 5844ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned CostPerUse = 0; 5854ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0; i != Dim; ++i) { 5864ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *Reg = Lists[i][n]; 5874ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen if (i) Name += '_'; 5884ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Name += Reg->getName(); 58977f8274c7d4bfb5e2a449eb49dc78dcae37e5457Jakob Stoklund Olesen Tuple.push_back(DefInit::get(Reg)); 5904ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen CostPerUse = std::max(CostPerUse, 5914ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen unsigned(Reg->getValueAsInt("CostPerUse"))); 5924ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 5934ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 5944ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Create a new Record representing the synthesized register. This record 5954ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // is only for consumption by CodeGenRegister, it is not added to the 5964ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // RecordKeeper. 5974ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Record *NewReg = new Record(Name, Def->getLoc(), Def->getRecords()); 5984ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Elts.insert(NewReg); 5994ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6004ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy Proto super-classes. 601b50df4a3df6db2ace3c011267934d3d10bdcc8dbJordan Rose ArrayRef<Record *> Supers = Proto->getSuperClasses(); 602b50df4a3df6db2ace3c011267934d3d10bdcc8dbJordan Rose ArrayRef<SMRange> Ranges = Proto->getSuperClassRanges(); 603b50df4a3df6db2ace3c011267934d3d10bdcc8dbJordan Rose for (unsigned i = 0, e = Supers.size(); i != e; ++i) 604b50df4a3df6db2ace3c011267934d3d10bdcc8dbJordan Rose NewReg->addSuperClass(Supers[i], Ranges[i]); 6054ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6064ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy Proto fields. 6074ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) { 6084ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RecordVal RV = Proto->getValues()[i]; 6094ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 61031867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen // Skip existing fields, like NAME. 61131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (NewReg->getValue(RV.getNameInit())) 612794481d5ca75c1e614625f8a9487b8fa9db9d4d8Jakob Stoklund Olesen continue; 613794481d5ca75c1e614625f8a9487b8fa9db9d4d8Jakob Stoklund Olesen 61431867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen StringRef Field = RV.getName(); 61531867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen 6164ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Replace the sub-register list with Tuple. 61731867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "SubRegs") 618dcd35c797d458d8b1dbc36cf7f1504166d5b2f16David Greene RV.setValue(ListInit::get(Tuple, RegisterRecTy)); 6194ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6204ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Provide a blank AsmName. MC hacks are required anyway. 62131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "AsmName") 6224ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen RV.setValue(BlankName); 6234ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6244ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // CostPerUse is aggregated from all Tuple members. 62531867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "CostPerUse") 626dcd35c797d458d8b1dbc36cf7f1504166d5b2f16David Greene RV.setValue(IntInit::get(CostPerUse)); 6274ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 62831867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen // Composite registers are always covered by sub-registers. 62931867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "CoveredBySubRegs") 63031867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen RV.setValue(BitInit::get(true)); 63131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen 6324ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Copy fields from the RegisterTuples def. 63331867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "SubRegIndices" || 63431867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen Field == "CompositeIndices") { 63531867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen NewReg->addValue(*Def->getValue(Field)); 6364ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen continue; 6374ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 6384ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6394ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Some fields get their default uninitialized value. 64031867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (Field == "DwarfNumbers" || 64131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen Field == "DwarfAlias" || 64231867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen Field == "Aliases") { 64331867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (const RecordVal *DefRV = RegisterCl->getValue(Field)) 6449b718e88642963bfb519c47b70d1daf5d2126325Jakob Stoklund Olesen NewReg->addValue(*DefRV); 6454ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen continue; 6464ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 6474ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6484ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Everything else is copied from Proto. 6494ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen NewReg->addValue(RV); 6504ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 6514ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 6524ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 6534ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen}; 6544ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen} 6554ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 6564ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen//===----------------------------------------------------------------------===// 657f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen// CodeGenRegisterClass 658f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 659f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 660ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund OlesenCodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) 661b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen : TheDef(R), 662b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen Name(R->getName()), 663b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigs(RegBank.getNumTopoSigs()), 664b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen EnumValue(-1) { 665f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // Rename anonymous register classes. 666f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (R->getName().size() > 9 && R->getName()[9] == '.') { 667f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen static unsigned AnonCounter = 0; 668f15fe8195b0a42d0e950f3694c4d6ccd4034804aMichael J. Spencer R->setName("AnonRegClass_" + utostr(AnonCounter)); 669f15fe8195b0a42d0e950f3694c4d6ccd4034804aMichael J. Spencer // MSVC2012 ICEs if AnonCounter++ is directly passed to utostr. 670f15fe8195b0a42d0e950f3694c4d6ccd4034804aMichael J. Spencer ++AnonCounter; 671f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 672f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 673f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes"); 674f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen for (unsigned i = 0, e = TypeList.size(); i != e; ++i) { 675f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Record *Type = TypeList[i]; 676f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen if (!Type->isSubClassOf("ValueType")) 67761131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError("RegTypes list member '" + Type->getName() + 67861131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger "' does not derive from the ValueType class!"); 679f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen VTs.push_back(getValueType(Type)); 680f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen } 681f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!"); 682f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 683cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen // Allocation order 0 is the full set. AltOrders provides others. 684cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen const SetTheory::RecVec *Elements = RegBank.getSets().expand(R); 685cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen ListInit *AltOrders = R->getValueAsListInit("AltOrders"); 686cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen Orders.resize(1 + AltOrders->size()); 687cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen 688b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Default allocation order always contains all registers. 689cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen for (unsigned i = 0, e = Elements->size(); i != e; ++i) { 690cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen Orders[0].push_back((*Elements)[i]); 691b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen const CodeGenRegister *Reg = RegBank.getReg((*Elements)[i]); 692b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen Members.insert(Reg); 693b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigs.set(Reg->getTopoSig()); 694cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen } 695f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 696b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Alternative allocation orders may be subsets. 697b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen SetTheory::RecSet Order; 698cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) { 6992c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc()); 700cc0c975b7db95ce6bc865c56a3016bf0d4f83304Jakob Stoklund Olesen Orders[1 + i].append(Order.begin(), Order.end()); 701b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen // Verify that all altorder members are regclass members. 702b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen while (!Order.empty()) { 703b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen CodeGenRegister *Reg = RegBank.getReg(Order.back()); 704b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen Order.pop_back(); 705b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen if (!contains(Reg)) 70661131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() + 707b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen " is not a class member"); 708b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen } 709b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen } 710b4c704877d1600852a55ab7bef2918a7c0af5e0dJakob Stoklund Olesen 711f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen // Allow targets to override the size in bits of the RegisterClass. 712f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen unsigned Size = R->getValueAsInt("Size"); 713f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 714f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Namespace = R->getValueAsString("Namespace"); 71536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SpillSize = Size ? Size : MVT(VTs[0]).getSizeInBits(); 716f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen SpillAlignment = R->getValueAsInt("Alignment"); 717f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen CopyCost = R->getValueAsInt("CopyCost"); 718f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen Allocatable = R->getValueAsBit("isAllocatable"); 7198dd6f0c8353f80de6526810899f271d539f6929cJakob Stoklund Olesen AltOrderSelect = R->getValueAsString("AltOrderSelect"); 720f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 721f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 722babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// Create an inferred register class that was missing from the .td files. 723babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// Most properties will be inherited from the closest super-class after the 724babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// class structure has been computed. 725a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund OlesenCodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, 726a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen StringRef Name, Key Props) 727babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen : Members(*Props.Members), 728dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TheDef(nullptr), 729babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Name(Name), 730a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen TopoSigs(RegBank.getNumTopoSigs()), 731babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen EnumValue(-1), 732babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen SpillSize(Props.SpillSize), 733babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen SpillAlignment(Props.SpillAlignment), 734babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen CopyCost(0), 735babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Allocatable(true) { 736a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen for (CodeGenRegister::Set::iterator I = Members.begin(), E = Members.end(); 737a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen I != E; ++I) 738a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen TopoSigs.set((*I)->getTopoSig()); 739babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 740babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 741babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// Compute inherited propertied for a synthesized register class. 742babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenvoid CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) { 743babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen assert(!getDef() && "Only synthesized classes can inherit properties"); 744babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen assert(!SuperClasses.empty() && "Synthesized class without super class"); 745babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 746babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // The last super-class is the smallest one. 747babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen CodeGenRegisterClass &Super = *SuperClasses.back(); 748babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 749babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Most properties are copied directly. 750babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Exceptions are members, size, and alignment 751babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Namespace = Super.Namespace; 752babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen VTs = Super.VTs; 753babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen CopyCost = Super.CopyCost; 754babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Allocatable = Super.Allocatable; 755babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen AltOrderSelect = Super.AltOrderSelect; 756babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 757babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Copy all allocation orders, filter out foreign registers from the larger 758babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // super-class. 759babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Orders.resize(Super.Orders.size()); 760babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i) 761babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j) 762babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen if (contains(RegBank.getReg(Super.Orders[i][j]))) 763babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Orders[i].push_back(Super.Orders[i][j]); 764babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 765babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 766ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesenbool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const { 767ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen return Members.count(Reg); 768ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen} 769ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen 770babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesennamespace llvm { 771babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) { 772babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen OS << "{ S=" << K.SpillSize << ", A=" << K.SpillAlignment; 773babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (CodeGenRegister::Set::const_iterator I = K.Members->begin(), 774babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen E = K.Members->end(); I != E; ++I) 775babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen OS << ", " << (*I)->getName(); 776babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen return OS << " }"; 777babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen } 778babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 779babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 780babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// This is a simple lexicographical order that can be used to search for sets. 781babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// It is not the same as the topological order provided by TopoOrderRC. 782babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenbool CodeGenRegisterClass::Key:: 783babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenoperator<(const CodeGenRegisterClass::Key &B) const { 784babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen assert(Members && B.Members); 78536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::tie(*Members, SpillSize, SpillAlignment) < 78636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(*B.Members, B.SpillSize, B.SpillAlignment); 787babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 788babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 789ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// Returns true if RC is a strict subclass. 790ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// RC is a sub-class of this class if it is a valid replacement for any 791ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// instruction operand where a register of this classis required. It must 792ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// satisfy these conditions: 793ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 794ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 1. All RC registers are also in this. 795ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 2. The RC spill size must not be smaller than our spill size. 796ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 3. RC spill alignment must be compatible with ours. 797ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen// 79852e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesenstatic bool testSubClass(const CodeGenRegisterClass *A, 79952e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen const CodeGenRegisterClass *B) { 80052e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen return A->SpillAlignment && B->SpillAlignment % A->SpillAlignment == 0 && 80152e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen A->SpillSize <= B->SpillSize && 80252e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen std::includes(A->getMembers().begin(), A->getMembers().end(), 80352e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen B->getMembers().begin(), B->getMembers().end(), 804c6596e2edc406298ff65d27633bd898613533c0bJakob Stoklund Olesen CodeGenRegister::Less()); 805ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen} 806ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen 8077dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// Sorting predicate for register classes. This provides a topological 8087dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// ordering that arranges all register classes before their sub-classes. 8097dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// 8107dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// Register classes with the same registers, spill size, and alignment form a 8117dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// clique. They will be ordered alphabetically. 8127dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen/// 8130d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramerstatic int TopoOrderRC(CodeGenRegisterClass *const *PA, 8140d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer CodeGenRegisterClass *const *PB) { 8150d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer const CodeGenRegisterClass *A = *PA; 8160d293e45b66c742fdbc3998209bb20ed6c5806bfBenjamin Kramer const CodeGenRegisterClass *B = *PB; 8177dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A == B) 8187dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 0; 8197dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 8207dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order by ascending spill size. 8217dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillSize < B->SpillSize) 8227dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return -1; 8237dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillSize > B->SpillSize) 8247dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 1; 8257dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 8267dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order by ascending spill alignment. 8277dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillAlignment < B->SpillAlignment) 8287dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return -1; 8297dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen if (A->SpillAlignment > B->SpillAlignment) 8307dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen return 1; 8317dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 832a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen // Order by descending set size. Note that the classes' allocation order may 833a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen // not have been computed yet. The Members set is always vaild. 834a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen if (A->getMembers().size() > B->getMembers().size()) 835a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen return -1; 836a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen if (A->getMembers().size() < B->getMembers().size()) 837a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen return 1; 838a93090ccd914492550ee43befe1f0c2286b22fedJakob Stoklund Olesen 8397dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Finally order by name as a tie breaker. 840ee599209e613cbe11ca67e8d084d2fc37d679f61Jakob Stoklund Olesen return StringRef(A->getName()).compare(B->getName()); 8417dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen} 8427dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen 8436fea31e7300fe012b0b2984d6bc0338d02b054d3Jakob Stoklund Olesenstd::string CodeGenRegisterClass::getQualifiedName() const { 8446fea31e7300fe012b0b2984d6bc0338d02b054d3Jakob Stoklund Olesen if (Namespace.empty()) 8456fea31e7300fe012b0b2984d6bc0338d02b054d3Jakob Stoklund Olesen return getName(); 8466fea31e7300fe012b0b2984d6bc0338d02b054d3Jakob Stoklund Olesen else 8476fea31e7300fe012b0b2984d6bc0338d02b054d3Jakob Stoklund Olesen return Namespace + "::" + getName(); 848f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen} 849f1e2b23dfabb74249c2f1828dc902bd4bda52aa8Jakob Stoklund Olesen 850203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen// Compute sub-classes of all register classes. 851203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen// Assume the classes are ordered topologically. 852babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenvoid CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) { 853babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen ArrayRef<CodeGenRegisterClass*> RegClasses = RegBank.getRegClasses(); 854babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 855203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // Visit backwards so sub-classes are seen first. 856203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen for (unsigned rci = RegClasses.size(); rci; --rci) { 857203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen CodeGenRegisterClass &RC = *RegClasses[rci - 1]; 858203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.resize(RegClasses.size()); 859203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.set(RC.EnumValue); 860203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 861203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // Normally, all subclasses have IDs >= rci, unless RC is part of a clique. 862203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen for (unsigned s = rci; s != RegClasses.size(); ++s) { 863203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen if (RC.SubClasses.test(s)) 864203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen continue; 865203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen CodeGenRegisterClass *SubRC = RegClasses[s]; 86652e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen if (!testSubClass(&RC, SubRC)) 867203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen continue; 868203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // SubRC is a sub-class. Grap all its sub-classes so we won't have to 869203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen // check them again. 870203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses |= SubRC->SubClasses; 871203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen } 872203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 873d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Sweep up missed clique members. They will be immediately preceding RC. 87452e7dfadc65257f05480de6e70da00373a8954d1Jakob Stoklund Olesen for (unsigned s = rci - 1; s && testSubClass(&RC, RegClasses[s - 1]); --s) 875203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen RC.SubClasses.set(s - 1); 876203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen } 877f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen 878f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen // Compute the SuperClasses lists from the SubClasses vectors. 879f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { 880f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen const BitVector &SC = RegClasses[rci]->getSubClasses(); 881f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen for (int s = SC.find_first(); s >= 0; s = SC.find_next(s)) { 882f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen if (unsigned(s) == rci) 883f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen continue; 884f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen RegClasses[s]->SuperClasses.push_back(RegClasses[rci]); 885f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen } 886f9a4bb78dadc12c7c1e604c6f17b63a71305c2caJakob Stoklund Olesen } 887babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 888babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // With the class hierarchy in place, let synthesized register classes inherit 889babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // properties from their closest super-class. The iteration order here can 890babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // propagate properties down multiple levels. 891babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned rci = 0; rci != RegClasses.size(); ++rci) 892babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen if (!RegClasses[rci]->getDef()) 893babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen RegClasses[rci]->inheritProperties(RegBank); 894203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen} 895203e0b17dd6049d64cb4ed7c4da09747204e6463Jakob Stoklund Olesen 896570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesenvoid 8975fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund OlesenCodeGenRegisterClass::getSuperRegClasses(CodeGenSubRegIndex *SubIdx, 8985fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen BitVector &Out) const { 8995fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen DenseMap<CodeGenSubRegIndex*, 9005fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen SmallPtrSet<CodeGenRegisterClass*, 8> >::const_iterator 901570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen FindI = SuperRegClasses.find(SubIdx); 902570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen if (FindI == SuperRegClasses.end()) 903570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen return; 904570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen for (SmallPtrSet<CodeGenRegisterClass*, 8>::const_iterator I = 905570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen FindI->second.begin(), E = FindI->second.end(); I != E; ++I) 906570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen Out.set((*I)->EnumValue); 907570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen} 908570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen 909ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick// Populate a unique sorted list of units from a register set. 910ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trickvoid CodeGenRegisterClass::buildRegUnitSet( 911ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick std::vector<unsigned> &RegUnits) const { 912ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick std::vector<unsigned> TmpUnits; 913ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick for (RegUnitIterator UnitI(Members); UnitI.isValid(); ++UnitI) 914ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick TmpUnits.push_back(*UnitI); 915ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick std::sort(TmpUnits.begin(), TmpUnits.end()); 916ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick std::unique_copy(TmpUnits.begin(), TmpUnits.end(), 917ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick std::back_inserter(RegUnits)); 918ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick} 919570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen 920dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 921dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen// CodeGenRegBank 922dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 923dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 924c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund OlesenCodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { 9254ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Configure register Sets to understand register classes and tuples. 92659f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen Sets.addFieldExpander("RegisterClass", "MemberList"); 927ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen Sets.addFieldExpander("CalleeSavedRegs", "SaveList"); 9284ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Sets.addExpander("RegisterTuples", new TupleExpander()); 92959f26aadce1bb985b9befe841fc106c891e1c728Jakob Stoklund Olesen 930b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Read in the user-defined (named) sub-register indices. 931b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // More indices will be synthesized later. 9325fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen std::vector<Record*> SRIs = Records.getAllDerivedDefinitions("SubRegIndex"); 9335fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen std::sort(SRIs.begin(), SRIs.end(), LessRecord()); 9345fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen for (unsigned i = 0, e = SRIs.size(); i != e; ++i) 9355fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen getSubRegIdx(SRIs[i]); 936b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen // Build composite maps from ComposedOf fields. 937b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) 938b5af2d943ed568f2f4cac545b6dfb150ae9d73aaJakob Stoklund Olesen SubRegIndices[i]->updateComponents(*this); 939b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 940b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Read in the register definitions. 941b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register"); 942b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier std::sort(Regs.begin(), Regs.end(), LessRecordRegister()); 943b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen Registers.reserve(Regs.size()); 944b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Assign the enumeration values. 945b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Regs.size(); i != e; ++i) 946abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen getReg(Regs[i]); 9477b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 9484ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen // Expand tuples and number the new registers. 9494ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen std::vector<Record*> Tups = 9504ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen Records.getAllDerivedDefinitions("RegisterTuples"); 951b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier 952b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier std::vector<Record*> TupRegsCopy; 9534ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen for (unsigned i = 0, e = Tups.size(); i != e; ++i) { 9544ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen const std::vector<Record*> *TupRegs = Sets.expand(Tups[i]); 955b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier TupRegsCopy.reserve(TupRegs->size()); 956b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier TupRegsCopy.assign(TupRegs->begin(), TupRegs->end()); 957b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister()); 958b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j) 959b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462Chad Rosier getReg((TupRegsCopy)[j]); 960bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick TupRegsCopy.clear(); 9614ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen } 9624ce25d5d69704a7a4aa4bcecbe4c7345b50b771aJakob Stoklund Olesen 963148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen // Now all the registers are known. Build the object graph of explicit 964148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen // register-register references. 965148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) 966148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen Registers[i]->buildObjectGraph(*this); 967148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen 968d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson // Compute register name map. 969d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson for (unsigned i = 0, e = Registers.size(); i != e; ++i) 970d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson RegistersByName.GetOrCreateValue( 971d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson Registers[i]->TheDef->getValueAsString("AsmName"), 972d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson Registers[i]); 973d2c699706ceae4a118a8dcafbef73b85093e5390Owen Anderson 974148f392195dec8772ab4c5ac0d0c3b85fba0e5f8Jakob Stoklund Olesen // Precompute all sub-register maps. 975babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // This will create Composite entries for all inferred sub-register indices. 976babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) 977da2be824346c316c6fc840de7b8493e3d587e785Jakob Stoklund Olesen Registers[i]->computeSubRegs(*this); 978babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 979fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Infer even more sub-registers by combining leading super-registers. 980fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) 981fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (Registers[i]->CoveredBySubRegs) 982fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Registers[i]->computeSecondarySubRegs(*this); 983fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 98479e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // After the sub-register graph is complete, compute the topologically 98579e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen // ordered SuperRegs list. 98679e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) 987b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen Registers[i]->computeSuperRegs(*this); 98879e2045531cb4d1978be42591e9254c38a463d30Jakob Stoklund Olesen 989d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Native register units are associated with a leaf register. They've all been 990d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // discovered now. 99140c6fb397d1e485aef8b4e1729ba9804784990c1Jakob Stoklund Olesen NumNativeRegUnits = RegUnits.size(); 992d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 9937b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Read in register class definitions. 9947b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass"); 9957b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (RCs.empty()) 99636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PrintFatalError("No 'RegisterClass' subclasses defined!"); 9977b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 998babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Allocate user-defined register classes. 9997b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen RegClasses.reserve(RCs.size()); 1000babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned i = 0, e = RCs.size(); i != e; ++i) 1001babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen addToMaps(new CodeGenRegisterClass(*this, RCs[i])); 1002babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 1003babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Infer missing classes to create a full algebra. 1004babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen computeInferredRegisterClasses(); 1005babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 10067dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen // Order register classes topologically and assign enum values. 10077dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen array_pod_sort(RegClasses.begin(), RegClasses.end(), TopoOrderRC); 10087dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen for (unsigned i = 0, e = RegClasses.size(); i != e; ++i) 10097dcaa5b0fb56468e774044d3b887c21b2d484a1cJakob Stoklund Olesen RegClasses[i]->EnumValue = i; 1010babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen CodeGenRegisterClass::computeSubClasses(*this); 1011dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen} 1012dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 1013c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen// Create a synthetic CodeGenSubRegIndex without a corresponding Record. 1014c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund OlesenCodeGenSubRegIndex* 1015c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund OlesenCodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) { 1016c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen CodeGenSubRegIndex *Idx = new CodeGenSubRegIndex(Name, Namespace, 1017c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen SubRegIndices.size() + 1); 1018c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen SubRegIndices.push_back(Idx); 1019c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen return Idx; 1020c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen} 1021c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen 10225fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund OlesenCodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) { 10235fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def]; 10245fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen if (Idx) 10255fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen return Idx; 10265fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen Idx = new CodeGenSubRegIndex(Def, SubRegIndices.size() + 1); 10275fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen SubRegIndices.push_back(Idx); 10285fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen return Idx; 10295fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen} 10305fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen 1031b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund OlesenCodeGenRegister *CodeGenRegBank::getReg(Record *Def) { 1032abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *&Reg = Def2Reg[Def]; 1033abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen if (Reg) 1034b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Reg; 1035abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen Reg = new CodeGenRegister(Def, Registers.size() + 1); 1036abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen Registers.push_back(Reg); 1037abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen return Reg; 1038b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 1039b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 1040babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenvoid CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) { 1041babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen RegClasses.push_back(RC); 1042babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 1043babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen if (Record *Def = RC->getDef()) 1044babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Def2RC.insert(std::make_pair(Def, RC)); 1045babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 1046babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Duplicate classes are rejected by insert(). 1047babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // That's OK, we only care about the properties handled by CGRC::Key. 1048babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen CodeGenRegisterClass::Key K(*RC); 1049babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen Key2RC.insert(std::make_pair(K, RC)); 1050babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 1051babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 10521b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen// Create a synthetic sub-class if it is missing. 10531b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund OlesenCodeGenRegisterClass* 10541b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund OlesenCodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC, 10551b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen const CodeGenRegister::Set *Members, 10561b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen StringRef Name) { 10571b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen // Synthetic sub-class has the same size and alignment as RC. 10581b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen CodeGenRegisterClass::Key K(Members, RC->SpillSize, RC->SpillAlignment); 10591b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen RCKeyMap::const_iterator FoundI = Key2RC.find(K); 10601b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen if (FoundI != Key2RC.end()) 10611b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen return FoundI->second; 10621b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen 10631b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen // Sub-class doesn't exist, create a new one. 1064a9fdbbc55f640fecd3bb8df12fd205694c2f71a2Jakob Stoklund Olesen CodeGenRegisterClass *NewRC = new CodeGenRegisterClass(*this, Name, K); 10651b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen addToMaps(NewRC); 10661b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen return NewRC; 10671b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen} 10681b3d218880a7147caeb58f2604af1df26a409f7dJakob Stoklund Olesen 10697b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund OlesenCodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { 10707b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (CodeGenRegisterClass *RC = Def2RC[Def]) 10717b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return RC; 10727b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 107361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Def->getLoc(), "Not a known RegisterClass!"); 10747b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen} 10757b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 10765fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund OlesenCodeGenSubRegIndex* 10775fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund OlesenCodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A, 107890498b195ba759cf4f2a98da4e46fb9a2b580396Jakob Stoklund Olesen CodeGenSubRegIndex *B) { 1079b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Look for an existing entry. 108090498b195ba759cf4f2a98da4e46fb9a2b580396Jakob Stoklund Olesen CodeGenSubRegIndex *Comp = A->compose(B); 108190498b195ba759cf4f2a98da4e46fb9a2b580396Jakob Stoklund Olesen if (Comp) 1082b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Comp; 1083b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 1084b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // None exists, synthesize one. 1085dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen std::string Name = A->getName() + "_then_" + B->getName(); 1086c97eda2c9e34f4c491f59bbac81af2fd63fef49dJakob Stoklund Olesen Comp = createSubRegIndex(Name, A->getNamespace()); 108790498b195ba759cf4f2a98da4e46fb9a2b580396Jakob Stoklund Olesen A->addComposite(B, Comp); 1088b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen return Comp; 1089dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen} 1090dc29c447136aabf05f48a7119e48065c3b4cee9bJakob Stoklund Olesen 1091fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund OlesenCodeGenSubRegIndex *CodeGenRegBank:: 1092a0ec3f9b7b826b9b40b80199923b664bad808cceCraig ToppergetConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts) { 1093fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen assert(Parts.size() > 1 && "Need two parts to concatenate"); 1094fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 1095fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // Look for an existing entry. 1096fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen CodeGenSubRegIndex *&Idx = ConcatIdx[Parts]; 1097fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen if (Idx) 1098fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen return Idx; 1099fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 1100fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen // None exists, synthesize one. 1101fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen std::string Name = Parts.front()->getName(); 110223ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha // Determine whether all parts are contiguous. 110323ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha bool isContinuous = true; 110423ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha unsigned Size = Parts.front()->Size; 110523ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha unsigned LastOffset = Parts.front()->Offset; 110623ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha unsigned LastSize = Parts.front()->Size; 1107fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen for (unsigned i = 1, e = Parts.size(); i != e; ++i) { 1108fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Name += '_'; 1109fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen Name += Parts[i]->getName(); 111023ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha Size += Parts[i]->Size; 111123ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha if (Parts[i]->Offset != (LastOffset + LastSize)) 111223ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha isContinuous = false; 111323ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha LastOffset = Parts[i]->Offset; 111423ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha LastSize = Parts[i]->Size; 1115fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen } 111623ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha Idx = createSubRegIndex(Name, Parts.front()->getNamespace()); 111723ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha Idx->Size = Size; 111823ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha Idx->Offset = isContinuous ? Parts.front()->Offset : -1; 111923ed37a6b76e79272194fb46597f7280661b828fAhmed Bougacha return Idx; 1120fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen} 1121fcad79671f22c8994663c6780862b9c38d3609c3Jakob Stoklund Olesen 1122b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenvoid CodeGenRegBank::computeComposites() { 1123b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Keep track of TopoSigs visited. We only need to visit each TopoSig once, 1124b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // and many registers will share TopoSigs on regular architectures. 1125b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen BitVector TopoSigs(getNumTopoSigs()); 1126b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen 1127b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 1128abdbc84b4ed4276ed3def50f554e3ba156325717Jakob Stoklund Olesen CodeGenRegister *Reg1 = Registers[i]; 1129b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen 1130b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Skip identical subreg structures already processed. 1131b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen if (TopoSigs.test(Reg1->getTopoSig())) 1132b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen continue; 1133b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigs.set(Reg1->getTopoSig()); 1134b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen 1135026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(); 1136b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(), 1137b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen e1 = SRM1.end(); i1 != e1; ++i1) { 11385fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenSubRegIndex *Idx1 = i1->first; 1139b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *Reg2 = i1->second; 1140b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Ignore identity compositions. 1141b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Reg1 == Reg2) 1142b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen continue; 1143026dc223aeef2579d63f395007491e37d6cde3a0Jakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs(); 1144b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Try composing Idx1 with another SubRegIndex. 1145b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM2.begin(), 1146b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen e2 = SRM2.end(); i2 != e2; ++i2) { 1147ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen CodeGenSubRegIndex *Idx2 = i2->first; 1148b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen CodeGenRegister *Reg3 = i2->second; 1149b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // Ignore identity compositions. 1150b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen if (Reg2 == Reg3) 1151b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen continue; 1152b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3. 1153ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen CodeGenSubRegIndex *Idx3 = Reg1->getSubRegIndex(Reg3); 1154ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen assert(Idx3 && "Sub-register doesn't have an index"); 1155ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen 1156ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen // Conflicting composition? Emit a warning but allow it. 1157ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen if (CodeGenSubRegIndex *Prev = Idx1->addComposite(Idx2, Idx3)) 1158ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen PrintWarning(Twine("SubRegIndex ") + Idx1->getQualifiedName() + 1159ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen " and " + Idx2->getQualifiedName() + 1160ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen " compose ambiguously as " + Prev->getQualifiedName() + 1161ddd657d16d7716f29982e97c5fa3f3ff33770108Jakob Stoklund Olesen " or " + Idx3->getQualifiedName()); 1162b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 1163b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 1164b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen } 1165b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 1166b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 1167a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// Compute lane masks. This is similar to register units, but at the 1168a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// sub-register index level. Each bit in the lane mask is like a register unit 1169a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// class, and two lane masks will have a bit in common if two sub-register 1170a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// indices overlap in some register. 1171a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// 1172a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// Conservatively share a lane mask bit if two sub-register indices overlap in 1173a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen// some registers, but not in others. That shouldn't happen a lot. 1174a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesenvoid CodeGenRegBank::computeSubRegIndexLaneMasks() { 1175a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // First assign individual bits to all the leaf indices. 1176a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen unsigned Bit = 0; 1177997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // Determine mask of lanes that cover their registers. 1178997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen CoveringLanes = ~0u; 1179a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { 1180a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen CodeGenSubRegIndex *Idx = SubRegIndices[i]; 1181a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen if (Idx->getComposites().empty()) { 1182a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen Idx->LaneMask = 1u << Bit; 1183a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // Share bit 31 in the unlikely case there are more than 32 leafs. 1184f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // 1185f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // Sharing bits is harmless; it allows graceful degradation in targets 1186f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // with more than 32 vector lanes. They simply get a limited resolution 1187f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // view of lanes beyond the 32nd. 1188f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // 1189f79c5e2f842e952d26a2aa380fa71d5917c865a0Jakob Stoklund Olesen // See also the comment for getSubRegIndexLaneMask(). 1190997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen if (Bit < 31) 1191997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen ++Bit; 1192997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen else 1193997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // Once bit 31 is shared among multiple leafs, the 'lane' it represents 1194997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // is no longer covering its registers. 1195997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen CoveringLanes &= ~(1u << Bit); 1196a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen } else { 1197a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen Idx->LaneMask = 0; 1198a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen } 1199a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen } 1200a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 1201a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented 1202a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // by the sub-register graph? This doesn't occur in any known targets. 1203a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 1204a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen // Inherit lanes from composites. 1205997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { 1206997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen unsigned Mask = SubRegIndices[i]->computeLaneMask(); 1207997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // If some super-registers without CoveredBySubRegs use this index, we can 1208997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen // no longer assume that the lanes are covering their registers. 1209997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen if (!SubRegIndices[i]->AllSuperRegsCovered) 1210997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen CoveringLanes &= ~Mask; 1211997fa623fc14122153c58ddda8c90aa30f192cc8Jakob Stoklund Olesen } 1212a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen} 1213a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen 1214d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Tricknamespace { 1215d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is 1216d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// the transitive closure of the union of overlapping register 1217d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// classes. Together, the UberRegSets form a partition of the registers. If we 1218d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// consider overlapping register classes to be connected, then each UberRegSet 1219d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// is a set of connected components. 1220d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1221d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// An UberRegSet will likely be a horizontal slice of register names of 1222d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// the same width. Nontrivial subregisters should then be in a separate 1223d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// UberRegSet. But this property isn't required for valid computation of 1224d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// register unit weights. 1225d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1226d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// A Weight field caches the max per-register unit weight in each UberRegSet. 1227d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1228d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// A set of SingularDeterminants flags single units of some register in this set 1229d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// for which the unit weight equals the set weight. These units should not have 1230d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// their weight increased. 1231d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickstruct UberRegSet { 1232d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::Set Regs; 1233d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned Weight; 1234d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::RegUnitList SingularDeterminants; 1235d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1236d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberRegSet(): Weight(0) {} 1237d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick}; 1238d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} // namespace 1239d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1240d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Partition registers into UberRegSets, where each set is the transitive 1241d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// closure of the union of overlapping register classes. 1242d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1243d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// UberRegSets[0] is a special non-allocatable set. 1244d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickstatic void computeUberSets(std::vector<UberRegSet> &UberSets, 1245d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick std::vector<UberRegSet*> &RegSets, 1246d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegBank &RegBank) { 1247d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1248d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick const std::vector<CodeGenRegister*> &Registers = RegBank.getRegisters(); 1249d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1250d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // The Register EnumValue is one greater than its index into Registers. 1251d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick assert(Registers.size() == Registers[Registers.size()-1]->EnumValue && 1252d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick "register enum value mismatch"); 1253d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1254d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // For simplicitly make the SetID the same as EnumValue. 1255d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick IntEqClasses UberSetIDs(Registers.size()+1); 1256aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick std::set<unsigned> AllocatableRegs; 1257d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (unsigned i = 0, e = RegBank.getRegClasses().size(); i != e; ++i) { 1258aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick 1259d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegisterClass *RegClass = RegBank.getRegClasses()[i]; 1260aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick if (!RegClass->Allocatable) 1261aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick continue; 1262aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick 1263d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick const CodeGenRegister::Set &Regs = RegClass->getMembers(); 1264aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick if (Regs.empty()) 1265aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick continue; 1266d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1267d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned USetID = UberSetIDs.findLeader((*Regs.begin())->EnumValue); 1268d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick assert(USetID && "register number 0 is invalid"); 1269d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1270aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick AllocatableRegs.insert((*Regs.begin())->EnumValue); 127136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (CodeGenRegister::Set::const_iterator I = std::next(Regs.begin()), 1272aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick E = Regs.end(); I != E; ++I) { 1273aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick AllocatableRegs.insert((*I)->EnumValue); 1274d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberSetIDs.join(USetID, (*I)->EnumValue); 1275aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick } 1276aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick } 1277aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick // Combine non-allocatable regs. 1278aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 1279aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick unsigned RegNum = Registers[i]->EnumValue; 1280aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick if (AllocatableRegs.count(RegNum)) 1281aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick continue; 1282aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick 1283aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick UberSetIDs.join(0, RegNum); 1284d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1285d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberSetIDs.compress(); 1286d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1287d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Make the first UberSet a special unallocatable set. 1288d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned ZeroID = UberSetIDs[0]; 1289d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1290d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Insert Registers into the UberSets formed by union-find. 1291d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Do not resize after this. 1292d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberSets.resize(UberSetIDs.getNumClasses()); 1293d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 1294d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick const CodeGenRegister *Reg = Registers[i]; 1295d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned USetID = UberSetIDs[Reg->EnumValue]; 1296d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (!USetID) 1297d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick USetID = ZeroID; 1298d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick else if (USetID == ZeroID) 1299d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick USetID = 0; 1300d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1301d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberRegSet *USet = &UberSets[USetID]; 1302d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick USet->Regs.insert(Reg); 1303d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegSets[i] = USet; 1304d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1305d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 1306d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1307d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Recompute each UberSet weight after changing unit weights. 1308d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickstatic void computeUberWeights(std::vector<UberRegSet> &UberSets, 1309d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegBank &RegBank) { 1310d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Skip the first unallocatable set. 131136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (std::vector<UberRegSet>::iterator I = std::next(UberSets.begin()), 1312d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick E = UberSets.end(); I != E; ++I) { 1313d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1314d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Initialize all unit weights in this set, and remember the max units/reg. 1315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const CodeGenRegister *Reg = nullptr; 1316d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned MaxWeight = 0, Weight = 0; 1317d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) { 1318d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (Reg != UnitI.getReg()) { 1319d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (Weight > MaxWeight) 1320d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick MaxWeight = Weight; 1321d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Reg = UnitI.getReg(); 1322d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Weight = 0; 1323d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 132440c6fb397d1e485aef8b4e1729ba9804784990c1Jakob Stoklund Olesen unsigned UWeight = RegBank.getRegUnit(*UnitI).Weight; 1325d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (!UWeight) { 1326d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UWeight = 1; 1327d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegBank.increaseRegUnitWeight(*UnitI, UWeight); 1328d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1329d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Weight += UWeight; 1330d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1331d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (Weight > MaxWeight) 1332d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick MaxWeight = Weight; 1333bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick if (I->Weight != MaxWeight) { 1334bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG( 1335bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "UberSet " << I - UberSets.begin() << " Weight " << MaxWeight; 1336bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (CodeGenRegister::Set::iterator 1337bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick UnitI = I->Regs.begin(), UnitE = I->Regs.end(); 1338bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick UnitI != UnitE; ++UnitI) { 1339bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << " " << (*UnitI)->getName(); 1340bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick } 1341bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "\n"); 1342bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick // Update the set weight. 1343bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick I->Weight = MaxWeight; 1344bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick } 1345d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1346d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Find singular determinants. 1347d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(), 1348d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegE = I->Regs.end(); RegI != RegE; ++RegI) { 1349d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if ((*RegI)->getRegUnits().size() == 1 1350d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick && (*RegI)->getWeight(RegBank) == I->Weight) 1351d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick mergeRegUnits(I->SingularDeterminants, (*RegI)->getRegUnits()); 1352d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1353d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1354d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 1355d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1356d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of 1357d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// a register and its subregisters so that they have the same weight as their 1358d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// UberSet. Self-recursion processes the subregister tree in postorder so 1359d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// subregisters are normalized first. 1360d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1361d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Side effects: 1362d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// - creates new adopted register units 1363d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// - causes superregisters to inherit adopted units 1364d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// - increases the weight of "singular" units 1365d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// - induces recomputation of UberWeights. 1366d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickstatic bool normalizeWeight(CodeGenRegister *Reg, 1367d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick std::vector<UberRegSet> &UberSets, 1368d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick std::vector<UberRegSet*> &RegSets, 13697b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick std::set<unsigned> &NormalRegs, 1370d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::RegUnitList &NormalUnits, 1371d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegBank &RegBank) { 1372d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick bool Changed = false; 13737b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick if (!NormalRegs.insert(Reg->EnumValue).second) 13747b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick return Changed; 13757b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick 1376d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs(); 1377d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (CodeGenRegister::SubRegMap::const_iterator SRI = SRM.begin(), 1378d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick SRE = SRM.end(); SRI != SRE; ++SRI) { 1379d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (SRI->second == Reg) 1380d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick continue; // self-cycles happen 1381d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 13827b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick Changed |= normalizeWeight(SRI->second, UberSets, RegSets, 13837b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick NormalRegs, NormalUnits, RegBank); 1384d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1385d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Postorder register normalization. 1386d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1387d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Inherit register units newly adopted by subregisters. 1388d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (Reg->inheritRegUnits(RegBank)) 1389d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick computeUberWeights(UberSets, RegBank); 1390d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1391d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Check if this register is too skinny for its UberRegSet. 1392d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)]; 1393d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1394d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned RegWeight = Reg->getWeight(RegBank); 1395d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (UberSet->Weight > RegWeight) { 1396d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // A register unit's weight can be adjusted only if it is the singular unit 1397d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // for this register, has not been used to normalize a subregister's set, 1398d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // and has not already been used to singularly determine this UberRegSet. 1399d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned AdjustUnit = Reg->getRegUnits().front(); 1400d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick if (Reg->getRegUnits().size() != 1 1401d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick || hasRegUnit(NormalUnits, AdjustUnit) 1402d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) { 1403d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // We don't have an adjustable unit, so adopt a new one. 1404d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick AdjustUnit = RegBank.newRegUnit(UberSet->Weight - RegWeight); 1405d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Reg->adoptRegUnit(AdjustUnit); 1406d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Adopting a unit does not immediately require recomputing set weights. 1407d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1408d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick else { 1409d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Adjust the existing single unit. 1410d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick RegBank.increaseRegUnitWeight(AdjustUnit, UberSet->Weight - RegWeight); 1411d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // The unit may be shared among sets and registers within this set. 1412d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick computeUberWeights(UberSets, RegBank); 1413d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1414d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Changed = true; 1415d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1416d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1417d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Mark these units normalized so superregisters can't change their weights. 1418d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick mergeRegUnits(NormalUnits, Reg->getRegUnits()); 1419d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1420d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick return Changed; 1421d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 1422d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1423d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// Compute a weight for each register unit created during getSubRegs. 1424d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// 1425d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// The goal is that two registers in the same class will have the same weight, 1426d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick// where each register's weight is defined as sum of its units' weights. 1427d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trickvoid CodeGenRegBank::computeRegUnitWeights() { 1428d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick std::vector<UberRegSet> UberSets; 1429d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick std::vector<UberRegSet*> RegSets(Registers.size()); 1430d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick computeUberSets(UberSets, RegSets, *this); 1431d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // UberSets and RegSets are now immutable. 1432d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1433d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick computeUberWeights(UberSets, *this); 1434d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1435d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Iterate over each Register, normalizing the unit weights until reaching 1436d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // a fix point. 1437d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick unsigned NumIters = 0; 1438d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (bool Changed = true; Changed; ++NumIters) { 1439d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights"); 1440d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick Changed = false; 1441d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 1442d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick CodeGenRegister::RegUnitList NormalUnits; 14437b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick std::set<unsigned> NormalRegs; 14447b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick Changed |= normalizeWeight(Registers[i], UberSets, RegSets, 14457b521ad6eea8ac25960a4efecb9578c18fbc0e93Andrew Trick NormalRegs, NormalUnits, *this); 1446d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1447d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick } 1448d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick} 1449d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1450176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// Find a set in UniqueSets with the same elements as Set. 1451176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// Return an iterator into UniqueSets. 1452176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trickstatic std::vector<RegUnitSet>::const_iterator 1453176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew TrickfindRegUnitSet(const std::vector<RegUnitSet> &UniqueSets, 1454176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick const RegUnitSet &Set) { 1455176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::vector<RegUnitSet>::const_iterator 1456176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick I = UniqueSets.begin(), E = UniqueSets.end(); 1457176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for(;I != E; ++I) { 1458176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick if (I->Units == Set.Units) 1459176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick break; 1460176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1461176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick return I; 1462176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick} 1463176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1464176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// Return true if the RUSubSet is a subset of RUSuperSet. 1465176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trickstatic bool isRegUnitSubSet(const std::vector<unsigned> &RUSubSet, 1466176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick const std::vector<unsigned> &RUSuperSet) { 1467c72e08b4a95e494d3bfdf1262ea8b28f614ac40eAndrew Trick return std::includes(RUSuperSet.begin(), RUSuperSet.end(), 1468c72e08b4a95e494d3bfdf1262ea8b28f614ac40eAndrew Trick RUSubSet.begin(), RUSubSet.end()); 1469176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick} 1470176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1471d3d751804c1f9d0ac77bbc3a6be48ee3cee2043bAndrew Trick/// Iteratively prune unit sets. Prune subsets that are close to the superset, 1472c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// but with one or two registers removed. We occasionally have registers like 1473c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// APSR and PC thrown in with the general registers. We also see many 1474c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// special-purpose register subsets, such as tail-call and Thumb 1475c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// encodings. Generating all possible overlapping sets is combinatorial and 1476c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// overkill for modeling pressure. Ideally we could fix this statically in 1477c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// tablegen by (1) having the target define register classes that only include 1478c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// the allocatable registers and marking other classes as non-allocatable and 1479c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// (2) having a way to mark special purpose classes as "don't-care" classes for 1480c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// the purpose of pressure. However, we make an attempt to handle targets that 1481c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// are not nicely defined by merging nearly identical register unit sets 1482c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// statically. This generates smaller tables. Then, dynamically, we adjust the 1483c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// set limit by filtering the reserved registers. 1484c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// 1485c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// Merge sets only if the units have the same weight. For example, on ARM, 1486c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// Q-tuples with ssub index 0 include all S regs but also include D16+. We 1487c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick/// should not expand the S set to include D regs. 1488176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trickvoid CodeGenRegBank::pruneUnitSets() { 1489176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets"); 1490176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1491176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Form an equivalence class of UnitSets with no significant difference. 14925c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick std::vector<unsigned> SuperSetIDs; 1493176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for (unsigned SubIdx = 0, EndIdx = RegUnitSets.size(); 1494176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick SubIdx != EndIdx; ++SubIdx) { 1495176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick const RegUnitSet &SubSet = RegUnitSets[SubIdx]; 1496aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick unsigned SuperIdx = 0; 1497aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick for (; SuperIdx != EndIdx; ++SuperIdx) { 1498176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick if (SuperIdx == SubIdx) 1499176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick continue; 15005c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick 1501c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight; 15025c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick const RegUnitSet &SuperSet = RegUnitSets[SuperIdx]; 15035c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick if (isRegUnitSubSet(SubSet.Units, SuperSet.Units) 1504c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick && (SubSet.Units.size() + 3 > SuperSet.Units.size()) 1505c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick && UnitWeight == RegUnits[SuperSet.Units[0]].Weight 1506c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) { 1507bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx 1508bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick << "\n"); 1509aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick break; 1510176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1511176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 15125c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick if (SuperIdx == EndIdx) 15135c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick SuperSetIDs.push_back(SubIdx); 15145c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick } 15155c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick // Populate PrunedUnitSets with each equivalence class's superset. 15165c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick std::vector<RegUnitSet> PrunedUnitSets(SuperSetIDs.size()); 15175c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick for (unsigned i = 0, e = SuperSetIDs.size(); i != e; ++i) { 15185c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick unsigned SuperIdx = SuperSetIDs[i]; 15195c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick PrunedUnitSets[i].Name = RegUnitSets[SuperIdx].Name; 15205c1761d486deb47648fa1b854692f4b64a35f0e2Andrew Trick PrunedUnitSets[i].Units.swap(RegUnitSets[SuperIdx].Units); 1521176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1522176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.swap(PrunedUnitSets); 1523176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick} 1524176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1525176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// Create a RegUnitSet for each RegClass that contains all units in the class 1526176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// including adopted units that are necessary to model register pressure. Then 1527176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// iteratively compute RegUnitSets such that the union of any two overlapping 1528176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// RegUnitSets is repreresented. 1529176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// 1530176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any 1531176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick// RegUnitSet that is a superset of that RegUnitClass. 1532176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trickvoid CodeGenRegBank::computeRegUnitSets() { 1533bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick assert(RegUnitSets.empty() && "dirty RegUnitSets"); 1534176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1535176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Compute a unique RegUnitSet for each RegClass. 1536176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick const ArrayRef<CodeGenRegisterClass*> &RegClasses = getRegClasses(); 1537176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick unsigned NumRegClasses = RegClasses.size(); 1538176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) { 1539aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick if (!RegClasses[RCIdx]->Allocatable) 1540aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick continue; 1541176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1542176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Speculatively grow the RegUnitSets to hold the new set. 1543176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.resize(RegUnitSets.size() + 1); 1544176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.back().Name = RegClasses[RCIdx]->getName(); 15450fb0678106c490b38343487ab121461f635875a0Andrew Trick 15460fb0678106c490b38343487ab121461f635875a0Andrew Trick // Compute a sorted list of units in this class. 1547ec14cd7ddc66d47cd7927f18d8c11844c400367eAndrew Trick RegClasses[RCIdx]->buildRegUnitSet(RegUnitSets.back().Units); 1548176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1549176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Find an existing RegUnitSet. 1550176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::vector<RegUnitSet>::const_iterator SetI = 1551176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick findRegUnitSet(RegUnitSets, RegUnitSets.back()); 155236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SetI != std::prev(RegUnitSets.end())) 1553176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.pop_back(); 1554176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1555176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1556bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "\nBefore pruning:\n"; 1557bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); 1558bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick USIdx < USEnd; ++USIdx) { 1559bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name 1560bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick << ":"; 1561bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units; 1562bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned i = 0, e = Units.size(); i < e; ++i) 1563bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); 1564bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "\n"; 1565bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick }); 1566bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick 1567176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Iteratively prune unit sets. 1568176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick pruneUnitSets(); 1569176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1570bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "\nBefore union:\n"; 1571bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); 1572bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick USIdx < USEnd; ++USIdx) { 1573bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name 1574bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick << ":"; 1575bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units; 1576bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned i = 0, e = Units.size(); i < e; ++i) 1577bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); 1578bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "\n"; 1579c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick } 1580c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick dbgs() << "\nUnion sets:\n"); 1581bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick 1582176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Iterate over all unit sets, including new ones added by this loop. 1583176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick unsigned NumRegUnitSubSets = RegUnitSets.size(); 1584176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) { 1585176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // In theory, this is combinatorial. In practice, it needs to be bounded 1586176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // by a small number of sets for regpressure to be efficient. 1587176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // If the assert is hit, we need to implement pruning. 1588176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick assert(Idx < (2*NumRegUnitSubSets) && "runaway unit set inference"); 1589176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1590176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Compare new sets with all original classes. 15914b745588c935a99cd3fcc574bc6e4934c2e85397Andrew Trick for (unsigned SearchIdx = (Idx >= NumRegUnitSubSets) ? 0 : Idx+1; 1592176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick SearchIdx != EndIdx; ++SearchIdx) { 1593176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::set<unsigned> Intersection; 1594176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::set_intersection(RegUnitSets[Idx].Units.begin(), 1595176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[Idx].Units.end(), 1596176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[SearchIdx].Units.begin(), 1597176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[SearchIdx].Units.end(), 1598176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::inserter(Intersection, Intersection.begin())); 1599176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick if (Intersection.empty()) 1600176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick continue; 1601176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1602176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Speculatively grow the RegUnitSets to hold the new set. 1603176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.resize(RegUnitSets.size() + 1); 1604176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.back().Name = 1605176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[Idx].Name + "+" + RegUnitSets[SearchIdx].Name; 1606176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1607176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::set_union(RegUnitSets[Idx].Units.begin(), 1608176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[Idx].Units.end(), 1609176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[SearchIdx].Units.begin(), 1610176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets[SearchIdx].Units.end(), 1611176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::inserter(RegUnitSets.back().Units, 1612176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.back().Units.begin())); 1613176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1614176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Find an existing RegUnitSet, or add the union to the unique sets. 1615176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick std::vector<RegUnitSet>::const_iterator SetI = 1616176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick findRegUnitSet(RegUnitSets, RegUnitSets.back()); 161736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SetI != std::prev(RegUnitSets.end())) 1618176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegUnitSets.pop_back(); 1619c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick else { 1620c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick DEBUG(dbgs() << "UnitSet " << RegUnitSets.size()-1 1621c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick << " " << RegUnitSets.back().Name << ":"; 1622c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick ArrayRef<unsigned> Units = RegUnitSets.back().Units; 1623c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick for (unsigned i = 0, e = Units.size(); i < e; ++i) 1624c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); 1625c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick dbgs() << "\n";); 1626c408335bf5128cb24214cce95863d9717e4cdb76Andrew Trick } 1627176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1628176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1629176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1630aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick // Iteratively prune unit sets after inferring supersets. 1631176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick pruneUnitSets(); 1632176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1633bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "\n"; 1634bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); 1635bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick USIdx < USEnd; ++USIdx) { 1636bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name 1637bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick << ":"; 1638bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units; 1639bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned i = 0, e = Units.size(); i < e; ++i) 1640bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); 1641bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "\n"; 1642bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick }); 1643bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick 1644176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // For each register class, list the UnitSets that are supersets. 1645176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegClassUnitSets.resize(NumRegClasses); 1646176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) { 1647aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick if (!RegClasses[RCIdx]->Allocatable) 1648aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick continue; 1649aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick 1650176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Recompute the sorted list of units in this class. 1651bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick std::vector<unsigned> RCRegUnits; 1652bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick RegClasses[RCIdx]->buildRegUnitSet(RCRegUnits); 1653176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1654176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Don't increase pressure for unallocatable regclasses. 1655bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick if (RCRegUnits.empty()) 1656176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick continue; 1657176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1658bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "RC " << RegClasses[RCIdx]->getName() << " Units: \n"; 1659bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick for (unsigned i = 0, e = RCRegUnits.size(); i < e; ++i) 1660bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << RegUnits[RCRegUnits[i]].getRoots()[0]->getName() << " "; 1661bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick dbgs() << "\n UnitSetIDs:"); 1662bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick 1663176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Find all supersets. 1664176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); 1665176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick USIdx != USEnd; ++USIdx) { 1666bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) { 1667bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << " " << USIdx); 1668176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick RegClassUnitSets[RCIdx].push_back(USIdx); 1669bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick } 1670176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1671bbf20d4d4af06f0410e7b3ffc71d9be751867067Andrew Trick DEBUG(dbgs() << "\n"); 1672aa744e2c44b530fc2f7b266fb61f22976cb4ea0fAndrew Trick assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass"); 1673176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick } 1674eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick 1675eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick // For each register unit, ensure that we have the list of UnitSets that 1676eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick // contain the unit. Normally, this matches an existing list of UnitSets for a 1677eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick // register class. If not, we create a new entry in RegClassUnitSets as a 1678eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick // "fake" register class. 1679eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits; 1680eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick UnitIdx < UnitEnd; ++UnitIdx) { 1681eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick std::vector<unsigned> RUSets; 1682eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) { 1683eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RegUnitSet &RUSet = RegUnitSets[i]; 1684eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick if (std::find(RUSet.Units.begin(), RUSet.Units.end(), UnitIdx) 1685eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick == RUSet.Units.end()) 1686eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick continue; 1687eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RUSets.push_back(i); 1688eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick } 1689eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick unsigned RCUnitSetsIdx = 0; 1690eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick for (unsigned e = RegClassUnitSets.size(); 1691eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RCUnitSetsIdx != e; ++RCUnitSetsIdx) { 1692eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) { 1693eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick break; 1694eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick } 1695eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick } 1696eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx; 1697eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick if (RCUnitSetsIdx == RegClassUnitSets.size()) { 1698eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick // Create a new list of UnitSets as a "fake" register class. 1699eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RegClassUnitSets.resize(RCUnitSetsIdx + 1); 1700eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick RegClassUnitSets[RCUnitSetsIdx].swap(RUSets); 1701eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick } 1702eca1fcf3d2d8246c45648fea59bd21a4091f9115Andrew Trick } 1703176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick} 1704176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1705b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesenvoid CodeGenRegBank::computeDerivedInfo() { 1706b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen computeComposites(); 1707a6035773d8d29827a124e65c258adbf0dcbb1a5aJakob Stoklund Olesen computeSubRegIndexLaneMasks(); 1708d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick 1709d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // Compute a weight for each register unit created during getSubRegs. 1710d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick // This may create adopted register units (with unit # >= NumNativeRegUnits). 1711d35ac3c8bc37ab383b10a04b9c8b1087d6b2bc45Andrew Trick computeRegUnitWeights(); 1712176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick 1713176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // Compute a unique set of RegUnitSets. One for each RegClass and inferred 1714176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick // supersets for the union of overlapping sets. 1715176194d4ee2774bc135ababc5bd6c6c9f606b2a5Andrew Trick computeRegUnitSets(); 1716bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick 1717bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick // Get the weight of each set. 1718bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) 1719bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units); 1720bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick 1721bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick // Find the order of each set. 1722bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick RegUnitSetOrder.reserve(RegUnitSets.size()); 1723bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) 1724bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick RegUnitSetOrder.push_back(Idx); 1725bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick 1726bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick std::stable_sort(RegUnitSetOrder.begin(), RegUnitSetOrder.end(), 172736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines [this](unsigned ID1, unsigned ID2) { 172836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return getRegPressureSet(ID1).Units.size() < 172936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines getRegPressureSet(ID2).Units.size(); 173036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 1731bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) { 1732bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx; 1733bba663e30a61b138c8f76632f8cacf00d7b0649aAndrew Trick } 1734b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen} 1735b5923db192d2aa938ff3c12aaac87d80ab649625Jakob Stoklund Olesen 17367e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// 17377e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// Synthesize missing register class intersections. 17387e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// 17397e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X) 17407e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// returns a maximal register class for all X. 17417e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen// 17427e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesenvoid CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) { 17437e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen for (unsigned rci = 0, rce = RegClasses.size(); rci != rce; ++rci) { 17447e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen CodeGenRegisterClass *RC1 = RC; 17457e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen CodeGenRegisterClass *RC2 = RegClasses[rci]; 17467e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen if (RC1 == RC2) 17477e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen continue; 17487e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 17497e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen // Compute the set intersection of RC1 and RC2. 17507e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen const CodeGenRegister::Set &Memb1 = RC1->getMembers(); 17517e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen const CodeGenRegister::Set &Memb2 = RC2->getMembers(); 17527e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen CodeGenRegister::Set Intersection; 17537e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen std::set_intersection(Memb1.begin(), Memb1.end(), 17547e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen Memb2.begin(), Memb2.end(), 1755d4c826f64866295fcbfa472d812bd3ec3a5e4c9fJakob Stoklund Olesen std::inserter(Intersection, Intersection.begin()), 1756d4c826f64866295fcbfa472d812bd3ec3a5e4c9fJakob Stoklund Olesen CodeGenRegister::Less()); 17577e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 17587e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen // Skip disjoint class pairs. 17597e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen if (Intersection.empty()) 17607e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen continue; 17617e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 17627e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen // If RC1 and RC2 have different spill sizes or alignments, use the 17637e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen // larger size for sub-classing. If they are equal, prefer RC1. 17647e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen if (RC2->SpillSize > RC1->SpillSize || 17657e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen (RC2->SpillSize == RC1->SpillSize && 17667e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen RC2->SpillAlignment > RC1->SpillAlignment)) 17677e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen std::swap(RC1, RC2); 17687e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 17697e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen getOrCreateSubClass(RC1, &Intersection, 17707e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen RC1->getName() + "_and_" + RC2->getName()); 17717e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen } 17727e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen} 17737e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 1774fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// 1775fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// Synthesize missing sub-classes for getSubClassWithSubReg(). 1776fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// 1777fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// Make sure that the set of registers in RC with a given SubIdx sub-register 1778fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// form a register class. Update RC->SubClassWithSubReg. 1779fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// 1780fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesenvoid CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) { 1781fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // Map SubRegIndex to set of registers in RC supporting that SubRegIndex. 17825fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen typedef std::map<CodeGenSubRegIndex*, CodeGenRegister::Set, 17835fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenSubRegIndex::Less> SubReg2SetMap; 1784fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen 1785fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // Compute the set of registers supporting each SubRegIndex. 1786fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen SubReg2SetMap SRSets; 1787fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(), 1788fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen RE = RC->getMembers().end(); RI != RE; ++RI) { 1789fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM = (*RI)->getSubRegs(); 1790fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(), 1791fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen E = SRM.end(); I != E; ++I) 1792fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen SRSets[I->first].insert(*RI); 1793fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen } 1794fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen 1795fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // Find matching classes for all SRSets entries. Iterate in SubRegIndex 1796fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // numerical order to visit synthetic indices last. 1797fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { 17985fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenSubRegIndex *SubIdx = SubRegIndices[sri]; 1799fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen SubReg2SetMap::const_iterator I = SRSets.find(SubIdx); 1800fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // Unsupported SubRegIndex. Skip it. 1801fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen if (I == SRSets.end()) 1802fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen continue; 1803fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // In most cases, all RC registers support the SubRegIndex. 1804fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen if (I->second.size() == RC->getMembers().size()) { 1805fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen RC->setSubClassWithSubReg(SubIdx, RC); 1806fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen continue; 1807fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen } 1808fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // This is a real subset. See if we have a matching class. 1809fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen CodeGenRegisterClass *SubRC = 1810fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen getOrCreateSubClass(RC, &I->second, 1811fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen RC->getName() + "_with_" + I->first->getName()); 1812fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen RC->setSubClassWithSubReg(SubIdx, SubRC); 1813fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen } 1814fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen} 1815fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen 1816fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen// 1817a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// Synthesize missing sub-classes of RC for getMatchingSuperRegClass(). 1818a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// 1819a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X) 1820a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// has a maximal result for any SubIdx and any X >= FirstSubRegRC. 1821a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// 1822a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1823a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesenvoid CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC, 1824a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen unsigned FirstSubRegRC) { 1825a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen SmallVector<std::pair<const CodeGenRegister*, 1826a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen const CodeGenRegister*>, 16> SSPairs; 1827b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen BitVector TopoSigs(getNumTopoSigs()); 1828a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1829a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Iterate in SubRegIndex numerical order to visit synthetic indices last. 1830a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { 18315fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen CodeGenSubRegIndex *SubIdx = SubRegIndices[sri]; 1832a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Skip indexes that aren't fully supported by RC's registers. This was 1833a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // computed by inferSubClassWithSubReg() above which should have been 1834a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // called first. 1835a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen if (RC->getSubClassWithSubReg(SubIdx) != RC) 1836a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen continue; 1837a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1838a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Build list of (Super, Sub) pairs for this SubIdx. 1839a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen SSPairs.clear(); 1840b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigs.reset(); 1841a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(), 1842a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen RE = RC->getMembers().end(); RI != RE; ++RI) { 1843a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen const CodeGenRegister *Super = *RI; 1844a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen const CodeGenRegister *Sub = Super->getSubRegs().find(SubIdx)->second; 1845a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen assert(Sub && "Missing sub-register"); 1846a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen SSPairs.push_back(std::make_pair(Super, Sub)); 1847b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen TopoSigs.set(Sub->getTopoSig()); 1848a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen } 1849a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1850a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Iterate over sub-register class candidates. Ignore classes created by 1851a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // this loop. They will never be useful. 1852a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen for (unsigned rci = FirstSubRegRC, rce = RegClasses.size(); rci != rce; 1853a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen ++rci) { 1854a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen CodeGenRegisterClass *SubRC = RegClasses[rci]; 1855b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen // Topological shortcut: SubRC members have the wrong shape. 1856b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen if (!TopoSigs.anyCommon(SubRC->getTopoSigs())) 1857b81cbc271faed9fa633920436cd7ae49750a9a42Jakob Stoklund Olesen continue; 1858a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Compute the subset of RC that maps into SubRC. 1859a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen CodeGenRegister::Set SubSet; 1860a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen for (unsigned i = 0, e = SSPairs.size(); i != e; ++i) 1861a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen if (SubRC->contains(SSPairs[i].second)) 1862a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen SubSet.insert(SSPairs[i].first); 1863a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen if (SubSet.empty()) 1864a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen continue; 1865a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // RC injects completely into SubRC. 1866570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen if (SubSet.size() == SSPairs.size()) { 1867570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen SubRC->addSuperRegClass(SubIdx, RC); 1868a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen continue; 1869570f9a972e02830d1ca223743dd6b4cc4fdf9549Jakob Stoklund Olesen } 1870a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Only a subset of RC maps into SubRC. Make sure it is represented by a 1871a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // class. 1872a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen getOrCreateSubClass(RC, &SubSet, RC->getName() + 1873a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen "_with_" + SubIdx->getName() + 1874a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen "_in_" + SubRC->getName()); 1875a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen } 1876a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen } 1877a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen} 1878a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1879a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1880a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen// 1881babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// Infer missing register classes. 1882babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen// 1883babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesenvoid CodeGenRegBank::computeInferredRegisterClasses() { 1884babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // When this function is called, the register classes have not been sorted 1885babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // and assigned EnumValues yet. That means getSubClasses(), 1886babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // getSuperClasses(), and hasSubClass() functions are defunct. 1887a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen unsigned FirstNewRC = RegClasses.size(); 1888babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 1889babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen // Visit all register classes, including the ones being added by the loop. 1890babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { 1891fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen CodeGenRegisterClass *RC = RegClasses[rci]; 1892babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 1893fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen // Synthesize answers for getSubClassWithSubReg(). 1894fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen inferSubClassWithSubReg(RC); 18957e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen 18967e56831a6804812b2295c5446a05f4ec457b6b3eJakob Stoklund Olesen // Synthesize answers for getCommonSubClass(). 1897fec33444c5ca22e0338fdac0fcaee2644bd756afJakob Stoklund Olesen inferCommonSubClass(RC); 1898a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1899a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // Synthesize answers for getMatchingSuperRegClass(). 1900a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen inferMatchingSuperRegClass(RC); 1901a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen 1902a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // New register classes are created while this loop is running, and we need 1903a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // to visit all of them. I particular, inferMatchingSuperRegClass needs 1904a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // to match old super-register classes with sub-register classes created 1905a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // after inferMatchingSuperRegClass was called. At this point, 1906a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC = 1907a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen // [0..FirstNewRC). We need to cover SubRC = [FirstNewRC..rci]. 1908a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen if (rci + 1 == FirstNewRC) { 1909a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen unsigned NextNewRC = RegClasses.size(); 1910a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen for (unsigned rci2 = 0; rci2 != FirstNewRC; ++rci2) 1911a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen inferMatchingSuperRegClass(RegClasses[rci2], FirstNewRC); 1912a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen FirstNewRC = NextNewRC; 1913a9f65b9a1f57dcf546399ac32bf89d71d20df5b9Jakob Stoklund Olesen } 1914babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen } 1915babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen} 1916babf0569e2e4f204f9a304416cc4acc349d8f836Jakob Stoklund Olesen 19177b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// getRegisterClassForRegister - Find the register class that contains the 19187b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// specified physical register. If the register is not in a register class, 19197b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// return null. If the register is in multiple classes, and the classes have a 19207b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// superset-subset relationship and the same set of types, return the 19217b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen/// superclass. Otherwise return null. 19227b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesenconst CodeGenRegisterClass* 19237b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund OlesenCodeGenRegBank::getRegClassForRegister(Record *R) { 1924ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen const CodeGenRegister *Reg = getReg(R); 192529f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen ArrayRef<CodeGenRegisterClass*> RCs = getRegClasses(); 1926dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const CodeGenRegisterClass *FoundRC = nullptr; 19277b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen for (unsigned i = 0, e = RCs.size(); i != e; ++i) { 192829f018cee616e4082e5005bc9adee4dc777e621cJakob Stoklund Olesen const CodeGenRegisterClass &RC = *RCs[i]; 1929ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (!RC.contains(Reg)) 19307b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 19317b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 19327b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // If this is the first class that contains the register, 19337b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // make a note of it and go on to the next class. 19347b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (!FoundRC) { 19357b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen FoundRC = &RC; 19367b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 19377b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 19387b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 19397b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // If a register's classes have different types, return null. 19407b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen if (RC.getValueTypes() != FoundRC->getValueTypes()) 1941dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 19427b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 19437b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Check to see if the previously found class that contains 19447b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // the register is a subclass of the current class. If so, 19457b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // prefer the superclass. 1946ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (RC.hasSubClass(FoundRC)) { 19477b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen FoundRC = &RC; 19487b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 19497b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 19507b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 19517b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Check to see if the previously found class that contains 19527b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // the register is a superclass of the current class. If so, 19537b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // prefer the superclass. 1954ae1920b1efa72c1789d562df4746110d0c2e10bdJakob Stoklund Olesen if (FoundRC->hasSubClass(&RC)) 19557b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen continue; 19567b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen 19577b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Multiple classes, and neither is a superclass of the other. 19587b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen // Return null. 1959dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 19607b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen } 19617b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen return FoundRC; 19627b9cafde5e3faec22bbfbbc90cca0876968abad9Jakob Stoklund Olesen} 1963ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen 1964ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund OlesenBitVector CodeGenRegBank::computeCoveredRegisters(ArrayRef<Record*> Regs) { 1965c6a96ff6aeeb77e1007364e5603b72f3ab4cc7bdJakob Stoklund Olesen SetVector<const CodeGenRegister*> Set; 1966ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen 1967ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen // First add Regs with all sub-registers. 1968ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 1969ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen CodeGenRegister *Reg = getReg(Regs[i]); 1970ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen if (Set.insert(Reg)) 1971ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen // Reg is new, add all sub-registers. 1972ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen // The pre-ordering is not important here. 19735fcc156344e0d38fa5f5eab3d9193b859b27b45eJakob Stoklund Olesen Reg->addSubRegsPreOrder(Set, *this); 1974ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen } 1975ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen 1976ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen // Second, find all super-registers that are completely covered by the set. 197731867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen for (unsigned i = 0; i != Set.size(); ++i) { 197831867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen const CodeGenRegister::SuperRegList &SR = Set[i]->getSuperRegs(); 197931867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen for (unsigned j = 0, e = SR.size(); j != e; ++j) { 1980c6a96ff6aeeb77e1007364e5603b72f3ab4cc7bdJakob Stoklund Olesen const CodeGenRegister *Super = SR[j]; 198131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (!Super->CoveredBySubRegs || Set.count(Super)) 198231867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen continue; 198331867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen // This new super-register is covered by its sub-registers. 198431867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen bool AllSubsInSet = true; 198531867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen const CodeGenRegister::SubRegMap &SRM = Super->getSubRegs(); 198631867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(), 198731867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen E = SRM.end(); I != E; ++I) 198831867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (!Set.count(I->second)) { 198931867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen AllSubsInSet = false; 199031867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen break; 199131867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen } 199231867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen // All sub-registers in Set, add Super as well. 199331867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen // We will visit Super later to recheck its super-registers. 199431867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen if (AllSubsInSet) 199531867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen Set.insert(Super); 199631867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen } 199731867660cb81ea2b1d1a6ffa7d09c91acb754a8bJakob Stoklund Olesen } 1998ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen 1999ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen // Convert to BitVector. 2000ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen BitVector BV(Registers.size() + 1); 2001ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen for (unsigned i = 0, e = Set.size(); i != e; ++i) 2002ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen BV.set(Set[i]->EnumValue); 2003ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen return BV; 2004ec572539dd5660f9ca42027ac04df3a3f8c0cab1Jakob Stoklund Olesen} 2005