Index: src/compiler/greedy-allocator.cc |
diff --git a/src/compiler/greedy-allocator.cc b/src/compiler/greedy-allocator.cc |
deleted file mode 100644 |
index 683b75d49fa756701c3eb061f485a1168fc91515..0000000000000000000000000000000000000000 |
--- a/src/compiler/greedy-allocator.cc |
+++ /dev/null |
@@ -1,629 +0,0 @@ |
-// 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 |