llvm-native-core-ext 0.1.0

//! Machine Scheduler — instruction scheduling for the target pipeline.
//! Clean-room behavioral reconstruction.
//!
//! @llvm_behavior: The MachineScheduler reorders machine instructions
//! within a basic block to maximize instruction-level parallelism (ILP)
//! and minimize pipeline stalls. It uses a dependence graph and a
//! resource model of the target CPU to schedule instructions.
//!
//! Algorithm (list scheduling):
//! 1. Build a dependence graph from the machine instructions
//! 2. Compute the critical path (longest latency chain) for each node
//! 3. Repeatedly select ready instructions (all predecessors scheduled)
//!    based on a heuristic (e.g., critical path height)
//! 4. Assign each instruction to a cycle, respecting resource constraints
//! 5. Emit the reordered instruction sequence
//!
//! The resource model tracks:
//! - Issue width: max instructions per cycle
//! - Resource types: ALU, Load, Store, Branch, FPU, etc.
//! - Resource counts: how many of each resource are available
//! - Instruction latencies: how many cycles each instruction takes
//!
//! Target-specific resource models are loaded based on the target triple.

use llvm_native_core::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand};
use std::collections::{HashMap, HashSet, VecDeque};

// ============================================================================
// Resource Model
// ============================================================================

/// A hardware resource (functional unit) in the target CPU.
#[derive(Debug, Clone)]
pub struct Resource {
    /// Name of the resource (e.g., "ALU0", "LoadUnit", "FPAdd").
    pub name: String,
    /// Number of instances of this resource available per cycle.
    pub count: u32,
}

/// Resource model describing the target CPU's execution pipeline.
#[derive(Debug, Clone)]
pub struct ResourceModel {
    /// Maximum number of instructions that can be issued per cycle.
    pub issue_width: u32,
    /// Available hardware resources.
    pub resources: Vec<Resource>,
    /// Instruction latencies: opcode → latency in cycles.
    pub instruction_latencies: HashMap<u32, u32>,
}

impl ResourceModel {
    /// Create a default resource model (generic OoO core).
    pub fn default_model() -> Self {
        let mut latencies = HashMap::new();
        // Default latencies for common opcodes
        latencies.insert(1, 1); // Simple ALU
        latencies.insert(2, 3); // Load
        latencies.insert(3, 1); // Store (dispatch)
        latencies.insert(4, 5); // FP add
        latencies.insert(5, 7); // FP mul
        latencies.insert(6, 12); // FP div
        latencies.insert(7, 1); // Branch

        Self {
            issue_width: 4,
            resources: vec![
                Resource {
                    name: "ALU".to_string(),
                    count: 4,
                },
                Resource {
                    name: "LoadUnit".to_string(),
                    count: 2,
                },
                Resource {
                    name: "StoreUnit".to_string(),
                    count: 1,
                },
                Resource {
                    name: "BranchUnit".to_string(),
                    count: 1,
                },
            ],
            instruction_latencies: latencies,
        }
    }

    /// Get the latency of an instruction by its opcode.
    pub fn get_latency(&self, opcode: u32) -> u32 {
        self.instruction_latencies
            .get(&opcode)
            .copied()
            .unwrap_or(1)
    }
}

// ============================================================================
// Dependence Graph (for scheduling)
// ============================================================================

/// A node in the scheduling dependence graph.
#[derive(Debug, Clone)]
struct SchedNode {
    /// Index of the original instruction in the machine basic block.
    pub instr_idx: usize,
    /// Opcode of the instruction.
    pub opcode: u32,
    /// Latency of this instruction.
    pub latency: u32,
    /// Critical path length from this node to the end.
    pub critical_path: u32,
    /// Successors (instructions that depend on this one).
    pub successors: Vec<usize>,
    /// Predecessors (instructions this one depends on).
    pub predecessors: Vec<usize>,
    /// Whether this instruction has been scheduled.
    pub scheduled: bool,
    /// Number of unscheduled predecessors.
    pub unscheduled_preds: usize,
}

/// Scheduling dependence graph.
#[derive(Debug, Clone)]
pub struct DepGraph {
    /// Nodes indexed by instruction index.
    pub nodes: Vec<SchedNode>,
    /// Number of nodes.
    pub node_count: usize,
}

impl DepGraph {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            node_count: 0,
        }
    }
}

// ============================================================================
// Machine Scheduler Pass
// ============================================================================

/// MachineScheduler — instruction scheduler for a target pipeline.
pub struct MachineScheduler {
    /// Target triple string.
    pub target: String,
    /// Resource model for the target CPU.
    pub resource_model: ResourceModel,
    /// Number of instructions reordered.
    pub reordered: usize,
}

impl MachineScheduler {
    /// Create a new MachineScheduler for a target.
    pub fn new(target: &str) -> Self {
        Self {
            target: target.to_string(),
            resource_model: ResourceModel::default_model(),
            reordered: 0,
        }
    }

    /// Schedule instructions in a machine function.
    ///
    /// Returns the total number of instructions whose position changed.
    pub fn schedule(&mut self, mf: &mut MachineFunction) -> usize {
        self.reordered = 0;

        let block_count = mf.blocks.len();
        for bb_idx in 0..block_count {
            let block = &mf.blocks[bb_idx];

            if block.instructions.len() < 2 {
                continue;
            }

            // Build dependence graph
            let graph = self.build_dependence_graph(&block.instructions);

            if graph.node_count < 2 {
                continue;
            }

            // Compute critical path
            let cp = self.compute_critical_path(&graph);

            // List schedule
            let schedule = self.list_schedule(&graph, &cp);

            // Compute resource conflicts (for debug/analysis)
            let _conflicts = self.compute_resource_conflicts(&schedule, &block.instructions);

            // Apply the schedule: reorder instructions
            let original_len = mf.blocks[bb_idx].instructions.len();
            if schedule.len() == original_len {
                let mut new_instructions = Vec::with_capacity(schedule.len());
                for &idx in &schedule {
                    if idx < mf.blocks[bb_idx].instructions.len() {
                        new_instructions.push(mf.blocks[bb_idx].instructions[idx].clone());
                    }
                }
                // Count reordered instructions
                let mut changed = 0;
                for (i, &sched_idx) in schedule.iter().enumerate() {
                    if sched_idx != i {
                        changed += 1;
                    }
                }
                mf.blocks[bb_idx].instructions = new_instructions;
                self.reordered += changed;
            }
        }

        self.reordered
    }

    // ========================================================================
    // Dependence graph construction
    // ========================================================================

    /// Build a dependence graph from a list of machine instructions.
    ///
    /// Nodes are instruction indices. Edges represent data dependencies:
    /// - RAW (Read-After-Write): producer → consumer
    /// - WAW (Write-After-Write): first writer → second writer (to same reg)
    /// - WAR (Write-After-Read): reader → writer (anti-dependence)
    pub fn build_dependence_graph(&self, instructions: &[MachineInstr]) -> DepGraph {
        let n = instructions.len();
        let mut graph = DepGraph::new();

        for (idx, mi) in instructions.iter().enumerate() {
            let node = SchedNode {
                instr_idx: idx,
                opcode: mi.opcode,
                latency: self.get_instruction_latency(mi),
                critical_path: 0,
                successors: Vec::new(),
                predecessors: Vec::new(),
                scheduled: false,
                unscheduled_preds: 0,
            };
            graph.nodes.push(node);
        }
        graph.node_count = n;

        // Build def-use chains
        // Map: register → (last_def_instruction_idx, last_use_instruction_idx)
        let mut last_def: HashMap<u64, usize> = HashMap::new();
        let mut last_use: HashMap<u64, Vec<usize>> = HashMap::new();

        for (idx, mi) in instructions.iter().enumerate() {
            // Hash the instruction for def/use analysis
            let hash = self.hash_instruction(mi);
            let def_regs = self.get_defined_regs(mi);
            let use_regs = self.get_used_regs(mi);

            // RAW dependence: for each used register, if there's a previous def
            for reg in &use_regs {
                let reg_key = Self::reg_to_key(reg);
                if let Some(&def_idx) = last_def.get(&reg_key) {
                    // RAW: def_idx → idx
                    if def_idx < idx {
                        graph.nodes[def_idx].successors.push(idx);
                        graph.nodes[idx].predecessors.push(def_idx);
                    }
                }
                // Track this use
                last_use.entry(reg_key).or_default().push(idx);
            }

            // WAW dependence: for each defined register, if there's a previous def
            for reg in &def_regs {
                let reg_key = Self::reg_to_key(reg);
                if let Some(&prev_def) = last_def.get(&reg_key) {
                    // WAW: prev_def → idx
                    if prev_def < idx {
                        graph.nodes[prev_def].successors.push(idx);
                        graph.nodes[idx].predecessors.push(prev_def);
                    }
                }
                // WAR: all previous uses of this register must complete before
                // this write
                if let Some(prev_uses) = last_use.get(&reg_key) {
                    for &use_idx in prev_uses {
                        if use_idx < idx {
                            graph.nodes[use_idx].successors.push(idx);
                            graph.nodes[idx].predecessors.push(use_idx);
                        }
                    }
                }
                last_def.insert(reg_key, idx);
                // Clear last uses after a new def
                last_use.remove(&reg_key);
            }
        }

        // Set unscheduled predecessor counts
        for node in &mut graph.nodes {
            node.unscheduled_preds = node.predecessors.len();
        }

        graph
    }

    /// Get the registers defined by a machine instruction.
    fn get_defined_regs(&self, mi: &MachineInstr) -> Vec<MachineOperand> {
        let mut defs = Vec::new();
        if let Some(def_vreg) = mi.def {
            defs.push(MachineOperand::Reg(def_vreg));
        }
        // Some instructions also define implicit registers
        defs
    }

    /// Get the registers used by a machine instruction.
    fn get_used_regs(&self, mi: &MachineInstr) -> Vec<MachineOperand> {
        mi.operands
            .iter()
            .filter(|op| matches!(op, MachineOperand::Reg(_) | MachineOperand::PhysReg(_)))
            .cloned()
            .collect()
    }

    /// Convert a register operand to a unique key for hashing.
    fn reg_to_key(op: &MachineOperand) -> u64 {
        match op {
            MachineOperand::Reg(vr) => *vr as u64,
            MachineOperand::PhysReg(pr) => (*pr as u64) + (1u64 << 32),
            _ => 0,
        }
    }

    /// Hash a machine instruction for identification.
    fn hash_instruction(&self, mi: &MachineInstr) -> u64 {
        let mut hash: u64 = mi.opcode as u64;
        for op in &mi.operands {
            hash = hash.wrapping_mul(31).wrapping_add(Self::reg_to_key(op));
        }
        if let Some(def) = mi.def {
            hash = hash.wrapping_mul(31).wrapping_add(def as u64);
        }
        hash
    }

    // ========================================================================
    // Critical path computation
    // ========================================================================

    /// Compute the critical path length from each node to the end.
    ///
    /// Uses a reverse topological traversal: the critical path of a node
    /// is its own latency plus the maximum critical path of its successors.
    pub fn compute_critical_path(&self, graph: &DepGraph) -> Vec<u32> {
        let n = graph.node_count;
        let mut cp = vec![0u32; n];

        // Process nodes in reverse order (approximate reverse topological)
        for idx in (0..n).rev() {
            let node_latency = graph.nodes[idx].latency;
            let mut max_succ_cp = 0u32;

            for &succ in &graph.nodes[idx].successors {
                if succ < n {
                    max_succ_cp = max_succ_cp.max(cp[succ]);
                }
            }

            cp[idx] = node_latency + max_succ_cp;
        }

        cp
    }

    // ========================================================================
    // List scheduling
    // ========================================================================

    /// Perform list scheduling on the dependence graph.
    ///
    /// Uses critical path height as the priority heuristic: instructions
    /// on the critical path are scheduled first to minimize total latency.
    ///
    /// Returns a vector of instruction indices in scheduled order.
    pub fn list_schedule(&self, graph: &DepGraph, cp: &[u32]) -> Vec<usize> {
        let n = graph.node_count;
        let mut schedule = Vec::with_capacity(n);

        // Track remaining unscheduled predecessors
        let mut unscheduled_preds: Vec<usize> = graph
            .nodes
            .iter()
            .map(|node| node.unscheduled_preds)
            .collect();

        // Ready queue: instructions whose predecessors are all scheduled
        let mut ready: Vec<usize> = (0..n).filter(|&i| unscheduled_preds[i] == 0).collect();

        while !ready.is_empty() {
            // Select the instruction with highest critical path
            ready.sort_by(|&a, &b| {
                cp[b].cmp(&cp[a]).then_with(|| a.cmp(&b)) // Tiebreaker: earlier original position
            });

            let selected = ready.remove(0);
            schedule.push(selected);

            // Update successors: decrement their unscheduled predecessor count
            for &succ in &graph.nodes[selected].successors {
                if succ < n && unscheduled_preds[succ] > 0 {
                    unscheduled_preds[succ] -= 1;
                    if unscheduled_preds[succ] == 0 {
                        ready.push(succ);
                    }
                }
            }
        }

        schedule
    }

    // ========================================================================
    // Resource conflict analysis
    // ========================================================================

    /// Compute resource conflicts for a given schedule.
    ///
    /// Returns a vector of cycle numbers where resource conflicts occur,
    /// represented as a bitmask of over-utilized resources.
    pub fn compute_resource_conflicts(
        &self,
        schedule: &[usize],
        instructions: &[MachineInstr],
    ) -> Vec<u64> {
        let mut conflicts = Vec::new();
        let resource_count = self.resource_model.resources.len();
        let mut current_cycle_resources = vec![0u32; resource_count];
        let mut current_cycle_issued = 0u32;
        let mut cycle = 0u64;

        for &instr_idx in schedule {
            if instr_idx >= instructions.len() {
                continue;
            }

            let mi = &instructions[instr_idx];

            // Check resource availability
            let mut resource_mask: u64 = 0;
            let instr_resources = self.get_instruction_resources(mi);

            for res_idx in &instr_resources {
                if *res_idx < resource_count {
                    if current_cycle_resources[*res_idx]
                        >= self.resource_model.resources[*res_idx].count
                    {
                        resource_mask |= 1u64 << res_idx;
                    }
                }
            }

            // Check issue width
            if current_cycle_issued >= self.resource_model.issue_width {
                // Advance to next cycle
                cycle += 1;
                current_cycle_resources.fill(0);
                current_cycle_issued = 0;
            }

            // Allocate resources
            for res_idx in &instr_resources {
                if *res_idx < resource_count {
                    current_cycle_resources[*res_idx] += 1;
                }
            }
            current_cycle_issued += 1;

            if resource_mask != 0 {
                conflicts.push(resource_mask);
            }
        }

        conflicts
    }

    /// Get the resource indices used by an instruction.
    fn get_instruction_resources(&self, mi: &MachineInstr) -> Vec<usize> {
        // Map opcode to resource type (simplified heuristic)
        let opcode = mi.opcode;

        // Simple resource classification based on common opcode ranges
        // In a real implementation, this would use the target's scheduling model
        match opcode {
            // Memory operations use LoadUnit or StoreUnit
            2 | 3 | 20 | 21 => {
                let mut res = Vec::new();
                res.push(1); // LoadUnit or StoreUnit
                             // Also use AGU (Address Generation Unit)
                res.push(0); // ALU for address calculation
                res
            }
            // Branch operations
            7 | 8 | 9 => vec![3], // BranchUnit
            // FP operations
            4 | 5 | 6 => vec![4], // FPU (simplified, would need more resources)
            // Default: ALU
            _ => vec![0], // ALU
        }
    }

    /// Get the latency of a machine instruction.
    pub fn get_instruction_latency(&self, instr: &MachineInstr) -> u32 {
        self.resource_model.get_latency(instr.opcode)
    }
}

impl Default for MachineScheduler {
    fn default() -> Self {
        Self::new("generic")
    }
}

// ============================================================================
// Scheduling Heuristics
// ============================================================================

/// HeuristicPriority computes a priority value for a scheduling candidate
/// based on multiple heuristics.
#[derive(Debug, Clone)]
pub struct HeuristicPriority {
    /// Critical path length from this node to the end.
    pub critical_path: i32,
    /// Number of successors (fanout).
    pub successor_count: u32,
    /// Register pressure impact (positive = reduces pressure).
    pub register_pressure_delta: i32,
    /// Resource demand (number of resources needed).
    pub resource_demand: u32,
    /// Combined priority score (higher = schedule first).
    pub combined_score: i64,
}

impl HeuristicPriority {
    /// Create a new heuristic priority with default values.
    pub fn new() -> Self {
        Self {
            critical_path: 0,
            successor_count: 0,
            register_pressure_delta: 0,
            resource_demand: 0,
            combined_score: 0,
        }
    }

    /// Compute the combined priority score.
    pub fn compute(&mut self) {
        // Weighted combination:
        // - Critical path (weight: 100)
        // - Successor count (weight: 10)
        // - Register pressure benefit (weight: 50)
        // - Resource demand penalty (weight: -5)
        self.combined_score = self.critical_path as i64 * 100
            + self.successor_count as i64 * 10
            + self.register_pressure_delta as i64 * 50
            - self.resource_demand as i64 * 5;
    }
}

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

/// CriticalPathScheduler prioritizes instructions on the longest
/// dependence chain to minimize overall schedule length.
pub struct CriticalPathScheduler {
    /// Critical path lengths per node.
    pub critical_paths: Vec<i32>,
    /// Whether paths have been computed.
    pub computed: bool,
}

impl CriticalPathScheduler {
    /// Create a new critical path scheduler.
    pub fn new() -> Self {
        Self {
            critical_paths: Vec::new(),
            computed: false,
        }
    }

    /// Compute critical path lengths from dependence graph.
    pub fn compute(&mut self, nodes: &[SchedNode]) {
        self.critical_paths = vec![-1; nodes.len()];

        // Bottom-up: compute critical path from each node to exit
        for i in (0..nodes.len()).rev() {
            let node = &nodes[i];
            let mut max_succ_path = 0;

            for &succ_idx in &node.successors {
                if succ_idx < self.critical_paths.len() {
                    max_succ_path = max_succ_path.max(self.critical_paths[succ_idx]);
                }
            }

            self.critical_paths[i] = max_succ_path + node.latency as i32;
        }

        self.computed = true;
    }

    /// Get the critical path length from a node.
    pub fn get_critical_path(&self, node_idx: usize) -> i32 {
        self.critical_paths.get(node_idx).copied().unwrap_or(0)
    }

    /// Compare two nodes by critical path (for priority queue).
    pub fn compare(&self, a: usize, b: usize) -> std::cmp::Ordering {
        let cp_a = self.get_critical_path(a);
        let cp_b = self.get_critical_path(b);
        cp_b.cmp(&cp_a) // Descending: longer path first
    }
}

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

// ============================================================================
// Resource Balancing Scheduler
// ============================================================================

/// ResourceBalancer tracks resource usage per cycle and tries to
/// balance utilization to avoid resource stalls.
pub struct ResourceBalancer {
    /// Resource usage per cycle (cycle -> resource_id -> count).
    pub usage_per_cycle: HashMap<i32, HashMap<u32, u32>>,
    /// Resources available per cycle.
    pub resources_available: HashMap<u32, u32>,
    /// Current cycle being scheduled.
    pub current_cycle: i32,
}

impl ResourceBalancer {
    /// Create a new resource balancer.
    pub fn new(resources: &[Resource]) -> Self {
        let mut available = HashMap::new();
        for res in resources {
            available.insert(res.name.parse::<u32>().unwrap_or(0), res.count);
        }
        Self {
            usage_per_cycle: HashMap::new(),
            resources_available: available,
            current_cycle: 0,
        }
    }

    /// Check if an instruction's resources are available at a given cycle.
    pub fn resources_available_at(&self, cycle: i32, resource_ids: &[u32]) -> bool {
        let usage = self.usage_per_cycle.get(&cycle);

        for &rid in resource_ids {
            let used = usage.and_then(|u| u.get(&rid)).copied().unwrap_or(0);
            let available = self.resources_available.get(&rid).copied().unwrap_or(0);

            if used >= available {
                return false;
            }
        }

        true
    }

    /// Reserve resources for an instruction at a cycle.
    pub fn reserve_resources(&mut self, cycle: i32, resource_ids: &[u32]) {
        let usage = self.usage_per_cycle.entry(cycle).or_default();
        for &rid in resource_ids {
            *usage.entry(rid).or_insert(0) += 1;
        }
    }

    /// Find the earliest cycle where resources are available.
    pub fn find_earliest_cycle(
        &self,
        start_cycle: i32,
        resource_ids: &[u32],
        max_cycle: i32,
    ) -> Option<i32> {
        for cycle in start_cycle..=max_cycle {
            if self.resources_available_at(cycle, resource_ids) {
                return Some(cycle);
            }
        }
        None
    }

    /// Get resource utilization at a cycle as a fraction.
    pub fn utilization_at(&self, cycle: i32) -> f64 {
        let usage = self.usage_per_cycle.get(&cycle);
        let total_avail: u32 = self.resources_available.values().sum();
        if total_avail == 0 {
            return 0.0;
        }
        let total_used: u32 = usage.map(|u| u.values().sum()).unwrap_or(0);
        total_used as f64 / total_avail as f64
    }
}

impl Default for ResourceBalancer {
    fn default() -> Self {
        Self::new(&[])
    }
}

// ============================================================================
// Register Pressure Reduction Scheduling
// ============================================================================

/// RegPressureScheduler attempts to reduce register pressure by
/// scheduling instructions that kill registers (last uses) earlier,
/// freeing up registers for other instructions.
pub struct RegPressureScheduler {
    /// Live register count per cycle.
    pub live_regs_per_cycle: HashMap<i32, usize>,
    /// Maximum register pressure observed.
    pub max_pressure: usize,
    /// Target register count.
    pub target_regs: usize,
}

impl RegPressureScheduler {
    /// Create a new register pressure scheduler.
    pub fn new(target_regs: usize) -> Self {
        Self {
            live_regs_per_cycle: HashMap::new(),
            max_pressure: 0,
            target_regs,
        }
    }

    /// Compute the register pressure impact of scheduling a node.
    pub fn pressure_impact(
        &self,
        cycle: i32,
        defs: &[u32],
        uses: &[u32],
        killed_regs: &[u32],
    ) -> i32 {
        let current = self.live_regs_per_cycle.get(&cycle).copied().unwrap_or(0);

        // New defs increase pressure
        let def_pressure = defs.len() as i32;
        // Killed regs (last uses) decrease pressure
        let kill_benefit = killed_regs.len() as i32;
        // Uses don't change pressure (they're already live)

        // Negative = reduces pressure, Positive = increases pressure
        def_pressure - kill_benefit
    }

    /// Check if scheduling at this cycle would exceed pressure limit.
    pub fn would_exceed_limit(&self, cycle: i32, defs: &[u32]) -> bool {
        let current = self.live_regs_per_cycle.get(&cycle).copied().unwrap_or(0);

        current + defs.len() > self.target_regs
    }

    /// Update pressure tracking after scheduling an instruction.
    pub fn update_pressure(&mut self, cycle: i32, defs: &[u32], killed_regs: &[u32]) {
        let entry = self.live_regs_per_cycle.entry(cycle).or_insert(0);
        *entry = (*entry + defs.len()).saturating_sub(killed_regs.len());
        self.max_pressure = self.max_pressure.max(*entry);
    }

    /// Print pressure statistics.
    pub fn print_stats(&self) {
        eprintln!(
            "RegPressure: max={}, target={}",
            self.max_pressure, self.target_regs
        );
    }
}

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

// ============================================================================
// ScheduleDAG Mutation
// ============================================================================

/// ScheduleDAGMutation is a callback that modifies the dependence graph
/// before scheduling. Used to add artificial dependencies for
/// processor-specific constraints (e.g., MacroFusion, resource groups).
pub trait ScheduleDAGMutation {
    /// Apply a mutation to the dependence graph before scheduling.
    ///
    /// `nodes`: mutable reference to all schedule nodes.
    /// Returns true if the DAG was modified.
    fn apply(&mut self, nodes: &mut [SchedNode]) -> bool;

    /// Get the name of this mutation for debugging.
    fn name(&self) -> &str;
}

/// MacroFusionMutation adds artificial edges to keep fusible instruction
/// pairs adjacent in the schedule. This enables the processor to fuse
/// them into a single micro-op.
pub struct MacroFusionMutation {
    /// Pairs of opcodes that can be fused: (first_opcode, second_opcode).
    pub fusible_pairs: Vec<(u32, u32)>,
    /// Whether this mutation is enabled.
    pub enabled: bool,
}

impl MacroFusionMutation {
    /// Create a x86-64 macro fusion mutation.
    pub fn x86_default() -> Self {
        Self {
            fusible_pairs: vec![
                (0, 1),   // CMP + JCC
                (10, 11), // TEST + JCC
                (20, 21), // ADD + JCC
                (22, 23), // SUB + JCC
            ],
            enabled: true,
        }
    }

    /// Create an AArch64 macro fusion mutation.
    pub fn aarch64_default() -> Self {
        Self {
            fusible_pairs: vec![
                (100, 101), // CMP + B.COND
                (102, 103), // TST + B.COND
                (104, 105), // ADRP + LDR
            ],
            enabled: true,
        }
    }

    /// Check if a pair of opcodes can be fused.
    pub fn can_fuse(&self, op1: u32, op2: u32) -> bool {
        self.enabled
            && self
                .fusible_pairs
                .iter()
                .any(|&(a, b)| a == op1 && b == op2)
    }
}

impl ScheduleDAGMutation for MacroFusionMutation {
    fn apply(&mut self, nodes: &mut [SchedNode]) -> bool {
        if !self.enabled || nodes.len() < 2 {
            return false;
        }

        let mut modified = false;

        // Find adjacent instructions that can be fused
        for i in 0..nodes.len() - 1 {
            let op1 = nodes[i].opcode;
            let op2 = nodes[i + 1].opcode;

            if self.can_fuse(op1, op2) {
                // Add an artificial edge from i to i+1 to keep them adjacent
                if !nodes[i].successors.contains(&(i + 1)) {
                    nodes[i].successors.push(i + 1);
                    nodes[i + 1].predecessors.push(i);
                    modified = true;
                }
            }
        }

        modified
    }

    fn name(&self) -> &str {
        "MacroFusion"
    }
}

/// AntiDepMutation adds anti-dependencies to prevent WAW/WAR hazards
/// that could be introduced by out-of-order scheduling.
pub struct AntiDepMutation {
    /// Whether to add anti-dependencies.
    pub enabled: bool,
}

impl AntiDepMutation {
    /// Create a new anti-dependency mutation.
    pub fn new() -> Self {
        Self { enabled: true }
    }
}

impl ScheduleDAGMutation for AntiDepMutation {
    fn apply(&mut self, nodes: &mut [SchedNode]) -> bool {
        if !self.enabled {
            return false;
        }

        let mut modified = false;

        // Add anti-dependencies: if node A defines a register that
        // node B uses, ensure A is scheduled before B.
        // (This is a simplified version; full implementation uses def-use chains.)
        for i in 0..nodes.len() {
            for j in i + 1..nodes.len() {
                // Check if j uses a register that i defines (RAW)
                // or i defines a register that j also defines (WAW)
                // or i uses a register that j defines (WAR)
                // These are already captured by the dependence graph builder.
                // Here we add conservative edges for any overlapping registers.
                if !nodes[i].successors.contains(&j) && !nodes[j].predecessors.contains(&i) {
                    // Conservative: add edge if any register conflict possible
                    let has_conflict = nodes[i].opcode % 10 == nodes[j].opcode % 10;
                    if has_conflict {
                        nodes[i].successors.push(j);
                        nodes[j].predecessors.push(i);
                        modified = true;
                    }
                }
            }
        }

        modified
    }

    fn name(&self) -> &str {
        "AntiDep"
    }
}

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

// ============================================================================
// MachineSchedulerBase with DAG Postprocessing
// ============================================================================

/// MachineSchedulerBase provides the base scheduling infrastructure
/// with DAG mutation and postprocessing support.
pub struct MachineSchedulerBase {
    /// Core scheduler.
    pub scheduler: MachineScheduler,
    /// DAG mutations to apply before scheduling.
    pub mutations: Vec<Box<dyn ScheduleDAGMutation>>,
    /// Critical path scheduler.
    pub cp_scheduler: CriticalPathScheduler,
    /// Resource balancer.
    pub resource_balancer: Option<ResourceBalancer>,
    /// Register pressure scheduler.
    pub reg_pressure: RegPressureScheduler,
    /// Whether the DAG has been postprocessed.
    pub dag_processed: bool,
}

impl MachineSchedulerBase {
    /// Create a new scheduler base.
    pub fn new(target: &str) -> Self {
        Self {
            scheduler: MachineScheduler::new(target),
            mutations: Vec::new(),
            cp_scheduler: CriticalPathScheduler::new(),
            resource_balancer: None,
            reg_pressure: RegPressureScheduler::new(16),
            dag_processed: false,
        }
    }

    /// Add a DAG mutation.
    pub fn add_mutation(&mut self, mutation: Box<dyn ScheduleDAGMutation>) {
        self.mutations.push(mutation);
    }

    /// Run the full scheduling pipeline: build DAG, apply mutations,
    /// compute priorities, schedule.
    pub fn run_schedule(&mut self, mf: &mut MachineFunction) -> usize {
        self.dag_processed = false;

        // Step 2: Apply DAG mutations
        let mut nodes: Vec<SchedNode> =
            (0..self.scheduler.resource_model.instruction_latencies.len())
                .map(|i| SchedNode {
                    instr_idx: i,
                    opcode: i as u32,
                    latency: self.scheduler.resource_model.get_latency(i as u32),
                    critical_path: 0,
                    successors: Vec::new(),
                    predecessors: Vec::new(),
                    scheduled: false,
                    unscheduled_preds: 0,
                })
                .collect();

        for mutation in &mut self.mutations {
            mutation.apply(&mut nodes);
        }

        // Step 3: Compute critical paths
        self.cp_scheduler.compute(&nodes);

        // Step 4: Schedule using resource balancing + register pressure
        let total_reordered = self.scheduler.schedule(mf);
        self.dag_processed = true;

        total_reordered
    }

    /// Postprocess the DAG: remove redundant dependencies, optimize
    /// for macro fusion, and adjust for register pressure.
    pub fn postprocess_dag(&mut self, nodes: &mut [SchedNode]) -> usize {
        let mut changes = 0;

        // Remove transitive edges (if A->B and B->C, remove A->C if redundant)
        for i in 0..nodes.len() {
            let succs = nodes[i].successors.clone();
            for &s in &succs {
                // Check transitive paths from i through s
                for &t in &nodes[s].successors.clone() {
                    if nodes[i].successors.contains(&t) {
                        // Found a transitive edge i -> t; remove if
                        // latency(path) >= latency(edge)
                        nodes[i].successors.retain(|&x| x != t);
                        nodes[t].predecessors.retain(|&x| x != i);
                        changes += 1;
                    }
                }
            }
        }

        // Add macro fusion edges
        let mut fusion = MacroFusionMutation::x86_default();
        if fusion.apply(nodes) {
            changes += 1;
        }

        changes
    }

    /// Print the schedule with annotations.
    pub fn print_schedule(&self) {
        eprintln!("MachineSchedulerBase schedule:");
        eprintln!("  Target: {}", self.scheduler.target);
        eprintln!("  Reordered: {}", self.scheduler.reordered);
        eprintln!(
            "  Issue width: {}",
            self.scheduler.resource_model.issue_width
        );
        self.reg_pressure.print_stats();
    }
}

impl Default for MachineSchedulerBase {
    fn default() -> Self {
        Self::new("generic")
    }
}

// ============================================================================
// Hazard Recognition
// ============================================================================

/// Represents a type of pipeline hazard.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HazardKind {
    /// No hazard detected.
    None,
    /// Structural hazard: two instructions require the same pipeline resource
    /// in the same cycle.
    Structural,
    /// RAW (Read-After-Write): true data dependence; consumer reads after
    /// producer writes.
    RAW,
    /// WAR (Write-After-Read): anti-dependence; writer overwrites before
    /// reader reads.
    WAR,
    /// WAW (Write-After-Write): output dependence; two writes to the same
    /// register.
    WAW,
    /// Control hazard: branch or barrier instruction.
    Control,
}

/// Pipeline stage descriptor for a functional unit.
#[derive(Debug, Clone)]
pub struct PipelineStage {
    /// Name of this pipeline stage.
    pub name: String,
    /// Resources consumed in this stage.
    pub resources: Vec<usize>,
    /// Duration of this stage in cycles.
    pub duration: u32,
    /// Whether this stage allows forwarding.
    pub allows_forwarding: bool,
}

/// HazardRecognizer detects pipeline hazards between instructions.
///
/// It tracks which registers are being written/read in each cycle
/// and which pipeline resources are occupied, allowing it to detect
/// structural, data, and control hazards.
#[derive(Debug, Clone)]
pub struct HazardRecognizer {
    /// Number of functional units available.
    pub resource_count: usize,
    /// Per-cycle resource availability: cycle -> resource -> count used.
    pub resource_schedule: HashMap<u32, Vec<u32>>,
    /// Pipeline stage definitions per resource.
    pub pipeline_stages: Vec<PipelineStage>,
    /// Registers being written and the cycle they become available.
    pub write_registers: HashMap<u64, u32>,
    /// Registers being read and the cycle of the read.
    pub read_registers: HashMap<u64, Vec<u32>>,
    /// Instruction latencies per opcode.
    pub latencies: HashMap<u32, u32>,
    /// Current cycle counter.
    pub current_cycle: u32,
    /// Whether forwarding is enabled for this target.
    pub forwarding_enabled: bool,
}

impl HazardRecognizer {
    /// Create a new HazardRecognizer with default resource counts.
    pub fn new(resource_count: usize, forwarding_enabled: bool) -> Self {
        Self {
            resource_count,
            resource_schedule: HashMap::new(),
            pipeline_stages: Vec::new(),
            write_registers: HashMap::new(),
            read_registers: HashMap::new(),
            latencies: HashMap::new(),
            current_cycle: 0,
            forwarding_enabled,
        }
    }

    /// Add a pipeline stage definition.
    pub fn add_pipeline_stage(&mut self, stage: PipelineStage) {
        self.pipeline_stages.push(stage);
    }

    /// Set the latency for an opcode.
    pub fn set_latency(&mut self, opcode: u32, latency: u32) {
        self.latencies.insert(opcode, latency);
    }

    /// Set the current scheduling cycle.
    pub fn set_cycle(&mut self, cycle: u32) {
        self.current_cycle = cycle;
    }

    /// Check whether an instruction can be issued in the current cycle
    /// without causing any hazards.
    pub fn can_issue(
        &self,
        opcode: u32,
        def_regs: &[u64],
        use_regs: &[u64],
        resources: &[usize],
    ) -> HazardKind {
        // Check structural hazards: are all required resources available?
        for &res in resources {
            if res < self.resource_count {
                if let Some(cycle_usage) = self.resource_schedule.get(&self.current_cycle) {
                    if res < cycle_usage.len() && cycle_usage[res] > 0 {
                        // Check if the resource count allows multiple users
                        // In a simple model, 1 usage means occupied
                        if cycle_usage[res] >= 1 {
                            return HazardKind::Structural;
                        }
                    }
                }
            }
        }

        // Check RAW hazards: are all use registers ready?
        for &reg in use_regs {
            if let Some(&write_cycle) = self.write_registers.get(&reg) {
                let latency = self.latencies.get(&opcode).copied().unwrap_or(1);
                let available_cycle = write_cycle + latency;
                if self.current_cycle < available_cycle {
                    // Check if forwarding can bypass the write-back stage
                    if !self.can_forward(reg, write_cycle, self.current_cycle) {
                        return HazardKind::RAW;
                    }
                }
            }
        }

        // Check WAR hazards: are we writing a register that's still being read?
        for &reg in def_regs {
            if let Some(read_cycles) = self.read_registers.get(&reg) {
                for &read_cycle in read_cycles {
                    if read_cycle >= self.current_cycle {
                        return HazardKind::WAR;
                    }
                }
            }
        }

        // Check WAW hazards: are we writing a register that another
        // in-flight instruction is also writing?
        for &reg in def_regs {
            if let Some(&write_cycle) = self.write_registers.get(&reg) {
                if write_cycle >= self.current_cycle {
                    return HazardKind::WAW;
                }
            }
        }

        HazardKind::None
    }

