本文在 字节码联盟网站上交叉发布。

多值 是一个提议的 WebAssembly 核心扩展，它可以使函数返回多个值，除此之外还有其他功能。它也是 Wasm 接口类型 的先决条件。

我最近一直在各个地方添加多值支持

• 我在 Rust 和 WebAssembly 工具链中的所有各种板条箱中添加了多值支持，这样 Rust 项目就可以编译成使用多值功能的 Wasm 代码。

• 我在 Wasmtime 中添加了多值支持，Wasmtime 是构建在 Cranelift 代码生成器之上的 WebAssembly 运行时，因此它可以运行使用多值功能的 Wasm 代码。

现在，随着我的多值工作即将结束，似乎是反思这段经历并记录下让所有这些地方都支持多值所需做的一切的好时机。

等等 - 多值 Wasm 是什么？

在 WebAssembly 核心，语言存在一些关于元数的限制

• 函数只能返回零个或一个值，并且
• 像 block、if 和 loop 这样的指令序列不能使用任何堆栈值，并且只能产生零个或一个结果堆栈值。

多值提案 是对 WebAssembly 标准的扩展，它取消了这些元数限制。在新的多值 Wasm 规则下

• 函数可以返回任意数量的值，并且
• 指令序列可以使用和产生任意数量的堆栈值。

以下代码段仅在多值 Wasm 提案中引入的新规则下才有效

;; A function that takes an `i64` and returns
;; three `i32`s.
(func (param i64) (result i32 i32 i32)
  ...)

;; A loop that consumes an `i32` stack value
;; at the start of each iteration.
loop (param i32)
  ...
end

;; A block that produces two `i32` stack values.
block (result i32 i32)
  ...
end

多值提案目前处于 WebAssembly 标准化过程的第 3 阶段。

但这与我有什么关系？

代码大小

在一些场景下，当编译器生成用于 WebAssembly 核心的多个堆栈值时，它被迫绕弯路。解决方法包括引入临时局部变量，并使用 local.get 和 local.set 指令，因为对块的元数限制意味着这些值 *不能* 保留在堆栈上。

考虑一下我们正在计算两个堆栈值的场景：指向线性内存中字符串的指针，以及它的长度。此外，想象一下，我们根据某种条件在两个不同的字符串（因此具有不同的指针和长度对）之间进行选择。但是无论我们选择哪个字符串，我们都将以相同的方式处理该字符串，所以我们只需要将我们选择字符串的指针和长度对推送到堆栈上，然后控制流就可以之后合并。

使用多值，我们可以直接做到这一点

call $compute_condition
if (result i32 i32)
  call $get_first_string_pointer
  call $get_first_string_length
else
  call $get_second_string_pointer
  call $get_second_string_length
end

这种编码也很紧凑：只有 16 个字节！

当我们以 WebAssembly 核心为目标，并且多值不可用时，我们被迫寻求其他更复杂的形式。我们可以通过临时局部值将堆栈值从每个 if 和 else 分支中偷渡出来

;; Introduce a pair of locals to hold the values
;; across the instruction sequence boundary.
(local $string i32)
(local $length i32)

call $compute_condition
if
  call $get_first_string_pointer
  local.set $string
  call $get_first_string_length
  local.set $length
else
  call $get_second_string_pointer
  local.set $string
  call $get_second_string_length
  local.set $length
end

;; Restore the values onto the stack, from their
;; temporaries.
local.get $string
local.get $length

这种编码需要 30 个字节，比理想的多值版本多了 14 个字节。如果我们计算的是三个值而不是两个，那么开销会更大，对于四个值也是如此……额外的开销与我们在 if 和 else 分支中产生的值数量成正比。

我们实际上可以比这更小——仍然使用 WebAssembly 核心——通过绕过不同的弯路。我们可以将其拆分为两个 if ... else ... end 块，并复制条件检查以避免为每个计算的值本身引入临时变量

;; Introduce a local for the condition, so that
;; we only re-check it, and don't recompute it.
(local $condition i32)

;; Compute and save the condition.
call $compute_condition
local.set $condition

;; Compute the first stack value.
local.get $condition
if (result i32)
  call $get_first_string_pointer
else
  call $get_second_string_pointer
end

;; Compute the second stack value.
local.get $condition
if (result i32)
  call $get_first_string_length
else
  call $get_second_string_length
end

这使我们减少到 28 个字节。比上一个版本少两个，但与多值编码相比，仍然有 12 个字节的开销。而且开销仍然与我们计算的值数量成正比。

没有办法避免：我们需要多值才能获得最紧凑的代码。

新指令

多值提案为生成多个值的全新指令打开了可能性

• 类型为 [i32 i32] -> [i32 i32] 的 i32.divmod 指令，它接收一个分子和一个分母，并产生它们的商和余数。

• 具有额外进位结果的算术运算。这些可以用来更好地实现大整数、溢出检查和饱和运算。

更有效地返回小型结构体

从函数返回多个值将使我们能够更有效地返回小型结构体，比如 Rust 的 Result。如果没有多值返回，这些相对较小的结构体仍然不适合单个 Wasm 值类型，它们会被临时放置在线性内存中。使用多值返回，这些值不会逃逸到线性内存中，而是停留在堆栈上。这可能更有效，因为 Wasm 堆栈值通常比从线性内存中加载和存储更适合优化。

接口类型

缩小代码大小很棒，新的指令也很不错，但我真正兴奋的是：WebAssembly 接口类型。接口类型以前被称为“主机绑定”，它们是解锁的关键

• 在 Web 上直接、优化地访问浏览器的 DOM 方法，
• WebAssembly 模块的“无共享链接”，以及
• 定义语言中立的接口，比如 WASI。

对于所有这三种用例，我们可能希望从被调用 Wasm 模块返回一个字符串。使用该字符串的调用者可能是 Web 浏览器，也可能是另一个 Wasm 模块，或者可能是与 WASI 兼容的 Wasm 运行时。无论如何，返回字符串的一种自然方式是作为两个 i32

1. 指向线性内存中字符串开头的指针，以及
2. 字符串的字节长度。

然后，接口适配器可以将该对 i32 提升为抽象字符串类型，然后将其降低为另一侧的调用者的具体字符串表示。接口类型的设计使得在大多数情况下，这种提升和降低可以优化为从被调用者的线性内存到调用者的快速内存复制。

但在接口适配器可以执行这种提升和降低之前，它们需要访问指针和长度对，这意味着被调用 Wasm 函数需要返回两个值，这意味着我们需要多值 Wasm 才能使用接口类型。

所有实现！

现在我们知道了多值 Wasm 是什么，以及它为什么令人兴奋，我将讲述在各个地方实现对它的支持的故事。我从在 Rust 和 WebAssembly 工具链中实现多值支持开始，然后我在 Wasmtime 运行时以及它构建在之上的 Cranelift 代码生成器中添加了支持。

Rust 和 WebAssembly 工具链

Rust 和 Wasm 工具链伞下包含什么？它是通用 Rust 工具链的超集

• cargo：管理构建和依赖项。
• rustc：将 Rust 源代码编译成代码。
• LLVM：在幕后由 rustc 使用，用于优化和生成代码。

此外，当以 Wasm 为目标时，我们还使用了一些其他组件

• wasm-bindgen：部分是库，部分是 Wasm 后处理器，wasm-bindgen 生成用于使用和产生使用接口类型定义的接口的绑定（以及更多！）。
• walrus：一个用于转换和重写 WebAssembly 模块的库，由 wasm-bindgen 的后处理器使用。
• wasmparser：一个用于 WebAssembly 二进制文件的事件式解析器，由 walrus 使用。

以下是工具链管道的摘要，显示了工具之间输入和输出

我的目标是使用多值函数解锁接口类型。目前，我还没有关注从生成多值块中获得的代码大小优势。就我而言，我只需要在与接口适配器通信的 Wasm 模块边缘引入多值函数；我并不需要使所有函数体都使用最佳的多值指令序列结构。因此，我决定让 wasm-bindgen 的后处理器重新编写某些函数以使用多值返回，而不是在 LLVM 中添加支持。⁰ 使用这种方法，我只需要向以下工具添加支持

• cargo
• rustc
• LLVM
• wasm-bindgen
• walrus
• wasmparser

wasmparser

wasmparser 是一个用于 WebAssembly 二进制文件的事件式解析器。 添加用于 *生成* 多值 Wasm 的工具链支持从 *解析* 多值 Wasm 开始可能看起来很奇怪。但这是为了使测试变得轻松且无痛，并且我们最终也需要它，因为 Wasmtime 也使用 wasmparser。

在 WebAssembly 核心，block、loop 或 if 的可选值类型结果直接在指令中编码

• 一个 0x40 字节表示没有结果
• 一个 0x7f 字节表示有一个 i32 结果
• 一个 0x7e 字节表示有一个 i64 结果
• 等等……

在多值 Wasm 中，不仅存在零个或一个结果值类型，还存在参数类型。块可以与函数具有相同的类型集。函数已经在 Wasm 二进制文件的“类型”部分中对它们的类型进行了重复数据消除，并通过索引引用它们。在多值中，块现在也这样做。但这如何与非多值块类型共存呢？

索引被编码为一个带符号的变长整数，使用 LEB128 编码。如果我们将非多值块的可选结果值类型解释为一个带符号的 LEB128，我们会得到

• -64（可以用带符号的 LEB128 编码为单个字节的最小的数字）表示没有结果
• -1 表示有一个 i32 结果
• -2 表示有一个 i64 结果
• 等等……

它们都是负数，将正数留给解释为指向“类型”部分中多值块的索引！来自 WebAssembly 标准制定人员的一个很好的小编码技巧和先见之明。

添加对解析这些的支持很简单，但是 wasmparser 还支持在解析时验证 Wasm。添加验证支持稍微复杂一些。

wasmparser 的验证实现类似于 WebAssembly 规范附录中介绍的验证算法：它抽象地解释 Wasm 指令，维护一个类型堆栈，而不是一个值堆栈。如果任何操作使用错误类型的操作数——例如，当我们执行 i32.add 指令时，堆栈的顶部有一个 f32，因此我们期望堆栈的顶部有两个 i32——那么验证就会失败。如果没有类型错误，那么它就会成功。在处理堆栈多态指令（如 drop）时，有一些复杂之处，但它们并没有真正与多值交互。

