Subzero: Improve the memory-related performance of the register allocator.
Profiling indicated a noticeable amount of time spent on malloc/free related to the std::list<> implementation of UnorderedRanges. Therefore, we change the implementation to be std::vector<>, and up-front reserve a conservative amount of space to avoid expansion. The push_back() operation is always constant time with no allocation. Removing an element from the middle of the vector is done by swapping with the last element and then popping the last element, which is reasonable in principle because it is used as an unordered collection. Because of the swapping trick, the UnorderedRanges iterators are changed to iterate in reverse.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/781683002
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 2a30034..8a1656b 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -85,6 +85,7 @@
FindOverlap = true;
const VarList &Vars = Func->getVariables();
Unhandled.reserve(Vars.size());
+ UnhandledPrecolored.reserve(Vars.size());
// Gather the live ranges of all variables and add them to the
// Unhandled set.
for (Variable *Var : Vars) {
@@ -184,6 +185,7 @@
}
Unhandled.reserve(NumVars);
+ UnhandledPrecolored.reserve(NumVars);
for (SizeT i = 0; i < Vars.size(); ++i) {
Variable *Var = Vars[i];
if (LRBegin[i] != Inst::NumberSentinel) {
@@ -239,6 +241,10 @@
std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges());
std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(),
CompareRanges());
+
+ Handled.reserve(Unhandled.size());
+ Inactive.reserve(Unhandled.size());
+ Active.reserve(Unhandled.size());
}
// Implements the linear-scan algorithm. Based on "Linear Scan
@@ -276,7 +282,6 @@
assert(Active.empty());
assert(Inactive.empty());
assert(Handled.empty());
- UnorderedRanges::iterator Next;
const TargetLowering::RegSetMask RegsInclude =
TargetLowering::RegSet_CallerSave;
const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None;
@@ -319,10 +324,9 @@
}
// Check for active ranges that have expired or become inactive.
- for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
- Next = I;
- ++Next;
- Variable *Item = *I;
+ for (SizeT I = Active.size(); I > 0; --I) {
+ const SizeT Index = I - 1;
+ Variable *Item = Active[Index];
Item->trimLiveRange(Cur->getLiveRange().getStart());
bool Moved = false;
if (Item->rangeEndsBefore(Cur)) {
@@ -332,7 +336,7 @@
dumpLiveRange(Item, Func);
Str << "\n";
}
- Handled.splice(Handled.end(), Active, I);
+ moveItem(Active, Index, Handled);
Moved = true;
} else if (!Item->rangeOverlapsStart(Cur)) {
// Move Item from Active to Inactive list.
@@ -341,7 +345,7 @@
dumpLiveRange(Item, Func);
Str << "\n";
}
- Inactive.splice(Inactive.end(), Active, I);
+ moveItem(Active, Index, Inactive);
Moved = true;
}
if (Moved) {
@@ -354,10 +358,9 @@
}
// Check for inactive ranges that have expired or reactivated.
- for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
- Next = I;
- ++Next;
- Variable *Item = *I;
+ for (SizeT I = Inactive.size(); I > 0; --I) {
+ const SizeT Index = I - 1;
+ Variable *Item = Inactive[Index];
Item->trimLiveRange(Cur->getLiveRange().getStart());
if (Item->rangeEndsBefore(Cur)) {
// Move Item from Inactive to Handled list.
@@ -366,7 +369,7 @@
dumpLiveRange(Item, Func);
Str << "\n";
}
- Handled.splice(Handled.end(), Inactive, I);
+ moveItem(Inactive, Index, Handled);
} else if (Item->rangeOverlapsStart(Cur)) {
// Move Item from Inactive to Active list.
if (Verbose) {
@@ -374,7 +377,7 @@
dumpLiveRange(Item, Func);
Str << "\n";
}
- Active.splice(Active.end(), Inactive, I);
+ moveItem(Inactive, Index, Active);
// Increment Item in RegUses[].
assert(Item->hasRegTmp());
int32_t RegNum = Item->getRegNumTmp();
@@ -598,10 +601,9 @@
} else {
// Evict all live ranges in Active that register number
// MinWeightIndex is assigned to.
- for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
- Next = I;
- ++Next;
- Variable *Item = *I;
+ for (SizeT I = Active.size(); I > 0; --I) {
+ const SizeT Index = I - 1;
+ Variable *Item = Active[Index];
if (Item->getRegNumTmp() == MinWeightIndex) {
if (Verbose) {
Str << "Evicting ";
@@ -611,14 +613,13 @@
--RegUses[MinWeightIndex];
assert(RegUses[MinWeightIndex] >= 0);
Item->setRegNumTmp(Variable::NoRegister);
- Handled.splice(Handled.end(), Active, I);
+ moveItem(Active, Index, Handled);
}
}
// Do the same for Inactive.
- for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
- Next = I;
- ++Next;
- Variable *Item = *I;
+ for (SizeT I = Inactive.size(); I > 0; --I) {
+ const SizeT Index = I - 1;
+ Variable *Item = Inactive[Index];
// 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
@@ -636,7 +637,7 @@
Str << "\n";
}
Item->setRegNumTmp(Variable::NoRegister);
- Handled.splice(Handled.end(), Inactive, I);
+ moveItem(Inactive, Index, Handled);
}
}
// Assign the register to Cur.
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h
index 9b9992c..4ecae52 100644
--- a/src/IceRegAlloc.h
+++ b/src/IceRegAlloc.h
@@ -33,12 +33,24 @@
void dump(Cfg *Func) const;
private:
+ typedef std::vector<Variable *> OrderedRanges;
+ typedef std::vector<Variable *> UnorderedRanges;
+
void initForGlobal();
void initForInfOnly();
+ // Move an item from the From set to the To set. From[Index] is
+ // pushed onto the end of To[], then the item is efficiently removed
+ // from From[] by effectively swapping it with the last item in
+ // From[] and then popping it from the back. As such, the caller is
+ // best off iterating over From[] in reverse order to avoid the need
+ // for special handling of the iterator.
+ void moveItem(UnorderedRanges &From, SizeT Index, UnorderedRanges &To) {
+ To.push_back(From[Index]);
+ From[Index] = From.back();
+ From.pop_back();
+ }
Cfg *const Func;
- typedef std::vector<Variable *> OrderedRanges;
- typedef std::list<Variable *> UnorderedRanges;
OrderedRanges Unhandled;
// UnhandledPrecolored is a subset of Unhandled, specially collected
// for faster processing.
