[turbofan] reduce ResolveControlFlow overhead.

src/compiler/register-allocator.cc

 // Copyright 2014 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/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 3156 matching lines @@
       }
     }
   }
 }
 
 
 namespace {
 
 class LiveRangeBound {
  public:
-  explicit LiveRangeBound(const LiveRange* range)
-      : range_(range), start_(range->Start()), end_(range->End()) {
+  explicit LiveRangeBound(const LiveRange* range, bool skip)
+      : range_(range), start_(range->Start()), end_(range->End()), skip_(skip) {
     DCHECK(!range->IsEmpty());
   }
 
   bool CanCover(LifetimePosition position) {
     return start_ <= position && position < end_;
   }
 
   const LiveRange* const range_;
   const LifetimePosition start_;
   const LifetimePosition end_;
+  const bool skip_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBound);
 };
 
 
 struct FindResult {
   const LiveRange* cur_cover_;
   const LiveRange* pred_cover_;
 };
 
 
 class LiveRangeBoundArray {
  public:
   LiveRangeBoundArray() : length_(0), start_(nullptr) {}
 
   bool ShouldInitialize() { return start_ == nullptr; }
 
-  void Initialize(Zone* zone, const LiveRange* const range) {
-    size_t length = 0;
-    for (auto i = range; i != nullptr; i = i->next()) length++;
-    start_ = zone->NewArray<LiveRangeBound>(length);
-    length_ = length;
-    auto curr = start_;
-    for (auto i = range; i != nullptr; i = i->next(), ++curr) {
-      new (curr) LiveRangeBound(i);
+  void Initialize(Zone* zone, const TopLevelLiveRange* const range) {
+    length_ = range->GetChildCount();
+
+    start_ = zone->NewArray<LiveRangeBound>(length_);
+    LiveRangeBound* curr = start_;
+    // Normally, spilled ranges do not need connecting moves, because the spill
+    // location has been assigned at definition. For ranges spilled in deferred
+    // blocks, that is not the case, so we need to connect the spilled children.
+    bool spilled_in_blocks = range->IsSpilledOnlyInDeferredBlocks();
+    for (const LiveRange *i = range; i != nullptr; i = i->next(), ++curr) {
+      new (curr) LiveRangeBound(i, !spilled_in_blocks && i->spilled());
     }
   }
 
   LiveRangeBound* Find(const LifetimePosition position) const {
     size_t left_index = 0;
     size_t right_index = length_;
     while (true) {
       size_t current_index = left_index + (right_index - left_index) / 2;
       DCHECK(right_index > current_index);
       auto bound = &start_[current_index];
@@ skipping 12 matching lines @@
         pred->last_instruction_index());
     return Find(pred_end);
   }
 
   LiveRangeBound* FindSucc(const InstructionBlock* succ) {
     auto succ_start = LifetimePosition::GapFromInstructionIndex(
         succ->first_instruction_index());
     return Find(succ_start);
   }
 
-  void Find(const InstructionBlock* block, const InstructionBlock* pred,
-            FindResult* result) const {
-    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
-        pred->last_instruction_index());
-    auto bound = Find(pred_end);
+  bool FindConnectableSubranges(const InstructionBlock* block,
+                                const InstructionBlock* pred,
+                                FindResult* result) const {
+    LifetimePosition pred_end =
+        LifetimePosition::InstructionFromInstructionIndex(
+            pred->last_instruction_index());
+    LiveRangeBound* bound = Find(pred_end);
     result->pred_cover_ = bound->range_;
-    auto cur_start = LifetimePosition::GapFromInstructionIndex(
+    LifetimePosition cur_start = LifetimePosition::GapFromInstructionIndex(
         block->first_instruction_index());
-    // Common case.
+
     if (bound->CanCover(cur_start)) {
-      result->cur_cover_ = bound->range_;
-      return;
+      // Both blocks are covered by the same range, so there is nothing to
+      // connect.
+      return false;
     }
-    result->cur_cover_ = Find(cur_start)->range_;
+    bound = Find(cur_start);
+    if (bound->skip_) {
+      return false;
+    }
+    result->cur_cover_ = bound->range_;
     DCHECK(result->pred_cover_ != nullptr && result->cur_cover_ != nullptr);
+    return (result->cur_cover_ != result->pred_cover_);
   }
 
  private:
   size_t length_;
   LiveRangeBound* start_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRangeBoundArray);
 };
 
 
@@ skipping 67 matching lines @@
   auto& live_in_sets = data()->live_in_sets();
   for (auto block : code()->instruction_blocks()) {
     if (CanEagerlyResolveControlFlow(block)) continue;
     auto live = live_in_sets[block->rpo_number().ToInt()];
     BitVector::Iterator iterator(live);
     while (!iterator.Done()) {
       auto* array = finder.ArrayFor(iterator.Current());
       for (auto pred : block->predecessors()) {
         FindResult result;
         const auto* pred_block = code()->InstructionBlockAt(pred);
-        array->Find(block, pred_block, &result);
-        if (result.cur_cover_ == result.pred_cover_ ||
-            (!result.cur_cover_->TopLevel()->IsSpilledOnlyInDeferredBlocks() &&
-             result.cur_cover_->spilled()))
+        if (!array->FindConnectableSubranges(block, pred_block, &result)) {
           continue;
+        }
         auto pred_op = result.pred_cover_->GetAssignedOperand();
         auto cur_op = result.cur_cover_->GetAssignedOperand();
         if (pred_op.Equals(cur_op)) continue;
         ResolveControlFlow(block, cur_op, pred_block, pred_op);
       }
       iterator.Advance();
     }
   }
 }
 
@@ skipping 91 matching lines @@
     auto eliminate = moves->PrepareInsertAfter(move);
     to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8