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 14namespace v8 { 15namespace internal { 16namespace compiler { 17 18class ControlBuilder; 19class LoopBuilder; 20class 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. 26class 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// 194class 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. 282class 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. 326class 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). 337class 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). 348class 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. 361class 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. 397class 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 423Scope* 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_ 431