walrus 0.8.0

//! Intermediate representation for expressions.
//!
//! The goal is to match wasm instructions as closely as possible, but translate
//! the stack machine into an expression tree. Additionally all control frames
//! are representd as `Block`s.

pub mod matcher;

use crate::dot::Dot;
use crate::encode::Encoder;
use crate::module::{DisplayExpr, DotExpr};
use crate::{DataId, FunctionId, GlobalId, MemoryId, TableId, TypeId, ValType};
use id_arena::Id;
use std::fmt;
use std::mem;
use walrus_macro::walrus_expr;

/// The id of a local.
pub type LocalId = Id<Local>;

/// A local variable or parameter.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Local {
    id: LocalId,
    ty: ValType,
    /// A human-readable name for this local, often useful when debugging
    pub name: Option<String>,
}

impl Local {
    /// Construct a new local from the given id and type.
    pub fn new(id: LocalId, ty: ValType) -> Local {
        Local { id, ty, name: None }
    }

    /// Get this local's id that is unique across the whole module.
    pub fn id(&self) -> LocalId {
        self.id
    }

    /// Get this local's type.
    pub fn ty(&self) -> ValType {
        self.ty
    }
}

/// An identifier for a particular expression.
pub type ExprId = Id<Expr>;

impl Dot for ExprId {
    fn dot(&self, out: &mut String) {
        out.push_str(&format!("expr_{}", self.index()))
    }
}

/// A trait for anything that is an AST node in our IR.
///
/// Implementations of this trait are generated by `#[walrus_expr]`.
pub trait Ast: Into<Expr> {
    /// The identifier type for this AST node.
    type Id: Into<ExprId>;

    /// Create a new identifier given an `ExprId` that references an `Expr` of
    /// this type.
    fn new_id(id: ExprId) -> Self::Id;
}

/// Different kinds of blocks.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum BlockKind {
    /// A `block` block.
    Block,

    /// A `loop` block.
    Loop,

    /// An `if` or `else` block.
    IfElse,

    /// The entry to a function.
    FunctionEntry,
}

/// An enum of all the different kinds of wasm expressions.
///
/// Note that the `#[walrus_expr]` macro rewrites this enum's variants from
///
/// ```ignore
/// enum Expr {
///     Variant { field: Ty, .. },
///     ...
/// }
/// ```
///
/// into
///
/// ```ignore
/// enum Expr {
///     Variant(Variant),
///     ...
/// }
///
/// struct Variant {
///     field: Ty,
///     ...
/// }
/// ```
#[walrus_expr]
#[derive(Clone, Debug)]
pub enum Expr {
    /// A block of multiple expressions, and also a control frame.
    #[walrus(display_name = display_block_name, dot_name = dot_block_name)]
    Block {
        /// What kind of block is this?
        #[walrus(skip_visit)] // nothing to recurse
        kind: BlockKind,
        /// The types of the expected values on the stack when entering this
        /// block.
        #[walrus(skip_visit)] // nothing to recurse
        params: Box<[ValType]>,
        /// The types of the resulting values added to the stack after this
        /// block is evaluated.
        #[walrus(skip_visit)] // nothing to recurse
        results: Box<[ValType]>,
        /// The expressions that make up the body of this block.
        exprs: Vec<ExprId>,
    },

    /// `call`
    Call {
        /// The function being invoked.
        func: FunctionId,
        /// The arguments to the function.
        args: Box<[ExprId]>,
    },

    /// `call_indirect`
    CallIndirect {
        /// The type signature of the function we're calling
        ty: TypeId,
        /// The table which `func` below is indexing into
        table: TableId,
        /// The index of the function we're invoking
        func: ExprId,
        /// The arguments to the function.
        args: Box<[ExprId]>,
    },

    /// `local.get n`
    LocalGet {
        /// The local being got.
        local: LocalId,
    },

    /// `local.set n`
    LocalSet {
        /// The local being set.
        local: LocalId,
        /// The value to set the local to.
        value: ExprId,
    },

    /// `local.tee n`
    LocalTee {
        /// The local being set.
        local: LocalId,
        /// The value to set the local to and return.
        value: ExprId,
    },

