[wasm] asm.js - Parse and convert asm.js to wasm a function at a time.

src/asmjs/asm-typer.cc

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/asmjs/asm-typer.h"
 
 #include <algorithm>
 #include <limits>
 #include <memory>
 #include <string>
 
 #include "src/v8.h"
 
 #include "src/asmjs/asm-types.h"
 #include "src/ast/ast.h"
 #include "src/ast/scopes.h"
 #include "src/base/bits.h"
 #include "src/codegen.h"
 #include "src/globals.h"
 #include "src/utils.h"
 
+#define FAIL_LINE(line, msg)                                   \
+  do {                                                         \
+    base::OS::SNPrintF(error_message_, sizeof(error_message_), \
+                       "asm: line %d: %s", (line) + 1, msg);   \
+    return AsmType::None();                                    \
+  } while (false)
+
 #define FAIL(node, msg)                                        \
   do {                                                         \
     int line = node->position() == kNoSourcePosition           \
                    ? -1                                        \
                    : script_->GetLineNumber(node->position()); \
-    base::OS::SNPrintF(error_message_, sizeof(error_message_), \
-                       "asm: line %d: %s", line + 1, msg);     \
-    return AsmType::None();                                    \
+    FAIL_LINE(line, msg);                                      \
   } while (false)
 
 #define RECURSE(call)                                             \
   do {                                                            \
     if (GetCurrentStackPosition() < stack_limit_) {               \
       stack_overflow_ = true;                                     \
       FAIL(root_, "Stack overflow while parsing asm.js module."); \
     }                                                             \
                                                                   \
     AsmType* result = (call);                                     \
@@ skipping 44 matching lines @@
       context_stack_.emplace_back(
           Context(current_statement->AsBlock()->statements()));
       continue;
     }
 
     return current_statement;
   }
 }
 
 // ----------------------------------------------------------------------------
