Reland: Introducing the LLVM greedy register allocator.

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)
 
+
+class RegisterAllocationInfo : public ZoneObject {
+ public:
+  explicit RegisterAllocationInfo(Zone* zone) : storage_(zone) {}
+
+  bool Find(UseInterval* query, LiveRange** result) {
+    ZoneSplayTree<Config>::Locator locator;
+    bool ret = storage_.Find(GetKey(query), &locator);
+    if (ret) {
+      *result = locator.value();
+    }
+    return ret;
+  }
+
+  bool Insert(LiveRange* range) {
+    auto* interval = range->first_interval();
+    while (interval) {
+      if (!Insert(interval, range)) return false;
+      interval = interval->next();
+    }
+    return true;
+  }
+
+  bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); }
+
+  bool Remove(LiveRange* range) {
+    bool ret = false;
+    auto* segment = range->first_interval();
+    while (segment) {
+      ret |= Remove(segment);
+      segment = segment->next();
+    }
+    return ret;
+  }
+
+  bool IsEmpty() { return storage_.is_empty(); }
+
+ private:
+  struct Config {
+    typedef std::pair<int, int> Key;
+    typedef LiveRange* Value;
+    static const Key kNoKey;
+    static Value NoValue() { return nullptr; }
+    static int Compare(const Key& a, const Key& b) {
+      if (a.second <= b.first) return -1;
+      if (a.first >= b.second) return 1;
+      return 0;
+    }
+  };
+
+  Config::Key GetKey(UseInterval* interval) {
+    if (!interval) return std::make_pair(0, 0);
+    return std::make_pair(interval->start().Value(), interval->end().Value());
+  }
+  bool Insert(UseInterval* interval, LiveRange* range) {
+    ZoneSplayTree<Config>::Locator locator;
+    bool ret = storage_.Insert(GetKey(interval), &locator);
+    if (ret) locator.set_value(range);
+    return ret;
+  }
+
+  ZoneSplayTree<Config> storage_;
+  DISALLOW_COPY_AND_ASSIGN(RegisterAllocationInfo);
+};
+
+
+const std::pair<int, int> RegisterAllocationInfo::Config::kNoKey =
+    std::make_pair<int, int>(0, 0);
+
+
 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
   return a.Value() < b.Value() ? a : b;
 }
 
 
 static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
   return a.Value() > b.Value() ? a : b;
 }
 
 
@@ skipping 546 matching lines @@
 RegisterAllocator::RegisterAllocator(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()),
+      spill_ranges_(local_zone()),
+      live_in_sets_(code->InstructionBlockCount(), nullptr, local_zone()) {
+  spill_ranges().reserve(8);
+  assigned_registers_ =
+      new (code_zone()) BitVector(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_);
+}
+
+RegisterAllocatorLinear::RegisterAllocatorLinear(
+    const RegisterConfiguration* config, Zone* zone, Frame* frame,
+    InstructionSequence* code, const char* debug_name)
+    : RegisterAllocator(config, zone, frame, code, debug_name),
       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) {
   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_double_registers_ = new (code_zone())
-      BitVector(config->num_aliased_double_registers(), code_zone());
-  frame->SetAllocatedRegisters(assigned_registers_);
-  frame->SetAllocatedDoubleRegisters(assigned_double_registers_);
 }
 
 
 BitVector* RegisterAllocator::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.
@@ skipping 341 matching lines @@
 }
 
 
 SpillRange* RegisterAllocator::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) {
+bool RegisterAllocatorLinear::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 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]);
@@ skipping 806 matching lines @@
 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;
 }
 
 
