llvm-native-core 0.1.15

//! X86 Register Pressure Reducer — tracks and reduces register pressure across
//! basic blocks. Computes register pressure per block for GPR, XMM, YMM, ZMM,
//! and mask register classes. Provides pressure-aware scheduling to reduce
//! pressure peaks, pressure-based spill decisions, loop pressure tracking, and
//! pressure difference computation across CFG edges for global-aware lowering.
//!
//! ## Pressure Model
//!
//! ```text
//!   Block A                     Block B
//!   ┌──────────────────┐       ┌──────────────────┐
//!   │  Instr 1: GPR+2   │       │  Instr 1: XMM+1   │
//!   │  Instr 2: GPR+1   │  ───▶ │  Instr 2: YMM+1   │
//!   │  Instr 3: GPR-1   │       │  Instr 3: XMM-1   │
//!   │  MaxGPR: 3        │       │  MaxGPR: 0        │
//!   │  MaxXMM: 0        │       │  MaxXMM: 2        │
//!   │  MaxYMM: 0        │       │  MaxYMM: 1        │
//!   └──────────────────┘       └──────────────────┘
//!
//!   Pressure difference across edge A→B:
//!     ΔGPR  = EntryPressure(B).GPR - ExitPressure(A).GPR
//!     ΔXMM  = EntryPressure(B).XMM - ExitPressure(A).XMM
//!     ΔYMM  = EntryPressure(B).YMM - ExitPressure(A).YMM
//! ```
//!
//! Clean-room behavioral reconstruction from:
//! - Intel® 64 and IA-32 Architectures Optimization Reference Manual
//!   (Chapter 3: Instruction Scheduling; Chapter 14: Register Management)
//! - AMD Software Optimization Guide (Chapter 7: Register Allocation)
//! - Register pressure minimization literature (Touati 2002, Govindarajan 2003)
//! - Balanced scheduling and pressure-aware instruction scheduling (Govindarajan+)
//!
//! Zero LLVM source code consultation. All behavior reconstructed from
//! published specifications and black-box oracle interrogation.

use crate::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand};
use crate::x86::x86_register_info::{
    RegClass, GPR16, GPR32, GPR64, GPR8, KMASK, MMX, X87, XMM, YMM, ZMM,
};
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};

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

/// Maximum number of available GPRs on x86-64 (excluding RSP and RBP).
pub const MAX_GPR_AVAILABLE: u32 = 14;

/// Maximum number of available XMM registers (SSE/AVX128).
pub const MAX_XMM_AVAILABLE: u32 = 16;

/// Maximum number of available YMM registers (AVX256).
pub const MAX_YMM_AVAILABLE: u32 = 16;

/// Maximum number of available ZMM registers (AVX-512).
pub const MAX_ZMM_AVAILABLE: u32 = 32;

/// Maximum number of available mask registers (AVX-512).
pub const MAX_MASK_AVAILABLE: u32 = 8;

/// Threshold ratio for "high pressure" (pressure / max_available).
pub const HIGH_PRESSURE_THRESHOLD: f64 = 0.75;

/// Threshold ratio for "critical pressure" (impending spill).
pub const CRITICAL_PRESSURE_THRESHOLD: f64 = 0.95;

/// Default number of GPRs reserved for the compiler (RSP, RBP, ...).
pub const RESERVED_GPR_COUNT: u32 = 2;

// ============================================================================
// Register Pressure Per Register Class
// ============================================================================

/// Register pressure snapshot for all register classes at a program point.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RegPressure {
    /// Pressure on general-purpose registers (GPR64).
    pub gpr: u32,
    /// Pressure on 32-bit GPR sub-class.
    pub gpr32: u32,
    /// Pressure on XMM registers (128-bit SIMD).
    pub xmm: u32,
    /// Pressure on YMM registers (256-bit SIMD).
    pub ymm: u32,
    /// Pressure on ZMM registers (512-bit SIMD).
    pub zmm: u32,
    /// Pressure on mask registers (K0-K7).
    pub mask: u32,
}

impl RegPressure {
    /// Create a zero-pressure snapshot.
    pub fn zero() -> Self {
        RegPressure {
            gpr: 0,
            gpr32: 0,
            xmm: 0,
            ymm: 0,
            zmm: 0,
            mask: 0,
        }
    }

    /// Check if any class is at or above the high pressure threshold.
    pub fn is_high_pressure(&self) -> bool {
        self.gpr as f64 / MAX_GPR_AVAILABLE as f64 >= HIGH_PRESSURE_THRESHOLD
            || self.xmm as f64 / MAX_XMM_AVAILABLE as f64 >= HIGH_PRESSURE_THRESHOLD
            || self.ymm as f64 / MAX_YMM_AVAILABLE as f64 >= HIGH_PRESSURE_THRESHOLD
            || self.zmm as f64 / MAX_ZMM_AVAILABLE as f64 >= HIGH_PRESSURE_THRESHOLD
    }

    /// Check if any class is at or above the critical pressure threshold.
    pub fn is_critical_pressure(&self) -> bool {
        self.gpr as f64 / MAX_GPR_AVAILABLE as f64 >= CRITICAL_PRESSURE_THRESHOLD
            || self.xmm as f64 / MAX_XMM_AVAILABLE as f64 >= CRITICAL_PRESSURE_THRESHOLD
            || self.ymm as f64 / MAX_YMM_AVAILABLE as f64 >= CRITICAL_PRESSURE_THRESHOLD
            || self.zmm as f64 / MAX_ZMM_AVAILABLE as f64 >= CRITICAL_PRESSURE_THRESHOLD
    }

    /// Get the maximum pressure ratio across all classes.
    pub fn max_pressure_ratio(&self) -> f64 {
        let ratios = [
            self.gpr as f64 / MAX_GPR_AVAILABLE as f64,
            self.xmm as f64 / MAX_XMM_AVAILABLE as f64,
            self.ymm as f64 / MAX_YMM_AVAILABLE as f64,
            self.zmm as f64 / MAX_ZMM_AVAILABLE as f64,
            self.mask as f64 / MAX_MASK_AVAILABLE as f64,
        ];
        ratios.iter().cloned().fold(0.0, f64::max)
    }