    /// Emit an instruction, reserving its resources and marking its
    /// register effects.
    pub fn emit(&mut self, opcode: u32, def_regs: &[u64], use_regs: &[u64], resources: &[usize]) {
        let latency = self.latencies.get(&opcode).copied().unwrap_or(1);

        // Reserve resources for the duration of this instruction
        for cycle_offset in 0..latency {
            let cycle = self.current_cycle + cycle_offset;
            let usage = self
                .resource_schedule
                .entry(cycle)
                .or_insert_with(|| vec![0; self.resource_count]);
            for &res in resources {
                if res < usage.len() {
                    usage[res] += 1;
                }
            }
        }

        // Mark write registers with their completion cycle
        for &reg in def_regs {
            self.write_registers
                .insert(reg, self.current_cycle + latency);
        }

        // Record read registers
        for &reg in use_regs {
            self.read_registers
                .entry(reg)
                .or_default()
                .push(self.current_cycle);
        }
    }

    /// Check whether forwarding can bypass the latency for a RAW hazard.
    ///
    /// Forwarding allows the result of an ALU operation to be used
    /// before it's written back, reducing the effective latency.
    fn can_forward(&self, reg: u64, producer_cycle: u32, consumer_cycle: u32) -> bool {
        if !self.forwarding_enabled {
            return false;
        }

        // Forwarding typically works when the consumer is in the cycle
        // immediately after the producer (for ALU ops) or after a
        // small number of cycles (for loads with load-use forwarding).
        let distance = consumer_cycle - producer_cycle;

        // Common forwarding scenarios:
        // - ALU->ALU: 1 cycle forwarding
        // - Load->ALU: 1 cycle forwarding (load-use bypass)
        // - FP->FP: typically 0 cycles (cannot forward)
        distance <= 2
    }

    /// Advance to the next cycle and age existing reservations.
    pub fn advance_cycle(&mut self) {
        self.current_cycle += 1;
    }

    /// Find the earliest cycle where an instruction can be issued
    /// without hazards.
    pub fn find_earliest_issue(
        &self,
        opcode: u32,
        def_regs: &[u64],
        use_regs: &[u64],
        resources: &[usize],
        max_cycles: u32,
    ) -> Option<u32> {
        let mut probe = self.clone();
        for offset in 0..max_cycles {
            probe.current_cycle = self.current_cycle + offset;
            if probe.can_issue(opcode, def_regs, use_regs, resources) == HazardKind::None {
                return Some(self.current_cycle + offset);
            }
        }
        None
    }

    /// Reset the hazard recognizer for a new scheduling region.
    pub fn reset(&mut self) {
        self.resource_schedule.clear();
        self.write_registers.clear();
        self.read_registers.clear();
        self.current_cycle = 0;
    }

    /// Get the number of cycles scheduled so far.
    pub fn scheduled_cycles(&self) -> u32 {
        self.current_cycle
    }

    /// Get resource utilization at a given cycle.
    pub fn utilization_at(&self, cycle: u32) -> Vec<u32> {
        self.resource_schedule
            .get(&cycle)
            .cloned()
            .unwrap_or_else(|| vec![0; self.resource_count])
    }
}

impl Default for HazardRecognizer {
    fn default() -> Self {
        Self::new(8, true)
    }
}

// ============================================================================
// Pipeline Forwarding / Bypass Network
// ============================================================================

/// Describes a forwarding path from a producer pipeline stage to a
/// consumer pipeline stage.
#[derive(Debug, Clone)]
pub struct ForwardingPath {
    /// Source pipeline stage index.
    pub from_stage: usize,
    /// Destination pipeline stage index.
    pub to_stage: usize,
    /// The effective latency reduction (cycles saved).
    pub latency_reduction: u32,
    /// Whether this forwarding path applies to all opcodes.
    pub universal: bool,
    /// Specific producer opcodes (empty = all).
    pub producer_opcodes: Vec<u32>,
    /// Specific consumer opcodes (empty = all).
    pub consumer_opcodes: Vec<u32>,
}

/// ForwardingModel analyzes the bypass network of a CPU pipeline
/// and computes effective latencies after forwarding.
#[derive(Debug, Clone)]
pub struct ForwardingModel {
    /// Available forwarding paths.
    pub paths: Vec<ForwardingPath>,
    /// Default instruction latencies (opcode -> cycles).
    pub base_latencies: HashMap<u32, u32>,
    /// Computed effective latencies after forwarding.
    pub effective_latencies: HashMap<(u32, u32), u32>,
}

impl ForwardingModel {
    /// Create a new forwarding model.
    pub fn new() -> Self {
        Self {
            paths: Vec::new(),
            base_latencies: HashMap::new(),
            effective_latencies: HashMap::new(),
        }
    }

    /// Add a forwarding path.
    pub fn add_path(&mut self, path: ForwardingPath) {
        self.paths.push(path);
    }

    /// Set the base latency for an opcode.
    pub fn set_latency(&mut self, opcode: u32, latency: u32) {
        self.base_latencies.insert(opcode, latency);
    }

    /// Get the effective latency between a producer instruction and a
    /// consumer instruction considering all forwarding paths.
    pub fn get_effective_latency(&self, producer_opcode: u32, consumer_opcode: u32) -> u32 {
        // Check memoized result
        let key = (producer_opcode, consumer_opcode);
        if let Some(&lat) = self.effective_latencies.get(&key) {
            return lat;
        }

        let base = self
            .base_latencies
            .get(&producer_opcode)
            .copied()
            .unwrap_or(1);
        let mut best_reduction = 0u32;

        for path in &self.paths {
            // Check opcode compatibility
            let producer_ok = path.producer_opcodes.is_empty()
                || path.producer_opcodes.contains(&producer_opcode);
            let consumer_ok = path.consumer_opcodes.is_empty()
                || path.consumer_opcodes.contains(&consumer_opcode);

            if (producer_ok && consumer_ok) || path.universal {
                best_reduction = best_reduction.max(path.latency_reduction);
            }
        }

        let effective = base.saturating_sub(best_reduction).max(1);
        effective
    }

    /// Check if forwarding is available between two opcodes.
    pub fn can_forward(&self, producer_opcode: u32, consumer_opcode: u32) -> bool {
        self.get_effective_latency(producer_opcode, consumer_opcode)
            < self
                .base_latencies
                .get(&producer_opcode)
                .copied()
                .unwrap_or(1)
    }

    /// Create a default x86-64 forwarding model.
    pub fn x86_64_default() -> Self {
        let mut model = Self::new();

        // Base latencies for x86-64
        for op in 1..=10 {
            model.set_latency(op, 1); // ALU ops typically 1 cycle
        }
        model.set_latency(2, 4); // Load: 4 cycles (L1 hit)
        model.set_latency(3, 1); // Store: dispatch latency
        model.set_latency(4, 3); // FP add
        model.set_latency(5, 5); // FP mul

        // Forwarding paths:
        // ALU -> ALU: EX-to-EX forwarding (1 cycle saved)
        model.add_path(ForwardingPath {
            from_stage: 2,
            to_stage: 1,
            latency_reduction: 1,
            universal: false,
            producer_opcodes: vec![1],
            consumer_opcodes: vec![1],
        });

        // Load -> ALU: load-use forwarding (2 cycles saved)
        model.add_path(ForwardingPath {
            from_stage: 4,
            to_stage: 2,
            latency_reduction: 2,
            universal: false,
            producer_opcodes: vec![2],
            consumer_opcodes: vec![1],
        });

        // Store -> Load: store-to-load forwarding (no latency)
        model.add_path(ForwardingPath {
            from_stage: 3,
            to_stage: 3,
            latency_reduction: 3,
            universal: false,
            producer_opcodes: vec![3],
            consumer_opcodes: vec![2],
        });

        model
    }

    /// Create a default AArch64 forwarding model.
    pub fn aarch64_default() -> Self {
        let mut model = Self::new();

        for op in 1..=10 {
            model.set_latency(op, 1);
        }
        model.set_latency(2, 4);
        model.set_latency(3, 1);

        // AArch64 has rich forwarding: most ALU ops can forward
        model.add_path(ForwardingPath {
            from_stage: 2,
            to_stage: 1,
            latency_reduction: 1,
            universal: true,
            producer_opcodes: vec![],
            consumer_opcodes: vec![],
        });

        model
    }
}

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

// ============================================================================
// MicroFusion
// ============================================================================

/// MicroFusion fuses certain instruction pairs where an address
/// computation can be folded into a memory operation.
///
/// For example, on x86:
///   LEA r1, [r2 + r3*scale + offset]
///   MOV r4, [r1]       → MOV r4, [r2 + r3*scale + offset]
///
/// The LEA is fused into the memory operand of the MOV, eliminating
/// an instruction.
#[derive(Debug, Clone)]
pub struct MicroFusion {
    /// Whether micro-fusion is enabled.
    pub enabled: bool,
    /// List of fusible patterns: (address_op, mem_op).
    pub fusible_patterns: Vec<(u32, u32)>,
    /// Target architecture.
    pub target: String,
}

impl MicroFusion {
    /// Create a new MicroFusion instance.
    pub fn new(target: &str) -> Self {
        Self {
            enabled: !target.is_empty(),
            fusible_patterns: Vec::new(),
            target: target.to_string(),
        }
    }

    /// Add a fusible pattern.
    pub fn add_pattern(&mut self, addr_op: u32, mem_op: u32) {
        self.fusible_patterns.push((addr_op, mem_op));
    }

    /// Check whether two adjacent instructions can be micro-fused.
    ///
    /// Returns Some(fused_opcode) if they can be fused, None otherwise.
    pub fn can_micro_fuse(
        &self,
        addr_instr: &MachineInstr,
        mem_instr: &MachineInstr,
    ) -> Option<u32> {
        if !self.enabled {
            return None;
        }

        // Check if the address instruction defines a register that the
        // memory instruction uses as its pointer operand
        let addr_def = addr_instr.def?;

        // Check if the memory instruction uses the address register
        let uses_addr = mem_instr.operands.iter().any(|op| match op {
            MachineOperand::Reg(r) => *r == addr_def,
            _ => false,
        });

        if !uses_addr {
            return None;
        }

        // Check fusible pattern
        for &(addr_op, mem_op) in &self.fusible_patterns {
            if addr_instr.opcode == addr_op && mem_instr.opcode == mem_op {
                // Return the fused opcode (memory op with embedded address)
                return Some(mem_op + 100);
            }
        }

        // Default: any address computation can fuse with load/store
        if mem_instr.opcode == 2 || mem_instr.opcode == 3 {
            return Some(mem_instr.opcode);
        }

        None
    }

    /// Attempt to micro-fuse instructions in a basic block.
    ///
    /// Returns the number of fused pairs.
    pub fn apply(&self, instructions: &mut Vec<MachineInstr>) -> usize {
        let mut fused = 0;
        let mut i = 0;

        while i + 1 < instructions.len() {
            if let Some(_fused_op) = self.can_micro_fuse(&instructions[i], &instructions[i + 1]) {
                // Remove the address instruction (it's been folded in)
                instructions.remove(i);
                fused += 1;
                // Don't increment i; re-check at the same position
            } else {
                i += 1;
            }
        }

        fused
    }

    /// Create default x86 micro-fusion patterns.
    pub fn x86_default() -> Self {
        let mut mf = Self::new("x86_64");
        // LEA + LOAD
        mf.add_pattern(8, 2);
        // LEA + STORE
        mf.add_pattern(8, 3);
        // ADD (address calc) + LOAD
        mf.add_pattern(1, 2);
        mf
    }
}

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

// ============================================================================
// Cluster Formation (Load/Store Clustering)
// ============================================================================

/// Cluster groups loads and stores that share the same base register.
/// Clustered memory operations can be scheduled together to exploit
/// memory-level parallelism and reduce address generation overhead.
#[derive(Debug, Clone)]
pub struct MemoryCluster {
    /// Base register for this cluster.
    pub base_register: u64,
    /// Indices of instructions in the cluster.
    pub instructions: Vec<usize>,
    /// Whether this is a load cluster or store cluster.
    pub is_load: bool,
    /// Total byte footprint of the cluster.
    pub byte_footprint: u32,
}

/// ClusterFormation identifies groups of loads and stores that access
/// memory through the same base register and can be scheduled as a group.
#[derive(Debug, Clone)]
pub struct ClusterFormation {
    /// Whether clustering is enabled.
    pub enabled: bool,
    /// Maximum number of instructions per cluster.
    pub max_cluster_size: usize,
    /// Minimum number of instructions to form a cluster.
    pub min_cluster_size: usize,
    /// Formed clusters.
    pub clusters: Vec<MemoryCluster>,
}

impl ClusterFormation {
    /// Create a new ClusterFormation.
    pub fn new(max_cluster_size: usize) -> Self {
        Self {
            enabled: true,
            max_cluster_size,
            min_cluster_size: 2,
            clusters: Vec::new(),
        }
    }

    /// Analyze instructions and form clusters of loads and stores
    /// that share the same base register.
    pub fn form_clusters(&mut self, instructions: &[MachineInstr]) {
        self.clusters.clear();

        // Group loads and stores by their base register
        let mut load_groups: HashMap<u64, Vec<usize>> = HashMap::new();
        let mut store_groups: HashMap<u64, Vec<usize>> = HashMap::new();

        for (idx, instr) in instructions.iter().enumerate() {
            // Identify base register from operands
            let base_reg = self.extract_base_register(instr);
            if let Some(base) = base_reg {
                match instr.opcode {
                    2 => {
                        // LOAD
                        load_groups.entry(base).or_default().push(idx);
                    }
                    3 => {
                        // STORE
                        store_groups.entry(base).or_default().push(idx);
                    }
                    _ => {}
                }
            }
        }

        // Form load clusters
        for (base, indices) in load_groups {
            if indices.len() >= self.min_cluster_size {
                let byte_footprint = self.estimate_footprint(instructions, &indices);
                self.clusters.push(MemoryCluster {
                    base_register: base,
                    instructions: indices,
                    is_load: true,
                    byte_footprint,
                });
            }
        }

        // Form store clusters
        for (base, indices) in store_groups {
            if indices.len() >= self.min_cluster_size {
                let byte_footprint = self.estimate_footprint(instructions, &indices);
                self.clusters.push(MemoryCluster {
                    base_register: base,
                    instructions: indices,
                    is_load: false,
                    byte_footprint,
                });
            }
        }
    }

    /// Extract the base register from a machine instruction.
    /// For memory operations, this is typically the first register operand.
    fn extract_base_register(&self, instr: &MachineInstr) -> Option<u64> {
        for operand in &instr.operands {
            match operand {
                MachineOperand::Reg(r) => return Some(*r as u64),
                MachineOperand::PhysReg(pr) => return Some(*pr as u64 + (1u64 << 32)),
                _ => continue,
            }
        }
        None
    }

    /// Estimate the total byte footprint of a group of instructions.
    fn estimate_footprint(&self, instructions: &[MachineInstr], indices: &[usize]) -> u32 {
        // Simplified: assume each load/store is 4 bytes
        indices.len() as u32 * 4
    }

    /// Check whether two instructions should be in the same cluster.
    pub fn should_cluster(&self, instr_a: &MachineInstr, instr_b: &MachineInstr) -> bool {
        let base_a = self.extract_base_register(instr_a);
        let base_b = self.extract_base_register(instr_b);

        match (base_a, base_b) {
            (Some(a), Some(b)) => a == b,
            _ => false,
        }
    }

    /// Get load clusters sorted by byte footprint (largest first).
    pub fn load_clusters(&self) -> Vec<&MemoryCluster> {
        let mut loads: Vec<&MemoryCluster> = self.clusters.iter().filter(|c| c.is_load).collect();
        loads.sort_by_key(|c| -(c.byte_footprint as i64));
        loads
    }

    /// Get store clusters sorted by byte footprint.
    pub fn store_clusters(&self) -> Vec<&MemoryCluster> {
        let mut stores: Vec<&MemoryCluster> = self.clusters.iter().filter(|c| !c.is_load).collect();
        stores.sort_by_key(|c| -(c.byte_footprint as i64));
        stores
    }

    /// Print cluster statistics.
    pub fn print_stats(&self) {
        eprintln!("ClusterFormation: {} clusters formed", self.clusters.len());
        for cluster in &self.clusters {
            eprintln!(
                "  {} cluster: base={}, {} instrs, {} bytes",
                if cluster.is_load { "Load" } else { "Store" },
                cluster.base_register,
                cluster.instructions.len(),
                cluster.byte_footprint
            );
        }
    }
}

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

// ============================================================================
// Scheduling Regions
// ============================================================================

/// A scheduling region is a contiguous range of instructions within
/// a basic block that can be reordered freely. Regions are bounded
/// by scheduling barriers (calls, returns, branches, labels).
#[derive(Debug, Clone)]
pub struct SchedulingRegion {
    /// Start instruction index (inclusive).
    pub start: usize,
    /// End instruction index (inclusive).
    pub end: usize,
    /// Whether this region is at the top of the block (prologue).
    pub is_top: bool,
    /// Whether this region is at the bottom of the block (epilogue).
    pub is_bottom: bool,
    /// Whether this region contains a terminator.
    pub has_terminator: bool,
}

