Added register unit weights to the target description.

This is a new algorithm that associates registers with weighted
register units to accuretely model their effect on register
pressure. This handles registers with multiple overlapping
subregisters. It is possible, but almost inconceivable that the
algorithm fails to find an exact solution for a target description. If
an exact solution cannot be found, an inexact, but reasonable solution
will be chosen.

llvm-svn: 154373

1 files changed, 306 insertions, 17 deletions

diff --git a/llvm/utils/TableGen/CodeGenRegisters.cpp b/llvm/utils/TableGen/CodeGenRegisters.cpp
index 6784d53a8cf..59398040508 100644
--- a/llvm/utils/TableGen/CodeGenRegisters.cpp
+++ b/llvm/utils/TableGen/CodeGenRegisters.cpp
@@ -15,6 +15,7 @@
 #include "CodeGenRegisters.h"
 #include "CodeGenTarget.h"
 #include "llvm/TableGen/Error.h"
+#include "llvm/ADT/IntEqClasses.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
@@ -88,6 +89,48 @@ const std::string &CodeGenRegister::getName() const {
   return TheDef->getName();
 }
 
+namespace {
+// Iterate over all register units in a set of registers.
+class RegUnitIterator {
+  CodeGenRegister::Set::const_iterator RegI, RegE;
+  CodeGenRegister::RegUnitList::const_iterator UnitI, UnitE;
+
+public:
+  RegUnitIterator(const CodeGenRegister::Set &Regs):
+    RegI(Regs.begin()), RegE(Regs.end()), UnitI(), UnitE() {
+
+    if (RegI != RegE) {
+      UnitI = (*RegI)->getRegUnits().begin();
+      UnitE = (*RegI)->getRegUnits().end();
+      advance();
+    }
+  }
+
+  bool isValid() const { return UnitI != UnitE; }
+
+  unsigned operator* () const { assert(isValid()); return *UnitI; };
+
+  const CodeGenRegister *getReg() const { assert(isValid()); return *RegI; }
+
+  /// Preincrement.  Move to the next unit.
+  void operator++() {
+    assert(isValid() && "Cannot advance beyond the last operand");
+    ++UnitI;
+    advance();
+  }
+
+protected:
+  void advance() {
+    while (UnitI == UnitE) {
+      if (++RegI == RegE)
+        break;
+      UnitI = (*RegI)->getRegUnits().begin();
+      UnitE = (*RegI)->getRegUnits().end();
+    }
+  }
+};
+} // namespace
+
 // Merge two RegUnitLists maintaining the order and removing duplicates.
 // Overwrites MergedRU in the process.
 static void mergeRegUnits(CodeGenRegister::RegUnitList &MergedRU,
@@ -98,6 +141,32 @@ static void mergeRegUnits(CodeGenRegister::RegUnitList &MergedRU,
                  std::back_inserter(MergedRU));
 }
 
+// Return true of this unit appears in RegUnits.
+static bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) {
+  return std::count(RegUnits.begin(), RegUnits.end(), Unit);
+}
+
+// Inherit register units from subregisters.
+// Return true if the RegUnits changed.
+bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) {
+  unsigned OldNumUnits = RegUnits.size();
+  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 getSubRegs, prior to computing weight.
+      if (RegUnits.empty())
+        RegUnits.push_back(RegBank.newRegUnit(0));
+      continue;
+    }
+    // Merge the subregister's units into this register's RegUnits.
+    mergeRegUnits(RegUnits, SR->RegUnits);
+  }
+  return OldNumUnits != RegUnits.size();
+}
+
 const CodeGenRegister::SubRegMap &
 CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) {
   // Only compute this map once.
@@ -248,23 +317,10 @@ CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) {
   // aliases. This can be done by iteratively merging units for aliasing
   // registers using a worklist.
   assert(RegUnits.empty() && "Should only initialize RegUnits once");
-  if (SubRegs.empty()) {
-    RegUnits.push_back(RegBank.newRegUnit());
-  }
-  else {
-    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.
-      CodeGenRegister *SR = I->second;
-      if (SR == this) {
-        if (RegUnits.empty())
-          RegUnits.push_back(RegBank.newRegUnit());
-        continue;
-      }
-      // Merge the subregister's units into this register's RegUnits.
-      mergeRegUnits(RegUnits, SR->RegUnits);
-    }
-  }
+  if (SubRegs.empty())
+    RegUnits.push_back(RegBank.newRegUnit(0));
+  else
+    inheritRegUnits(RegBank);
   return SubRegs;
 }
 
@@ -281,6 +337,16 @@ CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
   }
 }
 
