lamina-mir 0.2.0

//! Structural, definition, dominance, and type verification for MIR.

use crate::{
    Function, Immediate, Instruction, MirType, Module, Operand, Register, RegisterClass,
    ScalarType, VectorLane, VectorOp, VectorType, io_intrinsic_result_type,
};
use std::collections::HashMap;

#[derive(Clone, Copy)]
struct Definition {
    block_index: usize,
    instruction_index: Option<usize>,
    ty: Option<MirType>,
}

#[derive(Clone, Copy)]
struct VerificationConfig {
    verify_terminator_placement: bool,
    verify_ssa: bool,
    verify_dominance: bool,
    verify_register_types: bool,
    verify_register_classes: bool,
    verify_immediate_widths: bool,
}

const STRICT_CONFIG: VerificationConfig = VerificationConfig {
    verify_terminator_placement: true,
    verify_ssa: true,
    verify_dominance: true,
    verify_register_types: true,
    verify_register_classes: true,
    verify_immediate_widths: true,
};
/// Edge copies give a register one definition per incoming edge, so single
/// definition is no longer a property to check. Dominance still is: it skips a
/// register with several definitions and reports one with none.
const POST_SSA_CONFIG: VerificationConfig = VerificationConfig {
    verify_terminator_placement: true,
    verify_ssa: false,
    verify_dominance: true,
    verify_register_types: true,
    verify_register_classes: true,
    verify_immediate_widths: true,
};

/// Verify one MIR function and return every problem found.
pub fn verify_function(function: &Function) -> Result<(), Vec<String>> {
    let errors = function_errors_with_config(function, STRICT_CONFIG, None);
    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}

/// Verify MIR at optimizer and backend input boundaries, where a register may be defined once per edge.
#[doc(hidden)]
pub fn verify_function_in_pipeline(function: &Function) -> Result<(), Vec<String>> {
    let errors = function_errors_with_config(function, POST_SSA_CONFIG, None);
    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}

/// Verify modules at optimizer and backend input boundaries, where a register may be defined once per edge.
#[doc(hidden)]
pub fn verify_module_in_pipeline(module: &Module) -> Result<(), Vec<String>> {
    let mut errors = Vec::new();
    for function in module.functions.values() {
        errors.extend(function_errors_with_config(
            function,
            POST_SSA_CONFIG,
            Some(module),
        ));
    }
    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}

pub(crate) fn function_errors(function: &Function, module: &Module) -> Vec<String> {
    function_errors_with_config(function, STRICT_CONFIG, Some(module))
}

fn function_errors_with_config(
    function: &Function,
    config: VerificationConfig,
    module: Option<&Module>,
) -> Vec<String> {
    let mut errors = Vec::new();
    if function.blocks.is_empty() {
        // A declaration: the signature is all there is to check.
        return errors;
    }
    let block_indices = verify_structure(function, config, &mut errors);
    let definitions = collect_definitions(function, config, module, &mut errors);
    if config.verify_dominance {
        let dominators = calculate_dominators(function, &block_indices);
        verify_dominance(function, &definitions, &dominators, &mut errors);
    }
    verify_instruction_types(function, &definitions, config, module, &mut errors);
    errors
}

fn verify_structure<'a>(
    function: &'a Function,
    config: VerificationConfig,
    errors: &mut Vec<String>,
) -> HashMap<&'a str, usize> {
    let mut block_indices = HashMap::new();
    for (block_index, block) in function.blocks.iter().enumerate() {
        if block_indices
            .insert(block.label.as_str(), block_index)
            .is_some()
        {
            errors.push(location(
                function,
                &block.label,
                format!(
                    "expected a unique block label, found duplicate '{}'",
                    block.label
                ),
            ));
        }

        let terminator_indices: Vec<usize> = block
            .instructions
            .iter()
            .enumerate()
            .filter_map(|(index, instruction)| instruction.is_terminator().then_some(index))
            .collect();
        if terminator_indices.is_empty()
            || (config.verify_terminator_placement && terminator_indices.len() != 1)
        {
            errors.push(location(
                function,
                &block.label,
                format!(
                    "expected exactly one terminator, found {}",
                    terminator_indices.len()
                ),
            ));
        }
        if config.verify_terminator_placement
            && let Some(terminator_index) = terminator_indices
                .iter()
                .find(|index| **index + 1 != block.instructions.len())
        {
            errors.push(instruction_location(
                function,
                &block.label,
                *terminator_index,
                format!(
                    "expected terminator to be the last instruction, found {} instruction(s) after it",
                    block.instructions.len() - terminator_index - 1
                ),
            ));
        }
    }

    if !block_indices.contains_key(function.entry.as_str()) {
        errors.push(location(
            function,
            &function.entry,
            format!(
                "expected entry block '{}' to exist, found no such block",
                function.entry
            ),
        ));
    }

    for block in &function.blocks {
        for (instruction_index, instruction) in block.instructions.iter().enumerate() {
            let instruction = &instruction.instr;
            for target in instruction_targets(instruction) {
                if !block_indices.contains_key(target) {
                    errors.push(instruction_location(
                        function,
                        &block.label,
                        instruction_index,
                        format!("expected branch target '{target}' to exist, found no such block"),
                    ));
                }
            }
        }
    }

    block_indices
}

fn collect_definitions(
    function: &Function,
    config: VerificationConfig,
    module: Option<&Module>,
    errors: &mut Vec<String>,
) -> HashMap<Register, Vec<Definition>> {
    let mut definitions: HashMap<Register, Vec<Definition>> = HashMap::new();
    let entry_index = function
        .blocks
        .iter()
        .position(|block| block.label == function.entry);

    if let Some(entry_index) = entry_index {
        for parameter in &function.sig.params {
            if parameter.reg.is_virtual() {
                definitions
                    .entry(parameter.reg.clone())
                    .or_default()
                    .push(Definition {
                        block_index: entry_index,
                        instruction_index: None,
                        ty: Some(parameter.ty),
                    });
            }
        }
    }
    for (block_index, block) in function.blocks.iter().enumerate() {
        for (instruction_index, instruction) in block.instructions.iter().enumerate() {
            let instruction = &instruction.instr;
            if let Some(register) = instruction.def_reg()
                && register.is_virtual()
            {
                definitions
                    .entry(register.clone())
                    .or_default()
                    .push(Definition {
                        block_index,
                        instruction_index: Some(instruction_index),
                        ty: match instruction {
                            Instruction::Call { name, .. } => module
                                .and_then(|m| m.functions.get(name))
                                .and_then(|callee| callee.sig.ret_ty)
                                .or_else(|| io_intrinsic_result_type(name, function.int64_regs)),
                            _ => instruction_definition_type(instruction),
                        },
                    });
            }
        }
    }

    if config.verify_register_types {
        for (register, defs) in &definitions {
            let mut types = defs.iter().filter_map(|definition| definition.ty);
            if let Some(first) = types.next()
                && types.any(|ty| ty != first)
            {
                errors.push(location(
                    function,
                    &function.entry,
                    format!("expected register {register} definitions to have consistent types"),
                ));
            }
        }
    }
    verify_unique_definitions(function, &definitions, config, errors);
    definitions
}

fn verify_unique_definitions(
    function: &Function,
    definitions: &HashMap<Register, Vec<Definition>>,
    config: VerificationConfig,
    errors: &mut Vec<String>,
) {
    for (register, register_definitions) in definitions {
        if config.verify_ssa && register_definitions.len() > 1 {
            for definition in register_definitions.iter().skip(1) {
                let block_label = function
                    .blocks
                    .get(definition.block_index)
                    .map_or(function.entry.as_str(), |block| block.label.as_str());
                let message = format!(
                    "expected virtual register {register} to be defined once, found {} definitions",
                    register_definitions.len()
                );
                errors.push(match definition.instruction_index {
                    Some(index) => instruction_location(function, block_label, index, message),
                    None => location(function, block_label, message),
                });
            }
        }
    }
}

/// Compute dominator sets by block index; unreachable blocks have no set.
/// Dominator tree of a function's reachable blocks, with constant-time ancestor queries.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dominators {
    idom: Vec<Option<usize>>,
    entry: Option<usize>,
    enter: Vec<u32>,
    leave: Vec<u32>,
    reachable: Vec<bool>,
}

impl Dominators {
    /// Whether the block is reachable from the entry block.
    pub fn is_reachable(&self, block: usize) -> bool {
        self.reachable.get(block).copied().unwrap_or(false)
    }

    /// Whether every path from entry to `block` passes through `dominator`.
    pub fn dominates(&self, dominator: usize, block: usize) -> bool {
        if !self.is_reachable(dominator) || !self.is_reachable(block) {
            return false;
        }
        self.enter[dominator] <= self.enter[block] && self.leave[block] <= self.leave[dominator]
    }

    /// Immediate dominator of a reachable non-entry block.
    pub fn immediate_dominator(&self, block: usize) -> Option<usize> {
        self.idom.get(block).copied().flatten()
    }

    /// Entry block index, absent when the function names no entry block.
    pub fn entry(&self) -> Option<usize> {
        self.entry
    }
}

/// Dominator tree by the Cooper, Harvey and Kennedy fixpoint over reverse postorder.
pub fn calculate_dominators(
    function: &Function,
    block_indices: &HashMap<&str, usize>,
) -> Dominators {
    let successors: Vec<Vec<usize>> = (0..function.blocks.len())
        .map(|block_index| {
            function.blocks[block_index]
                .instructions
                .last()
                .map(|terminator| {
                    instruction_targets(terminator)
                        .into_iter()
                        .filter_map(|target| block_indices.get(target).copied())
                        .collect()
                })
                .unwrap_or_default()
        })
        .collect();
    dominator_tree(
        &successors,
        block_indices.get(function.entry.as_str()).copied(),
    )
}

/// Dominator tree of a graph given by successor lists, rooted at `entry`.
pub(crate) fn dominator_tree(successors: &[Vec<usize>], entry: Option<usize>) -> Dominators {
    let block_count = successors.len();

    let Some(entry_index) = entry else {
        return Dominators {
            idom: vec![None; block_count],
            entry: None,
            enter: vec![0; block_count],
            leave: vec![0; block_count],
            reachable: vec![false; block_count],
        };
    };

    let mut reachable = vec![false; block_count];
    let mut postorder = Vec::new();
    let mut stack = vec![(entry_index, 0usize)];
    reachable[entry_index] = true;
    while let Some((block_index, next)) = stack.pop() {
        let edges = &successors[block_index];
        if next < edges.len() {
            stack.push((block_index, next + 1));
            let target = edges[next];
            if !reachable[target] {
                reachable[target] = true;
                stack.push((target, 0));
            }
        } else {
            postorder.push(block_index);
        }
    }

    let mut postorder_number = vec![usize::MAX; block_count];
    for (number, block_index) in postorder.iter().enumerate() {
        postorder_number[*block_index] = number;
    }

    let mut predecessors = vec![Vec::new(); block_count];
    for (block_index, live) in reachable.iter().enumerate() {
        if !live {
            continue;
        }
        for &target in &successors[block_index] {
            predecessors[target].push(block_index);
        }
    }

    let mut idom: Vec<Option<usize>> = vec![None; block_count];
    idom[entry_index] = Some(entry_index);
    let mut changed = true;
    while changed {
        changed = false;
        for block_index in postorder.iter().rev().copied() {
            if block_index == entry_index {
                continue;
            }
            let mut new_idom = None;
            for predecessor in predecessors[block_index].iter().copied() {
                if idom[predecessor].is_none() {
                    continue;
                }
                new_idom = match new_idom {
                    None => Some(predecessor),
                    Some(current) => {
                        let mut a = predecessor;
                        let mut b = current;
                        loop {
                            if a == b {
                                break Some(a);
                            }
                            if postorder_number[a] < postorder_number[b] {
                                match idom[a] {
                                    Some(next) => a = next,
                                    None => break None,
                                }
                            } else {
                                match idom[b] {
                                    Some(next) => b = next,
                                    None => break None,
                                }
                            }
                        }
                    }
                };
            }
            if new_idom.is_some() && idom[block_index] != new_idom {
                idom[block_index] = new_idom;
                changed = true;
            }
        }
    }

    let mut children = vec![Vec::new(); block_count];
    for (block_index, parent) in idom.iter().enumerate() {
        if block_index == entry_index || !reachable[block_index] {
            continue;
        }
        if let Some(parent) = parent {
            children[*parent].push(block_index);
        }
    }

    let mut enter = vec![0u32; block_count];
    let mut leave = vec![0u32; block_count];
    let mut clock = 0u32;
    let mut walk = vec![(entry_index, 0usize)];
    enter[entry_index] = clock;
    clock += 1;
    while let Some((block_index, next)) = walk.pop() {
        if next < children[block_index].len() {
            walk.push((block_index, next + 1));
            let child = children[block_index][next];
            enter[child] = clock;
            clock += 1;
            walk.push((child, 0));
        } else {
            leave[block_index] = clock;
            clock += 1;
        }
    }

    idom[entry_index] = None;
    Dominators {
        idom,
        entry: Some(entry_index),
        enter,
        leave,
        reachable,
    }
}