/// SchedulingBarrier identifies instructions that cannot be reordered
/// across.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SchedulingBarrier {
    /// No barrier.
    None,
    /// Call instruction: may have side effects.
    Call,
    /// Return instruction: end of block.
    Return,
    /// Branch instruction: control flow.
    Branch,
    /// Inline assembly: opaque to the scheduler.
    InlineAsm,
    /// EH label: exception handling landing pad.
    EHLabel,
    /// Debug instruction: should not affect scheduling.
    DebugInstr,
    /// Memory fence: full memory barrier.
    Fence,
}

/// RegionBuilder splits a basic block into scheduling regions.
#[derive(Debug, Clone)]
pub struct RegionBuilder {
    /// Formed regions.
    pub regions: Vec<SchedulingRegion>,
    /// Whether to allow scheduling across calls.
    pub schedule_across_calls: bool,
    /// Target triple for barrier identification.
    pub target: String,
}

impl RegionBuilder {
    /// Create a new RegionBuilder.
    pub fn new(target: &str, schedule_across_calls: bool) -> Self {
        Self {
            regions: Vec::new(),
            schedule_across_calls,
            target: target.to_string(),
        }
    }

    /// Split instructions into scheduling regions.
    pub fn build_regions(&mut self, instructions: &[MachineInstr]) {
        self.regions.clear();

        if instructions.is_empty() {
            return;
        }

        let mut region_start = 0usize;
        let is_top = true;

        for (i, instr) in instructions.iter().enumerate() {
            let barrier = self.classify_barrier(instr);

            let ends_region = match barrier {
                SchedulingBarrier::None => false,
                SchedulingBarrier::Call => !self.schedule_across_calls,
                SchedulingBarrier::Return | SchedulingBarrier::Branch => true,
                SchedulingBarrier::InlineAsm => true,
                SchedulingBarrier::EHLabel => true,
                SchedulingBarrier::DebugInstr => false,
                SchedulingBarrier::Fence => true,
            };

            if ends_region && i > region_start {
                self.regions.push(SchedulingRegion {
                    start: region_start,
                    end: i,
                    is_top: is_top && self.regions.is_empty(),
                    is_bottom: barrier == SchedulingBarrier::Return
                        || barrier == SchedulingBarrier::Branch,
                    has_terminator: barrier == SchedulingBarrier::Return
                        || barrier == SchedulingBarrier::Branch,
                });
                region_start = i + 1;
            }

            // Terminators end the block; start a new region after them
            if barrier == SchedulingBarrier::Return || barrier == SchedulingBarrier::Branch {
                if i + 1 < instructions.len() {
                    region_start = i + 1;
                }
            }
        }

        // Final region
        if region_start < instructions.len() {
            self.regions.push(SchedulingRegion {
                start: region_start,
                end: instructions.len() - 1,
                is_top: false,
                is_bottom: false,
                has_terminator: false,
            });
        }
    }

    /// Classify an instruction as a scheduling barrier.
    fn classify_barrier(&self, instr: &MachineInstr) -> SchedulingBarrier {
        match instr.opcode {
            0 => SchedulingBarrier::None,
            7 => SchedulingBarrier::Branch,      // Branch
            8 => SchedulingBarrier::Branch,      // Conditional branch
            9 => SchedulingBarrier::Return,      // Return
            10 => SchedulingBarrier::Call,       // Call
            11 => SchedulingBarrier::Fence,      // Fence
            12 => SchedulingBarrier::InlineAsm,  // Inline asm
            13 => SchedulingBarrier::EHLabel,    // EH label
            99 => SchedulingBarrier::DebugInstr, // Debug
            _ => SchedulingBarrier::None,
        }
    }

    /// Check if two instructions are in the same region.
    pub fn same_region(&self, idx_a: usize, idx_b: usize) -> bool {
        self.regions
            .iter()
            .any(|r| r.start <= idx_a && idx_a <= r.end && r.start <= idx_b && idx_b <= r.end)
    }

    /// Get the region containing an instruction index.
    pub fn get_region(&self, instr_idx: usize) -> Option<&SchedulingRegion> {
        self.regions
            .iter()
            .find(|r| r.start <= instr_idx && instr_idx <= r.end)
    }

    /// Get the number of regions.
    pub fn region_count(&self) -> usize {
        self.regions.len()
    }
}

impl Default for RegionBuilder {
    fn default() -> Self {
        Self::new("generic", false)
    }
}

// ============================================================================
// Post-RA Scheduling
// ============================================================================

/// PostRAScheduler performs scheduling after register allocation.
/// At this point, all virtual registers have been assigned to physical
/// registers, so the scheduler must respect physical register liveness.
#[derive(Debug, Clone)]
pub struct PostRAScheduler {
    /// Target architecture.
    pub target: String,
    /// Resource model for post-RA scheduling.
    pub resource_model: ResourceModel,
    /// Hazard recognizer for post-RA hazards.
    pub hazard_recognizer: HazardRecognizer,
    /// Forwarding model for bypass detection.
    pub forwarding: ForwardingModel,
    /// Whether anti-dependency breaking is enabled.
    pub break_anti_deps: bool,
    /// Physical register liveness at each program point.
    pub reg_liveness: HashMap<u64, Vec<(usize, usize)>>,
}

impl PostRAScheduler {
    /// Create a new PostRAScheduler.
    pub fn new(target: &str) -> Self {
        let mut hazard = HazardRecognizer::new(8, true);
        hazard.set_latency(1, 1);
        hazard.set_latency(2, 4);
        hazard.set_latency(3, 1);
        hazard.set_latency(7, 1);

        Self {
            target: target.to_string(),
            resource_model: ResourceModel::default_model(),
            hazard_recognizer: hazard,
            forwarding: ForwardingModel::x86_64_default(),
            break_anti_deps: true,
            reg_liveness: HashMap::new(),
        }
    }

    /// Schedule instructions after register allocation.
    ///
    /// Returns the number of reordered instructions.
    pub fn schedule(&mut self, instructions: &mut [MachineInstr]) -> usize {
        if instructions.len() < 2 {
            return 0;
        }

        // Build liveness information
        self.compute_liveness(instructions);

        // Build dependence graph with physical register constraints
        let graph = self.build_post_ra_dag(instructions);
        let cp = self.compute_physical_critical_path(&graph);

        // Schedule with post-RA constraints
        let schedule = self.list_schedule_post_ra(&graph, &cp, instructions);

        // Reorder instructions
        if schedule.len() == instructions.len() {
            let mut reordered = 0;
            let mut new_instrs = Vec::with_capacity(schedule.len());
            for &idx in &schedule {
                if idx < instructions.len() {
                    new_instrs.push(instructions[idx].clone());
                }
            }
            for (i, &sched_idx) in schedule.iter().enumerate() {
                if sched_idx != i {
                    reordered += 1;
                }
            }
            // Apply reordering in place
            for (i, instr) in new_instrs.into_iter().enumerate() {
                if i < instructions.len() {
                    instructions[i] = instr;
                }
            }
            reordered
        } else {
            0
        }
    }

    /// Compute physical register liveness for a sequence of instructions.
    fn compute_liveness(&mut self, instructions: &[MachineInstr]) {
        self.reg_liveness.clear();

        // Track last use of each register
        let mut last_use: HashMap<u64, usize> = HashMap::new();
        let mut first_def: HashMap<u64, usize> = HashMap::new();

        for (idx, instr) in instructions.iter().enumerate() {
            for operand in &instr.operands {
                if let Some(reg_key) = Self::phys_reg_key(operand) {
                    last_use.insert(reg_key, idx);
                }
            }
            if let Some(def) = instr.def {
                let key = def as u64;
                first_def.entry(key).or_insert(idx);
                // Record live range
                let end = last_use.get(&key).copied().unwrap_or(idx);
                self.reg_liveness.entry(key).or_default().push((idx, end));
            }
        }
    }

    /// Convert a machine operand to a physical register key.
    fn phys_reg_key(op: &MachineOperand) -> Option<u64> {
        match op {
            MachineOperand::Reg(r) => Some(*r as u64),
            MachineOperand::PhysReg(pr) => Some(*pr as u64 + (1u64 << 32)),
            _ => None,
        }
    }

    /// Build a dependence graph with post-RA physical register constraints.
    fn build_post_ra_dag(&self, instructions: &[MachineInstr]) -> DepGraph {
        let n = instructions.len();
        let mut graph = DepGraph::new();

        for (idx, mi) in instructions.iter().enumerate() {
            let node = SchedNode {
                instr_idx: idx,
                opcode: mi.opcode,
                latency: self.resource_model.get_latency(mi.opcode),
                critical_path: 0,
                successors: Vec::new(),
                predecessors: Vec::new(),
                scheduled: false,
                unscheduled_preds: 0,
            };
            graph.nodes.push(node);
        }
        graph.node_count = n;

        // Track last definitions of each physical register
        let mut last_def: HashMap<u64, usize> = HashMap::new();
        let mut last_use: HashMap<u64, Vec<usize>> = HashMap::new();

        for (idx, mi) in instructions.iter().enumerate() {
            let def_regs: Vec<u64> = mi.def.into_iter().map(|d| d as u64).collect();
            let use_regs: Vec<u64> = mi
                .operands
                .iter()
                .filter_map(|op| Self::phys_reg_key(op))
                .collect();

            // RAW dependencies
            for &reg in &use_regs {
                if let Some(&def_idx) = last_def.get(&reg) {
                    if def_idx < idx {
                        graph.nodes[def_idx].successors.push(idx);
                        graph.nodes[idx].predecessors.push(def_idx);
                    }
                }
                last_use.entry(reg).or_default().push(idx);
            }

            // WAW and WAR
            for &reg in &def_regs {
                // WAW: previous def
                if let Some(&prev_def) = last_def.get(&reg) {
                    if prev_def < idx {
                        graph.nodes[prev_def].successors.push(idx);
                        graph.nodes[idx].predecessors.push(prev_def);
                    }
                }
                // WAR: previous uses
                if let Some(prev_uses) = last_use.get(&reg) {
                    for &use_idx in prev_uses {
                        if use_idx < idx {
                            graph.nodes[use_idx].successors.push(idx);
                            graph.nodes[idx].predecessors.push(use_idx);
                        }
                    }
                }
                last_def.insert(reg, idx);
                last_use.remove(&reg);
            }
        }

        // Set unscheduled predecessor counts
        for node in &mut graph.nodes {
            node.unscheduled_preds = node.predecessors.len();
        }

        graph
    }

    /// Compute critical path for post-RA scheduling.
    fn compute_physical_critical_path(&self, graph: &DepGraph) -> Vec<u32> {
        let n = graph.node_count;
        let mut cp = vec![0u32; n];

        for idx in (0..n).rev() {
            let node_latency = graph.nodes[idx].latency;
            let mut max_succ_cp = 0u32;

            for &succ in &graph.nodes[idx].successors {
                if succ < n {
                    max_succ_cp = max_succ_cp.max(cp[succ]);
                }
            }

            cp[idx] = node_latency + max_succ_cp;
        }

        cp
    }

    /// List-schedule with post-RA register constraints.
    fn list_schedule_post_ra(
        &self,
        graph: &DepGraph,
        cp: &[u32],
        instructions: &[MachineInstr],
    ) -> Vec<usize> {
        let n = graph.node_count;
        let mut schedule = Vec::with_capacity(n);

        let mut unscheduled_preds: Vec<usize> = graph
            .nodes
            .iter()
            .map(|node| node.unscheduled_preds)
            .collect();

        let mut ready: Vec<usize> = (0..n).filter(|&i| unscheduled_preds[i] == 0).collect();

        while !ready.is_empty() {
            ready.sort_by(|&a, &b| cp[b].cmp(&cp[a]).then_with(|| a.cmp(&b)));

            let selected = ready.remove(0);
            schedule.push(selected);

            for &succ in &graph.nodes[selected].successors {
                if succ < n && unscheduled_preds[succ] > 0 {
                    unscheduled_preds[succ] -= 1;
                    if unscheduled_preds[succ] == 0 {
                        ready.push(succ);
                    }
                }
            }
        }

        schedule
    }

    /// Attempt to break anti-dependencies by renaming registers.
    ///
    /// If an instruction writes to a register that is still live from
    /// a previous read, and a free physical register is available,
    /// rename the destination register to break the WAR dependence.
    pub fn break_anti_dependencies(
        &self,
        graph: &mut DepGraph,
        instructions: &mut [MachineInstr],
    ) -> usize {
        if !self.break_anti_deps {
            return 0;
        }

        let mut broken = 0;

        // Find WAR edges and attempt to break them
        for i in 0..graph.node_count {
            let war_edges: Vec<usize> = graph.nodes[i]
                .predecessors
                .iter()
                .copied()
                .filter(|&pred| {
                    // Check if this is a WAR edge: pred reads, i writes
                    instructions.get(pred).map_or(false, |p_instr| {
                        instructions.get(i).map_or(false, |i_instr| {
                            // p_instr reads a reg that i_instr writes
                            i_instr.def.is_some()
                        })
                    })
                })
                .collect();

            if !war_edges.is_empty() && instructions[i].def.is_some() {
                // Attempt to rename: assign a new virtual register
                // In a real implementation, this would use free physical
                // registers from the allocation
                let new_reg = (instructions[i].def.unwrap() as u64).wrapping_add(10000);
                let old_def = instructions[i].def;
                instructions[i].def = Some(new_reg as u32);

                // Remove WAR edges
                for &pred in &war_edges {
                    graph.nodes[pred].successors.retain(|&x| x != i);
                    graph.nodes[i].predecessors.retain(|&x| x != pred);
                }

                broken += war_edges.len();
            }
        }

        broken
    }
}

impl Default for PostRAScheduler {
    fn default() -> Self {
        Self::new("generic")
    }
}

// ============================================================================
// Reservation Table
// ============================================================================

/// A reservation table tracks which pipeline resources are occupied
/// at each cycle for a given instruction.
#[derive(Debug, Clone)]
pub struct ReservationTable {
    /// Number of pipeline stages tracked.
    pub num_stages: usize,
    /// Number of functional units tracked.
    pub num_units: usize,
    /// Table[cycle][unit] = true if the unit is occupied.
    pub table: Vec<Vec<bool>>,
    /// The instruction this table describes.
    pub opcode: u32,
    /// Duration of the reservation in cycles.
    pub duration: u32,
}

impl ReservationTable {
    /// Create an empty reservation table.
    pub fn new(num_stages: usize, num_units: usize, opcode: u32) -> Self {
        Self {
            num_stages,
            num_units,
            table: vec![vec![false; num_units]; num_stages],
            opcode,
            duration: num_stages as u32,
        }
    }

    /// Reserve a unit at a specific cycle.
    pub fn reserve(&mut self, cycle: usize, unit: usize) {
        if cycle < self.table.len() && unit < self.num_units {
            self.table[cycle][unit] = true;
        }
    }

    /// Check if a unit is reserved at a cycle.
    pub fn is_reserved(&self, cycle: usize, unit: usize) -> bool {
        if cycle < self.table.len() && unit < self.num_units {
            self.table[cycle][unit]
        } else {
            false
        }
    }

    /// Check if this reservation table collides with another at a
    /// given offset.
    pub fn collides_with(&self, other: &ReservationTable, offset: usize) -> bool {
        for cycle in 0..self.table.len() {
            let other_cycle = cycle.wrapping_sub(offset);
            if other_cycle < other.table.len() {
                for unit in 0..self.num_units.min(other.num_units) {
                    if self.table[cycle][unit] && other.table[other_cycle][unit] {
                        return true;
                    }
                }
            }
        }
        false
    }

    /// Get the resource usage at a specific cycle.
    pub fn usage_at(&self, cycle: usize) -> Vec<usize> {
        if cycle < self.table.len() {
            self.table[cycle]
                .iter()
                .enumerate()
                .filter(|&(_, &used)| used)
                .map(|(unit, _)| unit)
                .collect()
        } else {
            Vec::new()
        }
    }

    /// Create a reservation table for a typical ALU instruction.
    pub fn alu_default() -> Self {
        let mut rt = Self::new(5, 4, 1);
        rt.reserve(0, 0); // Issue
        rt.reserve(1, 1); // Execute
        rt.reserve(2, 1); // Execute (continued for multi-cycle)
        rt.reserve(3, 2); // Write-back
        rt
    }

    /// Create a reservation table for a load instruction.
    pub fn load_default() -> Self {
        let mut rt = Self::new(6, 4, 2);
        rt.reserve(0, 0); // Issue
        rt.reserve(1, 1); // AGU (Address Generation)
        rt.reserve(2, 3); // Cache access
        rt.reserve(3, 3); // Cache access
        rt.reserve(4, 3); // Data alignment
        rt.reserve(5, 2); // Write-back
        rt
    }

    /// Print the reservation table as ASCII art.
    pub fn print(&self) {
        eprintln!("Reservation table for opcode {}:", self.opcode);
        eprint!("Cycle |");
        for unit in 0..self.num_units {
            eprint!(" U{}", unit);
        }
        eprintln!();
        eprintln!("{:-<1$}", "", 10 + self.num_units * 3);

        for cycle in 0..self.table.len() {
            eprint!("  {:3} |", cycle);
            for unit in 0..self.num_units {
                let c = if self.table[cycle][unit] { 'X' } else { '.' };
                eprint!("  {}", c);
            }
            eprintln!();
        }
    }
}

impl Default for ReservationTable {
    fn default() -> Self {
        Self::alu_default()
    }
}

// ============================================================================
// Bidirectional Scheduling
// ============================================================================

/// BidirectionalScheduler performs both top-down (forward) and
/// bottom-up (backward) list scheduling and picks the best result.
#[derive(Debug, Clone)]
pub struct BidirectionalScheduler {
    /// Target triple.
    pub target: String,
    /// Resource model for scheduling.
    pub resource_model: ResourceModel,
    /// Forward schedule result.
    pub forward_schedule: Vec<usize>,
    /// Backward schedule result.
    pub backward_schedule: Vec<usize>,
    /// Best schedule (the one with shorter critical path).
    pub best_schedule: Vec<usize>,
    /// Forward schedule length in cycles.
    pub forward_length: u32,
    /// Backward schedule length in cycles.
    pub backward_length: u32,
}

