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