Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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. |
| 4 | |
| 5 | #ifndef V8_COMPILER_AST_GRAPH_BUILDER_H_ |
| 6 | #define V8_COMPILER_AST_GRAPH_BUILDER_H_ |
| 7 | |
| 8 | #include "src/v8.h" |
| 9 | |
| 10 | #include "src/ast.h" |
| 11 | #include "src/compiler/graph-builder.h" |
| 12 | #include "src/compiler/js-graph.h" |
| 13 | |
| 14 | namespace v8 { |
| 15 | namespace internal { |
| 16 | namespace compiler { |
| 17 | |
| 18 | class ControlBuilder; |
| 19 | class LoopBuilder; |
| 20 | class Graph; |
| 21 | |
| 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 { |
| 27 | public: |
| 28 | AstGraphBuilder(CompilationInfo* info, JSGraph* jsgraph); |
| 29 | |
| 30 | // Creates a graph by visiting the entire AST. |
| 31 | bool CreateGraph(); |
| 32 | |
| 33 | protected: |
| 34 | class AstContext; |
| 35 | class AstEffectContext; |
| 36 | class AstValueContext; |
| 37 | class AstTestContext; |
| 38 | class BreakableScope; |
| 39 | class ContextScope; |
| 40 | class Environment; |
| 41 | |
| 42 | Environment* environment() { |
| 43 | return reinterpret_cast<Environment*>( |
| 44 | StructuredGraphBuilder::environment()); |
| 45 | } |
| 46 | |
| 47 | AstContext* ast_context() const { return ast_context_; } |
| 48 | BreakableScope* breakable() const { return breakable_; } |
| 49 | ContextScope* execution_context() const { return execution_context_; } |
| 50 | |
| 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; } |
| 54 | |
| 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); |
| 59 | |
| 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; |
| 63 | |
| 64 | // Getters for values in the activation record. |
| 65 | Node* GetFunctionClosure(); |
| 66 | Node* GetFunctionContext(); |
| 67 | |
| 68 | // |
| 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. |
| 72 | // |
| 73 | |
| 74 | // Builder to create a local function context. |
| 75 | Node* BuildLocalFunctionContext(Node* context, Node* closure); |
| 76 | |
| 77 | // Builder to create an arguments object if it is used. |
| 78 | Node* BuildArgumentsObject(Variable* arguments); |
| 79 | |
| 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); |
| 86 | |
| 87 | // Builders for accessing the function context. |
| 88 | Node* BuildLoadBuiltinsObject(); |
| 89 | Node* BuildLoadGlobalObject(); |
| 90 | Node* BuildLoadClosure(); |
| 91 | Node* BuildLoadObjectField(Node* object, int offset); |
| 92 | |
| 93 | // Builders for automatic type conversion. |
| 94 | Node* BuildToBoolean(Node* value); |
| 95 | |
| 96 | // Builders for error reporting at runtime. |
| 97 | Node* BuildThrowReferenceError(Variable* var); |
| 98 | |
| 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); |
| 102 | |
| 103 | // Builders for binary operations. |
| 104 | Node* BuildBinaryOp(Node* left, Node* right, Token::Value op); |
| 105 | |
| 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) |
| 109 | #undef DECLARE_VISIT |
| 110 | |
| 111 | // Visiting function for declarations list is overridden. |
| 112 | virtual void VisitDeclarations(ZoneList<Declaration*>* declarations); |
| 113 | |
| 114 | private: |
| 115 | CompilationInfo* info_; |
| 116 | AstContext* ast_context_; |
| 117 | JSGraph* jsgraph_; |
| 118 | |
| 119 | // List of global declarations for functions and variables. |
| 120 | ZoneList<Handle<Object> > globals_; |
| 121 | |
| 122 | // Stack of breakable statements entered by the visitor. |
| 123 | BreakableScope* breakable_; |
| 124 | |
| 125 | // Stack of context objects pushed onto the chain by the visitor. |
| 126 | ContextScope* execution_context_; |
| 127 | |
| 128 | // Nodes representing values in the activation record. |
| 129 | SetOncePointer<Node> function_closure_; |
| 130 | SetOncePointer<Node> function_context_; |
| 131 | |
| 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_; } |
| 137 | |
| 138 | // Current scope during visitation. |
| 139 | inline Scope* current_scope() const; |
| 140 | |
| 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); |
| 144 | |
| 145 | // Visit statements. |
| 146 | void VisitIfNotNull(Statement* stmt); |
| 147 | |
| 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); |
| 154 | |
| 155 | // Common for all IterationStatement bodies. |
| 156 | void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int); |
| 157 | |
| 158 | // Dispatched from VisitCallRuntime. |
| 159 | void VisitCallJSRuntime(CallRuntime* expr); |
| 160 | |
| 161 | // Dispatched from VisitUnaryOperation. |
| 162 | void VisitDelete(UnaryOperation* expr); |
| 163 | void VisitVoid(UnaryOperation* expr); |
| 164 | void VisitTypeof(UnaryOperation* expr); |
| 165 | void VisitNot(UnaryOperation* expr); |
| 166 | |
| 167 | // Dispatched from VisitBinaryOperation. |
| 168 | void VisitComma(BinaryOperation* expr); |
| 169 | void VisitLogicalExpression(BinaryOperation* expr); |
| 170 | void VisitArithmeticExpression(BinaryOperation* expr); |
| 171 | |
| 172 | // Dispatched from VisitForInStatement. |
| 173 | void VisitForInAssignment(Expression* expr, Node* value); |
| 174 | |
| 175 | // Builds deoptimization for a given node. |
| 176 | void PrepareFrameState(Node* node, BailoutId ast_id, |
| 177 | OutputFrameStateCombine combine = kIgnoreOutput); |
| 178 | |
| 179 | OutputFrameStateCombine StateCombineFromAstContext(); |
| 180 | |
| 181 | DEFINE_AST_VISITOR_SUBCLASS_MEMBERS(); |
| 182 | DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder); |
| 183 | }; |
| 184 | |
| 185 | |
| 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: |
| 191 | // |
| 192 | // [parameters (+receiver)] [locals] [operand stack] |
| 193 | // |
| 194 | class AstGraphBuilder::Environment |
| 195 | : public StructuredGraphBuilder::Environment { |
| 196 | public: |
| 197 | Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); |
| 198 | Environment(const Environment& copy); |
| 199 | |
| 200 | int parameters_count() const { return parameters_count_; } |
| 201 | int locals_count() const { return locals_count_; } |
| 202 | int stack_height() { |
| 203 | return static_cast<int>(values()->size()) - parameters_count_ - |
| 204 | locals_count_; |
| 205 | } |
| 206 | |
| 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; |
| 213 | } else { |
| 214 | DCHECK(variable->IsStackLocal()); |
| 215 | values()->at(variable->index() + parameters_count_) = node; |
| 216 | } |
| 217 | } |
| 218 | Node* Lookup(Variable* variable) { |
| 219 | DCHECK(variable->IsStackAllocated()); |
| 220 | if (variable->IsParameter()) { |
| 221 | return values()->at(variable->index() + 1); |
| 222 | } else { |
| 223 | DCHECK(variable->IsStackLocal()); |
| 224 | return values()->at(variable->index() + parameters_count_); |
| 225 | } |
| 226 | } |
| 227 | |
| 228 | // Operations on the operand stack. |
| 229 | void Push(Node* node) { |
| 230 | values()->push_back(node); |
| 231 | } |
| 232 | Node* Top() { |
| 233 | DCHECK(stack_height() > 0); |
| 234 | return values()->back(); |
| 235 | } |
| 236 | Node* Pop() { |
| 237 | DCHECK(stack_height() > 0); |
| 238 | Node* back = values()->back(); |
| 239 | values()->pop_back(); |
| 240 | return back; |
| 241 | } |
| 242 | |
| 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; |
| 248 | } |
| 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); |
| 253 | } |
| 254 | void Drop(int depth) { |
| 255 | DCHECK(depth >= 0 && depth <= stack_height()); |
| 256 | values()->erase(values()->end() - depth, values()->end()); |
| 257 | } |
| 258 | |
| 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); |
| 262 | |
| 263 | protected: |
| 264 | AstGraphBuilder* builder() const { |
| 265 | return reinterpret_cast<AstGraphBuilder*>( |
| 266 | StructuredGraphBuilder::Environment::builder()); |
| 267 | } |
| 268 | |
| 269 | private: |
| 270 | void UpdateStateValues(Node** state_values, int offset, int count); |
| 271 | |
| 272 | int parameters_count_; |
| 273 | int locals_count_; |
| 274 | Node* parameters_node_; |
| 275 | Node* locals_node_; |
| 276 | Node* stack_node_; |
| 277 | }; |
| 278 | |
| 279 | |
| 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 { |
| 283 | public: |
| 284 | bool IsEffect() const { return kind_ == Expression::kEffect; } |
| 285 | bool IsValue() const { return kind_ == Expression::kValue; } |
| 286 | bool IsTest() const { return kind_ == Expression::kTest; } |
| 287 | |
| 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; |
| 292 | } |
| 293 | |
| 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; |
| 297 | |
| 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; |
| 301 | |
| 302 | // Shortcut for "context->ProduceValue(context->ConsumeValue())". |
| 303 | void ReplaceValue() { ProduceValue(ConsumeValue()); } |
| 304 | |
| 305 | protected: |
| 306 | AstContext(AstGraphBuilder* owner, Expression::Context kind); |
| 307 | virtual ~AstContext(); |
| 308 | |
| 309 | AstGraphBuilder* owner() const { return owner_; } |
| 310 | Environment* environment() const { return owner_->environment(); } |
| 311 | |
| 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. |
| 314 | #ifdef DEBUG |
| 315 | int original_height_; |
| 316 | #endif |
| 317 | |
| 318 | private: |
| 319 | Expression::Context kind_; |
| 320 | AstGraphBuilder* owner_; |
| 321 | AstContext* outer_; |
| 322 | }; |
| 323 | |
| 324 | |
| 325 | // Context to evaluate expression for its side effects only. |
| 326 | class AstGraphBuilder::AstEffectContext FINAL : public AstContext { |
| 327 | public: |
| 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; |
| 333 | }; |
| 334 | |
| 335 | |
| 336 | // Context to evaluate expression for its value (and side effects). |
| 337 | class AstGraphBuilder::AstValueContext FINAL : public AstContext { |
| 338 | public: |
| 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; |
| 344 | }; |
| 345 | |
| 346 | |
| 347 | // Context to evaluate expression for a condition value (and side effects). |
| 348 | class AstGraphBuilder::AstTestContext FINAL : public AstContext { |
| 349 | public: |
| 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; |
| 355 | }; |
| 356 | |
| 357 | |
| 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 { |
| 362 | public: |
| 363 | BreakableScope(AstGraphBuilder* owner, BreakableStatement* target, |
| 364 | ControlBuilder* control, int drop_extra) |
| 365 | : owner_(owner), |
| 366 | target_(target), |
| 367 | next_(owner->breakable()), |
| 368 | control_(control), |
| 369 | drop_extra_(drop_extra) { |
| 370 | owner_->set_breakable(this); // Push. |
| 371 | } |
| 372 | |
| 373 | ~BreakableScope() { |
| 374 | owner_->set_breakable(next_); // Pop. |
| 375 | } |
| 376 | |
| 377 | // Either 'break' or 'continue' the target statement. |
| 378 | void BreakTarget(BreakableStatement* target); |
| 379 | void ContinueTarget(BreakableStatement* target); |
| 380 | |
| 381 | private: |
| 382 | AstGraphBuilder* owner_; |
| 383 | BreakableStatement* target_; |
| 384 | BreakableScope* next_; |
| 385 | ControlBuilder* control_; |
| 386 | int drop_extra_; |
| 387 | |
| 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); |
| 391 | }; |
| 392 | |
| 393 | |
| 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 { |
| 398 | public: |
| 399 | ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context) |
| 400 | : owner_(owner), |
| 401 | next_(owner->execution_context()), |
| 402 | outer_(owner->current_context()), |
| 403 | scope_(scope) { |
| 404 | owner_->set_execution_context(this); // Push. |
| 405 | owner_->set_current_context(context); |
| 406 | } |
| 407 | |
| 408 | ~ContextScope() { |
| 409 | owner_->set_execution_context(next_); // Pop. |
| 410 | owner_->set_current_context(outer_); |
| 411 | } |
| 412 | |
| 413 | // Current scope during visitation. |
| 414 | Scope* scope() const { return scope_; } |
| 415 | |
| 416 | private: |
| 417 | AstGraphBuilder* owner_; |
| 418 | ContextScope* next_; |
| 419 | Node* outer_; |
| 420 | Scope* scope_; |
| 421 | }; |
| 422 | |
| 423 | Scope* AstGraphBuilder::current_scope() const { |
| 424 | return execution_context_->scope(); |
| 425 | } |
| 426 | } |
| 427 | } |
| 428 | } // namespace v8::internal::compiler |
| 429 | |
| 430 | #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ |