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/base/adapters.h"
 #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 CoallescedLiveRanges : public ZoneObject {
+ public:
+  explicit CoallescedLiveRanges(Zone* zone) : storage_(zone) {}
+
+  LiveRange* Find(UseInterval* query) {
+    ZoneSplayTree<Config>::Locator locator;
+
+    if (storage_.Find(GetKey(query), &locator)) {
+      return locator.value();
+    }
+    return nullptr;
+  }
+
+  // TODO(mtrofin): Change to void returning if we do not care if the interval
+  // was previously added.
+  bool Insert(LiveRange* range) {
+    auto* interval = range->first_interval();
+    while (interval != nullptr) {
+      if (!Insert(interval, range)) return false;
+      interval = interval->next();
+    }
+    return true;
+  }
+
+  bool Remove(LiveRange* range) {
+    bool ret = false;
+    auto* segment = range->first_interval();
+    while (segment != nullptr) {
+      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 == nullptr) return std::make_pair(0, 0);
+    return std::make_pair(interval->start().Value(), interval->end().Value());
+  }
+
+  // TODO(mtrofin): Change to void returning if we do not care if the interval
+  // was previously added.
+  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;
+  }
+
+  bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); }
+
+  ZoneSplayTree<Config> storage_;
+  DISALLOW_COPY_AND_ASSIGN(CoallescedLiveRanges);
+};
+
+
+const std::pair<int, int> CoallescedLiveRanges::Config::kNoKey =
+    std::make_pair<int, int>(0, 0);
+
+
 namespace {
 
 inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
   return a.Value() < b.Value() ? a : b;
 }
 
 
 inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
   return a.Value() > b.Value() ? a : b;
 }
 
 
 void RemoveElement(ZoneVector<LiveRange*>* v, LiveRange* range) {
   auto it = std::find(v->begin(), v->end(), range);
   DCHECK(it != v->end());
   v->erase(it);
 }
 
+
+static int GetRegisterCount(const RegisterConfiguration* cfg,
+                            RegisterKind kind) {
+  return kind == DOUBLE_REGISTERS ? cfg->num_aliased_double_registers()
+                                  : cfg->num_general_registers();
+}
+
+
+static const ZoneVector<LiveRange*>& GetFixedRegisters(
+    const RegisterAllocationData* data, RegisterKind kind) {
+  return kind == DOUBLE_REGISTERS ? data->fixed_double_live_ranges()
+                                  : data->fixed_live_ranges();
+}
+
 }  // 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_);
@@ skipping 1377 matching lines @@
   for (auto current : data()->live_ranges()) {
     if (current != nullptr) current->Verify();
   }
 }
 
 
 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
                                          RegisterKind kind)
     : data_(data),
       mode_(kind),
