Line data Source code
1 : // Copyright 2015 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_
6 : #define V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_
7 :
8 : #include "src/compiler/bytecode-analysis.h"
9 : #include "src/compiler/js-graph.h"
10 : #include "src/compiler/js-type-hint-lowering.h"
11 : #include "src/compiler/state-values-utils.h"
12 : #include "src/interpreter/bytecode-array-iterator.h"
13 : #include "src/interpreter/bytecode-flags.h"
14 : #include "src/interpreter/bytecodes.h"
15 : #include "src/source-position-table.h"
16 :
17 : namespace v8 {
18 : namespace internal {
19 : namespace compiler {
20 :
21 : class Reduction;
22 : class SourcePositionTable;
23 :
24 : // The BytecodeGraphBuilder produces a high-level IR graph based on
25 : // interpreter bytecodes.
26 : class BytecodeGraphBuilder {
27 : public:
28 : BytecodeGraphBuilder(
29 : Zone* local_zone, Handle<SharedFunctionInfo> shared,
30 : Handle<FeedbackVector> feedback_vector, BailoutId osr_offset,
31 : JSGraph* jsgraph, CallFrequency invocation_frequency,
32 : SourcePositionTable* source_positions, Handle<Context> native_context,
33 : int inlining_id = SourcePosition::kNotInlined,
34 : JSTypeHintLowering::Flags flags = JSTypeHintLowering::kNoFlags,
35 : bool stack_check = true);
36 :
37 : // Creates a graph by visiting bytecodes.
38 : void CreateGraph();
39 :
40 : private:
41 : class Environment;
42 : class OsrIteratorState;
43 : struct SubEnvironment;
44 :
45 : void RemoveMergeEnvironmentsBeforeOffset(int limit_offset);
46 : void AdvanceToOsrEntryAndPeelLoops(
47 : interpreter::BytecodeArrayIterator* iterator,
48 : SourcePositionTableIterator* source_position_iterator);
49 :
50 : void VisitSingleBytecode(
51 : SourcePositionTableIterator* source_position_iterator);
52 : void VisitBytecodes();
53 :
54 : // Get or create the node that represents the outer function closure.
55 : Node* GetFunctionClosure();
56 :
57 : // Builder for loading the a native context field.
58 : Node* BuildLoadNativeContextField(int index);
59 :
60 : // Helper function for creating a pair containing type feedback vector and
61 : // a feedback slot.
62 : VectorSlotPair CreateVectorSlotPair(int slot_id);
63 :
64 3332809 : void set_environment(Environment* env) { environment_ = env; }
65 : const Environment* environment() const { return environment_; }
66 : Environment* environment() { return environment_; }
67 :
68 : // Node creation helpers
69 : Node* NewNode(const Operator* op, bool incomplete = false) {
70 7593033 : return MakeNode(op, 0, static_cast<Node**>(nullptr), incomplete);
71 : }
72 :
73 : Node* NewNode(const Operator* op, Node* n1) {
74 2660875 : Node* buffer[] = {n1};
75 2660875 : return MakeNode(op, arraysize(buffer), buffer, false);
76 : }
77 :
78 : Node* NewNode(const Operator* op, Node* n1, Node* n2) {
79 1569063 : Node* buffer[] = {n1, n2};
80 1569063 : return MakeNode(op, arraysize(buffer), buffer, false);
81 : }
82 :
83 : Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) {
84 64554 : Node* buffer[] = {n1, n2, n3};
85 64554 : return MakeNode(op, arraysize(buffer), buffer, false);
86 : }
87 :
88 : Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) {
89 56916 : Node* buffer[] = {n1, n2, n3, n4};
90 56916 : return MakeNode(op, arraysize(buffer), buffer, false);
91 : }
92 :
93 : // Helpers to create new control nodes.
94 1674408 : Node* NewIfTrue() { return NewNode(common()->IfTrue()); }
95 1674408 : Node* NewIfFalse() { return NewNode(common()->IfFalse()); }
96 48294 : Node* NewIfValue(int32_t value) { return NewNode(common()->IfValue(value)); }
97 21018 : Node* NewIfDefault() { return NewNode(common()->IfDefault()); }
98 1868310 : Node* NewMerge() { return NewNode(common()->Merge(1), true); }
99 133359 : Node* NewLoop() { return NewNode(common()->Loop(1), true); }
100 558136 : Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) {
101 1116272 : return NewNode(common()->Branch(hint), condition);
102 : }
103 14012 : Node* NewSwitch(Node* condition, int control_output_count) {
104 21018 : return NewNode(common()->Switch(control_output_count), condition);
105 : }
106 :
107 : // Creates a new Phi node having {count} input values.
108 : Node* NewPhi(int count, Node* input, Node* control);
109 : Node* NewEffectPhi(int count, Node* input, Node* control);
110 :
111 : // Helpers for merging control, effect or value dependencies.
112 : Node* MergeControl(Node* control, Node* other);
113 : Node* MergeEffect(Node* effect, Node* other_effect, Node* control);
114 : Node* MergeValue(Node* value, Node* other_value, Node* control);
115 :
116 : // The main node creation chokepoint. Adds context, frame state, effect,
117 : // and control dependencies depending on the operator.
118 : Node* MakeNode(const Operator* op, int value_input_count,
119 : Node* const* value_inputs, bool incomplete);
120 :
121 : Node** EnsureInputBufferSize(int size);
122 :
123 : Node* const* GetCallArgumentsFromRegisters(Node* callee, Node* receiver,
124 : interpreter::Register first_arg,
125 : int arg_count);
126 : Node* const* ProcessCallVarArgs(ConvertReceiverMode receiver_mode,
127 : Node* callee, interpreter::Register first_reg,
128 : int arg_count);
129 : Node* ProcessCallArguments(const Operator* call_op, Node* const* args,
130 : int arg_count);
131 : Node* ProcessCallArguments(const Operator* call_op, Node* callee,
132 : interpreter::Register receiver, size_t reg_count);
133 : Node* const* GetConstructArgumentsFromRegister(
134 : Node* target, Node* new_target, interpreter::Register first_arg,
135 : int arg_count);
136 : Node* ProcessConstructArguments(const Operator* op, Node* const* args,
137 : int arg_count);
138 : Node* ProcessCallRuntimeArguments(const Operator* call_runtime_op,
139 : interpreter::Register receiver,
140 : size_t reg_count);
141 :
142 : // Prepare information for eager deoptimization. This information is carried
143 : // by dedicated {Checkpoint} nodes that are wired into the effect chain.
144 : // Conceptually this frame state is "before" a given operation.
145 : void PrepareEagerCheckpoint();
146 :
147 : // Prepare information for lazy deoptimization. This information is attached
148 : // to the given node and the output value produced by the node is combined.
149 : // Conceptually this frame state is "after" a given operation.
150 : void PrepareFrameState(Node* node, OutputFrameStateCombine combine);
151 :
152 : void BuildCreateArguments(CreateArgumentsType type);
153 : Node* BuildLoadGlobal(Handle<Name> name, uint32_t feedback_slot_index,
154 : TypeofMode typeof_mode);
155 : void BuildStoreGlobal(LanguageMode language_mode);
156 :
157 : enum class StoreMode {
158 : // Check the prototype chain before storing.
159 : kNormal,
160 : // Store value to the receiver without checking the prototype chain.
161 : kOwn,
162 : };
163 : void BuildNamedStore(StoreMode store_mode);
164 : void BuildLdaLookupSlot(TypeofMode typeof_mode);
165 : void BuildLdaLookupContextSlot(TypeofMode typeof_mode);
166 : void BuildLdaLookupGlobalSlot(TypeofMode typeof_mode);
167 : void BuildCallVarArgs(ConvertReceiverMode receiver_mode);
168 : void BuildCall(ConvertReceiverMode receiver_mode, Node* const* args,
169 : size_t arg_count, int slot_id);
170 : void BuildCall(ConvertReceiverMode receiver_mode,
171 : std::initializer_list<Node*> args, int slot_id) {
172 524070 : BuildCall(receiver_mode, args.begin(), args.size(), slot_id);
173 : }
174 : void BuildBinaryOp(const Operator* op);
175 : void BuildBinaryOpWithImmediate(const Operator* op);
176 : void BuildCompareOp(const Operator* op);
177 : void BuildTestingOp(const Operator* op);
178 : void BuildDelete(LanguageMode language_mode);
179 : void BuildCastOperator(const Operator* op);
180 : void BuildHoleCheckAndThrow(Node* condition, Runtime::FunctionId runtime_id,
181 : Node* name = nullptr);
182 :
183 : // Optional early lowering to the simplified operator level. Note that
184 : // the result has already been wired into the environment just like
185 : // any other invocation of {NewNode} would do.
186 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedBinaryOp(
187 : const Operator* op, Node* left, Node* right, FeedbackSlot slot);
188 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInNext(
189 : Node* receiver, Node* cache_array, Node* cache_type, Node* index,
190 : FeedbackSlot slot);
191 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedForInPrepare(
192 : Node* receiver, FeedbackSlot slot);
193 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedToNumber(
194 : Node* input, FeedbackSlot slot);
195 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedCall(const Operator* op,
196 : Node* const* args,
197 : int arg_count,
198 : FeedbackSlot slot);
199 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedConstruct(
200 : const Operator* op, Node* const* args, int arg_count, FeedbackSlot slot);
201 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadNamed(
202 : const Operator* op, Node* receiver, FeedbackSlot slot);
203 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedLoadKeyed(
204 : const Operator* op, Node* receiver, Node* key, FeedbackSlot slot);
205 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreNamed(
206 : const Operator* op, Node* receiver, Node* value, FeedbackSlot slot);
207 : JSTypeHintLowering::LoweringResult TryBuildSimplifiedStoreKeyed(
208 : const Operator* op, Node* receiver, Node* key, Node* value,
209 : FeedbackSlot slot);
210 :
211 : // Applies the given early reduction onto the current environment.
212 : void ApplyEarlyReduction(JSTypeHintLowering::LoweringResult reduction);
213 :
214 : // Check the context chain for extensions, for lookup fast paths.
215 : Environment* CheckContextExtensions(uint32_t depth);
216 :
217 : // Helper function to create binary operation hint from the recorded
218 : // type feedback.
219 : BinaryOperationHint GetBinaryOperationHint(int operand_index);
220 :
221 : // Helper function to create compare operation hint from the recorded
222 : // type feedback.
223 : CompareOperationHint GetCompareOperationHint();
224 :
225 : // Helper function to create for-in mode from the recorded type feedback.
226 : ForInMode GetForInMode(int operand_index);
227 :
228 : // Helper function to compute call frequency from the recorded type
229 : // feedback.
230 : CallFrequency ComputeCallFrequency(int slot_id) const;
231 :
232 : // Control flow plumbing.
233 : void BuildJump();
234 : void BuildJumpIf(Node* condition);
235 : void BuildJumpIfNot(Node* condition);
236 : void BuildJumpIfEqual(Node* comperand);
237 : void BuildJumpIfNotEqual(Node* comperand);
238 : void BuildJumpIfTrue();
239 : void BuildJumpIfFalse();
240 : void BuildJumpIfToBooleanTrue();
241 : void BuildJumpIfToBooleanFalse();
242 : void BuildJumpIfNotHole();
243 : void BuildJumpIfJSReceiver();
244 :
245 : void BuildSwitchOnSmi(Node* condition);
246 :
247 : // Simulates control flow by forward-propagating environments.
248 : void MergeIntoSuccessorEnvironment(int target_offset);
249 : void BuildLoopHeaderEnvironment(int current_offset);
250 : void SwitchToMergeEnvironment(int current_offset);
251 :
252 : // Simulates control flow that exits the function body.
253 : void MergeControlToLeaveFunction(Node* exit);
254 :
255 : // Builds loop exit nodes for every exited loop between the current bytecode
256 : // offset and {target_offset}.
257 : void BuildLoopExitsForBranch(int target_offset);
258 : void BuildLoopExitsForFunctionExit(const BytecodeLivenessState* liveness);
259 : void BuildLoopExitsUntilLoop(int loop_offset,
260 : const BytecodeLivenessState* liveness);
261 :
262 : // Simulates entry and exit of exception handlers.
263 : void ExitThenEnterExceptionHandlers(int current_offset);
264 :
265 : // Update the current position of the {SourcePositionTable} to that of the
266 : // bytecode at {offset}, if any.
267 : void UpdateSourcePosition(SourcePositionTableIterator* it, int offset);
268 :
269 : // Growth increment for the temporary buffer used to construct input lists to
270 : // new nodes.
271 : static const int kInputBufferSizeIncrement = 64;
272 :
273 : // An abstract representation for an exception handler that is being
274 : // entered and exited while the graph builder is iterating over the
275 : // underlying bytecode. The exception handlers within the bytecode are
276 : // well scoped, hence will form a stack during iteration.
277 : struct ExceptionHandler {
278 : int start_offset_; // Start offset of the handled area in the bytecode.
279 : int end_offset_; // End offset of the handled area in the bytecode.
280 : int handler_offset_; // Handler entry offset within the bytecode.
281 : int context_register_; // Index of register holding handler context.
282 : };
283 :
284 : // Field accessors
285 37307717 : Graph* graph() const { return jsgraph_->graph(); }
286 20739553 : CommonOperatorBuilder* common() const { return jsgraph_->common(); }
287 2370424 : Zone* graph_zone() const { return graph()->zone(); }
288 : JSGraph* jsgraph() const { return jsgraph_; }
289 5891442 : JSOperatorBuilder* javascript() const { return jsgraph_->javascript(); }
290 : SimplifiedOperatorBuilder* simplified() const {
291 373045 : return jsgraph_->simplified();
292 : }
293 : Zone* local_zone() const { return local_zone_; }
294 : const Handle<BytecodeArray>& bytecode_array() const {
295 : return bytecode_array_;
296 : }
297 : const Handle<HandlerTable>& exception_handler_table() const {
298 : return exception_handler_table_;
299 : }
300 : const Handle<FeedbackVector>& feedback_vector() const {
301 : return feedback_vector_;
302 : }
303 : const JSTypeHintLowering& type_hint_lowering() const {
304 : return type_hint_lowering_;
305 : }
306 : const FrameStateFunctionInfo* frame_state_function_info() const {
307 : return frame_state_function_info_;
308 : }
309 :
310 : const interpreter::BytecodeArrayIterator& bytecode_iterator() const {
311 : return *bytecode_iterator_;
312 : }
313 :
314 : void set_bytecode_iterator(
315 : interpreter::BytecodeArrayIterator* bytecode_iterator) {
316 1009819 : bytecode_iterator_ = bytecode_iterator;
317 : }
318 :
319 : const BytecodeAnalysis* bytecode_analysis() const {
320 : return bytecode_analysis_;
321 : }
322 :
323 : void set_bytecode_analysis(const BytecodeAnalysis* bytecode_analysis) {
324 1009818 : bytecode_analysis_ = bytecode_analysis;
325 : }
326 :
327 : int currently_peeled_loop_offset() const {
328 : return currently_peeled_loop_offset_;
329 : }
330 :
331 : void set_currently_peeled_loop_offset(int offset) {
332 6681 : currently_peeled_loop_offset_ = offset;
333 : }
334 :
335 : bool stack_check() const { return stack_check_; }
336 :
337 61528 : void set_stack_check(bool stack_check) { stack_check_ = stack_check; }
338 :
339 : int current_exception_handler() { return current_exception_handler_; }
340 :
341 : void set_current_exception_handler(int index) {
342 872 : current_exception_handler_ = index;
343 : }
344 :
345 : bool needs_eager_checkpoint() const { return needs_eager_checkpoint_; }
346 : void mark_as_needing_eager_checkpoint(bool value) {
347 8106222 : needs_eager_checkpoint_ = value;
348 : }
349 :
350 : Handle<Context> native_context() const { return native_context_; }
351 :
352 : #define DECLARE_VISIT_BYTECODE(name, ...) void Visit##name();
353 : BYTECODE_LIST(DECLARE_VISIT_BYTECODE)
354 : #undef DECLARE_VISIT_BYTECODE
355 :
356 : Zone* local_zone_;
357 : JSGraph* jsgraph_;
358 : CallFrequency const invocation_frequency_;
359 : Handle<BytecodeArray> bytecode_array_;
360 : Handle<HandlerTable> exception_handler_table_;
361 : Handle<FeedbackVector> feedback_vector_;
362 : const JSTypeHintLowering type_hint_lowering_;
363 : const FrameStateFunctionInfo* frame_state_function_info_;
364 : const interpreter::BytecodeArrayIterator* bytecode_iterator_;
365 : const BytecodeAnalysis* bytecode_analysis_;
366 : Environment* environment_;
367 : BailoutId osr_offset_;
368 : int currently_peeled_loop_offset_;
369 : bool stack_check_;
370 :
371 : // Merge environments are snapshots of the environment at points where the
372 : // control flow merges. This models a forward data flow propagation of all
373 : // values from all predecessors of the merge in question.
374 : ZoneMap<int, Environment*> merge_environments_;
375 :
376 : // Exception handlers currently entered by the iteration.
377 : ZoneStack<ExceptionHandler> exception_handlers_;
378 : int current_exception_handler_;
379 :
380 : // Temporary storage for building node input lists.
381 : int input_buffer_size_;
382 : Node** input_buffer_;
383 :
384 : // Optimization to only create checkpoints when the current position in the
385 : // control-flow is not effect-dominated by another checkpoint already. All
386 : // operations that do not have observable side-effects can be re-evaluated.
387 : bool needs_eager_checkpoint_;
388 :
389 : // Nodes representing values in the activation record.
390 : SetOncePointer<Node> function_closure_;
391 :
392 : // Control nodes that exit the function body.
393 : ZoneVector<Node*> exit_controls_;
394 :
395 : StateValuesCache state_values_cache_;
396 :
397 : // The source position table, to be populated.
398 : SourcePositionTable* source_positions_;
399 :
400 : SourcePosition const start_position_;
401 :
402 : // The native context for which we optimize.
403 : Handle<Context> const native_context_;
404 :
405 : static int const kBinaryOperationHintIndex = 1;
406 : static int const kCountOperationHintIndex = 0;
407 : static int const kBinaryOperationSmiHintIndex = 1;
408 : static int const kUnaryOperationHintIndex = 0;
409 :
410 : DISALLOW_COPY_AND_ASSIGN(BytecodeGraphBuilder);
411 : };
412 :
413 : } // namespace compiler
414 : } // namespace internal
415 : } // namespace v8
416 :
417 : #endif // V8_COMPILER_BYTECODE_GRAPH_BUILDER_H_
|
