自己动手实现一个 WebAssembly 解释器

原创姚忠孝字节前端 ByteFE

1. 前言

课程的 WebAssembly 工作原理一章已经详细介绍了基于栈结构的指令执行原理和过程，然而，了解 WebAssembly 原理最有效的方式仍然是自己动手实现一个执行引擎；本文将从零开始实现一个简单的 WebAssembly 解释器 WAInterp (WebAssembly Interpreter)，通过这一过程来进一步掌握和实践 WebAssembly 虚拟机技术。

本文将介绍最基本的虚拟机实现技术，高级优化虚拟机相关技术请阅读参考文献 [2~5] 中列出的相关专业书籍和文档。

2. WAInterp 解析器流程

从语义上讲，一个 WebAssembly 模块的生命周期可以分为"编译"、"解码"、"验证"、"实例化"、"指令执行" 几个阶段，而各个阶段分别创建和使用了 WebAssembly 模块的不同变体:

编译阶段: 将高级语言编译为 WebAssembly 规范定义的二进制或者文本两种模块格式，如果和传统汇编语言类比，模块的二进制格式相当于目标文件或可执行文件格式，文本格式则相当于汇编语言；
解码阶段: 将二进制模块解码为内存格式，内存格式是模块加载到内存之后的内部数据结构表示 (与实现相关)；
验证阶段: 对模块进行静态分析，确保模块的结构满足规范要求，且函数的字节码没有不良行为 (比如调用不存在的函数等)；
实例化阶段: 完成内存中函数、Table，线性内存，全局变量的链接及初始化工作；
执行阶段: 则完成函数的指令序列执行。

WebAssembly 模块生命周期流程如下图 1 所示。

图 1. WebAssembly 模块生命周期流程图

本文将从零开始实现一个简单的基于 IR (Intermediate Representation) 树遍历的 WebAssembly 二进制解释器 "WAInterp"；该解析器的执行主要包括二进制模块的"解码"、"实例化"、"执行"等几个阶段。接下来各个小节将逐一介绍每个阶段的详细设计和实现，以便读者可以循序渐进地构建 WAInterp 解析器。由于本文的主要目的是更好的理解 WebAssembly 底层原理、实践 WebAssembly 虚拟机相关技术，因此，我们采用相对简单和便于发布、共享的 Typescript 作为解析器的开发语言，并以 NPM 包的形式发布至 NPM Registery[6]，以便开发者能够方便的集成。

3. WAInterp 解码器

WAInterp 解释器的输入是 WebAssembly 二进制格式文件，实现二进制模块的加载和解码是模块实例化和指令执行的前提和必要条件；因此，本节先简要回顾下 WebAssembly 二进制格式相关内容，然后，实现一个二进制文件解码器；从而完成 WebAssembly 文件加载并转换为运行环境中对应的数据结构。

3.1 WAInterp 模块结构定义

与其他很多二进制格式 (比如 Java 类文件、ELF二进制文件) 类似，WebAssembly 二进制文件也是以魔数 (Magic Number )和版本号开头。在魔数和版本号之后是模块的主体内容，这些内容以段 (Section) 的形式进行组织。WebAssembly MVP 规范一共定义了12种段，并给每种段分配了 ID (从0到11)，除了自定义段以外，其他所有的段都最多只能出现一次，且必须按照段 ID 递增的顺序出现 (本文中暂不实现自定义段相关功能)。WebAssembly 模块结构如下图 2 所示。

图 2. WebAssembly 模块文件结构

根据 WebAssembly 模块的规范和格式定义 (如上图2所示)，我们为二进制模块定义如下的模块数据类型。

type BinaryModule = {
    Magic      : uint32,
    Version    : uint32,
    TypeSec    : Array<TypeInstruction>,
    ImportSec  : Array<ModuleImport>,
    FuncSec    : Array<Func>,
    TableSec   : Array <Table>,
    MemSec     : Array<Memory>,
    GlobalSec  : Array<Global>,
    ExportSec  : Array<ModuleExport>,
    StartFunc  : Funcidx,
    ElemSec    : Array<Elem>,
    CodeSec    : Array<Array<Instruction>>,
    DataSec    : Array<Data>
}

在详细描述 BinaryModule 各段 (Segment) 的表示和解码之前，我们先为 WebAssembly 内置的值类型定义对应的数据结构。WebAssembly 规范中定义了 4 种基本的值类型：32 位整数 (简称 i32)、64 位整数 (简称 i64)、32 位浮点数 (简称 f32) 和 64 位浮点数 (简称 f64)，与高级语言中的整数类型有所不同，WebAssembly 底层的整数类型是不区分符号的。高级语言所支持的一切类型 (比如布尔值、数值、指针、数组、结构体等)，都必须由编译器翻译成这 4 种基本类型或者组合。按照二进制规范，我们定义如下的 valtypes 来表示模块中定义的基本类型编码。

const valtypes = {
  0x7f: "i32",
  0x7e: "i64",
  0x7d: "f32",
  0x7c: "f64",
  0x7b: "v128",
};

在 BinaryModule 中的大部分段都包含结构化的项目，运行环境中这些结构化项目的容器被称呼为 "索引空间"。函数签名、函数、表、内存、全局变量等类型在模块内有各自的索引空间；局部变量和跳转标签在函数内有各自的索引空间。模块的各类索引空间及其作用可以总结如下：

类型索引空间: 不管是外部导入的函数还是内部定义的函数，其签名全都存储在类型段中，因此类型段的有效索引范围就是类型索引空间。
函数索引空间: 函数索引空间由外部函数和内部函数共同构成；当调用某函数时，需要给定该函数的索引。
全局变量索引空间: 和函数一样，全局变量索引空间也是由外部全局变量和内部全局变量共同构成的；当读写某全局变量时，需要给定该全局变量的索引。
表和内存索引: 表和内存也可以从外部导入，所以索引空间的情况和函数索引空间类似；由于 WebAssembly MVP 规范的限制，最多只能导入或定义一个表和内存，所以索引空间内的唯一有效索引只能是 0。
局部变量索引: 函数的局部变量索引空间由函数的参数和局部变量构成；当读写某参数或局部变量时，需要给定该参数或局部变量的索引。
跳转标签索引: 和局部变量索引一样，每个函数有自己的跳转标签索引空间；结构化控制指令和跳转指令需要指定跳转标签索引。

为了提高代码的可读性，我们给这些索引分别定义了类型别名，如下代码所示。

type U32Literal = NumberLiteral;
type Typeidx = U32Literal;
type Funcidx = U32Literal;
type Tableidx = U32Literal;
type Memidx = U32Literal;
type Globalidx = U32Literal;
type Localidx = U32Literal;
type Labelidx = U32Literal;

type Index =
  | Typeidx
  | Funcidx
  | Tableidx
  | Memidx
  | Globalidx
  | Localidx
  | Labelidx

3.2 WAInterp 段解码

模块解码是将 WebAssembly 二进制文件中各个段的编码数据解析为运行时环境中的数据结构的过程。为了便于理解，我们对 WebAssembly 二进制模块的的形式化表示[7] 做了简化，其中，id 表示各个段的识别号，byte_count 表示对应段的字节数，vec表示元素类型为 T 的向量，leb(T) 用于表示对应类型 T 的 LEB128 编码值，竖线 "|" 作为各个语义域的分隔符；采用简化的形式化描述，WebAssembly 中二进制格式中段编码可以见如下的描述。

sec: id | byte_count | vec<byte>
byte_count: leb(u32)               #LEB128编码的32位无符号整数

上面我们已经简要地介绍了 WebAssembly 的内置类型及段结构描述，接下来，我们将逐一实现各个段的二进制数据编码，将它们转换为运行环境中的对象"内存格式"数据结构。

类型段 (ID = 1)

类型段记录了模块中使用到的所有函数类型，函数类型包括参数数量和类型，以及返回值数量和类型。在 WebAssembly 二进制格式里，函数类型以 0x60 开头，后跟参数数量、参数类型、返回值数量和返回值类型，函数类型的二进制编码格式如下所示。

type_section : id   | byte_count    | vector<func_type>
func_type    : 0x60 | vec<val_type> | vec<val_type>

针对类型段及函数类型编码，我们定义如下的数据结构；其中 FuncSig 表示函数类型签名，其中 params 描述函数的参数数量和类型，result 描述返回值数量和类型。

const typesInModule: Array<TypeInstruction>

type TypeInstruction = {
  type: "TypeInstruction";
  id: Index;
  functype: FuncSig;
};

type FuncSig = {
  params: Array<FuncParam>,
  result: Array<Valtype>,
};

type FuncParam = {
  id ?: string,
  valtype: Valtype,
};

基于类型段和函数类型的定义，WAInterp 定义 parseTypeSection 函数实现类型段的二进制解析；其中，typesInModule 为模块中函数类型集合。

function parseTypeSection(numberOfTypes: number) {
  const typesInModule: Array<TypeInstruction> = [];
  for (let i = 0; i < numberOfTypes; i++) {
    // 0x60
    const type = readByte();
    skipBytes(1);

    if (type == constants.types.func) {
      const paramValtypes: Array<Valtype> = parseVec(
        (b) => constants.valtypes[b]
      );
      const params = paramValtypes.map((v) =>
        t.funcParam(/*Valtype*/ v, undefined)
      );
      const result: Array<Valtype> = parseVec((b) => constants.valtypes[b]);
      typesInModule.push(
        t.typeInstruction(undefined, t.signature(params, result)),
      );
    } else {
      throw new Error("Unsupported type: " + toHex(type));
    }
  }
  return typesInModule;
}

导入段 (ID = 2)

一个模块可以导入函数、表、内存、全局变量 4 种类型的外部对象；这些导入对象通过模块名、成员名，以及具体描述信息在模块的导入段进行声明，导入段的二进制编码格式如下所示。

import_sec : 0x02        | byte_count  | vec<import>
import     : module_name | member_name | import_desc
import_desc: tag | [type_idx, table_type, mem_type, global_type]

针对导入段及导入项的结构，我们定义如下的数据结构；其中 ModuleImport 为导入项，module 和 name 分别表示导入的模块名和符号名；ImportDescr 用于表示实际导入的函数、表、内存、全局变量的详细信息。为了表示 4 种不同的导入项， ImportDescr 数据类型为 GlobalType，Table，Memory，FuncImportDescr 的组合类型；其中 GlobalType 用于描述全局变量类型信息；Table 用于描述表类型信息，元素类型可以为 funcref 和 externref；Memory 用于描述内存类型信息；FuncImportDescr 用户描述导入的外部函数签名信息，如下代码所示。

const importsInModule: Array<ModuleImport>

type ModuleImport = {
  type: "ModuleImport";
  module: string;
  name: string;
  descr: ImportDescr;
};

type ImportDescr = GlobalType | Table | Memory | FuncImportDescr;

