Subzero: Implement "second-chance bin-packing" for register allocation.

Subzero: Implement "second-chance bin-packing" for register allocation.

If a variable gets a register but is later evicted because of a higher-weight variable, there's a chance that the first variable could have been allocated a register if only its initial choice had been different.

To improve this, we keep track of which variables are evicted, and then allow register allocation to run again, focusing only on those once-evicted variables, and not changing any previous register assignments.

This can iterate until there are no more evictions.

This is more or less what the linear-scan literature describes as "second-chance bin-packing".

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4095
R=jpp@chromium.org

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

[Jim Stichnoth, 2015-10-08 19:48:16]

stichnot@chromium.org changed reviewers:
+ jpp@chromium.org, kschimpf@google.com, sehr@google.com

[Jim Stichnoth, 2015-10-09 20:07:36]

Ping.  I'm especially keen on this since it gives a 10% improvement on bzip2.

If my documentation is lacking and it's hard to understand what's going on, let
me know and I'll try to fix that.

[John, 2015-10-09 20:13:04]

lgtm

Here's an idea (future work): why not splitting the live ranges that were
evicted, and then rerun the register allocator? Do you think the split ranges
would help?

https://chromiumcodereview.appspot.com/1395693005/diff/1/src/IceClFlags.h
File src/IceClFlags.h (right):

https://chromiumcodereview.appspot.com/1395693005/diff/1/src/IceClFlags.h#new...
src/IceClFlags.h:109: bool shouldRegAllocRepeat() const { return RegAllocRepeat;
}
This reads a bit funny to me... maybe shouldRepeatRegAlloc?

[Jim Stichnoth, 2015-10-09 21:33:07]

I also added "REQUIRES: allow_dump" to the new ret.ll test.

https://chromiumcodereview.appspot.com/1395693005/diff/1/src/IceClFlags.h
File src/IceClFlags.h (right):

https://chromiumcodereview.appspot.com/1395693005/diff/1/src/IceClFlags.h#new...
src/IceClFlags.h:109: bool shouldRegAllocRepeat() const { return RegAllocRepeat;
}
On 2015/10/09 20:13:04, John wrote:
> This reads a bit funny to me... maybe shouldRepeatRegAlloc?

Good point.  I changed all that to be RepeatRegAlloc.  Except for the
command-line argument string, I stuck with -regalloc-repeat for the hierarchical
aspect.

[Jim Stichnoth, 2015-10-09 21:33:30]

Committed patchset #2 (id:20001) manually as
4001c9394cade69a60a6b798b7ece891f3b68abb (presubmit successful).

[Jim Stichnoth, 2015-10-11 15:25:34]

On 2015/10/09 20:13:04, John wrote:
> lgtm
> 
> Here's an idea (future work): why not splitting the live ranges that were
> evicted, and then rerun the register allocator? Do you think the split ranges
> would help?

Yes, I think live range splitting will have to be done in the future.

We'll need some new machinery to enable this, since variables are assumed to
have a single register and a single live range.  There's also the question of
whether to do splitting and retrying as part of the register allocation pass, or
treat it as regalloc->split->regalloc as you suggest.

In the short term, I'm more likely to first try a post-regalloc pass that tracks
register/variable availability across a basic block, to reduce unnecessary loads
from the stack.

But, doing a proper live range splitting algorithm such as LLVM's Greedy
allocator should make it possible to remove these availability peephole
optimizations.