[turbofan] Deferred block spilling heuristic - first step.

src/compiler/greedy-allocator.cc

Index: src/compiler/greedy-allocator.cc
diff --git a/src/compiler/greedy-allocator.cc b/src/compiler/greedy-allocator.cc
index 8d658c39ff4203bb420e7f184dd46f8634b1900f..cf02a590b233c1eac5c6b544f582d9e8d7740f5a 100644
--- a/src/compiler/greedy-allocator.cc
+++ b/src/compiler/greedy-allocator.cc
@@ -40,6 +40,17 @@ LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
 }
 
 
+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,
@@ -67,6 +78,40 @@ int GetLastGapIndex(const UseInterval* interval) {
 }
 
 
+// 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,
@@ -244,18 +289,16 @@ void GreedyAllocator::SplitAndSpillRangesDefinedByMemoryOperand() {
     // 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);
     }
   }
 }
@@ -326,11 +369,13 @@ void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
   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());