OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_COMPILER_AST_GRAPH_BUILDER_H_ | 5 #ifndef V8_COMPILER_AST_GRAPH_BUILDER_H_ |
6 #define V8_COMPILER_AST_GRAPH_BUILDER_H_ | 6 #define V8_COMPILER_AST_GRAPH_BUILDER_H_ |
7 | 7 |
8 #include "src/v8.h" | 8 #include "src/v8.h" |
9 | 9 |
10 #include "src/ast.h" | 10 #include "src/ast.h" |
11 #include "src/compiler/graph-builder.h" | |
12 #include "src/compiler/js-graph.h" | 11 #include "src/compiler/js-graph.h" |
13 | 12 |
14 namespace v8 { | 13 namespace v8 { |
15 namespace internal { | 14 namespace internal { |
| 15 |
| 16 class BitVector; |
| 17 |
16 namespace compiler { | 18 namespace compiler { |
17 | 19 |
18 class ControlBuilder; | 20 class ControlBuilder; |
19 class Graph; | 21 class Graph; |
20 class LoopAssignmentAnalysis; | 22 class LoopAssignmentAnalysis; |
21 class LoopBuilder; | 23 class LoopBuilder; |
| 24 class Node; |
22 | 25 |
23 // The AstGraphBuilder produces a high-level IR graph, based on an | 26 // The AstGraphBuilder produces a high-level IR graph, based on an |
24 // underlying AST. The produced graph can either be compiled into a | 27 // underlying AST. The produced graph can either be compiled into a |
25 // stand-alone function or be wired into another graph for the purposes | 28 // stand-alone function or be wired into another graph for the purposes |
26 // of function inlining. | 29 // of function inlining. |
27 class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor { | 30 class AstGraphBuilder : public AstVisitor { |
28 public: | 31 public: |
29 AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, | 32 AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph, |
30 LoopAssignmentAnalysis* loop_assignment = NULL); | 33 LoopAssignmentAnalysis* loop_assignment = NULL); |
31 | 34 |
32 // Creates a graph by visiting the entire AST. | 35 // Creates a graph by visiting the entire AST. |
33 bool CreateGraph(); | 36 bool CreateGraph(); |
34 | 37 |
| 38 // Helpers to create new control nodes. |
| 39 Node* NewIfTrue() { return NewNode(common()->IfTrue()); } |
| 40 Node* NewIfFalse() { return NewNode(common()->IfFalse()); } |
| 41 Node* NewMerge() { return NewNode(common()->Merge(1), true); } |
| 42 Node* NewLoop() { return NewNode(common()->Loop(1), true); } |
| 43 Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) { |
| 44 return NewNode(common()->Branch(hint), condition); |
| 45 } |
| 46 |
35 protected: | 47 protected: |
| 48 #define DECLARE_VISIT(type) void Visit##type(type* node) OVERRIDE; |
| 49 // Visiting functions for AST nodes make this an AstVisitor. |
| 50 AST_NODE_LIST(DECLARE_VISIT) |
| 51 #undef DECLARE_VISIT |
| 52 |
| 53 // Visiting function for declarations list is overridden. |
| 54 void VisitDeclarations(ZoneList<Declaration*>* declarations) OVERRIDE; |
| 55 |
| 56 // Get the node that represents the outer function context. |
| 57 Node* GetFunctionContext(); |
| 58 // Get the node that represents the outer function closure. |
| 59 Node* GetFunctionClosure(); |
| 60 |
| 61 private: |
36 class AstContext; | 62 class AstContext; |
37 class AstEffectContext; | 63 class AstEffectContext; |
38 class AstValueContext; | 64 class AstValueContext; |
39 class AstTestContext; | 65 class AstTestContext; |
40 class BreakableScope; | 66 class BreakableScope; |
41 class ContextScope; | 67 class ContextScope; |
42 class Environment; | 68 class Environment; |
| 69 friend class ControlBuilder; |
43 | 70 |
44 Environment* environment() { | 71 Zone* local_zone_; |
45 return reinterpret_cast<Environment*>( | 72 CompilationInfo* info_; |
46 StructuredGraphBuilder::environment()); | 73 JSGraph* jsgraph_; |
47 } | 74 Environment* environment_; |
| 75 AstContext* ast_context_; |
48 | 76 |
| 77 // List of global declarations for functions and variables. |
| 78 ZoneVector<Handle<Object>> globals_; |
| 79 |
| 80 // Stack of breakable statements entered by the visitor. |
| 81 BreakableScope* breakable_; |
| 82 |
| 83 // Stack of context objects pushed onto the chain by the visitor. |
| 84 ContextScope* execution_context_; |
| 85 |
| 86 // Nodes representing values in the activation record. |
| 87 SetOncePointer<Node> function_closure_; |
| 88 SetOncePointer<Node> function_context_; |
| 89 |
| 90 // Temporary storage for building node input lists. |
| 91 int input_buffer_size_; |
| 92 Node** input_buffer_; |
| 93 |
| 94 // Node representing the control dependency for dead code. |
| 95 SetOncePointer<Node> dead_control_; |
| 96 |
| 97 // Node representing the current context within the function body. |
| 98 Node* current_context_; |
| 99 |
| 100 // Merge of all control nodes that exit the function body. |
| 101 Node* exit_control_; |
| 102 |
| 103 // Result of loop assignment analysis performed before graph creation. |
| 104 LoopAssignmentAnalysis* loop_assignment_analysis_; |
| 105 |
| 106 // Growth increment for the temporary buffer used to construct input lists to |
| 107 // new nodes. |
| 108 static const int kInputBufferSizeIncrement = 64; |
| 109 |
| 110 Zone* local_zone() const { return local_zone_; } |
| 111 Environment* environment() { return environment_; } |
49 AstContext* ast_context() const { return ast_context_; } | 112 AstContext* ast_context() const { return ast_context_; } |
50 BreakableScope* breakable() const { return breakable_; } | 113 BreakableScope* breakable() const { return breakable_; } |
51 ContextScope* execution_context() const { return execution_context_; } | 114 ContextScope* execution_context() const { return execution_context_; } |
| 115 CommonOperatorBuilder* common() const { return jsgraph_->common(); } |
| 116 CompilationInfo* info() const { return info_; } |
| 117 StrictMode strict_mode() const; |
| 118 JSGraph* jsgraph() { return jsgraph_; } |
| 119 Graph* graph() { return jsgraph_->graph(); } |
| 120 Zone* graph_zone() { return graph()->zone(); } |
| 121 JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } |
| 122 ZoneVector<Handle<Object>>* globals() { return &globals_; } |
| 123 inline Scope* current_scope() const; |
| 124 Node* current_context() const { return current_context_; } |
| 125 Node* dead_control(); |
| 126 Node* exit_control() const { return exit_control_; } |
52 | 127 |
53 void set_ast_context(AstContext* ctx) { ast_context_ = ctx; } | 128 void set_ast_context(AstContext* ctx) { ast_context_ = ctx; } |
54 void set_breakable(BreakableScope* brk) { breakable_ = brk; } | 129 void set_breakable(BreakableScope* brk) { breakable_ = brk; } |
55 void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; } | 130 void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; } |
| 131 void set_exit_control(Node* exit) { exit_control_ = exit; } |
| 132 void set_current_context(Node* ctx) { current_context_ = ctx; } |
| 133 void set_environment(Environment* env) { environment_ = env; } |
56 | 134 |
57 // Support for control flow builders. The concrete type of the environment | 135 // Node creation helpers. |
58 // depends on the graph builder, but environments themselves are not virtual. | 136 Node* NewNode(const Operator* op, bool incomplete = false) { |
59 typedef StructuredGraphBuilder::Environment BaseEnvironment; | 137 return MakeNode(op, 0, static_cast<Node**>(NULL), incomplete); |
60 BaseEnvironment* CopyEnvironment(BaseEnvironment* env) OVERRIDE; | 138 } |
61 | 139 |
62 // Getters for values in the activation record. | 140 Node* NewNode(const Operator* op, Node* n1) { |
63 Node* GetFunctionClosure(); | 141 return MakeNode(op, 1, &n1, false); |
64 Node* GetFunctionContext(); | 142 } |
| 143 |
| 144 Node* NewNode(const Operator* op, Node* n1, Node* n2) { |
| 145 Node* buffer[] = {n1, n2}; |
| 146 return MakeNode(op, arraysize(buffer), buffer, false); |
| 147 } |
| 148 |
| 149 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { |
| 150 Node* buffer[] = {n1, n2, n3}; |
| 151 return MakeNode(op, arraysize(buffer), buffer, false); |
| 152 } |
| 153 |
| 154 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { |
| 155 Node* buffer[] = {n1, n2, n3, n4}; |
| 156 return MakeNode(op, arraysize(buffer), buffer, false); |
| 157 } |
| 158 |
| 159 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 160 Node* n5) { |
| 161 Node* buffer[] = {n1, n2, n3, n4, n5}; |
| 162 return MakeNode(op, arraysize(buffer), buffer, false); |
| 163 } |
| 164 |
| 165 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 166 Node* n5, Node* n6) { |
| 167 Node* nodes[] = {n1, n2, n3, n4, n5, n6}; |
| 168 return MakeNode(op, arraysize(nodes), nodes, false); |
| 169 } |
| 170 |
| 171 Node* NewNode(const Operator* op, int value_input_count, Node** value_inputs, |
| 172 bool incomplete = false) { |
| 173 return MakeNode(op, value_input_count, value_inputs, incomplete); |
| 174 } |
| 175 |
| 176 // Creates a new Phi node having {count} input values. |
| 177 Node* NewPhi(int count, Node* input, Node* control); |
| 178 Node* NewEffectPhi(int count, Node* input, Node* control); |
| 179 |
| 180 // Helpers for merging control, effect or value dependencies. |
| 181 Node* MergeControl(Node* control, Node* other); |
| 182 Node* MergeEffect(Node* value, Node* other, Node* control); |
| 183 Node* MergeValue(Node* value, Node* other, Node* control); |
| 184 |
| 185 // The main node creation chokepoint. Adds context, frame state, effect, |
| 186 // and control dependencies depending on the operator. |
| 187 Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs, |
| 188 bool incomplete); |
| 189 |
| 190 // Helper to indicate a node exits the function body. |
| 191 void UpdateControlDependencyToLeaveFunction(Node* exit); |
65 | 192 |
66 // | 193 // |
67 // The following build methods all generate graph fragments and return one | 194 // The following build methods all generate graph fragments and return one |
68 // resulting node. The operand stack height remains the same, variables and | 195 // resulting node. The operand stack height remains the same, variables and |
69 // other dependencies tracked by the environment might be mutated though. | 196 // other dependencies tracked by the environment might be mutated though. |
70 // | 197 // |
71 | 198 |
72 // Builder to create a receiver check for sloppy mode. | 199 // Builder to create a receiver check for sloppy mode. |
73 Node* BuildPatchReceiverToGlobalProxy(Node* receiver); | 200 Node* BuildPatchReceiverToGlobalProxy(Node* receiver); |
74 | 201 |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
113 // Builders for binary operations. | 240 // Builders for binary operations. |
114 Node* BuildBinaryOp(Node* left, Node* right, Token::Value op); | 241 Node* BuildBinaryOp(Node* left, Node* right, Token::Value op); |
115 | 242 |
116 // Builder for stack-check guards. | 243 // Builder for stack-check guards. |
117 Node* BuildStackCheck(); | 244 Node* BuildStackCheck(); |
118 | 245 |
119 // Check if the given statement is an OSR entry. | 246 // Check if the given statement is an OSR entry. |
120 // If so, record the stack height into the compilation and return {true}. | 247 // If so, record the stack height into the compilation and return {true}. |
121 bool CheckOsrEntry(IterationStatement* stmt); | 248 bool CheckOsrEntry(IterationStatement* stmt); |
122 | 249 |
123 #define DECLARE_VISIT(type) void Visit##type(type* node) OVERRIDE; | 250 // Helper to wrap a Handle<T> into a Unique<T>. |
| 251 template <class T> |
| 252 Unique<T> MakeUnique(Handle<T> object) { |
| 253 return Unique<T>::CreateUninitialized(object); |
| 254 } |
124 | 255 |
125 // Visiting functions for AST nodes make this an AstVisitor. | 256 Node** EnsureInputBufferSize(int size); |
126 AST_NODE_LIST(DECLARE_VISIT) | |
127 #undef DECLARE_VISIT | |
128 | |
129 // Visiting function for declarations list is overridden. | |
130 void VisitDeclarations(ZoneList<Declaration*>* declarations) OVERRIDE; | |
131 | |
132 private: | |
133 CompilationInfo* info_; | |
134 AstContext* ast_context_; | |
135 JSGraph* jsgraph_; | |
136 | |
137 // List of global declarations for functions and variables. | |
138 ZoneVector<Handle<Object>> globals_; | |
139 | |
140 // Stack of breakable statements entered by the visitor. | |
141 BreakableScope* breakable_; | |
142 | |
143 // Stack of context objects pushed onto the chain by the visitor. | |
144 ContextScope* execution_context_; | |
145 | |
146 // Nodes representing values in the activation record. | |
147 SetOncePointer<Node> function_closure_; | |
148 SetOncePointer<Node> function_context_; | |
149 | |
150 // The node representing the OSR entry into the loop, if any. | |
151 SetOncePointer<Node> osr_loop_entry_; | |
152 | |
153 // Result of loop assignment analysis performed before graph creation. | |
154 LoopAssignmentAnalysis* loop_assignment_analysis_; | |
155 | |
156 CompilationInfo* info() const { return info_; } | |
157 inline StrictMode strict_mode() const; | |
158 JSGraph* jsgraph() { return jsgraph_; } | |
159 JSOperatorBuilder* javascript() { return jsgraph_->javascript(); } | |
160 ZoneVector<Handle<Object>>* globals() { return &globals_; } | |
161 | |
162 // Current scope during visitation. | |
163 inline Scope* current_scope() const; | |
164 | 257 |
165 // Named and keyed loads require a VectorSlotPair for successful lowering. | 258 // Named and keyed loads require a VectorSlotPair for successful lowering. |
166 VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const; | 259 VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const; |
167 | 260 |
168 // Process arguments to a call by popping {arity} elements off the operand | 261 // Process arguments to a call by popping {arity} elements off the operand |
169 // stack and build a call node using the given call operator. | 262 // stack and build a call node using the given call operator. |
170 Node* ProcessArguments(const Operator* op, int arity); | 263 Node* ProcessArguments(const Operator* op, int arity); |
171 | 264 |
172 // Visit statements. | 265 // Visit statements. |
173 void VisitIfNotNull(Statement* stmt); | 266 void VisitIfNotNull(Statement* stmt); |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
219 | 312 |
220 | 313 |
221 // The abstract execution environment for generated code consists of | 314 // The abstract execution environment for generated code consists of |
222 // parameter variables, local variables and the operand stack. The | 315 // parameter variables, local variables and the operand stack. The |
223 // environment will perform proper SSA-renaming of all tracked nodes | 316 // environment will perform proper SSA-renaming of all tracked nodes |
224 // at split and merge points in the control flow. Internally all the | 317 // at split and merge points in the control flow. Internally all the |
225 // values are stored in one list using the following layout: | 318 // values are stored in one list using the following layout: |
226 // | 319 // |
227 // [parameters (+receiver)] [locals] [operand stack] | 320 // [parameters (+receiver)] [locals] [operand stack] |
228 // | 321 // |
229 class AstGraphBuilder::Environment | 322 class AstGraphBuilder::Environment : public ZoneObject { |
230 : public StructuredGraphBuilder::Environment { | |
231 public: | 323 public: |
232 Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); | 324 Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); |
233 Environment(const Environment& copy); | |
234 | 325 |
235 int parameters_count() const { return parameters_count_; } | 326 int parameters_count() const { return parameters_count_; } |
236 int locals_count() const { return locals_count_; } | 327 int locals_count() const { return locals_count_; } |
237 int stack_height() { | 328 int stack_height() { |
238 return static_cast<int>(values()->size()) - parameters_count_ - | 329 return static_cast<int>(values()->size()) - parameters_count_ - |
239 locals_count_; | 330 locals_count_; |
240 } | 331 } |
241 | 332 |
242 // Operations on parameter or local variables. The parameter indices are | 333 // Operations on parameter or local variables. The parameter indices are |
243 // shifted by 1 (receiver is parameter index -1 but environment index 0). | 334 // shifted by 1 (receiver is parameter index -1 but environment index 0). |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
288 } | 379 } |
289 void Drop(int depth) { | 380 void Drop(int depth) { |
290 DCHECK(depth >= 0 && depth <= stack_height()); | 381 DCHECK(depth >= 0 && depth <= stack_height()); |
291 values()->erase(values()->end() - depth, values()->end()); | 382 values()->erase(values()->end() - depth, values()->end()); |
292 } | 383 } |
293 | 384 |
294 // Preserve a checkpoint of the environment for the IR graph. Any | 385 // Preserve a checkpoint of the environment for the IR graph. Any |
295 // further mutation of the environment will not affect checkpoints. | 386 // further mutation of the environment will not affect checkpoints. |
296 Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine); | 387 Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine); |
297 | 388 |
298 protected: | 389 // Control dependency tracked by this environment. |
299 AstGraphBuilder* builder() const { | 390 Node* GetControlDependency() { return control_dependency_; } |
300 return reinterpret_cast<AstGraphBuilder*>( | 391 void UpdateControlDependency(Node* dependency) { |
301 StructuredGraphBuilder::Environment::builder()); | 392 control_dependency_ = dependency; |
| 393 } |
| 394 |
| 395 // Effect dependency tracked by this environment. |
| 396 Node* GetEffectDependency() { return effect_dependency_; } |
| 397 void UpdateEffectDependency(Node* dependency) { |
| 398 effect_dependency_ = dependency; |
| 399 } |
| 400 |
| 401 // Mark this environment as being unreachable. |
| 402 void MarkAsUnreachable() { |
| 403 UpdateControlDependency(builder()->dead_control()); |
| 404 } |
| 405 bool IsMarkedAsUnreachable() { |
| 406 return GetControlDependency()->opcode() == IrOpcode::kDead; |
| 407 } |
| 408 |
| 409 // Merge another environment into this one. |
| 410 void Merge(Environment* other); |
| 411 |
| 412 // Copies this environment at a control-flow split point. |
| 413 Environment* CopyForConditional() { return Copy(); } |
| 414 |
| 415 // Copies this environment to a potentially unreachable control-flow point. |
| 416 Environment* CopyAsUnreachable() { |
| 417 Environment* env = Copy(); |
| 418 env->MarkAsUnreachable(); |
| 419 return env; |
| 420 } |
| 421 |
| 422 // Copies this environment at a loop header control-flow point. |
| 423 Environment* CopyForLoop(BitVector* assigned, bool is_osr = false) { |
| 424 PrepareForLoop(assigned, is_osr); |
| 425 return Copy(); |
302 } | 426 } |
303 | 427 |
304 private: | 428 private: |
305 void UpdateStateValues(Node** state_values, int offset, int count); | 429 AstGraphBuilder* builder_; |
306 | |
307 int parameters_count_; | 430 int parameters_count_; |
308 int locals_count_; | 431 int locals_count_; |
| 432 NodeVector values_; |
| 433 Node* control_dependency_; |
| 434 Node* effect_dependency_; |
309 Node* parameters_node_; | 435 Node* parameters_node_; |
310 Node* locals_node_; | 436 Node* locals_node_; |
311 Node* stack_node_; | 437 Node* stack_node_; |
| 438 |
| 439 explicit Environment(const Environment* copy); |
| 440 Environment* Copy() { return new (zone()) Environment(this); } |
| 441 void UpdateStateValues(Node** state_values, int offset, int count); |
| 442 Zone* zone() const { return builder_->local_zone(); } |
| 443 Graph* graph() const { return builder_->graph(); } |
| 444 AstGraphBuilder* builder() const { return builder_; } |
| 445 CommonOperatorBuilder* common() { return builder_->common(); } |
| 446 NodeVector* values() { return &values_; } |
| 447 |
| 448 // Prepare environment to be used as loop header. |
| 449 void PrepareForLoop(BitVector* assigned, bool is_osr = false); |
312 }; | 450 }; |
313 | 451 |
314 | 452 |
315 // Each expression in the AST is evaluated in a specific context. This context | 453 // Each expression in the AST is evaluated in a specific context. This context |
316 // decides how the evaluation result is passed up the visitor. | 454 // decides how the evaluation result is passed up the visitor. |
317 class AstGraphBuilder::AstContext BASE_EMBEDDED { | 455 class AstGraphBuilder::AstContext BASE_EMBEDDED { |
318 public: | 456 public: |
319 bool IsEffect() const { return kind_ == Expression::kEffect; } | 457 bool IsEffect() const { return kind_ == Expression::kEffect; } |
320 bool IsValue() const { return kind_ == Expression::kValue; } | 458 bool IsValue() const { return kind_ == Expression::kValue; } |
321 bool IsTest() const { return kind_ == Expression::kTest; } | 459 bool IsTest() const { return kind_ == Expression::kTest; } |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
458 | 596 |
459 Scope* AstGraphBuilder::current_scope() const { | 597 Scope* AstGraphBuilder::current_scope() const { |
460 return execution_context_->scope(); | 598 return execution_context_->scope(); |
461 } | 599 } |
462 | 600 |
463 } // namespace compiler | 601 } // namespace compiler |
464 } // namespace internal | 602 } // namespace internal |
465 } // namespace v8 | 603 } // namespace v8 |
466 | 604 |
467 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ | 605 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ |
OLD | NEW |