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

src/lithium-allocator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1927 matching lines @@
 
 void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   ASSERT(current->HasRegisterAssigned());
   int reg = current->assigned_register();
   LifetimePosition split_pos = current->Start();
   for (int i = 0; i < active_live_ranges_.length(); ++i) {
     LiveRange* range = active_live_ranges_[i];
     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:

       }
       ActiveToHandled(range);
       --i;
     }
   }
 
   for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
     LiveRange* range = inactive_live_ranges_[i];
     ASSERT(range->End().Value() > current->Start().Value());
     if (range->assigned_register() == reg && !range->IsFixed()) {
       LifetimePosition next_intersection = range->FirstIntersection(current);
       if (next_intersection.IsValid()) {
         UsePosition* next_pos = range->NextRegisterPosition(current->Start());
         if (next_pos == NULL) {
           SpillAfter(range, split_pos);

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

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/07 06:42:25]

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:

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

Ah, I see. Got it.

On 2013/01/07 06:42:25, Vyacheslav Egorov (Google) wrote:

         } else {
           next_intersection = Min(next_intersection, next_pos->pos());
           SpillBetween(range, split_pos, next_intersection);

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

And here, too?

         }
         InactiveToHandled(range);
         --i;
       }
     }
   }
 }
 
 
 bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
@@ skipping 131 matching lines @@
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal