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..1870496629b1ba121723f8a5fe34d3da0f03779e 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -47,6 +47,18 @@ const InstructionBlock* GetContainingLoop(const InstructionSequence* sequence,
 }
 
 
+unsigned GetContainingLoopCount(const InstructionSequence* sequence,
+                                const InstructionBlock* block) {
+  if (block->loop_header().IsValid()) return 1;

[Jarin, 2015/05/13 13:12:56]

Can't you use block->IsLoopHeader()?

+
+  if (block->PredecessorCount() == 0)

[Jarin, 2015/05/13 13:12:56]

Style nit: only omit the parentheses if the statement fits on one line.

+    return 0;
+  else
+    return GetContainingLoopCount(
+        sequence, sequence->InstructionBlockAt(block->predecessors()[0]));

[Jarin, 2015/05/13 13:12:56]

Can we get rid of the recursion?

More importantly, what is it supposed to compute?

At the moment, it only returns 0 or 1, that seems wrong.

Moreover, by walking up the predecessor chain you could get into a loop and then
return 1 even if the starting block was not in a loop. That does not seem right
either.

+}
+
+
 const InstructionBlock* GetInstructionBlock(const InstructionSequence* code,
                                             LifetimePosition pos) {
   return code->GetInstructionBlock(pos.ToInstructionIndex());
@@ -795,8 +807,12 @@ std::ostream& operator<<(std::ostream& os,
   PrintableInstructionOperand pio;
   pio.register_configuration_ = printable_range.register_configuration_;
   while (use_pos != nullptr) {
-    pio.op_ = *use_pos->operand();
-    os << pio << use_pos->pos() << " ";
+    if (use_pos->HasOperand()) {
+      pio.op_ = *use_pos->operand();
+      os << pio << use_pos->pos() << " ";
+    } else {
+      os << "<no_op> ";
+    }
     use_pos = use_pos->next();
   }
   os << std::endl;
@@ -1844,6 +1860,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,13 +1889,17 @@ LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
 
 
 void LinearScanAllocator::AllocateRegisters() {
+  stats_.reset();
+  unsigned range_count = 0;
   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()) {
+      range_count++;
       AddToUnhandledUnsorted(range);
     }
   }
@@ -1924,7 +1946,11 @@ void LinearScanAllocator::AllocateRegisters() {
       }
     }
 
-    if (TryReuseSpillForPhi(current)) continue;
+    bool cont = false;
+    TRACE("Entering TryReuseSpillForPhi with range %d\n", current->id());
+    if (TryReuseSpillForPhi(current)) cont = true;
+    TRACE("Exiting TryReuseSpillForPhi with range %d\n", current->id());
+    if (cont) continue;
 
     for (size_t i = 0; i < active_live_ranges().size(); ++i) {
       auto cur_active = active_live_ranges()[i];
@@ -1951,15 +1977,31 @@ void LinearScanAllocator::AllocateRegisters() {
     DCHECK(!current->HasRegisterAssigned() && !current->spilled());
 
     bool result = TryAllocateFreeReg(current);
+    TRACE("Failed to allocate free reg for %d\n", current->id());
     if (!result) 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());
+  if (FLAG_greedy_stats) {
+    OFStream os(stdout);
+    os << "==================================================" << std::endl;
+    os << "allocation stats for:  " << data()->debug_name() << "(" << mode()
+       << ")" << std::endl;
+    os << "input ranges:          " << range_count << std::endl;
+    os << "input fixed ranges:    " << GetFixedRegisters(data(), mode()).size()
+       << std::endl;
+    os << stats_;
+    os << "==================================================" << std::endl;
   }
 }
 
 
-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 +2169,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 +2245,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 +2254,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 +2284,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 +2296,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 +2313,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);
@@ -2470,6 +2528,22 @@ class CoalescedLiveRanges : public ZoneObject {
 
 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;
+  return os;
+}
+
+
 GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
                                  RegisterKind kind, Zone* local_zone)
     : RegisterAllocator(data, kind),
@@ -2478,17 +2552,15 @@ GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
       queue_(local_zone) {}
 
 
-unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) {
-  auto interval = range->first_interval();
-  if (interval == nullptr) return 0;
+unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range,
+                                           LifetimePosition start,
+                                           LifetimePosition end) {
+  return (end.value() - start.value());
+}
 
-  unsigned size = 0;
-  while (interval != nullptr) {
-    size += (interval->end().value() - interval->start().value());
-    interval = interval->next();
-  }
 
-  return size;
+unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) {
+  return GetLiveRangeSize(range, range->Start(), range->End());
 }
 
 
@@ -2498,6 +2570,7 @@ void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
     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()) {
@@ -2507,47 +2580,62 @@ void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
 
 
 float GreedyAllocator::CalculateSpillWeight(LiveRange* range) {
-  InstructionOperand* first_hint = nullptr;
-  if (range->FirstHintPosition() != nullptr) {
-    first_hint = range->FirstHintPosition()->operand();
-  }
+  return CalculateSpillWeight(range, range->Start(), range->End());
+}
+
 
+// Local definition of integer power, to avoid casting std::pow.
+unsigned ipow(unsigned b, unsigned e) {
+  if (e == 0) return 1;
+  if (e == 1) return b;
+  auto odd = e & 1;
+  auto rem = e >> 1;
+  auto half = ipow(b, rem);

[Jarin, 2015/05/13 13:12:57]

If you wrote this function for efficiency, then you should not use recursion
here.

+  auto ret = half * half;
+  if (odd) ret *= b;
+  return ret;
+}
+
+
+float GreedyAllocator::CalculateSpillWeight(LiveRange* range,
+                                            LifetimePosition start,
+                                            LifetimePosition end) {
   if (range->IsFixed()) return std::numeric_limits<float>::max();
-  bool spill;
-  if (!FindProgressingSplitPosition(range, &spill).IsValid())
+
+  if (!RangeHasSplitOrSpillPosition(range, start, end))
     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();
+  const InstructionBlock* last_block = nullptr;
+
+  unsigned last_loop_count = 0;
+  unsigned last_use_count = 0;
+  for (; pos != nullptr; pos = pos->next()) {
+    if (pos->pos() < start) continue;
+    if (pos->pos() > end) break;
+
+    auto block = GetInstructionBlock(code(), pos->pos());
+    if (block != last_block) {
+      last_block = block;
+      use_count += last_use_count * ipow(2, last_loop_count);

[Jarin, 2015/05/13 13:12:56]

ipow(2, x) --> 1 << x?

+      last_loop_count = GetContainingLoopCount(code(), block);
+      last_use_count = 0;
+    }
+    if (pos->RegisterIsBeneficial()) last_use_count++;
   }
+  use_count += last_use_count * ipow(2, last_loop_count);

[Jarin, 2015/05/13 13:12:56]

ipow(2, x) --> 1 << x?

 
-  unsigned range_size = GetLiveRangeSize(range);
+  unsigned range_size = GetLiveRangeSize(range, start, end);
   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;
+  return static_cast<float>(use_count) / static_cast<float>(range_size);
 }
 
 
 void GreedyAllocator::Evict(LiveRange* range) {
+  TRACE("Evicting range %d\n", range->id());
   bool removed = allocations_[range->assigned_register()]->Remove(range);
   CHECK(removed);
   range->UnsetUseHints();
@@ -2651,7 +2739,7 @@ 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());
+  TRACE("Enqueuing range %d size %d\n", range->id(), size);
   queue_.push(std::make_pair(size, range));
 }
 
@@ -2680,17 +2768,25 @@ bool GreedyAllocator::HandleSpillOperands(LiveRange* range) {
       return true;
     }
   }
-  return TryReuseSpillForPhi(range);
+  TRACE("Entering TryReuseSpillForPhi with range %d\n", range->id());
+  bool ret = TryReuseSpillForPhi(range);
+  TRACE("Exiting TryReuseSpillForPhi with range %d\n", range->id());
+  return ret;
 }
 
 
 void GreedyAllocator::AllocateRegisters() {
+  stats_.reset();
+  unsigned range_count = 0;
+  TRACE("Begin allocating function %s with the Greedy Allocator\n",
+        data()->debug_name());
   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);