fn verify_dominance(
    function: &Function,
    definitions: &HashMap<Register, Vec<Definition>>,
    dominators: &Dominators,
    errors: &mut Vec<String>,
) {
    for (block_index, block) in function.blocks.iter().enumerate() {
        for (instruction_index, instruction) in block.instructions.iter().enumerate() {
            let instruction = &instruction.instr;
            for register in instruction.use_regs() {
                if !register.is_virtual() {
                    continue;
                }
                let Some(register_definitions) = definitions.get(register) else {
                    errors.push(instruction_location(
                        function,
                        &block.label,
                        instruction_index,
                        format!(
                            "expected use of virtual register {register} to have a dominating definition, found no definition"
                        ),
                    ));
                    continue;
                };
                if register_definitions.len() != 1 {
                    continue;
                }
                let definition = register_definitions[0];
                let dominates = if definition.block_index == block_index {
                    definition
                        .instruction_index
                        .is_none_or(|definition_index| definition_index < instruction_index)
                } else {
                    !dominators.is_reachable(block_index)
                        || dominators.dominates(definition.block_index, block_index)
                };
                if !dominates {
                    let definition_block = &function.blocks[definition.block_index].label;
                    errors.push(instruction_location(
                        function,
                        &block.label,
                        instruction_index,
                        format!(
                            "expected definition of virtual register {register} in block '{definition_block}' to dominate this use, found a non-dominating definition"
                        ),
                    ));
                }
            }
        }
    }
}

