summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/utils/TableGen/CodeGenRegisters.cpp42
-rw-r--r--llvm/utils/TableGen/CodeGenRegisters.h42
2 files changed, 76 insertions, 8 deletions
diff --git a/llvm/utils/TableGen/CodeGenRegisters.cpp b/llvm/utils/TableGen/CodeGenRegisters.cpp
index 83118abc626..499292a1969 100644
--- a/llvm/utils/TableGen/CodeGenRegisters.cpp
+++ b/llvm/utils/TableGen/CodeGenRegisters.cpp
@@ -84,7 +84,8 @@ CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
CostPerUse(R->getValueAsInt("CostPerUse")),
CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")),
SubRegsComplete(false),
- SuperRegsComplete(false)
+ SuperRegsComplete(false),
+ TopoSig(~0u)
{}
void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
@@ -448,7 +449,7 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
}
}
-void CodeGenRegister::computeSuperRegs() {
+void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) {
// Only visit each register once.
if (SuperRegsComplete)
return;
@@ -458,11 +459,18 @@ void CodeGenRegister::computeSuperRegs() {
// lists will be topologically ordered.
for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
I != E; ++I)
- I->second->computeSuperRegs();
+ I->second->computeSuperRegs(RegBank);
// Now add this as a super-register on all sub-registers.
+ // Also compute the TopoSigId in post-order.
+ TopoSigId Id;
for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
I != E; ++I) {
+ // Topological signature computed from SubIdx, TopoId(SubReg).
+ // Loops and idempotent indices have TopoSig = ~0u.
+ Id.push_back(I->first->EnumValue);
+ Id.push_back(I->second->TopoSig);
+
if (I->second == this)
continue;
// Don't add duplicate entries.
@@ -470,6 +478,7 @@ void CodeGenRegister::computeSuperRegs() {
continue;
I->second->SuperRegs.push_back(this);
}
+ TopoSig = RegBank.getTopoSig(Id);
}
void
@@ -612,7 +621,10 @@ struct TupleExpander : SetTheory::Expander {
//===----------------------------------------------------------------------===//
CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
- : TheDef(R), Name(R->getName()), EnumValue(-1) {
+ : TheDef(R),
+ Name(R->getName()),
+ TopoSigs(RegBank.getNumTopoSigs()),
+ EnumValue(-1) {
// Rename anonymous register classes.
if (R->getName().size() > 9 && R->getName()[9] == '.') {
static unsigned AnonCounter = 0;
@@ -637,7 +649,9 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
// Default allocation order always contains all registers.
for (unsigned i = 0, e = Elements->size(); i != e; ++i) {
Orders[0].push_back((*Elements)[i]);
- Members.insert(RegBank.getReg((*Elements)[i]));
+ const CodeGenRegister *Reg = RegBank.getReg((*Elements)[i]);
+ Members.insert(Reg);
+ TopoSigs.set(Reg->getTopoSig());
}
// Alternative allocation orders may be subsets.
@@ -918,7 +932,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
// After the sub-register graph is complete, compute the topologically
// ordered SuperRegs list.
for (unsigned i = 0, e = Registers.size(); i != e; ++i)
- Registers[i]->computeSuperRegs();
+ Registers[i]->computeSuperRegs(*this);
// Native register units are associated with a leaf register. They've all been
// discovered now.
@@ -1032,8 +1046,18 @@ getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8> &Parts) {
}
void CodeGenRegBank::computeComposites() {
+ // Keep track of TopoSigs visited. We only need to visit each TopoSig once,
+ // and many registers will share TopoSigs on regular architectures.
+ BitVector TopoSigs(getNumTopoSigs());
+
for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
CodeGenRegister *Reg1 = Registers[i];
+
+ // Skip identical subreg structures already processed.
+ if (TopoSigs.test(Reg1->getTopoSig()))
+ continue;
+ TopoSigs.set(Reg1->getTopoSig());
+
const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs();
for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(),
e1 = SRM1.end(); i1 != e1; ++i1) {
@@ -1634,6 +1658,7 @@ void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
unsigned FirstSubRegRC) {
SmallVector<std::pair<const CodeGenRegister*,
const CodeGenRegister*>, 16> SSPairs;
+ BitVector TopoSigs(getNumTopoSigs());
// Iterate in SubRegIndex numerical order to visit synthetic indices last.
for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) {
@@ -1646,12 +1671,14 @@ void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
// Build list of (Super, Sub) pairs for this SubIdx.
SSPairs.clear();
+ TopoSigs.reset();
for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(),
RE = RC->getMembers().end(); RI != RE; ++RI) {
const CodeGenRegister *Super = *RI;
const CodeGenRegister *Sub = Super->getSubRegs().find(SubIdx)->second;
assert(Sub && "Missing sub-register");
SSPairs.push_back(std::make_pair(Super, Sub));
+ TopoSigs.set(Sub->getTopoSig());
}
// Iterate over sub-register class candidates. Ignore classes created by
@@ -1659,6 +1686,9 @@ void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
for (unsigned rci = FirstSubRegRC, rce = RegClasses.size(); rci != rce;
++rci) {
CodeGenRegisterClass *SubRC = RegClasses[rci];
+ // Topological shortcut: SubRC members have the wrong shape.
+ if (!TopoSigs.anyCommon(SubRC->getTopoSigs()))
+ continue;
// Compute the subset of RC that maps into SubRC.
CodeGenRegister::Set SubSet;
for (unsigned i = 0, e = SSPairs.size(); i != e; ++i)
diff --git a/llvm/utils/TableGen/CodeGenRegisters.h b/llvm/utils/TableGen/CodeGenRegisters.h
index f5413b6a740..7e2c07ee580 100644
--- a/llvm/utils/TableGen/CodeGenRegisters.h
+++ b/llvm/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) {
OpenPOWER on IntegriCloud