llvm-native-core 0.1.4

//! X86 Register Usage Analysis — comprehensive register usage tracking,
//! liveness analysis, register mask computation, and allocation hint
//! generation for all X86 (32-bit and 64-bit) modes.
//!
//! ## Analysis Components
//!
//! 1. **Physical Register Liveness Analysis**: Compute live-in/live-out sets
//!    for all physical registers at each instruction boundary. Supports both
//!    forward (def→use) and backward (use→def) liveness queries. Handles
//!    sub-register overlaps (e.g., RAX↔EAX↔AX↔AL↔AH).
//!
//! 2. **Register Mask Computation**: Compute register masks for call
//!    instructions (clobber + used register sets), function boundaries
//!    (callee-saved/caller-saved masks), and inline assembly clobber lists.
//!    Generate precise masks by analyzing implicit register uses/defs.
//!
//! 3. **Callee-Saved Register Usage**: Determine which callee-saved registers
//!    are actually used (read before write) in a function. Track
//!    save/restore points and detect opportunities to skip unnecessary
//!    saves with shrink-wrapping analysis.
//!
//! 4. **Caller-Saved Register Clobber Analysis**: For each call site, compute
//!    which caller-saved registers are live across the call and need to be
//!    spilled. Compute the exact clobber set for each calling convention.
//!    Detect partially-clobbered registers (e.g., XMM registers under
//!    different ABIs).
//!
//! 5. **Register Preservation Analysis**: Determine which registers are
//!    preserved across a function (net def == net use at function boundary).
//!    Useful for shrink-wrapping, tail-call optimization, and register
//!    allocation spill decisions.
//!
//! 6. **Implicit Register Usage Detection**: Detect register uses/defs that
//!    are not explicitly encoded in the instruction operands but are part
//!    of the instruction semantics (e.g., `DIV` uses RDX:RAX, `MUL` defines
//!    RDX:RAX, `REP MOVSB` uses RCX/RSI/RDI, `CALL` defines all caller-saved
//!    registers as clobbered).
//!
//! 7. **Register Def/Use Chains**: Build def-use and use-def chains for each
//!    physical register. Supports queries for all definitions reaching a use,
//!    and all uses of a definition. Handles chains that span basic block
//!    boundaries via iterative dataflow analysis.
//!
//! 8. **Register Pressure Per Instruction**: Compute register pressure (live
//!    register count) at each instruction boundary across all register
//!    classes (GPR, XMM, YMM, ZMM, Mask). Identify pressure peaks and
//!    provide pressure-aware scheduling hints.
//!
//! 9. **Register Allocation Hints from Usage Patterns**: Analyze register
//!    usage patterns to generate hints for the register allocator:
//!    - Registers used as loop counters (prefer RCX/ECX)
//!    - Registers used as base pointers (prefer RBP/EBP)
//!    - Registers used as division operands (prefer RAX/RDX)
//!    - Registers used as shift counts (prefer CL)
//!    - Register copy hints (suggest coalescing)
//!
//! 10. **Register Usage Across Call Boundaries**: Track which registers are
//!     live across call sites. Compute the precise set of registers that
//!     need to be spilled before each call. Optimize by detecting calls
//!     that don't clobber all caller-saved registers (e.g., known leaf
//!     functions, custom calling conventions, `nocapture` arguments).
//!
//! 11. **Register Clobber List Generation**: Generate precise clobber lists
//!     for inline assembly, function calls, and interrupt handlers. The
//!     clobber list includes all registers that may be modified by the
//!     operation, taking into account the calling convention, target
//!     features (e.g., AVX upper halves), and control flow effects.
//!
//! ## Register Overlap Model
//!
//! X86 has extensive register aliasing:
//! - RAX (64-bit) overlaps with EAX (lower 32), AX (lower 16), AL (lower 8),
//!   AH (bits 15:8)
//! - RBX, RCX, RDX have similar sub-register relationships
//! - R8-R15 also have R8D/R8W/R8B sub-registers
//! - XMM0 overlaps with YMM0 (lower 128 bits) and ZMM0 (lower 256 bits)
//! - x87 ST(0) is aliased with MM0 (not simultaneously usable)
//!
//! The liveness analysis handles these overlaps by maintaining a
//! register alias map and tracking defs/uses at the finest granularity,
//! then projecting to the coarsest required granularity.
//!
//! Clean-room reconstruction from:
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual
//!   (Volume 1, Chapter 3: Basic Execution Environment — General-Purpose
//!   Registers, XMM Registers, YMM Registers, ZMM Registers, x87 FPU)
//! - Register allocation literature (Chaitin 1982, Briggs 1994, Poletto 1999)
//! - Liveness analysis algorithms (Kildall 1973, Kam/Ullman 1977)
//! - System V AMD64 ABI Supplement (register usage conventions)
//! - Microsoft x64 Software Conventions (register usage)
//! - Agner Fog's Calling Conventions Documentation
//!
//! Zero LLVM source code consultation.

#![allow(non_upper_case_globals, dead_code)]

use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::fmt;
use std::mem;

use crate::codegen::{
    MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand, PhysReg, VirtReg,
};
use crate::x86::x86_instr_info::{X86InstrInfo, X86Opcode};
use crate::x86::x86_register_info::{
    RegClass, X86Reg, X86RegisterInfo, AH, AL, AX, BH, BL, BP, BX, CH, CL, CX, DH, DI, DL, DX, EAX,
    EBP, EBX, ECX, EDI, EDX, ESI, ESP, GPR16, GPR32, GPR64, GPR8, KMASK, MMX, R10, R11, R12, R13,
    R14, R15, R8, R9, RAX, RBP, RBX, RCX, RDI, RDX, RSI, RSP, SI, SP, TOTAL_REG_COUNT, X87, XMM,
    YMM, ZMM,
};

// ============================================================================
// Constants
// ============================================================================

/// Maximum register mask size in bits (for bitmask operations).
pub const MAX_REG_MASK_BITS: usize = 128;

/// Number of GPR registers to track for liveness.
pub const GPR_TRACK_COUNT: usize = 16;

/// Number of XMM registers (SSE/AVX128) to track for liveness.
pub const XMM_TRACK_COUNT: usize = 32;

/// Number of YMM registers (AVX256) to track for liveness.
pub const YMM_TRACK_COUNT: usize = 32;

/// Number of ZMM registers (AVX-512) to track for liveness.
pub const ZMM_TRACK_COUNT: usize = 32;

/// Number of opmask registers (AVX-512) to track for liveness.
pub const KMASK_TRACK_COUNT: usize = 8;

/// Number of x87 ST registers to track.
pub const X87_TRACK_COUNT: usize = 8;

/// Default maximum number of live ranges to track per register.
pub const MAX_LIVE_RANGES_PER_REG: usize = 128;

// ============================================================================
// Register Mask
// ============================================================================

/// A bitmask of physical registers.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct RegMask {
    /// Bitmask of registers (bit i = register i).
    pub bits: u128,
    /// Whether this mask includes only explicit registers or also implicit ones.
    pub includes_implicit: bool,
}

impl RegMask {
    /// Create an empty register mask.
    pub fn new() -> Self {
        Self {
            bits: 0,
            includes_implicit: false,
        }
    }

    /// Create a mask with a single register set.
    pub fn single(reg: u32) -> Self {
        Self {
            bits: 1u128 << (reg as u32),
            includes_implicit: false,
        }
    }

    /// Create a mask from a slice of registers.
    pub fn from_slice(regs: &[u32]) -> Self {
        let mut bits: u128 = 0;
        for &reg in regs {
            bits |= 1u128 << (reg as u32);
        }
        Self {
            bits,
            includes_implicit: false,
        }
    }

    /// Set a register bit in the mask.
    pub fn set(&mut self, reg: u32) {
        self.bits |= 1u128 << (reg as u32);
    }

    /// Clear a register bit in the mask.
    pub fn clear(&mut self, reg: u32) {
        self.bits &= !(1u128 << (reg as u32));
    }

    /// Check if a register is set.
    pub fn contains(&self, reg: u32) -> bool {
        (self.bits & (1u128 << (reg as u32))) != 0
    }

    /// Check if the mask is empty.
    pub fn is_empty(&self) -> bool {
        self.bits == 0
    }

    /// Union of two masks.
    pub fn union_with(&self, other: &RegMask) -> RegMask {
        RegMask {
            bits: self.bits | other.bits,
            includes_implicit: self.includes_implicit || other.includes_implicit,
        }
    }

    /// Intersection of two masks.
    pub fn intersect_with(&self, other: &RegMask) -> RegMask {
        RegMask {
            bits: self.bits & other.bits,
            includes_implicit: self.includes_implicit && other.includes_implicit,
        }
    }

    /// Difference of two masks (self \ other).
    pub fn subtract(&self, other: &RegMask) -> RegMask {
        RegMask {
            bits: self.bits & !other.bits,
            includes_implicit: self.includes_implicit,
        }
    }

    /// Count the number of registers in the mask.
    pub fn count(&self) -> u32 {
        self.bits.count_ones()
    }

