Home | History | Annotate | Download | only in ast 
      1 // Copyright 2012 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 #include "src/ast/ast-numbering.h"
      6 
      7 #include "src/ast/ast.h"
      8 #include "src/ast/scopes.h"
      9 
     10 namespace v8 {
     11 namespace internal {
     12 
     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  private:
     30 // AST node visitor interface.
     31 #define DEFINE_VISIT(type) void Visit##type(type* node);
     32   AST_NODE_LIST(DEFINE_VISIT)
     33 #undef DEFINE_VISIT
     34 
     35   void VisitVariableProxyReference(VariableProxy* node);
     36   void VisitPropertyReference(Property* node);
     37   void VisitReference(Expression* expr);
     38 
     39   void VisitStatements(ZoneList<Statement*>* statements);
     40   void VisitDeclarations(Declaration::List* declarations);
     41   void VisitArguments(ZoneList<Expression*>* arguments);
     42   void VisitLiteralProperty(LiteralProperty* property);
     43 
     44   int ReserveIdRange(int n) {
     45     int tmp = next_id_;
     46     next_id_ += n;
     47     return tmp;
     48   }
     49 
     50   void IncrementNodeCount() { properties_.add_node_count(1); }
     51   void DisableSelfOptimization() {
     52     properties_.flags() |= AstProperties::kDontSelfOptimize;
     53   }
     54   void DisableOptimization(BailoutReason reason) {
     55     dont_optimize_reason_ = reason;
     56     DisableSelfOptimization();
     57   }
     58   void DisableCrankshaft(BailoutReason reason) {
     59     properties_.flags() |= AstProperties::kDontCrankshaft;
     60   }
     61 
     62   template <typename Node>
     63   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   // The slot cache allows us to reuse certain feedback vector slots.
     76   FeedbackVectorSlotCache slot_cache_;
     77   BailoutReason dont_optimize_reason_;
     78   HandlerTable::CatchPrediction catch_prediction_;
     79 
     80   DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
     81   DISALLOW_COPY_AND_ASSIGN(AstNumberingVisitor);
     82 };
     83 
     84 
     85 void AstNumberingVisitor::VisitVariableDeclaration(VariableDeclaration* node) {
     86   IncrementNodeCount();
     87   VisitVariableProxy(node->proxy());
     88 }
     89 
     90 
     91 void AstNumberingVisitor::VisitEmptyStatement(EmptyStatement* node) {
     92   IncrementNodeCount();
     93 }
     94 
     95 
     96 void AstNumberingVisitor::VisitSloppyBlockFunctionStatement(
     97     SloppyBlockFunctionStatement* node) {
     98   IncrementNodeCount();
     99   Visit(node->statement());
    100 }
    101 
    102 
    103 void AstNumberingVisitor::VisitContinueStatement(ContinueStatement* node) {
    104   IncrementNodeCount();
    105 }
    106 
    107 
    108 void AstNumberingVisitor::VisitBreakStatement(BreakStatement* node) {
    109   IncrementNodeCount();
    110 }
    111 
    112 
    113 void AstNumberingVisitor::VisitDebuggerStatement(DebuggerStatement* node) {
    114   IncrementNodeCount();
    115   DisableOptimization(kDebuggerStatement);
    116   node->set_base_id(ReserveIdRange(DebuggerStatement::num_ids()));
    117 }
    118 
    119 
    120 void AstNumberingVisitor::VisitNativeFunctionLiteral(
    121     NativeFunctionLiteral* node) {
    122   IncrementNodeCount();
    123   DisableOptimization(kNativeFunctionLiteral);
    124   node->set_base_id(ReserveIdRange(NativeFunctionLiteral::num_ids()));
    125 }
    126 
    127 
    128 void AstNumberingVisitor::VisitDoExpression(DoExpression* node) {
    129   IncrementNodeCount();
    130   node->set_base_id(ReserveIdRange(DoExpression::num_ids()));
    131   Visit(node->block());
    132   Visit(node->result());
    133 }
    134 
    135 
    136 void AstNumberingVisitor::VisitLiteral(Literal* node) {
    137   IncrementNodeCount();
    138   node->set_base_id(ReserveIdRange(Literal::num_ids()));
    139 }
    140 
    141 
    142 void AstNumberingVisitor::VisitRegExpLiteral(RegExpLiteral* node) {
    143   IncrementNodeCount();
    144   node->set_base_id(ReserveIdRange(RegExpLiteral::num_ids()));
    145 }
    146 
    147 
    148 void AstNumberingVisitor::VisitVariableProxyReference(VariableProxy* node) {
    149   IncrementNodeCount();
    150   switch (node->var()->location()) {
    151     case VariableLocation::LOOKUP:
    152       DisableCrankshaft(kReferenceToAVariableWhichRequiresDynamicLookup);
    153       break;
    154     case VariableLocation::MODULE:
    155       DisableCrankshaft(kReferenceToModuleVariable);
    156       break;
    157     default:
    158       break;
    159   }
    160   node->set_base_id(ReserveIdRange(VariableProxy::num_ids()));
    161 }
    162 
    163 
    164 void AstNumberingVisitor::VisitVariableProxy(VariableProxy* node) {
    165   VisitVariableProxyReference(node);
    166   ReserveFeedbackSlots(node);
    167 }
    168 
    169 
    170 void AstNumberingVisitor::VisitThisFunction(ThisFunction* node) {
    171   IncrementNodeCount();
    172   node->set_base_id(ReserveIdRange(ThisFunction::num_ids()));
    173 }
    174 
    175 
    176 void AstNumberingVisitor::VisitSuperPropertyReference(
    177     SuperPropertyReference* node) {
    178   IncrementNodeCount();
    179   DisableCrankshaft(kSuperReference);
    180   node->set_base_id(ReserveIdRange(SuperPropertyReference::num_ids()));
    181   Visit(node->this_var());
    182   Visit(node->home_object());
    183 }
    184 
    185 
    186 void AstNumberingVisitor::VisitSuperCallReference(SuperCallReference* node) {
    187   IncrementNodeCount();
    188   DisableCrankshaft(kSuperReference);
    189   node->set_base_id(ReserveIdRange(SuperCallReference::num_ids()));
    190   Visit(node->this_var());
    191   Visit(node->new_target_var());
    192   Visit(node->this_function_var());
    193 }
    194 
    195 
    196 void AstNumberingVisitor::VisitExpressionStatement(ExpressionStatement* node) {
    197   IncrementNodeCount();
    198   Visit(node->expression());
    199 }
    200 
    201 
    202 void AstNumberingVisitor::VisitReturnStatement(ReturnStatement* node) {
    203   IncrementNodeCount();
    204   Visit(node->expression());
    205 }
    206 
    207 
    208 void AstNumberingVisitor::VisitYield(Yield* node) {
    209   node->set_yield_id(yield_count_);
    210   yield_count_++;
    211   IncrementNodeCount();
    212   node->set_base_id(ReserveIdRange(Yield::num_ids()));
    213   Visit(node->generator_object());
    214   Visit(node->expression());
    215 }
    216 
    217 
    218 void AstNumberingVisitor::VisitThrow(Throw* node) {
    219   IncrementNodeCount();
    220   node->set_base_id(ReserveIdRange(Throw::num_ids()));
    221   Visit(node->exception());
    222 }
    223 
    224 
    225 void AstNumberingVisitor::VisitUnaryOperation(UnaryOperation* node) {
    226   IncrementNodeCount();
    227   node->set_base_id(ReserveIdRange(UnaryOperation::num_ids()));
    228   Visit(node->expression());
    229 }
    230 
    231 
    232 void AstNumberingVisitor::VisitCountOperation(CountOperation* node) {
    233   IncrementNodeCount();
    234   node->set_base_id(ReserveIdRange(CountOperation::num_ids()));
    235   Visit(node->expression());
    236   ReserveFeedbackSlots(node);
    237 }
    238 
    239 
    240 void AstNumberingVisitor::VisitBlock(Block* node) {
    241   IncrementNodeCount();
    242   node->set_base_id(ReserveIdRange(Block::num_ids()));
    243   if (node->scope() != NULL) VisitDeclarations(node->scope()->declarations());
    244   VisitStatements(node->statements());
    245 }
    246 
    247 
    248 void AstNumberingVisitor::VisitFunctionDeclaration(FunctionDeclaration* node) {
    249   IncrementNodeCount();
    250   VisitVariableProxy(node->proxy());
    251   VisitFunctionLiteral(node->fun());
    252 }
    253 
    254 
    255 void AstNumberingVisitor::VisitCallRuntime(CallRuntime* node) {
    256   IncrementNodeCount();
    257   node->set_base_id(ReserveIdRange(CallRuntime::num_ids()));
    258   VisitArguments(node->arguments());
    259   // To support catch prediction within async/await:
    260   //
    261   // The AstNumberingVisitor is when catch prediction currently occurs, and it
    262   // is the only common point that has access to this information. The parser
    263   // just doesn't know yet. Take the following two cases of catch prediction:
    264   //
    265   // try { await fn(); } catch (e) { }
    266   // try { await fn(); } finally { }
    267   //
    268   // When parsing the await that we want to mark as caught or uncaught, it's
    269   // not yet known whether it will be followed by a 'finally' or a 'catch.
    270   // The AstNumberingVisitor is what learns whether it is caught. To make
    271   // the information available later to the runtime, the AstNumberingVisitor
    272   // has to stash it somewhere. Changing the runtime function into another
    273   // one in ast-numbering seemed like a simple and straightforward solution to
    274   // that problem.
    275   if (node->is_jsruntime() &&
    276       node->context_index() == Context::ASYNC_FUNCTION_AWAIT_CAUGHT_INDEX &&
    277       catch_prediction_ == HandlerTable::ASYNC_AWAIT) {
    278     node->set_context_index(Context::ASYNC_FUNCTION_AWAIT_UNCAUGHT_INDEX);
    279   }
    280 }
    281 
    282 
    283 void AstNumberingVisitor::VisitWithStatement(WithStatement* node) {
    284   IncrementNodeCount();
    285   DisableCrankshaft(kWithStatement);
    286   node->set_base_id(ReserveIdRange(WithStatement::num_ids()));
    287   Visit(node->expression());
    288   Visit(node->statement());
    289 }
    290 
    291 
    292 void AstNumberingVisitor::VisitDoWhileStatement(DoWhileStatement* node) {
    293   IncrementNodeCount();
    294   DisableSelfOptimization();
    295   node->set_base_id(ReserveIdRange(DoWhileStatement::num_ids()));
    296   node->set_first_yield_id(yield_count_);
    297   Visit(node->body());
    298   Visit(node->cond());
    299   node->set_yield_count(yield_count_ - node->first_yield_id());
    300 }
    301 
    302 
    303 void AstNumberingVisitor::VisitWhileStatement(WhileStatement* node) {
    304   IncrementNodeCount();
    305   DisableSelfOptimization();
    306   node->set_base_id(ReserveIdRange(WhileStatement::num_ids()));
    307   node->set_first_yield_id(yield_count_);
    308   Visit(node->cond());
    309   Visit(node->body());
    310   node->set_yield_count(yield_count_ - node->first_yield_id());
    311 }
    312 
    313 
    314 void AstNumberingVisitor::VisitTryCatchStatement(TryCatchStatement* node) {
    315   IncrementNodeCount();
    316   DisableCrankshaft(kTryCatchStatement);
    317   {
    318     const HandlerTable::CatchPrediction old_prediction = catch_prediction_;
    319     // This node uses its own prediction, unless it's "uncaught", in which case
    320     // we adopt the prediction of the outer try-block.
    321     HandlerTable::CatchPrediction catch_prediction = node->catch_prediction();
    322     if (catch_prediction != HandlerTable::UNCAUGHT) {
    323       catch_prediction_ = catch_prediction;
    324     }
    325     node->set_catch_prediction(catch_prediction_);
    326     Visit(node->try_block());
    327     catch_prediction_ = old_prediction;
    328   }
    329   Visit(node->catch_block());
    330 }
    331 
    332 
    333 void AstNumberingVisitor::VisitTryFinallyStatement(TryFinallyStatement* node) {
    334   IncrementNodeCount();
    335   DisableCrankshaft(kTryFinallyStatement);
    336   // We can't know whether the finally block will override ("catch") an
    337   // exception thrown in the try block, so we just adopt the outer prediction.
    338   node->set_catch_prediction(catch_prediction_);
    339   Visit(node->try_block());
    340   Visit(node->finally_block());
    341 }
    342 
    343 
    344 void AstNumberingVisitor::VisitPropertyReference(Property* node) {
    345   IncrementNodeCount();
    346   node->set_base_id(ReserveIdRange(Property::num_ids()));
    347   Visit(node->key());
    348   Visit(node->obj());
    349 }
    350 
    351 
    352 void AstNumberingVisitor::VisitReference(Expression* expr) {
    353   DCHECK(expr->IsProperty() || expr->IsVariableProxy());
    354   if (expr->IsProperty()) {
    355     VisitPropertyReference(expr->AsProperty());
    356   } else {
    357     VisitVariableProxyReference(expr->AsVariableProxy());
    358   }
    359 }
    360 
    361 
    362 void AstNumberingVisitor::VisitProperty(Property* node) {
    363   VisitPropertyReference(node);
    364   ReserveFeedbackSlots(node);
    365 }
    366 
    367 
    368 void AstNumberingVisitor::VisitAssignment(Assignment* node) {
    369   IncrementNodeCount();
    370   node->set_base_id(ReserveIdRange(Assignment::num_ids()));
    371 
    372   if (node->is_compound()) VisitBinaryOperation(node->binary_operation());
    373   VisitReference(node->target());
    374   Visit(node->value());
    375   ReserveFeedbackSlots(node);
    376 }
    377 
    378 
    379 void AstNumberingVisitor::VisitBinaryOperation(BinaryOperation* node) {
    380   IncrementNodeCount();
    381   node->set_base_id(ReserveIdRange(BinaryOperation::num_ids()));
    382   Visit(node->left());
    383   Visit(node->right());
    384   ReserveFeedbackSlots(node);
    385 }
    386 
    387 
    388 void AstNumberingVisitor::VisitCompareOperation(CompareOperation* node) {
    389   IncrementNodeCount();
    390   node->set_base_id(ReserveIdRange(CompareOperation::num_ids()));
    391   Visit(node->left());
    392   Visit(node->right());
    393   ReserveFeedbackSlots(node);
    394 }
    395 
    396 
    397 void AstNumberingVisitor::VisitSpread(Spread* node) { UNREACHABLE(); }
    398 
    399 
    400 void AstNumberingVisitor::VisitEmptyParentheses(EmptyParentheses* node) {
    401   UNREACHABLE();
    402 }
    403 
    404 
    405 void AstNumberingVisitor::VisitForInStatement(ForInStatement* node) {
    406   IncrementNodeCount();
    407   DisableSelfOptimization();
    408   node->set_base_id(ReserveIdRange(ForInStatement::num_ids()));
    409   Visit(node->enumerable());  // Not part of loop.
    410   node->set_first_yield_id(yield_count_);
    411   Visit(node->each());
    412   Visit(node->body());
    413   node->set_yield_count(yield_count_ - node->first_yield_id());
    414   ReserveFeedbackSlots(node);
    415 }
    416 
    417 
    418 void AstNumberingVisitor::VisitForOfStatement(ForOfStatement* node) {
    419   IncrementNodeCount();
    420   DisableCrankshaft(kForOfStatement);
    421   node->set_base_id(ReserveIdRange(ForOfStatement::num_ids()));
    422   Visit(node->assign_iterator());  // Not part of loop.
    423   node->set_first_yield_id(yield_count_);
    424   Visit(node->next_result());
    425   Visit(node->result_done());
    426   Visit(node->assign_each());
    427   Visit(node->body());
    428   node->set_yield_count(yield_count_ - node->first_yield_id());
    429 }
    430 
    431 
    432 void AstNumberingVisitor::VisitConditional(Conditional* node) {
    433   IncrementNodeCount();
    434   node->set_base_id(ReserveIdRange(Conditional::num_ids()));
    435   Visit(node->condition());
    436   Visit(node->then_expression());
    437   Visit(node->else_expression());
    438 }
    439 
    440 
    441 void AstNumberingVisitor::VisitIfStatement(IfStatement* node) {
    442   IncrementNodeCount();
    443   node->set_base_id(ReserveIdRange(IfStatement::num_ids()));
    444   Visit(node->condition());
    445   Visit(node->then_statement());
    446   if (node->HasElseStatement()) {
    447     Visit(node->else_statement());
    448   }
    449 }
    450 
    451 
    452 void AstNumberingVisitor::VisitSwitchStatement(SwitchStatement* node) {
    453   IncrementNodeCount();
    454   node->set_base_id(ReserveIdRange(SwitchStatement::num_ids()));
    455   Visit(node->tag());
    456   ZoneList<CaseClause*>* cases = node->cases();
    457   for (int i = 0; i < cases->length(); i++) {
    458     VisitCaseClause(cases->at(i));
    459   }
    460 }
    461 
    462 
    463 void AstNumberingVisitor::VisitCaseClause(CaseClause* node) {
    464   IncrementNodeCount();
    465   node->set_base_id(ReserveIdRange(CaseClause::num_ids()));
    466   if (!node->is_default()) Visit(node->label());
    467   VisitStatements(node->statements());
    468   ReserveFeedbackSlots(node);
    469 }
    470 
    471 
    472 void AstNumberingVisitor::VisitForStatement(ForStatement* node) {
    473   IncrementNodeCount();
    474   DisableSelfOptimization();
    475   node->set_base_id(ReserveIdRange(ForStatement::num_ids()));
    476   if (node->init() != NULL) Visit(node->init());  // Not part of loop.
    477   node->set_first_yield_id(yield_count_);
    478   if (node->cond() != NULL) Visit(node->cond());
    479   if (node->next() != NULL) Visit(node->next());
    480   Visit(node->body());
    481   node->set_yield_count(yield_count_ - node->first_yield_id());
    482 }
    483 
    484 
    485 void AstNumberingVisitor::VisitClassLiteral(ClassLiteral* node) {
    486   IncrementNodeCount();
    487   DisableCrankshaft(kClassLiteral);
    488   node->set_base_id(ReserveIdRange(node->num_ids()));
    489   if (node->extends()) Visit(node->extends());
    490   if (node->constructor()) Visit(node->constructor());
    491   if (node->class_variable_proxy()) {
    492     VisitVariableProxy(node->class_variable_proxy());
    493   }
    494   for (int i = 0; i < node->properties()->length(); i++) {
    495     VisitLiteralProperty(node->properties()->at(i));
    496   }
    497   ReserveFeedbackSlots(node);
    498 }
    499 
    500 
    501 void AstNumberingVisitor::VisitObjectLiteral(ObjectLiteral* node) {
    502   IncrementNodeCount();
    503   node->set_base_id(ReserveIdRange(node->num_ids()));
    504   for (int i = 0; i < node->properties()->length(); i++) {
    505     VisitLiteralProperty(node->properties()->at(i));
    506   }
    507   node->BuildConstantProperties(isolate_);
    508   // Mark all computed expressions that are bound to a key that
    509   // is shadowed by a later occurrence of the same key. For the
    510   // marked expressions, no store code will be is emitted.
    511   node->CalculateEmitStore(zone_);
    512   ReserveFeedbackSlots(node);
    513 }
    514 
    515 void AstNumberingVisitor::VisitLiteralProperty(LiteralProperty* node) {
    516   if (node->is_computed_name()) DisableCrankshaft(kComputedPropertyName);
    517   Visit(node->key());
    518   Visit(node->value());
    519 }
    520 
    521 void AstNumberingVisitor::VisitArrayLiteral(ArrayLiteral* node) {
    522   IncrementNodeCount();
    523   node->set_base_id(ReserveIdRange(node->num_ids()));
    524   for (int i = 0; i < node->values()->length(); i++) {
    525     Visit(node->values()->at(i));
    526   }
    527   node->BuildConstantElements(isolate_);
    528   ReserveFeedbackSlots(node);
    529 }
    530 
    531 
    532 void AstNumberingVisitor::VisitCall(Call* node) {
    533   IncrementNodeCount();
    534   ReserveFeedbackSlots(node);
    535   node->set_base_id(ReserveIdRange(Call::num_ids()));
    536   Visit(node->expression());
    537   VisitArguments(node->arguments());
    538 }
    539 
    540 
    541 void AstNumberingVisitor::VisitCallNew(CallNew* node) {
    542   IncrementNodeCount();
    543   ReserveFeedbackSlots(node);
    544   node->set_base_id(ReserveIdRange(CallNew::num_ids()));
    545   Visit(node->expression());
    546   VisitArguments(node->arguments());
    547 }
    548 
    549 
    550 void AstNumberingVisitor::VisitStatements(ZoneList<Statement*>* statements) {
    551   if (statements == NULL) return;
    552   for (int i = 0; i < statements->length(); i++) {
    553     Visit(statements->at(i));
    554   }
    555 }
    556 
    557 void AstNumberingVisitor::VisitDeclarations(Declaration::List* decls) {
    558   for (Declaration* decl : *decls) Visit(decl);
    559 }
    560 
    561 
    562 void AstNumberingVisitor::VisitArguments(ZoneList<Expression*>* arguments) {
    563   for (int i = 0; i < arguments->length(); i++) {
    564     Visit(arguments->at(i));
    565   }
    566 }
    567 
    568 
    569 void AstNumberingVisitor::VisitFunctionLiteral(FunctionLiteral* node) {
    570   IncrementNodeCount();
    571   node->set_base_id(ReserveIdRange(FunctionLiteral::num_ids()));
    572   // We don't recurse into the declarations or body of the function literal:
    573   // you have to separately Renumber() each FunctionLiteral that you compile.
    574 }
    575 
    576 
    577 void AstNumberingVisitor::VisitRewritableExpression(
    578     RewritableExpression* node) {
    579   IncrementNodeCount();
    580   node->set_base_id(ReserveIdRange(RewritableExpression::num_ids()));
    581   Visit(node->expression());
    582 }
    583 
    584 
    585 bool AstNumberingVisitor::Renumber(FunctionLiteral* node) {
    586   DeclarationScope* scope = node->scope();
    587   if (scope->new_target_var()) DisableCrankshaft(kSuperReference);
    588   if (scope->calls_eval()) DisableCrankshaft(kFunctionCallsEval);
    589   if (scope->arguments() != NULL && !scope->arguments()->IsStackAllocated()) {
    590     DisableCrankshaft(kContextAllocatedArguments);
    591   }
    592 
    593   if (scope->rest_parameter() != nullptr) {
    594     DisableCrankshaft(kRestParameter);
    595   }
    596 
    597   if (IsGeneratorFunction(node->kind()) || IsAsyncFunction(node->kind())) {
    598     DisableCrankshaft(kGenerator);
    599   }
    600 
    601   if (IsClassConstructor(node->kind())) {
    602     DisableCrankshaft(kClassConstructorFunction);
    603   }
    604 
    605   VisitDeclarations(scope->declarations());
    606   VisitStatements(node->body());
    607 
    608   node->set_ast_properties(&properties_);
    609   node->set_dont_optimize_reason(dont_optimize_reason());
    610   node->set_yield_count(yield_count_);
    611   return !HasStackOverflow();
    612 }
    613 
    614 
    615 bool AstNumbering::Renumber(Isolate* isolate, Zone* zone,
    616                             FunctionLiteral* function) {
    617   AstNumberingVisitor visitor(isolate, zone);
    618   return visitor.Renumber(function);
    619 }
    620 }  // namespace internal
    621 }  // namespace v8
    622