-      num_registers_(kind == DOUBLE_REGISTERS
-                         ? config()->num_aliased_double_registers()
-                         : config()->num_general_registers()),
+      num_registers_(GetRegisterCount(data->config(), kind)),
       unhandled_live_ranges_(allocation_zone()),
       active_live_ranges_(allocation_zone()),
       inactive_live_ranges_(allocation_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 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 (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);
+  auto& fixed_ranges = GetFixedRegisters(data(), mode_);
+  for (auto current : fixed_ranges) {
+    if (current != nullptr) {
+      DCHECK_EQ(mode_, current->Kind());
+      AddToInactive(current);
     }
   }
 
   while (!unhandled_live_ranges().empty()) {
     DCHECK(UnhandledIsSorted());
     auto current = unhandled_live_ranges().back();
     unhandled_live_ranges().pop_back();
     DCHECK(UnhandledIsSorted());
     auto position = current->Start();
 #ifdef DEBUG
     allocation_finger_ = position;
 #endif
     TRACE("Processing interval %d start=%d\n", current->id(), position.Value());
 
     if (!current->HasNoSpillType()) {
       TRACE("Live range %d already has a spill operand\n", current->id());
       auto next_pos = position;
       if (next_pos.IsGapPosition()) {
         next_pos = next_pos.NextStart();
       }
       auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
       // If the range already has a spill operand and it doesn't need a
       // register immediately, split it and spill the first part of the range.
       if (pos == nullptr) {
-        Spill(current);
+        data()->Spill(current);
         continue;
       } else if (pos->pos().Value() > current->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.
         SpillBetween(current, current->Start(), pos->pos());
         DCHECK(UnhandledIsSorted());
         continue;
       }
     }
 
@@ skipping 186 matching lines @@
   auto pos = free_until_pos[reg];
 
   if (pos.Value() <= current->Start().Value()) {
     // All registers are blocked.
     return false;
   }
 
   if (pos.Value() < current->End().Value()) {
     // Register reg is available at the range start but becomes blocked before
     // the range end. Split current at position where it becomes blocked.
-    auto tail = SplitRangeAt(current, pos);
+    auto tail = data()->SplitRangeAt(current, pos);
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is available at the range start and is free until
   // 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 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);
+    data()->Spill(current);
     return;
   }
 
   LifetimePosition use_pos[RegisterConfiguration::kMaxDoubleRegisters];
   LifetimePosition block_pos[RegisterConfiguration::kMaxDoubleRegisters];
 
   for (int i = 0; i < num_registers_; i++) {
     use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition();
   }
 
@@ skipping 39 matching lines @@
     // All registers are blocked before the first use that requires a register.
     // Spill starting part of live range up to that use.
     SpillBetween(current, current->Start(), register_use->pos());
     return;
   }
 
   if (block_pos[reg].Value() < current->End().Value()) {
     // Register becomes blocked before the current range end. Split before that
     // position.
     LiveRange* tail =
-        SplitBetween(current, current->Start(), block_pos[reg].Start());
+        data()->SplitBetween(current, current->Start(), block_pos[reg].Start());
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is not blocked for the whole range.
   DCHECK(block_pos[reg].Value() >= current->End().Value());
   TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg),
         current->id());
   SetLiveRangeAssignedRegister(current, reg);
 
   // This register was not free. Thus we need to find and spill
@@ skipping 153 matching lines @@
   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()
             : data()->AssignSpillRangeToLiveRange(range->TopLevel());
     bool merged = first_op_spill->TryMerge(spill_range);
     CHECK(merged);
-    Spill(range);
+    data()->Spill(range);
     return true;
   } else if (pos->pos().Value() > range->Start().NextStart().Value()) {
     auto spill_range =
         range->TopLevel()->HasSpillRange()
             ? range->TopLevel()->GetSpillRange()
             : data()->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* LinearScanAllocator::SplitRangeAt(LiveRange* range,
-                                             LifetimePosition pos) {
+LiveRange* RegisterAllocationData::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, allocation_zone());
   return result;
 }
 
 