+      range_count++;
     }
   }
 
@@ -2712,23 +2808,21 @@ void GreedyAllocator::AllocateRegisters() {
     auto current_pair = queue_.top();
     queue_.pop();
     auto current = current_pair.second;
+    TRACE("Processing interval %d of size %d\n", current->id(),
+          current_pair.first);
     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);
-      }
+      float this_weight = CalculateSpillWeight(current);
 
       bool evicted = false;
       for (auto* conflict : conflicting) {
-        if (CalculateSpillWeight(conflict) < this_weight) {
+        float conflict_weight = CalculateSpillWeight(conflict);
+        if (conflict_weight < this_weight) {
           Evict(conflict);
           Enqueue(conflict);
           evicted = true;
@@ -2737,11 +2831,19 @@ void GreedyAllocator::AllocateRegisters() {
       if (evicted) {
         conflicting.clear();
         TryAllocate(current, &conflicting);
+        if (conflicting.size() == 0) {
+          stats_.wins++;
+        } else {
+          stats_.losses_after_eviction++;
+        }
+      } else {
+        stats_.losses_no_eviction++;
       }
-      if (!conflicting.empty()) {
+      if (conflicting.size() > 0) {
+        TRACE("Could evict for range %d\n", current->id());
         DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
-        DCHECK(split_pos.IsValid());
-        AllocateBlockedRange(current, split_pos, spill);
+        // DCHECK(split_pos.IsValid());

[Jarin, 2015/05/13 13:12:57]

Remove.

+        AllocateBlockedRange(current, conflicting);
       }
     }
   }
@@ -2751,90 +2853,215 @@ void GreedyAllocator::AllocateRegisters() {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
+  TRACE("End allocating function %s with the Greedy Allocator\n",
+        data()->debug_name());
+  if (FLAG_greedy_stats) {
+    OFStream os(stdout);
+    os << "==================================================" << std::endl;
+    os << "allocation stats for:  " << data()->debug_name() << "(" << mode()
+       << ")" << std::endl;
+    os << "input ranges:          " << range_count << std::endl;
+    os << "input fixed ranges:    " << GetFixedRegisters(data(), mode()).size()
+       << std::endl;
+    os << stats_;
+    os << "==================================================" << std::endl;
+  }
 }
 
 
-LifetimePosition GreedyAllocator::GetSplittablePos(LifetimePosition pos) {
-  auto ret = pos.PrevStart().End();
+LifetimePosition GreedyAllocator::GetCorrectSplitPos(LifetimePosition pos) {
+  LifetimePosition ret;
   if (IsBlockBoundary(code(), pos.Start())) {
     ret = pos.Start();
+  } else {
+    ret = pos.PrevStart().End();
   }
   DCHECK(ret <= pos);
   return ret;
 }
 
-LifetimePosition GreedyAllocator::FindProgressingSplitPosition(
-    LiveRange* range, bool* is_spill_pos) {
+LifetimePosition GreedyAllocator::GetSplittablePos(UsePosition* use_pos,
+                                                   LiveRange* range) {
+  DCHECK(use_pos != nullptr);
   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();
+  auto pos = GetCorrectSplitPos(use_pos->pos());
+  if (start < pos && pos < end) {
+    return pos;
   }
 
-  if (next_reg_use == nullptr) {
-    *is_spill_pos = true;
-    auto ret = FindOptimalSpillingPos(range, start);
-    DCHECK(ret.IsValid());
-    return ret;
+  if (pos >= end) {
+    return LifetimePosition::Invalid();

[Jarin, 2015/05/13 13:12:56]

How can this happen?

   }
 
-  *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;
+  auto after = pos.NextFullStart();
+  if (start < after && after < end) {
+    return after;
   }
+  if (use_pos->next() != nullptr) {
+    return GetSplittablePos(use_pos->next(), range);
+  }
+  return LifetimePosition::Invalid();
+}
 
-  if (correct_pos >= end) {
-    return LifetimePosition::Invalid();
+bool GreedyAllocator::RangeHasSplitOrSpillPosition(LiveRange* range,
+                                                   LifetimePosition start,
+                                                   LifetimePosition end) {
+  UsePosition* next_reg_use = range->first_pos();
+  for (; next_reg_use != nullptr; next_reg_use = next_reg_use->next()) {
+    if (next_reg_use->pos() > end) break;
+    if (next_reg_use->pos() < start) continue;
+    if (next_reg_use->type() == UsePositionType::kRequiresRegister) break;
   }
 
-  // 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;
+  if (next_reg_use == nullptr || next_reg_use->pos() > end) {
+    auto ret = FindOptimalSpillingPos(range, start);
+    CHECK(ret.IsValid());
+    return true;
+  }
+  auto pos = GetCorrectSplitPos(next_reg_use->pos());
+  if (start < pos && pos < end) return true;
+  while (next_reg_use->next() != nullptr &&
+         next_reg_use->pos().NextFullStart() > next_reg_use->next()->pos()) {
     next_reg_use = next_reg_use->next();
   }
+  CHECK(next_reg_use != nullptr);
+  pos = next_reg_use->pos().NextFullStart();
+  if (start < pos && pos < end) return true;

[Jarin, 2015/05/13 13:12:56]

return start < pos && pos < end;

+  return false;
+}
 
-  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;
+bool GreedyAllocator::FindGoodSplitPoint(LiveRange* range,
+                                         const ZoneSet<LiveRange*>& conflicts) {
+  auto start = range->Start();
+  auto end = range->End();
+  end = end.IsInstructionPosition() ? end.End() : end.PrevStart().End();
+  auto pos = LifetimePosition::Invalid();
+  float heaviest = 0.0;
+  stats_.good_split_attempts++;
+
+  bool winner_is_smart = false;
+  bool winner_is_above = false;
+  for (auto conflict : conflicts) {
+    bool upper_is_freed = false;
+    bool using_smart = false;
+    auto first_intersection = range->FirstIntersection(conflict);
+    DCHECK(first_intersection.IsValid());
+    DCHECK(conflict->HasRegisterAssigned());
+    if (first_intersection == start && FLAG_greedy_below) {
+      first_intersection = conflict->End();
+    } else {
+      upper_is_freed = true;
+    }
+    auto corrected_pos = GetCorrectSplitPos(first_intersection);
+    if (start >= corrected_pos || corrected_pos >= end) continue;
+    auto candidate_pos =
+        FLAG_greedy_smart
+            ? (upper_is_freed ? FindOptimalSplitPos(start, corrected_pos)
+                              : FindOptimalSplitPos(corrected_pos, end))
+            : corrected_pos;
+
+    if (start >= candidate_pos || candidate_pos >= end) {
+      if (FLAG_greedy_alternative && start < corrected_pos &&
+          corrected_pos < end) {
+        candidate_pos = corrected_pos;
+      } else {
+        continue;
+      }
+    }
+    using_smart = (candidate_pos != corrected_pos);
+
+    float this_weight = 0.0;
+    if (upper_is_freed) {
+      this_weight = CalculateSpillWeight(range, start, candidate_pos);
+    } else {
+      this_weight = CalculateSpillWeight(range, candidate_pos, end);
+    }
+
+    if (FLAG_greedy_split_longest) {
+      pos = Max(pos, candidate_pos);
+    } else if (this_weight > heaviest) {
+      pos = candidate_pos;
+      heaviest = this_weight;
+      winner_is_smart = using_smart;
+      winner_is_above = upper_is_freed;
     }
-    return LifetimePosition::Invalid();
   }
 
-  correct_pos = GetSplittablePos(next_reg_use->pos());
-  if (start < correct_pos && correct_pos < end) {
-    DCHECK(reference < correct_pos);
-    return correct_pos;
+  if (!pos.IsValid()) {
+    // All registers are blocked.
+    TRACE("All registers are blocked for range %d\n", range->id());
+    return false;
   }
-  return LifetimePosition::Invalid();
+  CHECK(FLAG_greedy_split_longest || heaviest > 0.0);
+
+  // Register reg is available at the range start but becomes blocked before
+  // the range end. Split current at position where it becomes blocked.
+  TRACE("Splitting range %d at position %d where the length is %f", range->id(),
+        pos.value(), heaviest);
+
+  LiveRange* tail = SplitRangeAt(range, pos);
+  CHECK(tail != range);
+  Enqueue(tail);
+  Enqueue(range);
+  if (winner_is_smart) {
+    if (winner_is_above) {
+      stats_.good_split_smart_above++;
+    } else {
+      stats_.good_split_smart_below++;
+    }
+  } else {
+    if (winner_is_above) {
+      stats_.good_split_above++;
+    } else {
+      stats_.good_split_below++;
+    }
+  }
+  stats_.good_split_successes++;
+  return true;
 }
 
+void GreedyAllocator::AllocateBlockedRange(
+    LiveRange* current, const ZoneSet<LiveRange*>& conflicts) {
+  auto start = current->Start();
+  auto end = current->End();
+
+  UsePosition* next_reg_use = current->first_pos();
+  while (next_reg_use != nullptr &&
+         next_reg_use->type() != UsePositionType::kRequiresRegister) {
+    next_reg_use = next_reg_use->next();
+  }
 
-void GreedyAllocator::AllocateBlockedRange(LiveRange* current,
-                                           LifetimePosition pos, bool spill) {
-  auto tail = SplitRangeAt(current, pos);
-  if (spill) {
+  if (next_reg_use == nullptr) {
+    auto pos = FindOptimalSpillingPos(current, start);
+    DCHECK(pos.IsValid());
+    auto tail = SplitRangeAt(current, pos);
     Spill(tail);
-  } else {
-    Enqueue(tail);
+    if (tail != current) {
+      Enqueue(current);
+    }
+    return;
   }
-  if (tail != current) {
-    Enqueue(current);
+
+  if (FindGoodSplitPoint(current, conflicts)) return;
+  auto alternate = GetCorrectSplitPos(next_reg_use->pos());
+  if (start >= alternate || alternate >= end) {
+    auto reg_use_backup = next_reg_use;
+    for (; next_reg_use != nullptr; next_reg_use = next_reg_use->next()) {
+      if (next_reg_use->type() == UsePositionType::kRequiresRegister) {
+        alternate = next_reg_use->pos();
+      }
+    }
+    alternate = alternate.NextStart();
+    if (start >= alternate || alternate >= end) {
+      alternate = GetSplittablePos(reg_use_backup, current);
+      CHECK(alternate.IsValid());
+    }
   }
+  auto tail = SplitRangeAt(current, alternate);
+  Enqueue(tail);
+  Enqueue(current);
 }
 
 
@@ -2860,7 +3087,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();
@@ -3320,6 +3546,7 @@ void LiveRangeConnector::ResolveControlFlow(const InstructionBlock* block,
 
 void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
   DelayedInsertionMap delayed_insertion_map(local_zone);
+  unsigned moves_counter = 0;
   for (auto first_range : data()->live_ranges()) {
     if (first_range == nullptr || first_range->IsChild()) continue;
     for (auto second_range = first_range->next(); second_range != nullptr;
@@ -3351,6 +3578,7 @@ void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
       }
       auto move = code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
           gap_pos, code_zone());
+      moves_counter++;
       if (!delay_insertion) {
         move->AddMove(prev_operand, cur_operand);
       } else {
@@ -3359,6 +3587,10 @@ void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
       }
     }
   }
+  if (FLAG_greedy_stats) {
+    OFStream os(stdout);
+    os << "Moves: " << moves_counter << std::endl;
+  }
   if (delayed_insertion_map.empty()) return;
   // Insert all the moves which should occur after the stored move.
   ZoneVector<MoveOperands*> to_insert(local_zone);
@@ -3390,6 +3622,7 @@ void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
   }
 }
 
+  // #include "../prints.inc"

[Jarin, 2015/05/13 13:12:56]

Remove this line.

 
 }  // namespace compiler
 }  // namespace internal