From bc7f79a67042de6255e09c984b4196f3eef6b2d6 Mon Sep 17 00:00:00 2001 From: svenpanne Date: Tue, 28 Apr 2015 22:54:41 -0700 Subject: [PATCH] Calculate blocks needing a frame and frame (de)construction sites. Review URL: https://codereview.chromium.org/1053123006 Cr-Commit-Position: refs/heads/master@{#28120} --- BUILD.gn | 2 + src/compiler/code-generator.cc | 8 ++- src/compiler/frame-elider.cc | 129 +++++++++++++++++++++++++++++++++++++++++ src/compiler/frame-elider.h | 41 +++++++++++++ src/compiler/instruction.cc | 5 +- src/compiler/instruction.h | 12 ++++ src/compiler/pipeline.cc | 15 +++++ src/flag-definitions.h | 1 + tools/gyp/v8.gyp | 2 + 9 files changed, 212 insertions(+), 3 deletions(-) create mode 100644 src/compiler/frame-elider.cc create mode 100644 src/compiler/frame-elider.h diff --git a/BUILD.gn b/BUILD.gn index fb0c577..64d7502 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -573,6 +573,8 @@ source_set("v8_base") { "src/compiler/control-reducer.h", "src/compiler/diamond.h", "src/compiler/frame.h", + "src/compiler/frame-elider.cc", + "src/compiler/frame-elider.h", "src/compiler/gap-resolver.cc", "src/compiler/gap-resolver.h", "src/compiler/graph-builder.h", diff --git a/src/compiler/code-generator.cc b/src/compiler/code-generator.cc index dd6565c..13087ec 100644 --- a/src/compiler/code-generator.cc +++ b/src/compiler/code-generator.cc @@ -84,8 +84,12 @@ Handle CodeGenerator::GenerateCode() { current_block_ = block->rpo_number(); if (FLAG_code_comments) { // TODO(titzer): these code comments are a giant memory leak. - Vector buffer = Vector::New(32); - SNPrintF(buffer, "-- B%d start --", block->rpo_number().ToInt()); + Vector buffer = Vector::New(200); + SNPrintF(buffer, "-- B%d start%s%s%s%s --", block->rpo_number().ToInt(), + block->IsDeferred() ? " (deferred)" : "", + block->needs_frame() ? "" : " (no frame)", + block->must_construct_frame() ? " (construct frame)" : "", + block->must_deconstruct_frame() ? " (deconstruct frame)" : ""); masm()->RecordComment(buffer.start()); } masm()->bind(GetLabel(current_block_)); diff --git a/src/compiler/frame-elider.cc b/src/compiler/frame-elider.cc new file mode 100644 index 0000000..1263c3f --- /dev/null +++ b/src/compiler/frame-elider.cc @@ -0,0 +1,129 @@ +// 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/base/adapters.h" +#include "src/compiler/frame-elider.h" + +namespace v8 { +namespace internal { +namespace compiler { + +FrameElider::FrameElider(InstructionSequence* code) : code_(code) {} + +void FrameElider::Run() { + MarkBlocks(); + PropagateMarks(); + MarkDeConstruction(); +} + + +void FrameElider::MarkBlocks() { + for (auto block : instruction_blocks()) { + for (auto i = block->code_start(); i < block->code_end(); ++i) { + if (InstructionAt(i)->IsCall()) { + block->mark_needs_frame(); + break; + } + } + } +} + + +void FrameElider::PropagateMarks() { + while (PropagateInOrder() && PropagateReversed()) { + } +} + + +void FrameElider::MarkDeConstruction() { + for (auto block : instruction_blocks()) { + if (block->needs_frame()) { + // Special case: The start block needs a frame. + if (block->predecessors().empty()) { + block->mark_must_construct_frame(); + } + // Find "frame -> no frame" transitions, inserting frame + // deconstructions. + for (auto succ : block->successors()) { + if (!InstructionBlockAt(succ)->needs_frame()) { + DCHECK_EQ(1, block->SuccessorCount()); + block->mark_must_deconstruct_frame(); + } + } + } else { + // Find "no frame -> frame" transitions, inserting frame constructions. + for (auto succ : block->successors()) { + if (InstructionBlockAt(succ)->needs_frame()) { + DCHECK_NE(1, block->SuccessorCount()); + InstructionBlockAt(succ)->mark_must_construct_frame(); + } + } + } + } +} + + +bool FrameElider::PropagateInOrder() { + bool changed = false; + for (auto block : instruction_blocks()) { + changed |= PropagateIntoBlock(block); + } + return changed; +} + + +bool FrameElider::PropagateReversed() { + bool changed = false; + for (auto block : base::Reversed(instruction_blocks())) { + changed |= PropagateIntoBlock(block); + } + return changed; +} + + +bool FrameElider::PropagateIntoBlock(InstructionBlock* block) { + // Already marked, nothing to do... + if (block->needs_frame()) return false; + + // Never mark the dummy end node, otherwise we might incorrectly decide to + // put frame deconstruction code there later, + if (block->successors().empty()) return false; + + // Propagate towards the end ("downwards") if there is a predecessor needing + // a frame, but don't "bleed" from deferred code to non-deferred code. + for (auto pred : block->predecessors()) { + if (InstructionBlockAt(pred)->needs_frame() && + (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) { + block->mark_needs_frame(); + return true; + } + } + + // Propagate towards start ("upwards") if there are successors and all of + // them need a frame. + for (auto succ : block->successors()) { + if (!InstructionBlockAt(succ)->needs_frame()) return false; + } + block->mark_needs_frame(); + return true; +} + + +const InstructionBlocks& FrameElider::instruction_blocks() const { + return code_->instruction_blocks(); +} + + +InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const { + return code_->InstructionBlockAt(rpo_number); +} + + +Instruction* FrameElider::InstructionAt(int index) const { + return code_->InstructionAt(index); +} + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/src/compiler/frame-elider.h b/src/compiler/frame-elider.h new file mode 100644 index 0000000..7d31619 --- /dev/null +++ b/src/compiler/frame-elider.h @@ -0,0 +1,41 @@ +// 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. + +#ifndef V8_COMPILER_FRAME_ELIDER_H_ +#define V8_COMPILER_FRAME_ELIDER_H_ + +#include "src/compiler/instruction.h" + +namespace v8 { +namespace internal { +namespace compiler { + + +// Determine which instruction blocks need a frame and where frames must be +// constructed/deconstructed. +class FrameElider { + public: + explicit FrameElider(InstructionSequence* code); + void Run(); + + + private: + void MarkBlocks(); + void PropagateMarks(); + void MarkDeConstruction(); + bool PropagateInOrder(); + bool PropagateReversed(); + bool PropagateIntoBlock(InstructionBlock* block); + const InstructionBlocks& instruction_blocks() const; + InstructionBlock* InstructionBlockAt(RpoNumber rpo_number) const; + Instruction* InstructionAt(int index) const; + + InstructionSequence* const code_; +}; + +} // namespace compiler +} // namespace internal +} // namespace v8 + +#endif // V8_COMPILER_FRAME_ELIDER_H_ diff --git a/src/compiler/instruction.cc b/src/compiler/instruction.cc index 9d157a1..df3d345 100644 --- a/src/compiler/instruction.cc +++ b/src/compiler/instruction.cc @@ -387,7 +387,10 @@ InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number, loop_end_(loop_end), code_start_(-1), code_end_(-1), - deferred_(deferred) {} + deferred_(deferred), + needs_frame_(false), + must_construct_frame_(false), + must_deconstruct_frame_(false) {} size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const { diff --git a/src/compiler/instruction.h b/src/compiler/instruction.h index 6555b34..9b97282 100644 --- a/src/compiler/instruction.h +++ b/src/compiler/instruction.h @@ -928,6 +928,15 @@ class InstructionBlock final : public ZoneObject { void set_ao_number(RpoNumber ao_number) { ao_number_ = ao_number; } + bool needs_frame() const { return needs_frame_; } + void mark_needs_frame() { needs_frame_ = true; } + + bool must_construct_frame() const { return must_construct_frame_; } + void mark_must_construct_frame() { must_construct_frame_ = true; } + + bool must_deconstruct_frame() const { return must_deconstruct_frame_; } + void mark_must_deconstruct_frame() { must_deconstruct_frame_ = true; } + private: Successors successors_; Predecessors predecessors_; @@ -939,6 +948,9 @@ class InstructionBlock final : public ZoneObject { int32_t code_start_; // start index of arch-specific code. int32_t code_end_; // end index of arch-specific code. const bool deferred_; // Block contains deferred code. + bool needs_frame_; + bool must_construct_frame_; + bool must_deconstruct_frame_; }; typedef ZoneDeque ConstantDeque; diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index f6a5c05..e07ce76 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -7,6 +7,7 @@ #include // NOLINT(readability/streams) #include +#include "src/base/adapters.h" #include "src/base/platform/elapsed-timer.h" #include "src/compiler/ast-graph-builder.h" #include "src/compiler/ast-loop-assignment-analyzer.h" @@ -16,6 +17,7 @@ #include "src/compiler/common-operator-reducer.h" #include "src/compiler/control-flow-optimizer.h" #include "src/compiler/control-reducer.h" +#include "src/compiler/frame-elider.h" #include "src/compiler/graph-replay.h" #include "src/compiler/graph-visualizer.h" #include "src/compiler/instruction.h" @@ -832,6 +834,15 @@ struct OptimizeMovesPhase { }; +struct FrameElisionPhase { + static const char* phase_name() { return "frame elision"; } + + void Run(PipelineData* data, Zone* temp_zone) { + FrameElider(data->sequence()).Run(); + } +}; + + struct JumpThreadingPhase { static const char* phase_name() { return "jump threading"; } @@ -1184,6 +1195,10 @@ Handle Pipeline::ScheduleAndGenerateCode( return Handle(); } + if (FLAG_turbo_frame_elision) { + Run(); + } + BeginPhaseKind("code generation"); // Optimimize jumps. diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 19cac79..c16b2d6 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -422,6 +422,7 @@ DEFINE_BOOL(turbo_exceptions, false, "enable exception handling in TurboFan") DEFINE_BOOL(turbo_stress_loop_peeling, false, "stress loop peeling optimization") DEFINE_BOOL(turbo_cf_optimization, true, "optimize control flow in TurboFan") +DEFINE_BOOL(turbo_frame_elision, true, "elide frames in TurboFan") DEFINE_INT(typed_array_max_size_in_heap, 64, "threshold for in-heap typed array") diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index ee72d37..b0f7d67 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -458,6 +458,8 @@ '../../src/compiler/control-reducer.h', '../../src/compiler/diamond.h', '../../src/compiler/frame.h', + '../../src/compiler/frame-elider.cc', + '../../src/compiler/frame-elider.h', '../../src/compiler/gap-resolver.cc', '../../src/compiler/gap-resolver.h', '../../src/compiler/graph-builder.h', -- 2.7.4