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