-LiveRange* LinearScanAllocator::SplitBetween(LiveRange* range,
-                                             LifetimePosition start,
-                                             LifetimePosition end) {
+LiveRange* RegisterAllocationData::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 LinearScanAllocator::FindOptimalSplitPos(
+LifetimePosition RegisterAllocationData::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 16 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 LinearScanAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
-  auto second_part = SplitRangeAt(range, pos);
-  Spill(second_part);
+  auto second_part = data()->SplitRangeAt(range, pos);
+  data()->Spill(second_part);
 }
 
 
 void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
                                        LifetimePosition end) {
   SpillBetweenUntil(range, start, start, end);
 }
 
 
 void LinearScanAllocator::SpillBetweenUntil(LiveRange* range,
                                             LifetimePosition start,
                                             LifetimePosition until,
                                             LifetimePosition end) {
   CHECK(start.Value() < end.Value());
-  auto second_part = SplitRangeAt(range, start);
+  auto second_part = data()->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 (data()->IsBlockBoundary(end.Start())) {
       third_part_end = end.Start();
     }
-    auto third_part = SplitBetween(
+    auto third_part = data()->SplitBetween(
         second_part, Max(second_part->Start().End(), until), third_part_end);
 
     DCHECK(third_part != second_part);
 
-    Spill(second_part);
+    data()->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 LinearScanAllocator::Spill(LiveRange* range) {
+void RegisterAllocationData::Spill(LiveRange* range) {
   DCHECK(!range->IsSpilled());
   TRACE("Spilling live range %d\n", range->id());
   auto first = range->TopLevel();
   if (first->HasNoSpillType()) {
-    data()->AssignSpillRangeToLiveRange(first);
+    AssignSpillRangeToLiveRange(first);
   }
   range->MakeSpilled();
 }
 
 
 OperandAssigner::OperandAssigner(RegisterAllocationData* data) : data_(data) {}
 
 
 void OperandAssigner::AssignSpillSlots() {
   auto& spill_ranges = data()->spill_ranges();
@@ skipping 397 matching lines @@
       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);
   }
 }
 
+
+unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) {
+  auto interval = range->first_interval();
+  if (interval == nullptr) return 0;
+
+  unsigned size = 0;
+  while (interval != nullptr) {
+    size += (interval->end().Value() - interval->start().Value());
+    interval = interval->next();
+  }
+
+  DCHECK_NE(0, size);
+  return size;
+}
+
+GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
+                                 RegisterKind kind)
+    : data_(data),
+      mode_(kind),
+      num_registers_(GetRegisterCount(data->config(), kind)),
+      allocations_(data->allocation_zone()),
+      queue_(data->allocation_zone()) {}
+
+
+void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
+  allocations_[reg_id]->Insert(range);
+  if (range->HasRegisterAssigned()) {
+    DCHECK_EQ(reg_id, range->assigned_register());
+    return;
+  }
+  range->set_assigned_register(reg_id);
+}
+
+
+float GreedyAllocator::CalculateSpillWeight(LiveRange* range) {
+  if (range->IsFixed()) return std::numeric_limits<float>::max();
+
+  if (range->FirstHint() != nullptr && range->FirstHint()->IsRegister()) {
+    return std::numeric_limits<float>::max();
+  }
+
+  unsigned use_count = 0;
+  auto* pos = range->first_pos();
+  while (pos != nullptr) {
+    use_count++;
+    pos = pos->next();
+  }
+
+  // GetLiveRangeSize is DCHECK-ed to not be 0

[jvoung (off chromium), 2015/04/21 23:34:06]

GetLiveRangeSize can be 0 if range->first_interval() == nullptr, but maybe it's
not possible at this point.

[Mircea Trofin, 2015/04/22 04:37:33]

Thanks! Moved the check here.

+  return static_cast<float>(use_count) /
+         static_cast<float>(GetLiveRangeSize(range));
+}
+
+
+float GreedyAllocator::CalculateMaxSpillWeight(
+    const ZoneSet<LiveRange*>& ranges) {
+  float max = 0.0;
+  for (auto* r : ranges) {
+    max = std::max(max, CalculateSpillWeight(r));
+  }
+  return max;
+}
+
+
+void GreedyAllocator::Evict(LiveRange* range) {
+  bool removed = allocations_[range->assigned_register()]->Remove(range);
+  DCHECK(removed);
+}
+
+
+bool GreedyAllocator::TryAllocatePhysicalRegister(
+    unsigned reg_id, LiveRange* range, ZoneSet<LiveRange*>* conflicting) {
+  auto* segment = range->first_interval();
+
+  auto* alloc_info = allocations_[reg_id];
+  while (segment != nullptr) {
+    if (auto* existing = alloc_info->Find(segment)) {
+      DCHECK(existing->HasRegisterAssigned());
+      conflicting->insert(existing);
+    }
+    segment = segment->next();
+  }
+  if (!conflicting->empty()) return false;
+  // No conflicts means we can safely allocate this register to this range.
+  AssignRangeToRegister(reg_id, range);
+  return true;
+}
+
+bool GreedyAllocator::TryAllocate(LiveRange* current,
+                                  ZoneSet<LiveRange*>* conflicting) {
+  if (current->HasSpillOperand()) {
+    data()->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;
+}
+
+LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range,
+                                              LifetimePosition start,
+                                              LifetimePosition until,
+                                              LifetimePosition end) {
+  CHECK(start.Value() < end.Value());
+  auto second_part = data()->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 (data()->IsBlockBoundary(end.Start())) {
+      third_part_end = end.Start();
+    }
+    auto third_part = data()->SplitBetween(
+        second_part, Max(second_part->Start().End(), until), third_part_end);
+
+    DCHECK(third_part != second_part);
+
+    data()->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.

[jvoung (off chromium), 2015/04/21 23:34:06]

nit: This comment seems to come from the LinearScan version, but for
GreedyAllocator there isn't an "unhandled"? Can this be phrased differently?

[Mircea Trofin, 2015/04/22 04:37:33]

Most likely this copy of the API will be deleted once we make them stateless.
But your suggestion is correct, we'd need to come up with comments that avoid
algorithm specifics, at this level.

+    return second_part;
+  }
+}
+
+
+void GreedyAllocator::Enqueue(LiveRange* range) {
+  if (range == nullptr || range->IsEmpty()) return;
+  unsigned size = GetLiveRangeSize(range);
+  queue_.push(std::make_pair(size, range));
+}
+
+
+// TODO(mtrofin): consolidate with identical code segment in
+// LinearScanAllocator::AllocateRegisters
+bool GreedyAllocator::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);
+    // 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) {
+      data()->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 GreedyAllocator::AllocateRegisters() {
+  for (auto range : data()->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(num_registers_);
+  auto* zone = data()->allocation_zone();
+  for (int i = 0; i < num_registers_; i++) {
+    allocations_[i] = new (zone) CoallescedLiveRanges(zone);
+  }
+
+  for (auto* current : GetFixedRegisters(data(), mode_)) {
+    if (current != nullptr) {
+      DCHECK_EQ(mode_, current->Kind());
+      int reg_nr = current->assigned_register();
+      bool inserted = allocations_[reg_nr]->Insert(current);
+      CHECK(inserted);
+    }
+  }
+
+  while (!queue_.empty()) {
+    auto current_pair = queue_.top();
+    queue_.pop();
+    auto current = current_pair.second;
+    if (HandleSpillOperands(current)) continue;
+    ZoneSet<LiveRange*> conflicting(zone);
+    if (!TryAllocate(current, &conflicting)) {
+      DCHECK(conflicting.size());

[jvoung (off chromium), 2015/04/21 23:34:06]

Is there an !empty() method to check instead of size()?

[Mircea Trofin, 2015/04/22 04:37:33]

Done.

+      float this_max = CalculateSpillWeight(current);
+      float max_conflicting = CalculateMaxSpillWeight(conflicting);
+      if (max_conflicting < this_max) {
+        for (auto* conflict : conflicting) {
+          Evict(conflict);
+          Enqueue(conflict);
+        }
+        conflicting.clear();
+        bool allocated = TryAllocate(current, &conflicting);
+        CHECK(allocated);
+        DCHECK_EQ(0, conflicting.size());

[jvoung (off chromium), 2015/04/21 23:34:06]

conflicting.empty() ?

[Mircea Trofin, 2015/04/22 04:37:33]

Done.

+      } else {
+        DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
+        bool allocated = AllocateBlockedRange(current, conflicting);
+        CHECK(allocated);
+      }
+    }
+  }
+
+  BitVector* assigned_registers = new (zone) BitVector(num_registers_, zone);
+  for (size_t i = 0; i < allocations_.size(); ++i) {
+    if (!allocations_[i]->IsEmpty()) {
+      assigned_registers->Add(i);
+    }
+  }
+  data()->frame()->SetAllocatedRegisters(assigned_registers);
+}
+
+
+bool GreedyAllocator::AllocateBlockedRange(
+    LiveRange* current, const ZoneSet<LiveRange*>& conflicts) {
+  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.
+    data()->Spill(current);
+    return true;
+  }
+
+  auto second_part = data()->SplitRangeAt(current, register_use->pos());
+  data()->Spill(second_part);
+
+  return true;
+}
+
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8