[turbofan] Separate LiveRange and TopLevelLiveRange concepts

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 212 matching lines @@
   }
   if (pos.IsStart()) {
     os << 's';
   } else {
     os << 'e';
   }
   return os;
 }
 
 
-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;
-};
-
-
 const float LiveRange::kInvalidWeight = -1;
 const float LiveRange::kMaxWeight = std::numeric_limits<float>::max();
 
 
-LiveRange::LiveRange(int id, MachineType machine_type)
-    : id_(id),
-      spill_start_index_(kMaxInt),
+LiveRange::LiveRange(int relative_id, MachineType machine_type,
+                     TopLevelLiveRange* parent)
+    : relative_id_(relative_id),
       bits_(0),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
-      parent_(nullptr),
+      parent_(parent),
       next_(nullptr),
-      splintered_from_(nullptr),
-      spill_operand_(nullptr),
-      spills_at_definition_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
       current_hint_position_(nullptr),
       size_(kInvalidSize),
-      weight_(kInvalidWeight),
-      spilled_in_deferred_block_(false) {
+      weight_(kInvalidWeight) {
   DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
-  bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
-          AssignedRegisterField::encode(kUnassignedRegister) |
+  bits_ = AssignedRegisterField::encode(kUnassignedRegister) |
           MachineTypeField::encode(machine_type);
 }
 
 
 void LiveRange::Verify() const {
   // 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() <= pos->pos());
     CHECK(pos->pos() <= End());
@@ skipping 31 matching lines @@
     case kRepFloat32:
     case kRepFloat64:
       return DOUBLE_REGISTERS;
     default:
       break;
   }
   return GENERAL_REGISTERS;
 }
 
 
-void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
-                                  InstructionOperand* operand) {
-  DCHECK(HasNoSpillType());
-  spills_at_definition_ = new (zone)
-      SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
-}
-
-
-bool LiveRange::TryCommitSpillInDeferredBlock(
-    InstructionSequence* code, const InstructionOperand& spill_operand) {
-  DCHECK(!IsChild());
-
-  if (!FLAG_turbo_preprocess_ranges || IsEmpty() || HasNoSpillType() ||
-      spill_operand.IsConstant() || spill_operand.IsImmediate()) {
-    return false;
-  }
-
-  int count = 0;
-  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
-    int first_instr = child->Start().ToInstructionIndex();
-
-    // If the range starts at instruction end, the first instruction index is
-    // the next one.
-    if (!child->Start().IsGapPosition() && !child->Start().IsStart()) {
-      ++first_instr;
-    }
-
-    // We only look at where the range starts. It doesn't matter where it ends:
-    // if it ends past this block, then either there is a phi there already,
-    // or ResolveControlFlow will adapt the last instruction gap of this block
-    // as if there were a phi. In either case, data flow will be correct.
-    const InstructionBlock* block = code->GetInstructionBlock(first_instr);
-
-    // If we have slot uses in a subrange, bail out, because we need the value
-    // on the stack before that use.
-    bool has_slot_use = child->NextSlotPosition(child->Start()) != nullptr;
-    if (!block->IsDeferred()) {
-      if (child->spilled() || has_slot_use) {
-        TRACE(
-            "Live Range %d must be spilled at definition: found a "
-            "slot-requiring non-deferred child range %d.\n",
-            TopLevel()->id(), child->id());
-        return false;
-      }
-    } else {
-      if (child->spilled() || has_slot_use) ++count;
-    }
-  }
-  if (count == 0) return false;
-
-  spill_start_index_ = -1;
-  spilled_in_deferred_block_ = true;
-
-  TRACE("Live Range %d will be spilled only in deferred blocks.\n", id());
-  // If we have ranges that aren't spilled but require the operand on the stack,
-  // make sure we insert the spill.
-  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
-    if (!child->spilled() &&
-        child->NextSlotPosition(child->Start()) != nullptr) {
-      auto instr = code->InstructionAt(child->Start().ToInstructionIndex());
-      // Insert spill at the end to let live range connections happen at START.
-      auto move =
-          instr->GetOrCreateParallelMove(Instruction::END, code->zone());
-      InstructionOperand assigned = child->GetAssignedOperand();
-      if (TopLevel()->has_slot_use()) {
-        bool found = false;
-        for (auto move_op : *move) {
-          if (move_op->IsEliminated()) continue;
-          if (move_op->source().Equals(assigned) &&
-              move_op->destination().Equals(spill_operand)) {
-            found = true;
-            break;
-          }
-        }
-        if (found) continue;
-      }
-
-      move->AddMove(assigned, spill_operand);
-    }
-  }
-
-  return true;
-}
-
-
-void LiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence,
-                                         const InstructionOperand& op,
-                                         bool might_be_duplicated) {
-  DCHECK_IMPLIES(op.IsConstant(), spills_at_definition_ == nullptr);
-  DCHECK(!IsChild());
-  auto zone = sequence->zone();
-
-  for (auto to_spill = spills_at_definition_; to_spill != nullptr;
-       to_spill = to_spill->next) {
-    auto instr = sequence->InstructionAt(to_spill->gap_index);
-    auto move = instr->GetOrCreateParallelMove(Instruction::START, zone);
-    // Skip insertion if it's possible that the move exists already as a
-    // constraint move from a fixed output register to a slot.
-    if (might_be_duplicated) {
-      bool found = false;
-      for (auto move_op : *move) {
-        if (move_op->IsEliminated()) continue;
-        if (move_op->source().Equals(*to_spill->operand) &&
-            move_op->destination().Equals(op)) {
-          found = true;
-          break;
-        }
-      }
-      if (found) continue;
-    }
-    move->AddMove(*to_spill->operand, op);
-  }
-}
-
-
 UsePosition* LiveRange::FirstHintPosition(int* register_index) const {
   for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
     if (pos->HintRegister(register_index)) return pos;
   }
   return nullptr;
 }
 
 
-void LiveRange::SetSpillOperand(InstructionOperand* operand) {
-  DCHECK(HasNoSpillType());
-  DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
-  set_spill_type(SpillType::kSpillOperand);
-  spill_operand_ = operand;
-}
-
-
-void LiveRange::SetSpillRange(SpillRange* spill_range) {
-  DCHECK(!HasSpillOperand());
-  DCHECK(spill_range);
-  DCHECK(!IsChild());
-  spill_range_ = spill_range;
-}
-
-
 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const {
   UsePosition* use_pos = last_processed_use_;
   if (use_pos == nullptr || use_pos->pos() > start) {
     use_pos = first_pos();
   }
   while (use_pos != nullptr && use_pos->pos() < start) {
     use_pos = use_pos->next();
   }
   last_processed_use_ = use_pos;
   return use_pos;
@@ skipping 64 matching lines @@
   DCHECK(!HasRegisterAssigned());
   if (TopLevel()->HasSpillOperand()) {
     auto op = TopLevel()->GetSpillOperand();
     DCHECK(!op->IsUnallocated());
     return *op;
   }
   return TopLevel()->GetSpillRangeOperand();
 }
 
 
-AllocatedOperand LiveRange::GetSpillRangeOperand() const {
-  auto spill_range = GetSpillRange();
-  int index = spill_range->assigned_slot();
-  switch (kind()) {
-    case GENERAL_REGISTERS:
-      return StackSlotOperand(machine_type(), index);
-    case DOUBLE_REGISTERS:
-      return DoubleStackSlotOperand(machine_type(), index);
-  }
-  UNREACHABLE();
-  return StackSlotOperand(kMachNone, 0);
-}
-
-
 UseInterval* LiveRange::FirstSearchIntervalForPosition(
     LifetimePosition position) const {
   if (current_interval_ == nullptr) return first_interval_;
   if (current_interval_->start() > position) {
     current_interval_ = nullptr;
     return first_interval_;
   }
   return current_interval_;
 }
 
 
 void LiveRange::AdvanceLastProcessedMarker(
     UseInterval* to_start_of, LifetimePosition but_not_past) const {
   if (to_start_of == nullptr) return;
   if (to_start_of->start() > but_not_past) return;
   auto start = current_interval_ == nullptr ? LifetimePosition::Invalid()
                                             : current_interval_->start();
   if (to_start_of->start() > start) {
     current_interval_ = to_start_of;
   }
 }
 
 
-void LiveRange::SplitAt(LifetimePosition position, LiveRange* result,
-                        Zone* zone) {
+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->parent_ = TopLevel();
+  child->next_ = next_;
+  next_ = 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
   // 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.
   bool split_at_start = false;
@@ skipping 54 matching lines @@
   } else {
     first_pos_ = nullptr;
   }
   result->first_pos_ = use_after;
 
   // Discard cached iteration state. It might be pointing
   // to the use that no longer belongs to this live range.
   last_processed_use_ = nullptr;
   current_interval_ = nullptr;
 
-  // Link the new live range in the chain before any of the other
-  // ranges linked from the range before the split.
-  result->parent_ = (parent_ == nullptr) ? this : parent_;
-  result->next_ = next_;
-  next_ = result;
-
   // 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
 }
 
 
