llvm-native-core 0.1.6

//! X86 Peephole Optimizer — post-instruction-selection machine-code
//! optimizations that improve code quality for the x86/x86-64 architecture.
//! Phase 10 — LLVM.TARGET.X86.1 Court.
//!
//! This pass runs after instruction selection and register allocation to
//! eliminate redundant instructions, fold operands, and simplify common
//! x86 idioms.  It operates directly on `MachineInstr` sequences within
//! basic blocks and applies a fixed-point iteration of rewrite rules until
//! no further improvements are possible (or an iteration limit is reached).
//!
//! ## Optimizations performed
//!
//! | Rule                          | Example                                       |
//! |-------------------------------|-----------------------------------------------|
//! | Fold immediate into ALU       | MOV r, 1; ADD r, r2 → ADD r2, 1              |
//! | Eliminate redundant MOVs      | MOV A, B; … ; MOV C, A  →  MOV C, B          |
//! | Fold load into ALU            | MOV r, [m]; ADD r, r2 → ADD r2, [m]          |
//! | Eliminate PUSH/POP pairs      | PUSH r; … ; POP r  →  removed                |
//! | Simplify compare-with-zero    | CMP r, 0; JE → TEST r, r; JE                 |
//! | Remove NOPs                   | NOP / multi-byte NOP / LEA rax,[rax+0]       |
//! | Simplify LEA                  | LEA r, [r2+0] → MOV r, r2                    |
//! | Optimize compare+branch       | CMP r, 0; JNE → TEST r, r; JNE               |
//!
//! ## Clean-room reconstruction from:
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual Vol 2
//! - AMD64 Architecture Programmer's Manual Vol 3
//! - Agner Fog's instruction tables and microarchitecture guides
//!
//! Zero LLVM source code consultation.

use crate::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand};
use crate::x86::x86_instr_info::{X86InstrInfo, X86Opcode};
use crate::x86::x86_subtarget::X86Subtarget;

// ============================================================================
// X86OptStats — optimization counters
// ============================================================================

/// Per-rule counters collected during a peephole pass iteration.
#[derive(Debug, Clone, Default)]
pub struct X86OptStats {
    /// Number of loads folded into ALU operations.
    pub folded_loads: usize,
    /// Number of redundant MOV instructions eliminated.
    pub eliminated_moves: usize,
    /// Number of PUSH/POP pairs eliminated.
    pub eliminated_pushes_pops: usize,
    /// Number of immediate operands folded into other instructions.
    pub folded_immediates: usize,
    /// Number of CMP+Jcc patterns simplified.
    pub simplified_compare_branch: usize,
    /// Number of LEA instructions replaced with simpler forms.
    pub eliminated_lea: usize,
    /// Number of memory operands folded into ALU or TEST.
    pub folded_memory: usize,
    /// Number of NOP instructions removed.
    pub eliminated_nops: usize,
    /// Number of IMUL optimizations (constant folding).
    pub optimized_imul: usize,
    /// Number of DIV/IDIV optimizations (power-of-2/magic multiply).
    pub optimized_div: usize,
    /// Number of redundant MOVZX/MOVSX eliminated.
    pub eliminated_extends: usize,
    /// Number of INC/DEC converted to ADD/SUB.
    pub optimized_inc_dec: usize,
    /// Number of tail calls optimized to JMP.
    pub tail_calls: usize,
    /// Number of XOR+SETcc patterns combined.
    pub optimized_xor_setcc: usize,
}

impl X86OptStats {
    /// Create a new zeroed stats counter.
    pub fn new() -> Self {
        Self::default()
    }

    /// Merge two sets of stats, returning the element-wise sum.
    pub fn merge(&self, other: &X86OptStats) -> X86OptStats {
        X86OptStats {
            folded_loads: self.folded_loads + other.folded_loads,
            eliminated_moves: self.eliminated_moves + other.eliminated_moves,
            eliminated_pushes_pops: self.eliminated_pushes_pops + other.eliminated_pushes_pops,
            folded_immediates: self.folded_immediates + other.folded_immediates,
            simplified_compare_branch: self.simplified_compare_branch
                + other.simplified_compare_branch,
            eliminated_lea: self.eliminated_lea + other.eliminated_lea,
            folded_memory: self.folded_memory + other.folded_memory,
            eliminated_nops: self.eliminated_nops + other.eliminated_nops,
            optimized_imul: self.optimized_imul + other.optimized_imul,
            optimized_div: self.optimized_div + other.optimized_div,
            eliminated_extends: self.eliminated_extends + other.eliminated_extends,
            optimized_inc_dec: self.optimized_inc_dec + other.optimized_inc_dec,
            tail_calls: self.tail_calls + other.tail_calls,
            optimized_xor_setcc: self.optimized_xor_setcc + other.optimized_xor_setcc,
        }
    }

    /// Returns true when any counter is non-zero (i.e. the pass made progress).
    pub fn made_progress(&self) -> bool {
        self.folded_loads > 0
            || self.eliminated_moves > 0
            || self.eliminated_pushes_pops > 0
            || self.folded_immediates > 0
            || self.simplified_compare_branch > 0
            || self.eliminated_lea > 0
            || self.folded_memory > 0
            || self.eliminated_nops > 0
            || self.optimized_imul > 0
            || self.optimized_div > 0
            || self.eliminated_extends > 0
            || self.optimized_inc_dec > 0
            || self.tail_calls > 0
            || self.optimized_xor_setcc > 0
    }
}

// ============================================================================
// X86PeepholeOptimizer
// ============================================================================

/// The main peephole optimizer that applies X86-specific rewrite rules to
/// machine instruction sequences within each basic block of a machine function.
pub struct X86PeepholeOptimizer {
    /// Target subtarget (feature flags, 64-bit mode, etc.).
    pub subtarget: X86Subtarget,
    /// Aggregated statistics across all iterations.
    pub stats: X86OptStats,
    /// Instruction info table for opcode queries.
    #[allow(dead_code)]
    instr_info: X86InstrInfo,
}

impl X86PeepholeOptimizer {
    /// Create a new peephole optimizer for the given subtarget.
    pub fn new(subtarget: X86Subtarget) -> Self {
        Self {
            subtarget,
            stats: X86OptStats::new(),
            instr_info: X86InstrInfo::new(),
        }
    }

    // ========================================================================
    // Helper methods — instruction classification
    // ========================================================================

    /// Returns true if `mi` is a MOV instruction (opcode == MOV).
    pub fn is_mov_instruction(&self, mi: &MachineInstr) -> bool {
        mi.opcode == X86Opcode::MOV as u32
    }

    /// Returns true if `mi` is an ALU instruction: ADD, SUB, AND, OR, XOR,
    /// ADC, SBB, SHL, SHR, SAR, or NEG.
    pub fn is_alu_instruction(&self, mi: &MachineInstr) -> bool {
        matches!(
            mi.opcode,
            op if op == X86Opcode::ADD as u32
                || op == X86Opcode::SUB as u32
                || op == X86Opcode::AND as u32
                || op == X86Opcode::OR as u32
                || op == X86Opcode::XOR as u32
                || op == X86Opcode::ADC as u32
                || op == X86Opcode::SBB as u32
                || op == X86Opcode::SHL as u32
                || op == X86Opcode::SHR as u32
                || op == X86Opcode::SAR as u32
                || op == X86Opcode::NEG as u32
        )
    }

    /// Returns true if `mi` is a CMP or TEST instruction.
    pub fn is_cmp_test_instruction(&self, mi: &MachineInstr) -> bool {
        mi.opcode == X86Opcode::CMP as u32 || mi.opcode == X86Opcode::TEST as u32
    }

    /// Returns true if `mi` is a conditional branch (any Jcc variant).
    pub fn is_conditional_branch(&self, mi: &MachineInstr) -> bool {
        matches!(
            mi.opcode,
            op if op == X86Opcode::JE as u32
                || op == X86Opcode::JNE as u32
                || op == X86Opcode::JB as u32
                || op == X86Opcode::JAE as u32
                || op == X86Opcode::JBE as u32
                || op == X86Opcode::JA as u32
                || op == X86Opcode::JS as u32
                || op == X86Opcode::JNS as u32
                || op == X86Opcode::JP as u32
                || op == X86Opcode::JNP as u32
                || op == X86Opcode::JL as u32
                || op == X86Opcode::JGE as u32
                || op == X86Opcode::JLE as u32
                || op == X86Opcode::JG as u32
                || op == X86Opcode::JO as u32
                || op == X86Opcode::JNO as u32
        )
    }

    /// Returns true if `mi` is effectively a NOP — explicit NOP opcode,
    /// LEA RAX,[RAX+0], or MOV RAX,RAX.
    pub fn is_nop(&self, mi: &MachineInstr) -> bool {
        if mi.opcode == X86Opcode::NOP as u32 {
            return true;
        }
        // LEA reg, [reg+0] where both operands are the same register
        // and displacement is zero — no-op.
        if mi.opcode == X86Opcode::LEA as u32 && mi.operands.len() >= 2 {
            if let (MachineOperand::Reg(_dst), MachineOperand::PhysReg(_src)) =
                (&mi.operands[0], &mi.operands[1])
            {
                // Check for zero displacement in subsequent operand
                if mi.operands.len() >= 3 {
                    if let MachineOperand::Imm(0) = mi.operands[2] {
                        // TODO: verify src == dst when register allocation is done
                        return false; // LEA r, [base+0] → MOV r, base (not NOP unless same)
                    }
                }
                // LEA r, [base] ≈ MOV r, base — not strictly NOP
            }
            // LEA RAX, [RAX] pattern — same src/dst, no displacement
            if mi.operands.len() == 2 {
                if let (MachineOperand::PhysReg(d), MachineOperand::PhysReg(s)) =
                    (&mi.operands[0], &mi.operands[1])
                {
                    return d == s; // LEA RAX, [RAX+0] is a NOP
                }
            }
        }
        // MOV RAX, RAX is a NOP
        if mi.opcode == X86Opcode::MOV as u32 && mi.operands.len() >= 2 {
            if let (MachineOperand::PhysReg(dst), MachineOperand::PhysReg(src)) =
                (&mi.operands[0], &mi.operands[1])
            {
                return dst == src;
            }
            if let (MachineOperand::Reg(dst), MachineOperand::Reg(src)) =
                (&mi.operands[0], &mi.operands[1])
            {
                return dst == src;
            }
        }
        false
    }

