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