From 2379d34bdcfbf59a8e36bec69bc16ab9694ec019 Mon Sep 17 00:00:00 2001 From: titzer Date: Mon, 2 Feb 2015 11:09:48 -0800 Subject: [PATCH] [turbofan] Put StructuredGraphBuilder out of its misery and merge its remnants back into the AstGraphBuilder. R=mstarzinger@chromium.org BUG= Review URL: https://codereview.chromium.org/894073002 Cr-Commit-Position: refs/heads/master@{#26387} --- BUILD.gn | 1 - src/compiler/ast-graph-builder.cc | 299 +++++++++++++++++++++++++++++++++---- src/compiler/ast-graph-builder.h | 262 +++++++++++++++++++++++++-------- src/compiler/control-builders.h | 17 +-- src/compiler/graph-builder.cc | 300 -------------------------------------- src/compiler/graph-builder.h | 167 --------------------- tools/gyp/v8.gyp | 1 - 7 files changed, 481 insertions(+), 566 deletions(-) delete mode 100644 src/compiler/graph-builder.cc diff --git a/BUILD.gn b/BUILD.gn index 92a96d9..bd5a2552 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -536,7 +536,6 @@ source_set("v8_base") { "src/compiler/gap-resolver.cc", "src/compiler/gap-resolver.h", "src/compiler/generic-algorithm.h", - "src/compiler/graph-builder.cc", "src/compiler/graph-builder.h", "src/compiler/graph-inl.h", "src/compiler/graph-reducer.cc", diff --git a/src/compiler/ast-graph-builder.cc b/src/compiler/ast-graph-builder.cc index 18475d1..08f0fa2 100644 --- a/src/compiler/ast-graph-builder.cc +++ b/src/compiler/ast-graph-builder.cc @@ -20,15 +20,21 @@ namespace v8 { namespace internal { namespace compiler { + AstGraphBuilder::AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, LoopAssignmentAnalysis* loop) - : StructuredGraphBuilder(jsgraph->isolate(), local_zone, jsgraph->graph(), - jsgraph->common()), + : local_zone_(local_zone), info_(info), jsgraph_(jsgraph), + environment_(nullptr), + ast_context_(nullptr), globals_(0, local_zone), - breakable_(NULL), - execution_context_(NULL), + breakable_(nullptr), + execution_context_(nullptr), + input_buffer_size_(0), + input_buffer_(nullptr), + current_context_(nullptr), + exit_control_(nullptr), loop_assignment_analysis_(loop) { InitializeAstVisitor(info->isolate(), local_zone); } @@ -151,21 +157,18 @@ static LhsKind DetermineLhsKind(Expression* expr) { } -StructuredGraphBuilder::Environment* AstGraphBuilder::CopyEnvironment( - StructuredGraphBuilder::Environment* env) { - return new (zone()) Environment(*reinterpret_cast(env)); -} - - AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency) - : StructuredGraphBuilder::Environment(builder, control_dependency), + : builder_(builder), parameters_count_(scope->num_parameters() + 1), locals_count_(scope->num_stack_slots()), - parameters_node_(NULL), - locals_node_(NULL), - stack_node_(NULL) { + values_(builder_->local_zone()), + control_dependency_(control_dependency), + effect_dependency_(control_dependency), + parameters_node_(nullptr), + locals_node_(nullptr), + stack_node_(nullptr) { DCHECK_EQ(scope->num_parameters() + 1, parameters_count()); // Bind the receiver variable. @@ -187,14 +190,21 @@ AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder, } -AstGraphBuilder::Environment::Environment(const Environment& copy) - : StructuredGraphBuilder::Environment( - static_cast(copy)), - parameters_count_(copy.parameters_count_), - locals_count_(copy.locals_count_), - parameters_node_(copy.parameters_node_), - locals_node_(copy.locals_node_), - stack_node_(copy.stack_node_) {} +AstGraphBuilder::Environment::Environment( + const AstGraphBuilder::Environment* copy) + : builder_(copy->builder_), + parameters_count_(copy->parameters_count_), + locals_count_(copy->locals_count_), + values_(copy->zone()), + control_dependency_(copy->control_dependency_), + effect_dependency_(copy->effect_dependency_), + parameters_node_(copy->parameters_node_), + locals_node_(copy->locals_node_), + stack_node_(copy->stack_node_) { + const size_t kStackEstimate = 7; // optimum from experimentation! + values_.reserve(copy->values_.size() + kStackEstimate); + values_.insert(values_.begin(), copy->values_.begin(), copy->values_.end()); +} void AstGraphBuilder::Environment::UpdateStateValues(Node** state_values, @@ -229,7 +239,7 @@ Node* AstGraphBuilder::Environment::Checkpoint( const Operator* op = common()->FrameState(JS_FRAME, ast_id, combine); return graph()->NewNode(op, parameters_node_, locals_node_, stack_node_, - GetContext(), + builder()->current_context(), builder()->jsgraph()->UndefinedConstant()); } @@ -518,14 +528,14 @@ void AstGraphBuilder::VisitIfStatement(IfStatement* stmt) { void AstGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) { - StructuredGraphBuilder::Environment* env = environment()->CopyAsUnreachable(); + Environment* env = environment()->CopyAsUnreachable(); breakable()->ContinueTarget(stmt->target()); set_environment(env); } void AstGraphBuilder::VisitBreakStatement(BreakStatement* stmt) { - StructuredGraphBuilder::Environment* env = environment()->CopyAsUnreachable(); + Environment* env = environment()->CopyAsUnreachable(); breakable()->BreakTarget(stmt->target()); set_environment(env); } @@ -1945,7 +1955,7 @@ Node* AstGraphBuilder::BuildPatchReceiverToGlobalProxy(Node* receiver) { // Sloppy mode functions and builtins need to replace the receiver with the // global proxy when called as functions (without an explicit receiver // object). Otherwise there is nothing left to do here. - if (info()->strict_mode() != SLOPPY || info()->is_native()) return receiver; + if (strict_mode() != SLOPPY || info()->is_native()) return receiver; // There is no need to perform patching if the receiver is never used. Note // that scope predicates are purely syntactical, a call to eval might still @@ -2439,6 +2449,243 @@ BitVector* AstGraphBuilder::GetVariablesAssignedInLoop( return loop_assignment_analysis_->GetVariablesAssignedInLoop(stmt); } + +Node** AstGraphBuilder::EnsureInputBufferSize(int size) { + if (size > input_buffer_size_) { + size = size + kInputBufferSizeIncrement + input_buffer_size_; + input_buffer_ = local_zone()->NewArray(size); + input_buffer_size_ = size; + } + return input_buffer_; +} + + +Node* AstGraphBuilder::MakeNode(const Operator* op, int value_input_count, + Node** value_inputs, bool incomplete) { + DCHECK(op->ValueInputCount() == value_input_count); + + bool has_context = OperatorProperties::HasContextInput(op); + bool has_framestate = OperatorProperties::HasFrameStateInput(op); + bool has_control = op->ControlInputCount() == 1; + bool has_effect = op->EffectInputCount() == 1; + + DCHECK(op->ControlInputCount() < 2); + DCHECK(op->EffectInputCount() < 2); + + Node* result = NULL; + if (!has_context && !has_framestate && !has_control && !has_effect) { + result = graph()->NewNode(op, value_input_count, value_inputs, incomplete); + } else { + int input_count_with_deps = value_input_count; + if (has_context) ++input_count_with_deps; + if (has_framestate) ++input_count_with_deps; + if (has_control) ++input_count_with_deps; + if (has_effect) ++input_count_with_deps; + Node** buffer = EnsureInputBufferSize(input_count_with_deps); + memcpy(buffer, value_inputs, kPointerSize * value_input_count); + Node** current_input = buffer + value_input_count; + if (has_context) { + *current_input++ = current_context(); + } + if (has_framestate) { + // The frame state will be inserted later. Here we misuse + // the dead_control node as a sentinel to be later overwritten + // with the real frame state. + *current_input++ = dead_control(); + } + if (has_effect) { + *current_input++ = environment_->GetEffectDependency(); + } + if (has_control) { + *current_input++ = environment_->GetControlDependency(); + } + result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete); + if (has_effect) { + environment_->UpdateEffectDependency(result); + } + if (result->op()->ControlOutputCount() > 0 && + !environment()->IsMarkedAsUnreachable()) { + environment_->UpdateControlDependency(result); + } + } + + return result; +} + + +void AstGraphBuilder::UpdateControlDependencyToLeaveFunction(Node* exit) { + if (environment()->IsMarkedAsUnreachable()) return; + if (exit_control() != NULL) { + exit = MergeControl(exit_control(), exit); + } + environment()->MarkAsUnreachable(); + set_exit_control(exit); +} + + +void AstGraphBuilder::Environment::Merge(Environment* other) { + DCHECK(values_.size() == other->values_.size()); + + // Nothing to do if the other environment is dead. + if (other->IsMarkedAsUnreachable()) return; + + // Resurrect a dead environment by copying the contents of the other one and + // placing a singleton merge as the new control dependency. + if (this->IsMarkedAsUnreachable()) { + Node* other_control = other->control_dependency_; + Node* inputs[] = {other_control}; + control_dependency_ = + graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true); + effect_dependency_ = other->effect_dependency_; + values_ = other->values_; + return; + } + + // Create a merge of the control dependencies of both environments and update + // the current environment's control dependency accordingly. + Node* control = builder_->MergeControl(this->GetControlDependency(), + other->GetControlDependency()); + UpdateControlDependency(control); + + // Create a merge of the effect dependencies of both environments and update + // the current environment's effect dependency accordingly. + Node* effect = builder_->MergeEffect(this->GetEffectDependency(), + other->GetEffectDependency(), control); + UpdateEffectDependency(effect); + + // Introduce Phi nodes for values that have differing input at merge points, + // potentially extending an existing Phi node if possible. + for (int i = 0; i < static_cast(values_.size()); ++i) { + values_[i] = builder_->MergeValue(values_[i], other->values_[i], control); + } +} + + +void AstGraphBuilder::Environment::PrepareForLoop(BitVector* assigned, + bool is_osr) { + int size = static_cast(values()->size()); + + Node* control = builder_->NewLoop(); + if (assigned == nullptr) { + // Assume that everything is updated in the loop. + for (int i = 0; i < size; ++i) { + Node* phi = builder_->NewPhi(1, values()->at(i), control); + values()->at(i) = phi; + } + } else { + // Only build phis for those locals assigned in this loop. + for (int i = 0; i < size; ++i) { + if (i < assigned->length() && !assigned->Contains(i)) continue; + Node* phi = builder_->NewPhi(1, values()->at(i), control); + values()->at(i) = phi; + } + } + Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control); + UpdateEffectDependency(effect); + + if (is_osr) { + // Merge OSR values as inputs to the phis of the loop. + Graph* graph = builder_->graph(); + Node* osr_loop_entry = builder_->graph()->NewNode( + builder_->common()->OsrLoopEntry(), graph->start(), graph->start()); + + builder_->MergeControl(control, osr_loop_entry); + builder_->MergeEffect(effect, osr_loop_entry, control); + + for (int i = 0; i < size; ++i) { + Node* val = values()->at(i); + if (!IrOpcode::IsConstantOpcode(val->opcode())) { + Node* osr_value = + graph->NewNode(builder_->common()->OsrValue(i), osr_loop_entry); + values()->at(i) = builder_->MergeValue(val, osr_value, control); + } + } + } +} + + +Node* AstGraphBuilder::NewPhi(int count, Node* input, Node* control) { + const Operator* phi_op = common()->Phi(kMachAnyTagged, count); + Node** buffer = EnsureInputBufferSize(count + 1); + MemsetPointer(buffer, input, count); + buffer[count] = control; + return graph()->NewNode(phi_op, count + 1, buffer, true); +} + + +// TODO(mstarzinger): Revisit this once we have proper effect states. +Node* AstGraphBuilder::NewEffectPhi(int count, Node* input, Node* control) { + const Operator* phi_op = common()->EffectPhi(count); + Node** buffer = EnsureInputBufferSize(count + 1); + MemsetPointer(buffer, input, count); + buffer[count] = control; + return graph()->NewNode(phi_op, count + 1, buffer, true); +} + + +Node* AstGraphBuilder::MergeControl(Node* control, Node* other) { + int inputs = control->op()->ControlInputCount() + 1; + if (control->opcode() == IrOpcode::kLoop) { + // Control node for loop exists, add input. + const Operator* op = common()->Loop(inputs); + control->AppendInput(graph_zone(), other); + control->set_op(op); + } else if (control->opcode() == IrOpcode::kMerge) { + // Control node for merge exists, add input. + const Operator* op = common()->Merge(inputs); + control->AppendInput(graph_zone(), other); + control->set_op(op); + } else { + // Control node is a singleton, introduce a merge. + const Operator* op = common()->Merge(inputs); + Node* inputs[] = {control, other}; + control = graph()->NewNode(op, arraysize(inputs), inputs, true); + } + return control; +} + + +Node* AstGraphBuilder::MergeEffect(Node* value, Node* other, Node* control) { + int inputs = control->op()->ControlInputCount(); + if (value->opcode() == IrOpcode::kEffectPhi && + NodeProperties::GetControlInput(value) == control) { + // Phi already exists, add input. + value->set_op(common()->EffectPhi(inputs)); + value->InsertInput(graph_zone(), inputs - 1, other); + } else if (value != other) { + // Phi does not exist yet, introduce one. + value = NewEffectPhi(inputs, value, control); + value->ReplaceInput(inputs - 1, other); + } + return value; +} + + +Node* AstGraphBuilder::MergeValue(Node* value, Node* other, Node* control) { + int inputs = control->op()->ControlInputCount(); + if (value->opcode() == IrOpcode::kPhi && + NodeProperties::GetControlInput(value) == control) { + // Phi already exists, add input. + value->set_op(common()->Phi(kMachAnyTagged, inputs)); + value->InsertInput(graph_zone(), inputs - 1, other); + } else if (value != other) { + // Phi does not exist yet, introduce one. + value = NewPhi(inputs, value, control); + value->ReplaceInput(inputs - 1, other); + } + return value; +} + + +Node* AstGraphBuilder::dead_control() { + if (!dead_control_.is_set()) { + Node* dead_node = graph()->NewNode(common()->Dead()); + dead_control_.set(dead_node); + return dead_node; + } + return dead_control_.get(); +} + } // namespace compiler } // namespace internal } // namespace v8 diff --git a/src/compiler/ast-graph-builder.h b/src/compiler/ast-graph-builder.h index b23247b..07a2a06 100644 --- a/src/compiler/ast-graph-builder.h +++ b/src/compiler/ast-graph-builder.h @@ -8,23 +8,26 @@ #include "src/v8.h" #include "src/ast.h" -#include "src/compiler/graph-builder.h" #include "src/compiler/js-graph.h" namespace v8 { namespace internal { + +class BitVector; + namespace compiler { class ControlBuilder; class Graph; class LoopAssignmentAnalysis; class LoopBuilder; +class Node; // The AstGraphBuilder produces a high-level IR graph, based on an // underlying AST. The produced graph can either be compiled into a // stand-alone function or be wired into another graph for the purposes // of function inlining. -class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { +class AstGraphBuilder : public AstVisitor { public: AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, LoopAssignmentAnalysis* loop_assignment = NULL); @@ -32,7 +35,30 @@ class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { // Creates a graph by visiting the entire AST. bool CreateGraph(); + // Helpers to create new control nodes. + Node* NewIfTrue() { return NewNode(common()->IfTrue()); } + Node* NewIfFalse() { return NewNode(common()->IfFalse()); } + Node* NewMerge() { return NewNode(common()->Merge(1), true); } + Node* NewLoop() { return NewNode(common()->Loop(1), true); } + Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { + return NewNode(common()->Branch(hint), condition); + } + protected: +#define DECLARE_VISIT(type) void Visit##type(type* node) OVERRIDE; + // Visiting functions for AST nodes make this an AstVisitor. + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + // Visiting function for declarations list is overridden. + void VisitDeclarations(ZoneList* declarations) OVERRIDE; + + // Get the node that represents the outer function context. + Node* GetFunctionContext(); + // Get the node that represents the outer function closure. + Node* GetFunctionClosure(); + + private: class AstContext; class AstEffectContext; class AstValueContext; @@ -40,28 +66,129 @@ class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { class BreakableScope; class ContextScope; class Environment; + friend class ControlBuilder; - Environment* environment() { - return reinterpret_cast( - StructuredGraphBuilder::environment()); - } + Zone* local_zone_; + CompilationInfo* info_; + JSGraph* jsgraph_; + Environment* environment_; + AstContext* ast_context_; + + // List of global declarations for functions and variables. + ZoneVector> globals_; + + // Stack of breakable statements entered by the visitor. + BreakableScope* breakable_; + + // Stack of context objects pushed onto the chain by the visitor. + ContextScope* execution_context_; + + // Nodes representing values in the activation record. + SetOncePointer function_closure_; + SetOncePointer function_context_; + + // Temporary storage for building node input lists. + int input_buffer_size_; + Node** input_buffer_; + // Node representing the control dependency for dead code. + SetOncePointer dead_control_; + + // Node representing the current context within the function body. + Node* current_context_; + + // Merge of all control nodes that exit the function body. + Node* exit_control_; + + // Result of loop assignment analysis performed before graph creation. + LoopAssignmentAnalysis* loop_assignment_analysis_; + + // Growth increment for the temporary buffer used to construct input lists to + // new nodes. + static const int kInputBufferSizeIncrement = 64; + + Zone* local_zone() const { return local_zone_; } + Environment* environment() { return environment_; } AstContext* ast_context() const { return ast_context_; } BreakableScope* breakable() const { return breakable_; } ContextScope* execution_context() const { return execution_context_; } + CommonOperatorBuilder* common() const { return jsgraph_->common(); } + CompilationInfo* info() const { return info_; } + StrictMode strict_mode() const; + JSGraph* jsgraph() { return jsgraph_; } + Graph* graph() { return jsgraph_->graph(); } + Zone* graph_zone() { return graph()->zone(); } + JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } + ZoneVector>* globals() { return &globals_; } + inline Scope* current_scope() const; + Node* current_context() const { return current_context_; } + Node* dead_control(); + Node* exit_control() const { return exit_control_; } void set_ast_context(AstContext* ctx) { ast_context_ = ctx; } void set_breakable(BreakableScope* brk) { breakable_ = brk; } void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; } + void set_exit_control(Node* exit) { exit_control_ = exit; } + void set_current_context(Node* ctx) { current_context_ = ctx; } + void set_environment(Environment* env) { environment_ = env; } - // Support for control flow builders. The concrete type of the environment - // depends on the graph builder, but environments themselves are not virtual. - typedef StructuredGraphBuilder::Environment BaseEnvironment; - BaseEnvironment* CopyEnvironment(BaseEnvironment* env) OVERRIDE; + // Node creation helpers. + Node* NewNode(const Operator* op, bool incomplete = false) { + return MakeNode(op, 0, static_cast(NULL), incomplete); + } - // Getters for values in the activation record. - Node* GetFunctionClosure(); - Node* GetFunctionContext(); + Node* NewNode(const Operator* op, Node* n1) { + return MakeNode(op, 1, &n1, false); + } + + Node* NewNode(const Operator* op, Node* n1, Node* n2) { + Node* buffer[] = {n1, n2}; + return MakeNode(op, arraysize(buffer), buffer, false); + } + + Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { + Node* buffer[] = {n1, n2, n3}; + return MakeNode(op, arraysize(buffer), buffer, false); + } + + Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { + Node* buffer[] = {n1, n2, n3, n4}; + return MakeNode(op, arraysize(buffer), buffer, false); + } + + Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, + Node* n5) { + Node* buffer[] = {n1, n2, n3, n4, n5}; + return MakeNode(op, arraysize(buffer), buffer, false); + } + + Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, + Node* n5, Node* n6) { + Node* nodes[] = {n1, n2, n3, n4, n5, n6}; + return MakeNode(op, arraysize(nodes), nodes, false); + } + + Node* NewNode(const Operator* op, int value_input_count, Node** value_inputs, + bool incomplete = false) { + return MakeNode(op, value_input_count, value_inputs, incomplete); + } + + // Creates a new Phi node having {count} input values. + Node* NewPhi(int count, Node* input, Node* control); + Node* NewEffectPhi(int count, Node* input, Node* control); + + // Helpers for merging control, effect or value dependencies. + Node* MergeControl(Node* control, Node* other); + Node* MergeEffect(Node* value, Node* other, Node* control); + Node* MergeValue(Node* value, Node* other, Node* control); + + // The main node creation chokepoint. Adds context, frame state, effect, + // and control dependencies depending on the operator. + Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, + bool incomplete); + + // Helper to indicate a node exits the function body. + void UpdateControlDependencyToLeaveFunction(Node* exit); // // The following build methods all generate graph fragments and return one @@ -120,47 +247,13 @@ class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { // If so, record the stack height into the compilation and return {true}. bool CheckOsrEntry(IterationStatement* stmt); -#define DECLARE_VISIT(type) void Visit##type(type* node) OVERRIDE; - - // Visiting functions for AST nodes make this an AstVisitor. - AST_NODE_LIST(DECLARE_VISIT) -#undef DECLARE_VISIT - - // Visiting function for declarations list is overridden. - void VisitDeclarations(ZoneList* declarations) OVERRIDE; - - private: - CompilationInfo* info_; - AstContext* ast_context_; - JSGraph* jsgraph_; - - // List of global declarations for functions and variables. - ZoneVector> globals_; - - // Stack of breakable statements entered by the visitor. - BreakableScope* breakable_; - - // Stack of context objects pushed onto the chain by the visitor. - ContextScope* execution_context_; - - // Nodes representing values in the activation record. - SetOncePointer function_closure_; - SetOncePointer function_context_; - - // The node representing the OSR entry into the loop, if any. - SetOncePointer osr_loop_entry_; - - // Result of loop assignment analysis performed before graph creation. - LoopAssignmentAnalysis* loop_assignment_analysis_; - - CompilationInfo* info() const { return info_; } - inline StrictMode strict_mode() const; - JSGraph* jsgraph() { return jsgraph_; } - JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } - ZoneVector>* globals() { return &globals_; } + // Helper to wrap a Handle into a Unique. + template + Unique MakeUnique(Handle object) { + return Unique::CreateUninitialized(object); + } - // Current scope during visitation. - inline Scope* current_scope() const; + Node** EnsureInputBufferSize(int size); // Named and keyed loads require a VectorSlotPair for successful lowering. VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const; @@ -226,11 +319,9 @@ class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { // // [parameters (+receiver)] [locals] [operand stack] // -class AstGraphBuilder::Environment - : public StructuredGraphBuilder::Environment { +class AstGraphBuilder::Environment : public ZoneObject { public: Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); - Environment(const Environment& copy); int parameters_count() const { return parameters_count_; } int locals_count() const { return locals_count_; } @@ -295,20 +386,67 @@ class AstGraphBuilder::Environment // further mutation of the environment will not affect checkpoints. Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine); - protected: - AstGraphBuilder* builder() const { - return reinterpret_cast( - StructuredGraphBuilder::Environment::builder()); + // Control dependency tracked by this environment. + Node* GetControlDependency() { return control_dependency_; } + void UpdateControlDependency(Node* dependency) { + control_dependency_ = dependency; } - private: - void UpdateStateValues(Node** state_values, int offset, int count); + // Effect dependency tracked by this environment. + Node* GetEffectDependency() { return effect_dependency_; } + void UpdateEffectDependency(Node* dependency) { + effect_dependency_ = dependency; + } + + // Mark this environment as being unreachable. + void MarkAsUnreachable() { + UpdateControlDependency(builder()->dead_control()); + } + bool IsMarkedAsUnreachable() { + return GetControlDependency()->opcode() == IrOpcode::kDead; + } + + // Merge another environment into this one. + void Merge(Environment* other); + + // Copies this environment at a control-flow split point. + Environment* CopyForConditional() { return Copy(); } + // Copies this environment to a potentially unreachable control-flow point. + Environment* CopyAsUnreachable() { + Environment* env = Copy(); + env->MarkAsUnreachable(); + return env; + } + + // Copies this environment at a loop header control-flow point. + Environment* CopyForLoop(BitVector* assigned, bool is_osr = false) { + PrepareForLoop(assigned, is_osr); + return Copy(); + } + + private: + AstGraphBuilder* builder_; int parameters_count_; int locals_count_; + NodeVector values_; + Node* control_dependency_; + Node* effect_dependency_; Node* parameters_node_; Node* locals_node_; Node* stack_node_; + + explicit Environment(const Environment* copy); + Environment* Copy() { return new (zone()) Environment(this); } + void UpdateStateValues(Node** state_values, int offset, int count); + Zone* zone() const { return builder_->local_zone(); } + Graph* graph() const { return builder_->graph(); } + AstGraphBuilder* builder() const { return builder_; } + CommonOperatorBuilder* common() { return builder_->common(); } + NodeVector* values() { return &values_; } + + // Prepare environment to be used as loop header. + void PrepareForLoop(BitVector* assigned, bool is_osr = false); }; diff --git a/src/compiler/control-builders.h b/src/compiler/control-builders.h index ba04107..7ab12d8 100644 --- a/src/compiler/control-builders.h +++ b/src/compiler/control-builders.h @@ -7,7 +7,7 @@ #include "src/v8.h" -#include "src/compiler/graph-builder.h" +#include "src/compiler/ast-graph-builder.h" #include "src/compiler/node.h" namespace v8 { @@ -19,8 +19,7 @@ namespace compiler { // used to model breakable statements. class ControlBuilder { public: - explicit ControlBuilder(StructuredGraphBuilder* builder) - : builder_(builder) {} + explicit ControlBuilder(AstGraphBuilder* builder) : builder_(builder) {} virtual ~ControlBuilder() {} // Interface for break and continue. @@ -28,8 +27,8 @@ class ControlBuilder { virtual void Continue() { UNREACHABLE(); } protected: - typedef StructuredGraphBuilder Builder; - typedef StructuredGraphBuilder::Environment Environment; + typedef AstGraphBuilder Builder; + typedef AstGraphBuilder::Environment Environment; Zone* zone() const { return builder_->local_zone(); } Environment* environment() { return builder_->environment(); } @@ -42,7 +41,7 @@ class ControlBuilder { // Tracks control flow for a conditional statement. class IfBuilder FINAL : public ControlBuilder { public: - explicit IfBuilder(StructuredGraphBuilder* builder) + explicit IfBuilder(AstGraphBuilder* builder) : ControlBuilder(builder), then_environment_(NULL), else_environment_(NULL) {} @@ -62,7 +61,7 @@ class IfBuilder FINAL : public ControlBuilder { // Tracks control flow for an iteration statement. class LoopBuilder FINAL : public ControlBuilder { public: - explicit LoopBuilder(StructuredGraphBuilder* builder) + explicit LoopBuilder(AstGraphBuilder* builder) : ControlBuilder(builder), loop_environment_(NULL), continue_environment_(NULL), @@ -91,7 +90,7 @@ class LoopBuilder FINAL : public ControlBuilder { // Tracks control flow for a switch statement. class SwitchBuilder FINAL : public ControlBuilder { public: - explicit SwitchBuilder(StructuredGraphBuilder* builder, int case_count) + explicit SwitchBuilder(AstGraphBuilder* builder, int case_count) : ControlBuilder(builder), body_environment_(NULL), label_environment_(NULL), @@ -124,7 +123,7 @@ class SwitchBuilder FINAL : public ControlBuilder { // Tracks control flow for a block statement. class BlockBuilder FINAL : public ControlBuilder { public: - explicit BlockBuilder(StructuredGraphBuilder* builder) + explicit BlockBuilder(AstGraphBuilder* builder) : ControlBuilder(builder), break_environment_(NULL) {} // Primitive control commands. diff --git a/src/compiler/graph-builder.cc b/src/compiler/graph-builder.cc deleted file mode 100644 index aa268c0..0000000 --- a/src/compiler/graph-builder.cc +++ /dev/null @@ -1,300 +0,0 @@ -// Copyright 2013 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/graph-builder.h" - -#include "src/bit-vector.h" -#include "src/compiler.h" -#include "src/compiler/graph-visualizer.h" -#include "src/compiler/node.h" -#include "src/compiler/node-properties.h" -#include "src/compiler/operator-properties.h" - -namespace v8 { -namespace internal { -namespace compiler { - - -StructuredGraphBuilder::StructuredGraphBuilder(Isolate* isolate, - Zone* local_zone, Graph* graph, - CommonOperatorBuilder* common) - : GraphBuilder(isolate, graph), - common_(common), - environment_(NULL), - local_zone_(local_zone), - input_buffer_size_(0), - input_buffer_(NULL), - current_context_(NULL), - exit_control_(NULL) { - EnsureInputBufferSize(kInputBufferSizeIncrement); -} - - -Node** StructuredGraphBuilder::EnsureInputBufferSize(int size) { - if (size > input_buffer_size_) { - size += kInputBufferSizeIncrement; - input_buffer_ = local_zone()->NewArray(size); - } - return input_buffer_; -} - - -Node* StructuredGraphBuilder::MakeNode(const Operator* op, - int value_input_count, - Node** value_inputs, bool incomplete) { - DCHECK(op->ValueInputCount() == value_input_count); - - bool has_context = OperatorProperties::HasContextInput(op); - bool has_framestate = OperatorProperties::HasFrameStateInput(op); - bool has_control = op->ControlInputCount() == 1; - bool has_effect = op->EffectInputCount() == 1; - - DCHECK(op->ControlInputCount() < 2); - DCHECK(op->EffectInputCount() < 2); - - Node* result = NULL; - if (!has_context && !has_framestate && !has_control && !has_effect) { - result = graph()->NewNode(op, value_input_count, value_inputs, incomplete); - } else { - int input_count_with_deps = value_input_count; - if (has_context) ++input_count_with_deps; - if (has_framestate) ++input_count_with_deps; - if (has_control) ++input_count_with_deps; - if (has_effect) ++input_count_with_deps; - Node** buffer = EnsureInputBufferSize(input_count_with_deps); - memcpy(buffer, value_inputs, kPointerSize * value_input_count); - Node** current_input = buffer + value_input_count; - if (has_context) { - *current_input++ = current_context(); - } - if (has_framestate) { - // The frame state will be inserted later. Here we misuse - // the dead_control node as a sentinel to be later overwritten - // with the real frame state. - *current_input++ = dead_control(); - } - if (has_effect) { - *current_input++ = environment_->GetEffectDependency(); - } - if (has_control) { - *current_input++ = environment_->GetControlDependency(); - } - result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete); - if (has_effect) { - environment_->UpdateEffectDependency(result); - } - if (result->op()->ControlOutputCount() > 0 && - !environment()->IsMarkedAsUnreachable()) { - environment_->UpdateControlDependency(result); - } - } - - return result; -} - - -void StructuredGraphBuilder::UpdateControlDependencyToLeaveFunction( - Node* exit) { - if (environment()->IsMarkedAsUnreachable()) return; - if (exit_control() != NULL) { - exit = MergeControl(exit_control(), exit); - } - environment()->MarkAsUnreachable(); - set_exit_control(exit); -} - - -StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment( - Environment* env) { - return new (local_zone()) Environment(*env); -} - - -StructuredGraphBuilder::Environment::Environment( - StructuredGraphBuilder* builder, Node* control_dependency) - : builder_(builder), - control_dependency_(control_dependency), - effect_dependency_(control_dependency), - values_(zone()) {} - - -StructuredGraphBuilder::Environment::Environment(const Environment& copy) - : builder_(copy.builder()), - control_dependency_(copy.control_dependency_), - effect_dependency_(copy.effect_dependency_), - values_(copy.zone()) { - const size_t kStackEstimate = 7; // optimum from experimentation! - values_.reserve(copy.values_.size() + kStackEstimate); - values_.insert(values_.begin(), copy.values_.begin(), copy.values_.end()); -} - - -void StructuredGraphBuilder::Environment::Merge(Environment* other) { - DCHECK(values_.size() == other->values_.size()); - - // Nothing to do if the other environment is dead. - if (other->IsMarkedAsUnreachable()) return; - - // Resurrect a dead environment by copying the contents of the other one and - // placing a singleton merge as the new control dependency. - if (this->IsMarkedAsUnreachable()) { - Node* other_control = other->control_dependency_; - Node* inputs[] = {other_control}; - control_dependency_ = - graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true); - effect_dependency_ = other->effect_dependency_; - values_ = other->values_; - return; - } - - // Create a merge of the control dependencies of both environments and update - // the current environment's control dependency accordingly. - Node* control = builder_->MergeControl(this->GetControlDependency(), - other->GetControlDependency()); - UpdateControlDependency(control); - - // Create a merge of the effect dependencies of both environments and update - // the current environment's effect dependency accordingly. - Node* effect = builder_->MergeEffect(this->GetEffectDependency(), - other->GetEffectDependency(), control); - UpdateEffectDependency(effect); - - // Introduce Phi nodes for values that have differing input at merge points, - // potentially extending an existing Phi node if possible. - for (int i = 0; i < static_cast(values_.size()); ++i) { - values_[i] = builder_->MergeValue(values_[i], other->values_[i], control); - } -} - - -void StructuredGraphBuilder::Environment::PrepareForLoop(BitVector* assigned, - bool is_osr) { - int size = static_cast(values()->size()); - - Node* control = builder_->NewLoop(); - if (assigned == nullptr) { - // Assume that everything is updated in the loop. - for (int i = 0; i < size; ++i) { - Node* phi = builder_->NewPhi(1, values()->at(i), control); - values()->at(i) = phi; - } - } else { - // Only build phis for those locals assigned in this loop. - for (int i = 0; i < size; ++i) { - if (i < assigned->length() && !assigned->Contains(i)) continue; - Node* phi = builder_->NewPhi(1, values()->at(i), control); - values()->at(i) = phi; - } - } - Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control); - UpdateEffectDependency(effect); - - if (is_osr) { - // Merge OSR values as inputs to the phis of the loop. - Graph* graph = builder_->graph(); - Node* osr_loop_entry = builder_->graph()->NewNode( - builder_->common()->OsrLoopEntry(), graph->start(), graph->start()); - - builder_->MergeControl(control, osr_loop_entry); - builder_->MergeEffect(effect, osr_loop_entry, control); - - for (int i = 0; i < size; ++i) { - Node* val = values()->at(i); - if (!IrOpcode::IsConstantOpcode(val->opcode())) { - Node* osr_value = - graph->NewNode(builder_->common()->OsrValue(i), osr_loop_entry); - values()->at(i) = builder_->MergeValue(val, osr_value, control); - } - } - } -} - - -Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) { - const Operator* phi_op = common()->Phi(kMachAnyTagged, count); - Node** buffer = EnsureInputBufferSize(count + 1); - MemsetPointer(buffer, input, count); - buffer[count] = control; - return graph()->NewNode(phi_op, count + 1, buffer, true); -} - - -// TODO(mstarzinger): Revisit this once we have proper effect states. -Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input, - Node* control) { - const Operator* phi_op = common()->EffectPhi(count); - Node** buffer = EnsureInputBufferSize(count + 1); - MemsetPointer(buffer, input, count); - buffer[count] = control; - return graph()->NewNode(phi_op, count + 1, buffer, true); -} - - -Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) { - int inputs = control->op()->ControlInputCount() + 1; - if (control->opcode() == IrOpcode::kLoop) { - // Control node for loop exists, add input. - const Operator* op = common()->Loop(inputs); - control->AppendInput(graph_zone(), other); - control->set_op(op); - } else if (control->opcode() == IrOpcode::kMerge) { - // Control node for merge exists, add input. - const Operator* op = common()->Merge(inputs); - control->AppendInput(graph_zone(), other); - control->set_op(op); - } else { - // Control node is a singleton, introduce a merge. - const Operator* op = common()->Merge(inputs); - Node* inputs[] = {control, other}; - control = graph()->NewNode(op, arraysize(inputs), inputs, true); - } - return control; -} - - -Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other, - Node* control) { - int inputs = control->op()->ControlInputCount(); - if (value->opcode() == IrOpcode::kEffectPhi && - NodeProperties::GetControlInput(value) == control) { - // Phi already exists, add input. - value->set_op(common()->EffectPhi(inputs)); - value->InsertInput(graph_zone(), inputs - 1, other); - } else if (value != other) { - // Phi does not exist yet, introduce one. - value = NewEffectPhi(inputs, value, control); - value->ReplaceInput(inputs - 1, other); - } - return value; -} - - -Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other, - Node* control) { - int inputs = control->op()->ControlInputCount(); - if (value->opcode() == IrOpcode::kPhi && - NodeProperties::GetControlInput(value) == control) { - // Phi already exists, add input. - value->set_op(common()->Phi(kMachAnyTagged, inputs)); - value->InsertInput(graph_zone(), inputs - 1, other); - } else if (value != other) { - // Phi does not exist yet, introduce one. - value = NewPhi(inputs, value, control); - value->ReplaceInput(inputs - 1, other); - } - return value; -} - - -Node* StructuredGraphBuilder::dead_control() { - if (!dead_control_.is_set()) { - Node* dead_node = graph()->NewNode(common_->Dead()); - dead_control_.set(dead_node); - return dead_node; - } - return dead_control_.get(); -} -} -} -} // namespace v8::internal::compiler diff --git a/src/compiler/graph-builder.h b/src/compiler/graph-builder.h index 8374675..947c576 100644 --- a/src/compiler/graph-builder.h +++ b/src/compiler/graph-builder.h @@ -15,13 +15,8 @@ namespace v8 { namespace internal { - -class BitVector; - namespace compiler { -class Node; - // A common base class for anything that creates nodes in a graph. class GraphBuilder { public: @@ -82,168 +77,6 @@ class GraphBuilder { Graph* graph_; }; - -// The StructuredGraphBuilder produces a high-level IR graph. It is used as the -// base class for concrete implementations (e.g the AstGraphBuilder or the -// StubGraphBuilder). -class StructuredGraphBuilder : public GraphBuilder { - public: - StructuredGraphBuilder(Isolate* isolate, Zone* zone, Graph* graph, - CommonOperatorBuilder* common); - ~StructuredGraphBuilder() OVERRIDE {} - - // Creates a new Phi node having {count} input values. - Node* NewPhi(int count, Node* input, Node* control); - Node* NewEffectPhi(int count, Node* input, Node* control); - - // Helpers for merging control, effect or value dependencies. - Node* MergeControl(Node* control, Node* other); - Node* MergeEffect(Node* value, Node* other, Node* control); - Node* MergeValue(Node* value, Node* other, Node* control); - - // Helpers to create new control nodes. - Node* NewIfTrue() { return NewNode(common()->IfTrue()); } - Node* NewIfFalse() { return NewNode(common()->IfFalse()); } - Node* NewMerge() { return NewNode(common()->Merge(1), true); } - Node* NewLoop() { return NewNode(common()->Loop(1), true); } - Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { - return NewNode(common()->Branch(hint), condition); - } - - protected: - class Environment; - friend class Environment; - friend class ControlBuilder; - - // The following method creates a new node having the specified operator and - // ensures effect and control dependencies are wired up. The dependencies - // tracked by the environment might be mutated. - Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, - bool incomplete) FINAL; - - Environment* environment() const { return environment_; } - void set_environment(Environment* env) { environment_ = env; } - - Node* current_context() const { return current_context_; } - void set_current_context(Node* context) { current_context_ = context; } - - Node* exit_control() const { return exit_control_; } - void set_exit_control(Node* node) { exit_control_ = node; } - - Node* dead_control(); - - Zone* graph_zone() const { return graph()->zone(); } - Zone* local_zone() const { return local_zone_; } - CommonOperatorBuilder* common() const { return common_; } - - // Helper to wrap a Handle into a Unique. - template - Unique MakeUnique(Handle object) { - return Unique::CreateUninitialized(object); - } - - // Support for control flow builders. The concrete type of the environment - // depends on the graph builder, but environments themselves are not virtual. - virtual Environment* CopyEnvironment(Environment* env); - - // Helper to indicate a node exits the function body. - void UpdateControlDependencyToLeaveFunction(Node* exit); - - private: - CommonOperatorBuilder* common_; - Environment* environment_; - - // Zone local to the builder for data not leaking into the graph. - Zone* local_zone_; - - // Temporary storage for building node input lists. - int input_buffer_size_; - Node** input_buffer_; - - // Node representing the control dependency for dead code. - SetOncePointer dead_control_; - - // Node representing the current context within the function body. - Node* current_context_; - - // Merge of all control nodes that exit the function body. - Node* exit_control_; - - // Growth increment for the temporary buffer used to construct input lists to - // new nodes. - static const int kInputBufferSizeIncrement = 64; - - Node** EnsureInputBufferSize(int size); - - DISALLOW_COPY_AND_ASSIGN(StructuredGraphBuilder); -}; - - -// The abstract execution environment contains static knowledge about -// execution state at arbitrary control-flow points. It allows for -// simulation of the control-flow at compile time. -class StructuredGraphBuilder::Environment : public ZoneObject { - public: - Environment(StructuredGraphBuilder* builder, Node* control_dependency); - Environment(const Environment& copy); - - // Control dependency tracked by this environment. - Node* GetControlDependency() { return control_dependency_; } - void UpdateControlDependency(Node* dependency) { - control_dependency_ = dependency; - } - - // Effect dependency tracked by this environment. - Node* GetEffectDependency() { return effect_dependency_; } - void UpdateEffectDependency(Node* dependency) { - effect_dependency_ = dependency; - } - - // Mark this environment as being unreachable. - void MarkAsUnreachable() { - UpdateControlDependency(builder()->dead_control()); - } - bool IsMarkedAsUnreachable() { - return GetControlDependency()->opcode() == IrOpcode::kDead; - } - - // Merge another environment into this one. - void Merge(Environment* other); - - // Copies this environment at a control-flow split point. - Environment* CopyForConditional() { return builder()->CopyEnvironment(this); } - - // Copies this environment to a potentially unreachable control-flow point. - Environment* CopyAsUnreachable() { - Environment* env = builder()->CopyEnvironment(this); - env->MarkAsUnreachable(); - return env; - } - - // Copies this environment at a loop header control-flow point. - Environment* CopyForLoop(BitVector* assigned, bool is_osr = false) { - PrepareForLoop(assigned, is_osr); - return builder()->CopyEnvironment(this); - } - - Node* GetContext() { return builder_->current_context(); } - - protected: - Zone* zone() const { return builder_->local_zone(); } - Graph* graph() const { return builder_->graph(); } - StructuredGraphBuilder* builder() const { return builder_; } - CommonOperatorBuilder* common() { return builder_->common(); } - NodeVector* values() { return &values_; } - - // Prepare environment to be used as loop header. - void PrepareForLoop(BitVector* assigned, bool is_osr = false); - - private: - StructuredGraphBuilder* builder_; - Node* control_dependency_; - Node* effect_dependency_; - NodeVector values_; -}; } } } // namespace v8::internal::compiler diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 9538646..d70247f 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -441,7 +441,6 @@ '../../src/compiler/gap-resolver.cc', '../../src/compiler/gap-resolver.h', '../../src/compiler/generic-algorithm.h', - '../../src/compiler/graph-builder.cc', '../../src/compiler/graph-builder.h', '../../src/compiler/graph-inl.h', '../../src/compiler/graph-reducer.cc', -- 2.7.4