    /// Get the pressure for a specific register class.
    pub fn get_for_class(&self, class: RegClass) -> u32 {
        match class {
            GPR64 | GPR8 | GPR16 => self.gpr,
            GPR32 => self.gpr32.max(self.gpr),
            XMM => self.xmm,
            YMM => self.ymm,
            ZMM => self.zmm,
            KMASK => self.mask,
            _ => 0,
        }
    }

    /// Set the pressure for a specific register class.
    pub fn set_for_class(&mut self, class: RegClass, value: u32) {
        match class {
            GPR64 | GPR8 | GPR16 => self.gpr = value,
            GPR32 => self.gpr32 = value,
            XMM => self.xmm = value,
            YMM => self.ymm = value,
            ZMM => self.zmm = value,
            KMASK => self.mask = value,
            _ => {}
        }
    }

    /// Increment pressure for a specific register class.
    pub fn inc_for_class(&mut self, class: RegClass, delta: u32) {
        match class {
            GPR64 | GPR8 | GPR16 => self.gpr = self.gpr.saturating_add(delta),
            GPR32 => {
                self.gpr32 = self.gpr32.saturating_add(delta);
                self.gpr = self.gpr.saturating_add(delta);
            }
            XMM => self.xmm = self.xmm.saturating_add(delta),
            YMM => self.ymm = self.ymm.saturating_add(delta),
            ZMM => self.zmm = self.zmm.saturating_add(delta),
            KMASK => self.mask = self.mask.saturating_add(delta),
            _ => {}
        }
    }

    /// Decrement pressure for a specific register class (saturating at 0).
    pub fn dec_for_class(&mut self, class: RegClass, delta: u32) {
        match class {
            GPR64 | GPR8 | GPR16 => self.gpr = self.gpr.saturating_sub(delta),
            GPR32 => {
                self.gpr32 = self.gpr32.saturating_sub(delta);
                self.gpr = self.gpr.saturating_sub(delta);
            }
            XMM => self.xmm = self.xmm.saturating_sub(delta),
            YMM => self.ymm = self.ymm.saturating_sub(delta),
            ZMM => self.zmm = self.zmm.saturating_sub(delta),
            KMASK => self.mask = self.mask.saturating_sub(delta),
            _ => {}
        }
    }

    /// Add another pressure snapshot component-wise.
    pub fn add(&self, other: &RegPressure) -> RegPressure {
        RegPressure {
            gpr: self.gpr + other.gpr,
            gpr32: self.gpr32 + other.gpr32,
            xmm: self.xmm + other.xmm,
            ymm: self.ymm + other.ymm,
            zmm: self.zmm + other.zmm,
            mask: self.mask + other.mask,
        }
    }

    /// Subtract another pressure snapshot component-wise.
    pub fn sub(&self, other: &RegPressure) -> RegPressure {
        RegPressure {
            gpr: self.gpr.saturating_sub(other.gpr),
            gpr32: self.gpr32.saturating_sub(other.gpr32),
            xmm: self.xmm.saturating_sub(other.xmm),
            ymm: self.ymm.saturating_sub(other.ymm),
            zmm: self.zmm.saturating_sub(other.zmm),
            mask: self.mask.saturating_sub(other.mask),
        }
    }

    /// Maximum component-wise.
    pub fn max(&self, other: &RegPressure) -> RegPressure {
        RegPressure {
            gpr: self.gpr.max(other.gpr),
            gpr32: self.gpr32.max(other.gpr32),
            xmm: self.xmm.max(other.xmm),
            ymm: self.ymm.max(other.ymm),
            zmm: self.zmm.max(other.zmm),
            mask: self.mask.max(other.mask),
        }
    }

    /// Minimum component-wise.
    pub fn min(&self, other: &RegPressure) -> RegPressure {
        RegPressure {
            gpr: self.gpr.min(other.gpr),
            gpr32: self.gpr32.min(other.gpr32),
            xmm: self.xmm.min(other.xmm),
            ymm: self.ymm.min(other.ymm),
            zmm: self.zmm.min(other.zmm),
            mask: self.mask.min(other.mask),
        }
    }

    /// Check if all components are zero.
    pub fn is_zero(&self) -> bool {
        self.gpr == 0
            && self.gpr32 == 0
            && self.xmm == 0
            && self.ymm == 0
            && self.zmm == 0
            && self.mask == 0
    }
}

impl std::fmt::Display for RegPressure {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "GPR:{}/{}, XMM:{}/{}, YMM:{}/{}, ZMM:{}/{}, Mask:{}/{}",
            self.gpr,
            MAX_GPR_AVAILABLE,
            self.xmm,
            MAX_XMM_AVAILABLE,
            self.ymm,
            MAX_YMM_AVAILABLE,
            self.zmm,
            MAX_ZMM_AVAILABLE,
            self.mask,
            MAX_MASK_AVAILABLE
        )
    }
}

// ============================================================================
// Per-Block Pressure Tracking
// ============================================================================

/// Register pressure set for a single basic block.
#[derive(Debug, Clone)]
pub struct BlockPressureSet {
    /// Block ID.
    pub block_id: u32,
    /// Maximum register pressure observed at any point within the block.
    pub max_pressure: RegPressure,
    /// Register pressure at entry to the block (after phis and prologue).
    pub entry_pressure: RegPressure,
    /// Register pressure at exit from the block.
    pub exit_pressure: RegPressure,
    /// Number of instructions in the block.
    pub instruction_count: u32,
    /// Number of pressure-sensitive instructions (those on the critical path).
    pub pressure_sensitive_count: u32,
    /// The loop depth of this block (0 = not in a loop).
    pub loop_depth: u32,
    /// Set of live-out registers from this block.
    pub live_out_regs: HashSet<u32>,
    /// Set of live-in registers into this block.
    pub live_in_regs: HashSet<u32>,
}

