1 files changed, 158 insertions, 36 deletions

diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 232a6e7..eb6724e 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;
@@ -67,6 +68,7 @@ namespace llvm {
     // Return a conflicting composite, or NULL
     CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A,
                                      CodeGenSubRegIndex *B) {
+      assert(A && B);
       std::pair<CompMap::iterator, bool> Ins =
         Composed.insert(std::make_pair(A, B));
       return (Ins.second || Ins.first->second == B) ? 0 : Ins.first->second;
@@ -100,9 +102,20 @@ namespace llvm {
 
     const std::string &getName() const;
 
-    // Get a map of sub-registers computed lazily.
+    // Extract more information from TheDef. This is used to build an object
+    // graph after all CodeGenRegister objects have been created.
+    void buildObjectGraph(CodeGenRegBank&);
+
+    // Lazily compute a map of all sub-registers.
     // This includes unique entries for all sub-sub-registers.
-    const SubRegMap &getSubRegs(CodeGenRegBank&);
+    const SubRegMap &computeSubRegs(CodeGenRegBank&);
+
+    // Compute extra sub-registers by combining the existing sub-registers.
+    void computeSecondarySubRegs(CodeGenRegBank&);
+
+    // Add this as a super-register to all sub-registers after the sub-register
+    // graph has been built.
+    void computeSuperRegs(CodeGenRegBank&);
 
     const SubRegMap &getSubRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
@@ -113,23 +126,54 @@ namespace llvm {
     void addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
                             CodeGenRegBank&) const;
 
-    // List of super-registers in topological order, small to large.
+    // Return the sub-register index naming Reg as a sub-register of this
+    // register. Returns NULL if Reg is not a sub-register.
+    CodeGenSubRegIndex *getSubRegIndex(const CodeGenRegister *Reg) const {
+      return SubReg2Idx.lookup(Reg);
+    }
+
     typedef std::vector<const CodeGenRegister*> SuperRegList;
 
-    // Get the list of super-registers. This is valid after getSubReg
-    // visits all registers during RegBank construction.
+    // Get the list of super-registers in topological order, small to large.
+    // This is valid after computeSubRegs visits all registers during RegBank
+    // construction.
     const SuperRegList &getSuperRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
       return SuperRegs;
     }
 
+    // Get the list of ad hoc aliases. The graph is symmetric, so the list
+    // contains all registers in 'Aliases', and all registers that mention this
+    // register in 'Aliases'.
+    ArrayRef<CodeGenRegister*> getExplicitAliases() const {
+      return ExplicitAliases;
+    }
+
+    // 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;
 
+    // How many entries in RegUnitList are native?
+    unsigned NumNativeRegUnits;
+
     // Get the list of register units.
-    // This is only valid after getSubRegs() completes.
+    // This is only valid after computeSubRegs() completes.
     const RegUnitList &getRegUnits() const { return RegUnits; }
 
+    // Get the native register units. This is a prefix of getRegUnits().
+    ArrayRef<unsigned> getNativeRegUnits() const {
+      return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits);
+    }
+
     // Inherit register units from subregisters.
     // Return true if the RegUnits changed.
     bool inheritRegUnits(CodeGenRegBank &RegBank);
@@ -153,10 +197,27 @@ namespace llvm {
     // Canonically ordered set.
     typedef std::set<const CodeGenRegister*, Less> Set;
 
+    // Compute the set of registers overlapping this.
+    void computeOverlaps(Set &Overlaps, const CodeGenRegBank&) const;
+
   private:
     bool SubRegsComplete;
+    bool SuperRegsComplete;
+    unsigned TopoSig;
+
+    // The sub-registers explicit in the .td file form a tree.
+    SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices;
+    SmallVector<CodeGenRegister*, 8> ExplicitSubRegs;
+
+    // Explicit ad hoc aliases, symmetrized to form an undirected graph.
+    SmallVector<CodeGenRegister*, 8> ExplicitAliases;
+
+    // Super-registers where this is the first explicit sub-register.
+    SuperRegList LeadingSuperRegs;
+
     SubRegMap SubRegs;
     SuperRegList SuperRegs;
+    DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx;
     RegUnitList RegUnits;
   };
 
@@ -189,6 +250,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;
@@ -197,8 +262,6 @@ namespace llvm {
     unsigned SpillAlignment;
     int CopyCost;
     bool Allocatable;
-    // Map SubRegIndex -> RegisterClass
-    DenseMap<Record*,Record*> SubRegClasses;
     std::string AltOrderSelect;
 
     // Return the Record that defined this class, or NULL if the class was
@@ -279,6 +342,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;
 
@@ -310,12 +376,37 @@ namespace llvm {
     };
 
     // Create a non-user defined register class.
-    CodeGenRegisterClass(StringRef Name, Key Props);
+    CodeGenRegisterClass(CodeGenRegBank&, StringRef Name, Key Props);
 
     // Called by CodeGenRegBank::CodeGenRegBank().
     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;
@@ -324,6 +415,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 {
@@ -335,15 +430,19 @@ namespace llvm {
     DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx;
     unsigned NumNamedIndices;
 
+    typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>,
+                     CodeGenSubRegIndex*> ConcatIdxMap;
+    ConcatIdxMap ConcatIdx;
+
     // Registers.
     std::vector<CodeGenRegister*> Registers;
     DenseMap<Record*, CodeGenRegister*> Def2Reg;
     unsigned NumNativeRegUnits;
-    unsigned NumRegUnits; // # native + adopted register units.
 
-    // Map each register unit to a weight (for register pressure).
-    // Includes native and adopted register units.
-    std::vector<unsigned> RegUnitWeights;
+    std::map<TopoSigId, unsigned> TopoSigs;
+
+    // Includes native (0..NumNativeRegUnits-1) and adopted register units.
+    SmallVector<RegUnit, 8> RegUnits;
 
     // Register classes.
     std::vector<CodeGenRegisterClass*> RegClasses;
@@ -405,6 +504,17 @@ namespace llvm {
     CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,
                                                 CodeGenSubRegIndex *B);
 
+    // Find or create a sub-register index representing the concatenation of
+    // non-overlapping sibling indices.
+    CodeGenSubRegIndex *
+      getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8>&);
+
+    void
+    addConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8> &Parts,
+                         CodeGenSubRegIndex *Idx) {
+      ConcatIdx.insert(std::make_pair(Parts, Idx));
+    }
+
     const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
 
     // Find a register from its Record def.
@@ -415,15 +525,34 @@ 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 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
@@ -433,6 +562,13 @@ namespace llvm {
       return RUID < NumNativeRegUnits;
     }
 
+    unsigned getNumNativeRegUnits() const {
+      return NumNativeRegUnits;
+    }
+
+    RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; }
+    const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; }
+
     ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
       return RegClasses;
     }
@@ -447,23 +583,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.
@@ -485,15 +616,6 @@ namespace llvm {
     // Computed derived records such as missing sub-register indices.
     void computeDerivedInfo();
 
-    // Compute full overlap sets for every register. These sets include the
-    // rarely used aliases that are neither sub nor super-registers.
-    //
-    // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
-    //
-    // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
-    void computeOverlaps(std::map<const CodeGenRegister*,
-                                  CodeGenRegister::Set> &Map);
-
     // Compute the set of registers completely covered by the registers in Regs.
     // The returned BitVector will have a bit set for each register in Regs,
     // all sub-registers, and all super-registers that are covered by the