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
3 // found in the LICENSE file.
5 #ifndef V8_COMPILER_AST_GRAPH_BUILDER_H_
6 #define V8_COMPILER_AST_GRAPH_BUILDER_H_
11 #include "src/compiler/graph-builder.h"
12 #include "src/compiler/js-graph.h"
22 // The AstGraphBuilder produces a high-level IR graph, based on an
23 // underlying AST. The produced graph can either be compiled into a
24 // stand-alone function or be wired into another graph for the purposes
25 // of function inlining.
26 class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor {
28 AstGraphBuilder(CompilationInfo* info, JSGraph* jsgraph);
30 // Creates a graph by visiting the entire AST.
35 class AstEffectContext;
36 class AstValueContext;
42 Environment* environment() {
43 return reinterpret_cast<Environment*>(
44 StructuredGraphBuilder::environment());
47 AstContext* ast_context() const { return ast_context_; }
48 BreakableScope* breakable() const { return breakable_; }
49 ContextScope* execution_context() const { return execution_context_; }
51 void set_ast_context(AstContext* ctx) { ast_context_ = ctx; }
52 void set_breakable(BreakableScope* brk) { breakable_ = brk; }
53 void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; }
55 // Support for control flow builders. The concrete type of the environment
56 // depends on the graph builder, but environments themselves are not virtual.
57 typedef StructuredGraphBuilder::Environment BaseEnvironment;
58 virtual BaseEnvironment* CopyEnvironment(BaseEnvironment* env);
60 // TODO(mstarzinger): The pipeline only needs to be a friend to access the
61 // function context. Remove as soon as the context is a parameter.
62 friend class Pipeline;
64 // Getters for values in the activation record.
65 Node* GetFunctionClosure();
66 Node* GetFunctionContext();
69 // The following build methods all generate graph fragments and return one
70 // resulting node. The operand stack height remains the same, variables and
71 // other dependencies tracked by the environment might be mutated though.
74 // Builder to create a local function context.
75 Node* BuildLocalFunctionContext(Node* context, Node* closure);
77 // Builder to create an arguments object if it is used.
78 Node* BuildArgumentsObject(Variable* arguments);
80 // Builders for variable load and assignment.
81 Node* BuildVariableAssignment(Variable* var, Node* value, Token::Value op,
82 BailoutId bailout_id);
83 Node* BuildVariableDelete(Variable* var);
84 Node* BuildVariableLoad(Variable* var, BailoutId bailout_id,
85 ContextualMode mode = CONTEXTUAL);
87 // Builders for accessing the function context.
88 Node* BuildLoadBuiltinsObject();
89 Node* BuildLoadGlobalObject();
90 Node* BuildLoadClosure();
91 Node* BuildLoadObjectField(Node* object, int offset);
93 // Builders for automatic type conversion.
94 Node* BuildToBoolean(Node* value);
96 // Builders for error reporting at runtime.
97 Node* BuildThrowReferenceError(Variable* var);
99 // Builders for dynamic hole-checks at runtime.
100 Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole);
101 Node* BuildHoleCheckThrow(Node* value, Variable* var, Node* not_hole);
103 // Builders for binary operations.
104 Node* BuildBinaryOp(Node* left, Node* right, Token::Value op);
106 #define DECLARE_VISIT(type) virtual void Visit##type(type* node);
107 // Visiting functions for AST nodes make this an AstVisitor.
108 AST_NODE_LIST(DECLARE_VISIT)
111 // Visiting function for declarations list is overridden.
112 virtual void VisitDeclarations(ZoneList<Declaration*>* declarations);
115 CompilationInfo* info_;
116 AstContext* ast_context_;
119 // List of global declarations for functions and variables.
120 ZoneList<Handle<Object> > globals_;
122 // Stack of breakable statements entered by the visitor.
123 BreakableScope* breakable_;
125 // Stack of context objects pushed onto the chain by the visitor.
126 ContextScope* execution_context_;
128 // Nodes representing values in the activation record.
129 SetOncePointer<Node> function_closure_;
130 SetOncePointer<Node> function_context_;
132 CompilationInfo* info() { return info_; }
133 StrictMode strict_mode() { return info()->strict_mode(); }
134 JSGraph* jsgraph() { return jsgraph_; }
135 JSOperatorBuilder* javascript() { return jsgraph_->javascript(); }
136 ZoneList<Handle<Object> >* globals() { return &globals_; }
138 // Current scope during visitation.
139 inline Scope* current_scope() const;
141 // Process arguments to a call by popping {arity} elements off the operand
142 // stack and build a call node using the given call operator.
143 Node* ProcessArguments(const Operator* op, int arity);
146 void VisitIfNotNull(Statement* stmt);
148 // Visit expressions.
149 void VisitForTest(Expression* expr);
150 void VisitForEffect(Expression* expr);
151 void VisitForValue(Expression* expr);
152 void VisitForValueOrNull(Expression* expr);
153 void VisitForValues(ZoneList<Expression*>* exprs);
155 // Common for all IterationStatement bodies.
156 void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int);
158 // Dispatched from VisitCallRuntime.
159 void VisitCallJSRuntime(CallRuntime* expr);
161 // Dispatched from VisitUnaryOperation.
162 void VisitDelete(UnaryOperation* expr);
163 void VisitVoid(UnaryOperation* expr);
164 void VisitTypeof(UnaryOperation* expr);
165 void VisitNot(UnaryOperation* expr);
167 // Dispatched from VisitBinaryOperation.
168 void VisitComma(BinaryOperation* expr);
169 void VisitLogicalExpression(BinaryOperation* expr);
170 void VisitArithmeticExpression(BinaryOperation* expr);
172 // Dispatched from VisitForInStatement.
173 void VisitForInAssignment(Expression* expr, Node* value);
175 // Builds deoptimization for a given node.
176 void PrepareFrameState(Node* node, BailoutId ast_id,
177 OutputFrameStateCombine combine = kIgnoreOutput);
179 OutputFrameStateCombine StateCombineFromAstContext();
181 DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
182 DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder);
186 // The abstract execution environment for generated code consists of
187 // parameter variables, local variables and the operand stack. The
188 // environment will perform proper SSA-renaming of all tracked nodes
189 // at split and merge points in the control flow. Internally all the
190 // values are stored in one list using the following layout:
192 // [parameters (+receiver)] [locals] [operand stack]
194 class AstGraphBuilder::Environment
195 : public StructuredGraphBuilder::Environment {
197 Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency);
198 Environment(const Environment& copy);
200 int parameters_count() const { return parameters_count_; }
201 int locals_count() const { return locals_count_; }
203 return static_cast<int>(values()->size()) - parameters_count_ -
207 // Operations on parameter or local variables. The parameter indices are
208 // shifted by 1 (receiver is parameter index -1 but environment index 0).
209 void Bind(Variable* variable, Node* node) {
210 DCHECK(variable->IsStackAllocated());
211 if (variable->IsParameter()) {
212 values()->at(variable->index() + 1) = node;
214 DCHECK(variable->IsStackLocal());
215 values()->at(variable->index() + parameters_count_) = node;
218 Node* Lookup(Variable* variable) {
219 DCHECK(variable->IsStackAllocated());
220 if (variable->IsParameter()) {
221 return values()->at(variable->index() + 1);
223 DCHECK(variable->IsStackLocal());
224 return values()->at(variable->index() + parameters_count_);
228 // Operations on the operand stack.
229 void Push(Node* node) {
230 values()->push_back(node);
233 DCHECK(stack_height() > 0);
234 return values()->back();
237 DCHECK(stack_height() > 0);
238 Node* back = values()->back();
239 values()->pop_back();
243 // Direct mutations of the operand stack.
244 void Poke(int depth, Node* node) {
245 DCHECK(depth >= 0 && depth < stack_height());
246 int index = static_cast<int>(values()->size()) - depth - 1;
247 values()->at(index) = node;
249 Node* Peek(int depth) {
250 DCHECK(depth >= 0 && depth < stack_height());
251 int index = static_cast<int>(values()->size()) - depth - 1;
252 return values()->at(index);
254 void Drop(int depth) {
255 DCHECK(depth >= 0 && depth <= stack_height());
256 values()->erase(values()->end() - depth, values()->end());
259 // Preserve a checkpoint of the environment for the IR graph. Any
260 // further mutation of the environment will not affect checkpoints.
261 Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine);
264 AstGraphBuilder* builder() const {
265 return reinterpret_cast<AstGraphBuilder*>(
266 StructuredGraphBuilder::Environment::builder());
270 void UpdateStateValues(Node** state_values, int offset, int count);
272 int parameters_count_;
274 Node* parameters_node_;
280 // Each expression in the AST is evaluated in a specific context. This context
281 // decides how the evaluation result is passed up the visitor.
282 class AstGraphBuilder::AstContext BASE_EMBEDDED {
284 bool IsEffect() const { return kind_ == Expression::kEffect; }
285 bool IsValue() const { return kind_ == Expression::kValue; }
286 bool IsTest() const { return kind_ == Expression::kTest; }
288 // Determines how to combine the frame state with the value
289 // that is about to be plugged into this AstContext.
290 OutputFrameStateCombine GetStateCombine() {
291 return IsEffect() ? kIgnoreOutput : kPushOutput;
294 // Plug a node into this expression context. Call this function in tail
295 // position in the Visit functions for expressions.
296 virtual void ProduceValue(Node* value) = 0;
298 // Unplugs a node from this expression context. Call this to retrieve the
299 // result of another Visit function that already plugged the context.
300 virtual Node* ConsumeValue() = 0;
302 // Shortcut for "context->ProduceValue(context->ConsumeValue())".
303 void ReplaceValue() { ProduceValue(ConsumeValue()); }
306 AstContext(AstGraphBuilder* owner, Expression::Context kind);
307 virtual ~AstContext();
309 AstGraphBuilder* owner() const { return owner_; }
310 Environment* environment() const { return owner_->environment(); }
312 // We want to be able to assert, in a context-specific way, that the stack
313 // height makes sense when the context is filled.
315 int original_height_;
319 Expression::Context kind_;
320 AstGraphBuilder* owner_;
325 // Context to evaluate expression for its side effects only.
326 class AstGraphBuilder::AstEffectContext FINAL : public AstContext {
328 explicit AstEffectContext(AstGraphBuilder* owner)
329 : AstContext(owner, Expression::kEffect) {}
330 virtual ~AstEffectContext();
331 virtual void ProduceValue(Node* value) OVERRIDE;
332 virtual Node* ConsumeValue() OVERRIDE;
336 // Context to evaluate expression for its value (and side effects).
337 class AstGraphBuilder::AstValueContext FINAL : public AstContext {
339 explicit AstValueContext(AstGraphBuilder* owner)
340 : AstContext(owner, Expression::kValue) {}
341 virtual ~AstValueContext();
342 virtual void ProduceValue(Node* value) OVERRIDE;
343 virtual Node* ConsumeValue() OVERRIDE;
347 // Context to evaluate expression for a condition value (and side effects).
348 class AstGraphBuilder::AstTestContext FINAL : public AstContext {
350 explicit AstTestContext(AstGraphBuilder* owner)
351 : AstContext(owner, Expression::kTest) {}
352 virtual ~AstTestContext();
353 virtual void ProduceValue(Node* value) OVERRIDE;
354 virtual Node* ConsumeValue() OVERRIDE;
358 // Scoped class tracking breakable statements entered by the visitor. Allows to
359 // properly 'break' and 'continue' iteration statements as well as to 'break'
360 // from blocks within switch statements.
361 class AstGraphBuilder::BreakableScope BASE_EMBEDDED {
363 BreakableScope(AstGraphBuilder* owner, BreakableStatement* target,
364 ControlBuilder* control, int drop_extra)
367 next_(owner->breakable()),
369 drop_extra_(drop_extra) {
370 owner_->set_breakable(this); // Push.
374 owner_->set_breakable(next_); // Pop.
377 // Either 'break' or 'continue' the target statement.
378 void BreakTarget(BreakableStatement* target);
379 void ContinueTarget(BreakableStatement* target);
382 AstGraphBuilder* owner_;
383 BreakableStatement* target_;
384 BreakableScope* next_;
385 ControlBuilder* control_;
388 // Find the correct scope for the target statement. Note that this also drops
389 // extra operands from the environment for each scope skipped along the way.
390 BreakableScope* FindBreakable(BreakableStatement* target);
394 // Scoped class tracking context objects created by the visitor. Represents
395 // mutations of the context chain within the function body and allows to
396 // change the current {scope} and {context} during visitation.
397 class AstGraphBuilder::ContextScope BASE_EMBEDDED {
399 ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context)
401 next_(owner->execution_context()),
402 outer_(owner->current_context()),
404 owner_->set_execution_context(this); // Push.
405 owner_->set_current_context(context);
409 owner_->set_execution_context(next_); // Pop.
410 owner_->set_current_context(outer_);
413 // Current scope during visitation.
414 Scope* scope() const { return scope_; }
417 AstGraphBuilder* owner_;
423 Scope* AstGraphBuilder::current_scope() const {
424 return execution_context_->scope();
428 } // namespace v8::internal::compiler
430 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_