impl BlockPressureSet {
    pub fn new(block_id: u32) -> Self {
        BlockPressureSet {
            block_id,
            max_pressure: RegPressure::zero(),
            entry_pressure: RegPressure::zero(),
            exit_pressure: RegPressure::zero(),
            instruction_count: 0,
            pressure_sensitive_count: 0,
            loop_depth: 0,
            live_out_regs: HashSet::new(),
            live_in_regs: HashSet::new(),
        }
    }

    /// Check if this block has high register pressure.
    pub fn has_high_pressure(&self) -> bool {
        self.max_pressure.is_high_pressure()
    }

    /// Check if this block has critical register pressure.
    pub fn has_critical_pressure(&self) -> bool {
        self.max_pressure.is_critical_pressure()
    }
}

// ============================================================================
// Pressure Change Descriptor
// ============================================================================

/// Describes how much a single instruction changes register pressure.
#[derive(Debug, Clone, Copy)]
pub struct PressureChange {
    /// Change in GPR pressure (positive = increase, negative = decrease).
    pub delta_gpr: i32,
    /// Change in XMM pressure.
    pub delta_xmm: i32,
    /// Change in YMM pressure.
    pub delta_ymm: i32,
    /// Change in ZMM pressure.
    pub delta_zmm: i32,
    /// Change in mask register pressure.
    pub delta_mask: i32,
}

impl PressureChange {
    pub fn zero() -> Self {
        PressureChange {
            delta_gpr: 0,
            delta_xmm: 0,
            delta_ymm: 0,
            delta_zmm: 0,
            delta_mask: 0,
        }
    }

    /// Apply this change to a RegPressure snapshot.
    pub fn apply(&self, pressure: &mut RegPressure) {
        pressure.gpr = (pressure.gpr as i32 + self.delta_gpr).max(0) as u32;
        pressure.xmm = (pressure.xmm as i32 + self.delta_xmm).max(0) as u32;
        pressure.ymm = (pressure.ymm as i32 + self.delta_ymm).max(0) as u32;
        pressure.zmm = (pressure.zmm as i32 + self.delta_zmm).max(0) as u32;
        pressure.mask = (pressure.mask as i32 + self.delta_mask).max(0) as u32;
    }

    /// Check if this change increases pressure (net positive).
    pub fn increases_pressure(&self) -> bool {
        self.delta_gpr > 0
            || self.delta_xmm > 0
            || self.delta_ymm > 0
            || self.delta_zmm > 0
            || self.delta_mask > 0
    }

    /// Check if this change decreases pressure (net negative).
    pub fn decreases_pressure(&self) -> bool {
        self.delta_gpr < 0
            || self.delta_xmm < 0
            || self.delta_ymm < 0
            || self.delta_zmm < 0
            || self.delta_mask < 0
    }
}

// ============================================================================
// Pressure Difference Across CFG Edges
// ============================================================================

/// Captures the register pressure difference across a CFG edge.
#[derive(Debug, Clone)]
pub struct PressureDiff {
    /// Source block ID.
    pub from_block: u32,
    /// Destination block ID.
    pub to_block: u32,
    /// Difference in GPR pressure (to - from).
    pub gpr_diff: i32,
    /// Difference in XMM pressure.
    pub xmm_diff: i32,
    /// Difference in YMM pressure.
    pub ymm_diff: i32,
    /// Difference in ZMM pressure.
    pub zmm_diff: i32,
    /// Difference in mask pressure.
    pub mask_diff: i32,
}

impl PressureDiff {
    /// Compute the pressure difference across an edge.
    pub fn compute(from: &BlockPressureSet, to: &BlockPressureSet) -> Self {
        PressureDiff {
            from_block: from.block_id,
            to_block: to.block_id,
            gpr_diff: to.entry_pressure.gpr as i32 - from.exit_pressure.gpr as i32,
            xmm_diff: to.entry_pressure.xmm as i32 - from.exit_pressure.xmm as i32,
            ymm_diff: to.entry_pressure.ymm as i32 - from.exit_pressure.ymm as i32,
            zmm_diff: to.entry_pressure.zmm as i32 - from.exit_pressure.zmm as i32,
            mask_diff: to.entry_pressure.mask as i32 - from.exit_pressure.mask as i32,
        }
    }

    /// Check if pressure increases across this edge.
    pub fn pressure_increases(&self) -> bool {
        self.gpr_diff > 0
            || self.xmm_diff > 0
            || self.ymm_diff > 0
            || self.zmm_diff > 0
            || self.mask_diff > 0
    }

    /// Total weighted pressure increase across all register classes.
    pub fn total_increase(&self) -> f64 {
        let mut total = 0.0_f64;
        if self.gpr_diff > 0 {
            total += self.gpr_diff as f64 / MAX_GPR_AVAILABLE as f64;
        }
        if self.xmm_diff > 0 {
            total += self.xmm_diff as f64 / MAX_XMM_AVAILABLE as f64;
        }
        if self.ymm_diff > 0 {
            total += self.ymm_diff as f64 / MAX_YMM_AVAILABLE as f64;
        }
        if self.zmm_diff > 0 {
            total += self.zmm_diff as f64 / MAX_ZMM_AVAILABLE as f64;
        }
        if self.mask_diff > 0 {
            total += self.mask_diff as f64 / MAX_MASK_AVAILABLE as f64;
        }
        total
    }
}

// ============================================================================
// Instruction Scheduling Priority (Pressure-Aware)
// ============================================================================

/// A scheduling candidate with pressure-aware priority.
#[derive(Debug, Clone)]
pub struct SchedCandidate {
    /// Instruction index within the block.
    pub instr_index: usize,
    /// The pressure change this instruction causes.
    pub pressure_change: PressureChange,
    /// The current pressure before scheduling this instruction.
    pub current_pressure: RegPressure,
    /// Execution latency (for critical path).
    pub latency: u32,
    /// Whether this instruction is on the critical path.
    pub on_critical_path: bool,
    /// Number of dependent instructions.
    pub num_dependents: u32,
    /// Whether scheduling this would exceed pressure limits.
    pub would_spill: bool,
}

