Greedy allocator: perf work

Greedy allocator: Considering conflicts when deciding where to split a
losing range. Some weight calculation tuning. Rudimentary allocator
statistics. Helper flags to aid tuning (plan is to remove them once
tuning completes).

BUG=

[Mircea Trofin, 2015-05-10 18:21:14]

mtrofin@chromium.org changed reviewers:
+ jarin@chromium.org

[Mircea Trofin, 2015-05-10 18:22:41]

Updates to the greedy allocator. The main progress here is that the bots testing
this should pass; I'm still chasing perf.

[Mircea Trofin, 2015-05-11 02:23:37]

Not sure if the new bots (running the tests under the "--turbo_greedy_regalloc"
flag) are included. Added Michael.

[Michael Achenbach, 2015-05-12 10:29:51]

On 2015/05/11 02:23:37, Mircea Trofin wrote:
> Not sure if the new bots (running the tests under the
"--turbo_greedy_regalloc"
> flag) are included. Added Michael.

Nope - no trybots yet - I can add some. Note that also the perf tries don't use
the greedy allocator.

[Michael Achenbach, 2015-05-12 12:56:00]

I added trybots and started them on this CL. But they won't be used by default
by the CQ. See here how to add them in your CLs
https://www.chromium.org/developers/testing/commit-queue - CQ_INCLUDE_TRYBOTS

[Jarin, 2015-05-13 13:12:57]

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:52: if (block->loop_header().IsValid())
return 1;
Can't you use block->IsLoopHeader()?

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:54: if (block->PredecessorCount() == 0)
Style nit: only omit the parentheses if the statement fits on one line.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:58: sequence,
sequence->InstructionBlockAt(block->predecessors()[0]));
Can we get rid of the recursion?

More importantly, what is it supposed to compute?

At the moment, it only returns 0 or 1, that seems wrong.

Moreover, by walking up the predecessor chain you could get into a loop and then
return 1 even if the starting block was not in a loop. That does not seem right
either.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2593: auto half = ipow(b, rem);
If you wrote this function for efficiency, then you should not use recursion
here.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2622: use_count += last_use_count * ipow(2,
last_loop_count);
ipow(2, x) --> 1 << x?

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2628: use_count += last_use_count * ipow(2,
last_loop_count);
ipow(2, x) --> 1 << x?

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2845: // DCHECK(split_pos.IsValid());
Remove.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2895: return LifetimePosition::Invalid();
How can this happen?

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:2931: if (start < pos && pos < end) return
true;
return start < pos && pos < end;

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.cc:3625: // #include "../prints.inc"
Remove this line.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:744: };
Could we have a proper constructor that sets everything to zero? Then reset
could be simply *this = AllocatorStats().

I also like to have a separate Print method and have the operator<< call the
Print method. This makes it easier to print from the gdb. Up to you.

https://codereview.chromium.org/1132753005/diff/80001/src/compiler/register-a...
src/compiler/register-allocator.h:877: LifetimePosition
GetCorrectSplitPos(LifetimePosition pos);
Nit: ...Pos -> ...Position)

[Mircea Trofin, 2015-05-14 16:56:28]

Thanks for the review! I'll incorporate it shortly, in the meantime I believe I
found the reason for the regression in a few benchmarks (e.g. zlib), so I prefer
delaying this change in favor of fixing those regressions.

Thanks!
Mircea.

[Michael Achenbach, 2015-05-19 17:14:57]

Please also shorten the first line of the CL description.