[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 {
 
 #define TRACE(...)                             \
   do {                                         \
     if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
   } while (false)
 
-
 namespace {
 
 
 void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
   int reg_id = range->assigned_register();
   range->SetUseHints(reg_id);
   if (range->is_phi()) {
     data->GetPhiMapValueFor(range->id())->set_assigned_register(reg_id);
   }
 }
 
 
 LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
                  LifetimePosition pos) {
   DCHECK(range->Start() < pos && pos < range->End());
   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;
+}
+
+
+// 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) {
+  UsePosition* use = range->first_pos();
+
+  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 = data->code()->InstructionAt(index);
+      if (!instr->IsCall()) continue;
+      while (use != nullptr && use->pos().ToInstructionIndex() < index) {
+        use = use->next();
+      }
+      if (use != nullptr && use->pos().ToInstructionIndex() == index &&
+          use->type() == UsePositionType::kRequiresRegister)
+        continue;
+      LifetimePosition before_call =
+          GetSplitPositionForInstruction(range, data->code(), index);
+      if (!before_call.IsValid()) continue;
+      LiveRange* call_part = Split(range, data, before_call);
+      scheduler->Schedule(range);
+
+      for (auto next_use = use; next_use != nullptr;
+           next_use = next_use->next()) {
+        if (next_use->pos() <= before_call && !next_use->RegisterIsBeneficial())
+          continue;
+        int instr_to_split =
+            index + 1;  // next_use->pos().ToInstructionIndex();

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

If we change instr_to_split = next_use->pos().ToInstructionIndex(), everything
works fine. (to be clear, the current code lands on instr_to_split = index + 1
in a convoluted way, but it's simple to switch back and forth)

+        LifetimePosition after_call = GetSplitPositionForInstruction(
+            call_part, data->code(), instr_to_split);
+        if (after_call.IsValid()) {
+          LiveRange* keep = Split(call_part, data, after_call);
+          scheduler->Schedule(keep);
+          break;
+        }
+      }
+
+      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