Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1292)

Unified Diff: src/compiler/greedy-allocator.cc

Issue 2060673002: [turbofan] Retiring Greedy Allocator (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 4 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/greedy-allocator.h ('k') | src/compiler/pipeline.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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
« no previous file with comments | « src/compiler/greedy-allocator.h ('k') | src/compiler/pipeline.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698