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