-void LiveRange::Splinter(LifetimePosition start, LifetimePosition end,
-                         LiveRange* result, Zone* zone) {
+void LiveRange::AppendAsChild(TopLevelLiveRange* other) {
+  next_ = other;
+
+  other->UpdateParentForAllChildren(TopLevel());
+  TopLevel()->UpdateSpillRangePostMerge(other);
+}
+
+
+void LiveRange::UpdateParentForAllChildren(TopLevelLiveRange* new_parent) {
+  LiveRange* child = this;
+  for (; child != nullptr; child = child->next()) {
+    child->parent_ = new_parent;
+  }
+}
+
+
+void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
+                                     const InstructionOperand& spill_op) {
+  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
+    DCHECK(Start() <= pos->pos() && pos->pos() <= End());
+    if (!pos->HasOperand()) continue;
+    switch (pos->type()) {
+      case UsePositionType::kRequiresSlot:
+        DCHECK(spill_op.IsStackSlot() || spill_op.IsDoubleStackSlot());
+        InstructionOperand::ReplaceWith(pos->operand(), &spill_op);
+        break;
+      case UsePositionType::kRequiresRegister:
+        DCHECK(op.IsRegister() || op.IsDoubleRegister());
+      // Fall through.
+      case UsePositionType::kAny:
+        InstructionOperand::ReplaceWith(pos->operand(), &op);
+        break;
+    }
+  }
+}
+
+
+// This implements an ordering on live ranges so that they are ordered by their
+// start positions.  This is needed for the correctness of the register
+// allocation algorithm.  If two live ranges start at the same offset then there
+// is a tie breaker based on where the value is first used.  This part of the
+// ordering is merely a heuristic.
+bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
+  LifetimePosition start = Start();
+  LifetimePosition other_start = other->Start();
+  if (start == other_start) {
+    UsePosition* pos = first_pos();
+    if (pos == nullptr) return false;
+    UsePosition* other_pos = other->first_pos();
+    if (other_pos == nullptr) return true;
+    return pos->pos() < other_pos->pos();
+  }
+  return start < other_start;
+}
+
+
+void LiveRange::SetUseHints(int register_index) {
+  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
+    if (!pos->HasOperand()) continue;
+    switch (pos->type()) {
+      case UsePositionType::kRequiresSlot:
+        break;
+      case UsePositionType::kRequiresRegister:
+      case UsePositionType::kAny:
+        pos->set_assigned_register(register_index);
+        break;
+    }
+  }
+}
+
+
+bool LiveRange::CanCover(LifetimePosition position) const {
+  if (IsEmpty()) return false;
+  return Start() <= position && position < End();
+}
+
+
+bool LiveRange::Covers(LifetimePosition position) const {
+  if (!CanCover(position)) return false;
+  auto start_search = FirstSearchIntervalForPosition(position);
+  for (auto interval = start_search; interval != nullptr;
+       interval = interval->next()) {
+    DCHECK(interval->next() == nullptr ||
+           interval->next()->start() >= interval->start());
+    AdvanceLastProcessedMarker(interval, position);
+    if (interval->Contains(position)) return true;
+    if (interval->start() > position) return false;
+  }
+  return false;
+}
+
+
+LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const {
+  auto b = other->first_interval();
+  if (b == nullptr) return LifetimePosition::Invalid();
+  auto advance_last_processed_up_to = b->start();
+  auto a = FirstSearchIntervalForPosition(b->start());
+  while (a != nullptr && b != nullptr) {
+    if (a->start() > other->End()) break;
+    if (b->start() > End()) break;
+    auto cur_intersection = a->Intersect(b);
+    if (cur_intersection.IsValid()) {
+      return cur_intersection;
+    }
+    if (a->start() < b->start()) {
+      a = a->next();
+      if (a == nullptr || a->start() > other->End()) break;
+      AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
+    } else {
+      b = b->next();
+    }
+  }
+  return LifetimePosition::Invalid();
+}
+
+
+unsigned LiveRange::GetSize() {
+  if (size_ == kInvalidSize) {
+    size_ = 0;
+    for (auto interval = first_interval(); interval != nullptr;
+         interval = interval->next()) {
+      size_ += (interval->end().value() - interval->start().value());
+    }
+  }
+
+  return static_cast<unsigned>(size_);
+}
+
+
+struct TopLevelLiveRange::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;
+};
+
+
+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) {
+  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_);
+}
+
+
+bool TopLevelLiveRange::TryCommitSpillInDeferredBlock(
+    InstructionSequence* code, const InstructionOperand& spill_operand) {
+  if (!FLAG_turbo_preprocess_ranges || IsEmpty() || HasNoSpillType() ||
+      spill_operand.IsConstant() || spill_operand.IsImmediate()) {
+    return false;
+  }
+
+  int count = 0;
+  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
+    int first_instr = child->Start().ToInstructionIndex();
+
+    // If the range starts at instruction end, the first instruction index is
+    // the next one.
+    if (!child->Start().IsGapPosition() && !child->Start().IsStart()) {
+      ++first_instr;
+    }
+
+    // We only look at where the range starts. It doesn't matter where it ends:
+    // if it ends past this block, then either there is a phi there already,
+    // or ResolveControlFlow will adapt the last instruction gap of this block
+    // as if there were a phi. In either case, data flow will be correct.
+    const InstructionBlock* block = code->GetInstructionBlock(first_instr);
+
+    // If we have slot uses in a subrange, bail out, because we need the value
+    // on the stack before that use.
+    bool has_slot_use = child->NextSlotPosition(child->Start()) != nullptr;
+    if (!block->IsDeferred()) {
+      if (child->spilled() || has_slot_use) {
+        TRACE(
+            "Live Range %d must be spilled at definition: found a "
+            "slot-requiring non-deferred child range %d.\n",
+            TopLevel()->vreg(), child->relative_id());
+        return false;
+      }
+    } else {
+      if (child->spilled() || has_slot_use) ++count;
+    }
+  }
+  if (count == 0) return false;
+
+  spill_start_index_ = -1;
+  spilled_in_deferred_blocks_ = true;
+
+  TRACE("Live Range %d will be spilled only in deferred blocks.\n", vreg());
+  // If we have ranges that aren't spilled but require the operand on the stack,
+  // make sure we insert the spill.
+  for (const LiveRange* child = this; child != nullptr; child = child->next()) {
+    if (!child->spilled() &&
+        child->NextSlotPosition(child->Start()) != nullptr) {
+      auto instr = code->InstructionAt(child->Start().ToInstructionIndex());
+      // Insert spill at the end to let live range connections happen at START.
+      auto move =
+          instr->GetOrCreateParallelMove(Instruction::END, code->zone());
+      InstructionOperand assigned = child->GetAssignedOperand();
+      if (TopLevel()->has_slot_use()) {
+        bool found = false;
+        for (auto move_op : *move) {
+          if (move_op->IsEliminated()) continue;
+          if (move_op->source().Equals(assigned) &&
+              move_op->destination().Equals(spill_operand)) {
+            found = true;
+            break;
+          }
+        }
+        if (found) continue;
+      }
+
+      move->AddMove(assigned, spill_operand);
+    }
+  }
+
+  return true;
+}
+
+
+void TopLevelLiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence,
+                                                 const InstructionOperand& op,
+                                                 bool might_be_duplicated) {
+  DCHECK_IMPLIES(op.IsConstant(), spills_at_definition_ == nullptr);
+  auto zone = sequence->zone();
+
+  for (auto to_spill = spills_at_definition_; to_spill != nullptr;
+       to_spill = to_spill->next) {
+    auto instr = sequence->InstructionAt(to_spill->gap_index);
+    auto move = instr->GetOrCreateParallelMove(Instruction::START, zone);
+    // Skip insertion if it's possible that the move exists already as a
+    // constraint move from a fixed output register to a slot.
+    if (might_be_duplicated) {
+      bool found = false;
+      for (auto move_op : *move) {
+        if (move_op->IsEliminated()) continue;
+        if (move_op->source().Equals(*to_spill->operand) &&
+            move_op->destination().Equals(op)) {
+          found = true;
+          break;
+        }
+      }
+      if (found) continue;
+    }
+    move->AddMove(*to_spill->operand, op);
+  }
+}
+
+
+void TopLevelLiveRange::SetSpillOperand(InstructionOperand* operand) {
+  DCHECK(HasNoSpillType());
+  DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
+  set_spill_type(SpillType::kSpillOperand);
+  spill_operand_ = operand;
+}
+
+
+void TopLevelLiveRange::SetSpillRange(SpillRange* spill_range) {
+  DCHECK(!HasSpillOperand());
+  DCHECK(spill_range);
+  spill_range_ = spill_range;
+}
+
+
+AllocatedOperand TopLevelLiveRange::GetSpillRangeOperand() const {
+  auto spill_range = GetSpillRange();
+  int index = spill_range->assigned_slot();
+  switch (kind()) {
+    case GENERAL_REGISTERS:
+      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) {
   DCHECK(start != Start() || end != End());
   DCHECK(start < end);
 
   result->set_spill_type(spill_type());
 
   if (start <= Start()) {
     DCHECK(end < End());
-    SplitAt(end, result, zone);
+    DetachAt(end, result, zone);
     next_ = nullptr;
   } else if (end >= End()) {
     DCHECK(start > Start());
-    SplitAt(start, result, zone);
+    DetachAt(start, result, zone);
     next_ = nullptr;
   } else {
     DCHECK(start < End() && Start() < end);
 
     const int kInvalidId = std::numeric_limits<int>::max();
 
-    SplitAt(start, result, zone);
+    DetachAt(start, result, zone);
 
-    LiveRange end_part(kInvalidId, this->machine_type());
-    result->SplitAt(end, &end_part, 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_);
     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_);
     }
   }
   result->next_ = nullptr;
-  result->parent_ = nullptr;
+  result->parent_ = result;
 
   result->SetSplinteredFrom(this);
 }
 
 
-void LiveRange::SetSplinteredFrom(LiveRange* splinter_parent) {
+void TopLevelLiveRange::SetSplinteredFrom(TopLevelLiveRange* splinter_parent) {
   // The splinter parent is always the original "Top".
   DCHECK(splinter_parent->Start() < Start());
-  DCHECK(!splinter_parent->IsChild());
 
   splintered_from_ = splinter_parent;
   if (!HasSpillOperand()) {
     SetSpillRange(splinter_parent->spill_range_);
   }
 }
 
 
-void LiveRange::AppendChild(LiveRange* other) {
-  DCHECK(!other->IsChild());
-  next_ = other;
-
-  other->UpdateParentForAllChildren(TopLevel());
-  TopLevel()->UpdateSpillRangePostMerge(other);
-}
-
-
-void LiveRange::UpdateSpillRangePostMerge(LiveRange* merged) {
-  DCHECK(!IsChild());
+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_,
-                                           LiveRange::SpillType::kNoSpillType);
+    merged->bits_ =
+        SpillTypeField::update(merged->bits_, SpillType::kNoSpillType);
   }
 }
 
 
