llvm-native-core 0.1.11

//! GlobalISel Legalizer.
//!
//! Clean-room behavioral reconstruction from the LLVM GlobalISel
//! documentation and the Legalizer design. Zero LLVM C++ source
//! code consultation.
//!
//! The legalizer transforms generic machine instructions into
//! forms supported by the target. This includes widening/narrowing
//! scalar types, replacing unsupported operations with libcalls,
//! and lowering complex instructions into sequences of simpler ones.

use crate::global_isel::gisel_machine_ir::{
    GInstruction, GMachineFunction, GOpcode, MOperand, VReg,
};
use std::collections::HashMap;

// -----------------------------------------------------------------------
// Type descriptor for legalization purposes
// -----------------------------------------------------------------------

/// Scalar type descriptor used in legalization rules.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Type {
    /// Scalar integer of given bit width.
    S1,
    S8,
    S16,
    S32,
    S64,
    S128,
    /// Floating-point type.
    F16,
    F32,
    F64,
    F128,
}

impl Type {
    /// Returns the bit width of this type.
    pub fn bit_width(self) -> u32 {
        match self {
            Type::S1 => 1,
            Type::S8 => 8,
            Type::S16 => 16,
            Type::S32 => 32,
            Type::S64 => 64,
            Type::S128 => 128,
            Type::F16 => 16,
            Type::F32 => 32,
            Type::F64 => 64,
            Type::F128 => 128,
        }
    }

    /// Returns true if this is a floating-point type.
    pub fn is_floating_point(self) -> bool {
        matches!(self, Type::F16 | Type::F32 | Type::F64 | Type::F128)
    }
}

// -----------------------------------------------------------------------
// Legalization Rules
// -----------------------------------------------------------------------

/// A condition that determines when a legalization rule applies.
#[derive(Debug, Clone)]
pub enum LegalizeCondition {
    /// Always apply.
    Always,
    /// Apply when the scalar bit width is less than the threshold.
    NarrowScalar(u32),
    /// Apply when the scalar bit width exceeds the threshold.
    WideScalar(u32),
    /// Apply when the type matches.
    TypeIs(Type),
}

impl LegalizeCondition {
    /// Evaluates whether this condition is satisfied for a given type.
    pub fn evaluate(&self, ty: Option<Type>) -> bool {
        match self {
            LegalizeCondition::Always => true,
            LegalizeCondition::NarrowScalar(threshold) => {
                ty.map_or(false, |t| t.bit_width() < *threshold)
            }
            LegalizeCondition::WideScalar(threshold) => {
                ty.map_or(false, |t| t.bit_width() > *threshold)
            }
            LegalizeCondition::TypeIs(expected) => ty.map_or(false, |t| t == *expected),
        }
    }
}

/// The action to take when a legalization rule matches.
#[derive(Debug, Clone)]
pub enum LegalizeAction {
    /// The instruction is already legal; no action needed.
    Legal,
    /// Narrow the scalar operands to the given width.
    NarrowScalar { new_width: u32 },
    /// Widen the scalar operands to the given width.
    WidenScalar { new_width: u32 },
    /// Replace with a sequence of simpler instructions.
    Lower,
    /// Replace with a library call.
    LibCall(String),
}

/// A single legalization rule: if condition matches, apply action.
#[derive(Debug, Clone)]
pub struct LegalizeRule {
    /// The generic opcode this rule applies to.
    pub opcode: GOpcode,
    /// The condition that must hold.
    pub condition: LegalizeCondition,
    /// The action to take.
    pub action: LegalizeAction,
}

impl LegalizeRule {
    pub fn new(opcode: GOpcode, condition: LegalizeCondition, action: LegalizeAction) -> Self {
        LegalizeRule {
            opcode,
            condition,
            action,
        }
    }
}

/// Legalizer information: a set of rules that describe how to
/// make generic instructions legal for the target.
#[derive(Debug, Clone)]
pub struct LegalizerInfo {
    /// Ordered list of legalization rules.
    pub rules: Vec<LegalizeRule>,
}

impl LegalizerInfo {
    pub fn new() -> Self {
        LegalizerInfo { rules: Vec::new() }
    }

    /// Adds a rule to the legalizer.
    pub fn add_rule(&mut self, rule: LegalizeRule) {
        self.rules.push(rule);
    }

    /// Returns the number of rules.
    pub fn rule_count(&self) -> usize {
        self.rules.len()
    }

    /// Finds the action for a given opcode and type.
    pub fn get_action(&self, opcode: GOpcode, ty: Option<Type>) -> Option<&LegalizeAction> {
        for rule in &self.rules {
            if rule.opcode == opcode && rule.condition.evaluate(ty) {
                return Some(&rule.action);
            }
        }
        None
    }

    /// Creates a default legalizer info for a generic 64-bit target
    /// (e.g., AArch64).
    pub fn default_aarch64() -> Self {
        let mut info = LegalizerInfo::new();
        // Most 32/64-bit operations are legal.
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_SUB,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_MUL,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_AND,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_OR,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_XOR,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        // 128-bit ops need lowering.
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::WideScalar(64),
            LegalizeAction::Lower,
        ));
        // SREM/UREM might need libcalls on some targets.
        info.add_rule(LegalizeRule::new(
            GOpcode::G_SREM,
            LegalizeCondition::WideScalar(32),
            LegalizeAction::LibCall("__moddi3".to_string()),
        ));
        info.add_rule(LegalizeRule::new(
            GOpcode::G_UREM,
            LegalizeCondition::WideScalar(32),
            LegalizeAction::LibCall("__umoddi3".to_string()),
        ));
        info
    }

    /// Creates a default legalizer info for a 32-bit target
    /// (e.g., ARM).
    pub fn default_arm32() -> Self {
        let mut info = LegalizerInfo::new();
        // 32-bit ops are legal.
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        // 64-bit ops need widening or lowering.
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::WideScalar(32),
            LegalizeAction::Lower,
        ));
        info
    }
}

impl Default for LegalizerInfo {
    fn default() -> Self {
        Self::new()
    }
}

// -----------------------------------------------------------------------
// Legalizer
// -----------------------------------------------------------------------

/// The GlobalISel legalizer pass.
///
/// Iterates over instructions in a machine function, consulting
/// the `LegalizerInfo` to determine whether each instruction is
/// legal or needs to be transformed.
pub struct GISelLegalizer {
    /// Number of instructions legalized.
    pub legalized: usize,
    /// Number of instructions that were already legal.
    already_legal: usize,
    /// Number of instructions lowered.
    lowered: usize,
    /// Number of instructions replaced with libcalls.
    libcalls: usize,
    /// Maximum number of iterations (for convergence).
    max_iterations: usize,
}

impl GISelLegalizer {
    pub fn new() -> Self {
        GISelLegalizer {
            legalized: 0,
            already_legal: 0,
            lowered: 0,
            libcalls: 0,
            max_iterations: 32,
        }
    }

    /// Legalizes all instructions in the machine function.
    ///
    /// Iterates until either all instructions are legal or
    /// the maximum number of iterations is reached.
    pub fn legalize(&mut self, mf: &mut GMachineFunction, legalizer_info: &LegalizerInfo) {
        for _iteration in 0..self.max_iterations {
            let mut any_changed = false;

            for block_idx in 0..mf.blocks.len() {
                let block = &mf.blocks[block_idx];
                let inst_count = block.instruction_count();
                for inst_idx in 0..inst_count {
                    // Clone the instruction to avoid borrow issues.
                    let inst = mf.blocks[block_idx].instructions[inst_idx].clone();
                    let changed =
                        self.legalize_instruction(mf, block_idx, inst_idx, &inst, legalizer_info);
                    if changed {
                        any_changed = true;
                        break; // restart scanning after modification
                    } else {
                        self.already_legal += 1;
                    }
                }
                if any_changed {
                    break;
                }
            }

            if !any_changed {
                break; // converged
            }
        }
    }

    /// Attempts to legalize a single instruction.
    ///
    /// Returns true if the instruction was modified.
    pub fn legalize_instruction(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        inst_idx: usize,
        mi: &GInstruction,
        legalizer_info: &LegalizerInfo,
    ) -> bool {
        // Determine the type of the result (if any).
        // In a full implementation, we would track vreg types.
        let ty: Option<Type> = None; // placeholder

        let action = legalizer_info.get_action(mi.opcode, ty);
        match action {
            Some(LegalizeAction::Legal) => {
                self.legalized += 1;
                false // no change needed
            }
            Some(LegalizeAction::NarrowScalar { new_width }) => {
                // Narrow: split wide operations into narrower ones.
                // e.g., G_ADD on i128 → two G_ADD on i64 + carry.
                let _ = new_width;
                self.legalized += 1;
                self.lowered += 1;
                true
            }
            Some(LegalizeAction::WidenScalar { new_width }) => {
                // Widen: promote narrow operands to wider ones.
                // e.g., G_ADD on i8 → zext to i32, G_ADD i32, trunc.
                let _ = new_width;
                self.legalized += 1;
                self.lowered += 1;
                true
            }
            Some(LegalizeAction::Lower) => {
                // Replace with a sequence of simpler instructions.
                self.lower_instruction(mf, block_idx, inst_idx, mi);
                self.lowered += 1;
                true
            }
            Some(LegalizeAction::LibCall(name)) => {
                // Replace with a library call.
                let _name = name.clone();
                let opcode = mi.opcode;
                let dst = mi.def_vreg().unwrap_or(0);
                let uses = mi.uses();
                let src1 = uses.first().and_then(|o| o.as_vreg()).unwrap_or(0);
                let src2 = uses.get(1).and_then(|o| o.as_vreg()).unwrap_or(0);
                let _ = self.libcall_replace(opcode, dst, src1, src2, name);
                self.libcalls += 1;
                true
            }
            None => {
                // Unknown instruction: assume legal.
                self.legalized += 1;
                false
            }
        }
    }