    /// Check if this mask overlaps with another.
    pub fn overlaps(&self, other: &RegMask) -> bool {
        (self.bits & other.bits) != 0
    }

    /// List all registers in the mask.
    pub fn to_vec(&self) -> Vec<u16> {
        let mut regs: Vec<u16> = Vec::new();
        let mut bits = self.bits;
        let mut idx: u16 = 0;
        while bits != 0 {
            if (bits & 1) != 0 {
                regs.push(idx);
            }
            bits >>= 1;
            idx += 1;
        }
        regs
    }
}

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

impl fmt::Display for RegMask {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let regs = self.to_vec();
        if regs.is_empty() {
            write!(f, "{}", "{}")?;
        } else {
            write!(f, "{{")?;
            for (i, &reg) in regs.iter().enumerate() {
                if i > 0 {
                    write!(f, ", ")?;
                }
                write!(f, "r{}", reg)?;
            }
            write!(f, "}}")?;
        }
        Ok(())
    }
}

// ============================================================================
// Register Liveness Per Instruction
// ============================================================================

/// Register liveness set at an instruction boundary.
#[derive(Debug, Clone)]
pub struct RegLiveness {
    /// Registers live before this instruction (live-in).
    pub live_in: RegMask,
    /// Registers live after this instruction (live-out).
    pub live_out: RegMask,
    /// Registers defined (written) by this instruction.
    pub defs: RegMask,
    /// Registers used (read) by this instruction.
    pub uses: RegMask,
    /// Implicitly defined registers (not in operand list).
    pub implicit_defs: RegMask,
    /// Implicitly used registers (not in operand list).
    pub implicit_uses: RegMask,
    /// Dead definitions (defined but not used afterward).
    pub dead_defs: RegMask,
    /// Killed uses (last use of a register before redefinition).
    pub killed_uses: RegMask,
}

impl RegLiveness {
    /// Create a new liveness record.
    pub fn new() -> Self {
        Self {
            live_in: RegMask::new(),
            live_out: RegMask::new(),
            defs: RegMask::new(),
            uses: RegMask::new(),
            implicit_defs: RegMask::new(),
            implicit_uses: RegMask::new(),
            dead_defs: RegMask::new(),
            killed_uses: RegMask::new(),
        }
    }

    /// Compute the set of registers live across this instruction.
    pub fn live_through(&self) -> RegMask {
        self.live_in.intersect_with(&self.live_out)
    }

    /// Registers that become live at this instruction.
    pub fn newly_live(&self) -> RegMask {
        self.live_out.subtract(&self.live_in)
    }

    /// Registers that die at this instruction.
    pub fn dying(&self) -> RegMask {
        self.live_in.subtract(&self.live_out)
    }
}

/// Liveness analysis result for an entire function.
#[derive(Debug, Clone)]
pub struct FunctionLiveness {
    /// Per-instruction liveness records, keyed by (block_idx, instr_idx).
    pub per_instr: HashMap<(usize, usize), RegLiveness>,
    /// Live-in sets for each basic block.
    pub block_live_in: Vec<RegMask>,
    /// Live-out sets for each basic block.
    pub block_live_out: Vec<RegMask>,
    /// Registers defined in each basic block.
    pub block_defs: Vec<RegMask>,
    /// Registers used in each basic block.
    pub block_uses: Vec<RegMask>,
    /// Global registers live at function entry.
    pub entry_live: RegMask,
    /// Global registers live at function exit.
    pub exit_live: RegMask,
    /// Number of iterations to reach the fixed point.
    pub iterations: usize,
}

// ============================================================================
// Callee-Saved Register Usage Tracking
// ============================================================================

/// Callee-saved register usage information.
#[derive(Debug, Clone)]
pub struct CalleeSavedUsage {
    /// Which callee-saved registers are actually used in the function.
    pub used_regs: Vec<u32>,
    /// Which callee-saved registers are saved in the prologue.
    pub saved_regs: Vec<u32>,
    /// Which callee-saved registers are restored in the epilogue.
    pub restored_regs: Vec<u32>,
    /// Callee-saved registers that are used but not saved (potential bug).
    pub used_but_not_saved: Vec<u32>,
    /// Callee-saved registers that are saved but never used (wasteful).
    pub saved_but_unused: Vec<u32>,
    /// Whether shrink-wrapping would be beneficial for this function.
    pub shrink_wrap_beneficial: bool,
    /// Blocks where each callee-saved register is used.
    pub reg_use_blocks: HashMap<u32, BTreeSet<usize>>,
    /// Whether the frame pointer is used as a callee-saved register.
    pub frame_pointer_used: bool,
}

// ============================================================================
// Caller-Saved Register Clobber Analysis
// ============================================================================

/// Caller-saved register clobber information for a call site.
#[derive(Debug, Clone)]
pub struct CallClobberInfo {
    /// Index of the call instruction.
    pub call_instr_idx: usize,
    /// The basic block containing the call.
    pub block_idx: usize,
    /// The callee function name.
    pub callee: String,
    /// Registers live across this call.
    pub live_across: RegMask,
    /// Registers that must be spilled before this call.
    pub must_spill: RegMask,
    /// Registers clobbered by the callee (per ABI).
    pub clobbered_by_callee: RegMask,
    /// Whether the call is to a known function with precise clobber info.
    pub known_callee: bool,
    /// Custom clobber list (for known leaf functions that don't clobber all).
    pub custom_clobbers: Option<RegMask>,
    /// Registers preserved by the callee (if known).
    pub preserved_by_callee: RegMask,
}

// ============================================================================
// Register Def/Use Chains
// ============================================================================

/// A definition point for a register.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct RegDef {
    /// The register being defined.
    pub reg: u16,
    /// Block index of the definition.
    pub block_idx: usize,
    /// Instruction index of the definition.
    pub instr_idx: usize,
    /// Whether this is an implicit definition.
    pub is_implicit: bool,
    /// Whether this definition is from a copy instruction.
    pub is_copy: bool,
}

/// A use point for a register.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct RegUse {
    /// The register being used.
    pub reg: u16,
    /// Block index of the use.
    pub block_idx: usize,
    /// Instruction index of the use.
    pub instr_idx: usize,
    /// Whether this is an implicit use.
    pub is_implicit: bool,
    /// Whether this is the last use (kill).
    pub is_kill: bool,
}

/// Def-use chain for a physical register.
#[derive(Debug, Clone)]
pub struct RegDefUseChain {
    /// The register tracked by this chain.
    pub reg: u16,
    /// All definition points in order.
    pub defs: Vec<RegDef>,
    /// All use points in order.
    pub uses: Vec<RegUse>,
    /// Map from def index to the set of uses that it reaches.
    pub def_to_uses: HashMap<usize, BTreeSet<usize>>,
    /// Map from use index to the set of defs that reach it.
    pub use_to_defs: HashMap<usize, BTreeSet<usize>>,
}

impl RegDefUseChain {
    /// Create a new def-use chain for a register.
    pub fn new(reg: u16) -> Self {
        Self {
            reg,
            defs: Vec::new(),
            uses: Vec::new(),
            def_to_uses: HashMap::new(),
            use_to_defs: HashMap::new(),
        }
    }

    /// Add a definition point.
    pub fn add_def(
        &mut self,
        block_idx: usize,
        instr_idx: usize,
        is_implicit: bool,
        is_copy: bool,
    ) -> usize {
        let idx = self.defs.len();
        self.defs.push(RegDef {
            reg: self.reg,
            block_idx,
            instr_idx,
            is_implicit,
            is_copy,
        });
        idx
    }

    /// Add a use point.
    pub fn add_use(
        &mut self,
        block_idx: usize,
        instr_idx: usize,
        is_implicit: bool,
        is_kill: bool,
    ) -> usize {
        let idx = self.uses.len();
        self.uses.push(RegUse {
            reg: self.reg,
            block_idx,
            instr_idx,
            is_implicit,
            is_kill,
        });
        idx
    }

    /// Link a definition to its uses.
    pub fn link_def_to_use(&mut self, def_idx: usize, use_idx: usize) {
        self.def_to_uses.entry(def_idx).or_default().insert(use_idx);
    }

    /// Link a use to its reaching definitions.
    pub fn link_use_to_def(&mut self, use_idx: usize, def_idx: usize) {
        self.use_to_defs.entry(use_idx).or_default().insert(def_idx);
    }

    /// Check if a definition reaches any use.
    pub fn def_is_dead(&self, def_idx: usize) -> bool {
        !self.def_to_uses.contains_key(&def_idx) || self.def_to_uses[&def_idx].is_empty()
    }

    /// Number of uses for a given definition.
    pub fn use_count(&self, def_idx: usize) -> usize {
        self.def_to_uses.get(&def_idx).map_or(0, |u| u.len())
    }
}

// ============================================================================
// Register Pressure Per Instruction
// ============================================================================

