Greedy reg alloc - better splitting

Most of the issues so far encountered with the greedy allocator rest with the splitting mechanism. This change has:

- all RegisterAllocatorTest unit tests passing, when unittest has the flags: --turbo-filter=* --always-opt --turbo-deoptimization --turbo-verify-allocation --turbo_greedy_regalloc

./tools/run-tests.py passing when providing --turbo_greedy_regalloc, but still having some failing (more than the "normal" 43) when passing all the flags. I realize just passing --turbo_greedy_regalloc does not provide full coverage, but it did uncover some bugs, still

The CL centralizes the computing of split points (for "losing" intervals) with the determination of whether an interval is irreducible, and, therefore, of infinite spill weight (if an interval can't be split or spilled, it can't lose in weight comparison because there's nothing we can do to it and make progress).

There are allocator efficiency opportunities I haven't yet taken (this refers to the code itself, not the generated code). For example, the above split/spill computation can be cached. My plan is to defer this to at least after we see numbers showing the value of the algorithm, and potentially do at the same time we remove the linear algorithm, if that is still the plan. At that time, we can look where some APIs best belong (e.g. weight computation may fully live and cache itself on LiveRange)

In addition, the CL adds a few debug-time-only Print APIs I found very useful:  on demand (while in GDB) dump of the code, live range info (use positions & operand description, and intervals), etc.

BUG=

Committed: https://crrev.com/cd481a7dfdb1b698758d154d01169302992a5443
Cr-Commit-Position: refs/heads/master@{#28185}

[Mircea Trofin, 2015-04-29 15:32:37]

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

[Mircea Trofin, 2015-04-29 15:33:45]

Note: I saw the failing static initializers test fail, I'm investigating, but I
suppose we can make progress on the CR at the same time.

Thanks!

[dcarney, 2015-04-29 17:24:13]

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:12: #include <iostream>
this is not allowed - adds static initializers

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:107: LifetimePosition Next() const {
are these really useful?  they seem unusual...

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:171: static inline std::ostream&
operator<<(std::ostream& os,
this should not be DEBUG and should not be inline but in the impl file

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:609: void Print(LiveRange* range);
these we don't do in v8.  you'll need  a local patch if you want them.  you can
add  the ostream operator<< thing for LiveRange, though

[Mircea Trofin, 2015-04-29 17:35:33]

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:12: #include <iostream>
On 2015/04/29 17:24:13, dcarney wrote:
> this is not allowed - adds static initializers

OK. 

As a note, weird that it shows up in the bot test for static initializers, I
thought that one validates release builds only, or?

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:107: LifetimePosition Next() const {
On 2015/04/29 17:24:13, dcarney wrote:
> are these really useful?  they seem unusual...

Yes, see the way we pick split points.

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.h:609: void Print(LiveRange* range);
On 2015/04/29 17:24:13, dcarney wrote:
> these we don't do in v8.  you'll need  a local patch if you want them.  you
can
> add  the ostream operator<< thing for LiveRange, though

I see. So do we have an ostream available in gdb, akin LLVM's dbgs()? (I tried
to find something of the sort and unfortunately didn't)

I could add something like that and expose it here, so that the config is
available and we avoid asking the dev to construct Printable{...} while in the
debugger. 

I'd still have that stream available under DEBUG only, though.

[dcarney, 2015-04-29 18:13:44]

> I'd still have that stream available under DEBUG only, though.

that wouldn't be consistent with the rest of v8, just expose it unconditionally

[dcarney, 2015-04-29 18:18:35]

couple minor comments, everything else looks fine is you clean up all the
printing stuff

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.cc:2576: ZoneSet<LiveRange*>
local_conflicts(data()->allocation_zone());
the only things that should be allocated in the allocation_zone are things
surviving phases.  create a local_zone() accessor and use that

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.cc:2671: auto* zone =
allocations_.get_allocator().zone();
use local_zone() accessor here as well

[dcarney, 2015-04-30 06:01:32]

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
src/compiler/register-allocator.cc:909: std::ostream& operator<<(std::ostream&
os,
this should come after the live range class functions

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
src/compiler/register-allocator.h:634: OFStream dbgs_;
this is not done anywhere in v8 and seems anyway a little odd.  like i said,
these Print things are the kinds of things we locally hack when necessary but do
not put in the codebase

can you tear out all the debugging stuff for now, except for the 2 operator <<
functions
so we can land this patch. it's anyway unrelated

[dcarney, 2015-04-30 10:53:23]

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

[Mircea Trofin, 2015-04-30 18:16:49]

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.cc:2576: ZoneSet<LiveRange*>
local_conflicts(data()->allocation_zone());
On 2015/04/29 18:18:35, dcarney wrote:
> the only things that should be allocated in the allocation_zone are things
> surviving phases.  create a local_zone() accessor and use that

Done.

https://codereview.chromium.org/1105793002/diff/100001/src/compiler/register-...
src/compiler/register-allocator.cc:2671: auto* zone =
allocations_.get_allocator().zone();
On 2015/04/29 18:18:35, dcarney wrote:
> use local_zone() accessor here as well

Done.

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/120001/src/compiler/register-...
src/compiler/register-allocator.cc:909: std::ostream& operator<<(std::ostream&
os,
On 2015/04/30 06:01:32, dcarney wrote:
> this should come after the live range class functions

Done.

[Mircea Trofin, 2015-04-30 22:31:34]

Updated after latest rebase

[dcarney, 2015-05-01 07:56:04]

lgtm with nits

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.cc:2683: return (TryReuseSpillForPhi(range));
extra ()

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:480: const PrintableLiveRange
printable_range);
we usually use const & for these

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:622: }
these are dead code (gdb only). drop.

in gdb you can anyway use RegisterConfiguration::ArchDefault() for config

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:856: class CoallescedLiveRanges;
i missed this earlier, but coalesced has one 'l', can you change it in this cl
or a followup

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:871: Zone* local_zone() { return local_zone_;
}
const

[Mircea Trofin, 2015-05-01 15:06:33]

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.cc:2683: return (TryReuseSpillForPhi(range));
On 2015/05/01 07:56:03, dcarney wrote:
> extra ()

Done.

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
File src/compiler/register-allocator.h (right):

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:480: const PrintableLiveRange
printable_range);
On 2015/05/01 07:56:03, dcarney wrote:
> we usually use const & for these

Done.

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:622: }
On 2015/05/01 07:56:03, dcarney wrote:
> these are dead code (gdb only). drop.
> 
> in gdb you can anyway use RegisterConfiguration::ArchDefault() for config

But you still need to construct the Printable{xyz} things. Not super usable.
I'll remove them though to keep this "gdb usability" topic separate.

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:856: class CoallescedLiveRanges;
On 2015/05/01 07:56:03, dcarney wrote:
> i missed this earlier, but coalesced has one 'l', can you change it in this cl
> or a followup

Done.

https://codereview.chromium.org/1105793002/diff/160001/src/compiler/register-...
src/compiler/register-allocator.h:871: Zone* local_zone() { return local_zone_;
}
On 2015/05/01 07:56:03, dcarney wrote:
> const

Done.

[Mircea Trofin, 2015-05-01 15:06:39]

The CQ bit was checked by mtrofin@chromium.org

[Mircea Trofin, 2015-05-01 15:06:40]

The patchset sent to the CQ was uploaded after l-g-t-m from dcarney@chromium.org
Link to the patchset: https://codereview.chromium.org/1105793002/#ps180001
(title: " ")

[commit-bot: I haz the power, 2015-05-01 15:06:52]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1105793002/180001

[commit-bot: I haz the power, 2015-05-01 15:31:37]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2015-05-01 15:32:00]

Patchset 10 (id:??) landed as
https://crrev.com/cd481a7dfdb1b698758d154d01169302992a5443
Cr-Commit-Position: refs/heads/master@{#28185}