| // Copyright 2014 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_AST_GRAPH_BUILDER_H_ |
| #define V8_COMPILER_AST_GRAPH_BUILDER_H_ |
| |
| #include "src/v8.h" |
| |
| #include "src/ast.h" |
| #include "src/compiler/graph-builder.h" |
| #include "src/compiler/js-graph.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| class ControlBuilder; |
| class Graph; |
| class LoopAssignmentAnalysis; |
| class LoopBuilder; |
| |
| // 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 { |
| public: |
| AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, |
| LoopAssignmentAnalysis* loop_assignment = NULL); |
| |
| // Creates a graph by visiting the entire AST. |
| bool CreateGraph(); |
| |
| protected: |
| class AstContext; |
| class AstEffectContext; |
| class AstValueContext; |
| class AstTestContext; |
| class BreakableScope; |
| class ContextScope; |
| class Environment; |
| |
| Environment* environment() { |
| return reinterpret_cast<Environment*>( |
| StructuredGraphBuilder::environment()); |
| } |
| |
| AstContext* ast_context() const { return ast_context_; } |
| BreakableScope* breakable() const { return breakable_; } |
| ContextScope* execution_context() const { return execution_context_; } |
| |
| 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; } |
| |
| // 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; |
| |
| // Getters for values in the activation record. |
| Node* GetFunctionClosure(); |
| Node* GetFunctionContext(); |
| |
| // |
| // The following build methods all generate graph fragments and return one |
| // resulting node. The operand stack height remains the same, variables and |
| // other dependencies tracked by the environment might be mutated though. |
| // |
| |
| // Builder to create a receiver check for sloppy mode. |
| Node* BuildPatchReceiverToGlobalProxy(Node* receiver); |
| |
| // Builder to create a local function context. |
| Node* BuildLocalFunctionContext(Node* context, Node* closure); |
| |
| // Builder to create an arguments object if it is used. |
| Node* BuildArgumentsObject(Variable* arguments); |
| |
| // Builders for variable load and assignment. |
| Node* BuildVariableAssignment(Variable* var, Node* value, Token::Value op, |
| BailoutId bailout_id, |
| OutputFrameStateCombine state_combine = |
| OutputFrameStateCombine::Ignore()); |
| Node* BuildVariableDelete(Variable* var, BailoutId bailout_id, |
| OutputFrameStateCombine state_combine); |
| Node* BuildVariableLoad(Variable* var, BailoutId bailout_id, |
| const VectorSlotPair& feedback, |
| ContextualMode mode = CONTEXTUAL); |
| |
| // Builders for accessing the function context. |
| Node* BuildLoadBuiltinsObject(); |
| Node* BuildLoadGlobalObject(); |
| Node* BuildLoadGlobalProxy(); |
| Node* BuildLoadClosure(); |
| Node* BuildLoadObjectField(Node* object, int offset); |
| |
| // Builders for automatic type conversion. |
| Node* BuildToBoolean(Node* value); |
| |
| // Builders for error reporting at runtime. |
| Node* BuildThrowReferenceError(Variable* var, BailoutId bailout_id); |
| Node* BuildThrowConstAssignError(BailoutId bailout_id); |
| |
| // Builders for dynamic hole-checks at runtime. |
| Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole); |
| Node* BuildHoleCheckThrow(Node* value, Variable* var, Node* not_hole, |
| BailoutId bailout_id); |
| |
| // Builders for binary operations. |
| Node* BuildBinaryOp(Node* left, Node* right, Token::Value op); |
| |
| // Builder for stack-check guards. |
| Node* BuildStackCheck(); |
| |
| #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<Declaration*>* declarations) OVERRIDE; |
| |
| private: |
| CompilationInfo* info_; |
| AstContext* ast_context_; |
| JSGraph* jsgraph_; |
| |
| // List of global declarations for functions and variables. |
| ZoneVector<Handle<Object>> 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<Node> function_closure_; |
| SetOncePointer<Node> function_context_; |
| |
| // 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<Handle<Object>>* globals() { return &globals_; } |
| |
| // Current scope during visitation. |
| inline Scope* current_scope() const; |
| |
| // Named and keyed loads require a VectorSlotPair for successful lowering. |
| VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const; |
| |
| // Process arguments to a call by popping {arity} elements off the operand |
| // stack and build a call node using the given call operator. |
| Node* ProcessArguments(const Operator* op, int arity); |
| |
| // Visit statements. |
| void VisitIfNotNull(Statement* stmt); |
| |
| // Visit expressions. |
| void Visit(Expression* expr); |
| void VisitForTest(Expression* expr); |
| void VisitForEffect(Expression* expr); |
| void VisitForValue(Expression* expr); |
| void VisitForValueOrNull(Expression* expr); |
| void VisitForValues(ZoneList<Expression*>* exprs); |
| |
| // Common for all IterationStatement bodies. |
| void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int); |
| |
| // Dispatched from VisitCallRuntime. |
| void VisitCallJSRuntime(CallRuntime* expr); |
| |
| // Dispatched from VisitUnaryOperation. |
| void VisitDelete(UnaryOperation* expr); |
| void VisitVoid(UnaryOperation* expr); |
| void VisitTypeof(UnaryOperation* expr); |
| void VisitNot(UnaryOperation* expr); |
| |
| // Dispatched from VisitBinaryOperation. |
| void VisitComma(BinaryOperation* expr); |
| void VisitLogicalExpression(BinaryOperation* expr); |
| void VisitArithmeticExpression(BinaryOperation* expr); |
| |
| // Dispatched from VisitForInStatement. |
| void VisitForInAssignment(Expression* expr, Node* value); |
| |
| // Builds deoptimization for a given node. |
| void PrepareFrameState( |
| Node* node, BailoutId ast_id, |
| OutputFrameStateCombine combine = OutputFrameStateCombine::Ignore()); |
| |
| BitVector* GetVariablesAssignedInLoop(IterationStatement* stmt); |
| |
| DEFINE_AST_VISITOR_SUBCLASS_MEMBERS(); |
| DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder); |
| }; |
| |
| |
| // The abstract execution environment for generated code consists of |
| // parameter variables, local variables and the operand stack. The |
| // environment will perform proper SSA-renaming of all tracked nodes |
| // at split and merge points in the control flow. Internally all the |
| // values are stored in one list using the following layout: |
| // |
| // [parameters (+receiver)] [locals] [operand stack] |
| // |
| class AstGraphBuilder::Environment |
| : public StructuredGraphBuilder::Environment { |
| 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_; } |
| int stack_height() { |
| return static_cast<int>(values()->size()) - parameters_count_ - |
| locals_count_; |
| } |
| |
| // Operations on parameter or local variables. The parameter indices are |
| // shifted by 1 (receiver is parameter index -1 but environment index 0). |
| void Bind(Variable* variable, Node* node) { |
| DCHECK(variable->IsStackAllocated()); |
| if (variable->IsParameter()) { |
| values()->at(variable->index() + 1) = node; |
| } else { |
| DCHECK(variable->IsStackLocal()); |
| values()->at(variable->index() + parameters_count_) = node; |
| } |
| } |
| Node* Lookup(Variable* variable) { |
| DCHECK(variable->IsStackAllocated()); |
| if (variable->IsParameter()) { |
| return values()->at(variable->index() + 1); |
| } else { |
| DCHECK(variable->IsStackLocal()); |
| return values()->at(variable->index() + parameters_count_); |
| } |
| } |
| |
| // Operations on the operand stack. |
| void Push(Node* node) { |
| values()->push_back(node); |
| } |
| Node* Top() { |
| DCHECK(stack_height() > 0); |
| return values()->back(); |
| } |
| Node* Pop() { |
| DCHECK(stack_height() > 0); |
| Node* back = values()->back(); |
| values()->pop_back(); |
| return back; |
| } |
| |
| // Direct mutations of the operand stack. |
| void Poke(int depth, Node* node) { |
| DCHECK(depth >= 0 && depth < stack_height()); |
| int index = static_cast<int>(values()->size()) - depth - 1; |
| values()->at(index) = node; |
| } |
| Node* Peek(int depth) { |
| DCHECK(depth >= 0 && depth < stack_height()); |
| int index = static_cast<int>(values()->size()) - depth - 1; |
| return values()->at(index); |
| } |
| void Drop(int depth) { |
| DCHECK(depth >= 0 && depth <= stack_height()); |
| values()->erase(values()->end() - depth, values()->end()); |
| } |
| |
| // Preserve a checkpoint of the environment for the IR graph. Any |
| // further mutation of the environment will not affect checkpoints. |
| Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine); |
| |
| protected: |
| AstGraphBuilder* builder() const { |
| return reinterpret_cast<AstGraphBuilder*>( |
| StructuredGraphBuilder::Environment::builder()); |
| } |
| |
| private: |
| void UpdateStateValues(Node** state_values, int offset, int count); |
| |
| int parameters_count_; |
| int locals_count_; |
| Node* parameters_node_; |
| Node* locals_node_; |
| Node* stack_node_; |
| }; |
| |
| |
| // Each expression in the AST is evaluated in a specific context. This context |
| // decides how the evaluation result is passed up the visitor. |
| class AstGraphBuilder::AstContext BASE_EMBEDDED { |
| public: |
| bool IsEffect() const { return kind_ == Expression::kEffect; } |
| bool IsValue() const { return kind_ == Expression::kValue; } |
| bool IsTest() const { return kind_ == Expression::kTest; } |
| |
| // Determines how to combine the frame state with the value |
| // that is about to be plugged into this AstContext. |
| OutputFrameStateCombine GetStateCombine() { |
| return IsEffect() ? OutputFrameStateCombine::Ignore() |
| : OutputFrameStateCombine::Push(); |
| } |
| |
| // Plug a node into this expression context. Call this function in tail |
| // position in the Visit functions for expressions. |
| virtual void ProduceValue(Node* value) = 0; |
| |
| // Unplugs a node from this expression context. Call this to retrieve the |
| // result of another Visit function that already plugged the context. |
| virtual Node* ConsumeValue() = 0; |
| |
| // Shortcut for "context->ProduceValue(context->ConsumeValue())". |
| void ReplaceValue() { ProduceValue(ConsumeValue()); } |
| |
| protected: |
| AstContext(AstGraphBuilder* owner, Expression::Context kind); |
| virtual ~AstContext(); |
| |
| AstGraphBuilder* owner() const { return owner_; } |
| Environment* environment() const { return owner_->environment(); } |
| |
| // We want to be able to assert, in a context-specific way, that the stack |
| // height makes sense when the context is filled. |
| #ifdef DEBUG |
| int original_height_; |
| #endif |
| |
| private: |
| Expression::Context kind_; |
| AstGraphBuilder* owner_; |
| AstContext* outer_; |
| }; |
| |
| |
| // Context to evaluate expression for its side effects only. |
| class AstGraphBuilder::AstEffectContext FINAL : public AstContext { |
| public: |
| explicit AstEffectContext(AstGraphBuilder* owner) |
| : AstContext(owner, Expression::kEffect) {} |
| ~AstEffectContext() FINAL; |
| void ProduceValue(Node* value) FINAL; |
| Node* ConsumeValue() FINAL; |
| }; |
| |
| |
| // Context to evaluate expression for its value (and side effects). |
| class AstGraphBuilder::AstValueContext FINAL : public AstContext { |
| public: |
| explicit AstValueContext(AstGraphBuilder* owner) |
| : AstContext(owner, Expression::kValue) {} |
| ~AstValueContext() FINAL; |
| void ProduceValue(Node* value) FINAL; |
| Node* ConsumeValue() FINAL; |
| }; |
| |
| |
| // Context to evaluate expression for a condition value (and side effects). |
| class AstGraphBuilder::AstTestContext FINAL : public AstContext { |
| public: |
| explicit AstTestContext(AstGraphBuilder* owner) |
| : AstContext(owner, Expression::kTest) {} |
| ~AstTestContext() FINAL; |
| void ProduceValue(Node* value) FINAL; |
| Node* ConsumeValue() FINAL; |
| }; |
| |
| |
| // Scoped class tracking breakable statements entered by the visitor. Allows to |
| // properly 'break' and 'continue' iteration statements as well as to 'break' |
| // from blocks within switch statements. |
| class AstGraphBuilder::BreakableScope BASE_EMBEDDED { |
| public: |
| BreakableScope(AstGraphBuilder* owner, BreakableStatement* target, |
| ControlBuilder* control, int drop_extra) |
| : owner_(owner), |
| target_(target), |
| next_(owner->breakable()), |
| control_(control), |
| drop_extra_(drop_extra) { |
| owner_->set_breakable(this); // Push. |
| } |
| |
| ~BreakableScope() { |
| owner_->set_breakable(next_); // Pop. |
| } |
| |
| // Either 'break' or 'continue' the target statement. |
| void BreakTarget(BreakableStatement* target); |
| void ContinueTarget(BreakableStatement* target); |
| |
| private: |
| AstGraphBuilder* owner_; |
| BreakableStatement* target_; |
| BreakableScope* next_; |
| ControlBuilder* control_; |
| int drop_extra_; |
| |
| // Find the correct scope for the target statement. Note that this also drops |
| // extra operands from the environment for each scope skipped along the way. |
| BreakableScope* FindBreakable(BreakableStatement* target); |
| }; |
| |
| |
| // Scoped class tracking context objects created by the visitor. Represents |
| // mutations of the context chain within the function body and allows to |
| // change the current {scope} and {context} during visitation. |
| class AstGraphBuilder::ContextScope BASE_EMBEDDED { |
| public: |
| ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context) |
| : owner_(owner), |
| next_(owner->execution_context()), |
| outer_(owner->current_context()), |
| scope_(scope) { |
| owner_->set_execution_context(this); // Push. |
| owner_->set_current_context(context); |
| } |
| |
| ~ContextScope() { |
| owner_->set_execution_context(next_); // Pop. |
| owner_->set_current_context(outer_); |
| } |
| |
| // Current scope during visitation. |
| Scope* scope() const { return scope_; } |
| |
| private: |
| AstGraphBuilder* owner_; |
| ContextScope* next_; |
| Node* outer_; |
| Scope* scope_; |
| }; |
| |
| Scope* AstGraphBuilder::current_scope() const { |
| return execution_context_->scope(); |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |
| |
| #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ |