ast.cc 35.3 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/ast/ast.h"
6

7
#include <cmath>  // For isfinite.
8 9

#include "src/ast/prettyprinter.h"
10
#include "src/ast/scopes.h"
11 12 13 14 15
#include "src/builtins.h"
#include "src/code-stubs.h"
#include "src/contexts.h"
#include "src/conversions.h"
#include "src/hashmap.h"
16
#include "src/parsing/parser.h"
17
#include "src/property.h"
18
#include "src/property-details.h"
19 20
#include "src/string-stream.h"
#include "src/type-info.h"
21

22 23
namespace v8 {
namespace internal {
24 25 26 27

// ----------------------------------------------------------------------------
// All the Accept member functions for each syntax tree node type.

28 29
#define DECL_ACCEPT(type)                                       \
  void type::Accept(AstVisitor* v) { v->Visit##type(this); }
30
AST_NODE_LIST(DECL_ACCEPT)
31 32 33 34 35 36
#undef DECL_ACCEPT


// ----------------------------------------------------------------------------
// Implementation of other node functionality.

37 38
#ifdef DEBUG

39
void AstNode::Print(Isolate* isolate) {
40 41 42 43 44 45 46 47 48 49
  AstPrinter::PrintOut(isolate, this);
}


void AstNode::PrettyPrint(Isolate* isolate) {
  PrettyPrinter::PrintOut(isolate, this);
}

#endif  // DEBUG

50

51
bool Expression::IsSmiLiteral() const {
52
  return IsLiteral() && AsLiteral()->value()->IsSmi();
53 54 55
}


56
bool Expression::IsStringLiteral() const {
57
  return IsLiteral() && AsLiteral()->value()->IsString();
58 59 60
}


61
bool Expression::IsNullLiteral() const {
62
  return IsLiteral() && AsLiteral()->value()->IsNull();
63 64
}

65
bool Expression::IsUndefinedLiteral() const {
66 67 68 69
  if (IsLiteral() && AsLiteral()->value()->IsUndefined()) {
    return true;
  }

70
  const VariableProxy* var_proxy = AsVariableProxy();
71 72 73 74
  if (var_proxy == NULL) return false;
  Variable* var = var_proxy->var();
  // The global identifier "undefined" is immutable. Everything
  // else could be reassigned.
75
  return var != NULL && var->IsUnallocatedOrGlobalSlot() &&
76
         var_proxy->raw_name()->IsOneByteEqualTo("undefined");
77 78 79
}


80 81 82 83 84 85
bool Expression::IsValidReferenceExpressionOrThis() const {
  return IsValidReferenceExpression() ||
         (IsVariableProxy() && AsVariableProxy()->is_this());
}


86 87 88
VariableProxy::VariableProxy(Zone* zone, Variable* var, int start_position,
                             int end_position)
    : Expression(zone, start_position),
89 90 91
      bit_field_(IsThisField::encode(var->is_this()) |
                 IsAssignedField::encode(false) |
                 IsResolvedField::encode(false)),
92 93
      raw_name_(var->raw_name()),
      end_position_(end_position) {
94 95 96 97
  BindTo(var);
}


98 99 100
VariableProxy::VariableProxy(Zone* zone, const AstRawString* name,
                             Variable::Kind variable_kind, int start_position,
                             int end_position)
101
    : Expression(zone, start_position),
102 103
      bit_field_(IsThisField::encode(variable_kind == Variable::THIS) |
                 IsAssignedField::encode(false) |
104
                 IsResolvedField::encode(false)),
105 106
      raw_name_(name),
      end_position_(end_position) {}
107 108 109


void VariableProxy::BindTo(Variable* var) {
110 111 112
  DCHECK((is_this() && var->is_this()) || raw_name() == var->raw_name());
  set_var(var);
  set_is_resolved();
113
  var->set_is_used();
114 115 116
}


117 118
void VariableProxy::AssignFeedbackVectorSlots(Isolate* isolate,
                                              FeedbackVectorSpec* spec,
119
                                              FeedbackVectorSlotCache* cache) {
120 121 122
  if (UsesVariableFeedbackSlot()) {
    // VariableProxies that point to the same Variable within a function can
    // make their loads from the same IC slot.
123
    if (var()->IsUnallocated()) {
jkummerow's avatar
jkummerow committed
124 125
      ZoneHashMap::Entry* entry = cache->Get(var());
      if (entry != NULL) {
126
        variable_feedback_slot_ = FeedbackVectorSlot(
jkummerow's avatar
jkummerow committed
127
            static_cast<int>(reinterpret_cast<intptr_t>(entry->value)));
128
        return;
129 130
      }
    }
131 132 133 134
    variable_feedback_slot_ = spec->AddLoadICSlot();
    if (var()->IsUnallocated()) {
      cache->Put(var(), variable_feedback_slot_);
    }
135 136 137 138
  }
}


139
static void AssignVectorSlots(Expression* expr, FeedbackVectorSpec* spec,
140
                              FeedbackVectorSlot* out_slot) {
141 142 143 144 145 146 147 148 149 150
  Property* property = expr->AsProperty();
  LhsKind assign_type = Property::GetAssignType(property);
  if ((assign_type == VARIABLE &&
       expr->AsVariableProxy()->var()->IsUnallocated()) ||
      assign_type == NAMED_PROPERTY || assign_type == KEYED_PROPERTY) {
    // TODO(ishell): consider using ICSlotCache for variables here.
    FeedbackVectorSlotKind kind = assign_type == KEYED_PROPERTY
                                      ? FeedbackVectorSlotKind::KEYED_STORE_IC
                                      : FeedbackVectorSlotKind::STORE_IC;
    *out_slot = spec->AddSlot(kind);
151 152 153
  }
}

154 155 156
void ForInStatement::AssignFeedbackVectorSlots(Isolate* isolate,
                                               FeedbackVectorSpec* spec,
                                               FeedbackVectorSlotCache* cache) {
157
  AssignVectorSlots(each(), spec, &each_slot_);
158
  for_in_feedback_slot_ = spec->AddGeneralSlot();
159 160 161
}


162
Assignment::Assignment(Zone* zone, Token::Value op, Expression* target,
163 164
                       Expression* value, int pos)
    : Expression(zone, pos),
165 166 167
      bit_field_(
          IsUninitializedField::encode(false) | KeyTypeField::encode(ELEMENT) |
          StoreModeField::encode(STANDARD_STORE) | TokenField::encode(op)),
168 169
      target_(target),
      value_(value),
170
      binary_operation_(NULL) {}
171 172


173 174
void Assignment::AssignFeedbackVectorSlots(Isolate* isolate,
                                           FeedbackVectorSpec* spec,
175
                                           FeedbackVectorSlotCache* cache) {
176
  AssignVectorSlots(target(), spec, &slot_);
177 178 179
}


180 181
void CountOperation::AssignFeedbackVectorSlots(Isolate* isolate,
                                               FeedbackVectorSpec* spec,
182
                                               FeedbackVectorSlotCache* cache) {
183
  AssignVectorSlots(expression(), spec, &slot_);
184
}
185 186


187
Token::Value Assignment::binary_op() const {
188
  switch (op()) {
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
    case Token::ASSIGN_BIT_OR: return Token::BIT_OR;
    case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR;
    case Token::ASSIGN_BIT_AND: return Token::BIT_AND;
    case Token::ASSIGN_SHL: return Token::SHL;
    case Token::ASSIGN_SAR: return Token::SAR;
    case Token::ASSIGN_SHR: return Token::SHR;
    case Token::ASSIGN_ADD: return Token::ADD;
    case Token::ASSIGN_SUB: return Token::SUB;
    case Token::ASSIGN_MUL: return Token::MUL;
    case Token::ASSIGN_DIV: return Token::DIV;
    case Token::ASSIGN_MOD: return Token::MOD;
    default: UNREACHABLE();
  }
  return Token::ILLEGAL;
}


bool FunctionLiteral::AllowsLazyCompilation() {
  return scope()->AllowsLazyCompilation();
}


211 212 213 214 215
bool FunctionLiteral::AllowsLazyCompilationWithoutContext() {
  return scope()->AllowsLazyCompilationWithoutContext();
}


216 217 218 219 220 221 222 223 224 225
int FunctionLiteral::start_position() const {
  return scope()->start_position();
}


int FunctionLiteral::end_position() const {
  return scope()->end_position();
}


226 227
LanguageMode FunctionLiteral::language_mode() const {
  return scope()->language_mode();
228 229 230
}


231 232 233 234
bool FunctionLiteral::NeedsHomeObject(Expression* expr) {
  if (expr == nullptr || !expr->IsFunctionLiteral()) return false;
  DCHECK_NOT_NULL(expr->AsFunctionLiteral()->scope());
  return expr->AsFunctionLiteral()->scope()->NeedsHomeObject();
235 236 237
}


238 239 240 241 242 243 244 245 246 247 248 249
ObjectLiteralProperty::ObjectLiteralProperty(Expression* key, Expression* value,
                                             Kind kind, bool is_static,
                                             bool is_computed_name)
    : key_(key),
      value_(value),
      kind_(kind),
      emit_store_(true),
      is_static_(is_static),
      is_computed_name_(is_computed_name) {}


ObjectLiteralProperty::ObjectLiteralProperty(AstValueFactory* ast_value_factory,
arv's avatar
arv committed
250 251 252 253 254 255 256 257 258 259 260
                                             Expression* key, Expression* value,
                                             bool is_static,
                                             bool is_computed_name)
    : key_(key),
      value_(value),
      emit_store_(true),
      is_static_(is_static),
      is_computed_name_(is_computed_name) {
  if (!is_computed_name &&
      key->AsLiteral()->raw_value()->EqualsString(
          ast_value_factory->proto_string())) {
261
    kind_ = PROTOTYPE;
262 263
  } else if (value_->AsMaterializedLiteral() != NULL) {
    kind_ = MATERIALIZED_LITERAL;
264
  } else if (value_->IsLiteral()) {
265
    kind_ = CONSTANT;
266
  } else {
267
    kind_ = COMPUTED;
268 269 270
  }
}

271 272 273 274 275 276
bool ObjectLiteralProperty::NeedsSetFunctionName() const {
  return is_computed_name_ &&
         (value_->IsAnonymousFunctionDefinition() ||
          (value_->IsFunctionLiteral() &&
           IsConciseMethod(value_->AsFunctionLiteral()->kind())));
}
277

278 279
void ClassLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
                                             FeedbackVectorSpec* spec,
280
                                             FeedbackVectorSlotCache* cache) {
281 282
  // This logic that computes the number of slots needed for vector store
  // ICs must mirror FullCodeGenerator::VisitClassLiteral.
283
  prototype_slot_ = spec->AddLoadICSlot();
284
  if (NeedsProxySlot()) {
285
    proxy_slot_ = spec->AddStoreICSlot();
286 287
  }

288 289 290
  for (int i = 0; i < properties()->length(); i++) {
    ObjectLiteral::Property* property = properties()->at(i);
    Expression* value = property->value();
291
    if (FunctionLiteral::NeedsHomeObject(value)) {
292
      property->SetSlot(spec->AddStoreICSlot());
293
    }
294
  }
295 296 297
}


298 299 300 301 302 303 304
bool ObjectLiteral::Property::IsCompileTimeValue() {
  return kind_ == CONSTANT ||
      (kind_ == MATERIALIZED_LITERAL &&
       CompileTimeValue::IsCompileTimeValue(value_));
}


305 306 307 308 309 310 311 312 313 314
void ObjectLiteral::Property::set_emit_store(bool emit_store) {
  emit_store_ = emit_store;
}


bool ObjectLiteral::Property::emit_store() {
  return emit_store_;
}


315 316
void ObjectLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
                                              FeedbackVectorSpec* spec,
317
                                              FeedbackVectorSlotCache* cache) {
318 319
  // This logic that computes the number of slots needed for vector store
  // ics must mirror FullCodeGenerator::VisitObjectLiteral.
320 321 322 323
  int property_index = 0;
  for (; property_index < properties()->length(); property_index++) {
    ObjectLiteral::Property* property = properties()->at(property_index);
    if (property->is_computed_name()) break;
324 325
    if (property->IsCompileTimeValue()) continue;

326
    Literal* key = property->key()->AsLiteral();
327
    Expression* value = property->value();
328 329 330 331 332 333 334 335 336 337
    switch (property->kind()) {
      case ObjectLiteral::Property::CONSTANT:
        UNREACHABLE();
      case ObjectLiteral::Property::MATERIALIZED_LITERAL:
      // Fall through.
      case ObjectLiteral::Property::COMPUTED:
        // It is safe to use [[Put]] here because the boilerplate already
        // contains computed properties with an uninitialized value.
        if (key->value()->IsInternalizedString()) {
          if (property->emit_store()) {
338
            property->SetSlot(spec->AddStoreICSlot());
339
            if (FunctionLiteral::NeedsHomeObject(value)) {
340
              property->SetSlot(spec->AddStoreICSlot(), 1);
341 342 343 344 345
            }
          }
          break;
        }
        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
346
          property->SetSlot(spec->AddStoreICSlot());
347 348 349 350 351 352
        }
        break;
      case ObjectLiteral::Property::PROTOTYPE:
        break;
      case ObjectLiteral::Property::GETTER:
        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
353
          property->SetSlot(spec->AddStoreICSlot());
354 355 356 357
        }
        break;
      case ObjectLiteral::Property::SETTER:
        if (property->emit_store() && FunctionLiteral::NeedsHomeObject(value)) {
358
          property->SetSlot(spec->AddStoreICSlot());
359 360
        }
        break;
361 362 363
    }
  }