    /// Lowers a complex instruction into simpler ones.
    fn lower_instruction(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        inst_idx: usize,
        mi: &GInstruction,
    ) {
        match mi.opcode {
            GOpcode::G_SDIV => {
                // Lower G_SDIV into a sequence using G_SDIVREM or other primitives.
                // For now: replace with placeholder.
                let _ = mf;
                let _ = block_idx;
                let _ = inst_idx;
                self.legalized += 1;
            }
            GOpcode::G_UDIV => {
                let _ = mf;
                let _ = block_idx;
                let _ = inst_idx;
                self.legalized += 1;
            }
            _ => {
                let _ = mf;
                let _ = block_idx;
                let _ = inst_idx;
                self.legalized += 1;
            }
        }
    }

    /// Replaces an instruction with a library call.
    fn libcall_replace(
        &mut self,
        _opcode: GOpcode,
        _dst: VReg,
        _src1: VReg,
        _src2: VReg,
        _libcall_name: &str,
    ) -> LegalizeResult {
        // In a full implementation, we would:
        // 1. Create a G_GLOBAL_VALUE for the libcall symbol
        // 2. Emit a G_CALL to the libcall
        // 3. Replace uses of the original instruction's def with the call result
        // 4. Remove the original instruction
        self.legalized += 1;
        LegalizeResult::LibCallReplaced(Vec::new())
    }

    /// Returns statistics about legalization.
    pub fn already_legal_count(&self) -> usize {
        self.already_legal
    }

    pub fn lowered_count(&self) -> usize {
        self.lowered
    }

    pub fn libcalls_count(&self) -> usize {
        self.libcalls
    }

    /// Resets counters.
    pub fn reset(&mut self) {
        self.legalized = 0;
        self.already_legal = 0;
        self.lowered = 0;
        self.libcalls = 0;
    }

    /// Returns the maximum number of iterations.
    pub fn max_iterations(&self) -> usize {
        self.max_iterations
    }

    /// Sets the maximum number of iterations.
    pub fn set_max_iterations(&mut self, max: usize) {
        self.max_iterations = max.max(1);
    }
}

impl Default for GISelLegalizer {
    fn default() -> Self {
        Self::new()
    }
}

// ---------------------------------------------------------------------------
// Extended Legalizer: NarrowScalar, WidenScalar, Lower, LegalizeOp Dispatcher
// ---------------------------------------------------------------------------

/// Result of legalizing a single instruction.
#[derive(Debug, Clone)]
pub enum LegalizeResult {
    /// Instruction is already legal.
    AlreadyLegal,
    /// Instruction was narrowed; contains replacement instructions.
    Narrowed(Vec<GInstruction>),
    /// Instruction was widened; contains replacement instructions.
    Widened(Vec<GInstruction>),
    /// Instruction was lowered; contains replacement instructions.
    Lowered(Vec<GInstruction>),
    /// Instruction was replaced with a libcall.
    LibCallReplaced(Vec<GInstruction>),
    /// Instruction is unsupported and cannot be legalized.
    Unsupported,
}

impl GISelLegalizer {
    /// Narrow a scalar operation: replace a wide operation with narrower
    /// operations plus extensions/truncations.
    ///
    /// Example: G_ADD on i64 → G_ADD on i32 (low) + G_ADDC on i32 (high)
    pub fn narrow_scalar(
        &mut self,
        opcode: GOpcode,
        dst: VReg,
        src1: VReg,
        src2: VReg,
        _current_width: u32,
        new_width: u32,
    ) -> LegalizeResult {
        if new_width == 0 || new_width >= _current_width {
            return LegalizeResult::Unsupported;
        }

        let mut replacements = Vec::new();

        match opcode {
            GOpcode::G_ADD | GOpcode::G_SUB | GOpcode::G_AND | GOpcode::G_OR | GOpcode::G_XOR => {
                // Truncate operands to new width.
                let trunc_dst1 = dst + 100; // temporary vreg
                let trunc_dst2 = dst + 200;

                replacements.push(GInstruction::with_operands(
                    GOpcode::G_TRUNC,
                    vec![MOperand::vreg(trunc_dst1), MOperand::vreg(src1)],
                ));
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_TRUNC,
                    vec![MOperand::vreg(trunc_dst2), MOperand::vreg(src2)],
                ));

                // Do the narrow operation.
                let narrow_dst = dst + 300;
                replacements.push(GInstruction::with_operands(
                    opcode,
                    vec![
                        MOperand::vreg(narrow_dst),
                        MOperand::vreg(trunc_dst1),
                        MOperand::vreg(trunc_dst2),
                    ],
                ));

                // Extend the result back.
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_ANYEXT,
                    vec![MOperand::vreg(dst), MOperand::vreg(narrow_dst)],
                ));

                self.lowered += 1;
                LegalizeResult::Narrowed(replacements)
            }
            _ => LegalizeResult::Unsupported,
        }
    }

    /// Widen a scalar operation: replace a narrow operation with wider
    /// operations plus truncations.
    pub fn widen_scalar(
        &mut self,
        opcode: GOpcode,
        dst: VReg,
        src1: VReg,
        src2: VReg,
        _current_width: u32,
        new_width: u32,
    ) -> LegalizeResult {
        if new_width <= _current_width {
            return LegalizeResult::Unsupported;
        }

        let mut replacements = Vec::new();

        match opcode {
            GOpcode::G_ADD | GOpcode::G_SUB | GOpcode::G_AND | GOpcode::G_OR | GOpcode::G_XOR => {
                // Extend operands to new width.
                let ext_dst1 = dst + 100;
                let ext_dst2 = dst + 200;

                replacements.push(GInstruction::with_operands(
                    GOpcode::G_ANYEXT,
                    vec![MOperand::vreg(ext_dst1), MOperand::vreg(src1)],
                ));
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_ANYEXT,
                    vec![MOperand::vreg(ext_dst2), MOperand::vreg(src2)],
                ));

                // Do the wide operation.
                let wide_dst = dst + 300;
                replacements.push(GInstruction::with_operands(
                    opcode,
                    vec![
                        MOperand::vreg(wide_dst),
                        MOperand::vreg(ext_dst1),
                        MOperand::vreg(ext_dst2),
                    ],
                ));

                // Truncate the result to the original width.
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_TRUNC,
                    vec![MOperand::vreg(dst), MOperand::vreg(wide_dst)],
                ));

                self.lowered += 1;
                LegalizeResult::Widened(replacements)
            }
            _ => LegalizeResult::Unsupported,
        }
    }

    /// Lower an unsupported operation into a sequence of supported operations.
    pub fn lower(&mut self, opcode: GOpcode, dst: VReg, src1: VReg, src2: VReg) -> LegalizeResult {
        let mut replacements = Vec::new();

        match opcode {
            GOpcode::G_CTLZ => {
                // Lower CTLZ using a combination of shifts and bit ops.
                // Typical expansion: CTLZ(x) = bit_width - 1 - find_msb(x)
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_CONSTANT,
                    vec![MOperand::vreg(dst), MOperand::imm(31)],
                ));
                self.lowered += 1;
                LegalizeResult::Lowered(replacements)
            }
            GOpcode::G_BSWAP => {
                // Lower BSWAP using shifts and OR.
                let tmp1 = dst + 100;
                let tmp2 = dst + 200;
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_SHL,
                    vec![
                        MOperand::vreg(tmp1),
                        MOperand::vreg(src1),
                        MOperand::imm(24),
                    ],
                ));
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_LSHR,
                    vec![
                        MOperand::vreg(tmp2),
                        MOperand::vreg(src1),
                        MOperand::imm(24),
                    ],
                ));
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_OR,
                    vec![
                        MOperand::vreg(dst),
                        MOperand::vreg(tmp1),
                        MOperand::vreg(tmp2),
                    ],
                ));
                self.lowered += 1;
                LegalizeResult::Lowered(replacements)
            }
            GOpcode::G_FMA => {
                // Lower FMA: mul + add.
                let mul_dst = dst + 100;
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_FMUL,
                    vec![
                        MOperand::vreg(mul_dst),
                        MOperand::vreg(src1),
                        MOperand::vreg(src2),
                    ],
                ));
                // Note: the third operand for FMA is handled separately.
                replacements.push(GInstruction::with_operands(
                    GOpcode::G_FADD,
                    vec![
                        MOperand::vreg(dst),
                        MOperand::vreg(mul_dst),
                        MOperand::vreg(dst + 200),
                    ],
                ));
                self.lowered += 1;
                LegalizeResult::Lowered(replacements)
            }
            _ => LegalizeResult::Unsupported,
        }
    }

    /// Handle fewer-elements-vector: decompose a vector operation into
    /// scalar operations.
    pub fn fewer_elements_vector(
        &mut self,
        _opcode: GOpcode,
        _dst: VReg,
        _src: VReg,
        _num_elements: usize,
    ) -> Vec<GInstruction> {
        // In a full implementation, this would:
        // 1. Extract each element of the vector
        // 2. Apply the scalar operation
        // 3. Rebuild the result vector
        self.lowered += 1;
        Vec::new()
    }

    /// Handle more-elements-vector: combine scalar operations into a
    /// vector operation.
    pub fn more_elements_vector(
        &mut self,
        _opcode: GOpcode,
        _dst: VReg,
        _src: VReg,
        _target_elements: usize,
    ) -> Vec<GInstruction> {
        // In a full implementation, this would:
        // 1. Replicate the scalar value across vector lanes
        // 2. Combine multiple scalars into a vector
        self.lowered += 1;
        Vec::new()
    }

    /// LegalizeOp dispatcher: route an instruction through the appropriate
    /// legalization path based on the target's legalizer info.
    pub fn legalize_op(&mut self, inst: &GInstruction, info: &LegalizerInfo) -> LegalizeResult {
        let opcode = inst.opcode;
        let action = info.get_action(opcode, None).cloned();

        // Extract operands.
        let dst = inst.def_vreg().unwrap_or(0);
        let uses = inst.uses();
        let src1 = uses.first().and_then(|o| o.as_vreg()).unwrap_or(0);
        let src2 = uses.get(1).and_then(|o| o.as_vreg()).unwrap_or(0);

        match action {
            Some(LegalizeAction::Legal) => LegalizeResult::AlreadyLegal,
            Some(LegalizeAction::NarrowScalar { new_width }) => {
                self.narrow_scalar(opcode, dst, src1, src2, 64, new_width)
            }
            Some(LegalizeAction::WidenScalar { new_width }) => {
                self.widen_scalar(opcode, dst, src1, src2, 32, new_width)
            }
            Some(LegalizeAction::Lower) => self.lower(opcode, dst, src1, src2),
            Some(LegalizeAction::LibCall(name)) => {
                self.libcall_replace(opcode, dst, src1, src2, &name)
            }
            None => LegalizeResult::Unsupported,
        }
    }

    /// Run the legalizer with target-specific legalization rules.
    pub fn legalize_with_rules(
        &mut self,
        mf: &mut GMachineFunction,
        info: &LegalizerInfo,
    ) -> usize {
        self.reset();
        let mut total_legalized = 0;

        for _iteration in 0..self.max_iterations {
            let mut changed = false;

            for block_idx in 0..mf.blocks.len() {
                let mut new_insts: Vec<GInstruction> = Vec::new();
                let mut remove_indices: Vec<usize> = Vec::new();

                for (i_idx, inst) in mf.blocks[block_idx].instructions.iter().enumerate() {
                    match self.legalize_op(inst, info) {
                        LegalizeResult::AlreadyLegal => {
                            self.already_legal += 1;
                        }
                        LegalizeResult::Narrowed(replacements)
                        | LegalizeResult::Widened(replacements)
                        | LegalizeResult::Lowered(replacements)
                        | LegalizeResult::LibCallReplaced(replacements) => {
                            remove_indices.push(i_idx);
                            new_insts.extend(replacements);
                            changed = true;
                            total_legalized += 1;
                        }
                        LegalizeResult::Unsupported => {
                            // Leave as-is.
                        }
                    }
                }

                // Remove old instructions and insert replacements.
                for &idx in remove_indices.iter().rev() {
                    if idx < mf.blocks[block_idx].instructions.len() {
                        mf.blocks[block_idx].instructions.remove(idx);
                    }
                }
                mf.blocks[block_idx].instructions.extend(new_insts);
            }

            if !changed {
                break;
            }
        }

        total_legalized
    }
}

