// 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_BYTECODE_GRAPH_BUILDER_H_ #define V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_ #include "src/compiler/bytecode-analysis.h" #include "src/compiler/js-graph.h" #include "src/compiler/js-type-hint-lowering.h" #include "src/compiler/state-values-utils.h" #include "src/interpreter/bytecode-array-iterator.h" #include "src/interpreter/bytecode-flags.h" #include "src/interpreter/bytecodes.h" #include "src/source-position-table.h" namespace v8 { namespace internal { class VectorSlotPair; namespace compiler { class Reduction; class SourcePositionTable; // The BytecodeGraphBuilder produces a high-level IR graph based on // interpreter bytecodes. class BytecodeGraphBuilder { public: BytecodeGraphBuilder( Zone* local_zone, Handle shared, Handle feedback_vector, BailoutId osr_offset, JSGraph* jsgraph, CallFrequency& invocation_frequency, SourcePositionTable* source_positions, Handle native_context, int inlining_id = SourcePosition::kNotInlined, JSTypeHintLowering::Flags flags = JSTypeHintLowering::kNoFlags, bool stack_check = true, bool analyze_environment_liveness = true); // Creates a graph by visiting bytecodes. void CreateGraph(); private: class Environment; class OsrIteratorState; struct SubEnvironment; void RemoveMergeEnvironmentsBeforeOffset(int limit_offset); void AdvanceToOsrEntryAndPeelLoops( interpreter::BytecodeArrayIterator* iterator, SourcePositionTableIterator* source_position_iterator); void VisitSingleBytecode( SourcePositionTableIterator* source_position_iterator); void VisitBytecodes(); // Get or create the node that represents the outer function closure. Node* GetFunctionClosure(); // Builder for loading the a native context field. Node* BuildLoadNativeContextField(int index); // Helper function for creating a pair containing type feedback vector and // a feedback slot. VectorSlotPair CreateVectorSlotPair(int slot_id); void set_environment(Environment* env) { environment_ = env; } const Environment* environment() const { return environment_; } Environment* environment() { return environment_; } // Node creation helpers Node* NewNode(const Operator* op, bool incomplete = false) { return MakeNode(op, 0, static_cast(nullptr), incomplete); } Node* NewNode(const Operator* op, Node* n1) { Node* buffer[] = {n1}; return MakeNode(op, arraysize(buffer), buffer, 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* n6) { Node* buffer[] = {n1, n2, n3, n4, n5, n6}; return MakeNode(op, arraysize(buffer), buffer, false); } // Helpers to create new control nodes. Node* NewIfTrue() { return NewNode(common()->IfTrue()); } Node* NewIfFalse() { return NewNode(common()->IfFalse()); } Node* NewIfValue(int32_t value) { return NewNode(common()->IfValue(value)); } Node* NewIfDefault() { return NewNode(common()->IfDefault()); } Node* NewMerge() { return NewNode(common()->Merge(1), true); } Node* NewLoop() { return NewNode(common()->Loop(1), true); } Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone, IsSafetyCheck is_safety_check = IsSafetyCheck::kSafetyCheck) { return NewNode(common()->Branch(hint, is_safety_check), condition); } Node* NewSwitch(Node* condition, int control_output_count) { return NewNode(common()->Switch(control_output_count), condition); } // 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* effect, Node* other_effect, Node* control); Node* MergeValue(Node* value, Node* other_value, 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* const* value_inputs, bool incomplete); Node** EnsureInputBufferSize(int size); Node* const* GetCallArgumentsFromRegisters(Node* callee, Node* receiver, interpreter::Register first_arg, int arg_count); Node* const* ProcessCallVarArgs(ConvertReceiverMode receiver_mode, Node* callee, interpreter::Register first_reg, int arg_count); Node* ProcessCallArguments(const Operator* call_op, Node* const* args, int arg_count); Node* ProcessCallArguments(const Operator* call_op, Node* callee, interpreter::Register receiver, size_t reg_count); Node* const* GetConstructArgumentsFromRegister( Node* target, Node* new_target, interpreter::Register first_arg, int arg_count); Node* ProcessConstructArguments(const Operator* op, Node* const* args, int arg_count); Node* ProcessCallRuntimeArguments(const Operator* call_runtime_op, interpreter::Register receiver, size_t reg_count); // 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(); // 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, OutputFrameStateCombine combine); void BuildCreateArguments(CreateArgumentsType type); Node* BuildLoadGlobal(Handle name, uint32_t feedback_slot_index, TypeofMode typeof_mode); enum class StoreMode { // Check the prototype chain before storing. kNormal, // Store value to the receiver without checking the prototype chain. kOwn, }; void BuildNamedStore(StoreMode store_mode); void BuildLdaLookupSlot(TypeofMode typeof_mode); void BuildLdaLookupContextSlot(TypeofMode typeof_mode); void BuildLdaLookupGlobalSlot(TypeofMode typeof_mode); void BuildCallVarArgs(ConvertReceiverMode receiver_mode); void BuildCall(ConvertReceiverMode receiver_mode, Node* const* args, size_t arg_count, int slot_id); void BuildCall(ConvertReceiverMode receiver_mode, std::initializer_list args, int slot_id) { BuildCall(receiver_mode, args.begin(), args.size(), slot_id); } void BuildUnaryOp(const Operator* op); void BuildBinaryOp(const Operator* op); void BuildBinaryOpWithImmediate(const Operator* op); void BuildCompareOp(const Operator* op); void BuildDelete(LanguageMode language_mode); void BuildCastOperator(const Operator* op); void BuildHoleCheckAndThrow(Node* condition, Runtime::FunctionId runtime_id, Node* name = nullptr); // Optional early lowering to the simplified operator level. Note that // the result has already been wired into the environment just like // any other invocation of {NewNode} would do. JSTypeHintLowering::LoweringResult TryBuildSimplifiedUnaryOp( const Operator* op, Node* operand, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedBinaryOp( const Operator* op, Node* left, Node* right, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInNext( Node* receiver, Node* cache_array, Node* cache_type, Node* index, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInPrepare( Node* receiver, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedToNumber( Node* input, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedCall(const Operator* op, Node* const* args, int arg_count, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedConstruct( const Operator* op, Node* const* args, int arg_count, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadNamed( const Operator* op, Node* receiver, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadKeyed( const Operator* op, Node* receiver, Node* key, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreNamed( const Operator* op, Node* receiver, Node* value, FeedbackSlot slot); JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreKeyed( const Operator* op, Node* receiver, Node* key, Node* value, FeedbackSlot slot); // Applies the given early reduction onto the current environment. void ApplyEarlyReduction(JSTypeHintLowering::LoweringResult reduction); // Check the context chain for extensions, for lookup fast paths. Environment* CheckContextExtensions(uint32_t depth); // Helper function to create binary operation hint from the recorded // type feedback. BinaryOperationHint GetBinaryOperationHint(int operand_index); // Helper function to create compare operation hint from the recorded // type feedback. CompareOperationHint GetCompareOperationHint(); // Helper function to create for-in mode from the recorded type feedback. ForInMode GetForInMode(int operand_index); // Helper function to compute call frequency from the recorded type // feedback. CallFrequency ComputeCallFrequency(int slot_id) const; // Helper function to extract the speculation mode from the recorded type // feedback. SpeculationMode GetSpeculationMode(int slot_id) const; // Control flow plumbing. void BuildJump(); void BuildJumpIf(Node* condition); void BuildJumpIfNot(Node* condition); void BuildJumpIfEqual(Node* comperand); void BuildJumpIfNotEqual(Node* comperand); void BuildJumpIfTrue(); void BuildJumpIfFalse(); void BuildJumpIfToBooleanTrue(); void BuildJumpIfToBooleanFalse(); void BuildJumpIfNotHole(); void BuildJumpIfJSReceiver(); void BuildSwitchOnSmi(Node* condition); void BuildSwitchOnGeneratorState( const ZoneVector& resume_jump_targets, bool allow_fallthrough_on_executing); // Simulates control flow by forward-propagating environments. void MergeIntoSuccessorEnvironment(int target_offset); void BuildLoopHeaderEnvironment(int current_offset); void SwitchToMergeEnvironment(int current_offset); // Simulates control flow that exits the function body. void MergeControlToLeaveFunction(Node* exit); // Builds loop exit nodes for every exited loop between the current bytecode // offset and {target_offset}. void BuildLoopExitsForBranch(int target_offset); void BuildLoopExitsForFunctionExit(const BytecodeLivenessState* liveness); void BuildLoopExitsUntilLoop(int loop_offset, const BytecodeLivenessState* liveness); // Helper for building a return (from an actual return or a suspend). void BuildReturn(const BytecodeLivenessState* liveness); // Simulates entry and exit of exception handlers. void ExitThenEnterExceptionHandlers(int current_offset); // Update the current position of the {SourcePositionTable} to that of the // bytecode at {offset}, if any. void UpdateSourcePosition(SourcePositionTableIterator* it, int offset); // Growth increment for the temporary buffer used to construct input lists to // new nodes. static const int kInputBufferSizeIncrement = 64; // An abstract representation for an exception handler that is being // entered and exited while the graph builder is iterating over the // underlying bytecode. The exception handlers within the bytecode are // well scoped, hence will form a stack during iteration. struct ExceptionHandler { int start_offset_; // Start offset of the handled area in the bytecode. int end_offset_; // End offset of the handled area in the bytecode. int handler_offset_; // Handler entry offset within the bytecode. int context_register_; // Index of register holding handler context. }; // Field accessors Graph* graph() const { return jsgraph_->graph(); } CommonOperatorBuilder* common() const { return jsgraph_->common(); } Zone* graph_zone() const { return graph()->zone(); } JSGraph* jsgraph() const { return jsgraph_; } Isolate* isolate() const { return jsgraph_->isolate(); } JSOperatorBuilder* javascript() const { return jsgraph_->javascript(); } SimplifiedOperatorBuilder* simplified() const { return jsgraph_->simplified(); } Zone* local_zone() const { return local_zone_; } const Handle& bytecode_array() const { return bytecode_array_; } const Handle& feedback_vector() const { return feedback_vector_; } const JSTypeHintLowering& type_hint_lowering() const { return type_hint_lowering_; } const FrameStateFunctionInfo* frame_state_function_info() const { return frame_state_function_info_; } const interpreter::BytecodeArrayIterator& bytecode_iterator() const { return *bytecode_iterator_; } void set_bytecode_iterator( interpreter::BytecodeArrayIterator* bytecode_iterator) { bytecode_iterator_ = bytecode_iterator; } const BytecodeAnalysis* bytecode_analysis() const { return bytecode_analysis_; } void set_bytecode_analysis(const BytecodeAnalysis* bytecode_analysis) { bytecode_analysis_ = bytecode_analysis; } int currently_peeled_loop_offset() const { return currently_peeled_loop_offset_; } void set_currently_peeled_loop_offset(int offset) { currently_peeled_loop_offset_ = offset; } bool stack_check() const { return stack_check_; } void set_stack_check(bool stack_check) { stack_check_ = stack_check; } bool analyze_environment_liveness() const { return analyze_environment_liveness_; } int current_exception_handler() { return current_exception_handler_; } void set_current_exception_handler(int index) { current_exception_handler_ = index; } bool needs_eager_checkpoint() const { return needs_eager_checkpoint_; } void mark_as_needing_eager_checkpoint(bool value) { needs_eager_checkpoint_ = value; } Handle native_context() const { return native_context_; } #define DECLARE_VISIT_BYTECODE(name, ...) void Visit##name(); BYTECODE_LIST(DECLARE_VISIT_BYTECODE) #undef DECLARE_VISIT_BYTECODE Zone* local_zone_; JSGraph* jsgraph_; CallFrequency const invocation_frequency_; Handle bytecode_array_; Handle feedback_vector_; const JSTypeHintLowering type_hint_lowering_; const FrameStateFunctionInfo* frame_state_function_info_; const interpreter::BytecodeArrayIterator* bytecode_iterator_; const BytecodeAnalysis* bytecode_analysis_; Environment* environment_; BailoutId osr_offset_; int currently_peeled_loop_offset_; bool stack_check_; bool analyze_environment_liveness_; // Merge environments are snapshots of the environment at points where the // control flow merges. This models a forward data flow propagation of all // values from all predecessors of the merge in question. They are indexed by // the bytecode offset ZoneMap merge_environments_; // Generator merge environments are snapshots of the current resume // environment, tracing back through loop headers to the resume switch of a // generator. They allow us to model a single resume jump as several switch // statements across loop headers, keeping those loop headers reducible, // without having to merge the "executing" environments of the generator into // the "resuming" ones. They are indexed by the suspend id of the resume. ZoneMap generator_merge_environments_; // Exception handlers currently entered by the iteration. ZoneStack exception_handlers_; int current_exception_handler_; // Temporary storage for building node input lists. int input_buffer_size_; Node** input_buffer_; // Optimization to only create checkpoints when the current position in the // control-flow is not effect-dominated by another checkpoint already. All // operations that do not have observable side-effects can be re-evaluated. bool needs_eager_checkpoint_; // Nodes representing values in the activation record. SetOncePointer function_closure_; // Control nodes that exit the function body. ZoneVector exit_controls_; StateValuesCache state_values_cache_; // The source position table, to be populated. SourcePositionTable* source_positions_; SourcePosition const start_position_; // The native context for which we optimize. Handle const native_context_; static int const kBinaryOperationHintIndex = 1; static int const kCountOperationHintIndex = 0; static int const kBinaryOperationSmiHintIndex = 1; static int const kUnaryOperationHintIndex = 0; DISALLOW_COPY_AND_ASSIGN(BytecodeGraphBuilder); }; } // namespace compiler } // namespace internal } // namespace v8 #endif // V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_