[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)
 
 
 const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;
 
-
 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) {
+                 LifetimePosition pos, bool update_size = true) {
   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());
+  if (update_size) {
+    range->UpdateSize();
+    result->UpdateSize();
+  }
+  TRACE("Split range %d(v%d) @%d => %d.\n", range->id(),
+        range->TopLevel()->id(), pos.ToInstructionIndex(), result->id());
   return result;
 }
 
 
+void SpillToStackSlot(LiveRange* range, RegisterAllocationData* data) {
+  DCHECK(!range->spilled());
+  TRACE("Spilling live range %d(v%d)\n", range->id(), range->TopLevel()->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);
+}
+
+
+bool DoesInstructionClobberRange(const LiveRange* range,
+                                 const Instruction* instruction) {
+  return instruction->IsCall();
+}
+
+
+// Split range just before the instr_index, and then at the closest position
+// the control flow resumes, and return the range after that position, if any.
+LiveRange* SplitRangeAtClobberingInstruction(LiveRange* range, int index,
+                                             RegisterAllocationData* data) {
+  LiveRange* ret = nullptr;
+  const InstructionSequence* code = data->code();
+
+  LifetimePosition before_call =
+      GetSplitPositionForInstruction(range, code, index);
+  LiveRange* call_part = nullptr;
+  if (before_call.IsValid()) {
+    call_part = Split(range, data, before_call, false);
+  } else {
+    // This range starts with the call.
+    call_part = range;
+  }
+
+  LifetimePosition after_call =
+      GetFirstSplitPosFollowingCall(call_part, code, index);
+  if (after_call.IsValid()) {
+    ret = Split(call_part, data, after_call, false);
+  }
+  SpillToStackSlot(call_part, data);
+  return ret;
+}
+
+
+// Split before a call that requires parameters on stack, and spill until
+// the first position requiring the parameter back in a register.
+// The range must not be fixed.
+void SplitRangeAroundClobberingInstructions(LiveRange* range,
+                                            RegisterAllocationData* data) {
+  DCHECK(!range->IsFixed());
+  // return;
+  const InstructionSequence* code = data->code();
+
+  LiveRange* current_subrange = range;
+  int top_id = range->id();
+  UseInterval* interval = current_subrange->first_interval();
+  while (interval != nullptr) {
+    int first_index = GetFirstInstructionIndex(interval);
+    int last_index = GetLastInstructionIndex(interval);
+    interval = interval->next();
+
+    for (int index = first_index; index <= last_index; ++index) {
+      const Instruction* instr = code->InstructionAt(index);
+      if (DoesInstructionClobberRange(current_subrange, instr)) {
+        TRACE("Range %d is clobbered by instruction at index %d.\n", top_id,
+              index);
+        current_subrange =
+            SplitRangeAtClobberingInstruction(current_subrange, index, data);
+        interval = current_subrange == nullptr
+                       ? nullptr
+                       : current_subrange->first_interval();
+        break;
+      }
+    }
+  }
+}
+
+
+bool DoesSubsequenceClobber(const InstructionSequence* code, int start,
+                            int stop) {
+  for (int i = start; i <= stop; ++i) {
+    if (code->InstructionAt(i)->IsCall()) return true;
+  }
+  return false;
+}
+
+
+// If the block has a throwing call, when the control flow takes the exception
+// handler path, the last instruction in the block - a jump to the normal
+// execution path - isn't executed. Implicitly, moves there won't be executed.
+// So we will try to split at the closest successor instead,
+LiveRange* SplitRangeAfterBlock(LiveRange* range, RegisterAllocationData* data,
+                                const InstructionBlock* block) {
+  const InstructionSequence* code = data->code();
+  int instr_index = block->last_instruction_index();
+  int outside_index = static_cast<int>(code->instructions().size());
+  bool has_handler = false;
+  for (auto successor_id : block->successors()) {
+    const InstructionBlock* successor = code->InstructionBlockAt(successor_id);
+    if (successor->IsHandler()) {
+      has_handler = true;
+    }
+    outside_index = Min(outside_index, successor->first_instruction_index());
+  }
+  if (!has_handler) {
+    // We can split at the end of the block, to ensure the fill happens here,
+    // however, we still need to split again at the beginning of the closest
+    // successor so that the control flow connector doesn't attempt to use the
+    // locally spilled slot.
+    LifetimePosition at_block_end =
+        GetSplitPositionForInstruction(range, code, instr_index);
+    if (!at_block_end.IsValid()) return nullptr;
+    range = Split(range, data, at_block_end);
+  }
+  instr_index = outside_index;
+
+  LifetimePosition after_block =
+      GetSplitPositionForInstruction(range, code, instr_index);
+
+  if (after_block.IsValid()) {
+    return Split(range, data, after_block);
+  } else {
+    return nullptr;
+  }
+}
+
+
+void SplitRangeByClobberingDeferredBlocks(LiveRange* range,
+                                          RegisterAllocationData* data) {
+  DCHECK(!range->IsFixed());
+  DCHECK(!range->spilled());
+
+  const InstructionSequence* code = data->code();
+  LiveRange* current_subrange = range;
+
+  UseInterval* interval = current_subrange->first_interval();
+
+  while (interval != nullptr) {
+    int first_index = GetFirstInstructionIndex(interval);
+    int last_index = interval->end().ToInstructionIndex();
+
+    if (last_index >= code->instructions().size()) {
+      last_index = static_cast<int>(code->instructions().size() - 1);
+    }
+    interval = interval->next();
+
+    for (int index = first_index; index <= last_index;) {
+      const InstructionBlock* block = code->GetInstructionBlock(index);
+      int working_index = index;
+      index = block->last_instruction_index() + 1;
+
+      if (!block->IsDeferred() ||
+          !DoesSubsequenceClobber(
+              code, working_index,
+              Min(last_index, block->last_instruction_index()))) {
+        continue;
+      }
+
+      TRACE("Deferred block B%d clobbers range %d(v%d).\n",
+            block->rpo_number().ToInt(), current_subrange->id(),
+            current_subrange->TopLevel()->id());
+      LifetimePosition block_start =
+          GetSplitPositionForInstruction(current_subrange, code, working_index);
+      LiveRange* block_and_after = nullptr;
+      if (block_start.IsValid()) {
+        block_and_after = Split(current_subrange, data, block_start);
+      } else {
+        block_and_after = current_subrange;
+      }
+      LiveRange* after_block =
+          SplitRangeAfterBlock(block_and_after, data, block);
+      if (after_block == nullptr && block_and_after != current_subrange) {
+        after_block = block_and_after;
+      }
+      current_subrange = after_block == nullptr ? nullptr : after_block;
+      interval = current_subrange == nullptr
+                     ? nullptr
+                     : current_subrange->first_interval();
+      break;
+    }
+  }
+}
+
+
 // 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);
   int last = GetLastGapIndex(interval);
   if (first == last) return LifetimePosition::Invalid();
 
   // TODO(mtrofin:) determine why we can't just split somewhere arbitrary