364 365
  for (; property_index < properties()->length(); property_index++) {
    ObjectLiteral::Property* property = properties()->at(property_index);
366

367 368 369
    Expression* value = property->value();
    if (property->kind() != ObjectLiteral::Property::PROTOTYPE) {
      if (FunctionLiteral::NeedsHomeObject(value)) {
370
        property->SetSlot(spec->AddStoreICSlot());
371 372 373
      }
    }
  }
374 375 376
}


377
void ObjectLiteral::CalculateEmitStore(Zone* zone) {
378 379 380
  const auto GETTER = ObjectLiteral::Property::GETTER;
  const auto SETTER = ObjectLiteral::Property::SETTER;

381 382 383 384
  ZoneAllocationPolicy allocator(zone);

  ZoneHashMap table(Literal::Match, ZoneHashMap::kDefaultHashMapCapacity,
                    allocator);
385 386
  for (int i = properties()->length() - 1; i >= 0; i--) {
    ObjectLiteral::Property* property = properties()->at(i);
arv's avatar
arv committed
387
    if (property->is_computed_name()) continue;
388
    if (property->kind() == ObjectLiteral::Property::PROTOTYPE) continue;
arv's avatar
arv committed
389
    Literal* literal = property->key()->AsLiteral();
390 391 392 393
    DCHECK(!literal->value()->IsNull());

    // If there is an existing entry do not emit a store unless the previous
    // entry was also an accessor.
394
    uint32_t hash = literal->Hash();
395
    ZoneHashMap::Entry* entry = table.LookupOrInsert(literal, hash, allocator);
396 397 398 399 400 401 402
    if (entry->value != NULL) {
      auto previous_kind =
          static_cast<ObjectLiteral::Property*>(entry->value)->kind();
      if (!((property->kind() == GETTER && previous_kind == SETTER) ||
            (property->kind() == SETTER && previous_kind == GETTER))) {
        property->set_emit_store(false);
      }
403
    }
404
    entry->value = property;
405 406 407 408
  }
}