impl SchedCandidate {
    /// Compute a scheduling priority score.
    /// Lower score = higher priority (scheduled earlier).
    pub fn priority_score(&self) -> f64 {
        let pressure_penalty = if self.would_spill {
            1000.0
        } else if self.pressure_change.increases_pressure() {
            // Penalize instructions that increase pressure.
            let max_ratio = self.current_pressure.max_pressure_ratio();
            if max_ratio > HIGH_PRESSURE_THRESHOLD {
                10.0 * (max_ratio - HIGH_PRESSURE_THRESHOLD)
            } else {
                0.0
            }
        } else if self.pressure_change.decreases_pressure() {
            // Reward instructions that decrease pressure.
            -5.0
        } else {
            0.0
        };

        let critical_path_bonus = if self.on_critical_path { -3.0 } else { 0.0 };
        let latency_penalty = self.latency as f64 * 0.1;

        pressure_penalty + critical_path_bonus + latency_penalty
    }
}

impl PartialEq for SchedCandidate {
    fn eq(&self, other: &Self) -> bool {
        self.instr_index == other.instr_index
    }
}

impl Eq for SchedCandidate {}

impl PartialOrd for SchedCandidate {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for SchedCandidate {
    fn cmp(&self, other: &Self) -> Ordering {
        // Lower priority score = higher scheduling priority.
        // BinaryHeap is a max-heap, so we reverse the comparison.
        other
            .priority_score()
            .partial_cmp(&self.priority_score())
            .unwrap_or(Ordering::Equal)
    }
}

// ============================================================================
// Pressure-Based Spill Decision
// ============================================================================

/// A decision about whether to spill a register based on pressure.
#[derive(Debug, Clone)]
pub struct SpillDecision {
    /// Whether to spill.
    pub should_spill: bool,
    /// The register class that is over pressure.
    pub class: RegClass,
    /// Current pressure for that class.
    pub current_pressure: u32,
    /// Maximum allowed pressure for that class.
    pub max_allowed: u32,
    /// How much to reduce pressure by (number of registers to spill).
    pub spill_count: u32,
    /// The estimated cost of spilling vs keeping in register.
    pub cost_savings: f64,
    /// Reason for the decision.
    pub reason: String,
}

impl SpillDecision {
    /// Create a "no spill" decision.
    pub fn no_spill() -> Self {
        SpillDecision {
            should_spill: false,
            class: GPR64,
            current_pressure: 0,
            max_allowed: 0,
            spill_count: 0,
            cost_savings: 0.0,
            reason: "pressure within limits".to_string(),
        }
    }

    /// Create a spill decision.
    pub fn spill(
        class: RegClass,
        current: u32,
        max_allowed: u32,
        count: u32,
        reason: impl Into<String>,
    ) -> Self {
        SpillDecision {
            should_spill: true,
            class,
            current_pressure: current,
            max_allowed,
            spill_count: count,
            cost_savings: 0.0,
            reason: reason.into(),
        }
    }
}

// ============================================================================
// Loop Pressure Tracking
// ============================================================================

/// Tracks register pressure through a loop nest.
#[derive(Debug, Clone)]
pub struct LoopPressure {
    /// The header block ID of the loop.
    pub header_id: u32,
    /// All block IDs in the loop.
    pub blocks: HashSet<u32>,
    /// Maximum pressure at any point in the loop body.
    pub max_pressure: RegPressure,
    /// Average pressure across the loop body.
    pub avg_pressure: RegPressure,
    /// Pressure at the loop header (pre-header).
    pub header_pressure: RegPressure,
    /// Pressure at the loop exit.
    pub exit_pressure: RegPressure,
    /// Loop depth (nesting level).
    pub depth: u32,
    /// Number of instructions in the loop.
    pub instr_count: u32,
    /// Whether this loop has high pressure.
    pub is_high_pressure: bool,
    /// Pressure spikes — points where pressure suddenly increases.
    pub pressure_spikes: Vec<(u32, RegPressure)>,
}

impl LoopPressure {
    pub fn new(header_id: u32, depth: u32) -> Self {
        LoopPressure {
            header_id,
            blocks: HashSet::new(),
            max_pressure: RegPressure::zero(),
            avg_pressure: RegPressure::zero(),
            header_pressure: RegPressure::zero(),
            exit_pressure: RegPressure::zero(),
            depth,
            instr_count: 0,
            is_high_pressure: false,
            pressure_spikes: Vec::new(),
        }
    }

    /// Update the loop pressure with a block's pressure.
    pub fn update(&mut self, block: &BlockPressureSet) {
        self.max_pressure = self.max_pressure.max(&block.max_pressure);
        self.instr_count += block.instruction_count;
        self.is_high_pressure = self.max_pressure.is_high_pressure();
    }

    /// Register a pressure spike at a specific instruction index.
    pub fn record_spike(&mut self, instr_index: u32, pressure: RegPressure) {
        self.pressure_spikes.push((instr_index, pressure));
    }
}

// ============================================================================
// X86RegPressure — main pressure tracker and reducer
// ============================================================================

/// Tracks register pressure across basic blocks, provides pressure-aware
/// scheduling, makes pressure-based spill decisions, and tracks pressure
/// through loops and across CFG edges.
pub struct X86RegPressure {
    /// Per-block pressure sets.
    pub block_pressure: HashMap<u32, BlockPressureSet>,
    /// Pressure differences across CFG edges.
    pub edge_diffs: Vec<PressureDiff>,
    /// Loop pressure tracking.
    pub loop_pressures: Vec<LoopPressure>,
    /// Loop headers and their block sets.
    pub loops: HashMap<u32, HashSet<u32>>,
    /// Maximum pressure observed across the entire function.
    pub function_max_pressure: RegPressure,
    /// Spill decisions made.
    pub spill_decisions: Vec<SpillDecision>,
    /// Total number of spills performed.
    pub total_spills: u32,
}

impl X86RegPressure {
    /// Create a new pressure tracker.
    pub fn new() -> Self {
        X86RegPressure {
            block_pressure: HashMap::new(),
            edge_diffs: Vec::new(),
            loop_pressures: Vec::new(),
            loops: HashMap::new(),
            function_max_pressure: RegPressure::zero(),
            spill_decisions: Vec::new(),
            total_spills: 0,
        }
    }

