Added register unit sets to the target description.

This is a new algorithm that finds sets of register units that can be
used to model registers pressure. This handles arbitrary, overlapping
register classes. Each register class is associated with a (small)
list of pressure sets. These are the dimensions of pressure affected
by the register class's liveness.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154374 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 292 insertions, 0 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index 5939804050..fc5c78019c 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -1118,6 +1118,169 @@ void CodeGenRegBank::computeRegUnitWeights() {
   }
 }
 
+// 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) {
+  for (RegUnitSet::iterator SubIdx = RUSubSet.begin(), EndIdx = RUSubSet.end(),
+         SearchIdx = RUSuperSet.begin(), SearchEnd = RUSuperSet.end();
+       SubIdx != EndIdx; ++SubIdx) {
+    SearchIdx = find(SearchIdx, SearchEnd, *SubIdx);
+    if (SearchIdx == SearchEnd)
+      return false;
+    ++SearchIdx;
+  }
+  return true;
+}
+
+// Iteratively prune unit sets.
+void CodeGenRegBank::pruneUnitSets() {
+  assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets");
+
+  // Form an equivalence class of UnitSets with no significant difference.
+  IntEqClasses RepUnitSetIDs(RegUnitSets.size());
+  for (unsigned SubIdx = 0, EndIdx = RegUnitSets.size();
+       SubIdx != EndIdx; ++SubIdx) {
+    const RegUnitSet &SubSet = RegUnitSets[SubIdx];
+    for (unsigned SuperIdx = 0; SuperIdx != EndIdx; ++SuperIdx) {
+      if (SuperIdx == SubIdx)
+        continue;
+
+      const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
+      if (isRegUnitSubSet(SubSet.Units, SuperSet.Units)
+          && (SubSet.Units.size() + 3 > SuperSet.Units.size())) {
+        RepUnitSetIDs.join(SubIdx, SuperIdx);
+      }
+    }
+  }
+  RepUnitSetIDs.compress();
+
+  // Populate PrunedUnitSets with each equivalence class's superset.
+  std::vector<RegUnitSet> PrunedUnitSets(RepUnitSetIDs.getNumClasses());
+  for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) {
+    RegUnitSet &SuperSet = PrunedUnitSets[RepUnitSetIDs[i]];
+    if (SuperSet.Units.size() < RegUnitSets[i].Units.size())
+      SuperSet = RegUnitSets[i];
+  }
+  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() {
+
+  // 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) {
+
+    // Compute a sorted list of units in this class.
+    std::vector<unsigned> RegUnits;
+    const CodeGenRegister::Set &Regs = RegClasses[RCIdx]->getMembers();
+    for (RegUnitIterator UnitI(Regs); UnitI.isValid(); ++UnitI)
+      RegUnits.push_back(*UnitI);
+    std::sort(RegUnits.begin(), RegUnits.end());
+
+    // Speculatively grow the RegUnitSets to hold the new set.
+    RegUnitSets.resize(RegUnitSets.size() + 1);
+    RegUnitSets.back().Name = RegClasses[RCIdx]->getName();
+    std::unique_copy(RegUnits.begin(), RegUnits.end(),
+                     std::back_inserter(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();
+  }
+
+  // Iteratively prune unit sets.
+  pruneUnitSets();
+
+  // 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 = (SearchIdx >= 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();
+    }
+  }
+
+  // Iteratively prune unit sets again after inferring supersets.
+  pruneUnitSets();
+
+  // For each register class, list the UnitSets that are supersets.
+  RegClassUnitSets.resize(NumRegClasses);
+  for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) {
+    // Recompute the sorted list of units in this class.
+    std::vector<unsigned> RegUnits;
+    const CodeGenRegister::Set &Regs = RegClasses[RCIdx]->getMembers();
+    for (RegUnitIterator UnitI(Regs); UnitI.isValid(); ++UnitI)
+      RegUnits.push_back(*UnitI);
+    std::sort(RegUnits.begin(), RegUnits.end());
+
+    // Don't increase pressure for unallocatable regclasses.
+    if (RegUnits.empty())
+      continue;
+
+    // Find all supersets.
+    for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+         USIdx != USEnd; ++USIdx) {
+      if (isRegUnitSubSet(RegUnits, RegUnitSets[USIdx].Units))
+        RegClassUnitSets[RCIdx].push_back(USIdx);
+    }
+  }
+}
+
 // Compute sets of overlapping registers.
 //
 // The standard set is all super-registers and all sub-registers, but the