409 410 411 412 413 414
bool ObjectLiteral::IsBoilerplateProperty(ObjectLiteral::Property* property) {
  return property != NULL &&
         property->kind() != ObjectLiteral::Property::PROTOTYPE;
}


415
void ObjectLiteral::BuildConstantProperties(Isolate* isolate) {
416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
  if (!constant_properties_.is_null()) return;

  // Allocate a fixed array to hold all the constant properties.
  Handle<FixedArray> constant_properties = isolate->factory()->NewFixedArray(
      boilerplate_properties_ * 2, TENURED);

  int position = 0;
  // Accumulate the value in local variables and store it at the end.
  bool is_simple = true;
  int depth_acc = 1;
  uint32_t max_element_index = 0;
  uint32_t elements = 0;
  for (int i = 0; i < properties()->length(); i++) {
    ObjectLiteral::Property* property = properties()->at(i);
    if (!IsBoilerplateProperty(property)) {
      is_simple = false;
      continue;
    }
arv's avatar
arv committed
434 435 436

    if (position == boilerplate_properties_ * 2) {
      DCHECK(property->is_computed_name());
437
      is_simple = false;
arv's avatar
arv committed
438 439 440 441
      break;
    }
    DCHECK(!property->is_computed_name());

442 443
    MaterializedLiteral* m_literal = property->value()->AsMaterializedLiteral();
    if (m_literal != NULL) {
444 445
      m_literal->BuildConstants(isolate);
      if (m_literal->depth() >= depth_acc) depth_acc = m_literal->depth() + 1;
446 447 448 449 450
    }

    // Add CONSTANT and COMPUTED properties to boilerplate. Use undefined
    // value for COMPUTED properties, the real value is filled in at
    // runtime. The enumeration order is maintained.
arv's avatar
arv committed
451
    Handle<Object> key = property->key()->AsLiteral()->value();
452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470
    Handle<Object> value = GetBoilerplateValue(property->value(), isolate);

    // Ensure objects that may, at any point in time, contain fields with double
    // representation are always treated as nested objects. This is true for
    // computed fields (value is undefined), and smi and double literals
    // (value->IsNumber()).
    // TODO(verwaest): Remove once we can store them inline.
    if (FLAG_track_double_fields &&
        (value->IsNumber() || value->IsUninitialized())) {
      may_store_doubles_ = true;
    }

    is_simple = is_simple && !value->IsUninitialized();

    // Keep track of the number of elements in the object literal and
    // the largest element index.  If the largest element index is
    // much larger than the number of elements, creating an object
    // literal with fast elements will be a waste of space.
    uint32_t element_index = 0;
471 472
    if (key->IsString() && String::cast(*key)->AsArrayIndex(&element_index)) {
      max_element_index = Max(element_index, max_element_index);
473
      elements++;
474 475 476
      key = isolate->factory()->NewNumberFromUint(element_index);
    } else if (key->ToArrayIndex(&element_index)) {
      max_element_index = Max(element_index, max_element_index);
477
      elements++;
478 479
    } else if (key->IsNumber()) {
      key = isolate->factory()->NumberToString(key);
480 481 482 483 484 485 486 487 488 489
    }

    // Add name, value pair to the fixed array.
    constant_properties->set(position++, *key);
    constant_properties->set(position++, *value);
  }

  constant_properties_ = constant_properties;
  fast_elements_ =
      (max_element_index <= 32) || ((2 * elements) >= max_element_index);
490
  has_elements_ = elements > 0;
491
  set_is_simple(is_simple);
492
  set_depth(depth_acc);
493 494 495
}