type GlobalType = {
  type: "GlobalType";
  valtype: Valtype;
  mutability: Mutability;
};

type Table = {
  type: "Table";
  elementType: TableElementType;
  limits: Limit;
  name?: Identifier;
  elements?: Array<Index>;
};
type TableElementType = "funcref" | "externref"

type Memory = {
  type: "Memory";
  limits: Limit;
  id?: Index;
};

type FuncImportDescr = {
  type: "FuncImportDescr";
  id: Identifier;
  signature: Signature;
};

基于导入段二进制格式和数据结构定义，WAInterp 定义 parseImportSection 函数实现导入段的二进制解析，其中， importsInModule 为模块中的导入项集合。

function parseImportSection(numberOfImports: number) {
  const importsInModule: Array<ModuleImport> = [];
  for (let i = 0; i < numberOfImports; i++) {
    const moduleName = readUTF8String();
    skipBytes(moduleName.nextIndex);

    const name = readUTF8String();
    skipBytes(name.nextIndex);

    const descrTypeTag = readByte(); // import kind
    skipBytes(1);

    let importDescr : ImportDescr;
    const descrType = constants.importTypes[descrTypeTag];
    if (descrType === "func") {
      const indexU32 = readU32();
      const typeindex = indexU32.value;
      skipBytes(indexU32.nextIndex);
      const signature = state.typesInModule[typeindex];
      const id = getUniqueName("func");
      importDescr = t.funcImportDescr(
        t.identifier(id),
        t.signature(signature.params, signature.result),
        true
      );
    } else if (descrType === "global") {
      importDescr = parseGlobalType();
    } else if (descrType === "table") {
      importDescr = parseTableType(i);
    } else if (descrType === "memory") {
      const importDescr = parseMemoryType(0);
    } else {
      throw new CompileError("Unsupported import of type: " + descrType);
    }
    importsInModule.push(
      t.moduleImport(moduleName.value, name.value, importDescr),
    );
  }
  return importsInModule;
}

函数段 (ID = 3)

函数段相对比较简单，它列出了内部函数的签名在类型段中的索引，函数段的编码格式如下所示。

func_sec: 0x03 | byte_count | vec<type_idx>

函数段实际声明了模块内部定义的函数类型，我们定义如下的数据结构来表示模块中的函数类型。

type FuncType = {
  id: Identifier,
  signature: Signature,
  isExternal: boolean,
};

type FuncSig = {
  params: Array<FuncParam>,
  result: Array<Valtype>,
};

基于函数段的二进制格式及数据结构，WAInterp 定义 parseFuncSection 函数实现导入段的二进制解析；其中， functionsInModule 为模块中函数集合。

function parseFuncSection(numberOfFunctions: number) {
  let functionsInModule: Array<DecodedModuleFunc> = [];
  for (let i = 0; i < numberOfFunctions; i++) {
    const indexU32 = readU32();  // type index
    const typeindex = indexU32.value;
    skipBytes(indexU32.nextIndex);

    const signature = state.typesInModule[typeindex];
    const id = t.withRaw(t.identifier(getUniqueName("func")), "") as Identifier;

    functionsInModule.push({
      id,
      signature,
      isExternal: false,
    });
    return functionsInModule;
  }
}

Table段 (ID = 4)

WebAssembly MVP 规定了一个模块最多只能定义一张表，且元素类型必须为函数引用。除了元素类型，表类型还需要指定元素数量的限制，包括元素数量的最小值和最大值；由于元素数量的最大值是可选域，因此二进制编码中通过 tag 域来识别，如果 tag 是0，表示只指定下限；否则，tag 必须为1，表示既指定下限，又指定上限。Table 段的二进制编码格式如下所示。

table_sec : 0x04 | byte_count | vec<table_type> # MVP vec长度只能是1
table_type: 0x70 | limits
limits    : tag  | min | max?

针对 Table 段的编码，我们定义如下的数据结构，其中 TableElementType 描述表中元素类型，当前只能为 funcref；Limit 用于描述表元素大小的限制。

const tablesInModule: Array<Table>

type Table = {
  type: "Table";
  elementType: TableElementType;
  limits: Limit;
  name?: Identifier;
  elements?: Array<Index>;
};

type TableElementType = "funcref" | "externref"

type Limit = {
  type: "Limit";
  min: number;
  max?: number;
};

基于表段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现表段的二进制解析；其中，tablesInModule 为模块中表的集合。

function parseTableSection(numberOfElements: number) {
  const tablesInModule: Array<Table> = [];
  for (let i = 0; i < numberOfElements; i++) {
    const tablesDescr: Table = parseTableType(i);
    tablesInModule.push(tablesDescr);
  }
  return tablesInModule;
}

内存段 (ID = 5)

和 Table 一样，WebAssembly MVP 规定一个模块最多只能定义一块内存；与 Table 不同的是内存类型只须指定内存页数限制，而不需要指定类型。内存段和内存类型的二进制编码格式如下所示。

mem_sec : 0x05 | byte_count | vec<mem_type> # MVP vec长度只能是1
mem_type: limits

针对内存段和内存类型编码，我们定义如下的数据结构，其中 Limits 用于描述指定内存页数限制。

const memoriesInModule: Array<Memory>

type Memory = {
  type: "Memory";
  limits: Limit;
  id?: Index;
};

type Limit = {
  type: "Limit";
  min: number;
  max?: number;
};

基于内存段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现内存段的二进制解析；其中，memoriesInModule 为模块中的内存集合。

function parseMemorySection(numberOfElements: number) {
  const memoriesInModule: Array<Memory> = [];
  for (let i = 0; i < numberOfElements; i++) {
    const memoryDescr: Memory = parseMemoryType(i);
    state.memoriesInModule.push(memoryDescr);
    memories.push(memoryDescr);
  }
  return memoriesInModule;
}

全局段 (ID = 6)

全局段列出模块内定义的所有全局变量，全局项需要指定全局变量类型和初始值；其中，全局变量类型需要描述全局变量的类型以及可变性。全局段和全局变量的二进制编码格式如下所示。

global_sec : 0x06        | byte_count | vec<global>
global     : global_type | init_expr
global_type: val_type    | mut
init_expr  : vec<byte>   | 0x0B

针对全局段和全局变量类型编码，我们定义如下的数据结构，其中 GlobalType 描述全局变量类型及其可变性；init 是初始化表达式，用指令序列 Array<Instruction> 来表示。

const globalsInModule: Array<Global>;

type Global = {
  type: "Global";
  globalType: GlobalType;
  init: Array<Instruction>;
  name?: Identifier;
};

type GlobalType = {
  type: "GlobalType";
  valtype: Valtype;
  mutability: Mutability;
};
type Valtype = "i32" | "i64" | "f32" | "f64";
type Mutability = "const" | "var";

基于全局段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现全局段的二进制解析；其中，globalsInModule 为模块中全局变量集合。

function parseGlobalSection(numberOfGlobals: number) {
  const globalsInModule: Array<Global> = [];
  for (let i = 0; i < numberOfGlobals; i++) {
    const globalType = parseGlobalType();
    const init: Array<Instruction> = [];
    parseInstructionBlock(init);
    const globalDescr: Global = t.global(globalType, init, undefined);
    globalsInModule.push(globalDescr);
  }
  return globalsInModule;
}

导出段 (ID = 7)

导出段列出模块所有导出成员，只有被导出的成员才能被外界访问，其他成员被很好地“封装”在模块内部。与模块导入类似，一个模块也可以导出 "函数"、"表"、"内存"、 "全局变量" 4 种类型的成员；导出项除了指定导出的符号名，还需要指定实际导出的元素内容，而元素的内容仅指定对应索引空间中成员索引即可，因为通过索引即可从对应的索引空间中获取需要的数据。
导出段及其导出项二进制编码格式如下所示。

export_sec : 0x07 | byte_count | vec<export>
export     : name | export_desc       
export_desc: tag  | [func_idx, table_idx, mem_idx, global_idx]

针对导出段编码，我们定义如下的数据结构，其中 name 为导出的符号名，ModuleExportDescr 用于描述导出的类型以及导出项在各自所以空间中的索引值。

const exportsInModule: Array<ModuleExport>

type ModuleExport = {
  type: "ModuleExport";
  name: string;
  descr: ModuleExportDescr;
};

type ModuleExportDescr = {
  type: "ModuleExportDescr";
  exportType: ExportDescrType;
  id: Index;
};
type ExportDescrType = "Func" | "Table" | "Memory" | "Global";

基于导出段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现全局段的二进制解析；其中，exportsInModule 为导出对象集合。