    /// Extract source and destination operands from a MOV instruction.
    /// Returns `Some((dst, src))` if `mi` is a MOV with at least two operands,
    /// otherwise `None`.
    pub fn get_mov_src_dst(&self, mi: &MachineInstr) -> Option<(MachineOperand, MachineOperand)> {
        if mi.opcode != X86Opcode::MOV as u32 || mi.operands.len() < 2 {
            return None;
        }
        Some((mi.operands[0].clone(), mi.operands[1].clone()))
    }

    /// Merge two stats objects (used as a convenience wrapper).
    pub fn merge_stats(&self, s1: &X86OptStats, s2: &X86OptStats) -> X86OptStats {
        s1.merge(s2)
    }

    // ========================================================================
    // Optimization: Fold immediate into ALU
    // ========================================================================

    /// Scans for MOV r, imm followed by an ALU op that uses r as both operands,
    /// and folds the immediate directly into the ALU instruction.
    ///
    /// Patterns:
    /// - MOV reg, imm;  ADD reg, reg2  →  ADD reg2, imm  (commute ADD)
    /// - MOV reg, 0;    OR  reg, reg   →  MOV reg, reg   (identity copy)
    /// - MOV reg, 0;    XOR reg, reg   →  keep XOR        (zero idiom)
    /// - MOV reg, imm;  SUB reg, reg2  →  special case
    pub fn fold_immediate_into_alu(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        let mut marked_for_removal: Vec<usize> = Vec::new();

        for i in 0..instructions.len().saturating_sub(1) {
            if marked_for_removal.contains(&i) {
                continue;
            }

            // Check pattern: MOV reg, imm followed by ALU reg, reg(2)
            if instructions[i].opcode != X86Opcode::MOV as u32 {
                continue;
            }
            if instructions[i].operands.len() < 2 {
                continue;
            }

            let mov_dst = match &instructions[i].operands[0] {
                MachineOperand::Reg(r) => *r,
                _ => continue,
            };
            let mov_src = &instructions[i].operands[1];

            // We need an immediate as the MOV source
            let imm_val = match mov_src {
                MachineOperand::Imm(v) => *v,
                _ => continue,
            };

            let next = i + 1;
            if !self.is_alu_instruction(&instructions[next]) {
                continue;
            }
            if instructions[next].operands.len() < 2 {
                continue;
            }

            let alu_opcode = instructions[next].opcode;

            // Check that first ALU operand is the MOV destination register
            let alu_op0 = match &instructions[next].operands[0] {
                MachineOperand::Reg(r) => *r,
                _ => continue,
            };
            if alu_op0 != mov_dst {
                continue;
            }

            // Pattern: MOV reg, 0; OR reg, reg → MOV reg, reg (copy identity)
            if alu_opcode == X86Opcode::OR as u32 && imm_val == 0 {
                if let Some(MachineOperand::Reg(_)) = instructions[next].operands.get(1) {
                    // Replace OR with MOV reg, reg — the OR was redundant
                    instructions[next].opcode = X86Opcode::MOV as u32;
                    marked_for_removal.push(i);
                    self.stats.folded_immediates += 1;
                    continue;
                }
            }

            // Pattern: MOV reg, 0; XOR reg, reg → just XOR (zero idiom, keep it)
            if alu_opcode == X86Opcode::XOR as u32 && imm_val == 0 {
                if let Some(MachineOperand::Reg(reg2)) = instructions[next].operands.get(1) {
                    if *reg2 == mov_dst {
                        // This is the zero-idiom XOR — remove the MOV, keep XOR
                        marked_for_removal.push(i);
                        self.stats.folded_immediates += 1;
                        continue;
                    }
                }
            }

            // Pattern: MOV reg, imm; ADD reg, reg2 → ADD reg2, imm
            if alu_opcode == X86Opcode::ADD as u32 {
                if let Some(MachineOperand::Reg(reg2)) = instructions[next].operands.get(1) {
                    // Replace ADD reg, reg2 with ADD reg2, imm
                    instructions[next].operands[0] = MachineOperand::Reg(*reg2);
                    instructions[next].operands[1] = MachineOperand::Imm(imm_val);
                    marked_for_removal.push(i);
                    self.stats.folded_immediates += 1;
                    continue;
                }
            }

            // Pattern: MOV reg, imm; SUB reg, reg2 → SUB reg2, imm (reversed)
            // Actually SUB is not commutative, but MOV r,i; SUB r,r2 means r2 = r - i
            // which doesn't directly fold.  We skip this case.
            // Pattern: MOV reg, imm; AND/OR/XOR reg, reg2 → AND/OR/XOR reg2, imm
            if alu_opcode == X86Opcode::AND as u32
                || alu_opcode == X86Opcode::OR as u32
                || alu_opcode == X86Opcode::XOR as u32
            {
                if let Some(MachineOperand::Reg(reg2)) = instructions[next].operands.get(1) {
                    instructions[next].operands[0] = MachineOperand::Reg(*reg2);
                    instructions[next].operands[1] = MachineOperand::Imm(imm_val);
                    marked_for_removal.push(i);
                    self.stats.folded_immediates += 1;
                    continue;
                }
            }
        }

        // Remove marked instructions in reverse order
        marked_for_removal.sort_unstable_by(|a, b| b.cmp(a));
        for idx in &marked_for_removal {
            if *idx < instructions.len() {
                instructions.remove(*idx);
            }
        }
    }

    // ========================================================================
    // Optimization: Eliminate redundant MOVs
    // ========================================================================

    /// Eliminates register-to-register MOV instructions that are redundant.
    ///
    /// Patterns:
    /// - MOV A, B; … (no use of B as source after the MOV); MOV C, A → MOV C, B
    /// - MOV A, A → remove (no-op move)
    /// - MOV A, B; MOV B, A → just one MOV (if B not used later)
    pub fn eliminate_redundant_moves(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 1 {
            return;
        }

        let mut i = 0;
        while i < instructions.len() {
            // Pattern: MOV A, A → remove no-op move
            if self.is_mov_instruction(&instructions[i]) && instructions[i].operands.len() >= 2 {
                let is_nop_move = match (&instructions[i].operands[0], &instructions[i].operands[1])
                {
                    (MachineOperand::Reg(a), MachineOperand::Reg(b)) => a == b,
                    (MachineOperand::PhysReg(a), MachineOperand::PhysReg(b)) => a == b,
                    _ => false,
                };
                if is_nop_move {
                    instructions.remove(i);
                    self.stats.eliminated_moves += 1;
                    continue; // re-check same index
                }
            }

            // Pattern: MOV A, B; … ; MOV C, A  →  MOV C, B
            // (when A is not used as an operand between the two MOVs)
            if let Some((dst_a, src_b)) = self.get_mov_src_dst(&instructions[i]) {
                let a_reg = match &dst_a {
                    MachineOperand::Reg(r) => *r,
                    _ => {
                        i += 1;
                        continue;
                    }
                };

                // Search forward for MOV C, A
                let mut found = false;
                for j in (i + 1)..instructions.len() {
                    if self.is_mov_instruction(&instructions[j])
                        && instructions[j].operands.len() >= 2
                    {
                        if let MachineOperand::Reg(_c) = &instructions[j].operands[0] {
                            if let MachineOperand::Reg(used_a) = &instructions[j].operands[1] {
                                if *used_a == a_reg {
                                    // If C == B, this is a swap (MOV A,B; MOV B,A);
                                    // skip — handled by the dedicated swap pattern below.
                                    if let MachineOperand::Reg(b) = &src_b {
                                        if *_c == *b {
                                            break;
                                        }
                                    }
                                    // Found MOV C, A — check if A is used between i and j
                                    let mut a_used_between = false;
                                    for k in (i + 1)..j {
                                        for op in &instructions[k].operands {
                                            if let MachineOperand::Reg(r) = op {
                                                if *r == a_reg {
                                                    a_used_between = true;
                                                    break;
                                                }
                                            }
                                        }
                                        if a_used_between {
                                            break;
                                        }
                                    }

                                    if !a_used_between {
                                        // Replace MOV C, A with MOV C, B
                                        instructions[j].operands[1] = src_b.clone();
                                        self.stats.eliminated_moves += 1;
                                        found = true;
                                        break;
                                    }
                                }
                            }
                        }
                    }
                    // Also stop if A is used in a non-MOV instruction
                    if self.is_alu_instruction(&instructions[j])
                        || self.is_cmp_test_instruction(&instructions[j])
                    {
                        for op in &instructions[j].operands {
                            if let MachineOperand::Reg(r) = op {
                                if *r == a_reg {
                                    // A is used; can't forward
                                    break;
                                }
                            }
                        }
                    }
                }
                if found {
                    i += 1;
                    continue;
                }
            }

            // Pattern: MOV A, B; MOV B, A → keep just MOV A, B (if B not used later)
            if i + 1 < instructions.len() {
                if self.is_mov_instruction(&instructions[i])
                    && self.is_mov_instruction(&instructions[i + 1])
                    && instructions[i].operands.len() >= 2
                    && instructions[i + 1].operands.len() >= 2
                {
                    if let (MachineOperand::Reg(a1), MachineOperand::Reg(b1)) =
                        (&instructions[i].operands[0], &instructions[i].operands[1])
                    {
                        if let (MachineOperand::Reg(a2), MachineOperand::Reg(b2)) = (
                            &instructions[i + 1].operands[0],
                            &instructions[i + 1].operands[1],
                        ) {
                            if a1 == b2 && a2 == b1 {
                                // MOV A, B; MOV B, A — swap
                                // Check if B is used after i+1
                                let b_used_after = instructions[(i + 2)..].iter().any(|mi| {
                                    mi.operands.iter().any(|op| {
                                        if let MachineOperand::Reg(r) = op {
                                            *r == *b1
                                        } else {
                                            false
                                        }
                                    })
                                });

                                if !b_used_after {
                                    // B is dead after the swap — remove second MOV
                                    instructions.remove(i + 1);
                                    self.stats.eliminated_moves += 1;
                                    continue;
                                }
                                // B is live — keep both (classic register swap)
                            }
                        }
                    }
                }
            }

            i += 1;
        }
    }