    /// Compute register pressure for all blocks in a function.
    pub fn compute_pressure(&mut self, mf: &MachineFunction) {
        self.block_pressure.clear();

        for block in &mf.blocks {
            let mut bp = BlockPressureSet::new(block.id);
            bp.instruction_count = block.instructions.len() as u32;
            bp.live_in_regs = self.live_in_for_block(mf, block.id);
            bp.live_out_regs = self.live_out_for_block(mf, block.id);

            // Compute entry pressure from live-ins.
            self.compute_pressure_from_live_set(&mut bp.entry_pressure, &bp.live_in_regs);

            // Track pressure through each instruction in the block.
            let mut current = bp.entry_pressure;
            for (i, instr) in block.instructions.iter().enumerate() {
                let change = self.compute_pressure_change(instr);
                change.apply(&mut current);

                // Track maximum.
                bp.max_pressure = bp.max_pressure.max(&current);

                // Check for pressure spikes.
                if current.is_high_pressure() {
                    bp.pressure_sensitive_count += 1;
                }
            }

            bp.exit_pressure = current;

            self.function_max_pressure = self.function_max_pressure.max(&bp.max_pressure);
            self.block_pressure.insert(block.id, bp);
        }
    }

    /// Compute entry live-in registers for a block (simplified).
    fn live_in_for_block(&self, _mf: &MachineFunction, block_id: u32) -> HashSet<u32> {
        // In a full implementation, this would compute actual liveness.
        // For now, return the live-out of all predecessors.
        let mut live_in: HashSet<u32> = HashSet::new();

        if let Some(bp) = self.block_pressure.get(&block_id) {
            for &reg in &bp.live_out_regs {
                live_in.insert(reg);
            }
        }

        live_in
    }

    /// Compute exit live-out registers for a block (simplified).
    fn live_out_for_block(&self, _mf: &MachineFunction, _block_id: u32) -> HashSet<u32> {
        // In a full implementation, this would compute actual liveness.
        HashSet::new()
    }

    /// Compute pressure from a live register set.
    fn compute_pressure_from_live_set(&self, pressure: &mut RegPressure, live_set: &HashSet<u32>) {
        for &reg in live_set {
            // Approximate: register numbers map to classes.
            if reg < 16 {
                pressure.gpr += 1;
            } else if reg < 32 {
                pressure.xmm += 1;
            } else if reg < 48 {
                pressure.ymm += 1;
            } else if reg < 80 {
                pressure.zmm += 1;
            } else if reg < 88 {
                pressure.mask += 1;
            }
        }
    }

    /// Compute the pressure change caused by an instruction.
    pub fn compute_pressure_change(&self, instr: &MachineInstr) -> PressureChange {
        let mut defs: Vec<RegClass> = Vec::new();
        let mut uses: Vec<RegClass> = Vec::new();

        for operand in &instr.operands {
            match operand {
                MachineOperand::PhysReg(preg) => {
                    let class = self.classify_register(*preg);
                    // First operand is typically the def; rest are uses.
                    if defs.is_empty() && !uses.is_empty() {
                        // This is a simplification; real analysis is more nuanced.
                    }
                    uses.push(class);
                }
                MachineOperand::Reg(_) => {
                    // Virtual register — assume GPR.
                    uses.push(GPR64);
                }
                _ => {}
            }
        }

        let mut change = PressureChange::zero();

        // Definitions decrease pressure (register becomes free after this point).
        for class in &defs {
            match class {
                GPR64 | GPR32 | GPR16 | GPR8 => change.delta_gpr -= 1,
                XMM => change.delta_xmm -= 1,
                YMM => change.delta_ymm -= 1,
                ZMM => change.delta_zmm -= 1,
                KMASK => change.delta_mask -= 1,
                _ => {}
            }
        }

        // Uses increase pressure (register is live from this point).
        for class in &uses {
            match class {
                GPR64 | GPR32 | GPR16 | GPR8 => change.delta_gpr += 1,
                XMM => change.delta_xmm += 1,
                YMM => change.delta_ymm += 1,
                ZMM => change.delta_zmm += 1,
                KMASK => change.delta_mask += 1,
                _ => {}
            }
        }

        change
    }

    /// Classify a physical register number into a register class.
    fn classify_register(&self, preg: u32) -> RegClass {
        // Simplified classification based on register number ranges.
        if preg < 16 {
            GPR64
        } else if preg < 32 {
            XMM
        } else if preg < 48 {
            YMM
        } else if preg < 80 {
            ZMM
        } else if preg < 88 {
            KMASK
        } else {
            GPR64 // default
        }
    }

    /// Compute pressure differences across all CFG edges.
    pub fn compute_edge_diffs(&mut self, mf: &MachineFunction) {
        self.edge_diffs.clear();

        for block in &mf.blocks {
            let from_bp = match self.block_pressure.get(&block.id) {
                Some(bp) => bp,
                None => continue,
            };

            for &succ_id in &block.successors {
                let to_bp = match self.block_pressure.get(&succ_id) {
                    Some(bp) => bp,
                    None => continue,
                };
                let diff = PressureDiff::compute(from_bp, to_bp);
                self.edge_diffs.push(diff);
            }
        }
    }

