+// Recompute each UberSet weight after changing unit weights.
+static void computeUberWeights(std::vector<UberRegSet> &UberSets,
+ CodeGenRegBank &RegBank) {
+ // Skip the first unallocatable set.
+ for (std::vector<UberRegSet>::iterator I = std::next(UberSets.begin()),
+ E = UberSets.end(); I != E; ++I) {
+
+ // Initialize all unit weights in this set, and remember the max units/reg.
+ const CodeGenRegister *Reg = nullptr;
+ unsigned MaxWeight = 0, Weight = 0;
+ for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) {
+ if (Reg != UnitI.getReg()) {
+ if (Weight > MaxWeight)
+ MaxWeight = Weight;
+ Reg = UnitI.getReg();
+ Weight = 0;
+ }
+ unsigned UWeight = RegBank.getRegUnit(*UnitI).Weight;
+ if (!UWeight) {
+ UWeight = 1;
+ RegBank.increaseRegUnitWeight(*UnitI, UWeight);
+ }
+ Weight += UWeight;
+ }
+ if (Weight > MaxWeight)
+ MaxWeight = Weight;
+ if (I->Weight != MaxWeight) {
+ DEBUG(
+ dbgs() << "UberSet " << I - UberSets.begin() << " Weight " << MaxWeight;
+ for (auto &Unit : I->Regs)
+ dbgs() << " " << Unit->getName();
+ dbgs() << "\n");
+ // Update the set weight.
+ I->Weight = MaxWeight;
+ }
+
+ // Find singular determinants.
+ for (const auto R : I->Regs) {
+ if (R->getRegUnits().count() == 1 && R->getWeight(RegBank) == I->Weight) {
+ I->SingularDeterminants |= R->getRegUnits();
+ }
+ }
+ }
+}
+
+// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
+// a register and its subregisters so that they have the same weight as their
+// UberSet. Self-recursion processes the subregister tree in postorder so
+// subregisters are normalized first.
+//
+// Side effects:
+// - creates new adopted register units
+// - causes superregisters to inherit adopted units
+// - increases the weight of "singular" units
+// - induces recomputation of UberWeights.
+static bool normalizeWeight(CodeGenRegister *Reg,
+ std::vector<UberRegSet> &UberSets,
+ std::vector<UberRegSet*> &RegSets,
+ SparseBitVector<> &NormalRegs,
+ CodeGenRegister::RegUnitList &NormalUnits,
+ CodeGenRegBank &RegBank) {
+ if (NormalRegs.test(Reg->EnumValue))
+ return false;
+ NormalRegs.set(Reg->EnumValue);
+
+ bool Changed = false;
+ const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
+ for (CodeGenRegister::SubRegMap::const_iterator SRI = SRM.begin(),
+ SRE = SRM.end(); SRI != SRE; ++SRI) {
+ if (SRI->second == Reg)
+ continue; // self-cycles happen
+
+ Changed |= normalizeWeight(SRI->second, UberSets, RegSets,
+ NormalRegs, NormalUnits, RegBank);
+ }
+ // Postorder register normalization.
+
+ // Inherit register units newly adopted by subregisters.
+ if (Reg->inheritRegUnits(RegBank))
+ computeUberWeights(UberSets, RegBank);
+
+ // Check if this register is too skinny for its UberRegSet.
+ UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)];
+
+ unsigned RegWeight = Reg->getWeight(RegBank);
+ if (UberSet->Weight > RegWeight) {
+ // A register unit's weight can be adjusted only if it is the singular unit
+ // for this register, has not been used to normalize a subregister's set,
+ // and has not already been used to singularly determine this UberRegSet.
+ unsigned AdjustUnit = *Reg->getRegUnits().begin();
+ if (Reg->getRegUnits().count() != 1
+ || hasRegUnit(NormalUnits, AdjustUnit)
+ || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) {
+ // We don't have an adjustable unit, so adopt a new one.
+ AdjustUnit = RegBank.newRegUnit(UberSet->Weight - RegWeight);
+ Reg->adoptRegUnit(AdjustUnit);
+ // Adopting a unit does not immediately require recomputing set weights.
+ }
+ else {
+ // Adjust the existing single unit.
+ RegBank.increaseRegUnitWeight(AdjustUnit, UberSet->Weight - RegWeight);
+ // The unit may be shared among sets and registers within this set.
+ computeUberWeights(UberSets, RegBank);
+ }
+ Changed = true;
+ }
+
+ // Mark these units normalized so superregisters can't change their weights.
+ NormalUnits |= Reg->getRegUnits();
+
+ return Changed;
+}
+
+// Compute a weight for each register unit created during getSubRegs.
+//
+// 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() {
+ std::vector<UberRegSet> UberSets;
+ std::vector<UberRegSet*> RegSets(Registers.size());
+ computeUberSets(UberSets, RegSets, *this);
+ // UberSets and RegSets are now immutable.
+
+ computeUberWeights(UberSets, *this);
+
+ // Iterate over each Register, normalizing the unit weights until reaching
+ // a fix point.
+ unsigned NumIters = 0;
+ for (bool Changed = true; Changed; ++NumIters) {
+ assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights");
+ Changed = false;
+ for (auto &Reg : Registers) {
+ CodeGenRegister::RegUnitList NormalUnits;
+ SparseBitVector<> NormalRegs;
+ Changed |= normalizeWeight(&Reg, UberSets, RegSets, NormalRegs,
+ NormalUnits, *this);
+ }
+ }
+}
+
+// Find a set in UniqueSets with the same elements as Set.
+// Return an iterator into UniqueSets.
+static std::vector<RegUnitSet>::const_iterator
+findRegUnitSet(const std::vector<RegUnitSet> &UniqueSets,
+ const RegUnitSet &Set) {
+ std::vector<RegUnitSet>::const_iterator
+ I = UniqueSets.begin(), E = UniqueSets.end();
+ for(;I != E; ++I) {
+ if (I->Units == Set.Units)
+ break;
+ }
+ return I;
+}
+
+// Return true if the RUSubSet is a subset of RUSuperSet.
+static bool isRegUnitSubSet(const std::vector<unsigned> &RUSubSet,
+ const std::vector<unsigned> &RUSuperSet) {
+ return std::includes(RUSuperSet.begin(), RUSuperSet.end(),
+ RUSubSet.begin(), RUSubSet.end());
+}
+
+/// Iteratively prune unit sets. Prune subsets that are close to the superset,
+/// but with one or two registers removed. We occasionally have registers like
+/// APSR and PC thrown in with the general registers. We also see many
+/// special-purpose register subsets, such as tail-call and Thumb
+/// encodings. Generating all possible overlapping sets is combinatorial and
+/// overkill for modeling pressure. Ideally we could fix this statically in
+/// tablegen by (1) having the target define register classes that only include
+/// the allocatable registers and marking other classes as non-allocatable and
+/// (2) having a way to mark special purpose classes as "don't-care" classes for
+/// the purpose of pressure. However, we make an attempt to handle targets that
+/// are not nicely defined by merging nearly identical register unit sets
+/// statically. This generates smaller tables. Then, dynamically, we adjust the
+/// set limit by filtering the reserved registers.
+///
+/// Merge sets only if the units have the same weight. For example, on ARM,
+/// Q-tuples with ssub index 0 include all S regs but also include D16+. We
+/// should not expand the S set to include D regs.
+void CodeGenRegBank::pruneUnitSets() {
+ assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets");
+
+ // Form an equivalence class of UnitSets with no significant difference.
+ std::vector<unsigned> SuperSetIDs;
+ for (unsigned SubIdx = 0, EndIdx = RegUnitSets.size();
+ SubIdx != EndIdx; ++SubIdx) {
+ const RegUnitSet &SubSet = RegUnitSets[SubIdx];
+ unsigned SuperIdx = 0;
+ for (; SuperIdx != EndIdx; ++SuperIdx) {
+ if (SuperIdx == SubIdx)
+ continue;
+
+ unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight;
+ const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
+ if (isRegUnitSubSet(SubSet.Units, SuperSet.Units)
+ && (SubSet.Units.size() + 3 > SuperSet.Units.size())
+ && UnitWeight == RegUnits[SuperSet.Units[0]].Weight
+ && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) {
+ DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx
+ << "\n");
+ break;
+ }
+ }
+ if (SuperIdx == EndIdx)
+ SuperSetIDs.push_back(SubIdx);
+ }
+ // Populate PrunedUnitSets with each equivalence class's superset.
+ std::vector<RegUnitSet> PrunedUnitSets(SuperSetIDs.size());
+ for (unsigned i = 0, e = SuperSetIDs.size(); i != e; ++i) {
+ unsigned SuperIdx = SuperSetIDs[i];
+ PrunedUnitSets[i].Name = RegUnitSets[SuperIdx].Name;
+ PrunedUnitSets[i].Units.swap(RegUnitSets[SuperIdx].Units);
+ }
+ RegUnitSets.swap(PrunedUnitSets);
+}
+
+// Create a RegUnitSet for each RegClass that contains all units in the class
+// including adopted units that are necessary to model register pressure. Then
+// iteratively compute RegUnitSets such that the union of any two overlapping
+// RegUnitSets is repreresented.
+//
+// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
+// RegUnitSet that is a superset of that RegUnitClass.
+void CodeGenRegBank::computeRegUnitSets() {
+ assert(RegUnitSets.empty() && "dirty RegUnitSets");
+
+ // Compute a unique RegUnitSet for each RegClass.
+ auto &RegClasses = getRegClasses();
+ for (auto &RC : RegClasses) {
+ if (!RC.Allocatable)
+ continue;
+
+ // Speculatively grow the RegUnitSets to hold the new set.
+ RegUnitSets.resize(RegUnitSets.size() + 1);
+ RegUnitSets.back().Name = RC.getName();
+
+ // Compute a sorted list of units in this class.
+ RC.buildRegUnitSet(RegUnitSets.back().Units);
+
+ // Find an existing RegUnitSet.
+ std::vector<RegUnitSet>::const_iterator SetI =
+ findRegUnitSet(RegUnitSets, RegUnitSets.back());
+ if (SetI != std::prev(RegUnitSets.end()))
+ RegUnitSets.pop_back();
+ }
+
+ DEBUG(dbgs() << "\nBefore pruning:\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ for (auto &U : RegUnitSets[USIdx].Units)
+ dbgs() << " " << RegUnits[U].Roots[0]->getName();
+ dbgs() << "\n";
+ });
+
+ // Iteratively prune unit sets.
+ pruneUnitSets();
+
+ DEBUG(dbgs() << "\nBefore union:\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ for (auto &U : RegUnitSets[USIdx].Units)
+ dbgs() << " " << RegUnits[U].Roots[0]->getName();
+ dbgs() << "\n";
+ }
+ dbgs() << "\nUnion sets:\n");
+
+ // Iterate over all unit sets, including new ones added by this loop.
+ unsigned NumRegUnitSubSets = RegUnitSets.size();
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
+ // In theory, this is combinatorial. In practice, it needs to be bounded
+ // by a small number of sets for regpressure to be efficient.
+ // If the assert is hit, we need to implement pruning.
+ assert(Idx < (2*NumRegUnitSubSets) && "runaway unit set inference");
+
+ // Compare new sets with all original classes.
+ for (unsigned SearchIdx = (Idx >= NumRegUnitSubSets) ? 0 : Idx+1;
+ SearchIdx != EndIdx; ++SearchIdx) {
+ std::set<unsigned> Intersection;
+ std::set_intersection(RegUnitSets[Idx].Units.begin(),
+ RegUnitSets[Idx].Units.end(),
+ RegUnitSets[SearchIdx].Units.begin(),
+ RegUnitSets[SearchIdx].Units.end(),
+ std::inserter(Intersection, Intersection.begin()));
+ if (Intersection.empty())
+ continue;
+
+ // Speculatively grow the RegUnitSets to hold the new set.
+ RegUnitSets.resize(RegUnitSets.size() + 1);
+ RegUnitSets.back().Name =
+ RegUnitSets[Idx].Name + "+" + RegUnitSets[SearchIdx].Name;
+
+ std::set_union(RegUnitSets[Idx].Units.begin(),
+ RegUnitSets[Idx].Units.end(),
+ RegUnitSets[SearchIdx].Units.begin(),
+ RegUnitSets[SearchIdx].Units.end(),
+ std::inserter(RegUnitSets.back().Units,
+ RegUnitSets.back().Units.begin()));
+
+ // Find an existing RegUnitSet, or add the union to the unique sets.
+ std::vector<RegUnitSet>::const_iterator SetI =
+ findRegUnitSet(RegUnitSets, RegUnitSets.back());
+ if (SetI != std::prev(RegUnitSets.end()))
+ RegUnitSets.pop_back();
+ else {
+ DEBUG(dbgs() << "UnitSet " << RegUnitSets.size()-1
+ << " " << RegUnitSets.back().Name << ":";
+ for (auto &U : RegUnitSets.back().Units)
+ dbgs() << " " << RegUnits[U].Roots[0]->getName();
+ dbgs() << "\n";);
+ }
+ }
+ }
+
+ // Iteratively prune unit sets after inferring supersets.
+ pruneUnitSets();
+
+ DEBUG(dbgs() << "\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ for (auto &U : RegUnitSets[USIdx].Units)
+ dbgs() << " " << RegUnits[U].Roots[0]->getName();
+ dbgs() << "\n";
+ });
+
+ // For each register class, list the UnitSets that are supersets.
+ RegClassUnitSets.resize(RegClasses.size());
+ int RCIdx = -1;
+ for (auto &RC : RegClasses) {
+ ++RCIdx;
+ if (!RC.Allocatable)
+ continue;
+
+ // Recompute the sorted list of units in this class.
+ std::vector<unsigned> RCRegUnits;
+ RC.buildRegUnitSet(RCRegUnits);
+
+ // Don't increase pressure for unallocatable regclasses.
+ if (RCRegUnits.empty())
+ continue;
+
+ DEBUG(dbgs() << "RC " << RC.getName() << " Units: \n";
+ for (auto &U : RCRegUnits)
+ dbgs() << RegUnits[U].getRoots()[0]->getName() << " ";
+ dbgs() << "\n UnitSetIDs:");
+
+ // Find all supersets.
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx != USEnd; ++USIdx) {
+ if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) {
+ DEBUG(dbgs() << " " << USIdx);
+ RegClassUnitSets[RCIdx].push_back(USIdx);
+ }
+ }
+ DEBUG(dbgs() << "\n");
+ assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass");
+ }
+
+ // 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<unsigned> 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);
+ }
+ 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::computeRegUnitLaneMasks() {
+ for (auto &Register : Registers) {
+ // Create an initial lane mask for all register units.
+ const auto &RegUnits = Register.getRegUnits();
+ CodeGenRegister::RegUnitLaneMaskList RegUnitLaneMasks(RegUnits.count(), 0);
+ // Iterate through SubRegisters.
+ typedef CodeGenRegister::SubRegMap SubRegMap;
+ const SubRegMap &SubRegs = Register.getSubRegs();
+ for (SubRegMap::const_iterator S = SubRegs.begin(),
+ SE = SubRegs.end(); S != SE; ++S) {
+ CodeGenRegister *SubReg = S->second;
+ // Ignore non-leaf subregisters, their lane masks are fully covered by
+ // the leaf subregisters anyway.
+ if (SubReg->getSubRegs().size() != 0)
+ continue;
+ CodeGenSubRegIndex *SubRegIndex = S->first;
+ const CodeGenRegister *SubRegister = S->second;
+ unsigned LaneMask = SubRegIndex->LaneMask;
+ // Distribute LaneMask to Register Units touched.
+ for (unsigned SUI : SubRegister->getRegUnits()) {
+ bool Found = false;
+ unsigned u = 0;
+ for (unsigned RU : RegUnits) {
+ if (SUI == RU) {
+ RegUnitLaneMasks[u] |= LaneMask;
+ assert(!Found);
+ Found = true;
+ }
+ ++u;
+ }
+ (void)Found;
+ assert(Found);
+ }
+ }
+ Register.setRegUnitLaneMasks(RegUnitLaneMasks);
+ }
+}
+
+void CodeGenRegBank::computeDerivedInfo() {
+ computeComposites();
+ computeSubRegLaneMasks();
+
+ // Compute a weight for each register unit created during getSubRegs.
+ // This may create adopted register units (with unit # >= NumNativeRegUnits).
+ computeRegUnitWeights();
+
+ // Compute a unique set of RegUnitSets. One for each RegClass and inferred
+ // supersets for the union of overlapping sets.
+ computeRegUnitSets();
+
+ computeRegUnitLaneMasks();
+
+ // Compute register class HasDisjunctSubRegs flag.
+ for (CodeGenRegisterClass &RC : RegClasses) {
+ RC.HasDisjunctSubRegs = false;
+ for (const CodeGenRegister *Reg : RC.getMembers())
+ RC.HasDisjunctSubRegs |= Reg->HasDisjunctSubRegs;
+ }
+
+ // Get the weight of each set.
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
+ RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units);
+
+ // Find the order of each set.
+ RegUnitSetOrder.reserve(RegUnitSets.size());
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
+ RegUnitSetOrder.push_back(Idx);
+
+ std::stable_sort(RegUnitSetOrder.begin(), RegUnitSetOrder.end(),
+ [this](unsigned ID1, unsigned ID2) {
+ return getRegPressureSet(ID1).Units.size() <
+ getRegPressureSet(ID2).Units.size();
+ });
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
+ RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
+ }
+}
+
+//
+// Synthesize missing register class intersections.
+//
+// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X)
+// returns a maximal register class for all X.
+//
+void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) {
+ assert(!RegClasses.empty());
+ // Stash the iterator to the last element so that this loop doesn't visit
+ // elements added by the getOrCreateSubClass call within it.
+ for (auto I = RegClasses.begin(), E = std::prev(RegClasses.end());
+ I != std::next(E); ++I) {
+ CodeGenRegisterClass *RC1 = RC;
+ CodeGenRegisterClass *RC2 = &*I;
+ if (RC1 == RC2)
+ continue;
+
+ // Compute the set intersection of RC1 and RC2.
+ const CodeGenRegister::Vec &Memb1 = RC1->getMembers();
+ const CodeGenRegister::Vec &Memb2 = RC2->getMembers();
+ CodeGenRegister::Vec Intersection;
+ std::set_intersection(
+ Memb1.begin(), Memb1.end(), Memb2.begin(), Memb2.end(),
+ std::inserter(Intersection, Intersection.begin()), deref<llvm::less>());
+
+ // Skip disjoint class pairs.
+ if (Intersection.empty())
+ continue;
+
+ // If RC1 and RC2 have different spill sizes or alignments, use the
+ // larger size for sub-classing. If they are equal, prefer RC1.
+ if (RC2->SpillSize > RC1->SpillSize ||
+ (RC2->SpillSize == RC1->SpillSize &&
+ RC2->SpillAlignment > RC1->SpillAlignment))
+ std::swap(RC1, RC2);
+
+ getOrCreateSubClass(RC1, &Intersection,
+ RC1->getName() + "_and_" + RC2->getName());
+ }
+}
+
+//
+// Synthesize missing sub-classes for getSubClassWithSubReg().
+//
+// Make sure that the set of registers in RC with a given SubIdx sub-register
+// form a register class. Update RC->SubClassWithSubReg.
+//
+void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
+ // Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
+ typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Vec,
+ deref<llvm::less>> SubReg2SetMap;
+
+ // Compute the set of registers supporting each SubRegIndex.
+ SubReg2SetMap SRSets;
+ for (const auto R : RC->getMembers()) {
+ const CodeGenRegister::SubRegMap &SRM = R->getSubRegs();
+ for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(),
+ E = SRM.end(); I != E; ++I)
+ SRSets[I->first].push_back(R);
+ }
+
+ for (auto I : SRSets)
+ sortAndUniqueRegisters(I.second);
+
+ // Find matching classes for all SRSets entries. Iterate in SubRegIndex
+ // numerical order to visit synthetic indices last.
+ for (const auto &SubIdx : SubRegIndices) {
+ SubReg2SetMap::const_iterator I = SRSets.find(&SubIdx);
+ // Unsupported SubRegIndex. Skip it.
+ if (I == SRSets.end())
+ continue;
+ // In most cases, all RC registers support the SubRegIndex.
+ if (I->second.size() == RC->getMembers().size()) {
+ RC->setSubClassWithSubReg(&SubIdx, RC);
+ continue;
+ }
+ // This is a real subset. See if we have a matching class.
+ CodeGenRegisterClass *SubRC =
+ getOrCreateSubClass(RC, &I->second,
+ RC->getName() + "_with_" + I->first->getName());
+ RC->setSubClassWithSubReg(&SubIdx, SubRC);
+ }
+}
+
+//
+// Synthesize missing sub-classes of RC for getMatchingSuperRegClass().
+//
+// Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X)
+// has a maximal result for any SubIdx and any X >= FirstSubRegRC.
+//
+
+void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
+ std::list<CodeGenRegisterClass>::iterator FirstSubRegRC) {
+ SmallVector<std::pair<const CodeGenRegister*,
+ const CodeGenRegister*>, 16> SSPairs;
+ BitVector TopoSigs(getNumTopoSigs());
+
+ // Iterate in SubRegIndex numerical order to visit synthetic indices last.
+ for (auto &SubIdx : SubRegIndices) {
+ // Skip indexes that aren't fully supported by RC's registers. This was
+ // computed by inferSubClassWithSubReg() above which should have been
+ // called first.
+ if (RC->getSubClassWithSubReg(&SubIdx) != RC)
+ continue;
+
+ // Build list of (Super, Sub) pairs for this SubIdx.
+ SSPairs.clear();
+ TopoSigs.reset();
+ for (const auto Super : RC->getMembers()) {
+ const CodeGenRegister *Sub = Super->getSubRegs().find(&SubIdx)->second;
+ assert(Sub && "Missing sub-register");
+ SSPairs.push_back(std::make_pair(Super, Sub));
+ TopoSigs.set(Sub->getTopoSig());
+ }
+
+ // Iterate over sub-register class candidates. Ignore classes created by
+ // this loop. They will never be useful.
+ // Store an iterator to the last element (not end) so that this loop doesn't
+ // visit newly inserted elements.
+ assert(!RegClasses.empty());
+ for (auto I = FirstSubRegRC, E = std::prev(RegClasses.end());
+ I != std::next(E); ++I) {
+ CodeGenRegisterClass &SubRC = *I;
+ // Topological shortcut: SubRC members have the wrong shape.
+ if (!TopoSigs.anyCommon(SubRC.getTopoSigs()))
+ continue;
+ // Compute the subset of RC that maps into SubRC.
+ CodeGenRegister::Vec SubSetVec;
+ for (unsigned i = 0, e = SSPairs.size(); i != e; ++i)
+ if (SubRC.contains(SSPairs[i].second))
+ SubSetVec.push_back(SSPairs[i].first);
+
+ if (SubSetVec.empty())
+ continue;
+
+ // RC injects completely into SubRC.
+ sortAndUniqueRegisters(SubSetVec);
+ if (SubSetVec.size() == SSPairs.size()) {
+ SubRC.addSuperRegClass(&SubIdx, RC);
+ continue;
+ }
+
+ // Only a subset of RC maps into SubRC. Make sure it is represented by a
+ // class.
+ getOrCreateSubClass(RC, &SubSetVec, RC->getName() + "_with_" +
+ SubIdx.getName() + "_in_" +
+ SubRC.getName());
+ }
+ }
+}
+
+
+//
+// Infer missing register classes.
+//
+void CodeGenRegBank::computeInferredRegisterClasses() {
+ assert(!RegClasses.empty());
+ // When this function is called, the register classes have not been sorted
+ // and assigned EnumValues yet. That means getSubClasses(),
+ // getSuperClasses(), and hasSubClass() functions are defunct.
+
+ // Use one-before-the-end so it doesn't move forward when new elements are
+ // added.
+ auto FirstNewRC = std::prev(RegClasses.end());
+
+ // Visit all register classes, including the ones being added by the loop.
+ // Watch out for iterator invalidation here.
+ for (auto I = RegClasses.begin(), E = RegClasses.end(); I != E; ++I) {
+ CodeGenRegisterClass *RC = &*I;
+
+ // Synthesize answers for getSubClassWithSubReg().
+ inferSubClassWithSubReg(RC);
+
+ // Synthesize answers for getCommonSubClass().
+ inferCommonSubClass(RC);
+
+ // Synthesize answers for getMatchingSuperRegClass().
+ inferMatchingSuperRegClass(RC);
+
+ // New register classes are created while this loop is running, and we need
+ // to visit all of them. I particular, inferMatchingSuperRegClass needs
+ // to match old super-register classes with sub-register classes created
+ // after inferMatchingSuperRegClass was called. At this point,
+ // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC =
+ // [0..FirstNewRC). We need to cover SubRC = [FirstNewRC..rci].
+ if (I == FirstNewRC) {
+ auto NextNewRC = std::prev(RegClasses.end());
+ for (auto I2 = RegClasses.begin(), E2 = std::next(FirstNewRC); I2 != E2;
+ ++I2)
+ inferMatchingSuperRegClass(&*I2, E2);
+ FirstNewRC = NextNewRC;
+ }
+ }
+}
+
+/// getRegisterClassForRegister - Find the register class that contains the
+/// specified physical register. If the register is not in a register class,
+/// return null. If the register is in multiple classes, and the classes have a
+/// superset-subset relationship and the same set of types, return the
+/// superclass. Otherwise return null.
+const CodeGenRegisterClass*
+CodeGenRegBank::getRegClassForRegister(Record *R) {
+ const CodeGenRegister *Reg = getReg(R);
+ const CodeGenRegisterClass *FoundRC = nullptr;
+ for (const auto &RC : getRegClasses()) {
+ if (!RC.contains(Reg))
+ continue;
+
+ // If this is the first class that contains the register,
+ // make a note of it and go on to the next class.
+ if (!FoundRC) {
+ FoundRC = &RC;
+ continue;
+ }
+
+ // If a register's classes have different types, return null.
+ if (RC.getValueTypes() != FoundRC->getValueTypes())
+ return nullptr;
+
+ // Check to see if the previously found class that contains
+ // the register is a subclass of the current class. If so,
+ // prefer the superclass.
+ if (RC.hasSubClass(FoundRC)) {
+ FoundRC = &RC;
+ continue;
+ }
+
+ // Check to see if the previously found class that contains
+ // the register is a superclass of the current class. If so,
+ // prefer the superclass.
+ if (FoundRC->hasSubClass(&RC))
+ continue;
+
+ // Multiple classes, and neither is a superclass of the other.
+ // Return null.
+ return nullptr;
+ }
+ return FoundRC;
+}
+
+BitVector CodeGenRegBank::computeCoveredRegisters(ArrayRef<Record*> Regs) {
+ SetVector<const CodeGenRegister*> Set;
+
+ // First add Regs with all sub-registers.
+ for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+ CodeGenRegister *Reg = getReg(Regs[i]);
+ if (Set.insert(Reg))
+ // Reg is new, add all sub-registers.
+ // The pre-ordering is not important here.
+ Reg->addSubRegsPreOrder(Set, *this);
+ }
+
+ // Second, find all super-registers that are completely covered by the set.
+ for (unsigned i = 0; i != Set.size(); ++i) {
+ const CodeGenRegister::SuperRegList &SR = Set[i]->getSuperRegs();
+ for (unsigned j = 0, e = SR.size(); j != e; ++j) {
+ const CodeGenRegister *Super = SR[j];
+ if (!Super->CoveredBySubRegs || Set.count(Super))
+ continue;
+ // This new super-register is covered by its sub-registers.
+ bool AllSubsInSet = true;
+ const CodeGenRegister::SubRegMap &SRM = Super->getSubRegs();
+ for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(),
+ E = SRM.end(); I != E; ++I)
+ if (!Set.count(I->second)) {
+ AllSubsInSet = false;
+ break;
+ }
+ // All sub-registers in Set, add Super as well.
+ // We will visit Super later to recheck its super-registers.
+ if (AllSubsInSet)
+ Set.insert(Super);
+ }
+ }
+
+ // Convert to BitVector.
+ BitVector BV(Registers.size() + 1);
+ for (unsigned i = 0, e = Set.size(); i != e; ++i)
+ BV.set(Set[i]->EnumValue);
+ return BV;
+}