+// Get the sum of this register's unit weights.
+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);
+  }
+  return Weight;
+}
+
 //===----------------------------------------------------------------------===//
 //                               RegisterTuples
 //===----------------------------------------------------------------------===//
@@ -701,6 +767,10 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
   for (unsigned i = 0, e = Registers.size(); i != e; ++i)
     Registers[i]->getSubRegs(*this);
 
+  // Native register units are associated with a leaf register. They've all been
+  // discovered now.
+  NumNativeRegUnits = NumRegUnits;
+
   // Read in register class definitions.
   std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
   if (RCs.empty())
@@ -833,6 +903,221 @@ void CodeGenRegBank::computeComposites() {
     SubRegIndices[i]->cleanComposites();
 }
 
+namespace {
+// UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is
+// the transitive closure of the union of overlapping register
+// classes. Together, the UberRegSets form a partition of the registers. If we
+// consider overlapping register classes to be connected, then each UberRegSet
+// is a set of connected components.
+//
+// An UberRegSet will likely be a horizontal slice of register names of
+// the same width. Nontrivial subregisters should then be in a separate
+// UberRegSet. But this property isn't required for valid computation of
+// register unit weights.
+//
+// A Weight field caches the max per-register unit weight in each UberRegSet.
+//
+// A set of SingularDeterminants flags single units of some register in this set
+// for which the unit weight equals the set weight. These units should not have
+// their weight increased.
+struct UberRegSet {
+  CodeGenRegister::Set Regs;
+  unsigned Weight;
+  CodeGenRegister::RegUnitList SingularDeterminants;
+
+  UberRegSet(): Weight(0) {}
+};
+} // namespace
+
+// Partition registers into UberRegSets, where each set is the transitive
+// closure of the union of overlapping register classes.
+//
+// UberRegSets[0] is a special non-allocatable set.
+static void computeUberSets(std::vector<UberRegSet> &UberSets,
+                            std::vector<UberRegSet*> &RegSets,
+                            CodeGenRegBank &RegBank) {
+
+  const std::vector<CodeGenRegister*> &Registers = RegBank.getRegisters();
+
+  // The Register EnumValue is one greater than its index into Registers.
+  assert(Registers.size() == Registers[Registers.size()-1]->EnumValue &&
+         "register enum value mismatch");
+
+  // For simplicitly make the SetID the same as EnumValue.
+  IntEqClasses UberSetIDs(Registers.size()+1);
+  for (unsigned i = 0, e = RegBank.getRegClasses().size(); i != e; ++i) {
+    CodeGenRegisterClass *RegClass = RegBank.getRegClasses()[i];
+    const CodeGenRegister::Set &Regs = RegClass->getMembers();
+    if (Regs.empty()) continue;
+
+    unsigned USetID = UberSetIDs.findLeader((*Regs.begin())->EnumValue);
+    assert(USetID && "register number 0 is invalid");
+
+    // combine non-allocatable classes
+    if (!RegClass->Allocatable) {
+      UberSetIDs.join(0, USetID);
+      USetID = 0;
+    }
+    for (CodeGenRegister::Set::const_iterator I = llvm::next(Regs.begin()),
+           E = Regs.end(); I != E; ++I)
+      UberSetIDs.join(USetID, (*I)->EnumValue);
+  }
+  UberSetIDs.compress();
+
+  // Make the first UberSet a special unallocatable set.
+  unsigned ZeroID = UberSetIDs[0];
+
+  // Insert Registers into the UberSets formed by union-find.
+  // Do not resize after this.
+  UberSets.resize(UberSetIDs.getNumClasses());
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
+    const CodeGenRegister *Reg = Registers[i];
+    unsigned USetID = UberSetIDs[Reg->EnumValue];
+    if (!USetID)
+      USetID = ZeroID;
+    else if (USetID == ZeroID)
+      USetID = 0;
+
+    UberRegSet *USet = &UberSets[USetID];
+    USet->Regs.insert(Reg);
+    RegSets[i] = USet;
+  }
+}
+
+// Recompute each UberSet weight after changing unit weights.
+static void computeUberWeights(std::vector<UberRegSet> &UberSets,
+                               CodeGenRegBank &RegBank) {
+  // Skip the first unallocatable set.
+  for (std::vector<UberRegSet>::iterator I = llvm::next(UberSets.begin()),
+         E = UberSets.end(); I != E; ++I) {
+
+    // Initialize all unit weights in this set, and remember the max units/reg.
+    const CodeGenRegister *Reg = 0;
+    unsigned MaxWeight = 0, Weight = 0;
+    for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) {
+      if (Reg != UnitI.getReg()) {
+        if (Weight > MaxWeight)
+          MaxWeight = Weight;
+        Reg = UnitI.getReg();
+        Weight = 0;
+      }
+      unsigned UWeight = RegBank.getRegUnitWeight(*UnitI);
+      if (!UWeight) {
+        UWeight = 1;
+        RegBank.increaseRegUnitWeight(*UnitI, UWeight);
+      }
+      Weight += UWeight;
+    }
+    if (Weight > MaxWeight)
+      MaxWeight = Weight;
+
+    // Update the set weight.
+    I->Weight = MaxWeight;
+
+    // Find singular determinants.
+    for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(),
+           RegE = I->Regs.end(); RegI != RegE; ++RegI) {
+      if ((*RegI)->getRegUnits().size() == 1
+          && (*RegI)->getWeight(RegBank) == I->Weight)
+        mergeRegUnits(I->SingularDeterminants, (*RegI)->getRegUnits());
+    }
+  }
+}
+
+// normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
+// a register and its subregisters so that they have the same weight as their
+// UberSet. Self-recursion processes the subregister tree in postorder so
+// subregisters are normalized first.
+//
+// Side effects:
+// - creates new adopted register units
+// - causes superregisters to inherit adopted units
+// - increases the weight of "singular" units
+// - induces recomputation of UberWeights.
+static bool normalizeWeight(CodeGenRegister *Reg,
+                            std::vector<UberRegSet> &UberSets,
+                            std::vector<UberRegSet*> &RegSets,
+                            CodeGenRegister::RegUnitList &NormalUnits,
+                            CodeGenRegBank &RegBank) {
+  bool Changed = false;
+  const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
+  for (CodeGenRegister::SubRegMap::const_iterator SRI = SRM.begin(),
+         SRE = SRM.end(); SRI != SRE; ++SRI) {
+    if (SRI->second == Reg)
+      continue; // self-cycles happen
+
+    Changed |=
+      normalizeWeight(SRI->second, UberSets, RegSets, NormalUnits, RegBank);
+  }
+  // Postorder register normalization.
+
+  // Inherit register units newly adopted by subregisters.
+  if (Reg->inheritRegUnits(RegBank))
+    computeUberWeights(UberSets, RegBank);
+
+  // Check if this register is too skinny for its UberRegSet.
+  UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)];
+
+  unsigned RegWeight = Reg->getWeight(RegBank);
+  if (UberSet->Weight > RegWeight) {
+    // A register unit's weight can be adjusted only if it is the singular unit
+    // for this register, has not been used to normalize a subregister's set,
+    // and has not already been used to singularly determine this UberRegSet.
+    unsigned AdjustUnit = Reg->getRegUnits().front();
+    if (Reg->getRegUnits().size() != 1
+        || hasRegUnit(NormalUnits, AdjustUnit)
+        || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) {
+      // We don't have an adjustable unit, so adopt a new one.
+      AdjustUnit = RegBank.newRegUnit(UberSet->Weight - RegWeight);
+      Reg->adoptRegUnit(AdjustUnit);
+      // Adopting a unit does not immediately require recomputing set weights.
+    }
+    else {
+      // Adjust the existing single unit.
+      RegBank.increaseRegUnitWeight(AdjustUnit, UberSet->Weight - RegWeight);
+      // The unit may be shared among sets and registers within this set.
+      computeUberWeights(UberSets, RegBank);
+    }
+    Changed = true;
+  }
+
+  // Mark these units normalized so superregisters can't change their weights.
+  mergeRegUnits(NormalUnits, Reg->getRegUnits());
+
+  return Changed;
+}
+
+// Compute a weight for each register unit created during getSubRegs.
+//
+// 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);
+  // UberSets and RegSets are now immutable.
+
+  computeUberWeights(UberSets, *this);
+
+  // Iterate over each Register, normalizing the unit weights until reaching
+  // a fix point.
+  unsigned NumIters = 0;
+  for (bool Changed = true; Changed; ++NumIters) {
+    assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights");
+    Changed = false;
+    for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
+      CodeGenRegister::RegUnitList NormalUnits;
+      Changed |=
+        normalizeWeight(Registers[i], UberSets, RegSets, NormalUnits, *this);
+    }
+  }
+}
+
 // Compute sets of overlapping registers.
 //
 // The standard set is all super-registers and all sub-registers, but the
@@ -909,6 +1194,10 @@ computeOverlaps(std::map<const CodeGenRegister*, CodeGenRegister::Set> &Map) {
 
 void CodeGenRegBank::computeDerivedInfo() {
   computeComposites();
+
+  // Compute a weight for each register unit created during getSubRegs.
+  // This may create adopted register units (with unit # >= NumNativeRegUnits).
+  computeRegUnitWeights();
 }
 
 //