When spilling live range with not register uses inside the loop try to move spilling out of the loo…

When spilling live range with not register uses inside the loop try to move spilling out of the loop.

This allows to minimize amount of memory moves on the back edge.

R=danno@chromium.org
BUG=

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

[danno, 2013-01-02 17:35:14]

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

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1951: if (loop_header != NULL) {
Don't you want a loop here? If there are nested loops, you want to try to spill
in a position in the outer-most loop header that is is still in the range and
beneficial?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1956: loop_header->first_instruction_index());
Don't you want last_instruction_index() in case the loop header itself contains
uses?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1962: split_pos = pos;
Since split_pos, can be different for every live range, I am not sure this is
100% correct. Don't you want to copy split_pos to "optimal_split_pos" every time
through so that only gets updated in this if, and do the spill like this:
SpillAfter(range, optimal_split_pos)?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1968: SpillBetween(range, split_pos, next_pos->pos());
Why doesn't your logic to hoist spills no also apply here? Since you are
spilling until next_pos, after which a new range is created, it seems that the
handling before next_pos->pos() degenerates to the case handled above, and the
same heuristics for avoiding the spill at split_pos in a loop still apply.

You might have to generalize the logic a bit.
NextUsePositionRegisterIsBeneficial == NULL is too strict, as long as it's at or
later than next_pos, it's still OK to insert the spill, isn't it?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1983: SpillAfter(range, split_pos);
Same applies here, doesn't it, or am I confused? Even if the range is inactive,
it's still not a good idea to put the spill in a loop if it can be avoided.

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1986: SpillBetween(range, split_pos,
next_intersection);
And here, too?

[Vyacheslav Egorov (Google), 2013-01-07 06:42:25]

Thanks for your comments. 

Hopefully I'll manage to address them this week.

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

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1951: if (loop_header != NULL) {
I just wanted to keep this code simple. I will add a loop.

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1956: loop_header->first_instruction_index());
On 2013/01/02 17:35:14, danno wrote:
> Don't you want last_instruction_index() in case the loop header itself
contains
> uses?

Not sure I understand. If I make it last_instruction_index then I'll miss those
uses. NextUsePositionRegisterIsBeneficial is searching forward.

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1962: split_pos = pos;
On 2013/01/02 17:35:14, danno wrote:
> Since split_pos, can be different for every live range, I am not sure this is
> 100% correct. Don't you want to copy split_pos to "optimal_split_pos" every
time
> through so that only gets updated in this if, and do the spill like this:
> SpillAfter(range, optimal_split_pos)?

Good catch. I misread where split_pos is defined. 

[Working on two similar but not exactly the same register allocators impacted my
concentration.]

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1968: SpillBetween(range, split_pos, next_pos->pos());
It can be applied here. I just did not want to apply it here because I
considered this to be an unlikely case.

On 2013/01/02 17:35:14, danno wrote:
> Why doesn't your logic to hoist spills no also apply here? Since you are
> spilling until next_pos, after which a new range is created, it seems that the
> handling before next_pos->pos() degenerates to the case handled above, and the
> same heuristics for avoiding the spill at split_pos in a loop still apply.
> 
> You might have to generalize the logic a bit.
> NextUsePositionRegisterIsBeneficial == NULL is too strict, as long as it's at
or
> later than next_pos, it's still OK to insert the spill, isn't it?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1983: SpillAfter(range, split_pos);
I don't think it applies here (or below): the loop is either completely in the
lifetime hole or not at all.

On 2013/01/02 17:35:14, danno wrote:
> Same applies here, doesn't it, or am I confused? Even if the range is
inactive,
> it's still not a good idea to put the spill in a loop if it can be avoided.

[danno, 2013-01-08 12:39:22]

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

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1956: loop_header->first_instruction_index());
On 2013/01/07 06:42:25, Vyacheslav Egorov (Google) wrote:
> On 2013/01/02 17:35:14, danno wrote:
> > Don't you want last_instruction_index() in case the loop header itself
> contains
> > uses?
> 
> Not sure I understand. If I make it last_instruction_index then I'll miss
those
> uses. NextUsePositionRegisterIsBeneficial is searching forward. 

Maybe I'm just confused. My thought was that you want to split at the latest
possible point before entering the loop (i.e. at the very end of the loop header
at last_instruction). If you split earlier than that (e.g. at the very beginning
at first_instruction), then if there is a use in the header later than that
point, then range->NextUsePositionRegisterIsBeneficial(pos) will return non-NULL
and the split won't be hoisted, even though it would have been a beneficial
hoist at the end of loop_header (last_instruction), at which position
NextUsePositionRegisterIsBeneficial of that position would return NULL.

Does that make sense?

https://codereview.chromium.org/11437015/diff/1/src/lithium-allocator.cc#newc...
src/lithium-allocator.cc:1983: SpillAfter(range, split_pos);
Ah, I see. Got it.

On 2013/01/07 06:42:25, Vyacheslav Egorov (Google) wrote:
> I don't think it applies here (or below): the loop is either completely in the
> lifetime hole or not at all.
> 
> On 2013/01/02 17:35:14, danno wrote:
> > Same applies here, doesn't it, or am I confused? Even if the range is
> inactive,
> > it's still not a good idea to put the spill in a loop if it can be avoided. 
>

[Vyacheslav Egorov (Google), 2013-01-25 13:19:24]

Please take another look.

[danno, 2013-02-01 11:56:39]

lgtm

[Vyacheslav Egorov (Google), 2013-03-15 13:26:02]

Committed patchset #2 manually as r13960 (presubmit successful).