src/v8/src/ast.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/ast.h"
   6
   7 #include <cmath>  // For isfinite.
   8 #include "src/builtins.h"
   9 #include "src/code-stubs.h"
  10 #include "src/contexts.h"
  11 #include "src/conversions.h"
  12 #include "src/hashmap.h"
  13 #include "src/parser.h"
  14 #include "src/property.h"
  15 #include "src/property-details.h"
  16 #include "src/scopes.h"
  17 #include "src/string-stream.h"
  18 #include "src/type-info.h"
  19
  20 namespace v8 {
  21 namespace internal {
  22
  23 // ----------------------------------------------------------------------------
  24 // All the Accept member functions for each syntax tree node type.
  25
  26 #define DECL_ACCEPT(type)                                       \
  27   void type::Accept(AstVisitor* v) { v->Visit##type(this); }
  28 AST_NODE_LIST(DECL_ACCEPT)
  29 #undef DECL_ACCEPT
  30
  31
  32 // ----------------------------------------------------------------------------
  33 // Implementation of other node functionality.
  34
  35
  36 bool Expression::IsSmiLiteral() const {
  37   return IsLiteral() && AsLiteral()->value()->IsSmi();
  38 }
  39
  40
  41 bool Expression::IsStringLiteral() const {
  42   return IsLiteral() && AsLiteral()->value()->IsString();
  43 }
  44
  45
  46 bool Expression::IsNullLiteral() const {
  47   return IsLiteral() && AsLiteral()->value()->IsNull();
  48 }
  49
  50
  51 bool Expression::IsUndefinedLiteral(Isolate* isolate) const {
  52   const VariableProxy* var_proxy = AsVariableProxy();
  53   if (var_proxy == NULL) return false;
  54   Variable* var = var_proxy->var();
  55   // The global identifier "undefined" is immutable. Everything
  56   // else could be reassigned.
  57   return var != NULL && var->location() == Variable::UNALLOCATED &&
  58          var_proxy->raw_name()->IsOneByteEqualTo("undefined");
  59 }
  60
  61
  62 VariableProxy::VariableProxy(Zone* zone, Variable* var, int position)
  63     : Expression(zone, position),
  64       is_this_(var->is_this()),
  65       is_assigned_(false),
  66       is_resolved_(false),
  67       variable_feedback_slot_(FeedbackVectorICSlot::Invalid()),
  68       raw_name_(var->raw_name()),
  69       interface_(var->interface()) {
  70   BindTo(var);
  71 }
  72
  73
  74 VariableProxy::VariableProxy(Zone* zone, const AstRawString* name, bool is_this,
  75                              Interface* interface, int position)
  76     : Expression(zone, position),
  77       is_this_(is_this),
  78       is_assigned_(false),
  79       is_resolved_(false),
  80       variable_feedback_slot_(FeedbackVectorICSlot::Invalid()),
  81       raw_name_(name),
  82       interface_(interface) {}
  83
  84
  85 void VariableProxy::BindTo(Variable* var) {
  86   DCHECK(!FLAG_harmony_modules || interface_->IsUnified(var->interface()));
  87   DCHECK((is_this() && var->is_this()) || raw_name() == var->raw_name());
  88   // Ideally CONST-ness should match. However, this is very hard to achieve
  89   // because we don't know the exact semantics of conflicting (const and
  90   // non-const) multiple variable declarations, const vars introduced via
  91   // eval() etc.  Const-ness and variable declarations are a complete mess
  92   // in JS. Sigh...
  93   set_var(var);
  94   set_is_resolved();
  95   var->set_is_used();
  96 }
  97
  98
  99 Assignment::Assignment(Zone* zone, Token::Value op, Expression* target,
 100                        Expression* value, int pos)
 101     : Expression(zone, pos),
 102       is_uninitialized_(false),
 103       key_type_(ELEMENT),
 104       store_mode_(STANDARD_STORE),
 105       op_(op),
 106       target_(target),
 107       value_(value),
 108       binary_operation_(NULL) {}
 109
 110
 111 Token::Value Assignment::binary_op() const {
 112   switch (op_) {
 113     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
 114     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
 115     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
 116     case Token::ASSIGN_SHL: return Token::SHL;
 117     case Token::ASSIGN_SAR: return Token::SAR;
 118     case Token::ASSIGN_SHR: return Token::SHR;
 119     case Token::ASSIGN_ADD: return Token::ADD;
 120     case Token::ASSIGN_SUB: return Token::SUB;
 121     case Token::ASSIGN_MUL: return Token::MUL;
 122     case Token::ASSIGN_DIV: return Token::DIV;
 123     case Token::ASSIGN_MOD: return Token::MOD;
 124     default: UNREACHABLE();
 125   }
 126   return Token::ILLEGAL;
 127 }
 128
 129
 130 bool FunctionLiteral::AllowsLazyCompilation() {
 131   return scope()->AllowsLazyCompilation();
 132 }
 133
 134
 135 bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
 136   return scope()->AllowsLazyCompilationWithoutContext();
 137 }
 138
 139
 140 int FunctionLiteral::start_position() const {
 141   return scope()->start_position();
 142 }
 143
 144
 145 int FunctionLiteral::end_position() const {
 146   return scope()->end_position();
 147 }
 148
 149
 150 StrictMode FunctionLiteral::strict_mode() const {
 151   return scope()->strict_mode();
 152 }
 153
 154
 155 void FunctionLiteral::InitializeSharedInfo(
 156     Handle<Code> unoptimized_code) {
 157   for (RelocIterator it(*unoptimized_code); !it.done(); it.next()) {
 158     RelocInfo* rinfo = it.rinfo();
 159     if (rinfo->rmode() != RelocInfo::EMBEDDED_OBJECT) continue;
 160     Object* obj = rinfo->target_object();
 161     if (obj->IsSharedFunctionInfo()) {
 162       SharedFunctionInfo* shared = SharedFunctionInfo::cast(obj);
 163       if (shared->start_position() == start_position()) {
 164         shared_info_ = Handle<SharedFunctionInfo>(shared);
 165         break;
 166       }
 167     }
 168   }
 169 }
 170
 171
 172 ObjectLiteralProperty::ObjectLiteralProperty(Zone* zone,
 173                                              AstValueFactory* ast_value_factory,
 174                                              Literal* key, Expression* value,
 175                                              bool is_static) {
 176   emit_store_ = true;
 177   key_ = key;
 178   value_ = value;
 179   is_static_ = is_static;
 180   if (key->raw_value()->EqualsString(ast_value_factory->proto_string())) {
 181     kind_ = PROTOTYPE;
 182   } else if (value_->AsMaterializedLiteral() != NULL) {
 183     kind_ = MATERIALIZED_LITERAL;
 184   } else if (value_->IsLiteral()) {
 185     kind_ = CONSTANT;
 186   } else {
 187     kind_ = COMPUTED;
 188   }
 189 }
 190
 191
 192 ObjectLiteralProperty::ObjectLiteralProperty(Zone* zone, bool is_getter,
 193                                              FunctionLiteral* value,
 194                                              bool is_static) {
 195   emit_store_ = true;
 196   value_ = value;
 197   kind_ = is_getter ? GETTER : SETTER;
 198   is_static_ = is_static;
 199 }
 200
 201
 202 bool ObjectLiteral::Property::IsCompileTimeValue() {
 203   return kind_ == CONSTANT ||
 204       (kind_ == MATERIALIZED_LITERAL &&
 205        CompileTimeValue::IsCompileTimeValue(value_));
 206 }
 207
 208
 209 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
 210   emit_store_ = emit_store;
 211 }
 212
 213
 214 bool ObjectLiteral::Property::emit_store() {
 215   return emit_store_;
 216 }
 217
 218
 219 void ObjectLiteral::CalculateEmitStore(Zone* zone) {
 220   ZoneAllocationPolicy allocator(zone);
 221
 222   ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
 223                     allocator);
 224   for (int i = properties()->length() - 1; i >= 0; i--) {
 225     ObjectLiteral::Property* property = properties()->at(i);
 226     Literal* literal = property->key();
 227     if (literal->value()->IsNull()) continue;
 228     uint32_t hash = literal->Hash();
 229     // If the key of a computed property is in the table, do not emit
 230     // a store for the property later.
 231     if ((property->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL ||
 232          property->kind() == ObjectLiteral::Property::COMPUTED) &&
 233         table.Lookup(literal, hash, false, allocator) != NULL) {
 234       property->set_emit_store(false);
 235     } else {
 236       // Add key to the table.
 237       table.Lookup(literal, hash, true, allocator);
 238     }
 239   }
 240 }
 241
 242
 243 bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) {
 244   return property != NULL &&
 245          property->kind() != ObjectLiteral::Property::PROTOTYPE;
 246 }
 247
 248
 249 void ObjectLiteral::BuildConstantProperties(Isolate* isolate) {
 250   if (!constant_properties_.is_null()) return;
 251
 252   // Allocate a fixed array to hold all the constant properties.
 253   Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray(
 254       boilerplate_properties_ * 2, TENURED);
 255
 256   int position = 0;
 257   // Accumulate the value in local variables and store it at the end.
 258   bool is_simple = true;
 259   int depth_acc = 1;
 260   uint32_t max_element_index = 0;
 261   uint32_t elements = 0;
 262   for (int i = 0; i < properties()->length(); i++) {
 263     ObjectLiteral::Property* property = properties()->at(i);
 264     if (!IsBoilerplateProperty(property)) {
 265       is_simple = false;
 266       continue;
 267     }
 268     MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral();
 269     if (m_literal != NULL) {
 270       m_literal->BuildConstants(isolate);
 271       if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1;
 272     }
 273
 274     // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined
 275     // value for COMPUTED properties, the real value is filled in at
 276     // runtime. The enumeration order is maintained.
 277     Handle<Object> key = property->key()->value();
 278     Handle<Object> value = GetBoilerplateValue(property->value(), isolate);
 279
 280     // Ensure objects that may, at any point in time, contain fields with double
 281     // representation are always treated as nested objects. This is true for
 282     // computed fields (value is undefined), and smi and double literals
 283     // (value->IsNumber()).
 284     // TODO(verwaest): Remove once we can store them inline.
 285     if (FLAG_track_double_fields &&
 286         (value->IsNumber() || value->IsUninitialized())) {
 287       may_store_doubles_ = true;
 288     }
 289
 290     is_simple = is_simple && !value->IsUninitialized();
 291
 292     // Keep track of the number of elements in the object literal and
 293     // the largest element index.  If the largest element index is
 294     // much larger than the number of elements, creating an object
 295     // literal with fast elements will be a waste of space.
 296     uint32_t element_index = 0;
 297     if (key->IsString()
 298         && Handle<String>::cast(key)->AsArrayIndex(&element_index)
 299         && element_index > max_element_index) {
 300       max_element_index = element_index;
 301       elements++;
 302     } else if (key->IsSmi()) {
 303       int key_value = Smi::cast(*key)->value();
 304       if (key_value > 0
 305           && static_cast<uint32_t>(key_value) > max_element_index) {
 306         max_element_index = key_value;
 307       }
 308       elements++;
 309     }
 310
 311     // Add name, value pair to the fixed array.
 312     constant_properties->set(position++, *key);
 313     constant_properties->set(position++, *value);
 314   }
 315
 316   constant_properties_ = constant_properties;
 317   fast_elements_ =
 318       (max_element_index <= 32) || ((2 * elements) >= max_element_index);
 319   set_is_simple(is_simple);
 320   set_depth(depth_acc);
 321 }
 322
 323
 324 void ArrayLiteral::BuildConstantElements(Isolate* isolate) {
 325   if (!constant_elements_.is_null()) return;
 326
 327   // Allocate a fixed array to hold all the object literals.
 328   Handle<JSArray> array =
 329       isolate->factory()->NewJSArray(0, FAST_HOLEY_SMI_ELEMENTS);
 330   JSArray::Expand(array, values()->length());
 331
 332   // Fill in the literals.
 333   bool is_simple = true;
 334   int depth_acc = 1;
 335   bool is_holey = false;
 336   for (int i = 0, n = values()->length(); i < n; i++) {
 337     Expression* element = values()->at(i);
 338     MaterializedLiteral* m_literal = element->AsMaterializedLiteral();
 339     if (m_literal != NULL) {
 340       m_literal->BuildConstants(isolate);
 341       if (m_literal->depth() + 1 > depth_acc) {
 342         depth_acc = m_literal->depth() + 1;
 343       }
 344     }
 345     Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate);
 346     if (boilerplate_value->IsTheHole()) {
 347       is_holey = true;
 348     } else if (boilerplate_value->IsUninitialized()) {
 349       is_simple = false;
 350       JSObject::SetOwnElement(
 351           array, i, handle(Smi::FromInt(0), isolate), SLOPPY).Assert();
 352     } else {
 353       JSObject::SetOwnElement(array, i, boilerplate_value, SLOPPY).Assert();
 354     }
 355   }
 356
 357   Handle<FixedArrayBase> element_values(array->elements());
 358
 359   // Simple and shallow arrays can be lazily copied, we transform the
 360   // elements array to a copy-on-write array.
 361   if (is_simple && depth_acc == 1 && values()->length() > 0 &&
 362       array->HasFastSmiOrObjectElements()) {
 363     element_values->set_map(isolate->heap()->fixed_cow_array_map());
 364   }
 365
 366   // Remember both the literal's constant values as well as the ElementsKind
 367   // in a 2-element FixedArray.
 368   Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED);
 369
 370   ElementsKind kind = array->GetElementsKind();
 371   kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind);
 372
 373   literals->set(0, Smi::FromInt(kind));
 374   literals->set(1, *element_values);
 375
 376   constant_elements_ = literals;
 377   set_is_simple(is_simple);
 378   set_depth(depth_acc);
 379 }
 380
 381
 382 Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression,
 383                                                         Isolate* isolate) {
 384   if (expression->IsLiteral()) {
 385     return expression->AsLiteral()->value();
 386   }
 387   if (CompileTimeValue::IsCompileTimeValue(expression)) {
 388     return CompileTimeValue::GetValue(isolate, expression);
 389   }
 390   return isolate->factory()->uninitialized_value();
 391 }
 392
 393
 394 void MaterializedLiteral::BuildConstants(Isolate* isolate) {
 395   if (IsArrayLiteral()) {
 396     return AsArrayLiteral()->BuildConstantElements(isolate);
 397   }
 398   if (IsObjectLiteral()) {
 399     return AsObjectLiteral()->BuildConstantProperties(isolate);
 400   }
 401   DCHECK(IsRegExpLiteral());
 402   DCHECK(depth() >= 1);  // Depth should be initialized.
 403 }
 404
 405
 406 void TargetCollector::AddTarget(Label* target, Zone* zone) {
 407   // Add the label to the collector, but discard duplicates.
 408   int length = targets_.length();
 409   for (int i = 0; i < length; i++) {
 410     if (targets_[i] == target) return;
 411   }
 412   targets_.Add(target, zone);
 413 }
 414
 415
 416 void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 417   // TODO(olivf) If this Operation is used in a test context, then the
 418   // expression has a ToBoolean stub and we want to collect the type
 419   // information. However the GraphBuilder expects it to be on the instruction
 420   // corresponding to the TestContext, therefore we have to store it here and
 421   // not on the operand.
 422   set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
 423 }
 424
 425
 426 void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 427   // TODO(olivf) If this Operation is used in a test context, then the right
 428   // hand side has a ToBoolean stub and we want to collect the type information.
 429   // However the GraphBuilder expects it to be on the instruction corresponding
 430   // to the TestContext, therefore we have to store it here and not on the
 431   // right hand operand.
 432   set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
 433 }
 434
 435
 436 bool BinaryOperation::ResultOverwriteAllowed() const {
 437   switch (op()) {
 438     case Token::COMMA:
 439     case Token::OR:
 440     case Token::AND:
 441       return false;
 442     case Token::BIT_OR:
 443     case Token::BIT_XOR:
 444     case Token::BIT_AND:
 445     case Token::SHL:
 446     case Token::SAR:
 447     case Token::SHR:
 448     case Token::ADD:
 449     case Token::SUB:
 450     case Token::MUL:
 451     case Token::DIV:
 452     case Token::MOD:
 453       return true;
 454     default:
 455       UNREACHABLE();
 456   }
 457   return false;
 458 }
 459
 460
 461 static bool IsTypeof(Expression* expr) {
 462   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 463   return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
 464 }
 465
 466
 467 // Check for the pattern: typeof <expression> equals <string literal>.
 468 static bool MatchLiteralCompareTypeof(Expression* left,
 469                                       Token::Value op,
 470                                       Expression* right,
 471                                       Expression** expr,
 472                                       Handle<String>* check) {
 473   if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
 474     *expr = left->AsUnaryOperation()->expression();
 475     *check = Handle<String>::cast(right->AsLiteral()->value());
 476     return true;
 477   }
 478   return false;
 479 }
 480
 481
 482 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
 483                                               Handle<String>* check) {
 484   return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
 485       MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
 486 }
 487
 488
 489 static bool IsVoidOfLiteral(Expression* expr) {
 490   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 491   return maybe_unary != NULL &&
 492       maybe_unary->op() == Token::VOID &&
 493       maybe_unary->expression()->IsLiteral();
 494 }
 495
 496
 497 // Check for the pattern: void <literal> equals <expression> or
 498 // undefined equals <expression>
 499 static bool MatchLiteralCompareUndefined(Expression* left,
 500                                          Token::Value op,
 501                                          Expression* right,
 502                                          Expression** expr,
 503                                          Isolate* isolate) {
 504   if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
 505     *expr = right;
 506     return true;
 507   }
 508   if (left->IsUndefinedLiteral(isolate) && Token::IsEqualityOp(op)) {
 509     *expr = right;
 510     return true;
 511   }
 512   return false;
 513 }
 514
 515
 516 bool CompareOperation::IsLiteralCompareUndefined(
 517     Expression** expr, Isolate* isolate) {
 518   return MatchLiteralCompareUndefined(left_, op_, right_, expr, isolate) ||
 519       MatchLiteralCompareUndefined(right_, op_, left_, expr, isolate);
 520 }
 521
 522
 523 // Check for the pattern: null equals <expression>
 524 static bool MatchLiteralCompareNull(Expression* left,
 525                                     Token::Value op,
 526                                     Expression* right,
 527                                     Expression** expr) {
 528   if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
 529     *expr = right;
 530     return true;
 531   }
 532   return false;
 533 }
 534
 535
 536 bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
 537   return MatchLiteralCompareNull(left_, op_, right_, expr) ||
 538       MatchLiteralCompareNull(right_, op_, left_, expr);
 539 }
 540
 541
 542 // ----------------------------------------------------------------------------
 543 // Inlining support
 544
 545 bool Declaration::IsInlineable() const {
 546   return proxy()->var()->IsStackAllocated();
 547 }
 548
 549 bool FunctionDeclaration::IsInlineable() const {
 550   return false;
 551 }
 552
 553
 554 // ----------------------------------------------------------------------------
 555 // Recording of type feedback
 556
 557 // TODO(rossberg): all RecordTypeFeedback functions should disappear
 558 // once we use the common type field in the AST consistently.
 559
 560 void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 561   set_to_boolean_types(oracle->ToBooleanTypes(test_id()));
 562 }
 563
 564
 565 bool Call::IsUsingCallFeedbackSlot(Isolate* isolate) const {
 566   CallType call_type = GetCallType(isolate);
 567   return (call_type != POSSIBLY_EVAL_CALL);
 568 }
 569
 570
 571 Call::CallType Call::GetCallType(Isolate* isolate) const {
 572   VariableProxy* proxy = expression()->AsVariableProxy();
 573   if (proxy != NULL) {
 574     if (proxy->var()->is_possibly_eval(isolate)) {
 575       return POSSIBLY_EVAL_CALL;
 576     } else if (proxy->var()->IsUnallocated()) {
 577       return GLOBAL_CALL;
 578     } else if (proxy->var()->IsLookupSlot()) {
 579       return LOOKUP_SLOT_CALL;
 580     }
 581   }
 582
 583   if (expression()->AsSuperReference() != NULL) return SUPER_CALL;
 584
 585   Property* property = expression()->AsProperty();
 586   return property != NULL ? PROPERTY_CALL : OTHER_CALL;
 587 }
 588
 589
 590 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
 591                                LookupIterator* it) {
 592   target_ = Handle<JSFunction>::null();
 593   cell_ = Handle<Cell>::null();
 594   DCHECK(it->IsFound() && it->GetHolder<JSObject>().is_identical_to(global));
 595   cell_ = it->GetPropertyCell();
 596   if (cell_->value()->IsJSFunction()) {
 597     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
 598     // If the function is in new space we assume it's more likely to
 599     // change and thus prefer the general IC code.
 600     if (!it->isolate()->heap()->InNewSpace(*candidate)) {
 601       target_ = candidate;
 602       return true;
 603     }
 604   }
 605   return false;
 606 }
 607
 608
 609 void CallNew::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 610   FeedbackVectorSlot allocation_site_feedback_slot =
 611       FLAG_pretenuring_call_new ? AllocationSiteFeedbackSlot()
 612                                 : CallNewFeedbackSlot();
 613   allocation_site_ =
 614       oracle->GetCallNewAllocationSite(allocation_site_feedback_slot);
 615   is_monomorphic_ = oracle->CallNewIsMonomorphic(CallNewFeedbackSlot());
 616   if (is_monomorphic_) {
 617     target_ = oracle->GetCallNewTarget(CallNewFeedbackSlot());
 618   }
 619 }
 620
 621
 622 void ObjectLiteral::Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 623   TypeFeedbackId id = key()->LiteralFeedbackId();
 624   SmallMapList maps;
 625   oracle->CollectReceiverTypes(id, &maps);
 626   receiver_type_ = maps.length() == 1 ? maps.at(0)
 627                                       : Handle<Map>::null();
 628 }
 629
 630
 631 // ----------------------------------------------------------------------------
 632 // Implementation of AstVisitor
 633
 634 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
 635   for (int i = 0; i < declarations->length(); i++) {
 636     Visit(declarations->at(i));
 637   }
 638 }
 639
 640
 641 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
 642   for (int i = 0; i < statements->length(); i++) {
 643     Statement* stmt = statements->at(i);
 644     Visit(stmt);
 645     if (stmt->IsJump()) break;
 646   }
 647 }
 648
 649
 650 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
 651   for (int i = 0; i < expressions->length(); i++) {
 652     // The variable statement visiting code may pass NULL expressions
 653     // to this code. Maybe this should be handled by introducing an
 654     // undefined expression or literal?  Revisit this code if this
 655     // changes
 656     Expression* expression = expressions->at(i);
 657     if (expression != NULL) Visit(expression);
 658   }
 659 }
 660
 661
 662 // ----------------------------------------------------------------------------
 663 // Regular expressions
 664
 665 #define MAKE_ACCEPT(Name)                                            \
 666   void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
 667     return visitor->Visit##Name(this, data);                         \
 668   }
 669 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
 670 #undef MAKE_ACCEPT
 671
 672 #define MAKE_TYPE_CASE(Name)                                         \
 673   RegExp##Name* RegExpTree::As##Name() {                             \
 674     return NULL;                                                     \
 675   }                                                                  \
 676   bool RegExpTree::Is##Name() { return false; }
 677 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 678 #undef MAKE_TYPE_CASE
 679
 680 #define MAKE_TYPE_CASE(Name)                                        \
 681   RegExp##Name* RegExp##Name::As##Name() {                          \
 682     return this;                                                    \
 683   }                                                                 \
 684   bool RegExp##Name::Is##Name() { return true; }
 685 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 686 #undef MAKE_TYPE_CASE
 687
 688
 689 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
 690   Interval result = Interval::Empty();
 691   for (int i = 0; i < children->length(); i++)
 692     result = result.Union(children->at(i)->CaptureRegisters());
 693   return result;
 694 }
 695
 696
 697 Interval RegExpAlternative::CaptureRegisters() {
 698   return ListCaptureRegisters(nodes());
 699 }
 700
 701
 702 Interval RegExpDisjunction::CaptureRegisters() {
 703   return ListCaptureRegisters(alternatives());
 704 }
 705
 706
 707 Interval RegExpLookahead::CaptureRegisters() {
 708   return body()->CaptureRegisters();
 709 }
 710
 711
 712 Interval RegExpCapture::CaptureRegisters() {
 713   Interval self(StartRegister(index()), EndRegister(index()));
 714   return self.Union(body()->CaptureRegisters());
 715 }
 716
 717
 718 Interval RegExpQuantifier::CaptureRegisters() {
 719   return body()->CaptureRegisters();
 720 }
 721
 722
 723 bool RegExpAssertion::IsAnchoredAtStart() {
 724   return assertion_type() == RegExpAssertion::START_OF_INPUT;
 725 }
 726
 727
 728 bool RegExpAssertion::IsAnchoredAtEnd() {
 729   return assertion_type() == RegExpAssertion::END_OF_INPUT;
 730 }
 731
 732
 733 bool RegExpAlternative::IsAnchoredAtStart() {
 734   ZoneList<RegExpTree*>* nodes = this->nodes();
 735   for (int i = 0; i < nodes->length(); i++) {
 736     RegExpTree* node = nodes->at(i);
 737     if (node->IsAnchoredAtStart()) { return true; }
 738     if (node->max_match() > 0) { return false; }
 739   }
 740   return false;
 741 }
 742
 743
 744 bool RegExpAlternative::IsAnchoredAtEnd() {
 745   ZoneList<RegExpTree*>* nodes = this->nodes();
 746   for (int i = nodes->length() - 1; i >= 0; i--) {
 747     RegExpTree* node = nodes->at(i);
 748     if (node->IsAnchoredAtEnd()) { return true; }
 749     if (node->max_match() > 0) { return false; }
 750   }
 751   return false;
 752 }
 753
 754
 755 bool RegExpDisjunction::IsAnchoredAtStart() {
 756   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 757   for (int i = 0; i < alternatives->length(); i++) {
 758     if (!alternatives->at(i)->IsAnchoredAtStart())
 759       return false;
 760   }
 761   return true;
 762 }
 763
 764
 765 bool RegExpDisjunction::IsAnchoredAtEnd() {
 766   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 767   for (int i = 0; i < alternatives->length(); i++) {
 768     if (!alternatives->at(i)->IsAnchoredAtEnd())
 769       return false;
 770   }
 771   return true;
 772 }
 773
 774
 775 bool RegExpLookahead::IsAnchoredAtStart() {
 776   return is_positive() && body()->IsAnchoredAtStart();
 777 }
 778
 779
 780 bool RegExpCapture::IsAnchoredAtStart() {
 781   return body()->IsAnchoredAtStart();
 782 }
 783
 784
 785 bool RegExpCapture::IsAnchoredAtEnd() {
 786   return body()->IsAnchoredAtEnd();
 787 }
 788
 789
 790 // Convert regular expression trees to a simple sexp representation.
 791 // This representation should be different from the input grammar
 792 // in as many cases as possible, to make it more difficult for incorrect
 793 // parses to look as correct ones which is likely if the input and
 794 // output formats are alike.
 795 class RegExpUnparser FINAL : public RegExpVisitor {
 796  public:
 797   RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {}
 798   void VisitCharacterRange(CharacterRange that);
 799 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*,          \
 800                                                   void* data) OVERRIDE;
 801   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 802 #undef MAKE_CASE
 803  private:
 804   std::ostream& os_;
 805   Zone* zone_;
 806 };
 807
 808
 809 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
 810   os_ << "(|";
 811   for (int i = 0; i <  that->alternatives()->length(); i++) {
 812     os_ << " ";
 813     that->alternatives()->at(i)->Accept(this, data);
 814   }
 815   os_ << ")";
 816   return NULL;
 817 }
 818
 819
 820 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
 821   os_ << "(:";
 822   for (int i = 0; i <  that->nodes()->length(); i++) {
 823     os_ << " ";
 824     that->nodes()->at(i)->Accept(this, data);
 825   }
 826   os_ << ")";
 827   return NULL;
 828 }
 829
 830
 831 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
 832   os_ << AsUC16(that.from());
 833   if (!that.IsSingleton()) {
 834     os_ << "-" << AsUC16(that.to());
 835   }
 836 }
 837
 838
 839
 840 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
 841                                           void* data) {
 842   if (that->is_negated()) os_ << "^";
 843   os_ << "[";
 844   for (int i = 0; i < that->ranges(zone_)->length(); i++) {
 845     if (i > 0) os_ << " ";
 846     VisitCharacterRange(that->ranges(zone_)->at(i));
 847   }
 848   os_ << "]";
 849   return NULL;
 850 }
 851
 852
 853 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
 854   switch (that->assertion_type()) {
 855     case RegExpAssertion::START_OF_INPUT:
 856       os_ << "@^i";
 857       break;
 858     case RegExpAssertion::END_OF_INPUT:
 859       os_ << "@$i";
 860       break;
 861     case RegExpAssertion::START_OF_LINE:
 862       os_ << "@^l";
 863       break;
 864     case RegExpAssertion::END_OF_LINE:
 865       os_ << "@$l";
 866        break;
 867     case RegExpAssertion::BOUNDARY:
 868       os_ << "@b";
 869       break;
 870     case RegExpAssertion::NON_BOUNDARY:
 871       os_ << "@B";
 872       break;
 873   }
 874   return NULL;
 875 }
 876
 877
 878 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
 879   os_ << "'";
 880   Vector<const uc16> chardata = that->data();
 881   for (int i = 0; i < chardata.length(); i++) {
 882     os_ << AsUC16(chardata[i]);
 883   }
 884   os_ << "'";
 885   return NULL;
 886 }
 887
 888
 889 void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
 890   if (that->elements()->length() == 1) {
 891     that->elements()->at(0).tree()->Accept(this, data);
 892   } else {
 893     os_ << "(!";
 894     for (int i = 0; i < that->elements()->length(); i++) {
 895       os_ << " ";
 896       that->elements()->at(i).tree()->Accept(this, data);
 897     }
 898     os_ << ")";
 899   }
 900   return NULL;
 901 }
 902
 903
 904 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
 905   os_ << "(# " << that->min() << " ";
 906   if (that->max() == RegExpTree::kInfinity) {
 907     os_ << "- ";
 908   } else {
 909     os_ << that->max() << " ";
 910   }
 911   os_ << (that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
 912   that->body()->Accept(this, data);
 913   os_ << ")";
 914   return NULL;
 915 }
 916
 917
 918 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
 919   os_ << "(^ ";
 920   that->body()->Accept(this, data);
 921   os_ << ")";
 922   return NULL;
 923 }
 924
 925
 926 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
 927   os_ << "(-> " << (that->is_positive() ? "+ " : "- ");
 928   that->body()->Accept(this, data);
 929   os_ << ")";
 930   return NULL;
 931 }
 932
 933
 934 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
 935                                          void* data) {
 936   os_ << "(<- " << that->index() << ")";
 937   return NULL;
 938 }
 939
 940
 941 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
 942   os_ << '%';
 943   return NULL;
 944 }
 945
 946
 947 std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) {  // NOLINT
 948   RegExpUnparser unparser(os, zone);
 949   Accept(&unparser, NULL);
 950   return os;
 951 }
 952
 953
 954 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
 955     : alternatives_(alternatives) {
 956   DCHECK(alternatives->length() > 1);
 957   RegExpTree* first_alternative = alternatives->at(0);
 958   min_match_ = first_alternative->min_match();
 959   max_match_ = first_alternative->max_match();
 960   for (int i = 1; i < alternatives->length(); i++) {
 961     RegExpTree* alternative = alternatives->at(i);
 962     min_match_ = Min(min_match_, alternative->min_match());
 963     max_match_ = Max(max_match_, alternative->max_match());
 964   }
 965 }
 966
 967
 968 static int IncreaseBy(int previous, int increase) {
 969   if (RegExpTree::kInfinity - previous < increase) {
 970     return RegExpTree::kInfinity;
 971   } else {
 972     return previous + increase;
 973   }
 974 }
 975
 976 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
 977     : nodes_(nodes) {
 978   DCHECK(nodes->length() > 1);
 979   min_match_ = 0;
 980   max_match_ = 0;
 981   for (int i = 0; i < nodes->length(); i++) {
 982     RegExpTree* node = nodes->at(i);
 983     int node_min_match = node->min_match();
 984     min_match_ = IncreaseBy(min_match_, node_min_match);
 985     int node_max_match = node->max_match();
 986     max_match_ = IncreaseBy(max_match_, node_max_match);
 987   }
 988 }
 989
 990
 991 CaseClause::CaseClause(Zone* zone, Expression* label,
 992                        ZoneList<Statement*>* statements, int pos)
 993     : Expression(zone, pos),
 994       label_(label),
 995       statements_(statements),
 996       compare_type_(Type::None(zone)) {}
 997
 998
 999 #define REGULAR_NODE(NodeType)                                   \
