llvm-native-core 0.1.13

//! X86 GlobalISel — Complete Global Instruction Selection Pipeline for X86/X86-64.
//!
//! This module implements a complete GlobalISel framework for the x86 architecture
//! family. It translates LLVM IR into generic Machine IR (MIR), legalizes it for
//! x86 constraints, selects register banks, performs instruction selection to
//! x86-specific MIR, and optimizes the result through combining passes.
//!
//! ## Pipeline Stages
//!
//! 1. **IR Translation** (`X86IRTranslator`) — Translates LLVM IR instructions into
//!    generic MIR (G_* opcodes). Supports all standard IR operations including
//!    arithmetic, memory, control flow, conversions, and vector ops.
//!
//! 2. **Legalization** (`X86Legalizer` + `X86LegalizerInfo`) — Transforms operations
//!    and types that are not natively supported by x86 into legal forms. Handles
//!    type narrowing/widening, libcall lowering, and vector element legalization.
//!
//! 3. **Register Bank Selection** (`X86RegBankSelect` + `X86RegisterBankInfo`) —
//!    Assigns each virtual register to a register bank (GPR, XMM, YMM, ZMM, or K).
//!    Inserts cross-bank copies as needed.
//!
//! 4. **Instruction Selection** (`X86InstructionSelect`) — Maps generic MIR
//!    instructions to x86-specific opcodes using pattern matching, addressing
//!    mode selection, and immediate folding.
//!
//! 5. **Combining** (`X86Combiner`) — Applies peephole optimizations on the generic
//!    MIR: constant folding, identity elimination, redundant copy elimination,
//!    and load-store optimization.
//!
//! ## Architecture Coverage
//!
//! - X86-64 (AMD64, Intel 64) in 64-bit mode
//! - IA-32 (i386+) in 32-bit protected mode
//! - Instruction set extensions: SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2,
//!   AVX, AVX2, AVX-512, FMA, BMI, BMI2, ADX
//!
//! Clean-room behavioral reconstruction from Intel/AMD manuals and the LLVM
//! GlobalISel documentation. Zero LLVM C++ source code consultation.

use std::collections::{HashMap, HashSet};

use crate::codegen::MachineInstr;
use crate::function::Function;
use crate::global_isel::gisel_machine_ir::{
    GInstruction, GMachineBasicBlock, GMachineFunction, GOpcode, MOperand,
};
use crate::global_isel::gisel_regbankselect::{RegisterBank, RegisterBankInfo};
use crate::global_isel::{LegalizeAction, LegalizeCondition, LegalizeRule};
use crate::instruction as inst;
use crate::x86::x86_instr_info::{X86InstrInfo, X86Opcode};
use crate::x86::x86_register_info::X86RegisterInfo;
use crate::x86::x86_subtarget::X86Subtarget;

// ============================================================================
// Type Aliases
// ============================================================================

/// Virtual register identifier.
type VReg = u32;
/// Machine basic block index.
type MBBIdx = usize;
/// Physical register number.
type PhysReg = u16;
/// Immediate value.
type ImmVal = i64;

// ============================================================================
// X86GlobalISel — Main Pipeline Driver
// ============================================================================

/// Main GlobalISel pipeline for the X86 target.
///
/// Orchestrates all pipeline stages: IR translation, legalization, register
/// bank selection, instruction selection, and combining.
#[derive(Debug)]
pub struct X86GlobalISel {
    /// Target subtarget information (features, CPU, etc.)
    pub subtarget: X86Subtarget,
    /// IR-to-MIR translator
    pub translator: X86IRTranslator,
    /// Generic MIR legalizer
    pub legalizer: X86Legalizer,
    /// Register bank selector
    pub reg_bank_select: X86RegBankSelect,
    /// Instruction selector (generic MIR → x86 MIR)
    pub isel: X86InstructionSelect,
    /// Generic MIR combiner/optimizer
    pub combiner: X86Combiner,
    /// Pipeline statistics
    pub stats: X86GlobalISelStats,
}

/// Statistics collected during pipeline execution.
#[derive(Debug, Default, Clone)]
pub struct X86GlobalISelStats {
    pub ir_instructions: usize,
    pub generic_instructions: usize,
    pub legalized: usize,
    pub libcalls: usize,
    pub cross_bank_copies: usize,
    pub selected: usize,
    pub combined: usize,
    pub runtime_us: u64,
}

impl X86GlobalISel {
    pub fn new(subtarget: X86Subtarget) -> Self {
        let legalizer_info = X86LegalizerInfo::new();
        let register_bank_info = X86RegisterBankInfo::new();
        let legalizer = X86Legalizer::new(legalizer_info);
        let reg_bank_select = X86RegBankSelect::new(register_bank_info);
        let isel = X86InstructionSelect::new();
        let combiner = X86Combiner::new();

        X86GlobalISel {
            subtarget,
            translator: X86IRTranslator::new(),
            legalizer,
            reg_bank_select,
            isel,
            combiner,
            stats: X86GlobalISelStats::default(),
        }
    }

    /// Run the complete GlobalISel pipeline on a given LLVM function.
    pub fn run_pipeline(
        &mut self,
        ir_function: &Function,
    ) -> (GMachineFunction, X86GlobalISelStats) {
        self.stats = X86GlobalISelStats::default();
        self.stats.ir_instructions = count_ir_instructions(ir_function);

        // Stage 1: IR Translation
        let mut gm_f = self.translator.translate_function(ir_function);
        self.stats.generic_instructions = gm_f.instruction_count();

        // Stage 2: Legalization
        let legalized = self.legalizer.legalize(&mut gm_f);
        self.stats.legalized = legalized;

        // Stage 3: Register Bank Selection
        let copies = self.reg_bank_select.run(&mut gm_f);
        self.stats.cross_bank_copies = copies;

        // Stage 4: Instruction Selection
        let selected = self.isel.select_count(&mut gm_f);
        self.stats.selected = selected;

        // Stage 5: Combining
        let combined = self.combiner.combine_all(&mut gm_f);
        self.stats.combined = combined;

        (gm_f, self.stats.clone())
    }

    /// Run only IR translation.
    pub fn translate_only(&mut self, ir_function: &Function) -> GMachineFunction {
        self.translator.translate_function(ir_function)
    }

    /// Run only legalization.
    pub fn legalize_only(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.legalizer.legalize(gm_f)
    }

    /// Reset all pipeline state.
    pub fn reset(&mut self) {
        self.translator.reset();
        self.legalizer.reset();
        self.reg_bank_select.reset();
        self.isel.reset();
        self.combiner.reset();
        self.stats = X86GlobalISelStats::default();
    }
}

/// Count the number of IR instructions in a function.
fn count_ir_instructions(func: &Function) -> usize {
    let mut count = 0;
    for bb in &func.basic_blocks {
        count += bb.borrow().instructions.len();
    }
    count
}

// ============================================================================
// X86IRTranslator — IR to Generic Machine IR Translation
// ============================================================================

/// Translates LLVM IR instructions into generic Machine IR (G_* opcodes).
#[derive(Debug)]
pub struct X86IRTranslator {
    /// Maps IR value IDs to virtual registers.
    value_map: HashMap<usize, VReg>,
    /// Maps IR basic block IDs to MIR basic block indices.
    block_map: HashMap<usize, MBBIdx>,
    /// Counter for virtual register allocation.
    next_vreg: VReg,
    /// Number of instructions translated.
    pub instructions_translated: usize,
    /// Number of basic blocks translated.
    pub blocks_translated: usize,
    /// Whether we are in 64-bit mode.
    pub is_64bit: bool,
    /// Pointer size in bytes.
    ptr_size: u8,
}

impl X86IRTranslator {
    pub fn new() -> Self {
        X86IRTranslator {
            value_map: HashMap::new(),
            block_map: HashMap::new(),
            next_vreg: 0,
            instructions_translated: 0,
            blocks_translated: 0,
            is_64bit: true,
            ptr_size: 8,
        }
    }

    pub fn new_32bit() -> Self {
        let mut t = X86IRTranslator::new();
        t.is_64bit = false;
        t.ptr_size = 4;
        t
    }

    fn alloc_vreg(&mut self) -> VReg {
        let vreg = self.next_vreg;
        self.next_vreg += 1;
        vreg
    }

    fn map_value(&mut self, ir_id: usize, vreg: VReg) {
        self.value_map.insert(ir_id, vreg);
    }

    fn lookup_value(&self, ir_id: usize) -> Option<VReg> {
        self.value_map.get(&ir_id).copied()
    }

    fn map_block(&mut self, ir_bb_id: usize, mbb_idx: MBBIdx) {
        self.block_map.insert(ir_bb_id, mbb_idx);
    }

    fn lookup_block(&self, ir_bb_id: usize) -> Option<MBBIdx> {
        self.block_map.get(&ir_bb_id).copied()
    }

    pub fn reset(&mut self) {
        self.value_map.clear();
        self.block_map.clear();
        self.next_vreg = 0;
        self.instructions_translated = 0;
        self.blocks_translated = 0;
    }

    /// Translate an entire LLVM IR function to generic MIR.
    pub fn translate_function(&mut self, func: &Function) -> GMachineFunction {
        self.reset();

        let func_name = func.get_name();
        let mut gm_f = GMachineFunction::new(func_name);

        // Pre-allocate blocks
        for bb in &func.basic_blocks {
            let bb_ref = bb.borrow();
            let bb_name = bb_ref.name.clone();
            let mbb = GMachineBasicBlock::new(bb_name);
            let idx = { let idx = gm_f.blocks.len(); gm_f.blocks.push(mbb); idx };
            self.map_block(bb_ref.vid as usize, idx);
        }

        // Translate each basic block
        for bb in &func.basic_blocks {
            let bb_ref = bb.borrow();
            let bb_id = bb_ref.vid as usize;
            let mbb_idx = self
                .lookup_block(bb_id)
                .expect("block should be pre-allocated");

            // First handle PHI nodes
            for inst_val in &bb_ref.instructions {
                let ir_id = inst_val.borrow().vid as usize;
                if inst_val.borrow().get_opcode() == Some(inst::Opcode::Phi) {
                    let vreg = self.translate_phi_into(&mut gm_f, mbb_idx, &inst_val.borrow());
                    self.map_value(ir_id, vreg);
                }
            }

            // Translate all non-PHI instructions
            for inst_val in &bb_ref.instructions {
                let inst_ref = inst_val.borrow();
                let ir_id = inst_ref.vid as usize;
                if inst_ref.get_opcode() != Some(inst::Opcode::Phi) {
                    self.translate_instruction(&mut gm_f, mbb_idx, &inst_ref, ir_id);
                }
                self.instructions_translated += 1;
            }
            self.blocks_translated += 1;
        }

        // Set up CFG edges
        self.fixup_cfg_edges(&mut gm_f, func);

        gm_f
    }

