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   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_