[turbofan] LiveRange splinter merging optimizations.

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 409 matching lines @@
 
 
 LiveRange* LiveRange::SplitAt(LifetimePosition position, Zone* zone) {
   int new_id = TopLevel()->GetNextChildId();
   LiveRange* child = new (zone) LiveRange(new_id, machine_type(), TopLevel());
   DetachAt(position, child, zone);
 
   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) {
   DCHECK(Start() < 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
@@ skipping 76 matching lines @@
   result->Verify();
 #endif
 }
 
 
 void LiveRange::AppendAsChild(TopLevelLiveRange* other) {
   next_ = other;
 
   other->UpdateParentForAllChildren(TopLevel());
   TopLevel()->UpdateSpillRangePostMerge(other);
+  TopLevel()->set_last_child(other->last_child());
 }
 
 
 void LiveRange::UpdateParentForAllChildren(TopLevelLiveRange* new_top_level) {
   LiveRange* child = this;
   for (; child != nullptr; child = child->next()) {
     child->top_level_ = new_top_level;
   }
 }
 
@@ skipping 122 matching lines @@
 
 
 TopLevelLiveRange::TopLevelLiveRange(int vreg, MachineType machine_type)
     : LiveRange(0, machine_type, this),
       vreg_(vreg),
       last_child_id_(0),
       splintered_from_(nullptr),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr),
       spilled_in_deferred_blocks_(false),
-      spill_start_index_(kMaxInt) {
+      spill_start_index_(kMaxInt),
+      last_child_(this),
+      last_insertion_point_(this) {
   bits_ |= SpillTypeField::encode(SpillType::kNoSpillType);
 }
 
 
 void TopLevelLiveRange::SpillAtDefinition(Zone* zone, int gap_index,
                                           InstructionOperand* operand) {
   DCHECK(HasNoSpillType());
   spills_at_definition_ = new (zone)
       SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
 }
@@ skipping 195 matching lines @@
   if (HasNoSpillType() && merged->HasSpillRange()) {
     set_spill_type(merged->spill_type());
     DCHECK(GetSpillRange()->live_ranges().size() > 0);
     merged->spill_range_ = nullptr;
     merged->bits_ =
         SpillTypeField::update(merged->bits_, SpillType::kNoSpillType);
   }
 }
 
 
-LiveRange* TopLevelLiveRange::GetLastChild() {
-  LiveRange* ret = this;
-  for (; ret->next() != nullptr; ret = ret->next()) {
-  }
-  return ret;
-}
-
-
 void TopLevelLiveRange::Merge(TopLevelLiveRange* other,
                               RegisterAllocationData* data) {
   DCHECK(Start() < other->Start());
+  DCHECK(other->splintered_from() == this);
 
   data->live_ranges()[other->vreg()] = nullptr;
 
-  LiveRange* last_other = other->GetLastChild();
-  LiveRange* last_me = GetLastChild();
+  LiveRange* last_other = other->last_child();
+  LiveRange* last_me = last_child();
 
   // Simple case: we just append at the end.
   if (last_me->End() <= other->Start()) return last_me->AppendAsChild(other);
 
   DCHECK(last_me->End() > last_other->End());
 
   // In the more general case, we need to find the ranges between which to
   // insert.
-  LiveRange* insertion_point = this;
-  for (; insertion_point->next() != nullptr &&
-         insertion_point->next()->Start() <= other->Start();
-       insertion_point = insertion_point->next()) {
+  if (other->Start() < last_insertion_point_->Start()) {
+    last_insertion_point_ = this;
+  }
+
+  for (; last_insertion_point_->next() != nullptr &&
+         last_insertion_point_->next()->Start() <= other->Start();
+       last_insertion_point_ = last_insertion_point_->next()) {
   }
 
   // When we splintered the original range, we reconstituted the original range
   // into one range without children, but with discontinuities. To merge the
   // splinter back in, we need to split the range - or a child obtained after
   // register allocation splitting.
-  LiveRange* after = insertion_point->next();
-  if (insertion_point->End() > other->Start()) {
+  LiveRange* after = last_insertion_point_->next();
+  if (last_insertion_point_->End() > other->Start()) {
     LiveRange* new_after =
-        insertion_point->SplitAt(other->Start(), data->allocation_zone());
-    new_after->set_spilled(insertion_point->spilled());
+        last_insertion_point_->SplitAt(other->Start(), data->allocation_zone());
+    new_after->set_spilled(last_insertion_point_->spilled());
     if (!new_after->spilled())
-      new_after->set_assigned_register(insertion_point->assigned_register());
+      new_after->set_assigned_register(
+          last_insertion_point_->assigned_register());
     after = new_after;
   }
 
   last_other->next_ = after;
-  insertion_point->next_ = other;
+  last_insertion_point_->next_ = other;
   other->UpdateParentForAllChildren(TopLevel());
   TopLevel()->UpdateSpillRangePostMerge(other);
 }
 
 
 void TopLevelLiveRange::ShortenTo(LifetimePosition start) {
   TRACE("Shorten live range %d to [%d\n", vreg(), start.value());
   DCHECK(first_interval_ != nullptr);
   DCHECK(first_interval_->start() <= start);
   DCHECK(start < first_interval_->end());
@@ skipping 2355 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