//
//===----------------------------------------------------------------------===//
+#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)
-{}
-
-std::string CodeGenSubRegIndex::getNamespace() const {
- if (TheDef->getValue("Namespace"))
- return TheDef->getValueAsString("Namespace");
- else
- return "";
+ : 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");
}
-const std::string &CodeGenSubRegIndex::getName() const {
- return TheDef->getName();
+CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,
+ unsigned Enum)
+ : TheDef(0), Name(N), Namespace(Nspace), Size(-1), Offset(-1),
+ EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) {
}
std::string CodeGenSubRegIndex::getQualifiedName() const {
}
void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) {
- std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf");
- if (Comps.empty())
+ if (!TheDef)
return;
- if (Comps.size() != 2)
- throw TGError(TheDef->getLoc(), "ComposedOf must have exactly two entries");
- CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);
- CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);
- CodeGenSubRegIndex *X = A->addComposite(B, this);
- if (X)
- throw TGError(TheDef->getLoc(), "Ambiguous ComposedOf entries");
-}
-void CodeGenSubRegIndex::cleanComposites() {
- // Clean out redundant mappings of the form this+X -> X.
- for (CompMap::iterator i = Composed.begin(), e = Composed.end(); i != e;) {
- CompMap::iterator j = i;
- ++i;
- if (j->first == j->second)
- Composed.erase(j);
+ std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf");
+ if (!Comps.empty()) {
+ if (Comps.size() != 2)
+ PrintFatalError(TheDef->getLoc(),
+ "ComposedOf must have exactly two entries");
+ CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);
+ CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);
+ CodeGenSubRegIndex *X = A->addComposite(B, this);
+ if (X)
+ PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries");
+ }
+
+ std::vector<Record*> Parts =
+ TheDef->getValueAsListOfDefs("CoveringSubRegIndices");
+ if (!Parts.empty()) {
+ if (Parts.size() < 2)
+ PrintFatalError(TheDef->getLoc(),
+ "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]));
+ RegBank.addConcatSubRegIndex(IdxParts, this);
}
}
+unsigned CodeGenSubRegIndex::computeLaneMask() {
+ // Already computed?
+ if (LaneMask)
+ return LaneMask;
+
+ // Recursion guard, shouldn't be required.
+ LaneMask = ~0u;
+
+ // The lane mask is simply the union of all sub-indices.
+ unsigned M = 0;
+ for (CompMap::iterator I = Composed.begin(), E = Composed.end(); I != E; ++I)
+ M |= I->second->computeLaneMask();
+ assert(M && "Missing lane mask, sub-register cycle?");
+ LaneMask = M;
+ return LaneMask;
+}
+
//===----------------------------------------------------------------------===//
// CodeGenRegister
//===----------------------------------------------------------------------===//
EnumValue(Enum),
CostPerUse(R->getValueAsInt("CostPerUse")),
CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")),
+ NumNativeRegUnits(0),
SubRegsComplete(false),
SuperRegsComplete(false),
TopoSig(~0u)
std::vector<Record*> SRs = TheDef->getValueAsListOfDefs("SubRegs");
if (SRIs.size() != SRs.size())
- throw TGError(TheDef->getLoc(),
- "SubRegs and SubRegIndices must have the same size");
+ PrintFatalError(TheDef->getLoc(),
+ "SubRegs and SubRegIndices must have the same size");
for (unsigned i = 0, e = SRIs.size(); i != e; ++i) {
ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i]));
if (CoveredBySubRegs && !ExplicitSubRegs.empty())
ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this);
- // Add ad hoc alias links. This is a symmetric relationship betwen two
+ // Add ad hoc alias links. This is a symmetric relationship between two
// registers, so build a symmetric graph by adding links in both ends.
std::vector<Record*> Aliases = TheDef->getValueAsListOfDefs("Aliases");
for (unsigned i = 0, e = Aliases.size(); i != e; ++i) {
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.
CodeGenRegister *SR = I->second;
- if (SR == this)
- continue;
// Merge the subregister's units into this register's RegUnits.
mergeRegUnits(RegUnits, SR->RegUnits);
}
CodeGenRegister *SR = ExplicitSubRegs[i];
CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i];
if (!SubRegs.insert(std::make_pair(Idx, SR)).second)
- throw TGError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() +
- " appears twice in Register " + getName());
+ PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() +
+ " appears twice in Register " + getName());
// Map explicit sub-registers first, so the names take precedence.
// The inherited sub-registers are mapped below.
SubReg2Idx.insert(std::make_pair(SR, Idx));
}
}
- // Process the composites.
- ListInit *Comps = TheDef->getValueAsListInit("CompositeIndices");
- for (unsigned i = 0, e = Comps->size(); i != e; ++i) {
- DagInit *Pat = dynamic_cast<DagInit*>(Comps->getElement(i));
- if (!Pat)
- throw TGError(TheDef->getLoc(), "Invalid dag '" +
- Comps->getElement(i)->getAsString() +
- "' in CompositeIndices");
- DefInit *BaseIdxInit = dynamic_cast<DefInit*>(Pat->getOperator());
- if (!BaseIdxInit || !BaseIdxInit->getDef()->isSubClassOf("SubRegIndex"))
- throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " +
- Pat->getAsString());
- CodeGenSubRegIndex *BaseIdx = RegBank.getSubRegIdx(BaseIdxInit->getDef());
-
- // Resolve list of subreg indices into R2.
- CodeGenRegister *R2 = this;
- for (DagInit::const_arg_iterator di = Pat->arg_begin(),
- de = Pat->arg_end(); di != de; ++di) {
- DefInit *IdxInit = dynamic_cast<DefInit*>(*di);
- if (!IdxInit || !IdxInit->getDef()->isSubClassOf("SubRegIndex"))
- throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " +
- Pat->getAsString());
- CodeGenSubRegIndex *Idx = RegBank.getSubRegIdx(IdxInit->getDef());
- const SubRegMap &R2Subs = R2->computeSubRegs(RegBank);
- SubRegMap::const_iterator ni = R2Subs.find(Idx);
- if (ni == R2Subs.end())
- throw TGError(TheDef->getLoc(), "Composite " + Pat->getAsString() +
- " refers to bad index in " + R2->getName());
- R2 = ni->second;
- }
-
- // Insert composite index. Allow overriding inherited indices etc.
- SubRegs[BaseIdx] = R2;
-
- // R2 is no longer an orphan.
- Orphans.erase(R2);
- }
-
// Now Orphans contains the inherited subregisters without a direct index.
// Create inferred indexes for all missing entries.
// Work backwards in the Indices vector in order to compose subregs bottom-up.
// dsub_2 -> ssub_0
//
// We pick the latter composition because another register may have [dsub_0,
- // dsub_1, dsub_2] subregs without neccessarily having a qsub_1 subreg. The
+ // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The
// dsub_2 -> ssub_0 composition can be shared.
while (!Indices.empty() && !Orphans.empty()) {
CodeGenSubRegIndex *Idx = Indices.pop_back_val();
// Compute the inverse SubReg -> Idx map.
for (SubRegMap::const_iterator SI = SubRegs.begin(), SE = SubRegs.end();
SI != SE; ++SI) {
- // Ignore idempotent sub-register indices.
- if (SI->second == this)
+ if (SI->second == this) {
+ ArrayRef<SMLoc> Loc;
+ if (TheDef)
+ Loc = TheDef->getLoc();
+ 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;
+ if (Ins->second == SI->first)
continue;
- // Is is possible to have multiple names for the same sub-register.
- // For example, XMM0 appears as sub_xmm, sub_sd, and sub_ss in YMM0.
- // Eventually, this degeneration should go away, but for now we simply give
- // precedence to the explicit sub-register index over the inherited ones.
- SubReg2Idx.insert(std::make_pair(SI->second, SI->first));
+ // Trouble: Two different names for SI->second.
+ ArrayRef<SMLoc> Loc;
+ if (TheDef)
+ Loc = TheDef->getLoc();
+ PrintFatalError(Loc, "Sub-register can't have two names: " +
+ SI->second->getName() + " available as " +
+ SI->first->getName() + " and " + Ins->second->getName());
}
// Derive possible names for sub-register concatenations from any explicit
if (RegUnits.empty())
RegUnits.push_back(RegBank.newRegUnit(this));
+ // We have now computed the native register units. More may be adopted later
+ // for balancing purposes.
+ NumNativeRegUnits = RegUnits.size();
+
return SubRegs;
}
SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) {
CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second);
if (!SubIdx)
- throw TGError(TheDef->getLoc(), "No SubRegIndex for " +
- SI->second->getName() + " in " + getName());
+ PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " +
+ SI->second->getName() + " in " + getName());
NewIdx->addComposite(SI->first, SubIdx);
}
}
Id.push_back(I->first->EnumValue);
Id.push_back(I->second->TopoSig);
- if (I->second == this)
- continue;
// Don't add duplicate entries.
if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this)
continue;
// Add any secondary sub-registers that weren't part of the explicit tree.
for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
I != E; ++I)
- if (I->second != this)
- 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());
- }
- }
+ OSet.insert(I->second);
}
// Get the sum of this register's unit weights.
unsigned Dim = Indices.size();
ListInit *SubRegs = Def->getValueAsListInit("SubRegs");
if (Dim != SubRegs->getSize())
- throw TGError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch");
+ PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch");
if (Dim < 2)
- throw TGError(Def->getLoc(), "Tuples must have at least 2 sub-registers");
+ PrintFatalError(Def->getLoc(),
+ "Tuples must have at least 2 sub-registers");
// Evaluate the sub-register lists to be zipped.
unsigned Length = ~0u;
SmallVector<SetTheory::RecSet, 4> Lists(Dim);
for (unsigned i = 0; i != Dim; ++i) {
- ST.evaluate(SubRegs->getElement(i), Lists[i]);
+ ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc());
Length = std::min(Length, unsigned(Lists[i].size()));
}
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");
for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
Record *Type = TypeList[i];
if (!Type->isSubClassOf("ValueType"))
- throw "RegTypes list member '" + Type->getName() +
- "' does not derive from the ValueType class!";
+ PrintFatalError("RegTypes list member '" + Type->getName() +
+ "' does not derive from the ValueType class!");
VTs.push_back(getValueType(Type));
}
assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!");
// Alternative allocation orders may be subsets.
SetTheory::RecSet Order;
for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) {
- RegBank.getSets().evaluate(AltOrders->getElement(i), Order);
+ RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc());
Orders[1 + i].append(Order.begin(), Order.end());
// Verify that all altorder members are regclass members.
while (!Order.empty()) {
CodeGenRegister *Reg = RegBank.getReg(Order.back());
Order.pop_back();
if (!contains(Reg))
- throw TGError(R->getLoc(), " AltOrder register " + Reg->getName() +
+ PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() +
" is not a class member");
}
}
unsigned Size = R->getValueAsInt("Size");
Namespace = R->getValueAsString("Namespace");
- SpillSize = Size ? Size : EVT(VTs[0]).getSizeInBits();
+ SpillSize = Size ? Size : MVT(VTs[0]).getSizeInBits();
SpillAlignment = R->getValueAsInt("Alignment");
CopyCost = R->getValueAsInt("CopyCost");
Allocatable = R->getValueAsBit("isAllocatable");
/// Register classes with the same registers, spill size, and alignment form a
/// clique. They will be ordered alphabetically.
///
-static int TopoOrderRC(const void *PA, const void *PB) {
- const CodeGenRegisterClass *A = *(const CodeGenRegisterClass* const*)PA;
- const CodeGenRegisterClass *B = *(const CodeGenRegisterClass* const*)PB;
+static int TopoOrderRC(CodeGenRegisterClass *const *PA,
+ CodeGenRegisterClass *const *PB) {
+ const CodeGenRegisterClass *A = *PA;
+ const CodeGenRegisterClass *B = *PB;
if (A == B)
return 0;
RC.SubClasses |= SubRC->SubClasses;
}
- // Sweep up missed clique members. They will be immediately preceeding RC.
+ // Sweep up missed clique members. They will be immediately preceding RC.
for (unsigned s = rci - 1; s && testSubClass(&RC, RegClasses[s - 1]); --s)
RC.SubClasses.set(s - 1);
}
// CodeGenRegBank
//===----------------------------------------------------------------------===//
-CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
+CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) {
// Configure register Sets to understand register classes and tuples.
Sets.addFieldExpander("RegisterClass", "MemberList");
Sets.addFieldExpander("CalleeSavedRegs", "SaveList");
// More indices will be synthesized later.
std::vector<Record*> SRIs = Records.getAllDerivedDefinitions("SubRegIndex");
std::sort(SRIs.begin(), SRIs.end(), LessRecord());
- NumNamedIndices = SRIs.size();
for (unsigned i = 0, e = SRIs.size(); i != e; ++i)
getSubRegIdx(SRIs[i]);
// Build composite maps from ComposedOf fields.
// 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
for (unsigned i = 0, e = Registers.size(); i != e; ++i)
Registers[i]->buildObjectGraph(*this);
+ // Compute register name map.
+ for (unsigned i = 0, e = Registers.size(); i != e; ++i)
+ RegistersByName.GetOrCreateValue(
+ Registers[i]->TheDef->getValueAsString("AsmName"),
+ Registers[i]);
+
// Precompute all sub-register maps.
// This will create Composite entries for all inferred sub-register indices.
for (unsigned i = 0, e = Registers.size(); i != e; ++i)
// Read in register class definitions.
std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
if (RCs.empty())
- throw std::string("No 'RegisterClass' subclasses defined!");
+ PrintFatalError(std::string("No 'RegisterClass' subclasses defined!"));
// Allocate user-defined register classes.
RegClasses.reserve(RCs.size());
CodeGenRegisterClass::computeSubClasses(*this);
}
+// Create a synthetic CodeGenSubRegIndex without a corresponding Record.
+CodeGenSubRegIndex*
+CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) {
+ CodeGenSubRegIndex *Idx = new CodeGenSubRegIndex(Name, Namespace,
+ SubRegIndices.size() + 1);
+ SubRegIndices.push_back(Idx);
+ return Idx;
+}
+
CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) {
CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def];
if (Idx)
if (CodeGenRegisterClass *RC = Def2RC[Def])
return RC;
- throw TGError(Def->getLoc(), "Not a known RegisterClass!");
+ PrintFatalError(Def->getLoc(), "Not a known RegisterClass!");
}
CodeGenSubRegIndex*
// None exists, synthesize one.
std::string Name = A->getName() + "_then_" + B->getName();
- Comp = getSubRegIdx(new Record(Name, SMLoc(), Records));
+ Comp = createSubRegIndex(Name, A->getNamespace());
A->addComposite(B, Comp);
return Comp;
}
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 = getSubRegIdx(new Record(Name, SMLoc(), Records));
+ Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
+ Idx->Size = Size;
+ Idx->Offset = isContinuous ? Parts.front()->Offset : -1;
+ return Idx;
}
void CodeGenRegBank::computeComposites() {
}
}
}
+}
- // We don't care about the difference between (Idx1, Idx2) -> Idx2 and invalid
- // compositions, so remove any mappings of that form.
- for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i)
- SubRegIndices[i]->cleanComposites();
+// Compute lane masks. This is similar to register units, but at the
+// sub-register index level. Each bit in the lane mask is like a register unit
+// class, and two lane masks will have a bit in common if two sub-register
+// indices overlap in some register.
+//
+// Conservatively share a lane mask bit if two sub-register indices overlap in
+// some registers, but not in others. That shouldn't happen a lot.
+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.
+ //
+ // 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;
+ }
+ }
+
+ // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented
+ // 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) {
+ 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 weight for each register unit created during getSubRegs.
// This may create adopted register units (with unit # >= NumNativeRegUnits).
// 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;
+ }
}
//