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 43namespace v8 { 44namespace 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); } 51AST_NODE_LIST(DECL_ACCEPT) 52#undef DECL_ACCEPT 53 54 55// ---------------------------------------------------------------------------- 56// Implementation of other node functionality. 57 58 59bool Expression::IsSmiLiteral() { 60 return AsLiteral() != NULL && AsLiteral()->value()->IsSmi(); 61} 62 63 64bool Expression::IsStringLiteral() { 65 return AsLiteral() != NULL && AsLiteral()->value()->IsString(); 66} 67 68 69bool Expression::IsNullLiteral() { 70 return AsLiteral() != NULL && AsLiteral()->value()->IsNull(); 71} 72 73 74bool 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 85VariableProxy::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 98VariableProxy::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 116void 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 131Assignment::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 148Token::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 167bool FunctionLiteral::AllowsLazyCompilation() { 168 return scope()->AllowsLazyCompilation(); 169} 170 171 172bool FunctionLiteral::AllowsLazyCompilationWithoutContext() { 173 return scope()->AllowsLazyCompilationWithoutContext(); 174} 175 176 177int FunctionLiteral::start_position() const { 178 return scope()->start_position(); 179} 180 181 182int FunctionLiteral::end_position() const { 183 return scope()->end_position(); 184} 185 186 187LanguageMode FunctionLiteral::language_mode() const { 188 return scope()->language_mode(); 189} 190 191 192ObjectLiteralProperty::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 212ObjectLiteralProperty::ObjectLiteralProperty(bool is_getter, 213 FunctionLiteral* value) { 214 emit_store_ = true; 215 value_ = value; 216 kind_ = is_getter ? GETTER : SETTER; 217} 218 219 220bool ObjectLiteral::Property::IsCompileTimeValue() { 221 return kind_ == CONSTANT || 222 (kind_ == MATERIALIZED_LITERAL && 223 CompileTimeValue::IsCompileTimeValue(value_)); 224} 225 226 227void ObjectLiteral::Property::set_emit_store(bool emit_store) { 228 emit_store_ = emit_store; 229} 230 231 232bool ObjectLiteral::Property::emit_store() { 233 return emit_store_; 234} 235 236 237bool 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 246bool 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 264void 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 288void 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 298void 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 308void 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 318bool 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 343static 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>. 350static 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 364bool 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 371static 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> 381static 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 398bool 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> 406static 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 418bool 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 427bool Declaration::IsInlineable() const { 428 return proxy()->var()->IsStackAllocated(); 429} 430 431bool 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 443void ForInStatement::RecordTypeFeedback(TypeFeedbackOracle* oracle) { 444 for_in_type_ = static_cast<ForInType>(oracle->ForInType(this)); 445} 446 447 448void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) { 449 to_boolean_types_ = oracle->ToBooleanTypes(test_id()); 450} 451 452 453void 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 486void 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 512void 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 532void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) { 533 compare_type_ = oracle->ClauseType(CompareId()); 534} 535 536 537bool 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 590bool 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 611Handle<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 637void 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 677void 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 692void 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 702void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) { 703 for (int i = 0; i < declarations->length(); i++) { 704 Visit(declarations->at(i)); 705 } 706} 707 708 709void 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 718void 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 } 737FOR_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; } 745FOR_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; } 753FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 754#undef MAKE_TYPE_CASE 755 756 757static 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 765Interval RegExpAlternative::CaptureRegisters() { 766 return ListCaptureRegisters(nodes()); 767} 768 769 770Interval RegExpDisjunction::CaptureRegisters() { 771 return ListCaptureRegisters(alternatives()); 772} 773 774 775Interval RegExpLookahead::CaptureRegisters() { 776 return body()->CaptureRegisters(); 777} 778 779 780Interval RegExpCapture::CaptureRegisters() { 781 Interval self(StartRegister(index()), EndRegister(index())); 782 return self.Union(body()->CaptureRegisters()); 783} 784 785 786Interval RegExpQuantifier::CaptureRegisters() { 787 return body()->CaptureRegisters(); 788} 789 790 791bool RegExpAssertion::IsAnchoredAtStart() { 792 return assertion_type() == RegExpAssertion::START_OF_INPUT; 793} 794 795 796bool RegExpAssertion::IsAnchoredAtEnd() { 797 return assertion_type() == RegExpAssertion::END_OF_INPUT; 798} 799 800 801bool 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 812bool 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 823bool 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 833bool 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 843bool RegExpLookahead::IsAnchoredAtStart() { 844 return is_positive() && body()->IsAnchoredAtStart(); 845} 846 847 848bool RegExpCapture::IsAnchoredAtStart() { 849 return body()->IsAnchoredAtStart(); 850} 851 852 853bool 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. 863class 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 879RegExpUnparser::RegExpUnparser(Zone* zone) : stream_(&alloc_), zone_(zone) { 880} 881 882 883void* 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 894void* 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 905void 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 914void* 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 928void* 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 953void* 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 964void* 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 979void* 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 993void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { 994 stream()->Add("(^ "); 995 that->body()->Accept(this, data); 996 stream()->Add(")"); 997 return NULL; 998} 999 1000 1001void* 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 1010void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, 1011 void* data) { 1012 stream()->Add("(<- %i)", that->index()); 1013 return NULL; 1014} 1015 1016 1017void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { 1018 stream()->Put('%'); 1019 return NULL; 1020} 1021 1022 1023SmartArrayPointer<const char> RegExpTree::ToString(Zone* zone) { 1024 RegExpUnparser unparser(zone); 1025 Accept(&unparser, NULL); 1026 return unparser.ToString(); 1027} 1028 1029 1030RegExpDisjunction::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 1044static 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 1052RegExpAlternative::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 1067CaseClause::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 1105REGULAR_NODE(VariableDeclaration) 1106REGULAR_NODE(FunctionDeclaration) 1107REGULAR_NODE(Block) 1108REGULAR_NODE(ExpressionStatement) 1109REGULAR_NODE(EmptyStatement) 1110REGULAR_NODE(IfStatement) 1111REGULAR_NODE(ContinueStatement) 1112REGULAR_NODE(BreakStatement) 1113REGULAR_NODE(ReturnStatement) 1114REGULAR_NODE(SwitchStatement) 1115REGULAR_NODE(Conditional) 1116REGULAR_NODE(Literal) 1117REGULAR_NODE(ArrayLiteral) 1118REGULAR_NODE(ObjectLiteral) 1119REGULAR_NODE(RegExpLiteral) 1120REGULAR_NODE(FunctionLiteral) 1121REGULAR_NODE(Assignment) 1122REGULAR_NODE(Throw) 1123REGULAR_NODE(Property) 1124REGULAR_NODE(UnaryOperation) 1125REGULAR_NODE(CountOperation) 1126REGULAR_NODE(BinaryOperation) 1127REGULAR_NODE(CompareOperation) 1128REGULAR_NODE(ThisFunction) 1129REGULAR_NODE(Call) 1130REGULAR_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. 1135REGULAR_NODE(VariableProxy) 1136 1137// We currently do not optimize any modules. 1138DONT_OPTIMIZE_NODE(ModuleDeclaration) 1139DONT_OPTIMIZE_NODE(ImportDeclaration) 1140DONT_OPTIMIZE_NODE(ExportDeclaration) 1141DONT_OPTIMIZE_NODE(ModuleVariable) 1142DONT_OPTIMIZE_NODE(ModulePath) 1143DONT_OPTIMIZE_NODE(ModuleUrl) 1144DONT_OPTIMIZE_NODE(ModuleStatement) 1145DONT_OPTIMIZE_NODE(Yield) 1146DONT_OPTIMIZE_NODE(WithStatement) 1147DONT_OPTIMIZE_NODE(TryCatchStatement) 1148DONT_OPTIMIZE_NODE(TryFinallyStatement) 1149DONT_OPTIMIZE_NODE(DebuggerStatement) 1150DONT_OPTIMIZE_NODE(SharedFunctionInfoLiteral) 1151 1152DONT_SELFOPTIMIZE_NODE(DoWhileStatement) 1153DONT_SELFOPTIMIZE_NODE(WhileStatement) 1154DONT_SELFOPTIMIZE_NODE(ForStatement) 1155DONT_SELFOPTIMIZE_NODE(ForInStatement) 1156DONT_SELFOPTIMIZE_NODE(ForOfStatement) 1157 1158DONT_CACHE_NODE(ModuleLiteral) 1159 1160void 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 1183Handle<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