每当 `wasmparser` 遇到 `block`、`loop` 或 `if` 指令时，它都会推送一个关联的控制帧，用于跟踪该块内的指令可以访问堆栈的深度。在多值之前，限制始终是进入块时堆栈的长度，因为块不会从堆栈中获取任何值。有了多值，这个限制就变成了 `stack.len() - block.num_params()`。当退出一个块时，`wasmparser` 会弹出关联的控制帧。它会检查堆栈顶部的 `n` 个类型是否与块的结果类型匹配，以及堆栈的长度是否为 `frame.depth + n`。在多值之前，`n` 始终为 `0` 或 `1`，但现在它可以是任何非负整数。

多值影响的最后一个验证位是当 `if` 需要 `else` 或不需要时。在核心 Wasm 中，如果 `if` 没有在堆栈上产生结果值，则不需要 `else` 分支，因为整个 `if` 的类型为 `[] -> []`，这也与无操作的类型相同。有了多值，这被推广到任何输入和输出类型相同的 `if`：`[t*] -> [t*]`。易于实现，但也容易被忽视（就像我最初做的那样！)

多值支持是在以下拉取请求中添加到 `wasmparser` 的

• #103：初始多值支持
• #135：允许 `[t*] -> [t*]` 类型的 `if` 块没有 `else`

walrus

`walrus` 是一个 WebAssembly 到 WebAssembly 的转换库。 我们用它在 `wasm-bindgen` 中生成粘合代码，以及为 WebAssembly 功能提供垫片。

`walrus` 为 WebAssembly 构建了自己的中间表示 (IR)。类似于 `wasmparser` 如何验证 Wasm 指令，`walrus` 也在构建其 IR 的同时抽象地解释指令。这意味着，向 `walrus` 添加构建多值 IR 的支持，非常类似于向 `wasmparser` 添加多值验证支持。实际上，`walrus` 在构建其 IR 时也会验证 Wasm。

但是多值对 IR 本身有很大的影响。在多值之前，可以将 Wasm 的基于堆栈的指令视为表达式树的后序编码。

考虑表达式 `(a + b) * (c - d)`。作为表达式树，它看起来像这样

     *
    / \
   /   \
  +     -
 / \   / \
a   b c   d

树的后序遍历是指在访问子节点之后访问节点。我们示例表达式树的后序遍历将是

a b + c d - *

假设 `a`、`b`、`c` 和 `d` 是类型为 `i32` 的 Wasm 局部变量，其值分别为 `9`、`7`、`5` 和 `3`。我们可以将这个后序直接转换为一系列 Wasm 指令，这些指令在 Wasm 堆栈上构建其结果

;; Instructions ;; Stack
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
local.get $a    ;; [9]
local.get $b    ;; [9, 7]
i32.add         ;; [16]
local.get $c    ;; [16, 5]
local.get $d    ;; [16, 5, 3]
i32.sub         ;; [16, 2]
i32.mul         ;; [32]

树和 Wasm 堆栈指令之间的这种对应关系使得在 `walrus` 中使用树状 IR 变得非常自然，其中节点是指令，节点的子节点是生成父节点输入值的指令。¹ 我们的 IR 过去看起来像这样

pub enum Expr {
    // A `local.get` instruction.
    LocalGet(LocalId),

    // An `i32.add` instruction.
    I32Add(ExprId, ExprId),

    // Etc...
}

但是多值在这个树状表示中引入了一个问题：现在一个指令可以产生多个值，当我们在树中有一个 `parent⟶child` 边缘时，我们如何知道父节点想要使用子节点的哪个结果值？而且，如果两个不同的父节点都使用一个指令生成的两个值中的一个，那么从根本上来说，我们不再有树，而是一个 有向无环图 (DAG)。

我们考虑将我们的树状表示推广为 DAG，并用 `n` 标记边缘以表示使用指令的第 `n` 个结果值。我们权衡了实现这种表示的复杂性与我们目前在 `wasm-bindgen` 中的使用案例以及我们能想到的任何未来使用案例的要求。最终，我们决定这并不值得付出努力，因为对于 `wasm-bindgen` 执行的任何转换或操作，或者我们预测它将在未来执行的任何操作，我们都不需要这种级别的细节。

相反，我们决定在一个块内，将指令表示为一个简单的列表对于我们的用例来说已经足够了，所以现在我们的 IR 看起来像这样

pub struct Block(Vec);

pub enum Instr {
    // A `local.get` instruction.
    LocalGet(LocalId),

    // An `i32.add` instruction. Note that its
    // children are left implicit now.
    I32Add,

    // Etc...
}

此外，事实证明，构建和遍历这种基于列表的表示速度更快，因此在 `walrus` 中切换表示也为 `wasm-bindgen` 带来了小小的速度提升。

以下拉取请求实现了 `walrus` 对多值的支持

• #114：将 `walrus` 从树切换到列表 IR
• #124：多值！以及更多模糊测试！

wasm-bindgen

`wasm-bindgen` 简化了 Wasm 模块与其主机之间的高级交互。 通常，该主机是 Web 浏览器及其 DOM 方法，或一些用户编写的 JavaScript。其他时候，它是 Web 之外的 Wasm 运行时，例如 Wasmtime，使用 WASI 和接口类型。`wasm-bindgen` 充当接口类型提案的垫片，以及一些额外的电池，用于提供强大的用户体验。

