src/v8/src/ast.cc

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include "ast.h"
  29
  30 #include <cmath>  // For isfinite.
  31 #include "builtins.h"
  32 #include "code-stubs.h"
  33 #include "contexts.h"
  34 #include "conversions.h"
  35 #include "hashmap.h"
  36 #include "parser.h"
  37 #include "property-details.h"
  38 #include "property.h"
  39 #include "scopes.h"
  40 #include "string-stream.h"
  41 #include "type-info.h"
  42
  43 namespace v8 {
  44 namespace internal {
  45
  46 // ----------------------------------------------------------------------------
  47 // All the Accept member functions for each syntax tree node type.
  48
  49 #define DECL_ACCEPT(type)                                       \
  50   void type::Accept(AstVisitor* v) { v->Visit##type(this); }
  51 AST_NODE_LIST(DECL_ACCEPT)
  52 #undef DECL_ACCEPT
  53
  54
  55 // ----------------------------------------------------------------------------
  56 // Implementation of other node functionality.
  57
  58
  59 bool Expression::IsSmiLiteral() {
  60   return AsLiteral() != NULL && AsLiteral()->value()->IsSmi();
  61 }
  62
  63
  64 bool Expression::IsStringLiteral() {
  65   return AsLiteral() != NULL && AsLiteral()->value()->IsString();
  66 }
  67
  68
  69 bool Expression::IsNullLiteral() {
  70   return AsLiteral() != NULL && AsLiteral()->value()->IsNull();
  71 }
  72
  73
  74 bool Expression::IsUndefinedLiteral(Isolate* isolate) {
  75   VariableProxy* var_proxy = AsVariableProxy();
  76   if (var_proxy == NULL) return false;
  77   Variable* var = var_proxy->var();
  78   // The global identifier "undefined" is immutable. Everything
  79   // else could be reassigned.
  80   return var != NULL && var->location() == Variable::UNALLOCATED &&
  81          var_proxy->name()->Equals(isolate->heap()->undefined_string());
  82 }
  83
  84
  85 VariableProxy::VariableProxy(Isolate* isolate, Variable* var, int position)
  86     : Expression(isolate, position),
  87       name_(var->name()),
  88       var_(NULL),  // Will be set by the call to BindTo.
  89       is_this_(var->is_this()),
  90       is_trivial_(false),
  91       is_lvalue_(false),
  92       interface_(var->interface()) {
  93   BindTo(var);
  94 }
  95
  96
  97 VariableProxy::VariableProxy(Isolate* isolate,
  98                              Handle<String> name,
  99                              bool is_this,
 100                              Interface* interface,
 101                              int position)
 102     : Expression(isolate, position),
 103       name_(name),
 104       var_(NULL),
 105       is_this_(is_this),
 106       is_trivial_(false),
 107       is_lvalue_(false),
 108       interface_(interface) {
 109   // Names must be canonicalized for fast equality checks.
 110   ASSERT(name->IsInternalizedString());
 111 }
 112
 113
 114 void VariableProxy::BindTo(Variable* var) {
 115   ASSERT(var_ == NULL);  // must be bound only once
 116   ASSERT(var != NULL);  // must bind
 117   ASSERT(!FLAG_harmony_modules || interface_->IsUnified(var->interface()));
 118   ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name()));
 119   // Ideally CONST-ness should match. However, this is very hard to achieve
 120   // because we don't know the exact semantics of conflicting (const and
 121   // non-const) multiple variable declarations, const vars introduced via
 122   // eval() etc.  Const-ness and variable declarations are a complete mess
 123   // in JS. Sigh...
 124   var_ = var;
 125   var->set_is_used(true);
 126 }
 127
 128
 129 Assignment::Assignment(Isolate* isolate,
 130                        Token::Value op,
 131                        Expression* target,
 132                        Expression* value,
 133                        int pos)
 134     : Expression(isolate, pos),
 135       op_(op),
 136       target_(target),
 137       value_(value),
 138       binary_operation_(NULL),
 139       assignment_id_(GetNextId(isolate)),
 140       is_monomorphic_(false),
 141       is_uninitialized_(false),
 142       is_pre_monomorphic_(false),
 143       store_mode_(STANDARD_STORE) { }
 144
 145
 146 Token::Value Assignment::binary_op() const {
 147   switch (op_) {
 148     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
 149     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
 150     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
 151     case Token::ASSIGN_SHL: return Token::SHL;
 152     case Token::ASSIGN_SAR: return Token::SAR;
 153     case Token::ASSIGN_SHR: return Token::SHR;
 154     case Token::ASSIGN_ADD: return Token::ADD;
 155     case Token::ASSIGN_SUB: return Token::SUB;
 156     case Token::ASSIGN_MUL: return Token::MUL;
 157     case Token::ASSIGN_DIV: return Token::DIV;
 158     case Token::ASSIGN_MOD: return Token::MOD;
 159     default: UNREACHABLE();
 160   }
 161   return Token::ILLEGAL;
 162 }
 163
 164
 165 bool FunctionLiteral::AllowsLazyCompilation() {
 166   return scope()->AllowsLazyCompilation();
 167 }
 168
 169
 170 bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
 171   return scope()->AllowsLazyCompilationWithoutContext();
 172 }
 173
 174
 175 int FunctionLiteral::start_position() const {
 176   return scope()->start_position();
 177 }
 178
 179
 180 int FunctionLiteral::end_position() const {
 181   return scope()->end_position();
 182 }
 183
 184
 185 LanguageMode FunctionLiteral::language_mode() const {
 186   return scope()->language_mode();
 187 }
 188
 189
 190 ObjectLiteralProperty::ObjectLiteralProperty(Literal* key,
 191                                              Expression* value,
 192                                              Isolate* isolate) {
 193   emit_store_ = true;
 194   key_ = key;
 195   value_ = value;
 196   Object* k = *key->value();
 197   if (k->IsInternalizedString() &&
 198       isolate->heap()->proto_string()->Equals(String::cast(k))) {
 199     kind_ = PROTOTYPE;
 200   } else if (value_->AsMaterializedLiteral() != NULL) {
 201     kind_ = MATERIALIZED_LITERAL;
 202   } else if (value_->AsLiteral() != NULL) {
 203     kind_ = CONSTANT;
 204   } else {
 205     kind_ = COMPUTED;
 206   }
 207 }
 208
 209
 210 ObjectLiteralProperty::ObjectLiteralProperty(bool is_getter,
 211                                              FunctionLiteral* value) {
 212   emit_store_ = true;
 213   value_ = value;
 214   kind_ = is_getter ? GETTER : SETTER;
 215 }
 216
 217
 218 bool ObjectLiteral::Property::IsCompileTimeValue() {
 219   return kind_ == CONSTANT ||
 220       (kind_ == MATERIALIZED_LITERAL &&
 221        CompileTimeValue::IsCompileTimeValue(value_));
 222 }
 223
 224
 225 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
 226   emit_store_ = emit_store;
 227 }
 228
 229
 230 bool ObjectLiteral::Property::emit_store() {
 231   return emit_store_;
 232 }
 233
 234
 235 void ObjectLiteral::CalculateEmitStore(Zone* zone) {
 236   ZoneAllocationPolicy allocator(zone);
 237
 238   ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
 239                     allocator);
 240   for (int i = properties()->length() - 1; i >= 0; i--) {
 241     ObjectLiteral::Property* property = properties()->at(i);
 242     Literal* literal = property->key();
 243     if (literal->value()->IsNull()) continue;
 244     uint32_t hash = literal->Hash();
 245     // If the key of a computed property is in the table, do not emit
 246     // a store for the property later.
 247     if ((property->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL ||
 248          property->kind() == ObjectLiteral::Property::COMPUTED) &&
 249         table.Lookup(literal, hash, false, allocator) != NULL) {
 250       property->set_emit_store(false);
 251     } else {
 252       // Add key to the table.
 253       table.Lookup(literal, hash, true, allocator);
 254     }
 255   }
 256 }
 257
 258
 259 void TargetCollector::AddTarget(Label* target, Zone* zone) {
 260   // Add the label to the collector, but discard duplicates.
 261   int length = targets_.length();
 262   for (int i = 0; i < length; i++) {
 263     if (targets_[i] == target) return;
 264   }
 265   targets_.Add(target, zone);
 266 }
 267
 268
 269 void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 270   // TODO(olivf) If this Operation is used in a test context, then the
 271   // expression has a ToBoolean stub and we want to collect the type
 272   // information. However the GraphBuilder expects it to be on the instruction
 273   // corresponding to the TestContext, therefore we have to store it here and
 274   // not on the operand.
 275   set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
 276 }
 277
 278
 279 void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 280   // TODO(olivf) If this Operation is used in a test context, then the right
 281   // hand side has a ToBoolean stub and we want to collect the type information.
 282   // However the GraphBuilder expects it to be on the instruction corresponding
 283   // to the TestContext, therefore we have to store it here and not on the
 284   // right hand operand.
 285   set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
 286 }
 287
 288
 289 bool BinaryOperation::ResultOverwriteAllowed() {
 290   switch (op_) {
 291     case Token::COMMA:
 292     case Token::OR:
 293     case Token::AND:
 294       return false;
 295     case Token::BIT_OR:
 296     case Token::BIT_XOR:
 297     case Token::BIT_AND:
 298     case Token::SHL:
 299     case Token::SAR:
 300     case Token::SHR:
 301     case Token::ADD:
 302     case Token::SUB:
 303     case Token::MUL:
 304     case Token::DIV:
 305     case Token::MOD:
 306       return true;
 307     default:
 308       UNREACHABLE();
 309   }
 310   return false;
 311 }
 312
 313
 314 static bool IsTypeof(Expression* expr) {
 315   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 316   return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
 317 }
 318
 319
 320 // Check for the pattern: typeof <expression> equals <string literal>.
 321 static bool MatchLiteralCompareTypeof(Expression* left,
 322                                       Token::Value op,
 323                                       Expression* right,
 324                                       Expression** expr,
 325                                       Handle<String>* check) {
 326   if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
 327     *expr = left->AsUnaryOperation()->expression();
 328     *check = Handle<String>::cast(right->AsLiteral()->value());
 329     return true;
 330   }
 331   return false;
 332 }
 333
 334
 335 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
 336                                               Handle<String>* check) {
 337   return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
 338       MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
 339 }
 340
 341
 342 static bool IsVoidOfLiteral(Expression* expr) {
 343   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 344   return maybe_unary != NULL &&
 345       maybe_unary->op() == Token::VOID &&
 346       maybe_unary->expression()->AsLiteral() != NULL;
 347 }
 348
 349
 350 // Check for the pattern: void <literal> equals <expression> or
 351 // undefined equals <expression>
 352 static bool MatchLiteralCompareUndefined(Expression* left,
 353                                          Token::Value op,
 354                                          Expression* right,
 355                                          Expression** expr,
 356                                          Isolate* isolate) {
 357   if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
 358     *expr = right;
 359     return true;
 360   }
 361   if (left->IsUndefinedLiteral(isolate) && Token::IsEqualityOp(op)) {
 362     *expr = right;
 363     return true;
 364   }
 365   return false;
 366 }
 367
 368
 369 bool CompareOperation::IsLiteralCompareUndefined(
 370     Expression** expr, Isolate* isolate) {
 371   return MatchLiteralCompareUndefined(left_, op_, right_, expr, isolate) ||
 372       MatchLiteralCompareUndefined(right_, op_, left_, expr, isolate);
 373 }
 374
 375
 376 // Check for the pattern: null equals <expression>
 377 static bool MatchLiteralCompareNull(Expression* left,
 378                                     Token::Value op,
 379                                     Expression* right,
 380                                     Expression** expr) {
 381   if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
 382     *expr = right;
 383     return true;
 384   }
 385   return false;
 386 }
 387
 388
 389 bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
 390   return MatchLiteralCompareNull(left_, op_, right_, expr) ||
 391       MatchLiteralCompareNull(right_, op_, left_, expr);
 392 }
 393
 394
 395 // ----------------------------------------------------------------------------
 396 // Inlining support
 397
 398 bool Declaration::IsInlineable() const {
 399   return proxy()->var()->IsStackAllocated();
 400 }
 401
 402 bool FunctionDeclaration::IsInlineable() const {
 403   return false;
 404 }
 405
 406
 407 // ----------------------------------------------------------------------------
 408 // Recording of type feedback
 409
 410 // TODO(rossberg): all RecordTypeFeedback functions should disappear
 411 // once we use the common type field in the AST consistently.
 412
 413
 414 void ForInStatement::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 415   for_in_type_ = static_cast<ForInType>(oracle->ForInType(this));
 416 }
 417
 418
 419 void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 420   to_boolean_types_ = oracle->ToBooleanTypes(test_id());
 421 }
 422
 423
 424 void Property::RecordTypeFeedback(TypeFeedbackOracle* oracle,
 425                                   Zone* zone) {
 426   // Record type feedback from the oracle in the AST.
 427   is_uninitialized_ = oracle->LoadIsUninitialized(this);
 428   if (is_uninitialized_) return;
 429
 430   is_pre_monomorphic_ = oracle->LoadIsPreMonomorphic(this);
 431   is_monomorphic_ = oracle->LoadIsMonomorphicNormal(this);
 432   ASSERT(!is_pre_monomorphic_ || !is_monomorphic_);
 433   receiver_types_.Clear();
 434   if (key()->IsPropertyName()) {
 435     FunctionPrototypeStub proto_stub(Code::LOAD_IC);
 436     if (oracle->LoadIsStub(this, &proto_stub)) {
 437       is_function_prototype_ = true;
 438     } else {
 439       Literal* lit_key = key()->AsLiteral();
 440       ASSERT(lit_key != NULL && lit_key->value()->IsString());
 441       Handle<String> name = Handle<String>::cast(lit_key->value());
 442       oracle->LoadReceiverTypes(this, name, &receiver_types_);
 443     }
 444   } else if (oracle->LoadIsBuiltin(this, Builtins::kKeyedLoadIC_String)) {
 445     is_string_access_ = true;
 446   } else if (is_monomorphic_) {
 447     receiver_types_.Add(oracle->LoadMonomorphicReceiverType(this), zone);
 448   } else if (oracle->LoadIsPolymorphic(this)) {
 449     receiver_types_.Reserve(kMaxKeyedPolymorphism, zone);
 450     oracle->CollectKeyedReceiverTypes(PropertyFeedbackId(), &receiver_types_);
 451   }
 452 }
 453
 454
 455 void Assignment::RecordTypeFeedback(TypeFeedbackOracle* oracle,
 456                                     Zone* zone) {
 457   Property* prop = target()->AsProperty();
 458   ASSERT(prop != NULL);
 459   TypeFeedbackId id = AssignmentFeedbackId();
 460   is_uninitialized_ = oracle->StoreIsUninitialized(id);
 461   if (is_uninitialized_) return;
 462
 463   is_pre_monomorphic_ = oracle->StoreIsPreMonomorphic(id);
 464   is_monomorphic_ = oracle->StoreIsMonomorphicNormal(id);
 465   ASSERT(!is_pre_monomorphic_ || !is_monomorphic_);
 466   receiver_types_.Clear();
 467   if (prop->key()->IsPropertyName()) {
 468     Literal* lit_key = prop->key()->AsLiteral();
 469     ASSERT(lit_key != NULL && lit_key->value()->IsString());
 470     Handle<String> name = Handle<String>::cast(lit_key->value());
 471     oracle->StoreReceiverTypes(this, name, &receiver_types_);
 472   } else if (is_monomorphic_) {
 473     // Record receiver type for monomorphic keyed stores.
 474     receiver_types_.Add(oracle->StoreMonomorphicReceiverType(id), zone);
 475     store_mode_ = oracle->GetStoreMode(id);
 476   } else if (oracle->StoreIsKeyedPolymorphic(id)) {
 477     receiver_types_.Reserve(kMaxKeyedPolymorphism, zone);
 478     oracle->CollectKeyedReceiverTypes(id, &receiver_types_);
 479     store_mode_ = oracle->GetStoreMode(id);
 480   }
 481 }
 482
 483
 484 void CountOperation::RecordTypeFeedback(TypeFeedbackOracle* oracle,
 485                                         Zone* zone) {
 486   TypeFeedbackId id = CountStoreFeedbackId();
 487   is_monomorphic_ = oracle->StoreIsMonomorphicNormal(id);
 488   receiver_types_.Clear();
 489   if (is_monomorphic_) {
 490     // Record receiver type for monomorphic keyed stores.
 491     receiver_types_.Add(
 492         oracle->StoreMonomorphicReceiverType(id), zone);
 493   } else if (oracle->StoreIsKeyedPolymorphic(id)) {
 494     receiver_types_.Reserve(kMaxKeyedPolymorphism, zone);
 495     oracle->CollectKeyedReceiverTypes(id, &receiver_types_);
 496   } else {
 497     oracle->CollectPolymorphicStoreReceiverTypes(id, &receiver_types_);
 498   }
 499   store_mode_ = oracle->GetStoreMode(id);
 500   type_ = oracle->IncrementType(this);
 501 }
 502
 503
 504 void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 505   compare_type_ = oracle->ClauseType(CompareId());
 506 }
 507
 508
 509 bool Call::ComputeTarget(Handle<Map> type, Handle<String> name) {
 510   // If there is an interceptor, we can't compute the target for a direct call.
 511   if (type->has_named_interceptor()) return false;
 512
 513   if (check_type_ == RECEIVER_MAP_CHECK) {
 514     // For primitive checks the holder is set up to point to the corresponding
 515     // prototype object, i.e. one step of the algorithm below has been already
 516     // performed. For non-primitive checks we clear it to allow computing
 517     // targets for polymorphic calls.
 518     holder_ = Handle<JSObject>::null();
 519   }
 520   LookupResult lookup(type->GetIsolate());
 521   while (true) {
 522     // If a dictionary map is found in the prototype chain before the actual
 523     // target, a new target can always appear. In that case, bail out.
 524     // TODO(verwaest): Alternatively a runtime negative lookup on the normal
 525     // receiver or prototype could be added.
 526     if (type->is_dictionary_map()) return false;
 527     type->LookupDescriptor(NULL, *name, &lookup);
 528     if (lookup.IsFound()) {
 529       switch (lookup.type()) {
 530         case CONSTANT: {
 531           // We surely know the target for a constant function.
 532           Handle<Object> constant(lookup.GetConstantFromMap(*type),
 533                                   type->GetIsolate());
 534           if (constant->IsJSFunction()) {
 535             target_ = Handle<JSFunction>::cast(constant);
 536             return true;
 537           }
 538           // Fall through.
 539         }
 540         case NORMAL:
 541         case FIELD:
 542         case CALLBACKS:
 543         case HANDLER:
 544         case INTERCEPTOR:
 545           // We don't know the target.
 546           return false;
 547         case TRANSITION:
 548         case NONEXISTENT:
 549           UNREACHABLE();
 550           break;
 551       }
 552     }
 553     // If we reach the end of the prototype chain, we don't know the target.
 554     if (!type->prototype()->IsJSObject()) return false;
 555     // Go up the prototype chain, recording where we are currently.
 556     holder_ = Handle<JSObject>(JSObject::cast(type->prototype()));
 557     type = Handle<Map>(holder()->map());
 558   }
 559 }
 560
 561
 562 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
 563                                LookupResult* lookup) {
 564   target_ = Handle<JSFunction>::null();
 565   cell_ = Handle<Cell>::null();
 566   ASSERT(lookup->IsFound() &&
 567          lookup->type() == NORMAL &&
 568          lookup->holder() == *global);
 569   cell_ = Handle<Cell>(global->GetPropertyCell(lookup));
 570   if (cell_->value()->IsJSFunction()) {
 571     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
 572     // If the function is in new space we assume it's more likely to
 573     // change and thus prefer the general IC code.
 574     if (!lookup->isolate()->heap()->InNewSpace(*candidate)) {
 575       target_ = candidate;
 576       return true;
 577     }
 578   }
 579   return false;
 580 }
 581
 582
 583 Handle<JSObject> Call::GetPrototypeForPrimitiveCheck(
 584     CheckType check, Isolate* isolate) {
 585   v8::internal::Context* native_context = isolate->context()->native_context();
 586   JSFunction* function = NULL;
 587   switch (check) {
 588     case RECEIVER_MAP_CHECK:
 589       UNREACHABLE();
 590       break;
 591     case STRING_CHECK:
 592       function = native_context->string_function();
 593       break;
 594     case SYMBOL_CHECK:
 595       function = native_context->symbol_function();
 596       break;
 597     case NUMBER_CHECK:
 598       function = native_context->number_function();
 599       break;
 600     case BOOLEAN_CHECK:
 601       function = native_context->boolean_function();
 602       break;
 603   }
 604   ASSERT(function != NULL);
 605   return Handle<JSObject>(JSObject::cast(function->instance_prototype()));
 606 }
 607
 608
 609 void Call::RecordTypeFeedback(TypeFeedbackOracle* oracle,
 610                               CallKind call_kind) {
 611   is_monomorphic_ = oracle->CallIsMonomorphic(this);
 612   Property* property = expression()->AsProperty();
 613   if (property == NULL) {
 614     // Function call.  Specialize for monomorphic calls.
 615     if (is_monomorphic_) target_ = oracle->GetCallTarget(this);
 616   } else {
 617     // Method call.  Specialize for the receiver types seen at runtime.
 618     Literal* key = property->key()->AsLiteral();
 619     ASSERT(key != NULL && key->value()->IsString());
 620     Handle<String> name = Handle<String>::cast(key->value());
 621     check_type_ = oracle->GetCallCheckType(this);
 622     receiver_types_.Clear();
 623     if (check_type_ == RECEIVER_MAP_CHECK) {
 624       oracle->CallReceiverTypes(this, name, call_kind, &receiver_types_);
 625       is_monomorphic_ = is_monomorphic_ && receiver_types_.length() > 0;
 626     } else {
 627       holder_ = GetPrototypeForPrimitiveCheck(check_type_, oracle->isolate());
 628       receiver_types_.Add(handle(holder_->map()), oracle->zone());
 629     }
 630 #ifdef ENABLE_SLOW_ASSERTS
 631     if (FLAG_enable_slow_asserts) {
 632       int length = receiver_types_.length();
 633       for (int i = 0; i < length; i++) {
 634         Handle<Map> map = receiver_types_.at(i);
 635         ASSERT(!map.is_null() && *map != NULL);
 636       }
 637     }
 638 #endif
 639     if (is_monomorphic_) {
 640       Handle<Map> map = receiver_types_.first();
 641       is_monomorphic_ = ComputeTarget(map, name);
 642     }
 643   }
 644 }
 645
 646
 647 void CallNew::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 648   allocation_info_cell_ = oracle->GetCallNewAllocationInfoCell(this);
 649   is_monomorphic_ = oracle->CallNewIsMonomorphic(this);
 650   if (is_monomorphic_) {
 651     target_ = oracle->GetCallNewTarget(this);
 652     Object* value = allocation_info_cell_->value();
 653     ASSERT(!value->IsTheHole());
 654     if (value->IsAllocationSite()) {
 655       AllocationSite* site = AllocationSite::cast(value);
 656       elements_kind_ = site->GetElementsKind();
 657     }
 658   }
 659 }
 660
 661
 662 void ObjectLiteral::Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 663   receiver_type_ = oracle->ObjectLiteralStoreIsMonomorphic(this)
 664       ? oracle->GetObjectLiteralStoreMap(this)
 665       : Handle<Map>::null();
 666 }
 667
 668
 669 // ----------------------------------------------------------------------------
 670 // Implementation of AstVisitor
 671
 672 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
 673   for (int i = 0; i < declarations->length(); i++) {
 674     Visit(declarations->at(i));
 675   }
 676 }
 677
 678
 679 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
 680   for (int i = 0; i < statements->length(); i++) {
 681     Statement* stmt = statements->at(i);
 682     Visit(stmt);
 683     if (stmt->IsJump()) break;
 684   }
 685 }
 686
 687
 688 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
 689   for (int i = 0; i < expressions->length(); i++) {
 690     // The variable statement visiting code may pass NULL expressions
 691     // to this code. Maybe this should be handled by introducing an
 692     // undefined expression or literal?  Revisit this code if this
 693     // changes
 694     Expression* expression = expressions->at(i);
 695     if (expression != NULL) Visit(expression);
 696   }
 697 }
 698
 699
 700 // ----------------------------------------------------------------------------
 701 // Regular expressions
 702
 703 #define MAKE_ACCEPT(Name)                                            \
 704   void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) {   \
 705     return visitor->Visit##Name(this, data);                         \
 706   }
 707 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
 708 #undef MAKE_ACCEPT
 709
 710 #define MAKE_TYPE_CASE(Name)                                         \
 711   RegExp##Name* RegExpTree::As##Name() {                             \
 712     return NULL;                                                     \
 713   }                                                                  \
 714   bool RegExpTree::Is##Name() { return false; }
 715 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 716 #undef MAKE_TYPE_CASE
 717
 718 #define MAKE_TYPE_CASE(Name)                                        \
 719   RegExp##Name* RegExp##Name::As##Name() {                          \
 720     return this;                                                    \
 721   }                                                                 \
 722   bool RegExp##Name::Is##Name() { return true; }
 723 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
 724 #undef MAKE_TYPE_CASE
 725
 726
 727 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
 728   Interval result = Interval::Empty();
 729   for (int i = 0; i < children->length(); i++)
 730     result = result.Union(children->at(i)->CaptureRegisters());
 731   return result;
 732 }
 733
 734
 735 Interval RegExpAlternative::CaptureRegisters() {
 736   return ListCaptureRegisters(nodes());
 737 }
 738
 739
 740 Interval RegExpDisjunction::CaptureRegisters() {
 741   return ListCaptureRegisters(alternatives());
 742 }
 743
 744
 745 Interval RegExpLookahead::CaptureRegisters() {
 746   return body()->CaptureRegisters();
 747 }
 748
 749
 750 Interval RegExpCapture::CaptureRegisters() {
 751   Interval self(StartRegister(index()), EndRegister(index()));
 752   return self.Union(body()->CaptureRegisters());
 753 }
 754
 755
 756 Interval RegExpQuantifier::CaptureRegisters() {
 757   return body()->CaptureRegisters();
 758 }
 759
 760
 761 bool RegExpAssertion::IsAnchoredAtStart() {
 762   return assertion_type() == RegExpAssertion::START_OF_INPUT;
 763 }
 764
 765
 766 bool RegExpAssertion::IsAnchoredAtEnd() {
 767   return assertion_type() == RegExpAssertion::END_OF_INPUT;
 768 }
 769
 770
 771 bool RegExpAlternative::IsAnchoredAtStart() {
 772   ZoneList<RegExpTree*>* nodes = this->nodes();
 773   for (int i = 0; i < nodes->length(); i++) {
 774     RegExpTree* node = nodes->at(i);
 775     if (node->IsAnchoredAtStart()) { return true; }
 776     if (node->max_match() > 0) { return false; }
 777   }
 778   return false;
 779 }
 780
 781
 782 bool RegExpAlternative::IsAnchoredAtEnd() {
 783   ZoneList<RegExpTree*>* nodes = this->nodes();
 784   for (int i = nodes->length() - 1; i >= 0; i--) {
 785     RegExpTree* node = nodes->at(i);
 786     if (node->IsAnchoredAtEnd()) { return true; }
 787     if (node->max_match() > 0) { return false; }
 788   }
 789   return false;
 790 }
 791
 792
 793 bool RegExpDisjunction::IsAnchoredAtStart() {
 794   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 795   for (int i = 0; i < alternatives->length(); i++) {
 796     if (!alternatives->at(i)->IsAnchoredAtStart())
 797       return false;
 798   }
 799   return true;
 800 }
 801
 802
 803 bool RegExpDisjunction::IsAnchoredAtEnd() {
 804   ZoneList<RegExpTree*>* alternatives = this->alternatives();
 805   for (int i = 0; i < alternatives->length(); i++) {
 806     if (!alternatives->at(i)->IsAnchoredAtEnd())
 807       return false;
 808   }
 809   return true;
 810 }
 811
 812
 813 bool RegExpLookahead::IsAnchoredAtStart() {
 814   return is_positive() && body()->IsAnchoredAtStart();
 815 }
 816
 817
 818 bool RegExpCapture::IsAnchoredAtStart() {
 819   return body()->IsAnchoredAtStart();
 820 }
 821
 822
 823 bool RegExpCapture::IsAnchoredAtEnd() {
 824   return body()->IsAnchoredAtEnd();
 825 }
 826
 827
 828 // Convert regular expression trees to a simple sexp representation.
 829 // This representation should be different from the input grammar
 830 // in as many cases as possible, to make it more difficult for incorrect
 831 // parses to look as correct ones which is likely if the input and
 832 // output formats are alike.
 833 class RegExpUnparser V8_FINAL : public RegExpVisitor {
 834  public:
 835   explicit RegExpUnparser(Zone* zone);
 836   void VisitCharacterRange(CharacterRange that);
 837   SmartArrayPointer<const char> ToString() { return stream_.ToCString(); }
 838 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*,          \
 839                                                   void* data) V8_OVERRIDE;
 840   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 841 #undef MAKE_CASE
 842  private:
 843   StringStream* stream() { return &stream_; }
 844   HeapStringAllocator alloc_;
 845   StringStream stream_;
 846   Zone* zone_;
 847 };
 848
 849
 850 RegExpUnparser::RegExpUnparser(Zone* zone) : stream_(&alloc_), zone_(zone) {
 851 }
 852
 853
 854 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
 855   stream()->Add("(|");
 856   for (int i = 0; i <  that->alternatives()->length(); i++) {
 857     stream()->Add(" ");
 858     that->alternatives()->at(i)->Accept(this, data);
 859   }
 860   stream()->Add(")");
 861   return NULL;
 862 }
 863
 864
 865 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
 866   stream()->Add("(:");
 867   for (int i = 0; i <  that->nodes()->length(); i++) {
 868     stream()->Add(" ");
 869     that->nodes()->at(i)->Accept(this, data);
 870   }
 871   stream()->Add(")");
 872   return NULL;
 873 }
 874
 875
 876 void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
 877   stream()->Add("%k", that.from());
 878   if (!that.IsSingleton()) {
 879     stream()->Add("-%k", that.to());
 880   }
 881 }
 882
 883
 884
 885 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
 886                                           void* data) {
 887   if (that->is_negated())
 888     stream()->Add("^");
 889   stream()->Add("[");
 890   for (int i = 0; i < that->ranges(zone_)->length(); i++) {
 891     if (i > 0) stream()->Add(" ");
 892     VisitCharacterRange(that->ranges(zone_)->at(i));
 893   }
 894   stream()->Add("]");
 895   return NULL;
 896 }
 897
 898
 899 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
 900   switch (that->assertion_type()) {
 901     case RegExpAssertion::START_OF_INPUT:
 902       stream()->Add("@^i");
 903       break;
 904     case RegExpAssertion::END_OF_INPUT:
 905       stream()->Add("@$i");
 906       break;
 907     case RegExpAssertion::START_OF_LINE:
 908       stream()->Add("@^l");
 909       break;
 910     case RegExpAssertion::END_OF_LINE:
 911       stream()->Add("@$l");
 912        break;
 913     case RegExpAssertion::BOUNDARY:
 914       stream()->Add("@b");
 915       break;
 916     case RegExpAssertion::NON_BOUNDARY:
 917       stream()->Add("@B");
 918       break;
 919   }
 920   return NULL;
 921 }
 922
 923
 924 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
 925   stream()->Add("'");
 926   Vector<const uc16> chardata = that->data();
 927   for (int i = 0; i < chardata.length(); i++) {
 928     stream()->Add("%k", chardata[i]);
 929   }
 930   stream()->Add("'");
 931   return NULL;
 932 }
 933
 934
 935 void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
 936   if (that->elements()->length() == 1) {
 937     that->elements()->at(0).tree()->Accept(this, data);
 938   } else {
 939     stream()->Add("(!");
 940     for (int i = 0; i < that->elements()->length(); i++) {
 941       stream()->Add(" ");
 942       that->elements()->at(i).tree()->Accept(this, data);
 943     }
 944     stream()->Add(")");
 945   }
 946   return NULL;
 947 }
 948
 949
 950 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
 951   stream()->Add("(# %i ", that->min());
 952   if (that->max() == RegExpTree::kInfinity) {
 953     stream()->Add("- ");
 954   } else {
 955     stream()->Add("%i ", that->max());
 956   }
 957   stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
 958   that->body()->Accept(this, data);
 959   stream()->Add(")");
 960   return NULL;
 961 }
 962
 963
 964 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
 965   stream()->Add("(^ ");
 966   that->body()->Accept(this, data);
 967   stream()->Add(")");
 968   return NULL;
 969 }
 970
 971
 972 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) {
 973   stream()->Add("(-> ");
 974   stream()->Add(that->is_positive() ? "+ " : "- ");
 975   that->body()->Accept(this, data);
 976   stream()->Add(")");
 977   return NULL;
 978 }
 979
 980
 981 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
 982                                          void* data) {
 983   stream()->Add("(<- %i)", that->index());
 984   return NULL;
 985 }
 986
 987
 988 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
 989   stream()->Put('%');
 990   return NULL;
 991 }
 992
 993
 994 SmartArrayPointer<const char> RegExpTree::ToString(Zone* zone) {
 995   RegExpUnparser unparser(zone);
 996   Accept(&unparser, NULL);
 997   return unparser.ToString();
 998 }
 999
