Very simple module linking in wasm-shell (#3792)

This is a rewrite of the wasm-shell tool, with the goal of improved
compatibility with the reference interpreter and the spec test suite.
To facilitate that, module instances are provided with a list of linked
instances, and imported objects are looked up in the correct instance.

The new shell can:

- register and link modules using the (register ...) command.
- parse binary modules with the syntax (module binary ...).
- provide the "spectest" module defined in the reference interpreter
- assert instantiation traps with assert_trap
- better check linkability by looking up the linked instances in
- assert_unlinkable

It cannot call external function references that are not direct imports.
That would require bigger changes.

6 files changed, 624 insertions, 415 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 161dcf9e3..c91c15422 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -3907,7 +3907,7 @@ BinaryenModuleRef BinaryenModuleRead(char* input, size_t inputSize) {
 
 void BinaryenModuleInterpret(BinaryenModuleRef module) {
   ShellExternalInterface interface;
-  ModuleInstance instance(*(Module*)module, &interface);
+  ModuleInstance instance(*(Module*)module, &interface, {});
 }
 
 BinaryenIndex BinaryenModuleAddDebugInfoFileName(BinaryenModuleRef module,
diff --git a/src/shell-interface.h b/src/shell-interface.h
index 15f600592..494722ab1 100644
--- a/src/shell-interface.h
+++ b/src/shell-interface.h
@@ -95,68 +95,41 @@ struct ShellExternalInterface : ModuleInstance::ExternalInterface {
   } memory;
 
   std::unordered_map<Name, std::vector<Literal>> tables;
+  std::map<Name, std::shared_ptr<ModuleInstance>> linkedInstances;
 
-  ShellExternalInterface() : memory() {}
+  ShellExternalInterface(
+    std::map<Name, std::shared_ptr<ModuleInstance>> linkedInstances_ = {})
+    : memory() {
+    linkedInstances.swap(linkedInstances_);
+  }
   virtual ~ShellExternalInterface() = default;
 
-  void init(Module& wasm, ModuleInstance& instance) override {
-    memory.resize(wasm.memory.initial * wasm::Memory::kPageSize);
+  ModuleInstance* getImportInstance(Importable* import) {
+    auto it = linkedInstances.find(import->module);
+    if (it == linkedInstances.end()) {
+      Fatal() << "importGlobals: unknown import: " << import->module.str << "."
+              << import->base.str;
+    }
+    return it->second.get();
+  }
 
-    if (wasm.tables.size() > 0) {
-      for (auto& table : wasm.tables) {
-        tables[table->name].resize(table->initial);
-      }
+  void init(Module& wasm, ModuleInstance& instance) override {
+    if (wasm.memory.exists && !wasm.memory.imported()) {
+      memory.resize(wasm.memory.initial * wasm::Memory::kPageSize);
     }
+    ModuleUtils::iterDefinedTables(
+      wasm, [&](Table* table) { tables[table->name].resize(table->initial); });
   }
 
   void importGlobals(std::map<Name, Literals>& globals, Module& wasm) override {
-    // add spectest globals
     ModuleUtils::iterImportedGlobals(wasm, [&](Global* import) {
-      if (import->module == SPECTEST && import->base.startsWith("global_")) {
-        TODO_SINGLE_COMPOUND(import->type);
-        switch (import->type.getBasic()) {
-          case Type::i32:
-            globals[import->name] = {Literal(int32_t(666))};
-            break;
-          case Type::i64:
-            globals[import->name] = {Literal(int64_t(666))};
-            break;
-          case Type::f32:
-            globals[import->name] = {Literal(float(666.6))};
-            break;
-          case Type::f64:
-            globals[import->name] = {Literal(double(666.6))};
-            break;
-          case Type::v128:
-            WASM_UNREACHABLE("v128 not implemented yet");
-          case Type::funcref:
-          case Type::externref:
-          case Type::anyref:
-          case Type::eqref:
-            globals[import->name] = {Literal::makeNull(import->type)};
-            break;
-          case Type::i31ref:
-            WASM_UNREACHABLE("TODO: i31ref");
-          case Type::dataref:
-            WASM_UNREACHABLE("TODO: dataref");
-          case Type::none:
-          case Type::unreachable:
-            WASM_UNREACHABLE("unexpected type");
-        }
-      }
-    });
-    if (wasm.memory.imported() && wasm.memory.module == SPECTEST &&
-        wasm.memory.base == MEMORY) {
-      // imported memory has initial 1 and max 2
-      wasm.memory.initial = 1;
-      wasm.memory.max = 2;
-    }
-
-    ModuleUtils::iterImportedTables(wasm, [&](Table* table) {
-      if (table->module == SPECTEST && table->base == TABLE) {
-        table->initial = 10;
-        table->max = 20;
+      auto inst = getImportInstance(import);
+      auto* exportedGlobal = inst->wasm.getExportOrNull(import->base);
+      if (!exportedGlobal) {
+        Fatal() << "importGlobals: unknown import: " << import->module.str
+                << "." << import->name.str;
       }
+      globals[import->name] = inst->globals[exportedGlobal->value];
     });
   }
 
@@ -170,6 +143,8 @@ struct ShellExternalInterface : ModuleInstance::ExternalInterface {
       // XXX hack for torture tests
       std::cout << "exit()\n";
       throw ExitException();
+    } else if (auto* inst = getImportInstance(import)) {
+      return inst->callExport(import->base, arguments);
     }
     Fatal() << "callImport: unknown import: " << import->module.str << "."
             << import->name.str;
@@ -254,7 +229,7 @@ struct ShellExternalInterface : ModuleInstance::ExternalInterface {
     if (addr >= table.size()) {
       trap("out of bounds table access");
     } else {
-      table.emplace(table.begin() + addr, entry);
+      table[addr] = entry;
     }
   }
 
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index 2f7707853..5bede4444 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -127,8 +127,11 @@ static Index STACK_UPPER_LIMIT = STACK_START + STACK_SIZE;
 class EvallingModuleInstance
   : public ModuleInstanceBase<EvallingGlobalManager, EvallingModuleInstance> {
 public:
-  EvallingModuleInstance(Module& wasm, ExternalInterface* externalInterface)
-    : ModuleInstanceBase(wasm, externalInterface) {
+  EvallingModuleInstance(Module& wasm,
+                         ExternalInterface* externalInterface,
+                         std::map<Name, std::shared_ptr<EvallingModuleInstance>>
+                           linkedInstances_ = {})
+    : ModuleInstanceBase(wasm, externalInterface, linkedInstances_) {
     // if any global in the module has a non-const constructor, it is using a
     // global import, which we don't have, and is illegal to use
     ModuleUtils::iterDefinedGlobals(wasm, [&](Global* global) {
@@ -165,9 +168,82 @@ public:
   }
 };
 
+// Build an artificial `env` module based on a module's imports, so that the
+// interpreter can use correct object instances. It initializes usable global
+// imports, and fills the rest with fake values since those are dangerous to
+// use. we will fail if dangerous globals are used.
+std::unique_ptr<Module> buildEnvModule(Module& wasm) {
+  auto env = std::make_unique<Module>();
+  env->name = "env";
+
+  // create empty functions with similar signature
+  ModuleUtils::iterImportedFunctions(wasm, [&](Function* func) {
+    if (func->module == "env") {
+      Builder builder(*env);
+      auto* copied = ModuleUtils::copyFunction(func, *env);
+      copied->module = Name();
+      copied->base = Name();
+      copied->body = builder.makeUnreachable();
+      env->addExport(
+        builder.makeExport(func->base, copied->name, ExternalKind::Function));
+    }
+  });
+
+  // create tables with similar initial and max values
+  ModuleUtils::iterImportedTables(wasm, [&](Table* table) {
+    if (table->module == "env") {
+      auto* copied = ModuleUtils::copyTable(table, *env);
+      copied->module = Name();
+      copied->base = Name();
+      env->addExport(Builder(*env).makeExport(
+        table->base, copied->name, ExternalKind::Table));
+    }
+  });
+
+  ModuleUtils::iterImportedGlobals(wasm, [&](Global* global) {
+    if (global->module == "env") {
+      auto* copied = ModuleUtils::copyGlobal(global, *env);
+      copied->module = Name();
+      copied->base = Name();
+
+      Builder builder(*env);
+      if (global->base == STACKTOP || global->base == STACK_MAX) {
+        copied->init = builder.makeConst(STACK_START);
+      } else {
+        copied->init = builder.makeConst(Literal::makeZero(global->type));
+      }
+      env->addExport(
+        builder.makeExport(global->base, copied->name, ExternalKind::Global));
+    }
+  });
+
+  // create an exported memory with the same initial and max size
+  ModuleUtils::iterImportedMemories(wasm, [&](Memory* memory) {
+    if (memory->module == "env") {
+      env->memory.name = wasm.memory.name;
+      env->memory.exists = true;
+      env->memory.initial = memory->initial;
+      env->memory.max = memory->max;
+      env->memory.shared = memory->shared;
+      env->memory.indexType = memory->indexType;
+      env->addExport(Builder(*env).makeExport(
+        wasm.memory.base, wasm.memory.name, ExternalKind::Memory));
+    }
+  });
+
+  return env;
+}
+
 struct CtorEvalExternalInterface : EvallingModuleInstance::ExternalInterface {
   Module* wasm;
   EvallingModuleInstance* instance;
+  std::map<Name, std::shared_ptr<EvallingModuleInstance>> linkedInstances;
+
+  CtorEvalExternalInterface(
+    std::map<Name, std::shared_ptr<EvallingModuleInstance>> linkedInstances_ =
+      {}) {
+    linkedInstances.swap(linkedInstances_);
+  }
 
   void init(Module& wasm_, EvallingModuleInstance& instance_) override {
     wasm = &wasm_;
@@ -175,31 +251,20 @@ struct CtorEvalExternalInterface : EvallingModuleInstance::ExternalInterface {
   }
 
   void importGlobals(EvallingGlobalManager& globals, Module& wasm_) override {
-    // fill usable values for stack imports, and globals initialized to them
-    ImportInfo imports(wasm_);
-    if (auto* stackTop = imports.getImportedGlobal(ENV, STACKTOP)) {
-      globals[stackTop->name] = {Literal(int32_t(STACK_START))};
-      if (auto* stackTop =
-            GlobalUtils::getGlobalInitializedToImport(wasm_, ENV, STACKTOP)) {
-        globals[stackTop->name] = {Literal(int32_t(STACK_START))};
-      }
-    }
-    if (auto* stackMax = imports.getImportedGlobal(ENV, STACK_MAX)) {
-      globals[stackMax->name] = {Literal(int32_t(STACK_START))};
-      if (auto* stackMax =
-            GlobalUtils::getGlobalInitializedToImport(wasm_, ENV, STACK_MAX)) {
-        globals[stackMax->name] = {Literal(int32_t(STACK_START))};
-      }
-    }
-    // fill in fake values for everything else, which is dangerous to use
-    ModuleUtils::iterDefinedGlobals(wasm_, [&](Global* defined) {
-      if (globals.find(defined->name) == globals.end()) {
-        globals[defined->name] = Literal::makeZeros(defined->type);
-      }
-    });
-    ModuleUtils::iterImportedGlobals(wasm_, [&](Global* import) {
-      if (globals.find(import->name) == globals.end()) {
-        globals[import->name] = Literal::makeZeros(import->type);
+    ModuleUtils::iterImportedGlobals(wasm_, [&](Global* global) {
+      auto it = linkedInstances.find(global->module);
+      if (it != linkedInstances.end()) {
+        auto* inst = it->second.get();
+        auto* globalExport = inst->wasm.getExportOrNull(global->base);
+        if (!globalExport) {
+          throw FailToEvalException(std::string("importGlobals: ") +
+                                    global->module.str + "." +
+                                    global->base.str);
+        }
+        globals[global->name] = inst->globals[globalExport->value];
+      } else {
+        throw FailToEvalException(std::string("importGlobals: ") +
+                                  global->module.str + "." + global->base.str);
       }
     });
   }
@@ -368,14 +433,25 @@ private:
 };
 
 void evalCtors(Module& wasm, std::vector<std::string> ctors) {
-  CtorEvalExternalInterface interface;
+  // build and link the env module
+  auto envModule = buildEnvModule(wasm);
+  CtorEvalExternalInterface envInterface;
+  auto envInstance =
+    std::make_shared<EvallingModuleInstance>(*envModule, &envInterface);
+  envInstance->setupEnvironment();
+
+  std::map<Name, std::shared_ptr<EvallingModuleInstance>> linkedInstances;
+  linkedInstances["env"] = envInstance;
+
+  CtorEvalExternalInterface interface(linkedInstances);
   try {
     // flatten memory, so we do not depend on the layout of data segments
     if (!MemoryUtils::flatten(wasm.memory)) {
       Fatal() << "  ...stopping since could not flatten memory\n";
     }
+
     // create an instance for evalling
-    EvallingModuleInstance instance(wasm, &interface);
+    EvallingModuleInstance instance(wasm, &interface, linkedInstances);
     // set up the stack area and other environment details
     instance.setupEnvironment();
     // we should not add new globals from here on; as a result, using
diff --git a/src/tools/wasm-shell.cpp b/src/tools/wasm-shell.cpp
index 6d2077e1c..a2d35f444 100644
--- a/src/tools/wasm-shell.cpp
+++ b/src/tools/wasm-shell.cpp
@@ -19,7 +19,6 @@
 // and executes it. This provides similar functionality as the reference
 // interpreter, like assert_* calls, so it can run the spec test suite.
 //
-
 #include <memory>
 
 #include "execution-results.h"
@@ -41,300 +40,384 @@ Name ASSERT_INVALID("assert_invalid");
 Name ASSERT_MALFORMED("assert_malformed");
 Name ASSERT_UNLINKABLE("assert_unlinkable");
 Name INVOKE("invoke");
+Name REGISTER("register");
 Name GET("get");
 
-//
-// An operation on a module
-//
+struct ShellOptions : public Options {
+  Name entry;
+  std::set<size_t> skipped;
 
-struct Operation {
-  ModuleInstance* instance;
-  Name operation;
-  Name name;
-  LiteralList arguments;
-
-  Operation(Element& element,
-            ModuleInstance* instanceInit,
-            SExpressionWasmBuilder& builder,
-            std::map<Name, std::unique_ptr<ModuleInstance>>& instances)
-    : instance(instanceInit) {
-    operation = element[0]->str();
-    Index i = 1;
-    if (element.size() >= 3 && element[2]->isStr()) {
-      // module also specified
-      Name moduleName = element[i++]->str();
-      instance = instances[moduleName].get();
-    }
-    name = element[i++]->str();
-    for (size_t j = i; j < element.size(); j++) {
-      Expression* argument = builder.parseExpression(*element[j]);
-      arguments.push_back(getLiteralFromConstExpression(argument));
-    }
+  ShellOptions(const std::string& command, const std::string& description)
+    : Options(command, description) {
+    (*this)
+      .add("--entry",
+           "-e",
+           "Call the entry point after parsing the module",
+           Options::Arguments::One,
+           [this](Options*, const std::string& argument) { entry = argument; })
+      .add("--skip",
+           "-s",
+           "Skip input on certain lines (comma-separated-list)",
+           Options::Arguments::One,
+           [this](Options*, const std::string& argument) {
+             size_t i = 0;
+             while (i < argument.size()) {
+               auto ending = argument.find(',', i);
+               if (ending == std::string::npos) {
+                 ending = argument.size();
+               }
+               auto sub = argument.substr(i, ending - i);
+               skipped.insert(atoi(sub.c_str()));
+               i = ending + 1;
+             }
+           })
+      .add_positional("INFILE",
+                      Options::Arguments::One,
+                      [](Options* o, const std::string& argument) {
+                        o->extra["infile"] = argument;
+                      });
   }
+};
 
-  Literals operate() {
-    if (operation == INVOKE) {
-      return instance->callExport(name, arguments);
-    } else if (operation == GET) {
-      return {instance->getExport(name)};
-    } else {
-      WASM_UNREACHABLE("unknown operation");
-    }
+class Shell {
+protected:
+  std::map<Name, std::unique_ptr<Module>> modules;
+  std::map<Name, std::unique_ptr<SExpressionWasmBuilder>> builders;
+  std::map<Name, std::unique_ptr<ShellExternalInterface>> interfaces;
+  std::map<Name, std::shared_ptr<ModuleInstance>> instances;
+  // used for imports
+  std::map<Name, std::shared_ptr<ModuleInstance>> linkedInstances;
+
+  Name lastModule;
+
+  void instantiate(Module* wasm) {
+    auto tempInterface =
+      wasm::make_unique<ShellExternalInterface>(linkedInstances);
+    auto tempInstance = std::make_shared<ModuleInstance>(
+      *wasm, tempInterface.get(), linkedInstances);
+    interfaces[wasm->name].swap(tempInterface);
+    instances[wasm->name].swap(tempInstance);
   }
-};
 
-static void
-run_asserts(Name moduleName,
-            size_t* i,
-            bool* checked,
-            Module* wasm,
-            Element* root,
-            SExpressionWasmBuilder* builder,
-            Name entry,
-            std::map<Name, std::unique_ptr<ShellExternalInterface>>& interfaces,
-            std::map<Name, std::unique_ptr<ModuleInstance>>& instances) {
-  ModuleInstance* instance = nullptr;
-  if (wasm) {
-    // prefix make_unique to work around visual studio bugs
-    auto tempInterface = wasm::make_unique<ShellExternalInterface>();
-    auto tempInstance =
-      wasm::make_unique<ModuleInstance>(*wasm, tempInterface.get());
-    interfaces[moduleName].swap(tempInterface);
-    instances[moduleName].swap(tempInstance);
-    instance = instances[moduleName].get();
-    if (entry.is()) {
-      Function* function = wasm->getFunction(entry);
-      if (!function) {
-        std::cerr << "Unknown entry " << entry << std::endl;
-      } else {
-        LiteralList arguments;
-        for (const auto& param : function->sig.params) {
-          arguments.push_back(Literal(param));
-        }
-        try {
-          instance->callExport(entry, arguments);
-        } catch (ExitException&) {
-        }
-      }
+  void parse(Element& s) {
+    IString id = s[0]->str();
+    if (id == MODULE) {
+      parseModule(s);
+    } else if (id == REGISTER) {
+      parseRegister(s);
+    } else if (id == INVOKE) {
+      parseOperation(s);
+    } else if (id == ASSERT_RETURN) {
+      parseAssertReturn(s);
+    } else if (id == ASSERT_TRAP) {
+      parseAssertTrap(s);
+    } else if ((id == ASSERT_INVALID) || (id == ASSERT_MALFORMED)) {
+      parseModuleAssertion(s);
     }
   }
-  while (*i < root->size()) {
-    Element& curr = *(*root)[*i];
-    IString id = curr[0]->str();
-    if (id == MODULE) {
-      break;
+
+  Module* parseModule(Element& s) {
+    if (options.debug) {
+      std::cerr << "parsing s-expressions to wasm...\n";
     }
-    *checked = true;
-    Colors::red(std::cerr);
-    std::cerr << *i << '/' << (root->size() - 1);
     Colors::green(std::cerr);
-    std::cerr << " CHECKING: ";
+    std::cerr << "BUILDING MODULE [line: " << s.line << "]\n";
     Colors::normal(std::cerr);
-    std::cerr << curr;
+    auto module = wasm::make_unique<Module>();
+    auto builder =
+      wasm::make_unique<SExpressionWasmBuilder>(*module, s, IRProfile::Normal);
+    auto moduleName = module->name;
+    lastModule = module->name;
+    builders[moduleName].swap(builder);
+    modules[moduleName].swap(module);
+    modules[moduleName]->features = FeatureSet::All;
+    bool valid = WasmValidator().validate(*modules[moduleName]);
+    if (!valid) {
+      std::cout << *modules[moduleName] << '\n';
+      Fatal() << "module failed to validate, see above";
+    }
+
+    instantiate(modules[moduleName].get());
+
+    return modules[moduleName].get();
+  }
+
+  void parseRegister(Element& s) {
+    auto instance = instances[lastModule];
+    if (!instance) {
+      Fatal() << "register called without a module";
+    }
+    auto name = s[1]->str();
+    linkedInstances[name] = instance;
+
+    // swap to the new name in all maps
+    modules[name].swap(modules[lastModule]);
+    modules.erase(lastModule);
+    builders[name].swap(builders[lastModule]);
+    builders.erase(lastModule);
+    interfaces[name].swap(interfaces[lastModule]);
+    interfaces.erase(lastModule);
+    instances[name].swap(instances[lastModule]);
+    instances.erase(lastModule);
+
     Colors::green(std::cerr);
-    std::cerr << " [line: " << curr.line << "]\n";
+    std::cerr << "REGISTER MODULE INSTANCE AS \"" << name.c_str()
+              << "\"  [line: " << s.line << "]\n";
     Colors::normal(std::cerr);
-    if (id == ASSERT_INVALID || id == ASSERT_MALFORMED ||
-        id == ASSERT_UNLINKABLE) {
-      // a module invalidity test
-      Module wasm;
-      wasm.features = FeatureSet::All;
-      bool invalid = false;
-      std::unique_ptr<SExpressionWasmBuilder> builder;
-      try {
-        builder = std::unique_ptr<SExpressionWasmBuilder>(
-          new SExpressionWasmBuilder(wasm, *curr[1], IRProfile::Normal));
-      } catch (const ParseException&) {
-        invalid = true;
-      }
-      if (!invalid) {
-        // maybe parsed ok, but otherwise incorrect
-        invalid = !WasmValidator().validate(wasm);
+  }
+
+  Literals parseOperation(Element& s) {
+    Index i = 1;
+    Name moduleName = lastModule;
+    if (s[i]->dollared()) {
+      moduleName = s[i++]->str();
+    }
+    ModuleInstance* instance = instances[moduleName].get();
+    assert(instance);
+
+    Name base = s[i++]->str();
+
+    if (s[0]->str() == INVOKE) {
+      LiteralList args;
+      while (i < s.size()) {
+        Expression* argument = builders[moduleName]->parseExpression(*s[i++]);
+        args.push_back(getLiteralFromConstExpression(argument));
       }
-      if (!invalid && id == ASSERT_UNLINKABLE) {
-        // validate "instantiating" the mdoule
-        auto reportUnknownImport = [&](Importable* import) {
+
+      return instance->callExport(base, args);
+    } else if (s[0]->str() == GET) {
+      return instance->getExport(base);
+    }
+
+    Fatal() << "Invalid operation " << s[0]->c_str();
+  }
+
+  void parseAssertTrap(Element& s) {
+    bool trapped = false;
+    auto& inner = *s[1];
+    if (inner[0]->str() == MODULE) {
+      return parseModuleAssertion(s);
+    }
+
+    try {
+      parseOperation(inner);
+    } catch (const TrapException&) {
+      trapped = true;
+    } catch (const WasmException& e) {
+      std::cout << "[exception thrown: " << e << "]" << std::endl;
+      trapped = true;
+    }
+
+    assert(trapped);
+  }
+
+  void parseAssertReturn(Element& s) {
+    Literals actual;
+    Literals expected;
+    if (s.size() >= 3) {
+      expected = getLiteralsFromConstExpression(
+        builders[lastModule]->parseExpression(*s[2]));
+    }
+    bool trapped = false;
+    try {
+      actual = parseOperation(*s[1]);
+    } catch (const TrapException&) {
+      trapped = true;
+    } catch (const WasmException& e) {
+      std::cout << "[exception thrown: " << e << "]" << std::endl;
+      trapped = true;
+    }
+    assert(!trapped);
+    std::cerr << "seen " << actual << ", expected " << expected << '\n';
+    if (expected != actual) {
+      Fatal() << "unexpected, should be identical\n";
+    }
+  }
+
+  void parseModuleAssertion(Element& s) {
+    Module wasm;
+    wasm.features = FeatureSet::All;
+    std::unique_ptr<SExpressionWasmBuilder> builder;
+    auto id = s[0]->str();
+
+    bool invalid = false;
+    try {
+      SExpressionWasmBuilder(wasm, *s[1], IRProfile::Normal);
+    } catch (const ParseException&) {
+      invalid = true;
+    }
+
+    if (!invalid) {
+      // maybe parsed ok, but otherwise incorrect
+      invalid = !WasmValidator().validate(wasm);
+    }
+
+    if (!invalid && id == ASSERT_UNLINKABLE) {
+      // validate "instantiating" the mdoule
+      auto reportUnknownImport = [&](Importable* import) {
+        auto it = linkedInstances.find(import->module);
+        if (it == linkedInstances.end() ||
+            it->second->wasm.getExportOrNull(import->base) == nullptr) {
           std::cerr << "unknown import: " << import->module << '.'
                     << import->base << '\n';
           invalid = true;
-        };
-        ModuleUtils::iterImportedGlobals(wasm, reportUnknownImport);
-        ModuleUtils::iterImportedTables(wasm, reportUnknownImport);
-        ModuleUtils::iterImportedFunctions(wasm, [&](Importable* import) {
-          if (import->module == SPECTEST && import->base.startsWith(PRINT)) {
-            // We can handle it.
-          } else {
-            reportUnknownImport(import);
-          }
-        });
-        ElementUtils::iterAllElementFunctionNames(&wasm, [&](Name name) {
-          // spec tests consider it illegal to use spectest.print in a table
-          if (auto* import = wasm.getFunction(name)) {
-            if (import->imported() && import->module == SPECTEST &&
-                import->base.startsWith(PRINT)) {
-              std::cerr << "cannot put spectest.print in table\n";
-              invalid = true;
-            }
+        }
+      };
+      ModuleUtils::iterImportedGlobals(wasm, reportUnknownImport);
+      ModuleUtils::iterImportedTables(wasm, reportUnknownImport);
+      ModuleUtils::iterImportedFunctions(wasm, [&](Importable* import) {
+        if (import->module == SPECTEST && import->base.startsWith(PRINT)) {
+          // We can handle it.
+        } else {
+          reportUnknownImport(import);
+        }
+      });
+      ElementUtils::iterAllElementFunctionNames(&wasm, [&](Name name) {
+        // spec tests consider it illegal to use spectest.print in a table
+        if (auto* import = wasm.getFunction(name)) {
+          if (import->imported() && import->module == SPECTEST &&
+              import->base.startsWith(PRINT)) {
+            std::cerr << "cannot put spectest.print in table\n";
+            invalid = true;
           }
-        });
-        if (wasm.memory.imported()) {
-          reportUnknownImport(&wasm.memory);
         }
+      });
+      if (wasm.memory.imported()) {
+        reportUnknownImport(&wasm.memory);
       }
-      if (!invalid) {
-        Colors::red(std::cerr);
-        std::cerr << "[should have been invalid]\n";
-        Colors::normal(std::cerr);
-        Fatal() << &wasm << '\n';
-      }
-    } else if (id == INVOKE) {
-      assert(wasm);
-      Operation operation(curr, instance, *builder, instances);
-      operation.operate();
-    } else if (wasm) { // if no wasm, we skipped the module
-      // an invoke test
-      bool trapped = false;
-      WASM_UNUSED(trapped);
-      Literals result;
+    }
+
+    if (!invalid && id == ASSERT_TRAP) {
       try {
-        Operation operation(*curr[1], instance, *builder, instances);
-        result = operation.operate();
+        instantiate(&wasm);
       } catch (const TrapException&) {
-        trapped = true;
+        invalid = true;
       } catch (const WasmException& e) {
         std::cout << "[exception thrown: " << e << "]" << std::endl;
-        trapped = true;
-      }
-      if (id == ASSERT_RETURN) {
-        assert(!trapped);
-        Literals expected;
-        if (curr.size() >= 3) {
-          expected =
-            getLiteralsFromConstExpression(builder->parseExpression(*curr[2]));
-        }
-        std::cerr << "seen " << result << ", expected " << expected << '\n';
-        if (expected != result) {
-          Fatal() << "unexpected, should be identical\n";
-        }
-      }
-      if (id == ASSERT_TRAP) {
-        assert(trapped);
+        invalid = true;
       }
     }
-    *i += 1;
-  }
-}
 
-//
-// main
-//
+    if (!invalid) {
+      Colors::red(std::cerr);
+      std::cerr << "[should have been invalid]\n";
+      Colors::normal(std::cerr);
+      Fatal() << &wasm << '\n';
+    }
+  }
 
-int main(int argc, const char* argv[]) {
-  Name entry;
-  std::set<size_t> skipped;
+protected:
+  ShellOptions& options;
 
-  Options options("wasm-shell", "Execute .wast files");
-  options
-    .add("--entry",
-         "-e",
-         "Call the entry point after parsing the module",
-         Options::Arguments::One,
-         [&entry](Options*, const std::string& argument) { entry = argument; })
-    .add("--skip",
-         "-s",
-         "Skip input on certain lines (comma-separated-list)",
-         Options::Arguments::One,
-         [&skipped](Options*, const std::string& argument) {
-           size_t i = 0;
-           while (i < argument.size()) {
-             auto ending = argument.find(',', i);
-             if (ending == std::string::npos) {
-               ending = argument.size();
-             }
-             auto sub = argument.substr(i, ending - i);
-             skipped.insert(atoi(sub.c_str()));
-             i = ending + 1;
-           }
-         })
-    .add_positional("INFILE",
-                    Options::Arguments::One,
-                    [](Options* o, const std::string& argument) {
-                      o->extra["infile"] = argument;
-                    });
-  options.parse(argc, argv);
+  // spectest module is a default host-provided module defined by the spec's
+  // reference interpreter. It's been replaced by the `(register ...)`
+  // mechanism in the recent spec tests, and is kept for legacy tests only.
+  //
+  // TODO: spectest module is considered deprecated by the spec. Remove when
+  // is actually removed from the spec test.
+  void buildSpectestModule() {
+    auto spectest = std::make_unique<Module>();
+    spectest->name = "spectest";
+    Builder builder(*spectest);
 
-  auto input(
-    read_file<std::vector<char>>(options.extra["infile"], Flags::Text));
+    spectest->addGlobal(builder.makeGlobal(Name::fromInt(0),
+                                           Type::i32,
+                                           builder.makeConst<uint32_t>(666),
+                                           Builder::Immutable));
+    spectest->addGlobal(builder.makeGlobal(Name::fromInt(1),
+                                           Type::i64,
+                                           builder.makeConst<uint64_t>(666),
+                                           Builder::Immutable));
+    spectest->addGlobal(builder.makeGlobal(Name::fromInt(2),
+                                           Type::f32,
+                                           builder.makeConst<float>(666.6),
+                                           Builder::Immutable));
+    spectest->addGlobal(builder.makeGlobal(Name::fromInt(3),
+                                           Type::f64,
+                                           builder.makeConst<double>(666.6),
+                                           Builder::Immutable));
+    spectest->addExport(
+      builder.makeExport("global_i32", Name::fromInt(0), ExternalKind::Global));
+    spectest->addExport(
+      builder.makeExport("global_i64", Name::fromInt(1), ExternalKind::Global));
+    spectest->addExport(
+      builder.makeExport("global_f32", Name::fromInt(2), ExternalKind::Global));
+    spectest->addExport(
+      builder.makeExport("global_f64", Name::fromInt(3), ExternalKind::Global));
 
-  bool checked = false;
+    spectest->addTable(
+      builder.makeTable(Name::fromInt(0), Type::funcref, 10, 20));
+    spectest->addExport(
+      builder.makeExport("table", Name::fromInt(0), ExternalKind::Table));
 
-  // Modules named in the file
+    spectest->memory.exists = true;
+    spectest->memory.initial = 1;
+    spectest->memory.max = 2;
+    spectest->addExport(builder.makeExport(
+      "memory", spectest->memory.name, ExternalKind::Memory));
 
-  std::map<Name, std::unique_ptr<Module>> modules;
-  std::map<Name, std::unique_ptr<SExpressionWasmBuilder>> builders;
-  std::map<Name, std::unique_ptr<ShellExternalInterface>> interfaces;
-  std::map<Name, std::unique_ptr<ModuleInstance>> instances;
+    modules["spectest"].swap(spectest);
+    modules["spectest"]->features = FeatureSet::All;
+    instantiate(modules["spectest"].get());
+    linkedInstances["spectest"] = instances["spectest"];
+    // print_* functions are handled separately, no need to define here.
+  }
 
-  try {
-    if (options.debug) {
-      std::cerr << "parsing text to s-expressions...\n";
-    }
-    SExpressionParser parser(input.data());
-    Element& root = *parser.root;
+public:
+  Shell(ShellOptions& options) : options(options) { buildSpectestModule(); }
 
-    // A .wast may have multiple modules, with some asserts after them
+  bool parseAndRun(Element& root) {
     size_t i = 0;
     while (i < root.size()) {
       Element& curr = *root[i];
-      if (skipped.count(curr.line) > 0) {
+
+      if (options.skipped.count(curr.line) > 0) {
         Colors::green(std::cerr);
         std::cerr << "SKIPPING [line: " << curr.line << "]\n";
         Colors::normal(std::cerr);
         i++;
         continue;
       }
-      IString id = curr[0]->str();
-      if (id == MODULE) {
-        if (options.debug) {
-          std::cerr << "parsing s-expressions to wasm...\n";
-        }
+
+      if (curr[0]->str() != MODULE) {
+        Colors::red(std::cerr);
+        std::cerr << i << '/' << (root.size() - 1);
         Colors::green(std::cerr);
-        std::cerr << "BUILDING MODULE [line: " << curr.line << "]\n";
+        std::cerr << " CHECKING: ";
+        Colors::normal(std::cerr);
+        std::cerr << curr;
+        Colors::green(std::cerr);
+        std::cerr << " [line: " << curr.line << "]\n";
         Colors::normal(std::cerr);
-        auto module = wasm::make_unique<Module>();
-        auto builder = wasm::make_unique<SExpressionWasmBuilder>(
-          *module, *root[i], IRProfile::Normal);
-        auto moduleName = module->name;
-        builders[moduleName].swap(builder);
-        modules[moduleName].swap(module);
-        i++;
-        modules[moduleName]->features = FeatureSet::All;
-        bool valid = WasmValidator().validate(*modules[moduleName]);
-        if (!valid) {
-          std::cout << *modules[moduleName] << '\n';
-          Fatal() << "module failed to validate, see above";
-        }
-        run_asserts(moduleName,
-                    &i,
-                    &checked,
-                    modules[moduleName].get(),
-                    &root,
-                    builders[moduleName].get(),
-                    entry,
-                    interfaces,
-                    instances);
-      } else {
-        run_asserts(Name(),
-                    &i,
-                    &checked,
-                    nullptr,
-                    &root,
-                    nullptr,
-                    entry,
-                    interfaces,
-                    instances);
       }
+
+      parse(curr);
+
+      i += 1;
     }
+
+    return false;
+  }
+};
+
+int main(int argc, const char* argv[]) {
+  Name entry;
+  std::set<size_t> skipped;
+
+  ShellOptions options("wasm-shell", "Execute .wast files");
+  options.parse(argc, argv);
+
+  auto input(
+    read_file<std::vector<char>>(options.extra["infile"], Flags::Text));
+
+  bool checked = false;
+  try {
+    if (options.debug) {
+      std::cerr << "parsing text to s-expressions...\n";
+    }
+    SExpressionParser parser(input.data());
+    Element& root = *parser.root;
+    checked = Shell(options).parseAndRun(root);
   } catch (ParseException& p) {
     p.dump(std::cerr);
     exit(1);
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 37bebdf6b..8c772a96e 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -2068,6 +2068,8 @@ public:
   // an imported function or accessing memory.
   //
   struct ExternalInterface {
+    ExternalInterface(
+      std::map<Name, std::shared_ptr<SubType>> linkedInstances = {}) {}
     virtual ~ExternalInterface() = default;
     virtual void init(Module& wasm, SubType& instance) {}
     virtual void importGlobals(GlobalManager& globals, Module& wasm) = 0;
@@ -2241,8 +2243,12 @@ public:
   // Multivalue ABI support (see push/pop).
   std::vector<Literals> multiValues;
 
-  ModuleInstanceBase(Module& wasm, ExternalInterface* externalInterface)
-    : wasm(wasm), externalInterface(externalInterface) {
+  ModuleInstanceBase(
+    Module& wasm,
+    ExternalInterface* externalInterface,
+    std::map<Name, std::shared_ptr<SubType>> linkedInstances_ = {})
+    : wasm(wasm), externalInterface(externalInterface),
+      linkedInstances(linkedInstances_) {
     // import globals from the outside
     externalInterface->importGlobals(globals, wasm);
     // prepare memory
@@ -2314,19 +2320,24 @@ private:
 
   void initializeTableContents() {
     ModuleUtils::iterActiveElementSegments(wasm, [&](ElementSegment* segment) {
-      Address offset =
-        (uint32_t)InitializerExpressionRunner<GlobalManager>(globals, maxDepth)
-          .visit(segment->offset)
-          .getSingleValue()
-          .geti32();
-
       Function dummyFunc;
       FunctionScope dummyScope(&dummyFunc, {});
       RuntimeExpressionRunner runner(*this, dummyScope, maxDepth);
+
+      Address offset =
+        (uint32_t)runner.visit(segment->offset).getSingleValue().geti32();
+
+      Table* table = wasm.getTable(segment->table);
+      ExternalInterface* extInterface = externalInterface;
+      Name tableName = segment->table;
+      if (table->imported()) {
+        auto inst = linkedInstances.at(table->module);
+        extInterface = inst->externalInterface;
+        tableName = inst->wasm.getExport(table->base)->value;
+      }
       for (Index i = 0; i < segment->data.size(); ++i) {
         Flow ret = runner.visit(segment->data[i]);
-        externalInterface->tableStore(
-          segment->table, offset + i, ret.getSingleValue());
+        extInterface->tableStore(tableName, offset + i, ret.getSingleValue());
       }
     });
   }
@@ -2408,6 +2419,28 @@ private:
     // Stack of <caught exception, caught catch's try label>
     SmallVector<std::pair<WasmException, Name>, 4> exceptionStack;
 
+  protected:
+    // Returns the instance that defines the memory used by this one.
+    SubType* getMemoryInstance() {
+      if (instance.wasm.memory.imported()) {
+        return instance.linkedInstances.at(instance.wasm.memory.module).get();
+      } else {
+        return static_cast<SubType*>(&instance);
+      }
+    }
+
+    // Returns a reference to the current value of a potentially imported global
+    Literals& getGlobal(Name name) {
+      auto* global = instance.wasm.getGlobal(name);
+      if (global->imported()) {
+        auto inst = instance.linkedInstances.at(global->module);
+        Export* globalExport = inst->wasm.getExport(global->base);
+        return inst->globals[globalExport->value];
+      } else {
+        return instance.globals[name];
+      }
+    }
+
   public:
     RuntimeExpressionRunner(ModuleInstanceBase& instance,
                             FunctionScope& scope,
@@ -2450,10 +2483,26 @@ private:
       if (target.breaking()) {
         return target;
       }
+
       Index index = target.getSingleValue().geti32();
       Type type = curr->isReturn ? scope.function->sig.results : curr->type;
-      Flow ret = instance.externalInterface->callTable(
-        curr->table, index, curr->sig, arguments, type, *instance.self());
+
+      Flow ret;
+      auto* table = instance.wasm.getTable(curr->table);
+      if (table->imported()) {
+        auto inst = instance.linkedInstances.at(table->module);
+        Export* tableExport = inst->wasm.getExport(table->base);
+        ret = inst->externalInterface->callTable(tableExport->value,
+                                                 index,
+                                                 curr->sig,
+                                                 arguments,
+                                                 type,
+                                                 *instance.self());
+      } else {
+        ret = instance.externalInterface->callTable(
+          curr->table, index, curr->sig, arguments, type, *instance.self());
+      }
+
       // TODO: make this a proper tail call (return first)
       if (curr->isReturn) {
         ret.breakTo = RETURN_FLOW;
@@ -2518,9 +2567,7 @@ private:
       NOTE_ENTER("GlobalGet");
       auto name = curr->name;
       NOTE_EVAL1(name);
-      assert(instance.globals.find(name) != instance.globals.end());
-      NOTE_EVAL1(instance.globals[name]);
-      return instance.globals[name];
+      return getGlobal(name);
     }
     Flow visitGlobalSet(GlobalSet* curr) {
       NOTE_ENTER("GlobalSet");
@@ -2531,7 +2578,8 @@ private:
       }
       NOTE_EVAL1(name);
       NOTE_EVAL1(flow.getSingleValue());
-      instance.globals[name] = flow.values;
+
+      getGlobal(name) = flow.values;
       return Flow();
     }
 
@@ -2542,11 +2590,12 @@ private:
         return flow;
       }
       NOTE_EVAL1(flow);
-      auto addr = instance.getFinalAddress(curr, flow.getSingleValue());
+      auto* inst = getMemoryInstance();
+      auto addr = inst->getFinalAddress(curr, flow.getSingleValue());
       if (curr->isAtomic) {
-        instance.checkAtomicAddress(addr, curr->bytes);
+        inst->checkAtomicAddress(addr, curr->bytes);
       }
-      auto ret = instance.externalInterface->load(curr, addr);
+      auto ret = inst->externalInterface->load(curr, addr);
       NOTE_EVAL1(addr);
       NOTE_EVAL1(ret);
       return ret;
@@ -2561,13 +2610,14 @@ private:
       if (value.breaking()) {
         return value;
       }
-      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue());
+      auto* inst = getMemoryInstance();
+      auto addr = inst->getFinalAddress(curr, ptr.getSingleValue());
       if (curr->isAtomic) {
-        instance.checkAtomicAddress(addr, curr->bytes);
+        inst->checkAtomicAddress(addr, curr->bytes);
       }
       NOTE_EVAL1(addr);
       NOTE_EVAL1(value);
-      instance.externalInterface->store(curr, addr, value.getSingleValue());
+      inst->externalInterface->store(curr, addr, value.getSingleValue());
       return Flow();
     }
 
@@ -2582,10 +2632,11 @@ private:
         return value;
       }
       NOTE_EVAL1(ptr);
-      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue());
+      auto* inst = getMemoryInstance();
+      auto addr = inst->getFinalAddress(curr, ptr.getSingleValue());
       NOTE_EVAL1(addr);
       NOTE_EVAL1(value);
-      auto loaded = instance.doAtomicLoad(addr, curr->bytes, curr->type);
+      auto loaded = inst->doAtomicLoad(addr, curr->bytes, curr->type);
       NOTE_EVAL1(loaded);
       auto computed = value.getSingleValue();
       switch (curr->op) {
@@ -2607,7 +2658,7 @@ private:
         case RMWXchg:
           break;
       }
-      instance.doAtomicStore(addr, curr->bytes, computed);
+      inst->doAtomicStore(addr, curr->bytes, computed);
       return loaded;
     }
     Flow visitAtomicCmpxchg(AtomicCmpxchg* curr) {
@@ -2625,16 +2676,17 @@ private:
       if (replacement.breaking()) {
         return replacement;
       }
-      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue());
+      auto* inst = getMemoryInstance();
+      auto addr = inst->getFinalAddress(curr, ptr.getSingleValue());
       expected =
         Flow(wrapToSmallerSize(expected.getSingleValue(), curr->bytes));
       NOTE_EVAL1(addr);
       NOTE_EVAL1(expected);
       NOTE_EVAL1(replacement);
-      auto loaded = instance.doAtomicLoad(addr, curr->bytes, curr->type);
+      auto loaded = inst->doAtomicLoad(addr, curr->bytes, curr->type);
       NOTE_EVAL1(loaded);
       if (loaded == expected.getSingleValue()) {
-        instance.doAtomicStore(addr, curr->bytes, replacement.getSingleValue());
+        inst->doAtomicStore(addr, curr->bytes, replacement.getSingleValue());
       }
       return loaded;
     }
@@ -2655,9 +2707,10 @@ private:
       if (timeout.breaking()) {
         return timeout;
       }
+      auto* inst = getMemoryInstance();
       auto bytes = curr->expectedType.getByteSize();
-      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue(), bytes);
-      auto loaded = instance.doAtomicLoad(addr, bytes, curr->expectedType);
+      auto addr = inst->getFinalAddress(curr, ptr.getSingleValue(), bytes);
+      auto loaded = inst->doAtomicLoad(addr, bytes, curr->expectedType);
       NOTE_EVAL1(loaded);
       if (loaded != expected.getSingleValue()) {
         return Literal(int32_t(1)); // not equal
@@ -2678,9 +2731,10 @@ private:
       if (count.breaking()) {
         return count;
       }
-      auto addr = instance.getFinalAddress(curr, ptr.getSingleValue(), 4);
+      auto* inst = getMemoryInstance();
+      auto addr = inst->getFinalAddress(curr, ptr.getSingleValue(), 4);
       // Just check TODO actual threads support
-      instance.checkAtomicAddress(addr, 4);
+      inst->checkAtomicAddress(addr, 4);
       return Literal(int32_t(0)); // none woken up
     }
     Flow visitSIMDLoad(SIMDLoad* curr) {
@@ -2745,20 +2799,21 @@ private:
       }
       NOTE_EVAL1(flow);
       Address src(uint32_t(flow.getSingleValue().geti32()));
+      auto* inst = getMemoryInstance();
       auto loadLane = [&](Address addr) {
         switch (curr->op) {
           case Load8x8SVec128:
-            return Literal(int32_t(instance.externalInterface->load8s(addr)));
+            return Literal(int32_t(inst->externalInterface->load8s(addr)));
           case Load8x8UVec128:
-            return Literal(int32_t(instance.externalInterface->load8u(addr)));
+            return Literal(int32_t(inst->externalInterface->load8u(addr)));
           case Load16x4SVec128:
-            return Literal(int32_t(instance.externalInterface->load16s(addr)));
+            return Literal(int32_t(inst->externalInterface->load16s(addr)));
           case Load16x4UVec128:
-            return Literal(int32_t(instance.externalInterface->load16u(addr)));
+            return Literal(int32_t(inst->externalInterface->load16u(addr)));
           case Load32x2SVec128:
-            return Literal(int64_t(instance.externalInterface->load32s(addr)));
+            return Literal(int64_t(inst->externalInterface->load32s(addr)));
           case Load32x2UVec128:
-            return Literal(int64_t(instance.externalInterface->load32u(addr)));
+            return Literal(int64_t(inst->externalInterface->load32u(addr)));
           default:
             WASM_UNREACHABLE("unexpected op");
         }
@@ -2767,7 +2822,7 @@ private:
       auto fillLanes = [&](auto lanes, size_t laneBytes) {
         for (auto& lane : lanes) {
           lane = loadLane(
-            instance.getFinalAddress(curr, Literal(uint32_t(src)), laneBytes));
+            inst->getFinalAddress(curr, Literal(uint32_t(src)), laneBytes));
           src = Address(uint32_t(src) + laneBytes);
         }
         return Literal(lanes);
@@ -2799,15 +2854,16 @@ private:
         return flow;
       }
       NOTE_EVAL1(flow);
-      Address src = instance.getFinalAddress(
-        curr, flow.getSingleValue(), curr->getMemBytes());
+      auto* inst = getMemoryInstance();
+      Address src =
+        inst->getFinalAddress(curr, flow.getSingleValue(), curr->getMemBytes());
       auto zero =
         Literal::makeZero(curr->op == Load32ZeroVec128 ? Type::i32 : Type::i64);
       if (curr->op == Load32ZeroVec128) {
-        auto val = Literal(instance.externalInterface->load32u(src));
+        auto val = Literal(inst->externalInterface->load32u(src));
         return Literal(std::array<Literal, 4>{{val, zero, zero, zero}});
       } else {
-        auto val = Literal(instance.externalInterface->load64u(src));
+        auto val = Literal(inst->externalInterface->load64u(src));
         return Literal(std::array<Literal, 2>{{val, zero}});
       }
     }
@@ -2818,8 +2874,9 @@ private:
         return flow;
       }
       NOTE_EVAL1(flow);
-      Address addr = instance.getFinalAddress(
-        curr, flow.getSingleValue(), curr->getMemBytes());
+      auto* inst = getMemoryInstance();
+      Address addr =
+        inst->getFinalAddress(curr, flow.getSingleValue(), curr->getMemBytes());
       flow = this->visit(curr->vec);
       if (flow.breaking()) {
         return flow;
@@ -2830,12 +2887,10 @@ private:
         case Store8LaneVec128: {
           std::array<Literal, 16> lanes = vec.getLanesUI8x16();
           if (curr->isLoad()) {
-            lanes[curr->index] =
-              Literal(instance.externalInterface->load8u(addr));
+            lanes[curr->index] = Literal(inst->externalInterface->load8u(addr));
             return Literal(lanes);
           } else {
-            instance.externalInterface->store8(addr,
-                                               lanes[curr->index].geti32());
+            inst->externalInterface->store8(addr, lanes[curr->index].geti32());
             return {};
           }
         }
@@ -2844,11 +2899,10 @@ private:
           std::array<Literal, 8> lanes = vec.getLanesUI16x8();
           if (curr->isLoad()) {
             lanes[curr->index] =
-              Literal(instance.externalInterface->load16u(addr));
+              Literal(inst->externalInterface->load16u(addr));
             return Literal(lanes);
           } else {
-            instance.externalInterface->store16(addr,
-                                                lanes[curr->index].geti32());
+            inst->externalInterface->store16(addr, lanes[curr->index].geti32());
             return {};
           }
         }
@@ -2857,11 +2911,10 @@ private:
           std::array<Literal, 4> lanes = vec.getLanesI32x4();
           if (curr->isLoad()) {
             lanes[curr->index] =
-              Literal(instance.externalInterface->load32u(addr));
+              Literal(inst->externalInterface->load32u(addr));
             return Literal(lanes);
           } else {
-            instance.externalInterface->store32(addr,
-                                                lanes[curr->index].geti32());
+            inst->externalInterface->store32(addr, lanes[curr->index].geti32());
             return {};
           }
         }
@@ -2870,11 +2923,10 @@ private:
           std::array<Literal, 2> lanes = vec.getLanesI64x2();
           if (curr->isLoad()) {
             lanes[curr->index] =
-              Literal(instance.externalInterface->load64u(addr));
+              Literal(inst->externalInterface->load64u(addr));
             return Literal(lanes);
           } else {
-            instance.externalInterface->store64(addr,
-                                                lanes[curr->index].geti64());
+            inst->externalInterface->store64(addr, lanes[curr->index].geti64());
             return {};
           }
         }
@@ -2883,38 +2935,39 @@ private:
     }
     Flow visitMemorySize(MemorySize* curr) {
       NOTE_ENTER("MemorySize");
-      return Literal::makeFromInt64(instance.memorySize,
-                                    instance.wasm.memory.indexType);
+      auto* inst = getMemoryInstance();
+      return Literal::makeFromInt64(inst->memorySize,
+                                    inst->wasm.memory.indexType);
     }
     Flow visitMemoryGrow(MemoryGrow* curr) {
       NOTE_ENTER("MemoryGrow");
-      auto indexType = instance.wasm.memory.indexType;
+      auto* inst = getMemoryInstance();
+      auto indexType = inst->wasm.memory.indexType;
       auto fail = Literal::makeFromInt64(-1, indexType);
       Flow flow = this->visit(curr->delta);
       if (flow.breaking()) {
         return flow;
       }
-      Flow ret = Literal::makeFromInt64(instance.memorySize, indexType);
+      Flow ret = Literal::makeFromInt64(inst->memorySize, indexType);
       uint64_t delta = flow.getSingleValue().getUnsigned();
       if (delta > uint32_t(-1) / Memory::kPageSize && indexType == Type::i32) {
         return fail;
       }
-      if (instance.memorySize >= uint32_t(-1) - delta &&
-          indexType == Type::i32) {
+      if (inst->memorySize >= uint32_t(-1) - delta && indexType == Type::i32) {
         return fail;
       }
-      auto newSize = instance.memorySize + delta;
-      if (newSize > instance.wasm.memory.max) {
+      auto newSize = inst->memorySize + delta;
+      if (newSize > inst->wasm.memory.max) {
         return fail;
       }
-      if (!instance.externalInterface->growMemory(
-            instance.memorySize * Memory::kPageSize,
-            newSize * Memory::kPageSize)) {
+      if (!inst->externalInterface->growMemory(inst->memorySize *
+                                                 Memory::kPageSize,
+                                               newSize * Memory::kPageSize)) {
         // We failed to grow the memory in practice, even though it was valid
         // to try to do so.
         return fail;
       }
-      instance.memorySize = newSize;
+      inst->memorySize = newSize;
       return ret;
     }
     Flow visitMemoryInit(MemoryInit* curr) {
@@ -2949,13 +3002,14 @@ private:
       if ((uint64_t)offsetVal + sizeVal > segment.data.size()) {
         trap("out of bounds segment access in memory.init");
       }
-      if (destVal + sizeVal > instance.memorySize * Memory::kPageSize) {
+      auto* inst = getMemoryInstance();
+      if (destVal + sizeVal > inst->memorySize * Memory::kPageSize) {
         trap("out of bounds memory access in memory.init");
       }
       for (size_t i = 0; i < sizeVal; ++i) {
         Literal addr(destVal + i);
-        instance.externalInterface->store8(
-          instance.getFinalAddressWithoutOffset(addr, 1),
+        inst->externalInterface->store8(
+          inst->getFinalAddressWithoutOffset(addr, 1),
           segment.data[offsetVal + i]);
       }
       return {};
@@ -2986,8 +3040,9 @@ private:
       Address sourceVal(source.getSingleValue().getUnsigned());
       Address sizeVal(size.getSingleValue().getUnsigned());
 
-      if (sourceVal + sizeVal > instance.memorySize * Memory::kPageSize ||
-          destVal + sizeVal > instance.memorySize * Memory::kPageSize ||
+      auto* inst = getMemoryInstance();
+      if (sourceVal + sizeVal > inst->memorySize * Memory::kPageSize ||
+          destVal + sizeVal > inst->memorySize * Memory::kPageSize ||
           // FIXME: better/cheaper way to detect wrapping?
           sourceVal + sizeVal < sourceVal || sourceVal + sizeVal < sizeVal ||
           destVal + sizeVal < destVal || destVal + sizeVal < sizeVal) {
@@ -3004,10 +3059,10 @@ private:
         step = -1;
       }
       for (int64_t i = start; i != end; i += step) {
-        instance.externalInterface->store8(
-          instance.getFinalAddressWithoutOffset(Literal(destVal + i), 1),
-          instance.externalInterface->load8s(
-            instance.getFinalAddressWithoutOffset(Literal(sourceVal + i), 1)));
+        inst->externalInterface->store8(
+          inst->getFinalAddressWithoutOffset(Literal(destVal + i), 1),
+          inst->externalInterface->load8s(
+            inst->getFinalAddressWithoutOffset(Literal(sourceVal + i), 1)));
       }
       return {};
     }
@@ -3031,16 +3086,17 @@ private:
       Address destVal(dest.getSingleValue().getUnsigned());
       Address sizeVal(size.getSingleValue().getUnsigned());
 
+      auto* inst = getMemoryInstance();
       // FIXME: cheaper wrapping detection?
-      if (destVal > instance.memorySize * Memory::kPageSize ||
-          sizeVal > instance.memorySize * Memory::kPageSize ||
-          destVal + sizeVal > instance.memorySize * Memory::kPageSize) {
+      if (destVal > inst->memorySize * Memory::kPageSize ||
+          sizeVal > inst->memorySize * Memory::kPageSize ||
+          destVal + sizeVal > inst->memorySize * Memory::kPageSize) {
         trap("out of bounds memory access in memory.fill");
       }
       uint8_t val(value.getSingleValue().geti32());
       for (size_t i = 0; i < sizeVal; ++i) {
-        instance.externalInterface->store8(
-          instance.getFinalAddressWithoutOffset(Literal(destVal + i), 1), val);
+        inst->externalInterface->store8(
+          inst->getFinalAddressWithoutOffset(Literal(destVal + i), 1), val);
       }
       return {};
     }
@@ -3289,6 +3345,7 @@ protected:
   }
 
   ExternalInterface* externalInterface;
+  std::map<Name, std::shared_ptr<SubType>> linkedInstances;
 };
 
 // The default ModuleInstance uses a trivial global manager
@@ -3296,8 +3353,11 @@ using TrivialGlobalManager = std::map<Name, Literals>;
 class ModuleInstance
   : public ModuleInstanceBase<TrivialGlobalManager, ModuleInstance> {
 public:
-  ModuleInstance(Module& wasm, ExternalInterface* externalInterface)
-    : ModuleInstanceBase(wasm, externalInterface) {}
+  ModuleInstance(
+    Module& wasm,
+    ExternalInterface* externalInterface,
+    std::map<Name, std::shared_ptr<ModuleInstance>> linkedInstances = {})
+    : ModuleInstanceBase(wasm, externalInterface, linkedInstances) {}
 };
 
 } // namespace wasm
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 9f7a2af12..e6584972e 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -339,8 +339,19 @@ SExpressionWasmBuilder::SExpressionWasmBuilder(Module& wasm,
   Index i = 1;
   if (module[i]->dollared()) {
     wasm.name = module[i]->str();
+    if (module.size() == 2) {
+      return;
+    }
+    i++;
+  }
+
+  // spec tests have a `binary` keyword after the optional module name. Skip it
+  Name BINARY("binary");
+  if (module[i]->isStr() && module[i]->str() == BINARY &&
+      !module[i]->quoted()) {
     i++;
   }
+
   if (i < module.size() && module[i]->isStr()) {
     // these s-expressions contain a binary module, actually
     std::vector<char> data;
@@ -3290,6 +3301,10 @@ void SExpressionWasmBuilder::parseElem(Element& s, Table* table) {
     // Offset expression (offset (<expr>)) | (<expr>)
     auto& inner = *s[i++];
     if (elementStartsWith(inner, OFFSET)) {
+      if (inner.size() > 2) {
+        throw ParseException(
+          "Invalid offset for an element segment.", s.line, s.col);
+      }
       segment->offset = parseExpression(inner[1]);
     } else {
       segment->offset = parseExpression(inner);