-void LiveRange::UpdateParentForAllChildren(LiveRange* new_parent) {
-  LiveRange* child = this;
-  for (; child != nullptr; child = child->next()) {
-    child->parent_ = new_parent;
-  }
-}
-
-
-LiveRange* LiveRange::GetLastChild() {
+LiveRange* TopLevelLiveRange::GetLastChild() {
   LiveRange* ret = this;
   for (; ret->next() != nullptr; ret = ret->next()) {
   }
   return ret;
 }
 
 
-void LiveRange::Merge(LiveRange* other, RegisterAllocationData* data) {
-  DCHECK(!IsChild());
-  DCHECK(!other->IsChild());
+void TopLevelLiveRange::Merge(TopLevelLiveRange* other,
+                              RegisterAllocationData* data) {
   DCHECK(Start() < other->Start());
 
+  data->live_ranges()[other->vreg()] = nullptr;
+
   LiveRange* last_other = other->GetLastChild();
   LiveRange* last_me = GetLastChild();
 
   // Simple case: we just append at the end.
-  if (last_me->End() <= other->Start()) return last_me->AppendChild(other);
+  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()) {
   }
 
   // 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* new_after = data->NewChildRangeFor(insertion_point);
-    insertion_point->SplitAt(other->Start(), new_after,
-                             data->allocation_zone());
+    LiveRange* new_after =
+        insertion_point->SplitAt(other->Start(), data->allocation_zone());
     new_after->set_spilled(insertion_point->spilled());
     if (!new_after->spilled())
       new_after->set_assigned_register(insertion_point->assigned_register());
     after = new_after;
   }
 
   last_other->next_ = after;
   insertion_point->next_ = other;
   other->UpdateParentForAllChildren(TopLevel());
   TopLevel()->UpdateSpillRangePostMerge(other);
 }
 
 
-// This implements an ordering on live ranges so that they are ordered by their
-// start positions.  This is needed for the correctness of the register
-// allocation algorithm.  If two live ranges start at the same offset then there
-// is a tie breaker based on where the value is first used.  This part of the
-// ordering is merely a heuristic.
-bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
-  LifetimePosition start = Start();
-  LifetimePosition other_start = other->Start();
-  if (start == other_start) {
-    UsePosition* pos = first_pos();
-    if (pos == nullptr) return false;
-    UsePosition* other_pos = other->first_pos();
-    if (other_pos == nullptr) return true;
-    return pos->pos() < other_pos->pos();
-  }
-  return start < other_start;
-}
-
-
-void LiveRange::ShortenTo(LifetimePosition start) {
-  TRACE("Shorten live range %d to [%d\n", id_, start.value());
+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);
 }
 
 