1000
1001 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
1002     : alternatives_(alternatives) {
1003   ASSERT(alternatives->length() > 1);
1004   RegExpTree* first_alternative = alternatives->at(0);
1005   min_match_ = first_alternative->min_match();
1006   max_match_ = first_alternative->max_match();
1007   for (int i = 1; i < alternatives->length(); i++) {
1008     RegExpTree* alternative = alternatives->at(i);
1009     min_match_ = Min(min_match_, alternative->min_match());
1010     max_match_ = Max(max_match_, alternative->max_match());
1011   }
1012 }
1013
1014
1015 static int IncreaseBy(int previous, int increase) {
1016   if (RegExpTree::kInfinity - previous < increase) {
1017     return RegExpTree::kInfinity;
1018   } else {
1019     return previous + increase;
1020   }
1021 }
1022
1023 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
1024     : nodes_(nodes) {
1025   ASSERT(nodes->length() > 1);
1026   min_match_ = 0;
1027   max_match_ = 0;
1028   for (int i = 0; i < nodes->length(); i++) {
1029     RegExpTree* node = nodes->at(i);
1030     int node_min_match = node->min_match();
1031     min_match_ = IncreaseBy(min_match_, node_min_match);
1032     int node_max_match = node->max_match();
1033     max_match_ = IncreaseBy(max_match_, node_max_match);
1034   }
1035 }
1036
1037
1038 CaseClause::CaseClause(Isolate* isolate,
1039                        Expression* label,
1040                        ZoneList<Statement*>* statements,
1041                        int pos)
1042     : AstNode(pos),
1043       label_(label),
1044       statements_(statements),
1045       compare_type_(Type::None(), isolate),
1046       compare_id_(AstNode::GetNextId(isolate)),
1047       entry_id_(AstNode::GetNextId(isolate)) {
1048 }
1049
1050
1051 #define REGULAR_NODE(NodeType) \
1052   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1053     increase_node_count(); \
1054   }
1055 #define DONT_OPTIMIZE_NODE(NodeType) \
1056   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1057     increase_node_count(); \
1058     set_dont_optimize_reason(k##NodeType); \
1059     add_flag(kDontInline); \
1060     add_flag(kDontSelfOptimize); \
1061   }
1062 #define DONT_SELFOPTIMIZE_NODE(NodeType) \
1063   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1064     increase_node_count(); \
1065     add_flag(kDontSelfOptimize); \
1066   }
1067 #define DONT_CACHE_NODE(NodeType) \
1068   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1069     increase_node_count(); \
1070     set_dont_optimize_reason(k##NodeType); \
1071     add_flag(kDontInline); \
1072     add_flag(kDontSelfOptimize); \
1073     add_flag(kDontCache); \
1074   }
1075
1076 REGULAR_NODE(VariableDeclaration)
1077 REGULAR_NODE(FunctionDeclaration)
1078 REGULAR_NODE(Block)
1079 REGULAR_NODE(ExpressionStatement)
1080 REGULAR_NODE(EmptyStatement)
1081 REGULAR_NODE(IfStatement)
1082 REGULAR_NODE(ContinueStatement)
1083 REGULAR_NODE(BreakStatement)
1084 REGULAR_NODE(ReturnStatement)
1085 REGULAR_NODE(SwitchStatement)
1086 REGULAR_NODE(CaseClause)
1087 REGULAR_NODE(Conditional)
1088 REGULAR_NODE(Literal)
1089 REGULAR_NODE(ArrayLiteral)
1090 REGULAR_NODE(ObjectLiteral)
1091 REGULAR_NODE(RegExpLiteral)
1092 REGULAR_NODE(FunctionLiteral)
1093 REGULAR_NODE(Assignment)
1094 REGULAR_NODE(Throw)
1095 REGULAR_NODE(Property)
1096 REGULAR_NODE(UnaryOperation)
1097 REGULAR_NODE(CountOperation)
1098 REGULAR_NODE(BinaryOperation)
1099 REGULAR_NODE(CompareOperation)
1100 REGULAR_NODE(ThisFunction)
1101 REGULAR_NODE(Call)
1102 REGULAR_NODE(CallNew)
1103 // In theory, for VariableProxy we'd have to add:
1104 // if (node->var()->IsLookupSlot()) add_flag(kDontInline);
1105 // But node->var() is usually not bound yet at VariableProxy creation time, and
1106 // LOOKUP variables only result from constructs that cannot be inlined anyway.
1107 REGULAR_NODE(VariableProxy)
1108
1109 // We currently do not optimize any modules.
1110 DONT_OPTIMIZE_NODE(ModuleDeclaration)
1111 DONT_OPTIMIZE_NODE(ImportDeclaration)
1112 DONT_OPTIMIZE_NODE(ExportDeclaration)
1113 DONT_OPTIMIZE_NODE(ModuleVariable)
1114 DONT_OPTIMIZE_NODE(ModulePath)
1115 DONT_OPTIMIZE_NODE(ModuleUrl)
1116 DONT_OPTIMIZE_NODE(ModuleStatement)
1117 DONT_OPTIMIZE_NODE(Yield)
1118 DONT_OPTIMIZE_NODE(WithStatement)
1119 DONT_OPTIMIZE_NODE(TryCatchStatement)
1120 DONT_OPTIMIZE_NODE(TryFinallyStatement)
1121 DONT_OPTIMIZE_NODE(DebuggerStatement)
1122 DONT_OPTIMIZE_NODE(NativeFunctionLiteral)
1123
1124 DONT_SELFOPTIMIZE_NODE(DoWhileStatement)
1125 DONT_SELFOPTIMIZE_NODE(WhileStatement)
1126 DONT_SELFOPTIMIZE_NODE(ForStatement)
1127 DONT_SELFOPTIMIZE_NODE(ForInStatement)
1128 DONT_SELFOPTIMIZE_NODE(ForOfStatement)
1129
1130 DONT_CACHE_NODE(ModuleLiteral)
1131
1132 void AstConstructionVisitor::VisitCallRuntime(CallRuntime* node) {
1133   increase_node_count();
1134   if (node->is_jsruntime()) {
1135     // Don't try to inline JS runtime calls because we don't (currently) even
1136     // optimize them.
1137     add_flag(kDontInline);
1138   } else if (node->function()->intrinsic_type == Runtime::INLINE &&
1139       (node->name()->IsOneByteEqualTo(
1140           STATIC_ASCII_VECTOR("_ArgumentsLength")) ||
1141        node->name()->IsOneByteEqualTo(STATIC_ASCII_VECTOR("_Arguments")))) {
1142     // Don't inline the %_ArgumentsLength or %_Arguments because their
1143     // implementation will not work.  There is no stack frame to get them
1144     // from.
1145     add_flag(kDontInline);
1146   }
1147 }
1148
1149 #undef REGULAR_NODE
1150 #undef DONT_OPTIMIZE_NODE
1151 #undef DONT_SELFOPTIMIZE_NODE
1152 #undef DONT_CACHE_NODE
1153
1154
1155 Handle<String> Literal::ToString() {
1156   if (value_->IsString()) return Handle<String>::cast(value_);
1157   ASSERT(value_->IsNumber());
1158   char arr[100];
1159   Vector<char> buffer(arr, ARRAY_SIZE(arr));
1160   const char* str;
1161   if (value_->IsSmi()) {
1162     // Optimization only, the heap number case would subsume this.
1163     OS::SNPrintF(buffer, "%d", Smi::cast(*value_)->value());
1164     str = arr;
1165   } else {
1166     str = DoubleToCString(value_->Number(), buffer);
1167   }
1168   return isolate_->factory()->NewStringFromAscii(CStrVector(str));
1169 }
1170
1171
1172 } }  // namespace v8::internal