Greedy allocator: perf work

src/compiler/register-allocator.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 29 matching lines @@
 
 
 const InstructionBlock* GetContainingLoop(const InstructionSequence* sequence,
                                           const InstructionBlock* block) {
   auto index = block->loop_header();
   if (!index.IsValid()) return nullptr;
   return sequence->InstructionBlockAt(index);
 }
 
 
+unsigned GetContainingLoopCount(const InstructionSequence* sequence,
+                                const InstructionBlock* block) {
+  unsigned ret = 0;
+  for (auto cursor = GetContainingLoop(sequence, block); cursor != nullptr;
+       cursor = GetContainingLoop(sequence, cursor)) {
+    ++ret;
+  }
+  return ret;
+}
+
+
 const InstructionBlock* GetInstructionBlock(const InstructionSequence* code,
                                             LifetimePosition pos) {
   return code->GetInstructionBlock(pos.ToInstructionIndex());
 }
 
 
 bool IsBlockBoundary(const InstructionSequence* code, LifetimePosition pos) {
   return pos.IsFullStart() &&
          code->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
              pos.ToInstructionIndex();
@@ skipping 43 matching lines @@
     case kRepFloat32:
     case kRepWord64:
     case kRepFloat64:
       return 8;
     default:
       UNREACHABLE();
       return 0;
   }
 }
 
