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.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.