+unsigned RegisterAllocatorGreedy::GetLiveRangeSize(LiveRange* range) {
+  auto interval = range->first_interval();
+  if (!interval) return 0;
+
+  unsigned size = 0;
+  while (interval) {
+    size += (interval->end().Value() - interval->start().Value());
+    interval = interval->next();
+  }
+
+  DCHECK(size);
+  return size;
+}
+
+
+void RegisterAllocatorGreedy::Enqueue(LiveRange* range) {
+  if (!range || range->IsEmpty()) return;
+  unsigned size = GetLiveRangeSize(range);
+  queue_.push(std::make_pair(size, range));
+}
+
+
+// TODO(mtrofin): consolidate with identical code segment in
+// RegisterAllocatorLinear::AllocateRegisters
+bool RegisterAllocatorGreedy::HandleSpillOperands(LiveRange* range) {
+  auto position = range->Start();
+  TRACE("Processing interval %d start=%d\n", range->id(), position.Value());
+
+  if (!range->HasNoSpillType()) {
+    TRACE("Live range %d already has a spill operand\n", range->id());
+    auto next_pos = position;
+    if (next_pos.IsGapPosition()) {
+      next_pos = next_pos.NextStart();
+    }
+    auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);

[dcarney, 2015/04/18 19:01:33]

NextUsePositionRegisterIsBeneficial is not available to the Greedy allocator as
requires in-order processing of intervals to work

[Mircea Trofin, 2015/04/19 04:02:04]

Acknowledged.

This will need a rewrite anyway.

+    // 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(range);
+      return true;
+    } else if (pos->pos().Value() > range->Start().NextStart().Value()) {
+      // Do not spill live range eagerly if use position that can benefit from
+      // the register is too close to the start of live range.
+      auto* reminder = SpillBetweenUntil(range, position, position, pos->pos());
+      Enqueue(reminder);
+      return true;
+    }
+  }
+  return false;
+  // TODO(mtrofin): Do we need this?
+  // return (TryReuseSpillForPhi(range));
+}
+
+
+void RegisterAllocatorGreedy::AllocateRegisters(RegisterKind mode) {
+  // TODO(mtrofin): support for double registers
+  DCHECK(mode == GENERAL_REGISTERS);
+
+  for (auto range : live_ranges()) {
+    if (range == nullptr) continue;
+    if (range->Kind() == mode) {
+      DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
+      TRACE("Enqueueing live range %d to priority queue \n", range->id());
+      Enqueue(range);
+    }
+  }
+
+  allocations_.resize(config()->kMaxGeneralRegisters);

[dcarney, 2015/04/18 19:01:32]

config()->num_general_registers() is the number of registers available to the
current allocator kMaxGeneralRegisters is the max available across all platforms

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+  for (int i = 0; i < config()->kMaxGeneralRegisters; i++) {
+    allocations_[i] = new (local_zone()) RegisterAllocationInfo(local_zone());
+  }
+
+  for (auto* current : fixed_live_ranges()) {
+    if (current != nullptr) {
+      int regNr = current->assigned_register();
+      CHECK((allocations_[regNr]->Insert(current)));

[dcarney, 2015/04/18 19:01:33]

generally we ensure CHECK should be convertible to DCHECK and vice versa without
affecting correctness

bool inserted = allocations_[regNr]->Insert(current);
CHECK(inserted);

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+    }
+  }
+
+  while (!queue_.empty()) {
+    auto currentPair = queue_.top();
+    queue_.pop();
+    auto current = currentPair.second;
+    if (HandleSpillOperands(current)) continue;
+    ZoneSet<LiveRange*> conflicting(local_zone());
+    if (!TryAllocate(current, &conflicting)) {
+      DCHECK(conflicting.size());
+      float thisMax = CalculateSpillWeight(current);
+      float maxConflicting = CalculateMaxSpillWeight(conflicting);
+      if (maxConflicting < thisMax) {
+        for (auto* conflict : conflicting) {
+          Evict(conflict);
+          Enqueue(conflict);
+        }
+        conflicting.clear();
+        CHECK(TryAllocate(current, &conflicting));
+        DCHECK(conflicting.size() == 0);
+      } else {
+        DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
+        CHECK(AllocateBlockedRange(current, conflicting));

[dcarney, 2015/04/18 19:01:33]

here and 2 lines above CHECK issue again

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+      }
+    }
+  }
+  for (unsigned i = 0; i < allocations_.size(); i++) {

[dcarney, 2015/04/18 19:01:33]

size_t here and in other places when iterating to a std container size()
also, in all loops, use ++i, even for integers

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+    if (!allocations_[i]->IsEmpty()) {
+      assigned_registers()->Add(i);
+    }
+  }
+}
+
+
+bool RegisterAllocatorGreedy::AllocateBlockedRange(
+    LiveRange* current, const ZoneSet<LiveRange*>& conflicts) {
+  auto register_use = current->NextRegisterPosition(current->Start());

[dcarney, 2015/04/18 19:01:33]

NextRegisterPosition is also unavailable to the greedy allocator

[Mircea Trofin, 2015/04/19 04:02:04]

Acknowledged.

+  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 true;
+  }
+
+  auto second_part = SplitRangeAt(current, register_use->pos());
+  Spill(second_part);
+
+  return true;
+}
+
+
 void RegisterAllocator::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 = code()->reference_maps();
   ReferenceMapDeque::const_iterator first_it = reference_maps->begin();
   for (LiveRange* range : live_ranges()) {
     if (range == nullptr) continue;
@@ skipping 61 matching lines @@
             cur->id(), cur->Start().Value(), safe_point);
         auto operand = cur->GetAssignedOperand();
         DCHECK(!operand.IsStackSlot());
         map->RecordReference(operand);
       }
     }
   }
 }
 
 