impl BidirectionalScheduler {
    /// Create a new BidirectionalScheduler.
    pub fn new(target: &str) -> Self {
        Self {
            target: target.to_string(),
            resource_model: ResourceModel::default_model(),
            forward_schedule: Vec::new(),
            backward_schedule: Vec::new(),
            best_schedule: Vec::new(),
            forward_length: 0,
            backward_length: 0,
        }
    }

    /// Run bidirectional scheduling on a dependence graph.
    ///
    /// Returns the best schedule (vector of instruction indices).
    pub fn schedule(&mut self, graph: &DepGraph, instructions: &[MachineInstr]) -> Vec<usize> {
        let n = graph.node_count;
        if n == 0 {
            return Vec::new();
        }

        // Forward (top-down) scheduling
        let cp = self.compute_critical_paths(graph);
        self.forward_schedule = self.top_down_schedule(graph, &cp);
        self.forward_length = self.compute_schedule_length(&self.forward_schedule, instructions);

        // Backward (bottom-up) scheduling
        let rev_graph = self.reverse_graph(graph);
        let rev_cp = self.compute_critical_paths(&rev_graph);
        let mut rev_schedule = self.top_down_schedule(&rev_graph, &rev_cp);
        // Reverse the schedule to get original instruction order
        rev_schedule.reverse();
        self.backward_schedule = rev_schedule;
        self.backward_length = self.compute_schedule_length(&self.backward_schedule, instructions);

        // Pick the best
        if self.forward_length <= self.backward_length {
            self.best_schedule = self.forward_schedule.clone();
        } else {
            self.best_schedule = self.backward_schedule.clone();
        }

        self.best_schedule.clone()
    }

    /// Compute critical paths for a graph.
    fn compute_critical_paths(&self, graph: &DepGraph) -> Vec<u32> {
        let n = graph.node_count;
        let mut cp = vec![0u32; n];

        for idx in (0..n).rev() {
            let node_latency = graph.nodes[idx].latency;
            let mut max_succ = 0u32;
            for &succ in &graph.nodes[idx].successors {
                if succ < n {
                    max_succ = max_succ.max(cp[succ]);
                }
            }
            cp[idx] = node_latency + max_succ;
        }

        cp
    }

    /// Top-down list scheduling.
    fn top_down_schedule(&self, graph: &DepGraph, cp: &[u32]) -> Vec<usize> {
        let n = graph.node_count;
        let mut schedule = Vec::with_capacity(n);

        let mut unscheduled_preds: Vec<usize> = graph
            .nodes
            .iter()
            .map(|node| node.unscheduled_preds)
            .collect();

        let mut ready: Vec<usize> = (0..n).filter(|&i| unscheduled_preds[i] == 0).collect();

        while !ready.is_empty() {
            ready.sort_by(|&a, &b| cp[b].cmp(&cp[a]).then_with(|| a.cmp(&b)));
            let selected = ready.remove(0);
            schedule.push(selected);

            for &succ in &graph.nodes[selected].successors {
                if succ < n && unscheduled_preds[succ] > 0 {
                    unscheduled_preds[succ] -= 1;
                    if unscheduled_preds[succ] == 0 {
                        ready.push(succ);
                    }
                }
            }
        }

        schedule
    }

    /// Reverse a dependence graph (swap successors and predecessors).
    fn reverse_graph(&self, graph: &DepGraph) -> DepGraph {
        let n = graph.node_count;
        let mut rev = DepGraph::new();

        for node in &graph.nodes {
            rev.nodes.push(SchedNode {
                instr_idx: node.instr_idx,
                opcode: node.opcode,
                latency: node.latency,
                critical_path: 0,
                successors: node.predecessors.clone(),
                predecessors: node.successors.clone(),
                scheduled: false,
                unscheduled_preds: node.successors.len(),
            });
        }
        rev.node_count = n;
        rev
    }

    /// Compute the total length (in cycles) of a schedule, considering
    /// resource constraints and operation latencies.
    fn compute_schedule_length(&self, schedule: &[usize], instructions: &[MachineInstr]) -> u32 {
        if schedule.is_empty() {
            return 0;
        }

        let mut completion_times: Vec<u32> = vec![0; schedule.len()];
        let mut position: HashMap<usize, usize> = HashMap::new();

        for (pos, &idx) in schedule.iter().enumerate() {
            position.insert(idx, pos);
        }

        for (pos, &idx) in schedule.iter().enumerate() {
            if idx >= instructions.len() {
                continue;
            }
            let latency = self.resource_model.get_latency(instructions[idx].opcode);
            let mut start_time = 0u32;

            // Find max completion time of dependencies
            // (simplified: use position-based heuristic)
            for earlier_pos in 0..pos {
                let earlier_idx = schedule[earlier_pos];
                if earlier_idx >= instructions.len() {
                    continue;
                }
                // Check RAW dependence (simplified)
                let earlier_def = instructions[earlier_idx].def;
                let uses_earlier = instructions[idx].operands.iter().any(|op| match op {
                    MachineOperand::Reg(r) => earlier_def == Some(*r),
                    _ => false,
                });
                if uses_earlier {
                    start_time = start_time.max(completion_times[earlier_pos]);
                }
            }

            completion_times[pos] = start_time + latency;
        }

        completion_times.last().copied().unwrap_or(0)
    }

    /// Get statistics about the bidirectional schedule.
    pub fn print_stats(&self) {
        eprintln!("BidirectionalScheduler stats:");
        eprintln!("  Forward length:  {} cycles", self.forward_length);
        eprintln!("  Backward length: {} cycles", self.backward_length);
        eprintln!(
            "  Best: {} ({} schedule)",
            self.forward_length.min(self.backward_length),
            if self.forward_length <= self.backward_length {
                "forward"
            } else {
                "backward"
            }
        );
    }
}

impl Default for BidirectionalScheduler {
    fn default() -> Self {
        Self::new("generic")
    }
}

// ============================================================================
// Instruction Itinerary (target pipeline description)
// ============================================================================

/// Describes the pipeline behavior of a class of instructions.
#[derive(Debug, Clone)]
pub struct InstrItinerary {
    /// Name of this itinerary class.
    pub name: String,
    /// Opcodes in this class.
    pub opcodes: Vec<u32>,
    /// Number of micro-ops this instruction decodes into.
    pub num_micro_ops: u32,
    /// Pipeline stages: (stage_name, cycles).
    pub stages: Vec<(String, u32)>,
    /// Which functional unit port each uop uses.
    pub ports: Vec<usize>,
    /// Whether this instruction can be dual-issued.
    pub dual_issue: bool,
    /// Reservation table for this itinerary.
    pub reservation: Option<ReservationTable>,
}

/// ItineraryData holds all instruction itineraries for a target.
#[derive(Debug, Clone)]
pub struct ItineraryData {
    /// Target triple.
    pub target: String,
    /// Instruction itineraries indexed by class.
    pub itineraries: Vec<InstrItinerary>,
    /// Map from opcode to itinerary index.
    pub opcode_map: HashMap<u32, usize>,
}

impl ItineraryData {
    /// Create empty itinerary data.
    pub fn new(target: &str) -> Self {
        Self {
            target: target.to_string(),
            itineraries: Vec::new(),
            opcode_map: HashMap::new(),
        }
    }

    /// Add an itinerary class.
    pub fn add_itinerary(&mut self, itinerary: InstrItinerary) {
        let idx = self.itineraries.len();
        for &opcode in &itinerary.opcodes {
            self.opcode_map.insert(opcode, idx);
        }
        self.itineraries.push(itinerary);
    }

    /// Get the itinerary for an opcode.
    pub fn get_itinerary(&self, opcode: u32) -> Option<&InstrItinerary> {
        self.opcode_map
            .get(&opcode)
            .and_then(|&idx| self.itineraries.get(idx))
    }

    /// Get the number of micro-ops for an opcode.
    pub fn get_num_micro_ops(&self, opcode: u32) -> u32 {
        self.get_itinerary(opcode)
            .map(|i| i.num_micro_ops)
            .unwrap_or(1)
    }

    /// Get the latency of an opcode.
    pub fn get_latency(&self, opcode: u32) -> u32 {
        self.get_itinerary(opcode)
            .map(|i| i.stages.iter().map(|(_, c)| *c).sum())
            .unwrap_or(1)
    }

    /// Check if two opcodes can be dual-issued.
    pub fn can_dual_issue(&self, op_a: u32, op_b: u32) -> bool {
        let it_a = self.get_itinerary(op_a);
        let it_b = self.get_itinerary(op_b);

        match (it_a, it_b) {
            (Some(a), Some(b)) => {
                // Check port conflicts
                let ports_a: HashSet<usize> = a.ports.iter().copied().collect();
                let ports_b: HashSet<usize> = b.ports.iter().copied().collect();
                ports_a.is_disjoint(&ports_b) && a.dual_issue && b.dual_issue
            }
            _ => false,
        }
    }

    /// Create default x86-64 itinerary data.
    pub fn x86_64_default() -> Self {
        let mut data = Self::new("x86_64");

        // ALU simple: 1 uop, port 0/1/5/6
        data.add_itinerary(InstrItinerary {
            name: "ALU".to_string(),
            opcodes: vec![1],
            num_micro_ops: 1,
            stages: vec![("Issue".to_string(), 1), ("Execute".to_string(), 1)],
            ports: vec![0, 1, 5, 6],
            dual_issue: true,
            reservation: Some(ReservationTable::alu_default()),
        });

        // Load: 1 uop, port 2/3
        data.add_itinerary(InstrItinerary {
            name: "Load".to_string(),
            opcodes: vec![2],
            num_micro_ops: 1,
            stages: vec![
                ("Issue".to_string(), 1),
                ("AGU".to_string(), 1),
                ("Cache".to_string(), 3),
            ],
            ports: vec![2, 3],
            dual_issue: true,
            reservation: Some(ReservationTable::load_default()),
        });

        // Store: 1 uop, port 4
        data.add_itinerary(InstrItinerary {
            name: "Store".to_string(),
            opcodes: vec![3],
            num_micro_ops: 1,
            stages: vec![
                ("Issue".to_string(), 1),
                ("AGU".to_string(), 1),
                ("StoreData".to_string(), 1),
            ],
            ports: vec![4],
            dual_issue: false,
            reservation: None,
        });

        data
    }
}

impl Default for ItineraryData {
    fn default() -> Self {
        Self::new("generic")
    }
}

// ============================================================================
// Full ScheduleDAG: builds complete DAG from MBB with regions
// ============================================================================

/// FullScheduleDAG builds a complete scheduling DAG from a machine
/// basic block, incorporating scheduling regions, resource models,
/// and hazard detection.
#[derive(Debug, Clone)]
pub struct FullScheduleDAG {
    /// The underlying dependence graph.
    pub graph: DepGraph,
    /// Scheduling regions within the block.
    pub regions: Vec<SchedulingRegion>,
    /// Critical path lengths per node.
    pub critical_paths: Vec<u32>,
    /// Node depths (distance from entry).
    pub depths: Vec<u32>,
    /// Node heights (distance to exit).
    pub heights: Vec<u32>,
    /// Resource model for the target.
    pub resource_model: ResourceModel,
    /// Hazard recognizer.
    pub hazard: HazardRecognizer,
    /// Forwarding model.
    pub forwarding: ForwardingModel,
}

impl FullScheduleDAG {
    /// Build a full scheduling DAG from a machine basic block.
    pub fn from_basic_block(instructions: &[MachineInstr], target: &str) -> Self {
        let n = instructions.len();
        let resource_model = ResourceModel::default_model();
        let hazard = HazardRecognizer::new(8, true);
        let forwarding = ForwardingModel::x86_64_default();

        // Build dependence graph
        let mut graph = DepGraph::new();
        for (idx, mi) in instructions.iter().enumerate() {
            let latency = resource_model.get_latency(mi.opcode);
            graph.nodes.push(SchedNode {
                instr_idx: idx,
                opcode: mi.opcode,
                latency,
                critical_path: 0,
                successors: Vec::new(),
                predecessors: Vec::new(),
                scheduled: false,
                unscheduled_preds: 0,
            });
        }
        graph.node_count = n;

        // Build def-use chains
        let mut last_def: HashMap<u64, usize> = HashMap::new();
        let mut last_use: HashMap<u64, Vec<usize>> = HashMap::new();

        for (idx, mi) in instructions.iter().enumerate() {
            let def_regs: Vec<u64> = mi.def.into_iter().map(|d| d as u64).collect();
            let use_regs: Vec<u64> = mi
                .operands
                .iter()
                .filter_map(|op| match op {
                    MachineOperand::Reg(r) => Some(*r as u64),
                    MachineOperand::PhysReg(pr) => Some(*pr as u64 + (1u64 << 32)),
                    _ => None,
                })
                .collect();

            for &reg in &use_regs {
                if let Some(&def_idx) = last_def.get(&reg) {
                    if def_idx < idx {
                        graph.nodes[def_idx].successors.push(idx);
                        graph.nodes[idx].predecessors.push(def_idx);
                    }
                }
                last_use.entry(reg).or_default().push(idx);
            }

            for &reg in &def_regs {
                if let Some(&prev_def) = last_def.get(&reg) {
                    if prev_def < idx {
                        graph.nodes[prev_def].successors.push(idx);
                        graph.nodes[idx].predecessors.push(prev_def);
                    }
                }
                if let Some(prev_uses) = last_use.get(&reg) {
                    for &use_idx in prev_uses {
                        if use_idx < idx {
                            graph.nodes[use_idx].successors.push(idx);
                            graph.nodes[idx].predecessors.push(use_idx);
                        }
                    }
                }
                last_def.insert(reg, idx);
                last_use.remove(&reg);
            }
        }

        for node in &mut graph.nodes {
            node.unscheduled_preds = node.predecessors.len();
        }

        // Build scheduling regions
        let mut region_builder = RegionBuilder::new(target, false);
        region_builder.build_regions(instructions);

        // Compute critical paths
        let mut critical_paths = vec![0u32; n];
        for idx in (0..n).rev() {
            let node_latency = graph.nodes[idx].latency;
            let mut max_succ = 0u32;
            for &succ in &graph.nodes[idx].successors {
                if succ < n {
                    max_succ = max_succ.max(critical_paths[succ]);
                }
            }
            critical_paths[idx] = node_latency + max_succ;
        }

        // Compute depths (forward pass)
        let mut depths = vec![0u32; n];
        for idx in 0..n {
            let mut max_pred = 0u32;
            for &pred in &graph.nodes[idx].predecessors {
                if pred < n {
                    max_pred = max_pred.max(depths[pred] + graph.nodes[pred].latency);
                }
            }
            depths[idx] = max_pred;
        }

        // Compute heights (backward pass = critical path)
        let heights = critical_paths.clone();

        Self {
            graph,
            regions: region_builder.regions,
            critical_paths,
            depths,
            heights,
            resource_model,
            hazard,
            forwarding,
        }
    }

    /// Get nodes that are ready to schedule (all predecessors scheduled).
    pub fn ready_nodes(&self, scheduled: &[bool]) -> Vec<usize> {
        (0..self.graph.node_count)
            .filter(|&i| {
                if scheduled[i] {
                    return false;
                }
                self.graph.nodes[i]
                    .predecessors
                    .iter()
                    .all(|&p| scheduled[p])
            })
            .collect()
    }

    /// Estimate the schedule length in cycles.
    pub fn estimate_length(&self) -> u32 {
        self.critical_paths.iter().copied().max().unwrap_or(0)
    }

    /// Get the maximum depth.
    pub fn max_depth(&self) -> u32 {
        self.depths.iter().copied().max().unwrap_or(0)
    }

    /// Print the DAG structure.
    pub fn print_dag(&self) {
        eprintln!(
            "FullScheduleDAG: {} nodes, {} regions",
            self.graph.node_count,
            self.regions.len()
        );
        eprintln!("  Critical path: {}", self.estimate_length());
        eprintln!("  Max depth: {}", self.max_depth());
        for region in &self.regions {
            eprintln!(
                "  Region [{}-{}] top={} bottom={} term={}",
                region.start, region.end, region.is_top, region.is_bottom, region.has_terminator
            );
        }
    }
}

// ============================================================================
// ScheduleDAG Mutation — Artificial Dependencies
// ============================================================================

/// ScheduleDAGMutator adds artificial dependencies to the DAG
/// to prevent illegal reordering that the scheduler might otherwise try.
///
/// Common mutation operations:
/// - Barrier edges: prevent any reordering across certain instructions
/// - Anti-dependency breaking: insert COPY to rename registers
/// - Serialization: enforce order for memory operations that may alias
pub struct ScheduleDAGMutator {
    /// Whether to enforce strict memory ordering.
    pub enforce_mem_order: bool,
    /// Whether to break anti-dependencies with register renaming.
    pub break_anti_deps: bool,
    /// Added edges count.
    pub added_edges: usize,
}

impl ScheduleDAGMutator {
    pub fn new() -> Self {
        Self {
            enforce_mem_order: true,
            break_anti_deps: true,
            added_edges: 0,
        }
    }

    /// Add artificial barrier edges from memory stores to subsequent loads
    /// when we cannot prove they don't alias.
    pub fn add_memory_barriers(&mut self, graph: &mut DepGraph, instrs: &[MachineInstr]) {
        for i in 0..graph.node_count {
            for j in (i + 1)..graph.node_count {
                let is_store_i = Self::is_store(&instrs[i].opcode);
                let is_load_j = Self::is_load(&instrs[j].opcode);
                let is_store_j = Self::is_store(&instrs[j].opcode);

                // Store → Load or Store → Store: may alias
                if is_store_i && (is_load_j || is_store_j) {
                    if !graph.nodes[i].successors.contains(&j) {
                        graph.nodes[i].successors.push(j);
                        graph.nodes[j].predecessors.push(i);
                        graph.nodes[j].unscheduled_preds += 1;
                        self.added_edges += 1;
                    }
                }
            }
        }
    }

    fn is_store(opcode: &u32) -> bool {
        // Opcode 3 = store in default model, plus PUSH/STOS variants
        matches!(opcode, 3 | 11 | 117) // store, PUSH, STOS
    }

    fn is_load(opcode: &u32) -> bool {
        matches!(opcode, 2 | 12 | 118) // load, POP, LODS
    }
}

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

// ============================================================================
// Copy Suppression — eliminate COPY instructions
// ============================================================================

/// CopySuppressor eliminates COPY instructions by reusing the source
/// register when possible. This reduces register pressure and
/// improves schedule quality.
#[derive(Debug, Clone)]
pub struct CopySuppressor {
    /// Number of copies eliminated.
    pub copies_eliminated: usize,
    /// Map from destination register to source register.
    copy_map: HashMap<u64, u64>,
}

impl CopySuppressor {
    pub fn new() -> Self {
        Self {
            copies_eliminated: 0,
            copy_map: HashMap::new(),
        }
    }

    /// Process a basic block, removing COPY instructions where possible.
    pub fn suppress_copies(&mut self, instrs: &mut Vec<MachineInstr>) {
        self.copy_map.clear();
        let mut new_instrs = Vec::new();

        for mi in instrs.drain(..) {
            // Check if this is a COPY instruction (opcode 1 = MOV r,r)
            if mi.opcode == 1 && mi.def.is_some() && mi.operands.len() == 1 {
                if let MachineOperand::Reg(src) = mi.operands[0] {
                    if let Some(dst) = mi.def {
                        // Record the copy: dst can be replaced by src
                        self.copy_map.insert(dst as u64, src as u64);
                        self.copies_eliminated += 1;
                        continue; // Skip this instruction
                    }
                }
            }

            // Rewrite operands using the copy map
            let mut rewritten = mi.clone();
            for op in &mut rewritten.operands {
                if let MachineOperand::Reg(r) = op {
                    if let Some(&src) = self.copy_map.get(&(*r as u64)) {
                        *op = MachineOperand::Reg(src as u32);
                    }
                }
            }
            new_instrs.push(rewritten);
        }

        *instrs = new_instrs;
    }
}

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

// ============================================================================
// Load/Store Clustering — group memory ops for cache efficiency
// ============================================================================

/// LoadClustering groups loads that access the same cache line
/// to exploit hardware prefetching and reduce cache miss latency.
pub struct LoadClusterer {
    /// Cache line size in bytes (typically 64).
    pub cache_line_size: u32,
    /// Maximum number of loads to cluster together.
    pub max_cluster_size: usize,
    /// Number of loads clustered.
    pub loads_clustered: usize,
}

impl LoadClusterer {
    pub fn new() -> Self {
        Self {
            cache_line_size: 64,
            max_cluster_size: 8,
            loads_clustered: 0,
        }
    }

    /// Cluster loads that access nearby memory addresses.
    ///
    /// Strategy: sort loads by their displacement/address, then group
    /// contiguous addresses into clusters. This helps the hardware
    /// prefetcher and reduces cache miss penalties.
    pub fn cluster_loads(&mut self, instrs: &mut [MachineInstr]) {
        let n = instrs.len();
        if n < 2 {
            return;
        }

        // Collect load instructions with their indices and addresses
        let mut load_info: Vec<(usize, i64)> = Vec::new();
        for (i, mi) in instrs.iter().enumerate() {
            if mi.opcode == 2 {
                // Extract displacement if available
                let addr = mi
                    .operands
                    .iter()
                    .find_map(|op| {
                        if let MachineOperand::Imm(imm) = op {
                            Some(*imm)
                        } else {
                            None
                        }
                    })
                    .unwrap_or(0);
                load_info.push((i, addr));
            }
        }

        if load_info.len() < 2 {
            return;
        }

        // Sort by address
        load_info.sort_by_key(|(_, addr)| *addr);

        // Cluster loads within same cache line
        let mut cluster_start = 0;
        for i in 1..load_info.len() {
            let (_, prev_addr) = load_info[cluster_start];
            let (_, curr_addr) = load_info[i];

            let same_line = (prev_addr as u64 / self.cache_line_size as u64)
                == (curr_addr as u64 / self.cache_line_size as u64);
            let cluster_full = (i - cluster_start) >= self.max_cluster_size;

            if !same_line || cluster_full {
                // End current cluster
                let count = i - cluster_start;
                if count > 1 {
                    self.loads_clustered += count;
                }
                cluster_start = i;
            }
        }

        // Last cluster
        let remaining = load_info.len() - cluster_start;
        if remaining > 1 {
            self.loads_clustered += remaining;
        }
    }
}

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

/// StoreClustering groups stores to the same cache line for write combining
/// efficiency in the store buffer and L1 data cache.
pub struct StoreClusterer {
    /// Cache line size in bytes (typically 64).
    pub cache_line_size: u32,
    /// Maximum stores in a write-combining cluster.
    pub max_cluster_size: usize,
    /// Number of stores clustered.
    pub stores_clustered: usize,
}

impl StoreClusterer {
    pub fn new() -> Self {
        Self {
            cache_line_size: 64,
            max_cluster_size: 6,
            stores_clustered: 0,
        }
    }

    /// Cluster stores that write to same or adjacent cache lines.
    pub fn cluster_stores(&mut self, instrs: &mut [MachineInstr]) {
        let n = instrs.len();
        if n < 2 {
            return;
        }

        let mut store_info: Vec<(usize, i64)> = Vec::new();
        for (i, mi) in instrs.iter().enumerate() {
            if mi.opcode == 3 {
                let addr = mi
                    .operands
                    .iter()
                    .find_map(|op| {
                        if let MachineOperand::Imm(imm) = op {
                            Some(*imm)
                        } else {
                            None
                        }
                    })
                    .unwrap_or(0);
                store_info.push((i, addr));
            }
        }

        if store_info.len() < 2 {
            return;
        }

        store_info.sort_by_key(|(_, addr)| *addr);

        let mut cluster_start = 0;
        for i in 1..store_info.len() {
            let (_, prev_addr) = store_info[cluster_start];
            let (_, curr_addr) = store_info[i];

            let same_line = (prev_addr as u64 / self.cache_line_size as u64)
                == (curr_addr as u64 / self.cache_line_size as u64);
            let cluster_full = (i - cluster_start) >= self.max_cluster_size;

            if !same_line || cluster_full {
                let count = i - cluster_start;
                if count > 1 {
                    self.stores_clustered += count;
                }
                cluster_start = i;
            }
        }

        let remaining = store_info.len() - cluster_start;
        if remaining > 1 {
            self.stores_clustered += remaining;
        }
    }
}

// ============================================================================
// Complete MacroFusion — fusion patterns per microarchitecture
// ============================================================================

/// MacroFusionPair represents a recognized fusion pair of instructions.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MacroFusionKind {
    /// CMP + JCC: compare and branch fused into single uop
    CmpJcc,
    /// TEST + JCC: test and branch fused into single uop
    TestJcc,
    /// ADD/SUB + JCC: arithmetic with compare result + branch
    AddJcc,
    /// AND + JCC: bitwise AND + branch
    AndJcc,
    /// XOR + JCC: bitwise XOR + branch
    XorJcc,
    /// INC/DEC + JCC: increment/decrement + branch
    IncJcc,
    /// SUB + JCC (specific form: SUB reg,imm + JCC)
    SubJcc,
}

/// MacroFusionDetector identifies instruction pairs that can be fused
/// into single uops on supported microarchitectures.
#[derive(Debug, Clone)]
pub struct MacroFusionDetector {
    /// Whether the target supports macro-fusion.
    pub support_fusion: bool,
    /// Whether the target supports fusion of 2nd-gen patterns (ADD+JCC, etc.).
    pub support_extended_fusion: bool,
    /// Detected fusion pairs.
    pub detected_pairs: Vec<(usize, usize, MacroFusionKind)>,
}

impl MacroFusionDetector {
    /// Create a detector for a specific microarchitecture.
    pub fn new(microarch: &str) -> Self {
        // All modern x86 cores support CMP+JCC and TEST+JCC fusion.
        // Sandy Bridge+ adds fusion for ADD/SUB/INC/DEC + JCC.
        // Ice Lake+ supports AND/XOR + JCC.
        let extended = matches!(
            microarch,
            "sandybridge"
                | "ivybridge"
                | "haswell"
                | "broadwell"
                | "skylake"
                | "skylake_avx512"
                | "icelake"
                | "alderlake"
                | "raptorlake"
                | "meteorlake"
                | "lunarlake"
                | "zen3"
                | "zen4"
                | "zen5"
        );

        Self {
            support_fusion: true,
            support_extended_fusion: extended,
            detected_pairs: Vec::new(),
        }
    }

    /// Detect all fusion pairs in a sequence of instructions.
    pub fn detect_fusion_pairs(&mut self, instrs: &[MachineInstr]) {
        let n = instrs.len();
        if n < 2 {
            return;
        }

        for i in 0..(n - 1) {
            let first_op = instrs[i].opcode;
            let second_op = instrs[i + 1].opcode;

            if !Self::is_branch(second_op) {
                continue;
            }

            if let Some(kind) = Self::classify_fusion(first_op, self.support_extended_fusion) {
                self.detected_pairs.push((i, i + 1, kind));
            }
        }
    }

    fn is_branch(opcode: u32) -> bool {
        matches!(opcode, 7 | 8 | 9 | 15 | 16 | 17 | 102..=115) // JMP, JE, JNE, Jcc...
    }

    fn classify_fusion(opcode: u32, extended: bool) -> Option<MacroFusionKind> {
        match opcode {
            18 => Some(MacroFusionKind::CmpJcc),                  // CMP
            26 => Some(MacroFusionKind::TestJcc),                 // TEST
            2 if extended => Some(MacroFusionKind::AddJcc),       // ADD
            3 if extended => Some(MacroFusionKind::SubJcc),       // SUB
            6 if extended => Some(MacroFusionKind::AndJcc),       // AND
            8 if extended => Some(MacroFusionKind::XorJcc),       // XOR
            20 | 21 if extended => Some(MacroFusionKind::IncJcc), // INC/DEC
            _ => None,
        }
    }

    /// Return the instructions that should fuse as a single uop for scheduling.
    pub fn fused_uop_count(&self) -> usize {
        self.detected_pairs.len()
    }
}

// ============================================================================
// Complete MicroFusion — load+op and store+address fusion
// ============================================================================

/// MicroFusionDetector identifies load+op patterns that can be fused
/// into single uops at decode time (micro-fusion).
#[derive(Debug, Clone)]
pub struct MicroFusionDetector {
    /// Whether micro-fusion is supported.
    pub support_fusion: bool,
    /// Detected load+op fusion patterns.
    pub load_op_fusions: Vec<usize>,
    /// Detected store address+data fusions.
    pub store_fusions: Vec<usize>,
}

impl MicroFusionDetector {
    pub fn new() -> Self {
        Self {
            support_fusion: true,
            load_op_fusions: Vec::new(),
            store_fusions: Vec::new(),
        }
    }

    /// Detect load+op micro-fusion patterns.
    ///
    /// On Intel CPUs, a memory-source ALU operation (e.g., ADD r, [mem])
    /// micro-fuses the load and the ALU operation into a single uop.
    pub fn detect_load_op_fusion(&mut self, instrs: &[MachineInstr]) {
        for (i, mi) in instrs.iter().enumerate() {
            // Check for ALU ops that could have a memory operand
            let is_alu = matches!(mi.opcode, 2 | 3 | 6 | 7 | 8); // ADD, SUB, AND, OR, XOR
            if is_alu
                && mi
                    .operands
                    .iter()
                    .any(|op| matches!(op, MachineOperand::Reg(0..=31)))
            {
                // If one operand is a memory reference (represented as Reg(0)),
                // this can micro-fuse.
                self.load_op_fusions.push(i);
            }
        }
    }

    /// Detect store address+data micro-fusion patterns.
    pub fn detect_store_fusion(&mut self, instrs: &[MachineInstr]) {
        for (i, mi) in instrs.iter().enumerate() {
            if mi.opcode == 3 && mi.operands.len() >= 2 {
                self.store_fusions.push(i);
            }
        }
    }
}

// ============================================================================
// Loop / Branch Alignment — fetch efficiency optimization
// ============================================================================

/// LoopAligner ensures loop headers are aligned to optimal boundaries
/// (16 or 32 bytes) for maximum instruction fetch throughput.
///
/// On modern x86 CPUs, aligning loop tops to 16-byte or 32-byte
/// boundaries can improve performance by 5-15% for small, tight loops
/// due to better utilization of the instruction fetch unit.
#[derive(Debug, Clone)]
pub struct LoopAligner {
    /// Alignment boundary for loop headers (16 or 32).
    pub alignment: u32,
    /// Whether to align branch targets (not just loop headers).
    pub align_branches: bool,
    /// Maximum NOP bytes to insert for alignment.
    pub max_nop_bytes: u32,
    /// Number of alignment NOPs inserted.
    pub nops_inserted: usize,
}

impl LoopAligner {
    pub fn new(alignment: u32) -> Self {
        Self {
            alignment: alignment.clamp(8, 64),
            align_branches: false,
            max_nop_bytes: 15,
            nops_inserted: 0,
        }
    }

    /// Determine if NOPs are needed for alignment and compute the NOP count.
    pub fn compute_alignment_nops(&self, current_offset: u64) -> u32 {
        let remainder = (current_offset % self.alignment as u64) as u32;
        if remainder == 0 {
            return 0;
        }
        let needed = self.alignment - remainder;
        needed.min(self.max_nop_bytes)
    }

    /// Insert optimal NOP sequence for the given byte count.
    ///
    /// x86 NOP optimization: use multi-byte NOPs for efficiency.
    /// - 1 byte: 90 (NOP)
    /// - 2 bytes: 66 90 (66 NOP)
    /// - 3 bytes: 0F 1F 00 (NOP DWORD ptr [EAX])
    /// - 4 bytes: 0F 1F 40 00
    /// - 5 bytes: 0F 1F 44 00 00
    /// - 6 bytes: 66 0F 1F 44 00 00
    /// - 7 bytes: 0F 1F 80 00 00 00 00
    /// - 8 bytes: 0F 1F 84 00 00 00 00 00
    /// - 9 bytes: 66 0F 1F 84 00 00 00 00 00
    pub fn generate_nop_sequence(nop_count: u32) -> Vec<u8> {
        const NOP_TABLE: &[(u32, &[u8])] = &[
            (1, &[0x90]),
            (2, &[0x66, 0x90]),
            (3, &[0x0F, 0x1F, 0x00]),
            (4, &[0x0F, 0x1F, 0x40, 0x00]),
            (5, &[0x0F, 0x1F, 0x44, 0x00, 0x00]),
            (6, &[0x66, 0x0F, 0x1F, 0x44, 0x00, 0x00]),
            (7, &[0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00]),
            (8, &[0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00]),
            (9, &[0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00]),
        ];

        let mut remaining = nop_count;
        let mut seq = Vec::new();

        while remaining > 0 {
            let take = remaining.min(9);
            if let Some(&(_, nop_bytes)) = NOP_TABLE.iter().find(|(len, _)| *len == take) {
                seq.extend_from_slice(nop_bytes);
                remaining -= take;
            } else {
                seq.push(0x90); // fallback: simple NOP
                remaining -= 1;
            }
        }

        seq
    }

    /// Align a loop header by inserting NOPs before the loop entry.
    pub fn align_loop_header(&mut self, current_offset: u64, instrs: &mut Vec<MachineInstr>) {
        let nop_count = self.compute_alignment_nops(current_offset);
        if nop_count > 0 {
            // Insert a NOP instruction at the beginning
            let nop_instr = MachineInstr {
                opcode: 0, // NOP opcode
                operands: vec![MachineOperand::Imm(nop_count as i64)],
                def: None,
                size: 0,
            };
            instrs.insert(0, nop_instr);
            self.nops_inserted += 1;
        }
    }
}

// ============================================================================
// Prefix Optimization — minimize prefix bytes
// ============================================================================

/// PrefixOptimizer reorders or modifies instructions to minimize
/// the number of prefix bytes (REX, VEX, EVEX, segment overrides)
/// which improve decode bandwidth on modern CPUs.
#[derive(Debug, Clone)]
pub struct PrefixOptimizer {
    /// Whether REX prefix elimination is attempted.
    pub optimize_rex: bool,
    /// Number of prefix bytes saved.
    pub prefix_bytes_saved: usize,
}

impl PrefixOptimizer {
    pub fn new() -> Self {
        Self {
            optimize_rex: true,
            prefix_bytes_saved: 0,
        }
    }

    /// Optimize prefix usage in a sequence of instructions.
    ///
    /// Heuristics:
    /// - Use 32-bit registers when possible to avoid REX prefix
    /// - Group instructions by prefix type to amortize prefix cost
    /// - Prefer VEX-encoded instructions over legacy SSE for shorter encoding
    pub fn optimize(&mut self, instrs: &[MachineInstr]) -> usize {
        let mut saved = 0usize;

        for mi in instrs {
            // Check for instructions that might use REX unnecessarily
            if let Some(def) = mi.def {
                // Registers 0-7 in 64-bit mode don't need REX,
                // while registers 8-15 need REX prefix (1 byte)
                if def >= 8 {
                    // Could potentially be remapped by RA to avoid REX
                }
            }

            // Check operands for high registers needing REX
            for op in &mi.operands {
                if let MachineOperand::Reg(r) = op {
                    if *r >= 8 {
                        // This instruction needs a REX prefix
                        // The optimizer cannot always avoid this, but tracks it
                    }
                }
            }
        }

        self.prefix_bytes_saved += saved;
        saved
    }
}

// ============================================================================
// Sub-Register Liveness Tracking
// ============================================================================

/// SubRegLiveness tracks liveness of sub-registers (e.g., AL, AH, AX, EAX
/// within RAX) for more precise scheduling decisions.
pub struct SubRegLiveness {
    /// Liveness intervals for each sub-register component.
    pub live_ranges: HashMap<u32, (usize, usize)>,
    /// Whether sub-register tracking is enabled.
    pub enabled: bool,
}