    /// Schedule instructions within a block to reduce pressure peaks.
    /// Returns a reordered list of instruction indices.
    pub fn schedule_for_pressure(
        &self,
        block: &MachineBasicBlock,
        block_pressure: &BlockPressureSet,
    ) -> Vec<usize> {
        let mut scheduled: Vec<usize> = Vec::new();
        let mut ready: BinaryHeap<SchedCandidate> = BinaryHeap::new();
        let mut current_pressure = block_pressure.entry_pressure;
        let mut remaining: HashSet<usize> = (0..block.instructions.len()).collect();

        while !remaining.is_empty() {
            // Find all instructions whose operands are ready.
            // In a full implementation, we'd check data dependencies.
            // Here we approximate with a simple greedy strategy.

            // Compute current pressure.
            let max_ratio = current_pressure.max_pressure_ratio();

            // Prioritize: schedule pressure-decreasing instructions first.
            let mut best_idx: Option<usize> = None;
            let mut best_score: f64 = f64::MAX;

            for &idx in &remaining {
                let instr = &block.instructions[idx];
                let change = self.compute_pressure_change(instr);
                let mut test_pressure = current_pressure;
                change.apply(&mut test_pressure);

                let would_spill = test_pressure.is_critical_pressure();
                let score = if change.decreases_pressure() {
                    // Strongly prefer decreases.
                    -10.0
                } else if would_spill {
                    100.0
                } else if change.increases_pressure() {
                    max_ratio * 5.0
                } else {
                    1.0
                };

                if score < best_score {
                    best_score = score;
                    best_idx = Some(idx);
                }
            }

            if let Some(idx) = best_idx {
                scheduled.push(idx);
                remaining.remove(&idx);

                // Update pressure.
                let change = self.compute_pressure_change(&block.instructions[idx]);
                change.apply(&mut current_pressure);
            } else {
                // No candidates found; break to avoid infinite loop.
                break;
            }
        }

        scheduled
    }

    /// Make a pressure-based spill decision for a block.
    pub fn decide_spill(&self, block_id: u32) -> SpillDecision {
        let bp = match self.block_pressure.get(&block_id) {
            Some(bp) => bp,
            None => return SpillDecision::no_spill(),
        };

        // Check each register class for over-pressure.
        let classes: &[(RegClass, u32, u32, fn(&RegPressure) -> u32)] = &[
            (GPR64, MAX_GPR_AVAILABLE, bp.max_pressure.gpr, |p| p.gpr),
            (XMM, MAX_XMM_AVAILABLE, bp.max_pressure.xmm, |p| p.xmm),
            (YMM, MAX_YMM_AVAILABLE, bp.max_pressure.ymm, |p| p.ymm),
            (ZMM, MAX_ZMM_AVAILABLE, bp.max_pressure.zmm, |p| p.zmm),
            (KMASK, MAX_MASK_AVAILABLE, bp.max_pressure.mask, |p| p.mask),
        ];

        for &(class, max_allowed, current, _getter) in classes {
            if current >= max_allowed {
                let spill_count = current - max_allowed + 1;
                return SpillDecision::spill(
                    class,
                    current,
                    max_allowed,
                    spill_count,
                    format!(
                        "{:?} pressure {} exceeds max {}",
                        class, current, max_allowed
                    ),
                );
            }

            // Also spill if pressure is critically high.
            if current as f64 / max_allowed as f64 >= CRITICAL_PRESSURE_THRESHOLD {
                let spill_count = 1;
                return SpillDecision::spill(
                    class,
                    current,
                    max_allowed,
                    spill_count,
                    format!("{:?} pressure at critical threshold", class),
                );
            }
        }

        SpillDecision::no_spill()
    }

    /// Detect and build loop pressure tracking from CFG structure.
    pub fn detect_loops(&mut self, mf: &MachineFunction) {
        self.loops.clear();
        self.loop_pressures.clear();

        // Find back edges by looking for successors with lower block IDs.
        for block in &mf.blocks {
            for &succ_id in &block.successors {
                if succ_id <= block.id {
                    // This is a back edge → block is a loop header.
                    let loop_blocks = self.collect_loop_blocks(mf, block.id, succ_id);
                    self.loops.insert(block.id, loop_blocks.clone());

                    let mut lp = LoopPressure::new(block.id, 1); // depth estimate
                    lp.blocks = loop_blocks;
                    self.loop_pressures.push(lp);
                }
            }
        }

        // Compute loop pressures from block pressures.
        for lp in &mut self.loop_pressures {
            for &block_id in &lp.blocks {
                if let Some(bp) = self.block_pressure.get(&block_id) {
                    lp.update(bp);
                }
            }
        }
    }

    /// Collect all blocks in a loop given a header and a back-edge source.
    fn collect_loop_blocks(
        &self,
        mf: &MachineFunction,
        header_id: u32,
        back_edge_src: u32,
    ) -> HashSet<u32> {
        let mut loop_blocks: HashSet<u32> = HashSet::new();
        let mut worklist: VecDeque<u32> = VecDeque::new();

        loop_blocks.insert(header_id);
        worklist.push_back(back_edge_src);

        while let Some(block_id) = worklist.pop_front() {
            if loop_blocks.insert(block_id) {
                // Add all predecessors except the header.
                if let Some(block) = mf.blocks.iter().find(|b| b.id == block_id) {
                    for &pred_id in &block.predecessors {
                        if pred_id != header_id && !loop_blocks.contains(&pred_id) {
                            worklist.push_back(pred_id);
                        }
                    }
                }
            }
        }

        loop_blocks
    }

    /// Find the edge with the highest pressure increase.
    pub fn find_highest_pressure_edge(&self) -> Option<&PressureDiff> {
        self.edge_diffs.iter().max_by(|a, b| {
            a.total_increase()
                .partial_cmp(&b.total_increase())
                .unwrap_or(Ordering::Equal)
        })
    }

    /// Get pressure summary for the entire function.
    pub fn function_summary(&self) -> String {
        format!(
            "Max pressure: {} | Blocks: {} | Edges with diffs: {} | Loops: {} | Spills: {}",
            self.function_max_pressure,
            self.block_pressure.len(),
            self.edge_diffs.len(),
            self.loop_pressures.len(),
            self.total_spills,
        )
    }

    /// Report blocks that exceed high pressure threshold.
    pub fn high_pressure_blocks(&self) -> Vec<u32> {
        self.block_pressure
            .iter()
            .filter(|(_, bp)| bp.has_high_pressure())
            .map(|(id, _)| *id)
            .collect()
    }

