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) {
+  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());
 }
 
 
 bool IsBlockBoundary(const InstructionSequence* code, LifetimePosition pos) {
   return pos.IsFullStart() &&
          code->GetInstructionBlock(pos.ToInstructionIndex())->code_start() ==
              pos.ToInstructionIndex();
@@ skipping 728 matching lines @@
   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() << " ";
+    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;
 
   while (interval != nullptr) {
     os << '[' << interval->start() << ", " << interval->end() << ')'
        << std::endl;
     interval = interval->next();
   }
   os << "}";
@@ skipping 1027 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();
+  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);
     }
   }
   SortUnhandled();
   DCHECK(UnhandledIsSorted());
 
   auto& fixed_ranges = GetFixedRegisters(data(), mode());
   for (auto current : fixed_ranges) {
     if (current != nullptr) {
       DCHECK_EQ(mode(), current->kind());
@@ skipping 26 matching lines @@
         continue;
       } else if (pos->pos() > current->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.
         SpillBetween(current, current->Start(), pos->pos());
         DCHECK(UnhandledIsSorted());
         continue;
       }
     }
 
-    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];
       if (cur_active->End() <= position) {
         ActiveToHandled(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
       } else if (!cur_active->Covers(position)) {
         ActiveToInactive(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
       }
     }
 
     for (size_t i = 0; i < inactive_live_ranges().size(); ++i) {
       auto cur_inactive = inactive_live_ranges()[i];
       if (cur_inactive->End() <= position) {
         InactiveToHandled(cur_inactive);
         --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);
+    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 {
     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 188 matching lines @@
 
   bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); }
 
   ZoneSplayTree<Config> storage_;
   DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);
 };
 
 
 const std::pair<int, int> CoalescedLiveRanges::Config::kNoKey = {0, 0};
 
+
+std::ostream& operator<<(std::ostream& os, const AllocatorStats& stats) {
+  os << "losses after eviction: " << stats.losses_after_eviction << std::endl;
+  os << "losses, no eviction:   " << stats.losses_no_eviction << std::endl;
+  os << "spills:                " << stats.spills << std::endl;
+  os << "wins:                  " << stats.wins << std::endl;
+  os << "split attempts:        " << stats.good_split_attempts << std::endl;
+  os << "split successes:       " << stats.good_split_successes << std::endl;
+  os << "splits above:          " << stats.good_split_above << std::endl;
+  os << "splits below:          " << stats.good_split_below << std::endl;
+  os << "smart splits above:    " << stats.good_split_smart_above << std::endl;
+  os << "smart splits below:    " << stats.good_split_smart_below << std::endl;
+  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;
+unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range,
+                                           LifetimePosition start,
+                                           LifetimePosition end) {
+  return (end.value() - start.value());
 }
 
 
+unsigned GreedyAllocator::GetLiveRangeSize(LiveRange* range) {
+  return GetLiveRangeSize(range, range->Start(), range->End());
+}
+
+
 void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* 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();
-  }
+  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();
   range->UnsetAssignedRegister();
   if (range->is_phi()) {
     data()->GetPhiMapValueFor(range->id())->UnsetAssignedRegister();
   }
 }
 
 
@@ skipping 83 matching lines @@
     // 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());
+  TRACE("Enqueuing range %d size %d\n", range->id(), size);
   queue_.push(std::make_pair(size, range));
 }
 
 
 bool GreedyAllocator::HandleSpillOperands(LiveRange* range) {
   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);
       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++;
     }
   }
 
   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);
     }
   }
 
   while (!queue_.empty()) {
     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;
         }
       }
       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);
       }
     }
   }
 
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->IsEmpty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
-}
-
-
-LifetimePosition GreedyAllocator::GetSplittablePos(LifetimePosition pos) {
-  auto ret = pos.PrevStart().End();
+  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::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();
 
+  auto pos = GetCorrectSplitPos(use_pos->pos());
+  if (start < pos && pos < end) {
+    return pos;
+  }
+
+  if (pos >= end) {
+    return LifetimePosition::Invalid();

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

How can this happen?

+  }
+
+  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();
+}
+
+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;
+  }
+
+  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;
+}
+
+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;
+    }
+  }
+
+  if (!pos.IsValid()) {
+    // All registers are blocked.
+    TRACE("All registers are blocked for range %d\n", range->id());
+    return false;
+  }
+  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();
   }
 
   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) {
+    auto pos = FindOptimalSpillingPos(current, start);
+    DCHECK(pos.IsValid());
+    auto tail = SplitRangeAt(current, pos);
     Spill(tail);
-  } else {
-    Enqueue(tail);
-  }
-  if (tail != current) {
-    Enqueue(current);
-  }
-}
-
-
+    if (tail != current) {
+      Enqueue(current);
+    }
+    return;
+  }
+
+  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);
+}
+
+
 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;
@@ skipping 439 matching lines @@
                 ->HasReferenceMap());
     gap_index = pred->last_instruction_index();
     position = Instruction::END;
   }
   data()->AddGapMove(gap_index, position, pred_op, cur_op);
 }
 
 
 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;
          first_range = second_range, second_range = second_range->next()) {
       auto pos = second_range->Start();
       // Add gap move if the two live ranges touch and there is no block
       // boundary.
       if (second_range->spilled()) continue;
       if (first_range->End() != pos) continue;
       if (IsBlockBoundary(code(), pos) &&
@@ skipping 11 matching lines @@
       } else {
         if (pos.IsStart()) {
           delay_insertion = true;
         } else {
           gap_index++;
         }
         gap_pos = delay_insertion ? Instruction::END : Instruction::START;
       }
       auto move = code()->InstructionAt(gap_index)->GetOrCreateParallelMove(
           gap_pos, code_zone());
+      moves_counter++;
       if (!delay_insertion) {
         move->AddMove(prev_operand, cur_operand);
       } else {
         delayed_insertion_map.insert(
             std::make_pair(std::make_pair(move, prev_operand), cur_operand));
       }
     }
   }
+  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);
   ZoneVector<MoveOperands*> to_eliminate(local_zone);
   to_insert.reserve(4);
   to_eliminate.reserve(4);
   auto moves = delayed_insertion_map.begin()->first.first;
   for (auto it = delayed_insertion_map.begin();; ++it) {
     bool done = it == delayed_insertion_map.end();
     if (done || it->first.first != moves) {
@@ skipping 11 matching lines @@
       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);
   }
 }
 
+  // #include "../prints.inc"

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

Remove this line.

 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8