// ---------------------------------------------------------------------------
// Target-Specific Legalizer Rules and Type Legalization
// ---------------------------------------------------------------------------

impl LegalizerInfo {
    /// Default legalizer info for x86_64 target.
    pub fn default_x86_64() -> Self {
        let mut info = LegalizerInfo::new();

        // All basic scalar ops are legal on x86_64.
        let scalar_ops = [
            GOpcode::G_ADD,
            GOpcode::G_SUB,
            GOpcode::G_MUL,
            GOpcode::G_AND,
            GOpcode::G_OR,
            GOpcode::G_XOR,
            GOpcode::G_SHL,
            GOpcode::G_LSHR,
            GOpcode::G_ASHR,
            GOpcode::G_LOAD,
            GOpcode::G_STORE,
            GOpcode::G_BR,
            GOpcode::G_BRCOND,
            GOpcode::G_RET,
            GOpcode::G_CONSTANT,
            GOpcode::G_FCONSTANT,
            GOpcode::G_FADD,
            GOpcode::G_FSUB,
            GOpcode::G_FMUL,
            GOpcode::G_FDIV,
            GOpcode::G_ICMP,
            GOpcode::G_FCMP,
            GOpcode::G_SELECT,
            GOpcode::G_PHI,
            GOpcode::G_TRUNC,
            GOpcode::G_ZEXT,
            GOpcode::G_SEXT,
            GOpcode::G_ANYEXT,
            GOpcode::G_PTRTOINT,
            GOpcode::G_INTTOPTR,
            GOpcode::G_BITCAST,
            GOpcode::COPY,
        ];

        for op in &scalar_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::Legal,
            ));
        }

        // Operations that need lowering on x86_64.
        let lowering_ops = [
            (GOpcode::G_CTLZ, "ctlz"),
            (GOpcode::G_CTTZ, "cttz"),
            (GOpcode::G_CTPOP, "ctpop"),
            (GOpcode::G_BSWAP, "bswap"),
            (GOpcode::G_BITREVERSE, "bitreverse"),
        ];

        for (op, _name) in &lowering_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::LibCall(String::new()),
            ));
        }

        // Operations that need widening on x86_64.
        let widening_ops = [
            GOpcode::G_SDIV,
            GOpcode::G_UDIV,
            GOpcode::G_SREM,
            GOpcode::G_UREM,
        ];

        for op in &widening_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::NarrowScalar(64),
                LegalizeAction::WidenScalar { new_width: 64 },
            ));
        }

        info
    }

    /// Default legalizer info for RISC-V 64 target.
    pub fn default_riscv64() -> Self {
        let mut info = LegalizerInfo::new();

        // RISC-V has basic integer ops.
        let scalar_ops = [
            GOpcode::G_ADD,
            GOpcode::G_SUB,
            GOpcode::G_AND,
            GOpcode::G_OR,
            GOpcode::G_XOR,
            GOpcode::G_SHL,
            GOpcode::G_LSHR,
            GOpcode::G_ASHR,
            GOpcode::G_LOAD,
            GOpcode::G_STORE,
            GOpcode::G_BR,
            GOpcode::G_BRCOND,
            GOpcode::G_RET,
            GOpcode::G_CONSTANT,
            GOpcode::G_ICMP,
            GOpcode::G_SELECT,
            GOpcode::G_PHI,
            GOpcode::G_TRUNC,
            GOpcode::G_ZEXT,
            GOpcode::G_SEXT,
            GOpcode::COPY,
        ];

        for op in &scalar_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::Legal,
            ));
        }

        // RISC-V needs M extension for multiply/divide.
        let mul_div_ops = [
            GOpcode::G_MUL,
            GOpcode::G_SDIV,
            GOpcode::G_UDIV,
            GOpcode::G_SREM,
            GOpcode::G_UREM,
        ];

        for op in &mul_div_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::LibCall(String::new()),
            ));
        }

        // No hardware floating-point by default.
        let fp_ops = [
            GOpcode::G_FADD,
            GOpcode::G_FSUB,
            GOpcode::G_FMUL,
            GOpcode::G_FDIV,
            GOpcode::G_FNEG,
            GOpcode::G_FABS,
            GOpcode::G_FSQRT,
            GOpcode::G_FCMP,
            GOpcode::G_FCONSTANT,
        ];

        for op in &fp_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::LibCall(String::new()),
            ));
        }

        info
    }

    /// Check if all instructions in a function are legal according to
    /// this legalizer info.
    pub fn check_function_legality(&self, mf: &GMachineFunction) -> Vec<String> {
        let mut illegal = Vec::new();

        for (bb_idx, block) in mf.blocks.iter().enumerate() {
            for (i_idx, inst) in block.instructions.iter().enumerate() {
                let action = self.get_action(inst.opcode, None);
                match action {
                    Some(LegalizeAction::Legal) => {}
                    Some(a) => {
                        illegal.push(format!(
                            "BB{} inst{}: {:?} requires {:?}",
                            bb_idx, i_idx, inst.opcode, a
                        ));
                    }
                    None => {}
                }
            }
        }

        illegal
    }
}

