More aggressive reuse of spill slots in the register allocator.

More aggressive reuse of spill slots in the register allocator.

Two improvements:
- At phi nodes, we now try to merge operands into one spill slot and
  then reuse the spill slot for the phi.
- After register allocation we merge disjoint spill slots.

With this change, I see about 4% improvement in zlib.

BUG=
R=titzer@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=23532

[titzer, 2014-06-17 09:01:35]

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

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
src/lithium-allocator.cc:1134: while (interval1 != NULL && interval2 != NULL) {
I suppose we could speed this interval check up with a cache of the maximum end
position for each live range...but wow, this beast is already out of hand...

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
src/lithium-allocator.cc:1175: void SpillRange::Swap(UseInterval*& a,
UseInterval*& b) {
You can replace uses of this with std::swap

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

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.h#newc...
src/lithium-allocator.h:388: int spill_range_id_;
Why not a direct pointer to the SpillRange?

[Jarin, 2014-06-24 21:49:58]

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

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
src/lithium-allocator.cc:1134: while (interval1 != NULL && interval2 != NULL) {
On 2014/06/17 09:01:34, titzer wrote:
> I suppose we could speed this interval check up with a cache of the maximum
end
> position for each live range...but wow, this beast is already out of hand...

Yes, the asymptotic complexity is indeed bad, but it does not seem to be a
problem even for the massive functions in zlib.

I have added tracking of the maximum end position.

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
src/lithium-allocator.cc:1175: void SpillRange::Swap(UseInterval*& a,
UseInterval*& b) {
On 2014/06/17 09:01:34, titzer wrote:
> You can replace uses of this with std::swap

Done.

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

https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.h#newc...
src/lithium-allocator.h:388: int spill_range_id_;
On 2014/06/17 09:01:34, titzer wrote:
> Why not a direct pointer to the SpillRange?

Done.

[Jarin, 2014-07-16 15:23:50]

On 2014/06/24 21:49:58, jarin wrote:
> https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc
> File src/lithium-allocator.cc (right):
> 
>
https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
> src/lithium-allocator.cc:1134: while (interval1 != NULL && interval2 != NULL)
{
> On 2014/06/17 09:01:34, titzer wrote:
> > I suppose we could speed this interval check up with a cache of the maximum
> end
> > position for each live range...but wow, this beast is already out of hand...
> 
> Yes, the asymptotic complexity is indeed bad, but it does not seem to be a
> problem even for the massive functions in zlib.
> 
> I have added tracking of the maximum end position.
> 
>
https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.cc#new...
> src/lithium-allocator.cc:1175: void SpillRange::Swap(UseInterval*& a,
> UseInterval*& b) {
> On 2014/06/17 09:01:34, titzer wrote:
> > You can replace uses of this with std::swap
> 
> Done.
> 
> https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.h
> File src/lithium-allocator.h (right):
> 
>
https://codereview.chromium.org/310003003/diff/1/src/lithium-allocator.h#newc...
> src/lithium-allocator.h:388: int spill_range_id_;
> On 2014/06/17 09:01:34, titzer wrote:
> > Why not a direct pointer to the SpillRange?
> 
> Done.

ping.

[titzer, 2014-07-19 15:05:50]

lgtm

[Jarin, 2014-08-30 15:50:34]

Committed patchset #3 manually as 23532 (presubmit successful).