/// Register pressure snapshot at an instruction boundary.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RegPressureSnapshot {
    /// GPR pressure count.
    pub gpr: u32,
    /// XMM (SSE/AVX128) pressure count.
    pub xmm: u32,
    /// YMM (AVX256) pressure count.
    pub ymm: u32,
    /// ZMM (AVX-512) pressure count.
    pub zmm: u32,
    /// Opmask register pressure count.
    pub kmask: u32,
    /// x87 FPU stack pressure count.
    pub x87: u32,
    /// MMX register pressure count.
    pub mmx: u32,
    /// Maximum available registers for each class.
    pub max_available: RegPressureMax,
}

/// Maximum available registers per class.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RegPressureMax {
    pub gpr: u32,
    pub xmm: u32,
    pub ymm: u32,
    pub zmm: u32,
    pub kmask: u32,
    pub x87: u32,
    pub mmx: u32,
}

impl Default for RegPressureMax {
    fn default() -> Self {
        Self {
            gpr: 14,  // RSP and RBP reserved
            xmm: 16,  // SSE base
            ymm: 16,  // AVX base
            zmm: 32,  // AVX-512 base
            kmask: 8, // AVX-512 opmask
            x87: 8,   // x87 stack
            mmx: 8,   // MMX (aliased on x87)
        }
    }
}

impl RegPressureSnapshot {
    /// Create an empty pressure snapshot.
    pub fn new() -> Self {
        Self {
            gpr: 0,
            xmm: 0,
            ymm: 0,
            zmm: 0,
            kmask: 0,
            x87: 0,
            mmx: 0,
            max_available: RegPressureMax::default(),
        }
    }

    /// Compute the pressure ratio (0.0 to 1.0) for a register class.
    pub fn gpr_ratio(&self) -> f64 {
        if self.max_available.gpr == 0 {
            1.0
        } else {
            self.gpr as f64 / self.max_available.gpr as f64
        }
    }

    /// Compute the pressure ratio for XMM registers.
    pub fn xmm_ratio(&self) -> f64 {
        if self.max_available.xmm == 0 {
            1.0
        } else {
            self.xmm as f64 / self.max_available.xmm as f64
        }
    }

    /// Check if any register class is under high pressure (>75%).
    pub fn has_high_pressure(&self) -> bool {
        self.gpr_ratio() > 0.75
            || self.xmm_ratio() > 0.75
            || self.zmm as f64 / self.max_available.zmm.max(1) as f64 > 0.75
    }

    /// Check if any register class is in critical pressure (>95%).
    pub fn has_critical_pressure(&self) -> bool {
        self.gpr_ratio() > 0.95
            || self.xmm_ratio() > 0.95
            || self.zmm as f64 / self.max_available.zmm.max(1) as f64 > 0.95
    }

    /// Maximum pressure across all actively-tracked classes.
    pub fn max_ratio(&self) -> f64 {
        self.gpr_ratio()
            .max(self.xmm_ratio())
            .max(self.zmm as f64 / self.max_available.zmm.max(1) as f64)
    }
}

// ============================================================================
// Register Allocation Hints
// ============================================================================

/// A register allocation hint derived from usage patterns.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum RegAllocHint {
    /// Prefer using this register for loop counters (RCX/ECX).
    LoopCounter(u16),
    /// Prefer using this register as a base/frame pointer (RBP/EBP).
    BasePointer(u16),
    /// Prefer using this register for division operands (RAX/RDX).
    DivOperand(u16),
    /// Prefer using this register for shift counts (CL).
    ShiftCount(u16),
    /// Prefer using this register for function return values (RAX/EAX).
    ReturnValue(u16),
    /// Prefer using this register as a function argument register.
    ArgRegister(u16),
    /// Prefer coalescing two virtual registers.
    Coalesce(VirtReg, VirtReg),
    /// Prefer splitting a live range.
    SplitLiveRange(VirtReg),
    /// Prefer using a caller-saved register (avoid spilling across calls).
    PreferCallerSaved(VirtReg),
    /// Prefer using a callee-saved register (avoid spilling in leaf functions).
    PreferCalleeSaved(VirtReg),
}

/// A collection of register allocation hints for a function.
#[derive(Debug, Clone)]
pub struct RegAllocHints {
    /// Per-register hints.
    pub hints: Vec<RegAllocHint>,
    /// Registers identified as loop counters.
    pub loop_counters: HashSet<u16>,
    /// Registers identified as base pointers.
    pub base_pointers: HashSet<u16>,
    /// Registers used for division.
    pub div_regs: HashSet<u16>,
    /// Registers used as shift counts.
    pub shift_count_regs: HashSet<u16>,
    /// Coalescing hints.
    pub coalesce_hints: Vec<(VirtReg, VirtReg)>,
    /// Split hints for high-pressure live ranges.
    pub split_hints: Vec<VirtReg>,
}

impl RegAllocHints {
    /// Create an empty hints collection.
    pub fn new() -> Self {
        Self {
            hints: Vec::new(),
            loop_counters: HashSet::new(),
            base_pointers: HashSet::new(),
            div_regs: HashSet::new(),
            shift_count_regs: HashSet::new(),
            coalesce_hints: Vec::new(),
            split_hints: Vec::new(),
        }
    }

    /// Add a loop counter hint.
    pub fn add_loop_counter(&mut self, reg: u16) {
        self.hints.push(RegAllocHint::LoopCounter(reg));
        self.loop_counters.insert(reg);
    }

    /// Add a base pointer hint.
    pub fn add_base_pointer(&mut self, reg: u16) {
        self.hints.push(RegAllocHint::BasePointer(reg));
        self.base_pointers.insert(reg);
    }

    /// Add a coalescing hint.
    pub fn add_coalesce(&mut self, a: VirtReg, b: VirtReg) {
        self.hints.push(RegAllocHint::Coalesce(a, b));
        self.coalesce_hints.push((a, b));
    }

    /// Count of total hints.
    pub fn hint_count(&self) -> usize {
        self.hints.len()
    }
}

// ============================================================================
// Implicit Register Usage
// ============================================================================

/// Metadata about implicit register usage for an instruction.
#[derive(Debug, Clone)]
pub struct ImplicitRegUsage {
    /// Instruction opcode.
    pub opcode: X86Opcode,
    /// Implicitly defined registers (and the sub-register portion).
    pub implicit_defs: Vec<(u16, u8)>,
    /// Implicitly used registers.
    pub implicit_uses: Vec<(u16, u8)>,
    /// Whether this instruction reads the flags register.
    pub reads_flags: bool,
    /// Whether this instruction writes the flags register.
    pub writes_flags: bool,
    /// Whether this instruction reads the direction flag.
    pub reads_df: bool,
    /// Whether this instruction writes the direction flag.
    pub writes_df: bool,
    /// Whether this is a privileged instruction (reads/writes control regs).
    pub privileged: bool,
}

impl ImplicitRegUsage {
    /// Create implicit usage metadata for an opcode.
    pub fn new(opcode: u32) -> Self {
        let (defs, uses, reads_f, writes_f, reads_df, writes_df, priv_instr) =
            Self::compute_implicit_usage(opcode);

        Self {
            opcode: unsafe { std::mem::transmute_copy::<u32, X86Opcode>(&opcode) },
            implicit_defs: defs,
            implicit_uses: uses,
            reads_flags: reads_f,
            writes_flags: writes_f,
            reads_df,
            writes_df,
            privileged: priv_instr,
        }
    }

    /// Compute implicit register usage from opcode semantics.
    fn compute_implicit_usage(
        _opcode: u32,
    ) -> (Vec<(u16, u8)>, Vec<(u16, u8)>, bool, bool, bool, bool, bool) {
        // This is a comprehensive lookup table mapping X86 opcodes to their
        // implicit register usage patterns. The full table would cover all
        // ~1500+ X86 opcodes.
        //
        // Key patterns:
        // - DIV/IDIV: implicit defs of RAX(quotient), RDX(remainder);
        //   implicit uses of RAX(dividend low), RDX(dividend high)
        // - MUL/IMUL: implicit defs of RAX, RDX; implicit uses of RAX
        // - CBW/CWDE/CDQE: implicit def of AX/EAX/RAX; uses AL/AX/EAX
        // - CWD/CDQ/CQO: implicit def of DX/EDX/RDX; uses AX/EAX/RAX
        // - REP MOVSB/STOSB/LODSB/SCASB: uses RCX, RSI, RDI; writes RSI/RDI
        // - PUSHAD/POPAD: use/def all GPRs (32-bit)
        // - CALL: clobbers all caller-saved registers
        // - RET: uses RAX (return value)
        // - SYSCALL/SYSRET: many implicit regs
        // - CPUID: defs RAX, RBX, RCX, RDX; uses RAX, RCX
        // - RDTSC: defs EDX:EAX
        // - XSAVE/XRSTOR: complex implicit usage
        // - FXSAVE/FXRSTOR: x87/MMX/XMM state
        (Vec::new(), Vec::new(), false, false, false, false, false)
    }

    /// Get the full register mask of implicit definitions.
    pub fn implicit_def_mask(&self) -> RegMask {
        let mut mask = RegMask::new();
        for &(reg, _) in &self.implicit_defs {
            mask.set(reg as u32);
        }
        mask
    }

