[turbofan] Retiring Greedy Allocator

src/compiler/greedy-allocator.cc

-// Copyright 2015 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/compiler/greedy-allocator.h"
-#include "src/compiler/register-allocator.h"
-
-namespace v8 {
-namespace internal {
-namespace compiler {
-
-
-#define TRACE(...)                             \
-  do {                                         \
-    if (FLAG_trace_alloc) PrintF(__VA_ARGS__); \
-  } while (false)
-
-
-const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;
-
-
-namespace {
-
-void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
-  int reg_id = range->assigned_register();
-  range->SetUseHints(reg_id);
-  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
-    data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
-  }
-}
-
-
-void UnsetOperands(LiveRange* range, RegisterAllocationData* data) {
-  range->UnsetUseHints();
-  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
-    data->GetPhiMapValueFor(range->TopLevel())->UnsetAssignedRegister();
-  }
-}
-
-
-LiveRange* Split(LiveRange* range, RegisterAllocationData* data,
-                 LifetimePosition pos) {
-  DCHECK(range->Start() < pos && pos < range->End());
-  DCHECK(pos.IsStart() || pos.IsGapPosition() ||
-         (data->code()
-              ->GetInstructionBlock(pos.ToInstructionIndex())
-              ->last_instruction_index() != pos.ToInstructionIndex()));
-  LiveRange* result = range->SplitAt(pos, data->allocation_zone());
-  return result;
-}
-
-
-}  // namespace
-
-
-AllocationCandidate AllocationScheduler::GetNext() {
-  DCHECK(!queue_.empty());
-  AllocationCandidate ret = queue_.top();
-  queue_.pop();
-  return ret;
-}
-
-
-void AllocationScheduler::Schedule(LiveRange* range) {
-  TRACE("Scheduling live range %d:%d.\n", range->TopLevel()->vreg(),
-        range->relative_id());
-  queue_.push(AllocationCandidate(range));
-}
-
-
-void AllocationScheduler::Schedule(LiveRangeGroup* group) {
-  queue_.push(AllocationCandidate(group));
-}
-
-GreedyAllocator::GreedyAllocator(RegisterAllocationData* data,
-                                 RegisterKind kind, Zone* local_zone)
-    : RegisterAllocator(data, kind),
-      local_zone_(local_zone),
-      allocations_(local_zone),
-      scheduler_(local_zone),
-      groups_(local_zone) {}
-
-
-void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
-  TRACE("Assigning register %s to live range %d:%d\n", RegisterName(reg_id),
-        range->TopLevel()->vreg(), range->relative_id());
-
-  DCHECK(!range->HasRegisterAssigned());
-
-  AllocateRegisterToRange(reg_id, range);
-
-  TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
-        range->TopLevel()->vreg(), range->relative_id());
-  range->set_assigned_register(reg_id);
-  UpdateOperands(range, data());
-}
-
-
-void GreedyAllocator::PreallocateFixedRanges() {
-  allocations_.resize(num_registers());
-  for (int i = 0; i < num_registers(); i++) {
-    allocations_[i] = new (local_zone()) CoalescedLiveRanges(local_zone());
-  }
-
-  for (LiveRange* fixed_range : GetFixedRegisters()) {
-    if (fixed_range != nullptr) {
-      DCHECK_EQ(mode(), fixed_range->kind());
-      DCHECK(fixed_range->TopLevel()->IsFixed());
-
-      int reg_nr = fixed_range->assigned_register();
-      EnsureValidRangeWeight(fixed_range);
-      AllocateRegisterToRange(reg_nr, fixed_range);
-    }
-  }
-}
-
-
-void GreedyAllocator::GroupLiveRanges() {
-  CoalescedLiveRanges grouper(local_zone());
-  for (TopLevelLiveRange* range : data()->live_ranges()) {
-    grouper.clear();
-    // Skip splinters, because we do not want to optimize for them, and moves
-    // due to assigning them to different registers occur in deferred blocks.
-    if (!CanProcessRange(range) || range->IsSplinter() || !range->is_phi()) {
-      continue;
-    }
-
-    // A phi can't be a memory operand, so it couldn't have been split.
-    DCHECK(!range->spilled());
-
-    // Maybe this phi range is itself an input to another phi which was already
-    // processed.
-    LiveRangeGroup* latest_grp = range->group() != nullptr
-                                     ? range->group()
-                                     : new (local_zone())
-                                           LiveRangeGroup(local_zone());
-
-    // Populate the grouper.
-    if (range->group() == nullptr) {
-      grouper.AllocateRange(range);
-    } else {
-      for (LiveRange* member : range->group()->ranges()) {
-        grouper.AllocateRange(member);
-      }
-    }
-    for (int j : data()->GetPhiMapValueFor(range)->phi()->operands()) {
-      // skip output also in input, which may happen for loops.
-      if (j == range->vreg()) continue;
-
-      TopLevelLiveRange* other_top = data()->live_ranges()[j];
-
-      if (other_top->IsSplinter()) continue;
-      // If the other was a memory operand, it might have been split.
-      // So get the unsplit part.
-      LiveRange* other =
-          other_top->next() == nullptr ? other_top : other_top->next();
-
-      if (other->spilled()) continue;
-
-      LiveRangeGroup* other_group = other->group();
-      if (other_group != nullptr) {
-        bool can_merge = true;
-        for (LiveRange* member : other_group->ranges()) {
-          if (grouper.GetConflicts(member).Current() != nullptr) {
-            can_merge = false;
-            break;
-          }
-        }
-        // If each member doesn't conflict with the current group, then since
-        // the members don't conflict with eachother either, we can merge them.
-        if (can_merge) {
-          latest_grp->ranges().insert(latest_grp->ranges().end(),
-                                      other_group->ranges().begin(),
-                                      other_group->ranges().end());
-          for (LiveRange* member : other_group->ranges()) {
-            grouper.AllocateRange(member);
-            member->set_group(latest_grp);
-          }
-          // Clear the other range, so we avoid scheduling it.
-          other_group->ranges().clear();
-        }
-      } else if (grouper.GetConflicts(other).Current() == nullptr) {
-        grouper.AllocateRange(other);
-        latest_grp->ranges().push_back(other);
-        other->set_group(latest_grp);
-      }
-    }
-
-    if (latest_grp->ranges().size() > 0 && range->group() == nullptr) {
-      latest_grp->ranges().push_back(range);
-      DCHECK(latest_grp->ranges().size() > 1);
-      groups().push_back(latest_grp);
-      range->set_group(latest_grp);
-    }
-  }
-}
-
-
-void GreedyAllocator::ScheduleAllocationCandidates() {
-  for (LiveRangeGroup* group : groups()) {
-    if (group->ranges().size() > 0) {
-      // We shouldn't have added single-range groups.
-      DCHECK(group->ranges().size() != 1);
-      scheduler().Schedule(group);
-    }
-  }
-  for (LiveRange* range : data()->live_ranges()) {
-    if (CanProcessRange(range)) {
-      for (LiveRange* child = range; child != nullptr; child = child->next()) {
-        if (!child->spilled() && child->group() == nullptr) {
-          scheduler().Schedule(child);
-        }
-      }
-    }
-  }
-}
-
-
-void GreedyAllocator::TryAllocateCandidate(
-    const AllocationCandidate& candidate) {
-  if (candidate.is_group()) {
-    TryAllocateGroup(candidate.group());
-  } else {
-    TryAllocateLiveRange(candidate.live_range());
-  }
-}
-
-
-void GreedyAllocator::TryAllocateGroup(LiveRangeGroup* group) {
-  float group_weight = 0.0;
-  for (LiveRange* member : group->ranges()) {
-    EnsureValidRangeWeight(member);
-    group_weight = Max(group_weight, member->weight());
-  }
-
-  float eviction_weight = group_weight;
-  int eviction_reg = -1;
-  int free_reg = -1;
-  for (int i = 0; i < num_allocatable_registers(); ++i) {
-    int reg = allocatable_register_code(i);
-    float weight = GetMaximumConflictingWeight(reg, group, group_weight);
-    if (weight == LiveRange::kInvalidWeight) {
-      free_reg = reg;
-      break;
-    }
-    if (weight < eviction_weight) {
-      eviction_weight = weight;
-      eviction_reg = reg;
-    }
-  }
-  if (eviction_reg < 0 && free_reg < 0) {
-    for (LiveRange* member : group->ranges()) {
-      scheduler().Schedule(member);
-    }
-    return;
-  }
-  if (free_reg < 0) {
-    DCHECK(eviction_reg >= 0);
-    for (LiveRange* member : group->ranges()) {
-      EvictAndRescheduleConflicts(eviction_reg, member);
-    }
-    free_reg = eviction_reg;
-  }
-
-  DCHECK(free_reg >= 0);
-  for (LiveRange* member : group->ranges()) {
-    AssignRangeToRegister(free_reg, member);
-  }
-}
-
-
-void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
-  // TODO(mtrofin): once we introduce groups, we'll want to first try and
-  // allocate at the preferred register.
-  TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
-        range->relative_id());
-  int free_reg = -1;
-  int evictable_reg = -1;
-  int hinted_reg = -1;
-
-  EnsureValidRangeWeight(range);
-  float competing_weight = range->weight();
-  DCHECK(competing_weight != LiveRange::kInvalidWeight);
-
-  // Can we allocate at the hinted register?
-  if (range->FirstHintPosition(&hinted_reg) != nullptr) {
-    DCHECK(hinted_reg >= 0);
-    float max_conflict_weight =
-        GetMaximumConflictingWeight(hinted_reg, range, competing_weight);
-    if (max_conflict_weight == LiveRange::kInvalidWeight) {
-      free_reg = hinted_reg;
-    } else if (max_conflict_weight < range->weight()) {
-      evictable_reg = hinted_reg;
-    }
-  }
-
-  if (free_reg < 0 && evictable_reg < 0) {
-    // There was no hinted reg, or we cannot allocate there.
-    float smallest_weight = LiveRange::kMaxWeight;
-
-    // Seek either the first free register, or, from the set of registers
-    // where the maximum conflict is lower than the candidate's weight, the one
-    // with the smallest such weight.
-    for (int i = 0; i < num_allocatable_registers(); i++) {
-      int reg = allocatable_register_code(i);
-      // Skip unnecessarily re-visiting the hinted register, if any.
-      if (reg == hinted_reg) continue;
-      float max_conflict_weight =
-          GetMaximumConflictingWeight(reg, range, competing_weight);
-      if (max_conflict_weight == LiveRange::kInvalidWeight) {
-        free_reg = reg;
-        break;
-      }
-      if (max_conflict_weight < range->weight() &&
-          max_conflict_weight < smallest_weight) {
-        smallest_weight = max_conflict_weight;
-        evictable_reg = reg;
-      }
-    }
-  }
-
-  // We have a free register, so we use it.
-  if (free_reg >= 0) {
-    TRACE("Found free register %s for live range %d:%d.\n",
-          RegisterName(free_reg), range->TopLevel()->vreg(),
-          range->relative_id());
-    AssignRangeToRegister(free_reg, range);
-    return;
-  }
-
-  // We found a register to perform evictions, so we evict and allocate our
-  // candidate.
-  if (evictable_reg >= 0) {
-    TRACE("Found evictable register %s for live range %d:%d.\n",
-          RegisterName(free_reg), range->TopLevel()->vreg(),
-          range->relative_id());
-    EvictAndRescheduleConflicts(evictable_reg, range);
-    AssignRangeToRegister(evictable_reg, range);
-    return;
-  }
-
-  // The range needs to be split or spilled.
-  SplitOrSpillBlockedRange(range);
-}
-
-
-void GreedyAllocator::EvictAndRescheduleConflicts(unsigned reg_id,
-                                                  const LiveRange* range) {
-  auto conflicts = current_allocations(reg_id)->GetConflicts(range);
-  for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
-       conflict = conflicts.RemoveCurrentAndGetNext()) {
-    DCHECK(conflict->HasRegisterAssigned());
-    CHECK(!conflict->TopLevel()->IsFixed());
-    conflict->UnsetAssignedRegister();
-    UnsetOperands(conflict, data());
-    UpdateWeightAtEviction(conflict);
-    scheduler().Schedule(conflict);
-    TRACE("Evicted range %d%d.\n", conflict->TopLevel()->vreg(),
-          conflict->relative_id());
-  }
-}
-
-
-void GreedyAllocator::AllocateRegisters() {
-  CHECK(scheduler().empty());
-  CHECK(allocations_.empty());
-
-  TRACE("Begin allocating function %s with the Greedy Allocator\n",
-        data()->debug_name());
-
-  SplitAndSpillRangesDefinedByMemoryOperand(true);
-  GroupLiveRanges();
-  ScheduleAllocationCandidates();
-  PreallocateFixedRanges();
-  while (!scheduler().empty()) {
-    AllocationCandidate candidate = scheduler().GetNext();
-    TryAllocateCandidate(candidate);
-  }
-
-  for (size_t i = 0; i < allocations_.size(); ++i) {
-    if (!allocations_[i]->empty()) {
-      data()->MarkAllocated(mode(), static_cast<int>(i));
-    }
-  }
-  allocations_.clear();
-
-  TryReuseSpillRangesForGroups();
-
-  TRACE("End allocating function %s with the Greedy Allocator\n",
-        data()->debug_name());
-}
-
-
-void GreedyAllocator::TryReuseSpillRangesForGroups() {
-  for (TopLevelLiveRange* top : data()->live_ranges()) {
-    if (!CanProcessRange(top) || !top->is_phi() || top->group() == nullptr) {
-      continue;
-    }
-
-    SpillRange* spill_range = nullptr;
-    for (LiveRange* member : top->group()->ranges()) {
-      if (!member->TopLevel()->HasSpillRange()) continue;
-      SpillRange* member_range = member->TopLevel()->GetSpillRange();
-      if (spill_range == nullptr) {
-        spill_range = member_range;
-      } else {
-        // This may not always succeed, because we group non-conflicting ranges
-        // that may have been splintered, and the splinters may cause conflicts
-        // in the spill ranges.
-        // TODO(mtrofin): should the splinters own their own spill ranges?
-        spill_range->TryMerge(member_range);
-      }
-    }
-  }
-}
-
-
-float GreedyAllocator::GetMaximumConflictingWeight(
-    unsigned reg_id, const LiveRange* range, float competing_weight) const {
-  float ret = LiveRange::kInvalidWeight;
-
-  auto conflicts = current_allocations(reg_id)->GetConflicts(range);
-  for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
-       conflict = conflicts.GetNext()) {
-    DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
-    if (competing_weight <= conflict->weight()) return LiveRange::kMaxWeight;
-    ret = Max(ret, conflict->weight());
-    DCHECK(ret < LiveRange::kMaxWeight);
-  }
-
-  return ret;
-}
-
-
-float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
-                                                   const LiveRangeGroup* group,
-                                                   float group_weight) const {
-  float ret = LiveRange::kInvalidWeight;
-
-  for (LiveRange* member : group->ranges()) {
-    float member_conflict_weight =
-        GetMaximumConflictingWeight(reg_id, member, group_weight);
-    if (member_conflict_weight == LiveRange::kMaxWeight) {
-      return LiveRange::kMaxWeight;
-    }
-    if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
-    ret = Max(member_conflict_weight, ret);
-  }
-
-  return ret;
-}
-
-
-void GreedyAllocator::EnsureValidRangeWeight(LiveRange* range) {
-  // The live range weight will be invalidated when ranges are created or split.
-  // Otherwise, it is consistently updated when the range is allocated or
-  // unallocated.
-  if (range->weight() != LiveRange::kInvalidWeight) return;
-
-  if (range->TopLevel()->IsFixed()) {
-    range->set_weight(LiveRange::kMaxWeight);
-    return;
-  }
-  if (!IsProgressPossible(range)) {
-    range->set_weight(LiveRange::kMaxWeight);
-    return;
-  }
-
-  float use_count = 0.0;
-  for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
-    ++use_count;
-  }
-  range->set_weight(use_count / static_cast<float>(range->GetSize()));
-}
-
-
-void GreedyAllocator::SpillRangeAsLastResort(LiveRange* range) {
-  LifetimePosition start = range->Start();
-  CHECK(range->CanBeSpilled(start));
-
-  DCHECK(range->NextRegisterPosition(start) == nullptr);
-  Spill(range);
-}
-
-
-LiveRange* GreedyAllocator::GetRemainderAfterSplittingAroundFirstCall(
-    LiveRange* range) {
-  LiveRange* ret = range;
-  for (UseInterval* interval = range->first_interval(); interval != nullptr;
-       interval = interval->next()) {
-    LifetimePosition start = interval->start();
-    LifetimePosition end = interval->end();
-    // If the interval starts at instruction end, then the first instruction
-    // in the interval is the next one.
-    int first_full_instruction = (start.IsGapPosition() || start.IsStart())
-                                     ? start.ToInstructionIndex()
-                                     : start.ToInstructionIndex() + 1;
-    // If the interval ends in a gap or at instruction start, then the last
-    // instruction is the previous one.
-    int last_full_instruction = (end.IsGapPosition() || end.IsStart())
-                                    ? end.ToInstructionIndex() - 1
-                                    : end.ToInstructionIndex();
-
-    for (int instruction_index = first_full_instruction;
-         instruction_index <= last_full_instruction; ++instruction_index) {
-      if (!code()->InstructionAt(instruction_index)->IsCall()) continue;
-
-      LifetimePosition before =
-          GetSplitPositionForInstruction(range, instruction_index);
-      LiveRange* second_part =
-          before.IsValid() ? Split(range, data(), before) : range;
-
-      if (range != second_part) scheduler().Schedule(range);
-
-      LifetimePosition after =
-          FindSplitPositionAfterCall(second_part, instruction_index);
-
-      if (after.IsValid()) {
-        ret = Split(second_part, data(), after);
-      } else {
-        ret = nullptr;
-      }
-      Spill(second_part);
-      return ret;
-    }
-  }
-  return ret;
-}
-
-
-bool GreedyAllocator::TrySplitAroundCalls(LiveRange* range) {
-  bool modified = false;
-
-  while (range != nullptr) {
-    LiveRange* remainder = GetRemainderAfterSplittingAroundFirstCall(range);
-    // If we performed no modification, we're done.
-    if (remainder == range) {
-      break;
-    }
-    // We performed a modification.
-    modified = true;
-    range = remainder;
-  }
-  // If we have a remainder and we made modifications, it means the remainder
-  // has no calls and we should schedule it for further processing. If we made
-  // no modifications, we will just return false, because we want the algorithm
-  // to make progress by trying some other heuristic.
-  if (modified && range != nullptr) {
-    DCHECK(!range->spilled());
-    DCHECK(!range->HasRegisterAssigned());
-    scheduler().Schedule(range);
-  }
-  return modified;
-}
-
-
-LifetimePosition GreedyAllocator::FindSplitPositionAfterCall(
-    const LiveRange* range, int call_index) {
-  LifetimePosition after_call =
-      Max(range->Start(),
-          LifetimePosition::GapFromInstructionIndex(call_index + 1));
-  UsePosition* next_use = range->NextRegisterPosition(after_call);
-  if (!next_use) return LifetimePosition::Invalid();
-
-  LifetimePosition split_pos = FindOptimalSplitPos(after_call, next_use->pos());
-  split_pos =
-      GetSplitPositionForInstruction(range, split_pos.ToInstructionIndex());
-  return split_pos;
-}
-
-
-LifetimePosition GreedyAllocator::FindSplitPositionBeforeLoops(
-    LiveRange* range) {
-  LifetimePosition end = range->End();
-  if (end.ToInstructionIndex() >= code()->LastInstructionIndex()) {
-    end =
-        LifetimePosition::GapFromInstructionIndex(end.ToInstructionIndex() - 1);
-  }
-  LifetimePosition pos = FindOptimalSplitPos(range->Start(), end);
-  pos = GetSplitPositionForInstruction(range, pos.ToInstructionIndex());
-  return pos;
-}
-
-
-void GreedyAllocator::SplitOrSpillBlockedRange(LiveRange* range) {
-  if (TrySplitAroundCalls(range)) return;
-
-  LifetimePosition pos = FindSplitPositionBeforeLoops(range);
-
-  if (!pos.IsValid()) pos = GetLastResortSplitPosition(range);
-  if (pos.IsValid()) {
-    LiveRange* tail = Split(range, data(), pos);
-    DCHECK(tail != range);
-    scheduler().Schedule(tail);
-    scheduler().Schedule(range);
-    return;
-  }
-  SpillRangeAsLastResort(range);
-}
-
-
-// Basic heuristic for advancing the algorithm, if any other splitting heuristic
-// failed.
-LifetimePosition GreedyAllocator::GetLastResortSplitPosition(
-    const LiveRange* range) {
-  LifetimePosition previous = range->Start();
-  for (UsePosition *pos = range->NextRegisterPosition(previous); pos != nullptr;
-       previous = previous.NextFullStart(),
-                   pos = range->NextRegisterPosition(previous)) {
-    LifetimePosition optimal = FindOptimalSplitPos(previous, pos->pos());
-    LifetimePosition before =
-        GetSplitPositionForInstruction(range, optimal.ToInstructionIndex());
-    if (before.IsValid()) return before;
-    LifetimePosition after = GetSplitPositionForInstruction(
-        range, pos->pos().ToInstructionIndex() + 1);
-    if (after.IsValid()) return after;
-  }
-  return LifetimePosition::Invalid();
-}
-
-
-bool GreedyAllocator::IsProgressPossible(const LiveRange* range) {
-  return range->CanBeSpilled(range->Start()) ||
-         GetLastResortSplitPosition(range).IsValid();
-}
-
-}  // namespace compiler
-}  // namespace internal
-}  // namespace v8