496
void ArrayLiteral::BuildConstantElements(Isolate* isolate) {
497 498
  DCHECK_LT(first_spread_index_, 0);

499 500
  if (!constant_elements_.is_null()) return;

501
  int constants_length = values()->length();
502

503
  // Allocate a fixed array to hold all the object literals.
504
  Handle<JSArray> array = isolate->factory()->NewJSArray(
505
      FAST_HOLEY_SMI_ELEMENTS, constants_length, constants_length,
506
      INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE);
507 508

  // Fill in the literals.
509
  bool is_simple = true;
510 511
  int depth_acc = 1;
  bool is_holey = false;
arv's avatar
arv committed
512
  int array_index = 0;
513
  for (; array_index < constants_length; array_index++) {
arv's avatar
arv committed
514
    Expression* element = values()->at(array_index);
515
    DCHECK(!element->IsSpread());
516 517
    MaterializedLiteral* m_literal = element->AsMaterializedLiteral();
    if (m_literal != NULL) {
518 519 520 521
      m_literal->BuildConstants(isolate);
      if (m_literal->depth() + 1 > depth_acc) {
        depth_acc = m_literal->depth() + 1;
      }
522
    }
523

524 525 526
    // New handle scope here, needs to be after BuildContants().
    HandleScope scope(isolate);
    Handle<Object> boilerplate_value = GetBoilerplateValue(element, isolate);
527 528
    if (boilerplate_value->IsTheHole()) {
      is_holey = true;
529 530 531 532 533
      continue;
    }

    if (boilerplate_value->IsUninitialized()) {
      boilerplate_value = handle(Smi::FromInt(0), isolate);
534 535
      is_simple = false;
    }
536 537 538

    JSObject::AddDataElement(array, array_index, boilerplate_value, NONE)
        .Assert();
539 540
  }

541
  JSObject::ValidateElements(array);
542 543 544 545
  Handle<FixedArrayBase> element_values(array->elements());

  // Simple and shallow arrays can be lazily copied, we transform the
  // elements array to a copy-on-write array.
arv's avatar
arv committed
546
  if (is_simple && depth_acc == 1 && array_index > 0 &&
547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562
      array->HasFastSmiOrObjectElements()) {
    element_values->set_map(isolate->heap()->fixed_cow_array_map());
  }

  // Remember both the literal's constant values as well as the ElementsKind
  // in a 2-element FixedArray.
  Handle<FixedArray> literals = isolate->factory()->NewFixedArray(2, TENURED);

  ElementsKind kind = array->GetElementsKind();
  kind = is_holey ? GetHoleyElementsKind(kind) : GetPackedElementsKind(kind);

  literals->set(0, Smi::FromInt(kind));
  literals->set(1, *element_values);

  constant_elements_ = literals;
  set_is_simple(is_simple);
563
  set_depth(depth_acc);
564 565 566
}