+
+int GetHintedRegister(LiveRange* range) {
+  int reg;
+  auto hint = range->FirstHintPosition(&reg);
+  if (hint != nullptr) {
+    if (hint->HasOperand()) {
+      if (hint->operand()->IsDoubleStackSlot() ||
+          hint->operand()->IsStackSlot()) {
+        return -1;
+      }
+    }
+    return reg;
+  }
+  return -1;
+}
+
 }  // namespace
 
 
 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
                          void* hint, UsePositionHintType hint_type)
     : operand_(operand), hint_(hint), next_(nullptr), pos_(pos), flags_(0) {
   DCHECK_IMPLIES(hint == nullptr, hint_type == UsePositionHintType::kNone);
   bool register_beneficial = true;
   UsePositionType type = UsePositionType::kAny;
   if (operand_ != nullptr && operand_->IsUnallocated()) {
@@ skipping 13 matching lines @@
   DCHECK(pos_.IsValid());
 }
 
 
 bool UsePosition::HasHint() const {
   int hint_register;
   return HintRegister(&hint_register);
 }
 
 
+void UsePosition::dump_hint(std::ostream& os,
+                            const RegisterConfiguration* config) {
+  if (hint_ == nullptr) {
+    os << "H:nil";
+    return;
+  }
+  switch (HintTypeField::decode(flags_)) {
+    case UsePositionHintType::kNone:
+      os << "H:N";
+      return;
+    case UsePositionHintType::kUnresolved:
+      os << "H:U";
+      return;
+    case UsePositionHintType::kUsePos: {
+      auto use_pos = reinterpret_cast<UsePosition*>(hint_);
+      int assigned_register = AssignedRegisterField::decode(use_pos->flags_);
+      if (assigned_register == kUnassignedRegister) {
+        os << "H:Use(R ?";
+      } else {
+        os << "H:Use(R " << assigned_register;
+      }
+      if (use_pos->HasOperand()) {
+        PrintableInstructionOperand pio{config, *use_pos->operand()};
+        os << " | " << pio;
+      }
+      os << ")";
+      return;
+    }
+    case UsePositionHintType::kOperand: {
+      auto operand = reinterpret_cast<InstructionOperand*>(hint_);
+      int assigned_register = AllocatedOperand::cast(operand)->index();
+      PrintableInstructionOperand pio{config, *operand};
+      os << "H:Op(R" << assigned_register << " | " << pio << ")";
+      return;
+    }
+    case UsePositionHintType::kPhi: {
+      auto phi = reinterpret_cast<RegisterAllocationData::PhiMapValue*>(hint_);
+      int assigned_register = phi->assigned_register();
+      PrintableInstructionOperand pio{config, phi->phi()->output()};
+      if (assigned_register == kUnassignedRegister) {
+        os << "H:Phi(R x";
+
+      } else {
+        os << "H:Phi(R" << assigned_register;
+      }
+      os << " | " << pio;
+      os << ")";
+      return;
+    }
+  }
+  UNREACHABLE();
+}
+
+
 bool UsePosition::HintRegister(int* register_index) const {
   if (hint_ == nullptr) return false;
   switch (HintTypeField::decode(flags_)) {
     case UsePositionHintType::kNone:
     case UsePositionHintType::kUnresolved:
       return false;
     case UsePositionHintType::kUsePos: {
       auto use_pos = reinterpret_cast<UsePosition*>(hint_);
       int assigned_register = AssignedRegisterField::decode(use_pos->flags_);
       if (assigned_register == kUnassignedRegister) return false;
@@ skipping 101 matching lines @@
       bits_(0),
       last_interval_(nullptr),
       first_interval_(nullptr),
       first_pos_(nullptr),
       parent_(nullptr),
       next_(nullptr),
       spill_operand_(nullptr),
       spills_at_definition_(nullptr),
       current_interval_(nullptr),
       last_processed_use_(nullptr),
-      current_hint_position_(nullptr) {
+      current_hint_position_(nullptr),
+      group_(nullptr) {
   DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
   bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
           AssignedRegisterField::encode(kUnassignedRegister) |
           MachineTypeField::encode(machine_type);
+  InvalidateWeightAndSize();
 }
 
 
 void LiveRange::Verify() const {
   // Walk the positions, verifying that each is in an interval.
   auto interval = first_interval_;
   for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
     CHECK(Start() <= pos->pos());
     CHECK(pos->pos() <= End());
     CHECK(interval != nullptr);
@@ skipping 135 matching lines @@
 
 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
   UsePosition* pos = NextUsePosition(start);
   while (pos != nullptr && pos->type() != UsePositionType::kRequiresRegister) {
     pos = pos->next();
   }
   return pos;
 }
 
 
-bool LiveRange::CanBeSpilled(LifetimePosition pos) const {
-  // We cannot spill a live range that has a use requiring a register
-  // at the current or the immediate next position.
+bool LiveRange::CanBeSplit(LifetimePosition pos) const {
+  // We cannot split a live range that has a use requiring a register
+  // at the current or the immediate next position, because there would be
+  // no gap where to insert a parallel move.
   auto use_pos = NextRegisterPosition(pos);
   if (use_pos == nullptr) return true;
   return use_pos->pos() > pos.NextStart().End();
 }
 
 
 InstructionOperand LiveRange::GetAssignedOperand() const {
   if (HasRegisterAssigned()) {
     DCHECK(!spilled());
     switch (kind()) {
@@ skipping 125 matching lines @@
   // Discard cached iteration state. It might be pointing
   // to the use that no longer belongs to this live range.
   last_processed_use_ = nullptr;
   current_interval_ = nullptr;
 
   // Link the new live range in the chain before any of the other
   // ranges linked from the range before the split.
   result->parent_ = (parent_ == nullptr) ? this : parent_;
   result->next_ = next_;
   next_ = result;
+  InvalidateWeightAndSize();
 
 #ifdef DEBUG
   Verify();
   result->Verify();
 #endif
 }
 
 
 // This implements an ordering on live ranges so that they are ordered by their
 // start positions.  This is needed for the correctness of the register
@@ skipping 171 matching lines @@
       if (a == nullptr || a->start() > other->End()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
+LifetimePosition LiveRange::GetFirstSplittablePosition() {
+  for (auto c = first_pos(); c != nullptr; c = c->next()) {
+    LifetimePosition pos;
+    if (CanBeSpilled(c->pos())) {
+      pos = c->pos();
+    } else {
+      auto after = c->pos().NextStart();
+      if (Covers(after) && CanBeSpilled(after)) {
+        pos = after;
+      }
+    }
+    if (pos.IsValid() && Start() < pos && pos < End()) {
+      return pos;
+    }
+  }
+  return LifetimePosition::Invalid();
+}
+
+
+void LiveRange::RecalculateSize() {
+  size_ = 0;
+  for (auto cursor = first_interval(); cursor != nullptr;
+       cursor = cursor->next()) {
+    size_ += cursor->end().value() - cursor->start().value();
+  }
+
+  DCHECK_NE(0U, static_cast<unsigned>(size_));
+}
+
+
+const float LiveRange::kMaxWeight = FLT_MAX;
+const float LiveRange::kUseInLoopWeightMultiplier = 10.0f;
+const float LiveRange::kPreferredRegisterWeightMultiplier = 10.0f;
+const float LiveRange::kInvalidWeight = -1.0f;
+
+
+void LiveRange::RecalculateWeight(InstructionSequence* code) {
+  auto start = Start();
+
+  CHECK(!spilled());
+
+  if (IsFixed()) {
+    weight_ = kMaxWeight;
+    return;
+  }
+
+  if (first_interval()->next() == nullptr) {
+    bool can_be_split_or_spilled =
+        CanBeSpilled(start) || GetFirstSplittablePosition().IsValid();
+    if (!can_be_split_or_spilled) {
+      weight_ = kMaxWeight;
+      return;
+    }
+  }
+
+  float use_count = 0.0;
+  auto* pos = first_pos();
+
+  for (; pos != nullptr; pos = pos->next()) {
+    auto loop_count = GetContainingLoopCount(
+        code, code->GetInstructionBlock(pos->pos().ToInstructionIndex()));
+    use_count +=
+        std::pow(kUseInLoopWeightMultiplier, static_cast<float>(loop_count));
+  }
+
+
+  if (GetHintedRegister(this) >= 0 &&
+      GetHintedRegister(this) == assigned_register()) {
+    use_count *= kPreferredRegisterWeightMultiplier;
+  }
+
+  weight_ = use_count / static_cast<float>(size());
+}
+
+
 static bool AreUseIntervalsIntersecting(UseInterval* interval1,
                                         UseInterval* interval2) {
   while (interval1 != nullptr && interval2 != nullptr) {
     if (interval1->start() < interval2->start()) {
       if (interval1->end() > interval2->start()) {
         return true;
       }
       interval1 = interval1->next();
     } else {
       if (interval2->end() > interval1->start()) {
         return true;
       }
       interval2 = interval2->next();
     }
   }
   return false;
 }
 
 
-std::ostream& operator<<(std::ostream& os,
-                         const PrintableLiveRange& printable_range) {
-  const LiveRange* range = printable_range.range_;
-  os << "Range: " << range->id() << " ";
-  if (range->is_phi()) os << "phi ";
-  if (range->is_non_loop_phi()) os << "nlphi ";
-
-  os << "{" << std::endl;
-  auto interval = range->first_interval();
-  auto use_pos = range->first_pos();
-  PrintableInstructionOperand pio;
-  pio.register_configuration_ = printable_range.register_configuration_;
-  while (use_pos != nullptr) {
-    pio.op_ = *use_pos->operand();
-    os << pio << use_pos->pos() << " ";
-    use_pos = use_pos->next();
-  }
-  os << std::endl;
-
+void PrintIntervals(std::ostream& os, UseInterval* interval) {
   while (interval != nullptr) {
     os << '[' << interval->start() << ", " << interval->end() << ')'
        << std::endl;
     interval = interval->next();
   }
+}
+
+std::ostream& operator<<(std::ostream& os,
+                         const PrintableLiveRange& printable_range) {
+  PrintableInstructionOperand pio;
+  pio.register_configuration_ = printable_range.register_configuration_;
+
+  const LiveRange* range = printable_range.range_;
+  os << "Range: " << range->id() << " ";
+  if (range->is_phi()) os << "phi ";
+  if (range->is_non_loop_phi()) os << "nlphi ";
+  if (range->HasRegisterAssigned())
+    os << "R: " << range->assigned_register() << " ";
+
+  if (range->HasSpillOperand()) {
+    pio.op_ = *(range->GetSpillOperand());
+    os << "SOp: " << pio << " ";
+  }
+  if (range->HasSpillRange()) {
+    os << "SR: ";
+    if (range->GetSpillRange()->IsSlotAssigned()) {
+      os << range->GetSpillRange()->assigned_slot() << " ";
+    } else {
+      os << "x ";
+    }
+  }
+  os << "{" << std::endl;
+  auto interval = range->first_interval();
+  auto use_pos = range->first_pos();
+  while (use_pos != nullptr) {
+    os << "[";
+    if (use_pos->HasOperand()) {
+      pio.op_ = *use_pos->operand();
+      os << pio << use_pos->pos() << " ";
+    } else {
+      os << "<no_op> ";
+    }
+    use_pos->dump_hint(os, printable_range.register_configuration_);
+    os << "] ";
+    use_pos = use_pos->next();
+  }
+  os << std::endl;
+
+  PrintIntervals(os, interval);
   os << "}";
   return os;
 }
 
 
+std::ostream& operator<<(std::ostream& os, SpillRange* range) {
+  if (range->IsSlotAssigned()) {
+    os << "Slot: " << range->assigned_slot();
+  } else {
+    os << "Unassigned Slot.";
+  }
+  os << std::endl;
+  os << "{";
+  PrintIntervals(os, range->interval());
+  os << "}" << std::endl;
+  return os;
+}
+
+
 SpillRange::SpillRange(LiveRange* parent, Zone* zone)
     : live_ranges_(zone), assigned_slot_(kUnassignedSlot) {
   DCHECK(!parent->IsChild());
   UseInterval* result = nullptr;
   UseInterval* node = nullptr;
   // Copy the intervals for all ranges.
   for (auto range = parent; range != nullptr; range = range->next()) {
     auto src = range->first_interval();
     while (src != nullptr) {
       auto new_node = new (zone) UseInterval(src->start(), src->end());
@@ skipping 182 matching lines @@
   }
   auto child = new (allocation_zone()) LiveRange(vreg, range->machine_type());
   DCHECK_NULL(live_ranges()[vreg]);
   live_ranges()[vreg] = child;
   return child;
 }
 
 
 RegisterAllocationData::PhiMapValue* RegisterAllocationData::InitializePhiMap(
     const InstructionBlock* block, PhiInstruction* phi) {
-  auto map_value = new (allocation_zone())
-      RegisterAllocationData::PhiMapValue(phi, block, allocation_zone());
+  auto map_value =
+      new (allocation_zone()) PhiMapValue(phi, block, allocation_zone());
   auto res =
       phi_map_.insert(std::make_pair(phi->virtual_register(), map_value));
   DCHECK(res.second);
   USE(res);
   return map_value;
 }
 
 
 RegisterAllocationData::PhiMapValue* RegisterAllocationData::GetPhiMapValueFor(
     int virtual_register) {
@@ skipping 809 matching lines @@
     // Try hoisting out to an outer loop.
     loop_header = GetContainingLoop(code(), loop_header);
   }
 
   return pos;
 }
 
 
 void RegisterAllocator::Spill(LiveRange* range) {
   DCHECK(!range->spilled());
+  stats_.spills++;
+
   TRACE("Spilling live range %d\n", range->id());
   auto first = range->TopLevel();
   if (first->HasNoSpillType()) {
     data()->AssignSpillRangeToLiveRange(first);
   }
   range->Spill();
 }
 
 
 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
                                          RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       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 >=
          this->data()->config()->num_general_registers());
 }
 
 
 void LinearScanAllocator::AllocateRegisters() {
+  stats_.reset();
   DCHECK(unhandled_live_ranges().empty());
   DCHECK(active_live_ranges().empty());
   DCHECK(inactive_live_ranges().empty());
-
+  TRACE("Begin allocating function %s with the Linear Allocator\n",
+        data()->debug_name());
   for (auto range : data()->live_ranges()) {
     if (range == nullptr) continue;
     if (range->kind() == mode()) {
       AddToUnhandledUnsorted(range);
     }
   }
   SortUnhandled();
   DCHECK(UnhandledIsSorted());
 
   auto& fixed_ranges = GetFixedRegisters(data(), mode());
@@ skipping 56 matching lines @@
         --i;  // Live range was removed from the list of inactive live ranges.
       } else if (cur_inactive->Covers(position)) {
         InactiveToActive(cur_inactive);
         --i;  // Live range was removed from the list of inactive live ranges.
       }
     }
 
     DCHECK(!current->HasRegisterAssigned() && !current->spilled());
 
     bool result = TryAllocateFreeReg(current);
-    if (!result) AllocateBlockedReg(current);
+    if (!result) {
+      TRACE("Failed to allocate a free reg for %d\n", current->id());
+      AllocateBlockedReg(current);
+    }
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
+    } else {
+      TRACE("Failed to assign register to %d\n", current->id());
     }
   }
+  TRACE("End allocating function %s with the Linear Allocator\n",
+        data()->debug_name());
 }
 
 
-const char* LinearScanAllocator::RegisterName(int allocation_index) const {
+const char* RegisterAllocator::RegisterName(int allocation_index) const {
   if (mode() == GENERAL_REGISTERS) {
     return data()->config()->general_register_name(allocation_index);
   } else {
     return data()->config()->double_register_name(allocation_index);
   }
 }
 
 
 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
                                                        int reg) {
@@ skipping 115 matching lines @@
 
   for (auto cur_inactive : inactive_live_ranges()) {
     DCHECK(cur_inactive->End() > current->Start());
     auto next_intersection = cur_inactive->FirstIntersection(current);
     if (!next_intersection.IsValid()) continue;
     int cur_reg = cur_inactive->assigned_register();
     free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
   }
 
   int hint_register;
-  if (current->FirstHintPosition(&hint_register) != nullptr) {
+  UsePosition* hint = current->FirstHintPosition(&hint_register);
+  if (hint != nullptr) {
     TRACE("Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
           RegisterName(hint_register), free_until_pos[hint_register].value(),
           current->id(), current->End().value());
 
     // The desired register is free until the end of the current live range.
     if (free_until_pos[hint_register] >= current->End()) {
       TRACE("Assigning preferred reg %s to live range %d\n",
             RegisterName(hint_register), current->id());
       SetLiveRangeAssignedRegister(current, hint_register);
       return true;
@@ skipping 11 matching lines @@
   auto pos = free_until_pos[reg];
 
   if (pos <= current->Start()) {
     // All registers are blocked.
     return false;
   }
 
   if (pos < current->End()) {
     // Register reg is available at the range start but becomes blocked before
     // the range end. Split current at position where it becomes blocked.
+    TRACE(
+        "Register %d is available at the range start but becomes blocked "
+        "before range %d end\n",
+        reg, current->id());
     auto tail = SplitRangeAt(current, pos);
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is available at the range start and is free until
   // the range end.
   DCHECK(pos >= current->End());
   TRACE("Assigning free reg %s to live range %d\n", RegisterName(reg),
         current->id());
   SetLiveRangeAssignedRegister(current, reg);
@@ skipping 52 matching lines @@
     if (use_pos[i] > use_pos[reg]) {
       reg = i;
     }
   }
 
   auto pos = use_pos[reg];
 
   if (pos < register_use->pos()) {
     // All registers are blocked before the first use that requires a register.
     // Spill starting part of live range up to that use.
+    TRACE("All registers are blocked before the first use for %d\n",
+          current->id());
     SpillBetween(current, current->Start(), register_use->pos());
     return;
   }
 
   if (block_pos[reg] < current->End()) {
     // Register becomes blocked before the current range end. Split before that
     // position.
+    TRACE("Register %d becomes blocked before end of range %d\n", reg,
+          current->id());
     LiveRange* tail =
         SplitBetween(current, current->Start(), block_pos[reg].Start());
     AddToUnhandledSorted(tail);
   }
 
   // Register reg is not blocked for the whole range.
   DCHECK(block_pos[reg] >= current->End());
   TRACE("Assigning blocked reg %s to live range %d\n", RegisterName(reg),
         current->id());
   SetLiveRangeAssignedRegister(current, reg);
 
   // This register was not free. Thus we need to find and spill
   // parts of active and inactive live regions that use the same register
   // at the same lifetime positions as current.
   SplitAndSpillIntersecting(current);
 }
 
 
 void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   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) {
+        TRACE("SplitAndSpillIntersecting (1). Range %d, for %d\n", range->id(),
+              current->id());
         SpillAfter(range, spill_pos);
       } else {
         // When spilling between spill_pos and next_pos ensure that the range
         // remains spilled at least until the start of the current live range.
         // This guarantees that we will not introduce new unhandled ranges that
         // start before the current range as this violates allocation invariant
         // and will lead to an inconsistent state of active and inactive
         // live-ranges: ranges are allocated in order of their start positions,
         // ranges are retired from active/inactive when the start of the
         // current live-range is larger than their end.
+        TRACE("SplitAndSpillIntersecting (2). Range %d, for %d\n", range->id(),
+              current->id());
         SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
       }
       ActiveToHandled(range);
       --i;
     }
   }
 
   for (size_t i = 0; i < inactive_live_ranges().size(); ++i) {
     auto range = inactive_live_ranges()[i];
     DCHECK(range->End() > current->Start());
     if (range->assigned_register() == reg && !range->IsFixed()) {
       LifetimePosition next_intersection = range->FirstIntersection(current);
       if (next_intersection.IsValid()) {
         UsePosition* next_pos = range->NextRegisterPosition(current->Start());
         if (next_pos == nullptr) {
+          TRACE("SplitAndSpillIntersecting (3). Range %d, for %d\n",
+                range->id(), current->id());
           SpillAfter(range, split_pos);
         } else {
           next_intersection = Min(next_intersection, next_pos->pos());
+          TRACE("SplitAndSpillIntersecting (4). Range %d, for %d\n",
+                range->id(), current->id());
           SpillBetween(range, split_pos, next_intersection);
         }
         InactiveToHandled(range);
         --i;
       }
     }
   }
 }
 
 
@@ skipping 116 matching lines @@
     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);
   }
 }
 
 
