deps/v8/src/ast-numbering.cc

   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/v8.h"
   6
   7 #include "src/ast.h"
   8 #include "src/ast-numbering.h"
   9 #include "src/scopes.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13
  14
  15 class AstNumberingVisitor FINAL : public AstVisitor {
  16  public:
  17   explicit AstNumberingVisitor(Isolate* isolate, Zone* zone)
  18       : AstVisitor(),
  19         next_id_(BailoutId::FirstUsable().ToInt()),
  20         properties_(zone),
  21         ic_slot_cache_(FLAG_vector_ics ? 4 : 0),
  22         dont_optimize_reason_(kNoReason) {
  23     InitializeAstVisitor(isolate, zone);
  24   }
  25
  26   bool Renumber(FunctionLiteral* node);
  27
  28  private:
  29 // AST node visitor interface.
  30 #define DEFINE_VISIT(type) virtual void Visit##type(type* node) OVERRIDE;
  31   AST_NODE_LIST(DEFINE_VISIT)
  32 #undef DEFINE_VISIT
  33
  34   bool Finish(FunctionLiteral* node);
  35
  36   void VisitStatements(ZoneList<Statement*>* statements) OVERRIDE;
  37   void VisitDeclarations(ZoneList<Declaration*>* declarations) OVERRIDE;
  38   void VisitArguments(ZoneList<Expression*>* arguments);
  39   void VisitObjectLiteralProperty(ObjectLiteralProperty* property);
  40
  41   int ReserveIdRange(int n) {
  42     int tmp = next_id_;
  43     next_id_ += n;
  44     return tmp;
  45   }
  46
  47   void IncrementNodeCount() { properties_.add_node_count(1); }
  48   void DisableSelfOptimization() {
  49     properties_.flags()->Add(kDontSelfOptimize);
  50   }
  51   void DisableOptimization(BailoutReason reason) {
  52     dont_optimize_reason_ = reason;
  53     DisableSelfOptimization();
  54   }
  55   void DisableCaching(BailoutReason reason) {
  56     dont_optimize_reason_ = reason;
  57     DisableSelfOptimization();
  58     properties_.flags()->Add(kDontCache);
  59   }
  60
  61   template <typename Node>
  62   void ReserveFeedbackSlots(Node* node) {
  63     FeedbackVectorRequirements reqs =
  64         node->ComputeFeedbackRequirements(isolate(), &ic_slot_cache_);
  65     if (reqs.slots() > 0) {
  66       node->SetFirstFeedbackSlot(FeedbackVectorSlot(properties_.slots()));
  67       properties_.increase_slots(reqs.slots());
  68     }
  69     if (reqs.ic_slots() > 0) {
  70       int ic_slots = properties_.ic_slots();
  71       node->SetFirstFeedbackICSlot(FeedbackVectorICSlot(ic_slots),
  72                                    &ic_slot_cache_);
  73       properties_.increase_ic_slots(reqs.ic_slots());
  74       if (FLAG_vector_ics) {
  75         for (int i = 0; i < reqs.ic_slots(); i++) {
  76           properties_.SetKind(ic_slots + i, node->FeedbackICSlotKind(i));
  77         }
  78       }
  79     }
  80   }
  81
  82   BailoutReason dont_optimize_reason() const { return dont_optimize_reason_; }
  83
  84   int next_id_;
  85   AstProperties properties_;
  86   // The slot cache allows us to reuse certain vector IC slots. It's only used
  87   // if FLAG_vector_ics is true.
  88   ICSlotCache ic_slot_cache_;
  89   BailoutReason dont_optimize_reason_;
  90
  91   DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
  92   DISALLOW_COPY_AND_ASSIGN(AstNumberingVisitor);
  93 };
  94
  95
  96 void AstNumberingVisitor::VisitVariableDeclaration(VariableDeclaration* node) {
  97   IncrementNodeCount();
  98   VisitVariableProxy(node->proxy());
  99 }
 100
 101
 102 void AstNumberingVisitor::VisitExportDeclaration(ExportDeclaration* node) {
 103   IncrementNodeCount();
 104   DisableOptimization(kExportDeclaration);
 105   VisitVariableProxy(node->proxy());
 106 }
 107
 108
 109 void AstNumberingVisitor::VisitModuleUrl(ModuleUrl* node) {
 110   IncrementNodeCount();
 111   DisableOptimization(kModuleUrl);
 112 }
 113
 114
 115 void AstNumberingVisitor::VisitEmptyStatement(EmptyStatement* node) {
 116   IncrementNodeCount();
 117 }
 118
 119
 120 void AstNumberingVisitor::VisitContinueStatement(ContinueStatement* node) {
 121   IncrementNodeCount();
 122 }
 123
 124
 125 void AstNumberingVisitor::VisitBreakStatement(BreakStatement* node) {
 126   IncrementNodeCount();
 127 }
 128
 129
 130 void AstNumberingVisitor::VisitDebuggerStatement(DebuggerStatement* node) {
 131   IncrementNodeCount();
 132   DisableOptimization(kDebuggerStatement);
 133   node->set_base_id(ReserveIdRange(DebuggerStatement::num_ids()));
 134 }
 135
 136
 137 void AstNumberingVisitor::VisitNativeFunctionLiteral(
 138     NativeFunctionLiteral* node) {
 139   IncrementNodeCount();
 140   DisableOptimization(kNativeFunctionLiteral);
 141   node->set_base_id(ReserveIdRange(NativeFunctionLiteral::num_ids()));
 142 }
 143
 144
 145 void AstNumberingVisitor::VisitLiteral(Literal* node) {
 146   IncrementNodeCount();
 147   node->set_base_id(ReserveIdRange(Literal::num_ids()));
 148 }
 149
 150
 151 void AstNumberingVisitor::VisitRegExpLiteral(RegExpLiteral* node) {
 152   IncrementNodeCount();
 153   node->set_base_id(ReserveIdRange(RegExpLiteral::num_ids()));
 154 }
 155
 156
 157 void AstNumberingVisitor::VisitVariableProxy(VariableProxy* node) {
 158   IncrementNodeCount();
 159   if (node->var()->IsLookupSlot()) {
 160     DisableOptimization(kReferenceToAVariableWhichRequiresDynamicLookup);
 161   }
 162   ReserveFeedbackSlots(node);
 163   node->set_base_id(ReserveIdRange(VariableProxy::num_ids()));
 164 }
 165
 166
 167 void AstNumberingVisitor::VisitThisFunction(ThisFunction* node) {
 168   IncrementNodeCount();
 169   node->set_base_id(ReserveIdRange(ThisFunction::num_ids()));
 170 }
 171
 172
 173 void AstNumberingVisitor::VisitSuperReference(SuperReference* node) {
 174   IncrementNodeCount();
 175   DisableOptimization(kSuperReference);
 176   ReserveFeedbackSlots(node);
 177   node->set_base_id(ReserveIdRange(SuperReference::num_ids()));
 178   Visit(node->this_var());
 179 }
 180
 181
 182 void AstNumberingVisitor::VisitModuleDeclaration(ModuleDeclaration* node) {
 183   IncrementNodeCount();
 184   DisableOptimization(kModuleDeclaration);
 185   VisitVariableProxy(node->proxy());
 186   Visit(node->module());
 187 }
 188
 189
 190 void AstNumberingVisitor::VisitImportDeclaration(ImportDeclaration* node) {
 191   IncrementNodeCount();
 192   DisableOptimization(kImportDeclaration);
 193   VisitVariableProxy(node->proxy());
 194 }
 195
 196
 197 void AstNumberingVisitor::VisitModulePath(ModulePath* node) {
 198   IncrementNodeCount();
 199   DisableOptimization(kModulePath);
 200   Visit(node->module());
 201 }
 202
 203
 204 void AstNumberingVisitor::VisitModuleStatement(ModuleStatement* node) {
 205   IncrementNodeCount();
 206   DisableOptimization(kModuleStatement);
 207   Visit(node->body());
 208 }
 209
 210
 211 void AstNumberingVisitor::VisitExpressionStatement(ExpressionStatement* node) {
 212   IncrementNodeCount();
 213   Visit(node->expression());
 214 }
 215
 216
 217 void AstNumberingVisitor::VisitReturnStatement(ReturnStatement* node) {
 218   IncrementNodeCount();
 219   Visit(node->expression());
 220 }
 221
 222
 223 void AstNumberingVisitor::VisitYield(Yield* node) {
 224   IncrementNodeCount();
 225   DisableOptimization(kYield);
 226   ReserveFeedbackSlots(node);
 227   node->set_base_id(ReserveIdRange(Yield::num_ids()));
 228   Visit(node->generator_object());
 229   Visit(node->expression());
 230 }
 231
 232
 233 void AstNumberingVisitor::VisitThrow(Throw* node) {
 234   IncrementNodeCount();
 235   node->set_base_id(ReserveIdRange(Throw::num_ids()));
 236   Visit(node->exception());
 237 }
 238
 239
 240 void AstNumberingVisitor::VisitUnaryOperation(UnaryOperation* node) {
 241   IncrementNodeCount();
 242   node->set_base_id(ReserveIdRange(UnaryOperation::num_ids()));
 243   Visit(node->expression());
 244 }
 245
 246
 247 void AstNumberingVisitor::VisitCountOperation(CountOperation* node) {
 248   IncrementNodeCount();
 249   node->set_base_id(ReserveIdRange(CountOperation::num_ids()));
 250   Visit(node->expression());
 251 }
 252
 253
 254 void AstNumberingVisitor::VisitBlock(Block* node) {
 255   IncrementNodeCount();
 256   node->set_base_id(ReserveIdRange(Block::num_ids()));
 257   if (node->scope() != NULL) VisitDeclarations(node->scope()->declarations());
 258   VisitStatements(node->statements());
 259 }
 260
 261
 262 void AstNumberingVisitor::VisitFunctionDeclaration(FunctionDeclaration* node) {
 263   IncrementNodeCount();
 264   VisitVariableProxy(node->proxy());
 265   VisitFunctionLiteral(node->fun());
 266 }
 267
 268
 269 void AstNumberingVisitor::VisitModuleLiteral(ModuleLiteral* node) {
 270   IncrementNodeCount();
 271   DisableCaching(kModuleLiteral);
 272   VisitBlock(node->body());
 273 }
 274
 275
 276 void AstNumberingVisitor::VisitCallRuntime(CallRuntime* node) {
 277   IncrementNodeCount();
 278   ReserveFeedbackSlots(node);
 279   if (node->is_jsruntime()) {
 280     // Don't try to optimize JS runtime calls because we bailout on them.
 281     DisableOptimization(kCallToAJavaScriptRuntimeFunction);
 282   }
 283   node->set_base_id(ReserveIdRange(CallRuntime::num_ids()));
 284   VisitArguments(node->arguments());
 285 }
 286
 287
 288 void AstNumberingVisitor::VisitWithStatement(WithStatement* node) {
 289   IncrementNodeCount();
 290   DisableOptimization(kWithStatement);
 291   node->set_base_id(ReserveIdRange(WithStatement::num_ids()));
 292   Visit(node->expression());
 293   Visit(node->statement());
 294 }
 295
 296
 297 void AstNumberingVisitor::VisitDoWhileStatement(DoWhileStatement* node) {
 298   IncrementNodeCount();
 299   DisableSelfOptimization();
 300   node->set_base_id(ReserveIdRange(DoWhileStatement::num_ids()));
 301   Visit(node->body());
 302   Visit(node->cond());
 303 }
 304
 305
 306 void AstNumberingVisitor::VisitWhileStatement(WhileStatement* node) {
 307   IncrementNodeCount();
 308   DisableSelfOptimization();
 309   node->set_base_id(ReserveIdRange(WhileStatement::num_ids()));
 310   Visit(node->cond());
 311   Visit(node->body());
 312 }
 313
 314
 315 void AstNumberingVisitor::VisitTryCatchStatement(TryCatchStatement* node) {
 316   IncrementNodeCount();
 317   DisableOptimization(kTryCatchStatement);
 318   Visit(node->try_block());
 319   Visit(node->catch_block());
 320 }
 321
 322
 323 void AstNumberingVisitor::VisitTryFinallyStatement(TryFinallyStatement* node) {
 324   IncrementNodeCount();
 325   DisableOptimization(kTryFinallyStatement);
 326   Visit(node->try_block());
 327   Visit(node->finally_block());
 328 }
 329
 330
 331 void AstNumberingVisitor::VisitProperty(Property* node) {
 332   IncrementNodeCount();
 333   ReserveFeedbackSlots(node);
 334   node->set_base_id(ReserveIdRange(Property::num_ids()));
 335   Visit(node->key());
 336   Visit(node->obj());
 337 }
 338
 339
 340 void AstNumberingVisitor::VisitAssignment(Assignment* node) {
 341   IncrementNodeCount();
 342   node->set_base_id(ReserveIdRange(Assignment::num_ids()));
 343   if (node->is_compound()) VisitBinaryOperation(node->binary_operation());
 344   Visit(node->target());
 345   Visit(node->value());
 346 }
 347
 348
 349 void AstNumberingVisitor::VisitBinaryOperation(BinaryOperation* node) {
 350   IncrementNodeCount();
 351   node->set_base_id(ReserveIdRange(BinaryOperation::num_ids()));
 352   Visit(node->left());
 353   Visit(node->right());
 354 }
 355
 356
 357 void AstNumberingVisitor::VisitCompareOperation(CompareOperation* node) {
 358   IncrementNodeCount();
 359   node->set_base_id(ReserveIdRange(CompareOperation::num_ids()));
 360   Visit(node->left());
 361   Visit(node->right());
 362 }
 363
 364
 365 void AstNumberingVisitor::VisitForInStatement(ForInStatement* node) {
 366   IncrementNodeCount();
 367   DisableSelfOptimization();
 368   ReserveFeedbackSlots(node);
 369   node->set_base_id(ReserveIdRange(ForInStatement::num_ids()));
 370   Visit(node->each());
 371   Visit(node->enumerable());
 372   Visit(node->body());
 373 }
 374
 375
 376 void AstNumberingVisitor::VisitForOfStatement(ForOfStatement* node) {
 377   IncrementNodeCount();
 378   DisableOptimization(kForOfStatement);
 379   node->set_base_id(ReserveIdRange(ForOfStatement::num_ids()));
 380   Visit(node->assign_iterator());
 381   Visit(node->next_result());
 382   Visit(node->result_done());
 383   Visit(node->assign_each());
 384   Visit(node->body());
 385 }
 386
 387
 388 void AstNumberingVisitor::VisitConditional(Conditional* node) {
 389   IncrementNodeCount();
 390   node->set_base_id(ReserveIdRange(Conditional::num_ids()));
 391   Visit(node->condition());
 392   Visit(node->then_expression());
 393   Visit(node->else_expression());
 394 }
 395
 396
 397 void AstNumberingVisitor::VisitIfStatement(IfStatement* node) {
 398   IncrementNodeCount();
 399   node->set_base_id(ReserveIdRange(IfStatement::num_ids()));
 400   Visit(node->condition());
 401   Visit(node->then_statement());
 402   if (node->HasElseStatement()) {
 403     Visit(node->else_statement());
 404   }
 405 }
 406
 407
 408 void AstNumberingVisitor::VisitSwitchStatement(SwitchStatement* node) {
 409   IncrementNodeCount();
 410   node->set_base_id(ReserveIdRange(SwitchStatement::num_ids()));
 411   Visit(node->tag());
 412   ZoneList<CaseClause*>* cases = node->cases();
 413   for (int i = 0; i < cases->length(); i++) {
 414     VisitCaseClause(cases->at(i));
 415   }
 416 }
 417
 418
 419 void AstNumberingVisitor::VisitCaseClause(CaseClause* node) {
 420   IncrementNodeCount();
 421   node->set_base_id(ReserveIdRange(CaseClause::num_ids()));
 422   if (!node->is_default()) Visit(node->label());
 423   VisitStatements(node->statements());
 424 }
 425
 426
 427 void AstNumberingVisitor::VisitForStatement(ForStatement* node) {
 428   IncrementNodeCount();
 429   DisableSelfOptimization();
 430   node->set_base_id(ReserveIdRange(ForStatement::num_ids()));
 431   if (node->init() != NULL) Visit(node->init());
 432   if (node->cond() != NULL) Visit(node->cond());
 433   if (node->next() != NULL) Visit(node->next());
 434   Visit(node->body());
 435 }
 436
 437
 438 void AstNumberingVisitor::VisitClassLiteral(ClassLiteral* node) {
 439   IncrementNodeCount();
 440   DisableOptimization(kClassLiteral);
 441   node->set_base_id(ReserveIdRange(node->num_ids()));
 442   if (node->extends()) Visit(node->extends());
 443   if (node->constructor()) Visit(node->constructor());
 444   if (node->class_variable_proxy()) {
 445     VisitVariableProxy(node->class_variable_proxy());
 446   }
 447   for (int i = 0; i < node->properties()->length(); i++) {
 448     VisitObjectLiteralProperty(node->properties()->at(i));
 449   }
 450 }
 451
 452
 453 void AstNumberingVisitor::VisitObjectLiteral(ObjectLiteral* node) {
 454   IncrementNodeCount();
 455   node->set_base_id(ReserveIdRange(node->num_ids()));
 456   for (int i = 0; i < node->properties()->length(); i++) {
 457     VisitObjectLiteralProperty(node->properties()->at(i));
 458   }
 459 }
 460
 461
 462 void AstNumberingVisitor::VisitObjectLiteralProperty(
 463     ObjectLiteralProperty* node) {
 464   if (node->is_computed_name()) DisableOptimization(kComputedPropertyName);
 465   Visit(node->key());
 466   Visit(node->value());
 467 }
 468
 469
 470 void AstNumberingVisitor::VisitArrayLiteral(ArrayLiteral* node) {
 471   IncrementNodeCount();
 472   node->set_base_id(ReserveIdRange(node->num_ids()));
 473   for (int i = 0; i < node->values()->length(); i++) {
 474     Visit(node->values()->at(i));
 475   }
 476 }
 477
 478
 479 void AstNumberingVisitor::VisitCall(Call* node) {
 480   IncrementNodeCount();
 481   ReserveFeedbackSlots(node);
 482   node->set_base_id(ReserveIdRange(Call::num_ids()));
 483   Visit(node->expression());
 484   VisitArguments(node->arguments());
 485 }
 486
 487
 488 void AstNumberingVisitor::VisitCallNew(CallNew* node) {
 489   IncrementNodeCount();
 490   ReserveFeedbackSlots(node);
 491   node->set_base_id(ReserveIdRange(CallNew::num_ids()));
 492   Visit(node->expression());
 493   VisitArguments(node->arguments());
 494 }
 495
 496
 497 void AstNumberingVisitor::VisitStatements(ZoneList<Statement*>* statements) {
 498   if (statements == NULL) return;
 499   for (int i = 0; i < statements->length(); i++) {
 500     Visit(statements->at(i));
 501   }
 502 }
 503
 504
 505 void AstNumberingVisitor::VisitDeclarations(
 506     ZoneList<Declaration*>* declarations) {
 507   for (int i = 0; i < declarations->length(); i++) {
 508     Visit(declarations->at(i));
 509   }
 510 }
 511
 512
 513 void AstNumberingVisitor::VisitArguments(ZoneList<Expression*>* arguments) {
 514   for (int i = 0; i < arguments->length(); i++) {
 515     Visit(arguments->at(i));
 516   }
 517 }
 518
 519
 520 void AstNumberingVisitor::VisitFunctionLiteral(FunctionLiteral* node) {
 521   IncrementNodeCount();
 522   node->set_base_id(ReserveIdRange(FunctionLiteral::num_ids()));
 523   // We don't recurse into the declarations or body of the function literal:
 524   // you have to separately Renumber() each FunctionLiteral that you compile.
 525 }
 526
 527
 528 bool AstNumberingVisitor::Finish(FunctionLiteral* node) {
 529   node->set_ast_properties(&properties_);
 530   node->set_dont_optimize_reason(dont_optimize_reason());
 531   return !HasStackOverflow();
 532 }
 533
 534
 535 bool AstNumberingVisitor::Renumber(FunctionLiteral* node) {
 536   Scope* scope = node->scope();
 537
 538   if (scope->HasIllegalRedeclaration()) {
 539     scope->VisitIllegalRedeclaration(this);
 540     DisableOptimization(kFunctionWithIllegalRedeclaration);
 541     return Finish(node);
 542   }
 543   if (scope->calls_eval()) DisableOptimization(kFunctionCallsEval);
 544   if (scope->arguments() != NULL && !scope->arguments()->IsStackAllocated()) {
 545     DisableOptimization(kContextAllocatedArguments);
 546   }
 547
 548   VisitDeclarations(scope->declarations());
 549   if (scope->is_function_scope() && scope->function() != NULL) {
 550     // Visit the name of the named function expression.
 551     Visit(scope->function());
 552   }
 553   VisitStatements(node->body());
 554
 555   return Finish(node);
 556 }
 557
 558
 559 bool AstNumbering::Renumber(Isolate* isolate, Zone* zone,
 560                             FunctionLiteral* function) {
 561   AstNumberingVisitor visitor(isolate, zone);
 562   return visitor.Renumber(function);
 563 }
 564 }
 565 }  // namespace v8::internal