Greedy reg alloc - better splitting

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 207 matching lines @@
 UseInterval* UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
   DCHECK(Contains(pos) && pos != start());
   auto after = new (zone) UseInterval(pos, end_);
   after->next_ = next_;
   next_ = nullptr;
   end_ = pos;
   return after;
 }
 
 
+std::ostream& operator<<(std::ostream& os, const LifetimePosition pos) {
+  os << '@' << pos.ToInstructionIndex();
+  if (pos.IsGapPosition()) {
+    os << 'g';
+  } else {
+    os << 'i';
+  }
+  if (pos.IsStart()) {
+    os << 's';
+  } else {
+    os << 'e';
+  }
+  return os;
+}
+
+
 struct LiveRange::SpillAtDefinitionList : ZoneObject {
   SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
                         SpillAtDefinitionList* next)
       : gap_index(gap_index), operand(operand), next(next) {}
   const int gap_index;
   InstructionOperand* const operand;
   SpillAtDefinitionList* const next;
 };
 
 
@@ skipping 521 matching lines @@
       if (interval2->end() > interval1->start()) {
         return true;
       }
       interval2 = interval2->next();
     }
   }
   return false;
 }
 
 
+std::ostream& operator<<(std::ostream& os,
+                         const PrintableLiveRange& printable_range) {
+  const LiveRange* range = printable_range.range_;
+  os << "Range: " << range->id() << " ";
+  if (range->is_phi()) os << "phi ";
+  if (range->is_non_loop_phi()) os << "nlphi ";
+
+  os << "{" << std::endl;
+  auto interval = range->first_interval();
+  auto use_pos = range->first_pos();
+  PrintableInstructionOperand pio;
+  pio.register_configuration_ = printable_range.register_configuration_;
+  while (use_pos != nullptr) {
+    pio.op_ = *use_pos->operand();
+    os << pio << use_pos->pos() << " ";
+    use_pos = use_pos->next();
+  }
+  os << std::endl;
+
+  while (interval != nullptr) {
+    os << '[' << interval->start() << ", " << interval->end() << ')'
+       << std::endl;
+    interval = interval->next();
+  }
+  os << "}";
+  return os;
+}
+
+
 SpillRange::SpillRange(LiveRange* parent, Zone* zone)
     : live_ranges_(zone), assigned_slot_(kUnassignedSlot) {
   DCHECK(!parent->IsChild());
   UseInterval* result = nullptr;
   UseInterval* node = nullptr;
   // Copy the intervals for all ranges.
   for (auto range = parent; range != nullptr; range = range->next()) {
     auto src = range->first_interval();
     while (src != nullptr) {
       auto new_node = new (zone) UseInterval(src->start(), src->end());
@@ skipping 1567 matching lines @@
     Spill(second_part);
     AddToUnhandledSorted(third_part);
   } else {
     // The split result does not intersect with [start, end[.
     // Nothing to spill. Just put it to unhandled as whole.
     AddToUnhandledSorted(second_part);
   }
 }
 
 
-class CoallescedLiveRanges : public ZoneObject {
+class CoalescedLiveRanges : public ZoneObject {
  public:
-  explicit CoallescedLiveRanges(Zone* zone) : storage_(zone) {}
+  explicit CoalescedLiveRanges(Zone* zone) : storage_(zone) {}
 
   LiveRange* Find(UseInterval* query) {
     ZoneSplayTree<Config>::Locator locator;
 
     if (storage_.Find(GetKey(query), &locator)) {
       return locator.value();
     }
     return nullptr;
   }
 
@@ skipping 43 matching lines @@
   bool Insert(UseInterval* interval, LiveRange* range) {
     ZoneSplayTree<Config>::Locator locator;
     bool ret = storage_.Insert(GetKey(interval), &locator);
     if (ret) locator.set_value(range);
     return ret;
   }
 
   bool Remove(UseInterval* key) { return storage_.Remove(GetKey(key)); }
 
   ZoneSplayTree<Config> storage_;
-  DISALLOW_COPY_AND_ASSIGN(CoallescedLiveRanges);
+  DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);
 };
 
 
-const std::pair<int, int> CoallescedLiveRanges::Config::kNoKey = {0, 0};
+const std::pair<int, int> CoalescedLiveRanges::Config::kNoKey = {0, 0};
 
 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) {
@@ skipping 13 matching lines @@
   }
   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();
 
