src/typing-asm.cc

   1 // Copyright 2015 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/typing-asm.h"
   8
   9 #include "src/ast.h"
  10 #include "src/codegen.h"
  11 #include "src/scopes.h"
  12 #include "src/zone-type-cache.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace {
  17
  18 base::LazyInstance<ZoneTypeCache>::type kCache = LAZY_INSTANCE_INITIALIZER;
  19
  20 }  // namespace
  21
  22
  23 #define FAIL(node, msg)                                        \
  24   do {                                                         \
  25     valid_ = false;                                            \
  26     int line = node->position() == RelocInfo::kNoPosition      \
  27                    ? -1                                        \
  28                    : script_->GetLineNumber(node->position()); \
  29     base::OS::SNPrintF(error_message_, sizeof(error_message_), \
  30                        "asm: line %d: %s\n", line + 1, msg);   \
  31     return;                                                    \
  32   } while (false)
  33
  34
  35 #define RECURSE(call)               \
  36   do {                              \
  37     DCHECK(!HasStackOverflow());    \
  38     call;                           \
  39     if (HasStackOverflow()) return; \
  40     if (!valid_) return;            \
  41   } while (false)
  42
  43
  44 AsmTyper::AsmTyper(Isolate* isolate, Zone* zone, Script* script,
  45                    FunctionLiteral* root)
  46     : script_(script),
  47       root_(root),
  48       valid_(true),
  49       stdlib_types_(zone),
  50       stdlib_heap_types_(zone),
  51       stdlib_math_types_(zone),
  52       global_variable_type_(HashMap::PointersMatch,
  53                             ZoneHashMap::kDefaultHashMapCapacity,
  54                             ZoneAllocationPolicy(zone)),
  55       local_variable_type_(HashMap::PointersMatch,
  56                            ZoneHashMap::kDefaultHashMapCapacity,
  57                            ZoneAllocationPolicy(zone)),
  58       in_function_(false),
  59       building_function_tables_(false),
  60       cache_(kCache.Get()) {
  61   InitializeAstVisitor(isolate, zone);
  62   InitializeStdlib();
  63 }
  64
  65
  66 bool AsmTyper::Validate() {
  67   VisitAsmModule(root_);
  68   return valid_ && !HasStackOverflow();
  69 }
  70
  71
  72 void AsmTyper::VisitAsmModule(FunctionLiteral* fun) {
  73   Scope* scope = fun->scope();
  74   if (!scope->is_function_scope()) FAIL(fun, "not at function scope");
  75
  76   // Module parameters.
  77   for (int i = 0; i < scope->num_parameters(); ++i) {
  78     Variable* param = scope->parameter(i);
  79     DCHECK(GetType(param) == NULL);
  80     SetType(param, Type::None(zone()));
  81   }
  82
  83   ZoneList<Declaration*>* decls = scope->declarations();
  84
  85   // Set all globals to type Any.
  86   VariableDeclaration* decl = scope->function();
  87   if (decl != NULL) SetType(decl->proxy()->var(), Type::None());
  88   RECURSE(VisitDeclarations(scope->declarations()));
  89
  90   // Validate global variables.
  91   RECURSE(VisitStatements(fun->body()));
  92
  93   // Validate function annotations.
  94   for (int i = 0; i < decls->length(); ++i) {
  95     FunctionDeclaration* decl = decls->at(i)->AsFunctionDeclaration();
  96     if (decl != NULL) {
  97       RECURSE(VisitFunctionAnnotation(decl->fun()));
  98       Variable* var = decl->proxy()->var();
  99       DCHECK(GetType(var) == NULL);
 100       SetType(var, computed_type_);
 101       DCHECK(GetType(var) != NULL);
 102     }
 103   }
 104
 105   // Build function tables.
 106   building_function_tables_ = true;
 107   RECURSE(VisitStatements(fun->body()));
 108   building_function_tables_ = false;
 109
 110   // Validate function bodies.
 111   for (int i = 0; i < decls->length(); ++i) {
 112     FunctionDeclaration* decl = decls->at(i)->AsFunctionDeclaration();
 113     if (decl != NULL) {
 114       RECURSE(
 115           VisitWithExpectation(decl->fun(), Type::Any(zone()), "UNREACHABLE"));
 116       if (!computed_type_->IsFunction()) {
 117         FAIL(decl->fun(), "function literal expected to be a function");
 118       }
 119     }
 120   }
 121
 122   // Validate exports.
 123   ReturnStatement* stmt = fun->body()->last()->AsReturnStatement();
 124   RECURSE(VisitWithExpectation(stmt->expression(), Type::Object(),
 125                                "expected object export"));
 126 }
 127
 128
 129 void AsmTyper::VisitVariableDeclaration(VariableDeclaration* decl) {
 130   Variable* var = decl->proxy()->var();
 131   if (var->location() != VariableLocation::PARAMETER) {
 132     if (GetType(var) == NULL) {
 133       SetType(var, Type::Any(zone()));
 134     } else {
 135       DCHECK(!GetType(var)->IsFunction());
 136     }
 137   }
 138   DCHECK(GetType(var) != NULL);
 139   intish_ = 0;
 140 }
 141
 142
 143 void AsmTyper::VisitFunctionDeclaration(FunctionDeclaration* decl) {
 144   if (in_function_) {
 145     FAIL(decl, "function declared inside another");
 146   }
 147 }
 148
 149
 150 void AsmTyper::VisitFunctionAnnotation(FunctionLiteral* fun) {
 151   // Extract result type.
 152   ZoneList<Statement*>* body = fun->body();
 153   Type* result_type = Type::Undefined(zone());
 154   if (body->length() > 0) {
 155     ReturnStatement* stmt = body->last()->AsReturnStatement();
 156     if (stmt != NULL) {
 157       RECURSE(VisitExpressionAnnotation(stmt->expression()));
 158       result_type = computed_type_;
 159     }
 160   }
 161   Type::FunctionType* type =
 162       Type::Function(result_type, Type::Any(), fun->parameter_count(), zone())
 163           ->AsFunction();
 164
 165   // Extract parameter types.
 166   bool good = true;
 167   for (int i = 0; i < fun->parameter_count(); ++i) {
 168     good = false;
 169     if (i >= body->length()) break;
 170     ExpressionStatement* stmt = body->at(i)->AsExpressionStatement();
 171     if (stmt == NULL) break;
 172     Assignment* expr = stmt->expression()->AsAssignment();
 173     if (expr == NULL || expr->is_compound()) break;
 174     VariableProxy* proxy = expr->target()->AsVariableProxy();
 175     if (proxy == NULL) break;
 176     Variable* var = proxy->var();
 177     if (var->location() != VariableLocation::PARAMETER || var->index() != i)
 178       break;
 179     RECURSE(VisitExpressionAnnotation(expr->value()));
 180     SetType(var, computed_type_);
 181     type->InitParameter(i, computed_type_);
 182     good = true;
 183   }
 184   if (!good) FAIL(fun, "missing parameter type annotations");
 185
 186   SetResult(fun, type);
 187 }
 188
 189
 190 void AsmTyper::VisitExpressionAnnotation(Expression* expr) {
 191   // Normal +x or x|0 annotations.
 192   BinaryOperation* bin = expr->AsBinaryOperation();
 193   if (bin != NULL) {
 194     Literal* right = bin->right()->AsLiteral();
 195     if (right != NULL) {
 196       switch (bin->op()) {
 197         case Token::MUL:  // We encode +x as 1*x
 198           if (right->raw_value()->ContainsDot() &&
 199               right->raw_value()->AsNumber() == 1.0) {
 200             SetResult(expr, cache_.kFloat64);
 201             return;
 202           }
 203           break;
 204         case Token::BIT_OR:
 205           if (!right->raw_value()->ContainsDot() &&
 206               right->raw_value()->AsNumber() == 0.0) {
 207             SetResult(expr, cache_.kInt32);
 208             return;
 209           }
 210           break;
 211         default:
 212           break;
 213       }
 214     }
 215     FAIL(expr, "invalid type annotation on binary op");
 216   }
 217
 218   // Numbers or the undefined literal (for empty returns).
 219   if (expr->IsLiteral()) {
 220     RECURSE(VisitWithExpectation(expr, Type::Any(), "invalid literal"));
 221     return;
 222   }
 223
 224   Call* call = expr->AsCall();
 225   if (call != NULL) {
 226     if (call->expression()->IsVariableProxy()) {
 227       RECURSE(VisitWithExpectation(
 228           call->expression(), Type::Any(zone()),
 229           "only fround allowed on expression annotations"));
 230       if (!computed_type_->Is(
 231               Type::Function(cache_.kFloat32, Type::Number(zone()), zone()))) {
 232         FAIL(call->expression(),
 233              "only fround allowed on expression annotations");
 234       }
 235       if (call->arguments()->length() != 1) {
 236         FAIL(call, "invalid argument count calling fround");
 237       }
 238       SetResult(expr, cache_.kFloat32);
 239       return;
 240     }
 241   }
 242
 243   FAIL(expr, "invalid type annotation");
 244 }
 245
 246
 247 void AsmTyper::VisitStatements(ZoneList<Statement*>* stmts) {
 248   for (int i = 0; i < stmts->length(); ++i) {
 249     Statement* stmt = stmts->at(i);
 250     RECURSE(Visit(stmt));
 251   }
 252 }
 253
 254
 255 void AsmTyper::VisitBlock(Block* stmt) {
 256   RECURSE(VisitStatements(stmt->statements()));
 257 }
 258
 259
 260 void AsmTyper::VisitExpressionStatement(ExpressionStatement* stmt) {
 261   RECURSE(VisitWithExpectation(stmt->expression(), Type::Any(),
 262                                "expression statement expected to be any"));
 263 }
 264
 265
 266 void AsmTyper::VisitEmptyStatement(EmptyStatement* stmt) {}
 267
 268
 269 void AsmTyper::VisitEmptyParentheses(EmptyParentheses* expr) { UNREACHABLE(); }
 270
 271
 272 void AsmTyper::VisitIfStatement(IfStatement* stmt) {
 273   if (!in_function_) {
 274     FAIL(stmt, "if statement inside module body");
 275   }
 276   RECURSE(VisitWithExpectation(stmt->condition(), cache_.kInt32,
 277                                "if condition expected to be integer"));
 278   RECURSE(Visit(stmt->then_statement()));
 279   RECURSE(Visit(stmt->else_statement()));
 280 }
 281
 282
 283 void AsmTyper::VisitContinueStatement(ContinueStatement* stmt) {
 284   if (!in_function_) {
 285     FAIL(stmt, "continue statement inside module body");
 286   }
 287 }
 288
 289
 290 void AsmTyper::VisitBreakStatement(BreakStatement* stmt) {
 291   if (!in_function_) {
 292     FAIL(stmt, "continue statement inside module body");
 293   }
 294 }
 295
 296
 297 void AsmTyper::VisitReturnStatement(ReturnStatement* stmt) {
 298   // Handle module return statement in VisitAsmModule.
 299   if (!in_function_) {
 300     return;
 301   }
 302   RECURSE(
 303       VisitWithExpectation(stmt->expression(), return_type_,
 304                            "return expression expected to have return type"));
 305 }
 306
 307
 308 void AsmTyper::VisitWithStatement(WithStatement* stmt) {
 309   FAIL(stmt, "bad with statement");
 310 }
 311
 312
 313 void AsmTyper::VisitSwitchStatement(SwitchStatement* stmt) {
 314   if (!in_function_) {
 315     FAIL(stmt, "switch statement inside module body");
 316   }
 317   RECURSE(VisitWithExpectation(stmt->tag(), cache_.kInt32,
 318                                "switch expression non-integer"));
 319   ZoneList<CaseClause*>* clauses = stmt->cases();
 320   for (int i = 0; i < clauses->length(); ++i) {
 321     CaseClause* clause = clauses->at(i);
 322     if (clause->is_default()) continue;
 323     Expression* label = clause->label();
 324     RECURSE(
 325         VisitWithExpectation(label, cache_.kInt32, "case label non-integer"));
 326     if (!label->IsLiteral()) FAIL(label, "non-literal case label");
 327     Handle<Object> value = label->AsLiteral()->value();
 328     int32_t value32;
 329     if (!value->ToInt32(&value32)) FAIL(label, "illegal case label value");
 330     // TODO(bradnelson): Detect duplicates.
 331     ZoneList<Statement*>* stmts = clause->statements();
 332     RECURSE(VisitStatements(stmts));
 333   }
 334 }
 335
 336
 337 void AsmTyper::VisitCaseClause(CaseClause* clause) { UNREACHABLE(); }
 338
 339
 340 void AsmTyper::VisitDoWhileStatement(DoWhileStatement* stmt) {
 341   if (!in_function_) {
 342     FAIL(stmt, "do statement inside module body");
 343   }
 344   RECURSE(Visit(stmt->body()));
 345   RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 346                                "do condition expected to be integer"));
 347 }
 348
 349
 350 void AsmTyper::VisitWhileStatement(WhileStatement* stmt) {
 351   if (!in_function_) {
 352     FAIL(stmt, "while statement inside module body");
 353   }
 354   RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 355                                "while condition expected to be integer"));
 356   RECURSE(Visit(stmt->body()));
 357 }
 358
 359
 360 void AsmTyper::VisitForStatement(ForStatement* stmt) {
 361   if (!in_function_) {
 362     FAIL(stmt, "for statement inside module body");
 363   }
 364   if (stmt->init() != NULL) {
 365     RECURSE(Visit(stmt->init()));
 366   }
 367   if (stmt->cond() != NULL) {
 368     RECURSE(VisitWithExpectation(stmt->cond(), cache_.kInt32,
 369                                  "for condition expected to be integer"));
 370   }
 371   if (stmt->next() != NULL) {
 372     RECURSE(Visit(stmt->next()));
 373   }
 374   RECURSE(Visit(stmt->body()));
 375 }
 376
 377
 378 void AsmTyper::VisitForInStatement(ForInStatement* stmt) {
 379   FAIL(stmt, "for-in statement encountered");
 380 }
 381
 382
 383 void AsmTyper::VisitForOfStatement(ForOfStatement* stmt) {
 384   FAIL(stmt, "for-of statement encountered");
 385 }
 386
 387
 388 void AsmTyper::VisitTryCatchStatement(TryCatchStatement* stmt) {
 389   FAIL(stmt, "try statement encountered");
 390 }
 391
 392
 393 void AsmTyper::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
 394   FAIL(stmt, "try statement encountered");
 395 }
 396
 397
 398 void AsmTyper::VisitDebuggerStatement(DebuggerStatement* stmt) {
 399   FAIL(stmt, "debugger statement encountered");
 400 }
 401
 402
 403 void AsmTyper::VisitFunctionLiteral(FunctionLiteral* expr) {
 404   Scope* scope = expr->scope();
 405   DCHECK(scope->is_function_scope());
 406   if (in_function_) {
 407     FAIL(expr, "invalid nested function");
 408   }
 409
 410   if (!expr->bounds().upper->IsFunction()) {
 411     FAIL(expr, "invalid function literal");
 412   }
 413
 414   Type::FunctionType* type = expr->bounds().upper->AsFunction();
 415   Type* save_return_type = return_type_;
 416   return_type_ = type->Result();
 417   in_function_ = true;
 418   local_variable_type_.Clear();
 419   RECURSE(VisitDeclarations(scope->declarations()));
 420   RECURSE(VisitStatements(expr->body()));
 421   in_function_ = false;
 422   return_type_ = save_return_type;
 423   IntersectResult(expr, type);
 424 }
 425
 426
 427 void AsmTyper::VisitNativeFunctionLiteral(NativeFunctionLiteral* expr) {
 428   FAIL(expr, "function info literal encountered");
 429 }
 430
 431
 432 void AsmTyper::VisitConditional(Conditional* expr) {
 433   RECURSE(VisitWithExpectation(expr->condition(), cache_.kInt32,
 434                                "condition expected to be integer"));
 435   RECURSE(VisitWithExpectation(
 436       expr->then_expression(), expected_type_,
 437       "conditional then branch type mismatch with enclosing expression"));
 438   Type* then_type = computed_type_;
 439   RECURSE(VisitWithExpectation(
 440       expr->else_expression(), expected_type_,
 441       "conditional else branch type mismatch with enclosing expression"));
 442   Type* else_type = computed_type_;
 443   Type* type = Type::Intersect(then_type, else_type, zone());
 444   if (!(type->Is(cache_.kInt32) || type->Is(cache_.kFloat64))) {
 445     FAIL(expr, "ill-typed conditional");
 446   }
 447   IntersectResult(expr, type);
 448 }
 449
 450
 451 void AsmTyper::VisitVariableProxy(VariableProxy* expr) {
 452   Variable* var = expr->var();
 453   if (GetType(var) == NULL) {
 454     FAIL(expr, "unbound variable");
 455   }
 456   Type* type = Type::Intersect(GetType(var), expected_type_, zone());
 457   if (type->Is(cache_.kInt32)) {
 458     type = cache_.kInt32;
 459   }
 460   SetType(var, type);
 461   intish_ = 0;
 462   IntersectResult(expr, type);
 463 }
 464
 465
 466 void AsmTyper::VisitLiteral(Literal* expr) {
 467   intish_ = 0;
 468   Handle<Object> value = expr->value();
 469   if (value->IsNumber()) {
 470     int32_t i;
 471     uint32_t u;
 472     if (expr->raw_value()->ContainsDot()) {
 473       IntersectResult(expr, cache_.kFloat64);
 474     } else if (value->ToUint32(&u)) {
 475       IntersectResult(expr, cache_.kInt32);
 476     } else if (value->ToInt32(&i)) {
 477       IntersectResult(expr, cache_.kInt32);
 478     } else {
 479       FAIL(expr, "illegal number");
 480     }
 481   } else if (value->IsString()) {
 482     IntersectResult(expr, Type::String());
 483   } else if (value->IsUndefined()) {
 484     IntersectResult(expr, Type::Undefined());
 485   } else {
 486     FAIL(expr, "illegal literal");
 487   }
 488 }
 489
 490
 491 void AsmTyper::VisitRegExpLiteral(RegExpLiteral* expr) {
 492   FAIL(expr, "regular expression encountered");
 493 }
 494
 495
 496 void AsmTyper::VisitObjectLiteral(ObjectLiteral* expr) {
 497   if (in_function_) {
 498     FAIL(expr, "object literal in function");
 499   }
 500   // Allowed for asm module's export declaration.
 501   ZoneList<ObjectLiteralProperty*>* props = expr->properties();
 502   for (int i = 0; i < props->length(); ++i) {
 503     ObjectLiteralProperty* prop = props->at(i);
 504     RECURSE(VisitWithExpectation(prop->value(), Type::Any(zone()),
 505                                  "object property expected to be a function"));
 506     if (!computed_type_->IsFunction()) {
 507       FAIL(prop->value(), "non-function in function table");
 508     }
 509   }
 510   IntersectResult(expr, Type::Object(zone()));
 511 }
 512
 513
 514 void AsmTyper::VisitArrayLiteral(ArrayLiteral* expr) {
 515   if (in_function_) {
 516     FAIL(expr, "array literal inside a function");
 517   }
 518   // Allowed for function tables.
 519   ZoneList<Expression*>* values = expr->values();
 520   Type* elem_type = Type::None(zone());
 521   for (int i = 0; i < values->length(); ++i) {
 522     Expression* value = values->at(i);
 523     RECURSE(VisitWithExpectation(value, Type::Any(), "UNREACHABLE"));
 524     if (!computed_type_->IsFunction()) {
 525       FAIL(value, "array component expected to be a function");
 526     }
 527     elem_type = Type::Union(elem_type, computed_type_, zone());
 528   }
 529   array_size_ = values->length();
 530   IntersectResult(expr, Type::Array(elem_type, zone()));
 531 }
 532
 533
 534 void AsmTyper::VisitAssignment(Assignment* expr) {
 535   // Handle function tables and everything else in different passes.
 536   if (!in_function_) {
 537     if (expr->value()->IsArrayLiteral()) {
 538       if (!building_function_tables_) {
 539         return;
 540       }
 541     } else {
 542       if (building_function_tables_) {
 543         return;
 544       }
 545     }
 546   }
 547   if (expr->is_compound()) FAIL(expr, "compound assignment encountered");
 548   Type* type = expected_type_;
 549   RECURSE(VisitWithExpectation(
 550       expr->value(), type, "assignment value expected to match surrounding"));
 551   if (intish_ != 0) {
 552     FAIL(expr, "value still an intish");
 553   }
 554   RECURSE(VisitWithExpectation(expr->target(), computed_type_,
 555                                "assignment target expected to match value"));
 556   if (intish_ != 0) {
 557     FAIL(expr, "value still an intish");
 558   }
 559   IntersectResult(expr, computed_type_);
 560 }
 561
 562
 563 void AsmTyper::VisitYield(Yield* expr) {
 564   FAIL(expr, "yield expression encountered");
 565 }
 566
 567
 568 void AsmTyper::VisitThrow(Throw* expr) {
 569   FAIL(expr, "throw statement encountered");
 570 }
 571
 572
 573 int AsmTyper::ElementShiftSize(Type* type) {
 574   if (type->Is(cache_.kInt8) || type->Is(cache_.kUint8)) return 0;
 575   if (type->Is(cache_.kInt16) || type->Is(cache_.kUint16)) return 1;
 576   if (type->Is(cache_.kInt32) || type->Is(cache_.kUint32) ||
 577       type->Is(cache_.kFloat32))
 578     return 2;
 579   if (type->Is(cache_.kFloat64)) return 3;
 580   return -1;
 581 }
 582
 583
 584 void AsmTyper::VisitHeapAccess(Property* expr) {
 585   Type::ArrayType* array_type = computed_type_->AsArray();
 586   size_t size = array_size_;
 587   Type* type = array_type->AsArray()->Element();
 588   if (type->IsFunction()) {
 589     BinaryOperation* bin = expr->key()->AsBinaryOperation();
 590     if (bin == NULL || bin->op() != Token::BIT_AND) {
 591       FAIL(expr->key(), "expected & in call");
 592     }
 593     RECURSE(VisitWithExpectation(bin->left(), cache_.kInt32,
 594                                  "array index expected to be integer"));
 595     Literal* right = bin->right()->AsLiteral();
 596     if (right == NULL || right->raw_value()->ContainsDot()) {
 597       FAIL(right, "call mask must be integer");
 598     }
 599     RECURSE(VisitWithExpectation(bin->right(), cache_.kInt32,
 600                                  "call mask expected to be integer"));
 601     if (static_cast<size_t>(right->raw_value()->AsNumber()) != size - 1) {
 602       FAIL(right, "call mask must match function table");
 603     }
 604     bin->set_bounds(Bounds(cache_.kInt32));
 605   } else {
 606     BinaryOperation* bin = expr->key()->AsBinaryOperation();
 607     if (bin == NULL || bin->op() != Token::SAR) {
 608       FAIL(expr->key(), "expected >> in heap access");
 609     }
 610     RECURSE(VisitWithExpectation(bin->left(), cache_.kInt32,
 611                                  "array index expected to be integer"));
 612     Literal* right = bin->right()->AsLiteral();
 613     if (right == NULL || right->raw_value()->ContainsDot()) {
 614       FAIL(right, "heap access shift must be integer");
 615     }
 616     RECURSE(VisitWithExpectation(bin->right(), cache_.kInt32,
 617                                  "array shift expected to be integer"));
 618     int n = static_cast<int>(right->raw_value()->AsNumber());
 619     int expected_shift = ElementShiftSize(type);
 620     if (expected_shift < 0 || n != expected_shift) {
 621       FAIL(right, "heap access shift must match element size");
 622     }
 623     bin->set_bounds(Bounds(cache_.kInt32));
 624   }
 625   IntersectResult(expr, type);
 626 }
 627
 628
 629 void AsmTyper::VisitProperty(Property* expr) {
 630   // stdlib.Math.x
 631   Property* inner_prop = expr->obj()->AsProperty();
 632   if (inner_prop != NULL) {
 633     // Get property name.
 634     Literal* key = expr->key()->AsLiteral();
 635     if (key == NULL || !key->IsPropertyName())
 636       FAIL(expr, "invalid type annotation on property 2");
 637     Handle<String> name = key->AsPropertyName();
 638
 639     // Check that inner property name is "Math".
 640     Literal* math_key = inner_prop->key()->AsLiteral();
 641     if (math_key == NULL || !math_key->IsPropertyName() ||
 642         !math_key->AsPropertyName()->IsUtf8EqualTo(CStrVector("Math")))
 643       FAIL(expr, "invalid type annotation on stdlib (a1)");
 644
 645     // Check that object is stdlib.
 646     VariableProxy* proxy = inner_prop->obj()->AsVariableProxy();
 647     if (proxy == NULL) FAIL(expr, "invalid type annotation on stdlib (a2)");
 648     Variable* var = proxy->var();
 649     if (var->location() != VariableLocation::PARAMETER || var->index() != 0)
 650       FAIL(expr, "invalid type annotation on stdlib (a3)");
 651
 652     // Look up library type.
 653     Type* type = LibType(stdlib_math_types_, name);
 654     if (type == NULL) FAIL(expr, "unknown standard function 3 ");
 655     SetResult(expr, type);
 656     return;
 657   }
 658
 659   // Only recurse at this point so that we avoid needing
 660   // stdlib.Math to have a real type.
 661   RECURSE(VisitWithExpectation(expr->obj(), Type::Any(),
 662                                "property holder expected to be object"));
 663
 664   // For heap view or function table access.
 665   if (computed_type_->IsArray()) {
 666     VisitHeapAccess(expr);
 667     return;
 668   }
 669
 670   // Get property name.
 671   Literal* key = expr->key()->AsLiteral();
 672   if (key == NULL || !key->IsPropertyName())
 673     FAIL(expr, "invalid type annotation on property 3");
 674   Handle<String> name = key->AsPropertyName();
 675
 676   // stdlib.x or foreign.x
 677   VariableProxy* proxy = expr->obj()->AsVariableProxy();
 678   if (proxy != NULL) {
 679     Variable* var = proxy->var();
 680     if (var->location() != VariableLocation::PARAMETER) {
 681       FAIL(expr, "invalid type annotation on variable");
 682     }
 683     switch (var->index()) {
 684       case 0: {
 685         // Object is stdlib, look up library type.
 686         Type* type = LibType(stdlib_types_, name);
 687         if (type == NULL) {
 688           FAIL(expr, "unknown standard function 4");
 689         }
 690         SetResult(expr, type);
 691         return;
 692       }
 693       case 1:
 694         // Object is foreign lib.
 695         SetResult(expr, expected_type_);
 696         return;
 697       default:
 698         FAIL(expr, "invalid type annotation on parameter");
 699     }
 700   }
 701
 702   FAIL(expr, "invalid property access");
 703 }
 704
 705
 706 void AsmTyper::VisitCall(Call* expr) {
 707   RECURSE(VisitWithExpectation(expr->expression(), Type::Any(),
 708                                "callee expected to be any"));
 709   if (computed_type_->IsFunction()) {
 710     Type::FunctionType* fun_type = computed_type_->AsFunction();
 711     ZoneList<Expression*>* args = expr->arguments();
 712     if (fun_type->Arity() != args->length()) {
 713       FAIL(expr, "call with wrong arity");
 714     }
 715     for (int i = 0; i < args->length(); ++i) {
 716       Expression* arg = args->at(i);
 717       RECURSE(VisitWithExpectation(
 718           arg, fun_type->Parameter(i),
 719           "call argument expected to match callee parameter"));
 720     }
 721     IntersectResult(expr, fun_type->Result());
 722   } else if (computed_type_->Is(Type::Any())) {
 723     // For foreign calls.
 724     ZoneList<Expression*>* args = expr->arguments();
 725     for (int i = 0; i < args->length(); ++i) {
 726       Expression* arg = args->at(i);
 727       RECURSE(VisitWithExpectation(arg, Type::Any(),
 728                                    "foreign call argument expected to be any"));
 729     }
 730     IntersectResult(expr, Type::Number());
 731   } else {
 732     FAIL(expr, "invalid callee");
 733   }
 734 }
 735
 736
 737 void AsmTyper::VisitCallNew(CallNew* expr) {
 738   if (in_function_) {
 739     FAIL(expr, "new not allowed in module function");
 740   }
 741   RECURSE(VisitWithExpectation(expr->expression(), Type::Any(),
 742                                "expected stdlib function"));
 743   if (computed_type_->IsFunction()) {
 744     Type::FunctionType* fun_type = computed_type_->AsFunction();
 745     ZoneList<Expression*>* args = expr->arguments();
 746     if (fun_type->Arity() != args->length())
 747       FAIL(expr, "call with wrong arity");
 748     for (int i = 0; i < args->length(); ++i) {
 749       Expression* arg = args->at(i);
 750       RECURSE(VisitWithExpectation(
 751           arg, fun_type->Parameter(i),
 752           "constructor argument expected to match callee parameter"));
 753     }
 754     IntersectResult(expr, fun_type->Result());
 755     return;
 756   }
 757
 758   FAIL(expr, "ill-typed new operator");
 759 }
 760
 761
 762 void AsmTyper::VisitCallRuntime(CallRuntime* expr) {
 763   // Allow runtime calls for now.
 764 }
 765
 766
 767 void AsmTyper::VisitUnaryOperation(UnaryOperation* expr) {
 768   switch (expr->op()) {
 769     case Token::NOT:  // Used to encode != and !==
 770       RECURSE(VisitWithExpectation(expr->expression(), cache_.kInt32,
 771                                    "operand expected to be integer"));
 772       IntersectResult(expr, cache_.kInt32);
 773       return;
 774     case Token::DELETE:
 775       FAIL(expr, "delete operator encountered");
 776     case Token::VOID:
 777       FAIL(expr, "void operator encountered");
 778     case Token::TYPEOF:
 779       FAIL(expr, "typeof operator encountered");
 780     default:
 781       UNREACHABLE();
 782   }
 783 }
 784
 785
 786 void AsmTyper::VisitCountOperation(CountOperation* expr) {
 787   FAIL(expr, "increment or decrement operator encountered");
 788 }
 789
 790
 791 void AsmTyper::VisitBinaryOperation(BinaryOperation* expr) {
 792   switch (expr->op()) {
 793     case Token::COMMA: {
 794       RECURSE(VisitWithExpectation(expr->left(), Type::Any(),
 795                                    "left comma operand expected to be any"));
 796       RECURSE(VisitWithExpectation(expr->right(), Type::Any(),
 797                                    "right comma operand expected to be any"));
 798       IntersectResult(expr, computed_type_);
 799       return;
 800     }
 801     case Token::OR:
 802     case Token::AND:
 803       FAIL(expr, "logical operator encountered");
 804     case Token::BIT_OR:
 805     case Token::BIT_AND:
 806     case Token::BIT_XOR:
 807     case Token::SHL:
 808     case Token::SHR:
 809     case Token::SAR: {
 810       // BIT_OR allows Any since it is used as a type coercion.
 811       // BIT_XOR allows Number since it is used as a type coercion (encoding ~).
 812       Type* expectation =
 813           expr->op() == Token::BIT_OR
 814               ? Type::Any()
 815               : expr->op() == Token::BIT_XOR ? Type::Number() : cache_.kInt32;
 816       Type* result =
 817           expr->op() == Token::SHR ? Type::Unsigned32() : cache_.kInt32;
 818       RECURSE(VisitWithExpectation(expr->left(), expectation,
 819                                    "left bit operand expected to be integer"));
 820       int left_intish = intish_;
 821       RECURSE(VisitWithExpectation(expr->right(), expectation,
 822                                    "right bit operand expected to be integer"));
 823       int right_intish = intish_;
 824       if (left_intish > kMaxUncombinedAdditiveSteps) {
 825         FAIL(expr, "too many consecutive additive ops");
 826       }
 827       if (right_intish > kMaxUncombinedAdditiveSteps) {
 828         FAIL(expr, "too many consecutive additive ops");
 829       }
 830       intish_ = 0;
 831       IntersectResult(expr, result);
 832       return;
 833     }
 834     case Token::ADD:
 835     case Token::SUB:
 836     case Token::MUL:
 837     case Token::DIV:
 838     case Token::MOD: {
 839       RECURSE(VisitWithExpectation(
 840           expr->left(), Type::Number(),
 841           "left arithmetic operand expected to be number"));
 842       Type* left_type = computed_type_;
 843       int left_intish = intish_;
 844       RECURSE(VisitWithExpectation(
 845           expr->right(), Type::Number(),
 846           "right arithmetic operand expected to be number"));
 847       Type* right_type = computed_type_;
 848       int right_intish = intish_;
 849       Type* type = Type::Union(left_type, right_type, zone());
 850       if (type->Is(cache_.kInt32)) {
 851         if (expr->op() == Token::MUL) {
 852           if (!expr->left()->IsLiteral() && !expr->right()->IsLiteral()) {
 853             FAIL(expr, "direct integer multiply forbidden");
 854           }
 855           intish_ = 0;
 856           IntersectResult(expr, cache_.kInt32);
 857           return;
 858         } else {
 859           intish_ = left_intish + right_intish + 1;
 860           if (expr->op() == Token::ADD || expr->op() == Token::SUB) {
 861             if (intish_ > kMaxUncombinedAdditiveSteps) {
 862               FAIL(expr, "too many consecutive additive ops");
 863             }
 864           } else {
 865             if (intish_ > kMaxUncombinedMultiplicativeSteps) {
 866               FAIL(expr, "too many consecutive multiplicative ops");
 867             }
 868           }
 869           IntersectResult(expr, cache_.kInt32);
 870           return;
 871         }
 872       } else if (type->Is(Type::Number())) {
 873         IntersectResult(expr, cache_.kFloat64);
 874         return;
 875       } else {
 876         FAIL(expr, "ill-typed arithmetic operation");
 877       }
 878     }
 879     default:
 880       UNREACHABLE();
 881   }
 882 }
 883
 884
 885 void AsmTyper::VisitCompareOperation(CompareOperation* expr) {
 886   RECURSE(
 887       VisitWithExpectation(expr->left(), Type::Number(),
 888                            "left comparison operand expected to be number"));
 889   Type* left_type = computed_type_;
 890   RECURSE(
 891       VisitWithExpectation(expr->right(), Type::Number(),
 892                            "right comparison operand expected to be number"));
 893   Type* right_type = computed_type_;
 894   Type* type = Type::Union(left_type, right_type, zone());
 895   expr->set_combined_type(type);
 896   if (type->Is(Type::Integral32()) || type->Is(Type::UntaggedFloat64())) {
 897     IntersectResult(expr, cache_.kInt32);
 898   } else {
 899     FAIL(expr, "ill-typed comparison operation");
 900   }
 901 }
 902
 903
 904 void AsmTyper::VisitThisFunction(ThisFunction* expr) {
 905   FAIL(expr, "this function not allowed");
 906 }
 907
 908
 909 void AsmTyper::VisitDeclarations(ZoneList<Declaration*>* decls) {
 910   for (int i = 0; i < decls->length(); ++i) {
 911     Declaration* decl = decls->at(i);
 912     RECURSE(Visit(decl));
 913   }
 914 }
 915
 916
 917 void AsmTyper::VisitImportDeclaration(ImportDeclaration* decl) {
 918   FAIL(decl, "import declaration encountered");
 919 }
 920
 921
 922 void AsmTyper::VisitExportDeclaration(ExportDeclaration* decl) {
 923   FAIL(decl, "export declaration encountered");
 924 }
 925
 926
 927 void AsmTyper::VisitClassLiteral(ClassLiteral* expr) {
 928   FAIL(expr, "class literal not allowed");
 929 }
 930
 931
 932 void AsmTyper::VisitSpread(Spread* expr) { FAIL(expr, "spread not allowed"); }
 933
 934
 935 void AsmTyper::VisitSuperPropertyReference(SuperPropertyReference* expr) {
 936   FAIL(expr, "super property reference not allowed");
 937 }
 938
 939
 940 void AsmTyper::VisitSuperCallReference(SuperCallReference* expr) {
 941   FAIL(expr, "call reference not allowed");
 942 }
 943
 944
 945 void AsmTyper::InitializeStdlib() {
 946   Type* number_type = Type::Number(zone());
 947   Type* double_type = cache_.kFloat64;
 948   Type* double_fn1_type = Type::Function(double_type, double_type, zone());
 949   Type* double_fn2_type =
 950       Type::Function(double_type, double_type, double_type, zone());
 951
 952   Type* fround_type = Type::Function(cache_.kFloat32, number_type, zone());
 953   Type* imul_type =
 954       Type::Function(cache_.kInt32, cache_.kInt32, cache_.kInt32, zone());
 955   // TODO(bradnelson): currently only approximating the proper intersection type
 956   // (which we cannot currently represent).
 957   Type* abs_type = Type::Function(number_type, number_type, zone());
 958
 959   struct Assignment {
 960     const char* name;
 961     Type* type;
 962   };
 963
 964   const Assignment math[] = {
 965       {"PI", double_type},       {"E", double_type},
 966       {"LN2", double_type},      {"LN10", double_type},
 967       {"LOG2E", double_type},    {"LOG10E", double_type},
 968       {"SQRT2", double_type},    {"SQRT1_2", double_type},
 969       {"imul", imul_type},       {"abs", abs_type},
 970       {"ceil", double_fn1_type}, {"floor", double_fn1_type},
 971       {"fround", fround_type},   {"pow", double_fn2_type},
 972       {"exp", double_fn1_type},  {"log", double_fn1_type},
 973       {"min", double_fn2_type},  {"max", double_fn2_type},
 974       {"sqrt", double_fn1_type}, {"cos", double_fn1_type},
 975       {"sin", double_fn1_type},  {"tan", double_fn1_type},
 976       {"acos", double_fn1_type}, {"asin", double_fn1_type},
 977       {"atan", double_fn1_type}, {"atan2", double_fn2_type}};
 978   for (unsigned i = 0; i < arraysize(math); ++i) {
 979     stdlib_math_types_[math[i].name] = math[i].type;
 980   }
 981
 982   stdlib_types_["Infinity"] = double_type;
 983   stdlib_types_["NaN"] = double_type;
 984   Type* buffer_type = Type::Any(zone());
 985 #define TYPED_ARRAY(TypeName, type_name, TYPE_NAME, ctype, size) \
 986   stdlib_types_[#TypeName "Array"] =                             \
 987       Type::Function(cache_.k##TypeName##Array, buffer_type, zone());
 988   TYPED_ARRAYS(TYPED_ARRAY)
 989 #undef TYPED_ARRAY
 990
 991 #define TYPED_ARRAY(TypeName, type_name, TYPE_NAME, ctype, size) \
 992   stdlib_heap_types_[#TypeName "Array"] =                        \
 993       Type::Function(cache_.k##TypeName##Array, buffer_type, zone());
 994   TYPED_ARRAYS(TYPED_ARRAY)
 995 #undef TYPED_ARRAY
 996 }
 997
 998
 999 Type* AsmTyper::LibType(ObjectTypeMap map, Handle<String> name) {
1000   base::SmartArrayPointer<char> aname = name->ToCString();
1001   ObjectTypeMap::iterator i = map.find(std::string(aname.get()));
1002   if (i == map.end()) {
1003     return NULL;
1004   }
1005   return i->second;
1006 }
1007
1008
1009 void AsmTyper::SetType(Variable* variable, Type* type) {
1010   ZoneHashMap::Entry* entry;
1011   if (in_function_) {
1012     entry = local_variable_type_.LookupOrInsert(
1013         variable, ComputePointerHash(variable), ZoneAllocationPolicy(zone()));
1014   } else {
1015     entry = global_variable_type_.LookupOrInsert(
1016         variable, ComputePointerHash(variable), ZoneAllocationPolicy(zone()));
1017   }
1018   entry->value = reinterpret_cast<void*>(type);
1019 }
1020
1021
1022 Type* AsmTyper::GetType(Variable* variable) {
1023   i::ZoneHashMap::Entry* entry = NULL;
1024   if (in_function_) {
1025     entry = local_variable_type_.Lookup(variable, ComputePointerHash(variable));
1026   }
1027   if (entry == NULL) {
1028     entry =
1029         global_variable_type_.Lookup(variable, ComputePointerHash(variable));
1030   }
1031   if (entry == NULL) {
1032     return NULL;
1033   } else {
1034     return reinterpret_cast<Type*>(entry->value);
1035   }
1036 }
1037
1038
1039 void AsmTyper::SetResult(Expression* expr, Type* type) {
1040   computed_type_ = type;
1041   expr->set_bounds(Bounds(computed_type_));
1042 }
1043
1044
1045 void AsmTyper::IntersectResult(Expression* expr, Type* type) {
1046   computed_type_ = type;
1047   Type* bounded_type = Type::Intersect(computed_type_, expected_type_, zone());
1048   expr->set_bounds(Bounds(bounded_type));
1049 }
1050
1051
1052 void AsmTyper::VisitWithExpectation(Expression* expr, Type* expected_type,
1053                                     const char* msg) {
1054   Type* save = expected_type_;
1055   expected_type_ = expected_type;
1056   RECURSE(Visit(expr));
1057   Type* bounded_type = Type::Intersect(computed_type_, expected_type_, zone());
1058   if (bounded_type->Is(Type::None(zone()))) {
1059 #ifdef DEBUG
1060     PrintF("Computed type: ");
1061     computed_type_->Print();
1062     PrintF("Expected type: ");
1063     expected_type_->Print();
1064 #endif
1065     FAIL(expr, msg);
1066   }
1067   expected_type_ = save;
1068 }
1069 }
1070 }  // namespace v8::internal