[turbofan] split register allocator into little pieces

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/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 #define TRACE(...)                             \
   do {                                         \
     if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
   } while (false)
 
-static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
+namespace {
+
+inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
   return a.Value() < b.Value() ? a : b;
 }
 
 
-static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
+inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
   return a.Value() > b.Value() ? a : b;
 }
 
 
-static void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) {
+void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) {
   auto it = std::find(v->begin(), v->end(), range);
   DCHECK(it != v->end());
   v->erase(it);
 }
 
+}  // namespace
+
 
 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
                          InstructionOperand* hint)
     : operand_(operand), hint_(hint), pos_(pos), next_(nullptr), flags_(0) {
   bool register_beneficial = true;
   UsePositionType type = UsePositionType::kAny;
   if (operand_ != nullptr && operand_->IsUnallocated()) {
     const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_);
     if (unalloc->HasRegisterPolicy()) {
       type = UsePositionType::kRequiresRegister;
@@ skipping 34 matching lines @@
 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;
 };
 
 
-#ifdef DEBUG
+LiveRange::LiveRange(int id, Zone* zone)
+    : id_(id),
+      spilled_(false),
+      has_slot_use_(false),
+      is_phi_(false),
+      is_non_loop_phi_(false),
+      kind_(UNALLOCATED_REGISTERS),
+      assigned_register_(kInvalidAssignment),
+      last_interval_(nullptr),
+      first_interval_(nullptr),
+      first_pos_(nullptr),
+      parent_(nullptr),
+      next_(nullptr),
+      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) {
-    DCHECK(Start().Value() <= cur->pos().Value() &&
-           cur->pos().Value() <= End().Value());
+    CHECK(Start().Value() <= cur->pos().Value() &&
+          cur->pos().Value() <= End().Value());
     cur = cur->next();
   }
 }
 
 
 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;
 }
 
 
