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
43namespace v8 {
44namespace 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); }
51AST_NODE_LIST(DECL_ACCEPT)
52#undef DECL_ACCEPT
53
54
55// ----------------------------------------------------------------------------
56// Implementation of other node functionality.
57
58
59bool Expression::IsSmiLiteral() {
60  return AsLiteral() != NULL && AsLiteral()->value()->IsSmi();
61}
62
63
64bool Expression::IsStringLiteral() {
65  return AsLiteral() != NULL && AsLiteral()->value()->IsString();
66}
67
68
69bool Expression::IsNullLiteral() {
70  return AsLiteral() != NULL && AsLiteral()->value()->IsNull();
71}
72
73
74bool 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
85VariableProxy::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
98VariableProxy::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
116void 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
131Assignment::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
148Token::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
167bool FunctionLiteral::AllowsLazyCompilation() {
168  return scope()->AllowsLazyCompilation();
169}
170
171
172bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
173  return scope()->AllowsLazyCompilationWithoutContext();
174}
175
176
177int FunctionLiteral::start_position() const {
178  return scope()->start_position();
179}
180
181
182int FunctionLiteral::end_position() const {
183  return scope()->end_position();
184}
185
186
187LanguageMode FunctionLiteral::language_mode() const {
188  return scope()->language_mode();
189}
190
191
192ObjectLiteralProperty::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
212ObjectLiteralProperty::ObjectLiteralProperty(bool is_getter,
213                                             FunctionLiteral* value) {
214  emit_store_ = true;
215  value_ = value;
216  kind_ = is_getter ? GETTER : SETTER;
217}
218
219
220bool ObjectLiteral::Property::IsCompileTimeValue() {
221  return kind_ == CONSTANT ||
222      (kind_ == MATERIALIZED_LITERAL &&
223       CompileTimeValue::IsCompileTimeValue(value_));
224}
225
226
227void ObjectLiteral::Property::set_emit_store(bool emit_store) {
228  emit_store_ = emit_store;
229}
230
231
232bool ObjectLiteral::Property::emit_store() {
233  return emit_store_;
234}
235
236
237bool 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
246bool 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
264void 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
288void 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
298void 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
308void 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
318bool 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
343static 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>.
350static 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
364bool 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
371static 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>
381static 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
398bool 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>
406static 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
418bool 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
427bool Declaration::IsInlineable() const {
428  return proxy()->var()->IsStackAllocated();
429}
430
431bool 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
443void ForInStatement::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
444  for_in_type_ = static_cast<ForInType>(oracle->ForInType(this));
445}
446
447
448void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
449  to_boolean_types_ = oracle->ToBooleanTypes(test_id());
450}
451
452
453void 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
486void 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
512void 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
532void CaseClause::RecordTypeFeedback(TypeFeedbackOracle* oracle) {
533  compare_type_ = oracle->ClauseType(CompareId());
534}
535
536
537bool 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
590bool 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
611Handle<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
637void 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
677void 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
692void 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
702void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
703  for (int i = 0; i < declarations->length(); i++) {
704    Visit(declarations->at(i));
705  }
706}
707
708
709void 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
718void 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  }
737FOR_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; }
745FOR_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; }
753FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
754#undef MAKE_TYPE_CASE
755
756
757static 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
765Interval RegExpAlternative::CaptureRegisters() {
766  return ListCaptureRegisters(nodes());
767}
768
769
770Interval RegExpDisjunction::CaptureRegisters() {
771  return ListCaptureRegisters(alternatives());
772}
773
774
775Interval RegExpLookahead::CaptureRegisters() {
776  return body()->CaptureRegisters();
777}
778
779
780Interval RegExpCapture::CaptureRegisters() {
781  Interval self(StartRegister(index()), EndRegister(index()));
782  return self.Union(body()->CaptureRegisters());
783}
784
785
786Interval RegExpQuantifier::CaptureRegisters() {
787  return body()->CaptureRegisters();
788}
789
790
791bool RegExpAssertion::IsAnchoredAtStart() {
792  return assertion_type() == RegExpAssertion::START_OF_INPUT;
793}
794
795
796bool RegExpAssertion::IsAnchoredAtEnd() {
797  return assertion_type() == RegExpAssertion::END_OF_INPUT;
798}
799
800
801bool 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
812bool 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
823bool 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
833bool 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
843bool RegExpLookahead::IsAnchoredAtStart() {
844  return is_positive() && body()->IsAnchoredAtStart();
845}
846
847
848bool RegExpCapture::IsAnchoredAtStart() {
849  return body()->IsAnchoredAtStart();
850}
851
852
853bool 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.
863class 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
879RegExpUnparser::RegExpUnparser(Zone* zone) : stream_(&alloc_), zone_(zone) {
880}
881
882
883void* 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
894void* 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
905void 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
914void* 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
928void* 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
953void* 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
964void* 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
979void* 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
993void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
994  stream()->Add("(^ ");
995  that->body()->Accept(this, data);
996  stream()->Add(")");
997  return NULL;
998}
999
1000
1001void* 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
1010void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
1011                                         void* data) {
1012  stream()->Add("(<- %i)", that->index());
1013  return NULL;
1014}
1015
1016
1017void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
1018  stream()->Put('%');
1019  return NULL;
1020}
1021
1022
1023SmartArrayPointer<const char> RegExpTree::ToString(Zone* zone) {
1024  RegExpUnparser unparser(zone);
1025  Accept(&unparser, NULL);
1026  return unparser.ToString();
1027}
1028
1029
1030RegExpDisjunction::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
1044static 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
1052RegExpAlternative::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
1067CaseClause::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
1105REGULAR_NODE(VariableDeclaration)
1106REGULAR_NODE(FunctionDeclaration)
1107REGULAR_NODE(Block)
1108REGULAR_NODE(ExpressionStatement)
1109REGULAR_NODE(EmptyStatement)
1110REGULAR_NODE(IfStatement)
1111REGULAR_NODE(ContinueStatement)
1112REGULAR_NODE(BreakStatement)
1113REGULAR_NODE(ReturnStatement)
1114REGULAR_NODE(SwitchStatement)
1115REGULAR_NODE(Conditional)
1116REGULAR_NODE(Literal)
1117REGULAR_NODE(ArrayLiteral)
1118REGULAR_NODE(ObjectLiteral)
1119REGULAR_NODE(RegExpLiteral)
1120REGULAR_NODE(FunctionLiteral)
1121REGULAR_NODE(Assignment)
1122REGULAR_NODE(Throw)
1123REGULAR_NODE(Property)
1124REGULAR_NODE(UnaryOperation)
1125REGULAR_NODE(CountOperation)
1126REGULAR_NODE(BinaryOperation)
1127REGULAR_NODE(CompareOperation)
1128REGULAR_NODE(ThisFunction)
1129REGULAR_NODE(Call)
1130REGULAR_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.
1135REGULAR_NODE(VariableProxy)
1136
1137// We currently do not optimize any modules.
1138DONT_OPTIMIZE_NODE(ModuleDeclaration)
1139DONT_OPTIMIZE_NODE(ImportDeclaration)
1140DONT_OPTIMIZE_NODE(ExportDeclaration)
1141DONT_OPTIMIZE_NODE(ModuleVariable)
1142DONT_OPTIMIZE_NODE(ModulePath)
1143DONT_OPTIMIZE_NODE(ModuleUrl)
1144DONT_OPTIMIZE_NODE(ModuleStatement)
1145DONT_OPTIMIZE_NODE(Yield)
1146DONT_OPTIMIZE_NODE(WithStatement)
1147DONT_OPTIMIZE_NODE(TryCatchStatement)
1148DONT_OPTIMIZE_NODE(TryFinallyStatement)
1149DONT_OPTIMIZE_NODE(DebuggerStatement)
1150DONT_OPTIMIZE_NODE(SharedFunctionInfoLiteral)
1151
1152DONT_SELFOPTIMIZE_NODE(DoWhileStatement)
1153DONT_SELFOPTIMIZE_NODE(WhileStatement)
1154DONT_SELFOPTIMIZE_NODE(ForStatement)
1155DONT_SELFOPTIMIZE_NODE(ForInStatement)
1156DONT_SELFOPTIMIZE_NODE(ForOfStatement)
1157
1158DONT_CACHE_NODE(ModuleLiteral)
1159
1160void 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
1183Handle<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