Subzero: Improve regalloc performance by optimizing UnhandledPrecolored.

Subzero: Improve regalloc performance by optimizing UnhandledPrecolored.

A lot of time was being spent in the two loops that check precolored ranges in the Unhandled set, specifically in the endsBefore() check.

Solve this by keeping a shadow copy of Unhandled, restricted to the ranges that are precolored.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-10-02 14:06:47]

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

[Jim Stichnoth, 2014-10-02 14:09:37]

This improves 176.gcc translation time by almost 10%.

[jvoung (off chromium), 2014-10-02 16:08:18]

cool!

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

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: continue;
Tiny nit: I don't know if it saves anything to make a single Foo =
LiveRangeWrapper(Var);

and then Unhandled.insert(Foo); if (...) { UnhandlePrecolored.insert(Foo); }

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode324
src/IceRegAlloc.cpp:324: if (Item.overlaps(Cur)) {
Any idea if overlaps() is more expensive, or checking if !(Free[R] &&
PrecoloredUnhandledMask[R] && AllowOverlap) is more expensive?

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode400
src/IceRegAlloc.cpp:400: if (Item.overlaps(Cur)) {
Does this loop find the same set of Items which overlap Cur as the earlier loop?
Wondering if we could do something with that.

[jvoung (off chromium), 2014-10-02 17:00:06]

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

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: continue;
On 2014/10/02 16:08:18, jvoung wrote:
> Tiny nit: I don't know if it saves anything to make a single Foo =
> LiveRangeWrapper(Var);
> 
> and then Unhandled.insert(Foo); if (...) { UnhandlePrecolored.insert(Foo); }
> 

Ah maybe not -- there's probably something with move semantics that would make
it fine/better the way you had it.

[Jim Stichnoth, 2014-10-02 19:41:48]

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

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: continue;
On 2014/10/02 16:08:18, jvoung wrote:
> Tiny nit: I don't know if it saves anything to make a single Foo =
> LiveRangeWrapper(Var);
> 
> and then Unhandled.insert(Foo); if (...) { UnhandlePrecolored.insert(Foo); }
> 

Done.  Probably doesn't affect performance, but it improves clarity.

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: continue;
On 2014/10/02 17:00:06, jvoung wrote:
> On 2014/10/02 16:08:18, jvoung wrote:
> > Tiny nit: I don't know if it saves anything to make a single Foo =
> > LiveRangeWrapper(Var);
> > 
> > and then Unhandled.insert(Foo); if (...) { UnhandlePrecolored.insert(Foo); }
> > 
> 
> Ah maybe not -- there's probably something with move semantics that would make
> it fine/better the way you had it.

Well, I still like it better your way. :)

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode324
src/IceRegAlloc.cpp:324: if (Item.overlaps(Cur)) {
On 2014/10/02 16:08:18, jvoung wrote:
> Any idea if overlaps() is more expensive, or checking if !(Free[R] &&
> PrecoloredUnhandledMask[R] && AllowOverlap) is more expensive?

I don't think that would be worth it:

1. After combining the similar loop below with this one, the overlaps() check
will almost always have to be done anyway.

2. I'm not sure if there's a good way to cleanly express the rearrangement of
the logic.

3. The potential benefit seems limited to the handful of percent reported below
(though that might grow once more low-hanging fruit is dealt with).

https://codereview.chromium.org/622553003/diff/1/src/IceRegAlloc.cpp#newcode400
src/IceRegAlloc.cpp:400: if (Item.overlaps(Cur)) {
On 2014/10/02 16:08:18, jvoung wrote:
> Does this loop find the same set of Items which overlap Cur as the earlier
loop?
> Wondering if we could do something with that.

Nice!  We can pull Weights[] earlier in the loop and preset the pre-colored
weights to Inf, and avoid this loop entirely.

With the change from iterating over Unhandled to iterating over
UnhandledPrecolored, the gain isn't so much, but it still looks like a handful
of percent improvement on 176.gcc.

[jvoung (off chromium), 2014-10-02 19:52:21]

LGTM

[Jim Stichnoth, 2014-10-02 19:58:30]

Committed patchset #2 (id:20001) manually as
541ba667f21a4f21a4d8d68e685d522bd0005bea (presubmit successful).