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