+conflict_iterator& conflict_iterator::operator++() {
+  if (pos_ == storage_->end()) {

[Jarin, 2015/06/09 15:00:41]

Overall, this gymnastics of MoveToEnd seem to be quite messy. Why could not you
always insist that storage_ is not null, and consider the iterator finished if
pos_ == storage_->end(). (Moreover, the invariant should be that the current
allocation interval is overlapping with the current use interval or the
allocation interval is storage_->end() and query_ is null; this would mean that
pos_ is at end iff query is null).

In this particular case, the caller should make sure that the iterator is not
finished yet, so perhaps we could just DCHECK here.

At a higher level, this whole class is quite complex for what it does. 

E.g., its is not clear to me what is the invariant for entering the ++ operator.
The last loop of InitializeForNewQuery suggests that the query should be the
last use interval that overlaps with pos(?). Indeed if it was not then the
InitializeForNewQuery method could set the same pos as the current pos, so the
iterator would return the same allocation interval twice. However, neither the
++ operator nor the InitializeForNewQuery seem to maintain this invariant:
- when the ++ operator advances pos and it still intersects, it does not try to
move the query as far as possible.
- when InitializeForNewQuery's lower_bound lookup succeeds with the same start
(line 2699), it also does not try to advance the query.

Am I missing something?

[Mircea Trofin, 2015/06/10 05:37:10]

I'll take the suggestion with storage_, some complexity here is likely due to an
earlier design that I canned since, where "end()" was singular. I think what
you're suggesting will simplify things.

For the invariants question. When we enter ++, we know query_ is the last
"query" use interval to overlap with pos. It could be that this query overlaps
with the next allocated interval, ++pos. So we don't move query just yet.

I think you're correct about the second point, that's a bug.

+    MoveToEnd();
+    return *this;
+  }
+  ++pos_;
+  if (pos_ == storage_->end()) {
+    MoveToEnd();
+    return *this;
+  }
+  if (!Intersects(query_->start(), query_->end(), pos_->start, pos_->end)) {
+    query_ = query_->next();
+    if (query_ == nullptr) {
+      MoveToEnd();
+      return *this;
+    }
+    // We may discover it is better to linearly skip over non-conflicting
+    // use intervals rather than re-do the seeking in InitializeForNewQuery.
+    // No profiling data yet on this one.
+    InitializeForNewQuery();
+  }
+  return *this;
+}
+
+
+bool operator==(const conflict_iterator& first,
+                const conflict_iterator& second) {
+  bool same_storage_and_query =
+      first.storage_ == second.storage_ && first.query_ == second.query_;

[Jarin, 2015/06/09 15:00:41]

Does it even make sense to compare iterators with different storage? Could not
you just DCHECK that the storage is the same.

[Mircea Trofin, 2015/06/10 05:37:10]

That makes sense, thanks!

+  if (same_storage_and_query && first.IsValid())
+    return first.pos_ == second.pos_;
+  return same_storage_and_query;
+}
+
+
+bool operator!=(const conflict_iterator& first,
+                const conflict_iterator& second) {
+  return !(first == second);
+}
+
+
+void conflict_iterator::InitializeForNewQuery() {
+  if (storage_->empty()) {
+    MoveToEnd();
+    return;
+  }
+
+  // If the last element starts before the query, we have no conflicts.
+  if (storage_->rbegin()->end <= query_->start()) {
+    MoveToEnd();
+    return;
+  }
+
+  for (; query_ != nullptr; query_ = query_->next()) {
+    auto q_start = query_->start();
+    auto q_end = query_->end();
+    if (storage_->begin()->start >= q_end) {
+      // Skip over queried use intervals that end before the first stored
+      // element.
+      continue;
+    }
+
+    // Seek the first stored element that contains q_start. We do so by first
+    // finding the last stored interval that starts before q_start. Either there
+    // is a stored interval that starts at or after, meaning the one before is
+    // "it", or we position at the end of storage. We then check that the thus
+    // found stored interval actually intersects (or overlaps) with the current
+    // query.
+    pos_ = storage_->lower_bound(AsAllocatedInterval(q_start));

[Jarin, 2015/06/09 15:00:42]

Would not the upper_bound be easier to handle here? Then you can just MoveToEnd
and return if pos_ is at the beginning, or take --pos_ otherwise.

[Mircea Trofin, 2015/06/10 05:37:11]

upper_bound would never return a pos_ starting at q_start, if I understand your
suggestion correctly, but regardless, your suggestion led me to something
cleaner than the unhappy mess before. Thanks!

[Jarin, 2015/06/12 04:09:10]

Actually, you did what I had in mind (and fixed the gaps in my thinking).

+    if (pos_ != storage_->end()) {
+      if (pos_->start == q_start) return;
+      if (pos_->start > q_start && pos_ != storage_->begin()) {
+        // If pos_ starts after the query, then --pos_ starts strictly before.
+        // See if that position still includes q_start
+        --pos_;
+        if (pos_->end <= q_start) {
+          ++pos_;
+        }
+      }
+    } else if (pos_ != storage_->begin()) {
+      // No stored interval starts at or after q_start. So maybe the last one
+      // ends after q_start. Position at the last valid element.
+      --pos_;
+    }
+    if (!Intersects(q_start, q_end, pos_->start, pos_->end)) {
+      continue;
+    }
+    break;

[Jarin, 2015/06/09 15:00:42]

Why can't you just say "if (Intersects(...)) break;"?

[Mircea Trofin, 2015/06/10 05:37:10]

No reason - good catch.

+  }
+
+  // If we got here because we couldn't find an intersection and got to the last
+  // use interval query, we have no conflicts.
+  if (query_ == nullptr) {
+    MoveToEnd();
+    return;
+  }
+
+  // If we found a conflict, advance query_ past the last use interval that
+  // still intersects/overlaps with the current conflict, so that operator++ can
+  // pick up from there.
+  for (; query_->next() != nullptr; query_ = query_->next()) {
+    if (!Intersects(query_->next()->start(), query_->next()->end(), pos_->start,
+                    pos_->end)) {
+      break;
+    }
+  }
+}
+
+
+// Collection of live ranges allocated to the same register.
+// It supports efficiently finding all conflicts for a given, non-allocated
+// range. See AllocatedInterval.
+// Allocated live ranges do not intersect. At most, individual use intervals
+// touch. We store, for a live range, an AllocatedInterval corresponding to each
+// of that range's UseIntervals. We keep the list of AllocatedIntervals sorted
+// by starts. Then, given the non-intersecting property, we know that
+// consecutive AllocatedIntervals have the property that the "smaller"'s end is
+// less or equal to the "larger"'s start.
+// This allows for quick (logarithmic complexity) identification of the first
+// AllocatedInterval to conflict with a given LiveRange, and then for efficient
+// traversal of conflicts. See also conflict_iterator.
 class CoalescedLiveRanges : public ZoneObject {
  public:
   explicit CoalescedLiveRanges(Zone* zone) : storage_(zone) {}
 
-  LiveRange* Find(UseInterval* query) {
-    ZoneSplayTree<Config>::Locator locator;
+  void clear() { storage_.clear(); }
 
-    if (storage_.Find(GetKey(query), &locator)) {
-      return locator.value();
-    }
-    return nullptr;
+
+  conflict_iterator first_conflict(LiveRange* query) {
+    return first_conflict(query->first_interval());
   }
 
-  // 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();
+  conflict_iterator conflict_end() { return {}; }
+
+  // We assume it was determined that this range does not conflict with
+  // contained ranges.
+  void insert(LiveRange* range) {

[Jarin, 2015/06/09 15:00:42]

Style nit: why did you change the name to lower case? Only trivial getters
should have lower case names.

[Mircea Trofin, 2015/06/10 05:37:10]

to emulate the collections' casing - but happy to go either way.

+    for (auto interval = range->first_interval(); interval != nullptr;
+         interval = interval->next()) {
+      storage_.insert({interval->start(), interval->end(), range});
+    }
+  }
+
+  void remove(LiveRange* range) {
+    for (auto interval = range->first_interval(); interval != nullptr;
+         interval = interval->next()) {
+      storage_.erase({interval->start(), interval->end(), range});
+    }
+  }
+
+  bool empty() const { return storage_.empty(); }
+
+  bool IsValid() {
+    LifetimePosition last_end = LifetimePosition::GapFromInstructionIndex(0);
+    for (auto i : storage_) {
+      if (i.start < last_end) {
+        return false;
+      }
+      last_end = i.end;
     }
     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;
+ private:
+  conflict_iterator first_conflict(UseInterval* query) {
+    return conflict_iterator(query, &storage_);
   }
 
-  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_;
+  ZoneSet<AllocatedInterval, AllocatedInterval::Comparer> storage_;
   DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);
 };
 
 
-const std::pair<int, int> CoalescedLiveRanges::Config::kNoKey = {0, 0};
+std::ostream& operator<<(std::ostream& os, const AllocatorStats& stats) {
+  os << "losses after eviction: " << stats.losses_after_eviction << std::endl;
+  os << "losses, no eviction:   " << stats.losses_no_eviction << std::endl;
+  os << "spills:                " << stats.spills << std::endl;
+  os << "wins:                  " << stats.wins << std::endl;
+  os << "split attempts:        " << stats.good_split_attempts << std::endl;
+  os << "split successes:       " << stats.good_split_successes << std::endl;
+  os << "splits above:          " << stats.good_split_above << std::endl;
+  os << "splits below:          " << stats.good_split_below << std::endl;
+  os << "smart splits above:    " << stats.good_split_smart_above << std::endl;
+  os << "smart splits below:    " << stats.good_split_smart_below << std::endl;
+  os << "groups allocated:      " << stats.groups_allocated << std::endl;
+  os << "groups attempted:      " << stats.groups_attempted << std::endl;
+  os << "groups succeeded:      " << stats.groups_succeeded << std::endl;
+  return os;
+}
+
 
 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
       local_zone_(local_zone),
       allocations_(local_zone),
       queue_(local_zone) {}
 
 
-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();
-  }
-
-  return size;
-}
-
 
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
-  allocations_[reg_id]->Insert(range);
+  allocations_[reg_id]->insert(range);
   if (range->HasRegisterAssigned()) {
     DCHECK_EQ(reg_id, range->assigned_register());
     return;
   }
