Unify imported and non-imported things (#1678)

Fixes #1649

This moves us to a single object for functions, which can be imported or nor, and likewise for globals (as a result, GetGlobals do not need to check if the global is imported or not, etc.). All imported things now inherit from Importable, which has the module and base of the import, and if they are set then it is an import.

For convenient iteration, there are a few helpers like

ModuleUtils::iterDefinedGlobals(wasm, [&](Global* global) {
  .. use global ..
});

as often iteration only cares about imported or defined (non-imported) things.

11 files changed, 196 insertions, 72 deletions

diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index d91bc370c..44abc2f64 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -170,14 +170,6 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
         }
         break;
       }
-      case Expression::Id::CallImportId: {
-        CHECK(CallImport, target);
-        CHECK(CallImport, operands.size());
-        for (Index i = 0; i < left->cast<CallImport>()->operands.size(); i++) {
-          PUSH(CallImport, operands[i]);
-        }
-        break;
-      }
       case Expression::Id::CallIndirectId: {
         PUSH(CallIndirect, target);
         CHECK(CallIndirect, fullType);
@@ -423,14 +415,6 @@ uint32_t ExpressionAnalyzer::hash(Expression* curr) {
         }
         break;
       }
-      case Expression::Id::CallImportId: {
-        HASH_NAME(CallImport, target);
-        HASH(CallImport, operands.size());
-        for (Index i = 0; i < curr->cast<CallImport>()->operands.size(); i++) {
-          PUSH(CallImport, operands[i]);
-        }
-        break;
-      }
       case Expression::Id::CallIndirectId: {
         PUSH(CallIndirect, target);
         HASH_NAME(CallIndirect, fullType);
diff --git a/src/ir/ExpressionManipulator.cpp b/src/ir/ExpressionManipulator.cpp
index a3bff2d82..d65509c52 100644
--- a/src/ir/ExpressionManipulator.cpp
+++ b/src/ir/ExpressionManipulator.cpp
@@ -63,13 +63,6 @@ Expression* flexibleCopy(Expression* original, Module& wasm, CustomCopier custom
       }
       return ret;
     }
