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() const {
  60   return AsLiteral() != NULL && AsLiteral()->value()->IsSmi();
  61 }
  62
  63
  64 bool Expression::IsStringLiteral() const {
  65   return AsLiteral() != NULL && AsLiteral()->value()->IsString();
  66 }
  67
  68
  69 bool Expression::IsNullLiteral() const {
  70   return AsLiteral() != NULL && AsLiteral()->value()->IsNull();
  71 }
  72
  73
  74 bool Expression::IsUndefinedLiteral(Isolate* isolate) const {
  75   const 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(Zone* zone, Variable* var, int position)
  86     : Expression(zone, 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(Zone* zone,
  98                              Handle<String> name,
  99                              bool is_this,
 100                              Interface* interface,
 101                              int position)
 102     : Expression(zone, 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(Zone* zone,
 130                        Token::Value op,
 131                        Expression* target,
 132                        Expression* value,
 133                        int pos)
 134     : Expression(zone, pos),
 135       op_(op),
 136       target_(target),
 137       value_(value),
 138       binary_operation_(NULL),
 139       assignment_id_(GetNextId(zone)),
 140       is_uninitialized_(false),
 141       store_mode_(STANDARD_STORE) { }
 142
 143
 144 Token::Value Assignment::binary_op() const {
 145   switch (op_) {
 146     case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
 147     case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
 148     case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
 149     case Token::ASSIGN_SHL: return Token::SHL;
 150     case Token::ASSIGN_SAR: return Token::SAR;
 151     case Token::ASSIGN_SHR: return Token::SHR;
 152     case Token::ASSIGN_ADD: return Token::ADD;
 153     case Token::ASSIGN_SUB: return Token::SUB;
 154     case Token::ASSIGN_MUL: return Token::MUL;
 155     case Token::ASSIGN_DIV: return Token::DIV;
 156     case Token::ASSIGN_MOD: return Token::MOD;
 157     default: UNREACHABLE();
 158   }
 159   return Token::ILLEGAL;
 160 }
 161
 162
 163 bool FunctionLiteral::AllowsLazyCompilation() {
 164   return scope()->AllowsLazyCompilation();
 165 }
 166
 167
 168 bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
 169   return scope()->AllowsLazyCompilationWithoutContext();
 170 }
 171
 172
 173 int FunctionLiteral::start_position() const {
 174   return scope()->start_position();
 175 }
 176
 177
 178 int FunctionLiteral::end_position() const {
 179   return scope()->end_position();
 180 }
 181
 182
 183 StrictMode FunctionLiteral::strict_mode() const {
 184   return scope()->strict_mode();
 185 }
 186
 187
 188 void FunctionLiteral::InitializeSharedInfo(
 189     Handle<Code> unoptimized_code) {
 190   for (RelocIterator it(*unoptimized_code); !it.done(); it.next()) {
 191     RelocInfo* rinfo = it.rinfo();
 192     if (rinfo->rmode() != RelocInfo::EMBEDDED_OBJECT) continue;
 193     Object* obj = rinfo->target_object();
 194     if (obj->IsSharedFunctionInfo()) {
 195       SharedFunctionInfo* shared = SharedFunctionInfo::cast(obj);
 196       if (shared->start_position() == start_position()) {
 197         shared_info_ = Handle<SharedFunctionInfo>(shared);
 198         break;
 199       }
 200     }
 201   }
 202 }
 203
 204
 205 ObjectLiteralProperty::ObjectLiteralProperty(
 206     Zone* zone, Literal* key, Expression* value) {
 207   emit_store_ = true;
 208   key_ = key;
 209   value_ = value;
 210   Object* k = *key->value();
 211   if (k->IsInternalizedString() &&
 212       zone->isolate()->heap()->proto_string()->Equals(String::cast(k))) {
 213     kind_ = PROTOTYPE;
 214   } else if (value_->AsMaterializedLiteral() != NULL) {
 215     kind_ = MATERIALIZED_LITERAL;
 216   } else if (value_->AsLiteral() != NULL) {
 217     kind_ = CONSTANT;
 218   } else {
 219     kind_ = COMPUTED;
 220   }
 221 }
 222
 223
 224 ObjectLiteralProperty::ObjectLiteralProperty(
 225     Zone* zone, bool is_getter, FunctionLiteral* value) {
 226   emit_store_ = true;
 227   value_ = value;
 228   kind_ = is_getter ? GETTER : SETTER;
 229 }
 230
 231
 232 bool ObjectLiteral::Property::IsCompileTimeValue() {
 233   return kind_ == CONSTANT ||
 234       (kind_ == MATERIALIZED_LITERAL &&
 235        CompileTimeValue::IsCompileTimeValue(value_));
 236 }
 237
 238
 239 void ObjectLiteral::Property::set_emit_store(bool emit_store) {
 240   emit_store_ = emit_store;
 241 }
 242
 243
 244 bool ObjectLiteral::Property::emit_store() {
 245   return emit_store_;
 246 }
 247
 248
 249 void ObjectLiteral::CalculateEmitStore(Zone* zone) {
 250   ZoneAllocationPolicy allocator(zone);
 251
 252   ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
 253                     allocator);
 254   for (int i = properties()->length() - 1; i >= 0; i--) {
 255     ObjectLiteral::Property* property = properties()->at(i);
 256     Literal* literal = property->key();
 257     if (literal->value()->IsNull()) continue;
 258     uint32_t hash = literal->Hash();
 259     // If the key of a computed property is in the table, do not emit
 260     // a store for the property later.
 261     if ((property->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL ||
 262          property->kind() == ObjectLiteral::Property::COMPUTED) &&
 263         table.Lookup(literal, hash, false, allocator) != NULL) {
 264       property->set_emit_store(false);
 265     } else {
 266       // Add key to the table.
 267       table.Lookup(literal, hash, true, allocator);
 268     }
 269   }
 270 }
 271
 272
 273 bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) {
 274   return property != NULL &&
 275          property->kind() != ObjectLiteral::Property::PROTOTYPE;
 276 }
 277
 278
 279 void ObjectLiteral::BuildConstantProperties(Isolate* isolate) {
 280   if (!constant_properties_.is_null()) return;
 281
 282   // Allocate a fixed array to hold all the constant properties.
 283   Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray(
 284       boilerplate_properties_ * 2, TENURED);
 285
 286   int position = 0;
 287   // Accumulate the value in local variables and store it at the end.
 288   bool is_simple = true;
 289   int depth_acc = 1;
 290   uint32_t max_element_index = 0;
 291   uint32_t elements = 0;
 292   for (int i = 0; i < properties()->length(); i++) {
 293     ObjectLiteral::Property* property = properties()->at(i);
 294     if (!IsBoilerplateProperty(property)) {
 295       is_simple = false;
 296       continue;
 297     }
 298     MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral();
 299     if (m_literal != NULL) {
 300       m_literal->BuildConstants(isolate);
 301       if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1;
 302     }
 303
 304     // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined
 305     // value for COMPUTED properties, the real value is filled in at
 306     // runtime. The enumeration order is maintained.
 307     Handle<Object> key = property->key()->value();
 308     Handle<Object> value = GetBoilerplateValue(property->value(), isolate);
 309
 310     // Ensure objects that may, at any point in time, contain fields with double
 311     // representation are always treated as nested objects. This is true for
 312     // computed fields (value is undefined), and smi and double literals
 313     // (value->IsNumber()).
 314     // TODO(verwaest): Remove once we can store them inline.
 315     if (FLAG_track_double_fields &&
 316         (value->IsNumber() || value->IsUninitialized())) {
 317       may_store_doubles_ = true;
 318     }
 319
 320     is_simple = is_simple && !value->IsUninitialized();
 321
 322     // Keep track of the number of elements in the object literal and
 323     // the largest element index.  If the largest element index is
 324     // much larger than the number of elements, creating an object
 325     // literal with fast elements will be a waste of space.
 326     uint32_t element_index = 0;
 327     if (key->IsString()
 328         && Handle<String>::cast(key)->AsArrayIndex(&element_index)
 329         && element_index > max_element_index) {
 330       max_element_index = element_index;
 331       elements++;
 332     } else if (key->IsSmi()) {
 333       int key_value = Smi::cast(*key)->value();
 334       if (key_value > 0
 335           && static_cast<uint32_t>(key_value) > max_element_index) {
 336         max_element_index = key_value;
 337       }
 338       elements++;
 339     }
 340
 341     // Add name, value pair to the fixed array.
 342     constant_properties->set(position++, *key);
 343     constant_properties->set(position++, *value);
 344   }
 345
 346   constant_properties_ = constant_properties;
 347   fast_elements_ =
 348       (max_element_index <= 32) || ((2 * elements) >= max_element_index);
 349   set_is_simple(is_simple);
 350   set_depth(depth_acc);
 351 }
 352
 353
 354 void ArrayLiteral::BuildConstantElements(Isolate* isolate) {
 355   if (!constant_elements_.is_null()) return;
 356
 357   // Allocate a fixed array to hold all the object literals.
 358   Handle<JSArray> array =
 359       isolate->factory()->NewJSArray(0, FAST_HOLEY_SMI_ELEMENTS);
 360   JSArray::Expand(array, values()->length());
 361
 362   // Fill in the literals.
 363   bool is_simple = true;
 364   int depth_acc = 1;
 365   bool is_holey = false;
 366   for (int i = 0, n = values()->length(); i < n; i++) {
 367     Expression* element = values()->at(i);
 368     MaterializedLiteral* m_literal = element->AsMaterializedLiteral();
 369     if (m_literal != NULL) {
 370       m_literal->BuildConstants(isolate);
 371       if (m_literal->depth() + 1 > depth_acc) {
 372         depth_acc = m_literal->depth() + 1;
 373       }
 374     }
 375     Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate);
 376     if (boilerplate_value->IsTheHole()) {
 377       is_holey = true;
 378     } else if (boilerplate_value->IsUninitialized()) {
 379       is_simple = false;
 380       JSObject::SetOwnElement(
 381           array, i, handle(Smi::FromInt(0), isolate), SLOPPY);
 382     } else {
 383       JSObject::SetOwnElement(array, i, boilerplate_value, SLOPPY);
 384     }
 385   }
 386
 387   Handle<FixedArrayBase> element_values(array->elements());
 388
 389   // Simple and shallow arrays can be lazily copied, we transform the
 390   // elements array to a copy-on-write array.
 391   if (is_simple && depth_acc == 1 && values()->length() > 0 &&
 392       array->HasFastSmiOrObjectElements()) {
 393     element_values->set_map(isolate->heap()->fixed_cow_array_map());
 394   }
 395
 396   // Remember both the literal's constant values as well as the ElementsKind
 397   // in a 2-element FixedArray.
 398   Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED);
 399
 400   ElementsKind kind = array->GetElementsKind();
 401   kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind);
 402
 403   literals->set(0, Smi::FromInt(kind));
 404   literals->set(1, *element_values);
 405
 406   constant_elements_ = literals;
 407   set_is_simple(is_simple);
 408   set_depth(depth_acc);
 409 }
 410
 411
 412 Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression,
 413                                                         Isolate* isolate) {
 414   if (expression->AsLiteral() != NULL) {
 415     return expression->AsLiteral()->value();
 416   }
 417   if (CompileTimeValue::IsCompileTimeValue(expression)) {
 418     return CompileTimeValue::GetValue(isolate, expression);
 419   }
 420   return isolate->factory()->uninitialized_value();
 421 }
 422
 423
 424 void MaterializedLiteral::BuildConstants(Isolate* isolate) {
 425   if (IsArrayLiteral()) {
 426     return AsArrayLiteral()->BuildConstantElements(isolate);
 427   }
 428   if (IsObjectLiteral()) {
 429     return AsObjectLiteral()->BuildConstantProperties(isolate);
 430   }
 431   ASSERT(IsRegExpLiteral());
 432   ASSERT(depth() >= 1);  // Depth should be initialized.
 433 }
 434
 435
 436 void TargetCollector::AddTarget(Label* target, Zone* zone) {
 437   // Add the label to the collector, but discard duplicates.
 438   int length = targets_.length();
 439   for (int i = 0; i < length; i++) {
 440     if (targets_[i] == target) return;
 441   }
 442   targets_.Add(target, zone);
 443 }
 444
 445
 446 void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 447   // TODO(olivf) If this Operation is used in a test context, then the
 448   // expression has a ToBoolean stub and we want to collect the type
 449   // information. However the GraphBuilder expects it to be on the instruction
 450   // corresponding to the TestContext, therefore we have to store it here and
 451   // not on the operand.
 452   set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
 453 }
 454
 455
 456 void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 457   // TODO(olivf) If this Operation is used in a test context, then the right
 458   // hand side has a ToBoolean stub and we want to collect the type information.
 459   // However the GraphBuilder expects it to be on the instruction corresponding
 460   // to the TestContext, therefore we have to store it here and not on the
 461   // right hand operand.
 462   set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
 463 }
 464
 465
 466 bool BinaryOperation::ResultOverwriteAllowed() const {
 467   switch (op_) {
 468     case Token::COMMA:
 469     case Token::OR:
 470     case Token::AND:
 471       return false;
 472     case Token::BIT_OR:
 473     case Token::BIT_XOR:
 474     case Token::BIT_AND:
 475     case Token::SHL:
 476     case Token::SAR:
 477     case Token::SHR:
 478     case Token::ADD:
 479     case Token::SUB:
 480     case Token::MUL:
 481     case Token::DIV:
 482     case Token::MOD:
 483       return true;
 484     default:
 485       UNREACHABLE();
 486   }
 487   return false;
 488 }
 489
 490
 491 static bool IsTypeof(Expression* expr) {
 492   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 493   return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
 494 }
 495
 496
 497 // Check for the pattern: typeof <expression> equals <string literal>.
 498 static bool MatchLiteralCompareTypeof(Expression* left,
 499                                       Token::Value op,
 500                                       Expression* right,
 501                                       Expression** expr,
 502                                       Handle<String>* check) {
 503   if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
 504     *expr = left->AsUnaryOperation()->expression();
 505     *check = Handle<String>::cast(right->AsLiteral()->value());
 506     return true;
 507   }
 508   return false;
 509 }
 510
 511
 512 bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
 513                                               Handle<String>* check) {
 514   return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
 515       MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
 516 }
 517
 518
 519 static bool IsVoidOfLiteral(Expression* expr) {
 520   UnaryOperation* maybe_unary = expr->AsUnaryOperation();
 521   return maybe_unary != NULL &&
 522       maybe_unary->op() == Token::VOID &&
 523       maybe_unary->expression()->AsLiteral() != NULL;
 524 }
 525
 526
 527 // Check for the pattern: void <literal> equals <expression> or
 528 // undefined equals <expression>
 529 static bool MatchLiteralCompareUndefined(Expression* left,
 530                                          Token::Value op,
 531                                          Expression* right,
 532                                          Expression** expr,
 533                                          Isolate* isolate) {
 534   if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
 535     *expr = right;
 536     return true;
 537   }
 538   if (left->IsUndefinedLiteral(isolate) && Token::IsEqualityOp(op)) {
 539     *expr = right;
 540     return true;
 541   }
 542   return false;
 543 }
 544
 545
 546 bool CompareOperation::IsLiteralCompareUndefined(
 547     Expression** expr, Isolate* isolate) {
 548   return MatchLiteralCompareUndefined(left_, op_, right_, expr, isolate) ||
 549       MatchLiteralCompareUndefined(right_, op_, left_, expr, isolate);
 550 }
 551
 552
 553 // Check for the pattern: null equals <expression>
 554 static bool MatchLiteralCompareNull(Expression* left,
 555                                     Token::Value op,
 556                                     Expression* right,
 557                                     Expression** expr) {
 558   if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
 559     *expr = right;
 560     return true;
 561   }
 562   return false;
 563 }
 564
 565
 566 bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
 567   return MatchLiteralCompareNull(left_, op_, right_, expr) ||
 568       MatchLiteralCompareNull(right_, op_, left_, expr);
 569 }
 570
 571
 572 // ----------------------------------------------------------------------------
 573 // Inlining support
 574
 575 bool Declaration::IsInlineable() const {
 576   return proxy()->var()->IsStackAllocated();
 577 }
 578
 579 bool FunctionDeclaration::IsInlineable() const {
 580   return false;
 581 }
 582
 583
 584 // ----------------------------------------------------------------------------
 585 // Recording of type feedback
 586
 587 // TODO(rossberg): all RecordTypeFeedback functions should disappear
 588 // once we use the common type field in the AST consistently.
 589
 590 void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
 591   to_boolean_types_ = oracle->ToBooleanTypes(test_id());
 592 }
 593
 594
 595 int Call::ComputeFeedbackSlotCount(Isolate* isolate) {
 596   CallType call_type = GetCallType(isolate);
 597   if (call_type == LOOKUP_SLOT_CALL || call_type == OTHER_CALL) {
 598     // Call only uses a slot in some cases.
 599     return 1;
 600   }
 601
 602   return 0;
 603 }
 604
 605
 606 Call::CallType Call::GetCallType(Isolate* isolate) const {
 607   VariableProxy* proxy = expression()->AsVariableProxy();
 608   if (proxy != NULL) {
 609     if (proxy->var()->is_possibly_eval(isolate)) {
 610       return POSSIBLY_EVAL_CALL;
 611     } else if (proxy->var()->IsUnallocated()) {
 612       return GLOBAL_CALL;
 613     } else if (proxy->var()->IsLookupSlot()) {
 614       return LOOKUP_SLOT_CALL;
 615     }
 616   }
 617
 618   Property* property = expression()->AsProperty();
 619   return property != NULL ? PROPERTY_CALL : OTHER_CALL;
 620 }
 621
 622
 623 bool Call::ComputeGlobalTarget(Handle<GlobalObject> global,
 624                                LookupResult* lookup) {
 625   target_ = Handle<JSFunction>::null();
 626   cell_ = Handle<Cell>::null();
 627   ASSERT(lookup->IsFound() &&
 628          lookup->type() == NORMAL &&
 629          lookup->holder() == *global);
 630   cell_ = Handle<Cell>(global->GetPropertyCell(lookup));
 631   if (cell_->value()->IsJSFunction()) {
 632     Handle<JSFunction> candidate(JSFunction::cast(cell_->value()));
 633     // If the function is in new space we assume it's more likely to
 634     // change and thus prefer the general IC code.
 635     if (!lookup->isolate()->heap()->InNewSpace(*candidate)) {
 636       target_ = candidate;
 637       return true;
 638     }
 639   }
 640   return false;
 641 }
 642
 643
 644 void CallNew::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 645   int allocation_site_feedback_slot = FLAG_pretenuring_call_new
 646       ? AllocationSiteFeedbackSlot()
 647       : CallNewFeedbackSlot();
 648   allocation_site_ =
 649       oracle->GetCallNewAllocationSite(allocation_site_feedback_slot);
 650   is_monomorphic_ = oracle->CallNewIsMonomorphic(CallNewFeedbackSlot());
 651   if (is_monomorphic_) {
 652     target_ = oracle->GetCallNewTarget(CallNewFeedbackSlot());
 653     if (!allocation_site_.is_null()) {
 654       elements_kind_ = allocation_site_->GetElementsKind();
 655     }
 656   }
 657 }
 658
 659
 660 void ObjectLiteral::Property::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
 661   TypeFeedbackId id = key()->LiteralFeedbackId();
 662   SmallMapList maps;
 663   oracle->CollectReceiverTypes(id, &maps);
 664   receiver_type_ = maps.length() == 1 ? maps.at(0)
 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(Zone* zone,
1039                        Expression* label,
1040                        ZoneList<Statement*>* statements,
1041                        int pos)
1042     : Expression(zone, pos),
1043       label_(label),
1044       statements_(statements),
1045       compare_type_(Type::None(zone)),
1046       compare_id_(AstNode::GetNextId(zone)),
1047       entry_id_(AstNode::GetNextId(zone)) {
1048 }
1049
1050
1051 #define REGULAR_NODE(NodeType) \
1052   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1053     increase_node_count(); \
1054   }
1055 #define REGULAR_NODE_WITH_FEEDBACK_SLOTS(NodeType) \
1056   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1057     increase_node_count(); \
1058     add_slot_node(node); \
1059   }
1060 #define DONT_OPTIMIZE_NODE(NodeType) \
1061   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1062     increase_node_count(); \
1063     set_dont_optimize_reason(k##NodeType); \
1064     add_flag(kDontInline); \
1065     add_flag(kDontSelfOptimize); \
1066   }
1067 #define DONT_SELFOPTIMIZE_NODE(NodeType) \
1068   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1069     increase_node_count(); \
1070     add_flag(kDontSelfOptimize); \
1071   }
1072 #define DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(NodeType) \
1073   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1074     increase_node_count(); \
1075     add_slot_node(node); \
1076     add_flag(kDontSelfOptimize); \
1077   }
1078 #define DONT_CACHE_NODE(NodeType) \
1079   void AstConstructionVisitor::Visit##NodeType(NodeType* node) { \
1080     increase_node_count(); \
1081     set_dont_optimize_reason(k##NodeType); \
1082     add_flag(kDontInline); \
1083     add_flag(kDontSelfOptimize); \
1084     add_flag(kDontCache); \
1085   }
1086
1087 REGULAR_NODE(VariableDeclaration)
1088 REGULAR_NODE(FunctionDeclaration)
1089 REGULAR_NODE(Block)
1090 REGULAR_NODE(ExpressionStatement)
1091 REGULAR_NODE(EmptyStatement)
1092 REGULAR_NODE(IfStatement)
1093 REGULAR_NODE(ContinueStatement)
1094 REGULAR_NODE(BreakStatement)
1095 REGULAR_NODE(ReturnStatement)
1096 REGULAR_NODE(SwitchStatement)
1097 REGULAR_NODE(CaseClause)
1098 REGULAR_NODE(Conditional)
1099 REGULAR_NODE(Literal)
1100 REGULAR_NODE(ArrayLiteral)
1101 REGULAR_NODE(ObjectLiteral)
1102 REGULAR_NODE(RegExpLiteral)
1103 REGULAR_NODE(FunctionLiteral)
1104 REGULAR_NODE(Assignment)
1105 REGULAR_NODE(Throw)
1106 REGULAR_NODE(Property)
1107 REGULAR_NODE(UnaryOperation)
1108 REGULAR_NODE(CountOperation)
1109 REGULAR_NODE(BinaryOperation)
1110 REGULAR_NODE(CompareOperation)
1111 REGULAR_NODE(ThisFunction)
1112 REGULAR_NODE_WITH_FEEDBACK_SLOTS(Call)
1113 REGULAR_NODE_WITH_FEEDBACK_SLOTS(CallNew)
1114 // In theory, for VariableProxy we'd have to add:
1115 // if (node->var()->IsLookupSlot()) add_flag(kDontInline);
1116 // But node->var() is usually not bound yet at VariableProxy creation time, and
1117 // LOOKUP variables only result from constructs that cannot be inlined anyway.
1118 REGULAR_NODE(VariableProxy)
1119
1120 // We currently do not optimize any modules.
1121 DONT_OPTIMIZE_NODE(ModuleDeclaration)
1122 DONT_OPTIMIZE_NODE(ImportDeclaration)
1123 DONT_OPTIMIZE_NODE(ExportDeclaration)
1124 DONT_OPTIMIZE_NODE(ModuleVariable)
1125 DONT_OPTIMIZE_NODE(ModulePath)
1126 DONT_OPTIMIZE_NODE(ModuleUrl)
1127 DONT_OPTIMIZE_NODE(ModuleStatement)
1128 DONT_OPTIMIZE_NODE(Yield)
1129 DONT_OPTIMIZE_NODE(WithStatement)
1130 DONT_OPTIMIZE_NODE(TryCatchStatement)
1131 DONT_OPTIMIZE_NODE(TryFinallyStatement)
1132 DONT_OPTIMIZE_NODE(DebuggerStatement)
1133 DONT_OPTIMIZE_NODE(NativeFunctionLiteral)
1134
1135 DONT_SELFOPTIMIZE_NODE(DoWhileStatement)
1136 DONT_SELFOPTIMIZE_NODE(WhileStatement)
1137 DONT_SELFOPTIMIZE_NODE(ForStatement)
1138 DONT_SELFOPTIMIZE_NODE_WITH_FEEDBACK_SLOTS(ForInStatement)
1139 DONT_SELFOPTIMIZE_NODE(ForOfStatement)
1140
1141 DONT_CACHE_NODE(ModuleLiteral)
1142
1143
1144 void AstConstructionVisitor::VisitCallRuntime(CallRuntime* node) {
1145   increase_node_count();
1146   if (node->is_jsruntime()) {
1147     // Don't try to inline JS runtime calls because we don't (currently) even
1148     // optimize them.
1149     add_flag(kDontInline);
1150   } else if (node->function()->intrinsic_type == Runtime::INLINE &&
1151       (node->name()->IsOneByteEqualTo(
1152           STATIC_ASCII_VECTOR("_ArgumentsLength")) ||
1153        node->name()->IsOneByteEqualTo(STATIC_ASCII_VECTOR("_Arguments")))) {
1154     // Don't inline the %_ArgumentsLength or %_Arguments because their
1155     // implementation will not work.  There is no stack frame to get them
1156     // from.
1157     add_flag(kDontInline);
1158   }
1159 }
1160
1161 #undef REGULAR_NODE
1162 #undef DONT_OPTIMIZE_NODE
1163 #undef DONT_SELFOPTIMIZE_NODE
1164 #undef DONT_CACHE_NODE
1165
1166
1167 Handle<String> Literal::ToString() {
1168   if (value_->IsString()) return Handle<String>::cast(value_);
1169   ASSERT(value_->IsNumber());
1170   char arr[100];
1171   Vector<char> buffer(arr, ARRAY_SIZE(arr));
1172   const char* str;
1173   if (value_->IsSmi()) {
1174     // Optimization only, the heap number case would subsume this.
1175     OS::SNPrintF(buffer, "%d", Smi::cast(*value_)->value());
1176     str = arr;
1177   } else {
1178     str = DoubleToCString(value_->Number(), buffer);
1179   }
1180   return isolate_->factory()->NewStringFromAscii(CStrVector(str));
1181 }
1182
1183
1184 } }  // namespace v8::internal