@@ -1198,6 +1361,10 @@ void CodeGenRegBank::computeDerivedInfo() {
   // 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();
 }
 
 //
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index d22dced9d3..4b45467e9e 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -188,6 +188,7 @@ namespace llvm {
     //
     DenseMap<CodeGenSubRegIndex*,
              SmallPtrSet<CodeGenRegisterClass*, 8> > SuperRegClasses;
+
   public:
     unsigned EnumValue;
     std::string Namespace;
@@ -312,6 +313,14 @@ namespace llvm {
     static void computeSubClasses(CodeGenRegBank&);
   };
 
+  // Each RegUnitSet is a sorted vector with a name.
+  struct RegUnitSet {
+    typedef std::vector<unsigned>::const_iterator iterator;
+
+    std::string Name;
+    std::vector<unsigned> Units;
+  };
+
   // CodeGenRegBank - Represent a target's registers and the relations between
   // them.
   class CodeGenRegBank {
@@ -339,6 +348,15 @@ namespace llvm {
     typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap;
     RCKeyMap Key2RC;
 
+    // Remember each unique set of register units. Initially, this contains a
+    // unique set for each register class. Simliar sets are coalesced with
+    // pruneUnitSets and new supersets are inferred during computeRegUnitSets.
+    std::vector<RegUnitSet> RegUnitSets;
+
+    // Map RegisterClass index to the index of the RegUnitSet that contains the
+    // class's units and any inferred RegUnit supersets.
+    std::vector<std::vector<unsigned> > RegClassUnitSets;
+
     // Add RC to *2RC maps.
     void addToMaps(CodeGenRegisterClass*);
 
@@ -354,9 +372,15 @@ namespace llvm {
     void inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
                                     unsigned FirstSubRegRC = 0);
 
+    // Iteratively prune unit sets.
+    void pruneUnitSets();
+
     // Compute a weight for each register unit created during getSubRegs.
     void computeRegUnitWeights();
 
+    // Create a RegUnitSet for each RegClass and infer superclasses.
+    void computeRegUnitSets();
+
     // Populate the Composite map from sub-register relationships.
     void computeComposites();
 
@@ -392,12 +416,16 @@ namespace llvm {
     // to increase its pressure. Note that NumNativeRegUnits is not increased.
     unsigned newRegUnit(unsigned Weight) {
       if (!RegUnitWeights.empty()) {
+        assert(Weight && "should only add allocatable units");
         RegUnitWeights.resize(NumRegUnits+1);
         RegUnitWeights[NumRegUnits] = Weight;
       }
       return NumRegUnits++;
     }
 
+    // Native units are the singular unit of a leaf register. Register aliasing
+    // is completely characterized by native units. Adopted units exist to give
+    // register additional weight but don't affect aliasing.
     bool isNativeUnit(unsigned RUID) {
       return RUID < NumNativeRegUnits;
     }
@@ -416,14 +444,32 @@ namespace llvm {
     /// return the superclass.  Otherwise return null.
     const CodeGenRegisterClass* getRegClassForRegister(Record *R);
 
+    // Get a register unit's weight. Zero for unallocatable registers.
     unsigned getRegUnitWeight(unsigned RUID) const {
       return RegUnitWeights[RUID];
     }
 
+    // Increase a RegUnitWeight.
     void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {
       RegUnitWeights[RUID] += Inc;
     }
 
+    // Get the number of register pressure dimensions.
+    unsigned getNumRegPressureSets() const { return RegUnitSets.size(); }
+
+    // Get a set of register unit IDs for a given dimension of pressure.
+    RegUnitSet getRegPressureSet(unsigned Idx) const {
+      return RegUnitSets[Idx];
+    }
+
+    // Get a list of pressure set IDs for a register class. Liveness of a
+    // register in this class impacts each pressure set in this list by the
+    // weight of the register. An exact solution requires all registers in a
+    // class to have the same class, but it is not strictly guaranteed.
+    ArrayRef<unsigned> getRCPressureSetIDs(unsigned RCIdx) const {
+      return RegClassUnitSets[RCIdx];
+    }
+
     // Computed derived records such as missing sub-register indices.
     void computeDerivedInfo();
 
diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 0e273bc989..ac89e25843 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -118,6 +118,75 @@ RegisterInfoEmitter::runEnums(raw_ostream &OS,
   OS << "#endif // GET_REGINFO_ENUM\n\n";
 }
 
+void RegisterInfoEmitter::
+EmitRegUnitPressure(raw_ostream &OS, const CodeGenRegBank &RegBank,
+                    const std::string &ClassName) {
+  unsigned NumRCs = RegBank.getRegClasses().size();
+  unsigned NumSets = RegBank.getNumRegPressureSets();
+
+  OS << "/// Get the weight in units of pressure for this register class.\n"
+     << "unsigned " << ClassName << "::\n"
+     << "getRegClassWeight(const TargetRegisterClass *RC) const {\n"
+     << "  static const unsigned RCWeightTable[] = {\n";
+  for (unsigned i = 0, e = NumRCs; i != e; ++i) {
+    const CodeGenRegisterClass &RC = *RegBank.getRegClasses()[i];
+    const CodeGenRegister::Set &Regs = RC.getMembers();
+    if (Regs.empty())
+      OS << "    0";
+    else
+      OS << "    " << (*Regs.begin())->getWeight(RegBank);
+    OS << ",  \t// " << RC.getName() << "\n";
+  }
+  OS << "    0 };\n"
+     << "  return RCWeightTable[RC->getID()];\n"
+     << "}\n\n";
+
+  OS << "\n"
+     << "// Get the number of dimensions of register pressure.\n"
+     << "unsigned " << ClassName << "::getNumRegPressureSets() const {\n"
+     << "  return " << NumSets << ";\n}\n\n";
+
+  OS << "// Get the register unit pressure limit for this dimension.\n"
+     << "// This limit must be adjusted dynamically for reserved registers.\n"
+     << "unsigned " << ClassName << "::\n"
+     << "getRegPressureSetLimit(unsigned Idx) const {\n"
+     << "  static const unsigned PressureLimitTable[] = {\n";
+  for (unsigned i = 0; i < NumSets; ++i ) {
+    OS << "    " << RegBank.getRegPressureSet(i).Units.size()
+       << ",  \t// " << i << ": " << RegBank.getRegPressureSet(i).Name << "\n";
+  }
+  OS << "    0 };\n"
+     << "  return PressureLimitTable[Idx];\n"
+     << "}\n\n";
+
+  OS << "/// Get the dimensions of register pressure "
+     << "impacted by this register class.\n"
+     << "/// Returns a -1 terminated array of pressure set IDs\n"
+     << "const int* " << ClassName << "::\n"
+     << "getRegClassPressureSets(const TargetRegisterClass *RC) const {\n"
+     << "  static const int RCSetsTable[] = {\n    ";
+  std::vector<unsigned> RCSetStarts(NumRCs);
+  for (unsigned i = 0, StartIdx = 0, e = NumRCs; i != e; ++i) {
+    RCSetStarts[i] = StartIdx;
+    ArrayRef<unsigned> PSetIDs = RegBank.getRCPressureSetIDs(i);
+    for (ArrayRef<unsigned>::iterator PSetI = PSetIDs.begin(),
+           PSetE = PSetIDs.end(); PSetI != PSetE; ++PSetI) {
+      OS << *PSetI << ",  ";
+      ++StartIdx;
+    }
+    OS << "-1,  \t// " << RegBank.getRegClasses()[i]->getName() << "\n    ";
+    ++StartIdx;
+  }
+  OS << "-1 };\n";
+  OS << "  static const unsigned RCSetStartTable[] = {\n    ";
+  for (unsigned i = 0, e = NumRCs; i != e; ++i) {
+    OS << RCSetStarts[i] << ",";
+  }
+  OS << "0 };\n"
+     << "  unsigned SetListStart = RCSetStartTable[RC->getID()];\n"
+     << "  return &RCSetsTable[SetListStart];\n"
+     << "}\n\n";
+}
 
 void
 RegisterInfoEmitter::EmitRegMappingTables(raw_ostream &OS,
@@ -593,6 +662,11 @@ RegisterInfoEmitter::runTargetHeader(raw_ostream &OS, CodeGenTarget &Target,
      << "  const TargetRegisterClass *getMatchingSuperRegClass("
         "const TargetRegisterClass*, const TargetRegisterClass*, "
         "unsigned) const;\n"
+     << "  unsigned getRegClassWeight(const TargetRegisterClass *RC) const;\n"
+     << "  unsigned getNumRegPressureSets() const;\n"
+     << "  unsigned getRegPressureSetLimit(unsigned Idx) const;\n"
+     << "  const int *getRegClassPressureSets("
+     << "const TargetRegisterClass *RC) const;\n"
      << "};\n\n";
 
   ArrayRef<CodeGenRegisterClass*> RegisterClasses = RegBank.getRegClasses();
@@ -961,6 +1035,8 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target,
   }
   OS << "}\n\n";
 
+  EmitRegUnitPressure(OS, RegBank, ClassName);
+
   // Emit the constructor of the class...
   OS << "extern const MCRegisterDesc " << TargetName << "RegDesc[];\n";
   OS << "extern const uint16_t " << TargetName << "RegLists[];\n";
diff --git a/utils/TableGen/RegisterInfoEmitter.h b/utils/TableGen/RegisterInfoEmitter.h
index 2e6b64aa58..ee9903cac7 100644
--- a/utils/TableGen/RegisterInfoEmitter.h
+++ b/utils/TableGen/RegisterInfoEmitter.h
@@ -54,6 +54,9 @@ private:
                             const std::vector<CodeGenRegister*> &Regs,
                             bool isCtor);
   void EmitRegClasses(raw_ostream &OS, CodeGenTarget &Target);
+
+  void EmitRegUnitPressure(raw_ostream &OS, const CodeGenRegBank &RegBank,
+                           const std::string &ClassName);
 };
 
 } // End llvm namespace