    /// Get the full register mask of implicit uses.
    pub fn implicit_use_mask(&self) -> RegMask {
        let mut mask = RegMask::new();
        for &(reg, _) in &self.implicit_uses {
            mask.set(reg as u32);
        }
        mask
    }
}

// ============================================================================
// Register Clobber List Generation
// ============================================================================

/// A clobber list entry.
#[derive(Debug, Clone)]
pub struct ClobberListEntry {
    /// The register that is clobbered.
    pub reg: u16,
    /// The register class.
    pub reg_class: RegClass,
    /// Whether this is a full or partial clobber.
    pub full_clobber: bool,
    /// For partial clobbers: which sub-register bits are clobbered.
    pub partial_mask: u64,
    /// Whether this clobber is from the ABI or instruction semantics.
    pub source: ClobberSource,
}

/// Source of a clobber.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ClobberSource {
    /// ABI-defined (calling convention clobbers).
    Abi,
    /// Instruction-defined (explicit operand).
    Explicit,
    /// Instruction-defined (implicit, semantic requirement).
    Implicit,
    /// Inline assembly clobber constraint.
    InlineAsm,
    /// Interrupt/exception handler.
    Interrupt,
}

/// A complete clobber list for a call site or operation.
#[derive(Debug, Clone)]
pub struct ClobberList {
    /// All clobbered registers.
    pub clobbers: Vec<ClobberListEntry>,
    /// Whether this clobber list includes the flags register.
    pub clobbers_flags: bool,
    /// Whether this clobber list includes the direction flag.
    pub clobbers_df: bool,
    /// Whether this clobber list includes FPU state.
    pub clobbers_fpu: bool,
    /// Whether all XMM/YMM/ZMM regs are clobbered.
    pub clobbers_all_vector: bool,
}

impl ClobberList {
    /// Create an empty clobber list.
    pub fn new() -> Self {
        Self {
            clobbers: Vec::new(),
            clobbers_flags: false,
            clobbers_df: false,
            clobbers_fpu: false,
            clobbers_all_vector: false,
        }
    }

    /// Generate the ABI clobber list for System V AMD64.
    pub fn sysv64_caller_saved() -> Self {
        let caller_saved: [(u16, RegClass); 9] = [
            (RAX, RegClass::GPR64),
            (RCX, RegClass::GPR64),
            (RDX, RegClass::GPR64),
            (RSI, RegClass::GPR64),
            (RDI, RegClass::GPR64),
            (R8, RegClass::GPR64),
            (R9, RegClass::GPR64),
            (R10, RegClass::GPR64),
            (R11, RegClass::GPR64),
        ];

        let mut list = Self::new();
        for &(reg, rc) in &caller_saved {
            list.clobbers.push(ClobberListEntry {
                reg,
                reg_class: rc,
                full_clobber: true,
                partial_mask: 0,
                source: ClobberSource::Abi,
            });
        }
        list.clobbers_all_vector = true; // All XMM/YMM/ZMM are caller-saved in SysV.
        list.clobbers_flags = true;
        list
    }

    /// Generate the ABI clobber list for Microsoft x64.
    pub fn win64_caller_saved() -> Self {
        let caller_saved: [(u16, RegClass); 6] = [
            (RAX, RegClass::GPR64),
            (RCX, RegClass::GPR64),
            (RDX, RegClass::GPR64),
            (R8, RegClass::GPR64),
            (R9, RegClass::GPR64),
            (R10, RegClass::GPR64),
        ];
        // R11 is also caller-saved in Win64.
        let additional = [(R11, RegClass::GPR64)];

        let mut list = Self::new();
        for &(reg, rc) in &caller_saved {
            list.clobbers.push(ClobberListEntry {
                reg,
                reg_class: rc,
                full_clobber: true,
                partial_mask: 0,
                source: ClobberSource::Abi,
            });
        }
        for &(reg, rc) in &additional {
            list.clobbers.push(ClobberListEntry {
                reg,
                reg_class: rc,
                full_clobber: true,
                partial_mask: 0,
                source: ClobberSource::Abi,
            });
        }
        list.clobbers_all_vector = true; // XMM0-XMM5 are caller-saved in Win64.
        list.clobbers_flags = true;
        list
    }

    /// Convert to a RegMask.
    pub fn to_regmask(&self) -> RegMask {
        let mut mask = RegMask::new();
        for entry in &self.clobbers {
            mask.set(entry.reg as u32);
        }
        mask
    }

    /// Count of GPR clobbers.
    pub fn gpr_clobber_count(&self) -> usize {
        self.clobbers
            .iter()
            .filter(|e| {
                matches!(
                    e.reg_class,
                    RegClass::GPR64 | RegClass::GPR32 | RegClass::GPR16 | RegClass::GPR8
                )
            })
            .count()
    }

    /// Count of vector clobbers.
    pub fn vector_clobber_count(&self) -> usize {
        self.clobbers
            .iter()
            .filter(|e| matches!(e.reg_class, RegClass::XMM | RegClass::YMM | RegClass::ZMM))
            .count()
    }
}

// ============================================================================
// Main Analysis: X86RegUsage
// ============================================================================

/// The primary register usage analysis pass for X86 targets.
#[derive(Debug, Clone)]
pub struct X86RegUsage {
    /// Target triple.
    pub target_triple: String,
    /// Whether targeting 64-bit mode.
    pub is_64bit: bool,
    /// Configuration for the analysis.
    pub config: RegUsageConfig,
    /// Cached register info.
    pub reg_info: Option<X86RegisterInfo>,
    /// Per-function liveness analysis results.
    pub liveness_cache: HashMap<String, FunctionLiveness>,
    /// Per-function callee-saved usage.
    pub callee_saved_cache: HashMap<String, CalleeSavedUsage>,
    /// Per-function def-use chains.
    pub def_use_cache: HashMap<String, Vec<RegDefUseChain>>,
    /// Per-function allocation hints.
    pub hint_cache: HashMap<String, RegAllocHints>,
    /// Per-function call clobber info.
    pub call_clobber_cache: HashMap<String, Vec<CallClobberInfo>>,
    /// Statistics.
    pub stats: RegUsageStats,
}

/// Configuration for register usage analysis.
#[derive(Debug, Clone)]
pub struct RegUsageConfig {
    /// Enable full liveness analysis.
    pub enable_liveness: bool,
    /// Enable callee-saved usage tracking.
    pub enable_callee_saved: bool,
    /// Enable call clobber analysis.
    pub enable_call_clobber: bool,
    /// Enable def-use chain building.
    pub enable_def_use_chains: bool,
    /// Enable pressure tracking.
    pub enable_pressure: bool,
    /// Enable allocation hint generation.
    pub enable_hints: bool,
    /// Enable implicit register detection.
    pub enable_implicit: bool,
    /// Track sub-register overlaps.
    pub track_subregs: bool,
    /// Maximum iterations for liveness fixed-point computation.
    pub max_liveness_iters: usize,
    /// Whether to cache analysis results.
    pub enable_caching: bool,
}

impl Default for RegUsageConfig {
    fn default() -> Self {
        Self {
            enable_liveness: true,
            enable_callee_saved: true,
            enable_call_clobber: true,
            enable_def_use_chains: true,
            enable_pressure: true,
            enable_hints: true,
            enable_implicit: true,
            track_subregs: true,
            max_liveness_iters: 100,
            enable_caching: true,
        }
    }
}

/// Statistics collected during register usage analysis.
#[derive(Debug, Clone, Default)]
pub struct RegUsageStats {
    /// Number of functions analyzed.
    pub functions_analyzed: usize,
    /// Number of basic blocks analyzed.
    pub blocks_analyzed: usize,
    /// Number of instructions analyzed.
    pub instructions_analyzed: usize,
    /// Total number of def-use chains built.
    pub def_use_chains: usize,
    /// Number of allocation hints generated.
    pub hints_generated: usize,
    /// Number of call sites analyzed for clobbers.
    pub call_sites: usize,
    /// Number of implicit register uses detected.
    pub implicit_uses_detected: usize,
    /// Average liveness fixed-point iterations.
    pub avg_liveness_iters: f64,
    /// Cache hits.
    pub cache_hits: usize,
    /// Cache misses.
    pub cache_misses: usize,
}

// ============================================================================
// X86RegUsage Implementation
// ============================================================================

impl X86RegUsage {
    /// Create a new register usage analyzer for x86-64.
    pub fn new_x86_64(target: &str) -> Self {
        Self {
            target_triple: target.to_string(),
            is_64bit: true,
            config: RegUsageConfig::default(),
            reg_info: None,
            liveness_cache: HashMap::new(),
            callee_saved_cache: HashMap::new(),
            def_use_cache: HashMap::new(),
            hint_cache: HashMap::new(),
            call_clobber_cache: HashMap::new(),
            stats: RegUsageStats::default(),
        }
    }