-    Expression* visitCallImport(CallImport *curr) {
-      auto* ret = builder.makeCallImport(curr->target, {}, curr->type);
-      for (Index i = 0; i < curr->operands.size(); i++) {
-        ret->operands.push_back(copy(curr->operands[i]));
-      }
-      return ret;
-    }
     Expression* visitCallIndirect(CallIndirect *curr) {
       auto* ret = builder.makeCallIndirect(curr->fullType, copy(curr->target), {}, curr->type);
       for (Index i = 0; i < curr->operands.size(); i++) {
diff --git a/src/ir/cost.h b/src/ir/cost.h
index 9a97574f4..6d1078094 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -51,15 +51,12 @@ struct CostAnalyzer : public Visitor<CostAnalyzer, Index> {
     return 2 + visit(curr->condition) + maybeVisit(curr->value);
   }
   Index visitCall(Call *curr) {
+    // XXX this does not take into account if the call is to an import, which
+    //     may be costlier in general
     Index ret = 4;
     for (auto* child : curr->operands) ret += visit(child);
     return ret;
   }
-  Index visitCallImport(CallImport *curr) {
-    Index ret = 15;
-    for (auto* child : curr->operands) ret += visit(child);
-    return ret;
-  }
   Index visitCallIndirect(CallIndirect *curr) {
     Index ret = 6 + visit(curr->target);
     for (auto* child : curr->operands) ret += visit(child);
diff --git a/src/ir/effects.h b/src/ir/effects.h
index 98687c0dc..8919c6da4 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -176,13 +176,13 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer> {
     }
   }
 
-  void visitCall(Call *curr) { calls = true; }
-  void visitCallImport(CallImport *curr) {
+  void visitCall(Call *curr) {
     calls = true;
     if (debugInfo) {
       // debugInfo call imports must be preserved very strongly, do not
       // move code around them
-      branches = true; // !
+      // FIXME: we could check if the call is to an import
+      branches = true;
     }
   }
   void visitCallIndirect(CallIndirect *curr) { calls = true; }
diff --git a/src/ir/function-type-utils.h b/src/ir/function-type-utils.h
new file mode 100644
index 000000000..3c98cb16b
--- /dev/null
+++ b/src/ir/function-type-utils.h
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2018 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_ir_function_type_utils_h
+#define wasm_ir_function_type_utils_h
+
+
+namespace wasm {
+
+namespace FunctionTypeUtils {
+
+// Fills in function info from a function type
+inline void fillFunction(Function* func, FunctionType* type) {
+  func->params = type->params;
+  func->result = type->result;
+}
+
+} // namespace FunctionTypeUtils
+
+} // namespace wasm
+
+#endif // wasm_ir_function_type_utils_h
diff --git a/src/ir/function-utils.h b/src/ir/function-utils.h
index 317b2f1b1..3895b33bf 100644
--- a/src/ir/function-utils.h
+++ b/src/ir/function-utils.h
@@ -35,7 +35,10 @@ inline bool equal(Function* left, Function* right) {
   }
   if (left->result != right->result) return false;
   if (left->type != right->type) return false;
-  return ExpressionAnalyzer::equal(left->body, right->body);
+  if (!left->imported() && !right->imported()) {
+    return ExpressionAnalyzer::equal(left->body, right->body);
+  }
+  return left->imported() && right->imported();
 }
 
 } // namespace FunctionUtils
diff --git a/src/ir/global-utils.h b/src/ir/global-utils.h
index bcf0dae72..02bbbf2d2 100644
--- a/src/ir/global-utils.h
+++ b/src/ir/global-utils.h
@@ -22,6 +22,7 @@
 
 #include "literal.h"
 #include "wasm.h"
+#include "ir/module-utils.h"
 
 namespace wasm {
 
@@ -30,22 +31,22 @@ namespace GlobalUtils {
   inline Global* getGlobalInitializedToImport(Module& wasm, Name module, Name base) {
     // find the import
     Name imported;
-    for (auto& import : wasm.imports) {
+    ModuleUtils::iterImportedGlobals(wasm, [&](Global* import) {
       if (import->module == module && import->base == base) {
         imported = import->name;
-        break;
       }
-    }
+    });
     if (imported.isNull()) return nullptr;
     // find a global inited to it
-    for (auto& global : wasm.globals) {
-      if (auto* init = global->init->dynCast<GetGlobal>()) {
+    Global* ret = nullptr;
+    ModuleUtils::iterDefinedGlobals(wasm, [&](Global* defined) {
+      if (auto* init = defined->init->dynCast<GetGlobal>()) {
         if (init->name == imported) {
-          return global.get();
+          ret = defined;
         }
       }
-    }
-    return nullptr;
+    });
+    return ret;
   }
 };
 
diff --git a/src/ir/import-utils.h b/src/ir/import-utils.h
index f3f01c266..5f7bbc9ed 100644
--- a/src/ir/import-utils.h
+++ b/src/ir/import-utils.h
@@ -22,17 +22,66 @@
 
 namespace wasm {
 
-namespace ImportUtils {
-  // find an import by the module.base that is being imported.
-  // return the internal name
-  inline Import* getImport(Module& wasm, Name module, Name base) {
-    for (auto& import : wasm.imports) {
+// Collects info on imports, into a form convenient for summarizing
+// and searching.
+struct ImportInfo {
+  Module& wasm;
+
+  std::vector<Global*> importedGlobals;
+  std::vector<Function*> importedFunctions;
+
+  ImportInfo(Module& wasm) : wasm(wasm) {
+    for (auto& import : wasm.globals) {
+      if (import->imported()) {
+        importedGlobals.push_back(import.get());
+      }
+    }
+    for (auto& import : wasm.functions) {
+      if (import->imported()) {
+        importedFunctions.push_back(import.get());
+      }
+    }
+  }
+
+  Global* getImportedGlobal(Name module, Name base) {
+    for (auto* import : importedGlobals) {
+      if (import->module == module && import->base == base) {
+        return import;
+      }
+    }
+    return nullptr;
+  }
+
+  Function* getImportedFunction(Name module, Name base) {
+    for (auto* import : importedFunctions) {
       if (import->module == module && import->base == base) {
-        return import.get();
+        return import;
       }
     }
     return nullptr;
   }
+
+  Index getNumImportedGlobals() {
+    return importedGlobals.size();
+  }
+
+  Index getNumImportedFunctions() {
+    return importedFunctions.size();
+  }
+
+  Index getNumImports() {
+    return getNumImportedGlobals() + getNumImportedFunctions() +
+           (wasm.memory.imported() ? 1 : 0) +
+           (wasm.table.imported() ? 1 : 0);
+  }
+
+  Index getNumDefinedGlobals() {
+    return wasm.globals.size() - getNumImportedGlobals();
+  }
+
+  Index getNumDefinedFunctions() {
+    return wasm.functions.size() - getNumImportedFunctions();
+  }
 };
 
 } // namespace wasm
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 4205514e5..1d0512401 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -25,30 +25,45 @@ namespace wasm {
 namespace ModuleUtils {
 
 // Computes the indexes in a wasm binary, i.e., with function imports
-// and function implementations sharing a single index space, etc.
+// and function implementations sharing a single index space, etc.,
+// and with the imports first (the Module's functions and globals
+// arrays are not assumed to be in a particular order, so we can't
+// just use them directly).
 struct BinaryIndexes {
   std::unordered_map<Name, Index> functionIndexes;
   std::unordered_map<Name, Index> globalIndexes;
 
   BinaryIndexes(Module& wasm) {
-    for (Index i = 0; i < wasm.imports.size(); i++) {
-      auto& import = wasm.imports[i];
-      if (import->kind == ExternalKind::Function) {
-        auto index = functionIndexes.size();
-        functionIndexes[import->name] = index;
-      } else if (import->kind == ExternalKind::Global) {
-        auto index = globalIndexes.size();
-        globalIndexes[import->name] = index;
+    auto addGlobal = [&](Global* curr) {
+      auto index = globalIndexes.size();
+      globalIndexes[curr->name] = index;
+    };
+    for (auto& curr : wasm.globals) {
+      if (curr->imported()) {
+        addGlobal(curr.get());
+      }
+    }
+    for (auto& curr : wasm.globals) {
+      if (!curr->imported()) {
+        addGlobal(curr.get());
       }
     }
-    for (Index i = 0; i < wasm.functions.size(); i++) {
+    assert(globalIndexes.size() == wasm.globals.size());
+    auto addFunction = [&](Function* curr) {
       auto index = functionIndexes.size();
-      functionIndexes[wasm.functions[i]->name] = index;
+      functionIndexes[curr->name] = index;
+    };
+    for (auto& curr : wasm.functions) {
+      if (curr->imported()) {
+        addFunction(curr.get());
+      }
     }
-    for (Index i = 0; i < wasm.globals.size(); i++) {
-      auto index = globalIndexes.size();
-      globalIndexes[wasm.globals[i]->name] = index;
+    for (auto& curr : wasm.functions) {
+      if (!curr->imported()) {
+        addFunction(curr.get());
+      }
     }
+    assert(functionIndexes.size() == wasm.functions.size());
   }
 };
 
@@ -63,21 +78,34 @@ inline Function* copyFunction(Function* func, Module& out) {
   ret->localIndices = func->localIndices;
   ret->debugLocations = func->debugLocations;
   ret->body = ExpressionManipulator::copy(func->body, out);
+  ret->module = func->module;
+  ret->base = func->base;
   // TODO: copy Stack IR
   assert(!func->stackIR);
   out.addFunction(ret);
   return ret;
 }
 
+inline Global* copyGlobal(Global* global, Module& out) {
+  auto* ret = new Global();
+  ret->name = global->name;
+  ret->type = global->type;
+  ret->mutable_ = global->mutable_;
+  if (global->imported()) {
+    ret->init = nullptr;
+  } else {
+    ret->init = ExpressionManipulator::copy(global->init, out);
+  }
+  out.addGlobal(ret);
+  return ret;
+}
+
 inline void copyModule(Module& in, Module& out) {
   // we use names throughout, not raw points, so simple copying is fine
   // for everything *but* expressions
   for (auto& curr : in.functionTypes) {
     out.addFunctionType(new FunctionType(*curr));
   }
-  for (auto& curr : in.imports) {
-    out.addImport(new Import(*curr));
-  }
   for (auto& curr : in.exports) {
     out.addExport(new Export(*curr));
   }
@@ -85,7 +113,7 @@ inline void copyModule(Module& in, Module& out) {
     copyFunction(curr.get(), out);
   }
   for (auto& curr : in.globals) {
-    out.addGlobal(new Global(*curr));
+    copyGlobal(curr.get(), out);
   }
   out.table = in.table;
   for (auto& segment : out.table.segments) {
@@ -100,6 +128,44 @@ inline void copyModule(Module& in, Module& out) {
   out.debugInfoFileNames = in.debugInfoFileNames;
 }
 
+// Convenient iteration over imported/non-imported functions/globals
+
+template<typename T>
+inline void iterImportedGlobals(Module& wasm, T visitor) {
+  for (auto& import : wasm.globals) {
+    if (import->imported()) {
+      visitor(import.get());
+    }
+  }
+}
+
+template<typename T>
+inline void iterDefinedGlobals(Module& wasm, T visitor) {
+  for (auto& import : wasm.globals) {
+    if (!import->imported()) {
+      visitor(import.get());
+    }
+  }
+}
+
+template<typename T>
+inline void iterImportedFunctions(Module& wasm, T visitor) {
+  for (auto& import : wasm.functions) {
+    if (import->imported()) {
+      visitor(import.get());
+    }
+  }
+}
+
+template<typename T>
+inline void iterDefinedFunctions(Module& wasm, T visitor) {
+  for (auto& import : wasm.functions) {
+    if (!import->imported()) {
+      visitor(import.get());
+    }
+  }
+}
+
 } // namespace ModuleUtils
 
 } // namespace wasm
diff --git a/src/ir/trapping.h b/src/ir/trapping.h
index a3a87f8ef..48f485faa 100644
--- a/src/ir/trapping.h
+++ b/src/ir/trapping.h
@@ -57,10 +57,10 @@ public:
       wasm.addFunction(function);
     }
   }
-  void addImport(Import* import) {
+  void addImport(Function* import) {
     imports[import->name] = import;
     if (immediate) {
-      wasm.addImport(import);
+      wasm.addFunction(import);
     }
   }
 
@@ -70,7 +70,7 @@ public:
         wasm.addFunction(pair.second);
       }
       for (auto &pair : imports) {
-        wasm.addImport(pair.second);
+        wasm.addFunction(pair.second);
       }
     }
     functions.clear();
@@ -91,7 +91,7 @@ public:
 
 private:
   std::map<Name, Function*> functions;
-  std::map<Name, Import*> imports;
+  std::map<Name, Function*> imports;
 
   TrapMode mode;
   Module& wasm;
diff --git a/src/ir/utils.h b/src/ir/utils.h
index 61d8917be..5eff0a52d 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -158,7 +158,6 @@ struct ReFinalize : public WalkerPass<PostWalker<ReFinalize, OverriddenVisitor<R
     updateBreakValueType(curr->default_, valueType);
   }
   void visitCall(Call* curr) { curr->finalize(); }
-  void visitCallImport(CallImport* curr) { curr->finalize(); }
   void visitCallIndirect(CallIndirect* curr) { curr->finalize(); }
   void visitGetLocal(GetLocal* curr) { curr->finalize(); }
   void visitSetLocal(SetLocal* curr) { curr->finalize(); }
@@ -190,7 +189,6 @@ struct ReFinalize : public WalkerPass<PostWalker<ReFinalize, OverriddenVisitor<R
   }
 
   void visitFunctionType(FunctionType* curr) { WASM_UNREACHABLE(); }
-  void visitImport(Import* curr) { WASM_UNREACHABLE(); }
   void visitExport(Export* curr) { WASM_UNREACHABLE(); }
   void visitGlobal(Global* curr) { WASM_UNREACHABLE(); }
   void visitTable(Table* curr) { WASM_UNREACHABLE(); }
@@ -217,7 +215,6 @@ struct ReFinalizeNode : public OverriddenVisitor<ReFinalizeNode> {
   void visitBreak(Break* curr) { curr->finalize(); }
   void visitSwitch(Switch* curr) { curr->finalize(); }
   void visitCall(Call* curr) { curr->finalize(); }
-  void visitCallImport(CallImport* curr) { curr->finalize(); }
   void visitCallIndirect(CallIndirect* curr) { curr->finalize(); }
   void visitGetLocal(GetLocal* curr) { curr->finalize(); }
   void visitSetLocal(SetLocal* curr) { curr->finalize(); }
@@ -240,7 +237,6 @@ struct ReFinalizeNode : public OverriddenVisitor<ReFinalizeNode> {
   void visitUnreachable(Unreachable* curr) { curr->finalize(); }
 
   void visitFunctionType(FunctionType* curr) { WASM_UNREACHABLE(); }
-  void visitImport(Import* curr) { WASM_UNREACHABLE(); }
   void visitExport(Export* curr) { WASM_UNREACHABLE(); }
   void visitGlobal(Global* curr) { WASM_UNREACHABLE(); }
   void visitTable(Table* curr) { WASM_UNREACHABLE(); }