[turbofan] Splinter into one range.

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 680 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),
       last_child_(this),
-      last_insertion_point_(this) {
+      last_pos_(nullptr),
+      splinter_(nullptr) {
   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 126 matching lines @@
       return StackSlotOperand(machine_type(), index);
     case DOUBLE_REGISTERS:
       return DoubleStackSlotOperand(machine_type(), index);
   }
   UNREACHABLE();
   return StackSlotOperand(kMachNone, 0);
 }
 
 
 void TopLevelLiveRange::Splinter(LifetimePosition start, LifetimePosition end,
-                                 TopLevelLiveRange* result, Zone* zone) {
+                                 Zone* zone) {
   DCHECK(start != Start() || end != End());
   DCHECK(start < end);
 
-  result->set_spill_type(spill_type());
-
+  TopLevelLiveRange splinter_temp(-1, machine_type());
+  UsePosition* last_in_splinter = nullptr;
   if (start <= Start()) {
     // TODO(mtrofin): here, the TopLevel part is in the deferred range, so we
     // may want to continue processing the splinter. However, if the value is
     // defined in a cold block, and then used in a hot block, it follows that
     // it should terminate on the RHS of a phi, defined on the hot path. We
     // should check this, however, this may not be the place, because we don't
     // have access to the instruction sequence.
     DCHECK(end < End());
-    DetachAt(end, result, zone);
+    DetachAt(end, &splinter_temp, zone);
     next_ = nullptr;
   } else if (end >= End()) {
     DCHECK(start > Start());
-    DetachAt(start, result, zone);
+    DetachAt(start, &splinter_temp, zone);
     next_ = nullptr;
   } else {
     DCHECK(start < End() && Start() < end);
 
     const int kInvalidId = std::numeric_limits<int>::max();
 
-    UsePosition* last = DetachAt(start, result, zone);
+    UsePosition* last = DetachAt(start, &splinter_temp, zone);
 
     LiveRange end_part(kInvalidId, this->machine_type(), nullptr);
-    result->DetachAt(end, &end_part, zone);
+    last_in_splinter = splinter_temp.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 {
       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();
+  if (splinter()->IsEmpty()) {
+    splinter()->first_interval_ = splinter_temp.first_interval_;
+    splinter()->last_interval_ = splinter_temp.last_interval_;
+  } else {
+    splinter()->last_interval_->set_next(splinter_temp.first_interval_);
+    splinter()->last_interval_ = splinter_temp.last_interval_;
+  }
+  if (splinter()->first_pos() == nullptr) {
+    splinter()->first_pos_ = splinter_temp.first_pos_;
+  } else {
+    splinter()->last_pos_->set_next(splinter_temp.first_pos_);
+  }
+  if (last_in_splinter != nullptr) {
+    splinter()->last_pos_ = last_in_splinter;
+  } else {
+    if (splinter()->first_pos() != nullptr &&
+        splinter()->last_pos_ == nullptr) {
+      splinter()->last_pos_ = splinter()->first_pos();
+      for (UsePosition* pos = splinter()->first_pos(); pos != nullptr;
+           pos = pos->next()) {
+        splinter()->last_pos_ = pos;
+      }
+    }
+  }
+#if DEBUG
+  Verify();
+  splinter()->Verify();
+#endif
 }
 
 
 void TopLevelLiveRange::SetSplinteredFrom(TopLevelLiveRange* splinter_parent) {
-  // The splinter parent is always the original "Top".
-  DCHECK(splinter_parent->Start() < Start());
-
   splintered_from_ = splinter_parent;
   if (!HasSpillOperand() && splinter_parent->spill_range_ != nullptr) {
     SetSpillRange(splinter_parent->spill_range_);
   }
 }
 
 
 void TopLevelLiveRange::UpdateSpillRangePostMerge(TopLevelLiveRange* merged) {
   DCHECK(merged->TopLevel() == this);
 
   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);
   }
 }
 
 
 void TopLevelLiveRange::Merge(TopLevelLiveRange* other, Zone* zone) {
   DCHECK(Start() < other->Start());
   DCHECK(other->splintered_from() == this);
 
-  LiveRange* last_other = other->last_child();
-  LiveRange* last_me = last_child();
+  LiveRange* first = this;
+  LiveRange* second = other;
+  DCHECK(first->Start() < second->Start());
+  while (first != nullptr && second != nullptr) {
+    DCHECK(first != second);
+    // Make sure the ranges are in order each time we iterate.
+    if (second->Start() < first->Start()) {
+      LiveRange* tmp = second;
+      second = first;
+      first = tmp;
+      continue;
+    }
 
-  // Simple case: we just append at the end.
-  if (last_me->End() <= other->Start()) return last_me->AppendAsChild(other);
+    if (first->End() <= second->Start()) {
+      if (first->next() == nullptr ||
+          first->next()->Start() > second->Start()) {
+        // First is in order before second.
+        LiveRange* temp = first->next();
+        first->next_ = second;
+        first = temp;
+      } else {
+        // First is in order before its successor (or second), so advance first.
+        first = first->next();
+      }
+      continue;
+    }
 
-  DCHECK(last_me->End() > last_other->End());
+    DCHECK(first->Start() < second->Start());
+    // If first and second intersect, split first.
+    if (first->Start() < second->End() && second->Start() < first->End()) {
+      LiveRange* temp = first->SplitAt(second->Start(), zone);

[Benedikt Meurer, 2015/10/15 13:26:54]

I ran into an endless loop here with stress variant on
mjsunit/strong/implicit-conversions in release mode for
checkArgumentCombinations(), where it runs in this loop forever, always
splitting first and never making progress. I was unable to reproduce the issue
with debug, even inserting printf's magically fixed the problem, so that seems
to be a really weird edge case. But at least we know that there is some way to
enter an endless loop here. Please take another look.

 
-  // In the more general case, we need to find the ranges between which to
-  // insert.
-  if (other->Start() < last_insertion_point_->Start()) {
-    last_insertion_point_ = this;
+      temp->set_spilled(first->spilled());
+      if (!temp->spilled())
+        temp->set_assigned_register(first->assigned_register());
+
+      first->next_ = second;
+      first = temp;
+      continue;
+    }
+    DCHECK(first->End() <= second->Start());
   }
 
-  for (; last_insertion_point_->next() != nullptr &&
-         last_insertion_point_->next()->Start() <= other->Start();
-       last_insertion_point_ = last_insertion_point_->next()) {
-  }
+  TopLevel()->UpdateParentForAllChildren(TopLevel());
+  TopLevel()->UpdateSpillRangePostMerge(other);
 
-  // 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 = last_insertion_point_->next();
-  if (last_insertion_point_->End() > other->Start()) {
-    LiveRange* new_after = last_insertion_point_->SplitAt(other->Start(), zone);
-    new_after->set_spilled(last_insertion_point_->spilled());
-    if (!new_after->spilled())
-      new_after->set_assigned_register(
-          last_insertion_point_->assigned_register());
-    after = new_after;
-  }
-
-  last_other->next_ = after;
-  last_insertion_point_->next_ = other;
-  other->UpdateParentForAllChildren(TopLevel());
-  TopLevel()->UpdateSpillRangePostMerge(other);
+#if DEBUG
+  Verify();
+#endif
 }
 
 
 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());
   first_interval_->set_start(start);
 }
@@ skipping 2383 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