llvm-native-core 0.1.10

//! GlobalISel Combiner (Machine IR Peephole Optimizer).
//!
//! Clean-room behavioral reconstruction from the LLVM GlobalISel
//! documentation and the Combiner design. Zero LLVM C++ source
//! code consultation.
//!
//! The combiner applies peephole optimizations to the generic
//! Machine IR: algebraic simplifications, copy propagation,
//! constant folding, and identity elimination.

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

/// The GlobalISel combiner pass.
///
/// Scans the machine function for patterns that can be
/// simplified and applies transformations in place.
pub struct GISelCombiner {
    /// Number of instructions combined (removed or simplified).
    pub combined: usize,
    /// Number of combine iterations performed.
    iterations: usize,
    /// Maximum number of combine iterations.
    max_iterations: usize,
}

impl GISelCombiner {
    pub fn new() -> Self {
        GISelCombiner {
            combined: 0,
            iterations: 0,
            max_iterations: 8,
        }
    }

    /// Runs the combiner on a machine function until convergence
    /// or until the maximum number of iterations is reached.
    pub fn combine(&mut self, mf: &mut GMachineFunction) {
        self.combined = 0;
        self.iterations = 0;

        for _ in 0..self.max_iterations {
            self.iterations += 1;
            let mut any_changed = false;

            for block_idx in 0..mf.blocks.len() {
                let inst_count = mf.blocks[block_idx].instruction_count();
                let mut idx = 0;
                while idx < inst_count {
                    let changed = self.combine_instruction(mf, block_idx, idx);
                    if changed {
                        any_changed = true;
                        // The instruction at `idx` was removed/modified;
                        // re-scan at the same position.
                    } else {
                        idx += 1;
                    }
                }
            }

            if !any_changed {
                break;
            }
        }
    }

