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);

[Benedikt Meurer, 2015/06/11 05:30:29]

Don't use auto here. Use the correct type, and ideally even use const.

+  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();

[Benedikt Meurer, 2015/06/11 05:30:29]

Can we initialize properly instead of (mis)using an InvalidateSomething method
in the constructor?

[Mircea Trofin, 2015/06/11 07:19:36]

It would be inefficient to perform weight and size calculations at this stage.
In fact, this reminds me, certain live range operations - like handling spill
operands - can be done upfront before even worrying about (calculating) size and
weights. I plan on working on that in upcoming changes, so I'd prefer not to
change something that sets me in the right direction.

 }
 
 
 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();

[Benedikt Meurer, 2015/06/11 05:30:28]

Don't use auto here.

[Mircea Trofin, 2015/06/11 07:19:35]

Done.

+
+  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()) {

[Benedikt Meurer, 2015/06/11 05:30:28]

That looks kinda inefficient to me. Seems to be linear in the size of the
program in the worst case. What does LLVM do here?

[Mircea Trofin, 2015/06/11 07:19:36]

Mozilla, at least, does something similar. LLVM's code is more complicated, but
the high level description of the algorithm calls for a calculation of use
densities, and factoring in loop-ness is important in ensuring hot ranges don't
lose to colder ones.

We could, eventually, change the LiveRange model and the stages computing them
to pre-calculate certain components, for example the loop-ness of use positions,
if that information is readily available earlier. But I believe that would be
too much churn at this stage.

+    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);

[Benedikt Meurer, 2015/06/11 05:30:28]

Why did you change this?

[Mircea Trofin, 2015/06/11 07:19:36]

Probably some experimentations, thanks for the catch - there's no reason for
this to be changed.