    /// `global.get n`
    GlobalGet {
        /// The global being got.
        global: GlobalId,
    },

    /// `global.set n`
    GlobalSet {
        /// The global being set.
        global: GlobalId,
        /// The value to set the global to.
        value: ExprId,
    },

    /// `*.const`
    Const {
        /// The constant value.
        value: Value,
    },

    /// Binary operations, those requiring two operands
    #[walrus(display_name = display_binop_name, dot_name = dot_binop_name)]
    Binop {
        /// The operation being performed
        #[walrus(skip_visit)]
        op: BinaryOp,
        /// The left-hand operand
        lhs: ExprId,
        /// The right-hand operand
        rhs: ExprId,
    },

    /// Unary operations, those requiring one operand
    #[walrus(display_name = display_unop_name, dot_name = dot_unop_name)]
    Unop {
        /// The operation being performed
        #[walrus(skip_visit)]
        op: UnaryOp,
        /// The input operand
        expr: ExprId,
    },

    /// `select`
    Select {
        /// The condition.
        condition: ExprId,
        /// The value returned when the condition is true. Evaluated regardless
        /// if the condition is true.
        consequent: ExprId,
        /// The value returned when the condition is false. Evaluated regardless
        /// if the condition is false.
        alternative: ExprId,
    },

    /// `unreachable`
    Unreachable {},

    /// `br`
    #[walrus(display_extra = display_br)]
    Br {
        /// The target block to branch to.
        #[walrus(skip_visit)] // should have already been visited
        block: BlockId,
        /// The arguments to the block.
        args: Box<[ExprId]>,
    },

    /// `br_if`
    #[walrus(display_extra = display_br_if)]
    BrIf {
        /// The condition for when to branch.
        condition: ExprId,
        /// The target block to branch to when the condition is met.
        #[walrus(skip_visit)] // should have already been visited
        block: BlockId,
        /// The arguments to the block.
        args: Box<[ExprId]>,
    },

    /// `if ... else ... end`
    IfElse {
        /// The condition.
        condition: ExprId,
        /// The block to execute when the condition is true.
        consequent: BlockId,
        /// The block to execute when the condition is false.
        alternative: BlockId,
    },

    /// `br_table`
    #[walrus(display_extra = display_br_table)]
    BrTable {
        /// The table index of which block to branch to.
        which: ExprId,
        /// The table of target blocks.
        #[walrus(skip_visit)] // should have already been visited
        blocks: Box<[BlockId]>,
        /// The block that is branched to by default when `which` is out of the
        /// table's bounds.
        #[walrus(skip_visit)] // should have already been visited
        default: BlockId,
        /// The arguments to the block.
        args: Box<[ExprId]>,
    },

    /// `drop`
    Drop {
        /// The expression to be evaluated and results ignored.
        expr: ExprId,
    },

    /// `return`
    Return {
        /// The values being returned.
        values: Box<[ExprId]>,
    },

    /// memory.size
    MemorySize {
        /// The memory we're fetching the current size of.
        memory: MemoryId,
    },

    /// memory.grow
    MemoryGrow {
        /// The memory we're growing.
        memory: MemoryId,
        /// The number of pages to grow by.
        pages: ExprId,
    },

    /// memory.init
    MemoryInit {
        /// The memory we're growing.
        memory: MemoryId,
        /// The data to copy in
        data: DataId,
        /// The offset in bytes in memory
        memory_offset: ExprId,
        /// The offset in bytes in the data
        data_offset: ExprId,
        /// The number of bytes to copy
        len: ExprId,
    },

    /// data.drop
    DataDrop {
        /// The data to drop
        data: DataId,
    },

    /// memory.copy
    MemoryCopy {
        /// The source memory
        src: MemoryId,
        /// The destination memory
        dst: MemoryId,
        /// The offset in the destination memory
        dst_offset: ExprId,
        /// The offset in the source memory
        src_offset: ExprId,
        /// The number of bytes to copy
        len: ExprId,
    },

