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