-  int hint_register;
-  if (range->FirstHintPosition(&hint_register) != nullptr) {
-    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();
   }
 
-  // GetLiveRangeSize is DCHECK-ed to not be 0
   unsigned range_size = GetLiveRangeSize(range);
   DCHECK_NE(0U, range_size);
 
-  return static_cast<float>(use_count) / static_cast<float>(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;
@@ skipping 22 matching lines @@
       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->HasSpillOperand()) {
-    Spill(current);
-    return true;
-  }
   if (current->IsFixed()) {
     return TryAllocatePhysicalRegister(current->assigned_register(), current,
                                        conflicting);
   }
 
-  if (current->HasRegisterAssigned()) {
-    int reg_id = current->assigned_register();
-    return TryAllocatePhysicalRegister(reg_id, 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 (TryAllocatePhysicalRegister(candidate_reg, current, conflicting)) {
+    if (hinted_reg_id >= 0 &&
+        candidate_reg == static_cast<size_t>(hinted_reg_id))
+      continue;
+    local_conflicts.clear();
+    if (TryAllocatePhysicalRegister(candidate_reg, current, &local_conflicts)) {
       conflicting->clear();
       return true;
+    } else {
+      conflicting->insert(local_conflicts.begin(), local_conflicts.end());
     }
   }
   return false;
 }
 
+
 LiveRange* GreedyAllocator::SpillBetweenUntil(LiveRange* range,
                                               LifetimePosition start,
                                               LifetimePosition until,
                                               LifetimePosition end) {
   CHECK(start < end);
   auto second_part = SplitRangeAt(range, start);
 
   if (second_part->Start() < end) {
     // The split result intersects with [start, end[.
     // Split it at position between ]start+1, end[, spill the middle part
@@ skipping 13 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());
   queue_.push(std::make_pair(size, range));
 }
 
 
-// TODO(mtrofin): consolidate with identical code segment in
-// LinearScanAllocator::AllocateRegisters
 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 false;
-  // TODO(mtrofin): Do we need this?
-  // return (TryReuseSpillForPhi(range));
+  return TryReuseSpillForPhi(range);
 }
 
 
 void GreedyAllocator::AllocateRegisters() {
   for (auto range : data()->live_ranges()) {
     if (range == nullptr) continue;
     if (range->kind() == mode()) {
       DCHECK(!range->HasRegisterAssigned() && !range->spilled());
       TRACE("Enqueueing live range %d to priority queue \n", range->id());
       Enqueue(range);
     }
   }
 
   allocations_.resize(num_registers());
-  auto* zone = data()->allocation_zone();
   for (int i = 0; i < num_registers(); i++) {
-    allocations_[i] = new (zone) CoallescedLiveRanges(zone);
+    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;
-    if (HandleSpillOperands(current)) continue;
-    ZoneSet<LiveRange*> conflicting(zone);
+    if (HandleSpillOperands(current)) {
+      continue;
+    }
+    bool spill = false;
+    ZoneSet<LiveRange*> conflicting(local_zone());
     if (!TryAllocate(current, &conflicting)) {
       DCHECK(!conflicting.empty());
-      float this_max = CalculateSpillWeight(current);
-      float max_conflicting = CalculateMaxSpillWeight(conflicting);
-      if (max_conflicting < this_max) {
-        for (auto* conflict : conflicting) {
+      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();
-        bool allocated = TryAllocate(current, &conflicting);
-        CHECK(allocated);
-        DCHECK(conflicting.empty());
-      } else {
+        TryAllocate(current, &conflicting);
+      }
+      if (!conflicting.empty()) {
         DCHECK(!current->IsFixed() || current->CanBeSpilled(current->Start()));
-        bool allocated = AllocateBlockedRange(current, conflicting);
-        CHECK(allocated);
+        DCHECK(split_pos.IsValid());
+        AllocateBlockedRange(current, split_pos, spill);
       }
     }
   }
 
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->IsEmpty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
     }
   }
 }
 
 
