// 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/live-range-separator.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)
|
|
|
namespace {
|
|
|
void CreateSplinter(TopLevelLiveRange *range, RegisterAllocationData *data,
|
LifetimePosition first_cut, LifetimePosition last_cut) {
|
DCHECK(!range->IsSplinter());
|
// We can ignore ranges that live solely in deferred blocks.
|
// If a range ends right at the end of a deferred block, it is marked by
|
// the range builder as ending at gap start of the next block - since the
|
// end is a position where the variable isn't live. We need to take that
|
// into consideration.
|
LifetimePosition max_allowed_end = last_cut.NextFullStart();
|
|
if (first_cut <= range->Start() && max_allowed_end >= range->End()) {
|
return;
|
}
|
|
LifetimePosition start = Max(first_cut, range->Start());
|
LifetimePosition end = Min(last_cut, range->End());
|
|
if (start < end) {
|
// Ensure the original range has a spill range associated, before it gets
|
// splintered. Splinters will point to it. This way, when attempting to
|
// reuse spill slots of splinters, during allocation, we avoid clobbering
|
// such slots.
|
if (range->MayRequireSpillRange()) {
|
data->CreateSpillRangeForLiveRange(range);
|
}
|
if (range->splinter() == nullptr) {
|
TopLevelLiveRange *splinter =
|
data->NextLiveRange(range->representation());
|
DCHECK_NULL(data->live_ranges()[splinter->vreg()]);
|
data->live_ranges()[splinter->vreg()] = splinter;
|
range->SetSplinter(splinter);
|
}
|
Zone *zone = data->allocation_zone();
|
TRACE("creating splinter for range %d between %d and %d\n", range->vreg(),
|
start.ToInstructionIndex(), end.ToInstructionIndex());
|
range->Splinter(start, end, zone);
|
}
|
}
|
|
void SetSlotUse(TopLevelLiveRange *range) {
|
range->set_has_slot_use(false);
|
for (const UsePosition *pos = range->first_pos();
|
!range->has_slot_use() && pos != nullptr; pos = pos->next()) {
|
if (pos->type() == UsePositionType::kRequiresSlot) {
|
range->set_has_slot_use(true);
|
}
|
}
|
}
|
|
void SplinterLiveRange(TopLevelLiveRange *range, RegisterAllocationData *data) {
|
const InstructionSequence *code = data->code();
|
UseInterval *interval = range->first_interval();
|
|
LifetimePosition first_cut = LifetimePosition::Invalid();
|
LifetimePosition last_cut = LifetimePosition::Invalid();
|
|
while (interval != nullptr) {
|
UseInterval *next_interval = interval->next();
|
const InstructionBlock *first_block =
|
code->GetInstructionBlock(interval->FirstGapIndex());
|
const InstructionBlock *last_block =
|
code->GetInstructionBlock(interval->LastGapIndex());
|
int first_block_nr = first_block->rpo_number().ToInt();
|
int last_block_nr = last_block->rpo_number().ToInt();
|
for (int block_id = first_block_nr; block_id <= last_block_nr; ++block_id) {
|
const InstructionBlock *current_block =
|
code->InstructionBlockAt(RpoNumber::FromInt(block_id));
|
if (current_block->IsDeferred()) {
|
if (!first_cut.IsValid()) {
|
first_cut = LifetimePosition::GapFromInstructionIndex(
|
current_block->first_instruction_index());
|
}
|
last_cut = LifetimePosition::GapFromInstructionIndex(
|
current_block->last_instruction_index());
|
} else {
|
if (first_cut.IsValid()) {
|
CreateSplinter(range, data, first_cut, last_cut);
|
first_cut = LifetimePosition::Invalid();
|
last_cut = LifetimePosition::Invalid();
|
}
|
}
|
}
|
interval = next_interval;
|
}
|
// When the range ends in deferred blocks, first_cut will be valid here.
|
// Splinter from there to the last instruction that was in a deferred block.
|
if (first_cut.IsValid()) {
|
CreateSplinter(range, data, first_cut, last_cut);
|
}
|
|
// Redo has_slot_use
|
if (range->has_slot_use() && range->splinter() != nullptr) {
|
SetSlotUse(range);
|
SetSlotUse(range->splinter());
|
}
|
}
|
|
} // namespace
|
|
|
void LiveRangeSeparator::Splinter() {
|
size_t virt_reg_count = data()->live_ranges().size();
|
for (size_t vreg = 0; vreg < virt_reg_count; ++vreg) {
|
TopLevelLiveRange *range = data()->live_ranges()[vreg];
|
if (range == nullptr || range->IsEmpty() || range->IsSplinter()) {
|
continue;
|
}
|
int first_instr = range->first_interval()->FirstGapIndex();
|
if (!data()->code()->GetInstructionBlock(first_instr)->IsDeferred()) {
|
SplinterLiveRange(range, data());
|
}
|
}
|
}
|
|
|
void LiveRangeMerger::MarkRangesSpilledInDeferredBlocks() {
|
const InstructionSequence *code = data()->code();
|
for (TopLevelLiveRange *top : data()->live_ranges()) {
|
if (top == nullptr || top->IsEmpty() || top->splinter() == nullptr ||
|
top->HasSpillOperand() || !top->splinter()->HasSpillRange()) {
|
continue;
|
}
|
|
LiveRange *child = top;
|
for (; child != nullptr; child = child->next()) {
|
if (child->spilled() ||
|
child->NextSlotPosition(child->Start()) != nullptr) {
|
break;
|
}
|
}
|
if (child == nullptr) {
|
top->TreatAsSpilledInDeferredBlock(data()->allocation_zone(),
|
code->InstructionBlockCount());
|
}
|
}
|
}
|
|
|
void LiveRangeMerger::Merge() {
|
MarkRangesSpilledInDeferredBlocks();
|
|
int live_range_count = static_cast<int>(data()->live_ranges().size());
|
for (int i = 0; i < live_range_count; ++i) {
|
TopLevelLiveRange *range = data()->live_ranges()[i];
|
if (range == nullptr || range->IsEmpty() || !range->IsSplinter()) {
|
continue;
|
}
|
TopLevelLiveRange *splinter_parent = range->splintered_from();
|
|
int to_remove = range->vreg();
|
splinter_parent->Merge(range, data()->allocation_zone());
|
data()->live_ranges()[to_remove] = nullptr;
|
}
|
}
|
|
#undef TRACE
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