    /// Report blocks that exceed critical pressure threshold.
    pub fn critical_pressure_blocks(&self) -> Vec<u32> {
        self.block_pressure
            .iter()
            .filter(|(_, bp)| bp.has_critical_pressure())
            .map(|(id, _)| *id)
            .collect()
    }

    /// Dump a detailed pressure report for debugging.
    pub fn dump_report(&self) -> String {
        let mut report = String::new();
        report.push_str("=== X86 Register Pressure Report ===\n\n");

        report.push_str(&format!("Function max: {}\n", self.function_max_pressure));

        report.push_str("\n--- Per-Block Pressure ---\n");
        for (id, bp) in &self.block_pressure {
            report.push_str(&format!(
                "Block {}: max={}, entry={}, exit={}, instrs={}, pressure_sensitive={}\n",
                id,
                bp.max_pressure,
                bp.entry_pressure,
                bp.exit_pressure,
                bp.instruction_count,
                bp.pressure_sensitive_count,
            ));
        }

        report.push_str("\n--- Edge Pressure Differences ---\n");
        for diff in &self.edge_diffs {
            report.push_str(&format!(
                "Edge {}→{}: GPR:{:+}, XMM:{:+}, YMM:{:+}, ZMM:{:+}, Mask:{:+}\n",
                diff.from_block,
                diff.to_block,
                diff.gpr_diff,
                diff.xmm_diff,
                diff.ymm_diff,
                diff.zmm_diff,
                diff.mask_diff,
            ));
        }

        report.push_str("\n--- Loop Pressure ---\n");
        for lp in &self.loop_pressures {
            report.push_str(&format!(
                "Loop header={}, depth={}, max={}, blocks={}\n",
                lp.header_id,
                lp.depth,
                lp.max_pressure,
                lp.blocks.len(),
            ));
        }

        report.push_str("\n--- Spill Decisions ---\n");
        for sd in &self.spill_decisions {
            report.push_str(&format!(
                "  {:?} pressure {} / {} → {} (reason: {})\n",
                sd.class,
                sd.current_pressure,
                sd.max_allowed,
                if sd.should_spill {
                    format!("spill {}", sd.spill_count)
                } else {
                    "no spill".to_string()
                },
                sd.reason,
            ));
        }

        report
    }

    /// Reset all state for a new function.
    pub fn reset(&mut self) {
        self.block_pressure.clear();
        self.edge_diffs.clear();
        self.loop_pressures.clear();
        self.loops.clear();
        self.function_max_pressure = RegPressure::zero();
        self.spill_decisions.clear();
        self.total_spills = 0;
    }
}

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

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

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

    #[test]
    fn test_reg_pressure_zero() {
        let p = RegPressure::zero();
        assert!(p.is_zero());
        assert!(!p.is_high_pressure());
        assert_eq!(p.max_pressure_ratio(), 0.0);
    }

    #[test]
    fn test_reg_pressure_high() {
        let mut p = RegPressure::zero();
        // Set GPR pressure above threshold.
        p.gpr = (MAX_GPR_AVAILABLE as f64 * HIGH_PRESSURE_THRESHOLD) as u32 + 1;
        assert!(p.is_high_pressure());
        assert!(!p.is_critical_pressure());
    }

    #[test]
    fn test_reg_pressure_critical() {
        let mut p = RegPressure::zero();
        p.gpr = MAX_GPR_AVAILABLE;
        assert!(p.is_critical_pressure());
        assert!(p.is_high_pressure());
    }

    #[test]
    fn test_reg_pressure_add_sub() {
        let a = RegPressure {
            gpr: 5,
            gpr32: 0,
            xmm: 3,
            ymm: 2,
            zmm: 1,
            mask: 0,
        };
        let b = RegPressure {
            gpr: 2,
            gpr32: 0,
            xmm: 1,
            ymm: 1,
            zmm: 0,
            mask: 1,
        };

        let sum = a.add(&b);
        assert_eq!(sum.gpr, 7);
        assert_eq!(sum.xmm, 4);

        let diff = a.sub(&b);
        assert_eq!(diff.gpr, 3);
        assert_eq!(diff.xmm, 2);
        assert_eq!(diff.zmm, 1);
        assert_eq!(diff.mask, 0); // saturating
    }

    #[test]
    fn test_reg_pressure_max_min() {
        let a = RegPressure {
            gpr: 5,
            gpr32: 0,
            xmm: 1,
            ymm: 0,
            zmm: 0,
            mask: 0,
        };
        let b = RegPressure {
            gpr: 3,
            gpr32: 0,
            xmm: 7,
            ymm: 0,
            zmm: 0,
            mask: 0,
        };

        let max = a.max(&b);
        assert_eq!(max.gpr, 5);
        assert_eq!(max.xmm, 7);

        let min = a.min(&b);
        assert_eq!(min.gpr, 3);
        assert_eq!(min.xmm, 1);
    }

    #[test]
    fn test_reg_pressure_display() {
        let p = RegPressure {
            gpr: 3,
            gpr32: 0,
            xmm: 0,
            ymm: 0,
            zmm: 0,
            mask: 0,
        };
        let s = format!("{}", p);
        assert!(s.contains("GPR:3/"));
    }

    #[test]
    fn test_pressure_change_apply() {
        let mut p = RegPressure::zero();
        let change = PressureChange {
            delta_gpr: 3,
            delta_xmm: -1,
            delta_ymm: 0,
            delta_zmm: 2,
            delta_mask: 0,
        };
        change.apply(&mut p);
        assert_eq!(p.gpr, 3);
        assert_eq!(p.xmm, 0); // negative clamped to 0
        assert_eq!(p.zmm, 2);
    }

    #[test]
    fn test_pressure_change_increases() {
        let inc = PressureChange {
            delta_gpr: 1,
            delta_xmm: 0,
            delta_ymm: 0,
            delta_zmm: 0,
            delta_mask: 0,
        };
        assert!(inc.increases_pressure());
        assert!(!inc.decreases_pressure());

        let dec = PressureChange {
            delta_gpr: -1,
            delta_xmm: 0,
            delta_ymm: 0,
            delta_zmm: 0,
            delta_mask: 0,
        };
        assert!(!dec.increases_pressure());
        assert!(dec.decreases_pressure());
    }