-#endif
-
-
-LiveRange::LiveRange(int id, Zone* zone)
-    : id_(id),
-      spilled_(false),
-      has_slot_use_(false),
-      is_phi_(false),
-      is_non_loop_phi_(false),
-      kind_(UNALLOCATED_REGISTERS),
-      assigned_register_(kInvalidAssignment),
-      last_interval_(nullptr),
-      first_interval_(nullptr),
-      first_pos_(nullptr),
-      parent_(nullptr),
-      next_(nullptr),
-      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::set_assigned_register(int reg) {
   DCHECK(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
 }
 
 
 void LiveRange::MakeSpilled() {
   DCHECK(!IsSpilled());
   DCHECK(!TopLevel()->HasNoSpillType());
   spilled_ = true;
@@ skipping 414 matching lines @@
       if (a == nullptr || a->start().Value() > other->End().Value()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
-RegisterAllocator::RegisterAllocator(const RegisterConfiguration* config,
-                                     Zone* zone, Frame* frame,
-                                     InstructionSequence* code,
-                                     const char* debug_name)
+static bool AreUseIntervalsIntersecting(UseInterval* interval1,
+                                        UseInterval* interval2) {
+  while (interval1 != nullptr && interval2 != nullptr) {
+    if (interval1->start().Value() < interval2->start().Value()) {
+      if (interval1->end().Value() > interval2->start().Value()) {
+        return true;
+      }
+      interval1 = interval1->next();
+    } else {
+      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();
+  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);
+    }
+    node = new_node;
+    src = src->next();
+  }
+  use_interval_ = result;
+  live_ranges().push_back(range);
+  end_position_ = node->end();
+  DCHECK(!range->HasSpillRange());
+  range->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_);
+}
+
+
+bool SpillRange::TryMerge(SpillRange* other) {
+  if (Kind() != other->Kind() || IsIntersectingWith(other)) return false;
+
+  auto max = LifetimePosition::MaxPosition();
+  if (End().Value() < other->End().Value() &&
+      other->End().Value() != max.Value()) {
+    end_position_ = other->End();
+  }
+  other->end_position_ = max;
+
+  MergeDisjointIntervals(other->use_interval_);
+  other->use_interval_ = nullptr;
+
+  for (auto range : other->live_ranges()) {
+    DCHECK(range->GetSpillRange() == other);
+    range->SetSpillRange(this);
+  }
+
+  live_ranges().insert(live_ranges().end(), other->live_ranges().begin(),
+                       other->live_ranges().end());
+  other->live_ranges().clear();
+
+  return true;
+}
+
+
+void SpillRange::SetOperand(AllocatedOperand* op) {
+  for (auto range : live_ranges()) {
+    DCHECK(range->GetSpillRange() == this);
+    range->CommitSpillOperand(op);
+  }
+}
+
+
+void SpillRange::MergeDisjointIntervals(UseInterval* other) {
+  UseInterval* tail = nullptr;
+  auto current = use_interval_;
+  while (other != nullptr) {
+    // Make sure the 'current' list starts first
+    if (current == nullptr ||
+        current->start().Value() > other->start().Value()) {
+      std::swap(current, other);
+    }
+    // Check disjointness
+    DCHECK(other == nullptr ||
+           current->end().Value() <= other->start().Value());
+    // Append the 'current' node to the result accumulator and move forward
+    if (tail == nullptr) {
+      use_interval_ = current;
+    } else {
+      tail->set_next(current);
+    }
+    tail = current;
+    current = current->next();
+  }
+  // Other list is empty => we are done
+}
+
+
+LiveRangeBuilder::LiveRangeBuilder(const RegisterConfiguration* config,
+                                   Zone* zone, Frame* frame,
+                                   InstructionSequence* code,
+                                   const char* debug_name)
     : local_zone_(zone),
       frame_(frame),
       code_(code),
       debug_name_(debug_name),
       config_(config),
       phi_map_(local_zone()),
       live_in_sets_(code->InstructionBlockCount(), nullptr, local_zone()),
       live_ranges_(code->VirtualRegisterCount() * 2, nullptr, local_zone()),
       fixed_live_ranges_(this->config()->num_general_registers(), nullptr,
                          local_zone()),
       fixed_double_live_ranges_(this->config()->num_double_registers(), nullptr,
                                 local_zone()),
-      unhandled_live_ranges_(local_zone()),
-      active_live_ranges_(local_zone()),
-      inactive_live_ranges_(local_zone()),
       spill_ranges_(local_zone()),
-      mode_(UNALLOCATED_REGISTERS),
-      num_registers_(-1) {
+      assigned_registers_(nullptr),
+      assigned_double_registers_(nullptr) {
   DCHECK(this->config()->num_general_registers() <=
          RegisterConfiguration::kMaxGeneralRegisters);
   DCHECK(this->config()->num_double_registers() <=
          RegisterConfiguration::kMaxDoubleRegisters);
-  // TryAllocateFreeReg and AllocateBlockedReg assume this
-  // when allocating local arrays.
-  DCHECK(RegisterConfiguration::kMaxDoubleRegisters >=
-         this->config()->num_general_registers());
-  unhandled_live_ranges().reserve(
-      static_cast<size_t>(code->VirtualRegisterCount() * 2));
-  active_live_ranges().reserve(8);
-  inactive_live_ranges().reserve(8);
   spill_ranges().reserve(8);
-  assigned_registers_ =
-      new (code_zone()) BitVector(config->num_general_registers(), code_zone());
+  assigned_registers_ = new (code_zone())
+      BitVector(this->config()->num_general_registers(), code_zone());
   assigned_double_registers_ = new (code_zone())
-      BitVector(config->num_aliased_double_registers(), code_zone());
-  frame->SetAllocatedRegisters(assigned_registers_);
-  frame->SetAllocatedDoubleRegisters(assigned_double_registers_);
+      BitVector(this->config()->num_aliased_double_registers(), code_zone());
+  this->frame()->SetAllocatedRegisters(assigned_registers_);
+  this->frame()->SetAllocatedDoubleRegisters(assigned_double_registers_);
 }
 
 
-BitVector* RegisterAllocator::ComputeLiveOut(const InstructionBlock* block) {
+BitVector* LiveRangeBuilder::ComputeLiveOut(const InstructionBlock* block) {
   // Compute live out for the given block, except not including backward
   // successor edges.
   auto live_out = new (local_zone())
       BitVector(code()->VirtualRegisterCount(), local_zone());
 
   // Process all successor blocks.
   for (auto succ : block->successors()) {
     // Add values live on entry to the successor. Note the successor's
     // live_in will not be computed yet for backwards edges.
     auto live_in = live_in_sets_[succ.ToSize()];
     if (live_in != nullptr) live_out->Union(*live_in);
 
     // All phi input operands corresponding to this successor edge are live
     // out from this block.
     auto successor = code()->InstructionBlockAt(succ);
     size_t index = successor->PredecessorIndexOf(block->rpo_number());
     DCHECK(index < successor->PredecessorCount());
     for (auto phi : successor->phis()) {
       live_out->Add(phi->operands()[index]);
     }
   }
   return live_out;
 }
 
 
-void RegisterAllocator::AddInitialIntervals(const InstructionBlock* block,
-                                            BitVector* live_out) {
+void LiveRangeBuilder::AddInitialIntervals(const InstructionBlock* block,
+                                           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);
     range->AddUseInterval(start, end, local_zone());
     iterator.Advance();
   }
 }
 
 
-int RegisterAllocator::FixedDoubleLiveRangeID(int index) {
+int LiveRangeBuilder::FixedDoubleLiveRangeID(int index) {
   return -index - 1 - config()->num_general_registers();
 }
 
 
-InstructionOperand* RegisterAllocator::AllocateFixed(
-    UnallocatedOperand* operand, int pos, bool is_tagged) {
+InstructionOperand* LiveRangeBuilder::AllocateFixed(UnallocatedOperand* operand,
+                                                    int pos, bool is_tagged) {
   TRACE("Allocating fixed reg for op %d\n", operand->virtual_register());
   DCHECK(operand->HasFixedPolicy());
   InstructionOperand allocated;
   if (operand->HasFixedSlotPolicy()) {
     allocated = AllocatedOperand(AllocatedOperand::STACK_SLOT,
                                  operand->fixed_slot_index());
   } else if (operand->HasFixedRegisterPolicy()) {
     allocated = AllocatedOperand(AllocatedOperand::REGISTER,
                                  operand->fixed_register_index());
   } else if (operand->HasFixedDoubleRegisterPolicy()) {
     allocated = AllocatedOperand(AllocatedOperand::DOUBLE_REGISTER,
                                  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);
     if (instr->HasReferenceMap()) {
       instr->reference_map()->RecordReference(*operand);
     }
   }
   return operand;
 }
 
 
-LiveRange* RegisterAllocator::NewLiveRange(int index) {
+LiveRange* LiveRangeBuilder::NewLiveRange(int index) {
   // The LiveRange object itself can go in the local zone, but the
   // InstructionOperand needs to go in the code zone, since it may survive
   // register allocation.
   return new (local_zone()) LiveRange(index, code_zone());
 }
 
 
-LiveRange* RegisterAllocator::FixedLiveRangeFor(int index) {
+LiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) {
   DCHECK(index < config()->num_general_registers());
   auto result = fixed_live_ranges()[index];
   if (result == nullptr) {
     result = NewLiveRange(FixedLiveRangeID(index));
     DCHECK(result->IsFixed());
-    result->kind_ = GENERAL_REGISTERS;
+    result->set_kind(GENERAL_REGISTERS);
     SetLiveRangeAssignedRegister(result, index);
     fixed_live_ranges()[index] = result;
   }
   return result;
 }
 
 
-LiveRange* RegisterAllocator::FixedDoubleLiveRangeFor(int index) {
+LiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) {
   DCHECK(index < config()->num_aliased_double_registers());
   auto result = fixed_double_live_ranges()[index];
   if (result == nullptr) {
     result = NewLiveRange(FixedDoubleLiveRangeID(index));
     DCHECK(result->IsFixed());
-    result->kind_ = DOUBLE_REGISTERS;
+    result->set_kind(DOUBLE_REGISTERS);
     SetLiveRangeAssignedRegister(result, index);
     fixed_double_live_ranges()[index] = result;
   }
   return result;
 }
 
 
-LiveRange* RegisterAllocator::LiveRangeFor(int index) {
+LiveRange* LiveRangeBuilder::LiveRangeFor(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);
     live_ranges()[index] = result;
   }
   return result;
 }
 
 
-Instruction* RegisterAllocator::GetLastInstruction(
+Instruction* LiveRangeBuilder::GetLastInstruction(
     const InstructionBlock* block) {
   return code()->InstructionAt(block->last_instruction_index());
 }
 
 
-LiveRange* RegisterAllocator::LiveRangeFor(InstructionOperand* operand) {
+LiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) {
   if (operand->IsUnallocated()) {
     return LiveRangeFor(UnallocatedOperand::cast(operand)->virtual_register());
   } else if (operand->IsConstant()) {
     return LiveRangeFor(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;
   }
 }
 
 
-void RegisterAllocator::Define(LifetimePosition position,
-                               InstructionOperand* operand,
-                               InstructionOperand* hint) {
+void LiveRangeBuilder::Define(LifetimePosition position,
+                              InstructionOperand* operand,
+                              InstructionOperand* hint) {
   auto range = LiveRangeFor(operand);
   if (range == nullptr) return;
 
   if (range->IsEmpty() || range->Start().Value() > position.Value()) {
     // Can happen if there is a definition without use.
     range->AddUseInterval(position, position.NextStart(), local_zone());
     range->AddUsePosition(position.NextStart(), nullptr, nullptr, local_zone());
   } else {
     range->ShortenTo(position);
   }
 
   if (operand->IsUnallocated()) {
     auto unalloc_operand = UnallocatedOperand::cast(operand);
     range->AddUsePosition(position, unalloc_operand, hint, local_zone());
   }
 }
 
 
-void RegisterAllocator::Use(LifetimePosition block_start,
-                            LifetimePosition position,
-                            InstructionOperand* operand,
-                            InstructionOperand* hint) {
+void LiveRangeBuilder::Use(LifetimePosition block_start,
+                           LifetimePosition position,
+                           InstructionOperand* operand,
+                           InstructionOperand* hint) {
   auto range = LiveRangeFor(operand);
   if (range == nullptr) return;
   if (operand->IsUnallocated()) {
     UnallocatedOperand* unalloc_operand = UnallocatedOperand::cast(operand);
     range->AddUsePosition(position, unalloc_operand, hint, local_zone());
   }
   range->AddUseInterval(block_start, position, local_zone());
 }
 
 
-MoveOperands* RegisterAllocator::AddGapMove(int index,
-                                            Instruction::GapPosition position,
-                                            const InstructionOperand& from,
-                                            const InstructionOperand& to) {
+MoveOperands* LiveRangeBuilder::AddGapMove(int index,
+                                           Instruction::GapPosition position,
+                                           const InstructionOperand& from,
+                                           const InstructionOperand& to) {
   auto instr = code()->InstructionAt(index);
   auto moves = instr->GetOrCreateParallelMove(position, code_zone());
   return moves->AddMove(from, to);
 }
 
 
-static bool AreUseIntervalsIntersecting(UseInterval* interval1,
-                                        UseInterval* interval2) {
-  while (interval1 != nullptr && interval2 != nullptr) {
-    if (interval1->start().Value() < interval2->start().Value()) {
-      if (interval1->end().Value() > interval2->start().Value()) {
-        return true;
-      }
-      interval1 = interval1->next();
-    } else {
-      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();
-  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);
-    }
-    node = new_node;
-    src = src->next();
-  }
-  use_interval_ = result;
-  live_ranges().push_back(range);
-  end_position_ = node->end();
-  DCHECK(!range->HasSpillRange());
-  range->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_);
-}
-
-
-bool SpillRange::TryMerge(SpillRange* other) {
-  if (Kind() != other->Kind() || IsIntersectingWith(other)) return false;
-
-  auto max = LifetimePosition::MaxPosition();
-  if (End().Value() < other->End().Value() &&
-      other->End().Value() != max.Value()) {
-    end_position_ = other->End();
-  }
-  other->end_position_ = max;
-
-  MergeDisjointIntervals(other->use_interval_);
-  other->use_interval_ = nullptr;
-
-  for (auto range : other->live_ranges()) {
-    DCHECK(range->GetSpillRange() == other);
-    range->SetSpillRange(this);
-  }
-
-  live_ranges().insert(live_ranges().end(), other->live_ranges().begin(),
-                       other->live_ranges().end());
-  other->live_ranges().clear();
-
-  return true;
-}
-
-
-void SpillRange::SetOperand(AllocatedOperand* op) {
-  for (auto range : live_ranges()) {
-    DCHECK(range->GetSpillRange() == this);
-    range->CommitSpillOperand(op);
-  }
-}
-
-
-void SpillRange::MergeDisjointIntervals(UseInterval* other) {
-  UseInterval* tail = nullptr;
-  auto current = use_interval_;
-  while (other != nullptr) {
-    // Make sure the 'current' list starts first
-    if (current == nullptr ||
-        current->start().Value() > other->start().Value()) {
-      std::swap(current, other);
-    }
-    // Check disjointness
-    DCHECK(other == nullptr ||
-           current->end().Value() <= other->start().Value());
-    // Append the 'current' node to the result accumulator and move forward
-    if (tail == nullptr) {
-      use_interval_ = current;
-    } else {
-      tail->set_next(current);
-    }
-    tail = current;
-    current = current->next();
-  }
-  // Other list is empty => we are done
-}
-
-
-void RegisterAllocator::AssignSpillSlots() {
-  // Merge disjoint spill ranges
-  for (size_t i = 0; i < spill_ranges().size(); i++) {
-    auto range = spill_ranges()[i];
-    if (range->IsEmpty()) continue;
-    for (size_t j = i + 1; j < spill_ranges().size(); j++) {
-      auto other = spill_ranges()[j];
-      if (!other->IsEmpty()) {
-        range->TryMerge(other);
-      }
-    }
-  }
-
-  // Allocate slots for the merged spill ranges.
-  for (auto range : spill_ranges()) {
-    if (range->IsEmpty()) continue;
-    // Allocate a new operand referring to the spill slot.
-    auto kind = range->Kind();
-    int index = frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS);
-    auto op_kind = kind == DOUBLE_REGISTERS
-                       ? AllocatedOperand::DOUBLE_STACK_SLOT
-                       : AllocatedOperand::STACK_SLOT;
-    auto op = AllocatedOperand::New(code_zone(), op_kind, index);
-    range->SetOperand(op);
-  }
-}
-
-
-void RegisterAllocator::CommitAssignment() {
-  for (auto range : live_ranges()) {
-    if (range == nullptr || range->IsEmpty()) continue;
-    InstructionOperand* spill_operand = nullptr;
-    if (!range->TopLevel()->HasNoSpillType()) {
-      spill_operand = range->TopLevel()->GetSpillOperand();
-    }
-    auto assigned = range->GetAssignedOperand();
-    range->ConvertUsesToOperand(assigned, spill_operand);
-    if (range->is_phi()) AssignPhiInput(range, assigned);
-    if (!range->IsChild() && spill_operand != nullptr) {
-      range->CommitSpillsAtDefinition(code(), spill_operand,
-                                      range->has_slot_use());
-    }
-  }
-}
-
-
-SpillRange* RegisterAllocator::AssignSpillRangeToLiveRange(LiveRange* range) {
+SpillRange* LiveRangeBuilder::AssignSpillRangeToLiveRange(LiveRange* range) {
   auto spill_range = new (local_zone()) SpillRange(range, local_zone());
   spill_ranges().push_back(spill_range);
   return spill_range;
 }
 
 
-bool RegisterAllocator::TryReuseSpillForPhi(LiveRange* range) {
-  if (range->IsChild() || !range->is_phi()) return false;
-  DCHECK(!range->HasSpillOperand());
-
-  auto lookup = phi_map_.find(range->id());
-  DCHECK(lookup != phi_map_.end());
-  auto phi = lookup->second->phi;
-  auto block = lookup->second->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->GetSpillRange() == nullptr) 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->IsSpilled()) {
-      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();
-  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_spill = op_range->GetSpillRange();
-    if (op_spill != nullptr &&
-        (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() ||
-      AreUseIntervalsIntersecting(first_op_spill->interval(),
-                                  range->first_interval())) {
-    return false;
-  }
-
-  // If the range does not need register soon, spill it to the merged
-  // spill range.
-  auto next_pos = range->Start();
-  if (next_pos.IsGapPosition()) next_pos = next_pos.NextStart();
-  auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
-  if (pos == nullptr) {
-    auto spill_range = range->TopLevel()->HasSpillRange()
-                           ? range->TopLevel()->GetSpillRange()
-                           : AssignSpillRangeToLiveRange(range->TopLevel());
-    CHECK(first_op_spill->TryMerge(spill_range));
-    Spill(range);
-    return true;
-  } else if (pos->pos().Value() > range->Start().NextStart().Value()) {
-    auto spill_range = range->TopLevel()->HasSpillRange()
-                           ? range->TopLevel()->GetSpillRange()
-                           : AssignSpillRangeToLiveRange(range->TopLevel());
-    CHECK(first_op_spill->TryMerge(spill_range));
-    SpillBetween(range, range->Start(), pos->pos());
-    DCHECK(UnhandledIsSorted());
-    return true;
-  }
-  return false;
-}
-
-
-void RegisterAllocator::MeetRegisterConstraints(const InstructionBlock* block) {
+void LiveRangeBuilder::MeetRegisterConstraints(const InstructionBlock* block) {
   int start = block->first_instruction_index();
   int end = block->last_instruction_index();
   DCHECK_NE(-1, start);
   for (int i = start; i <= end; ++i) {
     MeetConstraintsBefore(i);
     if (i != end) MeetConstraintsAfter(i);
   }
   // Meet register constraints for the instruction in the end.
   MeetRegisterConstraintsForLastInstructionInBlock(block);
 }
 
 
-void RegisterAllocator::MeetRegisterConstraintsForLastInstructionInBlock(
+void LiveRangeBuilder::MeetRegisterConstraintsForLastInstructionInBlock(
     const InstructionBlock* block) {
   int end = block->last_instruction_index();
   auto last_instruction = 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);
     bool assigned = false;
@@ skipping 25 matching lines @@
         DCHECK(successor->PredecessorCount() == 1);
         int gap_index = successor->first_instruction_index();
         range->SpillAtDefinition(local_zone(), gap_index, output);
         range->SetSpillStartIndex(gap_index);
       }
     }
   }
 }
 
 
-void RegisterAllocator::MeetConstraintsAfter(int instr_index) {
+void LiveRangeBuilder::MeetConstraintsAfter(int instr_index) {
   auto first = 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);
       range->SetSpillStartIndex(instr_index + 1);
       range->SetSpillOperand(output);
       continue;
     }
     auto first_output = UnallocatedOperand::cast(output);
     auto range = LiveRangeFor(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 = HasTaggedValue(output_vreg);
+      bool is_tagged = 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() <
                frame_->GetSpillSlotCount());
         range->SetSpillOperand(StackSlotOperand::cast(first_output));
         range->SetSpillStartIndex(instr_index + 1);
         assigned = true;
       }
       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(local_zone(), instr_index + 1, first_output);
       range->SetSpillStartIndex(instr_index + 1);
     }
   }
 }
 
 
-void RegisterAllocator::MeetConstraintsBefore(int instr_index) {
+void LiveRangeBuilder::MeetConstraintsBefore(int instr_index) {
   auto second = 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 = HasTaggedValue(input_vreg);
+      bool is_tagged = IsReference(input_vreg);
       AllocateFixed(cur_input, instr_index, is_tagged);
       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());
     AddGapMove(instr_index, Instruction::END, input_copy, *cur_input);
-    if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) {
+    if (IsReference(input_vreg) && !IsReference(output_vreg)) {
       if (second->HasReferenceMap()) {
         second->reference_map()->RecordReference(input_copy);
       }
-    } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) {
+    } else if (!IsReference(input_vreg) && 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.
     }
   }
 }
 
 
