[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();
 }
 
 
+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,
                                             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