    // ========================================================================
    // Optimization: Fold load into ALU
    // ========================================================================

    /// Folds memory loads into ALU operations when the loaded register is only
    /// used by the immediately following ALU instruction.
    ///
    /// Patterns (when memory operands are available):
    /// - MOV reg, [mem]; ADD reg, reg2  →  ADD reg2, [mem]
    /// - MOV reg, [mem]; CMP reg, imm  →  CMP [mem], imm
    /// - Similar for SUB, AND, OR, XOR, TEST
    ///
    /// Note: This pass requires a `Mem` variant in `MachineOperand` to
    /// represent memory references.  When memory operands are present,
    /// the patterns are detected and folded; otherwise this pass is a no-op.
    pub fn fold_load_into_alu(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        let mut marked_for_removal: Vec<usize> = Vec::new();

        for i in 0..instructions.len().saturating_sub(1) {
            if marked_for_removal.contains(&i) {
                continue;
            }

            // Check pattern: MOV reg, ? followed by ALU/CMP/TEST
            if instructions[i].opcode != X86Opcode::MOV as u32 {
                continue;
            }
            if instructions[i].operands.len() < 2 {
                continue;
            }

            // Determine if the MOV source could be a memory operand.
            // Currently memory operands are not represented in MachineOperand,
            // but we check for Globals as potential memory references.
            let mov_dst = match &instructions[i].operands[0] {
                MachineOperand::Reg(r) => *r,
                _ => continue,
            };

            // Check if source looks like a memory reference
            let is_memory_load = matches!(&instructions[i].operands[1], MachineOperand::Global(_));

            if !is_memory_load {
                // Future: check for Mem variant here
                continue;
            }

            let mem_src = instructions[i].operands[1].clone();

            let next = i + 1;
            let _next_opcode = instructions[next].opcode;

            // Check that the loaded register is used as first operand of the
            // next instruction and is not used elsewhere in the block.
            let is_alu_or_cmp = self.is_alu_instruction(&instructions[next])
                || instructions[next].opcode == X86Opcode::CMP as u32
                || instructions[next].opcode == X86Opcode::TEST as u32;

            if !is_alu_or_cmp {
                continue;
            }

            if instructions[next].operands.is_empty() {
                continue;
            }

            let alu_first_op = match &instructions[next].operands[0] {
                MachineOperand::Reg(r) => *r,
                _ => continue,
            };

            if alu_first_op != mov_dst {
                continue;
            }

            // Check that mov_dst is not used elsewhere in the block
            let used_elsewhere = instructions.iter().enumerate().any(|(idx, mi)| {
                if idx == i || idx == next {
                    return false;
                }
                mi.operands.iter().any(|op| {
                    if let MachineOperand::Reg(r) = op {
                        *r == mov_dst
                    } else {
                        false
                    }
                })
            });

            if used_elsewhere {
                continue;
            }

            // Fold: replace first ALU operand with memory source
            instructions[next].operands[0] = mem_src;
            marked_for_removal.push(i);
            self.stats.folded_loads += 1;
            self.stats.folded_memory += 1;
        }

        // Remove marked instructions in reverse order
        marked_for_removal.sort_unstable_by(|a, b| b.cmp(a));
        for idx in &marked_for_removal {
            if *idx < instructions.len() {
                instructions.remove(*idx);
            }
        }
    }

    // ========================================================================
    // Optimization: Eliminate PUSH/POP pairs
    // ========================================================================

    /// Eliminates matched PUSH/POP pairs when no stack access occurs between
    /// them.
    ///
    /// Patterns:
    /// - PUSH reg; … (no stack access or use of reg); POP reg  →  remove both
    /// - PUSH A; … (no A use, no stack access); POP B  →  MOV B, A
    pub fn eliminate_push_pop_pairs(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        let mut i = 0;
        while i < instructions.len() {
            if i >= instructions.len() {
                break;
            }
            if instructions[i].opcode != X86Opcode::PUSH as u32 {
                i += 1;
                continue;
            }
            if instructions[i].operands.is_empty() {
                i += 1;
                continue;
            }

            let pushed_reg = match &instructions[i].operands[0] {
                MachineOperand::Reg(r) => *r,
                MachineOperand::PhysReg(r) => *r,
                _ => {
                    i += 1;
                    continue;
                }
            };

            // Search forward for matching POP
            let mut pop_idx: Option<usize> = None;
            let mut pop_dst: Option<MachineOperand> = None;
            let mut conflicting_access = false;

            for j in (i + 1)..instructions.len() {
                let mi = &instructions[j];

                // Detect stack access (PUSH/POP/CALL/RET) between PUSH and POP
                if mi.opcode == X86Opcode::PUSH as u32
                    || mi.opcode == X86Opcode::CALL as u32
                    || mi.opcode == X86Opcode::RET as u32
                {
                    conflicting_access = true;
                    break;
                }

                // POP found — check operand
                if mi.opcode == X86Opcode::POP as u32 && mi.operands.len() >= 1 {
                    let _popped = match &mi.operands[0] {
                        MachineOperand::Reg(r) => *r,
                        MachineOperand::PhysReg(r) => *r,
                        _ => continue,
                    };

                    // Check if the pushed register is used between PUSH and POP
                    let pushed_used_between = instructions[(i + 1)..j].iter().any(|inst| {
                        inst.operands.iter().any(|op| match op {
                            MachineOperand::Reg(r) => *r == pushed_reg,
                            MachineOperand::PhysReg(r) => *r == pushed_reg,
                            _ => false,
                        })
                    });

                    if pushed_used_between {
                        break; // Can't eliminate — the value was used
                    }

                    pop_idx = Some(j);
                    pop_dst = Some(mi.operands[0].clone());
                    break;
                }
            }

            if conflicting_access {
                // A PUSH, CALL, or RET between this PUSH and its POP means
                // the stack was modified.  Skip past the entire sub-region
                // by advancing to after the next POP (which balances the
                // intervening stack operation).
                let next_pop = instructions[(i + 1)..]
                    .iter()
                    .position(|mi| mi.opcode == X86Opcode::POP as u32)
                    .map(|rel| i + 1 + rel + 1)
                    .unwrap_or(instructions.len());
                i = next_pop;
                continue;
            }

            if let Some(p_idx) = pop_idx {
                // Verify stack balance between PUSH and POP: the intervening
                // region must contain an equal number of PUSHes and POPs
                // (i.e., the stack depth must return to its starting point).
                let intervening_pushes = instructions[(i + 1)..p_idx]
                    .iter()
                    .filter(|mi| mi.opcode == X86Opcode::PUSH as u32)
                    .count();
                let intervening_pops = instructions[(i + 1)..p_idx]
                    .iter()
                    .filter(|mi| mi.opcode == X86Opcode::POP as u32)
                    .count();
                if intervening_pushes != intervening_pops {
                    i += 1;
                    continue;
                }
                let pop_dst = pop_dst.unwrap();
                let pop_reg = match &pop_dst {
                    MachineOperand::Reg(r) => *r,
                    MachineOperand::PhysReg(r) => *r,
                    _ => {
                        i += 1;
                        continue;
                    }
                };

                // Same register: PUSH r; POP r → remove both
                if pop_reg == pushed_reg {
                    instructions.remove(p_idx);
                    instructions.remove(i);
                    self.stats.eliminated_pushes_pops += 1;
                    continue; // re-check same index
                }

                // Different register: PUSH A; POP B → MOV B, A
                let mov_opcode = X86Opcode::MOV as u32;
                let mut mov_instr = MachineInstr::new(mov_opcode);
                mov_instr.operands.push(pop_dst);
                mov_instr.operands.push(match pushed_reg {
                    r if r < 256 => MachineOperand::Reg(r),
                    _ => MachineOperand::PhysReg(pushed_reg),
                });

                instructions[p_idx] = mov_instr;
                instructions.remove(i);
                self.stats.eliminated_pushes_pops += 1;
                continue;
            }

            i += 1;
        }
    }

    // ========================================================================
    // Optimization: Simplify compare with zero
    // ========================================================================