-bool RegisterAllocator::IsOutputRegisterOf(Instruction* instr, int index) {
+bool LiveRangeBuilder::IsOutputRegisterOf(Instruction* instr, int index) {
   for (size_t i = 0; i < instr->OutputCount(); i++) {
     auto output = instr->OutputAt(i);
     if (output->IsRegister() && RegisterOperand::cast(output)->index() == index)
       return true;
   }
   return false;
 }
 
 
-bool RegisterAllocator::IsOutputDoubleRegisterOf(Instruction* instr,
-                                                 int index) {
+bool LiveRangeBuilder::IsOutputDoubleRegisterOf(Instruction* instr, int index) {
   for (size_t i = 0; i < instr->OutputCount(); i++) {
     auto output = instr->OutputAt(i);
     if (output->IsDoubleRegister() &&
         DoubleRegisterOperand::cast(output)->index() == index)
       return true;
   }
   return false;
 }
 
 
-void RegisterAllocator::ProcessInstructions(const InstructionBlock* block,
-                                            BitVector* live) {
+void LiveRangeBuilder::ProcessInstructions(const InstructionBlock* block,
+                                           BitVector* live) {
   int block_start = block->first_instruction_index();
   auto block_start_position =
       LifetimePosition::GapFromInstructionIndex(block_start);
 
   for (int index = block->last_instruction_index(); index >= block_start;
        index--) {
     auto curr_position =
         LifetimePosition::InstructionFromInstructionIndex(index);
     auto instr = InstructionAt(index);
     DCHECK(instr != nullptr);
@@ skipping 112 matching lines @@
         Use(block_start_position, curr_position, &from, hint);
         if (from.IsUnallocated()) {
           live->Add(UnallocatedOperand::cast(from).virtual_register());
         }
       }
     }
   }
 }
 
 
-void RegisterAllocator::ResolvePhis(const InstructionBlock* block) {
+void LiveRangeBuilder::ResolvePhis(const InstructionBlock* block) {
   for (auto phi : block->phis()) {
     int phi_vreg = phi->virtual_register();
     auto map_value = new (local_zone()) PhiMapValue(phi, block, local_zone());
     auto res = phi_map_.insert(std::make_pair(phi_vreg, map_value));
     DCHECK(res.second);
     USE(res);
     auto& output = phi->output();
     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 = AddGapMove(cur_block->last_instruction_index(),
                              Instruction::END, input, output);
       map_value->incoming_moves.push_back(move);
       DCHECK(!InstructionAt(cur_block->last_instruction_index())
                   ->HasReferenceMap());
     }
     auto live_range = LiveRangeFor(phi_vreg);
     int gap_index = block->first_instruction_index();
     live_range->SpillAtDefinition(local_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());
   }
 }
 
 
-void RegisterAllocator::AssignPhiInput(LiveRange* range,
-                                       const InstructionOperand& assignment) {
+void LiveRangeBuilder::AssignPhiInput(LiveRange* range,
+                                      const InstructionOperand& assignment) {
   DCHECK(range->is_phi());
   auto it = phi_map_.find(range->id());
   DCHECK(it != phi_map_.end());
   for (auto move : it->second->incoming_moves) {
     move->set_destination(assignment);
   }
 }
 
 
-void RegisterAllocator::MeetRegisterConstraints() {
+void LiveRangeBuilder::MeetRegisterConstraints() {
   for (auto block : code()->instruction_blocks()) {
     MeetRegisterConstraints(block);
   }
 }
 
 
-void RegisterAllocator::ResolvePhis() {
+void LiveRangeBuilder::ResolvePhis() {
   // Process the blocks in reverse order.
   for (auto i = code()->instruction_blocks().rbegin();
        i != code()->instruction_blocks().rend(); ++i) {
     ResolvePhis(*i);
   }
 }
 
 
-const InstructionBlock* RegisterAllocator::GetInstructionBlock(
-    LifetimePosition pos) {
-  return code()->GetInstructionBlock(pos.ToInstructionIndex());
-}
-
-
-void RegisterAllocator::ConnectRanges() {
-  ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand>
-      delayed_insertion_map(local_zone());
-  for (auto first_range : live_ranges()) {
-    if (first_range == nullptr || first_range->IsChild()) continue;
-    for (auto 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 (second_range->IsSpilled()) continue;
-      if (first_range->End().Value() != pos.Value()) continue;
-      if (IsBlockBoundary(pos) &&
-          !CanEagerlyResolveControlFlow(GetInstructionBlock(pos))) {
-        continue;
-      }
-      auto prev_operand = first_range->GetAssignedOperand();
-      auto cur_operand = second_range->GetAssignedOperand();
-      if (prev_operand == cur_operand) continue;
-      bool delay_insertion = false;
-      Instruction::GapPosition gap_pos;
-      int gap_index = pos.ToInstructionIndex();
-      if (pos.IsGapPosition()) {
-        gap_pos = pos.IsStart() ? Instruction::START : Instruction::END;
-      } else {
-        if (pos.IsStart()) {
-          delay_insertion = true;
-        } else {
-          gap_index++;
-        }
-        gap_pos = delay_insertion ? Instruction::END : Instruction::START;
-      }
-      auto move = code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
-          gap_pos, code_zone());
-      if (!delay_insertion) {
-        move->AddMove(prev_operand, cur_operand);
-      } else {
-        delayed_insertion_map.insert(
-            std::make_pair(std::make_pair(move, prev_operand), cur_operand));
-      }
-    }
-  }
-  if (delayed_insertion_map.empty()) return;
-  // Insert all the moves which should occur after the stored move.
-  ZoneVector<MoveOperands*> to_insert(local_zone());
-  ZoneVector<MoveOperands*> to_eliminate(local_zone());
-  to_insert.reserve(4);
-  to_eliminate.reserve(4);
-  auto moves = delayed_insertion_map.begin()->first.first;
-  for (auto it = delayed_insertion_map.begin();; ++it) {
-    bool done = it == delayed_insertion_map.end();
-    if (done || it->first.first != moves) {
-      // Commit the MoveOperands for current ParallelMove.
-      for (auto move : to_eliminate) {
-        move->Eliminate();
-      }
-      for (auto move : to_insert) {
-        moves->push_back(move);
-      }
-      if (done) break;
-      // Reset state.
-      to_eliminate.clear();
-      to_insert.clear();
-      moves = it->first.first;
-    }
-    // Gather all MoveOperands for a single ParallelMove.
-    auto move = new (code_zone()) MoveOperands(it->first.second, it->second);
-    auto eliminate = moves->PrepareInsertAfter(move);
-    to_insert.push_back(move);
-    if (eliminate != nullptr) to_eliminate.push_back(eliminate);
-  }
-}
-
-
-bool RegisterAllocator::CanEagerlyResolveControlFlow(
-    const InstructionBlock* block) const {
-  if (block->PredecessorCount() != 1) return false;
-  return block->predecessors()[0].IsNext(block->rpo_number());
-}
-
-
-namespace {
-
-class LiveRangeBound {
- public:
-  explicit LiveRangeBound(const LiveRange* range)
-      : range_(range), start_(range->Start()), end_(range->End()) {
-    DCHECK(!range->IsEmpty());
-  }
-
-  bool CanCover(LifetimePosition position) {
-    return start_.Value() <= position.Value() &&
-           position.Value() < end_.Value();
-  }
-
-  const LiveRange* const range_;
-  const LifetimePosition start_;
-  const LifetimePosition end_;
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(LiveRangeBound);
-};
-
-
-struct FindResult {
-  const LiveRange* cur_cover_;
-  const LiveRange* pred_cover_;
-};
-
-
-class LiveRangeBoundArray {
- public:
-  LiveRangeBoundArray() : length_(0), start_(nullptr) {}
-
-  bool ShouldInitialize() { return start_ == nullptr; }
-
-  void Initialize(Zone* zone, const LiveRange* const range) {
-    size_t length = 0;
-    for (auto i = range; i != nullptr; i = i->next()) length++;
-    start_ = zone->NewArray<LiveRangeBound>(length);
-    length_ = length;
-    auto curr = start_;
-    for (auto i = range; i != nullptr; i = i->next(), ++curr) {
-      new (curr) LiveRangeBound(i);
-    }
-  }
-
-  LiveRangeBound* Find(const LifetimePosition position) const {
-    size_t left_index = 0;
-    size_t right_index = length_;
-    while (true) {
-      size_t current_index = left_index + (right_index - left_index) / 2;
-      DCHECK(right_index > current_index);
-      auto bound = &start_[current_index];
-      if (bound->start_.Value() <= position.Value()) {
-        if (position.Value() < bound->end_.Value()) return bound;
-        DCHECK(left_index < current_index);
-        left_index = current_index;
-      } else {
-        right_index = current_index;
-      }
-    }
-  }
-
-  LiveRangeBound* FindPred(const InstructionBlock* pred) {
-    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
-        pred->last_instruction_index());
-    return Find(pred_end);
-  }
-
-  LiveRangeBound* FindSucc(const InstructionBlock* succ) {
-    auto succ_start = LifetimePosition::GapFromInstructionIndex(
-        succ->first_instruction_index());
-    return Find(succ_start);
-  }
-
-  void Find(const InstructionBlock* block, const InstructionBlock* pred,
-            FindResult* result) const {
-    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
-        pred->last_instruction_index());
-    auto bound = Find(pred_end);
-    result->pred_cover_ = bound->range_;
-    auto cur_start = LifetimePosition::GapFromInstructionIndex(
-        block->first_instruction_index());
-    // Common case.
-    if (bound->CanCover(cur_start)) {
-      result->cur_cover_ = bound->range_;
-      return;
-    }
-    result->cur_cover_ = Find(cur_start)->range_;
-    DCHECK(result->pred_cover_ != nullptr && result->cur_cover_ != nullptr);
-  }
-
- private:
-  size_t length_;
-  LiveRangeBound* start_;
-
-  DISALLOW_COPY_AND_ASSIGN(LiveRangeBoundArray);
-};
-
-
-class LiveRangeFinder {
- public:
-  explicit LiveRangeFinder(const RegisterAllocator& allocator)
-      : allocator_(allocator),
-        bounds_length_(static_cast<int>(allocator.live_ranges().size())),
-        bounds_(allocator.local_zone()->NewArray<LiveRangeBoundArray>(
-            bounds_length_)) {
-    for (int i = 0; i < bounds_length_; ++i) {
-      new (&bounds_[i]) LiveRangeBoundArray();
-    }
-  }
-
-  LiveRangeBoundArray* ArrayFor(int operand_index) {
-    DCHECK(operand_index < bounds_length_);
-    auto range = allocator_.live_ranges()[operand_index];
-    DCHECK(range != nullptr && !range->IsEmpty());
-    auto array = &bounds_[operand_index];
-    if (array->ShouldInitialize()) {
-      array->Initialize(allocator_.local_zone(), range);
-    }
-    return array;
-  }
-
- private:
-  const RegisterAllocator& allocator_;
-  const int bounds_length_;
-  LiveRangeBoundArray* const bounds_;
-
-  DISALLOW_COPY_AND_ASSIGN(LiveRangeFinder);
-};
-
-}  // namespace
-
-
-void RegisterAllocator::ResolveControlFlow() {
-  // Lazily linearize live ranges in memory for fast lookup.
-  LiveRangeFinder finder(*this);
-  for (auto block : code()->instruction_blocks()) {
-    if (CanEagerlyResolveControlFlow(block)) continue;
-    auto live = live_in_sets_[block->rpo_number().ToInt()];
-    BitVector::Iterator iterator(live);
-    while (!iterator.Done()) {
-      auto* array = finder.ArrayFor(iterator.Current());
-      for (auto pred : block->predecessors()) {
-        FindResult result;
-        const auto* pred_block = code()->InstructionBlockAt(pred);
-        array->Find(block, pred_block, &result);
-        if (result.cur_cover_ == result.pred_cover_ ||
-            result.cur_cover_->IsSpilled())
-          continue;
-        auto pred_op = result.pred_cover_->GetAssignedOperand();
-        auto cur_op = result.cur_cover_->GetAssignedOperand();
-        if (pred_op == cur_op) continue;
-        ResolveControlFlow(block, cur_op, pred_block, pred_op);
-      }
-      iterator.Advance();
-    }
-  }
-}
-
-
-void RegisterAllocator::ResolveControlFlow(const InstructionBlock* block,
-                                           const InstructionOperand& cur_op,
-                                           const InstructionBlock* pred,
-                                           const InstructionOperand& pred_op) {
-  DCHECK(pred_op != cur_op);
-  int gap_index;
-  Instruction::GapPosition position;
-  if (block->PredecessorCount() == 1) {
-    gap_index = block->first_instruction_index();
-    position = Instruction::START;
-  } else {
-    DCHECK(pred->SuccessorCount() == 1);
-    DCHECK(!InstructionAt(pred->last_instruction_index())->HasReferenceMap());
-    gap_index = pred->last_instruction_index();
-    position = Instruction::END;
-  }
-  AddGapMove(gap_index, position, pred_op, cur_op);
-}
-
-
-void RegisterAllocator::BuildLiveRanges() {
+void LiveRangeBuilder::BuildLiveRanges() {
   // Process the blocks in reverse order.
   for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0;
        --block_id) {
     auto block = code()->InstructionBlockAt(RpoNumber::FromInt(block_id));
     auto live = ComputeLiveOut(block);
     // Initially consider all live_out values live for the entire block. We
     // will shorten these intervals if necessary.
     AddInitialIntervals(block, live);
 
     // Process the instructions in reverse order, generating and killing
@@ skipping 43 matching lines @@
       // 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);
       }
     }
   }
 
   for (auto range : live_ranges()) {
     if (range == nullptr) continue;
-    range->kind_ = RequiredRegisterKind(range->id());
+    range->set_kind(RequiredRegisterKind(range->id()));
     // Give slots to all ranges with a non fixed slot use.
     if (range->has_slot_use() && range->HasNoSpillType()) {
       AssignSpillRangeToLiveRange(range);
     }
     // TODO(bmeurer): This is a horrible hack to make sure that for constant
     // live ranges, every use requires the constant to be in a register.
     // Without this hack, all uses with "any" policy would get the constant
     // operand assigned.
     if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) {
       for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next_) {
         if (pos->type() == UsePositionType::kRequiresSlot) continue;
         UsePositionType new_type = UsePositionType::kAny;
         // Can't mark phis as needing a register.
         if (!pos->pos().IsGapPosition()) {
           new_type = UsePositionType::kRequiresRegister;
         }
         pos->set_type(new_type, true);
       }
     }
   }