// ---------------------------------------------------------------------------
// Target-Specific Configuration for Various Architectures
// ---------------------------------------------------------------------------

/// Target legalization configuration.
#[derive(Debug, Clone)]
pub struct TargetConfig {
    /// Maximum native scalar width in bits.
    pub max_scalar_width: u32,
    /// Whether the target supports unaligned memory accesses.
    pub supports_unaligned_access: bool,
    /// Whether the target has hardware floating-point.
    pub has_hardware_fp: bool,
    /// Whether the target supports vector instructions.
    pub has_vector: bool,
    /// Maximum vector width in bits.
    pub max_vector_width: u32,
    /// Whether the target uses predicated execution.
    pub has_predication: bool,
}

impl Default for TargetConfig {
    fn default() -> Self {
        TargetConfig {
            max_scalar_width: 64,
            supports_unaligned_access: true,
            has_hardware_fp: true,
            has_vector: true,
            max_vector_width: 256,
            has_predication: false,
        }
    }
}

/// Factory to create legalizer info for common targets.
pub struct LegalizerFactory;

impl LegalizerFactory {
    /// Create legalizer info for the x86_64 target.
    pub fn for_x86_64() -> LegalizerInfo {
        LegalizerInfo::default_x86_64()
    }

    /// Create legalizer info for the aarch64 target.
    pub fn for_aarch64() -> LegalizerInfo {
        LegalizerInfo::default_aarch64()
    }

    /// Create legalizer info for the arm32 target.
    pub fn for_arm32() -> LegalizerInfo {
        LegalizerInfo::default_arm32()
    }

    /// Create legalizer info for the RISC-V 64 target.
    pub fn for_riscv64() -> LegalizerInfo {
        LegalizerInfo::default_riscv64()
    }

    /// Create legalizer info for a generic target with the given config.
    pub fn for_config(config: &TargetConfig) -> LegalizerInfo {
        let mut info = LegalizerInfo::new();

        // Scalar operations are legal up to the target's width.
        let scalar_ops = [
            GOpcode::G_ADD,
            GOpcode::G_SUB,
            GOpcode::G_AND,
            GOpcode::G_OR,
            GOpcode::G_XOR,
            GOpcode::G_SHL,
            GOpcode::G_LSHR,
            GOpcode::G_ASHR,
            GOpcode::G_CONSTANT,
            GOpcode::G_LOAD,
            GOpcode::G_STORE,
            GOpcode::G_BR,
            GOpcode::G_BRCOND,
            GOpcode::G_RET,
            GOpcode::G_ICMP,
            GOpcode::G_SELECT,
            GOpcode::G_PHI,
            GOpcode::COPY,
        ];

        for op in &scalar_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::Legal,
            ));
        }

        // Extensions and truncations.
        let ext_ops = [
            GOpcode::G_TRUNC,
            GOpcode::G_ZEXT,
            GOpcode::G_SEXT,
            GOpcode::G_ANYEXT,
            GOpcode::G_PTRTOINT,
            GOpcode::G_INTTOPTR,
            GOpcode::G_BITCAST,
        ];

        for op in &ext_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::Legal,
            ));
        }

        // FP ops depend on hardware support.
        let fp_ops = [
            GOpcode::G_FADD,
            GOpcode::G_FSUB,
            GOpcode::G_FMUL,
            GOpcode::G_FDIV,
            GOpcode::G_FNEG,
            GOpcode::G_FABS,
            GOpcode::G_FSQRT,
            GOpcode::G_FCMP,
            GOpcode::G_FCONSTANT,
            GOpcode::G_FPTRUNC,
            GOpcode::G_FPEXT,
            GOpcode::G_FPTOUI,
            GOpcode::G_FPTOSI,
            GOpcode::G_UITOFP,
            GOpcode::G_SITOFP,
        ];

        for op in &fp_ops {
            if config.has_hardware_fp {
                info.add_rule(LegalizeRule::new(
                    *op,
                    LegalizeCondition::Always,
                    LegalizeAction::Legal,
                ));
            } else {
                info.add_rule(LegalizeRule::new(
                    *op,
                    LegalizeCondition::Always,
                    LegalizeAction::LibCall(String::new()),
                ));
            }
        }

        // Bitwise manipulation ops are lowered.
        let bit_ops = [
            GOpcode::G_CTLZ,
            GOpcode::G_CTTZ,
            GOpcode::G_CTPOP,
            GOpcode::G_BSWAP,
            GOpcode::G_BITREVERSE,
        ];

        for op in &bit_ops {
            info.add_rule(LegalizeRule::new(
                *op,
                LegalizeCondition::Always,
                LegalizeAction::LibCall(String::new()),
            ));
        }

        info
    }
}

// ---------------------------------------------------------------------------
// Legalization Utilities and Debug Helpers
// ---------------------------------------------------------------------------

/// Statistics from a legalization run.
#[derive(Debug, Clone, Default)]
pub struct LegalizationStats {
    /// Number of instructions that were already legal.
    pub already_legal: usize,
    /// Number of instructions narrowed.
    pub narrowed: usize,
    /// Number of instructions widened.
    pub widened: usize,
    /// Number of instructions lowered.
    pub lowered: usize,
    /// Number of instructions replaced with libcalls.
    pub libcalls: usize,
    /// Number of instructions that could not be legalized.
    pub unsupported: usize,
    /// Total instructions processed.
    pub total: usize,
}

impl GISelLegalizer {
    /// Legalize a function and collect statistics.
    pub fn legalize_with_stats(
        &mut self,
        mf: &mut GMachineFunction,
        info: &LegalizerInfo,
    ) -> LegalizationStats {
        self.reset();
        let mut stats = LegalizationStats::default();

        for _iteration in 0..self.max_iterations {
            let mut changed = false;

            for block in &mut mf.blocks {
                let mut new_insts: Vec<GInstruction> = Vec::new();
                let mut remove_indices: Vec<usize> = Vec::new();

                for (i_idx, inst) in block.instructions.iter().enumerate() {
                    stats.total += 1;

                    match self.legalize_op(inst, info) {
                        LegalizeResult::AlreadyLegal => {
                            stats.already_legal += 1;
                        }
                        LegalizeResult::Narrowed(repl) => {
                            remove_indices.push(i_idx);
                            new_insts.extend(repl);
                            stats.narrowed += 1;
                            changed = true;
                        }
                        LegalizeResult::Widened(repl) => {
                            remove_indices.push(i_idx);
                            new_insts.extend(repl);
                            stats.widened += 1;
                            changed = true;
                        }
                        LegalizeResult::Lowered(repl) => {
                            remove_indices.push(i_idx);
                            new_insts.extend(repl);
                            stats.lowered += 1;
                            changed = true;
                        }
                        LegalizeResult::LibCallReplaced(repl) => {
                            remove_indices.push(i_idx);
                            new_insts.extend(repl);
                            stats.libcalls += 1;
                            changed = true;
                        }
                        LegalizeResult::Unsupported => {
                            stats.unsupported += 1;
                        }
                    }
                }

                for &idx in remove_indices.iter().rev() {
                    if idx < block.instructions.len() {
                        block.instructions.remove(idx);
                    }
                }
                block.instructions.extend(new_insts);
            }

            if !changed {
                break;
            }
        }

        stats
    }

    /// Check if a specific opcode is legal for the target.
    pub fn is_op_legal(&self, opcode: GOpcode, info: &LegalizerInfo) -> bool {
        matches!(info.get_action(opcode, None), Some(LegalizeAction::Legal))
    }

    /// Get a human-readable description of what action is needed.
    pub fn describe_action(&self, opcode: GOpcode, info: &LegalizerInfo) -> String {
        match info.get_action(opcode, None) {
            Some(LegalizeAction::Legal) => format!("{:?} is legal", opcode),
            Some(LegalizeAction::NarrowScalar { new_width }) => {
                format!("{:?} must be narrowed to {} bits", opcode, new_width)
            }
            Some(LegalizeAction::WidenScalar { new_width }) => {
                format!("{:?} must be widened to {} bits", opcode, new_width)
            }
            Some(LegalizeAction::Lower) => format!("{:?} must be lowered", opcode),
            Some(LegalizeAction::LibCall(name)) => {
                format!("{:?} requires libcall '{}'", opcode, name)
            }
            None => format!("{:?} has no known action", opcode),
        }
    }
}

// ============================================================================
// NarrowScalar Legalization
// ============================================================================

/// NarrowScalarLegalizer implements narrowing for operations on types
/// wider than the target supports. For example, if the target supports
/// max i64 but the IR has an i128 G_ADD, it narrows to 2×i64 operations
/// plus carry handling.
#[derive(Debug, Clone)]
pub struct NarrowScalarLegalizer {
    /// Maximum supported scalar width.
    pub max_width: u32,
}

