From 40c6fb397d1e485aef8b4e1729ba9804784990c1 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 15 May 2012 00:50:23 +0000 Subject: [PATCH] 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 --- utils/TableGen/CodeGenRegisters.cpp | 24 +++--------- utils/TableGen/CodeGenRegisters.h | 61 +++++++++++++++++++++-------- 2 files changed, 50 insertions(+), 35 deletions(-) diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 1a22dc24f2b..98d39f7a89e 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 RCs = Records.getAllDerivedDefinitions("RegisterClass"); @@ -1243,7 +1236,7 @@ static void computeUberWeights(std::vector &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 UberSets; std::vector RegSets(Registers.size()); computeUberSets(UberSets, RegSets, *this); diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h index 491a91667a0..e6c72df7407 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 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::const_iterator iterator; @@ -402,13 +427,11 @@ namespace llvm { std::vector Registers; DenseMap Def2Reg; unsigned NumNativeRegUnits; - unsigned NumRegUnits; // # native + adopted register units. std::map TopoSigs; - // Map each register unit to a weight (for register pressure). - // Includes native and adopted register units. - std::vector RegUnitWeights; + // Includes native (0..NumNativeRegUnits-1) and adopted register units. + SmallVector RegUnits; // Register classes. std::vector 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 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 &Units) const { unsigned Weight = 0; for (std::vector::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. -- 2.34.1