function parseExportSection(numberOfExport: number) {
  const exportsInModule: Array<ModuleExport>;
  for (let i = 0; i < numberOfExport; i++) {
    const name = readUTF8String(); // export name
    skipBytes(name.nextIndex);
    const typeIndex = readByte(); // export kind
    skipBytes(1);
    const indexu32 = readU32(); // export index
    const index = indexu32.value;
    skipBytes(indexu32.nextIndex);

    let id: Index;
    let signature = undefined;
    if (constants.exportTypes[typeIndex] === "Func") {
      const func = state.functionsInModule[index];
      id = t.numberLiteralFromRaw(index, String(index) as any) as NumberLiteral;
      signature = func.signature;
    } else if (constants.exportTypes[typeIndex] === "Table") {
      const table = state.tablesInModule[index];
      id = t.numberLiteralFromRaw(index, String(index) as any) as NumberLiteral;
    } else if (constants.exportTypes[typeIndex] === "Memory") {
      const memory = state.memoriesInModule[index];
      id = t.numberLiteralFromRaw(index, String(index) as any) as NumberLiteral;
    } else if (constants.exportTypes[typeIndex] === "Global") {
      const global = state.globalsInModule[index];
      id = t.numberLiteralFromRaw(index, String(index) as any) as NumberLiteral;
    } else {
      console.warn("Unsupported export type: " + toHex(typeIndex));
      return;
    }
    exportsInModule.push(
      t.moduleExport(
         name.value,
         t.moduleExportDescr(
           constants.exportTypes[typeIndex],
           t.numberLiteral(typeIndex, String(typeIndex)
         )
      )
    );
  }
}

起始段 (ID = 8)

起始段只需要记录一个起始函数索引，该函数是一个可选的模块入口函数，类似于高级编程语言中的 "main" 函数；起始段二进制编码格式如下所示。

start_sec: 0x08 | func_idx

针对起始段编码，我们定义如下的数据结构，其中 index 为函数名字空间的索引值。

type Start = {
  type: "Start";
  index: Index;
};

基于起始段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现全局段的二进制解析。

function parseStartSection() : Start {
  const u32 = readU32(); // start func index
  const startFuncIndex = u32.value;
  skipBytes(u32.nextIndex);
  return t.start(t.indexLiteral(startFuncIndex));
}

export function start(index: Index): Start {
  const node: Start = {
    type: "Start",
    index,
  };
  return node;
}

元素段 (ID = 9)

元素段存放 Table 的初始化数据，每个元素项由表索引、表内偏移量、函数索引列表三部分组成；其中，表索引用于指定初始化哪张表，表内偏移量用于指定初始元素填充的起始偏移，函数索引列表指定了用于初始化 Table 的函数索引值。和全局变量初始值类似，表内偏移量也用初始化表达式指定；元素段二进制编码格式如下所示。

elem_sec   : 0x09      | byte_count  | vec<elem>
elem       : table_idx | offset_expr | vec<func_idx>
offset_expr: vec<byte> | 0x0B

针对元素段编码格式，我们定义如下的数据结构；其中，offset 为初始化表达式描述的表初始化偏移量，funcs 为函数索引列表。

const elemsInModule: Array<Elem>;

type Elem = {
  type: "Elem";
  table: Index;  // table index
  offset: Array<Instruction>; // offset in table
  funcs: Array<Index>; // func indice
};

基于元素段的二进制格式和数据结构定义，WAInterp 定义 parseElemSection 函数实现元素段的二进制解析。

function parseElemSection(numberOfElements: number) {
  const elemsInTable: Array<Elem> = [];
  for (let i = 0; i < numberOfElements; i++) {
    const tableindexu32 = readU32();  // table index
    const tableindex = tableindexu32.value;
    skipBytes(tableindexu32.nextIndex);
 
    const instr: Array<Instruction> = [];
    parseInstructionBlock(instr); // offset expression

    const indicesu32 = readU32();  // func index number
    const indices = indicesu32.value;
    skipBytes(indicesu32.nextIndex);

    const indexValues : Arrany<Index> = [];
    for (let i = 0; i < indices; i++) {
      const indexu32 = readU32();
      const index = indexu32.value;
      skipBytes(indexu32.nextIndex);
      indexValues.push(t.indexLiteral(index));
    }
    const elemNode = t.elem(t.indexLiteral(tableindex), instr, indexValues);
    elemsInTable.push(elemNode);
  }
  return elemsInTable;
}

代码段 (ID = 10)

代码段描述了函数的局部变量信息和函数的指令序列，而函数的类型和索引信息在类型段和函数段中定义。和其它段相比，代码段中每个项都以所占字节数开头，虽然有所冗余，但方便 WebAssembly 实现验证、分析、编译的并行处理；此外，为了节约空间，连续多个相同类型的局部变量会被分为一组，统一记录变量数量和类型，从而实现局部变量信息的压缩存储；代码段二进制编码格式如下所示。

code_sec: 0x0A        | byte_count  | vec<code>
code    : byte_count  | vec<locals> | expr
locals  : local_count | val_type

针对代码段的编码格式，我们定义如下的数据结构，其中 code 为函数体的指令序列，locals 为局部变量列表。

const funcBodiesInModule : Array<FuncBody>；

type FuncBody = {
  code: Array<Instruction>,
  locals: Array<Valtype>,
  bodySize: number,
}

基于代码段的二进制格式和数据结构定义，WAInterp 定义 parseCodeSection 函数实现元素段的二进制解析，其中 funcBodiesInModule 为模块中的函数体集合。

function parseCodeSection(numberOfFuncs: number) {
  for (let i = 0; i < numberOfFuncs; i++) { // Parse vector of function
    const bodySizeU32 = readU32(); // size of the function code in bytes
    skipBytes(bodySizeU32.nextIndex);

    const code: Array<Instruction> = [];
    const funcLocalNumU32 = readU32();  // local group count
    const funcLocalNum = funcLocalNumU32.value;
    skipBytes(funcLocalNumU32.nextIndex);
    const locals: Array<Instr> = [];
    const localsTypes: Array<Valtype> = [];
    for (let i = 0; i < funcLocalNum; i++) {
      const localCountU32 = readU32(); // local count
      const localCount = localCountU32.value;
      skipBytes(localCountU32.nextIndex);
      const valtypeByte = readByte(); // local value type
      skipBytes(1);
      const type = constants.valtypes[valtypeByte];
      const args: Array<ValtypeLiteral> = [];
      for (let i = 0; i < localCount; i++) {
        args.push(t.valtypeLiteral(type));
        localsTypes.push(type);
      }
      const localNode: Instr = t.instruction("local", args) as Instr;
      locals.push(localNode);
    }
    code.push(...locals);
    parseInstructionBlock(code); // decode instrs until the "end"
    funcBodiesInModule.push({
      code,
      locals: localsTypes,
      bodySize: bodySizeU32.value,
    });
  }
}

数据段 (ID = 11)

数据段用于存放内存的初始化数据；与元素段中的元素项类似，数据项包含内存索引、内存偏移量、初始化数据三部分信息，内存索引用于指定初始化哪块内存，内存偏移量用于指定从哪里开始填充初始化数据，初始化数据为用于初始化内存的字节数组。数据段和数据项的二进制编码格式如下所示。

data_sec: 0x0B    | byte_count  | vec<data>
data    : mem_idx | offset_expr | vec<byte>

针对数据段的编码规范，我们定义如下的数据结构；其中，memoryIndex 描述需要初始化的内存块；offset 描述内存中的数据区域的起始偏移量；initData 指定内存区域的初始化数据。

const dataInModule: Array<Data>;

type Data = {
  type: "Data";
  memoryIndex: Memidx;
  offset: Array<Instruction>;
  initData: Array<Byte>;
};

基于数据段的二进制格式和数据结构定义，WAInterp 定义 parseDataSection 函数实现元素段的二进制解析。

function parseDataSection(numberOfElements: number) {
  const dataInModule: Array<Data> = [];
  for (let i = 0; i < numberOfElements; i++) {
    const memoryIndexu32 = readU32();  // memory index
    const memoryIndex = memoryIndexu32.value;
    skipBytes(memoryIndexu32.nextIndex);
    const instrs: Array<Instruction> = [];  // offset expr
    parseInstructionBlock(instrs);
    const bytes: Array<Byte> = parseVec((b) => b); // init data
    dataInModule.push(
      t.data(t.memIndexLiteral(memoryIndex), instrs, t.byteArray(bytes))
    );
  }
  return dataInModule;
}

自定义段 (ID = 0)

自定义段用于存放自定义功能数据，当前阶段主要用于保存调试符号信息。自定义段与其他段有如下两方面的差异，首先，自定义段不参与模块语义，自定义段存放的都是额外信息 (比如，函数名和局部变量名等调试信息，第三方扩展信息等)，即使完全忽略这些信息也不影响模块的执行；其次，自定义段可以出现在任何一个非自定义段前后，而且出现的次数不受限制。由于自定义段为定制化的需求服务，所以对于 WebAssembly 规范来说它的数据是非结构化的，即，对于自定义段中字节数组的结构化解析由对应的自定义功能模块负责。
自定义段二进制编码格式如下所示。

custom_sec: 0x00 | byte_count | name | vec<byte>

针对自定义段的编码规范，我们定义如下的数据结构来表示；其中，Bytes 用于保存原始的字节数据，提供给自定义功能解析和使用。

type CustomSec = {
    Name  : string
    Bytes : Array<Byte>
}

WAInterp 暂不考虑实现自定义段功能，因此，后续不再展开讨论自定义段，相关功能和详细的规范请参阅WebAssembly 核心规范[8]。

3.3 WAInterp 模块解码

在上一小节中，我们对模块中各个段的二进制编码格式做了详细分析，并为各段定义了对应的数据结构和解析函数。基于各段的解析函数和数据结构，WAInterp 定义 decode 函数来实现模块的二进制格式解析并转换为运行时环境中的对象实例；在 decode 函数中的，参数 buffer 是原始的模块二进制字节数组，返回值 Program 是解码后的运行时对象表示。解码的主要过程分为三个部分，第一部分是模块的文件头解析，包括模数和版本号；第二部分是各个段的解析及各个索引空间的创建；第三部分是运行时对象实例 Program 的创建和初始化。

type Program = {
  type: "Program";
  body: Array<Module>;
};
export function decode(buffer: ArrayBuffer, opts: DecoderOpts): Program

魔数和版本号

WebAssembly 模块二进制格式中魔数占 4 个字节，内容是\0asm；版本号也占 4 个字节，当前版本是 1。decode 函数中如下部分代码展示了魔数和版本号解码和校验过程，其中，解码失败后会直接抛出异常。

export function decode(buffer: ArrayBuffer, opts: DecoderOpts): Program {
  const buf : Uint8Array = new Uint8Array(buffer);
  // skip irrelevant code ...
  parseModuleHeader();
  parseVersion();
  // skip irrelevant code ...
}

const magicModuleHeader = [0x00, 0x61, 0x73, 0x6d]; //`\0asm`
const moduleVersion = [0x01, 0x00, 0x00, 0x00]; // 1

function parseModuleHeader() {
  const header = readBytes(4);
  skipBytes(4);
  
  if (byteArrayEq(constants.magicModuleHeader, header) === false) {
    throw new CompileError("magic header not detected");
  }
}

function parseVersion() {
  const version = readBytes(4);
  skipBytes(4);
  
  if (byteArrayEq(constants.moduleVersion, version) === false) {
    throw new CompileError("unknown binary version");
  }
}

段解析

段解码是整个模块解码的核心，为了统一表示各个段的数据类型，定义 Node 作为各段类型的组合类型来统一表示；其中，Module 表示解码后的模块对象类型，fields 用于记录模块解码后各个段的实例对象，SectionMetadata 用于记录各个段的元信息，其他各个段的类型定义如上各个小节所述。

type Node =
  | Module
  | SectionMetadata
  | TypeInstruction
  | ModuleImport
  | Func
  | Global
  | Table
  | Memory
  | Elem
  | Data
  | ModuleExport
  | Start

type Module = {
  type: "Module";
  id?: string;
  fields: Array<Node>;
  sectionMetas: Array<SectionMetadata>;
};

type SectionMetadata = {
  type: "SectionMetadata";
  section: SectionName;
  startOffset: number;
  size: number;
};

decode 函数中对各个段的解析实现，如下代码片段所示。

export function decode(ab: ArrayBuffer, opts: DecoderOpts): Program {
  const buf = new Uint8Array(ab);
  // skip irrelevant code ...
  let offset : number = 0;
  let sectionIndex : number = 0;
  const moduleFields : Array<Node> = [];
  while (offset < buf.length) {
    const { nodes, metadata, nextSectionIndex } = parseSection(sectionIndex);
    moduleFields.push(...nodes);
    if (nextSectionIndex) { // ignore custom section
      sectionIndex = nextSectionIndex;
    }
  }
  // skip irrelevant code ...
}

WAInterp 定义 parseSection 函数来组合各个段的解析函数，完成模块各段的二进制解析。

function parseSection(sectionIndex: number): {
  nodes: Array<Node>;
  metadata: SectionMetadata | Array<SectionMetadata>;
  nextSectionIndex: number;
} {
  // skip non-cricital code ...
  const sectionId = readByte();  // section id
  skipBytes(1);
  sectionIndex = sectionId + 1;
  const nextSectionIndex = sectionIndex;
  const u32 = readU32();  // section size
  const sectionSizeInBytes = u32.value;
  skipBytes(u32.nextIndex);
  switch (sectionId) {
    case constants.sections.type: {
      // skip non-cricital code ...
      const u32 = readU32();
      const numberOfTypes = u32.value;
      skipBytes(u32.nextIndex);
      const metadata = t.sectionMetadata("type", ...);
      const nodes = parseTypeSection(numberOfTypes);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.table: {
      // skip non-cricital code ...
      const u32 = readU32();
      const numberOfTable = u32.value;
      skipBytes(u32.nextIndex);
      const metadata = t.sectionMetadata("table", ...);
      const nodes = parseTableSection(numberOfTable);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.import: {
      // skip non-cricital code ...
      const numberOfImportsu32 = readU32();
      const numberOfImports = numberOfImportsu32.value;
      skipBytes(numberOfImportsu32.nextIndex);
      const metadata = t.sectionMetadata("import", ...);
      const nodes = parseImportSection(numberOfImports);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.func: {
      // skip non-cricital code ...
      const numberOfFunctionsu32 = readU32();
      const numberOfFunctions = numberOfFunctionsu32.value;
      skipBytes(numberOfFunctionsu32.nextIndex);
      const metadata = t.sectionMetadata("func", ...);
      const ndoes = parseFuncSection(numberOfFunctions);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.export: {
      // skip non-cricital code ...
      const u32 = readU32();
      const numberOfExport = u32.value;
      skipBytes(u32.nextIndex);
      const metadata = t.sectionMetadata("export", ...);
      const nodes = parseExportSection(numberOfExport);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.code: {
     // skip non-cricital code ...
      const u32 = readU32();
      const numberOfFuncs = u32.value;
      skipBytes(u32.nextIndex);
      const metadata = t.sectionMetadata("code", ...);
      const nodes = parseCodeSection(numberOfFuncs)
      return { nodes, metadata, nextSectionIndex };
    
    case constants.sections.start: {
      // skip non-cricital code ...
      const metadata = t.sectionMetadata("start", ...);
      const nodes = [parseStartSection()];
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.element: {
      // skip non-cricital code ...
      const numberOfElementsu32 = readU32();
      const numberOfElements = numberOfElementsu32.value;
      skipBytes(numberOfElementsu32.nextIndex);
      const metadata = t.sectionMetadata("element", ...)
      const nodes = parseElemSection(numberOfElements);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.global: {
      // skip non-cricital code ...
      const numberOfGlobalsu32 = readU32();
      const numberOfGlobals = numberOfGlobalsu32.value;
      skipBytes(numberOfGlobalsu32.nextIndex);
      const metadata = t.sectionMetadata("global", ...);
      const nodes = parseGlobalSection(numberOfGlobals);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.memory: {
      // skip non-cricital code ...
      const numberOfElementsu32 = readU32();
      const numberOfElements = numberOfElementsu32.value;
      skipBytes(numberOfElementsu32.nextIndex);
      const metadata = t.sectionMetadata("memory", ...);
      const nodes = parseMemorySection(numberOfElements);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.data: {
      // skip non-cricital code ...
      const numberOfElementsu32 = readU32();
      const numberOfElements = numberOfElementsu32.value;
      skipBytes(numberOfElementsu32.nextIndex);
      const metadata = t.sectionMetadata("data", ...);    
      const nodes = parseDataSection(numberOfElements);
      return { nodes, metadata, nextSectionIndex };
    }
    case constants.sections.custom: {
      skipBytes(sectionSizeInBytes);  // ignore cusom section
      return { nodes: [], metadata, nextSectionIndex };
    }
  }

Program 构造

上述过程已基本完了模块解码工作，最后 WAInterp 通过 module 和 program 函数来完成运行环境中 Module 和 Program 对象构造，如下代码所示。

type Program = {
  type: "Program";
  body: Array<Module>;
};

type Module = {
  type: "Module";
  id?: string;
  fields: Array<Node>;
  metadata?: ModuleMetadata;
}
export function decode(ab: ArrayBuffer, opts: DecoderOpts): Program 
  // skip irrelevant code ...
  const moduleFields : Array<Node> = [];
  // skip irrelevant code ...
  const module = t.module(..., moduleFields, ...);
  return t.program([module]);
}
export function module(id: string, fields: Array<Node>, ...): Module {
  // skip irrelevant code ...
  const node: Module = {
    type: "Module",
    id,
    fields,
  };
  return node;
}
export function program(body: Array<Module>): Program {
  // skip non-cricital code ...
  const node: Program = {
    type: "Program",
    body,
  };
  return node;
}

至此，我们已经完成了 WAInterp 的解码器的全部内容，接下来，我们基于解码后的 program 对象来完成模块的实例化工作。

4. WAInterp 实例化

WebAssembly 模块的实例化过程包括创建模块实例空间，实例构造并初始化索引空间，执行起始函数三个阶段。在本节中，我们将分别从这三个阶段来描述是和实现 WAInterp 实例化。

4.1 创建实例空间

实例空间是可以由 WebAssembly 程序操作的所有全局状态，它由实例化过程中分配的函数、表、内存和全局变量等所有实例的运行时表示组成；WAInterp 定义 Store 数据结构来表示实例空间。从语义上讲，Store 被定义为模块中各种类型实例的记录 _store 以及访问记录的各方法。

export const NULL = 0x0;
type InstType = FuncInstance | GlobalInstance | TableInstance | MemoryInstance | NULL

interface Store {
  _store: Array<InstType>;
  malloc(Bytes): Addr;
  get(Addr): InstType;
  set(Addr, InstType): void;
  free(Addr): void;
}

基于 Store 的类型定义，WAInterp 定义 createStore 函数来创建实例空间；其中，_store 用于保存各种全局状态的记录；malloc，free，get，set 为实例空间操作和管理全局状态的方法。

export function createStore(): Store {
  const _store: Array<InstType> = [];
  let index : number = 0;
  // malloc memory and return memory address
  function malloc(size: number): Addr {
    index += size;
    return {
      index,
      size,
    };
  }
  // get the instance of InstType from memory address p
  function get(p: Addr): InstType {
    return _store[p.index];
  }
  // set the instance of InstType into memory address p
  function set(p: Addr, value: InstType) {
    _store[p.index] = value;
  }
  // free the memory with memory address p
  function free(p: Addr) {
    _store[p.index] = NULL;
  }
  return {
    _store,
    malloc,
    free,
    get,
    set,
  };
}

4.2 模块实例化

当 WAInterp 完成实例空间创建后，运行时环境需要为模块中各种全局类型对象创建实例，并完成索引空间初始化，包括函数索引空间，表索引空间，内存索引空间，全局变量索引空间以及导出符号索引空间。WAInterp 定义 ModuleInstance 用于表示模块实例的数据结构；其中，Addr 表示实例对象在 Store 中的地址偏移量；funcaddrs 为函数索引表，用于表示函数实例在 Store 中的内存地址；tableaddrs 为表索引表，用于表示表实例在 Store 中的内存地址；memaddrs 为内存索引表，用于表示内存实例在 Store 中的内存地址；globaladdrs 为全局变量索引表，用于表示全局变量实例在 Store 中的内存地址；exports 为导出对象索引表，用于表示导出实例在 Store 中的内存地址。

type Addr = {
  index: number,
  size: number,
};

interface ExternalVal {
  type: string;
  addr: Addr;
}

type ExportInstance = {
  name: string,
  value: ExternalVal,
};

type ModuleInstance = {
  funcaddrs: Array<FuncAddr>,
  tableaddrs: Array<TableAddr>,
  memaddrs: Array<MemAddr>,
  globaladdrs: Array<GlobalAddr>,
  exports: Array<ExportInstance>,
};

基于模块实例和索引空间的数据结构，WAInterp 定义 createInstance 函数来完成对象实例化以及索引空间的初始化；其中，funcTable 为模块中定义的函数对象，包括函数名，函数体指令序列；store 为模块运行时的实例空间，用于实际存储模块全局对象实例；module 为解码后模块的内存数据结构表示；externalElements 为实例化过程中指定的外部导入对象实例，当前只支持了函数实例的导入，如下代码所示。

type IRFunc = {
  name: string,
  startAt: number,
  instructions?: Array<IRNode>;
};
export function createInstance(
  funcTable: Array<IRFunc>,
  store: Store,
  module: Module,
  externalElements: any = {}
): ModuleInstance {
  const moduleInstance: ModuleInstance = { ... };
  // skip non-cricital code ...
  instantiateImports(module, store, externalElements, ..., moduleInstance);
  instantiateInternals(funcTable, module, store, ..., moduleInstance);
  instantiateDataSections(module, store, moduleInstance);
  instantiateExports(module, store, ..., moduleInstance);
  return moduleInstance;
}

根据不同的对象类型，WAInterp 定义了不同的实例化过程，接下来，我们分别进行详细的阐述。

导入对象实例化

一个模块可以导入函数、表、内存、全局变量这四种类型的外部符号，这些外部导入的符号需要在模块实例化过程中完成符号解析和和链接过程，如下图 3 所示；模块链接原理和过程请阅读课程的如下两篇文章 WebAssembly 模块化与动态链接和 WebAssembly工作原理浅析，文中对动态链接的的设计、原理和实现有详细的介绍和示例。

图 3. 实例化导入成员链接示意图

基于链接过程和导入对象数据结构定义，WAInterp 定义 instantiateImports 函数来完成实例化导入对象和链接过程；其中，module 为解码后模块的内存数据结构表示；store 为模块运行时的实例空间，用于实际存储模块导入对象实例；externalElements 为导入符号所在的外部模块实例对象。instantiateImports 函数通过 traverse 函数遍历查找模块中 ModuleImport 类型的对象，并针对不同的导入类型采用不同的处理函数进行处理，如下代码所示。

function instantiateImports(
  module: Module,
  store: Store,
  externalElements: Object,
  moduleInstance: ModuleInstance
) : void {
  function getExternalElementOrThrow(key: string, key2: string): any {
    // skip non-cricital code ...
    return externalElements[key][key2];
  }
  // skip non-cricital code ...
  traverse(module, {
    ModuleImport({ node }: NodePath<ModuleImport>) {
      const node_desc_type = node.descr.type;
      switch (node.descr.type) {
        case "FuncImportDescr":
          return handleFuncImport(node, node.descr);
        case "GlobalType":
          return handleGlobalImport(node, node.descr);
        case "Memory":
          return handleMemoryImport(node);
        case "Table":
          return handleTableImport(node);
        default:
          throw new Error("Unsupported import of type: " + node_desc_type);
      }
    },
  });
}

instantiateImports 函数为了处理不同的导入类型定义了不同的处理函数；其中，handleFuncImport 函数用于在 Store 中创建导入的函数对象，并在模块实例的函数索引空间 funcaddrs 中保存函数对象在 Store 中的地址，如下代码所示。

function handleFuncImport(node: ModuleImport, descr: FuncImportDescr) {
  const element = getExternalElementOrThrow(node.module, node.name);
  const params = descr.signature.params != null ? descr.signature.params : [];
  const results =
    descr.signature.results != null ? descr.signature.results : [];
  const func_params: Array<Valtype> = [];
  params.forEach((p:FuncParam) => func_params.push(p.valtype));
  const externFuncinstance : FuncInstance =createFuncInstance(
      element, func_params, results);

  const externFuncinstanceAddr : Addr = store.malloc(1);
  store.set(externFuncinstanceAddr, externFuncinstance);
  moduleInstance.funcaddrs.push(externFuncinstanceAddr);
}
export function createFuncInstance(
  func: Function,
  params: Array<Valtype>,
  results: Array<Valtype>
): FuncInstance {
  const type: Functype = [params, results];
  return {
    type,
    code: func,
    module: undefined,
    isExternal: true,
  };
}

handleGlobalImport 函数用于在 Store 中创建导入的全局变量对象，并在模块实例的全局变量索引空间 globaladdrs 中保存全局变量对象在 Store 中的地址；其中 i32 是 NumericOperations 子类型，用于封装 32 位整数及其操作函数，如下代码所示。

interface NumericOperations<T> {
  add(operand: T): T;
  sub(operand: T): T;
  mul(operand: T): T;
  div(operand: T): T;
  // skip non-cricital code ...
}
function handleGlobalImport(node: ModuleImport, descr: GlobalType) {
  const element = getExternalElementOrThrow(node.module, node.name);
  const externglobalinstance : GlobalInstance = createGlobalInstance(
    new i32(element),
    descr.valtype,
    descr.mutability
  );
  const addr = store.malloc(1);
  store.set(addr, externglobalinstance);
  moduleInstance.globaladdrs.push(addr);
}
export function createGlobalInstance(
  value: NumericOperations<any>,
  type: Valtype,
  mutability: Mutability
): GlobalInstance {
  return {
    type,
    mutability,
    value,
  };
}

与其他导入类型处理函数相似，handleMemoryImport 和 handleTableImport 分别在 Store 中创建各自的实例对象，并在模块实例的对应的索引空间中保存对象在 Store 中的地址，如下代码所示。

function handleMemoryImport(node: ModuleImport) {
  const memoryinstance = getExternalElementOrThrow(node.module, node.name);
  const addr = store.malloc(1);
  store.set(addr, memoryinstance);
  moduleInstance.memaddrs.push(addr);
}
function handleTableImport(node: ModuleImport) {
  const tableinstance = getExternalElementOrThrow(node.module, node.name);
  const addr = store.malloc(1);
  store.set(addr, tableinstance);
  moduleInstance.tableaddrs.push(addr);
}

模块内部对象实例化

除了导入对象，模块会各自定义内部函数、表、内存、全局变量。在完成导入对象初始化后，我们需要为模块中自定义的各类对象实例化，并初始化对应类型的索引空间；与导入类型对象相似，内部对象实例化主要在 Store 中创建各自的实例对象，并在模块实例的对应的索引空间中保存对象在 Store 中的地址，如下代码所示。

function instantiateInternals(
  funcTable: Array<IRFunc>,
  n: Module,
  store: Store,
  internals: Object,
  moduleInstance: ModuleInstance
) {
  let funcIndex = 0;
  traverse(n, {
    Func({ node }: NodePath<Func>) {
      // skip non-cricital code ...
      const atOffset = funcTable[funcIndex].startAt;
      const funcinstance : FuncInstance = func.createInstance(atOffset, node, moduleInstance);
      const addr = store.malloc(1);
      store.set(addr, funcinstance);
      moduleInstance.funcaddrs.push(addr);
      funcIndex++;
    },
    Table({ node }: NodePath<Table>) {
      // skip non-cricital code ...
      const initial = node.limits.min;
      const element = node.elementType;
      const tableinstance : TableInstance = new TableInstance({ initial, element });
      const addr = store.malloc(1);
      store.set(addr, table instance);
      moduleInstance.tableaddrs.push(addr);
    },
    Memory({ node }: NodePath<Memory>) {
      // skip non-cricital code ...
      const { min, max } = node.limits;
      const memoryDescriptor: MemoryDescriptor = {
        initial: min,
      };
      if (typeof max === "number") {
        memoryDescriptor.maximum = max;
      }
      const memoryinstance = new Memory(memoryDescriptor);
      const addr = store.malloc(1);
      store.set(addr, memoryinstance);
      moduleInstance.memaddrs.push(addr);
    },
    Global({ node }: NodePath<Global>) {
      const globalinstance = global.createInstance(store, node);
      const addr = store.malloc(1);
      store.set(addr, globalinstance);
      moduleInstance.globaladdrs.push(addr);
    },
  });
}

内存和表初始化

WebAssembly 模块中的元素段和数据段用于初始化对应的内存和表内容。当完成模块对象实例化后，内存实例和表实例仍处于未初始化状态；WAInterp 定义 instantiateElemSections 和 instantiateDataSections 函数分别初始化表和线性内存空间；instantiateElemSections 遍历元素段中的所有元素项，并将对应的元素填入 Table 中以完成表的初始化过程；和表的初始化类似，instantiateDataSections 根据数据段把初始数据写入指定的内存地址即可，代码如下所示。

function instantiateElemSections(
  n: Module,
  store: Store,
  moduleInstance: ModuleInstance
) {
  traverse(n, {
    Elem({ node }: NodePath<Elem>) {
      // skip non-cricital code ...
      const addr = moduleInstance.tableaddrs[node.table.value];
      let table = store.get(addr);
      const funcs : Array<Index> = node.funcs;
      let offset : number = evalExpression(); // eval init expression
      funcs.forEach((func) => { // write element into table
        table[offset] = moduleInstance.funcaddrs[func.value];
      });
    },
  });
}
function instantiateDataSections(
  n: Module,
  store: Store,
  moduleInstance: ModuleInstance
) {
  traverse(n, {
    Data({ node }: NodePath<Data>) {
      const memIndex = node.memoryIndex.value;
      const memoryAddr = moduleInstance.memaddrs[memIndex];
      const memory = store.get(memoryAddr);
      const buffer = new Uint8Array(memory.buffer);
      let offset = evalExpress(node); // eval init expression
      for (let i = 0; i < node.init.values.length; i++) { // write data into linear memory
        buffer[i + offset] = node.init.values[i];
      }
    },
  });
}

导出对象实例化

对于 WebAssembly 模块而言，所有对象的实例都被"安全"地封装在模块的内部，而只有被导出的对象才能被外界访问；因此，WAInterp 最后通过 instantiateExports 函数来实例化导出对象，从而使模块可以被外部其他模块或者外界环境使用。instantiateExports 函数首先调用 traverse 函数遍历模块中 ModuleExport 类型的对象实例，并根据对象实例的类型分别调用 createModuleExport 函数创建导出实例对象。

function instantiateExports(
  n: Module,
  store: Store,
  internals: Object,
  moduleInstance: ModuleInstance
) {
  // skip non-cricital code ...
  traverse(n, {
    ModuleExport({ node }: NodePath<ModuleExport>) {
      switch (node.descr.exportType) {
        case "Func": {
          createModuleExport(node, ..., moduleInstance.funcaddrs, ...);
          break;
        }
        case "Global": {
          createModuleExport(node, ..., moduleInstance.globaladdrs, ...);
          break;
        }
        case "Table": {
          createModuleExport(node, ..., moduleInstance.tableaddrs, ...);
          break;
        }
        case "Memory": {
          createModuleExport(node, ..., moduleInstance.memaddrs, ...);
          break;
        }
        default: {
          throw new CompileError("unknown export: " + node.descr.exportType);
        }
      }
    }
  });
}

createModuleExport 函数主要负责创建和初始化 ExportInstance 实例；其主要逻辑是利用 ModuleExport 结构保留的导出符号名和对应类型的索引空间中的已实例化对象创建 ExportInstance 实例，并保存至模块实例 moduleInstance 的 exports 对象中提供给外部模块使用，代码如下所示。

type ExportInstance = {
  name: string,
  value: ExternalVal,
};
function createModuleExport(
  node: ModuleExport,
  instancesArray : Array<Addr>,
): void  {
  // skip non-cricital code ...
  const instantiatedItem = { instanceArray[node.descr.id.value] };
  moduleInstance.exports.push({
    name: node.name,
    value: {
      type: node.descr.exportType,
      addr: instantiatedItem.addr,
    },
  });
  // skip non-cricital code ...
}

至此，模块实例化及索引空间创建和初始化均已完成，WAInterp 实例化的最后步骤是调用起始函数，执行用户自定义的初始化逻辑。

4.3 模块起始函数执行

模块的起始函数是一个可选的模块入口函数，类似于高级编程语言中的 "main" 函数，由 Start 中的 index 属性指定；执行该函数可以完成模块自定义数据的初始化。WAInterp 定义 executeStartFunc 用于执行起始函数，其中，IR 为实例化代码在内存中的表示，offset 为起始函数指令在代码段 program 中的偏移量。

type Start = {
  type: "Start";
  index: Index;
};
type IR = {
  /**
   * name : function name
   * startAt: offset in program
   */
  funcTable: Array<{name: string, startAt: number}>,
  /* .text segment (code segment) */
  program: {
    [offset:number]: Instruction,
  },
};
executeStartFunc(ir: IR, offset: number) {
  const stackFrame = createStackFrame(
    params,
    this._moduleInstance,
    this._store
  );
  // Ignore the result
  executeStackFrameAndGetResult(ir, offset, stackFrame, true /* returnStackLocal */);
}

如上代码所示，实际的 WebAssembly 函数执行首先由 createStackFrame 创建栈帧，然后调用 executeStackFrameAndGetResult 执行具体的字节码并返回执行结果。由于起始函数的执行和普通函数执行并没有差别，因此，本文将不单独介绍其执行流程，而统一在下一节 WAInterp 解释执行中进行说明。

5. WAInterp 解释执行

经过了解码和实例化阶段，WebAssembly 二进制模块已经转换为内存索引空间中的函数、Table、内存(堆)和全局变量实例以及相关辅助信息。函数实例中是一个指令序列，WAInterp 执行流程的主要工作是获取函数的指令序列，并逐一执行指令流中的指令完成每个指令对应的操作。当虚拟机执行的时候，虚拟机维护操作数栈 (Operand stack) 和控制帧栈 (Control stack)，分别存储参数、局部变量、操作数 (values) 和控制结构 (labels)。虚拟机中每个函数调用都会产生一个函数调用帧 (Frame)，用于存储函数的参数、局部变量。WebAssembly 解释器指令执行全景如下图 4 所示，关于 WebAssembly 执行原理请参阅课程的 "WebAssembly 工作原理浅析" 一文。

图 4. WebAssembly 解释器指令执行示意图

和大多数解释型语言类似，WebAssembly 定义自己的一套指令集，按功能可以分为五类，他们分别是控制指令、参数指令、变量指令、内存指令和数值指令。接下来内容，我们将基于 "Switch-Dispatch" 指令分发模式，详细介绍 WebAssembly 指令在 WAInterp 解释器中的实现 (解释器的常见实现方式及结构请阅读参考文献[3])，WAInterp 解释执行代码结构如下所示；其中，program 模块中所有函数代码组成的代码段；offset 为函数的指令序列在代码段中的起始偏移；StackFrame 为函数调用栈帧，其中与函数执行相关的内容将在函数调用小节进行详细介绍。

export function executeStackFrame(
  { program }: IR,
  offset: number,
  firstFrame: StackFrame
): StackLocal {
  const callStack: Array<StackFrame> = [firstFrame];
  let pc  = program[String(offset)]
  // skip non-critical code ...
  while (true) {
    const frame = getActiveStackFrame();
    const instruction: Instruction = program[parseInt(offsets[pc])];
    // skip non-critical code ...
    pc++;
    switch (instruction.id) {
      // Parametric operators
      case "drop": { ... }
      case "select": { ... }
      // Variable access
      case "get_local": { ... }
      case "set_local": { ... }
      case "get_global": { ... }
      case "set_global": { ... }
            ...
      // memory-related operators
      case "store": { ... }
            ...
      case "load": { ... }
            ...
      // Numeric operators
      case "add": { ... }
      case "mul": { ... }
      case "sub": { ... }
            ...
      // Comparison operations
      case "eq":
      case "ne":
            ...
      // Control Instructions
      case "call": { ... }
      case "loop": { ... }
      case "block": { ... }
      case "br": { ... }
      case "br_if": { ... }
      // Administrative Instructions
      case "unreachable": { ... }
      case "trap": { ... }
      case "return": { ... }
  }
}

WAInterp 在 "Switch-Dispatch" 执行模式中展示了解释器的整体框架和常用指令集，接下面我们将分别介绍各类常用指令的语义及执行逻辑。

5.1 参数指令(Parametric Instructions)

参数指令包括 drop 和 select，其中 drop 指令从栈顶弹出一个操作数并把它 "丢弃"；而 select 指令类似于 "? :" 三目运算符，它从栈顶弹出 3 个操作数，然后根据最先弹出的操作数从其他两个操作数中选择一个压栈；下图 5 展示了参数指令的执行逻辑示例。

图 5. 参数指令执行示例

5.2 变量指令(Variable Instructions)

变量指令包括局部变量指令和全局变量指令，其中局部变量指令用于读写函数的参数和局部变量，全局变量指令用于读写模块实例的全局变量；变量指令格式如下所示。

local.get : 0x20 | local_idx
local.set : 0x21 | local_idx
local.tee : 0x22 | local_idx
global.get: 0x23 | global_idx
global.set: 0x24 | global_idx

下面我们介绍这两种变量指令的逻辑及其实现。

局部变量指令
local.get 指令用于获取局部变量的值，也就是把局部变量的值压栈；该指令带有一个立即数，给出局部变量索引；和 local.get 指令相反，local.set 指令用于设置局部变量的值；局部变量的索引由立即数指定，新的值从栈顶弹出；local.tee 指令与 local.set 指令类似，唯一吧不同是在用栈顶操作数设置局部变量后，仍然在栈顶保留了原来操作数的值；下图 6 展示了局部变量指令的执行逻辑示例。

图 6. 局部变量指令执行示例

全局变量指令
全局变量指令与局部变量指令很类似，只不过操作对象是全局变量。global.get 指令把全局变量的值压栈，全局变量的索引由立即数指定；而 global.set 指令设置全局变量的值，全局变量的索引由立即数指定，新的值从栈顶弹出；下图 7 展示了全局变量指令的执行逻辑示例。

图 7. 全局变量指令执行示例

5.3 内存指令(Memory Instructions)

内存指令按操作类型分为三类，他们分别是加载指令、存储指令、内存 size 和 grow 指令；其中，加载指令从内存中读取数据，压入操作数栈；存储指令从栈顶弹出数值，写入内存；内存 size 和 grow 指令只获取或者增长内存页数；内存指令格式如下所示。

load_instr : opcode | align | offset # align: u32, offset: u32
store_instr: opcode | align | offset
memory.size: 0x3f | 0x00
memory.grow: 0x40 | 0x00

下面我们分别介绍这三种内存指令的逻辑及其实现。

加载指令
加载指令编码格式中带有对齐方式和内存偏移量两个立即数，加载指令首先从操作数栈上弹出一个 i32 类型的数，把它和偏移量立即数相加得到实际线性内存地址，此时，加载指令便从线性内存地址加载数据并转换为类型 "T" 的值压入操作数栈；其中类型 "T" 可以为 i32，i64，f32，f64；下图 8 展示了加载指令的执行逻辑示例。

图 8. 内存加载指令执行示例

存储指令
和加载指令类似，存储指令也带有对齐方式和内存偏移量两个立即数，存储指令首先从操作数栈上弹出需要写入内存的操作数值和一个 i32 类型的内存基址，然后，把内存基址和偏移量立即数相加得到实际线性内存地址，此时，存储指令便可以将需要保持的操作数转换为类型 "T" 的值保存至内存地址处；其中类型 "T" 可以为 i32，i64，f32，f64；下图 9 展示了存储指令的执行逻辑示例。

图 9. 内存存储指令执行示例

内存 size 和 grow 指令
memory.size 指令把内存的当前页数以 i32 类型压栈，指令立即数用来指代操作的内存；WebAssembly MVP 规范规定最多只能导入或者定义一块内存，立即数必须为0。
memory.grow 指令用于扩展内存若干页，并获取原始内存页(增长前的页数)。执行时，该指令需要从栈顶弹出一个 i32 类型的数，代表要增长的页数；如果增长成功，指令把增长之前的页数以 i32 类型压栈；否则，把 -1 压栈；memory.grow 指令也带有一个单字节立即数，当前必须为 0。
内存 size 和 grow 指令执行逻辑示例如下图 10 所示。

图 10. 内存 size 和 grow 指令执行示例

5.4 数值指令(Numeric Instructions)

数值指令是 WebAssembly 指令集中数量最多的一类。按照操作类型，数值指令又可以分为常量指令、测试指令、比较指令、算术指令和类型转换指令。下面我们分别介绍各类数值指令的逻辑实现。

常量指令
常量指令将指令中的立即数常量作为指定类型的操作数压入操作数栈；其中类型 "T" 可以为 i32，i64，f32，f64 四种；常量指令执行逻辑示例如下图 11 所示。

图 11. 常量指令执行示例

测试指令
测试指令从栈顶弹出一个操作数，先“测试”它是否为 0，然后把 i32 类型的布尔值测试结果压栈；测试指令类型 "T" 只针对整数类型 i32 和 i64；测试指令执行逻辑示例如下图 12 所示。

图 12. 常量指令执行示例

比较指令
比较指令从栈顶弹出 2 个同类型的操作数进行比较，然后把 i32 类型的布尔值比较结果压栈；比较指令数量比较多，除了操作数类型和比较方式外，所有比较指令的逻辑都是相似的。以 i64.It_s 指令为例的比较指令示意图，其中类型 "T" 可以为 i32，i64，f32，f64 四种；比较指令执行逻辑示例如下图 13 所示。

图 13. 比较指令执行示例

WAInterp 定义 compare 函数用于统一实现比较和测试指令逻辑，如下代码所示。

type Operation =
  |"eq"    | "ne"
  | "lt_s" | "lt_u" | "le_s" | "le_u"
  | "gt"   | "gt_s" | "gt_u" | "ge_s" | "ge_u";

export function compare(
  { value: value1 }: StackLocal,
  { value: value2 }: StackLocal,
  op: Operation
): StackLocal {
  switch (op) {
    case "eq":
      return i32.createValue(value1.eq(value2));
    case "ne":
      return i32.createValue(value1.ne(value2));
    case "lt_s":
      return i32.createValue(value1.lt_s(value2));
    case "le_s":
      return i32.createValue(value1.le_s(value2));
    case "gt":
      return i32.createValue(value1.gt(value2));
    case ...
  }
  throw new Error("Unsupported binop: " + op);
}

算数指令
算数指令根据操作数的数量可以进一步分为一元算术指令和二元算术指令。
一元算术指令从栈顶弹出一个操作数进行计算，然后将同类型的结果压栈，除了操作数的类型和指令功能外，所有的一元算术指令的逻辑都是相似的；
二元算术指令从栈顶弹出2个相同类型的操作数进行计算，然后将同类型结果压栈，与一元算数指令类似，抛开操作数的类型和计算，二元算术指令的逻辑也都是相似的。其中类型 "T" 可以为 i32，i64，f32，f64 四种；算数指令执行逻辑示例如下图 14 所示。

图 14. 算数指令执行示例

WAInterp 定义 unop 和 binop 函数分别用于实现一元和二元算术指令，如下代码所示。

type Operation = "abs" | "neg" | "clz" | "ctz" | "popcnt" | "eqz"
function unop(
  { value: value }: StackLocal,
  operation: Operation,
  createValue: (arg: any) => StackLocal
): StackLocal {
  switch (operation) {
    case "abs":
      return createValue(value.abs());
    case "neg":
      return createValue(value.neg());
    case "clz":
      return createValue(value.clz());
    case "ctz":
      return createValue(value.ctz());
    case "popcnt":
      return createValue(value.popcnt());
    case "eqz":
      return i32.createValue(value.eqz());
    case ...
  }
  throw new Error("Unsupported unop: " + operation);
}

type Sign = "add" | "sub" | "div" | "div_s" | "div_u" | "mul"
  | "and" | "or" | "xor" | "~" | "min" | "max" | "copysign"
  | "rem_s" | "rem_u" | "shl" | "shr_s" | "shr_u" | "rotl" | "rotr";
function binop(
  { value: value1 }: StackLocal,
  { value: value2 }: StackLocal,
  sign: Sign,
  createValue: (arg: any) => StackLocal
): StackLocal {
  switch (sign) {
    case "add":
      return createValue(value1.add(value2));
    case "sub":
      return createValue(value1.sub(value2));
    case "mul":
      return createValue(value1.mul(value2));
    case "shl":
      return createValue(value1.shl(value2));
    case "shr_s":
      return createValue(value1.shr_s(value2));
    case "div":
      return createValue(value1.div(value2));
    case "and":
      return createValue(value1.and(value2));
    case "or":
      return createValue(value1.or(value2));
    case ...
  }
  throw new Error("Unsupported binop: " + sign);
}

类型转换
类型转换指令从栈顶弹出一个操作数进行类型转换，然后把结果压栈。按照转换方式，类型转换指令可以分为整数截断 (wrap)、整数扩展 (extend)、浮点数截断 (trunc)、整数转换 (convert)、浮点数精度调整 (demote、promote) 以及比特位重新解释 (reinterpret)。除了操作数类型和转换逻辑，所有的类型转换指令的逻辑也都是相似的，以 i32.wrap_i64 指令为例，其执行逻辑示例如下图 15 所示。

图 15. i32.wrap_i64 类型转换指令执行示例

至此，我们已经介绍了常用的数值指令及核心执行逻辑，完整指令列表及详细信息请参见 WebAssembly 指令列表[10]，不在此一一讨论和介绍。接下来，我们介绍最后一类和控制流相关的控制指令。

5.5 控制指令(Control Instructions)

控制指令是程序控制流管理的关键指令，主要包括结构化控制指令、跳转指令、函数调用指令、伪指令等类型。下面我将分别介绍各控制指令的逻辑功能及实现。

伪指令
伪指令是控制指令中最简单的一类，其中，unreachable 指令引发一个运行时错误；nop(No Operation 的缩写) 指令表示空操作，什么都不做；实现代码如下所示。

export function executeStackFrame(
  { program }: IR,
  offset: number,
  firstFrame: StackFrame
): StackLocal {
  // skip non-cricital code ...
  while (true) {
    // skip non-cricital code ...
    pc++;
    switch (instruction.id) {
      case "nop": { break; } // do nothing
      case "unreachable":
      case "trap": { throw new RuntimeError(); }
      case ...:
  }
}

结构化控制指令
程序中最基本的控制结构有顺序结构、分支结构、循环结构三种，组合使用这三种控制结构就可以构造出其他控制结构和复杂的程序。WebAssembly 提供了 block、loop、if 三条控制指令来生成对应的控制结构，由于控制指令有良好的结构化特征，因此被称为结构化控制指令；控制指令格式如下所示。

block_instr: 0x02 | block_type | instr* | 0x0b
loop_instr : 0x03 | block_type | instr* | 0x0b
if_instr   : 0x04 | block_type | instr* | (0x05 | instr*)? |0x0b
block_type : s32

从指令的语义上来看，除了跳转目标不同，block 指令和 loop 指令的结构和执行逻辑是基本一致的。针对结构化控制指令的编码规范，WAInterp 定义如下的数据结构来表示，如下代码所示。

type BlockInstruction = {
  type: "BlockInstruction";
  id: string;
  label?: Identifier;
  instr: Array<Instruction>;
  result?: Valtype;
};
type LoopInstruction = BlockInstruction & {
  type: "LoopInstruction";
};

结构化控制指令在语义上与函数调用类似，指令的块类型相当于函数的签名，内部指令相当于函数的字节码序列。当进入结构化控制指令时，操作数栈顶指定数目和类型的值作为控制指令参数；当指令结束时，栈顶生成指定数目和类型的执行结果。以如下的 block 和 loop 示例程序为例，对应的执行逻辑如图 16 所示。

(module
  (func $add (param $a i64) (param $b i64) (result i64)
    (local.get $a) (local.get $b)
    (block (param i64 i64) (result i64)
      (i64.add)
    ) 
  ) 
)

图 16. block/loop 指令执行示例

block 和 loop 指令主要维护控制栈并为跳转指令提供目标地址；因此，WAInterp 解释器对于 block 和 loop 的处理就比较简单，执行指令时，在栈帧的标签栈 frame.labels 中创建标签 label 对象；实际的跳转逻辑将在后续的详细介绍，不在此赘述。

type Label = {
  arity: number,
  value: any,
  id?: Identifier,
};
export function executeStackFrame(
  { program }: IR,
  offset: number,
  frame: StackFrame
): StackLocal {
  // skip irrelevant code ...
  while (true) {
    // skip irrelevant code ...
    switch (instruction.id) {
      case "loop":
      case "block": {
        frame.labels.push({ // control stack
          value: instruction,
          arity: 0,
          id: instruction.label,
        });
        pushResult(frame, label.createValue(instruction.label.value));
        break;
      }
  }
}

相比 block 和 loop 指令，if 指令相对复杂一些，其内部的指令序列被 "else" 指令一分为二；针对结构化控制指令的编码规范，WAInterp 定义如下的数据结构来表示，如下代码所示。

type IfInstruction = {
  type: "IfInstruction";
  id: string;
  test: Array<Instruction>;
  result?: Valtype;
  consequent: Array<Instruction>;
  alternate: Array<Instruction>;
};

if 指令携带 consequent 和 alternate 两个相同类型的指令序列，其中 alternate 是可选的；当指令执行时，会先从操作数栈顶弹出一个 i32 类型布尔值，如果该值为真就执行 consequent 指令序列，否则执行 alternate，这样就起到了分支的效果。以如下的示例程序为例，if 指令对应的执行逻辑如图 17 所示。

(module
  (func $calc (param $op i32) (param $a i64) (param $b i64) (result i64)
    (local.get $a) (local.get $b)
    (if (param i64 i64) (result i64)
      (i32.eqz (local.get $op))
      (then (i64.add))
      (else (i64.sub))                                             
    )
  )                                                
)

图 17. if 指令执行示例

由于 if 指令实际上是定义了两个 block 块，我们在函数实例化阶段已经对 if 指令进行的预处理，将其转换为独立的 block IR 同时添加跳转指令以维护 if 指令的执行语义；因此，WAInterp 不需要对 if 指令进行单独处理，而直接复用 block 指令的执行逻辑。

跳转指令
为了形成完整的控制流，WebAssembly 定义了 4 条跳转指令，它们分别是无条件跳转指令 br，条件跳转指令 br_if，查表跳转指令 br_table，函数返回指令 return。下面我们分别介绍各跳转指令的执行逻辑和实现。
br 指令进行无条件跳转，该指令带有一个立即数指定跳转的目标标签索引。从语义上看，不同的控制块类型 br 指令表现不同的行为。由于 block 指令控制块的标签在尾部，br 指令导致这个控制块提前结束；而 loop 指令控制块的标签在头部，br 指令导致这个控制块重新开始执行；br 指令执行语义如下图 18 所示。

图 18. br 指令跳转语义

WAInterp 在执行 br 指令时执行栈变化如下图 19 所示，其中 btr (block type result) 表示对应 block 的返回值，黑色三角形表示这个位置对应一个新的控制帧；br 指令执行前操作数栈的状态左侧所示，当函数准备执行 br 2 指令时，操作数栈上有 4 个整数对应每个 block 指令的返回值，对应的控制栈上也应该有 4 个控制帧。执行 br 2 指令时，控制栈顶的 3 个控制帧被弹出，与这 3 个控制帧对应的操作数栈也应该被清理。由于标签索引 2 指向的控制块有一个结果，所以应该先从栈顶弹出一个操作数，暂存起来。对栈进行清理之后，再把暂存的结果压栈。

图 19. br 指令执行示例

export function executeStackFrame(
  { program }: IR,
  offset: number,
  frame: StackFrame
): StackLocal {
  // skip non-cricital code ...
  while (true) {
    // skip non-cricital code ...
    switch (instruction.id) {
      // skip non-cricital code ...
      case "br": {
        const label = instruction.args[0];
        let result: Valtype = frame.values[frame.values.length - 1];
        while (label.id != frame.labels[frame.labels.length - 1].id) {
          frame.labels.pop()
          if (frame.labels[frame.labels.length - 1].arity != 0) {
            frame.values.pop();
          }
        }
        if (label.arity != 0) {
          frame.values.push(result)
        }
        GOTO(label.value);
        break;
      }
  }
}

在实现了 br 指令后，其他跳转指令就非常容易理解和实现了；其中 br_if 指令进行条件跳转，当执行 br_if 指令执行时，先从操作数栈顶弹出一个 i32 类型布尔值 c；如果该值为真，则接着执行和 br 指令完全一样的逻辑；否则，只相当于执行一次 drop 操作；br_if 指令的执行栈变化如下图 20 所示：

图 20. br_if 指令执行示例

br_table 指令进行无条件查表跳转；与 br 和 br_if 指令不同，br_table 指令可以指定多个跳转目标，最终使用哪个跳转目标要到运行期间才能决定；br_table 指令的立即数给定了 n + 1 个跳转标签索引；其中前 n 个标签索引构成了一个索引表，后一个标签索引是默认索引；当 br_table 指令执行时，要先从操作数栈顶弹出一个 i32 类型的值m；如果 m 小于等于 n，则跳转到索引表第 m 个索引指向的标签处；否则，跳转到默认索引指定的标签处，br_table 指令执行示例如下图 21 所示。

图 21. br_table 指令执行示例

函数体本身也是一个隐式的控制块，结构化控制指令 return 直接跳出最外层的块，并根据函数返回值清理操作数栈和函数调用栈，return 指令最终效果就是导致函数返回，代码如下所示。

export function executeStackFrame(
  { program }: IR,
  offset: number,
  frame: StackFrame
): StackLocal {
  // skip irrelevant code ...
  while (true) {
    // skip irrelevant code ...
    switch (instruction.id) {
      // skip irrelevant code ...
      case "return": {
        if (frame.returnAddress !== -1) {
          pc = frame.returnAddress; // raw goto
          POP_STACK_FRAME();
        }
        return RETURN();
      }
  }
}

函数调用指令
函数是 WebAssembly 的基本执行单位，为了执行函数，WebAssembly 定义了直接函数调用 call 指令和间接函数调用 call_indirect 指令；除了函数索引的确定时机不同，直接函数调用和间接函数调用执行逻辑是一致的；其中，call 指令的立即数指定的函数索引；call_indirect指令需要运行时的操作数栈提供函数表中的索引值实现动态函数调用。函数调用是一类特殊的结构化控制指令，为了记录函数执行过程中的状态和数据，WAInterp 为每个函数调用创建函数栈帧 StackFrame。

type StackFrame = {
  values: Array<StackLocal>,  // operands stack of current stackframe
  locals: Array<StackLocal>,  // local variable of current stackframe
  labels: Array<Label>,  // Labels are named block of current stackframe
  returnAddress: number, // caller address
  module: ModuleInstance, // reference to its originating module.
  store: Store, // shared memory storage
};

type StackLocal = {
  type: Valtype,
  value: any,
};

如上代码所述，每个栈帧包括如下关键内容。

模块实例 module: 包含栈帧关联的函数的所有信息，包括模块索引空间，函数类型，函数指令序列等。
操作数栈 values: 用于存储参数、局部变量、以及函数体指令执行过程中的操作数；为了简化实现，每个栈帧维护自己专有的操作数栈。
控制栈 labels: 前面小节中，我们已经详细介绍了 WebAssembly 的控制结构和控制指令；由于 WebAssembly 不支持任意跳转指令，只支持受限的结构化跳转，其核心的设计是通过block, loop, if结构化控制指令将函数分割为一系列嵌套的代码块，每个代码块拥有一个标签 label，跳转指令按照约定在跳转到嵌套代码块的外层标签处，如下图 22 所示。这种结构和逻辑类似于函数调用栈，因此，我们可以通过定义控制栈和控制帧来实现结构化控制指令和跳转指令，其中 CSP 与 SP 类似，表示 Control Stack Pointer，如下图 22 所示。

图 22. WebAssembly 控制帧栈和控制结构图

函数返回地址 returnAddress: 用于存储该栈帧调用指令的下一条指令的地址，当该栈帧从调用栈弹出时，会返回到该栈帧调用指令的下一条指令继续执行；换句话说，就是当前栈帧对应的函数执行完退出后，返回到调用该函数的地方继续执行后面的指令，即 returnAddress 所指定的指令处开始执行。
函数调用帧 CallFrame 需要记录函数被调用过程中的运行时信息，虚拟机执行过程中，每调用一个函数就会创建上述定义的栈帧，当函数执行结束后再把调用帧销毁；而函数的嵌套调用就形成了栈式结构 - 函数调用栈 (Call Stack)，如下图 23 所示。

图 23. WebAssembly 函数调用栈示意图

至此，我们已经分析和定义了函数调用帧和函数调用栈所必须的基础结构，接下来就让我们来实现函数调用指令。Call 指令执行时，首先从指令立即数获取被调用函数的索引，并根据被调用函数的类型从栈顶弹出参数，指令执行结束后，被调用函数的返回值会出现在栈顶，如下图 24 所示，其中函数参数类型为 U，V，返回值类型为 T。

图 24. call 指令执行示例图

基于 call 指令语义和栈相关数据结构，WAInterp 定义 executeStackFrame 用于实际执行目标函数的指令序列，如下代码片段所示。

export function executeStackFrame(
  { program }: IR,
  offset: number,
  frame: StackFrame
): StackLocal {
  // skip irrelevant code ...
  while (true) {
    const callStack: Array<StackFrame> = [firstFrame];
    const offsets = Object.keys(program);
    let pc = offsets.indexOf(String(offset));
    let framepointer : number = 0;
    // skip irrelevant code ...
    switch (instruction.id) {
      case "call": {
        PUSH_NEW_STACK_FRAME(pc);
        const index = instruction.index.value; // callee func index
        GOTO(index);
        break;
      }
      // skip irrelevant code ...
      case "return": {
        if (frame.returnAddress !== -1) {
          POP_STACK_FRAME();
          pc = frame.returnAddress; // raw goto
          break;
        } else {
          return RETURN();
        }
      }
  }
}

如上述代码所示，函数调用主要分为执行 call 指令和函数返回 return 两个过程。call 指令执行时，首先通过函数 PUSH_NEW_STACK_FRAME 为被调用函数创建栈帧并压入调用栈 callStack，然后从 call 指令立即数获取目标函数索引并跳转至目标指令处执行；当函数返回时会即执行 return 指令，首先调用 POP_STACK_FRAME 函数销毁栈帧并将返回值压入返回函数的操作数栈中，最后从当前栈获取返回地址并跳转到目标地址执行；函数调用和返回过程中的栈帧管理函数如下代码所示。

function PUSH_NEW_STACK_FRAME(pc: number): void {
  const activeFrame = getActiveStackFrame();
  const newStackFrame = createChildStackFrame(activeFrame, pc);
  framepointer++; // move active frame
  callStack[framepointer] = newStackFrame; // Push the frame on top of the stack
}

function POP_STACK_FRAME(): void {
  const activeFrame = getActiveStackFrame();
  let res; // pass the result of the previous call into the new active fame
  if (activeFrame.values.length > 0) {
    res = pop1(activeFrame);
    callStack.pop(); // Pop active frame from the stack
    framepointer--;
    const newStackFrame = getActiveStackFrame();
    if (res !== undefined && newStackFrame !== undefined) {
      pushResult(newStackFrame, res);
    }
  }
}

对于 call_indirect 指令而言，编译期只能确定被调用函数的类型并保存在 call_indirect 指令的立即数里，具体调用哪个函数只有在运行期间根据栈顶操作数才能确定；call_indirect 指令首先从指令立即数获取被调用函数所保存的表索引和函数类型，然后指令从栈顶弹出一个 i32 类型的操作数，该操作数指定了需要执行的函数在表中的索引值；如果表中的函数对应的函数类型与指令立即数指定的函数类型不匹配，那么执行非法，否则，call_indirect 可以根据索引查表找到函数引用，完成调用函数；call_indirect 指令执行示例如下图 25 所示。由于 call 指令和 call_indirect 除了函数索引确定的时机之外，执行逻辑基本是一致的，因此，call_indirect 指令实现与 call 指令基本类似，不再此赘述。

图 25. call_indirect 指令执行示例图

6. WAInterp 运行实例

在以上各小节，我们详细阐述了 WAInterp 解析器的工作原理及基于 Typescript 的实现，本节我们利用上述过程中实现的 WAInterp 来运行实际的示例程序，来验证解释器的正确性。
示例程序的源代码如下所示，其中 printstr 为外部导入函数用于打印字符串，hello 函数接收一个整数参数，根据不同的参数会打印不同的字符串，而 hello 函数会进一步通过调用 iadd 函数获取结果并返回。

// hello-world.c

WASM_IMPORT("env", "printstr") int printstr(char*);

WASM_EXPORT("iadd") int iadd(int a, int b) {
  return a + b;
}

WASM_EXPORT("main") int hello(int option) {
  if(option == 1) {
    printstr("hello world!");
  } else {
    printstr("see you again!");
  }
  return iadd(option, 100);
}

以上源代码生成的 WebAssembly 文本格式如下所示

(module
  (type (;0;) (func (param i32)))
  (type (;1;) (func))
  (type (;2;) (func (param i32) (result i32)))
  (type (;3;) (func (param i32 i32) (result i32)))
  (import "env" "printstr" (func $printstr (type 2)))
  (func $iadd (type 3) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    i32.add)
  (func $hello (type 2) (param i32) (result i32)
    (local i32)
    i32.const 1
    local.set 1
    block  ;; label = @1
      block  ;; label = @2
        local.get 0
        local.get 1
        i32.eq
        br_if 0 (;@2;)
        i32.const 1037
        local.set 1
        local.get 1
        call $printstr
        br 1 (;@1;)
        drop
      end
      i32.const 1024
      local.set 1
      local.get 1
      call $printstr
      drop
    end
    local.get 0
    i32.const 100
    call $iadd
    return)
  (memory (;0;) 1)
  (global $__stack_pointer (mut i32) (i32.const 2064))
  (export "memory" (memory 0))
  (export "main" (func $hello))
  (export "iadd" (func $iadd))
  (export "stack_pointer" (global $__stack_pointer))
  (data $.rodata (i32.const 1024) "hello world!\00see you again!\00"))

基于 WAInterp 解释器，我们实现了执行 WebAssembly 二进制文件的命令行工具 wasmrun.ts；通过如下命令行，可以在运行示例程序的过程中观察指令执行过程及执行结果，其中控制台输出为 [printstr] see you again!，返回结果为输入参数与 100 之和，如下所示。

npx ts-node src/cli/bin/wasmrun.ts test/wasm/hello.wasm main 2

Executing...
-> main(2):
  -> Instr(local)
  -> debug: new local i32
  -> Instr(const)
  -> Instr(set_local)
  -> BlockInstruction(block)
  -> entering block block_1
    -> BlockInstruction(block)
    -> entering block block_0
      -> Instr(get_local)
      -> Instr(get_local)
      -> Instr(eq)
      -> Instr(br_if)
      -> Instr(const)
      -> Instr(set_local)
      -> Instr(get_local)
      -> InternalCallExtern()
      [printstr] see you again!
      -> Instr(br)
    -> Instr(end)
    -> exiting block block_0
  -> Instr(get_local)
  -> Instr(const)
  -> CallInstruction(call)
    -> Instr(get_local)
    -> Instr(get_local)
    -> Instr(add)
    -> InternalEndAndReturn()
  -> Instr(return)
exited with code { type: 'i32', value: i32 { _value: 102 } }

7. 总结

至此，我们已经完整地实现了 WAInterp 虚拟机的最基础的能力，其中包括 WebAssembly 模块的加载和解码，模块的实例化以及指令执行；本文从零开始实现一个简单的 WebAssembly 解释器，通过这一过程不仅帮助我们进一步了解和掌握 WebAssembly 基本原理，还实实在在的构建一个可用的 WebAssembly 虚拟机。虽然我们只实现了 WebAssembly 规范的最小 MVP 子集，但 WAInterp 提供了一个 WebAssembly 虚拟机框架和运行时基座，可以基于此来进一步扩展和补充 WebAssembly 规范的功能和特性。

由于篇幅有限，我们仅在文中展示了 WAInterp 的核心实现代码，完整实现可以通过源码仓库 WARuntime[12] 进行获取；此外，JavaScript 工程可以通过添加 @zhongxiao/waruntime[6] 依赖获取 WARuntime NPM 依赖包。基于 WARuntime，读者可以方便的按照指引快速重建和运行本文中所有的示例程序。

8. 参考文献

[1]. WebAssembly工作原理浅析
[2]. Crafting Interpreters: https://craftinginterpreters.com/
[3]. Dispatch Techniques: http://www.cs.toronto.edu/~matz/dissertation/matzDissertation-latex2html/node6.html
[4]. Principles of Just-In-Time Compilers: https://nbp.github.io/slides/GlobalScope/2021-07/#intro,0
[5]. 计算机程序的构造和解释: https://book.douban.com/subject/1148282/
[6]. @zhongxiao/waruntime: https://www.npmjs.com/package/@zhongxiao/waruntime
[7]. Binary Module: https://WebAssembly.github.io/spec/core/binary/modules.html
[8]. Custom Sections: https://WebAssembly.github.io/spec/core/appendix/custom.html
[9]. Index of Instructions: https://WebAssembly.github.io/spec/core/appendix/index-instructions.html
[10]. WebAssembly Opcodes: https://pengowray.github.io/wasm-ops/
[11]. Binary Encoding: https://github.com/WebAssembly/design/blob/main/BinaryEncoding.md
[12]. WARuntime: https://github.com/yaozhongxiao/WebAssemblyToolkit

点击上方关注 · 我们下期再见

点击左下方“阅读原文”，或扫描上方二维码，进入专栏阅读《走进 WebAssembly 的世界》完整版。

继续滑动看下一个