    #[test]
    fn test_block_pressure_set() {
        let mut bp = BlockPressureSet::new(42);
        assert_eq!(bp.block_id, 42);
        assert!(!bp.has_high_pressure());

        bp.max_pressure.gpr = MAX_GPR_AVAILABLE;
        assert!(bp.has_critical_pressure());
        assert!(bp.has_high_pressure());
    }

    #[test]
    fn test_pressure_diff_computation() {
        let mut from = BlockPressureSet::new(0);
        from.exit_pressure.gpr = 5;
        from.exit_pressure.xmm = 2;

        let mut to = BlockPressureSet::new(1);
        to.entry_pressure.gpr = 8;
        to.entry_pressure.xmm = 1;

        let diff = PressureDiff::compute(&from, &to);
        assert_eq!(diff.gpr_diff, 3);
        assert_eq!(diff.xmm_diff, -1);
        assert!(diff.pressure_increases());
    }

    #[test]
    fn test_spill_decision_no_spill() {
        let d = SpillDecision::no_spill();
        assert!(!d.should_spill);
        assert_eq!(d.spill_count, 0);
    }

    #[test]
    fn test_spill_decision_spill() {
        let d = SpillDecision::spill(GPR64, 15, 14, 2, "too high");
        assert!(d.should_spill);
        assert_eq!(d.spill_count, 2);
        assert_eq!(d.class, GPR64);
    }

    #[test]
    fn test_x86_reg_pressure_new() {
        let xrp = X86RegPressure::new();
        assert!(xrp.block_pressure.is_empty());
        assert!(xrp.edge_diffs.is_empty());
        assert!(xrp.function_max_pressure.is_zero());
    }

    #[test]
    fn test_compute_pressure_change() {
        let xrp = X86RegPressure::new();
        let instr = MachineInstr::new(0x01);
        let change = xrp.compute_pressure_change(&instr);
        // With no operands, should be zero change.
        assert_eq!(change.delta_gpr, 0);
        assert_eq!(change.delta_xmm, 0);
    }

    #[test]
    fn test_classify_register() {
        let xrp = X86RegPressure::new();
        assert_eq!(xrp.classify_register(0), GPR64); // RAX
        assert_eq!(xrp.classify_register(15), GPR64); // R15
        assert_eq!(xrp.classify_register(16), XMM); // XMM0
    }

    #[test]
    fn test_function_summary() {
        let mut xrp = X86RegPressure::new();
        let bp = BlockPressureSet::new(0);
        xrp.block_pressure.insert(0, bp);
        let summary = xrp.function_summary();
        assert!(summary.contains("Blocks: 1"));
    }

    #[test]
    fn test_reset() {
        let mut xrp = X86RegPressure::new();
        xrp.function_max_pressure.gpr = 5;
        xrp.total_spills = 3;

        xrp.reset();
        assert!(xrp.function_max_pressure.is_zero());
        assert_eq!(xrp.total_spills, 0);
    }

    #[test]
    fn test_sched_candidate_ordering() {
        let low = SchedCandidate {
            instr_index: 1,
            pressure_change: PressureChange {
                delta_gpr: -1,
                delta_xmm: 0,
                delta_ymm: 0,
                delta_zmm: 0,
                delta_mask: 0,
            },
            current_pressure: RegPressure::zero(),
            latency: 1,
            on_critical_path: false,
            num_dependents: 0,
            would_spill: false,
        };

        let high = SchedCandidate {
            instr_index: 2,
            pressure_change: PressureChange {
                delta_gpr: 3,
                delta_xmm: 0,
                delta_ymm: 0,
                delta_zmm: 0,
                delta_mask: 0,
            },
            current_pressure: RegPressure::zero(),
            latency: 3,
            on_critical_path: false,
            num_dependents: 0,
            would_spill: false,
        };

        // Low score → higher priority.
        assert!(low.priority_score() < high.priority_score());
    }

    #[test]
    fn test_schedule_for_pressure() {
        let xrp = X86RegPressure::new();
        let mut block = MachineBasicBlock::new(0, "test");

        // Add some dummy instructions.
        block.instructions.push(MachineInstr::new(0x01));
        block.instructions.push(MachineInstr::new(0x02));
        block.instructions.push(MachineInstr::new(0x03));

        let bp = BlockPressureSet::new(0);
        let scheduled = xrp.schedule_for_pressure(&block, &bp);

        // Should schedule all instructions.
        assert_eq!(scheduled.len(), 3);
    }

    #[test]
    fn test_loop_pressure_update() {
        let mut lp = LoopPressure::new(0, 1);
        let mut bp = BlockPressureSet::new(1);
        bp.max_pressure.gpr = 5;
        bp.max_pressure.xmm = 3;
        bp.instruction_count = 10;

        lp.update(&bp);
        assert_eq!(lp.max_pressure.gpr, 5);
        assert_eq!(lp.instr_count, 10);
    }

    #[test]
    fn test_high_pressure_blocks() {
        let mut xrp = X86RegPressure::new();

        let mut bp1 = BlockPressureSet::new(1);
        bp1.max_pressure.gpr = MAX_GPR_AVAILABLE;
        xrp.block_pressure.insert(1, bp1);

        let mut bp2 = BlockPressureSet::new(2);
        bp2.max_pressure.gpr = 1;
        xrp.block_pressure.insert(2, bp2);

        let high = xrp.high_pressure_blocks();
        assert!(high.contains(&1));
        assert!(!high.contains(&2));
    }

    #[test]
    fn test_pressure_diff_total_increase() {
        let diff = PressureDiff {
            from_block: 0,
            to_block: 1,
            gpr_diff: 5,
            xmm_diff: -2,
            ymm_diff: 0,
            zmm_diff: 0,
            mask_diff: 0,
        };
        let total = diff.total_increase();
        assert!(total > 0.0);
    }
}