impl NarrowScalarLegalizer {
    /// Create a new narrow-scalar legalizer.
    pub fn new(max_width: u32) -> Self {
        Self { max_width }
    }

    /// Check if a bit width needs narrowing.
    pub fn needs_narrowing(&self, width: u32) -> bool {
        width > self.max_width
    }

    /// Narrow a G_ADD operation.
    ///
    /// Splits into lo-part add + hi-part add with carry.
    pub fn narrow_add(
        &self,
        a_lo: VReg,
        a_hi: VReg,
        b_lo: VReg,
        b_hi: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Add low parts
        let result_lo = a_lo.wrapping_add(100);
        seq.push((
            GOpcode::G_UADDO,
            vec![
                MOperand::vreg(result_lo),
                MOperand::vreg(a_lo),
                MOperand::vreg(b_lo),
            ],
        ));

        // Add high parts with carry
        let result_hi = a_hi.wrapping_add(101);
        let carry = result_lo.wrapping_add(1);
        seq.push((
            GOpcode::G_ADD,
            vec![
                MOperand::vreg(carry),
                MOperand::vreg(a_hi),
                MOperand::vreg(b_hi),
            ],
        ));
        seq.push((
            GOpcode::G_ADD,
            vec![
                MOperand::vreg(result_hi),
                MOperand::vreg(carry),
                MOperand::vreg(result_lo),
            ],
        ));

        seq
    }

    /// Narrow a G_SUB operation.
    pub fn narrow_sub(
        &self,
        a_lo: VReg,
        a_hi: VReg,
        b_lo: VReg,
        b_hi: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Subtract low parts with borrow
        let result_lo = a_lo.wrapping_add(100);
        seq.push((
            GOpcode::G_USUBO,
            vec![
                MOperand::vreg(result_lo),
                MOperand::vreg(a_lo),
                MOperand::vreg(b_lo),
            ],
        ));

        // Subtract high parts with borrow
        let result_hi = a_hi.wrapping_add(101);
        let borrow = a_lo.wrapping_add(1);
        seq.push((
            GOpcode::G_SUB,
            vec![
                MOperand::vreg(borrow),
                MOperand::vreg(a_hi),
                MOperand::vreg(b_hi),
            ],
        ));
        seq.push((
            GOpcode::G_SUB,
            vec![
                MOperand::vreg(result_hi),
                MOperand::vreg(borrow),
                MOperand::vreg(result_lo),
            ],
        ));

        seq
    }

    /// Narrow a G_MUL operation (simplified: split and combine).
    pub fn narrow_mul(
        &self,
        a_lo: VReg,
        a_hi: VReg,
        b_lo: VReg,
        b_hi: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Compute cross products and sum
        let t1 = a_lo.wrapping_add(100);
        seq.push((
            GOpcode::G_MUL,
            vec![
                MOperand::vreg(t1),
                MOperand::vreg(a_lo),
                MOperand::vreg(b_lo),
            ],
        ));

        let t2 = a_lo.wrapping_add(101);
        seq.push((
            GOpcode::G_MUL,
            vec![
                MOperand::vreg(t2),
                MOperand::vreg(a_lo),
                MOperand::vreg(b_hi),
            ],
        ));

        let t3 = a_lo.wrapping_add(102);
        seq.push((
            GOpcode::G_MUL,
            vec![
                MOperand::vreg(t3),
                MOperand::vreg(a_hi),
                MOperand::vreg(b_lo),
            ],
        ));

        let lo = t1;
        let hi = a_lo.wrapping_add(103);
        seq.push((
            GOpcode::G_ADD,
            vec![MOperand::vreg(hi), MOperand::vreg(t2), MOperand::vreg(t3)],
        ));

        seq
    }
}

impl Default for NarrowScalarLegalizer {
    fn default() -> Self {
        Self::new(64)
    }
}

// ============================================================================
// WidenScalar Legalization
// ============================================================================

/// WidenScalarLegalizer handles promotion of narrow scalar types to
/// wider legal types. For example, i8 G_ADD → i32 G_ADD + truncate.
#[derive(Debug, Clone)]
pub struct WidenScalarLegalizer {
    /// Minimum legal scalar width.
    pub min_width: u32,
}

impl WidenScalarLegalizer {
    /// Create a new widen-scalar legalizer.
    pub fn new(min_width: u32) -> Self {
        Self { min_width }
    }

    /// Check if a bit width needs widening.
    pub fn needs_widening(&self, width: u32) -> bool {
        width < self.min_width
    }

    /// Widen a binary operation: promote operands to legal type,
    /// perform operation, truncate result.
    pub fn widen_binary_op(
        &self,
        opcode: GOpcode,
        dst: VReg,
        a: VReg,
        b: VReg,
        original_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Extend operands to legal width
        let a_ext = a.wrapping_add(1000);
        let b_ext = b.wrapping_add(1001);
        seq.push((
            GOpcode::G_ANYEXT,
            vec![MOperand::vreg(a_ext), MOperand::vreg(a)],
        ));
        seq.push((
            GOpcode::G_ANYEXT,
            vec![MOperand::vreg(b_ext), MOperand::vreg(b)],
        ));

        // Perform operation at legal width
        let wide_result = dst.wrapping_add(1002);
        seq.push((
            opcode,
            vec![
                MOperand::vreg(wide_result),
                MOperand::vreg(a_ext),
                MOperand::vreg(b_ext),
            ],
        ));

        // Truncate result to original width
        seq.push((
            GOpcode::G_TRUNC,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(wide_result),
                MOperand::imm(original_width as i64),
            ],
        ));

        seq
    }

    /// Widen a unary operation.
    pub fn widen_unary_op(
        &self,
        opcode: GOpcode,
        dst: VReg,
        src: VReg,
        original_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        let src_ext = src.wrapping_add(1000);
        seq.push((
            GOpcode::G_ANYEXT,
            vec![MOperand::vreg(src_ext), MOperand::vreg(src)],
        ));

        let wide_result = dst.wrapping_add(1001);
        seq.push((
            opcode,
            vec![MOperand::vreg(wide_result), MOperand::vreg(src_ext)],
        ));

        seq.push((
            GOpcode::G_TRUNC,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(wide_result),
                MOperand::imm(original_width as i64),
            ],
        ));

        seq
    }
}

impl Default for WidenScalarLegalizer {
    fn default() -> Self {
        Self::new(32)
    }
}

// ============================================================================
// Lowering: Bit Manipulation (CTLZ, CTTZ, CTPOP, BSWAP, BITREVERSE)
// ============================================================================

/// BitManipLowerer lowers bit manipulation operations to sequences
/// of simpler instructions when the target lacks native support.
#[derive(Debug, Clone)]
pub struct BitManipLowerer {
    /// Whether the target has native CTLZ.
    pub has_ctlz: bool,
    /// Whether the target has native CTTZ.
    pub has_cttz: bool,
    /// Whether the target has native CTPOP.
    pub has_ctpop: bool,
    /// Whether the target has native BSWAP.
    pub has_bswap: bool,
    /// Whether the target has native BITREVERSE.
    pub has_bitreverse: bool,
}

impl BitManipLowerer {
    /// Create a new bit-manip lowerer.
    pub fn new() -> Self {
        Self {
            has_ctlz: false,
            has_cttz: false,
            has_ctpop: false,
            has_bswap: false,
            has_bitreverse: false,
        }
    }

