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 186 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 637 matching lines @@
       phi_map_(allocation_zone()),
       live_in_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()),
       live_ranges_(code->VirtualRegisterCount() * 2, nullptr,
                    allocation_zone()),
       fixed_live_ranges_(this->config()->num_general_registers(), nullptr,
                          allocation_zone()),
       fixed_double_live_ranges_(this->config()->num_double_registers(), nullptr,
                                 allocation_zone()),
       spill_ranges_(allocation_zone()),
       assigned_registers_(nullptr),
-      assigned_double_registers_(nullptr) {
+      assigned_double_registers_(nullptr),
+      dbgs_(stdout) {
   DCHECK(this->config()->num_general_registers() <=
          RegisterConfiguration::kMaxGeneralRegisters);
   DCHECK(this->config()->num_double_registers() <=
          RegisterConfiguration::kMaxDoubleRegisters);
   spill_ranges().reserve(8);
   assigned_registers_ = new (code_zone())
       BitVector(this->config()->num_general_registers(), code_zone());
   assigned_double_registers_ = new (code_zone())
       BitVector(this->config()->num_aliased_double_registers(), code_zone());
   this->frame()->SetAllocatedRegisters(assigned_registers_);
   this->frame()->SetAllocatedDoubleRegisters(assigned_double_registers_);
 }
 
 
 LiveRange* RegisterAllocationData::LiveRangeFor(int index) {
   if (index >= static_cast<int>(live_ranges().size())) {
     live_ranges().resize(index + 1, nullptr);
   }
   auto result = live_ranges()[index];
   if (result == nullptr) {
     result = NewLiveRange(index);
     live_ranges()[index] = result;
   }
   return result;
 }
 
 
+std::ostream& operator<<(std::ostream& os,

[dcarney, 2015/04/30 06:01:32]

this should come after the live range class functions

[Mircea Trofin, 2015/04/30 18:16:49]

Done.

+                         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;
+}
+
+
 MoveOperands* RegisterAllocationData::AddGapMove(
     int index, Instruction::GapPosition position,
     const InstructionOperand& from, const InstructionOperand& to) {
   auto instr = code()->InstructionAt(index);
   auto moves = instr->GetOrCreateParallelMove(position, code_zone());
   return moves->AddMove(from, to);
 }
 
 
 LiveRange* RegisterAllocationData::NewLiveRange(int index) {
@@ skipping 54 matching lines @@
 void RegisterAllocationData::MarkAllocated(RegisterKind kind, int index) {
   if (kind == DOUBLE_REGISTERS) {
     assigned_double_registers_->Add(index);
   } else {
     DCHECK(kind == GENERAL_REGISTERS);
     assigned_registers_->Add(index);
   }
 }
 
 
+ALLOW_UNUSED_TYPE
+void RegisterAllocationData::Print(Instruction* ins) {
+  dbgs() << ToPrintable(ins) << std::endl;
+}
+
+ALLOW_UNUSED_TYPE
+void RegisterAllocationData::Print(InstructionOperand op) {
+  dbgs() << ToPrintable(op) << std::endl;
+}
+
+ALLOW_UNUSED_TYPE
+void RegisterAllocationData::Print(InstructionSequence* seq) {
+  dbgs() << ToPrintable(seq) << std::endl;
+}
+
+ALLOW_UNUSED_TYPE
+void RegisterAllocationData::Print(LiveRange* range) {
+  dbgs() << ToPrintable(range) << std::endl;
+}
+
+
 ConstraintBuilder::ConstraintBuilder(RegisterAllocationData* data)
     : data_(data) {}
 
 
 InstructionOperand* ConstraintBuilder::AllocateFixed(
     UnallocatedOperand* operand, int pos, bool is_tagged) {
   TRACE("Allocating fixed reg for op %d\n", operand->virtual_register());
   DCHECK(operand->HasFixedPolicy());
   InstructionOperand allocated;
   if (operand->HasFixedSlotPolicy()) {
@@ skipping 1416 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(data()->allocation_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();
+  auto* zone = allocations_.get_allocator().zone();
   for (int i = 0; i < num_registers(); i++) {
     allocations_[i] = new (zone) CoallescedLiveRanges(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;
+    if (HandleSpillOperands(current)) {
+      continue;
+    }
+    bool spill = false;
     ZoneSet<LiveRange*> conflicting(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::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 ret = next_reg_use->pos();
+
+  if (start < ret.Prev()) {
+    return ret.Prev();
+  }
+
+  if (end == ret && start.Next() < end) {
+    return end.Prev();
+  }
+
+  auto blocked_pos = start;
+  while (next_reg_use->next() != nullptr &&
+         next_reg_use->next()->pos().Prev() <= next_reg_use->pos()) {
+    next_reg_use = next_reg_use->next();
+    blocked_pos = next_reg_use->pos();
+    ret = blocked_pos.Next();
+  }
+  DCHECK(next_reg_use != nullptr);
+
+  if (ret < end && start < ret) {
+    return ret;
+  }
+  ret = ret.Next();
+
+  if (ret == blocked_pos) {
+    return LifetimePosition::Invalid();
+  }
+
+  if (ret < end && start < ret) {
+    return ret;
+  }
+
+  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);
+  }
+}
+
+
+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 24 matching lines @@
     InstructionOperand* spill_operand = nullptr;
     if (!range->TopLevel()->HasNoSpillType()) {
       spill_operand = range->TopLevel()->GetSpillOperand();
     }
     auto assigned = range->GetAssignedOperand();
     range->ConvertUsesToOperand(assigned, spill_operand);
     if (range->is_phi()) {
       data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned);
     }
     if (!range->IsChild() && spill_operand != nullptr) {
-      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 352 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