Compute topological signatures of registers.

TableGen creates new register classes and sub-register indices based on
the sub-register structure present in the register bank. So far, it has
been doing that on a per-register basis, but that is not very efficient.

This patch teaches TableGen to compute topological signatures for
registers, and use that to reduce the amount of redundant computation.
Registers get the same TopoSig if they have identical sub-register
structure.

TopoSigs are not currently exposed outside TableGen.

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

1 files changed, 40 insertions, 2 deletions

diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index f5413b6a74..7e2c07ee58 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -35,9 +35,10 @@ namespace llvm {
   /// CodeGenSubRegIndex - Represents a sub-register index.
   class CodeGenSubRegIndex {
     Record *const TheDef;
-    const unsigned EnumValue;
 
   public:
+    const unsigned EnumValue;
+
     CodeGenSubRegIndex(Record *R, unsigned Enum);
 
     const std::string &getName() const;
@@ -114,7 +115,7 @@ namespace llvm {
 
     // Add this as a super-register to all sub-registers after the sub-register
     // graph has been built.
-    void computeSuperRegs();
+    void computeSuperRegs(CodeGenRegBank&);
 
     const SubRegMap &getSubRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
@@ -141,6 +142,16 @@ namespace llvm {
       return SuperRegs;
     }
 
+    // Get the topological signature of this register. This is a small integer
+    // less than RegBank.getNumTopoSigs(). Registers with the same TopoSig have
+    // identical sub-register structure. That is, they support the same set of
+    // sub-register indices mapping to the same kind of sub-registers
+    // (TopoSig-wise).
+    unsigned getTopoSig() const {
+      assert(SuperRegsComplete && "TopoSigs haven't been computed yet.");
+      return TopoSig;
+    }
+
     // List of register units in ascending order.
     typedef SmallVector<unsigned, 16> RegUnitList;
 
@@ -174,6 +185,7 @@ namespace llvm {
   private:
     bool SubRegsComplete;
     bool SuperRegsComplete;
+    unsigned TopoSig;
 
     // The sub-registers explicit in the .td file form a tree.
     SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices;
@@ -217,6 +229,10 @@ namespace llvm {
     DenseMap<CodeGenSubRegIndex*,
              SmallPtrSet<CodeGenRegisterClass*, 8> > SuperRegClasses;
 
+    // Bit vector of TopoSigs for the registers in this class. This will be
+    // very sparse on regular architectures.
+    BitVector TopoSigs;
+
   public:
     unsigned EnumValue;
     std::string Namespace;
@@ -305,6 +321,9 @@ namespace llvm {
     // getOrder(0).
     const CodeGenRegister::Set &getMembers() const { return Members; }
 
+    // Get a bit vector of TopoSigs present in this register class.
+    const BitVector &getTopoSigs() const { return TopoSigs; }
+
     // Populate a unique sorted list of units from a register set.
     void buildRegUnitSet(std::vector<unsigned> &RegUnits) const;
 
@@ -350,6 +369,10 @@ namespace llvm {
     std::vector<unsigned> Units;
   };
 
+  // Base vector for identifying TopoSigs. The contents uniquely identify a
+  // TopoSig, only computeSuperRegs needs to know how.
+  typedef SmallVector<unsigned, 16> TopoSigId;
+
   // CodeGenRegBank - Represent a target's registers and the relations between
   // them.
   class CodeGenRegBank {
@@ -371,6 +394,8 @@ namespace llvm {
     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;
@@ -456,6 +481,19 @@ namespace llvm {
       return Reg->EnumValue - 1;
     }
 
+    // Return the number of allocated TopoSigs. The first TopoSig representing
+    // leaf registers is allocated number 0.
+    unsigned getNumTopoSigs() const {
+      return TopoSigs.size();
+    }
+
+    // Find or create a TopoSig for the given TopoSigId.
+    // This function is only for use by CodeGenRegister::computeSuperRegs().
+    // Others should simply use Reg->getTopoSig().
+    unsigned getTopoSig(const TopoSigId &Id) {
+      return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second;
+    }
+
     // 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) {