`wasm-bindgen` 的职责之一是将 Wasm 函数的返回值转换为主机调用者可以理解的内容。当直接使用 Wasmtime 的接口类型时，这意味着生成接口适配器，将具体的 Wasm 返回值提升为抽象的接口类型。当调用者是 Web 上的一些 JavaScript 代码时，这意味着生成一些 JavaScript 代码，将 Wasm 值转换为 JavaScript 值。

让我们看看一些 Rust 函数及其编译后的 Wasm。

首先，考虑我们何时从 Rust 函数返回一个整数

// random.rs

#[no_mangle]
pub extern "C" fn get_random_int() -> i32 {
    // Chosen by fair dice roll.
    4
}

这是该 Rust 代码编译为 Wasm 的反汇编

;; random.wasm

(func $get_random_int (result i32)
  i32.const 4
)

生成的 Wasm 函数的签名实际上与 Rust 函数的签名相同。这里没有什么意外。 `wasm-bindgen` 很容易将生成的 Wasm 值转换为所需的值，因为 `wasm-bindgen` 可以直接访问它；它就在那里。

现在让我们看看从 Rust 返回不适合单个 Wasm 值的复合结构

// pair.rs

#[no_mangle]
pub extern "C" fn make_pair(a: i32, b: i32) -> [i32; 2] {
    [a, b]
}

这是新 Rust 代码编译为 Wasm 的反汇编

;; pair.wasm

(func $make_pair (param i32 i32 i32)
  local.get 0
  local.get 2
  i32.store offset=4
  local.get 0
  local.get 1
  i32.store
)

`pair.wasm` 中 `make_pair` 函数的签名与 `pair.rs` 中的对应签名不一致！它有三个参数而不是两个，并且它没有返回任何值，更不用说一对。

发生的事情是 LLVM 还不支持多值，因此它无法直接从函数返回两个 `i32`。相反，调用者会传递一个“结构返回”指针指向他们为返回值预留的一些空间，`make_pair` 会通过该结构返回指针将返回值写入预留的空间。按照惯例，LLVM 使用第一个参数作为结构返回指针，因此第二个 Wasm 参数是我们 Rust 中的原始 `a` 参数，第三个 Wasm 参数是我们 Rust 中的原始 `b` 参数。我们可以看到，Wasm 函数首先写入 `b` 字段，然后写入 `a` 字段。

如何为结构返回预留空间？与 Wasm 标准的堆栈不同，指令向该堆栈推送值并从中弹出值，LLVM 发出的代码会在线性内存中维护一个“影子堆栈”。有一个全局变量作为堆栈指针，始终指向堆栈的顶部。需要一些自身 scratch 空间的非叶子函数将在进入时递减堆栈指针以在线性内存中分配一些空间（因为堆栈向下增长，其“顶部”是最低地址），并且将在退出时递增堆栈指针以释放该空间。不调用任何其他函数的叶子函数可以跳过递增和递减这个堆栈指针，这正是我们没有看到 `make_pair` 干扰堆栈指针的原因。

为了验证调用者是否在线性内存的影子堆栈中分配了结构返回的空间，让我们创建一个调用 `make_pair` 的函数，然后检查其反汇编

// pair.rs

#[no_mangle]
pub extern "C" fn make_default_pair() -> [i32; 2] {
    make_pair(42, 1337)
}

我在下面注释了 `default_make_pair` 的反汇编，以清楚地说明如何操作影子堆栈指针以创建返回值空间，以及如何将指向该空间的指针传递给 `make_pair`

;; pair.wasm

(func $make_default_pair (param i32)
  (local i32)

  ;; Reserve 16 bytes of space in the shadow
  ;; stack. We only need 8 bytes, but LLVM keeps
  ;; the stack pointer 16-byte aligned. Global 0
  ;; is the stack pointer.
  global.get 0
  i32.const 16
  i32.sub
  local.tee 1
  global.set 0

  ;; Get a pointer to the last 8 bytes of our
  ;; shadow stack space. This is our struct
  ;; return pointer argument, where the result
  ;; of `make_pair` will be written to.
  local.get 1
  i32.const 8
  i32.add

  ;; Call `make_pair` with the struct return
  ;; pointer and our default values.
  i32.const 42
  i32.const 1337
  call $make_pair

  ;; Copy the resulting pair into our own struct
  ;; return pointer's space. LLVM optimized this
  ;; into a single `i64` load and store, instead
  ;; of two `i32` load and stores.
  local.get 0
  local.get 1
  i64.load offset=8
  i64.store align=4

  ;; Restore the stack pointer to the original
  ;; value it had upon entering this function,
  ;; deallocating our shadow stack frame.
  local.get 1
  i32.const 16
  i32.add
  global.set 0
  end
)

当调用者是 JavaScript 时， `wasm-bindgen` 可以使用它对这些调用约定的了解，生成 JavaScript 粘合代码，该代码分配影子堆栈空间，使用结构返回指针参数调用函数，从线性内存中读取值，最后在将 Wasm 值转换为一些 JavaScript 值之前，释放影子堆栈空间。

