+// 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.
+ const ArrayRef<CodeGenRegisterClass*> &RegClasses = getRegClasses();
+ unsigned NumRegClasses = RegClasses.size();
+ for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) {
+ if (!RegClasses[RCIdx]->Allocatable)
+ continue;
+
+ // Speculatively grow the RegUnitSets to hold the new set.
+ RegUnitSets.resize(RegUnitSets.size() + 1);
+ RegUnitSets.back().Name = RegClasses[RCIdx]->getName();
+
+ // Compute a sorted list of units in this class.
+ RegClasses[RCIdx]->buildRegUnitSet(RegUnitSets.back().Units);
+
+ // Find an existing RegUnitSet.
+ std::vector<RegUnitSet>::const_iterator SetI =
+ findRegUnitSet(RegUnitSets, RegUnitSets.back());
+ if (SetI != llvm::prior(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
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].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
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].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 != llvm::prior(RegUnitSets.end()))
+ RegUnitSets.pop_back();
+ else {
+ DEBUG(dbgs() << "UnitSet " << RegUnitSets.size()-1
+ << " " << RegUnitSets.back().Name << ":";
+ ArrayRef<unsigned> Units = RegUnitSets.back().Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].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
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName();
+ dbgs() << "\n";
+ });
+
+ // For each register class, list the UnitSets that are supersets.
+ RegClassUnitSets.resize(NumRegClasses);
+ for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) {
+ if (!RegClasses[RCIdx]->Allocatable)
+ continue;
+
+ // Recompute the sorted list of units in this class.
+ std::vector<unsigned> RCRegUnits;
+ RegClasses[RCIdx]->buildRegUnitSet(RCRegUnits);
+
+ // Don't increase pressure for unallocatable regclasses.
+ if (RCRegUnits.empty())
+ continue;
+
+ DEBUG(dbgs() << "RC " << RegClasses[RCIdx]->getName() << " Units: \n";
+ for (unsigned i = 0, e = RCRegUnits.size(); i < e; ++i)
+ dbgs() << RegUnits[RCRegUnits[i]].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);
+ }
+ }
+}
+
+struct LessUnits {
+ const CodeGenRegBank &RegBank;
+ LessUnits(const CodeGenRegBank &RB): RegBank(RB) {}
+
+ bool operator()(unsigned ID1, unsigned ID2) {
+ return RegBank.getRegPressureSet(ID1).Units.size()
+ < RegBank.getRegPressureSet(ID2).Units.size();
+ }
+};
+
+void CodeGenRegBank::computeDerivedInfo() {
+ computeComposites();
+ computeSubRegIndexLaneMasks();
+
+ // 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();
+
+ // 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(),
+ LessUnits(*this));
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
+ RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
+ }
+}
+