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