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
10namespace v8 {
11namespace internal {
12
13class 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
85void AstNumberingVisitor::VisitVariableDeclaration(VariableDeclaration* node) {
86  IncrementNodeCount();
87  VisitVariableProxy(node->proxy());
88}
89
90
91void AstNumberingVisitor::VisitEmptyStatement(EmptyStatement* node) {
92  IncrementNodeCount();
93}
94
95
96void AstNumberingVisitor::VisitSloppyBlockFunctionStatement(
97    SloppyBlockFunctionStatement* node) {
98  IncrementNodeCount();
99  Visit(node->statement());
100}
101
102
103void AstNumberingVisitor::VisitContinueStatement(ContinueStatement* node) {
104  IncrementNodeCount();
105}
106
107
108void AstNumberingVisitor::VisitBreakStatement(BreakStatement* node) {
109  IncrementNodeCount();
110}
111
112
113void AstNumberingVisitor::VisitDebuggerStatement(DebuggerStatement* node) {
114  IncrementNodeCount();
115  DisableOptimization(kDebuggerStatement);
116  node->set_base_id(ReserveIdRange(DebuggerStatement::num_ids()));
117}
118
119
120void AstNumberingVisitor::VisitNativeFunctionLiteral(
121    NativeFunctionLiteral* node) {
122  IncrementNodeCount();
123  DisableOptimization(kNativeFunctionLiteral);
124  node->set_base_id(ReserveIdRange(NativeFunctionLiteral::num_ids()));
125}
126
127
128void 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
136void AstNumberingVisitor::VisitLiteral(Literal* node) {
137  IncrementNodeCount();
138  node->set_base_id(ReserveIdRange(Literal::num_ids()));
139}
140
141
142void AstNumberingVisitor::VisitRegExpLiteral(RegExpLiteral* node) {
143  IncrementNodeCount();
144  node->set_base_id(ReserveIdRange(RegExpLiteral::num_ids()));
145}
146
147
148void 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
164void AstNumberingVisitor::VisitVariableProxy(VariableProxy* node) {
165  VisitVariableProxyReference(node);
166  ReserveFeedbackSlots(node);
167}
168
169
170void AstNumberingVisitor::VisitThisFunction(ThisFunction* node) {
171  IncrementNodeCount();
172  node->set_base_id(ReserveIdRange(ThisFunction::num_ids()));
173}
174
175
176void 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
186void 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
196void AstNumberingVisitor::VisitExpressionStatement(ExpressionStatement* node) {
197  IncrementNodeCount();
198  Visit(node->expression());
199}
200
201
202void AstNumberingVisitor::VisitReturnStatement(ReturnStatement* node) {
203  IncrementNodeCount();
204  Visit(node->expression());
205}
206
207
208void 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
218void AstNumberingVisitor::VisitThrow(Throw* node) {
219  IncrementNodeCount();
220  node->set_base_id(ReserveIdRange(Throw::num_ids()));
221  Visit(node->exception());
222}
223
224
225void AstNumberingVisitor::VisitUnaryOperation(UnaryOperation* node) {
226  IncrementNodeCount();
227  node->set_base_id(ReserveIdRange(UnaryOperation::num_ids()));
228  Visit(node->expression());
229}
230
231
232void 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
240void 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
248void AstNumberingVisitor::VisitFunctionDeclaration(FunctionDeclaration* node) {
249  IncrementNodeCount();
250  VisitVariableProxy(node->proxy());
251  VisitFunctionLiteral(node->fun());
252}
253
254
255void 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
283void 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
292void 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
303void 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
314void 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
333void 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
344void 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
352void 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
362void AstNumberingVisitor::VisitProperty(Property* node) {
363  VisitPropertyReference(node);
364  ReserveFeedbackSlots(node);
365}
366
367
368void 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
379void 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
388void 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
397void AstNumberingVisitor::VisitSpread(Spread* node) { UNREACHABLE(); }
398
399
400void AstNumberingVisitor::VisitEmptyParentheses(EmptyParentheses* node) {
401  UNREACHABLE();
402}
403
404
405void 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
418void 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
432void 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
441void 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
452void 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
463void 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
472void 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
485void 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
501void 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
515void AstNumberingVisitor::VisitLiteralProperty(LiteralProperty* node) {
516  if (node->is_computed_name()) DisableCrankshaft(kComputedPropertyName);
517  Visit(node->key());
518  Visit(node->value());
519}
520
521void 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
532void 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
541void 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
550void 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
557void AstNumberingVisitor::VisitDeclarations(Declaration::List* decls) {
558  for (Declaration* decl : *decls) Visit(decl);
559}
560
561
562void AstNumberingVisitor::VisitArguments(ZoneList<Expression*>* arguments) {
563  for (int i = 0; i < arguments->length(); i++) {
564    Visit(arguments->at(i));
565  }
566}
567
568
569void 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
577void AstNumberingVisitor::VisitRewritableExpression(
578    RewritableExpression* node) {
579  IncrementNodeCount();
580  node->set_base_id(ReserveIdRange(RewritableExpression::num_ids()));
581  Visit(node->expression());
582}
583
584
585bool 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
615bool 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