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;
+  const UsePosition* 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) {

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

Initialize size_ and weight_ here, please. It is safer. (It will be compiled
away if you worry about performance.)

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

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

Use the real type here.

+    LifetimePosition pos;
+    if (CanBeSpilled(c->pos())) {

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

I suppose you wanted to use your new CanBeSplit method here (and below).

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

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

Use the real type here.

+        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>(GetSize());
+}
+
+
 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 147 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()) {

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

The iterator should always be in canonical form, no? Moreover, the ++ operator
should not be called when already at the end, so perhaps just do "DCHECK(pos_ !=
storage_->end())" here?

+    // We're at the end - ensure we are in a canonical "end of iterator" form.
+    Invalidate();
+    return *this;
+  }
+  DCHECK(QueryIntersectsAllocatedInterval());
+  ++pos_;
+  if (pos_ == storage_->end()) {
+    // Advancing got us at the end of storage, so the iterator becomes "end".
+    Invalidate();
+    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()) {
+    LifetimePosition q_start = query_->start();
+    LifetimePosition 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_;

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

storage_ -> intervals_, perhaps?

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

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

Package the range->group() == nullptr check into the "if (...) continue;" above.

+      auto grp = range->group();

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

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

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

When can it happen that the iterator gives the same element several times in a
row? This just should not happen. (If it does happen, the iterator should be
fixed.)

+
+    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->GetSize());
+
+  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/12 04:09:11]

Does it make any performance difference if you keep this code? 

If no, please remove?

+  int hint_reg = GetHintedRegister(current);
+  float my_weight = current->GetWeight();
+  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);

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

What happens if you do not evict here? (And spill instead, just like the basic
algorithm from LLVM does?)

Could you measure the performance impact?

+  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)->GetWeight());
+    if (ret == LiveRange::kMaxWeight) return ret;
+  }
+  return ret;
+}
+
+
+bool GreedyAllocator::TryAllocateGroup(LiveRangeGroup* grp) {

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

Do you have any performance numbers on group allocation?

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

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

Could we have a method on CoalescedLiveRanges that just returns bool if a given
range conflicts with the supplied live range? That way, you would not have to
mess with the conflict_iterator here.

+    if (!first_conflict.IsEnd()) {
+      return false;
+    }
+  }
+  for (auto r : ranges) {
+    AssignRangeToRegister(reg, r);
+  }
+  return true;
+}
+
+
+int GreedyAllocator::FindRegisterToEvictForRange(
+    conflict_iterator all_conflicts[RegisterConfiguration::kMaxDoubleRegisters],

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

Sized array argument is a bit esoteric construct in C++ (it passes just the
reference, not the entire array), and in fact some earlier versions of Visual
C++ had trouble with this. Could you omit the size of the array here?

+    float competing) {
+  int ret = -1;
+  float smallest_weight = LiveRange::kMaxWeight;
+  for (int i = 0; i < num_registers(); ++i) {
+    float w = CalculateMaxSpillWeight(all_conflicts[i],

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

w -> weight

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

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

grp -> group.

+    for (auto r : ranges) {
+      auto first_conflict = allocations_[i]->conflicts_begin(r);
+      if (first_conflict.IsEnd()) continue;
+      auto w = CalculateMaxSpillWeight(first_conflict,

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

Do not use auto here.

+                                       allocations_[i]->conflicts_end());
+      grp_counter_weight = Max(grp_counter_weight, w);
+      if (grp_counter_weight >= competing) break;
+    }
+    if (grp_counter_weight >= competing) continue;

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

Could you fold the grp_counter_weight >= competing into the next if statement
(i.e., say "if (grp_counter_weight < competing && grp_counter_weight <
smallest_weight)" there? 

In fact, looking at this you should be able to start with smallest_weight =
competing and get rid of the check above, no?

The same question applies to the method above.

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

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

grp -> group

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

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

grp_weight -> group_weight

+  if (TryAllocateGroup(grp)) {
+    stats_.groups_allocated++;
+    return;
+  }
+
+  if (grp_weight < 0.0) {

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

If you really insist on having the same types for left and right side, use 0.0f
here.

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

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

No need for the intermediate variable.

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

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

Fold into the previous if?

+    auto top = r->TopLevel();

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

Use the real type here.

+    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:11]

DCHECK?

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

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

Explicit types, please.

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

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

I am wondering whether queuing a group for tail and range would help with our
spilling around calls problem (the hope is that the group would get the same
register, so moving stuff around would not be necessary).

+        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