567 568 569 570 571 572 573 574
void ArrayLiteral::AssignFeedbackVectorSlots(Isolate* isolate,
                                             FeedbackVectorSpec* spec,
                                             FeedbackVectorSlotCache* cache) {
  // This logic that computes the number of slots needed for vector store
  // ics must mirror FullCodeGenerator::VisitArrayLiteral.
  int array_index = 0;
  for (; array_index < values()->length(); array_index++) {
    Expression* subexpr = values()->at(array_index);
575
    DCHECK(!subexpr->IsSpread());
576 577 578 579 580 581 582 583 584 585
    if (CompileTimeValue::IsCompileTimeValue(subexpr)) continue;

    // We'll reuse the same literal slot for all of the non-constant
    // subexpressions that use a keyed store IC.
    literal_slot_ = spec->AddKeyedStoreICSlot();
    return;
  }
}


586 587
Handle<Object> MaterializedLiteral::GetBoilerplateValue(Expression* expression,
                                                        Isolate* isolate) {
588
  if (expression->IsLiteral()) {
589 590 591 592 593 594 595 596 597
    return expression->AsLiteral()->value();
  }
  if (CompileTimeValue::IsCompileTimeValue(expression)) {
    return CompileTimeValue::GetValue(isolate, expression);
  }
  return isolate->factory()->uninitialized_value();
}


598
void MaterializedLiteral::BuildConstants(Isolate* isolate) {
599
  if (IsArrayLiteral()) {
600
    return AsArrayLiteral()->BuildConstantElements(isolate);
601 602
  }
  if (IsObjectLiteral()) {
603
    return AsObjectLiteral()->BuildConstantProperties(isolate);
604
  }
605 606
  DCHECK(IsRegExpLiteral());
  DCHECK(depth() >= 1);  // Depth should be initialized.
607 608 609
}


610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
void UnaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
  // TODO(olivf) If this Operation is used in a test context, then the
  // expression has a ToBoolean stub and we want to collect the type
  // information. However the GraphBuilder expects it to be on the instruction
  // corresponding to the TestContext, therefore we have to store it here and
  // not on the operand.
  set_to_boolean_types(oracle->ToBooleanTypes(expression()->test_id()));
}


void BinaryOperation::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
  // TODO(olivf) If this Operation is used in a test context, then the right
  // hand side has a ToBoolean stub and we want to collect the type information.
  // However the GraphBuilder expects it to be on the instruction corresponding
  // to the TestContext, therefore we have to store it here and not on the
  // right hand operand.
  set_to_boolean_types(oracle->ToBooleanTypes(right()->test_id()));
}


630 631 632 633 634
static bool IsTypeof(Expression* expr) {
  UnaryOperation* maybe_unary = expr->AsUnaryOperation();
  return maybe_unary != NULL && maybe_unary->op() == Token::TYPEOF;
}

635

636 637 638 639 640 641 642
// Check for the pattern: typeof <expression> equals <string literal>.
static bool MatchLiteralCompareTypeof(Expression* left,
                                      Token::Value op,
                                      Expression* right,
                                      Expression** expr,
                                      Handle<String>* check) {
  if (IsTypeof(left) && right->IsStringLiteral() && Token::IsEqualityOp(op)) {
643
    *expr = left->AsUnaryOperation()->expression();
644
    *check = Handle<String>::cast(right->AsLiteral()->value());
645 646 647 648 649 650
    return true;
  }
  return false;
}


651 652 653 654 655
bool CompareOperation::IsLiteralCompareTypeof(Expression** expr,
                                              Handle<String>* check) {
  return MatchLiteralCompareTypeof(left_, op_, right_, expr, check) ||
      MatchLiteralCompareTypeof(right_, op_, left_, expr, check);
}
656 657


658 659 660 661
static bool IsVoidOfLiteral(Expression* expr) {
  UnaryOperation* maybe_unary = expr->AsUnaryOperation();
  return maybe_unary != NULL &&
      maybe_unary->op() == Token::VOID &&
662
      maybe_unary->expression()->IsLiteral();
663 664
}

665

666 667
// Check for the pattern: void <literal> equals <expression> or
// undefined equals <expression>
668 669 670
static bool MatchLiteralCompareUndefined(Expression* left,
                                         Token::Value op,
                                         Expression* right,
671
                                         Expression** expr) {
672
  if (IsVoidOfLiteral(left) && Token::IsEqualityOp(op)) {
673 674 675
    *expr = right;
    return true;
  }
676
  if (left->IsUndefinedLiteral() && Token::IsEqualityOp(op)) {
677
    *expr = right;
678 679 680 681 682
    return true;
  }
  return false;
}

683 684 685
bool CompareOperation::IsLiteralCompareUndefined(Expression** expr) {
  return MatchLiteralCompareUndefined(left_, op_, right_, expr) ||
         MatchLiteralCompareUndefined(right_, op_, left_, expr);
686
}
687 688


689 690 691 692 693 694 695
// Check for the pattern: null equals <expression>
static bool MatchLiteralCompareNull(Expression* left,
                                    Token::Value op,
                                    Expression* right,
                                    Expression** expr) {
  if (left->IsNullLiteral() && Token::IsEqualityOp(op)) {
    *expr = right;
696 697 698 699 700 701
    return true;
  }
  return false;
}


702 703 704 705 706 707
bool CompareOperation::IsLiteralCompareNull(Expression** expr) {
  return MatchLiteralCompareNull(left_, op_, right_, expr) ||
      MatchLiteralCompareNull(right_, op_, left_, expr);
}


708 709 710
// ----------------------------------------------------------------------------
// Inlining support

711
bool Declaration::IsInlineable() const {
712 713 714
  return proxy()->var()->IsStackAllocated();
}

715 716
bool FunctionDeclaration::IsInlineable() const {
  return false;
717 718 719
}


720 721 722
// ----------------------------------------------------------------------------
// Recording of type feedback

723 724 725
// TODO(rossberg): all RecordTypeFeedback functions should disappear
// once we use the common type field in the AST consistently.

726
void Expression::RecordToBooleanTypeFeedback(TypeFeedbackOracle* oracle) {
727
  set_to_boolean_types(oracle->ToBooleanTypes(test_id()));
728 729 730
}


731
bool Call::IsUsingCallFeedbackICSlot(Isolate* isolate) const {
732
  CallType call_type = GetCallType(isolate);
733 734 735
  if (call_type == POSSIBLY_EVAL_CALL) {
    return false;
  }
736 737 738 739 740 741
  return true;
}


bool Call::IsUsingCallFeedbackSlot(Isolate* isolate) const {
  // SuperConstructorCall uses a CallConstructStub, which wants
742
  // a Slot, in addition to any IC slots requested elsewhere.
743
  return GetCallType(isolate) == SUPER_CALL;
744 745 746
}


747
void Call::AssignFeedbackVectorSlots(Isolate* isolate, FeedbackVectorSpec* spec,
748
                                     FeedbackVectorSlotCache* cache) {
749 750 751 752
  if (IsUsingCallFeedbackICSlot(isolate)) {
    ic_slot_ = spec->AddCallICSlot();
  }
  if (IsUsingCallFeedbackSlot(isolate)) {
753
    stub_slot_ = spec->AddGeneralSlot();
754
  }
755 756 757
}


758 759 760 761 762
Call::CallType Call::GetCallType(Isolate* isolate) const {
  VariableProxy* proxy = expression()->AsVariableProxy();
  if (proxy != NULL) {
    if (proxy->var()->is_possibly_eval(isolate)) {
      return POSSIBLY_EVAL_CALL;
763
    } else if (proxy->var()->IsUnallocatedOrGlobalSlot()) {
764 765 766 767 768 769
      return GLOBAL_CALL;
    } else if (proxy->var()->IsLookupSlot()) {
      return LOOKUP_SLOT_CALL;
    }
  }

770
  if (expression()->IsSuperCallReference()) return SUPER_CALL;
771

772
  Property* property = expression()->AsProperty();
773 774 775 776 777 778 779 780 781 782
  if (property != nullptr) {
    bool is_super = property->IsSuperAccess();
    if (property->key()->IsPropertyName()) {
      return is_super ? NAMED_SUPER_PROPERTY_CALL : NAMED_PROPERTY_CALL;
    } else {
      return is_super ? KEYED_SUPER_PROPERTY_CALL : KEYED_PROPERTY_CALL;
    }
  }

  return OTHER_CALL;
783 784 785
}


786
// ----------------------------------------------------------------------------
787
// Implementation of AstVisitor
788

789 790 791 792 793 794 795
void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) {
  for (int i = 0; i < declarations->length(); i++) {
    Visit(declarations->at(i));
  }
}


796
void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) {
797
  for (int i = 0; i < statements->length(); i++) {
798 799 800
    Statement* stmt = statements->at(i);
    Visit(stmt);
    if (stmt->IsJump()) break;
801 802 803 804
  }
}