+  TRACE("Assigning %s to range %d\n", RegisterName(reg_id), range->id());
   range->set_assigned_register(reg_id);
   range->SetUseHints(reg_id);
   if (range->is_phi()) {
     data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg_id);
   }
-}
-
-
-float GreedyAllocator::CalculateSpillWeight(LiveRange* range) {
-  InstructionOperand* first_hint = nullptr;
-  if (range->FirstHintPosition() != nullptr) {
-    first_hint = range->FirstHintPosition()->operand();
-  }
-
-  if (range->IsFixed()) return std::numeric_limits<float>::max();
-  bool spill;
-  if (!FindProgressingSplitPosition(range, &spill).IsValid())
-    return std::numeric_limits<float>::max();
-
-  float multiplier = 1.0;
-  if (first_hint != nullptr && first_hint->IsRegister()) {
-    multiplier = 3.0;
-  }
-
-  unsigned use_count = 0;
-  auto* pos = range->first_pos();
-  while (pos != nullptr) {
-    use_count++;
-    pos = pos->next();
-  }
-
-  unsigned range_size = GetLiveRangeSize(range);
-  DCHECK_NE(0U, range_size);
-
-  return multiplier * static_cast<float>(use_count) /
-         static_cast<float>(range_size);
-}
-
-
-float GreedyAllocator::CalculateMaxSpillWeight(
-    const ZoneSet<LiveRange*>& ranges) {
-  float max = 0.0;
-  for (auto* r : ranges) {
-    max = std::max(max, CalculateSpillWeight(r));
-  }
-  return max;
+  range->RecalculateWeight(code());
+  DCHECK(allocations_[reg_id]->IsValid());
 }
 
 
 void GreedyAllocator::Evict(LiveRange* range) {
-  bool removed = allocations_[range->assigned_register()]->Remove(range);
-  CHECK(removed);
+  TRACE("Evicting range %d from register %s\n", range->id(),
+        RegisterName(range->assigned_register()));
   range->UnsetUseHints();
   range->UnsetAssignedRegister();
   if (range->is_phi()) {
     data()->GetPhiMapValueFor(range->id())->UnsetAssignedRegister();
   }
 }
 
 
