src/v8/src/compiler/ast-graph-builder.h

   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
  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
 118   // List of global declarations for functions and variables.
 119   ZoneList<Handle<Object> > globals_;
 120
 121   // Stack of breakable statements entered by the visitor.
 122   BreakableScope* breakable_;
 123
 124   // Stack of context objects pushed onto the chain by the visitor.
 125   ContextScope* execution_context_;
 126
 127   // Nodes representing values in the activation record.
 128   SetOncePointer<Node> function_closure_;
 129   SetOncePointer<Node> function_context_;
 130
 131   CompilationInfo* info() { return info_; }
 132   StrictMode strict_mode() { return info()->strict_mode(); }
 133   JSGraph* jsgraph() { return jsgraph_; }
 134   JSOperatorBuilder* javascript() { return jsgraph_->javascript(); }
 135   ZoneList<Handle<Object> >* globals() { return &globals_; }
 136
 137   // Current scope during visitation.
 138   inline Scope* current_scope() const;
 139
 140   // Process arguments to a call by popping {arity} elements off the operand
 141   // stack and build a call node using the given call operator.
 142   Node* ProcessArguments(Operator* op, int arity);
 143
 144   // Visit statements.
 145   void VisitIfNotNull(Statement* stmt);
 146
 147   // Visit expressions.
 148   void VisitForTest(Expression* expr);
 149   void VisitForEffect(Expression* expr);
 150   void VisitForValue(Expression* expr);
 151   void VisitForValueOrNull(Expression* expr);
 152   void VisitForValues(ZoneList<Expression*>* exprs);
 153
 154   // Common for all IterationStatement bodies.
 155   void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int);
 156
 157   // Dispatched from VisitCallRuntime.
 158   void VisitCallJSRuntime(CallRuntime* expr);
 159
 160   // Dispatched from VisitUnaryOperation.
 161   void VisitDelete(UnaryOperation* expr);
 162   void VisitVoid(UnaryOperation* expr);
 163   void VisitTypeof(UnaryOperation* expr);
 164   void VisitNot(UnaryOperation* expr);
 165
 166   // Dispatched from VisitBinaryOperation.
 167   void VisitComma(BinaryOperation* expr);
 168   void VisitLogicalExpression(BinaryOperation* expr);
 169   void VisitArithmeticExpression(BinaryOperation* expr);
 170
 171   // Dispatched from VisitForInStatement.
 172   void VisitForInAssignment(Expression* expr, Node* value);
 173
 174   void BuildLazyBailout(Node* node, BailoutId ast_id);
 175   void BuildLazyBailoutWithPushedNode(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 static_cast<int>(values()->size()) - parameters_count_ -
 200            locals_count_;
 201   }
 202
 203   // Operations on parameter or local variables. The parameter indices are
 204   // shifted by 1 (receiver is parameter index -1 but environment index 0).
 205   void Bind(Variable* variable, Node* node) {
 206     DCHECK(variable->IsStackAllocated());
 207     if (variable->IsParameter()) {
 208       values()->at(variable->index() + 1) = node;
 209       parameters_dirty_ = true;
 210     } else {
 211       DCHECK(variable->IsStackLocal());
 212       values()->at(variable->index() + parameters_count_) = node;
 213       locals_dirty_ = true;
 214     }
 215   }
 216   Node* Lookup(Variable* variable) {
 217     DCHECK(variable->IsStackAllocated());
 218     if (variable->IsParameter()) {
 219       return values()->at(variable->index() + 1);
 220     } else {
 221       DCHECK(variable->IsStackLocal());
 222       return values()->at(variable->index() + parameters_count_);
 223     }
 224   }
 225
 226   // Operations on the operand stack.
 227   void Push(Node* node) {
 228     values()->push_back(node);
 229     stack_dirty_ = true;
 230   }
 231   Node* Top() {
 232     DCHECK(stack_height() > 0);
 233     return values()->back();
 234   }
 235   Node* Pop() {
 236     DCHECK(stack_height() > 0);
 237     Node* back = values()->back();
 238     values()->pop_back();
 239     stack_dirty_ = true;
 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     stack_dirty_ = true;
 249   }
 250   Node* Peek(int depth) {
 251     DCHECK(depth >= 0 && depth < stack_height());
 252     int index = static_cast<int>(values()->size()) - depth - 1;
 253     return values()->at(index);
 254   }
 255   void Drop(int depth) {
 256     DCHECK(depth >= 0 && depth <= stack_height());
 257     values()->erase(values()->end() - depth, values()->end());
 258     stack_dirty_ = true;
 259   }
 260
 261   // Preserve a checkpoint of the environment for the IR graph. Any
 262   // further mutation of the environment will not affect checkpoints.
 263   Node* Checkpoint(BailoutId ast_id);
 264
 265  private:
 266   int parameters_count_;
 267   int locals_count_;
 268   Node* parameters_node_;
 269   Node* locals_node_;
 270   Node* stack_node_;
 271   bool parameters_dirty_;
 272   bool locals_dirty_;
 273   bool stack_dirty_;
 274 };
 275
 276
 277 // Each expression in the AST is evaluated in a specific context. This context
 278 // decides how the evaluation result is passed up the visitor.
 279 class AstGraphBuilder::AstContext BASE_EMBEDDED {
 280  public:
 281   bool IsEffect() const { return kind_ == Expression::kEffect; }
 282   bool IsValue() const { return kind_ == Expression::kValue; }
 283   bool IsTest() const { return kind_ == Expression::kTest; }
 284
 285   // Plug a node into this expression context.  Call this function in tail
 286   // position in the Visit functions for expressions.
 287   virtual void ProduceValue(Node* value) = 0;
 288   virtual void ProduceValueWithLazyBailout(Node* value) = 0;
 289
 290   // Unplugs a node from this expression context.  Call this to retrieve the
 291   // result of another Visit function that already plugged the context.
 292   virtual Node* ConsumeValue() = 0;
 293
 294   // Shortcut for "context->ProduceValue(context->ConsumeValue())".
 295   void ReplaceValue() { ProduceValue(ConsumeValue()); }
 296
 297  protected:
 298   AstContext(AstGraphBuilder* owner, Expression::Context kind,
 299              BailoutId bailout_id);
 300   virtual ~AstContext();
 301
 302   AstGraphBuilder* owner() const { return owner_; }
 303   Environment* environment() const { return owner_->environment(); }
 304
 305 // We want to be able to assert, in a context-specific way, that the stack
 306 // height makes sense when the context is filled.
 307 #ifdef DEBUG
 308   int original_height_;
 309 #endif
 310
 311   BailoutId bailout_id_;
 312
 313  private:
 314   Expression::Context kind_;
 315   AstGraphBuilder* owner_;
 316   AstContext* outer_;
 317 };
 318
 319
 320 // Context to evaluate expression for its side effects only.
 321 class AstGraphBuilder::AstEffectContext V8_FINAL : public AstContext {
 322  public:
 323   explicit AstEffectContext(AstGraphBuilder* owner, BailoutId bailout_id)
 324       : AstContext(owner, Expression::kEffect, bailout_id) {}
 325   virtual ~AstEffectContext();
 326   virtual void ProduceValue(Node* value) V8_OVERRIDE;
 327   virtual void ProduceValueWithLazyBailout(Node* value) V8_OVERRIDE;
 328   virtual Node* ConsumeValue() V8_OVERRIDE;
 329 };
 330
 331
 332 // Context to evaluate expression for its value (and side effects).
 333 class AstGraphBuilder::AstValueContext V8_FINAL : public AstContext {
 334  public:
 335   explicit AstValueContext(AstGraphBuilder* owner, BailoutId bailout_id)
 336       : AstContext(owner, Expression::kValue, bailout_id) {}
 337   virtual ~AstValueContext();
 338   virtual void ProduceValue(Node* value) V8_OVERRIDE;
 339   virtual void ProduceValueWithLazyBailout(Node* value) V8_OVERRIDE;
 340   virtual Node* ConsumeValue() V8_OVERRIDE;
 341 };
 342
 343
 344 // Context to evaluate expression for a condition value (and side effects).
 345 class AstGraphBuilder::AstTestContext V8_FINAL : public AstContext {
 346  public:
 347   explicit AstTestContext(AstGraphBuilder* owner, BailoutId bailout_id)
 348       : AstContext(owner, Expression::kTest, bailout_id) {}
 349   virtual ~AstTestContext();
 350   virtual void ProduceValue(Node* value) V8_OVERRIDE;
 351   virtual void ProduceValueWithLazyBailout(Node* value) V8_OVERRIDE;
 352   virtual Node* ConsumeValue() V8_OVERRIDE;
 353 };
 354
 355
 356 // Scoped class tracking breakable statements entered by the visitor. Allows to
 357 // properly 'break' and 'continue' iteration statements as well as to 'break'
 358 // from blocks within switch statements.
 359 class AstGraphBuilder::BreakableScope BASE_EMBEDDED {
 360  public:
 361   BreakableScope(AstGraphBuilder* owner, BreakableStatement* target,
 362                  ControlBuilder* control, int drop_extra)
 363       : owner_(owner),
 364         target_(target),
 365         next_(owner->breakable()),
 366         control_(control),
 367         drop_extra_(drop_extra) {
 368     owner_->set_breakable(this);  // Push.
 369   }
 370
 371   ~BreakableScope() {
 372     owner_->set_breakable(next_);  // Pop.
 373   }
 374
 375   // Either 'break' or 'continue' the target statement.
 376   void BreakTarget(BreakableStatement* target);
 377   void ContinueTarget(BreakableStatement* target);
 378
 379  private:
 380   AstGraphBuilder* owner_;
 381   BreakableStatement* target_;
 382   BreakableScope* next_;
 383   ControlBuilder* control_;
 384   int drop_extra_;
 385
 386   // Find the correct scope for the target statement. Note that this also drops
 387   // extra operands from the environment for each scope skipped along the way.
 388   BreakableScope* FindBreakable(BreakableStatement* target);
 389 };
 390
 391
 392 // Scoped class tracking context objects created by the visitor. Represents
 393 // mutations of the context chain within the function body and allows to
 394 // change the current {scope} and {context} during visitation.
 395 class AstGraphBuilder::ContextScope BASE_EMBEDDED {
 396  public:
 397   ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context)
 398       : owner_(owner),
 399         next_(owner->execution_context()),
 400         outer_(owner->current_context()),
 401         scope_(scope) {
 402     owner_->set_execution_context(this);  // Push.
 403     owner_->set_current_context(context);
 404   }
 405
 406   ~ContextScope() {
 407     owner_->set_execution_context(next_);  // Pop.
 408     owner_->set_current_context(outer_);
 409   }
 410
 411   // Current scope during visitation.
 412   Scope* scope() const { return scope_; }
 413
 414  private:
 415   AstGraphBuilder* owner_;
 416   ContextScope* next_;
 417   Node* outer_;
 418   Scope* scope_;
 419 };
 420
 421 Scope* AstGraphBuilder::current_scope() const {
 422   return execution_context_->scope();
 423 }
 424 }
 425 }
 426 }  // namespace v8::internal::compiler
 427
 428 #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_