// 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/ast/ast.h" #include "src/compiler/compiler-source-position-table.h" #include "src/compiler/js-graph.h" #include "src/compiler/liveness-analyzer.h" #include "src/compiler/state-values-utils.h" namespace v8 { namespace internal { // Forward declarations. class BitVector; class CompilationInfo; namespace compiler { // Forward declarations. class ControlBuilder; class Graph; class LoopAssignmentAnalysis; class LoopBuilder; class Node; class TypeHintAnalysis; // 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. // This AstVistor is not final, and provides the AstVisitor methods as virtual // methods so they can be specialized by subclasses. class AstGraphBuilder : public AstVisitor<AstGraphBuilder> { public: AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, float invocation_frequency, LoopAssignmentAnalysis* loop_assignment = nullptr, TypeHintAnalysis* type_hint_analysis = nullptr); virtual ~AstGraphBuilder() {} // Creates a graph by visiting the entire AST. bool CreateGraph(bool stack_check = true); // 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) virtual void Visit##type(type* node); // 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(Declaration::List* declarations); private: class AstContext; class AstEffectContext; class AstValueContext; class AstTestContext; class ContextScope; class ControlScope; class ControlScopeForBreakable; class ControlScopeForIteration; class ControlScopeForCatch; class ControlScopeForFinally; class Environment; friend class ControlBuilder; Isolate* isolate_; Zone* local_zone_; CompilationInfo* info_; JSGraph* jsgraph_; float const invocation_frequency_; Environment* environment_; AstContext* ast_context_; // List of global declarations for functions and variables. ZoneVector<Handle<Object>> globals_; // Stack of control scopes currently entered by the visitor. ControlScope* execution_control_; // 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_; SetOncePointer<Node> new_target_; // Tracks how many try-blocks are currently entered. int try_nesting_level_; // Temporary storage for building node input lists. int input_buffer_size_; Node** input_buffer_; // Optimization to cache loaded feedback vector. SetOncePointer<Node> feedback_vector_; // Optimization to cache empty frame state. SetOncePointer<Node> empty_frame_state_; // Control nodes that exit the function body. ZoneVector<Node*> exit_controls_; // Result of loop assignment analysis performed before graph creation. LoopAssignmentAnalysis* loop_assignment_analysis_; // Result of type hint analysis performed before graph creation. TypeHintAnalysis* type_hint_analysis_; // Cache for StateValues nodes for frame states. StateValuesCache state_values_cache_; // Analyzer of local variable liveness. LivenessAnalyzer liveness_analyzer_; // Function info for frame state construction. const FrameStateFunctionInfo* const frame_state_function_info_; // 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() const { return environment_; } AstContext* ast_context() const { return ast_context_; } ControlScope* execution_control() const { return execution_control_; } ContextScope* execution_context() const { return execution_context_; } CommonOperatorBuilder* common() const { return jsgraph_->common(); } CompilationInfo* info() const { return info_; } Isolate* isolate() const { return isolate_; } LanguageMode language_mode() const; JSGraph* jsgraph() { return jsgraph_; } Graph* graph() { return jsgraph_->graph(); } Zone* graph_zone() { return graph()->zone(); } JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } ZoneVector<Handle<Object>>* globals() { return &globals_; } Scope* current_scope() const; Node* current_context() const; LivenessAnalyzer* liveness_analyzer() { return &liveness_analyzer_; } const FrameStateFunctionInfo* frame_state_function_info() const { return frame_state_function_info_; } void set_environment(Environment* env) { environment_ = env; } void set_ast_context(AstContext* ctx) { ast_context_ = ctx; } void set_execution_control(ControlScope* ctrl) { execution_control_ = ctrl; } void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; } // Create the main graph body by visiting the AST. void CreateGraphBody(bool stack_check); // Get or create the node that represents the incoming function closure. Node* GetFunctionClosureForContext(); Node* GetFunctionClosure(); // Get or create the node that represents the incoming function context. Node* GetFunctionContext(); // Get or create the node that represents the incoming new target value. Node* GetNewTarget(); // Get or create the node that represents the empty frame state. Node* GetEmptyFrameState(); // Node creation helpers. Node* NewNode(const Operator* op, bool incomplete = false) { return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete); } 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); // Prepare information for lazy deoptimization. This information is attached // to the given node and the output value produced by the node is combined. // Conceptually this frame state is "after" a given operation. void PrepareFrameState(Node* node, BailoutId ast_id, OutputFrameStateCombine framestate_combine = OutputFrameStateCombine::Ignore()); // Prepare information for eager deoptimization. This information is carried // by dedicated {Checkpoint} nodes that are wired into the effect chain. // Conceptually this frame state is "before" a given operation. void PrepareEagerCheckpoint(BailoutId ast_id); BitVector* GetVariablesAssignedInLoop(IterationStatement* stmt); // Check if the given statement is an OSR entry. // If so, record the stack height into the compilation and return {true}. bool CheckOsrEntry(IterationStatement* stmt); // Computes local variable liveness and replaces dead variables in // frame states with the undefined values. void ClearNonLiveSlotsInFrameStates(); Node** EnsureInputBufferSize(int size); // Named and keyed loads require a VectorSlotPair for successful lowering. VectorSlotPair CreateVectorSlotPair(FeedbackVectorSlot slot) const; // Determine which contexts need to be checked for extension objects that // might shadow the optimistic declaration of dynamic lookup variables. uint32_t ComputeBitsetForDynamicGlobal(Variable* variable); uint32_t ComputeBitsetForDynamicContext(Variable* variable); // Computes the frequency for JSCallFunction and JSCallConstruct nodes. float ComputeCallFrequency(FeedbackVectorSlot slot) const; // =========================================================================== // 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. // Builders to create local function, script and block contexts. Node* BuildLocalActivationContext(Node* context); Node* BuildLocalFunctionContext(Scope* scope); Node* BuildLocalScriptContext(Scope* scope); Node* BuildLocalBlockContext(Scope* scope); // Builder to create an arguments object if it is used. Node* BuildArgumentsObject(Variable* arguments); // Builder to create an array of rest parameters if used. Node* BuildRestArgumentsArray(Variable* rest); // Builder that assigns to the {.this_function} internal variable if needed. Node* BuildThisFunctionVariable(Variable* this_function_var); // Builder that assigns to the {new.target} internal variable if needed. Node* BuildNewTargetVariable(Variable* new_target_var); // Builders for variable load and assignment. Node* BuildVariableAssignment(Variable* variable, Node* value, Token::Value op, const VectorSlotPair& slot, BailoutId bailout_id, OutputFrameStateCombine framestate_combine = OutputFrameStateCombine::Ignore()); Node* BuildVariableDelete(Variable* variable, BailoutId bailout_id, OutputFrameStateCombine framestate_combine); Node* BuildVariableLoad(Variable* variable, BailoutId bailout_id, const VectorSlotPair& feedback, OutputFrameStateCombine framestate_combine, TypeofMode typeof_mode = NOT_INSIDE_TYPEOF); // Builders for property loads and stores. Node* BuildKeyedLoad(Node* receiver, Node* key, const VectorSlotPair& feedback); Node* BuildNamedLoad(Node* receiver, Handle<Name> name, const VectorSlotPair& feedback); Node* BuildKeyedStore(Node* receiver, Node* key, Node* value, const VectorSlotPair& feedback); Node* BuildNamedStore(Node* receiver, Handle<Name> name, Node* value, const VectorSlotPair& feedback); // Builders for super property loads and stores. Node* BuildKeyedSuperStore(Node* receiver, Node* home_object, Node* key, Node* value); Node* BuildNamedSuperStore(Node* receiver, Node* home_object, Handle<Name> name, Node* value); Node* BuildNamedSuperLoad(Node* receiver, Node* home_object, Handle<Name> name, const VectorSlotPair& feedback); Node* BuildKeyedSuperLoad(Node* receiver, Node* home_object, Node* key, const VectorSlotPair& feedback); // Builders for global variable loads and stores. Node* BuildGlobalLoad(Handle<Name> name, const VectorSlotPair& feedback, TypeofMode typeof_mode); Node* BuildGlobalStore(Handle<Name> name, Node* value, const VectorSlotPair& feedback); // Builders for dynamic variable loads and stores. Node* BuildDynamicLoad(Handle<Name> name, TypeofMode typeof_mode); Node* BuildDynamicStore(Handle<Name> name, Node* value); // Builders for accessing the function context. Node* BuildLoadGlobalObject(); Node* BuildLoadNativeContextField(int index); // Builders for automatic type conversion. Node* BuildToBoolean(Node* input, TypeFeedbackId feedback_id); Node* BuildToName(Node* input, BailoutId bailout_id); Node* BuildToObject(Node* input, BailoutId bailout_id); // Builder for adding the [[HomeObject]] to a value if the value came from a // function literal and needs a home object. Do nothing otherwise. Node* BuildSetHomeObject(Node* value, Node* home_object, LiteralProperty* property, int slot_number = 0); // Builders for error reporting at runtime. Node* BuildThrowError(Node* exception, BailoutId bailout_id); Node* BuildThrowReferenceError(Variable* var, BailoutId bailout_id); Node* BuildThrowConstAssignError(BailoutId bailout_id); Node* BuildThrowStaticPrototypeError(BailoutId bailout_id); Node* BuildThrowUnsupportedSuperError(BailoutId bailout_id); // Builders for dynamic hole-checks at runtime. Node* BuildHoleCheckThenThrow(Node* value, Variable* var, Node* not_hole, BailoutId bailout_id); Node* BuildHoleCheckElseThrow(Node* value, Variable* var, Node* for_hole, BailoutId bailout_id); // Builders for conditional errors. Node* BuildThrowIfStaticPrototype(Node* name, BailoutId bailout_id); // Builders for non-local control flow. Node* BuildReturn(Node* return_value); Node* BuildThrow(Node* exception_value); // Builders for binary operations. Node* BuildBinaryOp(Node* left, Node* right, Token::Value op, TypeFeedbackId feedback_id); // 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); // =========================================================================== // The following build methods have the same contract as the above ones, but // they can also return {nullptr} to indicate that no fragment was built. Note // that these are optimizations, disabling any of them should still produce // correct graphs. // Optimization for variable load from global object. Node* TryLoadGlobalConstant(Handle<Name> name); // Optimization for variable load of dynamic lookup slot that is most likely // to resolve to a global slot or context slot (inferred from scope chain). Node* TryLoadDynamicVariable(Variable* variable, Handle<String> name, BailoutId bailout_id, const VectorSlotPair& feedback, OutputFrameStateCombine combine, TypeofMode typeof_mode); // Optimizations for automatic type conversion. Node* TryFastToBoolean(Node* input); Node* TryFastToName(Node* input); // =========================================================================== // The following visitation methods all recursively visit a subtree of the // underlying AST and extent the graph. The operand stack is mutated in a way // consistent with other compilers: // - Expressions pop operands and push result, depending on {AstContext}. // - Statements keep the operand stack balanced. // Visit statements. void VisitIfNotNull(Statement* stmt); void VisitInScope(Statement* stmt, Scope* scope, Node* context); // Visit expressions. void Visit(Expression* expr); void VisitForTest(Expression* expr); void VisitForEffect(Expression* expr); void VisitForValue(Expression* expr); void VisitForValueOrNull(Expression* expr); void VisitForValueOrTheHole(Expression* expr); void VisitForValues(ZoneList<Expression*>* exprs); // Common for all IterationStatement bodies. void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, BailoutId stack_check_id); // Dispatched from VisitCall. void VisitCallSuper(Call* expr); // 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 VisitTypeof, VisitLiteralCompareTypeof. void VisitTypeofExpression(Expression* expr); // Dispatched from VisitBinaryOperation. void VisitComma(BinaryOperation* expr); void VisitLogicalExpression(BinaryOperation* expr); void VisitArithmeticExpression(BinaryOperation* expr); // Dispatched from VisitCompareOperation. void VisitLiteralCompareNil(CompareOperation* expr, Expression* sub_expr, Node* nil_value); void VisitLiteralCompareTypeof(CompareOperation* expr, Expression* sub_expr, Handle<String> check); // Dispatched from VisitForInStatement. void VisitForInAssignment(Expression* expr, Node* value, const VectorSlotPair& feedback, BailoutId bailout_id); // Dispatched from VisitObjectLiteral. void VisitObjectLiteralAccessor(Node* home_object, ObjectLiteralProperty* property); 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 ZoneObject { public: Environment(AstGraphBuilder* builder, DeclarationScope* scope, Node* control_dependency); int parameters_count() const { return parameters_count_; } int locals_count() const { return locals_count_; } int context_chain_length() { return static_cast<int>(contexts_.size()); } int stack_height() { return static_cast<int>(values()->size()) - parameters_count_ - locals_count_; } // Operations on parameter or local variables. void Bind(Variable* variable, Node* node); Node* Lookup(Variable* variable); void MarkAllLocalsLive(); // Raw operations on parameter variables. void RawParameterBind(int index, Node* node); Node* RawParameterLookup(int index); // Operations on the context chain. Node* Context() const { return contexts_.back(); } void PushContext(Node* context) { contexts()->push_back(context); } void PopContext() { contexts()->pop_back(); } void TrimContextChain(int trim_to_length) { contexts()->resize(trim_to_length); } // 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()); } void TrimStack(int trim_to_height) { int depth = stack_height() - trim_to_height; 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 = OutputFrameStateCombine::Ignore(), bool node_has_exception = false); // Inserts a loop exit control node and renames the environment. // This is useful for loop peeling to insert phis at loop exits. void PrepareForLoopExit(Node* loop, BitVector* assigned_variables); // 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()->jsgraph()->Dead()); liveness_block_ = nullptr; } 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(); // Copies this environment to a potentially unreachable control-flow point. Environment* CopyAsUnreachable(); // Copies this environment at a loop header control-flow point. Environment* CopyForLoop(BitVector* assigned, bool is_osr = false); // Copies this environment for Osr entry. This only produces environment // of the right shape, the caller is responsible for filling in the right // values and dependencies. Environment* CopyForOsrEntry(); private: AstGraphBuilder* builder_; int parameters_count_; int locals_count_; LivenessAnalyzerBlock* liveness_block_; NodeVector values_; NodeVector contexts_; Node* control_dependency_; Node* effect_dependency_; Node* parameters_node_; Node* locals_node_; Node* stack_node_; explicit Environment(Environment* copy, LivenessAnalyzerBlock* liveness_block); Environment* CopyAndShareLiveness(); 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_; } NodeVector* contexts() { return &contexts_; } LivenessAnalyzerBlock* liveness_block() { return liveness_block_; } bool IsLivenessAnalysisEnabled(); bool IsLivenessBlockConsistent(); // Prepare environment to be used as loop header. void PrepareForLoop(BitVector* assigned); void PrepareForOsrEntry(); }; class AstGraphBuilderWithPositions final : public AstGraphBuilder { public: AstGraphBuilderWithPositions(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, float invocation_frequency, LoopAssignmentAnalysis* loop_assignment, TypeHintAnalysis* type_hint_analysis, SourcePositionTable* source_positions, int inlining_id = SourcePosition::kNotInlined); bool CreateGraph(bool stack_check = true) { SourcePositionTable::Scope pos_scope(source_positions_, start_position_); return AstGraphBuilder::CreateGraph(stack_check); } #define DEF_VISIT(type) \ void Visit##type(type* node) override { \ SourcePositionTable::Scope pos( \ source_positions_, \ SourcePosition(node->position(), start_position_.InliningId())); \ AstGraphBuilder::Visit##type(node); \ } AST_NODE_LIST(DEF_VISIT) #undef DEF_VISIT private: SourcePositionTable* const source_positions_; SourcePosition const start_position_; }; } // namespace compiler } // namespace internal } // namespace v8 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_