-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;
-}
-
-
-int GreedyAllocator::GetHintedRegister(LiveRange* range) {
-  int reg;
-  if (range->FirstHintPosition(&reg) != nullptr) {
-    return reg;
-  }
-  return -1;
-}
-
-
-bool GreedyAllocator::TryAllocate(LiveRange* current,
-                                  ZoneSet<LiveRange*>* conflicting) {
-  if (current->IsFixed()) {
-    return TryAllocatePhysicalRegister(current->assigned_register(), current,
-                                       conflicting);
-  }
-
-  int hinted_reg_id = GetHintedRegister(current);
-  if (hinted_reg_id >= 0) {
-    if (TryAllocatePhysicalRegister(hinted_reg_id, current, conflicting)) {
-      return true;
-    }
-  }
-
-  ZoneSet<LiveRange*> local_conflicts(local_zone());
-  for (unsigned candidate_reg = 0; candidate_reg < allocations_.size();
-       candidate_reg++) {
-    if (hinted_reg_id >= 0 &&
-        candidate_reg == static_cast<size_t>(hinted_reg_id))
-      continue;
-    local_conflicts.clear();
-    if (TryAllocatePhysicalRegister(candidate_reg, current, &local_conflicts)) {
-      conflicting->clear();
-      return true;
-    } else {
-      conflicting->insert(local_conflicts.begin(), local_conflicts.end());
-    }
-  }
-  return false;
-}
-
-
 LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range,
                                               LifetimePosition start,
                                               LifetimePosition until,
                                               LifetimePosition end) {
   CHECK(start < end);
   auto second_part = SplitRangeAt(range, start);
 
   if (second_part->Start() < end) {
     // The split result intersects with [start, end[.
     // Split it at position between ]start+1, end[, spill the middle part
@@ skipping 11 matching lines @@
     return third_part;
   } else {
     // The split result does not intersect with [start, end[.
     // Nothing to spill. Just return it for re-processing.
     return second_part;
   }
 }
 
 
 void GreedyAllocator::Enqueue(LiveRange* range) {
-  if (range == nullptr || range->IsEmpty()) return;
-  unsigned size = GetLiveRangeSize(range);
-  TRACE("Enqueuing range %d\n", range->id());
-  queue_.push(std::make_pair(size, range));
+  unsigned size = range->size();
+  range->RecalculateWeight(code());
+  TRACE("Enqueuing range %d size %d\n", range->id(), size);
+  DCHECK(size > 0);
+  queue_.push({size, PQueueElem(range)});
 }
 
 
-bool GreedyAllocator::HandleSpillOperands(LiveRange* range) {
+// We treat groups of ranges as one, so that we try first to allocate
+// them all to the same register. If that fails, they get processed as
+// individual ranges.
+void GreedyAllocator::Enqueue(LiveRangeGroup* group) {
+  unsigned size = 0;
+  for (auto r : group->ranges()) {
+    size += r->size();
+    r->RecalculateWeight(code());
+  }
+
+  DCHECK(size > 0);
+  TRACE("Enqueuing group of size %d\n", size);
+  queue_.push({size, PQueueElem(group)});
+}
+
+
+bool GreedyAllocator::HandleSpillOperands(LiveRange* range,
+                                          LiveRange** remaining) {
   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) {
       Spill(range);
       return true;
     } else if (pos->pos() > range->Start().NextStart()) {
       // Do not spill live range eagerly if use position that can benefit from
       // the register is too close to the start of live range.
-      auto* reminder = SpillBetweenUntil(range, position, position, pos->pos());
-      Enqueue(reminder);
+      *remaining = SpillBetweenUntil(range, position, position, pos->pos());
       return true;
     }
   }
