deps/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/ast.h"
   9 #include "src/compiler/js-graph.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13
  14 class BitVector;
  15
  16 namespace compiler {
  17
  18 class ControlBuilder;
  19 class Graph;
  20 class LoopAssignmentAnalysis;
  21 class LoopBuilder;
  22 class Node;
  23
  24 // The AstGraphBuilder produces a high-level IR graph, based on an
  25 // underlying AST. The produced graph can either be compiled into a
  26 // stand-alone function or be wired into another graph for the purposes
  27 // of function inlining.
  28 class AstGraphBuilder : public AstVisitor {
  29  public:
  30   AstGraphBuilder(Zone* local_zone, CompilationInfo* info, JSGraph* jsgraph,
  31                   LoopAssignmentAnalysis* loop_assignment = NULL);
  32
  33   // Creates a graph by visiting the entire AST.
  34   bool CreateGraph(bool constant_context);
  35
  36   // Helpers to create new control nodes.
  37   Node* NewIfTrue() { return NewNode(common()->IfTrue()); }
  38   Node* NewIfFalse() { return NewNode(common()->IfFalse()); }
  39   Node* NewMerge() { return NewNode(common()->Merge(1), true); }
  40   Node* NewLoop() { return NewNode(common()->Loop(1), true); }
  41   Node* NewBranch(Node* condition, BranchHint hint = BranchHint::kNone) {
  42     return NewNode(common()->Branch(hint), condition);
  43   }
  44
  45  protected:
  46 #define DECLARE_VISIT(type) void Visit##type(type* node) OVERRIDE;
  47   // Visiting functions for AST nodes make this an AstVisitor.
  48   AST_NODE_LIST(DECLARE_VISIT)
  49 #undef DECLARE_VISIT
  50
  51   // Visiting function for declarations list is overridden.
  52   void VisitDeclarations(ZoneList<Declaration*>* declarations) OVERRIDE;
  53
  54  private:
  55   class AstContext;
  56   class AstEffectContext;
  57   class AstValueContext;
  58   class AstTestContext;
  59   class ContextScope;
  60   class ControlScope;
  61   class ControlScopeForBreakable;
  62   class ControlScopeForIteration;
  63   class ControlScopeForCatch;
  64   class ControlScopeForFinally;
  65   class Environment;
  66   friend class ControlBuilder;
  67
  68   Zone* local_zone_;
  69   CompilationInfo* info_;
  70   JSGraph* jsgraph_;
  71   Environment* environment_;
  72   AstContext* ast_context_;
  73
  74   // List of global declarations for functions and variables.
  75   ZoneVector<Handle<Object>> globals_;
  76
  77   // Stack of control scopes currently entered by the visitor.
  78   ControlScope* execution_control_;
  79
  80   // Stack of context objects pushed onto the chain by the visitor.
  81   ContextScope* execution_context_;
  82
  83   // Nodes representing values in the activation record.
  84   SetOncePointer<Node> function_closure_;
  85   SetOncePointer<Node> function_context_;
  86
  87   // Temporary storage for building node input lists.
  88   int input_buffer_size_;
  89   Node** input_buffer_;
  90
  91   // Merge of all control nodes that exit the function body.
  92   Node* exit_control_;
  93
  94   // Result of loop assignment analysis performed before graph creation.
  95   LoopAssignmentAnalysis* loop_assignment_analysis_;
  96
  97   // Growth increment for the temporary buffer used to construct input lists to
  98   // new nodes.
  99   static const int kInputBufferSizeIncrement = 64;
 100
 101   Zone* local_zone() const { return local_zone_; }
 102   Environment* environment() const { return environment_; }
 103   AstContext* ast_context() const { return ast_context_; }
 104   ControlScope* execution_control() const { return execution_control_; }
 105   ContextScope* execution_context() const { return execution_context_; }
 106   CommonOperatorBuilder* common() const { return jsgraph_->common(); }
 107   CompilationInfo* info() const { return info_; }
 108   LanguageMode language_mode() const;
 109   JSGraph* jsgraph() { return jsgraph_; }
 110   Graph* graph() { return jsgraph_->graph(); }
 111   Zone* graph_zone() { return graph()->zone(); }
 112   JSOperatorBuilder* javascript() { return jsgraph_->javascript(); }
 113   ZoneVector<Handle<Object>>* globals() { return &globals_; }
 114   Scope* current_scope() const;
 115   Node* current_context() const;
 116   Node* exit_control() const { return exit_control_; }
 117
 118   void set_environment(Environment* env) { environment_ = env; }
 119   void set_ast_context(AstContext* ctx) { ast_context_ = ctx; }
 120   void set_execution_control(ControlScope* ctrl) { execution_control_ = ctrl; }
 121   void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; }
 122   void set_exit_control(Node* exit) { exit_control_ = exit; }
 123
 124   // Create the main graph body by visiting the AST.
 125   void CreateGraphBody();
 126
 127   // Create the node that represents the outer context of the function.
 128   void CreateFunctionContext(bool constant_context);
 129
 130   // Get or create the node that represents the outer function closure.
 131   Node* GetFunctionClosure();
 132
 133   // Node creation helpers.
 134   Node* NewNode(const Operator* op, bool incomplete = false) {
 135     return MakeNode(op, 0, static_cast<Node**>(NULL), incomplete);
 136   }
 137
 138   Node* NewNode(const Operator* op, Node* n1) {
 139     return MakeNode(op, 1, &n1, false);
 140   }
 141
 142   Node* NewNode(const Operator* op, Node* n1, Node* n2) {
 143     Node* buffer[] = {n1, n2};
 144     return MakeNode(op, arraysize(buffer), buffer, false);
 145   }
 146
 147   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) {
 148     Node* buffer[] = {n1, n2, n3};
 149     return MakeNode(op, arraysize(buffer), buffer, false);
 150   }
 151
 152   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) {
 153     Node* buffer[] = {n1, n2, n3, n4};
 154     return MakeNode(op, arraysize(buffer), buffer, false);
 155   }
 156
 157   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
 158                 Node* n5) {
 159     Node* buffer[] = {n1, n2, n3, n4, n5};
 160     return MakeNode(op, arraysize(buffer), buffer, false);
 161   }
 162
 163   Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
 164                 Node* n5, Node* n6) {
 165     Node* nodes[] = {n1, n2, n3, n4, n5, n6};
 166     return MakeNode(op, arraysize(nodes), nodes, false);
 167   }
 168
 169   Node* NewNode(const Operator* op, int value_input_count, Node** value_inputs,
 170                 bool incomplete = false) {
 171     return MakeNode(op, value_input_count, value_inputs, incomplete);
 172   }
 173
 174   // Creates a new Phi node having {count} input values.
 175   Node* NewPhi(int count, Node* input, Node* control);
 176   Node* NewEffectPhi(int count, Node* input, Node* control);
 177
 178   Node* NewOuterContextParam();
 179   Node* NewCurrentContextOsrValue();
 180
 181   // Helpers for merging control, effect or value dependencies.
 182   Node* MergeControl(Node* control, Node* other);
 183   Node* MergeEffect(Node* value, Node* other, Node* control);
 184   Node* MergeValue(Node* value, Node* other, Node* control);
 185
 186   // The main node creation chokepoint. Adds context, frame state, effect,
 187   // and control dependencies depending on the operator.
 188   Node* MakeNode(const Operator* op, int value_input_count, Node** value_inputs,
 189                  bool incomplete);
 190
 191   // Helper to indicate a node exits the function body.
 192   void UpdateControlDependencyToLeaveFunction(Node* exit);
 193
 194   //
 195   // The following build methods all generate graph fragments and return one
 196   // resulting node. The operand stack height remains the same, variables and
 197   // other dependencies tracked by the environment might be mutated though.
 198   //
 199
 200   // Builder to create a receiver check for sloppy mode.
 201   Node* BuildPatchReceiverToGlobalProxy(Node* receiver);
 202
 203   // Builders to create local function and block contexts.
 204   Node* BuildLocalFunctionContext(Node* context, Node* closure);
 205   Node* BuildLocalBlockContext(Scope* scope);
 206
 207   // Builder to create an arguments object if it is used.
 208   Node* BuildArgumentsObject(Variable* arguments);
 209
 210   // Builder to create an array of rest parameters if used
 211   Node* BuildRestArgumentsArray(Variable* rest, int index);
 212
 213   // Builders for variable load and assignment.
 214   Node* BuildVariableAssignment(Variable* var, Node* value, Token::Value op,
 215                                 BailoutId bailout_id,
 216                                 OutputFrameStateCombine state_combine =
 217                                     OutputFrameStateCombine::Ignore());
 218   Node* BuildVariableDelete(Variable* var, BailoutId bailout_id,
 219                             OutputFrameStateCombine state_combine);
 220   Node* BuildVariableLoad(Variable* var, BailoutId bailout_id,
 221                           const VectorSlotPair& feedback,
 222                           ContextualMode mode = CONTEXTUAL);
 223
 224   // Builders for accessing the function context.
 225   Node* BuildLoadBuiltinsObject();
 226   Node* BuildLoadGlobalObject();
 227   Node* BuildLoadGlobalProxy();
 228   Node* BuildLoadClosure();
 229   Node* BuildLoadObjectField(Node* object, int offset);
 230
 231   // Builders for automatic type conversion.
 232   Node* BuildToBoolean(Node* value);
 233   Node* BuildToName(Node* value, BailoutId bailout_id);
 234
 235   // Builder for adding the [[HomeObject]] to a value if the value came from a
 236   // function literal and needs a home object. Do nothing otherwise.
 237   Node* BuildSetHomeObject(Node* value, Node* home_object, Expression* expr);
 238
 239   // Builders for error reporting at runtime.
 240   Node* BuildThrowReferenceError(Variable* var, BailoutId bailout_id);
 241   Node* BuildThrowConstAssignError(BailoutId bailout_id);
 242
 243   // Builders for dynamic hole-checks at runtime.
 244   Node* BuildHoleCheckSilent(Node* value, Node* for_hole, Node* not_hole);
 245   Node* BuildHoleCheckThrow(Node* value, Variable* var, Node* not_hole,
 246                             BailoutId bailout_id);
 247
 248   // Builders for non-local control flow.
 249   Node* BuildReturn(Node* return_value);
 250   Node* BuildThrow(Node* exception_value);
 251
 252   // Builders for binary operations.
 253   Node* BuildBinaryOp(Node* left, Node* right, Token::Value op);
 254
 255   // Builder for stack-check guards.
 256   Node* BuildStackCheck();
 257
 258   // Check if the given statement is an OSR entry.
 259   // If so, record the stack height into the compilation and return {true}.
 260   bool CheckOsrEntry(IterationStatement* stmt);
 261
 262   // Helper to wrap a Handle<T> into a Unique<T>.
 263   template <class T>
 264   Unique<T> MakeUnique(Handle<T> object) {
 265     return Unique<T>::CreateUninitialized(object);
 266   }
 267
 268   Node** EnsureInputBufferSize(int size);
 269
 270   // Named and keyed loads require a VectorSlotPair for successful lowering.
 271   VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const;
 272
 273   // Process arguments to a call by popping {arity} elements off the operand
 274   // stack and build a call node using the given call operator.
 275   Node* ProcessArguments(const Operator* op, int arity);
 276
 277   // Visit statements.
 278   void VisitIfNotNull(Statement* stmt);
 279
 280   // Visit expressions.
 281   void Visit(Expression* expr);
 282   void VisitForTest(Expression* expr);
 283   void VisitForEffect(Expression* expr);
 284   void VisitForValue(Expression* expr);
 285   void VisitForValueOrNull(Expression* expr);
 286   void VisitForValueOrTheHole(Expression* expr);
 287   void VisitForValues(ZoneList<Expression*>* exprs);
 288
 289   // Common for all IterationStatement bodies.
 290   void VisitIterationBody(IterationStatement* stmt, LoopBuilder* loop, int);
 291
 292   // Dispatched from VisitCallRuntime.
 293   void VisitCallJSRuntime(CallRuntime* expr);
 294
 295   // Dispatched from VisitUnaryOperation.
 296   void VisitDelete(UnaryOperation* expr);
 297   void VisitVoid(UnaryOperation* expr);
 298   void VisitTypeof(UnaryOperation* expr);
 299   void VisitNot(UnaryOperation* expr);
 300
 301   // Dispatched from VisitBinaryOperation.
 302   void VisitComma(BinaryOperation* expr);
 303   void VisitLogicalExpression(BinaryOperation* expr);
 304   void VisitArithmeticExpression(BinaryOperation* expr);
 305
 306   // Dispatched from VisitForInStatement.
 307   void VisitForInAssignment(Expression* expr, Node* value,
 308                             BailoutId bailout_id);
 309   void VisitForInBody(ForInStatement* stmt);
 310
 311   // Dispatched from VisitClassLiteral.
 312   void VisitClassLiteralContents(ClassLiteral* expr);
 313
 314   // Builds deoptimization for a given node.
 315   void PrepareFrameState(
 316       Node* node, BailoutId ast_id,
 317       OutputFrameStateCombine combine = OutputFrameStateCombine::Ignore());
 318
 319   BitVector* GetVariablesAssignedInLoop(IterationStatement* stmt);
 320
 321   DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
 322   DISALLOW_COPY_AND_ASSIGN(AstGraphBuilder);
 323 };
 324
 325
 326 // The abstract execution environment for generated code consists of
 327 // parameter variables, local variables and the operand stack. The
 328 // environment will perform proper SSA-renaming of all tracked nodes
 329 // at split and merge points in the control flow. Internally all the
 330 // values are stored in one list using the following layout:
 331 //
 332 //  [parameters (+receiver)] [locals] [operand stack]
 333 //
 334 class AstGraphBuilder::Environment : public ZoneObject {
 335  public:
 336   Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency);
 337
 338   int parameters_count() const { return parameters_count_; }
 339   int locals_count() const { return locals_count_; }
 340   int stack_height() {
 341     return static_cast<int>(values()->size()) - parameters_count_ -
 342            locals_count_;
 343   }
 344
 345   // Operations on parameter or local variables. The parameter indices are
 346   // shifted by 1 (receiver is parameter index -1 but environment index 0).
 347   void Bind(Variable* variable, Node* node) {
 348     DCHECK(variable->IsStackAllocated());
 349     if (variable->IsParameter()) {
 350       values()->at(variable->index() + 1) = node;
 351     } else {
 352       DCHECK(variable->IsStackLocal());
 353       values()->at(variable->index() + parameters_count_) = node;
 354     }
 355   }
 356   Node* Lookup(Variable* variable) {
 357     DCHECK(variable->IsStackAllocated());
 358     if (variable->IsParameter()) {
 359       return values()->at(variable->index() + 1);
 360     } else {
 361       DCHECK(variable->IsStackLocal());
 362       return values()->at(variable->index() + parameters_count_);
 363     }
 364   }
 365
 366   Node* Context() const { return contexts_.back(); }
 367   void PushContext(Node* context) { contexts()->push_back(context); }
 368   void PopContext() { contexts()->pop_back(); }
 369
 370   // Operations on the operand stack.
 371   void Push(Node* node) {
 372     values()->push_back(node);
 373   }
 374   Node* Top() {
 375     DCHECK(stack_height() > 0);
 376     return values()->back();
 377   }
 378   Node* Pop() {
 379     DCHECK(stack_height() > 0);
 380     Node* back = values()->back();
 381     values()->pop_back();
 382     return back;
 383   }
 384
 385   // Direct mutations of the operand stack.
 386   void Poke(int depth, Node* node) {
 387     DCHECK(depth >= 0 && depth < stack_height());
 388     int index = static_cast<int>(values()->size()) - depth - 1;
 389     values()->at(index) = node;
 390   }
 391   Node* Peek(int depth) {
 392     DCHECK(depth >= 0 && depth < stack_height());
 393     int index = static_cast<int>(values()->size()) - depth - 1;
 394     return values()->at(index);
 395   }
 396   void Drop(int depth) {
 397     DCHECK(depth >= 0 && depth <= stack_height());
 398     values()->erase(values()->end() - depth, values()->end());
 399   }
 400
 401   // Preserve a checkpoint of the environment for the IR graph. Any
 402   // further mutation of the environment will not affect checkpoints.
 403   Node* Checkpoint(BailoutId ast_id, OutputFrameStateCombine combine);
 404
 405   // Control dependency tracked by this environment.
 406   Node* GetControlDependency() { return control_dependency_; }
 407   void UpdateControlDependency(Node* dependency) {
 408     control_dependency_ = dependency;
 409   }
 410
 411   // Effect dependency tracked by this environment.
 412   Node* GetEffectDependency() { return effect_dependency_; }
 413   void UpdateEffectDependency(Node* dependency) {
 414     effect_dependency_ = dependency;
 415   }
 416
 417   // Mark this environment as being unreachable.
 418   void MarkAsUnreachable() {
 419     UpdateControlDependency(builder()->jsgraph()->DeadControl());
 420   }
 421   bool IsMarkedAsUnreachable() {
 422     return GetControlDependency()->opcode() == IrOpcode::kDead;
 423   }
 424
 425   // Merge another environment into this one.
 426   void Merge(Environment* other);
 427
 428   // Copies this environment at a control-flow split point.
 429   Environment* CopyForConditional() { return Copy(); }
 430
 431   // Copies this environment to a potentially unreachable control-flow point.
 432   Environment* CopyAsUnreachable() {
 433     Environment* env = Copy();
 434     env->MarkAsUnreachable();
 435     return env;
 436   }
 437
 438   // Copies this environment at a loop header control-flow point.
 439   Environment* CopyForLoop(BitVector* assigned, bool is_osr = false) {
 440     PrepareForLoop(assigned, is_osr);
 441     return Copy();
 442   }
 443
 444   int ContextStackDepth() { return static_cast<int>(contexts_.size()); }
 445
 446  private:
 447   AstGraphBuilder* builder_;
 448   int parameters_count_;
 449   int locals_count_;
 450   NodeVector values_;
 451   NodeVector contexts_;
 452   Node* control_dependency_;
 453   Node* effect_dependency_;
 454   Node* parameters_node_;
 455   Node* locals_node_;
 456   Node* stack_node_;
 457
 458   explicit Environment(const Environment* copy);
 459   Environment* Copy() { return new (zone()) Environment(this); }
 460   void UpdateStateValues(Node** state_values, int offset, int count);
 461   Zone* zone() const { return builder_->local_zone(); }
 462   Graph* graph() const { return builder_->graph(); }
 463   AstGraphBuilder* builder() const { return builder_; }
 464   CommonOperatorBuilder* common() { return builder_->common(); }
 465   NodeVector* values() { return &values_; }
 466   NodeVector* contexts() { return &contexts_; }
 467
 468   // Prepare environment to be used as loop header.
 469   void PrepareForLoop(BitVector* assigned, bool is_osr = false);
 470 };
 471
 472 }  // namespace compiler
 473 }  // namespace internal
 474 }  // namespace v8
 475
 476 #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_