    /// memory.fill
    MemoryFill {
        /// The memory to fill
        memory: MemoryId,
        /// The offset in memory to start filling
        offset: ExprId,
        /// The value to fill
        value: ExprId,
        /// The number of bytes to fill in
        len: ExprId,
    },

    /// Loading a value from memory
    Load {
        /// The memory we're loading from.
        memory: MemoryId,
        /// The kind of memory load this is performing
        #[walrus(skip_visit)]
        kind: LoadKind,
        /// The alignment and offset of this memory load
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address that we're loading from
        address: ExprId,
    },

    /// Storing a value to memory
    Store {
        /// The memory we're storing to
        memory: MemoryId,
        /// The kind of memory store this is performing
        #[walrus(skip_visit)]
        kind: StoreKind,
        /// The alignment and offset of this memory store
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address that we're storing to
        address: ExprId,
        /// The value that we're storing
        value: ExprId,
    },

    /// An atomic read/modify/write operation
    AtomicRmw {
        /// The memory we're modifying
        memory: MemoryId,
        /// The atomic operation being performed
        #[walrus(skip_visit)]
        op: AtomicOp,
        /// The atomic operation being performed
        #[walrus(skip_visit)]
        width: AtomicWidth,
        /// The alignment and offset from the base address
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address at which to perform the operation
        address: ExprId,
        /// The value that's being used to modify what's at the address
        value: ExprId,
    },

    /// An atomic compare exchange operation
    Cmpxchg {
        /// The memory we're modifying
        memory: MemoryId,
        /// The atomic operation being performed
        #[walrus(skip_visit)]
        width: AtomicWidth,
        /// The alignment and offset from the base address
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address at which to perform the operation
        address: ExprId,
        /// The value that's being used to modify what's at the address
        expected: ExprId,
        /// The value that's being used to modify what's at the address
        replacement: ExprId,
    },

    /// The `atomic.notify` instruction to wake up threads
    AtomicNotify {
        /// The memory we're notifying through
        memory: MemoryId,
        /// The alignment and offset from the base address
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address at which to perform the operation
        address: ExprId,
        /// The number of threads to wake up
        count: ExprId,
    },

    /// The `*.atomic.wait` instruction to block threads
    AtomicWait {
        /// The memory we're waiting through
        memory: MemoryId,
        /// The alignment and offset from the base address
        #[walrus(skip_visit)]
        arg: MemArg,
        /// The address at which to perform the operation
        address: ExprId,
        /// The expected value at the address above
        expected: ExprId,
        /// The timeout, in nanoseconds, of this wait
        timeout: ExprId,
        /// Whether or not this is an i32 or i64 wait
        #[walrus(skip_visit)]
        sixty_four: bool,
    },

    /// A value followed by one or more stack-neutral, side-effecting
    /// expressions.
    ///
    /// This allows us to express "stacky" and "non-tree-like" expressions such
    /// as:
    ///
    /// ```wasm
    /// ;; Assuming `f` has type `[] -> i32` and potential side effects.
    /// call $f
    /// call $f
    /// call $f
    /// drop
    /// i32.add
    /// ```
    ///
    /// Without `WithSideEffects`, we would need to create a synthetic block
    /// with a temporary local like this:
    ///
    /// ```wasm
    /// (i32.added
    ///   (call $f)
    ///   (block
    ///     (set_local $temp (call $f))
    ///     (drop (call $f))
    ///     (get_local $temp)
    ///   end))
    /// ```
    ///
    /// But using `WithoutSideEffects` we can represent this like so:
    ///
    /// ```wasm
    /// (i32.add
    ///   (with_side_effects
    ///     ;; value
    ///     (call $f)
    ///     ;; side_effects
    ///     (drop (call $f)))
    ///   (call $f))
    /// ```
    WithSideEffects {
        /// The stack-neutral, side-effecting operations before `value`
        before: Vec<ExprId>,
        /// The value.
        value: ExprId,
        /// The stack-neutral, side-effecting operations after `value`
        after: Vec<ExprId>,
    },

    /// table.get
    TableGet {
        /// The table we're fetching from
        table: TableId,
        /// The table index to get
        index: ExprId,
    },