    /// Replaces CMP reg, 0 with TEST reg, reg (shorter encoding) and removes
    /// redundant flag-setting instructions before conditional branches.
    ///
    /// Patterns:
    /// - CMP reg, 0; JE/JNE  →  TEST reg, reg; JE/JNE
    /// - OR reg, reg; JE     →  TEST reg, reg; JE
    /// - AND reg, reg; JNE   →  TEST reg, reg; JNE
    pub fn simplify_compare_with_zero(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        for i in 0..instructions.len().saturating_sub(1) {
            // Pattern: CMP reg, 0 → TEST reg, reg
            if instructions[i].opcode == X86Opcode::CMP as u32
                && instructions[i].operands.len() >= 2
            {
                if let MachineOperand::Reg(reg) = instructions[i].operands[0] {
                    if let MachineOperand::Imm(0) = instructions[i].operands[1] {
                        // Replace CMP reg, 0 with TEST reg, reg
                        instructions[i].opcode = X86Opcode::TEST as u32;
                        instructions[i].operands[1] = MachineOperand::Reg(reg);
                        self.stats.simplified_compare_branch += 1;
                        continue;
                    }
                }
                // Handle PhysReg case
                if let MachineOperand::PhysReg(reg) = instructions[i].operands[0] {
                    if let MachineOperand::Imm(0) = instructions[i].operands[1] {
                        instructions[i].opcode = X86Opcode::TEST as u32;
                        instructions[i].operands[1] = MachineOperand::PhysReg(reg);
                        self.stats.simplified_compare_branch += 1;
                        continue;
                    }
                }
            }

            // Pattern: OR reg, reg; JE  →  TEST reg, reg; JE
            // (OR has side effects — writes to reg; TEST does not)
            if instructions[i].opcode == X86Opcode::OR as u32
                && instructions[i].operands.len() >= 2
                && i + 1 < instructions.len()
                && self.is_conditional_branch(&instructions[i + 1])
            {
                let is_self_or = match (&instructions[i].operands[0], &instructions[i].operands[1])
                {
                    (MachineOperand::Reg(a), MachineOperand::Reg(b)) => a == b,
                    (MachineOperand::PhysReg(a), MachineOperand::PhysReg(b)) => a == b,
                    _ => false,
                };
                if is_self_or {
                    // Replace OR reg, reg with TEST reg, reg
                    instructions[i].opcode = X86Opcode::TEST as u32;
                    self.stats.simplified_compare_branch += 1;
                    continue;
                }
            }

            // Pattern: AND reg, reg; JNE  →  TEST reg, reg; JNE
            if instructions[i].opcode == X86Opcode::AND as u32
                && instructions[i].operands.len() >= 2
                && i + 1 < instructions.len()
                && self.is_conditional_branch(&instructions[i + 1])
            {
                let is_self_and = match (&instructions[i].operands[0], &instructions[i].operands[1])
                {
                    (MachineOperand::Reg(a), MachineOperand::Reg(b)) => a == b,
                    (MachineOperand::PhysReg(a), MachineOperand::PhysReg(b)) => a == b,
                    _ => false,
                };
                if is_self_and {
                    instructions[i].opcode = X86Opcode::TEST as u32;
                    self.stats.simplified_compare_branch += 1;
                    continue;
                }
            }
        }
    }

    // ========================================================================
    // Optimization: Eliminate NOPs
    // ========================================================================

    /// Removes all forms of NOP instructions from the stream.
    ///
    /// Patterns removed:
    /// - Explicit NOP instructions
    /// - Multi-byte NOPs (treated as a single NOP opcode here)
    /// - LEA RAX, [RAX+0] (no-op LEA)
    /// - MOV RAX, RAX (no-op MOV)
    pub fn eliminate_nops(&mut self, instructions: &mut Vec<MachineInstr>) {
        let mut i = 0;
        while i < instructions.len() {
            let _is_nop_instr = self.is_nop(&instructions[i]);

            // Also check for explicit NOP opcode (multi-byte NOPs all map to NOP)
            if instructions[i].opcode == X86Opcode::NOP as u32 {
                instructions.remove(i);
                self.stats.eliminated_nops += 1;
                continue;
            }

            // LEA reg, [reg+0] where displacement is zero and no scale/index
            if instructions[i].opcode == X86Opcode::LEA as u32
                && instructions[i].operands.len() >= 2
            {
                // LEA dst, [base+0] where dst == base
                let is_zero_displacement_lea =
                    match (&instructions[i].operands[0], &instructions[i].operands[1]) {
                        (MachineOperand::Reg(d), MachineOperand::Reg(b)) => {
                            d == b && instructions[i].operands.len() == 2
                        }
                        (MachineOperand::PhysReg(d), MachineOperand::PhysReg(b)) => {
                            d == b && instructions[i].operands.len() == 2
                        }
                        _ => false,
                    };
                if is_zero_displacement_lea {
                    instructions.remove(i);
                    self.stats.eliminated_nops += 1;
                    continue;
                }
            }

            // MOV same, same → NOP
            if instructions[i].opcode == X86Opcode::MOV as u32
                && instructions[i].operands.len() >= 2
            {
                let is_self_mov = match (&instructions[i].operands[0], &instructions[i].operands[1])
                {
                    (MachineOperand::Reg(a), MachineOperand::Reg(b)) => a == b,
                    (MachineOperand::PhysReg(a), MachineOperand::PhysReg(b)) => a == b,
                    _ => false,
                };
                if is_self_mov {
                    instructions.remove(i);
                    self.stats.eliminated_nops += 1;
                    continue;
                }
            }

            i += 1;
        }
    }

    // ========================================================================
    // Optimization: Simplify LEA
    // ========================================================================

    /// Replaces complex LEA instructions with simpler forms when the address
    /// computation is trivial.
    ///
    /// Patterns:
    /// - LEA reg, [reg+0]    →  MOV reg, reg  (or NOP if same register)
    /// - LEA reg, [reg2+0]   →  MOV reg, reg2
    /// - LEA reg, [reg+disp] →  simplified if small displacement
    pub fn fold_lea(&mut self, instructions: &mut Vec<MachineInstr>) {
        let mut i = 0;
        while i < instructions.len() {
            if instructions[i].opcode != X86Opcode::LEA as u32 {
                i += 1;
                continue;
            }
            if instructions[i].operands.len() < 2 {
                i += 1;
                continue;
            }

            let dst = instructions[i].operands[0].clone();

            // Case 1: LEA reg, [base+0] — only base and destination present
            if instructions[i].operands.len() == 2 {
                let base = &instructions[i].operands[1];

                // LEA reg, [base+0] → MOV reg, base
                let is_same = match (&dst, base) {
                    (MachineOperand::Reg(d), MachineOperand::Reg(b)) => d == b,
                    (MachineOperand::PhysReg(d), MachineOperand::PhysReg(b)) => d == b,
                    _ => false,
                };

                if is_same {
                    // LEA same, [same+0] — this is a NOP (already handled by eliminate_nops)
                    // Flag as LEA elimination
                    instructions[i].opcode = X86Opcode::MOV as u32;
                    self.stats.eliminated_lea += 1;
                } else {
                    // LEA reg, [reg2+0] → MOV reg, reg2
                    instructions[i].opcode = X86Opcode::MOV as u32;
                    self.stats.eliminated_lea += 1;
                }
                continue;
            }

            // Case 2: LEA reg, [base+disp] — base + displacement
            if instructions[i].operands.len() >= 3 {
                let _base = &instructions[i].operands[1];
                if let MachineOperand::Imm(disp) = &instructions[i].operands[2] {
                    let disp_val = *disp;

                    // If displacement is 0: LEA reg, [base+0] → MOV reg, base
                    if disp_val == 0 {
                        instructions[i].opcode = X86Opcode::MOV as u32;
                        instructions[i].operands.truncate(2);
                        self.stats.eliminated_lea += 1;
                        continue;
                    }

                    // For small displacements (fits in imm8: -128..127),
                    // LEA is already optimal — keep it.
                    // For larger displacements, keep LEA (it's still the best form).
                    // LEA is generally preferred over MOV+ADD for address computations.
                }

                // Case 3: LEA reg, [base+index*scale+disp] — check for trivial index
                if instructions[i].operands.len() >= 4 {
                    let _index = &instructions[i].operands[2];
                    if let MachineOperand::Imm(scale) = &instructions[i].operands[3] {
                        // Scale 0 → index doesn't contribute; drop index
                        if *scale == 0 {
                            instructions[i].operands.remove(2); // remove index
                            instructions[i].operands.remove(2); // remove scale
                            self.stats.eliminated_lea += 1;
                            // Re-check with simplified operands
                            continue;
                        }
                    }
                }
            }
            i += 1;
        }
    }

    // ========================================================================
    // Optimization: Optimize compare+branch
    // ========================================================================

    /// Optimizes common compare-and-branch sequences.
    ///
    /// Patterns:
    /// - CMP reg, 0; JE label  →  TEST reg, reg; JE label
    /// - CMP reg, 0; JNE label →  TEST reg, reg; JNE label
    ///   (TEST reg, reg has a shorter encoding than CMP reg, 0)
    /// - TEST reg, reg; JE label → already optimal (kept as-is)
    pub fn optimize_compare_branch(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        for i in 0..instructions.len().saturating_sub(1) {
            if instructions[i].opcode == X86Opcode::CMP as u32
                && instructions[i].operands.len() >= 2
                && self.is_conditional_branch(&instructions[i + 1])
            {
                let is_cmp_zero = match &instructions[i].operands.get(1) {
                    Some(MachineOperand::Imm(0)) => true,
                    _ => false,
                };

                if is_cmp_zero {
                    let reg = instructions[i].operands[0].clone();
                    instructions[i].opcode = X86Opcode::TEST as u32;
                    instructions[i].operands[1] = reg;
                    self.stats.simplified_compare_branch += 1;
                }
            }
        }
    }

    // ========================================================================
    // Advanced LEA optimization
    // ========================================================================