但是，当直接使用接口类型而不是为它们提供垫片时，我们不能依赖于生成可以访问 Wasm 模块线性内存的粘合代码。首先，内存可能不会被导出。其次，我们拥有的唯一粘合代码是接口适配器，而不是任意的 JavaScript 代码。我们希望这些值作为适当的返回值，而不是通过侧信道。

因此，我在 `wasm-bindgen` 中编写了一个 `walrus` 转换，它将使用结构返回指针参数但没有实际 Wasm 返回值的函数，转换为不使用结构返回指针参数但返回多个 Wasm 结果值的函数。这种转换本质上是多值函数的“逆垫片”。

;; Before.
;;
;; First parameter is a struct return pointer. No
;; return values, as they are stored through the
;; struct return pointer.
(func $make_pair (param i32 i32 i32)
  ;; ...
)

;; After.
;;
;; No more struct return pointer parameter. Return
;; values are actual Wasm results.
(func $make_pair (param i32 i32) (result i32 i32)
  ;; ...
)

该转换仅应用于使用结构返回指针参数的导出函数，并且不是在原地重写源函数，而是保留原始函数，但将其从 Wasm 模块的导出列表中删除。它会生成一个新函数，以替换 Wasm 模块的导出列表中的旧函数。这个新函数为返回值分配影子堆栈空间，调用原始函数，将值从影子堆栈读取到 Wasm 值堆栈上，最后在返回之前释放影子堆栈空间。

对于我们正在运行的 `make_pair` 示例，转换会生成一个导出包装函数，如下所示

;; pair.wasm

(func $new_make_pair (param i32 i32) (result i32 i32)
  ;; Our struct return pointer that points to the
  ;; scratch space we are allocating on the shadow
  ;; stack for calling `$make_pair`.
  (local i32)

  ;; Allocate space on the shadow stack for the
  ;; result.
  global.get $shadow_stack_pointer
  i32.const 8
  i32.sub
  local.tee 2
  global.set $shadow_stack_pointer

  ;; Call the original `$make_pair` with our
  ;; allocated shadow stack space for its
  ;; results.
  local.get 2
  local.get 0
  local.get 1
  call $make_pair

  ;; Read the return values out of the shadow
  ;; stack and place them onto the Wasm stack.
  local.get 2
  i32.load
  local.get 2
  i32.load offset=4

  ;; Finally, restore the shadow stack pointer.
  local.get 2
  i32.const 8
  i32.add
  global.set $shadow_stack_pointer
)

有了这种转换， `wasm-bindgen` 现在可以生成多值函数导出以及相关接口适配器，将具体的 Wasm 返回值提升为抽象的接口类型。

多值支持和转换是在以下拉取请求中在 `wasm-bindgen` 中实现的

• #1764：引入多值转换
• #1805：在面向接口类型时始终使用多值
• #1839：在多值转换后更新绑定元数据

Wasmtime 和 Cranelift

好的，所以现在我们可以使用 Rust 和 Wasm 工具链生成多值 Wasm 二进制文件——太棒了！但是现在我们需要能够运行这些二进制文件。

输入 Wasmtime，这是一个基于 Cranelift 代码生成器 构建的 WebAssembly 运行时。Wasmtime 使用 `cranelift-wasm` crate 将 WebAssembly 转换为 Cranelift 的 IR，然后 Cranelift 将 IR 编译为本机机器代码。

在 Wasmtime 和 Cranelift 中实现多值 Wasm 支持大致涉及两个步骤

1. 将多值 Wasm 转换为 Cranelift IR
2. 在 Cranelift 中支持任意数量的返回值

将多值 Wasm 转换为 Cranelift IR

Cranelift 有自己的中间表示，它会在为目标架构生成机器代码之前对其进行操作、优化和合法化。为了让 Cranelift 编译一些代码，你需要将你正在处理的内容转换为 Cranelift 的 IR。在我们的例子中，这意味着将 Wasm 转换为 Cranelift 的 IR。这个过程类似于 `rustc` 将其中间级中间表示 (MIR) 转换为 LLVM 的 IR。²

Cranelift 的 IR 由 (扩展) 基本块³ 组成，其中包含 单静态赋值形式 (SSA) 的代码。SSA，顾名思义，意味着变量只能在定义时被赋值，并且永远不会被重新赋值

;; `42 + 1337` in Cranelift IR
v0 = iconst.32 42
v1 = iconst.32 1337
v2 = iadd v0, v1

在转换为 SSA 形式时，大多数对变量 `x` 的重新赋值可以通过定义一个新的 `x1` 并将后续对 `x` 的使用替换为 `x1` 来处理，然后将下一个重新赋值转换为 `x2`，等等。但这对于控制流合并的点（例如，`if`/`else` 的结果和备选分支后面的块）不起作用。

考虑这段 Rust 代码，以及我们如何将其转换为 SSA。

let x;
if some_condition() {
    // This version of `x` becomes `x0` when
    // translated to SSA.
    x = foo();
} else {
    // This version of `x` becomes `x1` when
    // translated to SSA.
    x = bar();
}
// Does this use `x0` or `x1`??
do_stuff(x);

在转换为 SSA 时，底部的 `do_stuff` 调用应该使用 `x0` 还是 `x1`？两者都不！