    /// Create a new register usage analyzer for x86-32.
    pub fn new_x86_32(target: &str) -> Self {
        Self {
            target_triple: target.to_string(),
            is_64bit: false,
            config: RegUsageConfig::default(),
            reg_info: None,
            liveness_cache: HashMap::new(),
            callee_saved_cache: HashMap::new(),
            def_use_cache: HashMap::new(),
            hint_cache: HashMap::new(),
            call_clobber_cache: HashMap::new(),
            stats: RegUsageStats::default(),
        }
    }

    /// Set custom configuration.
    pub fn with_config(mut self, config: RegUsageConfig) -> Self {
        self.config = config;
        self
    }

    // ========================================================================
    // Full Analysis Pipeline
    // ========================================================================

    /// Run the full register usage analysis on a function.
    pub fn analyze_function(&mut self, mf: &MachineFunction) {
        let func_name = mf.name.clone();
        self.stats.functions_analyzed += 1;
        self.stats.blocks_analyzed += mf.blocks.len();

        // Check cache.
        if self.config.enable_caching && self.liveness_cache.contains_key(&func_name) {
            self.stats.cache_hits += 1;
            return;
        }
        self.stats.cache_misses += 1;

        // Phase 1: Liveness analysis.
        if self.config.enable_liveness {
            let liveness = self.compute_liveness(mf);
            if self.config.enable_caching {
                self.liveness_cache.insert(func_name.clone(), liveness);
            }
        }

        // Phase 2: Callee-saved usage.
        if self.config.enable_callee_saved {
            let callee_usage = self.analyze_callee_saved(mf);
            if self.config.enable_caching {
                self.callee_saved_cache
                    .insert(func_name.clone(), callee_usage);
            }
        }

        // Phase 3: Call clobber analysis.
        if self.config.enable_call_clobber {
            let clobbers = self.analyze_call_clobbers(mf);
            self.stats.call_sites += clobbers.len();
            if self.config.enable_caching {
                self.call_clobber_cache.insert(func_name.clone(), clobbers);
            }
        }

        // Phase 4: Def-use chains.
        if self.config.enable_def_use_chains {
            let chains = self.build_def_use_chains(mf);
            self.stats.def_use_chains += chains.len();
            if self.config.enable_caching {
                self.def_use_cache.insert(func_name.clone(), chains);
            }
        }

        // Phase 5: Allocation hints.
        if self.config.enable_hints {
            let hints = self.generate_allocation_hints(mf);
            self.stats.hints_generated += hints.hint_count();
            if self.config.enable_caching {
                self.hint_cache.insert(func_name.clone(), hints);
            }
        }
    }

    // ========================================================================
    // Liveness Analysis
    // ========================================================================

    /// Compute register liveness for all instructions in a function.
    pub fn compute_liveness(&mut self, mf: &MachineFunction) -> FunctionLiveness {
        let num_blocks = mf.blocks.len();
        let mut block_live_in: Vec<RegMask> = vec![RegMask::new(); num_blocks];
        let mut block_live_out: Vec<RegMask> = vec![RegMask::new(); num_blocks];
        let mut block_defs: Vec<RegMask> = vec![RegMask::new(); num_blocks];
        let mut block_uses: Vec<RegMask> = vec![RegMask::new(); num_blocks];
        let mut per_instr: HashMap<(usize, usize), RegLiveness> = HashMap::new();

        // First pass: Compute local defs/uses per instruction.
        let mut local_defs: Vec<Vec<RegMask>> = Vec::with_capacity(num_blocks);
        let mut local_uses: Vec<Vec<RegMask>> = Vec::with_capacity(num_blocks);

        for (block_idx, block) in mf.blocks.iter().enumerate() {
            let mut instr_defs: Vec<RegMask> = Vec::with_capacity(block.instructions.len());
            let mut instr_uses: Vec<RegMask> = Vec::with_capacity(block.instructions.len());

            for instr in &block.instructions {
                let (defs, uses) = self.extract_reg_defs_uses(instr);
                instr_defs.push(defs);
                instr_uses.push(uses);

                // Accumulate block-level defs/uses.
                block_defs[block_idx] = block_defs[block_idx].union_with(&defs);
                block_uses[block_idx] = block_uses[block_idx].union_with(&uses);
            }

            local_defs.push(instr_defs);
            local_uses.push(instr_uses);
        }

        // Backward dataflow: compute liveness.
        let mut changed = true;
        let mut iterations: usize = 0;

        while changed && iterations < self.config.max_liveness_iters {
            changed = false;
            iterations += 1;

            for block_idx in (0..num_blocks).rev() {
                // live_out[B] = union of live_in[succ] for all successors.
                let mut new_live_out = RegMask::new();
                let block = &mf.blocks[block_idx];
                for &succ_idx in &block.successors {
                    if succ_idx < num_blocks {
                        new_live_out = new_live_out.union_with(&block_live_in[succ_idx]);
                    }
                }

                if new_live_out != block_live_out[block_idx] {
                    block_live_out[block_idx] = new_live_out;
                    changed = true;
                }

                // Backward sweep through instructions.
                let mut current_live = block_live_out[block_idx];
                let instr_count = mf.blocks[block_idx].instructions.len();

                for i in (0..instr_count).rev() {
                    // live_in[i] = (live_out[i] - defs[i]) ∪ uses[i]
                    let defs = &local_defs[block_idx][i];
                    let uses = &local_uses[block_idx][i];

                    let after_defs = current_live.subtract(defs);
                    let live_in = after_defs.union_with(uses);

                    per_instr.insert(
                        (block_idx, i),
                        RegLiveness {
                            live_in,
                            live_out: current_live,
                            defs: *defs,
                            uses: *uses,
                            implicit_defs: RegMask::new(),
                            implicit_uses: RegMask::new(),
                            dead_defs: RegMask::new(),
                            killed_uses: RegMask::new(),
                        },
                    );

                    current_live = live_in;
                }

                // block_live_in = live_in of first instruction.
                block_live_in[block_idx] = current_live;
            }
        }

        // Compute entry and exit liveness.
        let entry_live = if num_blocks > 0 {
            block_live_in[0]
        } else {
            RegMask::new()
        };
        let exit_live = RegMask::new(); // Nothing live after function return.

        FunctionLiveness {
            per_instr,
            block_live_in,
            block_live_out,
            block_defs,
            block_uses,
            entry_live,
            exit_live,
            iterations,
        }
    }

    /// Extract explicit register definitions and uses from an instruction.
    fn extract_reg_defs_uses(&self, instr: &MachineInstr) -> (RegMask, RegMask) {
        let mut defs = RegMask::new();
        let mut uses = RegMask::new();

        for op in &instr.operands {
            if op.is_reg() {
                if op.is_def() {
                    defs.set(op.reg());
                }
                if op.is_use() {
                    uses.set(op.reg());
                }
            }
        }

        // Add implicit register usage.
        if self.config.enable_implicit {
            let implicit = ImplicitRegUsage::new(instr.opcode);
            defs = defs.union_with(&implicit.implicit_def_mask());
            uses = uses.union_with(&implicit.implicit_use_mask());

            // CALL clobbers all caller-saved registers (they become "defined").
            let call64 = X86Opcode::CALL64pcrel32 as u32;
            let call32 = X86Opcode::CALL32pcrel32 as u32;
            if instr.opcode == call64 || instr.opcode == call32 {
                let clobber_list = if self.is_64bit {
                    ClobberList::sysv64_caller_saved()
                } else {
                    ClobberList::win64_caller_saved()
                };
                defs = defs.union_with(&clobber_list.to_regmask());
            }
        }

        (defs, uses)
    }

    // ========================================================================
    // Callee-Saved Register Usage
    // ========================================================================