-bool GreedyAllocator::AllocateBlockedRange(
-    LiveRange* current, const ZoneSet<LiveRange*>& conflicts) {
-  auto register_use = current->NextRegisterPosition(current->Start());
-  if (register_use == nullptr) {
-    // There is no use in the current live range that requires a register.
-    // We can just spill it.
-    Spill(current);
-    return true;
+LifetimePosition GreedyAllocator::GetSplittablePos(LifetimePosition pos) {
+  auto ret = pos.PrevStart().End();
+  if (IsBlockBoundary(code(), pos.Start())) {
+    ret = pos.Start();
+  }
+  DCHECK(ret <= pos);
+  return ret;
+}
+
+LifetimePosition GreedyAllocator::FindProgressingSplitPosition(
+    LiveRange* range, bool* is_spill_pos) {
+  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 second_part = SplitRangeAt(current, register_use->pos());
-  Spill(second_part);
+  if (next_reg_use == nullptr) {
+    *is_spill_pos = true;
+    auto ret = FindOptimalSpillingPos(range, start);
+    DCHECK(ret.IsValid());
+    return ret;
+  }
 
-  return true;
+  *is_spill_pos = false;
+  auto reg_pos = next_reg_use->pos();
+  auto correct_pos = GetSplittablePos(reg_pos);
+  if (start < correct_pos && correct_pos < end) {
+    return correct_pos;
+  }
+
+  if (correct_pos >= end) {
+    return LifetimePosition::Invalid();
+  }
+
+  // Correct_pos must be at or before start. Find the next use position.
+  next_reg_use = next_reg_use->next();
+  auto reference = reg_pos;
+  while (next_reg_use != nullptr) {
+    auto pos = next_reg_use->pos();
+    // Skip over tight successive uses.
+    if (reference.NextStart() < pos) {
+      break;
+    }
+    reference = pos;
+    next_reg_use = next_reg_use->next();
+  }
+
+  if (next_reg_use == nullptr) {
+    // While there may not be another use, we may still have space in the range
+    // to clip off.
+    correct_pos = reference.NextStart();
+    if (start < correct_pos && correct_pos < end) {
+      return correct_pos;
+    }
+    return LifetimePosition::Invalid();
+  }
+
+  correct_pos = GetSplittablePos(next_reg_use->pos());
+  if (start < correct_pos && correct_pos < end) {
+    DCHECK(reference < correct_pos);
+    return correct_pos;
+  }
+  return LifetimePosition::Invalid();
 }
 
 
+void GreedyAllocator::AllocateBlockedRange(LiveRange* current,
+                                           LifetimePosition pos, bool spill) {
+  auto tail = SplitRangeAt(current, pos);
+  if (spill) {
+    Spill(tail);
+  } else {
+    Enqueue(tail);
+  }
+  if (tail != current) {
+    Enqueue(current);
+  }
+}
+
+
 SpillSlotLocator::SpillSlotLocator(RegisterAllocationData* data)
     : data_(data) {}
 
 
 void SpillSlotLocator::LocateSpillSlots() {
   auto code = data()->code();
   for (auto range : data()->live_ranges()) {
     if (range == nullptr || range->IsEmpty() || range->IsChild()) continue;
     // We care only about ranges which spill in the frame.
     if (!range->HasSpillRange()) continue;
     auto spills = range->spills_at_definition();
     DCHECK_NOT_NULL(spills);
     for (; spills != nullptr; spills = spills->next) {
       code->GetInstructionBlock(spills->gap_index)->mark_needs_frame();
     }
   }
 }
 
 
+bool GreedyAllocator::TryReuseSpillForPhi(LiveRange* range) {
+  if (range->IsChild() || !range->is_phi()) return false;
+  DCHECK(!range->HasSpillOperand());
+
+  auto phi_map_value = data()->GetPhiMapValueFor(range->id());
+  auto phi = phi_map_value->phi();
+  auto block = phi_map_value->block();
+  // Count the number of spilled operands.
+  size_t spilled_count = 0;
+  LiveRange* first_op = nullptr;
+  for (size_t i = 0; i < phi->operands().size(); i++) {
+    int op = phi->operands()[i];
+    LiveRange* op_range = LiveRangeFor(op);
+    if (!op_range->HasSpillRange()) continue;
+    auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
+    auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
+        pred->last_instruction_index());
+    while (op_range != nullptr && !op_range->CanCover(pred_end)) {
+      op_range = op_range->next();
+    }
+    if (op_range != nullptr && op_range->spilled()) {
+      spilled_count++;
+      if (first_op == nullptr) {
+        first_op = op_range->TopLevel();
+      }
+    }
+  }
+
+  // Only continue if more than half of the operands are spilled.
+  if (spilled_count * 2 <= phi->operands().size()) {
+    return false;
+  }
+
+  // Try to merge the spilled operands and count the number of merged spilled
+  // operands.
+  DCHECK(first_op != nullptr);
+  auto first_op_spill = first_op->GetSpillRange();
+  size_t num_merged = 1;
+  for (size_t i = 1; i < phi->operands().size(); i++) {
+    int op = phi->operands()[i];
+    auto op_range = LiveRangeFor(op);
+    if (!op_range->HasSpillRange()) continue;
+    auto op_spill = op_range->GetSpillRange();
+    if (op_spill == first_op_spill || first_op_spill->TryMerge(op_spill)) {
+      num_merged++;
+    }
+  }
+
+  // Only continue if enough operands could be merged to the
+  // same spill slot.
+  if (num_merged * 2 <= phi->operands().size() ||
+      AreUseIntervalsIntersecting(first_op_spill->interval(),
+                                  range->first_interval())) {
+    return false;
+  }
+
+  // If the range does not need register soon, spill it to the merged
+  // spill range.
+  auto next_pos = range->Start();
+  if (next_pos.IsGapPosition()) next_pos = next_pos.NextStart();
+  auto pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
+  if (pos == nullptr) {
+    auto spill_range =
+        range->TopLevel()->HasSpillRange()
+            ? range->TopLevel()->GetSpillRange()
+            : data()->AssignSpillRangeToLiveRange(range->TopLevel());
+    bool merged = first_op_spill->TryMerge(spill_range);
+    CHECK(merged);
+    Spill(range);
+    return true;
+  } else if (pos->pos() > range->Start().NextStart()) {
+    auto spill_range =
+        range->TopLevel()->HasSpillRange()
+            ? range->TopLevel()->GetSpillRange()
+            : data()->AssignSpillRangeToLiveRange(range->TopLevel());
+    bool merged = first_op_spill->TryMerge(spill_range);
+    CHECK(merged);
+    Enqueue(
+        SpillBetweenUntil(range, range->Start(), range->Start(), pos->pos()));
+    return true;
+  }
+  return false;
+}
+
+
 OperandAssigner::OperandAssigner(RegisterAllocationData* data) : data_(data) {}
 
 
 void OperandAssigner::AssignSpillSlots() {
   auto& spill_ranges = data()->spill_ranges();
   // Merge disjoint spill ranges
   for (size_t i = 0; i < spill_ranges.size(); i++) {
     auto range = spill_ranges[i];
     if (range->IsEmpty()) continue;
     for (size_t j = i + 1; j < spill_ranges.size(); j++) {
@@ skipping 22 matching lines @@
       spill_operand = *range->TopLevel()->GetSpillOperand();
     } else if (range->TopLevel()->HasSpillRange()) {
       spill_operand = range->TopLevel()->GetSpillRangeOperand();
     }
     auto assigned = range->GetAssignedOperand();
     range->ConvertUsesToOperand(assigned, spill_operand);
     if (range->is_phi()) {
       data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned);
     }
     if (!range->IsChild() && !spill_operand.IsInvalid()) {
-      range->CommitSpillsAtDefinition(data()->code(), spill_operand,
-                                      range->has_slot_use());
+      range->CommitSpillsAtDefinition(
+          data()->code(), spill_operand,
+          range->has_slot_use() || range->spilled());
     }
   }
 }
 
 
 ReferenceMapPopulator::ReferenceMapPopulator(RegisterAllocationData* data)
     : data_(data) {}
 
 
 bool ReferenceMapPopulator::SafePointsAreInOrder() const {
@@ skipping 387 matching lines @@
     auto eliminate = moves->PrepareInsertAfter(move);
     to_insert.push_back(move);
     if (eliminate != nullptr) to_eliminate.push_back(eliminate);
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8