-void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end,
-                               Zone* zone) {
-  TRACE("Ensure live range %d in interval [%d %d[\n", id_, start.value(),
+void TopLevelLiveRange::EnsureInterval(LifetimePosition start,
+                                       LifetimePosition end, Zone* zone) {
+  TRACE("Ensure live range %d in interval [%d %d[\n", vreg(), start.value(),
         end.value());
   auto new_end = end;
   while (first_interval_ != nullptr && first_interval_->start() <= end) {
     if (first_interval_->end() > end) {
       new_end = first_interval_->end();
     }
     first_interval_ = first_interval_->next();
   }
 
   auto new_interval = new (zone) UseInterval(start, new_end);
   new_interval->set_next(first_interval_);
   first_interval_ = new_interval;
   if (new_interval->next() == nullptr) {
     last_interval_ = new_interval;
   }
 }
 
 
-void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end,
-                               Zone* zone) {
-  TRACE("Add to live range %d interval [%d %d[\n", id_, start.value(),
+void TopLevelLiveRange::AddUseInterval(LifetimePosition start,
+                                       LifetimePosition end, Zone* zone) {
+  TRACE("Add to live range %d interval [%d %d[\n", vreg(), start.value(),
         end.value());
   if (first_interval_ == nullptr) {
     auto interval = new (zone) UseInterval(start, end);
     first_interval_ = interval;
     last_interval_ = interval;
   } else {
     if (end == first_interval_->start()) {
       first_interval_->set_start(start);
     } else if (end < first_interval_->start()) {
       auto interval = new (zone) UseInterval(start, end);
       interval->set_next(first_interval_);
       first_interval_ = interval;
     } else {
       // Order of instruction's processing (see ProcessInstructions) guarantees
       // that each new use interval either precedes or intersects with
       // last added interval.
       DCHECK(start < first_interval_->end());
       first_interval_->set_start(Min(start, first_interval_->start()));
       first_interval_->set_end(Max(end, first_interval_->end()));
     }
   }
 }
 
 
-void LiveRange::AddUsePosition(UsePosition* use_pos) {
+void TopLevelLiveRange::AddUsePosition(UsePosition* use_pos) {
   auto pos = use_pos->pos();
-  TRACE("Add to live range %d use position %d\n", id_, pos.value());
+  TRACE("Add to live range %d use position %d\n", vreg(), pos.value());
   UsePosition* prev_hint = nullptr;
   UsePosition* prev = nullptr;
   auto current = first_pos_;
   while (current != nullptr && current->pos() < pos) {
     prev_hint = current->HasHint() ? current : prev_hint;
     prev = current;
     current = current->next();
   }
 
   if (prev == nullptr) {
     use_pos->set_next(first_pos_);
     first_pos_ = use_pos;
   } else {
     use_pos->set_next(prev->next());
     prev->set_next(use_pos);
   }
 
   if (prev_hint == nullptr && use_pos->HasHint()) {
     current_hint_position_ = use_pos;
   }
 }
 
 
-void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
-                                     const InstructionOperand& spill_op) {
-  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
-    DCHECK(Start() <= pos->pos() && pos->pos() <= End());
-    if (!pos->HasOperand()) continue;
-    switch (pos->type()) {
-      case UsePositionType::kRequiresSlot:
-        DCHECK(spill_op.IsStackSlot() || spill_op.IsDoubleStackSlot());
-        InstructionOperand::ReplaceWith(pos->operand(), &spill_op);
-        break;
-      case UsePositionType::kRequiresRegister:
-        DCHECK(op.IsRegister() || op.IsDoubleRegister());
-      // Fall through.
-      case UsePositionType::kAny:
-        InstructionOperand::ReplaceWith(pos->operand(), &op);
-        break;
-    }
-  }
-}
-
-
-void LiveRange::SetUseHints(int register_index) {
-  for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
-    if (!pos->HasOperand()) continue;
-    switch (pos->type()) {
-      case UsePositionType::kRequiresSlot:
-        break;
-      case UsePositionType::kRequiresRegister:
-      case UsePositionType::kAny:
-        pos->set_assigned_register(register_index);
-        break;
-    }
-  }
-}
-
-
-bool LiveRange::CanCover(LifetimePosition position) const {
-  if (IsEmpty()) return false;
-  return Start() <= position && position < End();
-}
-
-
-bool LiveRange::Covers(LifetimePosition position) const {
-  if (!CanCover(position)) return false;
-  auto start_search = FirstSearchIntervalForPosition(position);
-  for (auto interval = start_search; interval != nullptr;
-       interval = interval->next()) {
-    DCHECK(interval->next() == nullptr ||
-           interval->next()->start() >= interval->start());
-    AdvanceLastProcessedMarker(interval, position);
-    if (interval->Contains(position)) return true;
-    if (interval->start() > position) return false;
-  }
-  return false;
-}
-
-
-LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const {
-  auto b = other->first_interval();
-  if (b == nullptr) return LifetimePosition::Invalid();
-  auto advance_last_processed_up_to = b->start();
-  auto a = FirstSearchIntervalForPosition(b->start());
-  while (a != nullptr && b != nullptr) {
-    if (a->start() > other->End()) break;
-    if (b->start() > End()) break;
-    auto cur_intersection = a->Intersect(b);
-    if (cur_intersection.IsValid()) {
-      return cur_intersection;
-    }
-    if (a->start() < b->start()) {
-      a = a->next();
-      if (a == nullptr || a->start() > other->End()) break;
-      AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
-    } else {
-      b = b->next();
-    }
-  }
-  return LifetimePosition::Invalid();
-}
-
-
-unsigned LiveRange::GetSize() {
-  if (size_ == kInvalidSize) {
-    size_ = 0;
-    for (auto interval = first_interval(); interval != nullptr;
-         interval = interval->next()) {
-      size_ += (interval->end().value() - interval->start().value());
-    }
-  }
-
-  return static_cast<unsigned>(size_);
-}
-
-
 static bool AreUseIntervalsIntersecting(UseInterval* interval1,
                                         UseInterval* interval2) {
   while (interval1 != nullptr && interval2 != nullptr) {
     if (interval1->start() < interval2->start()) {
       if (interval1->end() > interval2->start()) {
         return true;
       }
       interval1 = interval1->next();
     } else {
       if (interval2->end() > interval1->start()) {
         return true;
       }
       interval2 = interval2->next();
     }
   }
   return false;
 }
 
 
 std::ostream& operator<<(std::ostream& os,
                          const PrintableLiveRange& printable_range) {
   const LiveRange* range = printable_range.range_;
-  os << "Range: " << range->id() << " ";
-  if (range->is_phi()) os << "phi ";
-  if (range->is_non_loop_phi()) os << "nlphi ";
+  os << "Range: " << range->TopLevel()->vreg() << ":" << range->relative_id()
+     << " ";
+  if (range->TopLevel()->is_phi()) os << "phi ";
+  if (range->TopLevel()->is_non_loop_phi()) os << "nlphi ";
 
   os << "{" << std::endl;
   auto interval = range->first_interval();
   auto use_pos = range->first_pos();
   PrintableInstructionOperand pio;
   pio.register_configuration_ = printable_range.register_configuration_;
   while (use_pos != nullptr) {
     pio.op_ = *use_pos->operand();
     os << pio << use_pos->pos() << " ";
     use_pos = use_pos->next();
   }
   os << std::endl;
 
   while (interval != nullptr) {
     os << '[' << interval->start() << ", " << interval->end() << ')'
        << std::endl;
     interval = interval->next();
   }
   os << "}";
   return os;
 }
 
 
-SpillRange::SpillRange(LiveRange* parent, Zone* zone)
+SpillRange::SpillRange(TopLevelLiveRange* parent, Zone* zone)
     : live_ranges_(zone),
       assigned_slot_(kUnassignedSlot),
       byte_width_(GetByteWidth(parent->machine_type())),
       kind_(parent->kind()) {
   // Spill ranges are created for top level, non-splintered ranges. This is so
   // that, when merging decisions are made, we consider the full extent of the
   // virtual register, and avoid clobbering it.
-  DCHECK(!parent->IsChild());
   DCHECK(!parent->IsSplinter());
   UseInterval* result = nullptr;
   UseInterval* node = nullptr;
   // Copy the intervals for all ranges.
-  for (auto range = parent; range != nullptr; range = range->next()) {
+  for (LiveRange* 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();
@@ skipping 140 matching lines @@
   return moves->AddMove(from, to);
 }
 
 
 MachineType RegisterAllocationData::MachineTypeFor(int virtual_register) {
   DCHECK_LT(virtual_register, code()->VirtualRegisterCount());
   return code()->GetRepresentation(virtual_register);
 }
 
 
-LiveRange* RegisterAllocationData::LiveRangeFor(int index) {
+TopLevelLiveRange* RegisterAllocationData::GetOrCreateLiveRangeFor(int index) {
   if (index >= static_cast<int>(live_ranges().size())) {
     live_ranges().resize(index + 1, nullptr);
   }
   auto result = live_ranges()[index];
   if (result == nullptr) {
     result = NewLiveRange(index, MachineTypeFor(index));
     live_ranges()[index] = result;
   }
   return result;
 }
 
 
-LiveRange* RegisterAllocationData::NewLiveRange(int index,
-                                                MachineType machine_type) {
-  return new (allocation_zone()) LiveRange(index, machine_type);
+TopLevelLiveRange* RegisterAllocationData::NewLiveRange(
+    int index, MachineType machine_type) {
+  return new (allocation_zone()) TopLevelLiveRange(index, machine_type);
 }
 
 
-LiveRange* RegisterAllocationData::NextLiveRange(MachineType machine_type) {
+int RegisterAllocationData::GetNextLiveRangeId() {
   int vreg = virtual_register_count_++;
   if (vreg >= static_cast<int>(live_ranges().size())) {
     live_ranges().resize(vreg + 1, nullptr);
   }
-  LiveRange* ret = NewLiveRange(vreg, machine_type);
+  return vreg;
+}
+
+
+TopLevelLiveRange* RegisterAllocationData::NextLiveRange(
+    MachineType machine_type) {
+  int vreg = GetNextLiveRangeId();
+  TopLevelLiveRange* ret = NewLiveRange(vreg, machine_type);
   return ret;
 }
 
 
-LiveRange* RegisterAllocationData::NewChildRangeFor(LiveRange* range) {
-  auto child = NextLiveRange(range->machine_type());
-  DCHECK_NULL(live_ranges()[child->id()]);
-  live_ranges()[child->id()] = child;
-  return child;
-}
-
-
 RegisterAllocationData::PhiMapValue* RegisterAllocationData::InitializePhiMap(
     const InstructionBlock* block, PhiInstruction* phi) {
   auto map_value = new (allocation_zone())
       RegisterAllocationData::PhiMapValue(phi, block, allocation_zone());
   auto res =
       phi_map_.insert(std::make_pair(phi->virtual_register(), map_value));
   DCHECK(res.second);
   USE(res);
   return map_value;
 }
 
 
 RegisterAllocationData::PhiMapValue* RegisterAllocationData::GetPhiMapValueFor(
     int virtual_register) {
   auto it = phi_map_.find(virtual_register);
   DCHECK(it != phi_map_.end());
   return it->second;
 }
 
 
+RegisterAllocationData::PhiMapValue* RegisterAllocationData::GetPhiMapValueFor(
+    TopLevelLiveRange* top_range) {
+  return GetPhiMapValueFor(top_range->vreg());
+}
+
+
 bool RegisterAllocationData::ExistsUseWithoutDefinition() {
   bool found = false;
   BitVector::Iterator iterator(live_in_sets()[0]);
   while (!iterator.Done()) {
     found = true;
     int operand_index = iterator.Current();
     PrintF("Register allocator error: live v%d reached first block.\n",
            operand_index);
-    LiveRange* range = LiveRangeFor(operand_index);
+    LiveRange* range = GetOrCreateLiveRangeFor(operand_index);
     PrintF("  (first use is at %d)\n", range->first_pos()->pos().value());
     if (debug_name() == nullptr) {
       PrintF("\n");
     } else {
       PrintF("  (function: %s)\n", debug_name());
     }
     iterator.Advance();
   }
   return found;
 }
 
 
 SpillRange* RegisterAllocationData::AssignSpillRangeToLiveRange(
-    LiveRange* range) {
-  DCHECK(!range->IsChild());
+    TopLevelLiveRange* range) {
   DCHECK(!range->HasSpillOperand());
 
   SpillRange* spill_range = range->GetAllocatedSpillRange();
   if (spill_range == nullptr) {
     DCHECK(!range->IsSplinter());
     spill_range = new (allocation_zone()) SpillRange(range, allocation_zone());
   }
-  range->set_spill_type(LiveRange::SpillType::kSpillRange);
+  range->set_spill_type(TopLevelLiveRange::SpillType::kSpillRange);
 
   spill_ranges().insert(spill_range);
   return spill_range;
 }
 
 
 SpillRange* RegisterAllocationData::CreateSpillRangeForLiveRange(
-    LiveRange* range) {
+    TopLevelLiveRange* range) {
   DCHECK(!range->HasSpillOperand());
-  DCHECK(!range->IsChild());
   DCHECK(!range->IsSplinter());
   auto spill_range =
       new (allocation_zone()) SpillRange(range, allocation_zone());
   return spill_range;
 }
 
 
 void RegisterAllocationData::MarkAllocated(RegisterKind kind, int index) {
   if (kind == DOUBLE_REGISTERS) {
     assigned_double_registers_->Add(index);
@@ skipping 58 matching lines @@
   wrapper.op_ = move->destination();
   os << wrapper << " = ";
   wrapper.op_ = move->source();
   os << wrapper << std::endl;
 }
 
 
 void RegisterAllocationData::Print(const SpillRange* spill_range) {
   OFStream os(stdout);
   os << "{" << std::endl;
-  for (LiveRange* range : spill_range->live_ranges()) {
-    os << range->id() << " ";
+  for (TopLevelLiveRange* range : spill_range->live_ranges()) {
+    os << range->vreg() << " ";
   }
   os << std::endl;
 
   for (UseInterval* interval = spill_range->interval(); interval != nullptr;
        interval = interval->next()) {
     os << '[' << interval->start() << ", " << interval->end() << ')'
        << std::endl;
   }
   os << "}" << std::endl;
 }
@@ skipping 25 matching lines @@
   } else if (operand->HasFixedDoubleRegisterPolicy()) {
     DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, virtual_register);
     allocated = AllocatedOperand(AllocatedOperand::DOUBLE_REGISTER,
                                  machine_type, operand->fixed_register_index());
   } else {
     UNREACHABLE();
   }
   InstructionOperand::ReplaceWith(operand, &allocated);
   if (is_tagged) {
     TRACE("Fixed reg is tagged at %d\n", pos);
-    auto instr = InstructionAt(pos);
+    auto instr = code()->InstructionAt(pos);
     if (instr->HasReferenceMap()) {
       instr->reference_map()->RecordReference(*AllocatedOperand::cast(operand));
     }
   }
   return operand;
 }
 
 
 void ConstraintBuilder::MeetRegisterConstraints() {
   for (auto block : code()->instruction_blocks()) {
@@ skipping 11 matching lines @@
     if (i != end) MeetConstraintsAfter(i);
   }
   // Meet register constraints for the instruction in the end.
   MeetRegisterConstraintsForLastInstructionInBlock(block);
 }
 
 
 void ConstraintBuilder::MeetRegisterConstraintsForLastInstructionInBlock(
     const InstructionBlock* block) {
   int end = block->last_instruction_index();
-  auto last_instruction = InstructionAt(end);
+  auto last_instruction = code()->InstructionAt(end);
   for (size_t i = 0; i < last_instruction->OutputCount(); i++) {
     auto output_operand = last_instruction->OutputAt(i);
     DCHECK(!output_operand->IsConstant());
     auto output = UnallocatedOperand::cast(output_operand);
     int output_vreg = output->virtual_register();
-    auto range = LiveRangeFor(output_vreg);
+    auto range = data()->GetOrCreateLiveRangeFor(output_vreg);
     bool assigned = false;
     if (output->HasFixedPolicy()) {
       AllocateFixed(output, -1, false);
       // This value is produced on the stack, we never need to spill it.
       if (output->IsStackSlot()) {
         DCHECK(StackSlotOperand::cast(output)->index() <
                data()->frame()->GetSpillSlotCount());
         range->SetSpillOperand(StackSlotOperand::cast(output));
         range->SetSpillStartIndex(end);
         assigned = true;
@@ skipping 17 matching lines @@
         int gap_index = successor->first_instruction_index();
         range->SpillAtDefinition(allocation_zone(), gap_index, output);
         range->SetSpillStartIndex(gap_index);
       }
     }
   }
 }
 
 
 void ConstraintBuilder::MeetConstraintsAfter(int instr_index) {
-  auto first = InstructionAt(instr_index);
+  auto first = code()->InstructionAt(instr_index);
   // Handle fixed temporaries.
   for (size_t i = 0; i < first->TempCount(); i++) {
     auto temp = UnallocatedOperand::cast(first->TempAt(i));
     if (temp->HasFixedPolicy()) AllocateFixed(temp, instr_index, false);
   }
   // Handle constant/fixed output operands.
   for (size_t i = 0; i < first->OutputCount(); i++) {
     InstructionOperand* output = first->OutputAt(i);
     if (output->IsConstant()) {
       int output_vreg = ConstantOperand::cast(output)->virtual_register();
-      auto range = LiveRangeFor(output_vreg);
+      auto range = data()->GetOrCreateLiveRangeFor(output_vreg);
       range->SetSpillStartIndex(instr_index + 1);
       range->SetSpillOperand(output);
       continue;
     }
     auto first_output = UnallocatedOperand::cast(output);
-    auto range = LiveRangeFor(first_output->virtual_register());
+    auto range =
+        data()->GetOrCreateLiveRangeFor(first_output->virtual_register());
     bool assigned = false;
     if (first_output->HasFixedPolicy()) {
       int output_vreg = first_output->virtual_register();
       UnallocatedOperand output_copy(UnallocatedOperand::ANY, output_vreg);
-      bool is_tagged = IsReference(output_vreg);
+      bool is_tagged = code()->IsReference(output_vreg);
       AllocateFixed(first_output, instr_index, is_tagged);
 
       // This value is produced on the stack, we never need to spill it.
       if (first_output->IsStackSlot()) {
         DCHECK(StackSlotOperand::cast(first_output)->index() <
                data()->frame()->GetTotalFrameSlotCount());
         range->SetSpillOperand(StackSlotOperand::cast(first_output));
         range->SetSpillStartIndex(instr_index + 1);
         assigned = true;
       }
       data()->AddGapMove(instr_index + 1, Instruction::START, *first_output,
                          output_copy);
     }
     // Make sure we add a gap move for spilling (if we have not done
     // so already).
     if (!assigned) {
       range->SpillAtDefinition(allocation_zone(), instr_index + 1,
                                first_output);
       range->SetSpillStartIndex(instr_index + 1);
     }
   }
 }
 
 
 void ConstraintBuilder::MeetConstraintsBefore(int instr_index) {
-  auto second = InstructionAt(instr_index);
+  auto second = code()->InstructionAt(instr_index);
   // Handle fixed input operands of second instruction.
   for (size_t i = 0; i < second->InputCount(); i++) {
     auto input = second->InputAt(i);
     if (input->IsImmediate()) continue;  // Ignore immediates.
     auto cur_input = UnallocatedOperand::cast(input);
     if (cur_input->HasFixedPolicy()) {
       int input_vreg = cur_input->virtual_register();
       UnallocatedOperand input_copy(UnallocatedOperand::ANY, input_vreg);
-      bool is_tagged = IsReference(input_vreg);
+      bool is_tagged = code()->IsReference(input_vreg);
       AllocateFixed(cur_input, instr_index, is_tagged);
       data()->AddGapMove(instr_index, Instruction::END, input_copy, *cur_input);
     }
   }
   // Handle "output same as input" for second instruction.
   for (size_t i = 0; i < second->OutputCount(); i++) {
     auto output = second->OutputAt(i);
     if (!output->IsUnallocated()) continue;
     auto second_output = UnallocatedOperand::cast(output);
     if (!second_output->HasSameAsInputPolicy()) continue;
     DCHECK(i == 0);  // Only valid for first output.
     UnallocatedOperand* cur_input =
         UnallocatedOperand::cast(second->InputAt(0));
     int output_vreg = second_output->virtual_register();
     int input_vreg = cur_input->virtual_register();
     UnallocatedOperand input_copy(UnallocatedOperand::ANY, input_vreg);
     cur_input->set_virtual_register(second_output->virtual_register());
     auto gap_move = data()->AddGapMove(instr_index, Instruction::END,
                                        input_copy, *cur_input);
-    if (IsReference(input_vreg) && !IsReference(output_vreg)) {
+    if (code()->IsReference(input_vreg) && !code()->IsReference(output_vreg)) {
       if (second->HasReferenceMap()) {
         RegisterAllocationData::DelayedReference delayed_reference = {
             second->reference_map(), &gap_move->source()};
         data()->delayed_references().push_back(delayed_reference);
       }
-    } else if (!IsReference(input_vreg) && IsReference(output_vreg)) {
+    } else if (!code()->IsReference(input_vreg) &&
+               code()->IsReference(output_vreg)) {
       // The input is assumed to immediately have a tagged representation,
       // before the pointer map can be used. I.e. the pointer map at the
       // instruction will include the output operand (whose value at the
       // beginning of the instruction is equal to the input operand). If
       // this is not desired, then the pointer map at this instruction needs
       // to be adjusted manually.
     }
   }
 }
 
@@ skipping 12 matching lines @@
     auto map_value = data()->InitializePhiMap(block, phi);
     auto& output = phi->output();
     // Map the destination operands, so the commitment phase can find them.
     for (size_t i = 0; i < phi->operands().size(); ++i) {
       InstructionBlock* cur_block =
           code()->InstructionBlockAt(block->predecessors()[i]);
       UnallocatedOperand input(UnallocatedOperand::ANY, phi->operands()[i]);
       auto move = data()->AddGapMove(cur_block->last_instruction_index(),
                                      Instruction::END, input, output);
       map_value->AddOperand(&move->destination());
-      DCHECK(!InstructionAt(cur_block->last_instruction_index())
+      DCHECK(!code()
+                  ->InstructionAt(cur_block->last_instruction_index())
                   ->HasReferenceMap());
     }
-    auto live_range = LiveRangeFor(phi_vreg);
+    auto live_range = data()->GetOrCreateLiveRangeFor(phi_vreg);
     int gap_index = block->first_instruction_index();
     live_range->SpillAtDefinition(allocation_zone(), gap_index, &output);
     live_range->SetSpillStartIndex(gap_index);
     // We use the phi-ness of some nodes in some later heuristics.
     live_range->set_is_phi(true);
     live_range->set_is_non_loop_phi(!block->IsLoopHeader());
   }
 }
 
 
@@ skipping 35 matching lines @@
                                            BitVector* live_out) {
   // Add an interval that includes the entire block to the live range for
   // each live_out value.
   auto start = LifetimePosition::GapFromInstructionIndex(
       block->first_instruction_index());
   auto end = LifetimePosition::InstructionFromInstructionIndex(
                  block->last_instruction_index()).NextStart();
   BitVector::Iterator iterator(live_out);
   while (!iterator.Done()) {
     int operand_index = iterator.Current();
-    auto range = LiveRangeFor(operand_index);
+    auto range = data()->GetOrCreateLiveRangeFor(operand_index);
     range->AddUseInterval(start, end, allocation_zone());
     iterator.Advance();
   }
 }
 
 
 int LiveRangeBuilder::FixedDoubleLiveRangeID(int index) {
   return -index - 1 - config()->num_general_registers();
 }
 
 
-LiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) {
+TopLevelLiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) {
   DCHECK(index < config()->num_general_registers());
   auto result = data()->fixed_live_ranges()[index];
   if (result == nullptr) {
     result = data()->NewLiveRange(FixedLiveRangeID(index),
                                   InstructionSequence::DefaultRepresentation());
     DCHECK(result->IsFixed());
     result->set_assigned_register(index);
     data()->MarkAllocated(GENERAL_REGISTERS, index);
     data()->fixed_live_ranges()[index] = result;
   }
   return result;
 }
 
 
-LiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) {
+TopLevelLiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) {
   DCHECK(index < config()->num_aliased_double_registers());
   auto result = data()->fixed_double_live_ranges()[index];
   if (result == nullptr) {
     result = data()->NewLiveRange(FixedDoubleLiveRangeID(index), kRepFloat64);
     DCHECK(result->IsFixed());
     result->set_assigned_register(index);
     data()->MarkAllocated(DOUBLE_REGISTERS, index);
     data()->fixed_double_live_ranges()[index] = result;
   }
   return result;
 }
 
 
-LiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) {
+TopLevelLiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) {
   if (operand->IsUnallocated()) {
-    return LiveRangeFor(UnallocatedOperand::cast(operand)->virtual_register());
+    return data()->GetOrCreateLiveRangeFor(
+        UnallocatedOperand::cast(operand)->virtual_register());
   } else if (operand->IsConstant()) {
-    return LiveRangeFor(ConstantOperand::cast(operand)->virtual_register());
+    return data()->GetOrCreateLiveRangeFor(
+        ConstantOperand::cast(operand)->virtual_register());
   } else if (operand->IsRegister()) {
     return FixedLiveRangeFor(RegisterOperand::cast(operand)->index());
   } else if (operand->IsDoubleRegister()) {
     return FixedDoubleLiveRangeFor(
         DoubleRegisterOperand::cast(operand)->index());
   } else {
     return nullptr;
   }
 }
 
@@ skipping 109 matching lines @@
         use_pos = curr_position;
       } else {
         use_pos = curr_position.End();
       }
 
       if (input->IsUnallocated()) {
         UnallocatedOperand* unalloc = UnallocatedOperand::cast(input);
         int vreg = unalloc->virtual_register();
         live->Add(vreg);
         if (unalloc->HasSlotPolicy()) {
-          LiveRangeFor(vreg)->set_has_slot_use(true);
+          data()->GetOrCreateLiveRangeFor(vreg)->set_has_slot_use(true);
         }
       }
       Use(block_start_position, use_pos, input);
     }
 
     for (size_t i = 0; i < instr->TempCount(); i++) {
       auto temp = instr->TempAt(i);
       // Unsupported.
       DCHECK_IMPLIES(temp->IsUnallocated(),
                      !UnallocatedOperand::cast(temp)->HasSlotPolicy());
@@ skipping 25 matching lines @@
       }
       for (auto cur : *move) {
         auto& from = cur->source();
         auto& to = cur->destination();
         void* hint = &to;
         UsePositionHintType hint_type = UsePosition::HintTypeForOperand(to);
         UsePosition* to_use = nullptr;
         int phi_vreg = -1;
         if (to.IsUnallocated()) {
           int to_vreg = UnallocatedOperand::cast(to).virtual_register();
-          auto to_range = LiveRangeFor(to_vreg);
+          auto to_range = data()->GetOrCreateLiveRangeFor(to_vreg);
           if (to_range->is_phi()) {
             phi_vreg = to_vreg;
             if (to_range->is_non_loop_phi()) {
               hint = to_range->current_hint_position();
               hint_type = hint == nullptr ? UsePositionHintType::kNone
                                           : UsePositionHintType::kUsePos;
             } else {
               hint_type = UsePositionHintType::kPhi;
               hint = data()->GetPhiMapValueFor(to_vreg);
             }
@@ skipping 64 matching lines @@
   DCHECK(block->IsLoopHeader());
   // Add a live range stretching from the first loop instruction to the last
   // for each value live on entry to the header.
   BitVector::Iterator iterator(live);
   auto start = LifetimePosition::GapFromInstructionIndex(
       block->first_instruction_index());
   auto end = LifetimePosition::GapFromInstructionIndex(
                  code()->LastLoopInstructionIndex(block)).NextFullStart();
   while (!iterator.Done()) {
     int operand_index = iterator.Current();
-    auto range = LiveRangeFor(operand_index);
+    auto range = data()->GetOrCreateLiveRangeFor(operand_index);

[Benedikt Meurer, 2015/08/26 04:31:20]

Nit: please deautofy this.

[Mircea Trofin, 2015/08/26 05:00:13]

Done.

     range->EnsureInterval(start, end, allocation_zone());
     iterator.Advance();
   }
   // Insert all values into the live in sets of all blocks in the loop.
   for (int i = block->rpo_number().ToInt() + 1; i < block->loop_end().ToInt();
        ++i) {
     live_in_sets()[i]->Union(*live);
   }
 }
 
@@ skipping 61 matching lines @@
   if (it == phi_hints_.end()) return;
   DCHECK(!it->second->IsResolved());
   it->second->ResolveHint(use_pos);
 }
 
 
 void LiveRangeBuilder::Verify() const {
   for (auto& hint : phi_hints_) {
     CHECK(hint.second->IsResolved());
   }
-  for (auto current : data()->live_ranges()) {
+  for (LiveRange* current : data()->live_ranges()) {
     if (current != nullptr) current->Verify();
   }
 }
 
 
 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data,
                                      RegisterKind kind)
     : data_(data),
       mode_(kind),
       num_registers_(GetRegisterCount(data->config(), kind)) {}
 
 
 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range,
                                            LifetimePosition pos) {
-  DCHECK(!range->IsFixed());
-  TRACE("Splitting live range %d at %d\n", range->id(), pos.value());
+  DCHECK(!range->TopLevel()->IsFixed());
+  TRACE("Splitting live range %d:%d at %d\n", range->TopLevel()->vreg(),
+        range->relative_id(), pos.value());
 
   if (pos <= range->Start()) return range;
 
   // We can't properly connect liveranges if splitting occurred at the end
   // a block.
   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
          (GetInstructionBlock(code(), pos)->last_instruction_index() !=
           pos.ToInstructionIndex()));
 
