summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--utils/TableGen/CodeGenRegisters.cpp323
-rw-r--r--utils/TableGen/CodeGenRegisters.h48
2 files changed, 352 insertions, 19 deletions
diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index 6784d53a8c..5939804050 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/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();
}
//
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 0d26bc493e..d22dced9d3 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -130,6 +130,17 @@ namespace llvm {
// This is only valid after getSubRegs() completes.
const RegUnitList &getRegUnits() const { return RegUnits; }
+ // Inherit register units from subregisters.
+ // Return true if the RegUnits changed.
+ bool inheritRegUnits(CodeGenRegBank &RegBank);
+
+ // Adopt a register unit for pressure tracking.
+ // A unit is adopted iff its unit number is >= NumNativeRegUnits.
+ void adoptRegUnit(unsigned RUID) { RegUnits.push_back(RUID); }
+
+ // Get the sum of this register's register unit weights.
+ unsigned getWeight(const CodeGenRegBank &RegBank) const;
+
// Order CodeGenRegister pointers by EnumValue.
struct Less {
bool operator()(const CodeGenRegister *A,
@@ -315,7 +326,12 @@ namespace llvm {
// Registers.
std::vector<CodeGenRegister*> Registers;
DenseMap<Record*, CodeGenRegister*> Def2Reg;
- unsigned NumRegUnits;
+ 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;
// Register classes.
std::vector<CodeGenRegisterClass*> RegClasses;
@@ -338,6 +354,9 @@ namespace llvm {
void inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
unsigned FirstSubRegRC = 0);
+ // Compute a weight for each register unit created during getSubRegs.
+ void computeRegUnitWeights();
+
// Populate the Composite map from sub-register relationships.
void computeComposites();
@@ -364,7 +383,24 @@ namespace llvm {
// Find a register from its Record def.
CodeGenRegister *getReg(Record*);
- unsigned newRegUnit() { return NumRegUnits++; }
+ // Get a Register's index into the Registers array.
+ unsigned getRegIndex(const CodeGenRegister *Reg) const {
+ return Reg->EnumValue - 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()) {
+ RegUnitWeights.resize(NumRegUnits+1);
+ RegUnitWeights[NumRegUnits] = Weight;
+ }
+ return NumRegUnits++;
+ }
+
+ bool isNativeUnit(unsigned RUID) {
+ return RUID < NumNativeRegUnits;
+ }
ArrayRef<CodeGenRegisterClass*> getRegClasses() const {
return RegClasses;
@@ -380,6 +416,14 @@ namespace llvm {
/// return the superclass. Otherwise return null.
const CodeGenRegisterClass* getRegClassForRegister(Record *R);
+ unsigned getRegUnitWeight(unsigned RUID) const {
+ return RegUnitWeights[RUID];
+ }
+
+ void increaseRegUnitWeight(unsigned RUID, unsigned Inc) {
+ RegUnitWeights[RUID] += Inc;
+ }
+
// Computed derived records such as missing sub-register indices.
void computeDerivedInfo();
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 01:36:04 +0000