Compute expected type for variables

src/typing.cc

 // 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
@@ skipping 56 matching lines @@
 
 #undef RECURSE
 
 #define RECURSE(call)                \
   do {                               \
     ASSERT(!HasStackOverflow());     \
     call;                            \
     if (HasStackOverflow()) return;  \
   } while (false)
 
+#define RECURSE_EXPR(call, expected_type)              \
+  do {                                                 \
+    Handle<Type> save = expected_type_;                \
+    expected_type_ = handle(expected_type, isolate_);  \
+    RECURSE(call);                                     \
+    expected_type_ = save;                             \
+  } while (false)
+
 
 void AstTyper::VisitStatements(ZoneList<Statement*>* stmts) {
   for (int i = 0; i < stmts->length(); ++i) {
     Statement* stmt = stmts->at(i);
     RECURSE(Visit(stmt));
   }
 }
 
 
 void AstTyper::VisitBlock(Block* stmt) {
   RECURSE(VisitStatements(stmt->statements()));
 }
 
 
 void AstTyper::VisitExpressionStatement(ExpressionStatement* stmt) {
-  RECURSE(Visit(stmt->expression()));
+  RECURSE_EXPR(Visit(stmt->expression()), Type::Any());
 }
 
 
 void AstTyper::VisitEmptyStatement(EmptyStatement* stmt) {
 }
 
 
 void AstTyper::VisitIfStatement(IfStatement* stmt) {
-  RECURSE(Visit(stmt->condition()));
-  RECURSE(Visit(stmt->then_statement()));
-  RECURSE(Visit(stmt->else_statement()));
-
+  // Collect type feedback.
   if (!stmt->condition()->ToBooleanIsTrue() &&
       !stmt->condition()->ToBooleanIsFalse()) {
     stmt->condition()->RecordToBooleanTypeFeedback(oracle());
   }
+
+  RECURSE_EXPR(Visit(stmt->condition()), Type::Boolean());
+  RECURSE(Visit(stmt->then_statement()));
+  RECURSE(Visit(stmt->else_statement()));
 }
 
 
 void AstTyper::VisitContinueStatement(ContinueStatement* stmt) {
 }
 
 
 void AstTyper::VisitBreakStatement(BreakStatement* stmt) {
 }
 
 
 void AstTyper::VisitReturnStatement(ReturnStatement* stmt) {
-  RECURSE(Visit(stmt->expression()));
-
+  // Collect type feedback.
   // TODO(rossberg): we only need this for inlining into test contexts...
   stmt->expression()->RecordToBooleanTypeFeedback(oracle());
+
+  RECURSE_EXPR(Visit(stmt->expression()), Type::Any());
 }
 
 
 void AstTyper::VisitWithStatement(WithStatement* stmt) {
-  RECURSE(stmt->expression());
+  RECURSE_EXPR(stmt->expression(), Type::Receiver());
   RECURSE(stmt->statement());
 }
 
 
 void AstTyper::VisitSwitchStatement(SwitchStatement* stmt) {
-  RECURSE(Visit(stmt->tag()));
+  RECURSE_EXPR(Visit(stmt->tag()), Type::Any());
   ZoneList<CaseClause*>* clauses = stmt->cases();
   SwitchStatement::SwitchType switch_type = stmt->switch_type();
   for (int i = 0; i < clauses->length(); ++i) {
     CaseClause* clause = clauses->at(i);
     if (!clause->is_default()) {
       Expression* label = clause->label();
-      RECURSE(Visit(label));
+      RECURSE_EXPR(Visit(label), *stmt->tag()->upper_type());
 
       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(VisitStatements(clause->statements()));
   }
   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::VisitDoWhileStatement(DoWhileStatement* stmt) {
-  RECURSE(Visit(stmt->body()));
-  RECURSE(Visit(stmt->cond()));
-
+  // Collect type feedback.
   if (!stmt->cond()->ToBooleanIsTrue()) {
     stmt->cond()->RecordToBooleanTypeFeedback(oracle());
   }
+
+  RECURSE(Visit(stmt->body()));
+  RECURSE_EXPR(Visit(stmt->cond()), Type::Boolean());
 }
 
 
 void AstTyper::VisitWhileStatement(WhileStatement* stmt) {
-  RECURSE(Visit(stmt->cond()));
-  RECURSE(Visit(stmt->body()));
-
+  // Collect type feedback.
   if (!stmt->cond()->ToBooleanIsTrue()) {
     stmt->cond()->RecordToBooleanTypeFeedback(oracle());
   }
+
+  RECURSE_EXPR(Visit(stmt->cond()), Type::Boolean());
+  RECURSE(Visit(stmt->body()));
 }
 
 
 void AstTyper::VisitForStatement(ForStatement* stmt) {
   if (stmt->init() != NULL) {
     RECURSE(Visit(stmt->init()));
   }
   if (stmt->cond() != NULL) {
-    RECURSE(Visit(stmt->cond()));
+    // Collect type feedback.
+    stmt->cond()->RecordToBooleanTypeFeedback(oracle());
 
-    stmt->cond()->RecordToBooleanTypeFeedback(oracle());
+    RECURSE_EXPR(Visit(stmt->cond()), Type::Boolean());
   }
   RECURSE(Visit(stmt->body()));
   if (stmt->next() != NULL) {
     RECURSE(Visit(stmt->next()));
   }
 }
 
 
 void AstTyper::VisitForInStatement(ForInStatement* stmt) {
-  RECURSE(Visit(stmt->enumerable()));
+  // Collect type feedback.
+  stmt->RecordTypeFeedback(oracle());
+
+  RECURSE_EXPR(Visit(stmt->enumerable()), Type::Receiver());
   RECURSE(Visit(stmt->body()));
-
-  stmt->RecordTypeFeedback(oracle());
 }
 
 
 void AstTyper::VisitForOfStatement(ForOfStatement* stmt) {
-  RECURSE(Visit(stmt->iterable()));
+  RECURSE_EXPR(Visit(stmt->iterable()), Type::Receiver());
   RECURSE(Visit(stmt->body()));
 }
 
 
 void AstTyper::VisitTryCatchStatement(TryCatchStatement* stmt) {
   RECURSE(Visit(stmt->try_block()));
   RECURSE(Visit(stmt->catch_block()));
 }
 
 
 void AstTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
   RECURSE(Visit(stmt->try_block()));
   RECURSE(Visit(stmt->finally_block()));
 }
 
 
 void AstTyper::VisitDebuggerStatement(DebuggerStatement* stmt) {
 }
 
 
 void AstTyper::VisitFunctionLiteral(FunctionLiteral* expr) {
 }
 
 
 void AstTyper::VisitSharedFunctionInfoLiteral(SharedFunctionInfoLiteral* expr) {
 }
 
 
 void AstTyper::VisitConditional(Conditional* expr) {
-  RECURSE(Visit(expr->condition()));
+  // Collect type feedback.
+  expr->condition()->RecordToBooleanTypeFeedback(oracle());
+
+  RECURSE_EXPR(Visit(expr->condition()), Type::Boolean());
   RECURSE(Visit(expr->then_expression()));
   RECURSE(Visit(expr->else_expression()));
 
-  expr->condition()->RecordToBooleanTypeFeedback(oracle());
-
   MergeLowerType(expr, Type::Intersect(
       expr->then_expression()->lower_type(),
       expr->else_expression()->lower_type()));
   MergeUpperType(expr, Type::Union(
       expr->then_expression()->upper_type(),
       expr->else_expression()->upper_type()));
 }
 
 
 void AstTyper::VisitVariableProxy(VariableProxy* expr) {
   // TODO(rossberg): typing of variables
+
+  Variable* var = expr->var();
+  var->set_expected_type(handle(
+      Type::Intersect(var->expected_type(), expected_type_), isolate_));

[Jakob Kummerow, 2013/07/09 16:01:50]

As discussed offline, I still think a Union would make more sense here.

 }
 
 
 void AstTyper::VisitLiteral(Literal* expr) {
   Type* type = Type::Constant(expr->value(), isolate_);
   MergeLowerType(expr, type);
   MergeUpperType(expr, type);
 }
 
 
 void AstTyper::VisitRegExpLiteral(RegExpLiteral* expr) {
   MergeLowerType(expr, Type::RegExp());
   MergeUpperType(expr, Type::RegExp());
 }
 
 
 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);