+
+#ifdef DEBUG
+  Verify();
+#endif
 }
 
 
-bool RegisterAllocator::ExistsUseWithoutDefinition() {
+bool LiveRangeBuilder::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);
     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;
 }
 
 
-bool RegisterAllocator::SafePointsAreInOrder() const {
-  int safe_point = 0;
-  for (auto map : *code()->reference_maps()) {
-    if (safe_point > map->instruction_position()) return false;
-    safe_point = map->instruction_position();
-  }
-  return true;
+bool LiveRangeBuilder::IsBlockBoundary(LifetimePosition pos) {
+  return pos.IsFullStart() &&
+         code()->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
+             pos.ToInstructionIndex();
 }
 
 
-void RegisterAllocator::PopulateReferenceMaps() {
-  DCHECK(SafePointsAreInOrder());
+RegisterKind LiveRangeBuilder::RequiredRegisterKind(
+    int virtual_register) const {
+  return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS
+                                              : GENERAL_REGISTERS;
+}
 
-  // 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 = code()->reference_maps();
-  ReferenceMapDeque::const_iterator first_it = reference_maps->begin();
-  for (LiveRange* range : 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 (!HasTaggedValue(range->id())) 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()) {
-      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;
-
-    // Step across all the safe points that are before the start of this range,
-    // recording how far we step in order to save doing this for the next range.
-    for (; first_it != reference_maps->end(); ++first_it) {
-      auto map = *first_it;
-      if (map->instruction_position() >= start) break;
-    }
-
-    // Step through the safe points to see whether they are in the range.
-    for (auto it = first_it; it != reference_maps->end(); ++it) {
-      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;
-      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.
-      if (range->HasSpillOperand() &&
-          safe_point >= range->spill_start_index() &&
-          !range->GetSpillOperand()->IsConstant()) {
-        TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
-              range->id(), range->spill_start_index(), safe_point);
-        map->RecordReference(*range->GetSpillOperand());
-      }
-
-      if (!cur->IsSpilled()) {
-        TRACE(
-            "Pointer in register for range %d (start at %d) "
-            "at safe point %d\n",
-            cur->id(), cur->Start().Value(), safe_point);
-        auto operand = cur->GetAssignedOperand();
-        DCHECK(!operand.IsStackSlot());
-        map->RecordReference(operand);
-      }
-    }
+void LiveRangeBuilder::Verify() const {
+  for (auto current : live_ranges()) {
+    if (current != nullptr) current->Verify();
   }
 }
 
 
-void RegisterAllocator::AllocateGeneralRegisters() {
-  num_registers_ = config()->num_general_registers();
-  mode_ = GENERAL_REGISTERS;
-  AllocateRegisters();
+void LiveRangeBuilder::SetLiveRangeAssignedRegister(LiveRange* range, int reg) {
+  if (range->Kind() == DOUBLE_REGISTERS) {
+    assigned_double_registers_->Add(reg);
+  } else {
+    DCHECK(range->Kind() == GENERAL_REGISTERS);
+    assigned_registers_->Add(reg);
+  }
+  range->set_assigned_register(reg);
+  auto assignment = range->GetAssignedOperand();
+  // TODO(dcarney): stop aliasing hint operands.
+  range->ConvertUsesToOperand(assignment, nullptr);
+  if (range->is_phi()) AssignPhiInput(range, assignment);
 }
 
 
-void RegisterAllocator::AllocateDoubleRegisters() {
-  num_registers_ = config()->num_aliased_double_registers();
-  mode_ = DOUBLE_REGISTERS;
-  AllocateRegisters();
+LinearScanAllocator::LinearScanAllocator(LiveRangeBuilder* live_range_builder,
+                                         RegisterKind kind)
+    : live_range_builder_(live_range_builder),
+      mode_(kind),
+      num_registers_(kind == DOUBLE_REGISTERS
+                         ? config()->num_aliased_double_registers()
+                         : config()->num_general_registers()),
+      unhandled_live_ranges_(local_zone()),
+      active_live_ranges_(local_zone()),
+      inactive_live_ranges_(local_zone()) {
+  unhandled_live_ranges().reserve(
+      static_cast<size_t>(code()->VirtualRegisterCount() * 2));
+  active_live_ranges().reserve(8);
+  inactive_live_ranges().reserve(8);
+  // TryAllocateFreeReg and AllocateBlockedReg assume this
+  // when allocating local arrays.
+  DCHECK(RegisterConfiguration::kMaxDoubleRegisters >=
+         config()->num_general_registers());
 }
 
 
-void RegisterAllocator::AllocateRegisters() {
+void LinearScanAllocator::AllocateRegisters() {
   DCHECK(unhandled_live_ranges().empty());
 
   for (auto range : live_ranges()) {
     if (range == nullptr) continue;
     if (range->Kind() == mode_) {
       AddToUnhandledUnsorted(range);
     }
   }
   SortUnhandled();
   DCHECK(UnhandledIsSorted());
 
   DCHECK(active_live_ranges().empty());
   DCHECK(inactive_live_ranges().empty());
 
   if (mode_ == DOUBLE_REGISTERS) {
-    for (int i = 0; i < config()->num_aliased_double_registers(); ++i) {
-      auto current = fixed_double_live_ranges()[i];
-      if (current != nullptr) {
-        AddToInactive(current);
-      }
+    for (auto current : fixed_double_live_ranges()) {
+      if (current != nullptr) AddToInactive(current);
     }
   } else {
     DCHECK(mode_ == GENERAL_REGISTERS);
     for (auto current : fixed_live_ranges()) {
-      if (current != nullptr) {
-        AddToInactive(current);
-      }
+      if (current != nullptr) 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
@@ skipping 53 matching lines @@
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
     }
   }
 
   active_live_ranges().clear();
   inactive_live_ranges().clear();
 }
 
 
-const char* RegisterAllocator::RegisterName(int allocation_index) {
+const char* LinearScanAllocator::RegisterName(int allocation_index) {
   if (mode_ == GENERAL_REGISTERS) {
     return config()->general_register_name(allocation_index);
   } else {
     return config()->double_register_name(allocation_index);
   }
 }
 
 
-bool RegisterAllocator::HasTaggedValue(int virtual_register) const {
-  return code()->IsReference(virtual_register);
-}
-
-
-RegisterKind RegisterAllocator::RequiredRegisterKind(
-    int virtual_register) const {
-  return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS
-                                              : GENERAL_REGISTERS;
-}
-
-
-void RegisterAllocator::AddToActive(LiveRange* range) {
+void LinearScanAllocator::AddToActive(LiveRange* range) {
   TRACE("Add live range %d to active\n", range->id());
   active_live_ranges().push_back(range);
 }
 
 
-void RegisterAllocator::AddToInactive(LiveRange* range) {
+void LinearScanAllocator::AddToInactive(LiveRange* range) {
   TRACE("Add live range %d to inactive\n", range->id());
   inactive_live_ranges().push_back(range);
 }
 
 
-void RegisterAllocator::AddToUnhandledSorted(LiveRange* range) {
+void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) {
   if (range == nullptr || range->IsEmpty()) return;
   DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
   DCHECK(allocation_finger_.Value() <= range->Start().Value());
   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);
     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());
   unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range);
   DCHECK(UnhandledIsSorted());
 }
 
 
-void RegisterAllocator::AddToUnhandledUnsorted(LiveRange* range) {
+void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) {
   if (range == nullptr || range->IsEmpty()) return;
   DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
   TRACE("Add live range %d to unhandled unsorted at end\n", range->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();
 }
 
 
 // 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 RegisterAllocator::SortUnhandled() {
+void LinearScanAllocator::SortUnhandled() {
   TRACE("Sort unhandled\n");
   std::sort(unhandled_live_ranges().begin(), unhandled_live_ranges().end(),
             &UnhandledSortHelper);
 }
 
 
-bool RegisterAllocator::UnhandledIsSorted() {
+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().Value() < b->Start().Value()) return false;
   }
   return true;
 }
 
 
-void RegisterAllocator::ActiveToHandled(LiveRange* range) {
+void LinearScanAllocator::ActiveToHandled(LiveRange* range) {
   RemoveElement(&active_live_ranges(), range);
   TRACE("Moving live range %d from active to handled\n", range->id());
 }
 
 
-void RegisterAllocator::ActiveToInactive(LiveRange* range) {
+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());
 }
 
 
-void RegisterAllocator::InactiveToHandled(LiveRange* range) {
+void LinearScanAllocator::InactiveToHandled(LiveRange* range) {
   RemoveElement(&inactive_live_ranges(), range);
   TRACE("Moving live range %d from inactive to handled\n", range->id());
 }
 
 
-void RegisterAllocator::InactiveToActive(LiveRange* range) {
+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());
 }
 
 
-bool RegisterAllocator::TryAllocateFreeReg(LiveRange* current) {
+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);
   }
@@ skipping 48 matching lines @@
   // the range end.
   DCHECK(pos.Value() >= current->End().Value());
   TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg),
         current->id());
   SetLiveRangeAssignedRegister(current, reg);
 
   return true;
 }
 
 
-void RegisterAllocator::AllocateBlockedReg(LiveRange* current) {
+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];
@@ skipping 69 matching lines @@
 
 
 static const InstructionBlock* GetContainingLoop(
     const InstructionSequence* sequence, const InstructionBlock* block) {
   auto index = block->loop_header();
   if (!index.IsValid()) return nullptr;
   return sequence->InstructionBlockAt(index);
 }
 
 
-LifetimePosition RegisterAllocator::FindOptimalSpillingPos(
+LifetimePosition LinearScanAllocator::FindOptimalSpillingPos(
     LiveRange* range, LifetimePosition pos) {
   auto block = GetInstructionBlock(pos.Start());
   auto loop_header =
       block->IsLoopHeader() ? block : GetContainingLoop(code(), block);
 
   if (loop_header == nullptr) return pos;
 
   auto prev_use = range->PreviousUsePositionRegisterIsBeneficial(pos);
 
   while (loop_header != nullptr) {
@@ skipping 11 matching lines @@
     }
 
     // Try hoisting out to an outer loop.
     loop_header = GetContainingLoop(code(), loop_header);
   }
 
   return pos;
 }
 
 
-void RegisterAllocator::SplitAndSpillIntersecting(LiveRange* current) {
+void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   DCHECK(current->HasRegisterAssigned());
   int reg = current->assigned_register();
   auto split_pos = current->Start();
   for (size_t i = 0; i < active_live_ranges().size(); ++i) {
     auto range = active_live_ranges()[i];
     if (range->assigned_register() == reg) {
       auto next_pos = range->NextRegisterPosition(current->Start());
       auto spill_pos = FindOptimalSpillingPos(range, split_pos);
       if (next_pos == nullptr) {
         SpillAfter(range, spill_pos);
@@ skipping 27 matching lines @@
           SpillBetween(range, split_pos, next_intersection);
         }
         InactiveToHandled(range);
         --i;
       }
     }
   }
 }
 
 