fn verify_instruction_types(
    function: &Function,
    definitions: &HashMap<Register, Vec<Definition>>,
    config: VerificationConfig,
    module: Option<&Module>,
    errors: &mut Vec<String>,
) {
    for block in &function.blocks {
        for (instruction_index, instruction) in block.instructions.iter().enumerate() {
            let instruction = &instruction.instr;
            let mut instruction_errors = Vec::new();
            match instruction {
                Instruction::Call { name, args, .. } | Instruction::TailCall { name, args } => {
                    if let Some(callee) = module.and_then(|m| m.functions.get(name)) {
                        let op = if matches!(instruction, Instruction::TailCall { .. }) {
                            "tailcall"
                        } else {
                            "call"
                        };
                        // A variadic callee takes its named parameters and any number
                        // of arguments after them.
                        let arity = if callee.sig.variadic {
                            args.len() < callee.sig.params.len()
                        } else {
                            args.len() != callee.sig.params.len()
                        };
                        if arity {
                            instruction_errors.push(format!(
                                "expected {op} '{name}' to have {}{} arguments, found {}",
                                if callee.sig.variadic { "at least " } else { "" },
                                callee.sig.params.len(),
                                args.len()
                            ));
                        }
                        for (index, (argument, parameter)) in
                            args.iter().zip(&callee.sig.params).enumerate()
                        {
                            verify_operand(
                                argument,
                                parameter.ty,
                                &format!("{op} '{name}' argument {index}"),
                                definitions,
                                config,
                                &mut instruction_errors,
                            );
                        }
                        match instruction {
                            Instruction::Call { ret: Some(dst), .. } => match callee.sig.ret_ty {
                                Some(ty) => verify_destination(dst, ty, "call result", config, &mut instruction_errors),
                                None => instruction_errors.push(format!("expected void call '{name}' to have no result")),
                            },
                            Instruction::TailCall { .. } if function.sig.ret_ty != callee.sig.ret_ty => instruction_errors.push(format!("expected tailcall '{name}' result {:?} to match caller result {:?}", callee.sig.ret_ty, function.sig.ret_ty)),
                            _ => {},
                        }
                    }
                }
                Instruction::SymbolAddress { dst, .. } => {
                    verify_destination(
                        dst,
                        MirType::Scalar(ScalarType::Ptr),
                        "SymbolAddress",
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::ThreadLocalAddr { dst, .. } => {
                    verify_destination(
                        dst,
                        MirType::Scalar(ScalarType::Ptr),
                        "ThreadLocalAddr",
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntOverflow {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_integer_scalar(*ty) {
                        instruction_errors.push(format!(
                            "expected IntOverflow operand type to be an integer scalar, found {ty}"
                        ));
                    }
                    verify_destination(
                        dst,
                        MirType::Scalar(ScalarType::I1),
                        "IntOverflow",
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        lhs,
                        *ty,
                        "IntOverflow lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "IntOverflow rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::Copy { ty, dst, src } => {
                    verify_destination(dst, *ty, "Copy", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *ty,
                        "Copy source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::Bitcast { from, to, dst, src } => {
                    if from.size_bytes(function.pointer_width)
                        != to.size_bytes(function.pointer_width)
                        || from.is_vector()
                        || to.is_vector()
                    {
                        instruction_errors.push("expected equal-width scalar bitcast".into());
                    }
                    verify_destination(dst, *to, "Bitcast", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *from,
                        "Bitcast source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntConvert {
                    from,
                    to,
                    signed,
                    dst,
                    src,
                } => {
                    if !is_integer_or_pointer(*from)
                        || !is_integer_or_pointer(*to)
                        || (*signed
                            && from.size_bytes(function.pointer_width)
                                >= to.size_bytes(function.pointer_width))
                    {
                        instruction_errors.push("expected a valid integer conversion".into());
                    }
                    verify_destination(dst, *to, "IntConvert", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *from,
                        "IntConvert source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntToFloat {
                    from, to, dst, src, ..
                } => {
                    if !is_plain_integer(*from) || !is_float_scalar(*to) {
                        instruction_errors.push(
                            "expected IntToFloat from an integer scalar to a float scalar".into(),
                        );
                    }
                    verify_destination(dst, *to, "IntToFloat", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *from,
                        "IntToFloat source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::FloatConvert { from, to, dst, src } => {
                    if !is_float_scalar(*from) || !is_float_scalar(*to) || from == to {
                        instruction_errors.push(
                            "expected FloatConvert between the two float scalar types".into(),
                        );
                    }
                    verify_destination(dst, *to, "FloatConvert", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *from,
                        "FloatConvert source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::FloatToInt {
                    from, to, dst, src, ..
                } => {
                    if !is_float_scalar(*from) || !is_plain_integer(*to) {
                        instruction_errors.push(
                            "expected FloatToInt from a float scalar to an integer scalar".into(),
                        );
                    }
                    verify_destination(dst, *to, "FloatToInt", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *from,
                        "FloatToInt source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntBinary {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_integer_or_pointer(*ty) {
                        instruction_errors.push(format!(
                            "expected IntBinary type to be an integer or pointer scalar, found {ty}"
                        ));
                    }
                    verify_destination(dst, *ty, "IntBinary", config, &mut instruction_errors);
                    verify_operand(
                        lhs,
                        *ty,
                        "IntBinary lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "IntBinary rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::FloatBinary {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_float_scalar(*ty) {
                        instruction_errors.push(format!(
                            "expected FloatBinary type to be a float scalar, found {ty}"
                        ));
                    }
                    verify_destination(dst, *ty, "FloatBinary", config, &mut instruction_errors);
                    verify_operand(
                        lhs,
                        *ty,
                        "FloatBinary lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "FloatBinary rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::FloatUnary { ty, dst, src, .. } => {
                    verify_destination(dst, *ty, "FloatUnary", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *ty,
                        "FloatUnary source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntUnary { ty, dst, src, .. } => {
                    if !is_integer_or_pointer(*ty) {
                        instruction_errors.push(format!(
                            "expected IntUnary type to be an integer or pointer scalar, found {ty}"
                        ));
                    }
                    verify_destination(dst, *ty, "IntUnary", config, &mut instruction_errors);
                    verify_operand(
                        src,
                        *ty,
                        "IntUnary source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntRotate {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_integer_or_pointer(*ty) {
                        instruction_errors.push(format!(
                            "expected IntRotate type to be an integer or pointer scalar, found {ty}"
                        ));
                    }
                    verify_destination(dst, *ty, "IntRotate", config, &mut instruction_errors);
                    verify_operand(
                        lhs,
                        *ty,
                        "IntRotate lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "IntRotate rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::IntCmp {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_integer_or_pointer(*ty) {
                        instruction_errors.push(format!(
                            "expected IntCmp operand type to be an integer or pointer scalar, found {ty}"
                        ));
                    }
                    verify_destination(
                        dst,
                        MirType::Scalar(ScalarType::I1),
                        "IntCmp",
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        lhs,
                        *ty,
                        "IntCmp lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "IntCmp rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::FloatCmp {
                    ty, dst, lhs, rhs, ..
                } => {
                    if !is_float_scalar(*ty) {
                        instruction_errors.push(format!(
                            "expected FloatCmp operand type to be a float scalar, found {ty}"
                        ));
                    }
                    verify_destination(
                        dst,
                        MirType::Scalar(ScalarType::I1),
                        "FloatCmp",
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        lhs,
                        *ty,
                        "FloatCmp lhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        rhs,
                        *ty,
                        "FloatCmp rhs",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::Select {
                    ty,
                    dst,
                    cond,
                    true_val,
                    false_val,
                } => {
                    verify_destination(dst, *ty, "Select", config, &mut instruction_errors);
                    verify_register(
                        cond,
                        MirType::Scalar(ScalarType::I1),
                        "Select condition",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        true_val,
                        *ty,
                        "Select true arm",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                    verify_operand(
                        false_val,
                        *ty,
                        "Select false arm",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::Br { cond, .. } => {
                    verify_register(
                        cond,
                        MirType::Scalar(ScalarType::I1),
                        "Branch condition",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::Store { ty, src, .. } => {
                    verify_operand(
                        src,
                        *ty,
                        "Store source",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::VectorOp {
                    op,
                    ty,
                    dst,
                    operands,
                } => {
                    let scalar = vector_scalar(*ty);
                    let dst_ty = if *op == VectorOp::VExtractLane {
                        scalar
                    } else {
                        *ty
                    };
                    verify_destination(dst, dst_ty, "VectorOp", config, &mut instruction_errors);
                    for (index, operand) in operands.iter().enumerate() {
                        let operand_ty = match (op, index) {
                            (VectorOp::VSplat, 0) | (VectorOp::VInsertLane, 1) => scalar,
                            (VectorOp::VExtractLane, 1)
                            | (VectorOp::VInsertLane, 2)
                            | (VectorOp::VShl | VectorOp::VLShr | VectorOp::VAShr, 1) => {
                                MirType::Scalar(ScalarType::I64)
                            }
                            _ => *ty,
                        };
                        verify_operand(
                            operand,
                            operand_ty,
                            if matches!(
                                (op, index),
                                (VectorOp::VExtractLane, 1) | (VectorOp::VInsertLane, 2)
                            ) {
                                "VectorOp lane index"
                            } else {
                                "VectorOp operand"
                            },
                            definitions,
                            config,
                            &mut instruction_errors,
                        );
                    }
                }
                Instruction::VaStart { ap } | Instruction::VaEnd { ap } => {
                    verify_operand(
                        ap,
                        MirType::Scalar(ScalarType::Ptr),
                        "va_list address",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::VaArg { ty, dst, ap } => {
                    verify_destination(dst, *ty, "VaArg", config, &mut instruction_errors);
                    verify_operand(
                        ap,
                        MirType::Scalar(ScalarType::Ptr),
                        "va_list address",
                        definitions,
                        config,
                        &mut instruction_errors,
                    );
                }
                Instruction::VaCopy { dst, src } => {
                    for (operand, what) in [(dst, "va_copy destination"), (src, "va_copy source")] {
                        verify_operand(
                            operand,
                            MirType::Scalar(ScalarType::Ptr),
                            what,
                            definitions,
                            config,
                            &mut instruction_errors,
                        );
                    }
                }
                Instruction::Ret { value: Some(value) } => {
                    if let Some(return_type) = function.sig.ret_ty {
                        verify_operand(
                            value,
                            return_type,
                            "return value",
                            definitions,
                            config,
                            &mut instruction_errors,
                        );
                    }
                }
                _ => {}
            }
            errors.extend(instruction_errors.into_iter().map(|message| {
                instruction_location(function, &block.label, instruction_index, message)
            }));
        }
    }
}

fn verify_destination(
    register: &Register,
    expected_type: MirType,
    instruction_name: &str,
    config: VerificationConfig,
    errors: &mut Vec<String>,
) {
    if !config.verify_register_types {
        return;
    }
    let expected_class = register_class_for_type(expected_type);
    if config.verify_register_classes && register.class() != expected_class {
        errors.push(format!(
            "expected {instruction_name} destination to have type {expected_type} ({expected_class:?} register), found {register} with {:?} register class",
            register.class()
        ));
    }
}

fn verify_operand(
    operand: &Operand,
    expected_type: MirType,
    operand_name: &str,
    definitions: &HashMap<Register, Vec<Definition>>,
    config: VerificationConfig,
    errors: &mut Vec<String>,
) {
    match operand {
        Operand::Register(register) => {
            verify_register(
                register,
                expected_type,
                operand_name,
                definitions,
                config,
                errors,
            );
        }
        Operand::Immediate(immediate) => {
            if config.verify_immediate_widths && !immediate_matches_type(*immediate, expected_type)
            {
                errors.push(format!(
                    "expected {operand_name} immediate to match type {expected_type}, found {} immediate",
                    immediate_type_name(*immediate)
                ));
            }
        }
    }
}

fn verify_register(
    register: &Register,
    expected_type: MirType,
    operand_name: &str,
    definitions: &HashMap<Register, Vec<Definition>>,
    config: VerificationConfig,
    errors: &mut Vec<String>,
) {
    if !config.verify_register_types {
        return;
    }
    let expected_class = register_class_for_type(expected_type);
    if config.verify_register_classes && register.class() != expected_class {
        errors.push(format!(
            "expected {operand_name} to have type {expected_type} ({expected_class:?} register), found {register} with {:?} register class",
            register.class()
        ));
        return;
    }
    let Some(register_definitions) = definitions.get(register) else {
        return;
    };
    for definition in register_definitions {
        if let Some(actual_type) = definition.ty
            && actual_type != expected_type
        {
            errors.push(format!(
            "expected {operand_name} to have type {expected_type}, found register {register} defined as {actual_type}"
        ));
        }
    }
}

pub(crate) fn instruction_definition_type(instruction: &Instruction) -> Option<MirType> {
    match instruction {
        Instruction::Copy { ty, .. }
        | Instruction::IntBinary { ty, .. }
        | Instruction::FloatBinary { ty, .. }
        | Instruction::FloatUnary { ty, .. }
        | Instruction::IntUnary { ty, .. }
        | Instruction::IntRotate { ty, .. }
        | Instruction::Select { ty, .. }
        | Instruction::Load { ty, .. } => Some(*ty),
        Instruction::VectorOp {
            op: VectorOp::VExtractLane,
            ty,
            ..
        } => Some(vector_scalar(*ty)),
        Instruction::VectorOp { ty, .. } => Some(*ty),
        Instruction::IntCmp { .. }
        | Instruction::FloatCmp { .. }
        | Instruction::IntOverflow { .. } => Some(MirType::Scalar(ScalarType::I1)),
        Instruction::IntConvert { to, .. }
        | Instruction::IntToFloat { to, .. }
        | Instruction::FloatToInt { to, .. }
        | Instruction::FloatConvert { to, .. }
        | Instruction::Bitcast { to, .. } => Some(*to),
        Instruction::Lea { .. }
        | Instruction::StackAddr { .. }
        | Instruction::SymbolAddress { .. }
        | Instruction::ThreadLocalAddr { .. } => Some(MirType::Scalar(ScalarType::Ptr)),
        _ => None,
    }
}

fn instruction_targets(instruction: &Instruction) -> Vec<&str> {
    match instruction {
        Instruction::Jmp { target } => vec![target],
        Instruction::Br {
            true_target,
            false_target,
            ..
        } => vec![true_target, false_target],
        Instruction::Switch { cases, default, .. } => {
            let mut targets = Vec::with_capacity(cases.len() + 1);
            targets.push(default.as_str());
            targets.extend(cases.iter().map(|(_, target)| target.as_str()));
            targets
        }
        _ => Vec::new(),
    }
}

fn vector_scalar(ty: MirType) -> MirType {
    let MirType::Vector(VectorType::V128(lane) | VectorType::V256(lane)) = ty else {
        return ty;
    };
    MirType::Scalar(match lane {
        VectorLane::I8 => ScalarType::I8,
        VectorLane::I16 => ScalarType::I16,
        VectorLane::I32 => ScalarType::I32,
        VectorLane::I64 => ScalarType::I64,
        VectorLane::F32 => ScalarType::F32,
        VectorLane::F64 => ScalarType::F64,
    })
}

fn is_plain_integer(ty: MirType) -> bool {
    matches!(
        ty,
        MirType::Scalar(ScalarType::I8 | ScalarType::I16 | ScalarType::I32 | ScalarType::I64)
    )
}

fn is_integer_or_pointer(ty: MirType) -> bool {
    matches!(
        ty,
        MirType::Scalar(
            ScalarType::I1
                | ScalarType::I8
                | ScalarType::I16
                | ScalarType::I32
                | ScalarType::I64
                | ScalarType::Ptr
                | ScalarType::PtrIn(_)
        )
    )
}

fn is_integer_scalar(ty: MirType) -> bool {
    matches!(
        ty,
        MirType::Scalar(ScalarType::I8 | ScalarType::I16 | ScalarType::I32 | ScalarType::I64)
    )
}

fn is_float_scalar(ty: MirType) -> bool {
    matches!(ty, MirType::Scalar(ScalarType::F32 | ScalarType::F64))
}

fn register_class_for_type(ty: MirType) -> RegisterClass {
    match ty {
        MirType::Scalar(ScalarType::F32 | ScalarType::F64) => RegisterClass::Fpr,
        MirType::Vector(VectorType::V128(_) | VectorType::V256(_)) => RegisterClass::Vec,
        MirType::Scalar(_) => RegisterClass::Gpr,
    }
}

fn immediate_matches_type(immediate: Immediate, ty: MirType) -> bool {
    matches!(
        (immediate, ty),
        (
            Immediate::I8(_),
            MirType::Scalar(ScalarType::I1 | ScalarType::I8)
        ) | (Immediate::I16(_), MirType::Scalar(ScalarType::I16))
            | (Immediate::I32(_), MirType::Scalar(ScalarType::I32))
            | (
                Immediate::I64(_),
                MirType::Scalar(ScalarType::I64 | ScalarType::Ptr | ScalarType::PtrIn(_))
            )
            | (Immediate::F32(_), MirType::Scalar(ScalarType::F32))
            | (Immediate::F64(_), MirType::Scalar(ScalarType::F64))
    )
}

fn immediate_type_name(immediate: Immediate) -> &'static str {
    match immediate {
        Immediate::I8(_) => "i8",
        Immediate::I16(_) => "i16",
        Immediate::I32(_) => "i32",
        Immediate::I64(_) => "i64",
        Immediate::F32(_) => "f32",
        Immediate::F64(_) => "f64",
    }
}

fn location(function: &Function, block: &str, message: String) -> String {
    format!(
        "function '{}', block '{}': {message}",
        function.sig.name, block
    )
}

fn instruction_location(
    function: &Function,
    block: &str,
    instruction_index: usize,
    message: String,
) -> String {
    location(
        function,
        block,
        format!("instruction {instruction_index}: {message}"),
    )
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        Block, FloatBinOp, FloatCmpOp, FunctionBuilder, IntBinOp, IntCmpOp, Parameter, Signature,
        VirtualReg,
    };

    fn verification_errors(function: &Function) -> Vec<String> {
        match verify_function(function) {
            Ok(()) => vec!["function unexpectedly passed verification".to_string()],
            Err(errors) => errors,
        }
    }

    #[test]
    fn symbol_address_requires_pointer_register_destination() {
        let symbol_address = |dst: Register| {
            FunctionBuilder::new("f")
                .block("entry")
                .instr(Instruction::SymbolAddress {
                    dst,
                    symbol: "g".to_string(),
                })
                .instr(Instruction::Ret { value: None })
                .build()
        };
        assert!(verify_function(&symbol_address(VirtualReg::gpr(0).into())).is_ok());
        assert!(
            verification_errors(&symbol_address(VirtualReg::fpr(0).into()))
                .iter()
                .any(|e| e.contains("SymbolAddress destination"))
        );
    }

    #[test]
    fn rejects_duplicate_definitions_and_non_dominating_uses() {
        let duplicate = FunctionBuilder::new("f")
            .param(VirtualReg::gpr(0).into(), MirType::Scalar(ScalarType::I64))
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::imm_i64(1),
            })
            .instr(Instruction::Ret { value: None })
            .build();
        assert!(
            verification_errors(&duplicate)
                .iter()
                .any(|e| e.contains("defined once"))
        );
        let forward = FunctionBuilder::new("f")
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(1).into(),
                src: Operand::v_gpr(0),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::imm_i64(1),
            })
            .instr(Instruction::Ret { value: None })
            .build();
        assert!(
            verification_errors(&forward)
                .iter()
                .any(|e| e.contains("non-dominating"))
        );
    }

    #[test]
    fn pipeline_rejects_integer_immediate_width_mismatch() {
        let mut module = Module::new("width");
        module.add_function(
            FunctionBuilder::new("f")
                .block("entry")
                .instr(Instruction::Copy {
                    ty: MirType::Scalar(ScalarType::I8),
                    dst: VirtualReg::gpr(0).into(),
                    src: Operand::imm_i64(1),
                })
                .instr(Instruction::Ret { value: None })
                .build(),
        );
        let errors = module.validate_in_pipeline().err().unwrap_or_default();
        assert!(
            errors.iter().any(|e| e.contains("match type i8")),
            "{errors:?}"
        );
    }

    #[test]
    fn signatures_check_call_arguments_results_and_tail_results() {
        for tail in [false, true] {
            let mut module = Module::new("calls");
            module.add_function(
                FunctionBuilder::new("callee")
                    .param(VirtualReg::gpr(0).into(), MirType::Scalar(ScalarType::I32))
                    .returns(MirType::Scalar(ScalarType::I32))
                    .block("entry")
                    .instr(Instruction::Ret {
                        value: Some(Operand::v_gpr(0)),
                    })
                    .build(),
            );
            let call = if tail {
                Instruction::TailCall {
                    name: "callee".into(),
                    args: vec![Operand::v_gpr(0)],
                }
            } else {
                Instruction::Call {
                    name: "callee".into(),
                    args: vec![Operand::v_gpr(0)],
                    ret: Some(VirtualReg::gpr(1).into()),
                }
            };
            let mut caller = FunctionBuilder::new("caller")
                .param(VirtualReg::gpr(0).into(), MirType::Scalar(ScalarType::I64))
                .returns(MirType::Scalar(ScalarType::I64))
                .block("entry")
                .instr(call);
            if !tail {
                caller = caller.instr(Instruction::Ret {
                    value: Some(Operand::v_gpr(1)),
                });
            }
            module.add_function(caller.build());
            for errors in [
                module.validate().err().unwrap_or_default(),
                module.validate_in_pipeline().err().unwrap_or_default(),
            ] {
                assert!(
                    errors
                        .iter()
                        .any(|e| e.contains("argument 0") && e.contains("defined as i64")),
                    "{errors:?}"
                );
                assert!(
                    errors.iter().any(|e| if tail {
                        e.contains("match caller result")
                    } else {
                        e.contains("return value") && e.contains("defined as i32")
                    }),
                    "{errors:?}"
                );
            }
        }
    }

    #[test]
    fn signatures_reject_void_call_destinations() {
        let mut module = Module::new("void");
        module.add_function(
            FunctionBuilder::new("callee")
                .block("entry")
                .instr(Instruction::Ret { value: None })
                .build(),
        );
        module.add_function(
            FunctionBuilder::new("caller")
                .block("entry")
                .instr(Instruction::Call {
                    name: "callee".into(),
                    args: vec![],
                    ret: Some(VirtualReg::gpr(0).into()),
                })
                .instr(Instruction::Ret { value: None })
                .build(),
        );
        assert!(
            module
                .validate_in_pipeline()
                .err()
                .unwrap_or_default()
                .iter()
                .any(|e| e.contains("void call"))
        );
    }

    #[test]
    fn pipeline_rejects_register_width_disagreements_with_multiple_definitions() {
        let function = FunctionBuilder::new("bad_widths")
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I32),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::imm_i32(1),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::imm_i64(2),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(1).into(),
                src: Operand::v_gpr(0),
            })
            .instr(Instruction::Ret { value: None })
            .build();
        let mut module = Module::new("bad_widths");
        module.add_function(function);
        let errors = module.validate_in_pipeline().err().unwrap_or_default();
        assert!(
            errors.iter().any(|e| e.contains("defined as i32")),
            "{errors:?}"
        );
    }

    #[test]
    fn pipeline_accepts_float_bits_in_general_register_storage() {
        let function = FunctionBuilder::new("float_storage")
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::F32),
                dst: VirtualReg::fpr(0).into(),
                src: Operand::imm_f32(1.0),
            })
            .instr(Instruction::Bitcast {
                from: MirType::Scalar(ScalarType::F32),
                to: MirType::Scalar(ScalarType::I32),
                dst: VirtualReg::gpr(1).into(),
                src: Operand::Register(VirtualReg::fpr(0).into()),
            })
            .instr(Instruction::Ret { value: None })
            .build();
        let mut module = Module::new("float_storage");
        module.add_function(function);
        assert!(module.validate_in_pipeline().is_ok());
    }

    #[test]
    fn rejects_instruction_after_terminator() {
        let function = FunctionBuilder::new("bad_terminator")
            .block("entry")
            .instr(Instruction::Jmp {
                target: "exit".to_string(),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::Immediate(Immediate::I64(1)),
            })
            .instr(Instruction::Ret { value: None })
            .block("exit")
            .instr(Instruction::Ret { value: None })
            .build();

        let mut module = Module::new("bad_terminator");
        module.add_function(function.clone());
        assert!(module.validate_in_pipeline().is_err());
        let errors = verification_errors(&function);
        assert!(
            errors
                .iter()
                .any(|error| error.contains("exactly one terminator"))
        );
        assert!(
            errors
                .iter()
                .any(|error| error.contains("last instruction"))
        );
    }

    #[test]
    fn accepts_one_final_terminator() {
        let function = FunctionBuilder::new("good_terminator")
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::Immediate(Immediate::I64(1)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        assert!(verify_function(&function).is_ok());
    }

    #[test]
    fn rejects_multiple_virtual_register_definitions() {
        let function = FunctionBuilder::new("bad_ssa")
            .param(VirtualReg::gpr(0).into(), MirType::Scalar(ScalarType::I64))
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::Immediate(Immediate::I64(1)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        let errors = verification_errors(&function);
        assert!(
            errors
                .iter()
                .any(|error| error.contains("found 2 definitions"))
        );
    }

    #[test]
    fn accepts_single_virtual_register_definitions() {
        let function = FunctionBuilder::new("good_ssa")
            .param(VirtualReg::gpr(0).into(), MirType::Scalar(ScalarType::I64))
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(1).into(),
                src: Operand::Register(VirtualReg::gpr(0).into()),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        assert!(verify_function(&function).is_ok());
    }

    #[test]
    fn rejects_definition_that_does_not_dominate_use() {
        let mut function = Function::new(
            Signature::new("bad_dominance")
                .with_params(vec![Parameter::new(
                    VirtualReg::gpr(0).into(),
                    MirType::Scalar(ScalarType::I1),
                )])
                .with_return(MirType::Scalar(ScalarType::I64)),
        );
        let mut entry = Block::new("entry");
        entry.push(Instruction::Br {
            cond: VirtualReg::gpr(0).into(),
            true_target: "left".to_string(),
            false_target: "right".to_string(),
        });
        let mut left = Block::new("left");
        left.push(Instruction::Copy {
            ty: MirType::Scalar(ScalarType::I64),
            dst: VirtualReg::gpr(1).into(),
            src: Operand::Immediate(Immediate::I64(1)),
        });
        left.push(Instruction::Jmp {
            target: "merge".to_string(),
        });
        let mut right = Block::new("right");
        right.push(Instruction::Jmp {
            target: "merge".to_string(),
        });
        let mut merge = Block::new("merge");
        merge.push(Instruction::Ret {
            value: Some(Operand::Register(VirtualReg::gpr(1).into())),
        });
        function.add_block(entry);
        function.add_block(left);
        function.add_block(right);
        function.add_block(merge);

        let errors = verification_errors(&function);
        assert!(
            errors
                .iter()
                .any(|error| error.contains("non-dominating definition"))
        );
    }

    #[test]
    fn accepts_definition_that_dominates_use() {
        let function = FunctionBuilder::new("good_dominance")
            .returns(MirType::Scalar(ScalarType::I64))
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::Immediate(Immediate::I64(1)),
            })
            .instr(Instruction::Jmp {
                target: "exit".to_string(),
            })
            .block("exit")
            .instr(Instruction::Ret {
                value: Some(Operand::Register(VirtualReg::gpr(0).into())),
            })
            .build();

        assert!(verify_function(&function).is_ok());
    }

    #[test]
    fn rejects_instruction_type_disagreements() {
        let function = FunctionBuilder::new("bad_types")
            .block("entry")
            .instr(Instruction::IntBinary {
                op: IntBinOp::Add,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(0).into(),
                lhs: Operand::Immediate(Immediate::F64(1.0)),
                rhs: Operand::Immediate(Immediate::F64(2.0)),
            })
            .instr(Instruction::FloatBinary {
                op: FloatBinOp::FAdd,
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(1).into(),
                lhs: Operand::Immediate(Immediate::I64(1)),
                rhs: Operand::Immediate(Immediate::I64(2)),
            })
            .instr(Instruction::IntCmp {
                op: IntCmpOp::Eq,
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::fpr(2).into(),
                lhs: Operand::Immediate(Immediate::I64(1)),
                rhs: Operand::Immediate(Immediate::I64(2)),
            })
            .instr(Instruction::FloatCmp {
                op: FloatCmpOp::Eq,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(3).into(),
                lhs: Operand::Immediate(Immediate::F64(1.0)),
                rhs: Operand::Immediate(Immediate::F64(2.0)),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(4).into(),
                src: Operand::Register(VirtualReg::gpr(1).into()),
            })
            .instr(Instruction::Select {
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(5).into(),
                cond: VirtualReg::fpr(2).into(),
                true_val: Operand::Register(VirtualReg::gpr(1).into()),
                false_val: Operand::Immediate(Immediate::F64(0.0)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        let errors = verification_errors(&function);
        assert!(errors.iter().any(|error| error.contains("IntBinary type")));
        assert!(
            errors
                .iter()
                .any(|error| error.contains("FloatBinary type"))
        );
        assert!(
            errors
                .iter()
                .filter(|error| error.contains("destination to have type i1"))
                .count()
                >= 2
        );
        assert!(errors.iter().any(|error| error.contains("Copy source")));
        assert!(errors.iter().any(|error| error.contains("Select true arm")));
    }

    #[test]
    fn rejects_non_i1_branch_condition() {
        let function = FunctionBuilder::new("bad_branch")
            .block("entry")
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I8),
                dst: VirtualReg::gpr(0).into(),
                src: Operand::Immediate(Immediate::I8(1)),
            })
            .instr(Instruction::Br {
                cond: VirtualReg::gpr(0).into(),
                true_target: "exit".to_string(),
                false_target: "exit".to_string(),
            })
            .block("exit")
            .instr(Instruction::Ret { value: None })
            .build();

        let errors = verification_errors(&function);
        assert!(errors.iter().any(|error| error.contains(
            "expected Branch condition to have type i1, found register v0 defined as i8"
        )));
    }

    #[test]
    fn accepts_instruction_type_agreement() {
        let function = FunctionBuilder::new("good_types")
            .block("entry")
            .instr(Instruction::IntBinary {
                op: IntBinOp::Add,
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(0).into(),
                lhs: Operand::Immediate(Immediate::I64(1)),
                rhs: Operand::Immediate(Immediate::I64(2)),
            })
            .instr(Instruction::FloatBinary {
                op: FloatBinOp::FAdd,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(1).into(),
                lhs: Operand::Immediate(Immediate::F64(1.0)),
                rhs: Operand::Immediate(Immediate::F64(2.0)),
            })
            .instr(Instruction::IntCmp {
                op: IntCmpOp::Eq,
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(2).into(),
                lhs: Operand::Register(VirtualReg::gpr(0).into()),
                rhs: Operand::Immediate(Immediate::I64(3)),
            })
            .instr(Instruction::FloatCmp {
                op: FloatCmpOp::Eq,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::gpr(3).into(),
                lhs: Operand::Register(VirtualReg::fpr(1).into()),
                rhs: Operand::Immediate(Immediate::F64(3.0)),
            })
            .instr(Instruction::Copy {
                ty: MirType::Scalar(ScalarType::I1),
                dst: VirtualReg::gpr(4).into(),
                src: Operand::Register(VirtualReg::gpr(3).into()),
            })
            .instr(Instruction::Select {
                ty: MirType::Scalar(ScalarType::I64),
                dst: VirtualReg::gpr(5).into(),
                cond: VirtualReg::gpr(2).into(),
                true_val: Operand::Register(VirtualReg::gpr(0).into()),
                false_val: Operand::Immediate(Immediate::I64(0)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        assert!(verify_function(&function).is_ok());
    }

    #[test]
    fn rejects_immediate_with_wrong_width() {
        let function = FunctionBuilder::new("bad_immediate")
            .block("entry")
            .instr(Instruction::FloatBinary {
                op: FloatBinOp::FAdd,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(0).into(),
                lhs: Operand::Immediate(Immediate::F64(1.0)),
                rhs: Operand::Immediate(Immediate::I64(2)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        let mut module = Module::new("bad_width");
        module.add_function(function.clone());
        assert!(module.validate_in_pipeline().is_err());
        let errors = verification_errors(&function);
        assert!(errors.iter().any(|error| {
            error.contains("expected FloatBinary rhs immediate to match type f64")
                && error.contains("found i64 immediate")
        }));
    }

    #[test]
    fn accepts_immediate_with_matching_width() {
        let function = FunctionBuilder::new("good_immediate")
            .block("entry")
            .instr(Instruction::FloatBinary {
                op: FloatBinOp::FAdd,
                ty: MirType::Scalar(ScalarType::F64),
                dst: VirtualReg::fpr(0).into(),
                lhs: Operand::Immediate(Immediate::F64(1.0)),
                rhs: Operand::Immediate(Immediate::F64(2.0)),
            })
            .instr(Instruction::Ret { value: None })
            .build();

        assert!(verify_function(&function).is_ok());
    }

    #[test]
    fn dominator_tree_answers_ancestor_queries_on_long_chain() {
        let length = 4000;
        let mut builder = FunctionBuilder::new("chain").block("entry");
        builder = builder.instr(Instruction::Jmp {
            target: "b0".to_string(),
        });
        for index in 0..length {
            builder = builder.block(format!("b{index}")).instr(Instruction::Jmp {
                target: format!("b{}", index + 1),
            });
        }
        let function = builder
            .block(format!("b{length}"))
            .instr(Instruction::Ret { value: None })
            .build();

        let labels: HashMap<&str, usize> = function
            .blocks
            .iter()
            .enumerate()
            .map(|(index, block)| (block.label.as_str(), index))
            .collect();
        let dominators = calculate_dominators(&function, &labels);

        let entry = labels["entry"];
        let first = labels["b0"];
        let middle = labels[format!("b{}", length / 2).as_str()];
        let last = labels[format!("b{length}").as_str()];

        assert!(dominators.dominates(entry, last));
        assert!(dominators.dominates(first, middle));
        assert!(dominators.dominates(middle, last));
        assert!(!dominators.dominates(last, middle));
        assert!(!dominators.dominates(middle, first));
        assert_eq!(dominators.immediate_dominator(first), Some(entry));
        assert!(dominators.is_reachable(last));
    }

    #[test]
    fn unreachable_blocks_dominate_nothing() {
        let function = FunctionBuilder::new("orphan")
            .block("entry")
            .instr(Instruction::Ret { value: None })
            .block("stranded")
            .instr(Instruction::Ret { value: None })
            .build();

        let labels: HashMap<&str, usize> = function
            .blocks
            .iter()
            .enumerate()
            .map(|(index, block)| (block.label.as_str(), index))
            .collect();
        let dominators = calculate_dominators(&function, &labels);

        assert!(dominators.is_reachable(labels["entry"]));
        assert!(!dominators.is_reachable(labels["stranded"]));
        assert!(!dominators.dominates(labels["stranded"], labels["entry"]));
        assert!(!dominators.dominates(labels["entry"], labels["stranded"]));
    }
}