-    RECURSE(Visit(prop->value()));
 
+    // 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_EXPR(Visit(prop->value()), Type::Any());
   }
 
   MergeLowerType(expr, Type::Object());
   MergeUpperType(expr, Type::Object());
 }
 
 
 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));
+    RECURSE_EXPR(Visit(value), Type::Any());
   }
 
   MergeLowerType(expr, Type::Array());
   MergeUpperType(expr, Type::Array());
 }
 
 
 void AstTyper::VisitAssignment(Assignment* expr) {
   // TODO(rossberg): Can we clean this up?
   if (expr->is_compound()) {
-    RECURSE(Visit(expr->binary_operation()));
-
+    // Collect type feedback.
     Expression* target = expr->target();
     Property* prop = target->AsProperty();
     if (prop != NULL) {
       prop->RecordTypeFeedback(oracle(), zone());
       if (!prop->key()->IsPropertyName()) {  // i.e., keyed
         expr->RecordTypeFeedback(oracle(), zone());
       }
     }
+
+    RECURSE_EXPR(Visit(expr->binary_operation()), Type::Any());
+    MergeLowerType(expr, expr->binary_operation()->lower_type());
+    MergeUpperType(expr, expr->binary_operation()->upper_type());
   } else {
-    RECURSE(Visit(expr->target()));
-    RECURSE(Visit(expr->value()));
-
+    // Collect type feedback.
     if (expr->target()->AsProperty()) {
       expr->RecordTypeFeedback(oracle(), zone());
     }
 
+    RECURSE(Visit(expr->target()));
+    RECURSE(Visit(expr->value()));

[Jakob Kummerow, 2013/07/09 16:01:50]

Shouldn't this be RECURSE_EXPR(_, Type::Any())?

     MergeLowerType(expr, expr->value()->lower_type());
     MergeUpperType(expr, expr->value()->upper_type());
   }
   // TODO(rossberg): handle target variables
 }
 
 
 void AstTyper::VisitYield(Yield* expr) {
-  RECURSE(Visit(expr->generator_object()));
-  RECURSE(Visit(expr->expression()));
+  RECURSE_EXPR(Visit(expr->generator_object()), Type::Receiver());
+  RECURSE_EXPR(Visit(expr->expression()), Type::Any());
 
-  // We don't know anything about the type.
+  // We don't know anything about the result type.
 }
 
 
 void AstTyper::VisitThrow(Throw* expr) {
-  RECURSE(Visit(expr->exception()));
+  RECURSE_EXPR(Visit(expr->exception()), Type::Any());
 
   // Lower type is None already.
   MergeUpperType(expr, Type::None());
 }
 
 
 void AstTyper::VisitProperty(Property* expr) {
-  RECURSE(Visit(expr->obj()));
-  RECURSE(Visit(expr->key()));
-
+  // Collect type feedback.
   expr->RecordTypeFeedback(oracle(), zone());
 
-  // We don't know anything about the type.
+  RECURSE_EXPR(Visit(expr->obj()), Type::Receiver());
+  RECURSE_EXPR(Visit(expr->key()), Type::Name());

[Jakob Kummerow, 2013/07/09 16:01:50]

I'm pretty sure that the key can also be a number.

+
+  // We don't know anything about the result type.
 }
 
 
 void AstTyper::VisitCall(Call* expr) {
-  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));
-  }
-
+  // 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);
   }
 
