CSE2410 Fall 2014 Bounce

// Copyright 2013 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "typing.h"

#include "parser.h"  // for CompileTimeValue; TODO(rossberg): should move

#include "scopes.h"

namespace v8 {

namespace internal {

AstTyper::AstTyper(CompilationInfo* info)

    : info_(info),

      oracle_(

          Handle<Code>(info->closure()->shared()->code()),

          Handle<Context>(info->closure()->context()->native_context()),

          info->isolate(),

          info->zone()),

      store_(info->zone()) {

  InitializeAstVisitor(info->isolate());

}

#define RECURSE(call)                         \

  do {                                        \

    ASSERT(!visitor->HasStackOverflow());     \

    call;                                     \

    if (visitor->HasStackOverflow()) return;  \

  } while (false)

void AstTyper::Run(CompilationInfo* info) {

  AstTyper* visitor = new(info->zone()) AstTyper(info);

  Scope* scope = info->scope();

  // Handle implicit declaration of the function name in named function

  // expressions before other declarations.

  if (scope->is_function_scope() && scope->function() != NULL) {

    RECURSE(visitor->VisitVariableDeclaration(scope->function()));

  }

  RECURSE(visitor->VisitDeclarations(scope->declarations()));

  RECURSE(visitor->VisitStatements(info->function()->body()));

}

#undef RECURSE

#define RECURSE(call)                \