1000   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1001   }
1002 #define REGULAR_NODE_WITH_FEEDBACK_SLOTS(NodeType)               \
1003   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1004     add_slot_node(node);                                         \
1005   }
1006 #define DONT_OPTIMIZE_NODE(NodeType)                             \
1007   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1008     set_dont_crankshaft_reason(k##NodeType);                     \
1009     add_flag(kDontSelfOptimize);                                 \
1010   }
1011 #define DONT_OPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(NodeType)         \
1012   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1013     add_slot_node(node);                                         \
1014     set_dont_crankshaft_reason(k##NodeType);                     \
1015     add_flag(kDontSelfOptimize);                                 \
1016   }
1017 #define DONT_TURBOFAN_NODE(NodeType)                             \
1018   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1019     set_dont_crankshaft_reason(k##NodeType);                     \
1020     set_dont_turbofan_reason(k##NodeType);                       \
1021     add_flag(kDontSelfOptimize);                                 \
1022   }
1023 #define DONT_TURBOFAN_NODE_WITH_FEEDBACK_SLOTS(NodeType)         \
1024   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1025     add_slot_node(node);                                         \
1026     set_dont_crankshaft_reason(k##NodeType);                     \
1027     set_dont_turbofan_reason(k##NodeType);                       \
1028     add_flag(kDontSelfOptimize);                                 \
1029   }
1030 #define DONT_SELFOPTIMIZE_NODE(NodeType)                         \
1031   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1032     add_flag(kDontSelfOptimize);                                 \
1033   }
1034 #define DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(NodeType)     \
1035   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1036     add_slot_node(node);                                         \
1037     add_flag(kDontSelfOptimize);                                 \
1038   }
1039 #define DONT_CACHE_NODE(NodeType)                                \
1040   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1041     set_dont_crankshaft_reason(k##NodeType);                     \
1042     add_flag(kDontSelfOptimize);                                 \
1043     add_flag(kDontCache);                                        \
1044   }
1045
1046 REGULAR_NODE(VariableDeclaration)
1047 REGULAR_NODE(FunctionDeclaration)
1048 REGULAR_NODE(Block)
1049 REGULAR_NODE(ExpressionStatement)
1050 REGULAR_NODE(EmptyStatement)
1051 REGULAR_NODE(IfStatement)
1052 REGULAR_NODE(ContinueStatement)
1053 REGULAR_NODE(BreakStatement)
1054 REGULAR_NODE(ReturnStatement)
1055 REGULAR_NODE(SwitchStatement)
1056 REGULAR_NODE(CaseClause)
1057 REGULAR_NODE(Conditional)
1058 REGULAR_NODE(Literal)
1059 REGULAR_NODE(ArrayLiteral)
1060 REGULAR_NODE(ObjectLiteral)
1061 REGULAR_NODE(RegExpLiteral)
1062 REGULAR_NODE(FunctionLiteral)
1063 REGULAR_NODE(Assignment)
1064 REGULAR_NODE(Throw)
1065 REGULAR_NODE(UnaryOperation)
1066 REGULAR_NODE(CountOperation)
1067 REGULAR_NODE(BinaryOperation)
1068 REGULAR_NODE(CompareOperation)
1069 REGULAR_NODE(ThisFunction)
1070
1071 REGULAR_NODE_WITH_FEEDBACK_SLOTS(Call)
1072 REGULAR_NODE_WITH_FEEDBACK_SLOTS(CallNew)
1073 REGULAR_NODE_WITH_FEEDBACK_SLOTS(Property)
1074 // In theory, for VariableProxy we'd have to add:
1075 // if (node->var()->IsLookupSlot())
1076 //   set_dont_optimize_reason(kReferenceToAVariableWhichRequiresDynamicLookup);
1077 // But node->var() is usually not bound yet at VariableProxy creation time, and
1078 // LOOKUP variables only result from constructs that cannot be inlined anyway.
1079 REGULAR_NODE_WITH_FEEDBACK_SLOTS(VariableProxy)
1080
1081 // We currently do not optimize any modules.
1082 DONT_OPTIMIZE_NODE(ModuleDeclaration)
1083 DONT_OPTIMIZE_NODE(ImportDeclaration)
1084 DONT_OPTIMIZE_NODE(ExportDeclaration)
1085 DONT_OPTIMIZE_NODE(ModuleVariable)
1086 DONT_OPTIMIZE_NODE(ModulePath)
1087 DONT_OPTIMIZE_NODE(ModuleUrl)
1088 DONT_OPTIMIZE_NODE(ModuleStatement)
1089 DONT_OPTIMIZE_NODE(WithStatement)
1090 DONT_OPTIMIZE_NODE(DebuggerStatement)
1091 DONT_OPTIMIZE_NODE(NativeFunctionLiteral)
1092
1093 DONT_OPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(Yield)
1094
1095 // TODO(turbofan): Remove the dont_turbofan_reason once this list is empty.
1096 // This list must be kept in sync with Pipeline::GenerateCode.
1097 DONT_TURBOFAN_NODE(ForOfStatement)
1098 DONT_TURBOFAN_NODE(TryCatchStatement)
1099 DONT_TURBOFAN_NODE(TryFinallyStatement)
1100 DONT_TURBOFAN_NODE(ClassLiteral)
1101
1102 DONT_TURBOFAN_NODE_WITH_FEEDBACK_SLOTS(SuperReference)
1103
1104 DONT_SELFOPTIMIZE_NODE(DoWhileStatement)
1105 DONT_SELFOPTIMIZE_NODE(WhileStatement)
1106 DONT_SELFOPTIMIZE_NODE(ForStatement)
1107
1108 DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(ForInStatement)
1109
1110 DONT_CACHE_NODE(ModuleLiteral)
1111
1112
1113 void AstConstructionVisitor::VisitCallRuntime(CallRuntime* node) {
1114   add_slot_node(node);
1115   if (node->is_jsruntime()) {
1116     // Don't try to optimize JS runtime calls because we bailout on them.
1117     set_dont_crankshaft_reason(kCallToAJavaScriptRuntimeFunction);
1118   }
1119 }
1120
1121 #undef REGULAR_NODE
1122 #undef DONT_OPTIMIZE_NODE
1123 #undef DONT_SELFOPTIMIZE_NODE
1124 #undef DONT_CACHE_NODE
1125
1126
1127 uint32_t Literal::Hash() {
1128   return raw_value()->IsString()
1129              ? raw_value()->AsString()->hash()
1130              : ComputeLongHash(double_to_uint64(raw_value()->AsNumber()));
1131 }
1132
1133
1134 // static
1135 bool Literal::Match(void* literal1, void* literal2) {
1136   const AstValue* x = static_cast<Literal*>(literal1)->raw_value();
1137   const AstValue* y = static_cast<Literal*>(literal2)->raw_value();
1138   return (x->IsString() && y->IsString() && *x->AsString() == *y->AsString()) ||
1139          (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber());
1140 }
1141
1142
1143 } }  // namespace v8::internal