[turbofan] Alternative splintering mechanism.

src/compiler/live-range-separator.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/live-range-separator.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 {
 
-// Starting from a deferred block, find the last consecutive deferred block.
-RpoNumber GetLastDeferredBlock(const InstructionBlock *block,
-                               const InstructionSequence *code) {
-  DCHECK(block->IsDeferred());
-  RpoNumber first = block->rpo_number();
-
-  RpoNumber last = first;
-  for (int i = first.ToInt(); i < code->InstructionBlockCount(); ++i) {
-    RpoNumber at_i = RpoNumber::FromInt(i);
-    const InstructionBlock *block_at_i = code->InstructionBlockAt(at_i);
-    if (!block_at_i->IsDeferred()) break;
-    last = at_i;
-  }
-
-  return last;
-}
-
-
-// Delimits consecutive deferred block sequences.
-void AssociateDeferredBlockSequences(InstructionSequence *code) {
-  for (int blk_id = 0; blk_id < code->InstructionBlockCount(); ++blk_id) {
-    InstructionBlock *block =
-        code->InstructionBlockAt(RpoNumber::FromInt(blk_id));
-    if (!block->IsDeferred()) continue;
-    RpoNumber last = GetLastDeferredBlock(block, code);
-    block->set_last_deferred(last);
-    // We know last is still deferred, and that last + 1, is not (or is an
-    // invalid index). So skip over last + 1 and continue from last + 2. This
-    // way, we visit each block exactly once, and the total complexity of this
-    // function is O(n), n being jthe number of blocks.
-    blk_id = last.ToInt() + 1;
-  }
-}
-
 
 void CreateSplinter(TopLevelLiveRange *range, RegisterAllocationData *data,
                     LifetimePosition first_cut, LifetimePosition last_cut) {
   DCHECK(!range->IsSplinter());
   // We can ignore ranges that live solely in deferred blocks.
   // If a range ends right at the end of a deferred block, it is marked by
   // the range builder as ending at gap start of the next block - since the
   // end is a position where the variable isn't live. We need to take that
   // into consideration.
   LifetimePosition max_allowed_end = last_cut.NextFullStart();
@@ skipping 16 matching lines @@
     TopLevelLiveRange *result = data->NextLiveRange(range->machine_type());
     DCHECK_NULL(data->live_ranges()[result->vreg()]);
     data->live_ranges()[result->vreg()] = result;
 
     Zone *zone = data->allocation_zone();
     range->Splinter(start, end, result, zone);
   }
 }
 
 