-  auto result = data()->NewChildRangeFor(range);
-  range->SplitAt(pos, result, allocation_zone());
+  LiveRange* result = range->SplitAt(pos, allocation_zone());
   return result;
 }
 
 
 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
                                            LifetimePosition start,
                                            LifetimePosition end) {
-  DCHECK(!range->IsFixed());
-  TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(),
-        start.value(), end.value());
+  DCHECK(!range->TopLevel()->IsFixed());
+  TRACE("Splitting live range %d:%d in position between [%d, %d]\n",
+        range->TopLevel()->vreg(), range->relative_id(), start.value(),
+        end.value());
 
   auto split_pos = FindOptimalSplitPos(start, end);
   DCHECK(split_pos >= start);
   return SplitRangeAt(range, split_pos);
 }
 
 
 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start,
                                                         LifetimePosition end) {
   int start_instr = start.ToInstructionIndex();
@@ skipping 57 matching lines @@
     // Try hoisting out to an outer loop.
     loop_header = GetContainingLoop(code(), loop_header);
   }
 
   return pos;
 }
 
 
 void RegisterAllocator::Spill(LiveRange* range) {
   DCHECK(!range->spilled());
-  TRACE("Spilling live range %d\n", range->id());
-  auto first = range->TopLevel();
+  TopLevelLiveRange* first = range->TopLevel();
+  TRACE("Spilling live range %d:%d\n", first->vreg(), range->relative_id());
+
   if (first->HasNoSpillType()) {
     data()->AssignSpillRangeToLiveRange(first);
   }
   range->Spill();
 }
 
 
