//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "regalloc-emitter"
+
#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/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/TableGen/Error.h"
using namespace llvm;
//===----------------------------------------------------------------------===//
CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum)
- : TheDef(R), EnumValue(Enum), LaneMask(0) {
+ : TheDef(R), EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) {
Name = R->getName();
if (R->getValue("Namespace"))
Namespace = R->getValueAsString("Namespace");
+ Size = R->getValueAsInt("Size");
+ Offset = R->getValueAsInt("Offset");
}
CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,
unsigned Enum)
- : TheDef(0), Name(N), Namespace(Nspace), EnumValue(Enum), LaneMask(0) {
+ : TheDef(0), Name(N), Namespace(Nspace), Size(-1), Offset(-1),
+ EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) {
}
std::string CodeGenSubRegIndex::getQualifiedName() const {
if (!Parts.empty()) {
if (Parts.size() < 2)
PrintFatalError(TheDef->getLoc(),
- "CoveredBySubRegs must have two or more entries");
+ "CoveredBySubRegs must have two or more entries");
SmallVector<CodeGenSubRegIndex*, 8> IdxParts;
for (unsigned i = 0, e = Parts.size(); i != e; ++i)
IdxParts.push_back(RegBank.getSubRegIdx(Parts[i]));
PrintFatalError(Loc, "Register " + getName() +
" has itself as a sub-register");
}
+
+ // Compute AllSuperRegsCovered.
+ if (!CoveredBySubRegs)
+ SI->first->AllSuperRegsCovered = false;
+
// Ensure that every sub-register has a unique name.
DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*>::iterator Ins =
SubReg2Idx.insert(std::make_pair(SI->second, SI->first)).first;
OSet.insert(I->second);
}
-// Compute overlapping registers.
-//
-// The standard set is all super-registers and all sub-registers, but the
-// target description can add arbitrary overlapping registers via the 'Aliases'
-// field. This complicates things, but we can compute overlapping sets using
-// the following rules:
-//
-// 1. The relation overlap(A, B) is reflexive and symmetric but not transitive.
-//
-// 2. overlap(A, B) implies overlap(A, S) for all S in supers(B).
-//
-// Alternatively:
-//
-// overlap(A, B) iff there exists:
-// A' in { A, subregs(A) } and B' in { B, subregs(B) } such that:
-// A' = B' or A' in aliases(B') or B' in aliases(A').
-//
-// Here subregs(A) is the full flattened sub-register set returned by
-// A.getSubRegs() while aliases(A) is simply the special 'Aliases' field in the
-// description of register A.
-//
-// This also implies that registers with a common sub-register are considered
-// overlapping. This can happen when forming register pairs:
-//
-// P0 = (R0, R1)
-// P1 = (R1, R2)
-// P2 = (R2, R3)
-//
-// In this case, we will infer an overlap between P0 and P1 because of the
-// shared sub-register R1. There is no overlap between P0 and P2.
-//
-void CodeGenRegister::computeOverlaps(CodeGenRegister::Set &Overlaps,
- const CodeGenRegBank &RegBank) const {
- assert(!RegUnits.empty() && "Compute register units before overlaps.");
-
- // Register units are assigned such that the overlapping registers are the
- // super-registers of the root registers of the register units.
- for (unsigned rui = 0, rue = RegUnits.size(); rui != rue; ++rui) {
- const RegUnit &RU = RegBank.getRegUnit(RegUnits[rui]);
- ArrayRef<const CodeGenRegister*> Roots = RU.getRoots();
- for (unsigned ri = 0, re = Roots.size(); ri != re; ++ri) {
- const CodeGenRegister *Root = Roots[ri];
- Overlaps.insert(Root);
- ArrayRef<const CodeGenRegister*> Supers = Root->getSuperRegs();
- Overlaps.insert(Supers.begin(), Supers.end());
- }
- }
-}
-
// Get the sum of this register's unit weights.
unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const {
unsigned Weight = 0;
Elts.insert(NewReg);
// Copy Proto super-classes.
- for (unsigned i = 0, e = Proto->getSuperClasses().size(); i != e; ++i)
- NewReg->addSuperClass(Proto->getSuperClasses()[i]);
+ ArrayRef<Record *> Supers = Proto->getSuperClasses();
+ ArrayRef<SMRange> Ranges = Proto->getSuperClassRanges();
+ for (unsigned i = 0, e = Supers.size(); i != e; ++i)
+ NewReg->addSuperClass(Supers[i], Ranges[i]);
// Copy Proto fields.
for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) {
// Rename anonymous register classes.
if (R->getName().size() > 9 && R->getName()[9] == '.') {
static unsigned AnonCounter = 0;
- R->setName("AnonRegClass_"+utostr(AnonCounter++));
+ R->setName("AnonRegClass_" + utostr(AnonCounter));
+ // MSVC2012 ICEs if AnonCounter++ is directly passed to utostr.
+ ++AnonCounter;
}
std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes");
// Read in the register definitions.
std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
- std::sort(Regs.begin(), Regs.end(), LessRecord());
+ std::sort(Regs.begin(), Regs.end(), LessRecordRegister());
Registers.reserve(Regs.size());
// Assign the enumeration values.
for (unsigned i = 0, e = Regs.size(); i != e; ++i)
// Expand tuples and number the new registers.
std::vector<Record*> Tups =
Records.getAllDerivedDefinitions("RegisterTuples");
+
+ std::vector<Record*> TupRegsCopy;
for (unsigned i = 0, e = Tups.size(); i != e; ++i) {
const std::vector<Record*> *TupRegs = Sets.expand(Tups[i]);
- for (unsigned j = 0, je = TupRegs->size(); j != je; ++j)
- getReg((*TupRegs)[j]);
+ TupRegsCopy.reserve(TupRegs->size());
+ TupRegsCopy.assign(TupRegs->begin(), TupRegs->end());
+ std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister());
+ for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j)
+ getReg((TupRegsCopy)[j]);
+ TupRegsCopy.clear();
}
// Now all the registers are known. Build the object graph of explicit
}
CodeGenSubRegIndex *CodeGenRegBank::
-getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8> &Parts) {
+getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts) {
assert(Parts.size() > 1 && "Need two parts to concatenate");
// Look for an existing entry.
// None exists, synthesize one.
std::string Name = Parts.front()->getName();
+ // Determine whether all parts are contiguous.
+ bool isContinuous = true;
+ unsigned Size = Parts.front()->Size;
+ unsigned LastOffset = Parts.front()->Offset;
+ unsigned LastSize = Parts.front()->Size;
for (unsigned i = 1, e = Parts.size(); i != e; ++i) {
Name += '_';
Name += Parts[i]->getName();
+ Size += Parts[i]->Size;
+ if (Parts[i]->Offset != (LastOffset + LastSize))
+ isContinuous = false;
+ LastOffset = Parts[i]->Offset;
+ LastSize = Parts[i]->Size;
}
- return Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
+ Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
+ Idx->Size = Size;
+ Idx->Offset = isContinuous ? Parts.front()->Offset : -1;
+ return Idx;
}
void CodeGenRegBank::computeComposites() {
void CodeGenRegBank::computeSubRegIndexLaneMasks() {
// First assign individual bits to all the leaf indices.
unsigned Bit = 0;
+ // Determine mask of lanes that cover their registers.
+ CoveringLanes = ~0u;
for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) {
CodeGenSubRegIndex *Idx = SubRegIndices[i];
if (Idx->getComposites().empty()) {
Idx->LaneMask = 1u << Bit;
// Share bit 31 in the unlikely case there are more than 32 leafs.
- if (Bit < 31) ++Bit;
+ //
+ // Sharing bits is harmless; it allows graceful degradation in targets
+ // with more than 32 vector lanes. They simply get a limited resolution
+ // view of lanes beyond the 32nd.
+ //
+ // See also the comment for getSubRegIndexLaneMask().
+ if (Bit < 31)
+ ++Bit;
+ else
+ // Once bit 31 is shared among multiple leafs, the 'lane' it represents
+ // is no longer covering its registers.
+ CoveringLanes &= ~(1u << Bit);
} else {
Idx->LaneMask = 0;
}
// by the sub-register graph? This doesn't occur in any known targets.
// Inherit lanes from composites.
- for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i)
- SubRegIndices[i]->computeLaneMask();
+ for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) {
+ unsigned Mask = SubRegIndices[i]->computeLaneMask();
+ // If some super-registers without CoveredBySubRegs use this index, we can
+ // no longer assume that the lanes are covering their registers.
+ if (!SubRegIndices[i]->AllSuperRegsCovered)
+ CoveringLanes &= ~Mask;
+ }
}
namespace {
}
if (Weight > MaxWeight)
MaxWeight = Weight;
-
- // Update the set weight.
- I->Weight = MaxWeight;
+ if (I->Weight != MaxWeight) {
+ DEBUG(
+ dbgs() << "UberSet " << I - UberSets.begin() << " Weight " << MaxWeight;
+ for (CodeGenRegister::Set::iterator
+ UnitI = I->Regs.begin(), UnitE = I->Regs.end();
+ UnitI != UnitE; ++UnitI) {
+ dbgs() << " " << (*UnitI)->getName();
+ }
+ dbgs() << "\n");
+ // Update the set weight.
+ I->Weight = MaxWeight;
+ }
// Find singular determinants.
for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(),
RUSubSet.begin(), RUSubSet.end());
}
-// Iteratively prune unit sets.
+/// Iteratively prune unit sets. Prune subsets that are close to the superset,
+/// but with one or two registers removed. We occasionally have registers like
+/// APSR and PC thrown in with the general registers. We also see many
+/// special-purpose register subsets, such as tail-call and Thumb
+/// encodings. Generating all possible overlapping sets is combinatorial and
+/// overkill for modeling pressure. Ideally we could fix this statically in
+/// tablegen by (1) having the target define register classes that only include
+/// the allocatable registers and marking other classes as non-allocatable and
+/// (2) having a way to mark special purpose classes as "don't-care" classes for
+/// the purpose of pressure. However, we make an attempt to handle targets that
+/// are not nicely defined by merging nearly identical register unit sets
+/// statically. This generates smaller tables. Then, dynamically, we adjust the
+/// set limit by filtering the reserved registers.
+///
+/// Merge sets only if the units have the same weight. For example, on ARM,
+/// Q-tuples with ssub index 0 include all S regs but also include D16+. We
+/// should not expand the S set to include D regs.
void CodeGenRegBank::pruneUnitSets() {
assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets");
if (SuperIdx == SubIdx)
continue;
+ unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight;
const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
if (isRegUnitSubSet(SubSet.Units, SuperSet.Units)
- && (SubSet.Units.size() + 3 > SuperSet.Units.size())) {
+ && (SubSet.Units.size() + 3 > SuperSet.Units.size())
+ && UnitWeight == RegUnits[SuperSet.Units[0]].Weight
+ && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) {
+ DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx
+ << "\n");
break;
}
}
// RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
// RegUnitSet that is a superset of that RegUnitClass.
void CodeGenRegBank::computeRegUnitSets() {
+ assert(RegUnitSets.empty() && "dirty RegUnitSets");
// Compute a unique RegUnitSet for each RegClass.
const ArrayRef<CodeGenRegisterClass*> &RegClasses = getRegClasses();
RegUnitSets.pop_back();
}
+ DEBUG(dbgs() << "\nBefore pruning:\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName();
+ dbgs() << "\n";
+ });
+
// Iteratively prune unit sets.
pruneUnitSets();
+ DEBUG(dbgs() << "\nBefore union:\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName();
+ dbgs() << "\n";
+ }
+ dbgs() << "\nUnion sets:\n");
+
// Iterate over all unit sets, including new ones added by this loop.
unsigned NumRegUnitSubSets = RegUnitSets.size();
for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
findRegUnitSet(RegUnitSets, RegUnitSets.back());
if (SetI != llvm::prior(RegUnitSets.end()))
RegUnitSets.pop_back();
+ else {
+ DEBUG(dbgs() << "UnitSet " << RegUnitSets.size()-1
+ << " " << RegUnitSets.back().Name << ":";
+ ArrayRef<unsigned> Units = RegUnitSets.back().Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName();
+ dbgs() << "\n";);
+ }
}
}
// Iteratively prune unit sets after inferring supersets.
pruneUnitSets();
+ DEBUG(dbgs() << "\n";
+ for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
+ USIdx < USEnd; ++USIdx) {
+ dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name
+ << ":";
+ ArrayRef<unsigned> Units = RegUnitSets[USIdx].Units;
+ for (unsigned i = 0, e = Units.size(); i < e; ++i)
+ dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName();
+ dbgs() << "\n";
+ });
+
// For each register class, list the UnitSets that are supersets.
RegClassUnitSets.resize(NumRegClasses);
for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) {
continue;
// Recompute the sorted list of units in this class.
- std::vector<unsigned> RegUnits;
- RegClasses[RCIdx]->buildRegUnitSet(RegUnits);
+ std::vector<unsigned> RCRegUnits;
+ RegClasses[RCIdx]->buildRegUnitSet(RCRegUnits);
// Don't increase pressure for unallocatable regclasses.
- if (RegUnits.empty())
+ if (RCRegUnits.empty())
continue;
+ DEBUG(dbgs() << "RC " << RegClasses[RCIdx]->getName() << " Units: \n";
+ for (unsigned i = 0, e = RCRegUnits.size(); i < e; ++i)
+ dbgs() << RegUnits[RCRegUnits[i]].getRoots()[0]->getName() << " ";
+ dbgs() << "\n UnitSetIDs:");
+
// Find all supersets.
for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
USIdx != USEnd; ++USIdx) {
- if (isRegUnitSubSet(RegUnits, RegUnitSets[USIdx].Units))
+ if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) {
+ DEBUG(dbgs() << " " << USIdx);
RegClassUnitSets[RCIdx].push_back(USIdx);
+ }
}
+ DEBUG(dbgs() << "\n");
assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass");
}
+
+ // For each register unit, ensure that we have the list of UnitSets that
+ // contain the unit. Normally, this matches an existing list of UnitSets for a
+ // register class. If not, we create a new entry in RegClassUnitSets as a
+ // "fake" register class.
+ for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits;
+ UnitIdx < UnitEnd; ++UnitIdx) {
+ std::vector<unsigned> RUSets;
+ for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) {
+ RegUnitSet &RUSet = RegUnitSets[i];
+ if (std::find(RUSet.Units.begin(), RUSet.Units.end(), UnitIdx)
+ == RUSet.Units.end())
+ continue;
+ RUSets.push_back(i);
+ }
+ unsigned RCUnitSetsIdx = 0;
+ for (unsigned e = RegClassUnitSets.size();
+ RCUnitSetsIdx != e; ++RCUnitSetsIdx) {
+ if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) {
+ break;
+ }
+ }
+ RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx;
+ if (RCUnitSetsIdx == RegClassUnitSets.size()) {
+ // Create a new list of UnitSets as a "fake" register class.
+ RegClassUnitSets.resize(RCUnitSetsIdx + 1);
+ RegClassUnitSets[RCUnitSetsIdx].swap(RUSets);
+ }
+ }
}
+struct LessUnits {
+ const CodeGenRegBank &RegBank;
+ LessUnits(const CodeGenRegBank &RB): RegBank(RB) {}
+
+ bool operator()(unsigned ID1, unsigned ID2) {
+ return RegBank.getRegPressureSet(ID1).Units.size()
+ < RegBank.getRegPressureSet(ID2).Units.size();
+ }
+};
+
void CodeGenRegBank::computeDerivedInfo() {
computeComposites();
computeSubRegIndexLaneMasks();
// Compute a unique set of RegUnitSets. One for each RegClass and inferred
// supersets for the union of overlapping sets.
computeRegUnitSets();
+
+ // Get the weight of each set.
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
+ RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units);
+
+ // Find the order of each set.
+ RegUnitSetOrder.reserve(RegUnitSets.size());
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
+ RegUnitSetOrder.push_back(Idx);
+
+ std::stable_sort(RegUnitSetOrder.begin(), RegUnitSetOrder.end(),
+ LessUnits(*this));
+ for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
+ RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
+ }
}
//
projects / oota-llvm.git / blobdiff