    /// table.set
    TableSet {
        /// The table we're storing to
        table: TableId,
        /// The table index to set
        index: ExprId,
        /// The value we're storing
        value: ExprId,
    },

    /// table.grow
    TableGrow {
        /// The table we're growing
        table: TableId,
        /// The amount we're growing by
        amount: ExprId,
        /// The value to store in all new slots
        value: ExprId,
    },

    /// table.size
    TableSize {
        /// The table we're getting the size of
        table: TableId,
    },

    /// ref.null
    RefNull {},

    /// ref.is_null
    RefIsNull {
        /// The reference that we're testing
        value: ExprId,
    },

    /// `v128.bitselect`
    V128Bitselect {
        /// The bit mask selecting bits from the two operands.
        mask: ExprId,
        /// Operand where bits are selected from if the `mask` bit is 1
        v1: ExprId,
        /// Operand where bits are selected from if the `mask` bit is 0c:w
        v2: ExprId,
    },

    /// `v128.shuffle`
    V128Shuffle {
        /// The indices that are used to create the final vector of this
        /// expression
        #[walrus(skip_visit)]
        indices: ShuffleIndices,
        /// The first 16 bytes to be indxed (with indices 0..15)
        lo: ExprId,
        /// The second 16 bytes to be indxed (with indices 16..31)
        hi: ExprId,
    },
}

/// Argument in `V128Shuffle` of lane indices to select
pub type ShuffleIndices = [u8; 16];

/// Constant values that can show up in WebAssembly
#[derive(Debug, Clone, Copy)]
pub enum Value {
    /// A constant 32-bit integer
    I32(i32),
    /// A constant 64-bit integer
    I64(i64),
    /// A constant 32-bit float
    F32(f32),
    /// A constant 64-bit float
    F64(f64),
    /// A constant 128-bit vector register
    V128(u128),
}

impl Value {
    pub(crate) fn emit(&self, encoder: &mut Encoder) {
        match *self {
            Value::I32(n) => {
                encoder.byte(0x41); // i32.const
                encoder.i32(n);
            }
            Value::I64(n) => {
                encoder.byte(0x42); // i64.const
                encoder.i64(n);
            }
            Value::F32(n) => {
                encoder.byte(0x43); // f32.const
                encoder.f32(n);
            }
            Value::F64(n) => {
                encoder.byte(0x44); // f64.const
                encoder.f64(n);
            }
            Value::V128(n) => {
                encoder.raw(&[0xfd, 0x02]); // v128.const
                for i in 0..16 {
                    encoder.byte((n >> (i * 8)) as u8);
                }
            }
        }
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Value::I32(i) => i.fmt(f),
            Value::I64(i) => i.fmt(f),
            Value::F32(i) => i.fmt(f),
            Value::F64(i) => i.fmt(f),
            Value::V128(i) => i.fmt(f),
        }
    }
}

/// Possible binary operations in wasm
#[allow(missing_docs)]
#[derive(Copy, Clone, Debug)]
pub enum BinaryOp {
    I32Eq,
    I32Ne,
    I32LtS,
    I32LtU,
    I32GtS,
    I32GtU,
    I32LeS,
    I32LeU,
    I32GeS,
    I32GeU,

    I64Eq,
    I64Ne,
    I64LtS,
    I64LtU,
    I64GtS,
    I64GtU,
    I64LeS,
    I64LeU,
    I64GeS,
    I64GeU,

    F32Eq,
    F32Ne,
    F32Lt,
    F32Gt,
    F32Le,
    F32Ge,

    F64Eq,
    F64Ne,
    F64Lt,
    F64Gt,
    F64Le,
    F64Ge,

    I32Add,
    I32Sub,
    I32Mul,
    I32DivS,
    I32DivU,
    I32RemS,
    I32RemU,
    I32And,
    I32Or,
    I32Xor,
    I32Shl,
    I32ShrS,
    I32ShrU,
    I32Rotl,
    I32Rotr,

