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