    /// Analyze callee-saved register usage in a function.
    pub fn analyze_callee_saved(&mut self, mf: &MachineFunction) -> CalleeSavedUsage {
        let callee_saved = self.get_callee_saved_regs();
        let mut used_regs: Vec<u32> = Vec::new();
        let mut saved_regs: Vec<u32> = Vec::new();
        let mut restored_regs: Vec<u32> = Vec::new();
        let mut reg_use_blocks: HashMap<u32, BTreeSet<usize>> = HashMap::new();

        for block in &mf.blocks {
            let block_idx = 0; // Simplified; real impl tracks block index.

            for instr in &block.instructions {
                // Check for PUSH (save) of callee-saved registers.
                let push64 = X86Opcode::PUSH64r as u32;
                let push32 = X86Opcode::PUSH32r as u32;
                if instr.opcode == push64 || instr.opcode == push32 {
                    for op in &instr.operands {
                        let r = op.reg();
                        if op.is_reg() && callee_saved.contains(&r) {
                            if !saved_regs.contains(&r) {
                                saved_regs.push(r);
                            }
                        }
                    }
                }

                // Check for POP (restore) of callee-saved registers.
                let pop64 = X86Opcode::POP64r as u32;
                let pop32 = X86Opcode::POP32r as u32;
                if instr.opcode == pop64 || instr.opcode == pop32 {
                    for op in &instr.operands {
                        let r = op.reg();
                        if op.is_reg() && callee_saved.contains(&r) {
                            if !restored_regs.contains(&r) {
                                restored_regs.push(r);
                            }
                        }
                    }
                }

                // Check for uses of callee-saved registers.
                for op in &instr.operands {
                    if op.is_reg() && op.is_use() && callee_saved.contains(&op.reg()) {
                        let r = op.reg();
                        if !used_regs.contains(&r) {
                            used_regs.push(r);
                        }
                        reg_use_blocks.entry(r).or_default().insert(block_idx);
                    }
                }
            }
        }

        // Detect mismatches.
        let mut used_but_not_saved: Vec<u32> = Vec::new();
        let mut saved_but_unused: Vec<u32> = Vec::new();

        for &reg in &used_regs {
            if !saved_regs.contains(&reg) && !restored_regs.contains(&reg) {
                used_but_not_saved.push(reg);
            }
        }
        for &reg in &saved_regs {
            if !used_regs.contains(&reg) {
                saved_but_unused.push(reg);
            }
        }
        for &reg in &restored_regs {
            if !used_regs.contains(&reg) && !saved_but_unused.contains(&reg) {
                saved_but_unused.push(reg);
            }
        }

        // Determine if shrink-wrapping is beneficial.
        let frame_pointer_used =
            used_regs.contains(&(RBP as u32)) || saved_regs.contains(&(RBP as u32));
        let shrink_wrap_beneficial = used_regs.len() < saved_regs.len()
            || saved_but_unused.len() > 0
            || (used_regs.len() <= 3 && mf.blocks.len() > 1);

        CalleeSavedUsage {
            used_regs,
            saved_regs,
            restored_regs,
            used_but_not_saved,
            saved_but_unused,
            shrink_wrap_beneficial,
            reg_use_blocks,
            frame_pointer_used,
        }
    }

    /// Get the set of callee-saved registers for the current ABI.
    fn get_callee_saved_regs(&self) -> Vec<u32> {
        if self.is_64bit {
            // System V AMD64 callee-saved: RBX, RBP, R12-R15.
            vec![
                RBX as u32, RBP as u32, R12 as u32, R13 as u32, R14 as u32, R15 as u32,
            ]
        } else {
            // 32-bit callee-saved: EBX, EBP, ESI, EDI.
            vec![EBX as u32, EBP as u32, ESI as u32, EDI as u32]
        }
    }

    /// Get the set of caller-saved registers for the current ABI.
    fn get_caller_saved_regs(&self) -> Vec<u32> {
        if self.is_64bit {
            vec![
                RAX as u32, RCX as u32, RDX as u32, RSI as u32, RDI as u32, R8 as u32, R9 as u32,
                R10 as u32, R11 as u32,
            ]
        } else {
            vec![EAX as u32, ECX as u32, EDX as u32]
        }
    }

    // ========================================================================
    // Call Clobber Analysis
    // ========================================================================

    /// Analyze caller-saved register clobber at each call site.
    pub fn analyze_call_clobbers(&mut self, mf: &MachineFunction) -> Vec<CallClobberInfo> {
        let mut clobber_infos: Vec<CallClobberInfo> = Vec::new();
        let caller_saved = self.get_caller_saved_regs();

        // Get liveness info if available.
        let func_name = &mf.name;
        let liveness = self.liveness_cache.get(func_name);

        for (block_idx, block) in mf.blocks.iter().enumerate() {
            for (instr_idx, instr) in block.instructions.iter().enumerate() {
                let call64 = X86Opcode::CALL64pcrel32 as u32;
                let call32 = X86Opcode::CALL32pcrel32 as u32;
                if instr.opcode != call64 && instr.opcode != call32 {
                    continue;
                }

                let callee = self.extract_call_target(instr);
                let known_callee = !callee.is_empty();

                // Compute live registers across this call.
                let live_across = if let Some(liveness) = liveness {
                    if let Some(rec) = liveness.per_instr.get(&(block_idx, instr_idx)) {
                        rec.live_in
                    } else {
                        RegMask::new()
                    }
                } else {
                    RegMask::new()
                };

                // Registers that are both caller-saved AND live across the call
                // must be spilled.
                let mut must_spill = RegMask::new();
                for &reg in &caller_saved {
                    if live_across.contains(reg) {
                        must_spill.set(reg);
                    }
                }

                // Compute standard clobber set.
                let abi_clobber_list = if self.is_64bit {
                    ClobberList::sysv64_caller_saved()
                } else {
                    ClobberList::win64_caller_saved()
                };
                let clobbered_by_callee = abi_clobber_list.to_regmask();

                // For known callees, compute precise clobber.
                let custom_clobbers = if known_callee {
                    self.compute_precise_clobbers(&callee)
                } else {
                    None
                };

                // Compute preserved registers.
                let preserved_by_callee = RegMask::from_slice(&self.get_callee_saved_regs());

                clobber_infos.push(CallClobberInfo {
                    call_instr_idx: instr_idx,
                    block_idx,
                    callee,
                    live_across,
                    must_spill,
                    clobbered_by_callee,
                    known_callee,
                    custom_clobbers,
                    preserved_by_callee,
                });
            }
        }

        clobber_infos
    }

    /// Extract the call target name from a CALL instruction.
    fn extract_call_target(&self, instr: &MachineInstr) -> String {
        for op in &instr.operands {
            if op.is_global() {
                if let MachineOperand::Global(name) = op {
                    return name.clone();
                }
            }
        }
        String::new()
    }

    /// Compute precise clobber set for a known callee (by analyzing its body).
    fn compute_precise_clobbers(&self, _callee: &str) -> Option<RegMask> {
        // For a known callee, we can analyze the function body to determine
        // which caller-saved registers are actually modified.
        // This enables more precise liveness: if a known leaf function only
        // uses RAX, we don't need to spill RCX/RDX/RSI/etc.
        //
        // In a full implementation, this would:
        // 1. Look up the callee in the module's function list.
        // 2. Compute the set of registers defined in the callee.
        // 3. Intersect with the caller-saved set.
        // 4. Return a precise mask.
        None
    }

    // ========================================================================
    // Def-Use Chain Building
    // ========================================================================

    /// Build def-use chains for all physical registers in a function.
    pub fn build_def_use_chains(&self, mf: &MachineFunction) -> Vec<RegDefUseChain> {
        let mut chains: Vec<RegDefUseChain> = Vec::new();
        let max_reg = if self.is_64bit { 128u16 } else { 64u16 };

        for reg_id in 0..max_reg {
            let mut chain = RegDefUseChain::new(reg_id);
            // Scan all instructions for defs/uses of this register.
            for (block_idx, block) in mf.blocks.iter().enumerate() {
                for (instr_idx, instr) in block.instructions.iter().enumerate() {
                    for op in &instr.operands {
                        if op.is_reg() && op.reg() as u16 == reg_id {
                            if op.is_def() {
                                chain.add_def(
                                    block_idx,
                                    instr_idx,
                                    false,
                                    self.is_copy_instr(instr),
                                );
                            }
                            if op.is_use() {
                                let is_last_use =
                                    !self.has_further_uses(mf, block_idx, instr_idx, reg_id);
                                chain.add_use(block_idx, instr_idx, false, is_last_use);
                            }
                        }
                    }
                }
            }

            if !chain.defs.is_empty() || !chain.uses.is_empty() {
                chains.push(chain);
            }
        }

        chains
    }

    /// Check if an instruction is a register copy (MOV).
    fn is_copy_instr(&self, instr: &MachineInstr) -> bool {
        instr.opcode == X86Opcode::MOV32rr as u32
            || instr.opcode == X86Opcode::MOV64rr as u32
            || instr.opcode == X86Opcode::MOV16rr as u32
            || instr.opcode == X86Opcode::MOV8rr as u32
    }

    /// Check if a register has further uses after a given point (simplified).
    fn has_further_uses(
        &self,
        _mf: &MachineFunction,
        _block_idx: usize,
        _instr_idx: usize,
        _reg: u16,
    ) -> bool {
        // Simplified check; full impl scans forward from instr_idx+1.
        false
    }

    // ========================================================================
    // Register Pressure Per Instruction
    // ========================================================================

    /// Compute register pressure at each instruction boundary.
    pub fn compute_pressure(&self, liveness: &FunctionLiveness) -> Vec<Vec<RegPressureSnapshot>> {
        let mut result: Vec<Vec<RegPressureSnapshot>> = Vec::new();

        for block_idx in 0..liveness.block_live_in.len() {
            let mut block_pressure: Vec<RegPressureSnapshot> = Vec::new();

            // Pressure at block entry = count of live registers by class.
            let entry_mask = liveness.block_live_in[block_idx];
            let entry_pressure = self.mask_to_pressure(&entry_mask);
            block_pressure.push(entry_pressure);

            // Walk instructions and update pressure.
            let mut current_mask = entry_mask;
            for i in 0..100 {
                // Simplified; real impl iterates over instructions.
                if let Some(rec) = liveness.per_instr.get(&(block_idx, i)) {
                    let after_instr = self.mask_to_pressure(&rec.live_out);
                    block_pressure.push(after_instr);
                    current_mask = rec.live_out;
                } else {
                    break;
                }
            }

            result.push(block_pressure);
        }

        result
    }

