ast-numbering.cc 17.5 KB
Newer Older
1 2 3 4
// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/ast/ast-numbering.h"
6

7 8
#include "src/ast/ast.h"
#include "src/ast/scopes.h"
9 10 11 12

namespace v8 {
namespace internal {

13
class AstNumberingVisitor final : public AstVisitor<AstNumberingVisitor> {
14
 public:
15
  AstNumberingVisitor(Isolate* isolate, Zone* zone)
16
      : isolate_(isolate),
17
        zone_(zone),
18
        next_id_(BailoutId::FirstUsable().ToInt()),
19
        yield_count_(0),
20
        properties_(zone),
21
        slot_cache_(zone),
22
        dont_optimize_reason_(kNoReason),
23
        catch_prediction_(HandlerTable::UNCAUGHT) {
24
    InitializeAstVisitor(isolate);
25 26
  }

27
  bool Renumber(FunctionLiteral* node);
28 29 30

 private:
// AST node visitor interface.
31
#define DEFINE_VISIT(type) void Visit##type(type* node);
32 33 34
  AST_NODE_LIST(DEFINE_VISIT)
#undef DEFINE_VISIT

35 36 37 38
  void VisitVariableProxyReference(VariableProxy* node);
  void VisitPropertyReference(Property* node);
  void VisitReference(Expression* expr);

39 40
  void VisitStatements(ZoneList<Statement*>* statements);
  void VisitDeclarations(ZoneList<Declaration*>* declarations);
41 42 43 44 45 46 47 48 49
  void VisitArguments(ZoneList<Expression*>* arguments);
  void VisitObjectLiteralProperty(ObjectLiteralProperty* property);