  do {                               \

    ASSERT(!HasStackOverflow());     \

    call;                            \

    if (HasStackOverflow()) return;  \

  } while (false)

void AstTyper::VisitStatements(ZoneList<Statement*>* stmts) {

  for (int i = 0; i < stmts->length(); ++i) {

    Statement* stmt = stmts->at(i);

    RECURSE(Visit(stmt));

    if (stmt->IsJump()) break;

  }

}

void AstTyper::VisitBlock(Block* stmt) {

  RECURSE(VisitStatements(stmt->statements()));

  if (stmt->labels() != NULL) {

    store_.Forget();  // Control may transfer here via 'break l'.

  }

}

void AstTyper::VisitExpressionStatement(ExpressionStatement* stmt) {

  RECURSE(Visit(stmt->expression()));

}

void AstTyper::VisitEmptyStatement(EmptyStatement* stmt) {

}

void AstTyper::VisitIfStatement(IfStatement* stmt) {

  // Collect type feedback.

  if (!stmt->condition()->ToBooleanIsTrue() &&

      !stmt->condition()->ToBooleanIsFalse()) {

    stmt->condition()->RecordToBooleanTypeFeedback(oracle());

  }

  RECURSE(Visit(stmt->condition()));

  Effects then_effects = EnterEffects();

  RECURSE(Visit(stmt->then_statement()));

  ExitEffects();

  Effects else_effects = EnterEffects();

  RECURSE(Visit(stmt->else_statement()));

  ExitEffects();

  then_effects.Alt(else_effects);

  store_.Seq(then_effects);

}

void AstTyper::VisitContinueStatement(ContinueStatement* stmt) {

  // TODO(rossberg): is it worth having a non-termination effect?

}

void AstTyper::VisitBreakStatement(BreakStatement* stmt) {

  // TODO(rossberg): is it worth having a non-termination effect?

}

void AstTyper::VisitReturnStatement(ReturnStatement* stmt) {

  // Collect type feedback.

  // TODO(rossberg): we only need this for inlining into test contexts...

  stmt->expression()->RecordToBooleanTypeFeedback(oracle());

  RECURSE(Visit(stmt->expression()));

  // TODO(rossberg): is it worth having a non-termination effect?

}

void AstTyper::VisitWithStatement(WithStatement* stmt) {

  RECURSE(stmt->expression());

  RECURSE(stmt->statement());

}

void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) {

  RECURSE(Visit(stmt->tag()));

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

  SwitchStatement::SwitchType switch_type = stmt->switch_type();

  Effects local_effects(zone());

  bool complex_effects = false;  // True for label effects or fall-through.

  for (int i = 0; i < clauses->length(); ++i) {

    CaseClause* clause = clauses->at(i);

    Effects clause_effects = EnterEffects();

    if (!clause->is_default()) {

      Expression* label = clause->label();

      SwitchStatement::SwitchType label_switch_type =

          label->IsSmiLiteral() ? SwitchStatement::SMI_SWITCH :

          label->IsStringLiteral() ? SwitchStatement::STRING_SWITCH :

              SwitchStatement::GENERIC_SWITCH;

      if (switch_type == SwitchStatement::UNKNOWN_SWITCH)

        switch_type = label_switch_type;

      else if (switch_type != label_switch_type)

        switch_type = SwitchStatement::GENERIC_SWITCH;

      RECURSE(Visit(label));

      if (!clause_effects.IsEmpty()) complex_effects = true;

    }

    ZoneList<Statement*>* stmts = clause->statements();

    RECURSE(VisitStatements(stmts));

    ExitEffects();

    if (stmts->is_empty() || stmts->last()->IsJump()) {

      local_effects.Alt(clause_effects);

    } else {

      complex_effects = true;

    }

  }

  if (complex_effects) {

    store_.Forget();  // Reached this in unknown state.

  } else {

    store_.Seq(local_effects);

  }

  if (switch_type == SwitchStatement::UNKNOWN_SWITCH)

    switch_type = SwitchStatement::GENERIC_SWITCH;

  stmt->set_switch_type(switch_type);

  // Collect type feedback.

  // TODO(rossberg): can we eliminate this special case and extra loop?

  if (switch_type == SwitchStatement::SMI_SWITCH) {

    for (int i = 0; i < clauses->length(); ++i) {

      CaseClause* clause = clauses->at(i);

      if (!clause->is_default())

        clause->RecordTypeFeedback(oracle());

    }

  }

}

void AstTyper::VisitCaseClause(CaseClause* clause) {

  UNREACHABLE();

}

void AstTyper::VisitDoWhileStatement(DoWhileStatement* stmt) {

  // Collect type feedback.

  if (!stmt->cond()->ToBooleanIsTrue()) {

    stmt->cond()->RecordToBooleanTypeFeedback(oracle());

  }

  // TODO(rossberg): refine the unconditional Forget (here and elsewhere) by

  // computing the set of variables assigned in only some of the origins of the

  // control transfer (such as the loop body here).

  store_.Forget();  // Control may transfer here via looping or 'continue'.

  RECURSE(Visit(stmt->body()));

  RECURSE(Visit(stmt->cond()));

  store_.Forget();  // Control may transfer here via 'break'.

}

void AstTyper::VisitWhileStatement(WhileStatement* stmt) {

  // Collect type feedback.

  if (!stmt->cond()->ToBooleanIsTrue()) {

    stmt->cond()->RecordToBooleanTypeFeedback(oracle());

  }

  store_.Forget();  // Control may transfer here via looping or 'continue'.

  RECURSE(Visit(stmt->cond()));

  RECURSE(Visit(stmt->body()));

  store_.Forget();  // Control may transfer here via termination or 'break'.

}

void AstTyper::VisitForStatement(ForStatement* stmt) {

  if (stmt->init() != NULL) {

    RECURSE(Visit(stmt->init()));

  }

  store_.Forget();  // Control may transfer here via looping.

  if (stmt->cond() != NULL) {

    // Collect type feedback.

    stmt->cond()->RecordToBooleanTypeFeedback(oracle());

    RECURSE(Visit(stmt->cond()));

  }

  RECURSE(Visit(stmt->body()));

  if (stmt->next() != NULL) {

    store_.Forget();  // Control may transfer here via 'continue'.

    RECURSE(Visit(stmt->next()));

  }

  store_.Forget();  // Control may transfer here via termination or 'break'.

}

void AstTyper::VisitForInStatement(ForInStatement* stmt) {

  // Collect type feedback.

  stmt->RecordTypeFeedback(oracle());

  RECURSE(Visit(stmt->enumerable()));

  store_.Forget();  // Control may transfer here via looping or 'continue'.

  RECURSE(Visit(stmt->body()));

  store_.Forget();  // Control may transfer here via 'break'.

}

void AstTyper::VisitForOfStatement(ForOfStatement* stmt) {

  RECURSE(Visit(stmt->iterable()));

  store_.Forget();  // Control may transfer here via looping or 'continue'.

  RECURSE(Visit(stmt->body()));

  store_.Forget();  // Control may transfer here via 'break'.

}

void AstTyper::VisitTryCatchStatement(TryCatchStatement* stmt) {

  Effects try_effects = EnterEffects();

  RECURSE(Visit(stmt->try_block()));

  ExitEffects();

  Effects catch_effects = EnterEffects();

  store_.Forget();  // Control may transfer here via 'throw'.

  RECURSE(Visit(stmt->catch_block()));

  ExitEffects();

  try_effects.Alt(catch_effects);

  store_.Seq(try_effects);

  // At this point, only variables that were reassigned in the catch block are

  // still remembered.

}

void AstTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) {

  RECURSE(Visit(stmt->try_block()));

  store_.Forget();  // Control may transfer here via 'throw'.

  RECURSE(Visit(stmt->finally_block()));

}