    /// Lower G_CTLZ to a bit-manipulation sequence.
    pub fn lower_ctlz(
        &self,
        dst: VReg,
        src: VReg,
        bit_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Algorithm: x |= x >> 1; x |= x >> 2; x |= x >> 4; ...
        // Then: ctlz(x) = ctpop(~x)
        let t1 = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(t1), MOperand::vreg(src), MOperand::imm(1)],
        ));
        let t2 = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_OR,
            vec![MOperand::vreg(t2), MOperand::vreg(src), MOperand::vreg(t1)],
        ));

        // Propagate bits: repeat with increasing shifts
        for shift in &[2u32, 4, 8, 16, 32] {
            if *shift >= bit_width {
                break;
            }
            let tn = dst.wrapping_add(110 + shift);
            let tm = dst.wrapping_add(120 + shift);
            seq.push((
                GOpcode::G_LSHR,
                vec![
                    MOperand::vreg(tn),
                    MOperand::vreg(t2),
                    MOperand::imm(*shift as i64),
                ],
            ));
            seq.push((
                GOpcode::G_OR,
                vec![MOperand::vreg(tm), MOperand::vreg(t2), MOperand::vreg(tn)],
            ));
        }

        // Count the set bits = CTPOP(~x)
        let inverted = dst.wrapping_add(200);
        seq.push((
            GOpcode::G_XOR,
            vec![
                MOperand::vreg(inverted),
                MOperand::vreg(t2),
                MOperand::imm(-1),
            ],
        ));

        // Lower CTPOP of inverted value
        seq.append(&mut self.lower_ctpop(dst, inverted, bit_width));

        seq
    }

    /// Lower G_CTTZ to a bit-manipulation sequence.
    pub fn lower_cttz(
        &self,
        dst: VReg,
        src: VReg,
        bit_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        // CTTZ(x) = CTLZ(reverse_bits(x))
        let mut seq = Vec::new();

        let reversed = dst.wrapping_add(200);
        seq.append(&mut self.lower_bitreverse(reversed, src, bit_width));
        seq.append(&mut self.lower_ctlz(dst, reversed, bit_width));

        seq
    }

    /// Lower G_CTPOP to a bit-manipulation sequence.
    pub fn lower_ctpop(
        &self,
        dst: VReg,
        src: VReg,
        bit_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        // Standard popcount algorithm:
        // x = (x & 0x5555...) + ((x >> 1) & 0x5555...)
        // x = (x & 0x3333...) + ((x >> 2) & 0x3333...)
        // x = (x & 0x0F0F...) + ((x >> 4) & 0x0F0F...)
        // ...
        let mut seq = Vec::new();

        let t1 = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(t1), MOperand::vreg(src), MOperand::imm(1)],
        ));
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(t1),
                MOperand::vreg(t1),
                MOperand::imm(0x5555555555555555i64),
            ],
        ));

        let t2 = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(t2),
                MOperand::vreg(src),
                MOperand::imm(0x5555555555555555i64),
            ],
        ));

        let sum1 = dst.wrapping_add(102);
        seq.push((
            GOpcode::G_ADD,
            vec![MOperand::vreg(sum1), MOperand::vreg(t1), MOperand::vreg(t2)],
        ));

        // Next step: mask with 0x3333..., shift by 2
        let s1 = dst.wrapping_add(103);
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(s1), MOperand::vreg(sum1), MOperand::imm(2)],
        ));
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(s1),
                MOperand::vreg(s1),
                MOperand::imm(0x3333333333333333i64),
            ],
        ));
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(sum1),
                MOperand::imm(0x3333333333333333i64),
            ],
        ));
        seq.push((
            GOpcode::G_ADD,
            vec![MOperand::vreg(dst), MOperand::vreg(dst), MOperand::vreg(s1)],
        ));

        seq
    }

    /// Lower G_BSWAP to a shift+or sequence.
    pub fn lower_bswap(
        &self,
        dst: VReg,
        src: VReg,
        bit_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();
        let byte_count = bit_width / 8;

        let mut accumulator = dst.wrapping_add(200);

        // Load byte 0, shift to position (bytes-1)*8
        for i in 0..byte_count {
            let byte_src = src.wrapping_add(100 + i);
            let shift_amount = (i * 8) as i64;
            let target_shift = ((byte_count - 1 - i) * 8) as i64;

            if i == 0 {
                // First byte: mask and shift
                seq.push((
                    GOpcode::G_AND,
                    vec![
                        MOperand::vreg(byte_src),
                        MOperand::vreg(src),
                        MOperand::imm(0xFF),
                    ],
                ));
                seq.push((
                    GOpcode::G_SHL,
                    vec![
                        MOperand::vreg(accumulator),
                        MOperand::vreg(byte_src),
                        MOperand::imm(target_shift),
                    ],
                ));
            } else {
                let shifted = src.wrapping_add(300 + i);
                seq.push((
                    GOpcode::G_LSHR,
                    vec![
                        MOperand::vreg(shifted),
                        MOperand::vreg(src),
                        MOperand::imm(shift_amount),
                    ],
                ));
                seq.push((
                    GOpcode::G_AND,
                    vec![
                        MOperand::vreg(byte_src),
                        MOperand::vreg(shifted),
                        MOperand::imm(0xFF),
                    ],
                ));
                let shifted_byte = src.wrapping_add(400 + i);
                seq.push((
                    GOpcode::G_SHL,
                    vec![
                        MOperand::vreg(shifted_byte),
                        MOperand::vreg(byte_src),
                        MOperand::imm(target_shift),
                    ],
                ));

                let new_acc = src.wrapping_add(500 + i);
                seq.push((
                    GOpcode::G_OR,
                    vec![
                        MOperand::vreg(new_acc),
                        MOperand::vreg(accumulator),
                        MOperand::vreg(shifted_byte),
                    ],
                ));
                accumulator = new_acc;
            }
        }

        // Final copy to dst
        if accumulator != dst {
            seq.push((
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(accumulator)],
            ));
        }

        seq
    }

    /// Lower G_BITREVERSE to byte-reverse + bit-reverse sequence.
    pub fn lower_bitreverse(
        &self,
        dst: VReg,
        src: VReg,
        bit_width: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        // Swap bits pairwise, then nibble-wise, then byte-wise
        let mut seq = Vec::new();

        let mut current = src;
        let mut next = dst.wrapping_add(300);

        // Swap bits within each pair: ((x & 0xAA...) >> 1) | ((x & 0x55...) << 1)
        let t1 = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(t1),
                MOperand::vreg(current),
                MOperand::imm(0xAAAAAAAAAAAAAAAAu64 as i64),
            ],
        ));
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(t1), MOperand::vreg(t1), MOperand::imm(1)],
        ));

        let t2 = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_AND,
            vec![
                MOperand::vreg(t2),
                MOperand::vreg(current),
                MOperand::imm(0x5555555555555555i64),
            ],
        ));
        seq.push((
            GOpcode::G_SHL,
            vec![MOperand::vreg(t2), MOperand::vreg(t2), MOperand::imm(1)],
        ));

        seq.push((
            GOpcode::G_OR,
            vec![MOperand::vreg(next), MOperand::vreg(t1), MOperand::vreg(t2)],
        ));

        // Then byte-reverse (use BSWAP if available, otherwise lower)
        if self.has_bswap {
            seq.push((
                GOpcode::G_BSWAP,
                vec![MOperand::vreg(dst), MOperand::vreg(next)],
            ));
        } else {
            seq.append(&mut self.lower_bswap(dst, next, bit_width));
        }

        seq
    }
}

impl Default for BitManipLowerer {
    fn default() -> Self {
        Self::new()
    }
}

// ============================================================================
// Funnel Shift Lowering (FSHL, FSHR)
// ============================================================================

/// FunnelShiftLowerer lowers G_FSHL and G_FSHR to shift+or sequences
/// on targets without native funnel shift support.
#[derive(Debug, Clone)]
pub struct FunnelShiftLowerer {
    /// Whether the target has native funnel shift.
    pub has_funnel_shift: bool,
}

impl FunnelShiftLowerer {
    /// Create a new funnel shift lowerer.
    pub fn new() -> Self {
        Self {
            has_funnel_shift: false,
        }
    }

    /// Lower G_FSHL(dst, a, b, amt) to:
    ///   (a << amt) | (b >> (width - amt))
    pub fn lower_fshl(
        &self,
        dst: VReg,
        a: VReg,
        b: VReg,
        amt: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // t1 = a << amt
        let t1 = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_SHL,
            vec![MOperand::vreg(t1), MOperand::vreg(a), MOperand::vreg(amt)],
        ));

        // t2 = width - amt
        let t2 = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(t2), MOperand::imm(64)],
        ));
        let t3 = dst.wrapping_add(102);
        seq.push((
            GOpcode::G_SUB,
            vec![MOperand::vreg(t3), MOperand::vreg(t2), MOperand::vreg(amt)],
        ));

        // t4 = b >> (width - amt)
        let t4 = dst.wrapping_add(103);
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(t4), MOperand::vreg(b), MOperand::vreg(t3)],
        ));

        // result = t1 | t4
        seq.push((
            GOpcode::G_OR,
            vec![MOperand::vreg(dst), MOperand::vreg(t1), MOperand::vreg(t4)],
        ));

        seq
    }

    /// Lower G_FSHR(dst, a, b, amt) to:
    ///   (a >> amt) | (b << (width - amt))
    pub fn lower_fshr(
        &self,
        dst: VReg,
        a: VReg,
        b: VReg,
        amt: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // t1 = a >> amt
        let t1 = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_LSHR,
            vec![MOperand::vreg(t1), MOperand::vreg(a), MOperand::vreg(amt)],
        ));

        // t2 = width - amt
        let t2 = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(t2), MOperand::imm(64)],
        ));
        let t3 = dst.wrapping_add(102);
        seq.push((
            GOpcode::G_SUB,
            vec![MOperand::vreg(t3), MOperand::vreg(t2), MOperand::vreg(amt)],
        ));

        // t4 = b << (width - amt)
        let t4 = dst.wrapping_add(103);
        seq.push((
            GOpcode::G_SHL,
            vec![MOperand::vreg(t4), MOperand::vreg(b), MOperand::vreg(t3)],
        ));

        // result = t1 | t4
        seq.push((
            GOpcode::G_OR,
            vec![MOperand::vreg(dst), MOperand::vreg(t1), MOperand::vreg(t4)],
        ));

        seq
    }
}

impl Default for FunnelShiftLowerer {
    fn default() -> Self {
        Self::new()
    }
}

// ============================================================================
// Vector Element Count Legalization
// ============================================================================

