[turbofan] Greedy: smarter last resort splitting.

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 45 matching lines @@
   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();
-}
-
-
-// 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.
-  for (UsePosition* pos = range->first_pos(); pos != nullptr;
-       pos = pos->next()) {
-    if (pos->type() != UsePositionType::kRequiresRegister) continue;
-    LifetimePosition before =
-        GetSplitPositionForInstruction(range, pos->pos().ToInstructionIndex());
-    if (before.IsValid()) return before;
-    LifetimePosition after = GetSplitPositionForInstruction(
-        range, pos->pos().ToInstructionIndex() + 1);
-    if (after.IsValid()) return after;
-  }
-  return LifetimePosition::Invalid();
-}
-
-
-bool IsProgressPossible(const LiveRange* range,
-                        const InstructionSequence* code) {
-  return range->CanBeSpilled(range->Start()) ||
-         GetLastResortSplitPosition(range, code).IsValid();
-}
 }  // namespace
 
 
 AllocationCandidate AllocationScheduler::GetNext() {
   DCHECK(!queue_.empty());
   AllocationCandidate ret = queue_.top();
   queue_.pop();
   return ret;
 }
 
@@ skipping 426 matching lines @@
 void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
   // The live range weight will be invalidated when ranges are created or split.
   // Otherwise, it is consistently updated when the range is allocated or
   // unallocated.
   if (range->weight() != LiveRange::kInvalidWeight) return;
 
   if (range->TopLevel()->IsFixed()) {
     range->set_weight(LiveRange::kMaxWeight);
     return;
   }
-  if (!IsProgressPossible(range, code())) {
+  if (!IsProgressPossible(range)) {
     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()));
 }
@@ skipping 105 matching lines @@
   pos = GetSplitPositionForInstruction(range, pos.ToInstructionIndex());
   return pos;
 }
 
 
 void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
   if (TrySplitAroundCalls(range)) return;
 
   LifetimePosition pos = FindSplitPositionBeforeLoops(range);
 
-  if (!pos.IsValid()) pos = GetLastResortSplitPosition(range, code());
+  if (!pos.IsValid()) pos = GetLastResortSplitPosition(range);
   if (pos.IsValid()) {
     LiveRange* tail = Split(range, data(), pos);
     DCHECK(tail != range);
     scheduler().Schedule(tail);
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
+// Basic heuristic for advancing the algorithm, if any other splitting heuristic
+// failed.
+LifetimePosition GreedyAllocator::GetLastResortSplitPosition(
+    const LiveRange* range) {
+  LifetimePosition previous = range->Start();
+  for (UsePosition *pos = range->NextRegisterPosition(previous); pos != nullptr;
+       previous = previous.NextFullStart(),
+                   pos = range->NextRegisterPosition(previous)) {
+    LifetimePosition optimal = FindOptimalSplitPos(previous, pos->pos());
+    LifetimePosition before =
+        GetSplitPositionForInstruction(range, optimal.ToInstructionIndex());
+    if (before.IsValid()) return before;
+    LifetimePosition after = GetSplitPositionForInstruction(
+        range, pos->pos().ToInstructionIndex() + 1);
+    if (after.IsValid()) return after;
+  }
+  return LifetimePosition::Invalid();
+}
+
+
+bool GreedyAllocator::IsProgressPossible(const LiveRange* range) {
+  return range->CanBeSpilled(range->Start()) ||
+         GetLastResortSplitPosition(range).IsValid();
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8