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