[turbofan] Deferred block spilling heuristic - first step.

src/compiler/greedy-allocator.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/greedy-allocator.h"
 #include "src/compiler/register-allocator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
@@ skipping 22 matching lines @@
   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
          (data->code()
               ->GetInstructionBlock(pos.ToInstructionIndex())
               ->last_instruction_index() != pos.ToInstructionIndex()));
   LiveRange* result = data->NewChildRangeFor(range);
   range->SplitAt(pos, result, data->allocation_zone());
   return result;
 }
 
 
+void SpillToStackSlot(LiveRange* range, RegisterAllocationData* data) {
+  DCHECK(!range->spilled());
+  TRACE("Spilling live range %d\n", range->id());
+  auto first = range->TopLevel();
+  if (first->HasNoSpillType()) {
+    data->AssignSpillRangeToLiveRange(first);
+  }
+  range->Spill();
+}
+
+
 // TODO(mtrofin): explain why splitting in gap START is always OK.
 LifetimePosition GetSplitPositionForInstruction(const LiveRange* range,
                                                 const InstructionSequence* code,
                                                 int instruction_index) {
   LifetimePosition ret = LifetimePosition::Invalid();
 
   ret = LifetimePosition::GapFromInstructionIndex(instruction_index);
   if (range->Start() >= ret || ret >= range->End()) {
     return LifetimePosition::Invalid();
   }
   return ret;
 }
 
 
 int GetFirstGapIndex(const UseInterval* interval) {
   LifetimePosition start = interval->start();
   int ret = start.ToInstructionIndex();
   return ret;
 }
 
 
 int GetLastGapIndex(const UseInterval* interval) {
   LifetimePosition end = interval->end();
   return end.ToInstructionIndex();
 }
 
 
+// Split before a call that requires parameters on stack, and spill until
+// the first position requiring the parameter back in a register.
+bool TrySplittingAroundCalls(LiveRange* range, RegisterAllocationData* data,
+                             AllocationScheduler* scheduler) {
+  for (auto use = range->first_pos(); use != nullptr; use = use->next()) {
+    int index = use->pos().ToInstructionIndex();
+    auto instr = data->code()->InstructionAt(index);

[Jarin, 2015/07/22 12:59:35]

Expand 'auto', please.

+    if (!instr->IsCall()) continue;

[Jarin, 2015/07/22 12:59:35]

This does not really work because live ranges can (and  do) get indirectly
spilled by calls: If a call's position lies somewhere inside one of the live
ranges intervals, the call clobbers all registers and thus makes it impossible
for the live range to be allocated. That happens even if the call is not in the
live range's use list.

Just try this on the following example:

var f = (function() {
  "use asm"
  return function f(x, y) {
    x = x|0;
    y = y|0;
    return x+y|0;
  }
})();

%OptimizeFunctionOnNextCall(f)
f(1, 2);

Here the live range corresponding to x should not be spilled on the fast path,
but it is. (The same goes for the context that lives in rsi.)

[Mircea Trofin, 2015/07/23 02:20:04]

I see. OK, so we need to iterate over each instruction then.

+    if (use->type() != UsePositionType::kRequiresSlot) continue;
+
+    LifetimePosition at_call =
+        GetSplitPositionForInstruction(range, data->code(), index);
+    if (!at_call.IsValid()) continue;
+    LiveRange* call_part = Split(range, data, at_call);
+    scheduler->Schedule(range);
+
+    use = use->next();
+    LifetimePosition next_split = LifetimePosition::Invalid();
+    for (; use != nullptr && !next_split.IsValid(); use = use->next()) {
+      next_split = GetSplitPositionForInstruction(
+          call_part, data->code(), use->pos().ToInstructionIndex());
+    }

[Jarin, 2015/07/22 12:59:35]

Why do we have the loop here? Cannot it happen that we fall off to a completely
unrelated basic block here?

[Mircea Trofin, 2015/07/23 02:20:04]

If we fall on to a different block, that's fine, correctness-wise, but we lose
the optimization opportunity.

The main issue here - and I'm investigating it - is why can't we just split
again at index + 1. It leads to runtime errors, and I suspect there's some
interplay with the way we handle traced pointers.

+    if (next_split.IsValid()) {
+      LiveRange* keep = Split(call_part, data, next_split);
+      scheduler->Schedule(keep);
+    }
+
+    SpillToStackSlot(call_part, data);
+    return true;
+  }
+  return false;
+}
+
+
 // Basic heuristic for advancing the algorithm, if any other splitting heuristic
 // failed.
 LifetimePosition GetLastResortSplitPosition(const LiveRange* range,
                                             const InstructionSequence* code) {
   if (range->first_interval()->next() != nullptr) {
     return range->first_interval()->next()->start();
   }
 
   UseInterval* interval = range->first_interval();
   int first = GetFirstGapIndex(interval);
@@ skipping 157 matching lines @@
     LifetimePosition start = range->Start();
     TRACE("Live range %d is defined by a spill operand.\n", range->id());
     auto next_pos = start;
     if (next_pos.IsGapPosition()) {
       next_pos = next_pos.NextStart();
     }
     auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
     // If the range already has a spill operand and it doesn't need a
     // register immediately, split it and spill the first part of the range.
     if (pos == nullptr) {
-      Spill(range);
+      SpillToStackSlot(range, data());
     } else if (pos->pos() > range->Start().NextStart()) {
       // Do not spill live range eagerly if use position that can benefit from
       // the register is too close to the start of live range.
-      auto split_pos = pos->pos();
-      if (data()->IsBlockBoundary(split_pos.Start())) {
-        split_pos = split_pos.Start();
-      } else {
-        split_pos = split_pos.PrevStart().End();
+      auto split_pos = GetSplitPositionForInstruction(
+          range, code(), pos->pos().ToInstructionIndex());
+      if (split_pos.IsValid()) {
+        Split(range, data(), split_pos);
+        SpillToStackSlot(range, data());
       }
-      Split(range, data(), split_pos);
-      Spill(range);
     }
   }
 }
 
 
 void GreedyAllocator::AllocateRegisters() {
   CHECK(scheduler().empty());
   CHECK(allocations_.empty());
 
   TRACE("Begin allocating function %s with the Greedy Allocator\n",
@@ skipping 50 matching lines @@
   }
   range->set_weight(use_count / static_cast<float>(range->GetSize()));
 }
 
 
 void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
   LifetimePosition start = range->Start();
   CHECK(range->CanBeSpilled(start));
 
   DCHECK(range->NextRegisterPosition(start) == nullptr);
-  Spill(range);
+  SpillToStackSlot(range, data());
 }
 
 
 void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
+  if (TrySplittingAroundCalls(range, data(), &scheduler())) return;
+
   // TODO(mtrofin): replace the call below with the entry point selecting
   // heuristics, once they exist, out of which GLRSP is the last one.
   auto pos = GetLastResortSplitPosition(range, code());
   if (pos.IsValid()) {
     LiveRange* tail = Split(range, data(), pos);
     DCHECK(tail != range);
     scheduler().Schedule(tail);
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8