    I64Add,
    I64Sub,
    I64Mul,
    I64DivS,
    I64DivU,
    I64RemS,
    I64RemU,
    I64And,
    I64Or,
    I64Xor,
    I64Shl,
    I64ShrS,
    I64ShrU,
    I64Rotl,
    I64Rotr,

    F32Add,
    F32Sub,
    F32Mul,
    F32Div,
    F32Min,
    F32Max,
    F32Copysign,

    F64Add,
    F64Sub,
    F64Mul,
    F64Div,
    F64Min,
    F64Max,
    F64Copysign,

    I8x16ReplaceLane { idx: u8 },
    I16x8ReplaceLane { idx: u8 },
    I32x4ReplaceLane { idx: u8 },
    I64x2ReplaceLane { idx: u8 },
    F32x4ReplaceLane { idx: u8 },
    F64x2ReplaceLane { idx: u8 },

    I8x16Eq,
    I8x16Ne,
    I8x16LtS,
    I8x16LtU,
    I8x16GtS,
    I8x16GtU,
    I8x16LeS,
    I8x16LeU,
    I8x16GeS,
    I8x16GeU,

    I16x8Eq,
    I16x8Ne,
    I16x8LtS,
    I16x8LtU,
    I16x8GtS,
    I16x8GtU,
    I16x8LeS,
    I16x8LeU,
    I16x8GeS,
    I16x8GeU,

    I32x4Eq,
    I32x4Ne,
    I32x4LtS,
    I32x4LtU,
    I32x4GtS,
    I32x4GtU,
    I32x4LeS,
    I32x4LeU,
    I32x4GeS,
    I32x4GeU,

    F32x4Eq,
    F32x4Ne,
    F32x4Lt,
    F32x4Gt,
    F32x4Le,
    F32x4Ge,

    F64x2Eq,
    F64x2Ne,
    F64x2Lt,
    F64x2Gt,
    F64x2Le,
    F64x2Ge,

    V128And,
    V128Or,
    V128Xor,

    I8x16Shl,
    I8x16ShrS,
    I8x16ShrU,
    I8x16Add,
    I8x16AddSaturateS,
    I8x16AddSaturateU,
    I8x16Sub,
    I8x16SubSaturateS,
    I8x16SubSaturateU,
    I8x16Mul,
    I16x8Shl,
    I16x8ShrS,
    I16x8ShrU,
    I16x8Add,
    I16x8AddSaturateS,
    I16x8AddSaturateU,
    I16x8Sub,
    I16x8SubSaturateS,
    I16x8SubSaturateU,
    I16x8Mul,
    I32x4Shl,
    I32x4ShrS,
    I32x4ShrU,
    I32x4Add,
    I32x4Sub,
    I32x4Mul,
    I64x2Shl,
    I64x2ShrS,
    I64x2ShrU,
    I64x2Add,
    I64x2Sub,

    F32x4Add,
    F32x4Sub,
    F32x4Mul,
    F32x4Div,
    F32x4Min,
    F32x4Max,
    F64x2Add,
    F64x2Sub,
    F64x2Mul,
    F64x2Div,
    F64x2Min,
    F64x2Max,
}

/// Possible unary operations in wasm
#[allow(missing_docs)]
#[derive(Copy, Clone, Debug)]
pub enum UnaryOp {
    I32Eqz,
    I32Clz,
    I32Ctz,
    I32Popcnt,

    I64Eqz,
    I64Clz,
    I64Ctz,
    I64Popcnt,

    F32Abs,
    F32Neg,
    F32Ceil,
    F32Floor,
    F32Trunc,
    F32Nearest,
    F32Sqrt,

    F64Abs,
    F64Neg,
    F64Ceil,
    F64Floor,
    F64Trunc,
    F64Nearest,
    F64Sqrt,

    I32WrapI64,
    I32TruncSF32,
    I32TruncUF32,
    I32TruncSF64,
    I32TruncUF64,
    I64ExtendSI32,
    I64ExtendUI32,
    I64TruncSF32,
    I64TruncUF32,
    I64TruncSF64,
    I64TruncUF64,

    F32ConvertSI32,
    F32ConvertUI32,
    F32ConvertSI64,
    F32ConvertUI64,
    F32DemoteF64,
    F64ConvertSI32,
    F64ConvertUI32,
    F64ConvertSI64,
    F64ConvertUI64,
    F64PromoteF32,

    I32ReinterpretF32,
    I64ReinterpretF64,
    F32ReinterpretI32,
    F64ReinterpretI64,

    I32Extend8S,
    I32Extend16S,
    I64Extend8S,
    I64Extend16S,
    I64Extend32S,

    I8x16Splat,
    I8x16ExtractLaneS { idx: u8 },
    I8x16ExtractLaneU { idx: u8 },
    I16x8Splat,
    I16x8ExtractLaneS { idx: u8 },
    I16x8ExtractLaneU { idx: u8 },
    I32x4Splat,
    I32x4ExtractLane { idx: u8 },
    I64x2Splat,
    I64x2ExtractLane { idx: u8 },
    F32x4Splat,
    F32x4ExtractLane { idx: u8 },
    F64x2Splat,
    F64x2ExtractLane { idx: u8 },

    V128Not,

    I8x16Neg,
    I8x16AnyTrue,
    I8x16AllTrue,
    I16x8Neg,
    I16x8AnyTrue,
    I16x8AllTrue,
    I32x4Neg,
    I32x4AnyTrue,
    I32x4AllTrue,
    I64x2Neg,
    I64x2AnyTrue,
    I64x2AllTrue,

    F32x4Abs,
    F32x4Neg,
    F32x4Sqrt,
    F64x2Abs,
    F64x2Neg,
    F64x2Sqrt,

    I32x4TruncSF32x4Sat,
    I32x4TruncUF32x4Sat,
    I64x2TruncSF64x2Sat,
    I64x2TruncUF64x2Sat,
    F32x4ConvertSI32x4,
    F32x4ConvertUI32x4,
    F64x2ConvertSI64x2,
    F64x2ConvertUI64x2,

    I32TruncSSatF32,
    I32TruncUSatF32,
    I32TruncSSatF64,
    I32TruncUSatF64,
    I64TruncSSatF32,
    I64TruncUSatF32,
    I64TruncSSatF64,
    I64TruncUSatF64,
}

/// The different kinds of load instructions that are part of a `Load` IR node
#[derive(Debug, Copy, Clone)]
#[allow(missing_docs)]
pub enum LoadKind {
    // TODO: much of this is probably redundant with type information already
    // ambiently available, we probably want to trim this down to just "value"
    // and then maybe some sign extensions. We'd then use the type of the node
    // to figure out what kind of store it actually is.
    I32 { atomic: bool },
    I64 { atomic: bool },
    F32,
    F64,
    V128,
    I32_8 { kind: ExtendedLoad },
    I32_16 { kind: ExtendedLoad },
    I64_8 { kind: ExtendedLoad },
    I64_16 { kind: ExtendedLoad },
    I64_32 { kind: ExtendedLoad },
}

/// The kinds of extended loads which can happen
#[derive(Debug, Copy, Clone)]
#[allow(missing_docs)]
pub enum ExtendedLoad {
    SignExtend,
    ZeroExtend,
    ZeroExtendAtomic,
}

impl LoadKind {
    /// Returns the number of bytes loaded
    pub fn width(&self) -> u32 {
        use self::LoadKind::*;
        match self {
            I32_8 { .. } | I64_8 { .. } => 1,
            I32_16 { .. } | I64_16 { .. } => 2,
            I32 { .. } | F32 | I64_32 { .. } => 4,
            I64 { .. } | F64 => 8,
            V128 => 16,
        }
    }

    /// Returns if this is an atomic load
    pub fn atomic(&self) -> bool {
        use self::LoadKind::*;
        match self {
            I32_8 { kind }
            | I32_16 { kind }
            | I64_8 { kind }
            | I64_16 { kind }
            | I64_32 { kind } => kind.atomic(),
            I32 { atomic } | I64 { atomic } => *atomic,
            F32 | F64 | V128 => false,
        }
    }
}

