OLD | NEW |
(Empty) | |
| 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 SourcePositionTable* source_positions_); |
| 30 |
| 31 // Creates a graph by visiting the entire AST. |
| 32 bool CreateGraph(); |
| 33 |
| 34 protected: |
| 35 class AstContext; |
| 36 class AstEffectContext; |
| 37 class AstValueContext; |
| 38 class AstTestContext; |
| 39 class BreakableScope; |
| 40 class ContextScope; |
| 41 class Environment; |
| 42 |
| 43 Environment* environment() { |
| 44 return reinterpret_cast<Environment*>(environment_internal()); |
| 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 SourcePositionTable* source_positions() { return source_positions_; } |
| 61 |
| 62 // TODO(mstarzinger): The pipeline only needs to be a friend to access the |
| 63 // function context. Remove as soon as the context is a parameter. |
| 64 friend class Pipeline; |
| 65 |
| 66 // Getters for values in the activation record. |
| 67 Node* GetFunctionClosure(); |
| 68 Node* GetFunctionContext(); |
| 69 |
| 70 // |
| 71 // The following build methods all generate graph fragments and return one |
| 72 // resulting node. The operand stack height remains the same, variables and |
| 73 // other dependencies tracked by the environment might be mutated though. |
| 74 // |
| 75 |
| 76 // Builder to create a local function context. |
| 77 Node* BuildLocalFunctionContext(Node* context, Node* closure); |
| 78 |
| 79 // Builder to create an arguments object if it is used. |
| 80 Node* BuildArgumentsObject(Variable* arguments); |
| 81 |
| 82 // Builders for variable load and assignment. |
| 83 Node* BuildVariableAssignment(Variable* var, Node* value, Token::Value op); |
| 84 Node* BuildVariableDelete(Variable* var); |
| 85 Node* BuildVariableLoad(Variable* var, ContextualMode mode = CONTEXTUAL); |
| 86 |
| 87 // Builders for accessing the function context. |
| 88 Node* BuildLoadBuiltinsObject(); |
| 89 Node* BuildLoadGlobalObject(); |
| 90 Node* BuildLoadClosure(); |
| 91 |
| 92 // Builders for automatic type conversion. |
| 93 Node* BuildToBoolean(Node* value); |
| 94 |
| 95 // Builders for error reporting at runtime. |
| 96 Node* BuildThrowReferenceError(Variable* var); |
| 97 |
| 98 // Builders for dynamic hole-checks at runtime. |
| 99 Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole); |
| 100 Node* BuildHoleCheckThrow(Node* value, Variable* var, Node* not_hole); |
| 101 |
| 102 // Builders for binary operations. |
| 103 Node* BuildBinaryOp(Node* left, Node* right, Token::Value op); |
| 104 |
| 105 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); |
| 106 // Visiting functions for AST nodes make this an AstVisitor. |
| 107 AST_NODE_LIST(DECLARE_VISIT) |
| 108 #undef DECLARE_VISIT |
| 109 |
| 110 // Visiting function for declarations list is overridden. |
| 111 virtual void VisitDeclarations(ZoneList<Declaration*>* declarations); |
| 112 |
| 113 private: |
| 114 CompilationInfo* info_; |
| 115 AstContext* ast_context_; |
| 116 JSGraph* jsgraph_; |
| 117 SourcePositionTable* source_positions_; |
| 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(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 void BuildLazyBailout(Node* node, BailoutId ast_id); |
| 176 |
| 177 DEFINE_AST_VISITOR_SUBCLASS_MEMBERS(); |
| 178 DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder); |
| 179 }; |
| 180 |
| 181 |
| 182 // The abstract execution environment for generated code consists of |
| 183 // parameter variables, local variables and the operand stack. The |
| 184 // environment will perform proper SSA-renaming of all tracked nodes |
| 185 // at split and merge points in the control flow. Internally all the |
| 186 // values are stored in one list using the following layout: |
| 187 // |
| 188 // [parameters (+receiver)] [locals] [operand stack] |
| 189 // |
| 190 class AstGraphBuilder::Environment |
| 191 : public StructuredGraphBuilder::Environment { |
| 192 public: |
| 193 Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency); |
| 194 Environment(const Environment& copy); |
| 195 |
| 196 int parameters_count() const { return parameters_count_; } |
| 197 int locals_count() const { return locals_count_; } |
| 198 int stack_height() { |
| 199 return values()->size() - parameters_count_ - locals_count_; |
| 200 } |
| 201 |
| 202 // Operations on parameter or local variables. The parameter indices are |
| 203 // shifted by 1 (receiver is parameter index -1 but environment index 0). |
| 204 void Bind(Variable* variable, Node* node) { |
| 205 ASSERT(variable->IsStackAllocated()); |
| 206 if (variable->IsParameter()) { |
| 207 values()->at(variable->index() + 1) = node; |
| 208 parameters_dirty_ = true; |
| 209 } else { |
| 210 ASSERT(variable->IsStackLocal()); |
| 211 values()->at(variable->index() + parameters_count_) = node; |
| 212 locals_dirty_ = true; |
| 213 } |
| 214 } |
| 215 Node* Lookup(Variable* variable) { |
| 216 ASSERT(variable->IsStackAllocated()); |
| 217 if (variable->IsParameter()) { |
| 218 return values()->at(variable->index() + 1); |
| 219 } else { |
| 220 ASSERT(variable->IsStackLocal()); |
| 221 return values()->at(variable->index() + parameters_count_); |
| 222 } |
| 223 } |
| 224 |
| 225 // Operations on the operand stack. |
| 226 void Push(Node* node) { |
| 227 values()->push_back(node); |
| 228 stack_dirty_ = true; |
| 229 } |
| 230 Node* Top() { |
| 231 ASSERT(stack_height() > 0); |
| 232 return values()->back(); |
| 233 } |
| 234 Node* Pop() { |
| 235 ASSERT(stack_height() > 0); |
| 236 Node* back = values()->back(); |
| 237 values()->pop_back(); |
| 238 return back; |
| 239 } |
| 240 |
| 241 // Direct mutations of the operand stack. |
| 242 void Poke(int depth, Node* node) { |
| 243 ASSERT(depth >= 0 && depth < stack_height()); |
| 244 int index = values()->size() - depth - 1; |
| 245 values()->at(index) = node; |
| 246 } |
| 247 Node* Peek(int depth) { |
| 248 ASSERT(depth >= 0 && depth < stack_height()); |
| 249 int index = values()->size() - depth - 1; |
| 250 return values()->at(index); |
| 251 } |
| 252 void Drop(int depth) { |
| 253 ASSERT(depth >= 0 && depth <= stack_height()); |
| 254 values()->erase(values()->end() - depth, values()->end()); |
| 255 } |
| 256 |
| 257 // Preserve a checkpoint of the environment for the IR graph. Any |
| 258 // further mutation of the environment will not affect checkpoints. |
| 259 Node* Checkpoint(BailoutId ast_id); |
| 260 |
| 261 private: |
| 262 int parameters_count_; |
| 263 int locals_count_; |
| 264 Node* parameters_node_; |
| 265 Node* locals_node_; |
| 266 Node* stack_node_; |
| 267 bool parameters_dirty_; |
| 268 bool locals_dirty_; |
| 269 bool stack_dirty_; |
| 270 }; |
| 271 |
| 272 |
| 273 // Each expression in the AST is evaluated in a specific context. This context |
| 274 // decides how the evaluation result is passed up the visitor. |
| 275 class AstGraphBuilder::AstContext BASE_EMBEDDED { |
| 276 public: |
| 277 bool IsEffect() const { return kind_ == Expression::kEffect; } |
| 278 bool IsValue() const { return kind_ == Expression::kValue; } |
| 279 bool IsTest() const { return kind_ == Expression::kTest; } |
| 280 |
| 281 // Plug a node into this expression context. Call this function in tail |
| 282 // position in the Visit functions for expressions. |
| 283 virtual void ProduceValue(Node* value) = 0; |
| 284 |
| 285 // Unplugs a node from this expression context. Call this to retrieve the |
| 286 // result of another Visit function that already plugged the context. |
| 287 virtual Node* ConsumeValue() = 0; |
| 288 |
| 289 // Shortcut for "context->ProduceValue(context->ConsumeValue())". |
| 290 void ReplaceValue() { ProduceValue(ConsumeValue()); } |
| 291 |
| 292 protected: |
| 293 AstContext(AstGraphBuilder* owner, Expression::Context kind); |
| 294 virtual ~AstContext(); |
| 295 |
| 296 AstGraphBuilder* owner() const { return owner_; } |
| 297 Environment* environment() const { return owner_->environment(); } |
| 298 |
| 299 // We want to be able to assert, in a context-specific way, that the stack |
| 300 // height makes sense when the context is filled. |
| 301 #ifdef DEBUG |
| 302 int original_height_; |
| 303 #endif |
| 304 |
| 305 private: |
| 306 Expression::Context kind_; |
| 307 AstGraphBuilder* owner_; |
| 308 AstContext* outer_; |
| 309 }; |
| 310 |
| 311 |
| 312 // Context to evaluate expression for its side effects only. |
| 313 class AstGraphBuilder::AstEffectContext V8_FINAL : public AstContext { |
| 314 public: |
| 315 explicit AstEffectContext(AstGraphBuilder* owner) |
| 316 : AstContext(owner, Expression::kEffect) {} |
| 317 virtual ~AstEffectContext(); |
| 318 virtual void ProduceValue(Node* value) V8_OVERRIDE; |
| 319 virtual Node* ConsumeValue() V8_OVERRIDE; |
| 320 }; |
| 321 |
| 322 |
| 323 // Context to evaluate expression for its value (and side effects). |
| 324 class AstGraphBuilder::AstValueContext V8_FINAL : public AstContext { |
| 325 public: |
| 326 explicit AstValueContext(AstGraphBuilder* owner) |
| 327 : AstContext(owner, Expression::kValue) {} |
| 328 virtual ~AstValueContext(); |
| 329 virtual void ProduceValue(Node* value) V8_OVERRIDE; |
| 330 virtual Node* ConsumeValue() V8_OVERRIDE; |
| 331 }; |
| 332 |
| 333 |
| 334 // Context to evaluate expression for a condition value (and side effects). |
| 335 class AstGraphBuilder::AstTestContext V8_FINAL : public AstContext { |
| 336 public: |
| 337 explicit AstTestContext(AstGraphBuilder* owner) |
| 338 : AstContext(owner, Expression::kTest) {} |
| 339 virtual ~AstTestContext(); |
| 340 virtual void ProduceValue(Node* value) V8_OVERRIDE; |
| 341 virtual Node* ConsumeValue() V8_OVERRIDE; |
| 342 }; |
| 343 |
| 344 |
| 345 // Scoped class tracking breakable statements entered by the visitor. Allows to |
| 346 // properly 'break' and 'continue' iteration statements as well as to 'break' |
| 347 // from blocks within switch statements. |
| 348 class AstGraphBuilder::BreakableScope BASE_EMBEDDED { |
| 349 public: |
| 350 BreakableScope(AstGraphBuilder* owner, BreakableStatement* target, |
| 351 ControlBuilder* control, int drop_extra) |
| 352 : owner_(owner), |
| 353 target_(target), |
| 354 next_(owner->breakable()), |
| 355 control_(control), |
| 356 drop_extra_(drop_extra) { |
| 357 owner_->set_breakable(this); // Push. |
| 358 } |
| 359 |
| 360 ~BreakableScope() { |
| 361 owner_->set_breakable(next_); // Pop. |
| 362 } |
| 363 |
| 364 // Either 'break' or 'continue' the target statement. |
| 365 void BreakTarget(BreakableStatement* target); |
| 366 void ContinueTarget(BreakableStatement* target); |
| 367 |
| 368 private: |
| 369 AstGraphBuilder* owner_; |
| 370 BreakableStatement* target_; |
| 371 BreakableScope* next_; |
| 372 ControlBuilder* control_; |
| 373 int drop_extra_; |
| 374 |
| 375 // Find the correct scope for the target statement. Note that this also drops |
| 376 // extra operands from the environment for each scope skipped along the way. |
| 377 BreakableScope* FindBreakable(BreakableStatement* target); |
| 378 }; |
| 379 |
| 380 |
| 381 // Scoped class tracking context objects created by the visitor. Represents |
| 382 // mutations of the context chain within the function body and allows to |
| 383 // change the current {scope} and {context} during visitation. |
| 384 class AstGraphBuilder::ContextScope BASE_EMBEDDED { |
| 385 public: |
| 386 ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context) |
| 387 : owner_(owner), |
| 388 next_(owner->execution_context()), |
| 389 outer_(owner->current_context()), |
| 390 scope_(scope) { |
| 391 owner_->set_execution_context(this); // Push. |
| 392 owner_->set_current_context(context); |
| 393 } |
| 394 |
| 395 ~ContextScope() { |
| 396 owner_->set_execution_context(next_); // Pop. |
| 397 owner_->set_current_context(outer_); |
| 398 } |
| 399 |
| 400 // Current scope during visitation. |
| 401 Scope* scope() const { return scope_; } |
| 402 |
| 403 private: |
| 404 AstGraphBuilder* owner_; |
| 405 ContextScope* next_; |
| 406 Node* outer_; |
| 407 Scope* scope_; |
| 408 }; |
| 409 |
| 410 Scope* AstGraphBuilder::current_scope() const { |
| 411 return execution_context_->scope(); |
| 412 } |
| 413 } |
| 414 } |
| 415 } // namespace v8::internal::compiler |
| 416 |
| 417 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ |
OLD | NEW |