805
void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
806 807 808 809 810 811 812 813 814 815
  for (int i = 0; i < expressions->length(); i++) {
    // The variable statement visiting code may pass NULL expressions
    // to this code. Maybe this should be handled by introducing an
    // undefined expression or literal?  Revisit this code if this
    // changes
    Expression* expression = expressions->at(i);
    if (expression != NULL) Visit(expression);
  }
}

816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
// ----------------------------------------------------------------------------
// Implementation of AstTraversalVisitor

AstTraversalVisitor::AstTraversalVisitor(Isolate* isolate) {
  InitializeAstVisitor(isolate);
}

void AstTraversalVisitor::VisitVariableDeclaration(VariableDeclaration* decl) {}

void AstTraversalVisitor::VisitFunctionDeclaration(FunctionDeclaration* decl) {
  Visit(decl->fun());
}

void AstTraversalVisitor::VisitImportDeclaration(ImportDeclaration* decl) {}

void AstTraversalVisitor::VisitExportDeclaration(ExportDeclaration* decl) {}

void AstTraversalVisitor::VisitStatements(ZoneList<Statement*>* stmts) {
  for (int i = 0; i < stmts->length(); ++i) {
    Statement* stmt = stmts->at(i);
    Visit(stmt);
    if (stmt->IsJump()) break;
  }
}

void AstTraversalVisitor::VisitExpressions(ZoneList<Expression*>* expressions) {
  for (int i = 0; i < expressions->length(); i++) {
    Expression* expression = expressions->at(i);
    if (expression != NULL) Visit(expression);
  }
}

void AstTraversalVisitor::VisitBlock(Block* stmt) {
  VisitStatements(stmt->statements());
}

void AstTraversalVisitor::VisitExpressionStatement(ExpressionStatement* stmt) {
  Visit(stmt->expression());
}

void AstTraversalVisitor::VisitEmptyStatement(EmptyStatement* stmt) {}

void AstTraversalVisitor::VisitSloppyBlockFunctionStatement(
    SloppyBlockFunctionStatement* stmt) {
  Visit(stmt->statement());
}

void AstTraversalVisitor::VisitIfStatement(IfStatement* stmt) {
  Visit(stmt->condition());
  Visit(stmt->then_statement());
  Visit(stmt->else_statement());
}

void AstTraversalVisitor::VisitContinueStatement(ContinueStatement* stmt) {}

void AstTraversalVisitor::VisitBreakStatement(BreakStatement* stmt) {}

void AstTraversalVisitor::VisitReturnStatement(ReturnStatement* stmt) {
  Visit(stmt->expression());
}

void AstTraversalVisitor::VisitWithStatement(WithStatement* stmt) {
  stmt->expression();
  stmt->statement();
}

void AstTraversalVisitor::VisitSwitchStatement(SwitchStatement* stmt) {
  Visit(stmt->tag());

  ZoneList<CaseClause*>* clauses = stmt->cases();

  for (int i = 0; i < clauses->length(); ++i) {
    CaseClause* clause = clauses->at(i);
    if (!clause->is_default()) {
      Expression* label = clause->label();
      Visit(label);
    }
    ZoneList<Statement*>* stmts = clause->statements();
    VisitStatements(stmts);
  }
}

void AstTraversalVisitor::VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }

void AstTraversalVisitor::VisitDoWhileStatement(DoWhileStatement* stmt) {
  Visit(stmt->body());
  Visit(stmt->cond());
}

void AstTraversalVisitor::VisitWhileStatement(WhileStatement* stmt) {
  Visit(stmt->cond());
  Visit(stmt->body());
}

void AstTraversalVisitor::VisitForStatement(ForStatement* stmt) {
  if (stmt->init() != NULL) {
    Visit(stmt->init());
  }
  if (stmt->cond() != NULL) {
    Visit(stmt->cond());
  }
  if (stmt->next() != NULL) {
    Visit(stmt->next());
  }
  Visit(stmt->body());
}

void AstTraversalVisitor::VisitForInStatement(ForInStatement* stmt) {
  Visit(stmt->enumerable());
  Visit(stmt->body());
}

void AstTraversalVisitor::VisitForOfStatement(ForOfStatement* stmt) {
  Visit(stmt->assign_iterator());
  Visit(stmt->next_result());
  Visit(stmt->result_done());
  Visit(stmt->assign_each());
  Visit(stmt->body());
}

void AstTraversalVisitor::VisitTryCatchStatement(TryCatchStatement* stmt) {
  Visit(stmt->try_block());
  Visit(stmt->catch_block());
}

void AstTraversalVisitor::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
  Visit(stmt->try_block());
  Visit(stmt->finally_block());
}

void AstTraversalVisitor::VisitDebuggerStatement(DebuggerStatement* stmt) {}

void AstTraversalVisitor::VisitFunctionLiteral(FunctionLiteral* expr) {
  Scope* scope = expr->scope();
  VisitDeclarations(scope->declarations());
  VisitStatements(expr->body());
}

void AstTraversalVisitor::VisitNativeFunctionLiteral(
    NativeFunctionLiteral* expr) {}

void AstTraversalVisitor::VisitDoExpression(DoExpression* expr) {
  VisitBlock(expr->block());
  VisitVariableProxy(expr->result());
}

void AstTraversalVisitor::VisitConditional(Conditional* expr) {
  Visit(expr->condition());
  Visit(expr->then_expression());
  Visit(expr->else_expression());
}