-bool RegisterAllocator::IsBlockBoundary(LifetimePosition pos) {
-  return pos.IsFullStart() &&
-         code()->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
-             pos.ToInstructionIndex();
+bool LinearScanAllocator::TryReuseSpillForPhi(LiveRange* range) {
+  if (range->IsChild() || !range->is_phi()) return false;
+  DCHECK(!range->HasSpillOperand());
+
+  auto lookup = phi_map().find(range->id());
+  DCHECK(lookup != phi_map().end());
+  auto phi = lookup->second->phi;
+  auto block = lookup->second->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->GetSpillRange() == nullptr) 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->IsSpilled()) {
+      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();
+  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_spill = op_range->GetSpillRange();
+    if (op_spill != nullptr &&
+        (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() ||
+      AreUseIntervalsIntersecting(first_op_spill->interval(),
+                                  range->first_interval())) {
+    return false;
+  }
+
+  // If the range does not need register soon, spill it to the merged
+  // spill range.
+  auto next_pos = range->Start();
+  if (next_pos.IsGapPosition()) next_pos = next_pos.NextStart();
+  auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
+  if (pos == nullptr) {
+    auto spill_range = range->TopLevel()->HasSpillRange()
+                           ? range->TopLevel()->GetSpillRange()
+                           : live_range_builder()->AssignSpillRangeToLiveRange(
+                                 range->TopLevel());
+    bool merged = first_op_spill->TryMerge(spill_range);
+    CHECK(merged);
+    Spill(range);
+    return true;
+  } else if (pos->pos().Value() > range->Start().NextStart().Value()) {
+    auto spill_range = range->TopLevel()->HasSpillRange()
+                           ? range->TopLevel()->GetSpillRange()
+                           : live_range_builder()->AssignSpillRangeToLiveRange(
+                                 range->TopLevel());
+    bool merged = first_op_spill->TryMerge(spill_range);
+    CHECK(merged);
+    SpillBetween(range, range->Start(), pos->pos());
+    DCHECK(UnhandledIsSorted());
+    return true;
+  }
+  return false;
 }
 
 
-LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range,
-                                           LifetimePosition pos) {
+LiveRange* LinearScanAllocator::SplitRangeAt(LiveRange* range,
+                                             LifetimePosition pos) {
   DCHECK(!range->IsFixed());
   TRACE("Splitting live range %d at %d\n", range->id(), pos.Value());
 
   if (pos.Value() <= range->Start().Value()) return range;
 
   // We can't properly connect liveranges if splitting occurred at the end
   // a block.
   DCHECK(pos.IsStart() || pos.IsGapPosition() ||
          (code()->GetInstructionBlock(pos.ToInstructionIndex()))
                  ->last_instruction_index() != pos.ToInstructionIndex());
 
   int vreg = GetVirtualRegister();
   auto result = LiveRangeFor(vreg);
   range->SplitAt(pos, result, local_zone());
   return result;
 }
 
 
-LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
-                                           LifetimePosition start,
-                                           LifetimePosition end) {
+LiveRange* LinearScanAllocator::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());
 
   auto split_pos = FindOptimalSplitPos(start, end);
   DCHECK(split_pos.Value() >= start.Value());
   return SplitRangeAt(range, split_pos);
 }
 
 
-LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start,
-                                                        LifetimePosition end) {
+LifetimePosition LinearScanAllocator::FindOptimalSplitPos(
+    LifetimePosition start, LifetimePosition end) {
   int start_instr = start.ToInstructionIndex();
   int end_instr = end.ToInstructionIndex();
   DCHECK(start_instr <= end_instr);
 
   // We have no choice
   if (start_instr == end_instr) return end;
 
   auto start_block = GetInstructionBlock(start);
   auto end_block = GetInstructionBlock(end);
 
@@ skipping 14 matching lines @@
 
   // We did not find any suitable outer loop. Split at the latest possible
   // position unless end_block is a loop header itself.
   if (block == end_block && !end_block->IsLoopHeader()) return end;
 
   return LifetimePosition::GapFromInstructionIndex(
       block->first_instruction_index());
 }
 
 
-void RegisterAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
+void LinearScanAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
   auto second_part = SplitRangeAt(range, pos);
   Spill(second_part);
 }
 
 
-void RegisterAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
-                                     LifetimePosition end) {
+void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
+                                       LifetimePosition end) {
   SpillBetweenUntil(range, start, start, end);
 }
 
 
-void RegisterAllocator::SpillBetweenUntil(LiveRange* range,
-                                          LifetimePosition start,
-                                          LifetimePosition until,
-                                          LifetimePosition end) {
+void LinearScanAllocator::SpillBetweenUntil(LiveRange* range,
+                                            LifetimePosition start,
+                                            LifetimePosition until,
+                                            LifetimePosition end) {
   CHECK(start.Value() < end.Value());
   auto second_part = SplitRangeAt(range, start);
 
   if (second_part->Start().Value() < end.Value()) {
     // The split result intersects with [start, end[.
     // Split it at position between ]start+1, end[, spill the middle part
     // and put the rest to unhandled.
     auto third_part_end = end.PrevStart().End();
-    if (IsBlockBoundary(end.Start())) {
+    if (live_range_builder()->IsBlockBoundary(end.Start())) {
       third_part_end = end.Start();
     }
     auto third_part = SplitBetween(
         second_part, Max(second_part->Start().End(), until), third_part_end);
 
     DCHECK(third_part != second_part);
 
     Spill(second_part);
     AddToUnhandledSorted(third_part);
   } else {
     // The split result does not intersect with [start, end[.
     // Nothing to spill. Just put it to unhandled as whole.
     AddToUnhandledSorted(second_part);
   }
 }
 
 
-void RegisterAllocator::Spill(LiveRange* range) {
+void LinearScanAllocator::Spill(LiveRange* range) {
   DCHECK(!range->IsSpilled());
   TRACE("Spilling live range %d\n", range->id());
   auto first = range->TopLevel();
   if (first->HasNoSpillType()) {
-    AssignSpillRangeToLiveRange(first);
+    live_range_builder()->AssignSpillRangeToLiveRange(first);
   }
   range->MakeSpilled();
 }
 
 
-int RegisterAllocator::RegisterCount() const { return num_registers_; }
-
-
-#ifdef DEBUG
-
-
-void RegisterAllocator::Verify() const {
-  for (auto current : live_ranges()) {
-    if (current != nullptr) current->Verify();
-  }
-}
-
-
-#endif
-
-
-void RegisterAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
-                                                     int reg) {
-  if (range->Kind() == DOUBLE_REGISTERS) {
-    assigned_double_registers_->Add(reg);
+OperandAssigner::OperandAssigner(LiveRangeBuilder* live_range_builder)
+    : live_range_builder_(live_range_builder) {}
+
+
+void OperandAssigner::AssignSpillSlots() {
+  auto& spill_ranges = live_range_builder()->spill_ranges();
+  // Merge disjoint spill ranges
+  for (size_t i = 0; i < spill_ranges.size(); i++) {
+    auto range = spill_ranges[i];
+    if (range->IsEmpty()) continue;
+    for (size_t j = i + 1; j < spill_ranges.size(); j++) {
+      auto other = spill_ranges[j];
+      if (!other->IsEmpty()) {
+        range->TryMerge(other);
+      }
+    }
+  }
+  // Allocate slots for the merged spill ranges.
+  for (auto range : spill_ranges) {
+    if (range->IsEmpty()) continue;
+    // Allocate a new operand referring to the spill slot.
+    auto kind = range->Kind();
+    int index = live_range_builder()->frame()->AllocateSpillSlot(
+        kind == DOUBLE_REGISTERS);
+    auto op_kind = kind == DOUBLE_REGISTERS
+                       ? AllocatedOperand::DOUBLE_STACK_SLOT
+                       : AllocatedOperand::STACK_SLOT;
+    auto op = AllocatedOperand::New(live_range_builder()->code_zone(), op_kind,
+                                    index);
+    range->SetOperand(op);
+  }
+}
+
+
+void OperandAssigner::CommitAssignment() {
+  for (auto range : live_range_builder()->live_ranges()) {
+    if (range == nullptr || range->IsEmpty()) continue;
+    InstructionOperand* spill_operand = nullptr;
+    if (!range->TopLevel()->HasNoSpillType()) {
+      spill_operand = range->TopLevel()->GetSpillOperand();
+    }
+    auto assigned = range->GetAssignedOperand();
+    range->ConvertUsesToOperand(assigned, spill_operand);
+    if (range->is_phi()) live_range_builder()->AssignPhiInput(range, assigned);
+    if (!range->IsChild() && spill_operand != nullptr) {
+      range->CommitSpillsAtDefinition(live_range_builder()->code(),
+                                      spill_operand, range->has_slot_use());
+    }
+  }
+}
+
+
+ReferenceMapPopulator::ReferenceMapPopulator(
+    LiveRangeBuilder* live_range_builder)
+    : live_range_builder_(live_range_builder) {}
+
+
+bool ReferenceMapPopulator::SafePointsAreInOrder() const {
+  int safe_point = 0;
+  for (auto map : *live_range_builder()->code()->reference_maps()) {
+    if (safe_point > map->instruction_position()) return false;
+    safe_point = map->instruction_position();
+  }
+  return true;
+}
+
+
+void ReferenceMapPopulator::PopulateReferenceMaps() {
+  DCHECK(SafePointsAreInOrder());
+
+  // 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 = live_range_builder()->code()->reference_maps();
+  ReferenceMapDeque::const_iterator first_it = reference_maps->begin();
+  for (LiveRange* range : live_range_builder()->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 (!IsReference(range->id())) 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()) {
+      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;
+
+    // Step across all the safe points that are before the start of this range,
+    // recording how far we step in order to save doing this for the next range.
+    for (; first_it != reference_maps->end(); ++first_it) {
+      auto map = *first_it;
+      if (map->instruction_position() >= start) break;
+    }
+
+    // Step through the safe points to see whether they are in the range.
+    for (auto it = first_it; it != reference_maps->end(); ++it) {
+      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;
+      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.
+      if (range->HasSpillOperand() &&
+          safe_point >= range->spill_start_index() &&
+          !range->GetSpillOperand()->IsConstant()) {
+        TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
+              range->id(), range->spill_start_index(), safe_point);
+        map->RecordReference(*range->GetSpillOperand());
+      }
+
+      if (!cur->IsSpilled()) {
+        TRACE(
+            "Pointer in register for range %d (start at %d) "
+            "at safe point %d\n",
+            cur->id(), cur->Start().Value(), safe_point);
+        auto operand = cur->GetAssignedOperand();
+        DCHECK(!operand.IsStackSlot());
+        map->RecordReference(operand);
+      }
+    }
+  }
+}
+
+
+namespace {
+
+class LiveRangeBound {
+ public:
+  explicit LiveRangeBound(const LiveRange* range)
+      : range_(range), start_(range->Start()), end_(range->End()) {
+    DCHECK(!range->IsEmpty());
+  }
+
+  bool CanCover(LifetimePosition position) {
+    return start_.Value() <= position.Value() &&
+           position.Value() < end_.Value();
+  }
+
+  const LiveRange* const range_;
+  const LifetimePosition start_;
+  const LifetimePosition end_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeBound);
+};
+
+
+struct FindResult {
+  const LiveRange* cur_cover_;
+  const LiveRange* pred_cover_;
+};
+
+
+class LiveRangeBoundArray {
+ public:
+  LiveRangeBoundArray() : length_(0), start_(nullptr) {}
+
+  bool ShouldInitialize() { return start_ == nullptr; }
+
+  void Initialize(Zone* zone, const LiveRange* const range) {
+    size_t length = 0;
+    for (auto i = range; i != nullptr; i = i->next()) length++;
+    start_ = zone->NewArray<LiveRangeBound>(length);
+    length_ = length;
+    auto curr = start_;
+    for (auto i = range; i != nullptr; i = i->next(), ++curr) {
+      new (curr) LiveRangeBound(i);
+    }
+  }
+
+  LiveRangeBound* Find(const LifetimePosition position) const {
+    size_t left_index = 0;
+    size_t right_index = length_;
+    while (true) {
+      size_t current_index = left_index + (right_index - left_index) / 2;
+      DCHECK(right_index > current_index);
+      auto bound = &start_[current_index];
+      if (bound->start_.Value() <= position.Value()) {
+        if (position.Value() < bound->end_.Value()) return bound;
+        DCHECK(left_index < current_index);
+        left_index = current_index;
+      } else {
+        right_index = current_index;
+      }
+    }
+  }
+
+  LiveRangeBound* FindPred(const InstructionBlock* pred) {
+    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
+        pred->last_instruction_index());
+    return Find(pred_end);
+  }
+
+  LiveRangeBound* FindSucc(const InstructionBlock* succ) {
+    auto succ_start = LifetimePosition::GapFromInstructionIndex(
+        succ->first_instruction_index());
+    return Find(succ_start);
+  }
+
+  void Find(const InstructionBlock* block, const InstructionBlock* pred,
+            FindResult* result) const {
+    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
+        pred->last_instruction_index());
+    auto bound = Find(pred_end);
+    result->pred_cover_ = bound->range_;
+    auto cur_start = LifetimePosition::GapFromInstructionIndex(
+        block->first_instruction_index());
+    // Common case.
+    if (bound->CanCover(cur_start)) {
+      result->cur_cover_ = bound->range_;
+      return;
+    }
+    result->cur_cover_ = Find(cur_start)->range_;
+    DCHECK(result->pred_cover_ != nullptr && result->cur_cover_ != nullptr);
+  }
+
+ private:
+  size_t length_;
+  LiveRangeBound* start_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeBoundArray);
+};
+
+
+class LiveRangeFinder {
+ public:
+  explicit LiveRangeFinder(const LiveRangeBuilder& builder)
+      : builder_(builder),
+        bounds_length_(static_cast<int>(builder.live_ranges().size())),
+        bounds_(builder.local_zone()->NewArray<LiveRangeBoundArray>(
+            bounds_length_)) {
+    for (int i = 0; i < bounds_length_; ++i) {
+      new (&bounds_[i]) LiveRangeBoundArray();
+    }
+  }
+
+  LiveRangeBoundArray* ArrayFor(int operand_index) {
+    DCHECK(operand_index < bounds_length_);
+    auto range = builder_.live_ranges()[operand_index];
+    DCHECK(range != nullptr && !range->IsEmpty());
+    auto array = &bounds_[operand_index];
+    if (array->ShouldInitialize()) {
+      array->Initialize(builder_.local_zone(), range);
+    }
+    return array;
+  }
+
+ private:
+  const LiveRangeBuilder& builder_;
+  const int bounds_length_;
+  LiveRangeBoundArray* const bounds_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeFinder);
+};
+
+}  // namespace
+
+
+LiveRangeConnector::LiveRangeConnector(LiveRangeBuilder* live_range_builder)
+    : live_range_builder_(live_range_builder) {}
+
+
+bool LiveRangeConnector::CanEagerlyResolveControlFlow(
+    const InstructionBlock* block) const {
+  if (block->PredecessorCount() != 1) return false;
+  return block->predecessors()[0].IsNext(block->rpo_number());
+}
+
+
+void LiveRangeConnector::ResolveControlFlow() {
+  // Lazily linearize live ranges in memory for fast lookup.
+  LiveRangeFinder finder(*live_range_builder());
+  auto& live_in_sets = live_range_builder()->live_in_sets();
+  for (auto block : code()->instruction_blocks()) {
+    if (CanEagerlyResolveControlFlow(block)) continue;
+    auto live = live_in_sets[block->rpo_number().ToInt()];
+    BitVector::Iterator iterator(live);
+    while (!iterator.Done()) {
+      auto* array = finder.ArrayFor(iterator.Current());
+      for (auto pred : block->predecessors()) {
+        FindResult result;
+        const auto* pred_block = code()->InstructionBlockAt(pred);
+        array->Find(block, pred_block, &result);
+        if (result.cur_cover_ == result.pred_cover_ ||
+            result.cur_cover_->IsSpilled())
+          continue;
+        auto pred_op = result.pred_cover_->GetAssignedOperand();
+        auto cur_op = result.cur_cover_->GetAssignedOperand();
+        if (pred_op == cur_op) continue;
+        ResolveControlFlow(block, cur_op, pred_block, pred_op);
+      }
+      iterator.Advance();
+    }
+  }
+}
+
+
+void LiveRangeConnector::ResolveControlFlow(const InstructionBlock* block,
+                                            const InstructionOperand& cur_op,
+                                            const InstructionBlock* pred,
+                                            const InstructionOperand& pred_op) {
+  DCHECK(pred_op != cur_op);
+  int gap_index;
+  Instruction::GapPosition position;
+  if (block->PredecessorCount() == 1) {
+    gap_index = block->first_instruction_index();
+    position = Instruction::START;
   } else {
-    DCHECK(range->Kind() == GENERAL_REGISTERS);
-    assigned_registers_->Add(reg);
-  }
-  range->set_assigned_register(reg);
-  auto assignment = range->GetAssignedOperand();
-  // TODO(dcarney): stop aliasing hint operands.
-  range->ConvertUsesToOperand(assignment, nullptr);
-  if (range->is_phi()) AssignPhiInput(range, assignment);
+    DCHECK(pred->SuccessorCount() == 1);
+    DCHECK(!live_range_builder()
+                ->InstructionAt(pred->last_instruction_index())
+                ->HasReferenceMap());
+    gap_index = pred->last_instruction_index();
+    position = Instruction::END;
+  }
+  live_range_builder()->AddGapMove(gap_index, position, pred_op, cur_op);
+}
+
+
+void LiveRangeConnector::ConnectRanges(Zone* temp_zone) {
+  ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand>
+      delayed_insertion_map(temp_zone);
+  for (auto first_range : live_range_builder()->live_ranges()) {
+    if (first_range == nullptr || first_range->IsChild()) continue;
+    for (auto 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 (second_range->IsSpilled()) continue;
+      if (first_range->End().Value() != pos.Value()) continue;
+      if (live_range_builder()->IsBlockBoundary(pos) &&
+          !CanEagerlyResolveControlFlow(GetInstructionBlock(pos))) {
+        continue;
+      }
+      auto prev_operand = first_range->GetAssignedOperand();
+      auto cur_operand = second_range->GetAssignedOperand();
+      if (prev_operand == cur_operand) continue;
+      bool delay_insertion = false;
+      Instruction::GapPosition gap_pos;
+      int gap_index = pos.ToInstructionIndex();
+      if (pos.IsGapPosition()) {
+        gap_pos = pos.IsStart() ? Instruction::START : Instruction::END;
+      } else {
+        if (pos.IsStart()) {
+          delay_insertion = true;
+        } else {
+          gap_index++;
+        }
+        gap_pos = delay_insertion ? Instruction::END : Instruction::START;
+      }
+      auto move = code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
+          gap_pos, code_zone());
+      if (!delay_insertion) {
+        move->AddMove(prev_operand, cur_operand);
+      } else {
+        delayed_insertion_map.insert(
+            std::make_pair(std::make_pair(move, prev_operand), cur_operand));
+      }
+    }
+  }
+  if (delayed_insertion_map.empty()) return;
+  // Insert all the moves which should occur after the stored move.
+  ZoneVector<MoveOperands*> to_insert(temp_zone);
+  ZoneVector<MoveOperands*> to_eliminate(temp_zone);
+  to_insert.reserve(4);
+  to_eliminate.reserve(4);
+  auto moves = delayed_insertion_map.begin()->first.first;
+  for (auto it = delayed_insertion_map.begin();; ++it) {
+    bool done = it == delayed_insertion_map.end();
+    if (done || it->first.first != moves) {
+      // Commit the MoveOperands for current ParallelMove.
+      for (auto move : to_eliminate) {
+        move->Eliminate();
+      }
+      for (auto move : to_insert) {
+        moves->push_back(move);
+      }
+      if (done) break;
+      // Reset state.
+      to_eliminate.clear();
+      to_insert.clear();
+      moves = it->first.first;
+    }
+    // Gather all MoveOperands for a single ParallelMove.
+    auto move = new (code_zone()) MoveOperands(it->first.second, it->second);
+    auto eliminate = moves->PrepareInsertAfter(move);
+    to_insert.push_back(move);
+    if (eliminate != nullptr) to_eliminate.push_back(eliminate);
+  }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8