Subzero: Improve the memory-related performance of the register allocator.

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

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=4ead35a7e6d1d04d8cab5db23299fb5c2fe1943d

[Jim Stichnoth, 2014-12-04 01:10:11]

stichnot@chromium.org changed reviewers:
+ jvoung@chromium.org

[Jim Stichnoth, 2014-12-04 01:14:13]

This looks like about 2% gain on translating pnacl-llc.pexe.

[jvoung (off chromium), 2014-12-04 02:46:44]

cool LGTM otherwise

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp#newcode222
src/IceRegAlloc.cpp:222: Inactive.reserve(Unhandled.size());
Should this be after initForGlobal/initForInfOnly?

Otherwise, Unhandled.size() is still 0?

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp#newcode327
src/IceRegAlloc.cpp:327: Variable *Item = Active[I - 1];
Maybe initialize I to Active.size() - 1, and go up to I >= 0, then the indexing
doesn't have to be I-1?

[Jim Stichnoth, 2014-12-04 04:25:17]

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp#newcode222
src/IceRegAlloc.cpp:222: Inactive.reserve(Unhandled.size());
On 2014/12/04 02:46:44, jvoung wrote:
> Should this be after initForGlobal/initForInfOnly?
> 
> Otherwise, Unhandled.size() is still 0?

Done, thanks!

https://codereview.chromium.org/781683002/diff/1/src/IceRegAlloc.cpp#newcode327
src/IceRegAlloc.cpp:327: Variable *Item = Active[I - 1];
On 2014/12/04 02:46:44, jvoung wrote:
> Maybe initialize I to Active.size() - 1, and go up to I >= 0, then the
indexing
> doesn't have to be I-1?

SizeT is unsigned (uint32_t), so I>=0 is always true...  That's why I used the
clumsy I-1 pattern.

After some thought, changed it to use "const SizeT Index = I - 1;".

[Jim Stichnoth, 2014-12-04 04:30:43]

Committed patchset #2 (id:20001) manually as
4ead35a7e6d1d04d8cab5db23299fb5c2fe1943d (presubmit successful).