[turbofan] More efficient splintering.

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 248 matching lines @@
     : relative_id_(relative_id),
       bits_(0),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
       top_level_(top_level),
       next_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
       current_hint_position_(nullptr),
+      splitting_pointer_(nullptr),
       size_(kInvalidSize),
       weight_(kInvalidWeight),
       group_(nullptr) {
   DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
   bits_ = AssignedRegisterField::encode(kUnassignedRegister) |
           MachineTypeField::encode(machine_type);
 }
 
 
 void LiveRange::Verify() const {
@@ skipping 169 matching lines @@
   child->top_level_ = TopLevel();
   child->next_ = next_;
   next_ = child;
   if (child->next() == nullptr) {
     TopLevel()->set_last_child(child);
   }
   return child;
 }
 
 
-void LiveRange::DetachAt(LifetimePosition position, LiveRange* result,
-                         Zone* zone) {
+UsePosition* LiveRange::DetachAt(LifetimePosition position, LiveRange* result,
+                                 Zone* zone) {
   DCHECK(Start() < position);
   DCHECK(End() > position);
   DCHECK(result->IsEmpty());
   // Find the last interval that ends before the position. If the
   // position is contained in one of the intervals in the chain, we
   // split that interval and use the first part.
   auto current = FirstSearchIntervalForPosition(position);
 
   // If the split position coincides with the beginning of a use interval
   // we need to split use positons in a special way.
@@ skipping 25 matching lines @@
   auto before = current;
   result->last_interval_ =
       (last_interval_ == before)
           ? after            // Only interval in the range after split.
           : last_interval_;  // Last interval of the original range.
   result->first_interval_ = after;
   last_interval_ = before;
 
   // Find the last use position before the split and the first use
   // position after it.
-  auto use_after = first_pos_;
+  auto use_after =
+      splitting_pointer_ == nullptr || splitting_pointer_->pos() > position
+          ? first_pos()
+          : splitting_pointer_;
   UsePosition* use_before = nullptr;
   if (split_at_start) {
     // The split position coincides with the beginning of a use interval (the
     // end of a lifetime hole). Use at this position should be attributed to
     // the split child because split child owns use interval covering it.
     while (use_after != nullptr && use_after->pos() < position) {
       use_before = use_after;
       use_after = use_after->next();
     }
   } else {
@@ skipping 17 matching lines @@
   current_interval_ = nullptr;
 
   // Invalidate size and weight of this range. The child range has them
   // invalid at construction.
   size_ = kInvalidSize;
   weight_ = kInvalidWeight;
 #ifdef DEBUG
   Verify();
   result->Verify();
 #endif
+  return use_before;
 }
 
 
 void LiveRange::AppendAsChild(TopLevelLiveRange* other) {
   next_ = other;
 
   other->UpdateParentForAllChildren(TopLevel());
   TopLevel()->UpdateSpillRangePostMerge(other);
   TopLevel()->set_last_child(other->last_child());
 }
@@ skipping 305 matching lines @@
     next_ = nullptr;
   } else if (end >= End()) {
     DCHECK(start > Start());
     DetachAt(start, result, zone);
     next_ = nullptr;
   } else {
     DCHECK(start < End() && Start() < end);
 
     const int kInvalidId = std::numeric_limits<int>::max();
 
-    DetachAt(start, result, zone);
+    UsePosition* last = DetachAt(start, result, zone);
 
     LiveRange end_part(kInvalidId, this->machine_type(), nullptr);
     result->DetachAt(end, &end_part, zone);
 
     next_ = end_part.next_;
     last_interval_->set_next(end_part.first_interval_);
     // The next splinter will happen either at or after the current interval.
     // We can optimize DetachAt by setting current_interval_ accordingly,
     // which will then be picked up by FirstSearchIntervalForPosition.
     current_interval_ = last_interval_;
     last_interval_ = end_part.last_interval_;
 
-
     if (first_pos_ == nullptr) {
       first_pos_ = end_part.first_pos_;
     } else {
-      UsePosition* pos = first_pos_;
-      for (; pos->next() != nullptr; pos = pos->next()) {
-      }
-      pos->set_next(end_part.first_pos_);
+      splitting_pointer_ = last;
+      if (last != nullptr) last->set_next(end_part.first_pos_);
     }
   }
   result->next_ = nullptr;
   result->top_level_ = result;
 
   result->SetSplinteredFrom(this);
   // Ensure the result's relative ID is unique within the IDs used for this
   // virtual register's children and splinters.
   result->relative_id_ = GetNextChildId();
 }
@@ skipping 2460 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