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 Graph;
  20 class LoopAssignmentAnalysis;
  21 class LoopBuilder;
  22
  23 // The AstGraphBuilder produces a high-level IR graph, based on an
  24 // underlying AST. The produced graph can either be compiled into a
  25 // stand-alone function or be wired into another graph for the purposes
  26 // of function inlining.
  27 class AstGraphBuilder : public StructuredGraphBuilder, public AstVisitor {
  28  public:
  29   AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph);
  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*>(
  45         StructuredGraphBuilder::environment());
  46   }
  47
  48   AstContext* ast_context() const { return ast_context_; }
  49   BreakableScope* breakable() const { return breakable_; }
  50   ContextScope* execution_context() const { return execution_context_; }
  51
  52   void set_ast_context(AstContext* ctx) { ast_context_ = ctx; }
  53   void set_breakable(BreakableScope* brk) { breakable_ = brk; }
  54   void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; }
  55
  56   // Support for control flow builders. The concrete type of the environment
  57   // depends on the graph builder, but environments themselves are not virtual.
  58   typedef StructuredGraphBuilder::Environment BaseEnvironment;
  59   virtual BaseEnvironment* CopyEnvironment(BaseEnvironment* env) OVERRIDE;
  60
  61   // TODO(mstarzinger): The pipeline only needs to be a friend to access the
  62   // function context. Remove as soon as the context is a parameter.
  63   friend class Pipeline;
  64
  65   // Getters for values in the activation record.
  66   Node* GetFunctionClosure();
  67   Node* GetFunctionContext();
  68
  69   //
  70   // The following build methods all generate graph fragments and return one
  71   // resulting node. The operand stack height remains the same, variables and
  72   // other dependencies tracked by the environment might be mutated though.
  73   //
  74
  75   // Builder to create a local function context.
  76   Node* BuildLocalFunctionContext(Node* context, Node* closure);
  77
  78   // Builder to create an arguments object if it is used.
  79   Node* BuildArgumentsObject(Variable* arguments);
  80
  81   // Builders for variable load and assignment.
  82   Node* BuildVariableAssignment(Variable* var, Node* value, Token::Value op,
  83                                 BailoutId bailout_id);
  84   Node* BuildVariableDelete(Variable* var, BailoutId bailout_id,
  85                             OutputFrameStateCombine state_combine);
  86   Node* BuildVariableLoad(Variable* var, BailoutId bailout_id,
  87                           const VectorSlotPair& feedback,
  88                           ContextualMode mode = CONTEXTUAL);
  89
  90   // Builders for accessing the function context.
  91   Node* BuildLoadBuiltinsObject();
  92   Node* BuildLoadGlobalObject();
  93   Node* BuildLoadClosure();
  94   Node* BuildLoadObjectField(Node* object, int offset);
  95
  96   // Builders for automatic type conversion.
  97   Node* BuildToBoolean(Node* value);
  98
  99   // Builders for error reporting at runtime.
 100   Node* BuildThrowReferenceError(Variable* var, BailoutId bailout_id);
 101
 102   // Builders for dynamic hole-checks at runtime.
 103   Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole);
 104   Node* BuildHoleCheckThrow(Node* value, Variable* var, Node* not_hole,
 105                             BailoutId bailout_id);
 106
 107   // Builders for binary operations.
 108   Node* BuildBinaryOp(Node* left, Node* right, Token::Value op);
 109
 110   // Builder for stack-check guards.
 111   Node* BuildStackCheck();
 112
 113 #define DECLARE_VISIT(type) virtual void Visit##type(type* node) OVERRIDE;
 114   // Visiting functions for AST nodes make this an AstVisitor.
 115   AST_NODE_LIST(DECLARE_VISIT)
 116 #undef DECLARE_VISIT
 117
 118   // Visiting function for declarations list is overridden.
 119   virtual void VisitDeclarations(ZoneList<Declaration*>* declarations) OVERRIDE;
 120
 121  private:
 122   CompilationInfo* info_;
 123   AstContext* ast_context_;
 124   JSGraph* jsgraph_;
 125
 126   // List of global declarations for functions and variables.
 127   ZoneList<Handle<Object> > globals_;
 128
 129   // Stack of breakable statements entered by the visitor.
 130   BreakableScope* breakable_;
 131
 132   // Stack of context objects pushed onto the chain by the visitor.
 133   ContextScope* execution_context_;
 134
 135   // Nodes representing values in the activation record.
 136   SetOncePointer<Node> function_closure_;
 137   SetOncePointer<Node> function_context_;
 138
 139   // Result of loop assignment analysis performed before graph creation.
 140   LoopAssignmentAnalysis* loop_assignment_analysis_;
 141
 142   CompilationInfo* info() const { return info_; }
 143   inline StrictMode strict_mode() const;
 144   JSGraph* jsgraph() { return jsgraph_; }
 145   JSOperatorBuilder* javascript() { return jsgraph_->javascript(); }
 146   ZoneList<Handle<Object> >* globals() { return &globals_; }
 147
 148   // Current scope during visitation.
 149   inline Scope* current_scope() const;
 150
 151   // Named and keyed loads require a VectorSlotPair for successful lowering.
 152   VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const;
 153
 154   // Process arguments to a call by popping {arity} elements off the operand
 155   // stack and build a call node using the given call operator.
 156   Node* ProcessArguments(const Operator* op, int arity);
 157
 158   // Visit statements.
 159   void VisitIfNotNull(Statement* stmt);
 160
 161   // Visit expressions.
 162   void Visit(Expression* expr);
 163   void VisitForTest(Expression* expr);
 164   void VisitForEffect(Expression* expr);
 165   void VisitForValue(Expression* expr);
 166   void VisitForValueOrNull(Expression* expr);
 167   void VisitForValues(ZoneList<Expression*>* exprs);
 168
 169   // Common for all IterationStatement bodies.
 170   void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int);
 171
 172   // Dispatched from VisitCallRuntime.
 173   void VisitCallJSRuntime(CallRuntime* expr);
 174
 175   // Dispatched from VisitUnaryOperation.
 176   void VisitDelete(UnaryOperation* expr);
 177   void VisitVoid(UnaryOperation* expr);
 178   void VisitTypeof(UnaryOperation* expr);
 179   void VisitNot(UnaryOperation* expr);
 180
 181   // Dispatched from VisitBinaryOperation.
 182   void VisitComma(BinaryOperation* expr);
 183   void VisitLogicalExpression(BinaryOperation* expr);
 184   void VisitArithmeticExpression(BinaryOperation* expr);
 185
 186   // Dispatched from VisitForInStatement.
 187   void VisitForInAssignment(Expression* expr, Node* value);
 188
 189   // Builds deoptimization for a given node.
 190   void PrepareFrameState(
 191       Node* node, BailoutId ast_id,
 192       OutputFrameStateCombine combine = OutputFrameStateCombine::Ignore());
 193
 194   BitVector* GetVariablesAssignedInLoop(IterationStatement* stmt);
 195
 196   DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
 197   DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder);
 198 };
 199
 200
 201 // The abstract execution environment for generated code consists of
 202 // parameter variables, local variables and the operand stack. The
 203 // environment will perform proper SSA-renaming of all tracked nodes
 204 // at split and merge points in the control flow. Internally all the
 205 // values are stored in one list using the following layout:
 206 //
 207 //  [parameters (+receiver)] [locals] [operand stack]
 208 //
 209 class AstGraphBuilder::Environment
 210     : public StructuredGraphBuilder::Environment {
 211  public:
 212   Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency);
 213   Environment(const Environment& copy);
 214
 215   int parameters_count() const { return parameters_count_; }
 216   int locals_count() const { return locals_count_; }
 217   int stack_height() {
 218     return static_cast<int>(values()->size()) - parameters_count_ -
 219            locals_count_;
 220   }
 221
 222   // Operations on parameter or local variables. The parameter indices are
 223   // shifted by 1 (receiver is parameter index -1 but environment index 0).
 224   void Bind(Variable* variable, Node* node) {
 225     DCHECK(variable->IsStackAllocated());
 226     if (variable->IsParameter()) {
 227       values()->at(variable->index() + 1) = node;
 228     } else {
 229       DCHECK(variable->IsStackLocal());
 230       values()->at(variable->index() + parameters_count_) = node;
 231     }
 232   }
 233   Node* Lookup(Variable* variable) {
 234     DCHECK(variable->IsStackAllocated());
 235     if (variable->IsParameter()) {
 236       return values()->at(variable->index() + 1);
 237     } else {
 238       DCHECK(variable->IsStackLocal());
 239       return values()->at(variable->index() + parameters_count_);
 240     }
 241   }
 242
 243   // Operations on the operand stack.
 244   void Push(Node* node) {
 245     values()->push_back(node);
 246   }
 247   Node* Top() {
 248     DCHECK(stack_height() > 0);
 249     return values()->back();
 250   }
 251   Node* Pop() {
 252     DCHECK(stack_height() > 0);
 253     Node* back = values()->back();
 254     values()->pop_back();
 255     return back;
 256   }
 257
 258   // Direct mutations of the operand stack.
 259   void Poke(int depth, Node* node) {
 260     DCHECK(depth >= 0 && depth < stack_height());
 261     int index = static_cast<int>(values()->size()) - depth - 1;
 262     values()->at(index) = node;
 263   }
 264   Node* Peek(int depth) {
 265     DCHECK(depth >= 0 && depth < stack_height());
 266     int index = static_cast<int>(values()->size()) - depth - 1;
 267     return values()->at(index);
 268   }
 269   void Drop(int depth) {
 270     DCHECK(depth >= 0 && depth <= stack_height());
 271     values()->erase(values()->end() - depth, values()->end());
 272   }
 273
 274   // Preserve a checkpoint of the environment for the IR graph. Any
 275   // further mutation of the environment will not affect checkpoints.
 276   Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine);
 277
 278  protected:
 279   AstGraphBuilder* builder() const {
 280     return reinterpret_cast<AstGraphBuilder*>(
 281         StructuredGraphBuilder::Environment::builder());
 282   }
 283
 284  private:
 285   void UpdateStateValues(Node** state_values, int offset, int count);
 286
 287   int parameters_count_;
 288   int locals_count_;
 289   Node* parameters_node_;
 290   Node* locals_node_;
 291   Node* stack_node_;
 292 };
 293
 294
 295 // Each expression in the AST is evaluated in a specific context. This context
 296 // decides how the evaluation result is passed up the visitor.
 297 class AstGraphBuilder::AstContext BASE_EMBEDDED {
 298  public:
 299   bool IsEffect() const { return kind_ == Expression::kEffect; }
 300   bool IsValue() const { return kind_ == Expression::kValue; }
 301   bool IsTest() const { return kind_ == Expression::kTest; }
 302
 303   // Determines how to combine the frame state with the value
 304   // that is about to be plugged into this AstContext.
 305   OutputFrameStateCombine GetStateCombine() {
 306     return IsEffect() ? OutputFrameStateCombine::Ignore()
 307                       : OutputFrameStateCombine::Push();
 308   }
 309
 310   // Plug a node into this expression context.  Call this function in tail
 311   // position in the Visit functions for expressions.
 312   virtual void ProduceValue(Node* value) = 0;
 313
 314   // Unplugs a node from this expression context.  Call this to retrieve the
 315   // result of another Visit function that already plugged the context.
 316   virtual Node* ConsumeValue() = 0;
 317
 318   // Shortcut for "context->ProduceValue(context->ConsumeValue())".
 319   void ReplaceValue() { ProduceValue(ConsumeValue()); }
 320
 321  protected:
 322   AstContext(AstGraphBuilder* owner, Expression::Context kind);
 323   virtual ~AstContext();
 324
 325   AstGraphBuilder* owner() const { return owner_; }
 326   Environment* environment() const { return owner_->environment(); }
 327
 328 // We want to be able to assert, in a context-specific way, that the stack
 329 // height makes sense when the context is filled.
 330 #ifdef DEBUG
 331   int original_height_;
 332 #endif
 333
 334  private:
 335   Expression::Context kind_;
 336   AstGraphBuilder* owner_;
 337   AstContext* outer_;
 338 };
 339
 340
 341 // Context to evaluate expression for its side effects only.
 342 class AstGraphBuilder::AstEffectContext FINAL : public AstContext {
 343  public:
 344   explicit AstEffectContext(AstGraphBuilder* owner)
 345       : AstContext(owner, Expression::kEffect) {}
 346   virtual ~AstEffectContext();
 347   virtual void ProduceValue(Node* value) OVERRIDE;
 348   virtual Node* ConsumeValue() OVERRIDE;
 349 };
 350
 351
 352 // Context to evaluate expression for its value (and side effects).
 353 class AstGraphBuilder::AstValueContext FINAL : public AstContext {
 354  public:
 355   explicit AstValueContext(AstGraphBuilder* owner)
 356       : AstContext(owner, Expression::kValue) {}
 357   virtual ~AstValueContext();
 358   virtual void ProduceValue(Node* value) OVERRIDE;
 359   virtual Node* ConsumeValue() OVERRIDE;
 360 };
 361
 362
 363 // Context to evaluate expression for a condition value (and side effects).
 364 class AstGraphBuilder::AstTestContext FINAL : public AstContext {
 365  public:
 366   explicit AstTestContext(AstGraphBuilder* owner)
 367       : AstContext(owner, Expression::kTest) {}
 368   virtual ~AstTestContext();
 369   virtual void ProduceValue(Node* value) OVERRIDE;
 370   virtual Node* ConsumeValue() OVERRIDE;
 371 };
 372
 373
 374 // Scoped class tracking breakable statements entered by the visitor. Allows to
 375 // properly 'break' and 'continue' iteration statements as well as to 'break'
 376 // from blocks within switch statements.
 377 class AstGraphBuilder::BreakableScope BASE_EMBEDDED {
 378  public:
 379   BreakableScope(AstGraphBuilder* owner, BreakableStatement* target,
 380                  ControlBuilder* control, int drop_extra)
 381       : owner_(owner),
 382         target_(target),
 383         next_(owner->breakable()),
 384         control_(control),
 385         drop_extra_(drop_extra) {
 386     owner_->set_breakable(this);  // Push.
 387   }
 388
 389   ~BreakableScope() {
 390     owner_->set_breakable(next_);  // Pop.
 391   }
 392
 393   // Either 'break' or 'continue' the target statement.
 394   void BreakTarget(BreakableStatement* target);
 395   void ContinueTarget(BreakableStatement* target);
 396
 397  private:
 398   AstGraphBuilder* owner_;
 399   BreakableStatement* target_;
 400   BreakableScope* next_;
 401   ControlBuilder* control_;
 402   int drop_extra_;
 403
 404   // Find the correct scope for the target statement. Note that this also drops
 405   // extra operands from the environment for each scope skipped along the way.
 406   BreakableScope* FindBreakable(BreakableStatement* target);
 407 };
 408
 409
 410 // Scoped class tracking context objects created by the visitor. Represents
 411 // mutations of the context chain within the function body and allows to
 412 // change the current {scope} and {context} during visitation.
 413 class AstGraphBuilder::ContextScope BASE_EMBEDDED {
 414  public:
 415   ContextScope(AstGraphBuilder* owner, Scope* scope, Node* context)
 416       : owner_(owner),
 417         next_(owner->execution_context()),
 418         outer_(owner->current_context()),
 419         scope_(scope) {
 420     owner_->set_execution_context(this);  // Push.
 421     owner_->set_current_context(context);
 422   }
 423
 424   ~ContextScope() {
 425     owner_->set_execution_context(next_);  // Pop.
 426     owner_->set_current_context(outer_);
 427   }
 428
 429   // Current scope during visitation.
 430   Scope* scope() const { return scope_; }
 431
 432  private:
 433   AstGraphBuilder* owner_;
 434   ContextScope* next_;
 435   Node* outer_;
 436   Scope* scope_;
 437 };
 438
 439 Scope* AstGraphBuilder::current_scope() const {
 440   return execution_context_->scope();
 441 }
 442
 443 }  // namespace compiler
 444 }  // namespace internal
 445 }  // namespace v8
 446
 447 #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_