SSA 使用 Φ (phi) 函数来处理这些情况。一个 phi 函数接受多个互斥的、控制流相关的参数，并返回定义了控制流来自哪个地方的那个参数。在我们的例子中，我们会有 `x2 = Φ(x0, x1)`，如果 `some_condition()` 为真，那么 `x2` 将从 `x0` 获取其值。否则，`x2` 将从 `x1` 获取其值。

如果您以前没接触过 SSA 和 phi 函数，并且感到困惑，不用担心！我第一次学习这些东西的时候也很困惑。但是 Cranelift IR 本身并不使用 phi 函数，它有一些我认为更直观的：块可以有形式参数。

将我们的示例转换为 Cranelift IR，我们得到以下结果。

;; Head of the `if`/`else`.
ebb0:
    v0 = call some_condition()
    brnz v0, ebb1
    jump ebb2

;; Consequent.
ebb1:
    v1 = call foo()
    jump ebb3(v1)

;; Alternative.
ebb2:
    v2 = call bar()
    jump ebb3(v2)

;; Code following the `if`/`else`.
ebb3(v3: i32):
    call do_stuff(v3)

请注意，`ebb3` 为我们应该传递给 `do_stuff` 的控制流相关值接受一个参数！并且 `ebb1` 和 `ebb2` 中的跳转会将它们在本地定义的值“传递到”`ebb3` 中！这等效于 phi 函数，但我认为它更直观。

无论如何，将 WebAssembly 代码转换为 Cranelift IR 在 `cranelift-wasm` crate 中完成。它使用 `wasmparser` 来解码给定的 Wasm 数据块并验证它，然后通过（您猜对了！）抽象解释来构建 Cranelift IR。当 `cranelift-wasm` 解释 Wasm 指令时，它会维护一个 Cranelift IR SSA 值堆栈，而不是压入和弹出 Wasm 值。当 `cranelift-wasm` 进入和退出 Wasm 控制帧时，它会创建 Cranelift IR 基本块。

这个过程与 `walrus` 的 IR 构造非常相似，后者与 `wasmparser` 的验证非常相似，现在整个过程感觉很熟悉。只是有一两个棘手的地方。

第一个棘手的地方是，要记住为 Wasm `loop` 的主体添加第一个基本块的参数（phi 函数），以表示其 Wasm 堆栈参数。这是必要的，因为控制流在循环主体顶部有两个地方合并：从我们第一次进入循环的地方，以及从我们完成一次迭代并开始另一次迭代的循环底部。在抽象解释方面，这意味着你需要弹出你在循环开始时堆栈上的特定 SSA 值，为循环的参数构建 SSA 值，然后将这些值压入堆栈。我最初忽略了这一点，导致大量头疼和调试错误翻译的 IR。哎呀！

第二，`cranelift-wasm` 将在转换过程中跟踪可达性，如果一些 Wasm 代码不可达，我们甚至不会费心为其构建 Cranelift IR。但不可达代码和可达代码之间的边界，以及一个从另一个转换到另一个的时间，可能有点微妙。你可以处于不可达状态，从当前块掉落到下一个块，然后再次变为可达。加入带有 `else` 的 `if`，没有 `else` 的 `if`，以及无条件分支，以及提前返回，很容易出现错误。在添加多值 Wasm 支持的过程中，错误确实潜入其中。这次涉及一个最初可达的 `if`，其结果分支也以可达结束，但其备选分支以不可达结束。鉴于此，结果分支和备选分支后面的块是否可达？是的，但我们错误地计算了它不应该可达。

为了修复这个错误，我重构了 `cranelift-wasm` 计算 `if` 后面代码的可达性的方式。现在它会正确地确定，如果 `if` 的头部可达，并且以下任何一个条件为真，则后面的块可达。

• 结果分支或备选分支以可达结束，在这种情况下它们将继续执行到后面的块。
• 结果分支或备选分支对后面的块进行提前分支（可能是有条件分支），并且该分支可达。
• 没有备选分支，因此如果 `if` 的条件为假，我们将直接进入后面的块。

为了确保我们正在正确处理所有这些边缘情况，我添加了测试，枚举了 `if` 分支的可达性以及提前分支的每种组合。呼！

最后，这个错误首先在 39 KiB 的 Wasm 文件中表现出来，而且 thanks to tools like wasm-reduce （它是 binaryen 的一部分）和 creduce （在 WAT 反汇编上工作，而不是二进制 Wasm），找出问题变得容易多了。我忘记这次用了哪一个，但我已经成功地将大型、复杂的 Wasm 测试用例变成了小型、孤立的测试用例，突出了手头的错误。这些工具是真正的救星，因此值得传播它们的存在，以防万一有人不知道它们！

将多值 Wasm 转换为 Cranelift IR 在以下 pull 请求中完成。

• #1049: 将多值 Wasm 转换为 Cranelift IR
• #1110: 在结果分支结束时正确跳转到目标块
• #1143: 修复 `if` 的可达性跟踪

在 Cranelift 中支持多个返回值

Cranelift IR 语言支持从函数返回任意多个值，但 Cranelift 实现只支持返回与函数正在使用的调用约定中可用的寄存器数量一样多的值。例如，在 System V 调用约定中，您可以返回最多三个指针大小的值，而在 Windows fastcall 调用约定中，您只能返回一个指针大小的值。

所以问题是