-void RegisterAllocator::AllocateGeneralRegisters() {
+void RegisterAllocatorLinear::AllocateGeneralRegisters() {
   num_registers_ = config()->num_general_registers();
   mode_ = GENERAL_REGISTERS;
   AllocateRegisters();
 }
 
 
-void RegisterAllocator::AllocateDoubleRegisters() {
+void RegisterAllocatorLinear::AllocateDoubleRegisters() {
   num_registers_ = config()->num_aliased_double_registers();
   mode_ = DOUBLE_REGISTERS;
   AllocateRegisters();
 }
 
 
-void RegisterAllocator::AllocateRegisters() {
+void RegisterAllocatorLinear::AllocateRegisters() {
   DCHECK(unhandled_live_ranges().empty());
 
   for (auto range : live_ranges()) {
     if (range == nullptr) continue;
     if (range->Kind() == mode_) {
       AddToUnhandledUnsorted(range);
     }
   }
   SortUnhandled();
   DCHECK(UnhandledIsSorted());
@@ skipping 80 matching lines @@
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
     }
   }
 
   active_live_ranges().clear();
   inactive_live_ranges().clear();
 }
 
 
-const char* RegisterAllocator::RegisterName(int allocation_index) {
+const char* RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::SortUnhandled() {
   TRACE("Sort unhandled\n");
   std::sort(unhandled_live_ranges().begin(), unhandled_live_ranges().end(),
             &UnhandledSortHelper);
 }
 
 
-bool RegisterAllocator::UnhandledIsSorted() {
+bool RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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) {
+RegisterAllocatorGreedy::RegisterAllocatorGreedy(
+    const RegisterConfiguration* config, Zone* local_zone, Frame* frame,
+    InstructionSequence* code, const char* debug_name)
+    : RegisterAllocator(config, local_zone, frame, code, debug_name),
+      allocations_(local_zone),
+      queue_(local_zone) {}
+
+
+void RegisterAllocatorGreedy::AllocateGeneralRegisters() {
+  AllocateRegisters(RegisterKind::GENERAL_REGISTERS);
+}
+
+
+void RegisterAllocatorGreedy::AllocateDoubleRegisters() {
+  AllocateRegisters(RegisterKind::DOUBLE_REGISTERS);
+}
+
+
+void RegisterAllocatorGreedy::AssignRangeToRegister(unsigned reg_id,
+                                                    LiveRange* range) {
+  allocations_[reg_id]->Insert(range);
+  if (range->HasRegisterAssigned()) {
+    DCHECK((unsigned)(range->assigned_register()) == reg_id);

[dcarney, 2015/04/18 19:01:33]

chromium style guide dictates that you must use static_cast<unsigned>() instead
of c-style casts
that being said, you probably want reg_id all over the place to be int, since
that's how it's coming in

also, we generally want DCHECK_EQ(expected_value, value) instead of
DCHECK(expected_value == value)

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+    return;
+  }
+  range->set_assigned_register(reg_id);
+}
+
+
+float RegisterAllocatorGreedy::CalculateSpillWeight(LiveRange* range) {
+  if (range->IsFixed()) return std::numeric_limits<float>::max();
+
+  if (range->FirstHint() && range->FirstHint()->IsRegister())

[dcarney, 2015/04/18 19:01:33]

need braces on multiline if 

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+    return std::numeric_limits<float>::max();
+
+  unsigned useCount = 0;
+  auto* pos = range->first_pos();
+  while (pos != nullptr) {
+    useCount++;
+    pos = pos->next();
+  }
+
+  // GetLiveRangeSize is DCHECK-ed to not be 0
+  return static_cast<float>(useCount) /
+         static_cast<float>(GetLiveRangeSize(range));
+}
+
+
+float RegisterAllocatorGreedy::CalculateMaxSpillWeight(
+    const ZoneSet<LiveRange*>& ranges) {
+  float max = 0.0;
+  for (auto* r : ranges) {
+    float localMax = CalculateSpillWeight(r);

[dcarney, 2015/04/18 19:01:33]

max = std::max(max, CalculateSpillWeight(r)

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+    if (localMax > max) max = localMax;
+  }
+  return max;
+}
+
+
+void RegisterAllocatorGreedy::Evict(LiveRange* range) {
+  allocations_[range->assigned_register()]->Remove(range);
+}
+
+
+bool RegisterAllocatorGreedy::TryAllocatePhysicalRegister(
+    unsigned reg_id, LiveRange* range, ZoneSet<LiveRange*>* conflicting) {
+  auto* segment = range->first_interval();
+
+  RegisterAllocationInfo* allocInfo = allocations_[reg_id];
+  while (segment) {
+    LiveRange* existing;
+    if (allocInfo->Find(segment, &existing)) {
+      DCHECK(existing->HasRegisterAssigned());
+      conflicting->insert(existing);
+    }
+    segment = segment->next();
+  }
+  if (!conflicting->empty()) return false;
+  // good to insert

[dcarney, 2015/04/18 19:01:33]

comments in v8 typically start with a capital and end with a period and are
generally complete sentences, but i'm really not sure if there are any rules
about that

[Mircea Trofin, 2015/04/19 04:02:04]

Done.

+  AssignRangeToRegister(reg_id, range);
+  return true;
+}
+
+bool RegisterAllocatorGreedy::TryAllocate(LiveRange* current,
+                                          ZoneSet<LiveRange*>* conflicting) {
+  if (current->HasSpillOperand()) {
+    Spill(current);
+    return true;
+  }
+  if (current->IsFixed()) {
+    return TryAllocatePhysicalRegister(current->assigned_register(), current,
+                                       conflicting);
+  }
+
+  if (current->HasRegisterAssigned()) {
+    int reg_id = current->assigned_register();
+    return TryAllocatePhysicalRegister(reg_id, current, conflicting);
+  }
+
+  for (unsigned candidate_reg = 0; candidate_reg < allocations_.size();
+       candidate_reg++) {
+    if (TryAllocatePhysicalRegister(candidate_reg, current, conflicting)) {
+      conflicting->clear();
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 RegisterAllocatorLinear::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 103 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 RegisterAllocatorLinear::SpillAfter(LiveRange* range,
+                                         LifetimePosition pos) {
   auto second_part = SplitRangeAt(range, pos);
   Spill(second_part);
 }
 
 
-void RegisterAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
-                                     LifetimePosition end) {
+void RegisterAllocatorLinear::SpillBetween(LiveRange* range,
+                                           LifetimePosition start,
+                                           LifetimePosition end) {
   SpillBetweenUntil(range, start, start, end);
 }
 
 
-void RegisterAllocator::SpillBetweenUntil(LiveRange* range,
-                                          LifetimePosition start,
-                                          LifetimePosition until,
-                                          LifetimePosition end) {
+void RegisterAllocatorLinear::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())) {
       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);
   }
 }
 
+LiveRange* RegisterAllocatorGreedy::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())) {
+      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);
+    return third_part;
+  } else {
+    // The split result does not intersect with [start, end[.
+    // Nothing to spill. Just put it to unhandled as whole.
+    return second_part;
+  }
+}
+
 
 void RegisterAllocator::Spill(LiveRange* range) {
   DCHECK(!range->IsSpilled());
   TRACE("Spilling live range %d\n", range->id());
   auto first = range->TopLevel();
   if (first->HasNoSpillType()) {
     AssignSpillRangeToLiveRange(first);
   }
   range->MakeSpilled();
 }
 
 
-int RegisterAllocator::RegisterCount() const { return num_registers_; }
+int RegisterAllocatorLinear::RegisterCount() const { return num_registers_; }
 
 
 #ifdef DEBUG
 
 
-void RegisterAllocator::Verify() const {
+void RegisterAllocatorLinear::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);
   } 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);
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8