Subzero: Translation-time improvements in the register allocator.

Subzero: Translation-time improvements in the register allocator.

1. Use a sorted std::vector instead of std::set to improve management
of the Unhandled sets.  This is the main performance gain.

2. Use std::list.splice() to move items between lists, instead of
erase()+push_back().  This doesn't really save much, but the intention
is somewhat clearer.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-10-13 21:27:05]

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

[Jim Stichnoth, 2014-10-13 21:28:08]

This gives at least 5% gain in most cases, sometimes more than 10%.

[jvoung (off chromium), 2014-10-13 21:41:50]

lgtm

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

https://codereview.chromium.org/642603005/diff/1/src/IceRegAlloc.cpp#newcode96
src/IceRegAlloc.cpp:96: // Unhandled set.  TODO: Unhandled is a set<> which is
based on a
Could remove comment about Unhandled being a set<>

https://codereview.chromium.org/642603005/diff/1/src/IceRegAlloc.cpp#newcode124
src/IceRegAlloc.cpp:124: // Do a reverse sort so that erasing elements (from the
end) is
Can the comment fit on one line?

https://codereview.chromium.org/642603005/diff/1/src/IceRegAlloc.cpp#newcode570
src/IceRegAlloc.cpp:570: for (const LiveRangeWrapper &Item : Unhandled) {
Maybe iterate over Unhandled in reverse to preserve the old printing order?

[Jim Stichnoth, 2014-10-13 23:21:03]

Committed patchset #2 (id:80001) manually as
e22f823680ec21304509c1ebcee119cb843f5e76 (presubmit successful).

[Jim Stichnoth, 2014-10-13 23:40:31]

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

https://codereview.chromium.org/642603005/diff/1/src/IceRegAlloc.cpp#newcode96
src/IceRegAlloc.cpp:96: // Unhandled set.  TODO: Unhandled is a set<> which is
based on a
On 2014/10/13 21:41:50, jvoung wrote:
> Could remove comment about Unhandled being a set<>

Removed the TODO altogether, as I think this is now the best overall approach.

https://codereview.chromium.org/642603005/diff/1/src/IceRegAlloc.cpp#newcode124
src/IceRegAlloc.cpp:124: // Do a reverse sort so that erasing elements (from the
end) is
On 2014/10/13 21:41:50, jvoung wrote:
> Can the comment fit on one line?

Done.  (overriding emacs's default preferences :) )