    /// Attempts to combine/simplify a single instruction.
    /// Returns true if the instruction was modified or removed.
    pub fn combine_instruction(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        if idx >= mf.blocks[block_idx].instruction_count() {
            return false;
        }

        // Try each combine pattern.
        if self.try_combine_add_zero(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_mul_one(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_and_all_ones(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_copy_propagation(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_constant_fold(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_sub_self(mf, block_idx, idx) {
            return true;
        }

        false
    }

    /// Simplifies `G_ADD %x, 0` → `COPY %x`.
    fn try_combine_add_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ADD {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        // Check if either operand is a constant zero.
        let op1 = &inst.operands[1];
        let op2 = &inst.operands[2];

        let non_zero = if op1.as_imm() == Some(0) {
            op2.as_vreg()
        } else if op2.as_imm() == Some(0) {
            op1.as_vreg()
        } else {
            return false;
        };

        if let Some(src) = non_zero {
            // Replace G_ADD with COPY.
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Simplifies `G_MUL %x, 1` → `COPY %x`.
    fn try_combine_mul_one(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_MUL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let op1 = &inst.operands[1];
        let op2 = &inst.operands[2];

        let non_one = if op1.as_imm() == Some(1) {
            op2.as_vreg()
        } else if op2.as_imm() == Some(1) {
            op1.as_vreg()
        } else {
            return false;
        };

        if let Some(src) = non_one {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Simplifies `G_AND %x, -1` → `COPY %x`.
    fn try_combine_and_all_ones(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_AND {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let check_all_ones =
            |op: &MOperand| -> bool { matches!(op, MOperand::Imm(-1) | MOperand::Imm(-1_i64)) };

        let op1 = &inst.operands[1];
        let op2 = &inst.operands[2];

        let non_ones = if check_all_ones(op1) {
            op2.as_vreg()
        } else if check_all_ones(op2) {
            op1.as_vreg()
        } else {
            return false;
        };

        if let Some(src) = non_ones {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Propagates copies: if instruction `idx` uses a vreg that was
    /// defined by a COPY, replace the use with the COPY's source.
    fn try_combine_copy_propagation(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        // This is a simplified version that looks for:
        //   %a = COPY %b
        //   ... = G_ADD %d, %a, %c
        // → ... = G_ADD %d, %b, %c
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode == GOpcode::COPY {
            return false; // don't propagate into COPY itself
        }

        // For each use operand, check if the defining instruction is a COPY.
        let mut replacements: Vec<(usize, VReg)> = Vec::new();
        for (op_idx, operand) in inst.operands.iter().enumerate().skip(1) {
            if let Some(vreg) = operand.as_vreg() {
                // Search backward in the same block for the COPY defining this vreg.
                for prev_idx in (0..idx).rev() {
                    let prev = &mf.blocks[block_idx].instructions[prev_idx];
                    if prev.opcode == GOpcode::COPY && prev.def_vreg() == Some(vreg) {
                        if let Some(src) = prev.operands.get(1).and_then(|o| o.as_vreg()) {
                            replacements.push((op_idx, src));
                        }
                        break;
                    }
                }
            }
        }

        if replacements.is_empty() {
            return false;
        }

        // Apply replacements.
        for (op_idx, new_src) in replacements {
            mf.blocks[block_idx].instructions[idx].operands[op_idx] = MOperand::vreg(new_src);
        }
        self.combined += 1;
        true
    }

    /// Constant folding: if both operands of a binary op are constants,
    /// replace with the computed result.
    fn try_combine_constant_fold(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.operands.len() < 3 {
            return false;
        }

        let lhs = inst.operands[1].as_imm();
        let rhs = inst.operands[2].as_imm();

        let (lhs, rhs) = match (lhs, rhs) {
            (Some(l), Some(r)) => (l, r),
            _ => return false,
        };

        let result: Option<i64> = match inst.opcode {
            GOpcode::G_ADD => Some(lhs.wrapping_add(rhs)),
            GOpcode::G_SUB => Some(lhs.wrapping_sub(rhs)),
            GOpcode::G_MUL => Some(lhs.wrapping_mul(rhs)),
            GOpcode::G_AND => Some(lhs & rhs),
            GOpcode::G_OR => Some(lhs | rhs),
            GOpcode::G_XOR => Some(lhs ^ rhs),
            GOpcode::G_SHL => {
                let shift = rhs as u32;
                if shift < 64 {
                    Some(lhs.wrapping_shl(shift))
                } else {
                    Some(0)
                }
            }
            GOpcode::G_LSHR => {
                let shift = rhs as u32;
                if shift < 64 {
                    Some(((lhs as u64).wrapping_shr(shift)) as i64)
                } else {
                    Some(0)
                }
            }
            GOpcode::G_ASHR => {
                let shift = rhs as u32;
                if shift < 64 {
                    Some(lhs.wrapping_shr(shift))
                } else {
                    Some(lhs >> 63) // sign extension
                }
            }
            _ => None,
        };

        if let Some(val) = result {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(val)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Simplifies `G_SUB %x, %x` → `G_CONSTANT 0`.
    fn try_combine_sub_self(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SUB {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let op1 = inst.operands[1].as_vreg();
        let op2 = inst.operands[2].as_vreg();

        if op1 == op2 && op1.is_some() {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(0)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Returns the number of instructions combined.
    pub fn combined_count(&self) -> usize {
        self.combined
    }

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

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

    /// Resets internal counters.
    pub fn reset(&mut self) {
        self.combined = 0;
        self.iterations = 0;
    }
}

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

// ---------------------------------------------------------------------------
// More Combine Patterns — Extension, Truncation, GEP, Pointer Conversions
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine sext(zext x) → zext x.
    ///
    /// A zero-extension followed by a sign-extension from the same
    /// bit width is equivalent to just the zero-extension, since
    /// zero-extended bits are non-negative.
    fn try_combine_sext_of_zext(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SEXT {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }

        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        // Look for a previous instruction that defines src_vreg as G_ZEXT.
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ZEXT && prev.def_vreg() == Some(src_vreg) {
                // Replace G_SEXT with G_ZEXT.
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let zext_src = prev.operands[1].as_vreg().unwrap_or(0);
                let new_inst = GInstruction::with_operands(
                    GOpcode::G_ZEXT,
                    vec![MOperand::vreg(dst), MOperand::vreg(zext_src)],
                );
                mf.blocks[block_idx].instructions[idx] = new_inst;
                self.combined += 1;
                return true;
            }
        }

        false
    }

    /// Combine trunc(binop(x, y)) → binop(trunc(x), trunc(y)).
    ///
    /// When a binary operation is truncated, push the truncation
    /// through to the operands, performing the operation in a
    /// narrower width.
    fn try_combine_trunc_of_binop(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_TRUNC {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }

        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        // Find the definition of src_vreg.
        for def_idx in (0..idx).rev() {
            let def_inst = &mf.blocks[block_idx].instructions[def_idx];
            if def_inst.def_vreg() != Some(src_vreg) {
                continue;
            }

            if !def_inst.opcode.is_binary_op() {
                return false;
            }

            let opcode = def_inst.opcode;
            let op_a = def_inst.operands[1].as_vreg().unwrap_or(0);
            let op_b = def_inst.operands[2].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);

            // Create: %t1 = trunc(op_a), %t2 = trunc(op_b), %dst = op(%t1, %t2)
            let t1 = dst + 100;
            let t2 = dst + 200;

            let trunc1 = GInstruction::with_operands(
                GOpcode::G_TRUNC,
                vec![MOperand::vreg(t1), MOperand::vreg(op_a)],
            );
            let trunc2 = GInstruction::with_operands(
                GOpcode::G_TRUNC,
                vec![MOperand::vreg(t2), MOperand::vreg(op_b)],
            );
            let binop = GInstruction::with_operands(
                opcode,
                vec![MOperand::vreg(dst), MOperand::vreg(t1), MOperand::vreg(t2)],
            );

            mf.blocks[block_idx].instructions[idx] = trunc1;
            mf.blocks[block_idx].instructions.insert(idx + 1, trunc2);
            mf.blocks[block_idx].instructions.insert(idx + 2, binop);

            self.combined += 1;
            return true;
        }

        false
    }

    /// Combine inttoptr(ptrtoint x) → x (round-trip elimination).
    fn try_combine_inttoptr_ptrtoint(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_INTTOPTR {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }

        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_PTRTOINT && prev.def_vreg() == Some(src_vreg) {
                // inttoptr(ptrtoint(x)) → x
                let original_ptr = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let copy = GInstruction::with_operands(
                    GOpcode::COPY,
                    vec![MOperand::vreg(dst), MOperand::vreg(original_ptr)],
                );
                mf.blocks[block_idx].instructions[idx] = copy;
                self.combined += 1;
                return true;
            }
        }

        false
    }

    /// Combine ptrtoint(inttoptr x) → x.
    fn try_combine_ptrtoint_inttoptr(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_PTRTOINT {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }

        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_INTTOPTR && prev.def_vreg() == Some(src_vreg) {
                let original_int = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let copy = GInstruction::with_operands(
                    GOpcode::COPY,
                    vec![MOperand::vreg(dst), MOperand::vreg(original_int)],
                );
                mf.blocks[block_idx].instructions[idx] = copy;
                self.combined += 1;
                return true;
            }
        }

        false
    }

    /// Narrow ICmp: if both operands are extensions, compare the
    /// original narrower values.
    fn try_combine_narrow_icmp(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ICMP {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }

        let lhs_vreg = match inst.operands[2].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        let rhs_vreg = match inst.operands[3].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        // Check if both operands are defined by the same extension.
        let mut lhs_src: Option<VReg> = None;
        let mut rhs_src: Option<VReg> = None;
        let mut ext_opcode: Option<GOpcode> = None;

        for prev_idx in 0..idx {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode.is_extension() {
                if prev.def_vreg() == Some(lhs_vreg) {
                    lhs_src = prev.operands.get(1).and_then(|o| o.as_vreg());
                    ext_opcode = Some(prev.opcode);
                }
                if prev.def_vreg() == Some(rhs_vreg) {
                    rhs_src = prev.operands.get(1).and_then(|o| o.as_vreg());
                }
            }
        }

        if let (Some(l), Some(r), Some(op)) = (lhs_src, rhs_src, ext_opcode) {
            // Both extended by same op; compare the original values.
            let pred = inst.operands[1].as_imm().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let new_icmp = GInstruction::with_operands(
                GOpcode::G_ICMP,
                vec![
                    MOperand::vreg(dst),
                    MOperand::imm(pred),
                    MOperand::vreg(l),
                    MOperand::vreg(r),
                ],
            );
            mf.blocks[block_idx].instructions[idx] = new_icmp;
            self.combined += 1;
            let _ = op; // use ext_opcode for narrowing decision
            return true;
        }

        false
    }

    /// Combine GEP canonicalization: replace G_PTR_ADD with constant
    /// offset by G_CONSTANT + G_PTR_ADD.
    fn try_combine_gep_canonicalization(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_PTR_ADD {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let base = inst.operands[1].as_vreg();
        let offset = inst.operands[2].as_imm();

        // If offset is 0, replace with COPY of base.
        if offset == Some(0) {
            if let Some(b) = base {
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let copy = GInstruction::with_operands(
                    GOpcode::COPY,
                    vec![MOperand::vreg(dst), MOperand::vreg(b)],
                );
                mf.blocks[block_idx].instructions[idx] = copy;
                self.combined += 1;
                return true;
            }
        }

        false
    }

    /// Combine extensions: if the same value is sign-extended and then
    /// zero-extended, use just the zero-extension.
    fn combine_extension(&mut self, mf: &mut GMachineFunction) {
        // Scan for redundant extension patterns.
        let num_blocks = mf.blocks.len();
        for block_idx in 0..num_blocks {
            let mut i = 0;
            while i < mf.blocks[block_idx].instruction_count() {
                let opcode = mf.blocks[block_idx].instructions[i].opcode;
                if opcode.is_extension() {
                    if self.try_combine_sext_of_zext(mf, block_idx, i) {
                        continue;
                    }
                }
                i += 1;
            }
        }
    }

    /// Combine truncations: push trunc through binops.
    fn combine_truncation(&mut self, mf: &mut GMachineFunction) {
        let num_blocks = mf.blocks.len();
        for block_idx in 0..num_blocks {
            let mut i = 0;
            while i < mf.blocks[block_idx].instruction_count() {
                let opcode = mf.blocks[block_idx].instructions[i].opcode;
                if opcode.is_truncation() {
                    if self.try_combine_trunc_of_binop(mf, block_idx, i) {
                        continue;
                    }
                }
                i += 1;
            }
        }
    }

    /// Run all combine patterns (extended version).
    pub fn combine_all(&mut self, mf: &mut GMachineFunction) {
        self.combined = 0;
        self.iterations = 0;

        for _ in 0..self.max_iterations {
            self.iterations += 1;
            let mut any_changed = false;

            for block_idx in 0..mf.blocks.len() {
                let mut idx = 0;
                while idx < mf.blocks[block_idx].instruction_count() {
                    let changed = self.combine_instruction_all(mf, block_idx, idx);
                    if changed {
                        any_changed = true;
                    } else {
                        idx += 1;
                    }
                }
            }

            if !any_changed {
                break;
            }
        }
    }

    /// Extended combine_instruction with all patterns.
    fn combine_instruction_all(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        if self.combine_instruction(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_sext_of_zext(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_trunc_of_binop(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_inttoptr_ptrtoint(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_ptrtoint_inttoptr(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_narrow_icmp(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_gep_canonicalization(mf, block_idx, idx) {
            return true;
        }
        false
    }
}

/// Helper for combining: collects all instructions that define a given vreg.
pub struct CombineHelper {
    /// Maps each vreg to the index of the instruction that defines it.
    def_map: Vec<(VReg, usize)>,
}

impl CombineHelper {
    pub fn new() -> Self {
        CombineHelper {
            def_map: Vec::new(),
        }
    }

    /// Build a def-use map for a basic block.
    pub fn build(&mut self, block: &crate::global_isel::gisel_machine_ir::GMachineBasicBlock) {
        self.def_map.clear();
        for (idx, inst) in block.instructions.iter().enumerate() {
            if let Some(vreg) = inst.def_vreg() {
                self.def_map.push((vreg, idx));
            }
        }
    }

    /// Find the defining instruction index for a vreg.
    pub fn find_def(&self, vreg: VReg) -> Option<usize> {
        self.def_map
            .iter()
            .find(|(v, _)| *v == vreg)
            .map(|(_, idx)| *idx)
    }

    /// Clear the def map.
    pub fn clear(&mut self) {
        self.def_map.clear();
    }
}

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

// ---------------------------------------------------------------------------
// Additional Combine Patterns — Algebraic Identities and Simplifications
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine x & 0 → 0.
    fn try_combine_and_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_AND {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let op1 = inst.operands[1].as_imm();
        let op2 = inst.operands[2].as_imm();

        if op1 == Some(0) || op2 == Some(0) {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(0)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Combine x | ~0 → ~0.
    fn try_combine_or_all_ones(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_OR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let op1 = inst.operands[1].as_imm();
        let op2 = inst.operands[2].as_imm();

        if op1 == Some(-1) || op2 == Some(-1) {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(-1)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Combine x ^ x → 0.
    fn try_combine_xor_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_XOR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        let op1 = inst.operands[1].as_vreg();
        let op2 = inst.operands[2].as_vreg();

        if op1 == op2 && op1.is_some() {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(0)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Combine G_SHL x, 0 → x (shift by zero is identity).
    fn try_combine_shl_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SHL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        if inst.operands[2].as_imm() == Some(0) {
            let src = inst.operands[1].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }

        false
    }

    /// Combine (x + C1) + C2 → x + (C1 + C2).
    fn try_combine_add_constant_chain(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ADD {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }

        // Check if one operand is a constant and the other is defined by G_ADD with constant.
        let c2 = inst.operands[2].as_imm();
        if c2.is_none() {
            return false;
        }
        let c2_val = c2.unwrap();

        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };

        // Look for the definition of src1.
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ADD
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(c1) = prev.operands[2].as_imm() {
                    let base = prev.operands[1].as_vreg().unwrap_or(0);
                    let new_c = c1.wrapping_add(c2_val);
                    let dst = inst.operands[0].as_vreg().unwrap_or(0);
                    let new_add = GInstruction::with_operands(
                        GOpcode::G_ADD,
                        vec![
                            MOperand::vreg(dst),
                            MOperand::vreg(base),
                            MOperand::imm(new_c),
                        ],
                    );
                    mf.blocks[block_idx].instructions[idx] = new_add;
                    self.combined += 1;
                    return true;
                }
            }
        }

        false
    }

    /// Combine redundant copies: COPY a, b where a == b.
    fn try_combine_redundant_copy(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::COPY {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }

        let dst = inst.operands[0].as_vreg();
        let src = inst.operands[1].as_vreg();

        if dst == src && dst.is_some() {
            // Remove the redundant COPY by replacing it with a nop
            // (replace with a G_CONSTANT 0 that will be cleaned up).
            mf.blocks[block_idx].instructions.remove(idx);
            self.combined += 1;
            return true;
        }

        false
    }
}

// ---------------------------------------------------------------------------
// G_ADD Combines — Identity, Constant Folding, Reassociation
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (add (add x, c1), c2) → (add x, c1+c2).
    fn try_combine_add_add_constant(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ADD {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let c2 = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ADD
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(c1) = prev.operands[2].as_imm() {
                    let base = prev.operands[1].as_vreg().unwrap_or(0);
                    let new_c = c1.wrapping_add(c2);
                    let dst = inst.operands[0].as_vreg().unwrap_or(0);
                    let new_add = GInstruction::with_operands(
                        GOpcode::G_ADD,
                        vec![
                            MOperand::vreg(dst),
                            MOperand::vreg(base),
                            MOperand::imm(new_c),
                        ],
                    );
                    mf.blocks[block_idx].instructions[idx] = new_add;
                    self.combined += 1;
                    return true;
                }
            }
        }
        false
    }

    /// Combine (add (sub x, c1), c2) → (add x, c2-c1).
    fn try_combine_add_sub_constant(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ADD {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let c2 = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_SUB
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(c1) = prev.operands[2].as_imm() {
                    let base = prev.operands[1].as_vreg().unwrap_or(0);
                    let new_c = c2.wrapping_sub(c1);
                    let dst = inst.operands[0].as_vreg().unwrap_or(0);
                    let new_add = GInstruction::with_operands(
                        GOpcode::G_ADD,
                        vec![
                            MOperand::vreg(dst),
                            MOperand::vreg(base),
                            MOperand::imm(new_c),
                        ],
                    );
                    mf.blocks[block_idx].instructions[idx] = new_add;
                    self.combined += 1;
                    return true;
                }
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_SUB Combines — Identity, Self-elimination, Reassociation
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (sub x, 0) → x.
    fn try_combine_sub_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SUB {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        if inst.operands[2].as_imm() == Some(0) {
            let src = inst.operands[1].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (sub (add x, c1), c2) → (add x, c1-c2).
    fn try_combine_sub_add_constant(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SUB {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let c2 = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ADD
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(c1) = prev.operands[2].as_imm() {
                    let base = prev.operands[1].as_vreg().unwrap_or(0);
                    let new_c = c1.wrapping_sub(c2);
                    let dst = inst.operands[0].as_vreg().unwrap_or(0);
                    let new_add = GInstruction::with_operands(
                        GOpcode::G_ADD,
                        vec![
                            MOperand::vreg(dst),
                            MOperand::vreg(base),
                            MOperand::imm(new_c),
                        ],
                    );
                    mf.blocks[block_idx].instructions[idx] = new_add;
                    self.combined += 1;
                    return true;
                }
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_MUL Combines — Zero, Identity, Pow2, Negate
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (mul x, 0) → 0.
    fn try_combine_mul_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_MUL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let op1 = inst.operands[1].as_imm();
        let op2 = inst.operands[2].as_imm();
        if op1 == Some(0) || op2 == Some(0) {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(0)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (mul x, 2^n) → (shl x, n).
    fn try_combine_mul_pow2(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_MUL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let (x, c) = if let Some(c) = inst.operands[1].as_imm() {
            match inst.operands[2].as_vreg() {
                Some(v) => (v, c),
                None => return false,
            }
        } else if let Some(c) = inst.operands[2].as_imm() {
            match inst.operands[1].as_vreg() {
                Some(v) => (v, c),
                None => return false,
            }
        } else {
            return false;
        };
        if c > 0 && (c as u64).is_power_of_two() {
            let shift = c.trailing_zeros() as i64;
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let shl = GInstruction::with_operands(
                GOpcode::G_SHL,
                vec![MOperand::vreg(dst), MOperand::vreg(x), MOperand::imm(shift)],
            );
            mf.blocks[block_idx].instructions[idx] = shl;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (mul x, -1) → (sub 0, x).
    fn try_combine_mul_neg_one(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_MUL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let (x, c) = if inst.operands[1].as_imm() == Some(-1) {
            match inst.operands[2].as_vreg() {
                Some(v) => (v, -1_i64),
                None => return false,
            }
        } else if inst.operands[2].as_imm() == Some(-1) {
            match inst.operands[1].as_vreg() {
                Some(v) => (v, -1_i64),
                None => return false,
            }
        } else {
            return false;
        };
        let dst = inst.operands[0].as_vreg().unwrap_or(0);
        let sub = GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(dst), MOperand::imm(0), MOperand::vreg(x)],
        );
        mf.blocks[block_idx].instructions[idx] = sub;
        self.combined += 1;
        let _ = c;
        return true;
    }
}

// ---------------------------------------------------------------------------
// G_AND Combines — Self, Mask Merging
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (and x, x) → x.
    fn try_combine_and_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_AND {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let op1 = inst.operands[1].as_vreg();
        let op2 = inst.operands[2].as_vreg();
        if op1 == op2 && op1.is_some() {
            let src = op1.unwrap();
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (and (and x, m1), m2) → (and x, m1&m2).
    fn try_combine_and_mask_merge(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_AND {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let m2 = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_AND
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(m1) = prev.operands[2].as_imm() {
                    let base = prev.operands[1].as_vreg().unwrap_or(0);
                    let merged = m1 & m2;
                    let dst = inst.operands[0].as_vreg().unwrap_or(0);
                    let new_and = GInstruction::with_operands(
                        GOpcode::G_AND,
                        vec![
                            MOperand::vreg(dst),
                            MOperand::vreg(base),
                            MOperand::imm(merged),
                        ],
                    );
                    mf.blocks[block_idx].instructions[idx] = new_and;
                    self.combined += 1;
                    return true;
                }
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_OR Combines — Identity, All-Ones, Self
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (or x, 0) → x.
    fn try_combine_or_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_OR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let non_zero = if inst.operands[1].as_imm() == Some(0) {
            inst.operands[2].as_vreg()
        } else if inst.operands[2].as_imm() == Some(0) {
            inst.operands[1].as_vreg()
        } else {
            return false;
        };
        if let Some(src) = non_zero {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (or x, x) → x.
    fn try_combine_or_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_OR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let op1 = inst.operands[1].as_vreg();
        let op2 = inst.operands[2].as_vreg();
        if op1 == op2 && op1.is_some() {
            let src = op1.unwrap();
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_XOR Combines — Identity, Self, Complement
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (xor x, 0) → x.
    fn try_combine_xor_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_XOR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let non_zero = if inst.operands[1].as_imm() == Some(0) {
            inst.operands[2].as_vreg()
        } else if inst.operands[2].as_imm() == Some(0) {
            inst.operands[1].as_vreg()
        } else {
            return false;
        };
        if let Some(src) = non_zero {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (xor x, -1) → (not x) / G_XOR x, -1 (bitwise complement).
    /// This is canonical form: x ^ (-1) is the bitwise NOT of x.
    fn try_combine_xor_neg_one(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_XOR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        // (xor x, -1) is canonical — no transformation needed.
        // This is a recognition pattern that could later feed into lowering.
        let _has_neg_one =
            inst.operands[1].as_imm() == Some(-1) || inst.operands[2].as_imm() == Some(-1);
        false
    }
}

// ---------------------------------------------------------------------------
// Shift Combines — Identity, Overshift, Cascade
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine shift by zero → identity for all shift opcodes.
    fn try_combine_shift_by_zero(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if !matches!(
            inst.opcode,
            GOpcode::G_SHL | GOpcode::G_LSHR | GOpcode::G_ASHR
        ) {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        if inst.operands[2].as_imm() == Some(0) {
            let src = inst.operands[1].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine shift by amount >= bit width → 0 (for shifts) or all-ones (for ASHR).
    fn try_combine_shift_overshift(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if !matches!(
            inst.opcode,
            GOpcode::G_SHL | GOpcode::G_LSHR | GOpcode::G_ASHR
        ) {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        if let Some(amt) = inst.operands[2].as_imm() {
            if amt >= 64 {
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let result = if inst.opcode == GOpcode::G_ASHR {
                    -1_i64 // arithmetic shift right fills with sign bit
                } else {
                    0_i64 // logical shifts produce zero
                };
                let constant = GInstruction::with_operands(
                    GOpcode::G_CONSTANT,
                    vec![MOperand::vreg(dst), MOperand::imm(result)],
                );
                mf.blocks[block_idx].instructions[idx] = constant;
                self.combined += 1;
                return true;
            }
        }
        false
    }

    /// Combine (shl (shl x, a), b) → (shl x, a+b) if a+b < bitwidth.
    fn try_combine_shl_shl(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SHL {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let b = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_SHL
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(a) = prev.operands[2].as_imm() {
                    let total = a + b;
                    if total < 64 {
                        let base = prev.operands[1].as_vreg().unwrap_or(0);
                        let dst = inst.operands[0].as_vreg().unwrap_or(0);
                        let merged = GInstruction::with_operands(
                            GOpcode::G_SHL,
                            vec![
                                MOperand::vreg(dst),
                                MOperand::vreg(base),
                                MOperand::imm(total),
                            ],
                        );
                        mf.blocks[block_idx].instructions[idx] = merged;
                        self.combined += 1;
                        return true;
                    }
                }
            }
        }
        false
    }

    /// Combine (lshr (lshr x, a), b) → (lshr x, a+b).
    fn try_combine_lshr_lshr(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_LSHR {
            return false;
        }
        if inst.operands.len() < 3 {
            return false;
        }
        let b = match inst.operands[2].as_imm() {
            Some(v) => v,
            None => return false,
        };
        let src1 = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_LSHR
                && prev.def_vreg() == Some(src1)
                && prev.operands.len() >= 3
            {
                if let Some(a) = prev.operands[2].as_imm() {
                    let total = a + b;
                    if total < 64 {
                        let base = prev.operands[1].as_vreg().unwrap_or(0);
                        let dst = inst.operands[0].as_vreg().unwrap_or(0);
                        let merged = GInstruction::with_operands(
                            GOpcode::G_LSHR,
                            vec![
                                MOperand::vreg(dst),
                                MOperand::vreg(base),
                                MOperand::imm(total),
                            ],
                        );
                        mf.blocks[block_idx].instructions[idx] = merged;
                        self.combined += 1;
                        return true;
                    }
                }
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// Extension & Truncation Combines
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine zext(zext x) → zext x (fold redundant extensions).
    fn try_combine_zext_zext(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ZEXT {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }
        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ZEXT && prev.def_vreg() == Some(src_vreg) {
                // Fold: zext(zext x) → zext x
                let inner_src = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let new_zext = GInstruction::with_operands(
                    GOpcode::G_ZEXT,
                    vec![MOperand::vreg(dst), MOperand::vreg(inner_src)],
                );
                mf.blocks[block_idx].instructions[idx] = new_zext;
                self.combined += 1;
                return true;
            }
        }
        false
    }

    /// Combine sext(sext x) → sext x.
    fn try_combine_sext_sext(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SEXT {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }
        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_SEXT && prev.def_vreg() == Some(src_vreg) {
                let inner_src = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let new_sext = GInstruction::with_operands(
                    GOpcode::G_SEXT,
                    vec![MOperand::vreg(dst), MOperand::vreg(inner_src)],
                );
                mf.blocks[block_idx].instructions[idx] = new_sext;
                self.combined += 1;
                return true;
            }
        }
        false
    }

    /// Combine anyext(anyext x) → anyext x.
    fn try_combine_anyext_anyext(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ANYEXT {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }
        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode == GOpcode::G_ANYEXT && prev.def_vreg() == Some(src_vreg) {
                let inner_src = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let new_ext = GInstruction::with_operands(
                    GOpcode::G_ANYEXT,
                    vec![MOperand::vreg(dst), MOperand::vreg(inner_src)],
                );
                mf.blocks[block_idx].instructions[idx] = new_ext;
                self.combined += 1;
                return true;
            }
        }
        false
    }

    /// Combine trunc(zext x) → x (truncate of extension cancels).
    fn try_combine_trunc_of_ext(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_TRUNC {
            return false;
        }
        if inst.operands.len() < 2 {
            return false;
        }
        let src_vreg = match inst.operands[1].as_vreg() {
            Some(v) => v,
            None => return false,
        };
        for prev_idx in (0..idx).rev() {
            let prev = &mf.blocks[block_idx].instructions[prev_idx];
            if prev.opcode.is_extension() && prev.def_vreg() == Some(src_vreg) {
                let inner = prev.operands[1].as_vreg().unwrap_or(0);
                let dst = inst.operands[0].as_vreg().unwrap_or(0);
                let copy = GInstruction::with_operands(
                    GOpcode::COPY,
                    vec![MOperand::vreg(dst), MOperand::vreg(inner)],
                );
                mf.blocks[block_idx].instructions[idx] = copy;
                self.combined += 1;
                return true;
            }
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_ICMP Combines — Constant Folding, Identity Comparisons
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Fold icmp with both operands constant.
    fn try_combine_icmp_const_fold(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ICMP {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        let lhs = inst.operands[2].as_imm();
        let rhs = inst.operands[3].as_imm();
        let (lhs, rhs) = match (lhs, rhs) {
            (Some(l), Some(r)) => (l, r),
            _ => return false,
        };
        let pred = inst.operands[1].as_imm().unwrap_or(0);
        // Common predicates: 0=eq, 1=ne, 2=sgt, 3=sge, 4=slt, 5=sle
        let result: bool = match pred {
            0 => lhs == rhs,
            1 => lhs != rhs,
            2 => lhs > rhs,
            3 => lhs >= rhs,
            4 => lhs < rhs,
            5 => lhs <= rhs,
            _ => return false,
        };
        let dst = inst.operands[0].as_vreg().unwrap_or(0);
        let const_val = if result { 1_i64 } else { 0_i64 };
        let constant = GInstruction::with_operands(
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(dst), MOperand::imm(const_val)],
        );
        mf.blocks[block_idx].instructions[idx] = constant;
        self.combined += 1;
        return true;
    }

    /// Combine icmp eq x, x → true.
    fn try_combine_icmp_eq_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ICMP {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        let pred = inst.operands[1].as_imm().unwrap_or(-1);
        if pred != 0 {
            // Only for EQ predicate.
            return false;
        }
        let lhs = inst.operands[2].as_vreg();
        let rhs = inst.operands[3].as_vreg();
        if lhs == rhs && lhs.is_some() {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(1)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine icmp ne x, x → false.
    fn try_combine_icmp_ne_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_ICMP {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        let pred = inst.operands[1].as_imm().unwrap_or(-1);
        if pred != 1 {
            return false;
        }
        let lhs = inst.operands[2].as_vreg();
        let rhs = inst.operands[3].as_vreg();
        if lhs == rhs && lhs.is_some() {
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let constant = GInstruction::with_operands(
                GOpcode::G_CONSTANT,
                vec![MOperand::vreg(dst), MOperand::imm(0)],
            );
            mf.blocks[block_idx].instructions[idx] = constant;
            self.combined += 1;
            return true;
        }
        false
    }
}

// ---------------------------------------------------------------------------
// G_SELECT Combines — True/False/Same-Value Elimination
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Combine (select true, a, b) → a.
    fn try_combine_select_true(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SELECT {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        if inst.operands[1].as_imm() == Some(1) {
            let true_val = inst.operands[2].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(true_val)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (select false, a, b) → b.
    fn try_combine_select_false(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SELECT {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        if inst.operands[1].as_imm() == Some(0) {
            let false_val = inst.operands[3].as_vreg().unwrap_or(0);
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(false_val)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }

    /// Combine (select c, x, x) → x.
    fn try_combine_select_same(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        let inst = &mf.blocks[block_idx].instructions[idx];
        if inst.opcode != GOpcode::G_SELECT {
            return false;
        }
        if inst.operands.len() < 4 {
            return false;
        }
        let t_val = inst.operands[2].as_vreg();
        let f_val = inst.operands[3].as_vreg();
        if t_val == f_val && t_val.is_some() {
            let src = t_val.unwrap();
            let dst = inst.operands[0].as_vreg().unwrap_or(0);
            let copy = GInstruction::with_operands(
                GOpcode::COPY,
                vec![MOperand::vreg(dst), MOperand::vreg(src)],
            );
            mf.blocks[block_idx].instructions[idx] = copy;
            self.combined += 1;
            return true;
        }
        false
    }
}

// ---------------------------------------------------------------------------
// Extended Combine All — Run All New Patterns
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Run all the newly added combine patterns on a single instruction.
    fn combine_instruction_extended(
        &mut self,
        mf: &mut GMachineFunction,
        block_idx: usize,
        idx: usize,
    ) -> bool {
        // ADD patterns
        if self.try_combine_add_add_constant(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_add_sub_constant(mf, block_idx, idx) {
            return true;
        }
        // SUB patterns
        if self.try_combine_sub_zero(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_sub_add_constant(mf, block_idx, idx) {
            return true;
        }
        // MUL patterns
        if self.try_combine_mul_zero(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_mul_pow2(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_mul_neg_one(mf, block_idx, idx) {
            return true;
        }
        // AND patterns
        if self.try_combine_and_same(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_and_mask_merge(mf, block_idx, idx) {
            return true;
        }
        // OR patterns
        if self.try_combine_or_zero(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_or_same(mf, block_idx, idx) {
            return true;
        }
        // XOR patterns
        if self.try_combine_xor_zero(mf, block_idx, idx) {
            return true;
        }
        let _ = self.try_combine_xor_neg_one(mf, block_idx, idx);
        // Shift patterns
        if self.try_combine_shift_by_zero(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_shift_overshift(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_shl_shl(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_lshr_lshr(mf, block_idx, idx) {
            return true;
        }
        // Extension patterns
        if self.try_combine_zext_zext(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_sext_sext(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_anyext_anyext(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_trunc_of_ext(mf, block_idx, idx) {
            return true;
        }
        // ICMP patterns
        if self.try_combine_icmp_const_fold(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_icmp_eq_same(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_icmp_ne_same(mf, block_idx, idx) {
            return true;
        }
        // SELECT patterns
        if self.try_combine_select_true(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_select_false(mf, block_idx, idx) {
            return true;
        }
        if self.try_combine_select_same(mf, block_idx, idx) {
            return true;
        }
        false
    }

    /// Run extended combine on all instructions in the function.
    pub fn combine_extended(&mut self, mf: &mut GMachineFunction) {
        for _ in 0..self.max_iterations {
            self.iterations += 1;
            let mut any_changed = false;
            for block_idx in 0..mf.blocks.len() {
                let mut idx = 0;
                while idx < mf.blocks[block_idx].instruction_count() {
                    let changed = self.combine_instruction_extended(mf, block_idx, idx);
                    if changed {
                        any_changed = true;
                    } else {
                        idx += 1;
                    }
                }
            }
            if !any_changed {
                break;
            }
        }
    }
}

// ---------------------------------------------------------------------------
// New Tests for Extended Combines
// ---------------------------------------------------------------------------

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

    #[test]
    fn test_combine_mul_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        let changed = combiner.try_combine_mul_zero(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_CONSTANT);
        assert_eq!(inst.operands[1].as_imm(), Some(0));
    }

    #[test]
    fn test_combine_mul_pow2() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(8)],
        ));
        let changed = combiner.try_combine_mul_pow2(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_SHL);
    }

    #[test]
    fn test_combine_mul_neg_one() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        let changed = combiner.try_combine_mul_neg_one(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_SUB);
    }

    #[test]
    fn test_combine_sub_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        let changed = combiner.try_combine_sub_zero(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_and_same() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_AND,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(1)],
        ));
        let changed = combiner.try_combine_and_same(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_or_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_OR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        let changed = combiner.try_combine_or_zero(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_or_all_ones() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_OR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        let changed = combiner.try_combine_or_all_ones(&mut mf, 0, 0);
        assert!(changed);
    }

    #[test]
    fn test_combine_xor_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_XOR,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        let changed = combiner.try_combine_xor_zero(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_select_true() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SELECT,
            vec![
                MOperand::vreg(0),
                MOperand::imm(1),
                MOperand::vreg(2),
                MOperand::vreg(3),
            ],
        ));
        let changed = combiner.try_combine_select_true(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_select_same() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SELECT,
            vec![
                MOperand::vreg(0),
                MOperand::vreg(1),
                MOperand::vreg(2),
                MOperand::vreg(2),
            ],
        ));
        let changed = combiner.try_combine_select_same(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_icmp_eq_same() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ICMP,
            vec![
                MOperand::vreg(0),
                MOperand::imm(0),
                MOperand::vreg(1),
                MOperand::vreg(1),
            ],
        ));
        let changed = combiner.try_combine_icmp_eq_same(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_CONSTANT);
        assert_eq!(inst.operands[1].as_imm(), Some(1));
    }

    #[test]
    fn test_combine_shift_by_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SHL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        let changed = combiner.try_combine_shift_by_zero(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_extended_runs() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(0)],
        ));
        combiner.combine_extended(&mut mf);
        assert!(combiner.combined_count() > 0);
    }
}

// ---------------------------------------------------------------------------
// Machine IR Optimization Pass and Dead Code Elimination
// ---------------------------------------------------------------------------

impl GISelCombiner {
    /// Eliminate dead code: remove instructions whose def is never used.
    pub fn eliminate_dead_code(&mut self, mf: &mut GMachineFunction) -> usize {
        let mut removed = 0;

        // Build a use count map.
        let mut use_count: std::collections::HashMap<VReg, usize> =
            std::collections::HashMap::new();

        for block in &mf.blocks {
            for inst in &block.instructions {
                for op in inst.uses() {
                    if let Some(vreg) = op.as_vreg() {
                        *use_count.entry(vreg).or_default() += 1;
                    }
                }
            }
        }

        // Remove instructions whose def is never used.
        for block in &mut mf.blocks {
            let mut i = 0;
            while i < block.instructions.len() {
                let inst = &block.instructions[i];
                if let Some(def) = inst.def_vreg() {
                    let count = use_count.get(&def).copied().unwrap_or(0);
                    if count == 0 && !inst.opcode.is_terminator() && inst.opcode != GOpcode::G_STORE
                    {
                        block.instructions.remove(i);
                        removed += 1;
                        continue;
                    }
                }
                i += 1;
            }
        }

        self.combined += removed;
        removed
    }

    /// Apply common subexpression elimination (CSE) on the machine IR.
    pub fn common_subexpression_elimination(&mut self, mf: &mut GMachineFunction) -> usize {
        let mut eliminated = 0;

        for block in &mut mf.blocks {
            let mut seen: std::collections::HashMap<(GOpcode, Vec<MOperand>), VReg> =
                std::collections::HashMap::new();

            let mut i = 0;
            while i < block.instructions.len() {
                let inst = &block.instructions[i];

                // Only CSE commutative and pure operations.
                if inst.opcode.is_commutative() || inst.opcode == GOpcode::G_CONSTANT {
                    let mut key_operands = inst.uses().to_vec();

                    // Sort operands for commutative ops.
                    if inst.opcode.is_commutative() {
                        key_operands.sort_by_key(|op| match op {
                            MOperand::VReg(v) => *v as i64,
                            MOperand::Imm(v) => *v,
                            _ => 0,
                        });
                    }

                    let key = (inst.opcode, key_operands);

                    if let Some(&existing_dst) = seen.get(&key) {
                        // Replace this instruction with a COPY from the existing result.
                        if let Some(dst) = inst.def_vreg() {
                            let copy = GInstruction::with_operands(
                                GOpcode::COPY,
                                vec![MOperand::vreg(dst), MOperand::vreg(existing_dst)],
                            );
                            block.instructions[i] = copy;
                            eliminated += 1;
                        }
                    } else if let Some(dst) = inst.def_vreg() {
                        seen.insert(key, dst);
                    }
                }

                i += 1;
            }
        }

        self.combined += eliminated;
        eliminated
    }

    /// Run a full optimization pipeline on the machine function.
    pub fn optimize(&mut self, mf: &mut GMachineFunction) -> usize {
        self.combined = 0;

        // Phase 1: Algebraic simplification and constant folding.
        self.combine(mf);

        // Phase 2: Extended combine patterns.
        self.combine_all(mf);

        // Phase 3: Dead code elimination.
        self.eliminate_dead_code(mf);

        // Phase 4: Common subexpression elimination.
        self.common_subexpression_elimination(mf);

        self.combined
    }
}

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

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

    fn make_add_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        // %0 = G_CONSTANT 5
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(1), MOperand::imm(5)],
        ));
        // %2 = G_ADD %1, 0  → should fold to COPY
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(2), MOperand::vreg(1), MOperand::imm(0)],
        ));
        mf
    }

    fn make_mul_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_CONSTANT,
            vec![MOperand::vreg(1), MOperand::imm(42)],
        ));
        // %2 = G_MUL %1, 1 → should fold to COPY
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(2), MOperand::vreg(1), MOperand::imm(1)],
        ));
        mf
    }

    fn make_const_fold_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        // %0 = G_ADD 3, 4 → should fold to G_CONSTANT 7
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::imm(3), MOperand::imm(4)],
        ));
        mf
    }

    fn make_sub_self_mf() -> GMachineFunction {
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        // %0 = G_SUB %1, %1 → should fold to G_CONSTANT 0
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(1)],
        ));
        mf
    }

    #[test]
    fn test_combiner_new() {
        let combiner = GISelCombiner::new();
        assert_eq!(combiner.combined_count(), 0);
        assert_eq!(combiner.iterations(), 0);
        assert_eq!(combiner.max_iterations(), 8);
    }

    #[test]
    fn test_combiner_default() {
        let combiner = GISelCombiner::default();
        assert_eq!(combiner.combined_count(), 0);
    }

    #[test]
    fn test_combine_add_zero() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_add_mf();
        let changed = combiner.try_combine_add_zero(&mut mf, 0, 1);
        assert!(changed);
        // The instruction at index 1 should now be a COPY.
        let inst = &mf.blocks[0].instructions[1];
        assert_eq!(inst.opcode, GOpcode::COPY);
        assert_eq!(combiner.combined_count(), 1);
    }

    #[test]
    fn test_combine_add_zero_not_applicable() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(5)],
        ));
        // rhs is 5, not 0 → should not change.
        let changed = combiner.try_combine_add_zero(&mut mf, 0, 0);
        assert!(!changed);
    }

    #[test]
    fn test_combine_mul_one() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_mul_mf();
        let changed = combiner.try_combine_mul_one(&mut mf, 0, 1);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[1];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_mul_one_not_applicable() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_MUL,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(2)],
        ));
        let changed = combiner.try_combine_mul_one(&mut mf, 0, 0);
        assert!(!changed);
    }

    #[test]
    fn test_combine_and_all_ones() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_AND,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(-1)],
        ));
        let changed = combiner.try_combine_and_all_ones(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::COPY);
    }

    #[test]
    fn test_combine_constant_fold_add() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_const_fold_mf();
        let changed = combiner.try_combine_constant_fold(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_CONSTANT);
        assert_eq!(inst.operands[1].as_imm(), Some(7));
    }

    #[test]
    fn test_combine_constant_fold_sub() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(0), MOperand::imm(10), MOperand::imm(3)],
        ));
        let changed = combiner.try_combine_constant_fold(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.operands[1].as_imm(), Some(7));
    }

    #[test]
    fn test_combine_constant_fold_not_applicable() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::imm(5)],
        ));
        // vreg + constant → can't fold.
        let changed = combiner.try_combine_constant_fold(&mut mf, 0, 0);
        assert!(!changed);
    }

    #[test]
    fn test_combine_sub_self() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_sub_self_mf();
        let changed = combiner.try_combine_sub_self(&mut mf, 0, 0);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[0];
        assert_eq!(inst.opcode, GOpcode::G_CONSTANT);
        assert_eq!(inst.operands[1].as_imm(), Some(0));
    }

    #[test]
    fn test_combine_sub_self_not_applicable() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_SUB,
            vec![MOperand::vreg(0), MOperand::vreg(1), MOperand::vreg(2)],
        ));
        // Different vregs → no fold.
        let changed = combiner.try_combine_sub_self(&mut mf, 0, 0);
        assert!(!changed);
    }

    #[test]
    fn test_combine_on_function() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_add_mf();
        combiner.combine(&mut mf);
        assert!(combiner.combined_count() >= 1);
        assert!(combiner.iterations() >= 1);
    }

    #[test]
    fn test_reset_counters() {
        let mut combiner = GISelCombiner::new();
        let mut mf = make_add_mf();
        combiner.combine(&mut mf);
        assert!(combiner.combined_count() > 0);
        combiner.reset();
        assert_eq!(combiner.combined_count(), 0);
        assert_eq!(combiner.iterations(), 0);
    }

    #[test]
    fn test_combine_copy_propagation() {
        let mut combiner = GISelCombiner::new();
        let mut mf = GMachineFunction::new("test".to_string());
        let entry = mf.push_block("entry".to_string());
        // %0 = COPY %1
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::COPY,
            vec![MOperand::vreg(0), MOperand::vreg(1)],
        ));
        // %2 = G_ADD %0, %3 → should become %2 = G_ADD %1, %3
        mf.blocks[entry].push_instruction(GInstruction::with_operands(
            GOpcode::G_ADD,
            vec![MOperand::vreg(2), MOperand::vreg(0), MOperand::vreg(3)],
        ));
        let changed = combiner.try_combine_copy_propagation(&mut mf, 0, 1);
        assert!(changed);
        let inst = &mf.blocks[0].instructions[1];
        assert_eq!(inst.operands[1].as_vreg(), Some(1)); // replaced %0 with %1
    }
}