+// 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;
+ }
+}
+