+  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++() {
+  DCHECK(storage_ != nullptr);
+
+  if (pos_ == storage_->end()) {
+    Invalidate();

[Benedikt Meurer, 2015/06/11 05:30:28]

Why invalidate here?

[Mircea Trofin, 2015/06/11 07:19:36]

Because we're at the end, we're out of matching conflicts. I want the end
iterator to have a canonical shape - valid storage, null query and past-end pos
- so that == and != work well. Hence calling Invalidate.

+    return *this;
+  }
+  DCHECK(QueryIntersectsAllocatedInterval());
+  ++pos_;
+  if (pos_ == storage_->end()) {
+    Invalidate();

[Benedikt Meurer, 2015/06/11 05:30:28]

Same here

[Mircea Trofin, 2015/06/11 07:19:35]

See above.

+    return *this;
+  }
+  if (!QueryIntersectsAllocatedInterval()) {
+    query_ = query_->next();
+    if (query_ == nullptr) {
+      Invalidate();
+      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) {
+  DCHECK_EQ(first.storage_, second.storage_);
+
+  return first.query_ == second.query_ && first.pos_ == second.pos_;
+}
+
+
+bool operator!=(const conflict_iterator& first,
+                const conflict_iterator& second) {
+  return !(first == second);
+}
+
+
+void conflict_iterator::InitializeForNewQuery() {
+  DCHECK(storage_ != nullptr);
+  DCHECK(query_ != nullptr);
+  // If empty or the last element starts before the query, we have no conflicts.
+  if (storage_->empty() || storage_->rbegin()->end <= query_->start()) {
+    Invalidate();
+    return;
+  }
+
+  for (; query_ != nullptr; query_ = query_->next()) {
+    auto q_start = query_->start();

[Benedikt Meurer, 2015/06/11 05:30:29]

No auto here.

[Mircea Trofin, 2015/06/11 07:19:35]

Done.

+    auto q_end = query_->end();
+    if (storage_->begin()->start >= q_end) {
+      // Skip over queried use intervals that end before the first stored
+      // element.
+      continue;
+    }
+
+    pos_ = storage_->upper_bound(AsAllocatedInterval(q_start));
+    // pos_ is either at the end (no start strictly greater than q_start) or
+    // at some position with the aforementioned property. In either case, the
+    // allocated interval before this one may intersect our query:
+    // either because, although it starts before this query's start, it ends
+    // after; or because it starts exactly at the query start. So unless we're
+    // right at the beginning of the storage - meaning the first allocated
+    // interval is also starting after this query's start - see what's behind.
+    if (pos_ != storage_->begin()) {
+      --pos_;
+      if (QueryIntersectsAllocatedInterval()) break;
+      // The interval behind wasn't intersecting, so move back.
+      ++pos_;
+    }
+    if (pos_ != storage_->end() && QueryIntersectsAllocatedInterval()) break;
+  }
+
+  // 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) {
+    Invalidate();
+    return;
+  }
+
+  SkipMatchedQueries();
+}
+
+
+// Advance query_ at the last use interval that still intersects/overlaps with
+// the current conflict, so that operator++ can pick up from there.
+void conflict_iterator::SkipMatchedQueries() {
+  DCHECK(query_ != nullptr);
+  DCHECK(QueryIntersectsAllocatedInterval());
+
+  for (; query_->next() != nullptr; query_ = query_->next()) {
+    if (!NextQueryIntersectsAllocatedInterval()) {
+      break;
+    }
+  }
+  DCHECK(query_ != nullptr);
+  DCHECK(QueryIntersectsAllocatedInterval());
+  DCHECK(query_->next() == nullptr || !NextQueryIntersectsAllocatedInterval());
+}
+
+
+// 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 conflicts_begin(LiveRange* query) {
+    return GetFirstConflict(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 conflicts_end() {
+    return conflict_iterator::EndIteratorForStorage(&storage_);
+  }
+
+  // We assume it was determined that this range does not conflict with
+  // contained ranges.
+  void insert(LiveRange* range) {
+    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 GetFirstConflict(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 LiveRangeGroup::CanAdd(LiveRange* r) {
+  for (auto member : ranges()) {
+    if (member->FirstIntersection(r).IsValid()) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+void LiveRangeGroup::TryMerge(LiveRangeGroup* other) {
+  DCHECK(other != nullptr);
+
+  bool can_merge = true;
+  for (auto r : ranges()) {
+    if (!other->CanAdd(r)) {
+      can_merge = false;
+      break;
+    }
+  }
+  if (can_merge) {
+    for (auto r : ranges()) {
+      other->ranges().insert(r);
+      r->SetGroup(other);
+    }
+  }
+}
+
+
+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 (r1->group()->CanAdd(r2)) {
+      r1->group()->ranges().insert(r2);
+      r2->SetGroup(r1->group());
+    }
+    return;
+  }
+  r1->group()->TryMerge(r2->group());
+}
+
+
+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;
+    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.IsEnd();) {
+    auto range = *c;
+    while (!c.IsEnd() && *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?
+  int hint_reg = GetHintedRegister(current);
+  float my_weight = current->weight();
+  if (hint_reg >= 0) {
+    auto first_conflict = allocations_[hint_reg]->conflicts_begin(current);
+    if (first_conflict.IsEnd()) {
+      AssignRangeToRegister(hint_reg, current);
+      return;
+    }
+    float max_weight = CalculateMaxSpillWeight(
+        first_conflict, allocations_[hint_reg]->conflicts_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]->conflicts_begin(current);
+    if (conflict.IsEnd()) {
+      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]->conflicts_begin(r);
+    if (!first_conflict.IsEnd()) {
+      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],
+                                      allocations_[i]->conflicts_end());
+    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]->conflicts_begin(r);
+      if (first_conflict.IsEnd()) continue;
+      auto w = CalculateMaxSpillWeight(first_conflict,
+                                       allocations_[i]->conflicts_end());
+      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;
+}
+
+
+// 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* remainder = nullptr;
+    if (HandleSpillOperands(range, &remainder)) {
+      grp->ranges().erase(iter_backup);
+      if (remainder != nullptr) {
+        grp->ranges().insert(remainder);
+        remainder->RecalculateWeight(code());
+      }
+    }
+  }
+
+  float grp_weight = -1.0;
+  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) {
+    for (auto r : grp->ranges()) {
+      EvictAll(reg_to_free, allocations_[reg_to_free]->conflicts_begin(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(queue_.empty());
+  CHECK(allocations_.empty());
+
+  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();
+    std::pair<unsigned, PQueueElem> current_pair = queue_.top();
     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);
+      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);
+      }
+    }
+  }
+  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) {
+      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