void AstTyper::VisitDebuggerStatement(DebuggerStatement* stmt) {

  store_.Forget();  // May do whatever.

}

void AstTyper::VisitFunctionLiteral(FunctionLiteral* expr) {

}

void AstTyper::VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {

}

void AstTyper::VisitConditional(Conditional* expr) {

  // Collect type feedback.

  expr->condition()->RecordToBooleanTypeFeedback(oracle());

  RECURSE(Visit(expr->condition()));

  Effects then_effects = EnterEffects();

  RECURSE(Visit(expr->then_expression()));

  ExitEffects();

  Effects else_effects = EnterEffects();

  RECURSE(Visit(expr->else_expression()));

  ExitEffects();

  then_effects.Alt(else_effects);

  store_.Seq(then_effects);

  NarrowType(expr, Bounds::Either(

      expr->then_expression()->bounds(),

      expr->else_expression()->bounds(), isolate_));

}

void AstTyper::VisitVariableProxy(VariableProxy* expr) {

  Variable* var = expr->var();

  if (var->IsStackAllocated()) {

    NarrowType(expr, store_.LookupBounds(variable_index(var)));

  }

}

void AstTyper::VisitLiteral(Literal* expr) {

  Type* type = Type::Constant(expr->value(), isolate_);

  NarrowType(expr, Bounds(type, isolate_));

}

void AstTyper::VisitRegExpLiteral(RegExpLiteral* expr) {

  NarrowType(expr, Bounds(Type::RegExp(), isolate_));

}

void AstTyper::VisitObjectLiteral(ObjectLiteral* expr) {

  ZoneList<ObjectLiteral::Property*>* properties = expr->properties();

  for (int i = 0; i < properties->length(); ++i) {

    ObjectLiteral::Property* prop = properties->at(i);

    // Collect type feedback.

    if ((prop->kind() == ObjectLiteral::Property::MATERIALIZED_LITERAL &&

        !CompileTimeValue::IsCompileTimeValue(prop->value())) ||

        prop->kind() == ObjectLiteral::Property::COMPUTED) {

      if (prop->key()->value()->IsInternalizedString() && prop->emit_store()) {

        prop->RecordTypeFeedback(oracle());

      }

    }

    RECURSE(Visit(prop->value()));

  }

  NarrowType(expr, Bounds(Type::Object(), isolate_));

}

void AstTyper::VisitArrayLiteral(ArrayLiteral* expr) {

  ZoneList<Expression*>* values = expr->values();

  for (int i = 0; i < values->length(); ++i) {

    Expression* value = values->at(i);

    RECURSE(Visit(value));

  }

  NarrowType(expr, Bounds(Type::Array(), isolate_));

}

void AstTyper::VisitAssignment(Assignment* expr) {

  // TODO(rossberg): Can we clean this up?

  if (expr->is_compound()) {

    // Collect type feedback.

    Expression* target = expr->target();

    Property* prop = target->AsProperty();

    if (prop != NULL) {

      prop->RecordTypeFeedback(oracle(), zone());

      expr->RecordTypeFeedback(oracle(), zone());

    }

    RECURSE(Visit(expr->binary_operation()));

    NarrowType(expr, expr->binary_operation()->bounds());

  } else {

    // Collect type feedback.

    if (expr->target()->IsProperty()) {

      expr->RecordTypeFeedback(oracle(), zone());

    }

    RECURSE(Visit(expr->target()));

    RECURSE(Visit(expr->value()));

    NarrowType(expr, expr->value()->bounds());

  }

  VariableProxy* proxy = expr->target()->AsVariableProxy();

  if (proxy != NULL && proxy->var()->IsStackAllocated()) {

    store_.Seq(variable_index(proxy->var()), Effect(expr->bounds()));

  }

}

void AstTyper::VisitYield(Yield* expr) {

  RECURSE(Visit(expr->generator_object()));

  RECURSE(Visit(expr->expression()));

  // We don't know anything about the result type.

}

void AstTyper::VisitThrow(Throw* expr) {

  RECURSE(Visit(expr->exception()));

  // TODO(rossberg): is it worth having a non-termination effect?

  NarrowType(expr, Bounds(Type::None(), isolate_));

}