如何返回超过寄存器容量的值？

这应该会引起一些似曾相识的感觉：在编译到 Wasm 时，LLVM 如何返回大于单个 Wasm 值的大小？结构返回指针参数！这没什么新鲜事，事实上它的使用是由某些调用约定决定的，我们只是还没有在 Cranelift 中实现对它的支持。所以我着手去做这件事。

当 Cranelift 被提供一些初始的 IR 时，IR 通常是可移植的，并且与机器无关。当 IR 在 Cranelift 中移动时，最终会到达合法化阶段，在这个阶段，没有与目标架构中的机器代码指令直接映射的指令会被替换为具有直接映射的指令。例如，在 32 位 x86 上，Cranelift 通过将其扩展为一系列 32 位操作来合法化 64 位算术。在这个过程中，我们还会合法化函数签名：传递大于寄存器容量的值可能需要拆分成多个参数，每个参数都可以放入寄存器中，例如。签名合法化还会根据函数的调用约定为形式参数分配位置：这个参数应该在这个寄存器中，那个参数应该在这个堆栈偏移量处，等等。

我通过结构返回指针参数实现任意数量的返回值的计划是，在签名合法化期间挂钩到 Cranelift 的合法化阶段，合法化 `return` 指令和合法化 `call` 指令。

在合法化签名时，我们需要确定是否需要结构返回指针，如果是，则更新签名以反映这一点。

;; Before legalization.
fn() -> i64, i64, i64, i64 fast

;; After legalization.
fn (v0: i64 sret [%rdi]) -> i64 sret [%rax] fast

这里，`fast` 表示签名使用我们内部的不稳定的“fast”调用约定。`sret` 是参数或返回值的注释，在本例中，它记录着它被用作结构返回指针。`%rdi` 和 `%rax` 是调用约定为参数和返回值分配的寄存器。⁴

合法化后，我们添加了结构返回指针参数，但我们也删除了旧的返回值，并且我们还返回结构返回指针参数。返回结构返回指针是 System V ABI 调用约定所要求的，但我们目前对我们内部的不稳定的调用约定也是这样做的。

签名合法化后，我们还需要合法化 `call` 和 `return` 指令，以便它们与新的合法化签名相匹配。让我们先关注后者。

合法化 `return` 指令会从 `return` 指令本身中删除返回值，并创建一系列在结构返回指针中写入返回值的先行 `store` 指令。以下是一个返回四个 `i32` 值的示例。

;; Before legalization.
ebb0:
    ;; ...
    return v0, v1, v2, v3

;; After legalization.
ebb0(v4: i64):
    ;; ...
    store notrap aligned v0, v4
    store notrap aligned v1, v4+4
    store notrap aligned v2, v4+8
    store notrap aligned v3, v4+12
    return v4

新的 `v4` 值是结构返回指针参数。`store` 指令上的 `notrap` 注释表示此存储不能触发陷阱。调用者有责任为我们提供一个有效的结构返回指针，该指针指向足够的空间以容纳我们所有的返回值。`aligned` 注释类似，表示我们正在存储的指针对于 `i32` 是正确对齐的（四字节对齐）。同样，调用者有责任确保结构返回指针至少具有返回值类型所需的最高对齐方式。`+4`、`+8` 和 `+12` 是静态立即数，它们指定要添加到实际 `v4` 操作数的偏移量，以计算存储的目标地址。

合法化 `call` 指令的责任与合法化 `return` 指令相比要多得多。是的，它涉及将结构返回指针参数添加到 `call` 指令本身，然后在被调用者返回给我们后从结构返回空间中加载值。但它还必须在调用者函数的堆栈帧中分配结构返回的空间，并且它必须确保被调用者及其 `return` 指令依赖的大小和对齐不变式得到维护。

让我们看一个调用者函数调用返回四个 `i32` 的被调用者函数的示例。

;; Before legalization.
function %caller() {
    fn0 = colocated %callee() -> i32, i32, i32, i32

ebb0:
    v0, v1, v2, v3 = call fn0()
    return
}

;; After legalization.
function %caller() {
    ss0 = sret_slot 16
    sig0 = (i64 sret [%rdi]) -> i64 sret [%rax] fast
    fn0 = colocated %callee sig0

ebb0:
    v4 = stack_addr.i64 ss0
    v5 = call fn0(v4)
    v6 = load.i32 notrap aligned v5
    v0 -> v6
    v7 = load.i32 notrap aligned v5+4
    v1 -> v7
    v8 = load.i32 notrap aligned v5+8
    v2 -> v8
    v9 = load.i32 notrap aligned v5+12
    v3 -> v9
    return
}

ss0 = sret_slot 16 是我们为结构返回空间创建的十六字节堆栈槽。它也对齐到十六字节，在这种情况下比必要的大，因为我们只需要对 `i32` 进行四字节对齐。与合法化的 `return` 中的 `store` 类似，合法化的 `call` 中的 `load` 也用 `notrap` 和 `aligned` 进行注释。`v0 -> v6` 确定 `v0` 是 `v6` 的另一个名称，我们不必急于将所有后续对 `v0` 的使用重写为对 `v6` 的使用（即使在本例中没有这样的使用）。