impl ExtendedLoad {
    /// Returns whether this is an atomic extended load
    pub fn atomic(&self) -> bool {
        match self {
            ExtendedLoad::SignExtend | ExtendedLoad::ZeroExtend => false,
            ExtendedLoad::ZeroExtendAtomic => true,
        }
    }
}

/// The different kinds of store instructions that are part of a `Store` IR node
#[derive(Debug, Copy, Clone)]
#[allow(missing_docs)]
pub enum StoreKind {
    I32 { atomic: bool },
    I64 { atomic: bool },
    F32,
    F64,
    V128,
    I32_8 { atomic: bool },
    I32_16 { atomic: bool },
    I64_8 { atomic: bool },
    I64_16 { atomic: bool },
    I64_32 { atomic: bool },
}

impl StoreKind {
    /// Returns the number of bytes stored
    pub fn width(&self) -> u32 {
        use self::StoreKind::*;
        match self {
            I32_8 { .. } | I64_8 { .. } => 1,
            I32_16 { .. } | I64_16 { .. } => 2,
            I32 { .. } | F32 | I64_32 { .. } => 4,
            I64 { .. } | F64 => 8,
            V128 => 16,
        }
    }

    /// Returns whether this is an atomic store
    pub fn atomic(&self) -> bool {
        use self::StoreKind::*;

        match self {
            I32 { atomic }
            | I64 { atomic }
            | I32_8 { atomic }
            | I32_16 { atomic }
            | I64_8 { atomic }
            | I64_16 { atomic }
            | I64_32 { atomic } => *atomic,
            F32 | F64 | V128 => false,
        }
    }
}

/// Arguments to memory operations, containing a constant offset from a dynamic
/// address as well as a predicted alignment.
#[derive(Debug, Copy, Clone)]
pub struct MemArg {
    /// The alignment of the memory operation, must be a power of two
    pub align: u32,
    /// The offset of the memory operation, in bytes from the source address
    pub offset: u32,
}

/// The different kinds of atomic rmw operations
#[derive(Debug, Copy, Clone)]
#[allow(missing_docs)]
pub enum AtomicOp {
    Add,
    Sub,
    And,
    Or,
    Xor,
    Xchg,
}

/// The different kinds of atomic rmw operations
#[derive(Debug, Copy, Clone)]
#[allow(missing_docs)]
pub enum AtomicWidth {
    I32,
    I32_8,
    I32_16,
    I64,
    I64_8,
    I64_16,
    I64_32,
}

impl AtomicWidth {
    /// Returns the size, in bytes, of this atomic operation
    pub fn bytes(&self) -> u32 {
        use self::AtomicWidth::*;
        match self {
            I32_8 | I64_8 => 1,
            I32_16 | I64_16 => 2,
            I32 | I64_32 => 4,
            I64 => 8,
        }
    }
}

impl Expr {
    /// Are any instructions that follow this expression's instruction (within
    /// the current block) unreachable?
    ///
    /// Returns `true` for unconditional branches (`br`, `return`, etc...) and
    /// `unreachable`. Returns `false` for all other "normal" instructions
    /// (`i32.add`, etc...).
    pub fn following_instructions_are_unreachable(&self) -> bool {
        match *self {
            Expr::Unreachable(..) | Expr::Br(..) | Expr::BrTable(..) | Expr::Return(..) => true,

            // No `_` arm to make sure that we properly update this function as
            // we add support for new instructions.
            Expr::Block(..)
            | Expr::Call(..)
            | Expr::LocalGet(..)
            | Expr::LocalSet(..)
            | Expr::LocalTee(..)
            | Expr::GlobalGet(..)
            | Expr::GlobalSet(..)
            | Expr::Const(..)
            | Expr::Binop(..)
            | Expr::Unop(..)
            | Expr::Select(..)
            | Expr::BrIf(..)
            | Expr::IfElse(..)
            | Expr::MemorySize(..)
            | Expr::MemoryGrow(..)
            | Expr::MemoryInit(..)
            | Expr::DataDrop(..)
            | Expr::MemoryCopy(..)
            | Expr::MemoryFill(..)
            | Expr::CallIndirect(..)
            | Expr::Load(..)
            | Expr::Store(..)
            | Expr::AtomicRmw(..)
            | Expr::Cmpxchg(..)
            | Expr::AtomicNotify(..)
            | Expr::AtomicWait(..)
            | Expr::WithSideEffects(..)
            | Expr::TableGet(..)
            | Expr::TableSet(..)
            | Expr::TableGrow(..)
            | Expr::TableSize(..)
            | Expr::RefNull(..)
            | Expr::RefIsNull(..)
            | Expr::V128Bitselect(..)
            | Expr::V128Shuffle(..)
            | Expr::Drop(..) => false,
        }
    }
}