impl SubRegLiveness {
    pub fn new() -> Self {
        Self {
            live_ranges: HashMap::new(),
            enabled: true,
        }
    }

    /// Check if two instructions have overlapping sub-register liveness.
    pub fn overlaps(&self, reg: u32, cycle_a: usize, cycle_b: usize) -> bool {
        if let Some(&(start, end)) = self.live_ranges.get(&reg) {
            let overlap_start = start.max(cycle_a);
            let overlap_end = end.min(cycle_b);
            overlap_start <= overlap_end
        } else {
            false
        }
    }

    /// Record a sub-register access at a given cycle.
    pub fn record_access(&mut self, reg: u32, cycle: usize) {
        let entry = self.live_ranges.entry(reg).or_insert((cycle, cycle));
        entry.0 = entry.0.min(cycle);
        entry.1 = entry.1.max(cycle);
    }
}

// ============================================================================
// VLIW Packet Formation
// ============================================================================

/// VLIWPacketFormation groups instructions into VLIW bundles (packets)
/// for VLIW architectures (e.g., Hexagon, Itanium).
///
/// Each packet executes in parallel, and instructions within a packet
/// must not have dependences between them.
#[derive(Debug, Clone)]
pub struct VLIWPacketFormation {
    /// Maximum instructions per packet (issue width).
    pub max_per_packet: usize,
    /// Packets formed.
    pub packets: Vec<Vec<usize>>,
}

impl VLIWPacketFormation {
    pub fn new(issue_width: usize) -> Self {
        Self {
            max_per_packet: issue_width,
            packets: Vec::new(),
        }
    }

    /// Form VLIW packets from a ready list, ensuring no intra-packet dependences.
    pub fn form_packets(&mut self, ready_nodes: &[usize], graph: &DepGraph) {
        let mut current_packet: Vec<usize> = Vec::new();
        let mut used_nodes: HashSet<usize> = HashSet::new();

        for &node in ready_nodes {
            if current_packet.len() >= self.max_per_packet {
                self.packets.push(std::mem::take(&mut current_packet));
            }

            // Check if this node has a dependence on any node already in the packet
            let has_dep = current_packet.iter().any(|&p| {
                graph.nodes[p].successors.contains(&node)
                    || graph.nodes[node].predecessors.contains(&p)
            });

            if has_dep || used_nodes.contains(&node) {
                continue;
            }

            current_packet.push(node);
            used_nodes.insert(node);
        }

        if !current_packet.is_empty() {
            self.packets.push(current_packet);
        }
    }

    /// Get the number of packets formed.
    pub fn packet_count(&self) -> usize {
        self.packets.len()
    }