随着签名、call 和 return 的合法化，所有模块都理解了何时以及如何使用结构返回指针，现在我们在 Cranelift 和 Wasmtime 中完全支持任意数量的多值返回值。此支持在以下拉取请求中实现

• #1147：支持使用结构返回指针的多值返回
• #1213：legalize_signatures：乐观地尝试将寄存器位置分配给返回值；回溯以使用结构返回指针参数

综合起来

最后，让我们将所有内容整合在一起，使用 Rust 和 Wasm 工具链创建一个多值 Wasm 二进制文件，然后在 Wasmtime 中运行它！

首先，让我们使用 cargo 创建一个新的库包

$ cargo new --lib hello-multi-value
Created library `hello-multi-value` package
$ cd hello-multi-value/

我们将使用 wasm-bindgen 从我们的 Wasm 函数返回一个字符串，所以让我们将其添加为依赖项。此外，我们将创建一个 Wasm 库，而不是可执行文件，所以指定这是一个“cdylib”

# Cargo.toml

[lib]
crate-type = ["cdylib"]

[dependencies]
wasm-bindgen = "0.2.54"

让我们用我们的字符串返回函数填充 src/lib.rs

use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn hello(name: &str) -> String {
    format!("Hello, {}!", name)
}

我们可以使用 cargo wasi 构建我们的 Wasm 库

$ cargo wasi build --release

这将自动为 wasm32-wasi 目标构建一个 Wasm 文件，然后运行 wasm-bindgen 的后处理器添加接口类型并引入多值。我们可以使用来自 WABT 的 wasm-objdump 工具来验证这一点

$ wasm-objdump -x \
    target/wasm32-wasi/release/hello_multi_value.wasm
hello_multi_value.wasm: file format wasm 0x1

Section Details:

Type[14]:
...
- type[6] (i32, i32) -> (i32, i32)
...

Function[151]:
...
- func[93] sig=6
...

Export[5]:
- func[93] -> "hello"
...

我们可以看到该函数被导出为 "hello" 并且它具有多值类型 (i32, i32) -> (i32, i32)。这个垫片函数确实是我们在 wasm-bindgen 中添加的多值转换引入的，用于包装原始函数并将它的结构返回指针转换为多值。

最后，我们可以将这个 Wasm 库加载到 Wasmtime 中，Wasmtime 将使用 Cranelift 对其进行即时 (JIT) 编译到机器码，然后使用字符串 "multi-value Wasm" 调用 hello 导出

$ wasmtime \
    target/wasm32-wasi/release/hello_multi_value.wasm \
    --invoke hello "multi-value Wasm"
Hello, multi-value Wasm!

它可以工作！！

结论

Rust 和 WebAssembly 工具链现在支持生成利用多值提案的 Wasm 二进制文件，而 Cranelift 和 Wasmtime 可以编译和运行多值 Wasm 二进制文件。我希望这 ——— 这是一个通过整个垂直生态系统实现 Wasm 特性的有趣故事，从头到尾。

最后，并且绝对不是最不重要的，我要感谢 Dan Gohman、Benjamin Bouvier、Alex Crichton、Yury Delendik、@bjorn3 和 @iximeow 在这个旅程的不同阶段为不同的部分提供了审查和实施建议。此外，再次感谢 Alex 和 Dan，以及 Lin Clark 和 Till Schneidereit 对本文早期草稿提供的所有反馈。

⁰ 此外，Thomas Lively 和其他一些人已经在努力将多值 Wasm 支持直接添加到 LLVM 中，所以这在将来肯定会实现，而我将注意力集中在其他方面是有意义的。 ↩

¹ 有些“堆栈式”形式并不完全直接映射到树。例如，您可以在表达式树的后序编码的任何部分的中间插入堆栈中性的、有副作用的指令序列。这里有一个生成一些值的 call，后面跟着一个 drop，它丢弃该值，插入到 1 + 2 的后序编码的中间

;; Instructions ;; Stack
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
i32.const 1     ;; [1]
call $foo       ;; [1, $result_of_foo]
drop            ;; [1]
i32.const 2     ;; [1, 2]
i32.add         ;; [3]

这些堆栈式形式可以通过引入不为控制流分支引入标签的块来表示。您可以将它们视为与 Common Lisp 的 progn 和 prog0 形式或 Scheme 的 (begin ...) 类似。 ↩

² 有趣的事实：目前也正在进行工作，使 Cranelift 成为 rustc 的一个可行的替代后端！请参阅 目标概述 和 bjorn3/rustc_codegen_cranelift 存储库了解详细信息。 ↩

³ 最初，Cranelift 被设计为使用扩展基本块，而不是常规基本块。两者都只能从它们的头部进入，但基本块还只能从它们的尾部退出，而扩展基本块可以在它们的中间从块中进行条件退出。这个想法是扩展基本块更直接地匹配机器码，该机器码会通过未执行的条件分支继续执行下一条指令。但是，Cranelift 正在切换到常规基本块，并删除对扩展基本块的支持。这样做的原因是所有优化流程最终都会基本上构造并跟踪基本块，这增加了复杂性，而扩展基本块最终并没有起到作用。 ↩

⁴ 有点令人困惑的是，方括号只是 Cranelift 决定用来包围参数位置的语法，它们不代表像在 Intel 风格的汇编语法中那样取消引用。 ↩