Create a struct representing register units in TableGen.

Besides the weight, we also want to store up to two root registers per
unit. Most units will have a single root, the leaf register they
represent. Units created for ad hoc aliasing get two roots: The two
aliasing registers.

The root registers can be used to compute the set of overlapping
registers.

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

2 files changed, 50 insertions, 35 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index 1a22dc24f2..98d39f7a89 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -187,15 +187,9 @@ bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) {
   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));
+    if (SR == this)
       continue;
-    }
     // Merge the subregister's units into this register's RegUnits.
     mergeRegUnits(RegUnits, SR->RegUnits);
   }
@@ -392,7 +386,7 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
       continue;
     // Create a RegUnit representing this alias edge, and add it to both
     // registers.
-    unsigned Unit = RegBank.newRegUnit(0);
+    unsigned Unit = RegBank.newRegUnit(this, AR);
     RegUnits.push_back(Unit);
     AR->RegUnits.push_back(Unit);
   }
@@ -401,7 +395,7 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
   // 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(0));
+    RegUnits.push_back(RegBank.newRegUnit(this));
 
   return SubRegs;
 }
@@ -540,7 +534,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;
 }
@@ -958,7 +952,6 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
 
   // 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);
 
@@ -974,7 +967,7 @@ 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<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
@@ -1243,7 +1236,7 @@ static void computeUberWeights(std::vector<UberRegSet> &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);
@@ -1338,11 +1331,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<UberRegSet> UberSets;
   std::vector<UberRegSet*> RegSets(Registers.size());
   computeUberSets(UberSets, RegSets, *this);
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 491a91667a..e6c72df740 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -371,6 +371,31 @@ namespace llvm {
     static void computeSubClasses(CodeGenRegBank&);
   };
 
+  // Register units are used to model interference and register pressure.
+  // Every register is assigned one or more register units such that two
+  // registers overlap if and only if they have a register unit in common.
+  //
+  // Normally, one register unit is created per leaf register. Non-leaf
+  // registers inherit the units of their sub-registers.
+  struct RegUnit {
+    // Weight assigned to this RegUnit for estimating register pressure.
+    // This is useful when equalizing weights in register classes with mixed
+    // register topologies.
+    unsigned Weight;
+
+    // Each native RegUnit corresponds to one or two root registers. The full
+    // set of registers containing this unit can be computed as the union of
+    // these two registers and their super-registers.
+    const CodeGenRegister *Roots[2];
+
+    RegUnit() : Weight(0) { Roots[0] = Roots[1] = 0; }
+
+    ArrayRef<const CodeGenRegister*> getRoots() const {
+      assert(!(Roots[1] && !Roots[0]) && "Invalid roots array");
+      return makeArrayRef(Roots, !!Roots[0] + !!Roots[1]);
+    }
+  };
+
   // Each RegUnitSet is a sorted vector with a name.
   struct RegUnitSet {
     typedef std::vector<unsigned>::const_iterator iterator;
@@ -402,13 +427,11 @@ namespace llvm {
     std::vector<CodeGenRegister*> Registers;
     DenseMap<Record*, CodeGenRegister*> Def2Reg;
     unsigned NumNativeRegUnits;
-    unsigned NumRegUnits; // # native + adopted register units.
 
     std::map<TopoSigId, unsigned> TopoSigs;
 
-    // Map each register unit to a weight (for register pressure).
-    // Includes native and adopted register units.
-    std::vector<unsigned> RegUnitWeights;
+    // Includes native (0..NumNativeRegUnits-1) and adopted register units.
+    SmallVector<RegUnit, 8> RegUnits;
 
     // Register classes.
     std::vector<CodeGenRegisterClass*> RegClasses;
@@ -504,15 +527,21 @@ namespace llvm {
       return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second;
     }
 
+    // Create a native register unit that is associated with one or two root
+    // registers.
+    unsigned newRegUnit(CodeGenRegister *R0, CodeGenRegister *R1 = 0) {
+      RegUnits.resize(RegUnits.size() + 1);
+      RegUnits.back().Roots[0] = R0;
+      RegUnits.back().Roots[1] = R1;
+      return RegUnits.size() - 1;
+    }
+
     // Create a new non-native register unit that can be adopted by a register
     // 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++;
+      RegUnits.resize(RegUnits.size() + 1);
+      RegUnits.back().Weight = Weight;
+      return RegUnits.size() - 1;
     }
 
     // Native units are the singular unit of a leaf register. Register aliasing
@@ -522,6 +551,9 @@ namespace llvm {
       return RUID < NumNativeRegUnits;
     }
 
+    RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; }
+    const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; }
+
     ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
       return RegClasses;
     }
@@ -536,23 +568,18 @@ 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];
-    }
-
     // Get the sum of unit weights.
     unsigned getRegUnitSetWeight(const std::vector<unsigned> &Units) const {
       unsigned Weight = 0;
       for (std::vector<unsigned>::const_iterator
              I = Units.begin(), E = Units.end(); I != E; ++I)
-        Weight += getRegUnitWeight(*I);
+        Weight += getRegUnit(*I).Weight;
       return Weight;
     }
 
     // Increase a RegUnitWeight.
     void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {
-      RegUnitWeights[RUID] += Inc;
+      getRegUnit(RUID).Weight += Inc;
     }
 
     // Get the number of register pressure dimensions.