  int ReserveIdRange(int n) {
    int tmp = next_id_;
    next_id_ += n;
    return tmp;
  }

50
  void IncrementNodeCount() { properties_.add_node_count(1); }
51
  void DisableSelfOptimization() {
52
    properties_.flags() |= AstProperties::kDontSelfOptimize;
53
  }
54 55 56 57
  void DisableOptimization(BailoutReason reason) {
    dont_optimize_reason_ = reason;
    DisableSelfOptimization();
  }
58
  void DisableCrankshaft(BailoutReason reason) {
59
    properties_.flags() |= AstProperties::kDontCrankshaft;
60
  }
61

62 63
  template <typename Node>
  void ReserveFeedbackSlots(Node* node) {
64
    node->AssignFeedbackVectorSlots(isolate_, properties_.get_spec(),
65
                                    &slot_cache_);
66 67
  }

68
  BailoutReason dont_optimize_reason() const { return dont_optimize_reason_; }
69

70
  Isolate* isolate_;
71
  Zone* zone_;
72
  int next_id_;
73
  int yield_count_;
74
  AstProperties properties_;
75 76
  // The slot cache allows us to reuse certain feedback vector slots.
  FeedbackVectorSlotCache slot_cache_;
77
  BailoutReason dont_optimize_reason_;
78
  HandlerTable::CatchPrediction catch_prediction_;
79 80 81 82 83 84 85

  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
  DISALLOW_COPY_AND_ASSIGN(AstNumberingVisitor);
};


void AstNumberingVisitor::VisitVariableDeclaration(VariableDeclaration* node) {
86
  IncrementNodeCount();
87 88 89 90
  VisitVariableProxy(node->proxy());
}


91 92 93
void AstNumberingVisitor::VisitEmptyStatement(EmptyStatement* node) {
  IncrementNodeCount();
}
94 95


96 97 98 99 100 101 102
void AstNumberingVisitor::VisitSloppyBlockFunctionStatement(
    SloppyBlockFunctionStatement* node) {
  IncrementNodeCount();
  Visit(node->statement());
}


103 104 105
void AstNumberingVisitor::VisitContinueStatement(ContinueStatement* node) {
  IncrementNodeCount();
}
106 107


108 109 110
void AstNumberingVisitor::VisitBreakStatement(BreakStatement* node) {
  IncrementNodeCount();
}
111 112 113


void AstNumberingVisitor::VisitDebuggerStatement(DebuggerStatement* node) {
114
  IncrementNodeCount();
115
  DisableOptimization(kDebuggerStatement);
116 117 118 119 120 121
  node->set_base_id(ReserveIdRange(DebuggerStatement::num_ids()));
}


void AstNumberingVisitor::VisitNativeFunctionLiteral(
    NativeFunctionLiteral* node) {
122
  IncrementNodeCount();
123
  DisableOptimization(kNativeFunctionLiteral);
124 125 126 127
  node->set_base_id(ReserveIdRange(NativeFunctionLiteral::num_ids()));
}


128 129 130 131 132 133 134 135
void AstNumberingVisitor::VisitDoExpression(DoExpression* node) {
  IncrementNodeCount();
  node->set_base_id(ReserveIdRange(DoExpression::num_ids()));
  Visit(node->block());
  Visit(node->result());
}


136
void AstNumberingVisitor::VisitLiteral(Literal* node) {
137
  IncrementNodeCount();
138 139 140 141 142
  node->set_base_id(ReserveIdRange(Literal::num_ids()));
}


void AstNumberingVisitor::VisitRegExpLiteral(RegExpLiteral* node) {
143
  IncrementNodeCount();
144 145 146 147
  node->set_base_id(ReserveIdRange(RegExpLiteral::num_ids()));
}


148
void AstNumberingVisitor::VisitVariableProxyReference(VariableProxy* node) {
149
  IncrementNodeCount();
150
  if (node->var()->IsLookupSlot()) {
151
    DisableCrankshaft(kReferenceToAVariableWhichRequiresDynamicLookup);
152
  }
153 154 155 156
  node->set_base_id(ReserveIdRange(VariableProxy::num_ids()));
}


157 158 159 160 161 162
void AstNumberingVisitor::VisitVariableProxy(VariableProxy* node) {
  VisitVariableProxyReference(node);
  ReserveFeedbackSlots(node);
}


163
void AstNumberingVisitor::VisitThisFunction(ThisFunction* node) {
164
  IncrementNodeCount();
165 166 167 168
  node->set_base_id(ReserveIdRange(ThisFunction::num_ids()));
}


169 170
void AstNumberingVisitor::VisitSuperPropertyReference(
    SuperPropertyReference* node) {
171
  IncrementNodeCount();
172
  DisableCrankshaft(kSuperReference);
173
  node->set_base_id(ReserveIdRange(SuperPropertyReference::num_ids()));
174
  Visit(node->this_var());
175
  Visit(node->home_object());
176 177 178
}


179 180
void AstNumberingVisitor::VisitSuperCallReference(SuperCallReference* node) {
  IncrementNodeCount();
181
  DisableCrankshaft(kSuperReference);
182 183 184 185 186 187 188
  node->set_base_id(ReserveIdRange(SuperCallReference::num_ids()));
  Visit(node->this_var());
  Visit(node->new_target_var());
  Visit(node->this_function_var());
}


189
void AstNumberingVisitor::VisitExpressionStatement(ExpressionStatement* node) {
190
  IncrementNodeCount();
191 192 193 194 195
  Visit(node->expression());
}


void AstNumberingVisitor::VisitReturnStatement(ReturnStatement* node) {
196
  IncrementNodeCount();
197 198 199 200 201
  Visit(node->expression());
}


void AstNumberingVisitor::VisitYield(Yield* node) {
202
  node->set_yield_id(yield_count_);
203
  yield_count_++;
204
  IncrementNodeCount();
205 206 207 208 209 210 211
  node->set_base_id(ReserveIdRange(Yield::num_ids()));
  Visit(node->generator_object());
  Visit(node->expression());
}


void AstNumberingVisitor::VisitThrow(Throw* node) {
212
  IncrementNodeCount();
213 214 215 216 217 218
  node->set_base_id(ReserveIdRange(Throw::num_ids()));
  Visit(node->exception());
}


void AstNumberingVisitor::VisitUnaryOperation(UnaryOperation* node) {
219
  IncrementNodeCount();
220 221 222 223 224 225
  node->set_base_id(ReserveIdRange(UnaryOperation::num_ids()));
  Visit(node->expression());
}


void AstNumberingVisitor::VisitCountOperation(CountOperation* node) {
226
  IncrementNodeCount();
227 228
  node->set_base_id(ReserveIdRange(CountOperation::num_ids()));
  Visit(node->expression());
229
  ReserveFeedbackSlots(node);
230 231 232 233
}


void AstNumberingVisitor::VisitBlock(Block* node) {
234
  IncrementNodeCount();
235
  node->set_base_id(ReserveIdRange(Block::num_ids()));
236 237 238 239 240 241 242 243

  if (FLAG_ignition && node->scope() != nullptr &&
      node->scope()->NeedsContext()) {
    // Create ScopeInfo while on the main thread to avoid allocation during
    // potentially concurrent bytecode generation.
    node->scope()->GetScopeInfo(isolate_);
  }

244 245 246 247 248 249
  if (node->scope() != NULL) VisitDeclarations(node->scope()->declarations());
  VisitStatements(node->statements());
}


void AstNumberingVisitor::VisitFunctionDeclaration(FunctionDeclaration* node) {
250
  IncrementNodeCount();
251 252 253 254 255 256
  VisitVariableProxy(node->proxy());
  VisitFunctionLiteral(node->fun());
}


void AstNumberingVisitor::VisitCallRuntime(CallRuntime* node) {
257
  IncrementNodeCount();
258 259 260 261 262 263
  node->set_base_id(ReserveIdRange(CallRuntime::num_ids()));
  VisitArguments(node->arguments());
}


void AstNumberingVisitor::VisitWithStatement(WithStatement* node) {
264
  IncrementNodeCount();
265
  DisableCrankshaft(kWithStatement);
266
  node->set_base_id(ReserveIdRange(WithStatement::num_ids()));
267 268 269 270 271 272
  Visit(node->expression());
  Visit(node->statement());
}


void AstNumberingVisitor::VisitDoWhileStatement(DoWhileStatement* node) {
273
  IncrementNodeCount();
274
  DisableSelfOptimization();
275
  node->set_base_id(ReserveIdRange(DoWhileStatement::num_ids()));
276
  node->set_first_yield_id(yield_count_);
277 278
  Visit(node->body());
  Visit(node->cond());
279
  node->set_yield_count(yield_count_ - node->first_yield_id());
280 281 282 283
}


void AstNumberingVisitor::VisitWhileStatement(WhileStatement* node) {
284
  IncrementNodeCount();
285
  DisableSelfOptimization();
286
  node->set_base_id(ReserveIdRange(WhileStatement::num_ids()));
287
  node->set_first_yield_id(yield_count_);
288 289
  Visit(node->cond());
  Visit(node->body());
290
  node->set_yield_count(yield_count_ - node->first_yield_id());
291 292 293 294
}


void AstNumberingVisitor::VisitTryCatchStatement(TryCatchStatement* node) {
295
  IncrementNodeCount();
296
  DisableCrankshaft(kTryCatchStatement);
297
  {
298 299 300 301 302 303 304 305
    const HandlerTable::CatchPrediction old_prediction = catch_prediction_;
    // This node uses its own prediction, unless it's "uncaught", in which case
    // we adopt the prediction of the outer try-block.
    HandlerTable::CatchPrediction catch_prediction = node->catch_prediction();
    if (catch_prediction != HandlerTable::UNCAUGHT) {
      catch_prediction_ = catch_prediction;
    }
    node->set_catch_prediction(catch_prediction_);
306
    Visit(node->try_block());
307
    catch_prediction_ = old_prediction;
308
  }
309 310 311 312 313
  Visit(node->catch_block());
}


void AstNumberingVisitor::VisitTryFinallyStatement(TryFinallyStatement* node) {
314
  IncrementNodeCount();
315
  DisableCrankshaft(kTryFinallyStatement);
316 317
  // We can't know whether the finally block will override ("catch") an
  // exception thrown in the try block, so we just adopt the outer prediction.
318
  node->set_catch_prediction(catch_prediction_);
319 320 321 322 323
  Visit(node->try_block());
  Visit(node->finally_block());
}


324
void AstNumberingVisitor::VisitPropertyReference(Property* node) {
325
  IncrementNodeCount();
326 327 328 329 330 331
  node->set_base_id(ReserveIdRange(Property::num_ids()));
  Visit(node->key());
  Visit(node->obj());
}


332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347
void AstNumberingVisitor::VisitReference(Expression* expr) {
  DCHECK(expr->IsProperty() || expr->IsVariableProxy());
  if (expr->IsProperty()) {
    VisitPropertyReference(expr->AsProperty());
  } else {
    VisitVariableProxyReference(expr->AsVariableProxy());
  }
}


void AstNumberingVisitor::VisitProperty(Property* node) {
  VisitPropertyReference(node);
  ReserveFeedbackSlots(node);
}


348
void AstNumberingVisitor::VisitAssignment(Assignment* node) {
349
  IncrementNodeCount();
350
  node->set_base_id(ReserveIdRange(Assignment::num_ids()));
351

352
  if (node->is_compound()) VisitBinaryOperation(node->binary_operation());
353
  VisitReference(node->target());
354
  Visit(node->value());
355
  ReserveFeedbackSlots(node);
356 357 358 359
}


void AstNumberingVisitor::VisitBinaryOperation(BinaryOperation* node) {
360
  IncrementNodeCount();
361 362 363
  node->set_base_id(ReserveIdRange(BinaryOperation::num_ids()));
  Visit(node->left());
  Visit(node->right());
364
  ReserveFeedbackSlots(node);
365 366 367 368
}


void AstNumberingVisitor::VisitCompareOperation(CompareOperation* node) {
369
  IncrementNodeCount();
370 371 372 373 374 375
  node->set_base_id(ReserveIdRange(CompareOperation::num_ids()));
  Visit(node->left());
  Visit(node->right());
}


376
void AstNumberingVisitor::VisitSpread(Spread* node) { UNREACHABLE(); }
377 378


379 380 381 382 383
void AstNumberingVisitor::VisitEmptyParentheses(EmptyParentheses* node) {
  UNREACHABLE();
}


384
void AstNumberingVisitor::VisitForInStatement(ForInStatement* node) {
385
  IncrementNodeCount();
386
  DisableSelfOptimization();
387
  node->set_base_id(ReserveIdRange(ForInStatement::num_ids()));
388
  Visit(node->enumerable());  // Not part of loop.
389
  node->set_first_yield_id(yield_count_);
390 391
  Visit(node->each());
  Visit(node->body());
392
  node->set_yield_count(yield_count_ - node->first_yield_id());
393
  ReserveFeedbackSlots(node);
394 395 396 397
}


void AstNumberingVisitor::VisitForOfStatement(ForOfStatement* node) {
398
  IncrementNodeCount();
399
  DisableCrankshaft(kForOfStatement);
400
  node->set_base_id(ReserveIdRange(ForOfStatement::num_ids()));
401
  Visit(node->assign_iterator());  // Not part of loop.
402
  node->set_first_yield_id(yield_count_);
403 404 405 406
  Visit(node->next_result());
  Visit(node->result_done());
  Visit(node->assign_each());
  Visit(node->body());
407
  node->set_yield_count(yield_count_ - node->first_yield_id());
408 409 410 411
}


void AstNumberingVisitor::VisitConditional(Conditional* node) {
412
  IncrementNodeCount();
413 414 415 416 417 418 419 420
  node->set_base_id(ReserveIdRange(Conditional::num_ids()));
  Visit(node->condition());
  Visit(node->then_expression());
  Visit(node->else_expression());
}


void AstNumberingVisitor::VisitIfStatement(IfStatement* node) {
421
  IncrementNodeCount();
422 423 424 425 426 427 428 429 430 431
  node->set_base_id(ReserveIdRange(IfStatement::num_ids()));
  Visit(node->condition());
  Visit(node->then_statement());
  if (node->HasElseStatement()) {
    Visit(node->else_statement());
  }
}


void AstNumberingVisitor::VisitSwitchStatement(SwitchStatement* node) {
432
  IncrementNodeCount();
433 434 435 436 437 438 439 440 441 442
  node->set_base_id(ReserveIdRange(SwitchStatement::num_ids()));
  Visit(node->tag());
  ZoneList<CaseClause*>* cases = node->cases();
  for (int i = 0; i < cases->length(); i++) {
    VisitCaseClause(cases->at(i));
  }
}


void AstNumberingVisitor::VisitCaseClause(CaseClause* node) {
443
  IncrementNodeCount();
444 445 446 447 448 449 450
  node->set_base_id(ReserveIdRange(CaseClause::num_ids()));
  if (!node->is_default()) Visit(node->label());
  VisitStatements(node->statements());
}


void AstNumberingVisitor::VisitForStatement(ForStatement* node) {
451
  IncrementNodeCount();
452
  DisableSelfOptimization();
453
  node->set_base_id(ReserveIdRange(ForStatement::num_ids()));
454
  if (node->init() != NULL) Visit(node->init());  // Not part of loop.
455
  node->set_first_yield_id(yield_count_);
456 457 458
  if (node->cond() != NULL) Visit(node->cond());
  if (node->next() != NULL) Visit(node->next());
  Visit(node->body());
459
  node->set_yield_count(yield_count_ - node->first_yield_id());
460 461 462 463
}


void AstNumberingVisitor::VisitClassLiteral(ClassLiteral* node) {
464
  IncrementNodeCount();
465
  DisableCrankshaft(kClassLiteral);
466
  node->set_base_id(ReserveIdRange(node->num_ids()));
467 468
  if (node->extends()) Visit(node->extends());
  if (node->constructor()) Visit(node->constructor());
469 470 471
  if (node->class_variable_proxy()) {
    VisitVariableProxy(node->class_variable_proxy());
  }
472 473 474
  for (int i = 0; i < node->properties()->length(); i++) {
    VisitObjectLiteralProperty(node->properties()->at(i));
  }
475
  ReserveFeedbackSlots(node);
476 477 478 479
}


void AstNumberingVisitor::VisitObjectLiteral(ObjectLiteral* node) {
480
  IncrementNodeCount();
481
  node->set_base_id(ReserveIdRange(node->num_ids()));
482 483 484
  for (int i = 0; i < node->properties()->length(); i++) {
    VisitObjectLiteralProperty(node->properties()->at(i));
  }
485
  node->BuildConstantProperties(isolate_);
486 487 488
  // Mark all computed expressions that are bound to a key that
  // is shadowed by a later occurrence of the same key. For the
  // marked expressions, no store code will be is emitted.
489
  node->CalculateEmitStore(zone_);
490
  ReserveFeedbackSlots(node);
491 492 493 494 495
}


void AstNumberingVisitor::VisitObjectLiteralProperty(
    ObjectLiteralProperty* node) {
496
  if (node->is_computed_name()) DisableCrankshaft(kComputedPropertyName);
497 498 499 500 501 502
  Visit(node->key());
  Visit(node->value());
}


void AstNumberingVisitor::VisitArrayLiteral(ArrayLiteral* node) {
503
  IncrementNodeCount();
504 505 506 507
  node->set_base_id(ReserveIdRange(node->num_ids()));
  for (int i = 0; i < node->values()->length(); i++) {
    Visit(node->values()->at(i));
  }
508
  node->BuildConstantElements(isolate_);
509
  ReserveFeedbackSlots(node);
510 511 512 513
}


void AstNumberingVisitor::VisitCall(Call* node) {
514
  IncrementNodeCount();
515
  ReserveFeedbackSlots(node);
516 517 518 519 520 521 522
  node->set_base_id(ReserveIdRange(Call::num_ids()));
  Visit(node->expression());
  VisitArguments(node->arguments());
}


void AstNumberingVisitor::VisitCallNew(CallNew* node) {
523
  IncrementNodeCount();
524
  ReserveFeedbackSlots(node);
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
  node->set_base_id(ReserveIdRange(CallNew::num_ids()));
  Visit(node->expression());
  VisitArguments(node->arguments());
}


void AstNumberingVisitor::VisitStatements(ZoneList<Statement*>* statements) {
  if (statements == NULL) return;
  for (int i = 0; i < statements->length(); i++) {
    Visit(statements->at(i));
  }
}


void AstNumberingVisitor::VisitDeclarations(
    ZoneList<Declaration*>* declarations) {
  for (int i = 0; i < declarations->length(); i++) {
    Visit(declarations->at(i));
  }
}


void AstNumberingVisitor::VisitArguments(ZoneList<Expression*>* arguments) {
  for (int i = 0; i < arguments->length(); i++) {
    Visit(arguments->at(i));
  }
}


void AstNumberingVisitor::VisitFunctionLiteral(FunctionLiteral* node) {
555
  IncrementNodeCount();
556 557 558 559 560 561
  node->set_base_id(ReserveIdRange(FunctionLiteral::num_ids()));
  // We don't recurse into the declarations or body of the function literal:
  // you have to separately Renumber() each FunctionLiteral that you compile.
}


562 563
void AstNumberingVisitor::VisitRewritableExpression(
    RewritableExpression* node) {
564
  IncrementNodeCount();
565
  node->set_base_id(ReserveIdRange(RewritableExpression::num_ids()));
566 567 568 569
  Visit(node->expression());
}


570
bool AstNumberingVisitor::Renumber(FunctionLiteral* node) {
571
  DeclarationScope* scope = node->scope();
572
  if (scope->new_target_var()) DisableCrankshaft(kSuperReference);
573
  if (scope->calls_eval()) DisableOptimization(kFunctionCallsEval);
574
  if (scope->arguments() != NULL && !scope->arguments()->IsStackAllocated()) {
575
    DisableCrankshaft(kContextAllocatedArguments);
576 577
  }

578 579 580 581 582
  int rest_index;
  if (scope->rest_parameter(&rest_index)) {
    DisableCrankshaft(kRestParameter);
  }

583 584 585 586 587 588
  if (FLAG_ignition && scope->NeedsContext() && scope->is_script_scope()) {
    // Create ScopeInfo while on the main thread to avoid allocation during
    // potentially concurrent bytecode generation.
    node->scope()->GetScopeInfo(isolate_);
  }

589
  if (IsGeneratorFunction(node->kind()) || IsAsyncFunction(node->kind())) {
590 591 592
    // TODO(neis): We may want to allow Turbofan optimization here if
    // --turbo-from-bytecode is set and we know that Ignition is used.
    // Unfortunately we can't express that here.
593 594 595
    DisableOptimization(kGenerator);
  }

596 597
  VisitDeclarations(scope->declarations());
  VisitStatements(node->body());
598

599 600 601 602
  node->set_ast_properties(&properties_);
  node->set_dont_optimize_reason(dont_optimize_reason());
  node->set_yield_count(yield_count_);
  return !HasStackOverflow();
603 604 605
}


606 607 608
bool AstNumbering::Renumber(Isolate* isolate, Zone* zone,
                            FunctionLiteral* function) {
  AstNumberingVisitor visitor(isolate, zone);
609
  return visitor.Renumber(function);
610
}
611 612
}  // namespace internal
}  // namespace v8