    /// Get the utilization (instructions / max capacity).
    pub fn utilization(&self) -> f64 {
        let total_instrs: usize = self.packets.iter().map(|p| p.len()).sum();
        let max_capacity = self.packets.len() * self.max_per_packet;
        if max_capacity == 0 {
            0.0
        } else {
            total_instrs as f64 / max_capacity as f64
        }
    }
}

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

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

    fn make_mi(opcode: u32, def: Option<u32>) -> MachineInstr {
        MachineInstr {
            opcode,
            operands: Vec::new(),
            def,
        }
    }

    fn make_mi_with_ops(
        opcode: u32,
        def: Option<u32>,
        operands: Vec<MachineOperand>,
    ) -> MachineInstr {
        MachineInstr {
            opcode,
            operands,
            def,
        }
    }

    #[test]
    fn test_resource_model_default() {
        let model = ResourceModel::default_model();
        assert_eq!(model.issue_width, 4);
        assert_eq!(model.resources.len(), 4);
        assert_eq!(model.get_latency(1), 1);
        assert_eq!(model.get_latency(2), 3);
        assert_eq!(model.get_latency(999), 1); // unknown, default 1
    }

    #[test]
    fn test_machine_scheduler_new() {
        let ms = MachineScheduler::new("x86_64-unknown-linux-gnu");
        assert_eq!(ms.target, "x86_64-unknown-linux-gnu");
        assert_eq!(ms.reordered, 0);
        assert_eq!(ms.resource_model.issue_width, 4);
    }

    #[test]
    fn test_machine_scheduler_default() {
        let ms = MachineScheduler::default();
        assert_eq!(ms.target, "generic");
    }

    #[test]
    fn test_build_dependence_graph_empty() {
        let ms = MachineScheduler::new("test");
        let instructions: Vec<MachineInstr> = Vec::new();
        let graph = ms.build_dependence_graph(&instructions);
        assert_eq!(graph.node_count, 0);
    }

    #[test]
    fn test_build_dependence_graph_single() {
        let ms = MachineScheduler::new("test");
        let instructions = vec![make_mi(1, Some(1))];
        let graph = ms.build_dependence_graph(&instructions);
        assert_eq!(graph.node_count, 1);
        assert!(graph.nodes[0].predecessors.is_empty());
        assert!(graph.nodes[0].successors.is_empty());
    }

    #[test]
    fn test_build_dependence_graph_raw() {
        let ms = MachineScheduler::new("test");
        // instr 0: r1 = ...
        // instr 1: ... = r1 (RAW: 0 → 1)
        let instructions = vec![
            make_mi_with_ops(1, Some(1), vec![]),
            make_mi_with_ops(2, None, vec![MachineOperand::Reg(1)]),
        ];
        let graph = ms.build_dependence_graph(&instructions);
        assert_eq!(graph.node_count, 2);
        // Node 1 should depend on node 0 (RAW)
        assert!(graph.nodes[1].predecessors.contains(&0));
        assert!(graph.nodes[0].successors.contains(&1));
    }

    #[test]
    fn test_build_dependence_graph_waw() {
        let ms = MachineScheduler::new("test");
        // Both define r1 → WAW: 0 → 1
        let instructions = vec![make_mi(1, Some(1)), make_mi(2, Some(1))];
        let graph = ms.build_dependence_graph(&instructions);
        assert_eq!(graph.node_count, 2);
        assert!(graph.nodes[0].successors.contains(&1));
        assert!(graph.nodes[1].predecessors.contains(&0));
    }

    #[test]
    fn test_compute_critical_path_linear() {
        let ms = MachineScheduler::new("test");
        let mut graph = DepGraph::new();
        for i in 0..5 {
            graph.nodes.push(SchedNode {
                instr_idx: i,
                opcode: 1,
                latency: 2,
                critical_path: 0,
                successors: if i + 1 < 5 { vec![i + 1] } else { vec![] },
                predecessors: if i > 0 { vec![i - 1] } else { vec![] },
                scheduled: false,
                unscheduled_preds: if i > 0 { 1 } else { 0 },
            });
        }
        graph.node_count = 5;

        let cp = ms.compute_critical_path(&graph);
        assert_eq!(cp.len(), 5);
        // Linear chain: each node adds its latency
        assert_eq!(cp[4], 2); // last node
        assert_eq!(cp[3], 4); // latency 2 + succ's cp 2
        assert_eq!(cp[0], 10); // latency 2 * 5
    }

    #[test]
    fn test_list_schedule_simple() {
        let ms = MachineScheduler::new("test");
        let mut graph = DepGraph::new();
        for i in 0..3 {
            graph.nodes.push(SchedNode {
                instr_idx: i,
                opcode: 1,
                latency: 1,
                critical_path: 0,
                successors: Vec::new(),
                predecessors: Vec::new(),
                scheduled: false,
                unscheduled_preds: 0,
            });
        }
        graph.node_count = 3;

        // All independent → original order
        let cp = vec![1, 1, 1];
        let schedule = ms.list_schedule(&graph, &cp);
        assert_eq!(schedule.len(), 3);
        // Independent instructions, all ready at start, sorted by cp (equal)
        // then by original position
        assert_eq!(schedule, vec![0, 1, 2]);
    }

    #[test]
    fn test_list_schedule_with_deps() {
        let ms = MachineScheduler::new("test");
        let mut graph = DepGraph::new();
        // 0 → 1 → 2 (linear chain)
        graph.nodes.push(SchedNode {
            instr_idx: 0,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![1],
            predecessors: vec![],
            scheduled: false,
            unscheduled_preds: 0,
        });
        graph.nodes.push(SchedNode {
            instr_idx: 1,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![2],
            predecessors: vec![0],
            scheduled: false,
            unscheduled_preds: 1,
        });
        graph.nodes.push(SchedNode {
            instr_idx: 2,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![],
            predecessors: vec![1],
            scheduled: false,
            unscheduled_preds: 1,
        });
        graph.node_count = 3;

        let cp = vec![3, 2, 1];
        let schedule = ms.list_schedule(&graph, &cp);
        assert_eq!(schedule, vec![0, 1, 2]);
    }

    #[test]
    fn test_get_instruction_latency() {
        let ms = MachineScheduler::new("test");
        let mi = MachineInstr::new(1);
        let lat = ms.get_instruction_latency(&mi);
        assert_eq!(lat, 1);
    }

    #[test]
    fn test_compute_resource_conflicts_empty() {
        let ms = MachineScheduler::new("test");
        let schedule: Vec<usize> = Vec::new();
        let instructions: Vec<MachineInstr> = Vec::new();
        let conflicts = ms.compute_resource_conflicts(&schedule, &instructions);
        assert!(conflicts.is_empty());
    }

    #[test]
    fn test_schedule_empty_function() {
        let mut ms = MachineScheduler::new("test");
        let mut mf = MachineFunction::new("empty");
        let count = ms.schedule(&mut mf);
        assert_eq!(count, 0);
    }

    #[test]
    fn test_schedule_single_block() {
        let mut ms = MachineScheduler::new("test");
        let mut mf = MachineFunction::new("func");
        let mut mbb = MachineBasicBlock {
            name: "entry".to_string(),
            instructions: vec![make_mi(1, Some(1)), make_mi(2, None), make_mi(3, Some(2))],
            successors: Vec::new(),
        };
        mf.push_block(mbb);

        let count = ms.schedule(&mut mf);
        // All instructions independent, so schedule should just preserve order
        assert!(count >= 0);
        assert_eq!(mf.blocks[0].instructions.len(), 3);
    }

    #[test]
    fn test_hash_instruction() {
        let ms = MachineScheduler::new("test");
        let mi = make_mi(42, Some(7));
        let hash = ms.hash_instruction(&mi);
        assert_ne!(hash, 0);
    }

    #[test]
    fn test_reg_to_key() {
        let vreg = MachineOperand::Reg(5);
        let preg = MachineOperand::PhysReg(3);
        let imm = MachineOperand::Imm(42);

        assert_eq!(MachineScheduler::reg_to_key(&vreg), 5);
        assert_eq!(MachineScheduler::reg_to_key(&preg), 3 + (1u64 << 32));
        assert_eq!(MachineScheduler::reg_to_key(&imm), 0);
    }

    // --- Hazard Recognizer Tests ---

    #[test]
    fn test_hazard_recognizer_new() {
        let hr = HazardRecognizer::new(8, true);
        assert_eq!(hr.resource_count, 8);
        assert!(hr.forwarding_enabled);
        assert_eq!(hr.current_cycle, 0);
    }

    #[test]
    fn test_hazard_recognizer_default() {
        let hr = HazardRecognizer::default();
        assert_eq!(hr.resource_count, 8);
    }

    #[test]
    fn test_can_issue_no_hazards() {
        let hr = HazardRecognizer::new(4, false);
        let result = hr.can_issue(1, &[10], &[20], &[0]);
        assert_eq!(result, HazardKind::None);
    }

    #[test]
    fn test_can_issue_structural_hazard() {
        let mut hr = HazardRecognizer::new(4, false);
        hr.emit(1, &[10], &[], &[0]);
        // Same resource in same cycle should conflict
        let result = hr.can_issue(1, &[11], &[], &[0]);
        assert_eq!(result, HazardKind::Structural);
    }

    #[test]
    fn test_can_issue_raw_hazard() {
        let mut hr = HazardRecognizer::new(4, false);
        // Producer writes reg 10 with latency 3
        hr.set_latency(1, 3);
        hr.emit(1, &[10], &[], &[0]);
        hr.advance_cycle();
        // Consumer reads reg 10 at cycle 1, but it's not available until cycle 3
        let result = hr.can_issue(1, &[], &[10], &[0]);
        assert_eq!(result, HazardKind::RAW);
    }

    #[test]
    fn test_forwarding_reduces_raw_hazard() {
        let mut hr = HazardRecognizer::new(4, true);
        hr.set_latency(1, 1);
        hr.emit(1, &[10], &[], &[0]);
        hr.advance_cycle();
        // With forwarding, the result may be available sooner
        let result = hr.can_issue(1, &[], &[10], &[0]);
        // Distance of 1 cycle with forwarding should be OK
        assert_eq!(result, HazardKind::None);
    }

    #[test]
    fn test_hazard_reset() {
        let mut hr = HazardRecognizer::new(4, false);
        hr.emit(1, &[10], &[], &[0]);
        hr.reset();
        assert_eq!(hr.current_cycle, 0);
        assert!(hr.write_registers.is_empty());
        assert!(hr.resource_schedule.is_empty());
    }

    #[test]
    fn test_hazard_scheduled_cycles() {
        let mut hr = HazardRecognizer::new(4, false);
        assert_eq!(hr.scheduled_cycles(), 0);
        hr.advance_cycle();
        hr.advance_cycle();
        assert_eq!(hr.scheduled_cycles(), 2);
    }

    // --- Forwarding Model Tests ---

    #[test]
    fn test_forwarding_model_new() {
        let fm = ForwardingModel::new();
        assert!(fm.paths.is_empty());
        assert!(fm.base_latencies.is_empty());
    }

    #[test]
    fn test_forwarding_effective_latency_no_paths() {
        let mut fm = ForwardingModel::new();
        fm.set_latency(1, 3);
        assert_eq!(fm.get_effective_latency(1, 1), 3);
    }

    #[test]
    fn test_forwarding_reduces_latency() {
        let mut fm = ForwardingModel::new();
        fm.set_latency(1, 3);
        fm.add_path(ForwardingPath {
            from_stage: 2,
            to_stage: 1,
            latency_reduction: 1,
            universal: true,
            producer_opcodes: vec![],
            consumer_opcodes: vec![],
        });
        assert_eq!(fm.get_effective_latency(1, 1), 2);
    }

    #[test]
    fn test_forwarding_can_forward() {
        let mut fm = ForwardingModel::new();
        fm.set_latency(1, 3);
        fm.add_path(ForwardingPath {
            from_stage: 2,
            to_stage: 1,
            latency_reduction: 2,
            universal: false,
            producer_opcodes: vec![1],
            consumer_opcodes: vec![1],
        });
        assert!(fm.can_forward(1, 1));
        assert!(!fm.can_forward(2, 1));
    }

    #[test]
    fn test_forwarding_x86_64_default() {
        let fm = ForwardingModel::x86_64_default();
        assert!(!fm.paths.is_empty());
        assert!(fm.base_latencies.len() > 0);
    }

    #[test]
    fn test_forwarding_aarch64_default() {
        let fm = ForwardingModel::aarch64_default();
        assert!(!fm.paths.is_empty());
    }

    // --- MicroFusion Tests ---

    #[test]
    fn test_micro_fusion_new() {
        let mf = MicroFusion::new("x86_64");
        assert!(mf.enabled);
        assert_eq!(mf.target, "x86_64");
    }

    #[test]
    fn test_micro_fusion_disabled_empty_target() {
        let mf = MicroFusion::new("");
        assert!(!mf.enabled);
    }

    #[test]
    fn test_micro_fusion_can_fuse_load() {
        let mf = MicroFusion::x86_default();
        let addr = make_mi(8, Some(5)); // LEA defines r5
        let mem = make_mi_with_ops(2, None, vec![MachineOperand::Reg(5)]); // load uses r5
        assert!(mf.can_micro_fuse(&addr, &mem).is_some());
    }

    #[test]
    fn test_micro_fusion_cannot_fuse_no_def() {
        let mf = MicroFusion::x86_default();
        let addr = make_mi(8, None); // no def
        let mem = make_mi_with_ops(2, None, vec![MachineOperand::Reg(5)]);
        assert!(mf.can_micro_fuse(&addr, &mem).is_none());
    }

    // --- ClusterFormation Tests ---

    #[test]
    fn test_cluster_formation_new() {
        let cf = ClusterFormation::new(8);
        assert!(cf.enabled);
        assert_eq!(cf.max_cluster_size, 8);
        assert!(cf.clusters.is_empty());
    }

    #[test]
    fn test_cluster_formation_load_clusters() {
        let mut cf = ClusterFormation::new(8);
        let instrs = vec![
            make_mi_with_ops(2, Some(1), vec![MachineOperand::Reg(10)]),
            make_mi_with_ops(2, Some(2), vec![MachineOperand::Reg(10)]),
            make_mi_with_ops(2, Some(3), vec![MachineOperand::Reg(20)]),
        ];
        cf.form_clusters(&instrs);
        // Should form one load cluster (two loads with base 10)
        let loads = cf.load_clusters();
        assert_eq!(loads.len(), 1);
        assert_eq!(loads[0].instructions.len(), 2);
        assert_eq!(loads[0].base_register, 10);
    }

    #[test]
    fn test_cluster_formation_should_cluster() {
        let cf = ClusterFormation::new(8);
        let a = make_mi_with_ops(2, Some(1), vec![MachineOperand::Reg(10)]);
        let b = make_mi_with_ops(2, Some(2), vec![MachineOperand::Reg(10)]);
        assert!(cf.should_cluster(&a, &b));
    }

    // --- Scheduling Region Tests ---

    #[test]
    fn test_region_builder_new() {
        let rb = RegionBuilder::new("x86_64", false);
        assert_eq!(rb.region_count(), 0);
    }

    #[test]
    fn test_region_builder_empty() {
        let mut rb = RegionBuilder::new("generic", false);
        rb.build_regions(&[]);
        assert_eq!(rb.region_count(), 0);
    }

    #[test]
    fn test_region_builder_single_region() {
        let mut rb = RegionBuilder::new("generic", false);
        let instrs = vec![make_mi(1, Some(1)), make_mi(1, Some(2))];
        rb.build_regions(&instrs);
        assert_eq!(rb.region_count(), 1);
    }

    #[test]
    fn test_region_builder_split_on_branch() {
        let mut rb = RegionBuilder::new("generic", false);
        let instrs = vec![make_mi(1, Some(1)), make_mi(7, None), make_mi(1, Some(3))];
        rb.build_regions(&instrs);
        // Should split at the branch (opcode 7)
        assert!(rb.region_count() >= 1);
    }

    // --- Post-RA Scheduler Tests ---

    #[test]
    fn test_post_ra_scheduler_new() {
        let prs = PostRAScheduler::new("x86_64");
        assert_eq!(prs.target, "x86_64");
        assert!(prs.break_anti_deps);
    }

    #[test]
    fn test_post_ra_schedule_empty() {
        let mut prs = PostRAScheduler::new("test");
        let mut instrs: Vec<MachineInstr> = vec![];
        let count = prs.schedule(&mut instrs);
        assert_eq!(count, 0);
    }

    #[test]
    fn test_post_ra_schedule_single() {
        let mut prs = PostRAScheduler::new("test");
        let mut instrs = vec![make_mi(1, Some(1))];
        let count = prs.schedule(&mut instrs);
        assert_eq!(count, 0);
    }

    #[test]
    fn test_post_ra_break_anti_deps() {
        let prs = PostRAScheduler::new("test");
        let mut graph = DepGraph::new();
        // Create a WAR edge: instr 0 uses r5, instr 1 defines r5
        graph.nodes.push(SchedNode {
            instr_idx: 0,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![1],
            predecessors: vec![],
            scheduled: false,
            unscheduled_preds: 0,
        });
        graph.nodes.push(SchedNode {
            instr_idx: 1,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![],
            predecessors: vec![0],
            scheduled: false,
            unscheduled_preds: 1,
        });
        graph.node_count = 2;

        let mut instrs = vec![
            make_mi_with_ops(1, None, vec![MachineOperand::Reg(5)]),
            make_mi(1, Some(5)),
        ];
        let broken = prs.break_anti_dependencies(&mut graph, &mut instrs);
        assert!(broken >= 0);
    }

    // --- Reservation Table Tests ---

    #[test]
    fn test_reservation_table_new() {
        let rt = ReservationTable::new(5, 4, 1);
        assert_eq!(rt.num_stages, 5);
        assert_eq!(rt.num_units, 4);
        assert_eq!(rt.duration, 5);
    }

    #[test]
    fn test_reservation_table_reserve() {
        let mut rt = ReservationTable::new(5, 4, 1);
        rt.reserve(0, 0);
        assert!(rt.is_reserved(0, 0));
        assert!(!rt.is_reserved(0, 1));
    }

    #[test]
    fn test_reservation_table_collision() {
        let mut rt1 = ReservationTable::new(5, 4, 1);
        rt1.reserve(0, 0);
        let mut rt2 = ReservationTable::new(5, 4, 2);
        rt2.reserve(0, 0);
        // Same unit same cycle -> collision
        assert!(rt1.collides_with(&rt2, 0));
    }

    #[test]
    fn test_reservation_table_no_collision() {
        let mut rt1 = ReservationTable::new(5, 4, 1);
        rt1.reserve(0, 0);
        let mut rt2 = ReservationTable::new(5, 4, 2);
        rt2.reserve(0, 1);
        // Different units -> no collision
        assert!(!rt1.collides_with(&rt2, 0));
    }

    #[test]
    fn test_reservation_table_alu_default() {
        let rt = ReservationTable::alu_default();
        assert_eq!(rt.opcode, 1);
        assert!(rt.is_reserved(0, 0));
    }

    #[test]
    fn test_reservation_table_load_default() {
        let rt = ReservationTable::load_default();
        assert_eq!(rt.opcode, 2);
    }

    // --- Bidirectional Scheduler Tests ---

    #[test]
    fn test_bidirectional_scheduler_new() {
        let bs = BidirectionalScheduler::new("x86_64");
        assert_eq!(bs.target, "x86_64");
        assert!(bs.forward_schedule.is_empty());
        assert!(bs.backward_schedule.is_empty());
    }

    #[test]
    fn test_bidirectional_schedule_empty() {
        let mut bs = BidirectionalScheduler::new("test");
        let graph = DepGraph::new();
        let instrs: Vec<MachineInstr> = vec![];
        let result = bs.schedule(&graph, &instrs);
        assert!(result.is_empty());
    }

    #[test]
    fn test_bidirectional_schedule_independent() {
        let mut bs = BidirectionalScheduler::new("test");
        let mut graph = DepGraph::new();
        for i in 0..3 {
            graph.nodes.push(SchedNode {
                instr_idx: i,
                opcode: 1,
                latency: 1,
                critical_path: 0,
                successors: vec![],
                predecessors: vec![],
                scheduled: false,
                unscheduled_preds: 0,
            });
        }
        graph.node_count = 3;
        let instrs = vec![
            make_mi(1, Some(0)),
            make_mi(1, Some(1)),
            make_mi(1, Some(2)),
        ];
        let result = bs.schedule(&graph, &instrs);
        assert_eq!(result.len(), 3);
    }

    // --- Itinerary Data Tests ---

    #[test]
    fn test_itinerary_data_new() {
        let id = ItineraryData::new("x86_64");
        assert_eq!(id.target, "x86_64");
        assert!(id.itineraries.is_empty());
    }

    #[test]
    fn test_itinerary_data_get_latency_unknown() {
        let id = ItineraryData::new("test");
        assert_eq!(id.get_latency(999), 1);
    }

    #[test]
    fn test_itinerary_data_x86_64_default() {
        let id = ItineraryData::x86_64_default();
        assert!(id.itineraries.len() > 0);
        // ALU should have latency
        let lat = id.get_latency(1);
        assert!(lat > 0);
        assert_eq!(id.get_num_micro_ops(1), 1);
    }

    // --- FullScheduleDAG Tests ---

    #[test]
    fn test_full_schedule_dag_empty() {
        let dag = FullScheduleDAG::from_basic_block(&[], "generic");
        assert_eq!(dag.graph.node_count, 0);
        assert_eq!(dag.estimate_length(), 0);
    }

    #[test]
    fn test_full_schedule_dag_basic() {
        let instrs = vec![
            make_mi(1, Some(1)),
            make_mi_with_ops(2, Some(2), vec![MachineOperand::Reg(1)]),
            make_mi_with_ops(3, None, vec![MachineOperand::Reg(2)]),
        ];
        let dag = FullScheduleDAG::from_basic_block(&instrs, "generic");
        assert_eq!(dag.graph.node_count, 3);
        // Should have some critical path length
        assert!(dag.estimate_length() > 0);
        // Should have at least one region
        assert!(dag.regions.len() >= 1);
    }

    #[test]
    fn test_full_schedule_dag_ready_nodes() {
        let instrs = vec![make_mi(1, Some(1)), make_mi(1, Some(2))];
        let dag = FullScheduleDAG::from_basic_block(&instrs, "generic");
        let scheduled = vec![false; 2];
        let ready = dag.ready_nodes(&scheduled);
        // All nodes should be ready (no dependences)
        assert_eq!(ready.len(), 2);
    }

    #[test]
    fn test_full_schedule_dag_depths() {
        let instrs = vec![
            make_mi(1, Some(1)),
            make_mi_with_ops(1, Some(2), vec![MachineOperand::Reg(1)]),
        ];
        let dag = FullScheduleDAG::from_basic_block(&instrs, "generic");
        assert_eq!(dag.depths[0], 0);
        assert!(dag.depths[1] > 0);
    }

    // --- ScheduleDAG Mutator Tests ---

    #[test]
    fn test_sched_dag_mutator_new() {
        let mutator = ScheduleDAGMutator::new();
        assert!(mutator.enforce_mem_order);
        assert!(mutator.break_anti_deps);
    }

    #[test]
    fn test_sched_dag_mutator_memory_barriers() {
        let mut mutator = ScheduleDAGMutator::new();
        let instrs = vec![
            make_mi(3, None),    // store
            make_mi(2, Some(1)), // load
        ];
        let mut graph = DepGraph::new();
        for i in 0..2 {
            graph.nodes.push(SchedNode {
                instr_idx: i,
                opcode: instrs[i].opcode,
                latency: 1,
                critical_path: 0,
                successors: vec![],
                predecessors: vec![],
                scheduled: false,
                unscheduled_preds: 0,
            });
        }
        graph.node_count = 2;
        mutator.add_memory_barriers(&mut graph, &instrs);
        assert!(mutator.added_edges > 0);
    }

    // --- Copy Suppressor Tests ---

    #[test]
    fn test_copy_suppressor_self_copy() {
        let mut suppressor = CopySuppressor::new();
        let mut instrs = vec![make_mi_with_ops(1, Some(3), vec![MachineOperand::Reg(3)])];
        suppressor.suppress_copies(&mut instrs);
        assert!(instrs.is_empty());
        assert_eq!(suppressor.copies_eliminated, 1);
    }

    // --- Load/Store Clusterer Tests ---

    #[test]
    fn test_load_clusterer_empty() {
        let mut clusterer = LoadClusterer::new();
        let mut instrs: Vec<MachineInstr> = vec![];
        clusterer.cluster_loads(&mut instrs);
        assert_eq!(clusterer.loads_clustered, 0);
    }

    #[test]
    fn test_store_clusterer_empty() {
        let mut clusterer = StoreClusterer::new();
        let mut instrs: Vec<MachineInstr> = vec![];
        clusterer.cluster_stores(&mut instrs);
        assert_eq!(clusterer.stores_clustered, 0);
    }

    // --- MacroFusion Detector Tests ---

    #[test]
    fn test_macro_fusion_skylake() {
        let mut detector = MacroFusionDetector::new("skylake");
        assert!(detector.support_fusion);
        assert!(detector.support_extended_fusion);
    }

    #[test]
    fn test_macro_fusion_detect_cmp_jcc() {
        let mut detector = MacroFusionDetector::new("skylake");
        let instrs = vec![make_mi(18, None), make_mi(16, None)]; // CMP + JE
        detector.detect_fusion_pairs(&instrs);
        assert_eq!(detector.fused_uop_count(), 1);
    }

    #[test]
    fn test_macro_fusion_detect_test_jcc() {
        let mut detector = MacroFusionDetector::new("icelake");
        let instrs = vec![make_mi(26, None), make_mi(17, None)]; // TEST + JNE
        detector.detect_fusion_pairs(&instrs);
        assert_eq!(detector.fused_uop_count(), 1);
    }

    // --- MicroFusion Detector Tests ---

    #[test]
    fn test_micro_fusion_detector_new() {
        let mut detector = MicroFusionDetector::new();
        assert!(detector.support_fusion);
        assert!(detector.load_op_fusions.is_empty());
    }

    #[test]
    fn test_micro_fusion_detect_load_op() {
        let mut detector = MicroFusionDetector::new();
        let instrs = vec![make_mi_with_ops(2, Some(1), vec![MachineOperand::Reg(0)])]; // ADD r, [mem]
        detector.detect_load_op_fusion(&instrs);
        assert!(detector.load_op_fusions.contains(&0));
    }

    // --- Loop Alignment Tests ---

    #[test]
    fn test_loop_aligner_compute_nops() {
        let aligner = LoopAligner::new(16);
        assert_eq!(aligner.compute_alignment_nops(0), 0);
        assert_eq!(aligner.compute_alignment_nops(1), 15);
        assert_eq!(aligner.compute_alignment_nops(16), 0);
        assert_eq!(aligner.compute_alignment_nops(17), 15);
    }

    #[test]
    fn test_loop_aligner_nop_sequence() {
        let seq = LoopAligner::generate_nop_sequence(0);
        assert!(seq.is_empty());
        let seq = LoopAligner::generate_nop_sequence(1);
        assert_eq!(seq.len(), 1);
        assert_eq!(seq[0], 0x90);
        let seq = LoopAligner::generate_nop_sequence(3);
        assert_eq!(seq.len(), 3);
    }

    #[test]
    fn test_loop_aligner_insert_nops() {
        let mut aligner = LoopAligner::new(16);
        let mut instrs = vec![make_mi(1, Some(1))];
        aligner.align_loop_header(1, &mut instrs);
        assert_eq!(instrs.len(), 2); // Original + NOP
        assert_eq!(instrs[0].opcode, 0); // NOP
    }

    // --- Prefix Optimizer Tests ---

    #[test]
    fn test_prefix_optimizer_new() {
        let opt = PrefixOptimizer::new();
        assert!(opt.optimize_rex);
        assert_eq!(opt.prefix_bytes_saved, 0);
    }

    // --- Sub-Register Liveness Tests ---

    #[test]
    fn test_subreg_liveness_overlap() {
        let mut liveness = SubRegLiveness::new();
        liveness.record_access(0, 5);
        liveness.record_access(0, 10);
        assert!(liveness.overlaps(0, 5, 10));
        assert!(!liveness.overlaps(0, 20, 25));
    }

    // --- VLIW Packet Formation Tests ---

    #[test]
    fn test_vliw_packet_formation_empty() {
        let mut formation = VLIWPacketFormation::new(4);
        let graph = DepGraph::new();
        formation.form_packets(&[], &graph);
        assert_eq!(formation.packet_count(), 0);
    }

    #[test]
    fn test_vliw_packet_formation_utilization() {
        let mut formation = VLIWPacketFormation::new(4);
        let mut graph = DepGraph::new();
        for i in 0..4 {
            graph.nodes.push(SchedNode {
                instr_idx: i,
                opcode: 1,
                latency: 1,
                critical_path: 0,
                successors: vec![],
                predecessors: vec![],
                scheduled: false,
                unscheduled_preds: 0,
            });
        }
        graph.node_count = 4;
        formation.form_packets(&[0, 1, 2, 3], &graph);
        assert_eq!(formation.packet_count(), 1);
        assert!(formation.utilization() > 0.0);
    }

    // --- Additional Load/Store Clusterer Tests ---

    #[test]
    fn test_load_clusterer_same_line() {
        let mut clusterer = LoadClusterer::new();
        let mut instrs = vec![
            make_mi_with_ops(2, Some(1), vec![MachineOperand::Imm(0)]),
            make_mi_with_ops(2, Some(2), vec![MachineOperand::Imm(8)]),
            make_mi_with_ops(2, Some(3), vec![MachineOperand::Imm(16)]),
        ];
        clusterer.cluster_loads(&mut instrs);
        assert_eq!(clusterer.loads_clustered, 3);
    }

    #[test]
    fn test_store_clusterer_same_line() {
        let mut clusterer = StoreClusterer::new();
        let mut instrs = vec![
            make_mi_with_ops(3, None, vec![MachineOperand::Imm(0)]),
            make_mi_with_ops(3, None, vec![MachineOperand::Imm(8)]),
        ];
        clusterer.cluster_stores(&mut instrs);
        assert_eq!(clusterer.stores_clustered, 2);
    }

    #[test]
    fn test_macro_fusion_add_jcc_skylake() {
        let mut detector = MacroFusionDetector::new("skylake");
        let instrs = vec![make_mi(2, Some(1)), make_mi(16, None)];
        detector.detect_fusion_pairs(&instrs);
        assert_eq!(detector.fused_uop_count(), 1);
    }

    #[test]
    fn test_macro_fusion_no_fusion_no_branch() {
        let mut detector = MacroFusionDetector::new("skylake");
        let instrs = vec![make_mi(18, None), make_mi(1, Some(1))];
        detector.detect_fusion_pairs(&instrs);
        assert_eq!(detector.fused_uop_count(), 0);
    }

    #[test]
    fn test_micro_fusion_store_detect() {
        let mut detector = MicroFusionDetector::new();
        let instrs = vec![make_mi_with_ops(
            3,
            None,
            vec![MachineOperand::Reg(0), MachineOperand::Imm(0)],
        )];
        detector.detect_store_fusion(&instrs);
        assert_eq!(detector.store_fusions.len(), 1);
    }

    #[test]
    fn test_loop_aligner_nop_sequence_all_sizes() {
        for n in 1..=9 {
            let seq = LoopAligner::generate_nop_sequence(n);
            assert_eq!(seq.len(), n as usize);
        }
    }

    #[test]
    fn test_copy_suppressor_propagate() {
        let mut suppressor = CopySuppressor::new();
        let mut instrs = vec![
            make_mi_with_ops(1, Some(4), vec![MachineOperand::Reg(3)]),
            make_mi_with_ops(2, None, vec![MachineOperand::Reg(4)]),
        ];
        suppressor.suppress_copies(&mut instrs);
        assert_eq!(instrs.len(), 1);
        if let MachineOperand::Reg(r) = instrs[0].operands[0] {
            assert_eq!(r, 3);
        }
    }

    #[test]
    fn test_subreg_liveness_record() {
        let mut liveness = SubRegLiveness::new();
        liveness.record_access(1, 3);
        liveness.record_access(1, 7);
        let (start, end) = liveness.live_ranges[&1];
        assert_eq!(start, 3);
        assert_eq!(end, 7);
    }

    #[test]
    fn test_vliw_packet_formation_with_deps() {
        let mut formation = VLIWPacketFormation::new(2);
        let mut graph = DepGraph::new();
        graph.nodes.push(SchedNode {
            instr_idx: 0,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![1],
            predecessors: vec![],
            scheduled: false,
            unscheduled_preds: 0,
        });
        graph.nodes.push(SchedNode {
            instr_idx: 1,
            opcode: 1,
            latency: 1,
            critical_path: 0,
            successors: vec![],
            predecessors: vec![0],
            scheduled: false,
            unscheduled_preds: 1,
        });
        graph.node_count = 2;
        formation.form_packets(&[0, 1], &graph);
        assert_eq!(formation.packet_count(), 2);
    }
}