void AstTyper::VisitProperty(Property* expr) {

  // Collect type feedback.

  expr->RecordTypeFeedback(oracle(), zone());

  RECURSE(Visit(expr->obj()));

  RECURSE(Visit(expr->key()));

  // We don't know anything about the result type.

}

void AstTyper::VisitCall(Call* expr) {

  // Collect type feedback.

  Expression* callee = expr->expression();

  Property* prop = callee->AsProperty();

  if (prop != NULL) {

    if (prop->key()->IsPropertyName())

      expr->RecordTypeFeedback(oracle(), CALL_AS_METHOD);

  } else {

    expr->RecordTypeFeedback(oracle(), CALL_AS_FUNCTION);

  }

  RECURSE(Visit(expr->expression()));

  ZoneList<Expression*>* args = expr->arguments();

  for (int i = 0; i < args->length(); ++i) {

    Expression* arg = args->at(i);

    RECURSE(Visit(arg));

  }

  VariableProxy* proxy = expr->expression()->AsVariableProxy();

  if (proxy != NULL && proxy->var()->is_possibly_eval(isolate())) {

    store_.Forget();  // Eval could do whatever to local variables.

  }

  // We don't know anything about the result type.

}

void AstTyper::VisitCallNew(CallNew* expr) {

  // Collect type feedback.

  expr->RecordTypeFeedback(oracle());

  RECURSE(Visit(expr->expression()));

  ZoneList<Expression*>* args = expr->arguments();

  for (int i = 0; i < args->length(); ++i) {

    Expression* arg = args->at(i);

    RECURSE(Visit(arg));

  }

  // We don't know anything about the result type.

}

void AstTyper::VisitCallRuntime(CallRuntime* expr) {

  ZoneList<Expression*>* args = expr->arguments();

  for (int i = 0; i < args->length(); ++i) {

    Expression* arg = args->at(i);

    RECURSE(Visit(arg));

  }

  // We don't know anything about the result type.

}

void AstTyper::VisitUnaryOperation(UnaryOperation* expr) {

  // Collect type feedback.

  if (expr->op() == Token::NOT) {

    // TODO(rossberg): only do in test or value context.

    expr->expression()->RecordToBooleanTypeFeedback(oracle());

  }

  RECURSE(Visit(expr->expression()));

  switch (expr->op()) {

    case Token::NOT:

    case Token::DELETE:

      NarrowType(expr, Bounds(Type::Boolean(), isolate_));

      break;

    case Token::VOID:

      NarrowType(expr, Bounds(Type::Undefined(), isolate_));

      break;

    case Token::TYPEOF:

      NarrowType(expr, Bounds(Type::InternalizedString(), isolate_));

      break;

    default:

      UNREACHABLE();

  }

}

void AstTyper::VisitCountOperation(CountOperation* expr) {

  // Collect type feedback.

  expr->RecordTypeFeedback(oracle(), zone());

  Property* prop = expr->expression()->AsProperty();

  if (prop != NULL) {

    prop->RecordTypeFeedback(oracle(), zone());

  }

  RECURSE(Visit(expr->expression()));

  NarrowType(expr, Bounds(Type::Smi(), Type::Number(), isolate_));

  VariableProxy* proxy = expr->expression()->AsVariableProxy();

  if (proxy != NULL && proxy->var()->IsStackAllocated()) {

    store_.Seq(variable_index(proxy->var()), Effect(expr->bounds()));

  }

}