-  // within the range, e.g. it's middle.
+  // within the range, e.g. its middle.
   for (UsePosition* pos = range->first_pos(); pos != nullptr;
        pos = pos->next()) {
     if (pos->type() != UsePositionType::kRequiresRegister) continue;
     LifetimePosition before = GetSplitPositionForInstruction(
         range, code, pos->pos().ToInstructionIndex());
     if (before.IsValid()) return before;
     LifetimePosition after = GetSplitPositionForInstruction(
         range, code, pos->pos().ToInstructionIndex() + 1);
     if (after.IsValid()) return after;
   }
@@ skipping 11 matching lines @@
 
 AllocationCandidate AllocationScheduler::GetNext() {
   DCHECK(!queue_.empty());
   AllocationCandidate ret = queue_.top();
   queue_.pop();
   return ret;
 }
 
 
 void AllocationScheduler::Schedule(LiveRange* range) {
-  TRACE("Scheduling live range %d.\n", range->id());
+  TRACE("Scheduling live range %d(v%d).\n", range->id(),
+        range->TopLevel()->id());
+  DCHECK(range->IsSizeValid());
   queue_.push(AllocationCandidate(range));
 }
 
 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       local_zone_(local_zone),
       allocations_(local_zone),
       scheduler_(local_zone) {}
 
 
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
-  TRACE("Assigning register %s to live range %d\n", RegisterName(reg_id),
-        range->id());
+  TRACE("Assigning register %s to live range %d(v%d).\n", RegisterName(reg_id),
+        range->id(), range->TopLevel()->id());
 
   DCHECK(!range->HasRegisterAssigned());
 
   AllocateRegisterToRange(reg_id, range);
 
-  TRACE("Assigning %s to range %d\n", RegisterName(reg_id), range->id());
+  TRACE("Assigning %s to range %d(v%d).\n", RegisterName(reg_id), range->id(),
+        range->TopLevel()->id());
   range->set_assigned_register(reg_id);
 }
 
 
 void GreedyAllocator::PreallocateFixedRanges() {
   allocations_.resize(num_registers());
   for (int i = 0; i < num_registers(); i++) {
     allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
   }
 
   for (LiveRange* fixed_range : GetFixedRegisters()) {
     if (fixed_range != nullptr) {
       DCHECK_EQ(mode(), fixed_range->kind());
       DCHECK(fixed_range->IsFixed());
 
       int reg_nr = fixed_range->assigned_register();
       EnsureValidRangeWeight(fixed_range);
       AllocateRegisterToRange(reg_nr, fixed_range);
     }
   }
 }
 
 
 void GreedyAllocator::ScheduleAllocationCandidates() {
   for (auto range : data()->live_ranges()) {
     if (CanProcessRange(range) && !range->spilled()) {
+      range->UpdateSize();
       scheduler().Schedule(range);
     }
   }
 }
 
 
 void GreedyAllocator::TryAllocateCandidate(
     const AllocationCandidate& candidate) {
   // At this point, this is just a live range. TODO: groups.
   TryAllocateLiveRange(candidate.live_range());
 }
 
 
 void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
   // TODO(mtrofin): once we introduce groups, we'll want to first try and
   // allocate at the preferred register.
