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

src/lithium-allocator.cc

Index: src/lithium-allocator.cc
diff --git a/src/lithium-allocator.cc b/src/lithium-allocator.cc
index 91a98112b61bd60a50b56d98f8ca4eebacdf01ff..104397e81ec50cb6e4229c11dbe6756391a4549e 100644
--- a/src/lithium-allocator.cc
+++ b/src/lithium-allocator.cc
@@ -1945,6 +1945,24 @@ void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
     if (range->assigned_register() == reg) {
       UsePosition* next_pos = range->NextRegisterPosition(current->Start());
       if (next_pos == NULL) {
+        HBasicBlock* block = GetBlock(current->Start().InstructionStart());
+        HBasicBlock* loop_header =
+            block->IsLoopHeader() ? block : block->parent_loop_header();
+        if (loop_header != NULL) {

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

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? 

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

I just wanted to keep this code simple. I will add a loop.

+          // We are going to spill live range inside the loop.
+          // If possible try to move spilling position backwards to loop header.
+          // This will reduce number of memory moves on the back edge.
+          LifetimePosition pos = LifetimePosition::FromInstructionIndex(
+            loop_header->first_instruction_index());

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

Don't you want last_instruction_index() in case the loop header itself contains
uses?

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

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

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

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?

+          if (range->Covers(pos)) {
+            range->ResetLastProcessedUse();
+            if (range->NextUsePositionRegisterIsBeneficial(pos) == NULL) {
+              // No register beneficial use since loop's start.
+              // Move split position backwards.
+              split_pos = pos;

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

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)?

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

Good catch. I misread where split_pos is defined. 

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

+            }
+          }
+        }
         SpillAfter(range, split_pos);
       } else {
         SpillBetween(range, split_pos, next_pos->pos());

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

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?

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

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: