Greedy allocator: perf work

src/compiler/register-allocator.cc

Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc
index 08b71f2e40488181657a064418bff797d9186b9c..d1ad6b248525a9e70b47b7b1655f6780520c7348 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -47,6 +47,17 @@ const InstructionBlock* GetContainingLoop(const InstructionSequence* sequence,
 }
 
 
+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());
@@ -110,6 +121,22 @@ int GetByteWidth(MachineType machine_type) {
   }
 }
 
+
+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
 
 
@@ -143,6 +170,60 @@ bool UsePosition::HasHint() const {
 }
 
 
+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_)) {
@@ -264,11 +345,13 @@ LiveRange::LiveRange(int id, MachineType machine_type)
       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();
 }
 
 
@@ -424,9 +507,10 @@ UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) const {
 }
 
 
-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();
@@ -572,6 +656,7 @@ void LiveRange::SplitAt(LifetimePosition position, LiveRange* result,
   result->parent_ = (parent_ == nullptr) ? this : parent_;
   result->next_ = next_;
   next_ = result;
+  InvalidateWeightAndSize();
 
 #ifdef DEBUG
   Verify();
@@ -763,6 +848,81 @@ LifetimePosition LiveRange::FirstIntersection(LiveRange* other) const {
 }
 
 
+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) {
@@ -782,35 +942,75 @@ static bool AreUseIntervalsIntersecting(UseInterval* interval1,
 }
 
 
+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();
-  PrintableInstructionOperand pio;
-  pio.register_configuration_ = printable_range.register_configuration_;
   while (use_pos != nullptr) {
-    pio.op_ = *use_pos->operand();
-    os << pio << use_pos->pos() << " ";
+    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;
 
-  while (interval != nullptr) {
-    os << '[' << interval->start() << ", " << interval->end() << ')'
-       << std::endl;
-    interval = interval->next();
-  }
+  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());
@@ -1013,8 +1213,8 @@ LiveRange* RegisterAllocationData::NewChildRangeFor(LiveRange* range) {
 
 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);
@@ -1844,6 +2044,8 @@ LifetimePosition RegisterAllocator::FindOptimalSpillingPos(
 
 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()) {
@@ -1871,10 +2073,12 @@ LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
 
 
 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()) {
@@ -1951,15 +2155,22 @@ void LinearScanAllocator::AllocateRegisters() {
     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 {
@@ -2127,6 +2338,10 @@ bool LinearScanAllocator::TryAllocateFreeReg(LiveRange* current) {
   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);
   }
@@ -2199,6 +2414,8 @@ void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) {
   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;
   }
@@ -2206,6 +2423,8 @@ void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) {
   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);
@@ -2234,6 +2453,8 @@ void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
       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
@@ -2244,6 +2465,8 @@ void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
         // 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);
@@ -2259,9 +2482,13 @@ void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* 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);
@@ -2398,77 +2625,196 @@ void LinearScanAllocator::SpillBetweenUntil(LiveRange* range,
 }
 
 
+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});
     }
-    return true;
   }
 
-  bool Remove(LiveRange* range) {
-    bool ret = false;
-    auto* segment = range->first_interval();
-    while (segment != nullptr) {
-      ret |= Remove(segment);
-      segment = segment->next();
+  void remove(LiveRange* range) {
+    for (auto interval = range->first_interval(); interval != nullptr;
+         interval = interval->next()) {
+      storage_.erase({interval->start(), interval->end(), range});
     }
-    return ret;
   }
 
-  bool IsEmpty() { return storage_.is_empty(); }
+  bool empty() const { return storage_.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;
+  bool IsValid() {
+    LifetimePosition last_end = LifetimePosition::GapFromInstructionIndex(0);
+    for (auto i : storage_) {
+      if (i.start < last_end) {
+        return false;
+      }
+      last_end = i.end;
     }
-  };
-
-  Config::Key GetKey(UseInterval* interval) {
-    if (interval == nullptr) return std::make_pair(0, 0);
-    return std::make_pair(interval->start().value(), interval->end().value());
+    return true;
   }
 
-  // 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;
+ private:
+  conflict_iterator GetFirstConflict(UseInterval* query) {
+    return conflict_iterator(query, &storage_);
   }
 
-  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)
@@ -2478,78 +2824,27 @@ GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
       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()) {
@@ -2558,66 +2853,6 @@ void GreedyAllocator::Evict(LiveRange* range) {
 }
 
 
-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,
@@ -2649,14 +2884,32 @@ LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range,
 
 
 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)});
+}
+
+
+// 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) {
+bool GreedyAllocator::HandleSpillOperands(LiveRange* range,
+                                          LiveRange** remaining) {
   auto position = range->Start();
   TRACE("Processing interval %d start=%d\n", range->id(), position.value());
 
@@ -2675,24 +2928,314 @@ bool GreedyAllocator::HandleSpillOperands(LiveRange* range) {
     } 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;
 }
 
 
-void GreedyAllocator::AllocateRegisters() {
+// 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) continue;
-    if (range->kind() == mode()) {
-      DCHECK(!range->HasRegisterAssigned() && !range->spilled());
-      TRACE("Enqueueing live range %d to priority queue \n", range->id());
+    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() {
+  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++) {
@@ -2703,138 +3246,225 @@ void GreedyAllocator::AllocateRegisters() {
     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));
     }
   }
+  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());
 }
 
 
-LifetimePosition GreedyAllocator::GetSplittablePos(LifetimePosition pos) {
-  auto ret = pos.PrevStart().End();
-  if (IsBlockBoundary(code(), pos.Start())) {
-    ret = pos.Start();
-  }
-  DCHECK(ret <= pos);
-  return ret;
-}
+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".
 
-LifetimePosition GreedyAllocator::FindProgressingSplitPosition(
-    LiveRange* range, bool* is_spill_pos) {
-  auto start = range->Start();
-  auto end = range->End();
+  // 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);
 
-  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 (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) {
-    *is_spill_pos = true;
-    auto ret = FindOptimalSpillingPos(range, start);
-    DCHECK(ret.IsValid());
-    return ret;
+    auto pos = FindOptimalSpillingPos(current, start);
+    DCHECK(pos.IsValid());
+    auto tail = SplitRangeAt(current, pos);
+    Spill(tail);
+    if (tail != current) {
+      Enqueue(current);
+    }
+    return;
   }
 
-  *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 (TrySplitAroundCalls(current)) return;
+  if (TrySplitBeforeLoops(current)) return;
+  if (TrySplitAfterLoops(current)) return;
 
-  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;
+  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;
     }
-    reference = pos;
-    next_reg_use = next_reg_use->next();
+    if (next_mandatory_use == nullptr) {
+      Spill(current);
+    } else {
+      Enqueue(
+          SpillBetweenUntil(current, start, start, next_mandatory_use->pos()));
+    }
+    return;
   }
 
-  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();
+  if (current->first_interval()->next() != nullptr) {
+    auto tail = SplitRangeAt(current, current->first_interval()->end());
+    DCHECK(tail != current);
+    Enqueue(tail);
+    Enqueue(current);
+    return;
   }
 
-  correct_pos = GetSplittablePos(next_reg_use->pos());
-  if (start < correct_pos && correct_pos < end) {
-    DCHECK(reference < correct_pos);
-    return correct_pos;
+  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();
+  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 LifetimePosition::Invalid();
+  return false;
 }
 
 
-void GreedyAllocator::AllocateBlockedRange(LiveRange* current,
-                                           LifetimePosition pos, bool spill) {
-  auto tail = SplitRangeAt(current, pos);
-  if (spill) {
-    Spill(tail);
-  } else {
-    Enqueue(tail);
+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;
+      }
+    }
   }
-  if (tail != current) {
-    Enqueue(current);
+  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;
 }
 
 
@@ -2857,91 +3487,6 @@ void SpillSlotLocator::LocateSpillSlots() {
 }
 
 
-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) {}
 
 
@@ -3377,7 +3922,6 @@ void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
         moves->push_back(move);
       }
       if (done) break;
-      // Reset state.
       to_eliminate.clear();
       to_insert.clear();
       moves = it->first.first;