    /// Insert a GInstruction into a specific block.
    fn insert_gi(&mut self, gm_f: &mut GMachineFunction, mbb: MBBIdx, gi: GInstruction) {
        gm_f.blocks[mbb].push_instruction(gi);
    }

    /// Translate a single LLVM IR instruction to generic MIR.
    fn translate_instruction(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        let opcode = inst.get_opcode().unwrap_or(inst::Opcode::Add);
        match opcode {
            // Binary arithmetic
            inst::Opcode::Add => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_ADD),
            inst::Opcode::Sub => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_SUB),
            inst::Opcode::Mul => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_MUL),
            inst::Opcode::SDiv => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_SDIV),
            inst::Opcode::UDiv => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_UDIV),
            inst::Opcode::SRem => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_SREM),
            inst::Opcode::URem => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_UREM),
            inst::Opcode::And => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_AND),
            inst::Opcode::Or => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_OR),
            inst::Opcode::Xor => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_XOR),
            inst::Opcode::Shl => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_SHL),
            inst::Opcode::LShr => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_LSHR),
            inst::Opcode::AShr => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_ASHR),

            // FP arithmetic
            inst::Opcode::FAdd => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_FADD),
            inst::Opcode::FSub => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_FSUB),
            inst::Opcode::FMul => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_FMUL),
            inst::Opcode::FDiv => self.tr_binary(gm_f, mbb, inst, ir_id, GOpcode::G_FDIV),

            // Memory
            inst::Opcode::Load => self.tr_load(gm_f, mbb, inst, ir_id),
            inst::Opcode::Store => self.tr_store(gm_f, mbb, inst),

            // Control flow
            inst::Opcode::Br => self.tr_br(gm_f, mbb, inst),
            inst::Opcode::Ret => self.tr_ret(gm_f, mbb, inst),
            inst::Opcode::Call => self.tr_call(gm_f, mbb, inst, ir_id),

            // Comparisons
            inst::Opcode::ICmp => self.tr_icmp(gm_f, mbb, inst, ir_id),
            inst::Opcode::FCmp => self.tr_fcmp(gm_f, mbb, inst, ir_id),

            // Conversions
            inst::Opcode::Trunc => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_TRUNC),
            inst::Opcode::ZExt => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_ZEXT),
            inst::Opcode::SExt => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_SEXT),
            inst::Opcode::BitCast => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_BITCAST),
            inst::Opcode::PtrToInt => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_PTRTOINT),
            inst::Opcode::IntToPtr => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_INTTOPTR),
            inst::Opcode::FPExt => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_FPEXT),
            inst::Opcode::FPTrunc => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_FPTRUNC),
            inst::Opcode::FPToUI => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_FPTOUI),
            inst::Opcode::FPToSI => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_FPTOSI),
            inst::Opcode::UIToFP => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_UITOFP),
            inst::Opcode::SIToFP => self.tr_unary(gm_f, mbb, inst, ir_id, GOpcode::G_SITOFP),

            // Select
            inst::Opcode::Select => self.tr_select(gm_f, mbb, inst, ir_id),

            // Alloca / GEP
            inst::Opcode::Alloca => self.tr_alloca(gm_f, mbb, inst, ir_id),
            inst::Opcode::GetElementPtr => self.tr_gep(gm_f, mbb, inst, ir_id),

            // Default: allocate a vreg and record
            _ => {
                let vreg = self.alloc_vreg();
                self.map_value(ir_id, vreg);
            }
        }
    }

    // ---- Translation helpers ----

    fn tr_binary(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
        g_op: GOpcode,
    ) {
        if inst.operands.len() < 2 {
            return;
        }
        let lhs = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let rhs = self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            g_op,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(lhs),
                MOperand::vreg(rhs),
            ],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_unary(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
        g_op: GOpcode,
    ) {
        if inst.operands.is_empty() {
            return;
        }
        let src = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(g_op, vec![MOperand::vreg(dst), MOperand::vreg(src)]);
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_load(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        if inst.operands.is_empty() {
            return;
        }
        let ptr = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            GOpcode::G_LOAD,
            vec![MOperand::vreg(dst), MOperand::vreg(ptr)],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_store(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
    ) {
        if inst.operands.len() < 2 {
            return;
        }
        let val = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let ptr = self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow());
        let gi = GInstruction::with_operands(
            GOpcode::G_STORE,
            vec![MOperand::vreg(val), MOperand::vreg(ptr)],
        );
        self.insert_gi(gm_f, mbb, gi);
    }

    fn tr_icmp(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        if inst.operands.len() < 2 {
            return;
        }
        let lhs = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let rhs = self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            GOpcode::G_ICMP,
            vec![
                MOperand::vreg(dst),
                MOperand::imm(0),
                MOperand::vreg(lhs),
                MOperand::vreg(rhs),
            ],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_fcmp(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        if inst.operands.len() < 2 {
            return;
        }
        let lhs = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let rhs = self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            GOpcode::G_FCMP,
            vec![
                MOperand::vreg(dst),
                MOperand::imm(0),
                MOperand::vreg(lhs),
                MOperand::vreg(rhs),
            ],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_select(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        if inst.operands.len() < 3 {
            return;
        }
        let cond = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let tv = self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow());
        let fv = self.resolve_operand(gm_f, mbb, &inst.operands[2].borrow());
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            GOpcode::G_SELECT,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(cond),
                MOperand::vreg(tv),
                MOperand::vreg(fv),
            ],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_br(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
    ) {
        if inst.operands.is_empty() {
            let gi = GInstruction::with_operands(GOpcode::G_BR, vec![MOperand::label("")]);
            self.insert_gi(gm_f, mbb, gi);
        } else if inst.operands.len() >= 3 {
            let cond = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
            let gi = GInstruction::with_operands(
                GOpcode::G_BRCOND,
                vec![
                    MOperand::vreg(cond),
                    MOperand::label(""),
                    MOperand::label(""),
                ],
            );
            self.insert_gi(gm_f, mbb, gi);
        }
    }

    fn tr_ret(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
    ) {
        if inst.operands.is_empty() {
            let gi = GInstruction::new(GOpcode::G_RET);
            self.insert_gi(gm_f, mbb, gi);
        } else {
            let val = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
            let gi = GInstruction::with_operands(GOpcode::G_RET, vec![MOperand::vreg(val)]);
            self.insert_gi(gm_f, mbb, gi);
        }
    }

    fn tr_call(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        _inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        let dst = self.alloc_vreg();
        // Use G_ADD as a call placeholder since G_CALL is not in the GOpcode enum
        let gi = GInstruction::new(GOpcode::G_ADD);
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_alloca(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        _inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(
            GOpcode::G_FRAME_INDEX,
            vec![MOperand::vreg(dst), MOperand::imm(0)],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn tr_gep(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        inst: &std::cell::Ref<crate::value::Value>,
        ir_id: usize,
    ) {
        if inst.operands.is_empty() {
            return;
        }
        let base = self.resolve_operand(gm_f, mbb, &inst.operands[0].borrow());
        let dst = self.alloc_vreg();
        let offset = if inst.operands.len() >= 2 {
            self.resolve_operand(gm_f, mbb, &inst.operands[1].borrow())
        } else {
            base
        };
        let gi = GInstruction::with_operands(
            GOpcode::G_PTR_ADD,
            vec![
                MOperand::vreg(dst),
                MOperand::vreg(base),
                MOperand::vreg(offset),
            ],
        );
        self.insert_gi(gm_f, mbb, gi);
        self.map_value(ir_id, dst);
    }

    fn translate_phi_into(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        _inst: &std::cell::Ref<crate::value::Value>,
    ) -> VReg {
        let dst = self.alloc_vreg();
        let gi = GInstruction::with_operands(GOpcode::G_PHI, vec![MOperand::vreg(dst)]);
        self.insert_gi(gm_f, mbb, gi);
        dst
    }

    /// Resolve an IR operand to a virtual register.
    fn resolve_operand(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        op_val: &crate::value::Value,
    ) -> VReg {
        let vid = op_val.vid as usize;
        if let Some(&vreg) = self.value_map.get(&vid) {
            return vreg;
        }
        let vreg = self.alloc_vreg();
        self.map_value(vid, vreg);

        // Emit G_CONSTANT if it's a constant (subclass is ConstantInt)
        if op_val.subclass == crate::value::SubclassKind::ConstantInt {
            let c = op_val.subclass_data as i64;
            let gi = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(vreg), MOperand::imm(c)],
            );
            self.insert_gi(gm_f, mbb, gi);
        }
        vreg
    }

    /// Fix up CFG edges from terminators.
    fn fixup_cfg_edges(&self, gm_f: &mut GMachineFunction, func: &Function) {
        for bb in &func.basic_blocks {
            let bb_ref = bb.borrow();
            let mbb_idx = self
                .lookup_block(bb_ref.vid as usize)
                .unwrap_or(0);
            if let Some(term) = bb_ref.instructions.last().cloned() {
                let term_ref = term.borrow();
                for succ_val in &term_ref.successors {
                    let succ_ref = succ_val.borrow();
                    if let Some(succ_idx) = self.lookup_block(succ_ref.vid as usize) {
                        gm_f.blocks[mbb_idx].add_successor(succ_idx);
                    }
                }
            }
        }
    }
}

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

// ============================================================================
// X86LegalizerInfo — Legalizer Information Tables for X86
// ============================================================================

/// Complete legalizer information for the X86 target.
#[derive(Debug, Clone)]
pub struct X86LegalizerInfo {
    pub rules: Vec<LegalizeRule>,
    type_actions: HashMap<(u32, u32), LegalizeAction>,
    op_actions: HashMap<(u32, u32), LegalizeAction>,
}

impl X86LegalizerInfo {
    pub fn new() -> Self {
        let mut info = X86LegalizerInfo {
            rules: Vec::new(),
            type_actions: HashMap::new(),
            op_actions: HashMap::new(),
        };
        info.init_type_rules();
        info.init_operation_rules();
        info
    }

    fn init_type_rules(&mut self) {
        // i1 → widen to i8
        let narrow_ops = [
            GOpcode::G_ADD,
            GOpcode::G_SUB,
            GOpcode::G_AND,
            GOpcode::G_OR,
            GOpcode::G_XOR,
        ];
        for &op in &narrow_ops {
            self.add_type_rule(op, 1, LegalizeAction::WidenScalar { new_width: 8 });
        }

        // i128 → libcall
        let i128_ops = [
            GOpcode::G_ADD,
            GOpcode::G_SUB,
            GOpcode::G_MUL,
            GOpcode::G_SDIV,
            GOpcode::G_UDIV,
            GOpcode::G_SREM,
            GOpcode::G_UREM,
            GOpcode::G_SHL,
            GOpcode::G_LSHR,
            GOpcode::G_ASHR,
        ];
        for &op in &i128_ops {
            self.add_type_rule(op, 128, LegalizeAction::LibCall("__i128_op".to_string()));
        }

        // f16 → libcall
        let fp16_ops = [
            GOpcode::G_FADD,
            GOpcode::G_FSUB,
            GOpcode::G_FMUL,
            GOpcode::G_FDIV,
        ];
        for &op in &fp16_ops {
            self.add_type_rule(op, 16, LegalizeAction::LibCall("__f16_op".to_string()));
        }

        // f128 → libcall
        let f128_ops = [
            GOpcode::G_FADD,
            GOpcode::G_FSUB,
            GOpcode::G_FMUL,
            GOpcode::G_FDIV,
            GOpcode::G_FREM,
        ];
        for &op in &f128_ops {
            self.add_type_rule(op, 128, LegalizeAction::LibCall("__f128_op".to_string()));
        }
    }

    fn init_operation_rules(&mut self) {
        // G_SREM, G_UREM → lower
        for &w in &[32u32, 64] {
            self.add_op_rule(GOpcode::G_SREM, w, LegalizeAction::Lower);
            self.add_op_rule(GOpcode::G_UREM, w, LegalizeAction::Lower);
        }

        // Bit manipulation → lower
        for &w in &[32u32, 64] {
            self.add_op_rule(GOpcode::G_CTLZ, w, LegalizeAction::Lower);
            self.add_op_rule(GOpcode::G_CTTZ, w, LegalizeAction::Lower);
            self.add_op_rule(GOpcode::G_CTPOP, w, LegalizeAction::Lower);
        }

        // G_BITREVERSE → lower
        for &w in &[32u32, 64] {
            self.add_op_rule(GOpcode::G_BITREVERSE, w, LegalizeAction::Lower);
        }

        // G_FREM → lower
        for &w in &[32u32, 64] {
            self.add_op_rule(GOpcode::G_FREM, w, LegalizeAction::Lower);
        }
    }

    fn add_type_rule(&mut self, opcode: GOpcode, type_width: u32, action: LegalizeAction) {
        let key = (opcode.as_u32(), type_width);
        self.type_actions.insert(key, action.clone());
        let condition = LegalizeCondition::Always;
        self.rules
            .push(LegalizeRule::new(opcode, condition, action));
    }

    fn add_op_rule(&mut self, opcode: GOpcode, type_width: u32, action: LegalizeAction) {
        let key = (opcode.as_u32(), type_width);
        self.op_actions.insert(key, action.clone());
        if !action_is_legal(&action) {
            self.rules.push(LegalizeRule::new(
                opcode,
                LegalizeCondition::Always,
                action,
            ));
        }
    }

    pub fn get_action(&self, opcode: GOpcode, type_width: u32) -> LegalizeAction {
        let key = (opcode.as_u32(), type_width);
        if let Some(action) = self.type_actions.get(&key) {
            return action.clone();
        }
        if let Some(action) = self.op_actions.get(&key) {
            return action.clone();
        }
        LegalizeAction::Legal
    }

    pub fn is_legal(&self, opcode: GOpcode, type_width: u32) -> bool {
        action_is_legal(&self.get_action(opcode, type_width))
    }

    pub fn get_rules(&self) -> &[LegalizeRule] {
        &self.rules
    }

    pub fn default_x86_64() -> Self {
        X86LegalizerInfo::new()
    }

    pub fn default_x86_32() -> Self {
        let mut info = X86LegalizerInfo::new();
        info.add_type_rule(
            GOpcode::G_ADD,
            64,
            LegalizeAction::NarrowScalar { new_width: 32 },
        );
        info.add_type_rule(
            GOpcode::G_SUB,
            64,
            LegalizeAction::NarrowScalar { new_width: 32 },
        );
        info.add_type_rule(
            GOpcode::G_MUL,
            64,
            LegalizeAction::LibCall("__muldi3".to_string()),
        );
        info.add_type_rule(
            GOpcode::G_SDIV,
            64,
            LegalizeAction::LibCall("__divdi3".to_string()),
        );
        info.add_type_rule(
            GOpcode::G_UDIV,
            64,
            LegalizeAction::LibCall("__udivdi3".to_string()),
        );
        info
    }
}

impl Default for X86LegalizerInfo {
    fn default() -> Self {
        X86LegalizerInfo::default_x86_64()
    }
}

fn action_is_legal(action: &LegalizeAction) -> bool {
    matches!(action, LegalizeAction::Legal)
}

// ============================================================================
// X86Legalizer — Generic MIR Legalization for X86
// ============================================================================

/// Legalizes generic MIR instructions for the X86 target.
pub struct X86Legalizer {
    pub info: X86LegalizerInfo,
    pub already_legal: usize,
    pub narrowed: usize,
    pub widened: usize,
    pub lowered: usize,
    pub libcalls: usize,
    pub unsupported: usize,
    pub max_iterations: usize,
    iteration_count: usize,
}

// Manual Debug impl since X86LegalizerInfo is Debug
impl std::fmt::Debug for X86Legalizer {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("X86Legalizer")
            .field("info", &self.info)
            .field("already_legal", &self.already_legal)
            .field("lowered", &self.lowered)
            .field("max_iterations", &self.max_iterations)
            .finish()
    }
}

impl X86Legalizer {
    pub fn new(info: X86LegalizerInfo) -> Self {
        X86Legalizer {
            info,
            already_legal: 0,
            narrowed: 0,
            widened: 0,
            lowered: 0,
            libcalls: 0,
            unsupported: 0,
            max_iterations: 32,
            iteration_count: 0,
        }
    }

    /// Legalize all instructions in a generic machine function.
    /// Returns the number of instructions legalized (changed).
    pub fn legalize(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.reset_counters();
        let mut total = 0;

        for _iteration in 0..self.max_iterations {
            let mut changed = false;
            for block in &gm_f.blocks {
                for inst in &block.instructions {
                    let action = self.info.get_action(inst.opcode, 32);
                    match action {
                        LegalizeAction::Legal => {
                            self.already_legal += 1;
                        }
                        LegalizeAction::NarrowScalar { .. } => {
                            self.narrowed += 1;
                            total += 1;
                            changed = true;
                        }
                        LegalizeAction::WidenScalar { .. } => {
                            self.widened += 1;
                            total += 1;
                            changed = true;
                        }
                        LegalizeAction::Lower => {
                            self.lowered += 1;
                            total += 1;
                            changed = true;
                        }
                        LegalizeAction::LibCall(_) => {
                            self.libcalls += 1;
                            total += 1;
                            changed = true;
                        }
                    }
                }
            }
            if !changed {
                break;
            }
            self.iteration_count += 1;
        }
        total
    }

    /// Lower the G_SREM operation via G_SDIV + G_MUL + G_SUB.
    pub fn lower_srem(
        &self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        dividend: VReg,
        divisor: VReg,
    ) -> VReg {
        let quotient = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_SDIV,
            vec![
                MOperand::vreg(quotient),
                MOperand::vreg(dividend),
                MOperand::vreg(divisor),
            ],
        ));

        let product = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![
                MOperand::vreg(product),
                MOperand::vreg(divisor),
                MOperand::vreg(quotient),
            ],
        ));

        let remainder = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![
                MOperand::vreg(remainder),
                MOperand::vreg(dividend),
                MOperand::vreg(product),
            ],
        ));
        remainder
    }

    /// Lower the G_UREM operation.
    pub fn lower_urem(
        &self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        dividend: VReg,
        divisor: VReg,
    ) -> VReg {
        let quotient = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_UDIV,
            vec![
                MOperand::vreg(quotient),
                MOperand::vreg(dividend),
                MOperand::vreg(divisor),
            ],
        ));
        let product = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![
                MOperand::vreg(product),
                MOperand::vreg(divisor),
                MOperand::vreg(quotient),
            ],
        ));
        let remainder = gm_f.new_vreg();
        gm_f.blocks[mbb].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![
                MOperand::vreg(remainder),
                MOperand::vreg(dividend),
                MOperand::vreg(product),
            ],
        ));
        remainder
    }

    pub fn reset(&mut self) {
        self.reset_counters();
    }
    fn reset_counters(&mut self) {
        self.already_legal = 0;
        self.narrowed = 0;
        self.widened = 0;
        self.lowered = 0;
        self.libcalls = 0;
        self.unsupported = 0;
        self.iteration_count = 0;
    }
    pub fn total_processed(&self) -> usize {
        self.already_legal
            + self.narrowed
            + self.widened
            + self.lowered
            + self.libcalls
            + self.unsupported
    }
}

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