/// VectorElementLegalizer legalizes vectors by element count.
/// Splits wide vectors or combines narrow vectors to match target limits.
#[derive(Debug, Clone)]
pub struct VectorElementLegalizer {
    /// Maximum vector width in bits.
    pub max_vector_bits: u32,
    /// Minimum vector width in bits.
    pub min_vector_bits: u32,
}

impl VectorElementLegalizer {
    /// Create a new vector element legalizer.
    pub fn new(max_bits: u32, min_bits: u32) -> Self {
        Self {
            max_vector_bits: max_bits,
            min_vector_bits: min_bits,
        }
    }

    /// Split a 256-bit vector into 2×128-bit pieces.
    pub fn split_256_to_128(
        &self,
        dst_lo: VReg,
        dst_hi: VReg,
        src: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        vec![
            (
                GOpcode::G_TRUNC,
                vec![
                    MOperand::vreg(dst_lo),
                    MOperand::vreg(src),
                    MOperand::imm(0),
                ],
            ),
            (
                GOpcode::G_TRUNC,
                vec![
                    MOperand::vreg(dst_hi),
                    MOperand::vreg(src),
                    MOperand::imm(128),
                ],
            ),
        ]
    }

    /// Split a 512-bit vector into 4×128-bit pieces.
    pub fn split_512_to_128(&self, dsts: &[VReg], src: VReg) -> Vec<(GOpcode, Vec<MOperand>)> {
        dsts.iter()
            .enumerate()
            .map(|(i, &dst)| {
                (
                    GOpcode::G_TRUNC,
                    vec![
                        MOperand::vreg(dst),
                        MOperand::vreg(src),
                        MOperand::imm((i * 128) as i64),
                    ],
                )
            })
            .collect()
    }

    /// Combine 2×64-bit vectors into a 128-bit vector.
    pub fn combine_2x64_to_128(
        &self,
        dst: VReg,
        lo: VReg,
        hi: VReg,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        vec![
            (
                GOpcode::G_ANYEXT,
                vec![MOperand::vreg(dst), MOperand::vreg(lo)],
            ),
            (
                GOpcode::G_ANYEXT,
                vec![MOperand::vreg(dst), MOperand::vreg(hi)],
            ),
        ]
    }

    /// FewerElementsVector: split a wide vector into fewer-element
    /// sub-vectors.
    pub fn fewer_elements(
        &self,
        src: VReg,
        src_bits: u32,
        num_parts: u32,
    ) -> Vec<(GOpcode, Vec<MOperand>)> {
        let part_bits = src_bits / num_parts;
        let mut seq = Vec::new();

        for i in 0..num_parts {
            let dst = src.wrapping_add(100 + i);
            seq.push((
                GOpcode::G_TRUNC,
                vec![
                    MOperand::vreg(dst),
                    MOperand::vreg(src),
                    MOperand::imm((i * part_bits) as i64),
                ],
            ));
        }

        seq
    }

    /// MoreElementsVector: combine narrow vectors into wider ones.
    pub fn more_elements(&self, dst: VReg, sources: &[VReg]) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();
        let mut current = dst;

        for &src in sources {
            let temp = dst.wrapping_add(200 + src);
            seq.push((
                GOpcode::G_ANYEXT,
                vec![MOperand::vreg(temp), MOperand::vreg(src)],
            ));
            seq.push((
                GOpcode::G_OR,
                vec![
                    MOperand::vreg(current),
                    MOperand::vreg(current),
                    MOperand::vreg(temp),
                ],
            ));
        }

        seq
    }
}

impl Default for VectorElementLegalizer {
    fn default() -> Self {
        Self::new(256, 64)
    }
}

// ============================================================================
// Varargs Legalization (G_VASTART, G_VAARG, G_VAEND, G_VACOPY)
// ============================================================================

/// VarargsLegalizer handles legalization of variable argument intrinsics.
/// On most targets, va_list is a pointer to a struct, and the intrinsics
/// are lowered to loads and stores of the va_list fields.
#[derive(Debug, Clone)]
pub struct VarargsLegalizer {
    /// Size of va_list in bytes.
    pub va_list_size: u32,
    /// Whether arguments are passed in registers for varargs.
    pub reg_save_area: bool,
    /// Pointer size in bits.
    pub pointer_size: u32,
}

impl VarargsLegalizer {
    /// Create a new varargs legalizer.
    pub fn new(va_list_size: u32, pointer_size: u32) -> Self {
        Self {
            va_list_size,
            reg_save_area: true,
            pointer_size,
        }
    }

    /// Lower G_VASTART to initialization of the va_list.
    pub fn lower_vastart(&self, va_list_ptr: VReg) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Store initial values to the va_list struct
        // Field 0: gp_offset (0 = use reg_save_area)
        let offset0 = va_list_ptr.wrapping_add(100);
        seq.push((
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(offset0), MOperand::imm(0)],
        ));
        seq.push((
            GOpcode::G_STORE,
            vec![MOperand::vreg(offset0), MOperand::vreg(va_list_ptr)],
        ));

        seq
    }

    /// Lower G_VAARG to load the next argument.
    pub fn lower_vaarg(&self, dst: VReg, va_list_ptr: VReg) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Load the gp_offset field
        let offset_val = dst.wrapping_add(100);
        seq.push((
            GOpcode::G_LOAD,
            vec![MOperand::vreg(offset_val), MOperand::vreg(va_list_ptr)],
        ));

        // Check if arg is in register save area or overflow area
        // Simplified: always load from overflow area
        let overflow_ptr = dst.wrapping_add(101);
        seq.push((
            GOpcode::G_PTR_ADD,
            vec![
                MOperand::vreg(overflow_ptr),
                MOperand::vreg(va_list_ptr),
                MOperand::imm(0),
            ],
        ));

        // Load the actual argument
        seq.push((
            GOpcode::G_LOAD,
            vec![MOperand::vreg(dst), MOperand::vreg(overflow_ptr)],
        ));

        // Increment the offset in va_list
        seq.push((
            GOpcode::G_ADD,
            vec![
                MOperand::vreg(offset_val),
                MOperand::vreg(offset_val),
                MOperand::imm(8),
            ],
        ));
        seq.push((
            GOpcode::G_STORE,
            vec![MOperand::vreg(offset_val), MOperand::vreg(va_list_ptr)],
        ));

        seq
    }

    /// Lower G_VAEND (typically a no-op).
    pub fn lower_vaend(&self) -> Vec<(GOpcode, Vec<MOperand>)> {
        // No-op on most targets
        Vec::new()
    }

    /// Lower G_VACOPY: copy va_list from src to dst.
    pub fn lower_vacopy(&self, dst_ptr: VReg, src_ptr: VReg) -> Vec<(GOpcode, Vec<MOperand>)> {
        let mut seq = Vec::new();

        // Copy the entire va_list struct byte by byte
        // Simplified: load and store the va_list as a single block
        let temp = dst_ptr.wrapping_add(100);
        seq.push((
            GOpcode::G_LOAD,
            vec![MOperand::vreg(temp), MOperand::vreg(src_ptr)],
        ));
        seq.push((
            GOpcode::G_STORE,
            vec![MOperand::vreg(temp), MOperand::vreg(dst_ptr)],
        ));

        seq
    }
}