-// Splinter all ranges live inside successive deferred blocks.
-// No control flow analysis is performed. After the register allocation, we will
-// merge the splinters back into the original ranges, and then rely on the
-// range connector to properly connect them.
-void SplinterRangesInDeferredBlocks(RegisterAllocationData *data) {
-  InstructionSequence *code = data->code();
-  int code_block_count = code->InstructionBlockCount();
-  Zone *zone = data->allocation_zone();
-  ZoneVector<BitVector *> &in_sets = data->live_in_sets();
+int FirstInstruction(const UseInterval *interval) {
+  LifetimePosition start = interval->start();
+  int ret = start.ToInstructionIndex();
+  if (start.IsInstructionPosition() && start.IsEnd()) {
+    ++ret;
+  }
+  return ret;
+}
 
-  for (int i = 0; i < code_block_count; ++i) {
-    InstructionBlock *block = code->InstructionBlockAt(RpoNumber::FromInt(i));
-    if (!block->IsDeferred()) continue;
 
-    RpoNumber last_deferred = block->last_deferred();
-    // last_deferred + 1 is not deferred, so no point in visiting it.
-    i = last_deferred.ToInt() + 1;
+int LastInstruction(const UseInterval *interval) {
+  LifetimePosition end = interval->end();
+  int ret = end.ToInstructionIndex();
+  if (end.IsGapPosition() || end.IsStart()) {
+    --ret;
+  }
+  return ret;
+}
 
-    LifetimePosition first_cut = LifetimePosition::GapFromInstructionIndex(
-        block->first_instruction_index());
 
-    LifetimePosition last_cut = LifetimePosition::GapFromInstructionIndex(
-        static_cast<int>(code->instructions().size()));
+void SplinterLiveRange(TopLevelLiveRange *range, RegisterAllocationData *data) {
+  const InstructionSequence *code = data->code();
+  UseInterval *interval = range->first_interval();
 
-    const BitVector *in_set = in_sets[block->rpo_number().ToInt()];
-    BitVector ranges_to_splinter(*in_set, zone);
-    InstructionBlock *last = code->InstructionBlockAt(last_deferred);
-    for (int deferred_id = block->rpo_number().ToInt();
-         deferred_id <= last->rpo_number().ToInt(); ++deferred_id) {
-      const BitVector *ins = in_sets[deferred_id];
-      ranges_to_splinter.Union(*ins);
-      const BitVector *outs = LiveRangeBuilder::ComputeLiveOut(
-          code->InstructionBlockAt(RpoNumber::FromInt(deferred_id)), data);
-      ranges_to_splinter.Union(*outs);
+  LifetimePosition first_cut = LifetimePosition::Invalid();
+  LifetimePosition last_cut = LifetimePosition::Invalid();
+
+  while (interval != nullptr) {
+    UseInterval *next_interval = interval->next();
+    const InstructionBlock *first_block =
+        code->GetInstructionBlock(FirstInstruction(interval));
+    const InstructionBlock *last_block =
+        code->GetInstructionBlock(LastInstruction(interval));
+    int first_block_nr = first_block->rpo_number().ToInt();
+    int last_block_nr = last_block->rpo_number().ToInt();
+    for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
+      const InstructionBlock *current_block =
+          code->InstructionBlockAt(RpoNumber::FromInt(block_id));
+      if (current_block->IsDeferred()) {
+        if (!first_cut.IsValid()) {
+          first_cut = LifetimePosition::GapFromInstructionIndex(
+              current_block->first_instruction_index());
+        }
+        last_cut = LifetimePosition::GapFromInstructionIndex(
+            current_block->last_instruction_index());
+      } else {
+        if (first_cut.IsValid()) {
+          CreateSplinter(range, data, first_cut, last_cut);
+          first_cut = LifetimePosition::Invalid();
+          last_cut = LifetimePosition::Invalid();
+        }
+      }
     }
-
-    int last_index = last->last_instruction_index();
-    if (code->InstructionAt(last_index)->opcode() ==
-        ArchOpcode::kArchDeoptimize) {
-      ++last_index;
-    }
-    last_cut = LifetimePosition::GapFromInstructionIndex(last_index);
-
-    BitVector::Iterator iterator(&ranges_to_splinter);
-
-    while (!iterator.Done()) {
-      int range_id = iterator.Current();
-      iterator.Advance();
-
-      TopLevelLiveRange *range = data->live_ranges()[range_id];
-      CreateSplinter(range, data, first_cut, last_cut);
-    }
+    interval = next_interval;
+  }
+  // When the range ends in deferred blocks, first_cut will be valid here.
+  if (first_cut.IsValid()) {
+    CreateSplinter(range, data, first_cut, range->End());
   }
 }
 }  // namespace
 
 
 void LiveRangeSeparator::Splinter() {
-  AssociateDeferredBlockSequences(data()->code());
-  SplinterRangesInDeferredBlocks(data());
+  size_t virt_reg_count = data()->live_ranges().size();
+  for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
+    TopLevelLiveRange *range = data()->live_ranges()[vreg];
+    if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
+      continue;
+    }
+    SplinterLiveRange(range, data());
+  }
 }
 
 
 void LiveRangeMerger::Merge() {
   int live_range_count = static_cast<int>(data()->live_ranges().size());
   for (int i = 0; i < live_range_count; ++i) {
     TopLevelLiveRange *range = data()->live_ranges()[i];
     if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
       continue;
     }
     TopLevelLiveRange *splinter_parent = range->splintered_from();
 
     int to_remove = range->vreg();
     splinter_parent->Merge(range, data()->allocation_zone());
     data()->live_ranges()[to_remove] = nullptr;
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8