-  TRACE("Attempting to allocate live range %d\n", range->id());
+  TRACE("Attempting to allocate live range %d(v%d).\n", range->id(),
+        range->TopLevel()->id());
   int free_reg = -1;
   int evictable_reg = -1;
   EnsureValidRangeWeight(range);
   DCHECK(range->weight() != LiveRange::kInvalidWeight);
 
   float smallest_weight = LiveRange::kMaxWeight;
 
   // Seek either the first free register, or, from the set of registers
   // where the maximum conflict is lower than the candidate's weight, the one
   // with the smallest such weight.
   for (int i = 0; i < num_registers(); i++) {
     float max_conflict_weight = GetMaximumConflictingWeight(i, range);
     if (max_conflict_weight == LiveRange::kInvalidWeight) {
       free_reg = i;
       break;
     }
     if (max_conflict_weight < range->weight() &&
         max_conflict_weight < smallest_weight) {
       smallest_weight = max_conflict_weight;
       evictable_reg = i;
     }
   }
 
   // We have a free register, so we use it.
   if (free_reg >= 0) {
-    TRACE("Found free register %s for live range %d\n", RegisterName(free_reg),
+    TRACE("Found free register %s for live range %d.\n", RegisterName(free_reg),
           range->id());
     AssignRangeToRegister(free_reg, range);
     return;
   }
 
   // We found a register to perform evictions, so we evict and allocate our
   // candidate.
   if (evictable_reg >= 0) {
-    TRACE("Found evictable register %s for live range %d\n",
+    TRACE("Found evictable register %s for live range %d.\n",
           RegisterName(free_reg), range->id());
     EvictAndRescheduleConflicts(evictable_reg, range);
     AssignRangeToRegister(evictable_reg, range);
     return;
   }
 
   // The range needs to be split or spilled.
   SplitOrSpillBlockedRange(range);
 }
 
 
 void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
                                                   const LiveRange* range) {
   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
        conflict = conflicts.RemoveCurrentAndGetNext()) {
     DCHECK(conflict->HasRegisterAssigned());
     CHECK(!conflict->IsFixed());
     conflict->UnsetAssignedRegister();
     UpdateWeightAtEviction(conflict);
     scheduler().Schedule(conflict);
-    TRACE("Evicted range %d.\n", conflict->id());
+    TRACE("Evicted range %d(v%d).\n", conflict->id(),
+          conflict->TopLevel()->id());
   }
 }
 
 
 void GreedyAllocator::SplitAndSpillRangesDefinedByMemoryOperand() {
   size_t initial_range_count = data()->live_ranges().size();
   for (size_t i = 0; i < initial_range_count; ++i) {
     auto range = data()->live_ranges()[i];
     if (!CanProcessRange(range)) continue;
-    if (range->HasNoSpillType()) continue;
+    if (!range->HasSpillOperand()) continue;
+    if (range->IsChild()) continue;
 
     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",
         data()->debug_name());
 
+  size_t live_range_count = data()->live_ranges().size();
+  for (size_t i = 0; i < live_range_count; i++) {
+    LiveRange* range = data()->live_ranges()[i];
+    if (CanProcessRange(range) && !range->spilled() && !range->IsFixed() &&
+        !range->IsChild()) {
+      SplitRangeByClobberingDeferredBlocks(range, data());
+    }
+  }
+
+  live_range_count = data()->live_ranges().size();
+  for (size_t i = 0; i < live_range_count; i++) {
+    LiveRange* range = data()->live_ranges()[i];
+    if (CanProcessRange(range) && !range->spilled() && !range->IsFixed()) {
+      SplitRangeAroundClobberingInstructions(range, data());
+    }
+  }
+
   SplitAndSpillRangesDefinedByMemoryOperand();
+
   PreallocateFixedRanges();
   ScheduleAllocationCandidates();
 
   while (!scheduler().empty()) {
     AllocationCandidate candidate = scheduler().GetNext();
     TryAllocateCandidate(candidate);
   }
 
 
   // We do not rely on the hint mechanism used by LinearScan, so no need to
@@ skipping 44 matching lines @@
   }
   if (!IsProgressPossible(range, code())) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
 
   float use_count = 0.0;
   for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
     ++use_count;
   }
-  range->set_weight(use_count / static_cast<float>(range->GetSize()));
+  DCHECK(range->IsSizeValid());
+  range->set_weight(use_count / static_cast<float>(range->size()));
 }
 
 
 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) {
   // 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