+// Implementation of AsmTyper::SourceLayoutTracker
+
+bool AsmTyper::SourceLayoutTracker::IsValid() const {
+  const Section* kAllSections[] = {&use_asm_, &globals_, &functions_, &tables_,
+                                   &exports_};
+  for (size_t ii = 0; ii < arraysize(kAllSections); ++ii) {
+    const auto& curr_section = *kAllSections[ii];
+    for (size_t jj = ii + 1; jj < arraysize(kAllSections); ++jj) {
+      if (curr_section.OverlapsWith(*kAllSections[jj])) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+void AsmTyper::SourceLayoutTracker::Section::AddNewElement(
+    const AstNode& node) {
+  const int node_pos = node.position();
+  if (start_ == kNoSourcePosition) {
+    start_ = node_pos;
+  } else {
+    start_ = std::max(start_, node_pos);
+  }
+  if (end_ == kNoSourcePosition) {
+    end_ = node_pos;
+  } else {
+    end_ = std::max(end_, node_pos);
+  }
+}
+
+bool AsmTyper::SourceLayoutTracker::Section::OverlapsWith(

[titzer, 2016/11/29 14:57:37]

This check is actually stricter than OverlapsWith; it is that this section is
actually starts and ends before {other}.

Different name?

[bradn, 2016/11/29 22:09:06]

Actually this is too strict.
It happens to work because other parts of validation prescribe the ordering, but
it's clear to just have this check for overlap.
Changed the comparison instead.

[bradn, 2016/11/29 23:30:02]

Actually this is not overlap, renaming.

+    const Section& other) const {
+  if (start_ == kNoSourcePosition) {
+    DCHECK_EQ(end_, kNoSourcePosition);
+    return false;
+  }
+  if (other.start_ == kNoSourcePosition) {
+    DCHECK_EQ(other.end_, kNoSourcePosition);
+    return false;
+  }
+  return other.start_ < end_ || other.end_ < start_;
+}
+
+// ----------------------------------------------------------------------------
 // Implementation of AsmTyper::VariableInfo
 
 AsmTyper::VariableInfo* AsmTyper::VariableInfo::ForSpecialSymbol(
     Zone* zone, StandardMember standard_member) {
   DCHECK(standard_member == kStdlib || standard_member == kFFI ||
          standard_member == kHeap || standard_member == kModule);
   auto* new_var_info = new (zone) VariableInfo(AsmType::None());
   new_var_info->standard_member_ = standard_member;
   new_var_info->mutability_ = kImmutableGlobal;
   return new_var_info;
 }
 
 AsmTyper::VariableInfo* AsmTyper::VariableInfo::Clone(Zone* zone) const {
   CHECK(standard_member_ != kNone);
   CHECK(!type_->IsA(AsmType::None()));
   auto* new_var_info = new (zone) VariableInfo(type_);
   new_var_info->standard_member_ = standard_member_;
   new_var_info->mutability_ = mutability_;
   return new_var_info;
 }
 
-void AsmTyper::VariableInfo::FirstForwardUseIs(VariableProxy* var) {
-  DCHECK(first_forward_use_ == nullptr);
+void AsmTyper::VariableInfo::FirstForwardUseIs(int source_location) {
+  DCHECK(source_location_ == -1);
   missing_definition_ = true;
-  first_forward_use_ = var;
+  source_location_ = source_location;
 }
 
 // ----------------------------------------------------------------------------
 // Implementation of AsmTyper
 
 AsmTyper::AsmTyper(Isolate* isolate, Zone* zone, Script* script,
                    FunctionLiteral* root)
     : isolate_(isolate),
       zone_(zone),
       script_(script),
       root_(root),
       forward_definitions_(zone),
       ffi_use_signatures_(zone),
       stdlib_types_(zone),
       stdlib_math_types_(zone),
       module_info_(VariableInfo::ForSpecialSymbol(zone_, kModule)),
       global_scope_(ZoneHashMap::kDefaultHashMapCapacity,
                     ZoneAllocationPolicy(zone)),
       local_scope_(ZoneHashMap::kDefaultHashMapCapacity,
                    ZoneAllocationPolicy(zone)),
       stack_limit_(isolate->stack_guard()->real_climit()),
-      node_types_(zone_),
+      module_node_types_(zone_),
+      function_node_types_(zone_),
       fround_type_(AsmType::FroundType(zone_)),
-      ffi_type_(AsmType::FFIType(zone_)) {
+      ffi_type_(AsmType::FFIType(zone_)),
+      function_pointer_tables_(zone_) {
   InitializeStdlib();
 }
 
 namespace {
 bool ValidAsmIdentifier(Handle<String> name) {
   static const char* kInvalidAsmNames[] = {"eval", "arguments"};
 
   for (size_t ii = 0; ii < arraysize(kInvalidAsmNames); ++ii) {
     if (strcmp(name->ToCString().get(), kInvalidAsmNames[ii]) == 0) {
       return false;
@@ skipping 185 matching lines @@
 
   if (entry == nullptr && !module_name_.is_null() &&
       module_name_->Equals(*variable->name())) {
     return module_info_;
   }
 
   return entry ? reinterpret_cast<VariableInfo*>(entry->value) : nullptr;
 }
 
 void AsmTyper::AddForwardReference(VariableProxy* proxy, VariableInfo* info) {
-  info->FirstForwardUseIs(proxy);
+  info->FirstForwardUseIs(proxy->position() == kNoSourcePosition
+                              ? -1
+                              : script_->GetLineNumber(proxy->position()));
   forward_definitions_.push_back(info);
 }
 
 bool AsmTyper::AddGlobal(Variable* variable, VariableInfo* info) {
   // We can't DCHECK(!in_function_) because function may actually install global
   // names (forward defined functions and function tables.)
   DCHECK(info->mutability() != VariableInfo::kInvalidMutability);
   DCHECK(info->IsGlobal());
   DCHECK(ValidAsmIdentifier(variable->name()));
 
@@ skipping 24 matching lines @@
   if (entry->value != nullptr) {
     return false;
   }
 
   entry->value = info;
   return true;
 }
 
 void AsmTyper::SetTypeOf(AstNode* node, AsmType* type) {
   DCHECK_NE(type, AsmType::None());
-  DCHECK(node_types_.find(node) == node_types_.end());
-  node_types_.insert(std::make_pair(node, type));
+  if (in_function_) {
+    DCHECK(function_node_types_.find(node) == function_node_types_.end());
+    function_node_types_.insert(std::make_pair(node, type));
+  } else {
+    DCHECK(module_node_types_.find(node) == module_node_types_.end());
+    module_node_types_.insert(std::make_pair(node, type));
+  }
 }
 
 AsmType* AsmTyper::TypeOf(AstNode* node) const {
-  auto node_type_iter = node_types_.find(node);
-  if (node_type_iter != node_types_.end()) {
+  auto node_type_iter = function_node_types_.find(node);
+  if (node_type_iter != function_node_types_.end()) {
+    return node_type_iter->second;
+  }
+  node_type_iter = module_node_types_.find(node);
+  if (node_type_iter != module_node_types_.end()) {
     return node_type_iter->second;
   }
 
   // Sometimes literal nodes are not added to the node_type_ map simply because
   // their are not visited with ValidateExpression().
   if (auto* literal = node->AsLiteral()) {
     if (literal->raw_value()->ContainsDot()) {
       return AsmType::Double();
     }
     uint32_t u;
@@ skipping 17 matching lines @@
 AsmTyper::StandardMember AsmTyper::VariableAsStandardMember(Variable* var) {
   auto* var_info = Lookup(var);
   if (var_info == nullptr) {
     return kNone;
   }
   StandardMember member = var_info->standard_member();
   return member;
 }
 
 bool AsmTyper::Validate() {
-  if (!AsmType::None()->IsExactly(ValidateModule(root_))) {
+  return ValidateBeforeFunctionsPhase() &&
+         !AsmType::None()->IsExactly(ValidateModuleFunctions(root_)) &&
+         ValidateAfterFunctionsPhase();
+}
+
+bool AsmTyper::ValidateBeforeFunctionsPhase() {
+  if (!AsmType::None()->IsExactly(ValidateModuleBeforeFunctionsPhase(root_))) {
     return true;
   }
   return false;
 }
 
+bool AsmTyper::ValidateInnerFunction(FunctionDeclaration* fun_decl) {
+  if (!AsmType::None()->IsExactly(ValidateModuleFunction(fun_decl))) {
+    return true;
+  }
+  return false;
+}
+
+bool AsmTyper::ValidateAfterFunctionsPhase() {
+  if (!AsmType::None()->IsExactly(ValidateModuleAfterFunctionsPhase(root_))) {
+    return true;
+  }
+  return false;
+}
+
+void AsmTyper::ClearFunctionNodeTypes() { function_node_types_.clear(); }
+
 namespace {
 bool IsUseAsmDirective(Statement* first_statement) {
   ExpressionStatement* use_asm = first_statement->AsExpressionStatement();
   if (use_asm == nullptr) {
     return false;
   }
 
   Literal* use_asm_literal = use_asm->expression()->AsLiteral();
 
   if (use_asm_literal == nullptr) {
@@ skipping 17 matching lines @@
   if (assign->op() != Token::INIT) {
     // Done with initializers.
     return nullptr;
   }
   return assign;
 }
 
 }  // namespace
 
 // 6.1 ValidateModule
-namespace {
-// SourceLayoutTracker keeps track of the start and end positions of each
-// section in the asm.js source. The sections should not overlap, otherwise the
-// asm.js source is invalid.
-class SourceLayoutTracker {
- public:
-  SourceLayoutTracker() = default;
-
-  bool IsValid() const {
-    const Section* kAllSections[] = {&use_asm_, &globals_, &functions_,
-                                     &tables_, &exports_};
-    for (size_t ii = 0; ii < arraysize(kAllSections); ++ii) {
-      const auto& curr_section = *kAllSections[ii];
-      for (size_t jj = ii + 1; jj < arraysize(kAllSections); ++jj) {
-        if (curr_section.OverlapsWith(*kAllSections[jj])) {
-          return false;
-        }
-      }
-    }
-    return true;
-  }
-
-  void AddUseAsm(const AstNode& node) { use_asm_.AddNewElement(node); }
-
-  void AddGlobal(const AstNode& node) { globals_.AddNewElement(node); }
-
-  void AddFunction(const AstNode& node) { functions_.AddNewElement(node); }
-
-  void AddTable(const AstNode& node) { tables_.AddNewElement(node); }
-
-  void AddExport(const AstNode& node) { exports_.AddNewElement(node); }
-
- private:
-  class Section {
-   public:
-    Section() = default;
-    Section(const Section&) = default;
-    Section& operator=(const Section&) = default;
-
-    void AddNewElement(const AstNode& node) {
-      const int node_pos = node.position();
-      if (start_ == kNoSourcePosition) {
-        start_ = node_pos;
-      } else {
-        start_ = std::max(start_, node_pos);
-      }
-      if (end_ == kNoSourcePosition) {
-        end_ = node_pos;
-      } else {
-        end_ = std::max(end_, node_pos);
-      }
-    }
-
-    bool OverlapsWith(const Section& other) const {
-      if (start_ == kNoSourcePosition) {
-        DCHECK_EQ(end_, kNoSourcePosition);
-        return false;
-      }
-      if (other.start_ == kNoSourcePosition) {
-        DCHECK_EQ(other.end_, kNoSourcePosition);
-        return false;
-      }
-      return other.start_ < end_ || other.end_ < start_;
-    }
-
-   private:
-    int start_ = kNoSourcePosition;
-    int end_ = kNoSourcePosition;
-  };
-
-  Section use_asm_;
-  Section globals_;
-  Section functions_;
-  Section tables_;
-  Section exports_;
-
-  DISALLOW_COPY_AND_ASSIGN(SourceLayoutTracker);
-};
-}  // namespace
-
-AsmType* AsmTyper::ValidateModule(FunctionLiteral* fun) {
-  SourceLayoutTracker source_layout;
-
+AsmType* AsmTyper::ValidateModuleBeforeFunctionsPhase(FunctionLiteral* fun) {
   DeclarationScope* scope = fun->scope();
   if (!scope->is_function_scope()) FAIL(fun, "Not at function scope.");
   if (!ValidAsmIdentifier(fun->name()))
     FAIL(fun, "Invalid asm.js identifier in module name.");
   module_name_ = fun->name();
 
   // Allowed parameters: Stdlib, FFI, Mem
   static const int MaxModuleParameters = 3;
   if (scope->num_parameters() > MaxModuleParameters) {
     FAIL(fun, "asm.js modules may not have more than three parameters.");
@@ skipping 14 matching lines @@
     }
 
     auto* param_info = VariableInfo::ForSpecialSymbol(
         zone_, kModuleParamInfo[ii].standard_member);
 
     if (!AddGlobal(param, param_info)) {
       FAIL(fun, "Redeclared identifier in module parameter.");
     }
   }
 
-  ZoneVector<Assignment*> function_pointer_tables(zone_);
   FlattenedStatements iter(zone_, fun->body());
   auto* use_asm_directive = iter.Next();
   if (use_asm_directive == nullptr) {
     FAIL(fun, "Missing \"use asm\".");
   }
   // Check for extra assignment inserted by the parser when in this form:
   // (function Module(a, b, c) {... })
   ExpressionStatement* estatement = use_asm_directive->AsExpressionStatement();
   if (estatement != nullptr) {
     Assignment* assignment = estatement->expression()->AsAssignment();
     if (assignment != nullptr && assignment->target()->IsVariableProxy() &&
         assignment->target()
             ->AsVariableProxy()
             ->var()
             ->is_sloppy_function_name()) {
       use_asm_directive = iter.Next();
     }
   }
   if (!IsUseAsmDirective(use_asm_directive)) {
     FAIL(fun, "Missing \"use asm\".");
   }
-  source_layout.AddUseAsm(*use_asm_directive);
-  ReturnStatement* module_return = nullptr;
+  source_layout_.AddUseAsm(*use_asm_directive);
+  module_return_ = nullptr;
 
   // *VIOLATION* The spec states that globals should be followed by function
   // declarations, which should be followed by function pointer tables, followed
   // by the module export (return) statement. Our AST might be rearraged by the
   // parser, so we can't rely on it being in source code order.
   while (Statement* current = iter.Next()) {
     if (auto* assign = ExtractInitializerExpression(current)) {
       if (assign->value()->IsArrayLiteral()) {
         // Save function tables for later validation.
-        function_pointer_tables.push_back(assign);
+        function_pointer_tables_.push_back(assign);
       } else {
         RECURSE(ValidateGlobalDeclaration(assign));
-        source_layout.AddGlobal(*assign);
+        source_layout_.AddGlobal(*assign);
       }
       continue;
     }
 
     if (auto* current_as_return = current->AsReturnStatement()) {
-      if (module_return != nullptr) {
+      if (module_return_ != nullptr) {
         FAIL(fun, "Multiple export statements.");
       }
-      module_return = current_as_return;
-      source_layout.AddExport(*module_return);
+      module_return_ = current_as_return;
+      source_layout_.AddExport(*module_return_);
       continue;
     }
 
     FAIL(current, "Invalid top-level statement in asm.js module.");
   }
 
+  return AsmType::Int();  // Any type that is not AsmType::None();
+}
+
+AsmType* AsmTyper::ValidateModuleFunction(FunctionDeclaration* fun_decl) {
+  RECURSE(ValidateFunction(fun_decl));
+  source_layout_.AddFunction(*fun_decl);
+
+  return AsmType::Int();  // Any type that is not AsmType::None();
+}
+
+AsmType* AsmTyper::ValidateModuleFunctions(FunctionLiteral* fun) {
+  DeclarationScope* scope = fun->scope();
   Declaration::List* decls = scope->declarations();
   for (Declaration* decl : *decls) {
     if (FunctionDeclaration* fun_decl = decl->AsFunctionDeclaration()) {
-      RECURSE(ValidateFunction(fun_decl));
-      source_layout.AddFunction(*fun_decl);
+      RECURSE(ValidateModuleFunction(fun_decl));
       continue;
     }
   }
 
-  for (auto* function_table : function_pointer_tables) {
+  return AsmType::Int();  // Any type that is not AsmType::None();
+}
+
+AsmType* AsmTyper::ValidateModuleAfterFunctionsPhase(FunctionLiteral* fun) {
+  for (auto* function_table : function_pointer_tables_) {
     RECURSE(ValidateFunctionTable(function_table));
-    source_layout.AddTable(*function_table);
+    source_layout_.AddTable(*function_table);
   }
 
+  DeclarationScope* scope = fun->scope();
+  Declaration::List* decls = scope->declarations();
   for (Declaration* decl : *decls) {
     if (decl->IsFunctionDeclaration()) {
       continue;
     }
 
     VariableDeclaration* var_decl = decl->AsVariableDeclaration();
     if (var_decl == nullptr) {
       FAIL(decl, "Invalid asm.js declaration.");
     }
 
     auto* var_proxy = var_decl->proxy();
     if (var_proxy == nullptr) {
       FAIL(decl, "Invalid asm.js declaration.");
     }
 
     if (Lookup(var_proxy->var()) == nullptr) {
       FAIL(decl, "Global variable missing initializer in asm.js module.");
     }
   }
 
   // 6.2 ValidateExport
-  if (module_return == nullptr) {
+  if (module_return_ == nullptr) {
     FAIL(fun, "Missing asm.js module export.");
   }
 
   for (auto* forward_def : forward_definitions_) {
     if (forward_def->missing_definition()) {
-      FAIL(forward_def->first_forward_use(),
-           "Missing definition for forward declared identifier.");
+      FAIL_LINE(forward_def->source_location(),
+                "Missing definition for forward declared identifier.");
     }
   }
 
-  RECURSE(ValidateExport(module_return));
+  RECURSE(ValidateExport(module_return_));
 
-  if (!source_layout.IsValid()) {
+  if (!source_layout_.IsValid()) {
     FAIL(fun, "Invalid asm.js source code layout.");
   }
 
   return AsmType::Int();  // Any type that is not AsmType::None();
 }
 
 namespace {
 bool IsDoubleAnnotation(BinaryOperation* binop) {
   // *VIOLATION* The parser replaces uses of +x with x*1.0.
   if (binop->op() != Token::MUL) {
@@ skipping 2148 matching lines @@
     return true;
   }
 
   *error_message = typer.error_message();
   return false;
 }
 
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8