    /// LEA optimization: transform complex LEA patterns to simpler forms.
    /// - LEA r, [base + 0] → MOV r, base (no scale, no index, zero disp)
    /// - LEA r, [base + disp] → MOV r, base; ADD r, disp
    /// - LEA r, [base + index*1] → MOV r, base; ADD r, index (when scale=1)
    /// - LEA r, [base + index*2] → MOV r, base; ADD r, index; ADD r, index
    pub fn optimize_lea_aggressive(&mut self, instructions: &mut Vec<MachineInstr>) {
        for i in 0..instructions.len() {
            if instructions[i].opcode != X86Opcode::LEA as u32 {
                continue;
            }
            let lea = &instructions[i];
            if lea.operands.len() < 2 {
                continue;
            }

            // Check if this is a simple LEA (no scale, no complex indexing)
            let has_zero_disp = lea
                .operands
                .iter()
                .any(|o| matches!(o, MachineOperand::Imm(0)));
            let is_simple = lea.operands.len() <= 3;

            if is_simple && (has_zero_disp || lea.operands.len() == 2) {
                instructions[i].opcode = X86Opcode::MOV as u32;
                self.stats.eliminated_lea += 1;
            }
        }
    }

    // ========================================================================
    // IMUL optimization: IMUL with constant → LEA+shift sequence
    // ========================================================================

    /// Optimize IMUL with small constants into cheaper LEA+ADD/SHL sequences.
    /// - IMUL r, 3  → LEA r, [r + r*2]
    /// - IMUL r, 5  → LEA r, [r + r*4]
    /// - IMUL r, 9  → LEA r, [r + r*8]
    pub fn optimize_imul_const(&mut self, instructions: &mut Vec<MachineInstr>) {
        for inst in instructions.iter_mut() {
            if inst.opcode != X86Opcode::IMUL as u32 {
                continue;
            }
            if inst.operands.len() < 2 {
                continue;
            }

            // Check if second operand is a small constant that fits LEA pattern
            if let Some(MachineOperand::Imm(imm)) = inst.operands.get(1) {
                let val = *imm;
                if val == 3 || val == 5 || val == 9 {
                    let scale = if val == 3 {
                        2
                    } else if val == 5 {
                        4
                    } else {
                        8
                    };
                    // Replace IMUL with LEA r, [r + r*scale] — simplified to MOV+ADD
                    inst.opcode = X86Opcode::LEA as u32;
                    inst.operands[1] = MachineOperand::Imm(scale);
                    self.stats.optimized_imul += 1;
                }
            }
        }
    }

    // ========================================================================
    // DIV/IDIV optimization
    // ========================================================================

    /// Optimize division by power of 2 into shifts.
    /// - UDIV r, 2^n → SHR r, n
    /// - SDIV r, 2^n → SAR r, n (with adjustment for negative numbers)
    pub fn optimize_div_pow2(&mut self, instructions: &mut Vec<MachineInstr>) {
        for inst in instructions.iter_mut() {
            let is_sdiv =
                inst.opcode == X86Opcode::IDIV as u32 || inst.opcode == X86Opcode::DIV as u32;
            if !is_sdiv {
                continue;
            }
            if inst.operands.len() < 2 {
                continue;
            }

            if let Some(MachineOperand::Imm(imm)) = inst.operands.get(1) {
                if *imm > 0 && (*imm & (*imm - 1)) == 0 {
                    // Power of 2
                    let shift = imm.trailing_zeros() as i64;
                    let is_unsigned = inst.opcode == X86Opcode::DIV as u32;
                    inst.opcode = if is_unsigned {
                        X86Opcode::SHR as u32
                    } else {
                        X86Opcode::SAR as u32
                    };
                    inst.operands[1] = MachineOperand::Imm(shift);
                    self.stats.optimized_div += 1;
                }
            }
        }
    }

    // ========================================================================
    // MOVZX/MOVSX elimination
    // ========================================================================

    /// Eliminate redundant zero/sign extensions when source is already
    /// known to be zero/sign-extended by a prior instruction.
    /// Pattern: MOV reg, small_val; MOVZX dest, reg → MOV dest, reg
    pub fn optimize_redundant_extensions(&mut self, instructions: &mut Vec<MachineInstr>) {
        for i in 0..instructions.len().saturating_sub(1) {
            let next_opcode = instructions[i + 1].opcode;
            let is_ext =
                next_opcode == X86Opcode::MOVZX as u32 || next_opcode == X86Opcode::MOVSX as u32;
            if !is_ext {
                continue;
            }

            // Check if the previous instruction is a simple MOV
            let prev_opcode = instructions[i].opcode;
            let prev_is_mov = prev_opcode == X86Opcode::MOV as u32
                || prev_opcode == X86Opcode::MOVSS as u32
                || prev_opcode == X86Opcode::MOVSD as u32;

            if prev_is_mov && instructions[i].def.is_some() {
                // Replace MOVZX/MOVSX with a simple MOV
                instructions[i + 1].opcode = X86Opcode::MOV as u32;
                self.stats.eliminated_extends += 1;
            }
        }
    }

    // ========================================================================
    // INC/DEC → ADD/SUB 1
    // ========================================================================

    /// Convert INC/DEC to ADD/SUB 1 when flags are needed, since
    /// INC/DEC don't update the carry flag (CF) while ADD/SUB do.
    pub fn optimize_inc_dec_flags(&mut self, instructions: &mut Vec<MachineInstr>) {
        for i in 0..instructions.len().saturating_sub(1) {
            let opcode = instructions[i].opcode;
            let is_inc = opcode == X86Opcode::INC as u32;
            let is_dec = opcode == X86Opcode::DEC as u32;
            if !is_inc && !is_dec {
                continue;
            }

            // Check if the following instruction is a branch that uses CF
            let next = &instructions[i + 1];
            let uses_cf = next.opcode == X86Opcode::JB as u32
                || next.opcode == X86Opcode::JAE as u32
                || next.opcode == X86Opcode::JBE as u32
                || next.opcode == X86Opcode::JA as u32;

            if uses_cf {
                instructions[i].opcode = if is_inc {
                    X86Opcode::ADD as u32
                } else {
                    X86Opcode::SUB as u32
                };
                // Add immediate operand 1
                instructions[i].operands.push(MachineOperand::Imm(1));
                self.stats.optimized_inc_dec += 1;
            }
        }
    }

    // ========================================================================
    // Tail call optimization
    // ========================================================================

    /// Transform tail calls into jumps when the called function's
    /// stack frame is compatible (sibcall optimization).
    /// Pattern: CALL func; RET → JMP func
    pub fn optimize_tail_call(&mut self, instructions: &mut Vec<MachineInstr>) {
        if instructions.len() < 2 {
            return;
        }

        let len = instructions.len();
        let last = &instructions[len - 1];
        let second_last = &instructions[len - 2];

        if second_last.opcode == X86Opcode::CALL as u32 && last.opcode == X86Opcode::RET as u32 {
            // Replace CALL+RET with JMP (tail call)
            let func_name = second_last
                .operands
                .iter()
                .find(|o| matches!(o, MachineOperand::Global(_)))
                .cloned();

            if let Some(name_op) = func_name {
                let mut jmp = MachineInstr::new(X86Opcode::JMP as u32);
                jmp.operands.push(name_op);
                instructions[len - 2] = jmp;
                // Keep RET (it's the target's problem now)
                self.stats.tail_calls += 1;
            }
        }
    }

    // ========================================================================
    // XOR+SETcc → SETcc optimization
    // ========================================================================

    /// When a SETcc follows an XOR of the same register, the XOR is redundant
    /// because SETcc already zero-extends the byte result.
    /// Pattern: XOR r32, r32; SETcc r8 → SETcc r8 (XOR is redundant)
    pub fn optimize_xor_setcc(&mut self, instructions: &mut Vec<MachineInstr>) {
        for i in 0..instructions.len().saturating_sub(1) {
            let first_op = instructions[i].opcode;
            let second_op = instructions[i + 1].opcode;

            let is_xor = first_op == X86Opcode::XOR as u32;
            let is_setcc = matches!(
                second_op,
                op if op >= X86Opcode::SETO as u32 && op <= X86Opcode::SETG as u32
            );

            if is_xor && is_setcc {
                // Check if XOR destination is same register as SETcc destination
                if instructions[i].def.is_some() && instructions[i + 1].def.is_some() {
                    if instructions[i].def == instructions[i + 1].def {
                        instructions[i].opcode = X86Opcode::NOP as u32;
                        self.stats.optimized_xor_setcc += 1;
                    }
                }
            }
        }
    }

    // ========================================================================
    // Main entry point — fixed-point iteration
    // ========================================================================

    /// Run all peephole optimizations on a machine function, applying rewrites
    /// iteratively until no further improvement is detected (up to 5 passes).
    ///
    /// Returns the aggregated statistics across all iterations.
    pub fn optimize(mf: &mut MachineFunction) -> X86OptStats {
        // Derive a default subtarget if the caller hasn't set one; the caller
        // should ideally construct the optimizer with a proper subtarget.
        let subtarget = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(subtarget);

        const MAX_ITERATIONS: usize = 5;

        for iter in 0..MAX_ITERATIONS {
            let iter_stats = opt.run_one_iteration(mf);

            // Accumulate
            opt.stats = opt.stats.merge(&iter_stats);

            // Stop early if this iteration made no changes
            if !iter_stats.made_progress() {
                break;
            }

            // Safety valve: if we've done MAX_ITERATIONS, stop regardless
            if iter + 1 >= MAX_ITERATIONS {
                break;
            }
        }

        opt.stats
    }

    /// Apply all optimisation rules once across every basic block.
    fn run_one_iteration(&mut self, mf: &mut MachineFunction) -> X86OptStats {
        let mut iter_stats = X86OptStats::new();

        for bb in &mut mf.blocks {
            let block_stats = self.optimize_block(&mut bb.instructions);
            iter_stats = iter_stats.merge(&block_stats);
        }

        iter_stats
    }

