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