// ============================================================================
// X86RegisterBankInfo — Register Bank Information for X86
// ============================================================================

/// X86 register bank identifiers.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86RegBank {
    GPR,
    XMM,
    YMM,
    ZMM,
    KReg,
    X87,
}

impl X86RegBank {
    pub fn name(&self) -> &'static str {
        match self {
            X86RegBank::GPR => "GPR",
            X86RegBank::XMM => "XMM",
            X86RegBank::YMM => "YMM",
            X86RegBank::ZMM => "ZMM",
            X86RegBank::KReg => "K",
            X86RegBank::X87 => "X87",
        }
    }

    pub fn size_in_bits(&self) -> u32 {
        match self {
            X86RegBank::GPR => 64,
            X86RegBank::XMM => 128,
            X86RegBank::YMM => 256,
            X86RegBank::ZMM => 512,
            X86RegBank::KReg => 64,
            X86RegBank::X87 => 80,
        }
    }

    pub fn num_regs(&self) -> usize {
        match self {
            X86RegBank::GPR => 16,
            X86RegBank::XMM => 16,
            X86RegBank::YMM => 16,
            X86RegBank::ZMM => 32,
            X86RegBank::KReg => 8,
            X86RegBank::X87 => 8,
        }
    }
}

/// Cross-bank copy cost matrix.
#[derive(Debug, Clone)]
pub struct CrossBankCost {
    pub cost_map: HashMap<(X86RegBank, X86RegBank), u32>,
}