void AstTyper::VisitBinaryOperation(BinaryOperation* expr) {

  // Collect type feedback.

  Handle<Type> type, left_type, right_type;

  Maybe<int> fixed_right_arg;

  oracle()->BinaryType(expr->BinaryOperationFeedbackId(),

      &left_type, &right_type, &type, &fixed_right_arg, expr->op());

  NarrowLowerType(expr, type);

  NarrowLowerType(expr->left(), left_type);

  NarrowLowerType(expr->right(), right_type);

  expr->set_fixed_right_arg(fixed_right_arg);

  if (expr->op() == Token::OR || expr->op() == Token::AND) {

    expr->left()->RecordToBooleanTypeFeedback(oracle());

  }

  switch (expr->op()) {

    case Token::COMMA:

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      NarrowType(expr, expr->right()->bounds());

      break;

    case Token::OR:

    case Token::AND: {

      Effects left_effects = EnterEffects();

      RECURSE(Visit(expr->left()));

      ExitEffects();

      Effects right_effects = EnterEffects();

      RECURSE(Visit(expr->right()));

      ExitEffects();

      left_effects.Alt(right_effects);

      store_.Seq(left_effects);

      NarrowType(expr, Bounds::Either(

          expr->left()->bounds(), expr->right()->bounds(), isolate_));

      break;

    }

    case Token::BIT_OR:

    case Token::BIT_AND: {

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      Handle<Type> upper(

          Type::Union(

              expr->left()->bounds().upper, expr->right()->bounds().upper),

          isolate_);

      if (!upper->Is(Type::Signed32()))

        upper = handle(Type::Signed32(), isolate_);

      Handle<Type> lower(Type::Intersect(

          handle(Type::Smi(), isolate_), upper), isolate_);

      NarrowType(expr, Bounds(lower, upper));

      break;

    }

    case Token::BIT_XOR:

    case Token::SHL:

    case Token::SAR:

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      NarrowType(expr, Bounds(Type::Smi(), Type::Signed32(), isolate_));

      break;

    case Token::SHR:

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      // TODO(rossberg): The upper bound would be Unsigned32, but since there

      // is no 'positive Smi' type for the lower bound, we use the smallest

      // union of Smi and Unsigned32 as upper bound instead.

      NarrowType(expr, Bounds(Type::Smi(), Type::Number(), isolate_));

      break;

    case Token::ADD: {

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      Bounds l = expr->left()->bounds();

      Bounds r = expr->right()->bounds();

      Type* lower =

          l.lower->Is(Type::None()) || r.lower->Is(Type::None()) ?

              Type::None() :

          l.lower->Is(Type::String()) || r.lower->Is(Type::String()) ?

              Type::String() :

          l.lower->Is(Type::Number()) && r.lower->Is(Type::Number()) ?

              Type::Smi() : Type::None();

      Type* upper =

          l.upper->Is(Type::String()) || r.upper->Is(Type::String()) ?

              Type::String() :

          l.upper->Is(Type::Number()) && r.upper->Is(Type::Number()) ?

              Type::Number() : Type::NumberOrString();

      NarrowType(expr, Bounds(lower, upper, isolate_));

      break;

    }

    case Token::SUB:

    case Token::MUL:

    case Token::DIV:

    case Token::MOD:

      RECURSE(Visit(expr->left()));

      RECURSE(Visit(expr->right()));

      NarrowType(expr, Bounds(Type::Smi(), Type::Number(), isolate_));

      break;

    default:

      UNREACHABLE();

  }

}

void AstTyper::VisitCompareOperation(CompareOperation* expr) {

  // Collect type feedback.

  Handle<Type> left_type, right_type, combined_type;

  oracle()->CompareType(expr->CompareOperationFeedbackId(),

      &left_type, &right_type, &combined_type);

  NarrowLowerType(expr->left(), left_type);

  NarrowLowerType(expr->right(), right_type);

  expr->set_combined_type(combined_type);

  RECURSE(Visit(expr->left()));

  RECURSE(Visit(expr->right()));

  NarrowType(expr, Bounds(Type::Boolean(), isolate_));

}

void AstTyper::VisitThisFunction(ThisFunction* expr) {

}

void AstTyper::VisitDeclarations(ZoneList<Declaration*>* decls) {

  for (int i = 0; i < decls->length(); ++i) {

    Declaration* decl = decls->at(i);

    RECURSE(Visit(decl));

  }

}

void AstTyper::VisitVariableDeclaration(VariableDeclaration* declaration) {

}

void AstTyper::VisitFunctionDeclaration(FunctionDeclaration* declaration) {

  RECURSE(Visit(declaration->fun()));

}

void AstTyper::VisitModuleDeclaration(ModuleDeclaration* declaration) {

  RECURSE(Visit(declaration->module()));

}

void AstTyper::VisitImportDeclaration(ImportDeclaration* declaration) {

  RECURSE(Visit(declaration->module()));

}

void AstTyper::VisitExportDeclaration(ExportDeclaration* declaration) {

}

void AstTyper::VisitModuleLiteral(ModuleLiteral* module) {

  RECURSE(Visit(module->body()));

}

void AstTyper::VisitModuleVariable(ModuleVariable* module) {

}

void AstTyper::VisitModulePath(ModulePath* module) {

  RECURSE(Visit(module->module()));

}

void AstTyper::VisitModuleUrl(ModuleUrl* module) {

}

void AstTyper::VisitModuleStatement(ModuleStatement* stmt) {

  RECURSE(Visit(stmt->body()));

}

} }  // namespace v8::internal