X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.cpp;h=613422549230a327c616d861d000fad1fed2b9d8;hb=b3cabb44c32b5a3aba9b4d23aae9723d498ea7a9;hp=797c31a934526fd775330b1bbc2f4fbe771db4eb;hpb=31d938a6b1173c642f975d78417459d4d8cd3677;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 797c31a9345..61342254923 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -14,12 +14,12 @@ #include "CodeGenRegisters.h" #include "CodeGenTarget.h" -#include "llvm/TableGen/Error.h" #include "llvm/ADT/IntEqClasses.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/Twine.h" +#include "llvm/TableGen/Error.h" using namespace llvm; @@ -28,19 +28,18 @@ using namespace llvm; //===----------------------------------------------------------------------===// CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum) - : TheDef(R), - EnumValue(Enum) -{} - -std::string CodeGenSubRegIndex::getNamespace() const { - if (TheDef->getValue("Namespace")) - return TheDef->getValueAsString("Namespace"); - else - return ""; + : TheDef(R), EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { + Name = R->getName(); + if (R->getValue("Namespace")) + Namespace = R->getValueAsString("Namespace"); + Size = R->getValueAsInt("Size"); + Offset = R->getValueAsInt("Offset"); } -const std::string &CodeGenSubRegIndex::getName() const { - return TheDef->getName(); +CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace, + unsigned Enum) + : TheDef(0), Name(N), Namespace(Nspace), Size(-1), Offset(-1), + EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { } std::string CodeGenSubRegIndex::getQualifiedName() const { @@ -52,26 +51,49 @@ std::string CodeGenSubRegIndex::getQualifiedName() const { } void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) { - std::vector Comps = TheDef->getValueAsListOfDefs("ComposedOf"); - if (Comps.empty()) + if (!TheDef) return; - if (Comps.size() != 2) - throw TGError(TheDef->getLoc(), "ComposedOf must have exactly two entries"); - CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]); - CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]); - CodeGenSubRegIndex *X = A->addComposite(B, this); - if (X) - throw TGError(TheDef->getLoc(), "Ambiguous ComposedOf entries"); -} -void CodeGenSubRegIndex::cleanComposites() { - // Clean out redundant mappings of the form this+X -> X. - for (CompMap::iterator i = Composed.begin(), e = Composed.end(); i != e;) { - CompMap::iterator j = i; - ++i; - if (j->first == j->second) - Composed.erase(j); + std::vector Comps = TheDef->getValueAsListOfDefs("ComposedOf"); + if (!Comps.empty()) { + if (Comps.size() != 2) + PrintFatalError(TheDef->getLoc(), + "ComposedOf must have exactly two entries"); + CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]); + CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]); + CodeGenSubRegIndex *X = A->addComposite(B, this); + if (X) + PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries"); } + + std::vector Parts = + TheDef->getValueAsListOfDefs("CoveringSubRegIndices"); + if (!Parts.empty()) { + if (Parts.size() < 2) + PrintFatalError(TheDef->getLoc(), + "CoveredBySubRegs must have two or more entries"); + SmallVector IdxParts; + for (unsigned i = 0, e = Parts.size(); i != e; ++i) + IdxParts.push_back(RegBank.getSubRegIdx(Parts[i])); + RegBank.addConcatSubRegIndex(IdxParts, this); + } +} + +unsigned CodeGenSubRegIndex::computeLaneMask() { + // Already computed? + if (LaneMask) + return LaneMask; + + // Recursion guard, shouldn't be required. + LaneMask = ~0u; + + // The lane mask is simply the union of all sub-indices. + unsigned M = 0; + for (CompMap::iterator I = Composed.begin(), E = Composed.end(); I != E; ++I) + M |= I->second->computeLaneMask(); + assert(M && "Missing lane mask, sub-register cycle?"); + LaneMask = M; + return LaneMask; } //===----------------------------------------------------------------------===// @@ -83,6 +105,7 @@ CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum) EnumValue(Enum), CostPerUse(R->getValueAsInt("CostPerUse")), CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")), + NumNativeRegUnits(0), SubRegsComplete(false), SuperRegsComplete(false), TopoSig(~0u) @@ -93,8 +116,8 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { std::vector SRs = TheDef->getValueAsListOfDefs("SubRegs"); if (SRIs.size() != SRs.size()) - throw TGError(TheDef->getLoc(), - "SubRegs and SubRegIndices must have the same size"); + PrintFatalError(TheDef->getLoc(), + "SubRegs and SubRegIndices must have the same size"); for (unsigned i = 0, e = SRIs.size(); i != e; ++i) { ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i])); @@ -109,7 +132,7 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { if (CoveredBySubRegs && !ExplicitSubRegs.empty()) ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this); - // Add ad hoc alias links. This is a symmetric relationship betwen two + // Add ad hoc alias links. This is a symmetric relationship between two // registers, so build a symmetric graph by adding links in both ends. std::vector Aliases = TheDef->getValueAsListOfDefs("Aliases"); for (unsigned i = 0, e = Aliases.size(); i != e; ++i) { @@ -186,16 +209,7 @@ bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) { unsigned OldNumUnits = RegUnits.size(); for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I) { - // Strangely a register may have itself as a subreg (self-cycle) e.g. XMM. - // Only create a unit if no other subregs have units. CodeGenRegister *SR = I->second; - if (SR == this) { - // RegUnits are only empty during computeSubRegs, prior to computing - // weight. - if (RegUnits.empty()) - RegUnits.push_back(RegBank.newRegUnit(0)); - continue; - } // Merge the subregister's units into this register's RegUnits. mergeRegUnits(RegUnits, SR->RegUnits); } @@ -214,8 +228,8 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { CodeGenRegister *SR = ExplicitSubRegs[i]; CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i]; if (!SubRegs.insert(std::make_pair(Idx, SR)).second) - throw TGError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() + - " appears twice in Register " + getName()); + PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() + + " appears twice in Register " + getName()); // Map explicit sub-registers first, so the names take precedence. // The inherited sub-registers are mapped below. SubReg2Idx.insert(std::make_pair(SR, Idx)); @@ -265,44 +279,6 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { } } - // Process the composites. - ListInit *Comps = TheDef->getValueAsListInit("CompositeIndices"); - for (unsigned i = 0, e = Comps->size(); i != e; ++i) { - DagInit *Pat = dynamic_cast(Comps->getElement(i)); - if (!Pat) - throw TGError(TheDef->getLoc(), "Invalid dag '" + - Comps->getElement(i)->getAsString() + - "' in CompositeIndices"); - DefInit *BaseIdxInit = dynamic_cast(Pat->getOperator()); - if (!BaseIdxInit || !BaseIdxInit->getDef()->isSubClassOf("SubRegIndex")) - throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + - Pat->getAsString()); - CodeGenSubRegIndex *BaseIdx = RegBank.getSubRegIdx(BaseIdxInit->getDef()); - - // Resolve list of subreg indices into R2. - CodeGenRegister *R2 = this; - for (DagInit::const_arg_iterator di = Pat->arg_begin(), - de = Pat->arg_end(); di != de; ++di) { - DefInit *IdxInit = dynamic_cast(*di); - if (!IdxInit || !IdxInit->getDef()->isSubClassOf("SubRegIndex")) - throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + - Pat->getAsString()); - CodeGenSubRegIndex *Idx = RegBank.getSubRegIdx(IdxInit->getDef()); - const SubRegMap &R2Subs = R2->computeSubRegs(RegBank); - SubRegMap::const_iterator ni = R2Subs.find(Idx); - if (ni == R2Subs.end()) - throw TGError(TheDef->getLoc(), "Composite " + Pat->getAsString() + - " refers to bad index in " + R2->getName()); - R2 = ni->second; - } - - // Insert composite index. Allow overriding inherited indices etc. - SubRegs[BaseIdx] = R2; - - // R2 is no longer an orphan. - Orphans.erase(R2); - } - // Now Orphans contains the inherited subregisters without a direct index. // Create inferred indexes for all missing entries. // Work backwards in the Indices vector in order to compose subregs bottom-up. @@ -317,7 +293,7 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // dsub_2 -> ssub_0 // // We pick the latter composition because another register may have [dsub_0, - // dsub_1, dsub_2] subregs without neccessarily having a qsub_1 subreg. The + // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The // dsub_2 -> ssub_0 composition can be shared. while (!Indices.empty() && !Orphans.empty()) { CodeGenSubRegIndex *Idx = Indices.pop_back_val(); @@ -332,14 +308,30 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // Compute the inverse SubReg -> Idx map. for (SubRegMap::const_iterator SI = SubRegs.begin(), SE = SubRegs.end(); SI != SE; ++SI) { - // Ignore idempotent sub-register indices. - if (SI->second == this) + if (SI->second == this) { + ArrayRef Loc; + if (TheDef) + Loc = TheDef->getLoc(); + PrintFatalError(Loc, "Register " + getName() + + " has itself as a sub-register"); + } + + // Compute AllSuperRegsCovered. + if (!CoveredBySubRegs) + SI->first->AllSuperRegsCovered = false; + + // Ensure that every sub-register has a unique name. + DenseMap::iterator Ins = + SubReg2Idx.insert(std::make_pair(SI->second, SI->first)).first; + if (Ins->second == SI->first) continue; - // Is is possible to have multiple names for the same sub-register. - // For example, XMM0 appears as sub_xmm, sub_sd, and sub_ss in YMM0. - // Eventually, this degeneration should go away, but for now we simply give - // precedence to the explicit sub-register index over the inherited ones. - SubReg2Idx.insert(std::make_pair(SI->second, SI->first)); + // Trouble: Two different names for SI->second. + ArrayRef Loc; + if (TheDef) + Loc = TheDef->getLoc(); + PrintFatalError(Loc, "Sub-register can't have two names: " + + SI->second->getName() + " available as " + + SI->first->getName() + " and " + Ins->second->getName()); } // Derive possible names for sub-register concatenations from any explicit @@ -360,20 +352,53 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { RegBank.addConcatSubRegIndex(Parts, ExplicitSubRegIndices[i]); } - // Initialize RegUnitList. A register with no subregisters creates its own - // unit. Otherwise, it inherits all its subregister's units. Because - // getSubRegs is called recursively, this processes the register hierarchy in - // postorder. + // Initialize RegUnitList. Because getSubRegs is called recursively, this + // processes the register hierarchy in postorder. // - // TODO: We currently assume all register units correspond to a named "leaf" - // register. We should also unify register units for ad-hoc register - // aliases. This can be done by iteratively merging units for aliasing - // registers using a worklist. - assert(RegUnits.empty() && "Should only initialize RegUnits once"); - if (SubRegs.empty()) - RegUnits.push_back(RegBank.newRegUnit(0)); - else - inheritRegUnits(RegBank); + // Inherit all sub-register units. It is good enough to look at the explicit + // sub-registers, the other registers won't contribute any more units. + for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { + CodeGenRegister *SR = ExplicitSubRegs[i]; + // Explicit sub-registers are usually disjoint, so this is a good way of + // computing the union. We may pick up a few duplicates that will be + // eliminated below. + unsigned N = RegUnits.size(); + RegUnits.append(SR->RegUnits.begin(), SR->RegUnits.end()); + std::inplace_merge(RegUnits.begin(), RegUnits.begin() + N, RegUnits.end()); + } + RegUnits.erase(std::unique(RegUnits.begin(), RegUnits.end()), RegUnits.end()); + + // Absent any ad hoc aliasing, we create one register unit per leaf register. + // These units correspond to the maximal cliques in the register overlap + // graph which is optimal. + // + // When there is ad hoc aliasing, we simply create one unit per edge in the + // undirected ad hoc aliasing graph. Technically, we could do better by + // identifying maximal cliques in the ad hoc graph, but cliques larger than 2 + // are extremely rare anyway (I've never seen one), so we don't bother with + // the added complexity. + for (unsigned i = 0, e = ExplicitAliases.size(); i != e; ++i) { + CodeGenRegister *AR = ExplicitAliases[i]; + // Only visit each edge once. + if (AR->SubRegsComplete) + continue; + // Create a RegUnit representing this alias edge, and add it to both + // registers. + unsigned Unit = RegBank.newRegUnit(this, AR); + RegUnits.push_back(Unit); + AR->RegUnits.push_back(Unit); + } + + // Finally, create units for leaf registers without ad hoc aliases. Note that + // a leaf register with ad hoc aliases doesn't get its own unit - it isn't + // necessary. This means the aliasing leaf registers can share a single unit. + if (RegUnits.empty()) + RegUnits.push_back(RegBank.newRegUnit(this)); + + // We have now computed the native register units. More may be adopted later + // for balancing purposes. + NumNativeRegUnits = RegUnits.size(); + return SubRegs; } @@ -451,8 +476,8 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) { SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) { CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second); if (!SubIdx) - throw TGError(TheDef->getLoc(), "No SubRegIndex for " + - SI->second->getName() + " in " + getName()); + PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " + + SI->second->getName() + " in " + getName()); NewIdx->addComposite(SI->first, SubIdx); } } @@ -480,8 +505,6 @@ void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) { Id.push_back(I->first->EnumValue); Id.push_back(I->second->TopoSig); - if (I->second == this) - continue; // Don't add duplicate entries. if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this) continue; @@ -502,8 +525,7 @@ CodeGenRegister::addSubRegsPreOrder(SetVector &OSet, // Add any secondary sub-registers that weren't part of the explicit tree. for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I) - if (I->second != this) - OSet.insert(I->second); + OSet.insert(I->second); } // Get the sum of this register's unit weights. @@ -511,7 +533,7 @@ unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const { unsigned Weight = 0; for (RegUnitList::const_iterator I = RegUnits.begin(), E = RegUnits.end(); I != E; ++I) { - Weight += RegBank.getRegUnitWeight(*I); + Weight += RegBank.getRegUnit(*I).Weight; } return Weight; } @@ -530,15 +552,16 @@ struct TupleExpander : SetTheory::Expander { unsigned Dim = Indices.size(); ListInit *SubRegs = Def->getValueAsListInit("SubRegs"); if (Dim != SubRegs->getSize()) - throw TGError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); + PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); if (Dim < 2) - throw TGError(Def->getLoc(), "Tuples must have at least 2 sub-registers"); + PrintFatalError(Def->getLoc(), + "Tuples must have at least 2 sub-registers"); // Evaluate the sub-register lists to be zipped. unsigned Length = ~0u; SmallVector Lists(Dim); for (unsigned i = 0; i != Dim; ++i) { - ST.evaluate(SubRegs->getElement(i), Lists[i]); + ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc()); Length = std::min(Length, unsigned(Lists[i].size())); } @@ -572,8 +595,10 @@ struct TupleExpander : SetTheory::Expander { Elts.insert(NewReg); // Copy Proto super-classes. - for (unsigned i = 0, e = Proto->getSuperClasses().size(); i != e; ++i) - NewReg->addSuperClass(Proto->getSuperClasses()[i]); + ArrayRef Supers = Proto->getSuperClasses(); + ArrayRef Ranges = Proto->getSuperClassRanges(); + for (unsigned i = 0, e = Supers.size(); i != e; ++i) + NewReg->addSuperClass(Supers[i], Ranges[i]); // Copy Proto fields. for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) { @@ -637,15 +662,17 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) // Rename anonymous register classes. if (R->getName().size() > 9 && R->getName()[9] == '.') { static unsigned AnonCounter = 0; - R->setName("AnonRegClass_"+utostr(AnonCounter++)); + R->setName("AnonRegClass_" + utostr(AnonCounter)); + // MSVC2012 ICEs if AnonCounter++ is directly passed to utostr. + ++AnonCounter; } std::vector TypeList = R->getValueAsListOfDefs("RegTypes"); for (unsigned i = 0, e = TypeList.size(); i != e; ++i) { Record *Type = TypeList[i]; if (!Type->isSubClassOf("ValueType")) - throw "RegTypes list member '" + Type->getName() + - "' does not derive from the ValueType class!"; + PrintFatalError("RegTypes list member '" + Type->getName() + + "' does not derive from the ValueType class!"); VTs.push_back(getValueType(Type)); } assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!"); @@ -666,14 +693,14 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) // Alternative allocation orders may be subsets. SetTheory::RecSet Order; for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) { - RegBank.getSets().evaluate(AltOrders->getElement(i), Order); + RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc()); Orders[1 + i].append(Order.begin(), Order.end()); // Verify that all altorder members are regclass members. while (!Order.empty()) { CodeGenRegister *Reg = RegBank.getReg(Order.back()); Order.pop_back(); if (!contains(Reg)) - throw TGError(R->getLoc(), " AltOrder register " + Reg->getName() + + PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() + " is not a class member"); } } @@ -692,15 +719,20 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) // Create an inferred register class that was missing from the .td files. // Most properties will be inherited from the closest super-class after the // class structure has been computed. -CodeGenRegisterClass::CodeGenRegisterClass(StringRef Name, Key Props) +CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, + StringRef Name, Key Props) : Members(*Props.Members), TheDef(0), Name(Name), + TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), SpillSize(Props.SpillSize), SpillAlignment(Props.SpillAlignment), CopyCost(0), Allocatable(true) { + for (CodeGenRegister::Set::iterator I = Members.begin(), E = Members.end(); + I != E; ++I) + TopoSigs.set((*I)->getTopoSig()); } // Compute inherited propertied for a synthesized register class. @@ -837,7 +869,7 @@ void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) { RC.SubClasses |= SubRC->SubClasses; } - // Sweep up missed clique members. They will be immediately preceeding RC. + // Sweep up missed clique members. They will be immediately preceding RC. for (unsigned s = rci - 1; s && testSubClass(&RC, RegClasses[s - 1]); --s) RC.SubClasses.set(s - 1); } @@ -888,7 +920,7 @@ void CodeGenRegisterClass::buildRegUnitSet( // CodeGenRegBank //===----------------------------------------------------------------------===// -CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { +CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Configure register Sets to understand register classes and tuples. Sets.addFieldExpander("RegisterClass", "MemberList"); Sets.addFieldExpander("CalleeSavedRegs", "SaveList"); @@ -898,7 +930,6 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // More indices will be synthesized later. std::vector SRIs = Records.getAllDerivedDefinitions("SubRegIndex"); std::sort(SRIs.begin(), SRIs.end(), LessRecord()); - NumNamedIndices = SRIs.size(); for (unsigned i = 0, e = SRIs.size(); i != e; ++i) getSubRegIdx(SRIs[i]); // Build composite maps from ComposedOf fields. @@ -907,7 +938,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // Read in the register definitions. std::vector Regs = Records.getAllDerivedDefinitions("Register"); - std::sort(Regs.begin(), Regs.end(), LessRecord()); + std::sort(Regs.begin(), Regs.end(), LessRecordRegister()); Registers.reserve(Regs.size()); // Assign the enumeration values. for (unsigned i = 0, e = Regs.size(); i != e; ++i) @@ -916,10 +947,16 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // Expand tuples and number the new registers. std::vector Tups = Records.getAllDerivedDefinitions("RegisterTuples"); + + std::vector TupRegsCopy; for (unsigned i = 0, e = Tups.size(); i != e; ++i) { const std::vector *TupRegs = Sets.expand(Tups[i]); - for (unsigned j = 0, je = TupRegs->size(); j != je; ++j) - getReg((*TupRegs)[j]); + TupRegsCopy.reserve(TupRegs->size()); + TupRegsCopy.assign(TupRegs->begin(), TupRegs->end()); + std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister()); + for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j) + getReg((TupRegsCopy)[j]); + TupRegsCopy.clear(); } // Now all the registers are known. Build the object graph of explicit @@ -927,9 +964,14 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { for (unsigned i = 0, e = Registers.size(); i != e; ++i) Registers[i]->buildObjectGraph(*this); + // Compute register name map. + for (unsigned i = 0, e = Registers.size(); i != e; ++i) + RegistersByName.GetOrCreateValue( + Registers[i]->TheDef->getValueAsString("AsmName"), + Registers[i]); + // Precompute all sub-register maps. // This will create Composite entries for all inferred sub-register indices. - NumRegUnits = 0; for (unsigned i = 0, e = Registers.size(); i != e; ++i) Registers[i]->computeSubRegs(*this); @@ -945,12 +987,12 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // Native register units are associated with a leaf register. They've all been // discovered now. - NumNativeRegUnits = NumRegUnits; + NumNativeRegUnits = RegUnits.size(); // Read in register class definitions. std::vector RCs = Records.getAllDerivedDefinitions("RegisterClass"); if (RCs.empty()) - throw std::string("No 'RegisterClass' subclasses defined!"); + PrintFatalError(std::string("No 'RegisterClass' subclasses defined!")); // Allocate user-defined register classes. RegClasses.reserve(RCs.size()); @@ -967,6 +1009,15 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { CodeGenRegisterClass::computeSubClasses(*this); } +// Create a synthetic CodeGenSubRegIndex without a corresponding Record. +CodeGenSubRegIndex* +CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) { + CodeGenSubRegIndex *Idx = new CodeGenSubRegIndex(Name, Namespace, + SubRegIndices.size() + 1); + SubRegIndices.push_back(Idx); + return Idx; +} + CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) { CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def]; if (Idx) @@ -1009,7 +1060,7 @@ CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC, return FoundI->second; // Sub-class doesn't exist, create a new one. - CodeGenRegisterClass *NewRC = new CodeGenRegisterClass(Name, K); + CodeGenRegisterClass *NewRC = new CodeGenRegisterClass(*this, Name, K); addToMaps(NewRC); return NewRC; } @@ -1018,7 +1069,7 @@ CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { if (CodeGenRegisterClass *RC = Def2RC[Def]) return RC; - throw TGError(Def->getLoc(), "Not a known RegisterClass!"); + PrintFatalError(Def->getLoc(), "Not a known RegisterClass!"); } CodeGenSubRegIndex* @@ -1031,7 +1082,7 @@ CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A, // None exists, synthesize one. std::string Name = A->getName() + "_then_" + B->getName(); - Comp = getSubRegIdx(new Record(Name, SMLoc(), Records)); + Comp = createSubRegIndex(Name, A->getNamespace()); A->addComposite(B, Comp); return Comp; } @@ -1047,11 +1098,24 @@ getConcatSubRegIndex(const SmallVector &Parts) { // None exists, synthesize one. std::string Name = Parts.front()->getName(); + // Determine whether all parts are contiguous. + bool isContinuous = true; + unsigned Size = Parts.front()->Size; + unsigned LastOffset = Parts.front()->Offset; + unsigned LastSize = Parts.front()->Size; for (unsigned i = 1, e = Parts.size(); i != e; ++i) { Name += '_'; Name += Parts[i]->getName(); + Size += Parts[i]->Size; + if (Parts[i]->Offset != (LastOffset + LastSize)) + isContinuous = false; + LastOffset = Parts[i]->Offset; + LastSize = Parts[i]->Size; } - return Idx = getSubRegIdx(new Record(Name, SMLoc(), Records)); + Idx = createSubRegIndex(Name, Parts.front()->getNamespace()); + Idx->Size = Size; + Idx->Offset = isContinuous ? Parts.front()->Offset : -1; + return Idx; } void CodeGenRegBank::computeComposites() { @@ -1097,11 +1161,53 @@ void CodeGenRegBank::computeComposites() { } } } +} + +// Compute lane masks. This is similar to register units, but at the +// sub-register index level. Each bit in the lane mask is like a register unit +// class, and two lane masks will have a bit in common if two sub-register +// indices overlap in some register. +// +// Conservatively share a lane mask bit if two sub-register indices overlap in +// some registers, but not in others. That shouldn't happen a lot. +void CodeGenRegBank::computeSubRegIndexLaneMasks() { + // First assign individual bits to all the leaf indices. + unsigned Bit = 0; + // Determine mask of lanes that cover their registers. + CoveringLanes = ~0u; + for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { + CodeGenSubRegIndex *Idx = SubRegIndices[i]; + if (Idx->getComposites().empty()) { + Idx->LaneMask = 1u << Bit; + // Share bit 31 in the unlikely case there are more than 32 leafs. + // + // Sharing bits is harmless; it allows graceful degradation in targets + // with more than 32 vector lanes. They simply get a limited resolution + // view of lanes beyond the 32nd. + // + // See also the comment for getSubRegIndexLaneMask(). + if (Bit < 31) + ++Bit; + else + // Once bit 31 is shared among multiple leafs, the 'lane' it represents + // is no longer covering its registers. + CoveringLanes &= ~(1u << Bit); + } else { + Idx->LaneMask = 0; + } + } - // We don't care about the difference between (Idx1, Idx2) -> Idx2 and invalid - // compositions, so remove any mappings of that form. - for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) - SubRegIndices[i]->cleanComposites(); + // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented + // by the sub-register graph? This doesn't occur in any known targets. + + // Inherit lanes from composites. + for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { + unsigned Mask = SubRegIndices[i]->computeLaneMask(); + // If some super-registers without CoveredBySubRegs use this index, we can + // no longer assume that the lanes are covering their registers. + if (!SubRegIndices[i]->AllSuperRegsCovered) + CoveringLanes &= ~Mask; + } } namespace { @@ -1214,7 +1320,7 @@ static void computeUberWeights(std::vector &UberSets, Reg = UnitI.getReg(); Weight = 0; } - unsigned UWeight = RegBank.getRegUnitWeight(*UnitI); + unsigned UWeight = RegBank.getRegUnit(*UnitI).Weight; if (!UWeight) { UWeight = 1; RegBank.increaseRegUnitWeight(*UnitI, UWeight); @@ -1309,11 +1415,6 @@ static bool normalizeWeight(CodeGenRegister *Reg, // The goal is that two registers in the same class will have the same weight, // where each register's weight is defined as sum of its units' weights. void CodeGenRegBank::computeRegUnitWeights() { - assert(RegUnitWeights.empty() && "Only initialize RegUnitWeights once"); - - // Only allocatable units will be initialized to nonzero weight. - RegUnitWeights.resize(NumRegUnits); - std::vector UberSets; std::vector RegSets(Registers.size()); computeUberSets(UberSets, RegSets, *this); @@ -1488,81 +1589,40 @@ void CodeGenRegBank::computeRegUnitSets() { } assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass"); } -} -// Compute sets of overlapping registers. -// -// The standard set is all super-registers and all sub-registers, but the -// target description can add arbitrary overlapping registers via the 'Aliases' -// field. This complicates things, but we can compute overlapping sets using -// the following rules: -// -// 1. The relation overlap(A, B) is reflexive and symmetric but not transitive. -// -// 2. overlap(A, B) implies overlap(A, S) for all S in supers(B). -// -// Alternatively: -// -// overlap(A, B) iff there exists: -// A' in { A, subregs(A) } and B' in { B, subregs(B) } such that: -// A' = B' or A' in aliases(B') or B' in aliases(A'). -// -// Here subregs(A) is the full flattened sub-register set returned by -// A.getSubRegs() while aliases(A) is simply the special 'Aliases' field in the -// description of register A. -// -// This also implies that registers with a common sub-register are considered -// overlapping. This can happen when forming register pairs: -// -// P0 = (R0, R1) -// P1 = (R1, R2) -// P2 = (R2, R3) -// -// In this case, we will infer an overlap between P0 and P1 because of the -// shared sub-register R1. There is no overlap between P0 and P2. -// -void CodeGenRegBank:: -computeOverlaps(std::map &Map) { - assert(Map.empty()); - - // Collect overlaps that don't follow from rule 2. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - CodeGenRegister *Reg = Registers[i]; - CodeGenRegister::Set &Overlaps = Map[Reg]; - - // Reg overlaps itself. - Overlaps.insert(Reg); - - // All super-registers overlap. - const CodeGenRegister::SuperRegList &Supers = Reg->getSuperRegs(); - Overlaps.insert(Supers.begin(), Supers.end()); - - // Form symmetrical relations from the special Aliases[] lists. - ArrayRef RegList = Reg->getExplicitAliases(); - for (unsigned i2 = 0, e2 = RegList.size(); i2 != e2; ++i2) { - CodeGenRegister *Reg2 = RegList[i2]; - const CodeGenRegister::SuperRegList &Supers2 = Reg2->getSuperRegs(); - // Reg overlaps Reg2 which implies it overlaps supers(Reg2). - Overlaps.insert(Reg2); - Overlaps.insert(Supers2.begin(), Supers2.end()); + // For each register unit, ensure that we have the list of UnitSets that + // contain the unit. Normally, this matches an existing list of UnitSets for a + // register class. If not, we create a new entry in RegClassUnitSets as a + // "fake" register class. + for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits; + UnitIdx < UnitEnd; ++UnitIdx) { + std::vector RUSets; + for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) { + RegUnitSet &RUSet = RegUnitSets[i]; + if (std::find(RUSet.Units.begin(), RUSet.Units.end(), UnitIdx) + == RUSet.Units.end()) + continue; + RUSets.push_back(i); } - } - - // Apply rule 2. and inherit all sub-register overlaps. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - CodeGenRegister *Reg = Registers[i]; - CodeGenRegister::Set &Overlaps = Map[Reg]; - const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs(); - for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM.begin(), - e2 = SRM.end(); i2 != e2; ++i2) { - CodeGenRegister::Set &Overlaps2 = Map[i2->second]; - Overlaps.insert(Overlaps2.begin(), Overlaps2.end()); + unsigned RCUnitSetsIdx = 0; + for (unsigned e = RegClassUnitSets.size(); + RCUnitSetsIdx != e; ++RCUnitSetsIdx) { + if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) { + break; + } + } + RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx; + if (RCUnitSetsIdx == RegClassUnitSets.size()) { + // Create a new list of UnitSets as a "fake" register class. + RegClassUnitSets.resize(RCUnitSetsIdx + 1); + RegClassUnitSets[RCUnitSetsIdx].swap(RUSets); } } } void CodeGenRegBank::computeDerivedInfo() { computeComposites(); + computeSubRegIndexLaneMasks(); // Compute a weight for each register unit created during getSubRegs. // This may create adopted register units (with unit # >= NumNativeRegUnits).