-  // We don't know anything about the type.
+  RECURSE_EXPR(Visit(expr->expression()), Type::Function());
+  ZoneList<Expression*>* args = expr->arguments();
+  for (int i = 0; i < args->length(); ++i) {
+    Expression* arg = args->at(i);
+    RECURSE_EXPR(Visit(arg), Type::Any());
+  }
+
+  // We don't know anything about the result type.
 }
 
 
 void AstTyper::VisitCallNew(CallNew* expr) {
-  RECURSE(Visit(expr->expression()));
+  // Collect type feedback.
+  expr->RecordTypeFeedback(oracle());
+
+  RECURSE_EXPR(Visit(expr->expression()), Type::Function());
   ZoneList<Expression*>* args = expr->arguments();
   for (int i = 0; i < args->length(); ++i) {
     Expression* arg = args->at(i);
-    RECURSE(Visit(arg));
+    RECURSE_EXPR(Visit(arg), Type::Any());
   }
 
-  expr->RecordTypeFeedback(oracle());
-
-  // We don't know anything about the type.
+  // 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));
+    RECURSE_EXPR(Visit(arg), Type::Any());
   }
 
-  // We don't know anything about the type.
+  // We don't know anything about the result type.
 }
 
 
 void AstTyper::VisitUnaryOperation(UnaryOperation* expr) {
-  RECURSE(Visit(expr->expression()));
-
   // Collect type feedback.
   Handle<Type> op_type = oracle()->UnaryType(expr->UnaryOperationFeedbackId());
   MergeLowerType(expr->expression(), op_type);
   if (expr->op() == Token::NOT) {
     // TODO(rossberg): only do in test or value context.
     expr->expression()->RecordToBooleanTypeFeedback(oracle());
   }
 
   switch (expr->op()) {
     case Token::NOT:
+      RECURSE_EXPR(Visit(expr->expression()), Type::Boolean());
+      MergeLowerType(expr, Type::Boolean());
+      MergeUpperType(expr, Type::Boolean());
+      break;
     case Token::DELETE:
+      RECURSE_EXPR(Visit(expr->expression()), Type::Any());
       MergeLowerType(expr, Type::Boolean());
       MergeUpperType(expr, Type::Boolean());
       break;
     case Token::VOID:
+      RECURSE_EXPR(Visit(expr->expression()), Type::Any());
       MergeLowerType(expr, Type::Undefined());
       MergeUpperType(expr, Type::Undefined());
       break;
     case Token::ADD:
     case Token::SUB: {
+      RECURSE_EXPR(Visit(expr->expression()), Type::Number());
       MergeLowerType(expr, Type::Smi());
       Type* upper = *expr->expression()->upper_type();
       MergeUpperType(expr, upper->Is(Type::Number()) ? upper : Type::Number());
       break;
     }
     case Token::BIT_NOT:
+      RECURSE_EXPR(Visit(expr->expression()), Type::Signed32());
       MergeLowerType(expr, Type::Smi());
       MergeUpperType(expr, Type::Signed32());
       break;
     case Token::TYPEOF:
+      RECURSE_EXPR(Visit(expr->expression()), Type::Any());
       MergeLowerType(expr, Type::InternalizedString());
       MergeUpperType(expr, Type::InternalizedString());
       break;
     default:
       UNREACHABLE();
   }
 }
 
 
 void AstTyper::VisitCountOperation(CountOperation* expr) {
-  RECURSE(Visit(expr->expression()));
-
+  // Collect type feedback.
   expr->RecordTypeFeedback(oracle(), zone());
   Property* prop = expr->expression()->AsProperty();
   if (prop != NULL) {
     prop->RecordTypeFeedback(oracle(), zone());
   }
 
+  RECURSE_EXPR(Visit(expr->expression()), Type::Number());
   MergeLowerType(expr, Type::Smi());
   MergeUpperType(expr, Type::Number());
 }
 
 
 void AstTyper::VisitBinaryOperation(BinaryOperation* expr) {
-  RECURSE(Visit(expr->left()));
-  RECURSE(Visit(expr->right()));
-
   // 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);
   MergeLowerType(expr, type);
   MergeLowerType(expr->left(), left_type);
   MergeLowerType(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_EXPR(Visit(expr->left()), Type::Any());
+      RECURSE_EXPR(Visit(expr->right()), Type::Any());
       MergeLowerType(expr, expr->right()->lower_type());
       MergeUpperType(expr, expr->right()->upper_type());
       break;
     case Token::OR:
     case Token::AND:
+      RECURSE_EXPR(Visit(expr->left()), Type::Any());
+      RECURSE_EXPR(Visit(expr->right()), Type::Any());
       MergeLowerType(expr, Type::Intersect(
           expr->left()->lower_type(), expr->right()->lower_type()));
       MergeUpperType(expr, Type::Union(
           expr->left()->upper_type(), expr->right()->upper_type()));
       break;
     case Token::BIT_OR:
     case Token::BIT_AND: {
+      RECURSE_EXPR(Visit(expr->left()), Type::Signed32());
+      RECURSE_EXPR(Visit(expr->right()), Type::Signed32());
       MergeLowerType(expr, Type::Smi());
       Type* upper =
           Type::Union(expr->left()->upper_type(), expr->right()->upper_type());
       MergeUpperType(expr,
           upper->Is(Type::Signed32()) ? upper : Type::Signed32());
       break;
     }
     case Token::BIT_XOR:
+      RECURSE_EXPR(Visit(expr->left()), Type::Signed32());
+      RECURSE_EXPR(Visit(expr->right()), Type::Signed32());
+      MergeLowerType(expr, Type::Smi());
+      MergeUpperType(expr, Type::Signed32());
+      break;
     case Token::SHL:
     case Token::SAR:
+      RECURSE_EXPR(Visit(expr->left()), Type::Signed32());
+      RECURSE_EXPR(Visit(expr->right()), Type::Unsigned32());
       MergeLowerType(expr, Type::Smi());
       MergeUpperType(expr, Type::Signed32());
       break;
     case Token::SHR:
+      RECURSE_EXPR(Visit(expr->left()), Type::Unsigned32());
+      RECURSE_EXPR(Visit(expr->right()), Type::Unsigned32());
       MergeLowerType(expr, Type::Smi());
       MergeUpperType(expr, Type::Unsigned32());
       break;
     case Token::ADD: {
+      RECURSE_EXPR(Visit(expr->left()), Type::NumberOrString());
+      RECURSE_EXPR(Visit(expr->right()), Type::NumberOrString());
       Handle<Type> l = expr->left()->lower_type();
       Handle<Type> r = expr->right()->lower_type();
       MergeLowerType(expr,
           l->Is(Type::Number()) && r->Is(Type::Number()) ? Type::Smi() :
           l->Is(Type::String()) || r->Is(Type::String()) ? Type::String() :
               Type::None());
       l = expr->left()->upper_type();
       r = expr->right()->upper_type();
       MergeUpperType(expr,
           l->Is(Type::Number()) && r->Is(Type::Number()) ? Type::Number() :
           l->Is(Type::String()) || r->Is(Type::String()) ? Type::String() :
               Type::NumberOrString());
       break;
     }
     case Token::SUB:
     case Token::MUL:
     case Token::DIV:
     case Token::MOD:
+      RECURSE_EXPR(Visit(expr->left()), Type::Number());
+      RECURSE_EXPR(Visit(expr->right()), Type::Number());
       MergeLowerType(expr, Type::Smi());
       MergeUpperType(expr, Type::Number());
       break;
     default:
       UNREACHABLE();
   }
 }
 
 
 void AstTyper::VisitCompareOperation(CompareOperation* expr) {
-  RECURSE(Visit(expr->left()));
-  RECURSE(Visit(expr->right()));
-
   // Collect type feedback.
   Handle<Type> left_type, right_type, combined_type;
   oracle()->CompareType(expr->CompareOperationFeedbackId(),
       &left_type, &right_type, &combined_type);
   MergeLowerType(expr->left(), left_type);
   MergeLowerType(expr->right(), right_type);
   expr->set_combined_type(combined_type);
 
+  switch (expr->op()) {
+    case Token::EQ:
+    case Token::NE:
+    case Token::EQ_STRICT:
+    case Token::NE_STRICT:
+      RECURSE_EXPR(Visit(expr->left()), Type::Any());
+      RECURSE_EXPR(Visit(expr->right()), Type::Any());
+      break;
+    case Token::LT:
+    case Token::GT:
+    case Token::LTE:
+    case Token::GTE:
+      RECURSE_EXPR(Visit(expr->left()), Type::NumberOrString());
+      RECURSE_EXPR(Visit(expr->right()), Type::NumberOrString());
+      break;
+    case Token::INSTANCEOF:
+      RECURSE_EXPR(Visit(expr->left()), Type::Receiver());
+      RECURSE_EXPR(Visit(expr->right()), Type::Function());
+      break;
+    case Token::IN:
+      RECURSE_EXPR(Visit(expr->left()), Type::Name());
+      RECURSE_EXPR(Visit(expr->right()), Type::Receiver());
+      break;
+    default:
+      UNREACHABLE();
+  }
   MergeLowerType(expr, Type::Boolean());
   MergeUpperType(expr, Type::Boolean());
 }
 
 
 void AstTyper::VisitThisFunction(ThisFunction* expr) {
 }
 
 
 void AstTyper::VisitDeclarations(ZoneList<Declaration*>* decls) {
@@ skipping 44 matching lines @@
 void AstTyper::VisitModuleUrl(ModuleUrl* module) {
 }
 
 
 void AstTyper::VisitModuleStatement(ModuleStatement* stmt) {
   RECURSE(Visit(stmt->body()));
 }
 
 
 } }  // namespace v8::internal