[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..d0ae5e25586c1ee619a97f47d52e54287efa10fc 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,102 @@ int GetLastGapIndex(const UseInterval* interval) {
 }
 
 
+int GetFirstInstructionIndex(const UseInterval* interval) {
+  int ret = interval->start().ToInstructionIndex();
+  if (!interval->start().IsGapPosition() && !interval->start().IsStart()) {
+    ++ret;
+  }
+  return ret;
+}
+
+
+int GetLastInstructionIndex(const UseInterval* interval) {
+  int ret = interval->end().ToInstructionIndex();
+  if (interval->end().IsGapPosition() || interval->end().IsStart()) {
+    // Meaning, this is either a gap or instruction start
+    --ret;
+  }
+  return ret;
+}
+
+
+LifetimePosition GetFirstSplitPosFollowingCall(const LiveRange* range,
+                                               const InstructionSequence* code,
+                                               int call_pos) {
+  int next_pos = call_pos + 1;
+  const InstructionBlock* block = code->GetInstructionBlock(call_pos);
+  if (next_pos == block->last_instruction_index()) {
+    // This may be a throwing call. Look through the successors for a
+    // handler. If there is one, then we pick the next position as the
+    // closest block start out of the successors:
+    // - if the next block is the handler, then splitting at the first position
+    // ensures a "fill" move instruction. The normal control flow block will
+    // evaluate false for LiveRangeConnector::CanEagerlyResolveControlFlow when
+    // we do the LiveRangeConnector::ResolveControlFlow phase, so that will
+    // ensure a fill move for it, too.
+    // - if the next block is the normal flow, then the same argument as above
+    // holds, but reversing the block roles.
+    // If there is no handler, just use call_pos + 1.
+    int outside_pos = static_cast<int>(code->instructions().size());
+    int alternative_next_pos = outside_pos;
+    bool found_handler = false;
+
+    for (RpoNumber successor_id : block->successors()) {
+      const InstructionBlock* successor =
+          code->InstructionBlockAt(successor_id);
+      if (successor->IsHandler()) {
+        DCHECK(!found_handler);
+        found_handler = true;
+      }
+      int first_succ_instruction = successor->first_instruction_index();
+      alternative_next_pos = Min(alternative_next_pos, first_succ_instruction);
+    }
+    if (found_handler) {
+      DCHECK_NE(outside_pos, alternative_next_pos);
+      next_pos = alternative_next_pos;
+    }
+  }
+  return GetSplitPositionForInstruction(range, code, next_pos);
+}
+
+
+// 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) {
+  TRACE("Attempting to split range %d around calls.\n", range->id());
+  const InstructionSequence* code = data->code();
+
+  for (auto interval = range->first_interval(); interval != nullptr;
+       interval = interval->next()) {
+    int first_index = GetFirstInstructionIndex(interval);
+    int last_index = GetLastInstructionIndex(interval);
+    for (int index = first_index; index <= last_index; ++index) {
+      auto instr = code->InstructionAt(index);
+      if (!instr->IsCall()) continue;
+      LifetimePosition before_call =
+          GetSplitPositionForInstruction(range, code, index);
+      if (!before_call.IsValid()) continue;
+      TRACE("Found call at instruction %d for range %d.\n", index, range->id());
+      LiveRange* call_part = Split(range, data, before_call);
+      scheduler->Schedule(range);
+
+      LifetimePosition after_call =
+          GetFirstSplitPosFollowingCall(call_part, code, index);
+      if (after_call.IsValid()) {
+        TRACE("Splitting after call at instruction %d for range %d.\n",
+              after_call.ToInstructionIndex(), call_part->id());
+        LiveRange* to_refill = Split(call_part, data, after_call);
+        scheduler->Schedule(to_refill);
+      }
+      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 +351,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 +431,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());