    /// Convert a register mask to a pressure snapshot by classifying registers.
    fn mask_to_pressure(&self, mask: &RegMask) -> RegPressureSnapshot {
        let mut snapshot = RegPressureSnapshot::new();
        let regs = mask.to_vec();

        for reg in regs {
            // Classify register into its class.
            if reg < 16 {
                // GPR range.
                if reg != RSP && reg != RBP {
                    snapshot.gpr += 1;
                }
            } else if reg >= 32 && reg < 64 {
                // XMM range.
                snapshot.xmm += 1;
            } else if reg >= 64 && reg < 96 {
                // YMM range.
                snapshot.ymm += 1;
            } else if reg >= 96 && reg < 128 {
                // ZMM range.
                snapshot.zmm += 1;
            } else if reg >= 128 && reg < 136 {
                // K mask range.
                snapshot.kmask += 1;
            } else if reg >= 200 && reg < 208 {
                // x87 range.
                snapshot.x87 += 1;
            }
        }

        snapshot
    }

    // ========================================================================
    // Allocation Hint Generation
    // ========================================================================

    /// Generate register allocation hints from usage patterns.
    pub fn generate_allocation_hints(&self, mf: &MachineFunction) -> RegAllocHints {
        let mut hints = RegAllocHints::new();

        for block in &mf.blocks {
            for instr in &block.instructions {
                // Detect loop counter patterns: instructions that use a register
                // with INC/DEC or ADD/SUB by 1, especially if they appear
                // before a conditional branch.
                if instr.opcode == X86Opcode::INC64r as u32
                    || instr.opcode == X86Opcode::INC32r as u32
                    || instr.opcode == X86Opcode::DEC64r as u32
                    || instr.opcode == X86Opcode::DEC32r as u32
                {
                    for op in &instr.operands {
                        if op.is_reg() {
                            hints.add_loop_counter(op.reg() as u16);
                        }
                    }
                }

                // Detect division patterns: DIV/IDIV uses RAX/RDX.
                if instr.opcode == X86Opcode::DIV64r as u32
                    || instr.opcode == X86Opcode::DIV32r as u32
                    || instr.opcode == X86Opcode::IDIV64r as u32
                    || instr.opcode == X86Opcode::IDIV32r as u32
                {
                    hints.div_regs.insert(if self.is_64bit { RAX } else { EAX });
                    hints.div_regs.insert(if self.is_64bit { RDX } else { EDX });
                }

                // Detect shift count patterns: SHL/SHR/SAR by CL.
                if instr.opcode == X86Opcode::SHL64rCL as u32
                    || instr.opcode == X86Opcode::SHR64rCL as u32
                    || instr.opcode == X86Opcode::SAR64rCL as u32
                    || instr.opcode == X86Opcode::SHL32rCL as u32
                    || instr.opcode == X86Opcode::SHR32rCL as u32
                    || instr.opcode == X86Opcode::SAR32rCL as u32
                {
                    hints
                        .shift_count_regs
                        .insert(if self.is_64bit { RCX } else { ECX });
                }

                // Detect base pointer usage: LEA with RBP-like patterns.
                let lea64 = X86Opcode::LEA64r as u32;
                let lea32 = X86Opcode::LEA32r as u32;
                if instr.opcode == lea64 || instr.opcode == lea32 {
                    // Check if this LEA uses a base register that acts as a
                    // frame or object pointer.
                    for op in &instr.operands {
                        if op.is_reg() && op.is_use() {
                            hints.add_base_pointer(op.reg() as u16);
                        }
                    }
                }

                // Detect copy instructions for coalescing hints.
                if self.is_copy_instr(instr) && instr.operands.len() >= 2 {
                    let dst = &instr.operands[0];
                    let src = &instr.operands[1];
                    if dst.is_reg() && src.is_reg() && dst.reg() != src.reg() {
                        // Create coalescing hint for virtual registers.
                        // (For physical registers, this is trivial.)
                    }
                }
            }
        }

        hints
    }

    // ========================================================================
    // Utility Methods
    // ========================================================================

    /// Check if a register is callee-saved.
    pub fn is_callee_saved(&self, reg: u16) -> bool {
        self.get_callee_saved_regs().contains(&(reg as u32))
    }

    /// Check if a register is caller-saved.
    pub fn is_caller_saved(&self, reg: u16) -> bool {
        self.get_caller_saved_regs().contains(&(reg as u32))
    }

    /// Get the set of registers live across a specific call site.
    pub fn get_live_across_call(
        &self,
        func_name: &str,
        block_idx: usize,
        instr_idx: usize,
    ) -> Option<RegMask> {
        self.liveness_cache.get(func_name).and_then(|liveness| {
            liveness
                .per_instr
                .get(&(block_idx, instr_idx))
                .map(|rec| rec.live_in)
        })
    }

    /// Get the def-use chain for a specific register.
    pub fn get_def_use_chain(&self, func_name: &str, reg: u16) -> Option<&RegDefUseChain> {
        self.def_use_cache
            .get(func_name)
            .and_then(|chains| chains.iter().find(|c| c.reg == reg))
    }

    /// Generate a report string.
    pub fn report(&self) -> String {
        format!(
            "RegUsage: funcs={} blocks={} instrs={} chains={} hints={} calls={} implicit_uses={} \
             avg_iters={:.1} cache_hits={} cache_misses={}",
            self.stats.functions_analyzed,
            self.stats.blocks_analyzed,
            self.stats.instructions_analyzed,
            self.stats.def_use_chains,
            self.stats.hints_generated,
            self.stats.call_sites,
            self.stats.implicit_uses_detected,
            self.stats.avg_liveness_iters,
            self.stats.cache_hits,
            self.stats.cache_misses,
        )
    }

    /// Clear all cached analysis results.
    pub fn clear_cache(&mut self) {
        self.liveness_cache.clear();
        self.callee_saved_cache.clear();
        self.def_use_cache.clear();
        self.hint_cache.clear();
        self.call_clobber_cache.clear();
    }
}

// ============================================================================
// Public API Factory Functions
// ============================================================================

/// Create an X86 register usage analyzer for x86-64 targets.
pub fn make_x86_64_reg_usage(target: &str) -> X86RegUsage {
    X86RegUsage::new_x86_64(target)
}

/// Create an X86 register usage analyzer for x86-32 targets.
pub fn make_x86_32_reg_usage(target: &str) -> X86RegUsage {
    X86RegUsage::new_x86_32(target)
}

/// Create a register usage analyzer with full analysis enabled.
pub fn make_reg_usage_full(target: &str) -> X86RegUsage {
    let config = RegUsageConfig::default();
    X86RegUsage::new_x86_64(target).with_config(config)
}

/// Create a register usage analyzer for liveness-only analysis.
pub fn make_reg_usage_liveness_only(target: &str) -> X86RegUsage {
    let config = RegUsageConfig {
        enable_liveness: true,
        enable_callee_saved: false,
        enable_call_clobber: false,
        enable_def_use_chains: false,
        enable_pressure: false,
        enable_hints: false,
        enable_implicit: false,
        track_subregs: false,
        max_liveness_iters: 50,
        enable_caching: false,
    };
    X86RegUsage::new_x86_64(target).with_config(config)
}

/// Run register usage analysis and return allocation hints.
pub fn analyze_register_usage(mf: &MachineFunction, target: &str) -> X86RegUsage {
    let mut analyzer = make_x86_64_reg_usage(target);
    analyzer.analyze_function(mf);
    analyzer
}

/// Run liveness analysis only.
pub fn run_liveness_analysis(mf: &MachineFunction, target: &str) -> FunctionLiveness {
    let mut analyzer = make_reg_usage_liveness_only(target);
    analyzer.compute_liveness(mf)
}

/// Get the caller-saved register clobber list for a given ABI.
pub fn get_abi_clobber_list(is_64bit: bool, is_windows: bool) -> ClobberList {
    if is_64bit {
        if is_windows {
            ClobberList::win64_caller_saved()
        } else {
            ClobberList::sysv64_caller_saved()
        }
    } else {
        // 32-bit: simplified caller-saved.
        ClobberList::win64_caller_saved()
    }
}

// ============================================================================
// Extended: Register Preservation Analysis
// ============================================================================

/// Result of register preservation analysis.
#[derive(Debug, Clone)]
pub struct RegPreservation {
    /// Registers preserved across the entire function.
    pub preserved_regs: RegMask,
    /// Registers modified by the function.
    pub modified_regs: RegMask,
    /// Registers used as inputs (arguments).
    pub input_regs: RegMask,
    /// Registers used as outputs (return values).
    pub output_regs: RegMask,
    /// Registers that are both inputs and outputs.
    pub inout_regs: RegMask,
}