-  return TryReuseSpillForPhi(range);
+  return false;
+}
+
+
+// TODO(mtrofin): consider using CoalescedLiveRanges for grouping.
+bool CanAddToGroup(LiveRange* r, LiveRangeGroup* grp) {

[Jarin, 2015/06/09 15:00:42]

Style nit: move to an anonymous name space (or make this a method of
LiveRangeGroup, where this seems to belong).

[Mircea Trofin, 2015/06/10 05:37:11]

Done.

+  bool ret = true;
+  for (auto member : grp->ranges()) {
+    if (member->FirstIntersection(r).IsValid()) {
+      ret = false;

[Jarin, 2015/06/09 15:00:41]

How about "return false" here and get rid of the "ret" variable?

[Mircea Trofin, 2015/06/10 05:37:10]

Done.

+      break;
+    }
+  }
+  return ret;
+}
+
+
+void TryMergeGroups(LiveRange* r1, LiveRange* r2) {

[Jarin, 2015/06/09 15:00:41]

It is a bit funny that its name is TryMergeGroups but it takes live ranges.
Could not it take groups instead?

[Mircea Trofin, 2015/06/10 05:37:10]

Done.

+  DCHECK(r1->group() != nullptr);
+  DCHECK(r2->group() != nullptr);
+
+  bool can_merge = true;
+  for (auto r : r1->group()->ranges()) {
+    if (!CanAddToGroup(r, r2->group())) {
+      can_merge = false;
+      break;
+    }
+  }
+  if (can_merge) {
+    for (auto r : r1->group()->ranges()) {
+      r2->group()->ranges().insert(r);
+      r->SetGroup(r2->group());
+    }
+    r1->SetGroup(r2->group());

[Jarin, 2015/06/09 15:00:42]

Is this necessary? r1 should be part of r1->group()->ranges(), so it should be
set by the SetGroup call above. Perhaps DCHECK(r1->group() == r2->group()) would
be enough?

[Mircea Trofin, 2015/06/10 05:37:11]

Done.

+  }
+}
+
+
+void TryGroup(LiveRange* r1, LiveRange* r2, Zone* local_zone) {
+  if (r1->group() == nullptr) {
+    if (r2->group() == nullptr) {
+      if (!r1->FirstIntersection(r2).IsValid()) {
+        LiveRangeGroup* grp = new (local_zone) LiveRangeGroup(local_zone);
+        grp->ranges().insert(r1);
+        grp->ranges().insert(r2);
+        r1->SetGroup(grp);
+        r2->SetGroup(grp);
+      }
+      return;
+    }
+    return TryGroup(r2, r1, local_zone);
+  }
+  DCHECK(r1->group() != nullptr);
+  if (r2->group() == nullptr) {
+    if (CanAddToGroup(r2, r1->group())) {
+      r1->group()->ranges().insert(r2);
+      r2->SetGroup(r1->group());
+    }
+    return;
+  }
+  TryMergeGroups(r1, r2);
+}
+
+
+void GreedyAllocator::GroupAndEnqueue() {
+  // Group phi inputs to the output. Ideally, they get all allocated to the same
+  // register, avoiding moves.
+  for (auto r : data()->live_ranges()) {
+    if (r == nullptr || r->IsEmpty() || r->kind() != mode()) continue;

[Jarin, 2015/06/09 15:00:42]

Are all these cases really possible? It seems to me that the nullptr case should
not happen. If that is the case, please DCHECK rather than silently skip.

[Mircea Trofin, 2015/06/10 05:37:10]

A similar test happens in LinearScanAllocator::AllocateRanges. I believe it may
have to do with how the live ranges get built and joined - I haven't
investigated deeper this area, I remember having seen null values though.

+    if (r->is_phi()) {
+      auto phi_map = data()->GetPhiMapValueFor(r->id());
+      auto phi = phi_map->phi();
+      auto inputs = phi->operands();
+      for (auto i : inputs) {
+        LiveRange* in_range = data()->live_ranges()[i];
+        TryGroup(r, in_range, local_zone());
+      }
+    }
+  }
+
+  ZoneSet<LiveRangeGroup*> seen_groups(local_zone());
+  for (auto range : data()->live_ranges()) {
+    if (range == nullptr || range->IsEmpty() || range->spilled() ||
+        range->kind() != mode())
+      continue;
+
+    if (range->group() != nullptr) {
+      auto grp = range->group();
+      if (seen_groups.count(grp) > 0) continue;
+      seen_groups.insert(grp);
+      Enqueue(grp);
+      if (FLAG_trace_alloc) {
+        OFStream os(stdout);
+        os << "group: " << std::endl;
+        PrintableLiveRange plr;
+        plr.register_configuration_ = data()->config();
+        for (auto r : grp->ranges()) {
+          plr.range_ = r;
+          os << plr;
+        }
+        os << std::endl;
+      }
+    } else {
+      Enqueue(range);
+    }
+  }
+}
+
+
+void GreedyAllocator::EvictAll(int reg,
+                               const conflict_iterator& first_conflict) {
+  for (conflict_iterator c = first_conflict; c.IsValid();) {
+    auto range = *c;
+    while (c.IsValid() && *c == range) ++c;
+
+    DCHECK(range->HasRegisterAssigned());
+    CHECK(!range->IsFixed());
+    allocations_[reg]->remove(range);
+    Evict(range);
+    Enqueue(range);
+  }
+}
+
+
+void GreedyAllocator::AllocateRange(LiveRange* current) {
+  TRACE("Processing interval %d of size %d\n", current->id(), current->size());
+
+  LiveRange* remaining = nullptr;
+  if (HandleSpillOperands(current, &remaining)) {
+    if (remaining != nullptr) Enqueue(remaining);
+    return;
+  }
+
+  // TODO(mtrofin): Does the linear algo's hinting mechanism even matter,
+  // now that we have groups?

[Jarin, 2015/06/09 15:00:42]

I think some hinting is important for both allocators, e.g., hinting from fixed
register use. However, most of the hinting is indeed useless for the greedy
algorithm because it assumes the hints propagate forward.

[Mircea Trofin, 2015/06/10 05:37:10]

I wonder if more elaborate grouping will help there - I'll leave the comment in
so I remember to tackle this in a next change.

+  int hint_reg = GetHintedRegister(current);
+  float my_weight = current->weight();
+  if (hint_reg >= 0) {
+    auto first_conflict = allocations_[hint_reg]->first_conflict(current);
+    if (!first_conflict.IsValid()) {
+      AssignRangeToRegister(hint_reg, current);
+      return;
+    }
+    float max_weight = CalculateMaxSpillWeight(
+        first_conflict, allocations_[hint_reg]->conflict_end());
+    if (max_weight < my_weight) {
+      EvictAll(hint_reg, first_conflict);
+      AssignRangeToRegister(hint_reg, current);
+      return;
+    }
+  }
+
+  int free_reg = -1;
+  conflict_iterator all_conflicts[RegisterConfiguration::kMaxDoubleRegisters];
+  for (int i = 0; i < num_registers(); i++) {
+    auto conflict = allocations_[i]->first_conflict(current);
+    if (!conflict.IsValid()) {
+      free_reg = i;
+      break;
+    }
+    all_conflicts[i] = conflict;
+  }
+
+  if (free_reg >= 0) {
+    AssignRangeToRegister(free_reg, current);
+    return;
+  }
+  free_reg = FindRegisterToEvictForRange(all_conflicts, my_weight);
+  if (free_reg >= 0) {
+    EvictAll(free_reg, all_conflicts[free_reg]);
+    AssignRangeToRegister(free_reg, current);
+    return;
+  }
+  HandleBlockedRange(current);
+}
+
+template <typename TIter>
+float GreedyAllocator::CalculateMaxSpillWeight(const TIter& begin,
+                                               const TIter& end) {
+  float ret = 0.0;
+  for (auto s = begin; s != end; ++s) {
+    ret = Max(ret, (*s)->weight());
+    if (ret == LiveRange::kMaxWeight) return ret;
+  }
+  return ret;
+}
+
+
+bool GreedyAllocator::TryAllocateGroup(LiveRangeGroup* grp) {
+  for (int i = 0; i < num_registers(); i++) {
+    if (TryAllocateGroupAtRegister(i, grp)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool GreedyAllocator::TryAllocateGroupAtRegister(unsigned reg,
+                                                 LiveRangeGroup* grp) {
+  auto ranges = grp->ranges();
+  for (auto r : ranges) {
+    auto first_conflict = allocations_[reg]->first_conflict(r);
+    if (first_conflict.IsValid()) {
+      return false;
+    }
+  }
+  for (auto r : ranges) {
+    AssignRangeToRegister(reg, r);
+  }
+  return true;
+}
+
+
+int GreedyAllocator::FindRegisterToEvictForRange(
+    conflict_iterator all_conflicts[RegisterConfiguration::kMaxDoubleRegisters],
+    float competing) {
+  int ret = -1;
+  float smallest_weight = LiveRange::kMaxWeight;
+  for (int i = 0; i < num_registers(); ++i) {
+    float w = CalculateMaxSpillWeight(all_conflicts[i], conflict_iterator());
+    if (w >= competing) continue;
+    if (w < smallest_weight) {
+      smallest_weight = w;
+      ret = i;
+    }
+  }
+  return ret;
+}
+
+
+int GreedyAllocator::FindRegisterToEvictForGroup(LiveRangeGroup* grp,
+                                                 float competing) {
+  int ret = -1;
+  auto ranges = grp->ranges();
+  float smallest_weight = LiveRange::kMaxWeight;
+  for (int i = 0; i < num_registers(); ++i) {
+    float grp_counter_weight = 0.0;
+    for (auto r : ranges) {
+      auto first_conflict = allocations_[i]->first_conflict(r);
+      if (!first_conflict.IsValid()) continue;
+      auto w = CalculateMaxSpillWeight(first_conflict, conflict_iterator());
+      grp_counter_weight = Max(grp_counter_weight, w);
+      if (grp_counter_weight >= competing) break;
+    }
+    if (grp_counter_weight >= competing) continue;
+    if (grp_counter_weight < smallest_weight) {
+      smallest_weight = grp_counter_weight;
+      ret = i;
+    }
+  }
+  return ret;
+}
+
+
+// Utility for improved readability in AllocateGroup
+enum Attempt {
+  Error = -1,
+  BeforeEviction = 0,
+  AfterEviction = 1,
+  AllocateIndividuals = 2
+};
+
+
+static Attempt Next(Attempt a) {
+  int i = static_cast<int>(a);

[Jarin, 2015/06/09 15:00:41]

This code is both brittle and hard to read. Please, use switch-case.

[Mircea Trofin, 2015/06/10 05:37:10]

Done.

+  if (i < 0) return Error;
+  if (i > 2) return Error;
+  return static_cast<Attempt>(i + 1);
+}
+
+
+// TODO(mtrofin): improved code reuse with AllocateRange?
+void GreedyAllocator::AllocateGroup(LiveRangeGroup* grp) {
+  // Modify the group ranges content after handling spill operands
+  for (auto iter = grp->ranges().begin(), end = grp->ranges().end();
+       iter != end;) {
+    auto iter_backup = iter;
+    auto range = *iter++;
+    LiveRange* reminder = nullptr;
+    if (HandleSpillOperands(range, &reminder)) {

[Jarin, 2015/06/09 15:00:41]

reminder -> remainder

[Mircea Trofin, 2015/06/10 05:37:10]

Done.

+      grp->ranges().erase(iter_backup);
+      if (reminder != nullptr) {
+        grp->ranges().insert(reminder);
+        reminder->RecalculateWeight(code());
+      }
+    }
+  }
+
+  float grp_weight = -1.0;
+  for (Attempt state = BeforeEviction; state != AllocateIndividuals;
+       Next(state)) {

[Jarin, 2015/06/09 15:00:42]

You mean "state = Next(state)"?

I am puzzled why this code does not hang.

Also, it seems the Attempt enum is not used in any interesting way; basically,
it just makes the loop run two iterations in a very roundabout way. Perhaps we
could just have a loop from 0 to 2?

[Mircea Trofin, 2015/06/10 05:37:11]

Ya, there's a bug, it should be state = Next(state); it probably got lucky and
all scenarios had allocating groups. Thanks for the catch.

As for a for (0..2) instead - it'd be functionally equivalent, but I believe
harder to read. E.g. why 2? I'd argue that the enum-based design makes it clear:
it's not a "loop" per se, it's just 2 states.

[Jarin, 2015/06/10 05:59:07]

Actually, there is a return at the end of the loop (and no continue), so I am
wondering why there is a loop at all.

+    if (TryAllocateGroup(grp)) {
+      stats_.groups_allocated++;
+      return;
+    }
+
+    if (grp_weight < 0.0)
+      grp_weight =
+          CalculateMaxSpillWeight(grp->ranges().begin(), grp->ranges().end());
+    int reg_to_free = FindRegisterToEvictForGroup(grp, grp_weight);
+    if (reg_to_free < 0) break;
+    for (auto r : grp->ranges()) {
+      EvictAll(reg_to_free, allocations_[reg_to_free]->first_conflict(r));
+      AssignRangeToRegister(reg_to_free, r);
+    }
+    return;
+  }
+
+  for (auto r : grp->ranges()) {
+    Enqueue(r);
+  }
 }
 
 
 void GreedyAllocator::AllocateRegisters() {
-  for (auto range : data()->live_ranges()) {
-    if (range == nullptr) continue;
-    if (range->kind() == mode()) {
-      DCHECK(!range->HasRegisterAssigned() && !range->spilled());
-      TRACE("Enqueueing live range %d to priority queue \n", range->id());
-      Enqueue(range);
-    }
-  }
+  stats_.reset();
+  CHECK_EQ(0, queue_.size());
+  CHECK_EQ(0, allocations_.size());

[Jarin, 2015/06/09 15:00:41]

CHECK(queue_.empty());
CHECK(allocations_.empty());

[Mircea Trofin, 2015/06/10 05:37:11]

Done.

+
+  TRACE("Begin allocating function %s with the Greedy Allocator\n",
+        data()->debug_name());
 
   allocations_.resize(num_registers());
   for (int i = 0; i < num_registers(); i++) {
     allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_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);
-    }
-  }
+      allocations_[reg_nr]->insert(current);
+      current->RecalculateWeight(code());
+    }
+  }
+
+  GroupAndEnqueue();
 
   while (!queue_.empty()) {
     auto current_pair = queue_.top();

[Jarin, 2015/06/09 15:00:42]

Could you replace the "auto" with a real type here (and elsewhere where the type
is not immediately obvious)?

[Mircea Trofin, 2015/06/10 05:37:10]

Done.

I'll keep an eye for other instances of this.

     queue_.pop();
-    auto current = current_pair.second;
-    if (HandleSpillOperands(current)) {
-      continue;
-    }
-    bool spill = false;
-    ZoneSet<LiveRange*> conflicting(local_zone());
-    if (!TryAllocate(current, &conflicting)) {
-      DCHECK(!conflicting.empty());
-      float this_weight = std::numeric_limits<float>::max();
-      LifetimePosition split_pos =
-          FindProgressingSplitPosition(current, &spill);
-      if (split_pos.IsValid()) {
-        this_weight = CalculateSpillWeight(current);
-      }
-
-      bool evicted = false;
-      for (auto* conflict : conflicting) {
-        if (CalculateSpillWeight(conflict) < this_weight) {
-          Evict(conflict);
-          Enqueue(conflict);
-          evicted = true;
-        }
-      }
-      if (evicted) {
-        conflicting.clear();
-        TryAllocate(current, &conflicting);
-      }
-      if (!conflicting.empty()) {
-        DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
-        DCHECK(split_pos.IsValid());
-        AllocateBlockedRange(current, split_pos, spill);
-      }
+    auto element = current_pair.second;
+    if (element.IsGroup()) {
+      AllocateGroup(element.get_group());
+    } else {
+      auto current = element.get_range();
+      AllocateRange(current);
     }
   }
 
   for (size_t i = 0; i < allocations_.size(); ++i) {
-    if (!allocations_[i]->IsEmpty()) {
+    if (!allocations_[i]->empty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
-}
-
-
-LifetimePosition GreedyAllocator::GetSplittablePos(LifetimePosition pos) {
-  auto ret = pos.PrevStart().End();
-  if (IsBlockBoundary(code(), pos.Start())) {
-    ret = pos.Start();
-  }
-  DCHECK(ret <= pos);
-  return ret;
-}
-
-LifetimePosition GreedyAllocator::FindProgressingSplitPosition(
-    LiveRange* range, bool* is_spill_pos) {
+  allocations_.clear();
+
+  for (auto r : data()->live_ranges()) {
+    if (r == nullptr || r->IsEmpty() || r->kind() != mode()) continue;
+    if (!r->spilled()) continue;
+    auto top = r->TopLevel();
+    if (top->group() != nullptr) {
+      if (!top->HasSpillRange()) continue;
+      auto top_sp_range = top->GetSpillRange();
+      CHECK(top_sp_range != nullptr);

[Jarin, 2015/06/12 04:09:10]

CHECK -> DCHECK
top_sp_range -> top_spill_range

We generally do not like abbreviations unless it is crystal clear what they
mean. (Style guide says: "Function names, variable names, and filenames should
be descriptive; eschew abbreviation.")

+      for (auto m : top->group()->ranges()) {
+        if (!m->HasSpillRange()) continue;
+        auto m_sp_range = m->TopLevel()->GetSpillRange();
+        if (m_sp_range == top_sp_range) continue;
+        bool merged = top_sp_range->TryMerge(m_sp_range);
+        CHECK(merged);
+      }
+    }

[Jarin, 2015/06/09 15:00:41]

I am a bit confused about what this is doing. It looks like it collects all
spilled sub-ranges of live range. If that is the case, it is quite dangerous
because we only spill in the beginning of the top level range, so if a
non-spilled subrange is reused for a different live range, it could overwrite
the spill slot, which would be bad. Perhaps I am missing something?

[Mircea Trofin, 2015/06/10 05:37:11]

It merges the spill ranges of live ranges belonging to a group. It's the moral
equivalent of TryReuseSpillForPhi. While it does visit all (including split)
ranges, it picks the spill ranges from the parent always. But I may be missing
something?

+  }
+  TRACE("End allocating function %s with the Greedy Allocator\n",
+        data()->debug_name());
+}
+
+
+void GreedyAllocator::HandleBlockedRange(LiveRange* current) {
+  // Make the best possible decision for splitting this range. The resulting
+  // chunks may have a better chance at allocation, or, if not, will eventually
+  // be unsplittable and "fit".
+
+  // TODO(mtrofin): more tuning. Is the ordering the one we want?
+  auto start = current->Start();
+  auto end = current->End();
+
+  UsePosition* next_reg_use =
+      current->NextUsePositionRegisterIsBeneficial(start);
+
+  if (current->is_phi()) {
+    CHECK(next_reg_use != nullptr && next_reg_use->pos() == start);
+    // If the range does not need register soon, spill it to the merged
+    // spill range.
+    auto next_pos = start;
+    if (next_pos.IsGapPosition()) next_pos = next_pos.NextStart();
+    auto pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
+    if (pos == nullptr) {
+      Spill(current);
+      return;
+    } else if (pos->pos() > start.NextStart()) {
+      Enqueue(SpillBetweenUntil(current, start, start, pos->pos()));
+      return;
+    }
+  }
+
+  if (next_reg_use == nullptr) {
+    auto pos = FindOptimalSpillingPos(current, start);
+    DCHECK(pos.IsValid());
+    auto tail = SplitRangeAt(current, pos);
+    Spill(tail);
+    if (tail != current) {
+      Enqueue(current);
+    }
+    return;
+  }
+
+  if (TrySplitAroundCalls(current)) return;
+  if (TrySplitBeforeLoops(current)) return;
+  if (TrySplitAfterLoops(current)) return;
+
+
+  if (current->CanBeSpilled(start)) {
+    UsePosition* next_mandatory_use = nullptr;
+    for (next_mandatory_use = current->first_pos();
+         next_mandatory_use != nullptr;
+         next_mandatory_use = next_mandatory_use->next()) {
+      if (next_mandatory_use->type() == UsePositionType::kRequiresRegister)
+        break;
+    }
+    if (next_mandatory_use == nullptr)

[Jarin, 2015/06/09 15:00:41]

Please, put the then- and else- clauses into braces. We generally omit the
braces only if the then-clause fits on the same line as the condition.

[Mircea Trofin, 2015/06/10 05:37:11]

Ugh... yes... llvm-ism

+      Spill(current);
+    else
+      Enqueue(
+          SpillBetweenUntil(current, start, start, next_mandatory_use->pos()));
+    return;
+  }
+
+  if (current->first_interval()->next() != nullptr) {
+    auto tail = SplitRangeAt(current, current->first_interval()->end());
+    DCHECK(tail != current);
+    Enqueue(tail);
+    Enqueue(current);
+    return;
+  }
+
+  auto pos_to_split = current->GetFirstSplittablePosition();
+  CHECK(pos_to_split.IsValid() && start < pos_to_split && pos_to_split < end);
+  auto tail = SplitRangeAt(current, pos_to_split);
+  CHECK(tail != current);
+  Enqueue(tail);
+  Enqueue(current);
+}
+
+
+bool GreedyAllocator::TrySplitAroundCalls(LiveRange* range) {
+  // TODO(mtrofin): should we just split around all calls?
   auto start = range->Start();
   auto end = range->End();
-
-  UsePosition* next_reg_use = range->first_pos();
-  while (next_reg_use != nullptr &&
-         next_reg_use->type() != UsePositionType::kRequiresRegister) {
-    next_reg_use = next_reg_use->next();
-  }
-
-  if (next_reg_use == nullptr) {
-    *is_spill_pos = true;
-    auto ret = FindOptimalSpillingPos(range, start);
-    DCHECK(ret.IsValid());
-    return ret;
-  }
-
-  *is_spill_pos = false;
-  auto reg_pos = next_reg_use->pos();
-  auto correct_pos = GetSplittablePos(reg_pos);
-  if (start < correct_pos && correct_pos < end) {
-    return correct_pos;
-  }
-
-  if (correct_pos >= end) {
-    return LifetimePosition::Invalid();
-  }
-
-  // Correct_pos must be at or before start. Find the next use position.
-  next_reg_use = next_reg_use->next();
-  auto reference = reg_pos;
-  while (next_reg_use != nullptr) {
-    auto pos = next_reg_use->pos();
-    // Skip over tight successive uses.
-    if (reference.NextStart() < pos) {
-      break;
-    }
-    reference = pos;
-    next_reg_use = next_reg_use->next();
-  }
-
-  if (next_reg_use == nullptr) {
-    // While there may not be another use, we may still have space in the range
-    // to clip off.
-    correct_pos = reference.NextStart();
-    if (start < correct_pos && correct_pos < end) {
-      return correct_pos;
-    }
-    return LifetimePosition::Invalid();
-  }
-
-  correct_pos = GetSplittablePos(next_reg_use->pos());
-  if (start < correct_pos && correct_pos < end) {
-    DCHECK(reference < correct_pos);
-    return correct_pos;
-  }
-  return LifetimePosition::Invalid();
-}
-
-
-void GreedyAllocator::AllocateBlockedRange(LiveRange* current,
-                                           LifetimePosition pos, bool spill) {
-  auto tail = SplitRangeAt(current, pos);
-  if (spill) {
-    Spill(tail);
-  } else {
-    Enqueue(tail);
-  }
-  if (tail != current) {
-    Enqueue(current);
-  }
-}
-
-
+  for (auto i = range->first_interval(); i != nullptr; i = i->next()) {
+    for (int instr_pos = i->start().ToInstructionIndex();
+         instr_pos < i->end().ToInstructionIndex(); instr_pos++) {
+      auto instr = code()->InstructionAt(instr_pos);
+      if (instr->IsCall()) {
+        auto pos = LifetimePosition::GapFromInstructionIndex(instr_pos);
+        if (start >= pos || pos >= end) continue;
+        auto tail = SplitRangeAt(range, pos);
+        DCHECK(tail != range);
+        Enqueue(tail);
+        Enqueue(range);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+
+bool GreedyAllocator::TrySplitBeforeLoops(LiveRange* range) {
+  auto start = range->Start();
+  auto end = range->End();
+  for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
+    if (!pos->RegisterIsBeneficial()) continue;
+    const InstructionBlock* block =
+        code()->GetInstructionBlock(pos->pos().ToInstructionIndex());
+    if (block->IsLoopHeader() || block->loop_header().IsValid()) {
+      block = block->IsLoopHeader() ? block : GetContainingLoop(code(), block);
+      auto split_pos = start;
+      while (block != nullptr) {
+        auto before_loop_start = LifetimePosition::GapFromInstructionIndex(
+            block->first_instruction_index() - 1);
+
+        if (range->Covers(before_loop_start)) {
+          split_pos = before_loop_start;
+        }
+
+        // Try hoisting out to an outer loop.
+        block = GetContainingLoop(code(), block);
+      }
+      if (start < split_pos && split_pos < end) {
+        auto tail = SplitRangeAt(range, split_pos);
+        Enqueue(tail);
+        Enqueue(range);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+
+bool GreedyAllocator::TrySplitAfterLoops(LiveRange* range) {
+  auto start = range->Start();
+  auto end = range->End();
+  for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
+    if (!pos->RegisterIsBeneficial()) continue;
+    const InstructionBlock* block =
+        code()->GetInstructionBlock(pos->pos().ToInstructionIndex());
+    if (block->IsLoopHeader() || block->loop_header().IsValid()) {
+      auto header = block->IsLoopHeader()
+                        ? block
+                        : code()->InstructionBlockAt(block->loop_header());
+
+      auto split_pos = start;
+      while (header != nullptr) {
+        if (header->loop_end().ToSize() >=
+            static_cast<size_t>(code()->InstructionBlockCount()))
+          break;
+        auto loop_end = code()->InstructionBlockAt(header->loop_end());
+        auto after_loop_start = LifetimePosition::GapFromInstructionIndex(
+            loop_end->last_instruction_index() + 1);
+
+        if (range->Covers(after_loop_start)) {
+          split_pos = after_loop_start;
+        }
+
+        // Try hoisting out to an outer loop.
+        header = GetContainingLoop(code(), header);
+      }
+      if (start < split_pos && split_pos < end) {
+        auto tail = SplitRangeAt(range, split_pos);
+        Enqueue(tail);
+        Enqueue(range);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+
 SpillSlotLocator::SpillSlotLocator(RegisterAllocationData* data)
     : data_(data) {}
 
 
 void SpillSlotLocator::LocateSpillSlots() {
   auto code = data()->code();
   for (auto range : data()->live_ranges()) {
     if (range == nullptr || range->IsEmpty() || range->IsChild()) continue;
     // We care only about ranges which spill in the frame.
     if (!range->HasSpillRange()) continue;
     auto spills = range->spills_at_definition();
     DCHECK_NOT_NULL(spills);
     for (; spills != nullptr; spills = spills->next) {
       code->GetInstructionBlock(spills->gap_index)->mark_needs_frame();
     }
   }
 }
 
 
-bool GreedyAllocator::TryReuseSpillForPhi(LiveRange* range) {
-  if (range->IsChild() || !range->is_phi()) return false;
-  DCHECK(!range->HasSpillOperand());
-
-  auto phi_map_value = data()->GetPhiMapValueFor(range->id());
-  auto phi = phi_map_value->phi();
-  auto block = phi_map_value->block();
-  // Count the number of spilled operands.
-  size_t spilled_count = 0;
-  LiveRange* first_op = nullptr;
-  for (size_t i = 0; i < phi->operands().size(); i++) {
-    int op = phi->operands()[i];
-    LiveRange* op_range = LiveRangeFor(op);
-    if (!op_range->HasSpillRange()) continue;
-    auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
-    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
-        pred->last_instruction_index());
-    while (op_range != nullptr && !op_range->CanCover(pred_end)) {
-      op_range = op_range->next();
-    }
-    if (op_range != nullptr && op_range->spilled()) {
-      spilled_count++;
-      if (first_op == nullptr) {
-        first_op = op_range->TopLevel();
-      }
-    }
-  }
-
-  // Only continue if more than half of the operands are spilled.
-  if (spilled_count * 2 <= phi->operands().size()) {
-    return false;
-  }
-
-  // Try to merge the spilled operands and count the number of merged spilled
-  // operands.
-  DCHECK(first_op != nullptr);
-  auto first_op_spill = first_op->GetSpillRange();
-  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);
-    if (!op_range->HasSpillRange()) continue;
-    auto op_spill = op_range->GetSpillRange();
-    if (op_spill == first_op_spill || first_op_spill->TryMerge(op_spill)) {
-      num_merged++;
-    }
-  }
-
-  // Only continue if enough operands could be merged to the
-  // same spill slot.
-  if (num_merged * 2 <= phi->operands().size() ||
-      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()
-            : data()->AssignSpillRangeToLiveRange(range->TopLevel());
-    bool merged = first_op_spill->TryMerge(spill_range);
-    CHECK(merged);
-    Spill(range);
-    return true;
-  } else if (pos->pos() > range->Start().NextStart()) {
-    auto spill_range =
-        range->TopLevel()->HasSpillRange()
-            ? range->TopLevel()->GetSpillRange()
-            : data()->AssignSpillRangeToLiveRange(range->TopLevel());
-    bool merged = first_op_spill->TryMerge(spill_range);
-    CHECK(merged);
-    Enqueue(
-        SpillBetweenUntil(range, range->Start(), range->Start(), pos->pos()));
-    return true;
-  }
-  return false;
-}
-
-
 OperandAssigner::OperandAssigner(RegisterAllocationData* data) : data_(data) {}
 
 
 void OperandAssigner::AssignSpillSlots() {
   auto& spill_ranges = data()->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++) {
@@ skipping 415 matching lines @@
     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