Fix issue 962.

Fix issue 962.

SplitBetween (formely known as Split with 3 arguments) should select split position from [start, end] instead of [start, end[. This should also improve allocation quality (remove certain redundant move patterns).

Also some minor renaming and refactoring to make register allocator code more readable.

BUG=v8:962
TEST=test/mjsunit/regress/regress-962.js

Committed: http://code.google.com/p/v8/source/detail?r=5969

[Kevin Millikin (Chromium), 2010-12-10 07:39:19]

The comments and renaming really help this code.

You're missing some articles ("the") :)  I've highlighted some places.

I don't think we can commit the CHECK, instead ASSERT and find a graceful way to
handle failure of the condition in product builds.

The rest LGTM.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc
File src/lithium-allocator.cc (right):

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:249: if (assigned_register_class_ == DOUBLE_REGISTERS)
{
Could use your IsDouble() predicate here.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1764: register_index,
Maybe it's not helpful here, but there's probably a function to convert the
register index to a string.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1769: // Desired register is free until end of current
live range.
The desired....until the end...

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1780: // Find register that stays free for the longest
time.
Find the register

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1816: // There is no use in currect live range that
requires register.
the current live range that requires a register

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1871: // All registers are blocked before the first use
that requires register.
that requires a register.  Spill the starting part of the

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1874: // Corner case: first use position is equal to
start of range.
the first use...the start of the range

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1878: CHECK(current->Start().Value() <
register_use->pos().Value());
We should consider what to do here.  CHECK will crash (fail fast) in product
builds.  We probably don't actually want to do that, and instead bail out safely
and fall back to unoptimized code?

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h
File src/lithium-allocator.h (right):

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode125
src/lithium-allocator.h:125: static inline LifetimePosition Invalid() { return
LifetimePosition(); }
I don't usually write inline here.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode145
src/lithium-allocator.h:145: enum RegistersClass {
RegisterKind?

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode147
src/lithium-allocator.h:147: CPU_REGISTERS,
Maybe GENERAL_REGISTERS is better?  They're all CPU registers :)

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode612
src/lithium-allocator.h:612: assigned_register_class_(NONE),
assigned_register_kind_?

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode669
src/lithium-allocator.h:669: // Split this live range at given position which
must follow start of
follow the start of

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode672
src/lithium-allocator.h:672: // live range to result live range.
to the result

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode795
src/lithium-allocator.h:795: // Returns register class required by given virtual
register.
Returns the register kind

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode889
src/lithium-allocator.h:889: // Split given range at position pos.
the given range

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode890
src/lithium-allocator.h:890: // If range starts at pos or range start follows
pos then
Something like: If the range starts at or after pos then the original range....

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode892
src/lithium-allocator.h:892: // Otherwise returns live range that starts at pos
and contains
the live range

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode893
src/lithium-allocator.h:893: // all uses from original range that follow pos.
Uses at pos will
from the origiinal

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode894
src/lithium-allocator.h:894: // still be owned by original range after
splitting.
by the original

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode908
src/lithium-allocator.h:908: // Spill give life range after position pos.
the given live range

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode911
src/lithium-allocator.h:911: // Spill given life range after position start and
up to end.
the given live range

[Vyacheslav Egorov (Chromium), 2010-12-10 14:18:27]

landing

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc
File src/lithium-allocator.cc (right):

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:249: if (assigned_register_class_ == DOUBLE_REGISTERS)
{
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Could use your IsDouble() predicate here.

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1764: register_index,
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Maybe it's not helpful here, but there's probably a function to convert the
> register index to a string.

Yes, I know. I was just lazy to introduce helper (which is required cause string
depends on mode_).

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1769: // Desired register is free until end of current
live range.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> The desired....until the end...

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1780: // Find register that stays free for the longest
time.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Find the register

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1816: // There is no use in currect live range that
requires register.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the current live range that requires a register

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1871: // All registers are blocked before the first use
that requires register.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> that requires a register.  Spill the starting part of the 

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1874: // Corner case: first use position is equal to
start of range.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the first use...the start of the range

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.cc#newcod...
src/lithium-allocator.cc:1878: CHECK(current->Start().Value() <
register_use->pos().Value());
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> We should consider what to do here.  CHECK will crash (fail fast) in product
> builds.  We probably don't actually want to do that, and instead bail out
safely
> and fall back to unoptimized code?

I replaced check with assert.

Yes. Gracefully bailing out on unsatisfiable constraints is my desire.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h
File src/lithium-allocator.h (right):

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode125
src/lithium-allocator.h:125: static inline LifetimePosition Invalid() { return
LifetimePosition(); }
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> I don't usually write inline here.

I prefer to state intention clearly.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode145
src/lithium-allocator.h:145: enum RegistersClass {
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> RegisterKind?

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode147
src/lithium-allocator.h:147: CPU_REGISTERS,
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Maybe GENERAL_REGISTERS is better?  They're all CPU registers :)

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode612
src/lithium-allocator.h:612: assigned_register_class_(NONE),
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> assigned_register_kind_?

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode669
src/lithium-allocator.h:669: // Split this live range at given position which
must follow start of
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> follow the start of

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode672
src/lithium-allocator.h:672: // live range to result live range.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> to the result

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode795
src/lithium-allocator.h:795: // Returns register class required by given virtual
register.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Returns the register kind

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode889
src/lithium-allocator.h:889: // Split given range at position pos.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the given range

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode890
src/lithium-allocator.h:890: // If range starts at pos or range start follows
pos then
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> Something like: If the range starts at or after pos then the original
range....

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode892
src/lithium-allocator.h:892: // Otherwise returns live range that starts at pos
and contains
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the live range

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode893
src/lithium-allocator.h:893: // all uses from original range that follow pos.
Uses at pos will
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> from the origiinal

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode894
src/lithium-allocator.h:894: // still be owned by original range after
splitting.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> by the original

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode908
src/lithium-allocator.h:908: // Spill give life range after position pos.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the given live range

Done.

http://codereview.chromium.org/5720001/diff/1/src/lithium-allocator.h#newcode911
src/lithium-allocator.h:911: // Spill given life range after position start and
up to end.
On 2010/12/10 07:39:19, Kevin Millikin wrote:
> the given live range

Done.