impl Default for VarargsLegalizer {
    fn default() -> Self {
        Self::new(24, 64)
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    fn make_test_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        // Add a G_ADD instruction
        let inst = GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(2)],
        );
        mf.blocks[entry].push_instruction(inst);
        // Add a G_SDIV instruction (may need lowering)
        let inst2 = GInstruction::with_operands(
            GOpcode::G_SDIV,
            vec![MOperand::vreg(3), MOperand::vreg(4), MOperand::vreg(5)],
        );
        mf.blocks[entry].push_instruction(inst2);
        mf
    }

    // ---- Type tests ----

    #[test]
    fn test_type_bit_width() {
        assert_eq!(Type::S1.bit_width(), 1);
        assert_eq!(Type::S8.bit_width(), 8);
        assert_eq!(Type::S32.bit_width(), 32);
        assert_eq!(Type::S64.bit_width(), 64);
        assert_eq!(Type::F32.bit_width(), 32);
        assert_eq!(Type::F64.bit_width(), 64);
    }

    #[test]
    fn test_type_is_floating_point() {
        assert!(Type::F32.is_floating_point());
        assert!(!Type::S32.is_floating_point());
    }

    // ---- LegalizeCondition tests ----

    #[test]
    fn test_condition_always() {
        assert!(LegalizeCondition::Always.evaluate(None));
        assert!(LegalizeCondition::Always.evaluate(Some(Type::S32)));
    }

    #[test]
    fn test_condition_narrow_scalar() {
        let cond = LegalizeCondition::NarrowScalar(32);
        assert!(cond.evaluate(Some(Type::S8)));
        assert!(cond.evaluate(Some(Type::S16)));
        assert!(!cond.evaluate(Some(Type::S32)));
        assert!(!cond.evaluate(Some(Type::S64)));
    }

    #[test]
    fn test_condition_wide_scalar() {
        let cond = LegalizeCondition::WideScalar(32);
        assert!(cond.evaluate(Some(Type::S64)));
        assert!(!cond.evaluate(Some(Type::S32)));
        assert!(!cond.evaluate(Some(Type::S8)));
    }

    #[test]
    fn test_condition_type_is() {
        let cond = LegalizeCondition::TypeIs(Type::S32);
        assert!(cond.evaluate(Some(Type::S32)));
        assert!(!cond.evaluate(Some(Type::S64)));
        assert!(!cond.evaluate(None));
    }

    // ---- LegalizerInfo tests ----

    #[test]
    fn test_legalizer_info_new() {
        let info = LegalizerInfo::new();
        assert_eq!(info.rule_count(), 0);
    }

    #[test]
    fn test_legalizer_info_add_rule() {
        let mut info = LegalizerInfo::new();
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        assert_eq!(info.rule_count(), 1);
    }

    #[test]
    fn test_legalizer_info_get_action() {
        let mut info = LegalizerInfo::new();
        info.add_rule(LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        ));
        let action = info.get_action(GOpcode::G_ADD, None);
        assert!(matches!(action, Some(LegalizeAction::Legal)));
    }

    #[test]
    fn test_legalizer_info_get_action_no_match() {
        let info = LegalizerInfo::new();
        assert!(info.get_action(GOpcode::G_ADD, None).is_none());
    }

    #[test]
    fn test_default_aarch64() {
        let info = LegalizerInfo::default_aarch64();
        assert!(info.rule_count() > 0);
        // G_ADD should be legal.
        let action = info.get_action(GOpcode::G_ADD, Some(Type::S32));
        assert!(matches!(action, Some(LegalizeAction::Legal)));
    }

    #[test]
    fn test_default_arm32() {
        let info = LegalizerInfo::default_arm32();
        assert!(info.rule_count() > 0);
    }

    #[test]
    fn test_default_info() {
        let info = LegalizerInfo::default();
        assert_eq!(info.rule_count(), 0);
    }

    // ---- GISelLegalizer tests ----

    #[test]
    fn test_legalizer_new() {
        let legalizer = GISelLegalizer::new();
        assert_eq!(legalizer.legalized, 0);
        assert_eq!(legalizer.already_legal_count(), 0);
        assert_eq!(legalizer.lowered_count(), 0);
        assert_eq!(legalizer.libcalls_count(), 0);
    }

    #[test]
    fn test_legalizer_default() {
        let legalizer = GISelLegalizer::default();
        assert_eq!(legalizer.legalized, 0);
    }

    #[test]
    fn test_legalize_empty_function() {
        let mut legalizer = GISelLegalizer::new();
        let mut mf = GMachineFunction::new("empty".to_string());
        mf.push_block("entry".to_string());
        let info = LegalizerInfo::default_aarch64();
        legalizer.legalize(&mut mf, &info);
        // No instructions to legalize.
        assert_eq!(legalizer.legalized, 0);
    }

    #[test]
    fn test_legalize_basic() {
        let mut legalizer = GISelLegalizer::new();
        let mut mf = make_test_mf();
        let info = LegalizerInfo::default_aarch64();
        legalizer.legalize(&mut mf, &info);
        // G_ADD should count as legalized.
        assert!(legalizer.legalized >= 1);
    }

    #[test]
    fn test_reset_counters() {
        let mut legalizer = GISelLegalizer::new();
        let mut mf = make_test_mf();
        let info = LegalizerInfo::default_aarch64();
        legalizer.legalize(&mut mf, &info);
        assert!(legalizer.legalized > 0);
        legalizer.reset();
        assert_eq!(legalizer.legalized, 0);
    }

    #[test]
    fn test_max_iterations() {
        let mut legalizer = GISelLegalizer::new();
        assert_eq!(legalizer.max_iterations(), 32);
        legalizer.set_max_iterations(10);
        assert_eq!(legalizer.max_iterations(), 10);
        legalizer.set_max_iterations(0); // clamped
        assert_eq!(legalizer.max_iterations(), 1);
    }

    #[test]
    fn test_legalize_rule_new() {
        let rule = LegalizeRule::new(
            GOpcode::G_ADD,
            LegalizeCondition::Always,
            LegalizeAction::Legal,
        );
        assert_eq!(rule.opcode, GOpcode::G_ADD);
        assert!(matches!(rule.action, LegalizeAction::Legal));
    }

    // --- NarrowScalarLegalizer Tests ---

    #[test]
    fn test_narrow_scalar_new() {
        let nl = NarrowScalarLegalizer::new(64);
        assert_eq!(nl.max_width, 64);
    }

    #[test]
    fn test_narrow_scalar_needs_narrowing() {
        let nl = NarrowScalarLegalizer::new(64);
        assert!(!nl.needs_narrowing(32));
        assert!(nl.needs_narrowing(128));
    }

    #[test]
    fn test_narrow_scalar_add() {
        let nl = NarrowScalarLegalizer::new(64);
        let seq = nl.narrow_add(10, 11, 20, 21);
        assert!(!seq.is_empty());
        // Should produce multiple instructions for add-with-carry
        assert!(seq.len() >= 2);
    }

    #[test]
    fn test_narrow_scalar_sub() {
        let nl = NarrowScalarLegalizer::new(64);
        let seq = nl.narrow_sub(10, 11, 20, 21);
        assert!(!seq.is_empty());
    }

    // --- WidenScalarLegalizer Tests ---

    #[test]
    fn test_widen_scalar_new() {
        let wl = WidenScalarLegalizer::new(32);
        assert_eq!(wl.min_width, 32);
    }

    #[test]
    fn test_widen_scalar_needs_widening() {
        let wl = WidenScalarLegalizer::new(32);
        assert!(wl.needs_widening(8));
        assert!(!wl.needs_widening(64));
    }

    #[test]
    fn test_widen_scalar_binary_op() {
        let wl = WidenScalarLegalizer::new(32);
        let seq = wl.widen_binary_op(GOpcode::G_ADD, 100, 10, 20, 8);
        assert!(!seq.is_empty());
        // Should have extend, add, truncate
        assert!(seq.len() >= 3);
    }

    // --- BitManipLowerer Tests ---

    #[test]
    fn test_bitmanip_lowerer_new() {
        let bl = BitManipLowerer::new();
        assert!(!bl.has_ctlz);
    }

    #[test]
    fn test_lower_ctlz() {
        let bl = BitManipLowerer::new();
        let seq = bl.lower_ctlz(100, 10, 32);
        // Should produce a sequence of bit manipulation instructions
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_cttz() {
        let bl = BitManipLowerer::new();
        let seq = bl.lower_cttz(100, 10, 32);
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_ctpop() {
        let bl = BitManipLowerer::new();
        let seq = bl.lower_ctpop(100, 10, 32);
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_bswap() {
        let bl = BitManipLowerer::new();
        let seq = bl.lower_bswap(100, 10, 32);
        assert!(!seq.is_empty());
    }

    // --- FunnelShiftLowerer Tests ---

    #[test]
    fn test_funnel_shift_new() {
        let fl = FunnelShiftLowerer::new();
        assert!(!fl.has_funnel_shift);
    }

    #[test]
    fn test_lower_fshl() {
        let fl = FunnelShiftLowerer::new();
        let seq = fl.lower_fshl(100, 10, 20, 30);
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_fshr() {
        let fl = FunnelShiftLowerer::new();
        let seq = fl.lower_fshr(100, 10, 20, 30);
        assert!(!seq.is_empty());
    }

    // --- VectorElementLegalizer Tests ---

    #[test]
    fn test_vector_element_new() {
        let vl = VectorElementLegalizer::new(256, 64);
        assert_eq!(vl.max_vector_bits, 256);
        assert_eq!(vl.min_vector_bits, 64);
    }

    #[test]
    fn test_fewer_elements() {
        let vl = VectorElementLegalizer::new(256, 64);
        let seq = vl.fewer_elements(100, 256, 2);
        assert_eq!(seq.len(), 2);
    }

    #[test]
    fn test_more_elements() {
        let vl = VectorElementLegalizer::new(256, 64);
        let seq = vl.more_elements(100, &[10, 20]);
        assert!(!seq.is_empty());
    }

    // --- VarargsLegalizer Tests ---

    #[test]
    fn test_varargs_legalizer_new() {
        let vl = VarargsLegalizer::new(24, 64);
        assert_eq!(vl.va_list_size, 24);
        assert_eq!(vl.pointer_size, 64);
    }

    #[test]
    fn test_lower_vastart() {
        let vl = VarargsLegalizer::new(24, 64);
        let seq = vl.lower_vastart(100);
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_vaarg() {
        let vl = VarargsLegalizer::new(24, 64);
        let seq = vl.lower_vaarg(100, 200);
        assert!(!seq.is_empty());
    }

    #[test]
    fn test_lower_vaend() {
        let vl = VarargsLegalizer::new(24, 64);
        let seq = vl.lower_vaend();
        assert!(seq.is_empty());
    }

    #[test]
    fn test_lower_vacopy() {
        let vl = VarargsLegalizer::new(24, 64);
        let seq = vl.lower_vacopy(100, 200);
        assert!(!seq.is_empty());
    }
}