// Copyright 2015 the V8 project authors. All rights reserved.

// Use of this source code is governed by a BSD-style license that can be

// found in the LICENSE file.

#include "src/compiler/bytecode-graph-builder.h"

#include "src/ast/ast.h"

#include "src/base/platform/wrappers.h"

#include "src/codegen/source-position-table.h"

#include "src/codegen/tick-counter.h"

#include "src/common/assert-scope.h"

#include "src/compiler/access-builder.h"

#include "src/compiler/bytecode-analysis.h"

#include "src/compiler/common-operator.h"

#include "src/compiler/compiler-source-position-table.h"

#include "src/compiler/js-heap-broker.h"

#include "src/compiler/linkage.h"

#include "src/compiler/node-matchers.h"

#include "src/compiler/node-observer.h"

#include "src/compiler/operator-properties.h"

#include "src/compiler/simplified-operator.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/objects/js-array-inl.h"

#include "src/objects/js-generator.h"

#include "src/objects/literal-objects-inl.h"

#include "src/objects/objects-inl.h"

#include "src/objects/smi.h"

#include "src/objects/template-objects-inl.h"

namespace v8 {

namespace internal {

namespace compiler {

class BytecodeGraphBuilder {

public:

BytecodeGraphBuilder(JSHeapBroker* broker, Zone* local_zone,

NativeContextRef const& native_context,

SharedFunctionInfoRef const& shared_info,

FeedbackCellRef const& feedback_cell,

BytecodeOffset osr_offset, JSGraph* jsgraph,

CallFrequency const& invocation_frequency,

SourcePositionTable* source_positions, int inlining_id,

CodeKind code_kind, BytecodeGraphBuilderFlags flags,

TickCounter* tick_counter,

ObserveNodeInfo const& observe_node_info);

BytecodeGraphBuilder(const BytecodeGraphBuilder&) = delete;

BytecodeGraphBuilder& operator=(const BytecodeGraphBuilder&) = delete;

// Creates a graph by visiting bytecodes.

void CreateGraph();

private:

class Environment;

class OsrIteratorState;

struct SubEnvironment;

void RemoveMergeEnvironmentsBeforeOffset(int limit_offset);

void AdvanceToOsrEntryAndPeelLoops();

// Advance {bytecode_iterator} to the given offset. If possible, also advance

// {source_position_iterator} while updating the source position table.

void AdvanceIteratorsTo(int bytecode_offset);

void VisitSingleBytecode();

void VisitBytecodes();

// Get or create the node that represents the outer function closure.

Node* GetFunctionClosure();

// Get or create the node for this parameter index. If such a node is

// already cached, it is returned directly and the {debug_name_hint} is

// ignored.

Node* GetParameter(int index, const char* debug_name_hint = nullptr);

CodeKind code_kind() const { return code_kind_; }

bool native_context_independent() const {

// TODO(jgruber,v8:8888): Remove dependent code.

return false;

}

bool is_turboprop() const { return code_kind_ == CodeKind::TURBOPROP; }

bool generate_full_feedback_collection() const {

// NCI code currently collects full feedback.

DCHECK_IMPLIES(native_context_independent(),

CollectFeedbackInGenericLowering());

return native_context_independent();

}

static JSTypeHintLowering::LoweringResult NoChange() {

return JSTypeHintLowering::LoweringResult::NoChange();

}

bool CanApplyTypeHintLowering(IrOpcode::Value opcode) const {

return !generate_full_feedback_collection() ||

!IrOpcode::IsFeedbackCollectingOpcode(opcode);

}

bool CanApplyTypeHintLowering(const Operator* op) const {

return CanApplyTypeHintLowering(static_cast<IrOpcode::Value>(op->opcode()));

}

// The node representing the current feedback vector is generated once prior

// to visiting bytecodes, and is later passed as input to other nodes that

// may need it.

// TODO(jgruber): Remove feedback_vector() and rename feedback_vector_node()

// to feedback_vector() once all uses of the direct heap object reference

// have been replaced with a Node* reference.

void CreateFeedbackVectorNode();

Node* BuildLoadFeedbackVector();

Node* feedback_vector_node() const {

DCHECK_NOT_NULL(feedback_vector_node_);

return feedback_vector_node_;

}

void CreateFeedbackCellNode();

Node* BuildLoadFeedbackCell();

Node* feedback_cell_node() const {

DCHECK_NOT_NULL(feedback_cell_node_);

return feedback_cell_node_;

}

// Same as above for the feedback vector node.

void CreateNativeContextNode();

Node* BuildLoadNativeContext();

Node* native_context_node() const {

DCHECK_NOT_NULL(native_context_node_);

return native_context_node_;

}

Node* BuildLoadFeedbackCell(int index);

// Checks the optimization marker and potentially triggers compilation or

// installs the finished code object.

// Only relevant for specific code kinds (see CodeKindCanTierUp).

void MaybeBuildTierUpCheck();

// Like bytecode, NCI code must collect call feedback to preserve proper

// behavior of inlining heuristics when tiering up to Turbofan in the future.

// The invocation count (how often a particular JSFunction has been called)

// is tracked by the callee. For bytecode, this happens in the

// InterpreterEntryTrampoline, for NCI code it happens here in the prologue.

void MaybeBuildIncrementInvocationCount();

// Builder for loading the a native context field.

Node* BuildLoadNativeContextField(int index);

// Helper function for creating a feedback source containing type feedback

// vector and a feedback slot.

FeedbackSource CreateFeedbackSource(int slot_id);

FeedbackSource CreateFeedbackSource(FeedbackSlot slot);

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<Node**>(nullptr), incomplete);

}

template <class... Args>

Node* NewNode(const Operator* op, Node* n0, Args... nodes) {

Node* buffer[] = {n0, nodes...};

return MakeNode(op, arraysize(buffer), buffer);

}

// 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 = false);

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* const* GetConstructArgumentsFromRegister(

Node* target, Node* new_target, interpreter::Register first_arg,

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.

//

// The low-level chokepoint - use the variants below instead.

void PrepareFrameState(Node* node, OutputFrameStateCombine combine,

BytecodeOffset bailout_id,

const BytecodeLivenessState* liveness);

// In the common case, frame states are conceptually "after" a given

// operation and at the current bytecode offset.

void PrepareFrameState(Node* node, OutputFrameStateCombine combine) {

if (!OperatorProperties::HasFrameStateInput(node->op())) return;

const int offset = bytecode_iterator().current_offset();

return PrepareFrameState(node, combine, BytecodeOffset(offset),

bytecode_analysis().GetOutLivenessFor(offset));

}

// For function-entry stack checks, they're conceptually "before" the first

// bytecode and at a special marker bytecode offset.

// In the case of FE stack checks, the current bytecode is also the first

// bytecode, so we use a special marker bytecode offset to signify a virtual

// bytecode before the first physical bytecode.

void PrepareFrameStateForFunctionEntryStackCheck(Node* node) {

DCHECK_EQ(bytecode_iterator().current_offset(), 0);

DCHECK(OperatorProperties::HasFrameStateInput(node->op()));

DCHECK(node->opcode() == IrOpcode::kJSStackCheck);

return PrepareFrameState(node, OutputFrameStateCombine::Ignore(),

BytecodeOffset(kFunctionEntryBytecodeOffset),

bytecode_analysis().GetInLivenessFor(0));

}

// For OSR-entry stack checks, they're conceptually "before" the first

// bytecode of the current loop. We implement this in a similar manner to

// function-entry (FE) stack checks above, i.e. we deopt at the predecessor

// of the current bytecode.

// In the case of OSR-entry stack checks, a physical predecessor bytecode

// exists: the JumpLoop bytecode. We attach to JumpLoop by using

// `bytecode_analysis().osr_bailout_id()` instead of current_offset (the

// former points at JumpLoop, the latter at the loop header, i.e. the target

// of JumpLoop).

void PrepareFrameStateForOSREntryStackCheck(Node* node) {

DCHECK_EQ(bytecode_iterator().current_offset(),

bytecode_analysis().osr_entry_point());

DCHECK(OperatorProperties::HasFrameStateInput(node->op()));

DCHECK(node->opcode() == IrOpcode::kJSStackCheck);

const int offset = bytecode_analysis().osr_bailout_id().ToInt();

return PrepareFrameState(node, OutputFrameStateCombine::Ignore(),

BytecodeOffset(offset),

bytecode_analysis().GetOutLivenessFor(offset));

}

void BuildCreateArguments(CreateArgumentsType type);

Node* BuildLoadGlobal(NameRef 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<Node*> 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 TryBuildSimplifiedGetIterator(

const Operator* op, Node* receiver, FeedbackSlot load_slot,

FeedbackSlot call_slot);

JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadNamed(

const Operator* op, 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);

// Slow path taken when we cannot figure out the current scope info.

Environment* CheckContextExtensionsSlowPath(uint32_t depth);

// Helper function that tries to get the current scope info.

base::Optional<ScopeInfoRef> TryGetScopeInfo();

// Helper function to create a context extension check.

Environment* CheckContextExtensionAtDepth(Environment* slow_environment,

uint32_t depth);

// Helper function to create for-in mode from the recorded type feedback.

ForInMode GetForInMode(FeedbackSlot slot);

// Helper function to compute call frequency from the recorded type

// feedback. Returns unknown if invocation count is unknown. Returns 0 if

// feedback is insufficient.

CallFrequency ComputeCallFrequency(int slot_id) const;

// Helper function to extract the speculation mode from the recorded type

// feedback. Returns kDisallowSpeculation if feedback is insufficient.

SpeculationMode GetSpeculationMode(int slot_id) const;

// Helper function to determine the call feedback relation from the recorded

// type feedback. Returns kUnrelated if feedback is insufficient.

CallFeedbackRelation ComputeCallFeedbackRelation(int slot_id) const;

// Helpers for building the implicit FunctionEntry and IterationBody

// StackChecks.

void BuildFunctionEntryStackCheck();

void BuildIterationBodyStackCheck();

void MaybeBuildOSREntryStackCheck();

// 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 BuildUpdateInterruptBudget(int delta);

void BuildSwitchOnSmi(Node* condition);

void BuildSwitchOnGeneratorState(

const ZoneVector<ResumeJumpTarget>& 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(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.

};

template <class T = Object>

typename ref_traits<T>::ref_type MakeRefForConstantForIndexOperand(

int operand_index) {

// The BytecodeArray itself was fetched by using a barrier so all reads

// from the constant pool are safe.

return MakeRefAssumeMemoryFence(

broker(), broker()->CanonicalPersistentHandle(Handle<T>::cast(

bytecode_iterator().GetConstantForIndexOperand(

operand_index, local_isolate_))));

}

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_; }

BytecodeArrayRef bytecode_array() const { return bytecode_array_; }

FeedbackVectorRef const& 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_;

}

SourcePositionTableIterator& source_position_iterator() {

return *source_position_iterator_.get();

}

interpreter::BytecodeArrayIterator const& bytecode_iterator() const {

return bytecode_iterator_;

}

interpreter::BytecodeArrayIterator& bytecode_iterator() {

return bytecode_iterator_;

}

BytecodeAnalysis const& bytecode_analysis() const {

return 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 skip_first_stack_check() const {

return skip_first_stack_and_tierup_check_;

}

bool skip_tierup_check() const {

return skip_first_stack_and_tierup_check_ || osr_;

}

int current_exception_handler() const { 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;

}

JSHeapBroker* broker() const { return broker_; }

NativeContextRef native_context() const { return native_context_; }

SharedFunctionInfoRef shared_info() const { return shared_info_; }

#define DECLARE_VISIT_BYTECODE(name, ...) void Visit##name();

BYTECODE_LIST(DECLARE_VISIT_BYTECODE)

#undef DECLARE_VISIT_BYTECODE

JSHeapBroker* const broker_;

LocalIsolate* const local_isolate_;

Zone* const local_zone_;

JSGraph* const jsgraph_;

// The native context for which we optimize.

NativeContextRef const native_context_;

SharedFunctionInfoRef const shared_info_;

BytecodeArrayRef const bytecode_array_;

FeedbackCellRef const feedback_cell_;

FeedbackVectorRef const feedback_vector_;

CallFrequency const invocation_frequency_;

JSTypeHintLowering const type_hint_lowering_;

const FrameStateFunctionInfo* const frame_state_function_info_;

std::unique_ptr<SourcePositionTableIterator> source_position_iterator_;

interpreter::BytecodeArrayIterator bytecode_iterator_;

BytecodeAnalysis const bytecode_analysis_;

Environment* environment_;

bool const osr_;

int currently_peeled_loop_offset_;

bool is_osr_entry_stack_check_pending_;

const bool skip_first_stack_and_tierup_check_;

// 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<int, Environment*> 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<int, Environment*> generator_merge_environments_;

ZoneVector<Node*> cached_parameters_;

// Exception handlers currently entered by the iteration.

ZoneStack<ExceptionHandler> exception_handlers_;

int current_exception_handler_;

// Temporary storage for building node input lists.

int input_buffer_size_;

Node** input_buffer_;

const CodeKind code_kind_;

Node* feedback_cell_node_;

Node* feedback_vector_node_;

Node* native_context_node_;

// 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<Node> function_closure_;

// Control nodes that exit the function body.

ZoneVector<Node*> exit_controls_;

StateValuesCache state_values_cache_;

// The source position table, to be populated.

SourcePositionTable* const source_positions_;

SourcePosition const start_position_;

TickCounter* const tick_counter_;

ObserveNodeInfo const observe_node_info_;

static constexpr int kBinaryOperationHintIndex = 1;

static constexpr int kBinaryOperationSmiHintIndex = 1;

static constexpr int kCompareOperationHintIndex = 1;

static constexpr int kCountOperationHintIndex = 0;

static constexpr int kUnaryOperationHintIndex = 0;

};

// The abstract execution environment simulates the content of the interpreter

// register file. The environment performs SSA-renaming of all tracked nodes at

// split and merge points in the control flow.

class BytecodeGraphBuilder::Environment : public ZoneObject {

public:

Environment(BytecodeGraphBuilder* builder, int register_count,

int parameter_count,

interpreter::Register incoming_new_target_or_generator,

Node* control_dependency);

// Specifies whether environment binding methods should attach frame state

// inputs to nodes representing the value being bound. This is done because

// the {OutputFrameStateCombine} is closely related to the binding method.

enum FrameStateAttachmentMode { kAttachFrameState, kDontAttachFrameState };

int parameter_count() const { return parameter_count_; }

int register_count() const { return register_count_; }

Node* LookupAccumulator() const;

Node* LookupRegister(interpreter::Register the_register) const;

Node* LookupGeneratorState() const;

void BindAccumulator(Node* node,

FrameStateAttachmentMode mode = kDontAttachFrameState);

void BindRegister(interpreter::Register the_register, Node* node,

FrameStateAttachmentMode mode = kDontAttachFrameState);

void BindRegistersToProjections(

interpreter::Register first_reg, Node* node,

FrameStateAttachmentMode mode = kDontAttachFrameState);

void BindGeneratorState(Node* node);

void RecordAfterState(Node* node,

FrameStateAttachmentMode mode = kDontAttachFrameState);

// Effect dependency tracked by this environment.

Node* GetEffectDependency() { return effect_dependency_; }

void UpdateEffectDependency(Node* dependency) {

effect_dependency_ = dependency;

}

// Preserve a checkpoint of the environment for the IR graph. Any

// further mutation of the environment will not affect checkpoints.

Node* Checkpoint(BytecodeOffset bytecode_offset,

OutputFrameStateCombine combine,

const BytecodeLivenessState* liveness);

// Control dependency tracked by this environment.

Node* GetControlDependency() const { return control_dependency_; }

void UpdateControlDependency(Node* dependency) {

control_dependency_ = dependency;

}

Node* Context() const { return context_; }

void SetContext(Node* new_context) { context_ = new_context; }

Environment* Copy();

void Merge(Environment* other, const BytecodeLivenessState* liveness);

void FillWithOsrValues();

void PrepareForLoop(const BytecodeLoopAssignments& assignments,

const BytecodeLivenessState* liveness);

void PrepareForLoopExit(Node* loop,

const BytecodeLoopAssignments& assignments,

const BytecodeLivenessState* liveness);

private:

friend Zone;

explicit Environment(const Environment* copy);

bool StateValuesRequireUpdate(Node** state_values, Node** values, int count);

void UpdateStateValues(Node** state_values, Node** values, int count);

Node* GetStateValuesFromCache(Node** values, int count,

const BitVector* liveness, int liveness_offset);

int RegisterToValuesIndex(interpreter::Register the_register) const;

Zone* zone() const { return builder_->local_zone(); }

Graph* graph() const { return builder_->graph(); }

CommonOperatorBuilder* common() const { return builder_->common(); }

BytecodeGraphBuilder* builder() const { return builder_; }

const NodeVector* values() const { return &values_; }

NodeVector* values() { return &values_; }

int register_base() const { return register_base_; }

int accumulator_base() const { return accumulator_base_; }

BytecodeGraphBuilder* builder_;

int register_count_;

int parameter_count_;

Node* context_;

Node* control_dependency_;

Node* effect_dependency_;

NodeVector values_;

Node* parameters_state_values_;

Node* generator_state_;

int register_base_;

int accumulator_base_;

};

// A helper for creating a temporary sub-environment for simple branches.

struct BytecodeGraphBuilder::SubEnvironment final {

public:

explicit SubEnvironment(BytecodeGraphBuilder* builder)

: builder_(builder), parent_(builder->environment()->Copy()) {}

~SubEnvironment() { builder_->set_environment(parent_); }

private:

BytecodeGraphBuilder* builder_;

BytecodeGraphBuilder::Environment* parent_;

};

// Issues:

// - Scopes - intimately tied to AST. Need to eval what is needed.

// - Need to resolve closure parameter treatment.

BytecodeGraphBuilder::Environment::Environment(

BytecodeGraphBuilder* builder, int register_count, int parameter_count,

interpreter::Register incoming_new_target_or_generator,

Node* control_dependency)

: builder_(builder),

register_count_(register_count),

parameter_count_(parameter_count),

control_dependency_(control_dependency),

effect_dependency_(control_dependency),

values_(builder->local_zone()),

parameters_state_values_(nullptr),

generator_state_(nullptr) {

// The layout of values_ is:

//

// [receiver] [parameters] [registers] [accumulator]

//

// parameter[0] is the receiver (this), parameters 1..N are the

// parameters supplied to the method (arg0..argN-1). The accumulator

// is stored separately.

// Parameters including the receiver

for (int i = 0; i < parameter_count; i++) {

const char* debug_name = (i == 0) ? "%this" : nullptr;

Node* parameter = builder->GetParameter(i, debug_name);

values()->push_back(parameter);

}

// Registers

register_base_ = static_cast<int>(values()->size());

Node* undefined_constant = builder->jsgraph()->UndefinedConstant();

values()->insert(values()->end(), register_count, undefined_constant);

// Accumulator

accumulator_base_ = static_cast<int>(values()->size());

values()->push_back(undefined_constant);

// Context

int context_index = Linkage::GetJSCallContextParamIndex(parameter_count);

context_ = builder->GetParameter(context_index, "%context");

// Incoming new.target or generator register

if (incoming_new_target_or_generator.is_valid()) {

int new_target_index =

Linkage::GetJSCallNewTargetParamIndex(parameter_count);

Node* new_target_node =

builder->GetParameter(new_target_index, "%new.target");

int values_index = RegisterToValuesIndex(incoming_new_target_or_generator);

values()->at(values_index) = new_target_node;

}

}

BytecodeGraphBuilder::Environment::Environment(

const BytecodeGraphBuilder::Environment* other)

: builder_(other->builder_),

register_count_(other->register_count_),

parameter_count_(other->parameter_count_),

context_(other->context_),

control_dependency_(other->control_dependency_),

effect_dependency_(other->effect_dependency_),

values_(other->zone()),

parameters_state_values_(other->parameters_state_values_),

generator_state_(other->generator_state_),

register_base_(other->register_base_),

accumulator_base_(other->accumulator_base_) {

values_ = other->values_;

}

int BytecodeGraphBuilder::Environment::RegisterToValuesIndex(

interpreter::Register the_register) const {

if (the_register.is_parameter()) {

return the_register.ToParameterIndex(parameter_count());

} else {

return the_register.index() + register_base();

}

}

Node* BytecodeGraphBuilder::Environment::LookupAccumulator() const {

return values()->at(accumulator_base_);

}

Node* BytecodeGraphBuilder::Environment::LookupGeneratorState() const {

DCHECK_NOT_NULL(generator_state_);

return generator_state_;

}

Node* BytecodeGraphBuilder::Environment::LookupRegister(

interpreter::Register the_register) const {

if (the_register.is_current_context()) {

return Context();

} else if (the_register.is_function_closure()) {

return builder()->GetFunctionClosure();

} else {

int values_index = RegisterToValuesIndex(the_register);

return values()->at(values_index);

}

}

void BytecodeGraphBuilder::Environment::BindAccumulator(

Node* node, FrameStateAttachmentMode mode) {

if (mode == FrameStateAttachmentMode::kAttachFrameState) {

builder()->PrepareFrameState(node, OutputFrameStateCombine::PokeAt(0));

}

values()->at(accumulator_base_) = node;

}

void BytecodeGraphBuilder::Environment::BindGeneratorState(Node* node) {

generator_state_ = node;

}

void BytecodeGraphBuilder::Environment::BindRegister(

interpreter::Register the_register, Node* node,

FrameStateAttachmentMode mode) {

int values_index = RegisterToValuesIndex(the_register);

if (mode == FrameStateAttachmentMode::kAttachFrameState) {

builder()->PrepareFrameState(node, OutputFrameStateCombine::PokeAt(

accumulator_base_ - values_index));

}

values()->at(values_index) = node;

}

void BytecodeGraphBuilder::Environment::BindRegistersToProjections(

interpreter::Register first_reg, Node* node,

FrameStateAttachmentMode mode) {

int values_index = RegisterToValuesIndex(first_reg);

if (mode == FrameStateAttachmentMode::kAttachFrameState) {

builder()->PrepareFrameState(node, OutputFrameStateCombine::PokeAt(

accumulator_base_ - values_index));

}

for (int i = 0; i < node->op()->ValueOutputCount(); i++) {

values()->at(values_index + i) =

builder()->NewNode(common()->Projection(i), node);

}

}

void BytecodeGraphBuilder::Environment::RecordAfterState(

Node* node, FrameStateAttachmentMode mode) {

if (mode == FrameStateAttachmentMode::kAttachFrameState) {

builder()->PrepareFrameState(node, OutputFrameStateCombine::Ignore());

}

}

BytecodeGraphBuilder::Environment* BytecodeGraphBuilder::Environment::Copy() {

return zone()->New<Environment>(this);

}

void BytecodeGraphBuilder::Environment::Merge(

BytecodeGraphBuilder::Environment* other,

const BytecodeLivenessState* liveness) {

// Create a merge of the control dependencies of both environments and update

// the current environment's control dependency accordingly.

Node* control = builder()->MergeControl(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(GetEffectDependency(),

other->GetEffectDependency(), control);

UpdateEffectDependency(effect);

// Introduce Phi nodes for values that are live and have differing inputs at

// the merge point, potentially extending an existing Phi node if possible.

context_ = builder()->MergeValue(context_, other->context_, control);

for (int i = 0; i < parameter_count(); i++) {

values_[i] = builder()->MergeValue(values_[i], other->values_[i], control);

}

for (int i = 0; i < register_count(); i++) {

int index = register_base() + i;

if (liveness == nullptr || liveness->RegisterIsLive(i)) {

#if DEBUG

// We only do these DCHECKs when we are not in the resume path of a

// generator -- this is, when either there is no generator state at all,

// or the generator state is not the constant "executing" value.

if (generator_state_ == nullptr ||

NumberMatcher(generator_state_)

.Is(JSGeneratorObject::kGeneratorExecuting)) {

DCHECK_NE(values_[index], builder()->jsgraph()->OptimizedOutConstant());

DCHECK_NE(other->values_[index],

builder()->jsgraph()->OptimizedOutConstant());

}

#endif

values_[index] =

builder()->MergeValue(values_[index], other->values_[index], control);

} else {

values_[index] = builder()->jsgraph()->OptimizedOutConstant();

}

}

if (liveness == nullptr || liveness->AccumulatorIsLive()) {

DCHECK_NE(values_[accumulator_base()],

builder()->jsgraph()->OptimizedOutConstant());

DCHECK_NE(other->values_[accumulator_base()],

builder()->jsgraph()->OptimizedOutConstant());

values_[accumulator_base()] =

builder()->MergeValue(values_[accumulator_base()],

other->values_[accumulator_base()], control);

} else {

values_[accumulator_base()] = builder()->jsgraph()->OptimizedOutConstant();

}

if (generator_state_ != nullptr) {

DCHECK_NOT_NULL(other->generator_state_);

generator_state_ = builder()->MergeValue(generator_state_,

other->generator_state_, control);

}

}

void BytecodeGraphBuilder::Environment::PrepareForLoop(

const BytecodeLoopAssignments& assignments,

const BytecodeLivenessState* liveness) {

// Create a control node for the loop header.

Node* control = builder()->NewLoop();

// Create a Phi for external effects.

Node* effect = builder()->NewEffectPhi(1, GetEffectDependency(), control);

UpdateEffectDependency(effect);

// Create Phis for any values that are live on entry to the loop and may be

// updated by the end of the loop.

context_ = builder()->NewPhi(1, context_, control);

for (int i = 0; i < parameter_count(); i++) {

if (assignments.ContainsParameter(i)) {

values_[i] = builder()->NewPhi(1, values_[i], control);

}

}

for (int i = 0; i < register_count(); i++) {

if (assignments.ContainsLocal(i) &&

(liveness == nullptr || liveness->RegisterIsLive(i))) {

int index = register_base() + i;

values_[index] = builder()->NewPhi(1, values_[index], control);

}

}

// The accumulator should not be live on entry.

DCHECK_IMPLIES(liveness != nullptr, !liveness->AccumulatorIsLive());

if (generator_state_ != nullptr) {

generator_state_ = builder()->NewPhi(1, generator_state_, control);

}

// Connect to the loop end.

Node* terminate = builder()->graph()->NewNode(

builder()->common()->Terminate(), effect, control);

builder()->exit_controls_.push_back(terminate);

}

void BytecodeGraphBuilder::Environment::FillWithOsrValues() {

Node* start = graph()->start();

// Create OSR values for each environment value.

SetContext(graph()->NewNode(

common()->OsrValue(Linkage::kOsrContextSpillSlotIndex), start));

int size = static_cast<int>(values()->size());

for (int i = 0; i < size; i++) {

int idx = i; // Indexing scheme follows {StandardFrame}, adapt accordingly.

if (i >= register_base()) idx += InterpreterFrameConstants::kExtraSlotCount;

if (i >= accumulator_base()) idx = Linkage::kOsrAccumulatorRegisterIndex;

values()->at(i) = graph()->NewNode(common()->OsrValue(idx), start);

}

}

bool BytecodeGraphBuilder::Environment::StateValuesRequireUpdate(

Node** state_values, Node** values, int count) {

if (*state_values == nullptr) {

return true;

}

Node::Inputs inputs = (*state_values)->inputs();

if (inputs.count() != count) return true;

for (int i = 0; i < count; i++) {

if (inputs[i] != values[i]) {

return true;

}

}

return false;

}

void BytecodeGraphBuilder::Environment::PrepareForLoopExit(

Node* loop, const BytecodeLoopAssignments& assignments,

const BytecodeLivenessState* liveness) {

DCHECK_EQ(loop->opcode(), IrOpcode::kLoop);

Node* control = GetControlDependency();

// Create the loop exit node.

Node* loop_exit = graph()->NewNode(common()->LoopExit(), control, loop);

UpdateControlDependency(loop_exit);

// Rename the effect.

Node* effect_rename = graph()->NewNode(common()->LoopExitEffect(),

GetEffectDependency(), loop_exit);

UpdateEffectDependency(effect_rename);

// TODO(jarin) We should also rename context here. However, unconditional

// renaming confuses global object and native context specialization.

// We should only rename if the context is assigned in the loop.

// Rename the environment values if they were assigned in the loop and are

// live after exiting the loop.

for (int i = 0; i < parameter_count(); i++) {

if (assignments.ContainsParameter(i)) {

Node* rename = graph()->NewNode(

common()->LoopExitValue(MachineRepresentation::kTagged), values_[i],

loop_exit);

values_[i] = rename;

}

}

for (int i = 0; i < register_count(); i++) {