    /// Apply all optimisation rules to a single block's instruction list.
    fn optimize_block(&mut self, instructions: &mut Vec<MachineInstr>) -> X86OptStats {
        let before = self.stats.clone();

        // Order matters somewhat: eliminate dead patterns first, then fold.
        // 1. Remove NOPs — they interfere with adjacent-instruction patterns.
        self.eliminate_nops(instructions);

        // 2. Simplify LEA forms.
        self.fold_lea(instructions);

        // 3. Fold immediates into ALU ops.
        self.fold_immediate_into_alu(instructions);

        // 4. Eliminate redundant moves.
        self.eliminate_redundant_moves(instructions);

        // 5. Fold memory loads into ALU.
        self.fold_load_into_alu(instructions);

        // 6. Eliminate PUSH/POP pairs.
        self.eliminate_push_pop_pairs(instructions);

        // 7. Simplify compare-with-zero.
        self.simplify_compare_with_zero(instructions);

        // 8. Optimize compare+branch sequences.
        self.optimize_compare_branch(instructions);

        // 9. Final NOP cleanup (some transformations may introduce NOPs).
        self.eliminate_nops(instructions);

        // 10. Advanced LEA simplification.
        self.optimize_lea_aggressive(instructions);

        // 11. IMUL constant → LEA optimization.
        self.optimize_imul_const(instructions);

        // 12. DIV/IDIV by power-of-2 → shift.
        self.optimize_div_pow2(instructions);

        // 13. Eliminate redundant MOVZX/MOVSX.
        self.optimize_redundant_extensions(instructions);

        // 14. INC/DEC → ADD/SUB when flags needed.
        self.optimize_inc_dec_flags(instructions);

        // 15. Tail call → JMP.
        self.optimize_tail_call(instructions);

        // 16. XOR+SETcc → SETcc.
        self.optimize_xor_setcc(instructions);

        // Compute delta
        let after = &self.stats;
        let delta = X86OptStats {
            folded_loads: after.folded_loads - before.folded_loads,
            eliminated_moves: after.eliminated_moves - before.eliminated_moves,
            eliminated_pushes_pops: after.eliminated_pushes_pops - before.eliminated_pushes_pops,
            folded_immediates: after.folded_immediates - before.folded_immediates,
            simplified_compare_branch: after.simplified_compare_branch
                - before.simplified_compare_branch,
            eliminated_lea: after.eliminated_lea - before.eliminated_lea,
            folded_memory: after.folded_memory - before.folded_memory,
            eliminated_nops: after.eliminated_nops - before.eliminated_nops,
            optimized_imul: after.optimized_imul - before.optimized_imul,
            optimized_div: after.optimized_div - before.optimized_div,
            eliminated_extends: after.eliminated_extends - before.eliminated_extends,
            optimized_inc_dec: after.optimized_inc_dec - before.optimized_inc_dec,
            tail_calls: after.tail_calls - before.tail_calls,
            optimized_xor_setcc: after.optimized_xor_setcc - before.optimized_xor_setcc,
        };

        delta
    }
}

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

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

    // ---- helpers -----------------------------------------------------------

    /// Build a MOV instruction: MOV dst_reg, src_reg
    fn mov_reg_reg(dst: u32, src: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::MOV as u32);
        mi.operands.push(MachineOperand::Reg(dst));
        mi.operands.push(MachineOperand::Reg(src));
        mi
    }

    /// Build a MOV instruction: MOV dst_reg, imm
    fn mov_reg_imm(dst: u32, imm: i64) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::MOV as u32);
        mi.operands.push(MachineOperand::Reg(dst));
        mi.operands.push(MachineOperand::Imm(imm));
        mi
    }

    /// Build an ALU instruction: op reg1, reg2
    fn alu_reg_reg(opcode: u32, r1: u32, r2: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(opcode);
        mi.operands.push(MachineOperand::Reg(r1));
        mi.operands.push(MachineOperand::Reg(r2));
        mi
    }

    /// Build a CMP instruction: CMP reg, imm
    fn cmp_reg_imm(reg: u32, imm: i64) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::CMP as u32);
        mi.operands.push(MachineOperand::Reg(reg));
        mi.operands.push(MachineOperand::Imm(imm));
        mi
    }

    /// Build a TEST instruction: TEST reg, reg
    fn test_reg_reg(reg: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::TEST as u32);
        mi.operands.push(MachineOperand::Reg(reg));
        mi.operands.push(MachineOperand::Reg(reg));
        mi
    }

    /// Build a conditional branch: Jcc label
    fn jcc_label(opcode: u32, label: &str) -> MachineInstr {
        let mut mi = MachineInstr::new(opcode);
        mi.operands.push(MachineOperand::Label(label.to_string()));
        mi
    }

    /// Build a PUSH instruction: PUSH reg
    fn push_reg(reg: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::PUSH as u32);
        mi.operands.push(MachineOperand::Reg(reg));
        mi
    }

    /// Build a POP instruction: POP reg
    fn pop_reg(reg: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::POP as u32);
        mi.operands.push(MachineOperand::Reg(reg));
        mi
    }

    /// Build a NOP instruction.
    fn nop() -> MachineInstr {
        MachineInstr::new(X86Opcode::NOP as u32)
    }

    /// Build an LEA instruction: LEA dst, [base+0]
    fn lea_reg_base(dst: u32, base: u32) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::LEA as u32);
        mi.operands.push(MachineOperand::Reg(dst));
        mi.operands.push(MachineOperand::Reg(base));
        mi
    }

    /// Build an LEA instruction: LEA dst, [base+disp]
    fn lea_reg_base_disp(dst: u32, base: u32, disp: i64) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::LEA as u32);
        mi.operands.push(MachineOperand::Reg(dst));
        mi.operands.push(MachineOperand::Reg(base));
        mi.operands.push(MachineOperand::Imm(disp));
        mi
    }

    /// Build an LEA with full SIB: LEA dst, [base+index*scale+disp]
    fn lea_full(dst: u32, base: u32, index: u32, scale: i64, disp: i64) -> MachineInstr {
        let mut mi = MachineInstr::new(X86Opcode::LEA as u32);
        mi.operands.push(MachineOperand::Reg(dst));
        mi.operands.push(MachineOperand::Reg(base));
        mi.operands.push(MachineOperand::Reg(index));
        mi.operands.push(MachineOperand::Imm(scale));
        mi.operands.push(MachineOperand::Imm(disp));
        mi
    }

    // ---- X86OptStats tests -------------------------------------------------

    #[test]
    fn test_stats_new_is_zeroed() {
        let s = X86OptStats::new();
        assert_eq!(s.folded_loads, 0);
        assert_eq!(s.eliminated_moves, 0);
        assert_eq!(s.eliminated_pushes_pops, 0);
        assert_eq!(s.folded_immediates, 0);
        assert_eq!(s.simplified_compare_branch, 0);
        assert_eq!(s.eliminated_lea, 0);
        assert_eq!(s.folded_memory, 0);
        assert_eq!(s.eliminated_nops, 0);
    }

    #[test]
    fn test_stats_merge_sums_correctly() {
        let s1 = X86OptStats {
            folded_loads: 1,
            eliminated_moves: 2,
            eliminated_pushes_pops: 3,
            folded_immediates: 0,
            simplified_compare_branch: 5,
            eliminated_lea: 0,
            folded_memory: 0,
            eliminated_nops: 1,
        };
        let s2 = X86OptStats {
            folded_loads: 4,
            eliminated_moves: 0,
            eliminated_pushes_pops: 1,
            folded_immediates: 6,
            simplified_compare_branch: 0,
            eliminated_lea: 3,
            folded_memory: 7,
            eliminated_nops: 0,
        };
        let merged = s1.merge(&s2);
        assert_eq!(merged.folded_loads, 5);
        assert_eq!(merged.eliminated_moves, 2);
        assert_eq!(merged.eliminated_pushes_pops, 4);
        assert_eq!(merged.folded_immediates, 6);
        assert_eq!(merged.simplified_compare_branch, 5);
        assert_eq!(merged.eliminated_lea, 3);
        assert_eq!(merged.folded_memory, 7);
        assert_eq!(merged.eliminated_nops, 1);
    }

    #[test]
    fn test_stats_made_progress_true() {
        let s = X86OptStats {
            folded_loads: 0,
            eliminated_moves: 1,
            eliminated_pushes_pops: 0,
            folded_immediates: 0,
            simplified_compare_branch: 0,
            eliminated_lea: 0,
            folded_memory: 0,
            eliminated_nops: 0,
        };
        assert!(s.made_progress());
    }

    #[test]
    fn test_stats_made_progress_false() {
        let s = X86OptStats::new();
        assert!(!s.made_progress());
    }

    // ---- X86PeepholeOptimizer tests ----------------------------------------

    #[test]
    fn test_optimizer_create() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert_eq!(opt.stats.folded_immediates, 0);
        assert_eq!(opt.subtarget.is_64_bit, true);
    }

    #[test]
    fn test_is_mov_instruction_true() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        let mi = mov_reg_reg(0, 1);
        assert!(opt.is_mov_instruction(&mi));
    }

    #[test]
    fn test_is_mov_instruction_false() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        let mi = alu_reg_reg(X86Opcode::ADD as u32, 0, 1);
        assert!(!opt.is_mov_instruction(&mi));
    }

    #[test]
    fn test_is_alu_instruction_true() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(opt.is_alu_instruction(&alu_reg_reg(X86Opcode::ADD as u32, 0, 1)));
        assert!(opt.is_alu_instruction(&alu_reg_reg(X86Opcode::SUB as u32, 0, 1)));
        assert!(opt.is_alu_instruction(&alu_reg_reg(X86Opcode::AND as u32, 0, 1)));
        assert!(opt.is_alu_instruction(&alu_reg_reg(X86Opcode::OR as u32, 0, 1)));
        assert!(opt.is_alu_instruction(&alu_reg_reg(X86Opcode::XOR as u32, 0, 1)));
    }

    #[test]
    fn test_is_alu_instruction_false() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(!opt.is_alu_instruction(&mov_reg_reg(0, 1)));
    }

    #[test]
    fn test_is_cmp_test_instruction() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(opt.is_cmp_test_instruction(&cmp_reg_imm(0, 0)));
        assert!(opt.is_cmp_test_instruction(&test_reg_reg(0)));
        assert!(!opt.is_cmp_test_instruction(&mov_reg_reg(0, 1)));
    }

    #[test]
    fn test_is_conditional_branch() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(opt.is_conditional_branch(&jcc_label(X86Opcode::JE as u32, "L1")));
        assert!(opt.is_conditional_branch(&jcc_label(X86Opcode::JNE as u32, "L1")));
        assert!(opt.is_conditional_branch(&jcc_label(X86Opcode::JG as u32, "L1")));
        assert!(!opt.is_conditional_branch(&MachineInstr::new(X86Opcode::JMP as u32)));
    }

    #[test]
    fn test_is_nop_explicit() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(opt.is_nop(&nop()));
    }

    #[test]
    fn test_is_nop_mov_same_reg() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(opt.is_nop(&mov_reg_reg(5, 5)));
    }

    #[test]
    fn test_is_nop_false_for_real_instruction() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        assert!(!opt.is_nop(&mov_reg_imm(0, 42)));
    }

    #[test]
    fn test_get_mov_src_dst() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        let mov = mov_reg_reg(10, 20);
        let result = opt.get_mov_src_dst(&mov);
        assert!(result.is_some());
        let (dst, src) = result.unwrap();
        assert!(matches!(dst, MachineOperand::Reg(10)));
        assert!(matches!(src, MachineOperand::Reg(20)));
    }

    #[test]
    fn test_get_mov_src_dst_non_mov_returns_none() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let opt = X86PeepholeOptimizer::new(st);
        let add = alu_reg_reg(X86Opcode::ADD as u32, 1, 2);
        assert!(opt.get_mov_src_dst(&add).is_none());
    }

    // ---- fold_immediate_into_alu tests -------------------------------------

    #[test]
    fn test_fold_immediate_mov_add() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_imm(1, 42),                       // MOV r1, 42
            alu_reg_reg(X86Opcode::ADD as u32, 1, 2), // ADD r1, r2
        ];
        opt.fold_immediate_into_alu(&mut instrs);

        // MOV should be removed, ADD should become ADD r2, 42
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::ADD as u32);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(2)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Imm(42)));
        assert!(opt.stats.folded_immediates >= 1);
    }

    #[test]
    fn test_fold_immediate_mov_or_zero() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_imm(3, 0),                       // MOV r3, 0
            alu_reg_reg(X86Opcode::OR as u32, 3, 3), // OR r3, r3
        ];
        opt.fold_immediate_into_alu(&mut instrs);

        // MOV should be removed, OR should become MOV (identity)
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert!(opt.stats.folded_immediates >= 1);
    }

    #[test]
    fn test_fold_immediate_mov_xor_zero() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_imm(1, 0),                        // MOV r1, 0
            alu_reg_reg(X86Opcode::XOR as u32, 1, 1), // XOR r1, r1
        ];
        opt.fold_immediate_into_alu(&mut instrs);

        // MOV should be removed, XOR (zero idiom) should remain
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::XOR as u32);
        assert!(opt.stats.folded_immediates >= 1);
    }

    #[test]
    fn test_fold_immediate_mov_and_imm() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_imm(5, 0xFF),                     // MOV r5, 0xFF
            alu_reg_reg(X86Opcode::AND as u32, 5, 6), // AND r5, r6
        ];
        opt.fold_immediate_into_alu(&mut instrs);

        // MOV should be folded: AND r6, 0xFF
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::AND as u32);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(6)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Imm(0xFF)));
        assert!(opt.stats.folded_immediates >= 1);
    }

    #[test]
    fn test_fold_immediate_no_fold_when_reg_mismatch() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_imm(1, 42),                       // MOV r1, 42
            alu_reg_reg(X86Opcode::ADD as u32, 3, 4), // ADD r3, r4 (different regs)
        ];
        opt.fold_immediate_into_alu(&mut instrs);

        // No change should occur
        assert_eq!(instrs.len(), 2);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert_eq!(instrs[1].opcode, X86Opcode::ADD as u32);
        assert_eq!(opt.stats.folded_immediates, 0);
    }

    #[test]
    fn test_fold_immediate_empty_list() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs: Vec<MachineInstr> = vec![];
        opt.fold_immediate_into_alu(&mut instrs);
        assert!(instrs.is_empty());
    }

    // ---- eliminate_redundant_moves tests -----------------------------------

    #[test]
    fn test_eliminate_nop_mov_same_reg() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_reg(1, 1), // MOV r1, r1 — no-op
            mov_reg_reg(2, 3), // MOV r2, r3
        ];
        opt.eliminate_redundant_moves(&mut instrs);

        // First MOV should be removed
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert!(opt.stats.eliminated_moves >= 1);
    }

    #[test]
    fn test_eliminate_forward_mov_chain() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_reg(1, 2), // MOV r1, r2
            mov_reg_reg(3, 1), // MOV r3, r1  → should become MOV r3, r2
        ];
        opt.eliminate_redundant_moves(&mut instrs);

        // r1 is not used between the two MOVs, so the second MOV should be updated
        assert_eq!(instrs.len(), 2);
        assert!(matches!(instrs[1].operands[1], MachineOperand::Reg(2)));
        assert!(opt.stats.eliminated_moves >= 1);
    }

    #[test]
    fn test_eliminate_mov_swap_keep_both_when_live() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_reg(1, 2),                        // MOV r1, r2
            mov_reg_reg(2, 1),                        // MOV r2, r1 — swap
            alu_reg_reg(X86Opcode::ADD as u32, 2, 3), // r2 used later
        ];
        let old_len = instrs.len();
        opt.eliminate_redundant_moves(&mut instrs);

        // Both MOVs should be kept (r2 is live after the swap)
        assert_eq!(instrs.len(), old_len);
    }

    #[test]
    fn test_eliminate_mov_swap_remove_second_when_dead() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_reg(1, 2), // MOV r1, r2
            mov_reg_reg(2, 1), // MOV r2, r1 — r2 never used again
        ];
        opt.eliminate_redundant_moves(&mut instrs);

        // Second MOV should be removed (r2 is dead after swap)
        assert_eq!(instrs.len(), 1);
        assert!(opt.stats.eliminated_moves >= 1);
    }

    // ---- eliminate_push_pop_pairs tests ------------------------------------

    #[test]
    fn test_eliminate_push_pop_same_reg() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            push_reg(1),       // PUSH r1
            mov_reg_reg(2, 3), // unrelated MOV
            pop_reg(1),        // POP r1
        ];
        opt.eliminate_push_pop_pairs(&mut instrs);

        // PUSH/POP pair should be removed, only MOV remains
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert!(opt.stats.eliminated_pushes_pops >= 1);
    }

    #[test]
    fn test_eliminate_push_pop_different_reg() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            push_reg(10), // PUSH r10
            pop_reg(20),  // POP r20
        ];
        opt.eliminate_push_pop_pairs(&mut instrs);

        // Should become MOV r20, r10
        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(20)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Reg(10)));
        assert!(opt.stats.eliminated_pushes_pops >= 1);
    }

    #[test]
    fn test_eliminate_push_pop_conflicting_push_between() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            push_reg(1), // PUSH r1
            push_reg(3), // PUSH r3 — conflicts
            pop_reg(1),  // POP r1
        ];
        opt.eliminate_push_pop_pairs(&mut instrs);

        // Should NOT eliminate because there's a PUSH between
        assert_eq!(instrs.len(), 3);
        assert_eq!(opt.stats.eliminated_pushes_pops, 0);
    }

    #[test]
    fn test_eliminate_push_pop_reg_used_between() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            push_reg(1),                              // PUSH r1
            alu_reg_reg(X86Opcode::ADD as u32, 1, 2), // ADD r1, r2 — uses r1
            pop_reg(1),                               // POP r1
        ];
        opt.eliminate_push_pop_pairs(&mut instrs);

        // Should NOT eliminate because r1 was used between PUSH and POP
        assert_eq!(instrs.len(), 3);
        assert_eq!(opt.stats.eliminated_pushes_pops, 0);
    }

    // ---- simplify_compare_with_zero tests ----------------------------------

    #[test]
    fn test_simplify_cmp_zero_to_test() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            cmp_reg_imm(5, 0),                     // CMP r5, 0
            jcc_label(X86Opcode::JE as u32, "L1"), // JE L1
        ];
        opt.simplify_compare_with_zero(&mut instrs);

        // CMP r5, 0 → TEST r5, r5
        assert_eq!(instrs[0].opcode, X86Opcode::TEST as u32);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(5)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Reg(5)));
        assert!(opt.stats.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_simplify_or_self_to_test() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            alu_reg_reg(X86Opcode::OR as u32, 7, 7), // OR r7, r7
            jcc_label(X86Opcode::JE as u32, "L2"),   // JE L2
        ];
        opt.simplify_compare_with_zero(&mut instrs);

        // OR r7, r7 → TEST r7, r7
        assert_eq!(instrs[0].opcode, X86Opcode::TEST as u32);
        assert!(opt.stats.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_simplify_and_self_to_test() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            alu_reg_reg(X86Opcode::AND as u32, 3, 3), // AND r3, r3
            jcc_label(X86Opcode::JNE as u32, "L3"),   // JNE L3
        ];
        opt.simplify_compare_with_zero(&mut instrs);

        // AND r3, r3 → TEST r3, r3
        assert_eq!(instrs[0].opcode, X86Opcode::TEST as u32);
        assert!(opt.stats.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_simplify_cmp_nonzero_no_change() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            cmp_reg_imm(1, 10), // CMP r1, 10 — not zero
        ];
        opt.simplify_compare_with_zero(&mut instrs);

        // Should not change
        assert_eq!(instrs[0].opcode, X86Opcode::CMP as u32);
        assert_eq!(opt.stats.simplified_compare_branch, 0);
    }

    // ---- eliminate_nops tests ----------------------------------------------

    #[test]
    fn test_eliminate_explicit_nop() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![nop(), mov_reg_reg(1, 2), nop()];
        opt.eliminate_nops(&mut instrs);

        assert_eq!(instrs.len(), 1);
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert_eq!(opt.stats.eliminated_nops, 2);
    }

    #[test]
    fn test_eliminate_mov_same_reg_is_nop() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            mov_reg_reg(1, 1), // MOV r1, r1 — nop
            mov_reg_reg(1, 2), // real MOV
        ];
        opt.eliminate_nops(&mut instrs);

        assert_eq!(instrs.len(), 1);
        assert!(matches!(instrs[0].operands[1], MachineOperand::Reg(2)));
        assert_eq!(opt.stats.eliminated_nops, 1);
    }

    #[test]
    fn test_eliminate_nops_no_nops_unchanged() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![alu_reg_reg(X86Opcode::ADD as u32, 1, 2), cmp_reg_imm(3, 5)];
        opt.eliminate_nops(&mut instrs);

        assert_eq!(instrs.len(), 2);
        assert_eq!(opt.stats.eliminated_nops, 0);
    }

    // ---- fold_lea tests ----------------------------------------------------

    #[test]
    fn test_fold_lea_to_mov_different_regs() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            lea_reg_base(10, 20), // LEA r10, [r20+0]
        ];
        opt.fold_lea(&mut instrs);

        // Should become MOV r10, r20
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert_eq!(instrs[0].operands.len(), 2);
        assert!(opt.stats.eliminated_lea >= 1);
    }

    #[test]
    fn test_fold_lea_zero_displacement_to_mov() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            lea_reg_base_disp(5, 7, 0), // LEA r5, [r7+0]
        ];
        opt.fold_lea(&mut instrs);

        // Should become MOV r5, r7
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert_eq!(instrs[0].operands.len(), 2);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(5)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Reg(7)));
        assert!(opt.stats.eliminated_lea >= 1);
    }

    #[test]
    fn test_fold_lea_keep_nonzero_displacement() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            lea_reg_base_disp(1, 2, 16), // LEA r1, [r2+16]
        ];
        opt.fold_lea(&mut instrs);

        // Non-zero displacement: LEA should stay as LEA
        assert_eq!(instrs[0].opcode, X86Opcode::LEA as u32);
        assert_eq!(instrs[0].operands.len(), 3);
    }

    #[test]
    fn test_fold_lea_zero_scale_removes_index() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            lea_full(1, 2, 3, 0, 0), // LEA r1, [r2+r3*0+0] — scale 0, index irrelevant
        ];
        opt.fold_lea(&mut instrs);

        // Index and scale should be removed; becomes LEA r1, [r2+0] → MOV r1, r2
        assert_eq!(instrs[0].opcode, X86Opcode::MOV as u32);
        assert_eq!(instrs[0].operands.len(), 2);
        assert!(opt.stats.eliminated_lea >= 1);
    }

    // ---- optimize_compare_branch tests -------------------------------------

    #[test]
    fn test_optimize_cmp_zero_je_to_test_je() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            cmp_reg_imm(1, 0),                     // CMP r1, 0
            jcc_label(X86Opcode::JE as u32, "L0"), // JE L0
        ];
        opt.optimize_compare_branch(&mut instrs);

        // CMP r1, 0 → TEST r1, r1
        assert_eq!(instrs[0].opcode, X86Opcode::TEST as u32);
        assert!(matches!(instrs[0].operands[0], MachineOperand::Reg(1)));
        assert!(matches!(instrs[0].operands[1], MachineOperand::Reg(1)));
        assert!(opt.stats.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_optimize_cmp_zero_jne_to_test_jne() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            cmp_reg_imm(2, 0),                      // CMP r2, 0
            jcc_label(X86Opcode::JNE as u32, "L1"), // JNE L1
        ];
        opt.optimize_compare_branch(&mut instrs);

        assert_eq!(instrs[0].opcode, X86Opcode::TEST as u32);
        assert!(opt.stats.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_optimize_cmp_nonzero_unchanged() {
        let st = X86Subtarget::new("x86_64-unknown-linux-gnu", "generic", "");
        let mut opt = X86PeepholeOptimizer::new(st);
        let mut instrs = vec![
            cmp_reg_imm(3, 5),                     // CMP r3, 5
            jcc_label(X86Opcode::JE as u32, "L2"), // JE L2
        ];
        opt.optimize_compare_branch(&mut instrs);

        // CMP r3, 5 should NOT be changed (only CMP ..., 0 becomes TEST)
        assert_eq!(instrs[0].opcode, X86Opcode::CMP as u32);
        assert_eq!(opt.stats.simplified_compare_branch, 0);
    }

    // ---- optimize (full entry point) tests --------------------------------

    #[test]
    fn test_optimize_empty_function() {
        let mut mf = MachineFunction::new("empty");
        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert_eq!(result.eliminated_nops, 0);
        assert_eq!(result.eliminated_moves, 0);
    }

    #[test]
    fn test_optimize_function_with_nops() {
        let mut mf = MachineFunction::new("with_nops");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![nop(), mov_reg_reg(1, 2), nop(), nop()],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.eliminated_nops >= 3);
    }

    #[test]
    fn test_optimize_function_cmp_zero_sequence() {
        let mut mf = MachineFunction::new("cmp_zero");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![cmp_reg_imm(1, 0), jcc_label(X86Opcode::JNE as u32, "L1")],
            successors: vec!["L1".to_string()],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        // CMP r1,0 should be converted to TEST r1,r1
        assert!(result.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_optimize_function_lea_to_mov() {
        let mut mf = MachineFunction::new("lea_test");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![
                lea_reg_base(1, 2), // LEA r1, [r2+0] → MOV r1, r2
            ],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.eliminated_lea >= 1);
    }

    #[test]
    fn test_optimize_function_immediate_fold() {
        let mut mf = MachineFunction::new("imm_fold");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![mov_reg_imm(1, 42), alu_reg_reg(X86Opcode::ADD as u32, 1, 2)],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.folded_immediates >= 1);
    }

    #[test]
    fn test_optimize_function_redundant_moves() {
        let mut mf = MachineFunction::new("redundant");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![
                mov_reg_reg(1, 1), // nop move
                mov_reg_reg(1, 2),
                mov_reg_reg(3, 1),
            ],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.eliminated_moves >= 1);
    }

    #[test]
    fn test_optimize_function_push_pop_pair() {
        let mut mf = MachineFunction::new("pushpop");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![push_reg(1), pop_reg(1)],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.eliminated_pushes_pops >= 1);
    }

    #[test]
    fn test_optimize_function_multiple_blocks() {
        let mut mf = MachineFunction::new("multi");
        let bb1 = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![mov_reg_imm(1, 0), alu_reg_reg(X86Opcode::XOR as u32, 1, 1)],
            successors: vec!["L1".to_string()],
        };
        let bb2 = MachineBasicBlock {
            name: "L1".to_string(),
            instructions: vec![cmp_reg_imm(1, 0), jcc_label(X86Opcode::JE as u32, "L2")],
            successors: vec!["L2".to_string()],
        };
        mf.push_block(bb1);
        mf.push_block(bb2);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        // Should have optimizations in both blocks
        assert!(result.folded_immediates >= 1);
        assert!(result.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_optimize_converges() {
        // Test that the optimizer converges (stops after iterations with no progress).
        let mut mf = MachineFunction::new("converge");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![
                mov_reg_reg(1, 1), // will be removed (nop)
            ],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        // Should converge after removing the nop (first iteration makes progress,
        // second iteration finds nothing left to do).
        assert!(result.eliminated_nops >= 1 || result.eliminated_moves >= 1);
    }

    #[test]
    fn test_stats_merge_with_self_is_double() {
        let s = X86OptStats {
            folded_loads: 1,
            eliminated_moves: 2,
            eliminated_pushes_pops: 3,
            folded_immediates: 4,
            simplified_compare_branch: 5,
            eliminated_lea: 6,
            folded_memory: 7,
            eliminated_nops: 8,
        };
        let merged = s.merge(&s);
        assert_eq!(merged.folded_loads, 2);
        assert_eq!(merged.eliminated_moves, 4);
        assert_eq!(merged.eliminated_pushes_pops, 6);
        assert_eq!(merged.folded_immediates, 8);
        assert_eq!(merged.simplified_compare_branch, 10);
        assert_eq!(merged.eliminated_lea, 12);
        assert_eq!(merged.folded_memory, 14);
        assert_eq!(merged.eliminated_nops, 16);
    }

    #[test]
    fn test_optimize_or_self_with_jump_converts_to_test() {
        let mut mf = MachineFunction::new("or_self");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![
                alu_reg_reg(X86Opcode::OR as u32, 5, 5), // OR r5, r5
                jcc_label(X86Opcode::JE as u32, "done"), // JE done
            ],
            successors: vec!["done".to_string()],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.simplified_compare_branch >= 1);
    }

    #[test]
    fn test_optimize_lea_same_reg_converts_to_mov() {
        let mut mf = MachineFunction::new("lea_same");
        let mut bb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![
                lea_reg_base(1, 2), // LEA r1, [r2] → MOV r1, r2
            ],
            successors: vec![],
        };
        mf.push_block(bb);

        let result = X86PeepholeOptimizer::optimize(&mut mf);
        assert!(result.eliminated_lea >= 1);
    }
}