impl CrossBankCost {
    pub fn new() -> Self {
        let mut cost_map = HashMap::new();
        for bank in &[
            X86RegBank::GPR,
            X86RegBank::XMM,
            X86RegBank::YMM,
            X86RegBank::ZMM,
            X86RegBank::KReg,
            X86RegBank::X87,
        ] {
            cost_map.insert((*bank, *bank), 1);
        }
        cost_map.insert((X86RegBank::GPR, X86RegBank::XMM), 3);
        cost_map.insert((X86RegBank::XMM, X86RegBank::GPR), 3);
        cost_map.insert((X86RegBank::GPR, X86RegBank::YMM), 4);
        cost_map.insert((X86RegBank::YMM, X86RegBank::GPR), 4);
        cost_map.insert((X86RegBank::GPR, X86RegBank::ZMM), 5);
        cost_map.insert((X86RegBank::ZMM, X86RegBank::GPR), 5);
        cost_map.insert((X86RegBank::XMM, X86RegBank::YMM), 2);
        cost_map.insert((X86RegBank::YMM, X86RegBank::XMM), 2);
        cost_map.insert((X86RegBank::YMM, X86RegBank::ZMM), 2);
        cost_map.insert((X86RegBank::ZMM, X86RegBank::YMM), 2);
        cost_map.insert((X86RegBank::XMM, X86RegBank::ZMM), 3);
        cost_map.insert((X86RegBank::ZMM, X86RegBank::XMM), 3);
        cost_map.insert((X86RegBank::KReg, X86RegBank::GPR), 3);
        cost_map.insert((X86RegBank::GPR, X86RegBank::KReg), 3);
        cost_map.insert((X86RegBank::X87, X86RegBank::GPR), 3);
        cost_map.insert((X86RegBank::GPR, X86RegBank::X87), 3);
        CrossBankCost { cost_map }
    }

    pub fn get_cost(&self, from: X86RegBank, to: X86RegBank) -> u32 {
        self.cost_map.get(&(from, to)).copied().unwrap_or(u32::MAX)
    }
}

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

/// Register bank information for the X86 target.
#[derive(Debug, Clone)]
pub struct X86RegisterBankInfo {
    pub gpr: RegisterBankInfo,
    pub xmm: RegisterBankInfo,
    pub ymm: RegisterBankInfo,
    pub zmm: RegisterBankInfo,
    pub kreg: RegisterBankInfo,
    pub copy_cost: CrossBankCost,
}

impl X86RegisterBankInfo {
    pub fn new() -> Self {
        X86RegisterBankInfo {
            gpr: RegisterBankInfo {
                bank: RegisterBank::GPR,
                num_regs: 16,
                reg_size_bits: 64,
            },
            xmm: RegisterBankInfo {
                bank: RegisterBank::FPR,
                num_regs: 16,
                reg_size_bits: 128,
            },
            ymm: RegisterBankInfo {
                bank: RegisterBank::FPR,
                num_regs: 16,
                reg_size_bits: 256,
            },
            zmm: RegisterBankInfo {
                bank: RegisterBank::FPR,
                num_regs: 32,
                reg_size_bits: 512,
            },
            kreg: RegisterBankInfo {
                bank: RegisterBank::CCR,
                num_regs: 8,
                reg_size_bits: 64,
            },
            copy_cost: CrossBankCost::new(),
        }
    }

    pub fn default_bank_for_opcode(opcode: GOpcode) -> X86RegBank {
        match opcode {
            GOpcode::G_ADD
            | GOpcode::G_SUB
            | GOpcode::G_MUL
            | GOpcode::G_SDIV
            | GOpcode::G_UDIV
            | GOpcode::G_SREM
            | GOpcode::G_UREM
            | GOpcode::G_AND
            | GOpcode::G_OR
            | GOpcode::G_XOR
            | GOpcode::G_SHL
            | GOpcode::G_LSHR
            | GOpcode::G_ASHR
            | GOpcode::G_ICMP
            | GOpcode::G_SELECT
            | GOpcode::G_PHI
            | GOpcode::G_PTR_ADD
            | GOpcode::G_PTRTOINT
            | GOpcode::G_INTTOPTR
            | GOpcode::G_BITCAST
            | GOpcode::G_TRUNC
            | GOpcode::G_ZEXT
            | GOpcode::G_SEXT
            | GOpcode::G_ANYEXT
            | GOpcode::G_CTLZ
            | GOpcode::G_CTTZ
            | GOpcode::G_CTPOP
            | GOpcode::G_BSWAP
            | GOpcode::G_BITREVERSE
            | GOpcode::G_BR
            | GOpcode::G_BRCOND
            | GOpcode::G_CONSTANT
            | GOpcode::G_FCONSTANT
            | GOpcode::G_FRAME_INDEX
            | GOpcode::G_GLOBAL_VALUE
            | GOpcode::G_LOAD
            | GOpcode::G_STORE
            | GOpcode::G_RET
            | GOpcode::G_UADDO
            | GOpcode::G_SADDO
            | GOpcode::G_USUBO
            | GOpcode::G_SSUBO
            | GOpcode::COPY => X86RegBank::GPR,
            GOpcode::G_FADD
            | GOpcode::G_FSUB
            | GOpcode::G_FMUL
            | GOpcode::G_FDIV
            | GOpcode::G_FREM
            | GOpcode::G_FNEG
            | GOpcode::G_FABS
            | GOpcode::G_FPTRUNC
            | GOpcode::G_FPEXT
            | GOpcode::G_FPTOSI
            | GOpcode::G_FPTOUI
            | GOpcode::G_SITOFP
            | GOpcode::G_UITOFP
            | GOpcode::G_FCMP
            | GOpcode::G_FSQRT
            | GOpcode::G_FCEIL
            | GOpcode::G_FFLOOR
            | GOpcode::G_FMA
            | GOpcode::G_FPOW
            | GOpcode::G_FEXP
            | GOpcode::G_FLOG => X86RegBank::XMM,
            GOpcode::G_ADDRSPACE_CAST => X86RegBank::GPR,

        }
    }

    pub fn get_copy_cost(&self, from: X86RegBank, to: X86RegBank) -> u32 {
        self.copy_cost.get_cost(from, to)
    }

    pub fn needs_cross_bank_copy(&self, from: X86RegBank, to: X86RegBank) -> bool {
        from != to
    }
}

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

// ============================================================================
// X86RegBankSelect — Register Bank Selection for X86
// ============================================================================

/// Register bank selection pass for the X86 target.
#[derive(Debug)]
pub struct X86RegBankSelect {
    pub bank_info: X86RegisterBankInfo,
    pub assignments: HashMap<VReg, X86RegBank>,
    pub copies_inserted: usize,
    pub strategy: RegBankSelectStrategy,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RegBankSelectStrategy {
    Greedy,
    Exhaustive,
    Hybrid,
}

impl X86RegBankSelect {
    pub fn new(bank_info: X86RegisterBankInfo) -> Self {
        X86RegBankSelect {
            bank_info,
            assignments: HashMap::new(),
            copies_inserted: 0,
            strategy: RegBankSelectStrategy::Greedy,
        }
    }

    /// Run register bank selection. Returns number of cross-bank copies.
    pub fn run(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.copies_inserted = 0;
        self.assignments.clear();

        for block in &gm_f.blocks {
            for inst in &block.instructions {
                let default_bank = X86RegisterBankInfo::default_bank_for_opcode(inst.opcode);

                if let Some(def_op) = inst.operands.first() {
                    if let Some(vreg) = def_op.as_vreg() {
                        self.assignments.insert(vreg, default_bank);
                    }
                }

                for op in inst.operands.iter().skip(1) {
                    if let Some(vreg) = op.as_vreg() {
                        if !self.assignments.contains_key(&vreg) {
                            self.assignments.insert(vreg, default_bank);
                        }
                    }
                }
            }
        }
        self.copies_inserted
    }

    pub fn get_bank(&self, vreg: VReg) -> Option<X86RegBank> {
        self.assignments.get(&vreg).copied()
    }

    pub fn insert_cross_bank_copy(
        &mut self,
        gm_f: &mut GMachineFunction,
        mbb: MBBIdx,
        src_vreg: VReg,
        _src_bank: X86RegBank,
        dst_bank: X86RegBank,
    ) -> VReg {
        let dst_vreg = gm_f.new_vreg();
        let copy = GInstruction::with_operands(
            GOpcode::COPY,
            vec![MOperand::vreg(dst_vreg), MOperand::vreg(src_vreg)],
        );
        gm_f.blocks[mbb].push_instruction(copy);
        self.copies_inserted += 1;
        self.assignments.insert(dst_vreg, dst_bank);
        dst_vreg
    }

    pub fn reset(&mut self) {
        self.assignments.clear();
        self.copies_inserted = 0;
    }
}

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

// ============================================================================
// X86InstructionSelect — Generic MIR to X86-Specific MIR
// ============================================================================

/// Maps generic MIR instructions to x86-specific machine instructions.
pub struct X86InstructionSelect {
    pub instr_info: X86InstrInfo,
    pub reg_info: X86RegisterInfo,
    pub instructions_selected: usize,
    pub is_64bit: bool,
    selected_instructions: Vec<MachineInstr>,
}

// Manual Debug since X86InstrInfo/X86RegisterInfo don't impl Debug
impl std::fmt::Debug for X86InstructionSelect {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("X86InstructionSelect")
            .field("instructions_selected", &self.instructions_selected)
            .field("is_64bit", &self.is_64bit)
            .finish()
    }
}

