[turbofan] break link between split use intervals

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 94 matching lines @@
 }
 
 
 void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
   DCHECK_IMPLIES(type == UsePositionType::kRequiresSlot, !register_beneficial);
   flags_ = TypeField::encode(type) |
            RegisterBeneficialField::encode(register_beneficial);
 }
 
 
-void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
+UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
   DCHECK(Contains(pos) && pos.Value() != start().Value());
   auto after = new (zone) UseInterval(pos, end_);
   after->next_ = next_;
-  next_ = after;
+  next_ = nullptr;
   end_ = pos;
+  return after;
 }
 
 
 struct LiveRange::SpillAtDefinitionList : ZoneObject {
   SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
                         SpillAtDefinitionList* next)
       : gap_index(gap_index), operand(operand), next(next) {}
   const int gap_index;
   InstructionOperand* const operand;
   SpillAtDefinitionList* const next;
@@ skipping 16 matching lines @@
       current_interval_(nullptr),
       last_processed_use_(nullptr),
       current_hint_operand_(nullptr),
       spill_start_index_(kMaxInt),
       spill_type_(SpillType::kNoSpillType),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr) {}
 
 
 void LiveRange::Verify() const {
-  UsePosition* cur = first_pos_;
-  while (cur != nullptr) {
-    CHECK(Start().Value() <= cur->pos().Value() &&
-          cur->pos().Value() <= End().Value());
-    cur = cur->next();
+  // Walk the positions, verifying that each is in an interval.
+  auto interval = first_interval_;
+  for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
+    CHECK(Start().Value() <= pos->pos().Value());
+    CHECK(pos->pos().Value() <= End().Value());
+    CHECK(interval != nullptr);
+    while (!interval->Contains(pos->pos()) &&
+           interval->end().Value() != pos->pos().Value()) {
+      interval = interval->next();
+      CHECK(interval != nullptr);
+    }
   }
 }
 
 
-bool LiveRange::HasOverlap(UseInterval* target) const {
-  UseInterval* current_interval = first_interval_;
-  while (current_interval != nullptr) {
-    // Intervals overlap if the start of one is contained in the other.
-    if (current_interval->Contains(target->start()) ||
-        target->Contains(current_interval->start())) {
-      return true;
-    }
-    current_interval = current_interval->next();
-  }
-  return false;
-}
-
-
 void LiveRange::set_assigned_register(int reg) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
 }
 
 
 void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
   DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
@@ skipping 169 matching lines @@
 
   // If the split position coincides with the beginning of a use interval
   // we need to split use positons in a special way.
   bool split_at_start = false;
 
   if (current->start().Value() == position.Value()) {
     // When splitting at start we need to locate the previous use interval.
     current = first_interval_;
   }
 
+  UseInterval* after = nullptr;
   while (current != nullptr) {
     if (current->Contains(position)) {
-      current->SplitAt(position, zone);
+      after = current->SplitAt(position, zone);
       break;
     }
     auto next = current->next();
     if (next->start().Value() >= position.Value()) {
       split_at_start = (next->start().Value() == position.Value());
       break;
     }
     current = next;
   }
 
   // Partition original use intervals to the two live ranges.
   auto before = current;
-  auto after = before->next();
+  if (after == nullptr) after = before->next();
   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_;
@@ skipping 230 matching lines @@
       if (interval2->end().Value() > interval1->start().Value()) {
         return true;
       }
       interval2 = interval2->next();
     }
   }
   return false;
 }
 
 
-SpillRange::SpillRange(LiveRange* range, Zone* zone) : live_ranges_(zone) {
-  auto src = range->first_interval();
+SpillRange::SpillRange(LiveRange* parent, Zone* zone) : live_ranges_(zone) {
+  DCHECK(!parent->IsChild());
   UseInterval* result = nullptr;
   UseInterval* node = nullptr;
-  // Copy the nodes
-  while (src != nullptr) {
-    auto new_node = new (zone) UseInterval(src->start(), src->end());
-    if (result == nullptr) {
-      result = new_node;
-    } else {
-      node->set_next(new_node);
+  // Copy the intervals for all ranges.
+  for (auto range = parent; range != nullptr; range = range->next()) {
+    auto src = range->first_interval();
+    while (src != nullptr) {
+      auto new_node = new (zone) UseInterval(src->start(), src->end());
+      if (result == nullptr) {
+        result = new_node;
+      } else {
+        node->set_next(new_node);
+      }
+      node = new_node;
+      src = src->next();
     }
-    node = new_node;
-    src = src->next();
   }
   use_interval_ = result;
-  live_ranges().push_back(range);
+  live_ranges().push_back(parent);
   end_position_ = node->end();
-  DCHECK(!range->HasSpillRange());
-  range->SetSpillRange(this);
+  DCHECK(!parent->HasSpillRange());
+  parent->SetSpillRange(this);
 }
 
 
 bool SpillRange::IsIntersectingWith(SpillRange* other) const {
   if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
       this->End().Value() <= other->use_interval_->start().Value() ||
       other->End().Value() <= this->use_interval_->start().Value()) {
     return false;
   }
   return AreUseIntervalsIntersecting(use_interval_, other->use_interval_);
@@ skipping 2199 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