From ac3c4d40f5e82cdd10d5b48683c1576963f69999 Mon Sep 17 00:00:00 2001 From: dcarney Date: Fri, 21 Nov 2014 05:13:49 -0800 Subject: [PATCH] [turbofan] put late ssa deconstruction in register allocator behind a flag BUG= Review URL: https://codereview.chromium.org/751543002 Cr-Commit-Position: refs/heads/master@{#25465} --- src/compiler/pipeline.cc | 10 ++++ src/compiler/register-allocator.cc | 111 +++++++++++++++++++++++++++++-------- src/compiler/register-allocator.h | 26 ++++++--- src/flag-definitions.h | 3 + 4 files changed, 120 insertions(+), 30 deletions(-) diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index e5460d1..d9a9ec4 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -506,6 +506,15 @@ struct MeetRegisterConstraintsPhase { }; +struct ResolvePhisPhase { + static const char* phase_name() { return "resolve phis"; } + + void Run(PipelineData* data, Zone* temp_zone) { + data->register_allocator()->ResolvePhis(); + } +}; + + struct BuildLiveRangesPhase { static const char* phase_name() { return "build live ranges"; } @@ -926,6 +935,7 @@ void Pipeline::AllocateRegisters(const RegisterConfiguration* config, debug_name.get()); Run(); + Run(); Run(); if (FLAG_trace_turbo) { OFStream os(stdout); diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc index 283603a..3e1ac62 100644 --- a/src/compiler/register-allocator.cc +++ b/src/compiler/register-allocator.cc @@ -100,6 +100,8 @@ bool LiveRange::HasOverlap(UseInterval* target) const { LiveRange::LiveRange(int id, Zone* zone) : id_(id), spilled_(false), + is_phi_(false), + is_non_loop_phi_(false), kind_(UNALLOCATED_REGISTERS), assigned_register_(kInvalidAssignment), last_interval_(NULL), @@ -1163,12 +1165,20 @@ void RegisterAllocator::ProcessInstructions(const InstructionBlock* block, InstructionOperand* hint = to; if (to->IsUnallocated()) { int to_vreg = UnallocatedOperand::cast(to)->virtual_register(); - if (live->Contains(to_vreg)) { - Define(curr_position, to, from); - live->Remove(to_vreg); + LiveRange* to_range = LiveRangeFor(to_vreg); + if (to_range->is_phi()) { + DCHECK(!FLAG_turbo_delay_ssa_decon); + if (to_range->is_non_loop_phi()) { + hint = to_range->current_hint_operand(); + } } else { - cur->Eliminate(); - continue; + if (live->Contains(to_vreg)) { + Define(curr_position, to, from); + live->Remove(to_vreg); + } else { + cur->Eliminate(); + continue; + } } } else { Define(curr_position, to, from); @@ -1248,28 +1258,53 @@ void RegisterAllocator::ProcessInstructions(const InstructionBlock* block, } -void RegisterAllocator::ProcessPhis(const InstructionBlock* block) { +void RegisterAllocator::ResolvePhis(const InstructionBlock* block) { for (auto phi : block->phis()) { auto output = phi->output(); int phi_vreg = phi->virtual_register(); + if (!FLAG_turbo_delay_ssa_decon) { + for (size_t i = 0; i < phi->operands().size(); ++i) { + InstructionBlock* cur_block = + code()->InstructionBlockAt(block->predecessors()[i]); + // The gap move must be added without any special processing as in + // the AddConstraintsGapMove. + code()->AddGapMove(cur_block->last_instruction_index() - 1, + phi->inputs()[i], output); + DCHECK(!InstructionAt(cur_block->last_instruction_index()) + ->HasPointerMap()); + } + } LiveRange* live_range = LiveRangeFor(phi_vreg); BlockStartInstruction* block_start = code()->GetBlockStart(block->rpo_number()); block_start->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone()) ->AddMove(output, live_range->GetSpillOperand(), code_zone()); live_range->SetSpillStartIndex(block->first_instruction_index()); + // We use the phi-ness of some nodes in some later heuristics. + live_range->set_is_phi(true); + if (!block->IsLoopHeader()) { + live_range->set_is_non_loop_phi(true); + } } } void RegisterAllocator::MeetRegisterConstraints() { for (auto block : code()->instruction_blocks()) { - ProcessPhis(block); MeetRegisterConstraints(block); } } +void RegisterAllocator::ResolvePhis() { + // Process the blocks in reverse order. + for (auto i = code()->instruction_blocks().rbegin(); + i != code()->instruction_blocks().rend(); ++i) { + ResolvePhis(*i); + } +} + + ParallelMove* RegisterAllocator::GetConnectingParallelMove( LifetimePosition pos) { int index = pos.InstructionIndex(); @@ -1474,21 +1509,24 @@ void RegisterAllocator::ResolveControlFlow() { LiveRangeFinder finder(*this); for (auto block : code()->instruction_blocks()) { if (CanEagerlyResolveControlFlow(block)) continue; - // resolve phis - for (auto phi : block->phis()) { - auto* block_bound = - finder.ArrayFor(phi->virtual_register())->FindSucc(block); - auto phi_output = block_bound->range_->CreateAssignedOperand(code_zone()); - phi->output()->ConvertTo(phi_output->kind(), phi_output->index()); - size_t pred_index = 0; - for (auto pred : block->predecessors()) { - const InstructionBlock* pred_block = code()->InstructionBlockAt(pred); - auto* pred_bound = - finder.ArrayFor(phi->operands()[pred_index])->FindPred(pred_block); - auto pred_op = pred_bound->range_->CreateAssignedOperand(code_zone()); - phi->inputs()[pred_index] = pred_op; - ResolveControlFlow(block, phi_output, pred_block, pred_op); - pred_index++; + if (FLAG_turbo_delay_ssa_decon) { + // resolve phis + for (auto phi : block->phis()) { + auto* block_bound = + finder.ArrayFor(phi->virtual_register())->FindSucc(block); + auto phi_output = + block_bound->range_->CreateAssignedOperand(code_zone()); + phi->output()->ConvertTo(phi_output->kind(), phi_output->index()); + size_t pred_index = 0; + for (auto pred : block->predecessors()) { + const InstructionBlock* pred_block = code()->InstructionBlockAt(pred); + auto* pred_bound = finder.ArrayFor(phi->operands()[pred_index]) + ->FindPred(pred_block); + auto pred_op = pred_bound->range_->CreateAssignedOperand(code_zone()); + phi->inputs()[pred_index] = pred_op; + ResolveControlFlow(block, phi_output, pred_block, pred_op); + pred_index++; + } } } BitVector* live = live_in_sets_[block->rpo_number().ToInt()]; @@ -1556,6 +1594,27 @@ void RegisterAllocator::BuildLiveRanges() { // block. int phi_vreg = phi->virtual_register(); live->Remove(phi_vreg); + if (!FLAG_turbo_delay_ssa_decon) { + InstructionOperand* hint = NULL; + InstructionOperand* phi_operand = NULL; + GapInstruction* gap = + GetLastGap(code()->InstructionBlockAt(block->predecessors()[0])); + ParallelMove* move = + gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); + for (int j = 0; j < move->move_operands()->length(); ++j) { + InstructionOperand* to = move->move_operands()->at(j).destination(); + if (to->IsUnallocated() && + UnallocatedOperand::cast(to)->virtual_register() == phi_vreg) { + hint = move->move_operands()->at(j).source(); + phi_operand = to; + break; + } + } + DCHECK(hint != NULL); + LifetimePosition block_start = LifetimePosition::FromInstructionIndex( + block->first_instruction_index()); + Define(block_start, phi_operand, hint); + } } // Now live is live_in for this block except not including values live @@ -1600,7 +1659,13 @@ void RegisterAllocator::BuildLiveRanges() { for (UsePosition* pos = range->first_pos(); pos != NULL; pos = pos->next_) { pos->register_beneficial_ = true; - pos->requires_reg_ = true; + // TODO(dcarney): should the else case assert requires_reg_ == false? + // Can't mark phis as needing a register. + if (!code() + ->InstructionAt(pos->pos().InstructionIndex()) + ->IsGapMoves()) { + pos->requires_reg_ = true; + } } } } diff --git a/src/compiler/register-allocator.h b/src/compiler/register-allocator.h index 8499a79..b70ee6e 100644 --- a/src/compiler/register-allocator.h +++ b/src/compiler/register-allocator.h @@ -198,6 +198,12 @@ class LiveRange FINAL : public ZoneObject { int spill_start_index() const { return spill_start_index_; } void set_assigned_register(int reg, Zone* zone); void MakeSpilled(Zone* zone); + bool is_phi() const { return is_phi_; } + void set_is_phi(bool is_phi) { is_phi_ = is_phi; } + bool is_non_loop_phi() const { return is_non_loop_phi_; } + void set_is_non_loop_phi(bool is_non_loop_phi) { + is_non_loop_phi_ = is_non_loop_phi; + } // Returns use position in this live range that follows both start // and last processed use position. @@ -295,6 +301,8 @@ class LiveRange FINAL : public ZoneObject { int id_; bool spilled_; + bool is_phi_; + bool is_non_loop_phi_; RegisterKind kind_; int assigned_register_; UseInterval* last_interval_; @@ -363,24 +371,28 @@ class RegisterAllocator FINAL : public ZoneObject { // Phase 1 : insert moves to account for fixed register operands. void MeetRegisterConstraints(); - // Phase 2: compute liveness of all virtual register. + // Phase 2: deconstruct SSA by inserting moves in successors and the headers + // of blocks containing phis. + void ResolvePhis(); + + // Phase 3: compute liveness of all virtual register. void BuildLiveRanges(); bool ExistsUseWithoutDefinition(); - // Phase 3: compute register assignments. + // Phase 4: compute register assignments. void AllocateGeneralRegisters(); void AllocateDoubleRegisters(); - // Phase 4: reassign spill splots for maximal reuse. + // Phase 5: reassign spill splots for maximal reuse. void ReuseSpillSlots(); - // Phase 5: compute values for pointer maps. + // Phase 6: compute values for pointer maps. void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. - // Phase 6: reconnect split ranges with moves. + // Phase 7: reconnect split ranges with moves. void ConnectRanges(); - // Phase 7: insert moves to connect ranges across basic blocks. + // Phase 8: insert moves to connect ranges across basic blocks. void ResolveControlFlow(); private: @@ -428,7 +440,7 @@ class RegisterAllocator FINAL : public ZoneObject { int gap_index); void MeetRegisterConstraintsForLastInstructionInBlock( const InstructionBlock* block); - void ProcessPhis(const InstructionBlock* block); + void ResolvePhis(const InstructionBlock* block); // Helper methods for building intervals. InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 25426d6..be4e278 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -390,6 +390,9 @@ DEFINE_IMPLICATION(turbo_inlining, turbo_types) DEFINE_BOOL(turbo_profiling, false, "enable profiling in TurboFan") // TODO(dcarney): this is just for experimentation, remove when default. DEFINE_BOOL(turbo_reuse_spill_slots, false, "reuse spill slots in TurboFan") +// TODO(dcarney): this is just for experimentation, remove when default. +DEFINE_BOOL(turbo_delay_ssa_decon, false, + "delay ssa deconstruction in TurboFan register allocator") DEFINE_INT(typed_array_max_size_in_heap, 64, "threshold for in-heap typed array") -- 2.7.4