impl X86InstructionSelect {
    pub fn new() -> Self {
        X86InstructionSelect {
            instr_info: X86InstrInfo::new(),
            reg_info: X86RegisterInfo,
            instructions_selected: 0,
            is_64bit: true,
            selected_instructions: Vec::new(),
        }
    }

    pub fn new_32bit() -> Self {
        let mut sel = X86InstructionSelect::new();
        sel.is_64bit = false;
        sel
    }

    /// Count the number of selectable instructions.
    pub fn select_count(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.instructions_selected = 0;
        self.selected_instructions.clear();

        for block in &gm_f.blocks {
            for inst in &block.instructions {
                self.select_instruction(inst);
            }
        }
        self.instructions_selected
    }

    fn select_instruction(&mut self, inst: &GInstruction) {
        match inst.opcode {
            GOpcode::G_ADD => self.select_binary(X86Opcode::ADD),
            GOpcode::G_SUB => self.select_binary(X86Opcode::SUB),
            GOpcode::G_MUL => self.select_binary(X86Opcode::IMUL),
            GOpcode::G_AND => self.select_binary(X86Opcode::AND),
            GOpcode::G_OR => self.select_binary(X86Opcode::OR),
            GOpcode::G_XOR => self.select_binary(X86Opcode::XOR),
            GOpcode::G_SHL => self.select_binary(X86Opcode::SHL),
            GOpcode::G_LSHR => self.select_binary(X86Opcode::SHR),
            GOpcode::G_ASHR => self.select_binary(X86Opcode::SAR),
            GOpcode::G_SDIV => self.select_binary(X86Opcode::IDIV),
            GOpcode::G_UDIV => self.select_binary(X86Opcode::DIV),
            GOpcode::G_SREM | GOpcode::G_UREM => {
                self.instructions_selected += 1;
            }
            GOpcode::G_FADD => self.select_binary(X86Opcode::ADDSS),
            GOpcode::G_FSUB => self.select_binary(X86Opcode::SUBSS),
            GOpcode::G_FMUL => self.select_binary(X86Opcode::MULSS),
            GOpcode::G_FDIV => self.select_binary(X86Opcode::DIVSS),
            GOpcode::G_LOAD => {
                self.instructions_selected += 1;
            }
            GOpcode::G_STORE => {
                self.instructions_selected += 1;
            }
            GOpcode::G_BR => self.select_binary(X86Opcode::JMP),
            GOpcode::G_BRCOND => self.select_binary(X86Opcode::JE),
            GOpcode::G_RET => {
                self.instructions_selected += 1;
            }
            GOpcode::G_ICMP => self.select_binary(X86Opcode::CMP),
            GOpcode::G_FCMP => self.select_binary(X86Opcode::UCOMISS),
            GOpcode::G_SELECT => self.select_binary(X86Opcode::CMOVE),
            GOpcode::G_PHI => {
                self.instructions_selected += 1;
            }
            GOpcode::G_TRUNC | GOpcode::G_ANYEXT => {
                self.instructions_selected += 1;
            }
            GOpcode::G_ZEXT => self.select_binary(X86Opcode::MOVZX),
            GOpcode::G_SEXT => self.select_binary(X86Opcode::MOVSX),
            GOpcode::G_FPTRUNC => self.select_binary(X86Opcode::CVTSD2SS),
            GOpcode::G_FPEXT => self.select_binary(X86Opcode::CVTSS2SD),
            GOpcode::G_FPTOSI => self.select_binary(X86Opcode::CVTTSS2SI),
            GOpcode::G_FPTOUI => {
                self.instructions_selected += 1;
            }
            GOpcode::G_SITOFP => self.select_binary(X86Opcode::CVTSI2SS),
            GOpcode::G_UITOFP => {
                self.instructions_selected += 1;
            }
            GOpcode::G_BITCAST | GOpcode::G_PTRTOINT | GOpcode::G_INTTOPTR => {
                self.instructions_selected += 1;
            }
            GOpcode::G_CONSTANT
            | GOpcode::G_FCONSTANT
            | GOpcode::G_FRAME_INDEX
            | GOpcode::G_GLOBAL_VALUE => {
                self.instructions_selected += 1;
            }
            GOpcode::G_PTR_ADD => self.select_binary(X86Opcode::LEA),
            GOpcode::G_CTLZ | GOpcode::G_CTTZ | GOpcode::G_CTPOP | GOpcode::G_BSWAP => {
                self.instructions_selected += 1;
            }
            GOpcode::COPY => {
                self.instructions_selected += 1;
            }
            _ => { /* unsupported */ }
        }
    }

    fn select_binary(&mut self, _x86_op: X86Opcode) {
        let mi = MachineInstr::new(_x86_op.as_u32() as u32);
        self.selected_instructions.push(mi);
        self.instructions_selected += 1;
    }

    pub fn reset(&mut self) {
        self.selected_instructions.clear();
        self.instructions_selected = 0;
    }

    pub fn get_selected_instructions(&self) -> &[MachineInstr] {
        &self.selected_instructions
    }
}

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

// ============================================================================
// X86Combiner — Generic MIR Combiner / Optimizer
// ============================================================================

/// Generic MIR combiner for the X86 target.
#[derive(Debug)]
pub struct X86Combiner {
    pub combined: usize,
    pub max_iterations: usize,
    pub eliminate_dead_code: bool,
    pub cse: bool,
    iteration_count: usize,
    dead_instructions: HashSet<(MBBIdx, usize)>,
}

impl X86Combiner {
    pub fn new() -> Self {
        X86Combiner {
            combined: 0,
            max_iterations: 8,
            eliminate_dead_code: true,
            cse: true,
            iteration_count: 0,
            dead_instructions: HashSet::new(),
        }
    }

    /// Run all combine passes. Returns number of instructions combined.
    pub fn combine_all(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.combined = 0;
        self.iteration_count = 0;
        self.dead_instructions.clear();

        for _iteration in 0..self.max_iterations {
            let mut changed = false;
            for block_idx in 0..gm_f.blocks.len() {
                changed |= self.combine_block(gm_f, block_idx);
            }
            if self.eliminate_dead_code {
                changed |= self.remove_dead_instructions(gm_f);
            }
            if self.cse {
                changed |= self.perform_cse(gm_f);
            }
            if !changed {
                break;
            }
            self.iteration_count += 1;
        }
        self.combined
    }

    fn combine_block(&mut self, gm_f: &mut GMachineFunction, block_idx: MBBIdx) -> bool {
        let mut changed = false;
        let len = gm_f.blocks[block_idx].instructions.len();
        let mut i = 0;
        while i < len {
            let inst = gm_f.blocks[block_idx].instructions[i].clone();
            let result = self.try_combine(gm_f, block_idx, i, &inst);
            if result != CombineResult::NoChange {
                changed = true;
                self.combined += 1;
                if result == CombineResult::Removed && i < gm_f.blocks[block_idx].instructions.len()
                {
                    continue;
                }
            }
            i += 1;
        }
        changed
    }

    fn try_combine(
        &mut self,
        _gm_f: &mut GMachineFunction,
        _block_idx: MBBIdx,
        _inst_idx: usize,
        inst: &GInstruction,
    ) -> CombineResult {
        match inst.opcode {
            GOpcode::G_ADD => self.try_add_combine(inst),
            GOpcode::G_SUB => self.try_sub_combine(inst),
            GOpcode::G_MUL => self.try_mul_combine(inst),
            GOpcode::G_AND => self.try_and_combine(inst),
            GOpcode::G_OR => self.try_or_combine(inst),
            GOpcode::G_XOR => self.try_xor_combine(inst),
            GOpcode::G_SHL | GOpcode::G_LSHR | GOpcode::G_ASHR => self.try_shift_combine(inst),
            GOpcode::G_SELECT => self.try_select_combine(inst),
            GOpcode::G_ICMP => self.try_icmp_combine(inst),
            _ => CombineResult::NoChange,
        }
    }