-const ZoneVector<LiveRange*>& RegisterAllocator::GetFixedRegisters() const {
+const ZoneVector<TopLevelLiveRange*>& RegisterAllocator::GetFixedRegisters()
+    const {
   return mode() == DOUBLE_REGISTERS ? data()->fixed_double_live_ranges()
                                     : data()->fixed_live_ranges();
 }
 
 
 const char* RegisterAllocator::RegisterName(int allocation_index) const {
   if (mode() == GENERAL_REGISTERS) {
     return data()->config()->general_register_name(allocation_index);
   } else {
     return data()->config()->double_register_name(allocation_index);
@@ skipping 16 matching lines @@
   DCHECK(RegisterConfiguration::kMaxDoubleRegisters >=
          this->data()->config()->num_general_registers());
 }
 
 
 void LinearScanAllocator::AllocateRegisters() {
   DCHECK(unhandled_live_ranges().empty());
   DCHECK(active_live_ranges().empty());
   DCHECK(inactive_live_ranges().empty());
 
-  for (auto range : data()->live_ranges()) {
+  for (LiveRange* range : data()->live_ranges()) {
     if (range == nullptr) continue;
     if (range->kind() == mode()) {
       AddToUnhandledUnsorted(range);
     }
   }
   SortUnhandled();
   DCHECK(UnhandledIsSorted());
 
   auto& fixed_ranges = GetFixedRegisters();
   for (auto current : fixed_ranges) {
     if (current != nullptr) {
       DCHECK_EQ(mode(), current->kind());
       AddToInactive(current);
     }
   }
 
   while (!unhandled_live_ranges().empty()) {
     DCHECK(UnhandledIsSorted());
     auto current = unhandled_live_ranges().back();
     unhandled_live_ranges().pop_back();
     DCHECK(UnhandledIsSorted());
     auto position = current->Start();
 #ifdef DEBUG
     allocation_finger_ = position;
 #endif
-    TRACE("Processing interval %d start=%d\n", current->id(), position.value());
+    TRACE("Processing interval %d:%d start=%d\n", current->TopLevel()->vreg(),
+          current->relative_id(), position.value());
 
-    if (!current->HasNoSpillType()) {
-      TRACE("Live range %d already has a spill operand\n", current->id());
+    if (current->IsTopLevel() && !current->TopLevel()->HasNoSpillType()) {
+      TRACE("Live range %d:%d already has a spill operand\n",
+            current->TopLevel()->vreg(), current->relative_id());
       auto next_pos = position;
       if (next_pos.IsGapPosition()) {
         next_pos = next_pos.NextStart();
       }
       auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
       // If the range already has a spill operand and it doesn't need a
       // register immediately, split it and spill the first part of the range.
       if (pos == nullptr) {
         Spill(current);
         continue;
       } else if (pos->pos() > current->Start().NextStart()) {
         // Do not spill live range eagerly if use position that can benefit from
         // the register is too close to the start of live range.
         SpillBetween(current, current->Start(), pos->pos());
         DCHECK(UnhandledIsSorted());
         continue;
       }
     }
 
-    if (TryReuseSpillForPhi(current)) continue;
+    if (current->IsTopLevel() && TryReuseSpillForPhi(current->TopLevel()))
+      continue;
 
     for (size_t i = 0; i < active_live_ranges().size(); ++i) {
       auto cur_active = active_live_ranges()[i];
       if (cur_active->End() <= position) {
         ActiveToHandled(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
       } else if (!cur_active->Covers(position)) {
         ActiveToInactive(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
       }
@@ skipping 19 matching lines @@
     }
   }
 }
 
 
 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
                                                        int reg) {
   data()->MarkAllocated(range->kind(), reg);
   range->set_assigned_register(reg);
   range->SetUseHints(reg);
-  if (range->is_phi()) {
-    data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg);
+  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
+    data()->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg);
   }
 }
 
 
 void LinearScanAllocator::AddToActive(LiveRange* range) {
-  TRACE("Add live range %d to active\n", range->id());
+  TRACE("Add live range %d:%d to active\n", range->TopLevel()->vreg(),
+        range->relative_id());
   active_live_ranges().push_back(range);
 }
 
 
 void LinearScanAllocator::AddToInactive(LiveRange* range) {
-  TRACE("Add live range %d to inactive\n", range->id());
+  TRACE("Add live range %d:%d to inactive\n", range->TopLevel()->vreg(),
+        range->relative_id());
   inactive_live_ranges().push_back(range);
 }
 
 
 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) {
   if (range == nullptr || range->IsEmpty()) return;
   DCHECK(!range->HasRegisterAssigned() && !range->spilled());
   DCHECK(allocation_finger_ <= range->Start());
   for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0;
        --i) {
     auto cur_range = unhandled_live_ranges().at(i);
     if (!range->ShouldBeAllocatedBefore(cur_range)) continue;
-    TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1);
+    TRACE("Add live range %d:%d to unhandled at %d\n",
+          range->TopLevel()->vreg(), range->relative_id(), i + 1);
     auto it = unhandled_live_ranges().begin() + (i + 1);
     unhandled_live_ranges().insert(it, range);
     DCHECK(UnhandledIsSorted());
     return;
   }
-  TRACE("Add live range %d to unhandled at start\n", range->id());
+  TRACE("Add live range %d:%d to unhandled at start\n",
+        range->TopLevel()->vreg(), range->relative_id());
   unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range);
   DCHECK(UnhandledIsSorted());
 }
 
 
 void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) {
   if (range == nullptr || range->IsEmpty()) return;
   DCHECK(!range->HasRegisterAssigned() && !range->spilled());
-  TRACE("Add live range %d to unhandled unsorted at end\n", range->id());
+  TRACE("Add live range %d:%d to unhandled unsorted at end\n",
+        range->TopLevel()->vreg(), range->relative_id());
   unhandled_live_ranges().push_back(range);
 }
 
 
 static bool UnhandledSortHelper(LiveRange* a, LiveRange* b) {
   DCHECK(!a->ShouldBeAllocatedBefore(b) || !b->ShouldBeAllocatedBefore(a));
   if (a->ShouldBeAllocatedBefore(b)) return false;
   if (b->ShouldBeAllocatedBefore(a)) return true;
-  return a->id() < b->id();
+  return a->TopLevel()->vreg() < b->TopLevel()->vreg();
 }
 
 
 // Sort the unhandled live ranges so that the ranges to be processed first are
 // at the end of the array list.  This is convenient for the register allocation
 // algorithm because it is efficient to remove elements from the end.
 void LinearScanAllocator::SortUnhandled() {
   TRACE("Sort unhandled\n");
   std::sort(unhandled_live_ranges().begin(), unhandled_live_ranges().end(),
             &UnhandledSortHelper);
 }
 
 
 bool LinearScanAllocator::UnhandledIsSorted() {
   size_t len = unhandled_live_ranges().size();
   for (size_t i = 1; i < len; i++) {
     auto a = unhandled_live_ranges().at(i - 1);
     auto b = unhandled_live_ranges().at(i);
     if (a->Start() < b->Start()) return false;
   }
   return true;
 }
 
 
 void LinearScanAllocator::ActiveToHandled(LiveRange* range) {
   RemoveElement(&active_live_ranges(), range);
-  TRACE("Moving live range %d from active to handled\n", range->id());
+  TRACE("Moving live range %d:%d from active to handled\n",
+        range->TopLevel()->vreg(), range->relative_id());
 }
 
 
 void LinearScanAllocator::ActiveToInactive(LiveRange* range) {
   RemoveElement(&active_live_ranges(), range);
   inactive_live_ranges().push_back(range);
-  TRACE("Moving live range %d from active to inactive\n", range->id());
+  TRACE("Moving live range %d:%d from active to inactive\n",
+        range->TopLevel()->vreg(), range->relative_id());
 }
 
 
 void LinearScanAllocator::InactiveToHandled(LiveRange* range) {
   RemoveElement(&inactive_live_ranges(), range);
-  TRACE("Moving live range %d from inactive to handled\n", range->id());
+  TRACE("Moving live range %d:%d from inactive to handled\n",
+        range->TopLevel()->vreg(), range->relative_id());
 }
 
 
 void LinearScanAllocator::InactiveToActive(LiveRange* range) {
   RemoveElement(&inactive_live_ranges(), range);
   active_live_ranges().push_back(range);
-  TRACE("Moving live range %d from inactive to active\n", range->id());
+  TRACE("Moving live range %d:%d from inactive to active\n",
+        range->TopLevel()->vreg(), range->relative_id());
 }
 
 
 bool LinearScanAllocator::TryAllocateFreeReg(LiveRange* current) {
   LifetimePosition free_until_pos[RegisterConfiguration::kMaxDoubleRegisters];
 
   for (int i = 0; i < num_registers(); i++) {
     free_until_pos[i] = LifetimePosition::MaxPosition();
   }
 
   for (auto cur_active : active_live_ranges()) {
     free_until_pos[cur_active->assigned_register()] =
         LifetimePosition::GapFromInstructionIndex(0);
   }
 
   for (auto cur_inactive : inactive_live_ranges()) {
     DCHECK(cur_inactive->End() > current->Start());
     auto next_intersection = cur_inactive->FirstIntersection(current);
     if (!next_intersection.IsValid()) continue;
     int cur_reg = cur_inactive->assigned_register();
     free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
   }
 
   int hint_register;
   if (current->FirstHintPosition(&hint_register) != nullptr) {
-    TRACE("Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
-          RegisterName(hint_register), free_until_pos[hint_register].value(),
-          current->id(), current->End().value());
+    TRACE(
+        "Found reg hint %s (free until [%d) for live range %d:%d (end %d[).\n",
+        RegisterName(hint_register), free_until_pos[hint_register].value(),
+        current->TopLevel()->vreg(), current->relative_id(),
+        current->End().value());
 
     // The desired register is free until the end of the current live range.
     if (free_until_pos[hint_register] >= current->End()) {
-      TRACE("Assigning preferred reg %s to live range %d\n",
-            RegisterName(hint_register), current->id());
+      TRACE("Assigning preferred reg %s to live range %d:%d\n",
+            RegisterName(hint_register), current->TopLevel()->vreg(),
+            current->relative_id());
       SetLiveRangeAssignedRegister(current, hint_register);
       return true;
     }
   }
 
   // Find the register which stays free for the longest time.
   int reg = 0;
   for (int i = 1; i < num_registers(); ++i) {
     if (free_until_pos[i] > free_until_pos[reg]) {
       reg = i;
@@ skipping 10 matching lines @@
   if (pos < current->End()) {
     // Register reg is available at the range start but becomes blocked before
     // the range end. Split current at position where it becomes blocked.
     auto tail = SplitRangeAt(current, pos);
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is available at the range start and is free until
   // the range end.
   DCHECK(pos >= current->End());
-  TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg),
-        current->id());
+  TRACE("Assigning free reg %s to live range %d:%d\n", RegisterName(reg),
+        current->TopLevel()->vreg(), current->relative_id());
   SetLiveRangeAssignedRegister(current, reg);
 
   return true;
 }
 
 
 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) {
   auto register_use = current->NextRegisterPosition(current->Start());
   if (register_use == nullptr) {
     // There is no use in the current live range that requires a register.
     // We can just spill it.
     Spill(current);
     return;
   }
 
   LifetimePosition use_pos[RegisterConfiguration::kMaxDoubleRegisters];
   LifetimePosition block_pos[RegisterConfiguration::kMaxDoubleRegisters];
 
   for (int i = 0; i < num_registers(); i++) {
     use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition();
   }
 
   for (auto range : active_live_ranges()) {
     int cur_reg = range->assigned_register();
-    if (range->IsFixed() || !range->CanBeSpilled(current->Start())) {
+    if (range->TopLevel()->IsFixed() ||
+        !range->CanBeSpilled(current->Start())) {
       block_pos[cur_reg] = use_pos[cur_reg] =
           LifetimePosition::GapFromInstructionIndex(0);
     } else {
       auto next_use =
           range->NextUsePositionRegisterIsBeneficial(current->Start());
       if (next_use == nullptr) {
         use_pos[cur_reg] = range->End();
       } else {
         use_pos[cur_reg] = next_use->pos();
       }
     }
   }
 
   for (auto range : inactive_live_ranges()) {
     DCHECK(range->End() > current->Start());
     auto next_intersection = range->FirstIntersection(current);
     if (!next_intersection.IsValid()) continue;
     int cur_reg = range->assigned_register();
-    if (range->IsFixed()) {
+    if (range->TopLevel()->IsFixed()) {
       block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection);
       use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]);
     } else {
       use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection);
     }
   }
 
   int reg = 0;
   for (int i = 1; i < num_registers(); ++i) {
     if (use_pos[i] > use_pos[reg]) {
@@ skipping 13 matching lines @@
   if (block_pos[reg] < current->End()) {
     // Register becomes blocked before the current range end. Split before that
     // position.
     LiveRange* tail =
         SplitBetween(current, current->Start(), block_pos[reg].Start());
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is not blocked for the whole range.
   DCHECK(block_pos[reg] >= current->End());
-  TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg),
-        current->id());
+  TRACE("Assigning blocked reg %s to live range %d:%d\n", RegisterName(reg),
+        current->TopLevel()->vreg(), current->relative_id());
   SetLiveRangeAssignedRegister(current, reg);
 
   // This register was not free. Thus we need to find and spill
   // parts of active and inactive live regions that use the same register
   // at the same lifetime positions as current.
   SplitAndSpillIntersecting(current);
 }
 
 
 void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