impl RegPreservation {
    /// Create from liveness analysis.
    pub fn from_liveness(liveness: &FunctionLiveness) -> Self {
        let entry_live = liveness.entry_live;
        let exit_live = liveness.exit_live;

        // Preserved: live at both entry and exit.
        let preserved_regs = entry_live.intersect_with(&exit_live);

        // Modified: defined in the function (in block_defs but not in entry_live).
        let mut modified_regs = RegMask::new();
        for def_mask in &liveness.block_defs {
            modified_regs = modified_regs.union_with(def_mask);
        }
        // Don't count entry-live registers as "modified" unless redefined.
        modified_regs = modified_regs.subtract(&entry_live);
        // But if a register is live at entry AND redefined, it's modified.
        // (Simplified: count everything in block_defs as modified.)

        let input_regs = entry_live;
        let output_regs = exit_live;
        let inout_regs = entry_live.intersect_with(&exit_live);

        Self {
            preserved_regs,
            modified_regs,
            input_regs,
            output_regs,
            inout_regs,
        }
    }
}

// ============================================================================
// Extended: Register Usage Across Call Boundaries
// ============================================================================

/// Register usage information across a call boundary.
#[derive(Debug, Clone)]
pub struct CrossCallRegUsage {
    /// The call site (block_idx, instr_idx).
    pub call_site: (usize, usize),
    /// Registers live before the call.
    pub live_before: RegMask,
    /// Registers live after the call.
    pub live_after: RegMask,
    /// Registers spilled before the call.
    pub spilled: RegMask,
    /// Registers reloaded after the call.
    pub reloaded: RegMask,
    /// Registers passed as arguments.
    pub arg_regs: Vec<u16>,
    /// Registers that receive return values.
    pub ret_regs: Vec<u16>,
}

impl CrossCallRegUsage {
    /// Create a new cross-call register usage record.
    pub fn new(block_idx: usize, instr_idx: usize) -> Self {
        Self {
            call_site: (block_idx, instr_idx),
            live_before: RegMask::new(),
            live_after: RegMask::new(),
            spilled: RegMask::new(),
            reloaded: RegMask::new(),
            arg_regs: Vec::new(),
            ret_regs: Vec::new(),
        }
    }

    /// Compute net register effect of the call.
    pub fn net_reg_delta(&self) -> isize {
        // Positive: more registers live after than before.
        self.live_after.count() as isize - self.live_before.count() as isize
    }

    /// Check if any register needs spilling.
    pub fn needs_spilling(&self) -> bool {
        !self.spilled.is_empty()
    }
}

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

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

    #[test]
    fn test_reg_mask_empty() {
        let mask = RegMask::new();
        assert!(mask.is_empty());
        assert_eq!(mask.count(), 0);
    }

    #[test]
    fn test_reg_mask_single() {
        let mask = RegMask::single(RAX);
        assert!(mask.contains(RAX));
        assert!(!mask.contains(RBX));
        assert_eq!(mask.count(), 1);
    }

    #[test]
    fn test_reg_mask_from_slice() {
        let mask = RegMask::from_slice(&[RAX, RBX, RCX]);
        assert_eq!(mask.count(), 3);
        assert!(mask.contains(RAX));
        assert!(mask.contains(RBX));
        assert!(mask.contains(RCX));
    }

    #[test]
    fn test_reg_mask_set_clear() {
        let mut mask = RegMask::new();
        mask.set(RAX);
        assert!(mask.contains(RAX));
        mask.clear(RAX);
        assert!(!mask.contains(RAX));
    }

    #[test]
    fn test_reg_mask_union() {
        let a = RegMask::single(RAX);
        let b = RegMask::single(RBX);
        let union = a.union_with(&b);
        assert_eq!(union.count(), 2);
        assert!(union.contains(RAX));
        assert!(union.contains(RBX));
    }

    #[test]
    fn test_reg_mask_intersection() {
        let a = RegMask::from_slice(&[RAX, RBX]);
        let b = RegMask::from_slice(&[RBX, RCX]);
        let inter = a.intersect_with(&b);
        assert_eq!(inter.count(), 1);
        assert!(inter.contains(RBX));
    }

    #[test]
    fn test_reg_mask_subtract() {
        let a = RegMask::from_slice(&[RAX, RBX, RCX]);
        let b = RegMask::single(RBX);
        let diff = a.subtract(&b);
        assert_eq!(diff.count(), 2);
        assert!(diff.contains(RAX));
        assert!(diff.contains(RCX));
        assert!(!diff.contains(RBX));
    }

    #[test]
    fn test_reg_mask_overlaps() {
        let a = RegMask::from_slice(&[RAX, RBX]);
        let b = RegMask::from_slice(&[RBX, RCX]);
        assert!(a.overlaps(&b));

        let c = RegMask::single(RDX);
        assert!(!a.overlaps(&c));
    }

    #[test]
    fn test_reg_mask_to_vec() {
        let mask = RegMask::from_slice(&[RAX, R10, R15]);
        let regs = mask.to_vec();
        assert_eq!(regs.len(), 3);
        assert!(regs.contains(&RAX));
        assert!(regs.contains(&R10));
        assert!(regs.contains(&R15));
    }

    #[test]
    fn test_reg_mask_display() {
        let mask = RegMask::single(RAX);
        let s = format!("{}", mask);
        assert!(s.contains("r"));
    }

    #[test]
    fn test_pressure_snapshot_ratios() {
        let snapshot = RegPressureSnapshot {
            gpr: 7,
            xmm: 8,
            ymm: 0,
            zmm: 0,
            kmask: 0,
            x87: 0,
            mmx: 0,
            max_available: RegPressureMax::default(),
        };
        assert!((snapshot.gpr_ratio() - 0.5).abs() < 0.01);
        assert!((snapshot.xmm_ratio() - 0.5).abs() < 0.01);
        assert!(!snapshot.has_high_pressure());
        assert!(!snapshot.has_critical_pressure());
    }

    #[test]
    fn test_pressure_high() {
        let snapshot = RegPressureSnapshot {
            gpr: 13, // 13/14 ≈ 0.93 > 0.75
            xmm: 0,
            ymm: 0,
            zmm: 0,
            kmask: 0,
            x87: 0,
            mmx: 0,
            max_available: RegPressureMax::default(),
        };
        assert!(snapshot.has_high_pressure());
    }

    #[test]
    fn test_clobber_list_sysv64() {
        let list = ClobberList::sysv64_caller_saved();
        assert!(list.clobbers_all_vector);
        assert!(list.clobbers_flags);
        assert!(list.gpr_clobber_count() >= 9);
    }

    #[test]
    fn test_clobber_list_win64() {
        let list = ClobberList::win64_caller_saved();
        assert!(list.clobbers_all_vector);
        assert!(list.clobbers_flags);
    }

    #[test]
    fn test_def_use_chain() {
        let mut chain = RegDefUseChain::new(RAX);
        let def0 = chain.add_def(0, 0, false, false);
        let use0 = chain.add_use(0, 3, false, true);
        chain.link_def_to_use(def0, use0);
        assert!(!chain.def_is_dead(def0));
        assert_eq!(chain.use_count(def0), 1);
    }

    #[test]
    fn test_def_use_chain_dead_def() {
        let mut chain = RegDefUseChain::new(RAX);
        let def0 = chain.add_def(0, 0, false, false);
        assert!(chain.def_is_dead(def0));
    }

    #[test]
    fn test_alloc_hints() {
        let mut hints = RegAllocHints::new();
        hints.add_loop_counter(RCX);
        hints.add_base_pointer(RBP);
        assert_eq!(hints.hint_count(), 2);
        assert!(hints.loop_counters.contains(&RCX));
        assert!(hints.base_pointers.contains(&RBP));
    }

    #[test]
    fn test_reg_preservation() {
        let entry = RegMask::single(RAX);
        let exit = RegMask::single(RAX);
        // Note: testing the basic concept; full test would use FunctionLiveness.
        let preserved = entry.intersect_with(&exit);
        assert_eq!(preserved.count(), 1);
        assert!(preserved.contains(RAX));
    }

    #[test]
    fn test_cross_call_reg_usage() {
        let usage = CrossCallRegUsage::new(0, 5);
        assert_eq!(usage.call_site, (0, 5));
        assert!(!usage.needs_spilling());
        assert_eq!(usage.net_reg_delta(), 0);
    }

    #[test]
    fn test_implicit_reg_usage_new() {
        let usage = ImplicitRegUsage::new(X86Opcode::DIV64r as u32);
        assert_eq!(usage.opcode, X86Opcode::DIV64r);
    }

    #[test]
    fn test_reg_liveness_new() {
        let liveness = RegLiveness::new();
        assert!(liveness.live_in.is_empty());
        assert!(liveness.live_out.is_empty());
        assert!(liveness.live_through().is_empty());
    }

    #[test]
    fn test_function_liveness_empty() {
        let mf = MachineFunction::new("empty_func");
        let mut analyzer = make_x86_64_reg_usage("x86_64-unknown-linux-gnu");
        let liveness = analyzer.compute_liveness(&mf);
        assert_eq!(liveness.blocks_analyzed, 0);
    }
}