impl Block {
    /// Construct a new block.
    pub fn new(kind: BlockKind, params: Box<[ValType]>, results: Box<[ValType]>) -> Block {
        let exprs = vec![];
        Block {
            kind,
            params,
            results,
            exprs,
        }
    }
}

/// Anything that can be visited by a `Visitor`.
pub trait Visit<'expr> {
    /// Visit this thing with the given visitor.
    fn visit<V>(&self, visitor: &mut V)
    where
        V: Visitor<'expr>;
}

/// Anything that can be visited by a `Visitor`.
pub trait VisitMut {
    /// Visit this thing with the given visitor.
    fn visit_mut<V>(&mut self, visitor: &mut V)
    where
        V: VisitorMut;
}

impl<'expr> Visit<'expr> for ExprId {
    fn visit<V>(&self, visitor: &mut V)
    where
        V: Visitor<'expr>,
    {
        visitor.visit_expr(&visitor.local_function().get(*self))
    }
}

impl VisitMut for ExprId {
    fn visit_mut<V>(&mut self, visitor: &mut V)
    where
        V: VisitorMut,
    {
        // TODO: this is somewhat unfortunate and seems like it's susceptible to
        // being bug-prone when we have a DAG of an IR. We'll need to for sure
        // use graph traversal instead of a simple tree walk like we have today
        // when that comes about.
        let mut expr = mem::replace(
            visitor.local_function_mut().get_mut(*self),
            Expr::Unreachable(Unreachable {}),
        );
        visitor.visit_expr_mut(&mut expr);
        *visitor.local_function_mut().get_mut(*self) = expr;
    }
}

fn display_block_name(block: &Block, out: &mut DisplayExpr) {
    match block.kind {
        BlockKind::Loop => out.f.push_str("loop"),
        _ => out.f.push_str("block"),
    }
}

fn dot_block_name(block: &Block, out: &mut DotExpr<'_, '_>) {
    match block.kind {
        BlockKind::Loop => out.out.push_str("loop"),
        BlockKind::IfElse => out.out.push_str("if_else"),
        BlockKind::FunctionEntry => out.out.push_str("entry"),
        BlockKind::Block => out.out.push_str("block"),
    }
}

fn display_br(e: &Br, out: &mut DisplayExpr) {
    out.f
        .push_str(&format!(" (;e{};)", ExprId::from(e.block).index()))
}

fn display_br_if(e: &BrIf, out: &mut DisplayExpr) {
    out.f
        .push_str(&format!(" (;e{};)", ExprId::from(e.block).index()))
}

fn display_br_table(e: &BrTable, out: &mut DisplayExpr) {
    let blocks = e
        .blocks
        .iter()
        .map(|b| format!("e{}", ExprId::from(*b).index()))
        .collect::<Vec<_>>()
        .join(" ");
    out.f.push_str(&format!(
        " (;default:e{}  [{}];)",
        ExprId::from(e.default).index(),
        blocks
    ))
}

fn display_binop_name(e: &Binop, out: &mut DisplayExpr) {
    out.f.push_str(&format!("{:?}", e.op))
}

fn dot_binop_name(e: &Binop, out: &mut DotExpr<'_, '_>) {
    out.out.push_str(&format!("{:?}", e.op))
}

fn display_unop_name(e: &Unop, out: &mut DisplayExpr) {
    out.f.push_str(&format!("{:?}", e.op))
}

fn dot_unop_name(e: &Unop, out: &mut DotExpr<'_, '_>) {
    out.out.push_str(&format!("{:?}", e.op))
}