@@ skipping 19 matching lines @@
         SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
       }
       ActiveToHandled(range);
       --i;
     }
   }
 
   for (size_t i = 0; i < inactive_live_ranges().size(); ++i) {
     auto range = inactive_live_ranges()[i];
     DCHECK(range->End() > current->Start());
-    if (range->assigned_register() == reg && !range->IsFixed()) {
+    if (range->assigned_register() == reg && !range->TopLevel()->IsFixed()) {
       LifetimePosition next_intersection = range->FirstIntersection(current);
       if (next_intersection.IsValid()) {
         UsePosition* next_pos = range->NextRegisterPosition(current->Start());
         if (next_pos == nullptr) {
           SpillAfter(range, split_pos);
         } else {
           next_intersection = Min(next_intersection, next_pos->pos());
           SpillBetween(range, split_pos, next_intersection);
         }
         InactiveToHandled(range);
         --i;
       }
     }
   }
 }
 
 
-bool LinearScanAllocator::TryReuseSpillForPhi(LiveRange* range) {
-  if (range->IsChild() || !range->is_phi()) return false;
+bool LinearScanAllocator::TryReuseSpillForPhi(TopLevelLiveRange* range) {
+  if (!range->is_phi()) return false;
+
   DCHECK(!range->HasSpillOperand());
-  auto phi_map_value = data()->GetPhiMapValueFor(range->id());
+  auto phi_map_value = data()->GetPhiMapValueFor(range);
   auto phi = phi_map_value->phi();
   auto block = phi_map_value->block();
   // Count the number of spilled operands.
   size_t spilled_count = 0;
   LiveRange* first_op = nullptr;
   for (size_t i = 0; i < phi->operands().size(); i++) {
     int op = phi->operands()[i];
-    LiveRange* op_range = LiveRangeFor(op);
-    if (!op_range->HasSpillRange()) continue;
+    LiveRange* op_range = data()->GetOrCreateLiveRangeFor(op);
+    if (!op_range->TopLevel()->HasSpillRange()) continue;
     auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
     auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
         pred->last_instruction_index());
     while (op_range != nullptr && !op_range->CanCover(pred_end)) {
       op_range = op_range->next();
     }
     if (op_range != nullptr && op_range->spilled()) {
       spilled_count++;
       if (first_op == nullptr) {
         first_op = op_range->TopLevel();
       }
     }
   }
 
   // Only continue if more than half of the operands are spilled.
   if (spilled_count * 2 <= phi->operands().size()) {
     return false;
   }
 
   // Try to merge the spilled operands and count the number of merged spilled
   // operands.
   DCHECK(first_op != nullptr);
-  auto first_op_spill = first_op->GetSpillRange();
+  auto first_op_spill = first_op->TopLevel()->GetSpillRange();
   size_t num_merged = 1;
   for (size_t i = 1; i < phi->operands().size(); i++) {
     int op = phi->operands()[i];
-    auto op_range = LiveRangeFor(op);
+    auto op_range = data()->GetOrCreateLiveRangeFor(op);
     if (!op_range->HasSpillRange()) continue;
     auto op_spill = op_range->GetSpillRange();
     if (op_spill == first_op_spill || first_op_spill->TryMerge(op_spill)) {
       num_merged++;
     }
   }
 
   // Only continue if enough operands could be merged to the
   // same spill slot.
   if (num_merged * 2 <= phi->operands().size() ||
@@ skipping 72 matching lines @@
   }
 }
 
 
 SpillSlotLocator::SpillSlotLocator(RegisterAllocationData* data)
     : data_(data) {}
 
 
 void SpillSlotLocator::LocateSpillSlots() {
   auto code = data()->code();
-  for (auto range : data()->live_ranges()) {
-    if (range == nullptr || range->IsEmpty() || range->IsChild()) continue;
+  for (TopLevelLiveRange* range : data()->live_ranges()) {
+    if (range == nullptr || range->IsEmpty()) continue;
     // We care only about ranges which spill in the frame.
     if (!range->HasSpillRange()) continue;
     auto spills = range->spills_at_definition();
     DCHECK_NOT_NULL(spills);
     for (; spills != nullptr; spills = spills->next) {
       code->GetInstructionBlock(spills->gap_index)->mark_needs_frame();
     }
   }
 }
 
@@ skipping 21 matching lines @@
     if (range->IsEmpty()) continue;
     // Allocate a new operand referring to the spill slot.
     int byte_width = range->ByteWidth();
     int index = data()->frame()->AllocateSpillSlot(byte_width);
     range->set_assigned_slot(index);
   }
 }
 
 
 void OperandAssigner::CommitAssignment() {
-  for (auto range : data()->live_ranges()) {
-    if (range == nullptr || range->IsEmpty()) continue;
+  for (TopLevelLiveRange* top_range : data()->live_ranges()) {
+    if (top_range == nullptr || top_range->IsEmpty()) continue;
     InstructionOperand spill_operand;
-    if (range->TopLevel()->HasSpillOperand()) {
-      spill_operand = *range->TopLevel()->GetSpillOperand();
-    } else if (range->TopLevel()->HasSpillRange()) {
-      spill_operand = range->TopLevel()->GetSpillRangeOperand();
+    if (top_range->HasSpillOperand()) {
+      spill_operand = *top_range->TopLevel()->GetSpillOperand();
+    } else if (top_range->TopLevel()->HasSpillRange()) {
+      spill_operand = top_range->TopLevel()->GetSpillRangeOperand();
     }
-    auto assigned = range->GetAssignedOperand();
-    range->ConvertUsesToOperand(assigned, spill_operand);
-    if (range->is_phi()) {
-      data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned);
+    if (top_range->is_phi()) {
+      data()->GetPhiMapValueFor(top_range)->CommitAssignment(
+          top_range->GetAssignedOperand());
     }
-    if (!range->IsChild() && !spill_operand.IsInvalid()) {
+    for (LiveRange* range = top_range; range != nullptr;
+         range = range->next()) {
+      auto assigned = range->GetAssignedOperand();
+      range->ConvertUsesToOperand(assigned, spill_operand);
+    }
+
+    if (!spill_operand.IsInvalid()) {
       // If this top level range has a child spilled in a deferred block, we use
       // the range and control flow connection mechanism instead of spilling at
       // definition. Refer to the ConnectLiveRanges and ResolveControlFlow
       // phases. Normally, when we spill at definition, we do not insert a
       // connecting move when a successor child range is spilled - because the
       // spilled range picks up its value from the slot which was assigned at
       // definition. For ranges that are determined to spill only in deferred
       // blocks, we let ConnectLiveRanges and ResolveControlFlow insert such
       // moves between ranges. Because of how the ranges are split around
       // deferred blocks, this amounts to spilling and filling inside such
       // blocks.
-      if (!range->TryCommitSpillInDeferredBlock(data()->code(),
-                                                spill_operand)) {
+      if (!top_range->TryCommitSpillInDeferredBlock(data()->code(),
+                                                    spill_operand)) {
         // Spill at definition if the range isn't spilled only in deferred
         // blocks.
-        range->CommitSpillsAtDefinition(
+        top_range->CommitSpillsAtDefinition(
             data()->code(), spill_operand,
-            range->has_slot_use() || range->spilled());
+            top_range->has_slot_use() || top_range->spilled());
       }
     }
   }
 }
 
 
 ReferenceMapPopulator::ReferenceMapPopulator(RegisterAllocationData* data)
     : data_(data) {}
 
 
@@ skipping 12 matching lines @@
   // Map all delayed references.
   for (auto& delayed_reference : data()->delayed_references()) {
     delayed_reference.map->RecordReference(
         AllocatedOperand::cast(*delayed_reference.operand));
   }
   // Iterate over all safe point positions and record a pointer
   // for all spilled live ranges at this point.
   int last_range_start = 0;
   auto reference_maps = data()->code()->reference_maps();
   ReferenceMapDeque::const_iterator first_it = reference_maps->begin();
-  for (LiveRange* range : data()->live_ranges()) {
+  for (TopLevelLiveRange* range : data()->live_ranges()) {
     if (range == nullptr) continue;
-    // Iterate over the first parts of multi-part live ranges.
-    if (range->IsChild()) continue;
     // Skip non-reference values.
-    if (!data()->IsReference(range->id())) continue;
+    if (!data()->IsReference(range)) continue;
     // Skip empty live ranges.
     if (range->IsEmpty()) continue;
 
     // Find the extent of the range and its children.
     int start = range->Start().ToInstructionIndex();
     int end = 0;
-    for (auto cur = range; cur != nullptr; cur = cur->next()) {
+    for (LiveRange* cur = range; cur != nullptr; cur = cur->next()) {
       auto this_end = cur->End();
       if (this_end.ToInstructionIndex() > end)
         end = this_end.ToInstructionIndex();
       DCHECK(cur->Start().ToInstructionIndex() >= start);
     }
 
     // Most of the ranges are in order, but not all.  Keep an eye on when they
     // step backwards and reset the first_it so we don't miss any safe points.
     if (start < last_range_start) first_it = reference_maps->begin();
     last_range_start = start;
@@ skipping 24 matching lines @@
       auto map = *it;
       int safe_point = map->instruction_position();
 
       // The safe points are sorted so we can stop searching here.
       if (safe_point - 1 > end) break;
 
       // Advance to the next active range that covers the current
       // safe point position.
       auto safe_point_pos =
           LifetimePosition::InstructionFromInstructionIndex(safe_point);
-      auto cur = range;
+      LiveRange* cur = range;
       while (cur != nullptr && !cur->Covers(safe_point_pos)) {
         cur = cur->next();
       }
       if (cur == nullptr) continue;
 
       // Check if the live range is spilled and the safe point is after
       // the spill position.
       int spill_index = range->IsSpilledOnlyInDeferredBlocks()
                             ? cur->Start().ToInstructionIndex()
                             : range->spill_start_index();
 
       if (!spill_operand.IsInvalid() && safe_point >= spill_index) {
         TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
-              range->id(), spill_index, safe_point);
+              range->vreg(), spill_index, safe_point);
         map->RecordReference(AllocatedOperand::cast(spill_operand));
       }
 
       if (!cur->spilled()) {
         TRACE(
-            "Pointer in register for range %d (start at %d) "
+            "Pointer in register for range %d:%d (start at %d) "
             "at safe point %d\n",
-            cur->id(), cur->Start().value(), safe_point);
+            range->vreg(), cur->relative_id(), cur->Start().value(),
+            safe_point);
         auto operand = cur->GetAssignedOperand();
         DCHECK(!operand.IsStackSlot());
         DCHECK_EQ(kRepTagged, AllocatedOperand::cast(operand).machine_type());
         map->RecordReference(AllocatedOperand::cast(operand));
       }
     }
   }
 }
 
 
@@ skipping 206 matching lines @@
                 ->HasReferenceMap());
     gap_index = pred->last_instruction_index();
     position = Instruction::END;
   }
   data()->AddGapMove(gap_index, position, pred_op, cur_op);
 }
 
 
 void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
   DelayedInsertionMap delayed_insertion_map(local_zone);
-  for (auto first_range : data()->live_ranges()) {
-    if (first_range == nullptr || first_range->IsChild()) continue;
-    bool connect_spilled = first_range->IsSpilledOnlyInDeferredBlocks();
-    for (auto second_range = first_range->next(); second_range != nullptr;
+  for (TopLevelLiveRange* top_range : data()->live_ranges()) {
+    if (top_range == nullptr) continue;
+    bool connect_spilled = top_range->IsSpilledOnlyInDeferredBlocks();
+    LiveRange* first_range = top_range;
+    for (LiveRange *second_range = first_range->next(); second_range != nullptr;
          first_range = second_range, second_range = second_range->next()) {
       auto pos = second_range->Start();
       // Add gap move if the two live ranges touch and there is no block
       // boundary.
       if (!connect_spilled && second_range->spilled()) continue;
       if (first_range->End() != pos) continue;
       if (data()->IsBlockBoundary(pos) &&
           !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {
         continue;
       }
@@ skipping 51 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