wasm/core/
sidetable.rs

1//! This module contains a data structure to allow in-place interpretation
2//!
3//! Control-flow in WASM is denoted in labels. To avoid linear search through the WASM binary or
4//! stack for the respective label of a branch, a sidetable is generated during validation, which
5//! stores the offset on the current instruction pointer for the branch. A sidetable entry hence
6//! allows to translate the implicit control flow information ("jump to the next `else`") to
7//! explicit modifications of the instruction pointer (`instruction_pointer += 13`).
8//!
9//! Branches in WASM can only go outwards, they either `break` out of a block or `continue` to the
10//! head of a loob block. Put differently, a label can only be referenced from within its
11//! associated structured control instruction.
12//!
13//! Noteworthy, branching can also have side-effects on the operand stack:
14//!
15//! - Taking a branch unwinds the operand stack, down to where the targeted structured control flow
16//!   instruction was entered. [`SidetableEntry::popcnt`] holds information on how many values to
17//!   pop from the operand stack when a branch is taken.
18//! - When a branch is taken, it may consume arguments from the operand stack. These are pushed
19//!   back on the operand stack after unwinding. This behavior can be emulated by copying the
20//!   uppermost [`SidetableEntry::valcnt`] operands on the operand stack before taking a branch
21//!   into a structured control instruction.
22//!
23//! # Reference
24//!
25//! - Core / Syntax / Instructions / Control Instructions, WASM Spec,
26//!   <https://webassembly.github.io/spec/core/syntax/instructions.html#control-instructions>
27//! - "A fast in-place interpreter for WebAssembly", Ben L. Titzer,
28//!   <https://arxiv.org/abs/2205.01183>
29
30use alloc::vec::Vec;
31
32// A sidetable
33
34pub type Sidetable = Vec<SidetableEntry>;
35
36/// Entry to translate the current branches implicit target into an explicit offset to the instruction pointer, as well as the side table pointer
37///
38/// Each of the following constructs requires a [`SidetableEntry`]:
39///
40/// - br
41/// - br_if
42/// - br_table
43/// - else
44// TODO hide implementation
45// TODO Remove Clone trait from sidetables
46#[derive(Debug, Clone)]
47pub struct SidetableEntry {
48    /// Δpc: the amount to adjust the instruction pointer by if the branch is taken
49    pub delta_pc: isize,
50
51    /// Δstp: the amount to adjust the side-table index by if the branch is taken
52    pub delta_stp: isize,
53
54    /// valcnt: the number of values that will be copied if the branch is taken
55    ///
56    /// Branches may additionally consume operands themselves, which they push back on the operand
57    /// stack after unwinding.
58    pub valcnt: usize,
59
60    /// popcnt: the number of values that will be popped if the branch is taken
61    ///
62    /// Taking a branch unwinds the operand stack down to the height where the targeted structured
63    /// control instruction was entered.
64    pub popcnt: usize,
65}
wasm/core/sidetable.rs

wasm/core/
sidetable.rs