void AstTraversalVisitor::VisitVariableProxy(VariableProxy* expr) {}

void AstTraversalVisitor::VisitLiteral(Literal* expr) {}

void AstTraversalVisitor::VisitRegExpLiteral(RegExpLiteral* expr) {}

void AstTraversalVisitor::VisitObjectLiteral(ObjectLiteral* expr) {
  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
  for (int i = 0; i < props->length(); ++i) {
    ObjectLiteralProperty* prop = props->at(i);
    if (!prop->key()->IsLiteral()) {
      Visit(prop->key());
    }
    Visit(prop->value());
  }
}

void AstTraversalVisitor::VisitArrayLiteral(ArrayLiteral* expr) {
  ZoneList<Expression*>* values = expr->values();
  for (int i = 0; i < values->length(); ++i) {
    Expression* value = values->at(i);
    Visit(value);
  }
}

void AstTraversalVisitor::VisitAssignment(Assignment* expr) {
  Visit(expr->target());
  Visit(expr->value());
}

void AstTraversalVisitor::VisitYield(Yield* expr) {
  Visit(expr->generator_object());
  Visit(expr->expression());
}

void AstTraversalVisitor::VisitThrow(Throw* expr) { Visit(expr->exception()); }

void AstTraversalVisitor::VisitProperty(Property* expr) {
  Visit(expr->obj());
  Visit(expr->key());
}

void AstTraversalVisitor::VisitCall(Call* expr) {
  Visit(expr->expression());
  ZoneList<Expression*>* args = expr->arguments();
  for (int i = 0; i < args->length(); ++i) {
    Expression* arg = args->at(i);
    Visit(arg);
  }
}

void AstTraversalVisitor::VisitCallNew(CallNew* expr) {
  Visit(expr->expression());
  ZoneList<Expression*>* args = expr->arguments();
  for (int i = 0; i < args->length(); ++i) {
    Expression* arg = args->at(i);
    Visit(arg);
  }
}

void AstTraversalVisitor::VisitCallRuntime(CallRuntime* expr) {
  ZoneList<Expression*>* args = expr->arguments();
  for (int i = 0; i < args->length(); ++i) {
    Expression* arg = args->at(i);
    Visit(arg);
  }
}

void AstTraversalVisitor::VisitUnaryOperation(UnaryOperation* expr) {
  Visit(expr->expression());
}

void AstTraversalVisitor::VisitCountOperation(CountOperation* expr) {
  Visit(expr->expression());
}

void AstTraversalVisitor::VisitBinaryOperation(BinaryOperation* expr) {
  Visit(expr->left());
  Visit(expr->right());
}

void AstTraversalVisitor::VisitCompareOperation(CompareOperation* expr) {
  Visit(expr->left());
  Visit(expr->right());
}

void AstTraversalVisitor::VisitThisFunction(ThisFunction* expr) {}

void AstTraversalVisitor::VisitDeclarations(ZoneList<Declaration*>* decls) {
  for (int i = 0; i < decls->length(); ++i) {
    Declaration* decl = decls->at(i);
    Visit(decl);
  }
}

void AstTraversalVisitor::VisitClassLiteral(ClassLiteral* expr) {
  if (expr->extends() != nullptr) {
    Visit(expr->extends());
  }
  Visit(expr->constructor());
  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
  for (int i = 0; i < props->length(); ++i) {
    ObjectLiteralProperty* prop = props->at(i);
    if (!prop->key()->IsLiteral()) {
      Visit(prop->key());
    }
    Visit(prop->value());
  }
}

void AstTraversalVisitor::VisitSpread(Spread* expr) {
  Visit(expr->expression());
}

void AstTraversalVisitor::VisitEmptyParentheses(EmptyParentheses* expr) {}

void AstTraversalVisitor::VisitSuperPropertyReference(
    SuperPropertyReference* expr) {
  VisitVariableProxy(expr->this_var());
  Visit(expr->home_object());
}

void AstTraversalVisitor::VisitSuperCallReference(SuperCallReference* expr) {
  VisitVariableProxy(expr->this_var());
  VisitVariableProxy(expr->new_target_var());
  VisitVariableProxy(expr->this_function_var());
}

void AstTraversalVisitor::VisitRewritableExpression(
    RewritableExpression* expr) {
  Visit(expr->expression());
}

1101
CaseClause::CaseClause(Zone* zone, Expression* label,
1102 1103
                       ZoneList<Statement*>* statements, int pos)
    : Expression(zone, pos),
1104
      label_(label),
1105
      statements_(statements),
1106
      compare_type_(Type::None()) {}
1107

1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118
uint32_t Literal::Hash() {
  return raw_value()->IsString()
             ? raw_value()->AsString()->hash()
             : ComputeLongHash(double_to_uint64(raw_value()->AsNumber()));
}


// static
bool Literal::Match(void* literal1, void* literal2) {
  const AstValue* x = static_cast<Literal*>(literal1)->raw_value();
  const AstValue* y = static_cast<Literal*>(literal2)->raw_value();
1119
  return (x->IsString() && y->IsString() && x->AsString() == y->AsString()) ||
1120
         (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber());
1121 1122 1123
}


1124 1125
}  // namespace internal
}  // namespace v8