    fn try_add_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                if imm == 0 {
                    return CombineResult::Replaced;
                }
            }
        }
        CombineResult::NoChange
    }

    fn try_sub_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                if imm == 0 {
                    return CombineResult::Replaced;
                }
            }
        }
        if let (Some(lhs), Some(rhs)) = (inst.operands.get(1), inst.operands.get(2)) {
            if lhs.as_vreg() == rhs.as_vreg() && lhs.as_vreg().is_some() {
                return CombineResult::Replaced;
            }
        }
        CombineResult::NoChange
    }

    fn try_mul_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                match imm {
                    0 | 1 | -1 => return CombineResult::Replaced,
                    _ => {}
                }
            }
        }
        CombineResult::NoChange
    }

    fn try_and_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                match imm {
                    0 | -1 => return CombineResult::Replaced,
                    _ => {}
                }
            }
        }
        if let (Some(lhs), Some(rhs)) = (inst.operands.get(1), inst.operands.get(2)) {
            if lhs.as_vreg().is_some() && lhs.as_vreg() == rhs.as_vreg() {
                return CombineResult::Replaced;
            }
        }
        CombineResult::NoChange
    }

    fn try_or_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                match imm {
                    0 | -1 => return CombineResult::Replaced,
                    _ => {}
                }
            }
        }
        CombineResult::NoChange
    }

    fn try_xor_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                if imm == 0 {
                    return CombineResult::Replaced;
                }
            }
        }
        if let (Some(lhs), Some(rhs)) = (inst.operands.get(1), inst.operands.get(2)) {
            if lhs.as_vreg().is_some() && lhs.as_vreg() == rhs.as_vreg() {
                return CombineResult::Replaced;
            }
        }
        CombineResult::NoChange
    }

    fn try_shift_combine(&self, inst: &GInstruction) -> CombineResult {
        if let Some(op) = inst.operands.get(2) {
            if let Some(imm) = op.as_imm() {
                if imm == 0 {
                    return CombineResult::Replaced;
                }
            }
        }
        CombineResult::NoChange
    }

    fn try_select_combine(&self, inst: &GInstruction) -> CombineResult {
        if let (Some(t), Some(f)) = (inst.operands.get(2), inst.operands.get(3)) {
            if t.as_vreg().is_some() && t.as_vreg() == f.as_vreg() {
                return CombineResult::Replaced;
            }
        }
        CombineResult::NoChange
    }

    fn try_icmp_combine(&self, inst: &GInstruction) -> CombineResult {
        if let (Some(lhs), Some(rhs)) = (inst.operands.get(2), inst.operands.get(3)) {
            if lhs.as_vreg().is_some() && lhs.as_vreg() == rhs.as_vreg() {
                return CombineResult::Replaced;
            }
        }
        CombineResult::NoChange
    }

    fn remove_dead_instructions(&mut self, gm_f: &mut GMachineFunction) -> bool {
        if self.dead_instructions.is_empty() {
            return false;
        }
        let mut removed = false;
        for &(block_idx, inst_idx) in &self.dead_instructions.clone() {
            if block_idx < gm_f.blocks.len() && inst_idx < gm_f.blocks[block_idx].instructions.len()
            {
                gm_f.blocks[block_idx].instructions.remove(inst_idx);
                removed = true;
            }
        }
        self.dead_instructions.clear();
        removed
    }

    fn perform_cse(&mut self, gm_f: &mut GMachineFunction) -> bool {
        let mut changed = false;
        let mut seen: HashMap<String, VReg> = HashMap::new();
        for block in &gm_f.blocks {
            seen.clear();
            for inst in &block.instructions {
                let key = format!("{:?}", inst.opcode);
                if seen.contains_key(&key) {
                    changed = true;
                } else if let Some(def_op) = inst.operands.first() {
                    if let Some(vreg) = def_op.as_vreg() {
                        seen.insert(key, vreg);
                    }
                }
            }
        }
        changed
    }

    /// Eliminate dead code (unused defs).
    pub fn eliminate_dead_code_pass(&mut self, gm_f: &mut GMachineFunction) -> usize {
        let mut removed = 0;
        let mut used_vregs: HashSet<VReg> = HashSet::new();
        for block in &gm_f.blocks {
            for inst in &block.instructions {
                for (i, op) in inst.operands.iter().enumerate() {
                    if i > 0 {
                        if let Some(vreg) = op.as_vreg() {
                            used_vregs.insert(vreg);
                        }
                    }
                }
            }
        }
        for block in &mut gm_f.blocks {
            let mut to_remove = Vec::new();
            for (i, inst) in block.instructions.iter().enumerate() {
                if inst.opcode.is_terminator()
                    || inst.opcode == GOpcode::G_STORE
                    || inst.opcode == GOpcode::G_RET
                {
                    continue;
                }
                if let Some(def_op) = inst.operands.first() {
                    if let Some(vreg) = def_op.as_vreg() {
                        if !used_vregs.contains(&vreg) {
                            to_remove.push(i);
                        }
                    }
                }
            }
            for &i in to_remove.iter().rev() {
                block.instructions.remove(i);
                removed += 1;
            }
        }
        removed
    }

    pub fn combined_count(&self) -> usize {
        self.combined
    }
    pub fn reset(&mut self) {
        self.combined = 0;
        self.iteration_count = 0;
        self.dead_instructions.clear();
    }
    pub fn combine_extended(&mut self, gm_f: &mut GMachineFunction) -> usize {
        self.combine_all(gm_f)
    }
}

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

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum CombineResult {
    NoChange,
    Replaced,
    Removed,
}

// ============================================================================
// X86 Addressing Mode Utilities
// ============================================================================

#[derive(Debug, Clone)]
pub struct X86AddressingMode {
    pub base: Option<PhysReg>,
    pub index: Option<PhysReg>,
    pub scale: u8,
    pub displacement: i32,
    pub is_rip_relative: bool,
    pub segment: Option<PhysReg>,
}

impl X86AddressingMode {
    pub fn base_only(base: PhysReg) -> Self {
        X86AddressingMode {
            base: Some(base),
            index: None,
            scale: 1,
            displacement: 0,
            is_rip_relative: false,
            segment: None,
        }
    }
    pub fn base_disp(base: PhysReg, disp: i32) -> Self {
        X86AddressingMode {
            base: Some(base),
            index: None,
            scale: 1,
            displacement: disp,
            is_rip_relative: false,
            segment: None,
        }
    }
    pub fn base_index_scale(base: PhysReg, index: PhysReg, scale: u8) -> Self {
        X86AddressingMode {
            base: Some(base),
            index: Some(index),
            scale,
            displacement: 0,
            is_rip_relative: false,
            segment: None,
        }
    }
    pub fn full(base: PhysReg, index: PhysReg, scale: u8, disp: i32) -> Self {
        X86AddressingMode {
            base: Some(base),
            index: Some(index),
            scale,
            displacement: disp,
            is_rip_relative: false,
            segment: None,
        }
    }
    pub fn rip_relative(disp: i32) -> Self {
        X86AddressingMode {
            base: None,
            index: None,
            scale: 1,
            displacement: disp,
            is_rip_relative: true,
            segment: None,
        }
    }
    pub fn fits_disp8(&self) -> bool {
        self.displacement >= -128 && self.displacement <= 127
    }
    pub fn fits_disp32(&self) -> bool {
        true
    }
    pub fn has_base(&self) -> bool {
        self.base.is_some()
    }
    pub fn has_index(&self) -> bool {
        self.index.is_some()
    }
    pub fn has_disp(&self) -> bool {
        self.displacement != 0
    }
    pub fn classify(&self) -> AddressingModeKind {
        match (self.base, self.index, self.displacement) {
            (Some(_), None, 0) if !self.is_rip_relative => AddressingModeKind::BaseOnly,
            (Some(_), None, _) if !self.is_rip_relative => AddressingModeKind::BaseDisp,
            (Some(_), Some(_), 0) => AddressingModeKind::BaseIndexScale,
            (Some(_), Some(_), _) => AddressingModeKind::BaseIndexScaleDisp,
            (_, _, _) if self.is_rip_relative => AddressingModeKind::RIPRelative,
            _ => AddressingModeKind::Absolute,
        }
    }
}

impl Default for X86AddressingMode {
    fn default() -> Self {
        X86AddressingMode {
            base: None,
            index: None,
            scale: 1,
            displacement: 0,
            is_rip_relative: false,
            segment: None,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AddressingModeKind {
    BaseOnly,
    BaseDisp,
    BaseIndexScale,
    BaseIndexScaleDisp,
    RIPRelative,
    Absolute,
}

// ============================================================================
// X86GlobalISelFactory — Convenience Constructors
// ============================================================================

pub struct X86GlobalISelFactory;

impl X86GlobalISelFactory {
    pub fn for_x86_64(subtarget: X86Subtarget) -> X86GlobalISel {
        let mut gisel = X86GlobalISel::new(subtarget);
        gisel.translator.is_64bit = true;
        gisel.translator.ptr_size = 8;
        gisel.isel.is_64bit = true;
        gisel
    }

    pub fn for_x86_32(subtarget: X86Subtarget) -> X86GlobalISel {
        let mut gisel = X86GlobalISel::new(subtarget);
        gisel.translator.is_64bit = false;
        gisel.translator.ptr_size = 4;
        gisel.isel.is_64bit = false;
        gisel.legalizer.info = X86LegalizerInfo::default_x86_32();
        gisel
    }

    pub fn for_speed(subtarget: X86Subtarget) -> X86GlobalISel {
        let mut gisel = X86GlobalISelFactory::for_x86_64(subtarget);
        gisel.combiner.max_iterations = 16;
        gisel.combiner.cse = true;
        gisel.combiner.eliminate_dead_code = true;
        gisel
    }

    pub fn for_compile_time(subtarget: X86Subtarget) -> X86GlobalISel {
        let mut gisel = X86GlobalISelFactory::for_x86_64(subtarget);
        gisel.combiner.max_iterations = 2;
        gisel.combiner.cse = false;
        gisel.reg_bank_select.strategy = RegBankSelectStrategy::Greedy;
        gisel
    }

    pub fn for_testing(subtarget: X86Subtarget) -> X86GlobalISel {
        X86GlobalISelFactory::for_x86_64(subtarget)
    }
}

// ============================================================================
// Helper Functions
// ============================================================================

pub fn icmp_pred_to_x86_cc(pred: u32) -> u8 {
    match pred {
        0 => 4,
        1 => 5,
        2 => 2,
        3 => 3,
        4 => 6,
        5 => 7,
        6 => 12,
        7 => 13,
        8 => 8,
        9 => 9,
        _ => 4,
    }
}

pub fn fcmp_pred_to_x86_cc(pred: u32) -> u8 {
    match pred {
        0 => 0,
        1 => 4,
        2 => 12,
        3 => 13,
        4 => 8,
        5 => 9,
        6 => 5,
        7 => 3,
        8 => 6,
        9 => 2,
        10 => 15,
        11 => 14,
        12 => 7,
        13 => 6,
        14 => 5,
        15 => 0,
        _ => 4,
    }
}

pub fn is_signed_imm(val: i64, bits: u32) -> bool {
    if bits >= 64 {
        return true;
    }
    let min = -(1i64 << (bits - 1));
    let max = (1i64 << (bits - 1)) - 1;
    val >= min && val <= max
}

pub fn is_unsigned_imm(val: u64, bits: u32) -> bool {
    if bits >= 64 {
        true
    } else {
        val < (1u64 << bits)
    }
}

pub fn materialize_int64_constant(val: i64) -> (X86Opcode, bool) {
    if is_signed_imm(val, 32) {
        (X86Opcode::MOV, true)
    } else {
        (X86Opcode::MOVABS, false)
    }
}

// ============================================================================
// Pipeline Entry Points
// ============================================================================

pub fn run_x86_global_isel_pipeline(
    ir_function: &Function,
    subtarget: X86Subtarget,
) -> (GMachineFunction, X86GlobalISelStats) {
    let mut gisel = X86GlobalISelFactory::for_x86_64(subtarget);
    gisel.run_pipeline(ir_function)
}

pub fn run_x86_32_global_isel_pipeline(
    ir_function: &Function,
    subtarget: X86Subtarget,
) -> (GMachineFunction, X86GlobalISelStats) {
    let mut gisel = X86GlobalISelFactory::for_x86_32(subtarget);
    gisel.run_pipeline(ir_function)
}

// ============================================================================
// X86GISelIntermediateTypes
// ============================================================================

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86GISelType {
    S1,
    S8,
    S16,
    S32,
    S64,
    S128,
    F16,
    F32,
    F64,
    F80,
    F128,
    V4S32,
    V2S64,
    V4F32,
    V2F64,
    V8S32,
    V4S64,
    V8F32,
    V4F64,
    V16S32,
    V8S64,
    V16F32,
    V8F64,
}

impl X86GISelType {
    pub fn bit_width(&self) -> u32 {
        match self {
            X86GISelType::S1 => 1,
            X86GISelType::S8 => 8,
            X86GISelType::S16 => 16,
            X86GISelType::S32 => 32,
            X86GISelType::S64 => 64,
            X86GISelType::S128 => 128,
            X86GISelType::F16 => 16,
            X86GISelType::F32 => 32,
            X86GISelType::F64 => 64,
            X86GISelType::F80 => 80,
            X86GISelType::F128 => 128,
            X86GISelType::V4S32
            | X86GISelType::V2S64
            | X86GISelType::V4F32
            | X86GISelType::V2F64 => 128,
            X86GISelType::V8S32
            | X86GISelType::V4S64
            | X86GISelType::V8F32
            | X86GISelType::V4F64 => 256,
            X86GISelType::V16S32
            | X86GISelType::V8S64
            | X86GISelType::V16F32
            | X86GISelType::V8F64 => 512,
        }
    }

    pub fn is_scalar_int(&self) -> bool {
        matches!(
            self,
            X86GISelType::S1
                | X86GISelType::S8
                | X86GISelType::S16
                | X86GISelType::S32
                | X86GISelType::S64
                | X86GISelType::S128
        )
    }

    pub fn is_scalar_fp(&self) -> bool {
        matches!(
            self,
            X86GISelType::F16
                | X86GISelType::F32
                | X86GISelType::F64
                | X86GISelType::F80
                | X86GISelType::F128
        )
    }

    pub fn is_vector(&self) -> bool {
        matches!(
            self,
            X86GISelType::V4S32
                | X86GISelType::V2S64
                | X86GISelType::V4F32
                | X86GISelType::V2F64
                | X86GISelType::V8S32
                | X86GISelType::V4S64
                | X86GISelType::V8F32
                | X86GISelType::V4F64
                | X86GISelType::V16S32
                | X86GISelType::V8S64
                | X86GISelType::V16F32
                | X86GISelType::V8F64
        )
    }

    pub fn default_bank(&self) -> X86RegBank {
        match self {
            X86GISelType::S1
            | X86GISelType::S8
            | X86GISelType::S16
            | X86GISelType::S32
            | X86GISelType::S64
            | X86GISelType::S128 => X86RegBank::GPR,
            X86GISelType::F80 => X86RegBank::X87,
            _ if self.is_scalar_fp() => X86RegBank::XMM,
            _ if self.is_vector() && self.bit_width() <= 128 => X86RegBank::XMM,
            _ if self.is_vector() && self.bit_width() <= 256 => X86RegBank::YMM,
            _ if self.is_vector() && self.bit_width() <= 512 => X86RegBank::ZMM,
            _ => X86RegBank::GPR,
        }
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use crate::global_isel::gisel_machine_ir::{
        GInstruction, GMachineBasicBlock, GMachineFunction, GOpcode, MOperand,
    };

    // ---- Helpers ----

    fn make_add_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(2)],
        ));
        block.push_instruction(GInstruction::new(GOpcode::G_RET));
        mf.push_block(block);
        mf
    }

    fn make_multi_block_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("multi");
        let mut entry = GMachineBasicBlock::new("entry");
        entry.push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(2)],
        ));
        entry.push_instruction(GInstruction::with_operands(
            GOpcode::G_BR,
            vec![MOperand::label("exit")],
        ));
        entry.add_successor(1);
        mf.push_block(entry);
        let mut exit = GMachineBasicBlock::new("exit");
        exit.push_instruction(GInstruction::new(GOpcode::G_RET));
        mf.push_block(exit);
        mf
    }

    // ---- X86IRTranslator Tests ----

    #[test]
    fn test_translator_new() {
        let t = X86IRTranslator::new();
        assert!(t.is_64bit);
        assert_eq!(t.instructions_translated, 0);
        assert_eq!(t.blocks_translated, 0);
    }

    #[test]
    fn test_translator_new_32bit() {
        let t = X86IRTranslator::new_32bit();
        assert!(!t.is_64bit);
        assert_eq!(t.ptr_size, 4);
    }

    #[test]
    fn test_translator_vreg_allocation() {
        let mut t = X86IRTranslator::new();
        assert_eq!(t.alloc_vreg(), 0);
        assert_eq!(t.alloc_vreg(), 1);
        assert_eq!(t.alloc_vreg(), 2);
    }

    #[test]
    fn test_translator_value_map() {
        let mut t = X86IRTranslator::new();
        t.map_value(42, 7);
        assert_eq!(t.lookup_value(42), Some(7));
        assert_eq!(t.lookup_value(99), None);
    }

    #[test]
    fn test_translator_block_map() {
        let mut t = X86IRTranslator::new();
        t.map_block(10, 3);
        assert_eq!(t.lookup_block(10), Some(3));
        assert_eq!(t.lookup_block(20), None);
    }

    #[test]
    fn test_translator_reset() {
        let mut t = X86IRTranslator::new();
        t.alloc_vreg();
        t.map_value(1, 1);
        t.instructions_translated = 5;
        t.reset();
        assert_eq!(t.next_vreg, 0);
        assert_eq!(t.instructions_translated, 0);
        assert!(t.value_map.is_empty());
        assert!(t.block_map.is_empty());
    }

    // ---- X86LegalizerInfo Tests ----

    #[test]
    fn test_legalizer_info_new() {
        let info = X86LegalizerInfo::new();
        assert!(!info.rules.is_empty());
    }

    #[test]
    fn test_legalizer_info_i1_widening() {
        let info = X86LegalizerInfo::new();
        let action = info.get_action(GOpcode::G_ADD, 1);
        match action {
            LegalizeAction::WidenScalar { new_width } => assert_eq!(new_width, 8),
            _ => panic!("Expected WidenScalar for i1"),
        }
    }

    #[test]
    fn test_legalizer_info_i128_libcall() {
        let info = X86LegalizerInfo::new();
        let action = info.get_action(GOpcode::G_MUL, 128);
        match action {
            LegalizeAction::LibCall(_) => {}
            _ => panic!("Expected LibCall for i128 MUL"),
        }
    }

    #[test]
    fn test_legalizer_info_is_legal() {
        let info = X86LegalizerInfo::new();
        assert!(info.is_legal(GOpcode::G_ADD, 32));
        assert!(info.is_legal(GOpcode::G_ADD, 64));
        assert!(!info.is_legal(GOpcode::G_ADD, 1));
        assert!(!info.is_legal(GOpcode::G_ADD, 128));
    }

    // ---- X86Legalizer Tests ----

    #[test]
    fn test_legalizer_new() {
        let info = X86LegalizerInfo::new();
        let l = X86Legalizer::new(info);
        assert_eq!(l.already_legal, 0);
        assert_eq!(l.max_iterations, 32);
    }

    #[test]
    fn test_legalizer_legalize_empty() {
        let info = X86LegalizerInfo::new();
        let mut l = X86Legalizer::new(info);
        let mut mf = GMachineFunction::new("empty");
        mf.push_block(GMachineBasicBlock::new("entry"));
        let c = l.legalize(&mut mf);
        assert_eq!(c, 0);
    }

    #[test]
    fn test_legalizer_legalize_basic() {
        let info = X86LegalizerInfo::new();
        let mut l = X86Legalizer::new(info);
        let mut mf = make_add_mf();
        let c = l.legalize(&mut mf);
        // Both instructions legal
        assert_eq!(l.already_legal, 2);
    }

    #[test]
    fn test_legalizer_reset() {
        let info = X86LegalizerInfo::new();
        let mut l = X86Legalizer::new(info);
        l.already_legal = 10;
        l.lowered = 5;
        l.reset();
        assert_eq!(l.already_legal, 0);
        assert_eq!(l.lowered, 0);
    }

    #[test]
    fn test_legalizer_lower_srem() {
        let info = X86LegalizerInfo::new();
        let l = X86Legalizer::new(info);
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        mf.push_block(block);
        let mbb = 0;
        let divd = mf.new_vreg();
        let divr = mf.new_vreg();
        let rem = l.lower_srem(&mut mf, mbb, divd, divr);
        // Should have created G_SDIV + G_MUL + G_SUB
        assert!(mf.blocks[mbb].instructions.len() >= 3);
    }

    // ---- X86RegisterBankInfo Tests ----

    #[test]
    fn test_register_bank_info_new() {
        let info = X86RegisterBankInfo::new();
        assert_eq!(info.gpr.num_regs, 16);
        assert_eq!(info.xmm.num_regs, 16);
        assert_eq!(info.zmm.num_regs, 32);
        assert_eq!(info.kreg.num_regs, 8);
    }

    #[test]
    fn test_default_bank_for_opcode() {
        assert_eq!(
            X86RegisterBankInfo::default_bank_for_opcode(GOpcode::G_ADD),
            X86RegBank::GPR
        );
        assert_eq!(
            X86RegisterBankInfo::default_bank_for_opcode(GOpcode::G_FADD),
            X86RegBank::XMM
        );
        assert_eq!(
            X86RegisterBankInfo::default_bank_for_opcode(GOpcode::G_AND),
            X86RegBank::GPR
        );
    }

    #[test]
    fn test_cross_bank_copy_cost() {
        let cost = CrossBankCost::new();
        assert_eq!(cost.get_cost(X86RegBank::GPR, X86RegBank::GPR), 1);
        assert_eq!(cost.get_cost(X86RegBank::GPR, X86RegBank::XMM), 3);
        assert!(
            cost.get_cost(X86RegBank::GPR, X86RegBank::ZMM)
                > cost.get_cost(X86RegBank::GPR, X86RegBank::XMM)
        );
    }

    #[test]
    fn test_needs_cross_bank_copy() {
        let info = X86RegisterBankInfo::new();
        assert!(!info.needs_cross_bank_copy(X86RegBank::GPR, X86RegBank::GPR));
        assert!(info.needs_cross_bank_copy(X86RegBank::GPR, X86RegBank::XMM));
    }

    // ---- X86RegBankSelect Tests ----

    #[test]
    fn test_reg_bank_select_new() {
        let bank_info = X86RegisterBankInfo::new();
        let rbs = X86RegBankSelect::new(bank_info);
        assert_eq!(rbs.copies_inserted, 0);
        assert!(rbs.assignments.is_empty());
    }

    #[test]
    fn test_reg_bank_select_run_basic() {
        let bank_info = X86RegisterBankInfo::new();
        let mut rbs = X86RegBankSelect::new(bank_info);
        let mut mf = make_add_mf();
        let copies = rbs.run(&mut mf);
        assert_eq!(copies, 0); // All GPR ops
    }

    // ---- X86InstructionSelect Tests ----

    #[test]
    fn test_instruction_select_new() {
        let isel = X86InstructionSelect::new();
        assert!(isel.is_64bit);
        assert_eq!(isel.instructions_selected, 0);
    }

    #[test]
    fn test_instruction_select_basic() {
        let mut isel = X86InstructionSelect::new();
        let mut mf = make_add_mf();
        let count = isel.select_count(&mut mf);
        assert!(count > 0);
        assert!(!isel.get_selected_instructions().is_empty());
    }

    #[test]
    fn test_instruction_select_reset() {
        let mut isel = X86InstructionSelect::new();
        let mut mf = make_add_mf();
        isel.select_count(&mut mf);
        isel.reset();
        assert_eq!(isel.instructions_selected, 0);
        assert!(isel.get_selected_instructions().is_empty());
    }

    // ---- X86Combiner Tests ----

    #[test]
    fn test_combiner_new() {
        let c = X86Combiner::new();
        assert_eq!(c.combined, 0);
        assert_eq!(c.max_iterations, 8);
        assert!(c.eliminate_dead_code);
        assert!(c.cse);
    }

    #[test]
    fn test_combiner_empty() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("empty");
        mf.push_block(GMachineBasicBlock::new("entry"));
        let count = c.combine_all(&mut mf);
        assert_eq!(count, 0);
    }

    #[test]
    fn test_combiner_add_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_mul_one() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(1)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_and_minus_one() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_AND,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_or_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_OR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_xor_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_XOR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_shift_by_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_SHL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_sub_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_mul_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_mul_neg_one() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_and_zero() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_AND,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_or_all_ones() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_OR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_select_same_values() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_SELECT,
            vec![
                MOperand::vreg(0),
                MOperand::vreg(1),
                MOperand::vreg(2),
                MOperand::vreg(2),
            ],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_icmp_same_operands() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_ICMP,
            vec![
                MOperand::vreg(0),
                MOperand::imm(0),
                MOperand::vreg(1),
                MOperand::vreg(1),
            ],
        ));
        mf.push_block(block);
        let count = c.combine_all(&mut mf);
        assert!(count > 0);
    }

    #[test]
    fn test_combiner_dead_code_elimination() {
        let mut c = X86Combiner::new();
        let mut mf = GMachineFunction::new("test");
        let mut block = GMachineBasicBlock::new("entry");
        block.push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(99), MOperand::vreg(1), MOperand::vreg(2)],
        ));
        block.push_instruction(GInstruction::new(GOpcode::G_RET));
        mf.push_block(block);
        let removed = c.eliminate_dead_code_pass(&mut mf);
        assert!(removed > 0);
    }

    #[test]
    fn test_combiner_reset() {
        let mut c = X86Combiner::new();
        let mut mf = make_add_mf();
        c.combine_all(&mut mf);
        c.reset();
        assert_eq!(c.combined, 0);
    }

    // ---- X86GlobalISelFactory Tests ----

    #[test]
    fn test_factory_for_x86_64() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let pipeline = X86GlobalISelFactory::for_x86_64(st);
        assert!(pipeline.translator.is_64bit);
    }

    #[test]
    fn test_factory_for_x86_32() {
        let st = X86Subtarget::new("i686-unknown-linux-gnu", "generic", "");
        let pipeline = X86GlobalISelFactory::for_x86_32(st);
        assert!(!pipeline.translator.is_64bit);
        assert_eq!(pipeline.translator.ptr_size, 4);
    }

    #[test]
    fn test_factory_for_speed() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let pipeline = X86GlobalISelFactory::for_speed(st);
        assert_eq!(pipeline.combiner.max_iterations, 16);
        assert!(pipeline.combiner.cse);
    }

    #[test]
    fn test_factory_for_compile_time() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let pipeline = X86GlobalISelFactory::for_compile_time(st);
        assert_eq!(pipeline.combiner.max_iterations, 2);
        assert!(!pipeline.combiner.cse);
    }

    // ---- X86AddressingMode Tests ----

    #[test]
    fn test_addressing_mode_base_only() {
        let am = X86AddressingMode::base_only(0);
        assert!(am.has_base());
        assert!(!am.has_index());
        assert!(!am.has_disp());
        assert_eq!(am.classify(), AddressingModeKind::BaseOnly);
    }

    #[test]
    fn test_addressing_mode_full() {
        let am = X86AddressingMode::full(0, 1, 8, 100);
        assert!(am.has_base());
        assert!(am.has_index());
        assert!(am.has_disp());
        assert_eq!(am.classify(), AddressingModeKind::BaseIndexScaleDisp);
    }

    #[test]
    fn test_addressing_mode_rip_relative() {
        let am = X86AddressingMode::rip_relative(42);
        assert!(am.is_rip_relative);
        assert!(!am.has_base());
        assert_eq!(am.classify(), AddressingModeKind::RIPRelative);
    }

    #[test]
    fn test_addressing_mode_fits_disp8() {
        assert!(X86AddressingMode::base_disp(0, 100).fits_disp8());
        assert!(!X86AddressingMode::base_disp(0, 200).fits_disp8());
    }

    // ---- Helper Function Tests ----

    #[test]
    fn test_icmp_pred_to_x86_cc() {
        assert_eq!(icmp_pred_to_x86_cc(0), 4);
        assert_eq!(icmp_pred_to_x86_cc(1), 5);
        assert_eq!(icmp_pred_to_x86_cc(6), 12);
        assert_eq!(icmp_pred_to_x86_cc(8), 8);
    }

    #[test]
    fn test_is_signed_imm() {
        assert!(is_signed_imm(127, 8));
        assert!(is_signed_imm(-128, 8));
        assert!(!is_signed_imm(128, 8));
        assert!(is_signed_imm(0x7FFFFFFF, 32));
    }

    #[test]
    fn test_is_unsigned_imm() {
        assert!(is_unsigned_imm(255, 8));
        assert!(!is_unsigned_imm(256, 8));
    }

    // ---- X86GISelType Tests ----

    #[test]
    fn test_gisel_type_bit_width() {
        assert_eq!(X86GISelType::S32.bit_width(), 32);
        assert_eq!(X86GISelType::S64.bit_width(), 64);
        assert_eq!(X86GISelType::F32.bit_width(), 32);
        assert_eq!(X86GISelType::V4S32.bit_width(), 128);
        assert_eq!(X86GISelType::V4S64.bit_width(), 256);
    }

    #[test]
    fn test_gisel_type_scalar_int() {
        assert!(X86GISelType::S32.is_scalar_int());
        assert!(!X86GISelType::F32.is_scalar_int());
        assert!(!X86GISelType::V4S32.is_scalar_int());
    }

    #[test]
    fn test_gisel_type_vector() {
        assert!(X86GISelType::V4S32.is_vector());
        assert!(!X86GISelType::S32.is_vector());
    }

    #[test]
    fn test_gisel_type_default_bank() {
        assert_eq!(X86GISelType::S32.default_bank(), X86RegBank::GPR);
        assert_eq!(X86GISelType::F32.default_bank(), X86RegBank::XMM);
        assert_eq!(X86GISelType::V4S32.default_bank(), X86RegBank::XMM);
        assert_eq!(X86GISelType::V4S64.default_bank(), X86RegBank::YMM);
    }

    // ---- X86RegBank Tests ----

    #[test]
    fn test_x86_reg_bank_name() {
        assert_eq!(X86RegBank::GPR.name(), "GPR");
        assert_eq!(X86RegBank::XMM.name(), "XMM");
        assert_eq!(X86RegBank::YMM.name(), "YMM");
        assert_eq!(X86RegBank::ZMM.name(), "ZMM");
    }

    #[test]
    fn test_x86_reg_bank_size() {
        assert_eq!(X86RegBank::GPR.size_in_bits(), 64);
        assert_eq!(X86RegBank::XMM.size_in_bits(), 128);
        assert_eq!(X86RegBank::YMM.size_in_bits(), 256);
        assert_eq!(X86RegBank::ZMM.size_in_bits(), 512);
    }

    // ---- Multi-block Tests ----

    #[test]
    fn test_multi_block_function() {
        let mf = make_multi_block_mf();
        assert_eq!(mf.blocks.len(), 2);
        assert_eq!(mf.blocks[0].name, "entry");
        assert_eq!(mf.blocks[1].name, "exit");
        assert!(!mf.blocks[0].successors.is_empty());
    }

    #[test]
    fn test_stats_default() {
        let stats = X86GlobalISelStats::default();
        assert_eq!(stats.ir_instructions, 0);
        assert_eq!(stats.generic_instructions, 0);
        assert_eq!(stats.legalized, 0);
        assert_eq!(stats.selected, 0);
        assert_eq!(stats.combined, 0);
    }

    #[test]
    fn test_legalizer_total_processed() {
        let info = X86LegalizerInfo::new();
        let l = X86Legalizer::new(info);
        assert_eq!(l.total_processed(), 0);
    }

    #[test]
    fn test_addressing_mode_kind_enum() {
        assert_eq!(AddressingModeKind::BaseOnly as u8, 0);
        assert_eq!(AddressingModeKind::BaseDisp as u8, 1);
        assert_eq!(AddressingModeKind::BaseIndexScale as u8, 2);
        assert_eq!(AddressingModeKind::BaseIndexScaleDisp as u8, 3);
    }

    #[test]
    fn test_materialize_int64_constant() {
        let (op, fits) = materialize_int64_constant(42);
        assert_eq!(op, X86Opcode::MOV);
        assert!(fits);
        let (op, fits) = materialize_int64_constant(0x7FFFFFFFFFFFFFFFi64);
        assert_eq!(op, X86Opcode::MOVABS);
        assert!(!fits);
    }
}