Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(641)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/IceRegAlloc.cpp

Issue 1448773002: Subzero: Do some cleanup on the regalloc code. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Created 5 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | src/IceTargetLowering.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/IceRegAlloc.cpp
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index e6f3f560e4ad6fe5470d109ba0233a197abd57c0..14a3f295ff6fc0696e2635b9617de014e7771a84 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -49,19 +49,20 @@ void dumpDisableOverlap(const Cfg *Func, const Variable *Var,
const char *Reason) {
if (!BuildDefs::dump())
return;
- if (Func->isVerbose(IceV_LinearScan)) {
- VariablesMetadata *VMetadata = Func->getVMetadata();
- Ostream &Str = Func->getContext()->getStrDump();
- Str << "Disabling Overlap due to " << Reason << " " << *Var
- << " LIVE=" << Var->getLiveRange() << " Defs=";
- if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var))
- Str << FirstDef->getNumber();
- const InstDefList &Defs = VMetadata->getLatterDefinitions(Var);
- for (size_t i = 0; i < Defs.size(); ++i) {
- Str << "," << Defs[i]->getNumber();
- }
- Str << "\n";
+ if (!Func->isVerbose(IceV_LinearScan))
+ return;
+
+ VariablesMetadata *VMetadata = Func->getVMetadata();
+ Ostream &Str = Func->getContext()->getStrDump();
+ Str << "Disabling Overlap due to " << Reason << " " << *Var
+ << " LIVE=" << Var->getLiveRange() << " Defs=";
+ if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var))
+ Str << FirstDef->getNumber();
+ const InstDefList &Defs = VMetadata->getLatterDefinitions(Var);
+ for (size_t i = 0; i < Defs.size(); ++i) {
+ Str << "," << Defs[i]->getNumber();
}
+ Str << "\n";
}
void dumpLiveRange(const Variable *Var, const Cfg *Func) {
@@ -160,9 +161,8 @@ bool LinearScan::livenessValidateIntervals(
return false;
}
-// Prepare for very simple register allocation of only infinite-weight
-// Variables while respecting pre-colored Variables. Some properties we take
-// advantage of:
+// Prepare for very simple register allocation of only infinite-weight Variables
+// while respecting pre-colored Variables. Some properties we take advantage of:
//
// * Live ranges of interest consist of a single segment.
//
@@ -172,9 +172,9 @@ bool LinearScan::livenessValidateIntervals(
// lowered, or they don't contain any pre-colored or infinite-weight
// Variables.
//
-// * We don't need to renumber instructions before computing live ranges
-// because all the high-level ICE instructions are deleted prior to lowering,
-// and the low-level instructions are added in monotonically increasing order.
+// * We don't need to renumber instructions before computing live ranges because
+// all the high-level ICE instructions are deleted prior to lowering, and the
+// low-level instructions are added in monotonically increasing order.
//
// * There are no opportunities for register preference or allowing overlap.
//
@@ -183,8 +183,7 @@ bool LinearScan::livenessValidateIntervals(
// * Because live ranges are a single segment, the Inactive set will always be
// empty, and the live range trimming operation is unnecessary.
//
-// * Calculating overlap of single-segment live ranges could be optimized a
-// bit.
+// * Calculating overlap of single-segment live ranges could be optimized a bit.
void LinearScan::initForInfOnly() {
TimerMarker T(TimerStack::TT_initUnhandled, Func);
FindPreference = false;
@@ -350,10 +349,10 @@ void LinearScan::init(RegAllocKind Kind) {
}
// This is called when Cur must be allocated a register but no registers are
-// available across Cur's live range. To handle this, we find a register that
-// is not explicitly used during Cur's live range, spill that register to a
-// stack location right before Cur's live range begins, and fill (reload) the
-// register from the stack location right after Cur's live range ends.
+// available across Cur's live range. To handle this, we find a register that is
+// not explicitly used during Cur's live range, spill that register to a stack
+// location right before Cur's live range begins, and fill (reload) the register
+// from the stack location right after Cur's live range ends.
void LinearScan::addSpillFill(IterationState &Iter) {
// Identify the actual instructions that begin and end Iter.Cur's live range.
// Iterate through Iter.Cur's node's instruction list until we find the actual
@@ -385,9 +384,9 @@ void LinearScan::addSpillFill(IterationState &Iter) {
if (I->getNumber() == End)
FillPoint = I;
if (SpillPoint != E) {
- // Remove from RegMask any physical registers referenced during Cur's
- // live range. Start looking after SpillPoint gets set, i.e. once Cur's
- // live range begins.
+ // Remove from RegMask any physical registers referenced during Cur's live
+ // range. Start looking after SpillPoint gets set, i.e. once Cur's live
+ // range begins.
FOREACH_VAR_IN_INST(Var, *I) {
if (!Var->hasRegTmp())
continue;
@@ -407,9 +406,8 @@ void LinearScan::addSpillFill(IterationState &Iter) {
assert(RegNum != -1);
Iter.Cur->setRegNumTmp(RegNum);
Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType());
- // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that
- // SpillLoc is correctly identified as !isMultiBlock(), reducing stack frame
- // size.
+ // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc
+ // is correctly identified as !isMultiBlock(), reducing stack frame size.
Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType());
// Add "reg=FakeDef;spill=reg" before SpillPoint
Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg));
@@ -475,68 +473,67 @@ void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) {
}
// Infer register preference and allowable overlap. Only form a preference when
-// the current Variable has an unambiguous "first" definition. The preference
-// is some source Variable of the defining instruction that either is assigned
-// a register that is currently free, or that is assigned a register that is
-// not free but overlap is allowed. Overlap is allowed when the Variable under
-// consideration is single-definition, and its definition is a simple
-// assignment - i.e., the register gets copied/aliased but is never modified.
-// Furthermore, overlap is only allowed when preferred Variable definition
-// instructions do not appear within the current Variable's live range.
+// the current Variable has an unambiguous "first" definition. The preference is
+// some source Variable of the defining instruction that either is assigned a
+// register that is currently free, or that is assigned a register that is not
+// free but overlap is allowed. Overlap is allowed when the Variable under
+// consideration is single-definition, and its definition is a simple assignment
+// - i.e., the register gets copied/aliased but is never modified. Furthermore,
+// overlap is only allowed when preferred Variable definition instructions do
+// not appear within the current Variable's live range.
void LinearScan::findRegisterPreference(IterationState &Iter) {
Iter.Prefer = nullptr;
Iter.PreferReg = Variable::NoRegister;
Iter.AllowOverlap = false;
- if (FindPreference) {
- VariablesMetadata *VMetadata = Func->getVMetadata();
- if (const Inst *DefInst =
- VMetadata->getFirstDefinitionSingleBlock(Iter.Cur)) {
- assert(DefInst->getDest() == Iter.Cur);
- bool IsAssign = DefInst->isVarAssign();
- bool IsSingleDef = !VMetadata->isMultiDef(Iter.Cur);
- FOREACH_VAR_IN_INST(SrcVar, *DefInst) {
- // Only consider source variables that have (so far) been assigned a
- // register. That register must be one in the RegMask set, e.g. don't
- // try to prefer the stack pointer as a result of the stacksave
- // intrinsic.
- if (SrcVar->hasRegTmp()) {
- const llvm::SmallBitVector &Aliases =
- *RegAliases[SrcVar->getRegNumTmp()];
- const int32_t SrcReg = (Iter.RegMask & Aliases).find_first();
- const bool IsAliasAvailable = (SrcReg != -1);
- if (IsAliasAvailable) {
- if (FindOverlap && !Iter.Free[SrcReg]) {
- // Don't bother trying to enable AllowOverlap if the register is
- // already free.
- Iter.AllowOverlap = IsSingleDef && IsAssign &&
- !overlapsDefs(Func, Iter.Cur, SrcVar);
- }
- if (Iter.AllowOverlap || Iter.Free[SrcReg]) {
- Iter.Prefer = SrcVar;
- Iter.PreferReg = SrcReg;
- // Stop looking for a preference after the first valid preference
- // is found. One might think that we should look at all
- // instruction variables to find the best <Prefer,AllowOverlap>
- // combination, but note that AllowOverlap can only be true for a
- // simple assignment statement which can have only one source
- // operand, so it's not possible for AllowOverlap to be true
- // beyond the first source operand.
- FOREACH_VAR_IN_INST_BREAK;
- }
- }
- }
- }
- if (Verbose && Iter.Prefer) {
- Ostream &Str = Ctx->getStrDump();
- Str << "Initial Iter.Prefer=";
- Iter.Prefer->dump(Func);
- Str << " R=" << Iter.PreferReg
- << " LIVE=" << Iter.Prefer->getLiveRange()
- << " Overlap=" << Iter.AllowOverlap << "\n";
- }
+ if (!FindPreference)
+ return;
+
+ VariablesMetadata *VMetadata = Func->getVMetadata();
+ const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur);
+ if (DefInst == nullptr)
+ return;
+
+ assert(DefInst->getDest() == Iter.Cur);
+ const bool IsSingleDefAssign =
Jim Stichnoth 2015/11/15 18:24:42 IsAssign and IsSingleDef are combined into IsSingl
+ DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur);
+ FOREACH_VAR_IN_INST(SrcVar, *DefInst) {
+ // Only consider source variables that have (so far) been assigned a
+ // register.
+ if (!SrcVar->hasRegTmp())
+ continue;
+
+ // That register must be one in the RegMask set, e.g. don't try to prefer
+ // the stack pointer as a result of the stacksave intrinsic.
+ const llvm::SmallBitVector &Aliases = *RegAliases[SrcVar->getRegNumTmp()];
+ const int32_t SrcReg = (Iter.RegMask & Aliases).find_first();
+ if (SrcReg == -1)
+ continue;
+
+ if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) {
Jim Stichnoth 2015/11/15 18:24:42 Pull the IsSingleDefAssign test up here for slight
+ // Don't bother trying to enable AllowOverlap if the register is already
+ // free (hence the test on Iter.Free[SrcReg]).
+ Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar);
+ }
+ if (Iter.AllowOverlap || Iter.Free[SrcReg]) {
+ Iter.Prefer = SrcVar;
+ Iter.PreferReg = SrcReg;
+ // Stop looking for a preference after the first valid preference is
+ // found. One might think that we should look at all instruction
+ // variables to find the best <Prefer,AllowOverlap> combination, but note
+ // that AllowOverlap can only be true for a simple assignment statement
+ // which can have only one source operand, so it's not possible for
+ // AllowOverlap to be true beyond the first source operand.
+ FOREACH_VAR_IN_INST_BREAK;
}
}
+ if (BuildDefs::dump() && Verbose && Iter.Prefer) {
+ Ostream &Str = Ctx->getStrDump();
+ Str << "Initial Iter.Prefer=";
+ Iter.Prefer->dump(Func);
+ Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange()
+ << " Overlap=" << Iter.AllowOverlap << "\n";
+ }
}
// Remove registers from the Free[] list where an Inactive range overlaps with
@@ -554,8 +551,7 @@ void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) {
// AllowOverlap.
Iter.Free[RegAlias] = false;
// Disable AllowOverlap if an Inactive variable, which is not Prefer,
- // shares Prefer's register, and has a definition within Cur's live
- // range.
+ // shares Prefer's register, and has a definition within Cur's live range.
if (Iter.AllowOverlap && Item != Iter.Prefer &&
RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) {
Iter.AllowOverlap = false;
@@ -567,28 +563,28 @@ void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) {
// Remove registers from the Free[] list where an Unhandled pre-colored range
// overlaps with the current range, and set those registers to infinite weight
-// so that they aren't candidates for eviction. Cur->rangeEndsBefore(Item) is
-// an early exit check that turns a guaranteed O(N^2) algorithm into expected
+// so that they aren't candidates for eviction. Cur->rangeEndsBefore(Item) is an
+// early exit check that turns a guaranteed O(N^2) algorithm into expected
// linear complexity.
void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) {
for (Variable *Item : reverse_range(UnhandledPrecolored)) {
assert(Item->hasReg());
if (Iter.Cur->rangeEndsBefore(Item))
break;
- if (Item->rangeOverlaps(Iter.Cur)) {
- const llvm::SmallBitVector &Aliases =
- *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
- for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
- RegAlias = Aliases.find_next(RegAlias)) {
- Iter.Weights[RegAlias].setWeight(RegWeight::Inf);
- Iter.Free[RegAlias] = false;
- Iter.PrecoloredUnhandledMask[RegAlias] = true;
- // Disable Iter.AllowOverlap if the preferred register is one of these
- // pre-colored unhandled overlapping ranges.
- if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) {
- Iter.AllowOverlap = false;
- dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
- }
+ if (!Item->rangeOverlaps(Iter.Cur))
+ continue;
+ const llvm::SmallBitVector &Aliases =
+ *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp()
+ for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0;
+ RegAlias = Aliases.find_next(RegAlias)) {
+ Iter.Weights[RegAlias].setWeight(RegWeight::Inf);
+ Iter.Free[RegAlias] = false;
+ Iter.PrecoloredUnhandledMask[RegAlias] = true;
+ // Disable Iter.AllowOverlap if the preferred register is one of these
+ // pre-colored unhandled overlapping ranges.
+ if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) {
+ Iter.AllowOverlap = false;
+ dumpDisableOverlap(Func, Item, "PrecoloredUnhandled");
}
}
}
@@ -664,8 +660,7 @@ void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
}
}
- // All the weights are now calculated. Find the register with smallest
- // weight.
+ // All the weights are now calculated. Find the register with smallest weight.
int32_t MinWeightIndex = Iter.RegMask.find_first();
// MinWeightIndex must be valid because of the initial RegMask.any() test.
assert(MinWeightIndex >= 0);
@@ -713,10 +708,10 @@ void LinearScan::handleNoFreeRegisters(IterationState &Iter) {
// Note: The Item->rangeOverlaps(Cur) clause is not part of the
// description of AssignMemLoc() in the original paper. But there doesn't
// seem to be any need to evict an inactive live range that doesn't
- // overlap with the live range currently being considered. It's
- // especially bad if we would end up evicting an infinite-weight but
- // currently-inactive live range. The most common situation for this
- // would be a scratch register kill set for call instructions.
+ // overlap with the live range currently being considered. It's especially
+ // bad if we would end up evicting an infinite-weight but
+ // currently-inactive live range. The most common situation for this would
+ // be a scratch register kill set for call instructions.
if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) {
dumpLiveRangeTrace("Evicting I ", Item);
Item->setRegNumTmp(Variable::NoRegister);
@@ -762,7 +757,7 @@ void LinearScan::assignFinalRegisters(
if (Randomized && Item->hasRegTmp() && !Item->hasReg()) {
AssignedRegNum = Permutation[RegNum];
}
- if (Verbose) {
+ if (BuildDefs::dump() && Verbose) {
Ostream &Str = Ctx->getStrDump();
if (!Item->hasRegTmp()) {
Str << "Not assigning ";
@@ -785,8 +780,8 @@ void LinearScan::assignFinalRegisters(
// Allocation in the Context of SSA Form and Register Constraints" by Hanspeter
// Mössenböck and Michael Pfeiffer,
// ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is
-// modified to take affinity into account and allow two interfering variables
-// to share the same register in certain cases.
+// modified to take affinity into account and allow two interfering variables to
+// share the same register in certain cases.
//
// Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results
// are assigned to Variable::RegNum for each Variable.
@@ -809,12 +804,11 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
LiveRange KillsRange(Kills);
KillsRange.untrim();
- // Reset the register use count
+ // Reset the register use count.
RegUses.resize(NumRegisters);
std::fill(RegUses.begin(), RegUses.end(), 0);
- // Unhandled is already set to all ranges in increasing order of start
- // points.
+ // Unhandled is already set to all ranges in increasing order of start points.
assert(Active.empty());
assert(Inactive.empty());
assert(Handled.empty());
@@ -824,7 +818,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
const llvm::SmallBitVector KillsMask =
Target->getRegisterSet(RegsInclude, RegsExclude);
- // Allocate memory once outside the loop
+ // Allocate memory once outside the loop.
IterationState Iter;
Iter.Weights.reserve(NumRegisters);
Iter.PrecoloredUnhandledMask.reserve(NumRegisters);
@@ -894,7 +888,7 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
}
// Print info about physical register availability.
- if (Verbose) {
+ if (BuildDefs::dump() && Verbose) {
Ostream &Str = Ctx->getStrDump();
for (SizeT i = 0; i < Iter.RegMask.size(); ++i) {
if (Iter.RegMask[i]) {
@@ -907,15 +901,15 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
}
if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) {
- // First choice: a preferred register that is either free or is allowed
- // to overlap with its linked variable.
+ // First choice: a preferred register that is either free or is allowed to
+ // overlap with its linked variable.
allocatePreferredRegister(Iter);
} else if (Iter.Free.any()) {
// Second choice: any free register.
allocateFreeRegister(Iter);
} else {
- // Fallback: there are no free registers, so we look for the
- // lowest-weight register and see if Cur has higher weight.
+ // Fallback: there are no free registers, so we look for the lowest-weight
+ // register and see if Cur has higher weight.
handleNoFreeRegisters(Iter);
}
dump(Func);
@@ -930,16 +924,6 @@ void LinearScan::scan(const llvm::SmallBitVector &RegMaskFull,
assignFinalRegisters(RegMaskFull, PreDefinedRegisters, Randomized);
- // TODO: Consider running register allocation one more time, with infinite
- // registers, for two reasons. First, evicted live ranges get a second chance
- // for a register. Second, it allows coalescing of stack slots. If there is
- // no time budget for the second register allocation run, each unallocated
- // variable just gets its own slot.
- //
- // Another idea for coalescing stack slots is to initialize the Unhandled
- // list with just the unallocated variables, saving time but not offering
- // second-chance opportunities.
-
if (Verbose)
Ctx->unlockStr();
}
@@ -961,7 +945,7 @@ void LinearScan::dumpLiveRangeTrace(const char *Label, const Variable *Item) {
void LinearScan::dump(Cfg *Func) const {
if (!BuildDefs::dump())
return;
- if (!Func->isVerbose(IceV_LinearScan))
+ if (Verbose)
return;
Ostream &Str = Func->getContext()->getStrDump();
Func->resetCurrentNode();
« no previous file with comments | « no previous file | src/IceTargetLowering.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698