llvm-native-core-ext 0.1.0

// codegen_deep_sched.rs — World-Class Instruction Scheduling Deep Expansion
//
// Deep instruction scheduling with comprehensive dependence analysis,
// resource modeling, hazard recognition, post-RA scheduling, and
// macro-fusion support. Clean-room behavioral reconstruction.
//
// @llvm_behavior: This module provides a full instruction scheduling
// pipeline:
//   1. DependenceGraph — build true/anti/output dependence DAG from
//      machine instructions, tracking register and memory deps.
//   2. ScheduleDAG — topological sort, ASAP/ALAP scheduling, mobility
//      (slack) computation for each node.
//   3. ListScheduler — priority-based list scheduling with critical-path
//      heuristics, ready-list management, cycle-by-cycle issue.
//   4. ResourceModel — execution unit modeling (ALU, memory, branch,
//      FP, vector), pipeline stages, issue width, reservation tables.
//   5. HazardRecognizer — structural and data hazard detection,
//      forwarding-path analysis, stall insertion.
//   6. PostRAScheduler — post-register-allocation scheduling, anti-dep
//      breaking via register renaming, copy insertion.
//   7. MacroFusion — instruction fusion for adjacent pairs (CMP+JCC,
//      DEC+JNZ, TEST+JCC), fusion eligibility checks.
//
// All algorithms use only std library types. No external crate
// dependencies.

// ============================================================================
// Imports
// ============================================================================

use std::cmp::Ordering;
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;

// ============================================================================
// Common / Utility Types
// ============================================================================

/// A physical register number.
pub type PhysReg = u32;

/// A virtual register number.
pub type VirtReg = u32;

/// A cycle count in the schedule.
pub type Cycle = u64;

/// A node index in the dependence graph.
pub type NodeId = usize;

/// A register that can be either virtual or physical.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Reg {
    /// A virtual register (pre-RA).
    Virt(VirtReg),
    /// A physical register (post-RA).
    Phys(PhysReg),
}

impl Reg {
    /// Return the concrete numeric id regardless of kind.
    pub fn id(self) -> u32 {
        match self {
            Reg::Virt(v) => v,
            Reg::Phys(p) => p,
        }
    }

    /// True if this is a physical register.
    pub fn is_phys(self) -> bool {
        matches!(self, Reg::Phys(_))
    }

    /// True if this is a virtual register.
    pub fn is_virt(self) -> bool {
        matches!(self, Reg::Virt(_))
    }
}

impl fmt::Display for Reg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Reg::Virt(v) => write!(f, "v{}", v),
            Reg::Phys(p) => write!(f, "p{}", p),
        }
    }
}

/// Kind of dependence between two instructions.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DepKind {
    /// True (read-after-write): producer → consumer flow dependence.
    True,
    /// Anti (write-after-read): consumer must not clobber before reader.
    Anti,
    /// Output (write-after-write): two writes to same register must stay ordered.
    Output,
    /// Memory ordering dependence (e.g., store → load aliasing).
    Memory,
    /// Control dependence (branch/barrier).
    Control,
    /// Artificial chain inserted by the scheduler (e.g., to prevent reordering).
    Chain,
}

impl DepKind {
    /// Whether this kind of dependence is a read-after-write hazard.
    pub fn is_true(self) -> bool {
        matches!(self, DepKind::True)
    }

    /// Whether this kind of dependence can be broken by renaming.
    pub fn is_renamable(self) -> bool {
        matches!(self, DepKind::Anti | DepKind::Output)
    }

    /// Whether this is a memory-ordering dependence.
    pub fn is_memory(self) -> bool {
        matches!(self, DepKind::Memory)
    }

    /// Returns a string name for the dependence kind.
    pub fn as_str(self) -> &'static str {
        match self {
            DepKind::True => "true",
            DepKind::Anti => "anti",
            DepKind::Output => "output",
            DepKind::Memory => "memory",
            DepKind::Control => "control",
            DepKind::Chain => "chain",
        }
    }
}

/// A single edge in the dependence graph.
#[derive(Debug, Clone)]
pub struct DepEdge {
    /// Source node (producer / earlier instruction).
    pub from: NodeId,
    /// Target node (consumer / later instruction).
    pub to: NodeId,
    /// Kind of dependence.
    pub kind: DepKind,
    /// The register involved (if a register dependence).
    pub reg: Option<Reg>,
    /// Minimum latency (cycles) this edge imposes.
    pub min_latency: u32,
}

impl DepEdge {
    pub fn new(from: NodeId, to: NodeId, kind: DepKind, min_latency: u32) -> Self {
        Self {
            from,
            to,
            kind,
            reg: None,
            min_latency,
        }
    }

    pub fn with_reg(from: NodeId, to: NodeId, kind: DepKind, reg: Reg, min_latency: u32) -> Self {
        Self {
            from,
            to,
            kind,
            reg: Some(reg),
            min_latency,
        }
    }
}

/// Machine operand types used by the scheduling infrastructure.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SchedOperand {
    /// A register operand (def or use).
    Reg(Reg),
    /// A constant immediate operand.
    Imm(i64),
    /// A block label reference.
    Label(String),
    /// A global symbol reference.
    Global(String),
    /// A stack slot reference.
    StackSlot(i32),
    /// A memory operand with base register and offset.
    Mem { base: Option<Reg>, offset: i64 },
}

/// A machine instruction as seen by the deep scheduler.
#[derive(Debug, Clone)]
pub struct SchedInstr {
    /// Index in the original instruction stream.
    pub index: usize,
    /// Opcode of the instruction.
    pub opcode: u32,
    /// Operands of the instruction.
    pub operands: Vec<SchedOperand>,
    /// Registers defined (written) by this instruction.
    pub defs: Vec<Reg>,
    /// Registers used (read) by this instruction.
    pub uses: Vec<Reg>,
    /// Whether this instruction reads memory.
    pub may_load: bool,
    /// Whether this instruction writes memory.
    pub may_store: bool,
    /// Whether this is a branch or barrier.
    pub is_branch: bool,
    /// Whether this is a call instruction.
    pub is_call: bool,
    /// Whether this has side effects (must not be reordered freely).
    pub has_side_effects: bool,
    /// Latency of this instruction in cycles.
    pub latency: u32,
    /// Whether this instruction can be issued in parallel with others.
    pub is_parallel: bool,
    /// Number of micro-ops (for split-issue modeling).
    pub micro_ops: u32,
}

impl SchedInstr {
    /// Create a minimal scheduling instruction.
    pub fn new(index: usize, opcode: u32) -> Self {
        Self {
            index,
            opcode,
            operands: Vec::new(),
            defs: Vec::new(),
            uses: Vec::new(),
            may_load: false,
            may_store: false,
            is_branch: false,
            is_call: false,
            has_side_effects: false,
            latency: 1,
            is_parallel: false,
            micro_ops: 1,
        }
    }

    /// Set the latency.
    pub fn with_latency(mut self, latency: u32) -> Self {
        self.latency = latency;
        self
    }

    /// Add a register definition.
    pub fn def(mut self, reg: Reg) -> Self {
        self.defs.push(reg);
        self
    }

    /// Add a register use.
    pub fn use_reg(mut self, reg: Reg) -> Self {
        self.uses.push(reg);
        self
    }

    /// Mark as a load.
    pub fn load(mut self) -> Self {
        self.may_load = true;
        self
    }

    /// Mark as a store.
    pub fn store(mut self) -> Self {
        self.may_store = true;
        self
    }

    /// Mark as a branch.
    pub fn branch(mut self) -> Self {
        self.is_branch = true;
        self
    }

    /// Mark as a call.
    pub fn call(mut self) -> Self {
        self.is_call = true;
        self
    }

    /// Mark as having side effects.
    pub fn side_effects(mut self) -> Self {
        self.has_side_effects = true;
        self
    }
}

// ============================================================================
// Instruction Itinerary & Micro-Op Decomposition
// ============================================================================
// Models the pipeline behavior of individual instructions: which pipeline
// stages they occupy, how many micro-ops they decompose into, and what
// resources each micro-op uses. This data drives precise resource modeling.

/// A single stage in an instruction's pipeline itinerary.
#[derive(Debug, Clone)]
pub struct PipelineStage {
    /// Functional unit used by this stage.
    pub unit: FuncUnitKind,
    /// Cycles spent in this stage.
    pub cycles: u32,
    /// Whether this stage can overlap with the next instruction.
    pub overlap: bool,
}

impl PipelineStage {
    pub fn new(unit: FuncUnitKind, cycles: u32) -> Self {
        Self {
            unit,
            cycles,
            overlap: true,
        }
    }

    pub fn non_overlapping(mut self) -> Self {
        self.overlap = false;
        self
    }
}

/// Pipeline itinerary for an opcode: ordered list of pipeline stages.
#[derive(Debug, Clone)]
pub struct InstrItinerary {
    /// Opcode this itinerary applies to.
    pub opcode: u32,
    /// Mnemonic for readability.
    pub mnemonic: String,
    /// Ordered pipeline stages.
    pub stages: Vec<PipelineStage>,
    /// Total latency in cycles.
    pub latency: u32,
    /// Number of micro-ops.
    pub micro_ops: u32,
    /// Whether this instruction can be dual-issued with another.
    pub dual_issue: bool,
}

impl InstrItinerary {
    pub fn new(opcode: u32, mnemonic: &str) -> Self {
        Self {
            opcode,
            mnemonic: mnemonic.to_string(),
            stages: Vec::new(),
            latency: 0,
            micro_ops: 1,
            dual_issue: false,
        }
    }

    pub fn with_stage(mut self, unit: FuncUnitKind, cycles: u32) -> Self {
        self.stages.push(PipelineStage::new(unit, cycles));
        self.latency += cycles;
        self
    }

    pub fn with_micro_ops(mut self, count: u32) -> Self {
        self.micro_ops = count;
        self
    }

    /// Total cycles across all stages.
    pub fn total_cycles(&self) -> u32 {
        self.stages.iter().map(|s| s.cycles).sum()
    }

    /// Check if this itinerary uses a given functional unit.
    pub fn uses_unit(&self, unit: FuncUnitKind) -> bool {
        self.stages.iter().any(|s| s.unit == unit)
    }
}

/// A micro-op within a macro-instruction.
#[derive(Debug, Clone)]
pub struct MicroOp {
    /// The functional unit this micro-op executes on.
    pub unit: FuncUnitKind,
    /// Latency of this micro-op.
    pub latency: u32,
    /// Defs produced by this micro-op.
    pub defs: Vec<Reg>,
    /// Uses consumed by this micro-op.
    pub uses: Vec<Reg>,
}

impl MicroOp {
    pub fn new(unit: FuncUnitKind, latency: u32) -> Self {
        Self {
            unit,
            latency,
            defs: Vec::new(),
            uses: Vec::new(),
        }
    }
}

/// Decompose an instruction into its constituent micro-ops.
#[derive(Debug, Clone)]
pub struct MicroOpDecomposition {
    /// The original opcode.
    pub opcode: u32,
    /// Ordered micro-ops.
    pub uops: Vec<MicroOp>,
    /// Total latency (critical path through micro-ops).
    pub total_latency: u32,
}

impl MicroOpDecomposition {
    pub fn new(opcode: u32, uops: Vec<MicroOp>) -> Self {
        let total_latency = uops.iter().map(|u| u.latency).sum();
        Self {
            opcode,
            uops,
            total_latency,
        }
    }

    /// Returns the total number of micro-ops.
    pub fn count(&self) -> usize {
        self.uops.len()
    }
}

// ============================================================================
// DependenceGraph — Build data dependence DAG
// ============================================================================
// Builds a dependence directed acyclic graph (DAG) from a sequence of
// machine instructions. Tracks true (RAW), anti (WAR), and output (WAW)
// register dependences, plus memory-ordering dependences for loads and
// stores.
//
// The builder scans instructions in order, maintaining the most recent
// definition and use of each register. For each instruction, it adds
// edges from:
//   - True:  from the most recent def of each use register to this inst
//   - Anti:  from the most recent use of each def register to this inst
//   - Output: from the most recent def of each def register to this inst
//   - Memory: from prior stores/loads to later loads/stores (conservative)
//
// Additional ordering edges are added for branches, calls, and
// side-effecting instructions.

/// A node in the dependence graph.
#[derive(Debug, Clone)]
pub struct DepNode {
    /// The instruction this node represents.
    pub instr: SchedInstr,
    /// Node index in the graph.
    pub id: NodeId,
    /// Outgoing dependence edges (successors).
    pub succs: Vec<DepEdge>,
    /// Incoming dependence edges (predecessors).
    pub preds: Vec<DepEdge>,
    /// ASAP scheduling cycle (earliest possible start).
    pub asap: Cycle,
    /// ALAP scheduling cycle (latest possible start).
    pub alap: Cycle,
    /// Mobility: ALAP - ASAP (slack). Zero means critical.
    pub mobility: u64,
    /// Critical path length (longest latency path to a sink).
    pub depth: u64,
    /// Height (longest latency path from a source).
    pub height: u64,
    /// Number of unscheduled predecessors (for list scheduling).
    pub unscheduled_preds: usize,
    /// Whether this node has been scheduled.
    pub scheduled: bool,
    /// Cycle at which this instruction was scheduled.
    pub scheduled_cycle: Cycle,
    /// Priority value used by the list scheduler.
    pub priority: i64,
}

impl DepNode {
    pub fn new(id: NodeId, instr: SchedInstr) -> Self {
        Self {
            instr,
            id,
            succs: Vec::new(),
            preds: Vec::new(),
            asap: 0,
            alap: 0,
            mobility: 0,
            depth: 0,
            height: 0,
            unscheduled_preds: 0,
            scheduled: false,
            scheduled_cycle: 0,
            priority: 0,
        }
    }

    /// Return the opcode.
    pub fn opcode(&self) -> u32 {
        self.instr.opcode
    }

    /// Return the latency.
    pub fn latency(&self) -> u32 {
        self.instr.latency
    }

    /// True if this node is a leaf/sink (no successors).
    pub fn is_sink(&self) -> bool {
        self.succs.is_empty()
    }

    /// True if this node is a root/source (no predecessors).
    pub fn is_source(&self) -> bool {
        self.preds.is_empty()
    }

    /// True if all predecessors have been scheduled.
    pub fn is_ready(&self) -> bool {
        self.unscheduled_preds == 0 && !self.scheduled
    }

    /// Get the latest predecessor finish cycle.
    pub fn earliest_start(&self, nodes: &[DepNode]) -> Cycle {
        let mut max_cycle: Cycle = 0;
        for edge in &self.preds {
            let pred = &nodes[edge.from];
            if pred.scheduled {
                let finish = pred.scheduled_cycle + pred.latency() as u64 + edge.min_latency as u64;
                if finish > max_cycle {
                    max_cycle = finish;
                }
            }
        }
        max_cycle
    }
}

/// The dependence graph for a sequence of instructions.
#[derive(Debug, Clone)]
pub struct DependenceGraph {
    /// All nodes in the graph, indexed by NodeId.
    pub nodes: Vec<DepNode>,
    /// Number of instructions originally (may include sentinels).
    pub num_instrs: usize,
    /// Entry sentinel node (before all real instructions).
    pub entry_node: Option<NodeId>,
    /// Exit sentinel node (after all real instructions).
    pub exit_node: Option<NodeId>,
    /// Whether memory dependences are modeled precisely.
    pub precise_memory: bool,
    /// Whether anti/output dependences are included.
    pub include_anti_output: bool,
}

impl DependenceGraph {
    /// Create a new empty dependence graph.
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            num_instrs: 0,
            entry_node: None,
            exit_node: None,
            precise_memory: false,
            include_anti_output: true,
        }
    }

    /// Build the dependence graph from a slice of scheduling instructions.
    ///
    /// This is the main entry point. It performs register tracking
    /// and memory dependence analysis to construct the full DAG.
    pub fn build(&mut self, instrs: &[SchedInstr]) {
        self.nodes.clear();
        self.num_instrs = instrs.len();

        if instrs.is_empty() {
            return;
        }

        // Create nodes for all instructions.
        for (i, instr) in instrs.iter().enumerate() {
            let mut si = instr.clone();
            si.index = i;
            self.nodes.push(DepNode::new(i, si));
        }

        // Create entry sentinel.
        let entry_instr = SchedInstr::new(self.nodes.len(), 0);
        self.entry_node = Some(self.nodes.len());
        self.nodes.push(DepNode::new(self.nodes.len(), entry_instr));

        // Create exit sentinel.
        let exit_instr = SchedInstr::new(self.nodes.len(), 0);
        self.exit_node = Some(self.nodes.len());
        self.nodes.push(DepNode::new(self.nodes.len(), exit_instr));

        // Build register dependences.
        self.build_register_deps();

        // Build memory dependences.
        self.build_memory_deps();

        // Build control/ordering dependences.
        self.build_ordering_deps();

        // Connect entry → sources and sinks → exit.
        self.connect_sentinels();
    }

    /// Build register dependences (true, anti, output).
    fn build_register_deps(&mut self) {
        // Track last definition of each register.
        let mut last_def: HashMap<Reg, NodeId> = HashMap::new();
        // Track last use of each register.
        let mut last_use: HashMap<Reg, NodeId> = HashMap::new();

        let n = self.num_instrs;

        // Collect edges to avoid borrow conflicts.
        let mut pending_edges: Vec<DepEdge> = Vec::new();

        for i in 0..n {
            let uses: Vec<Reg> = self.nodes[i].instr.uses.clone();
            let defs: Vec<Reg> = self.nodes[i].instr.defs.clone();

            // For each use: add true dependence from last definition.
            for u in &uses {
                if let Some(&def_node) = last_def.get(u) {
                    if def_node != i {
                        pending_edges.push(DepEdge::with_reg(def_node, i, DepKind::True, *u, 0));
                    }
                }
                last_use.insert(*u, i);
            }

            // For each def: add anti and output dependences.
            if self.include_anti_output {
                for d in &defs {
                    if let Some(&use_node) = last_use.get(d) {
                        if use_node != i {
                            pending_edges.push(DepEdge::with_reg(
                                use_node,
                                i,
                                DepKind::Anti,
                                *d,
                                0,
                            ));
                        }
                    }
                    if let Some(&prev_def) = last_def.get(d) {
                        if prev_def != i {
                            pending_edges.push(DepEdge::with_reg(
                                prev_def,
                                i,
                                DepKind::Output,
                                *d,
                                0,
                            ));
                        }
                    }
                    last_def.insert(*d, i);
                }
            }
        }

        // Add all pending edges.
        for edge in pending_edges {
            let from = edge.from;
            let to = edge.to;
            self.add_edge(from, to, edge);
        }
    }

    /// Build memory-ordering dependences between loads and stores.
    ///
    /// Conservatively adds edges from each store to later loads/stores
    /// and from each load to later stores (to preserve ordering).
    /// In a more precise implementation, alias analysis would filter
    /// these edges.
    fn build_memory_deps(&mut self) {
        let n = self.num_instrs;

        // Track the most recent store for store→load and store→store deps.
        let mut last_store: Option<NodeId> = None;
        // Track the most recent memory access (load or store) for ordering.
        let mut last_mem_access: Option<NodeId> = None;

        for i in 0..n {
            let may_store = self.nodes[i].instr.may_store;
            let may_load = self.nodes[i].instr.may_load;

            if may_store {
                // Store → Store: ordering edge from previous store.
                if let Some(prev) = last_store {
                    let edge = DepEdge::new(prev, i, DepKind::Memory, 0);
                    self.add_edge(prev, i, edge);
                }
                // Memory → Store: general memory ordering.
                if let Some(prev) = last_mem_access {
                    if prev != last_store.unwrap_or(prev) {
                        let edge = DepEdge::new(prev, i, DepKind::Memory, 0);
                        self.add_edge(prev, i, edge);
                    }
                }
                last_store = Some(i);
                last_mem_access = Some(i);
            } else if may_load {
                // Store → Load: ordering edge from last store.
                if let Some(prev) = last_store {
                    let edge = DepEdge::new(prev, i, DepKind::Memory, 0);
                    self.add_edge(prev, i, edge);
                }
                // Don't update last_store for loads.
                last_mem_access = Some(i);
            }
        }
    }

    /// Build ordering dependences for branches, calls, and side effects.
    fn build_ordering_deps(&mut self) {
        let n = self.num_instrs;

        for i in 1..n {
            let is_barrier = self.nodes[i - 1].instr.is_branch
                || self.nodes[i - 1].instr.is_call
                || self.nodes[i - 1].instr.has_side_effects;

            // Previous branch/call/side-effect → next instruction.
            if is_barrier {
                // Already captured by the sequential nature, but add explicit edges
                // to prevent any scheduler from moving instructions across barriers.
                let edge = DepEdge::new(i - 1, i, DepKind::Control, 0);
                self.add_edge(i - 1, i, edge);
            }
        }
    }

    /// Connect entry sentinel to all source nodes, and all sink nodes to exit.
    fn connect_sentinels(&mut self) {
        let entry = self.entry_node.unwrap();
        let exit = self.exit_node.unwrap();
        let n = self.num_instrs;

        for i in 0..n {
            let preds_empty = self.nodes[i].preds.is_empty();
            let succs_empty = self.nodes[i].succs.is_empty();
            if preds_empty {
                let edge = DepEdge::new(entry, i, DepKind::Chain, 0);
                self.add_edge(entry, i, edge);
            }
            if succs_empty {
                let edge = DepEdge::new(i, exit, DepKind::Chain, 0);
                self.add_edge(i, exit, edge);
            }
        }
    }

    /// Add an edge to the graph. Updates successor and predecessor lists.
    fn add_edge(&mut self, from: NodeId, to: NodeId, edge: DepEdge) {
        // Avoid duplicate edges between the same nodes.
        for existing in &self.nodes[from].succs {
            if existing.to == to && existing.kind == edge.kind && existing.reg == edge.reg {
                return;
            }
        }
        self.nodes[from].succs.push(edge.clone());
        self.nodes[to].preds.push(edge);
    }

    /// Compute the transitive closure of dependences (for debugging/introspection).
    pub fn transitive_succs(&self, node: NodeId) -> HashSet<NodeId> {
        let mut visited = HashSet::new();
        let mut stack = vec![node];
        while let Some(current) = stack.pop() {
            if !visited.insert(current) {
                continue;
            }
            for edge in &self.nodes[current].succs {
                stack.push(edge.to);
            }
        }
        visited.remove(&node);
        visited
    }

    /// Return the number of nodes (including sentinels).
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// True if the graph is empty.
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Get all true dependence edges in the graph.
    pub fn true_deps(&self) -> Vec<&DepEdge> {
        let mut result = Vec::new();
        for node in &self.nodes {
            for edge in &node.succs {
                if edge.kind == DepKind::True {
                    result.push(edge);
                }
            }
        }
        result
    }

    /// Get all anti dependence edges in the graph.
    pub fn anti_deps(&self) -> Vec<&DepEdge> {
        let mut result = Vec::new();
        for node in &self.nodes {
            for edge in &node.succs {
                if edge.kind == DepKind::Anti {
                    result.push(edge);
                }
            }
        }
        result
    }

    /// Get all output dependence edges in the graph.
    pub fn output_deps(&self) -> Vec<&DepEdge> {
        let mut result = Vec::new();
        for node in &self.nodes {
            for edge in &node.succs {
                if edge.kind == DepKind::Output {
                    result.push(edge);
                }
            }
        }
        result
    }

    /// Count the number of edges of a given kind.
    pub fn count_edges(&self, kind: DepKind) -> usize {
        let mut count = 0;
        for node in &self.nodes {
            for edge in &node.succs {
                if edge.kind == kind {
                    count += 1;
                }
            }
        }
        count
    }

    /// Check for cycles in the graph (should not exist in a valid DAG).
    /// Uses depth-first search with three-color marking.
    pub fn has_cycle(&self) -> bool {
        let n = self.nodes.len();
        let mut color: Vec<u8> = vec![0; n]; // 0=white, 1=gray, 2=black

        fn dfs_visit(node: usize, nodes: &[DepNode], color: &mut [u8]) -> bool {
            color[node] = 1; // gray
            for edge in &nodes[node].succs {
                let to = edge.to;
                if color[to] == 1 {
                    return true; // back edge → cycle
                }
                if color[to] == 0 {
                    if dfs_visit(to, nodes, color) {
                        return true;
                    }
                }
            }
            color[node] = 2; // black
            false
        }

        for i in 0..n {
            if color[i] == 0 {
                if dfs_visit(i, &self.nodes, &mut color) {
                    return true;
                }
            }
        }
        false
    }

    /// Return a dot-format string of the graph for visualization.
    pub fn to_dot(&self) -> String {
        let mut dot = String::from("digraph DependenceGraph {\n");
        dot.push_str("  rankdir=TB;\n");
        dot.push_str("  node [shape=box, style=filled, fillcolor=lightyellow];\n");

        for node in &self.nodes {
            let label = if node.id == self.entry_node.unwrap_or(usize::MAX) {
                "ENTRY".to_string()
            } else if node.id == self.exit_node.unwrap_or(usize::MAX) {
                "EXIT".to_string()
            } else {
                format!("N{}: op{}", node.id, node.instr.opcode)
            };
            dot.push_str(&format!("  n{} [label=\"{}\"];\n", node.id, label));
        }

        for node in &self.nodes {
            for edge in &node.succs {
                let style = match edge.kind {
                    DepKind::True => "solid",
                    DepKind::Anti => "dashed",
                    DepKind::Output => "dotted",
                    DepKind::Memory => "bold",
                    DepKind::Control => "dashdot",
                    DepKind::Chain => "invis",
                };
                dot.push_str(&format!(
                    "  n{} -> n{} [style={}, label=\"{}\"];\n",
                    edge.from,
                    edge.to,
                    style,
                    edge.kind.as_str()
                ));
            }
        }

        dot.push_str("}\n");
        dot
    }
}

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

// ============================================================================
// DepGraphAnalysis — Extended dependence graph analysis
// ============================================================================

/// Result of a subgraph analysis.
#[derive(Debug, Clone)]
pub struct DepGraphAnalysis {
    pub critical_path: Vec<NodeId>,
    pub critical_path_length: Cycle,
    pub independent_groups: Vec<Vec<NodeId>>,
    pub max_parallelism: usize,
    pub true_deps: usize,
    pub anti_deps: usize,
    pub output_deps: usize,
    pub has_cycle: bool,
}

impl DepGraphAnalysis {
    pub fn analyze(dg: &DependenceGraph) -> Self {
        let dag = ScheduleDAG::new(dg.clone());
        let critical_path = dag.critical_path_nodes();
        let groups = Self::find_independent_groups(dg);
        let max_parallelism = groups.iter().map(|g| g.len()).max().unwrap_or(0);

        Self {
            critical_path_length: dag.critical_path_length,
            critical_path,
            independent_groups: groups,
            max_parallelism,
            true_deps: dg.count_edges(DepKind::True),
            anti_deps: dg.count_edges(DepKind::Anti),
            output_deps: dg.count_edges(DepKind::Output),
            has_cycle: dg.has_cycle(),
        }
    }

    fn find_independent_groups(dg: &DependenceGraph) -> Vec<Vec<NodeId>> {
        let n = dg.num_instrs;
        if n == 0 {
            return Vec::new();
        }
        let mut adjacent: HashMap<NodeId, HashSet<NodeId>> = HashMap::new();
        for i in 0..n {
            adjacent.entry(i).or_default();
        }
        for node in &dg.nodes {
            for edge in &node.succs {
                if edge.from < n && edge.to < n {
                    adjacent.entry(edge.from).or_default().insert(edge.to);
                    adjacent.entry(edge.to).or_default().insert(edge.from);
                }
            }
        }
        let mut groups: Vec<Vec<NodeId>> = Vec::new();
        for i in 0..n {
            let conflicts = adjacent.get(&i).cloned().unwrap_or_default();
            let mut placed = false;
            for group in &mut groups {
                let has_conflict = group.iter().any(|&g| conflicts.contains(&g));
                if !has_conflict {
                    group.push(i);
                    placed = true;
                    break;
                }
            }
            if !placed {
                groups.push(vec![i]);
            }
        }
        groups
    }

    pub fn height_range(dg: &DependenceGraph) -> (u64, u64) {
        let mut min_h = u64::MAX;
        let mut max_h = 0u64;
        for node in &dg.nodes {
            min_h = min_h.min(node.height);
            max_h = max_h.max(node.height);
        }
        (min_h, max_h)
    }

    pub fn nodes_by_depth(dg: &DependenceGraph) -> Vec<NodeId> {
        let mut indices: Vec<NodeId> = (0..dg.num_instrs).collect();
        indices.sort_by_key(|&i| -(dg.nodes[i].depth as i64));
        indices
    }

    pub fn enumerate_paths(
        dg: &DependenceGraph,
        source: NodeId,
        sink: NodeId,
        max_paths: usize,
    ) -> Vec<Vec<NodeId>> {
        let mut paths = Vec::new();
        let mut current_path = Vec::new();
        let mut visited = HashSet::new();
        Self::dfs_paths(
            dg,
            source,
            sink,
            &mut current_path,
            &mut visited,
            &mut paths,
            max_paths,
        );
        paths
    }

    fn dfs_paths(
        dg: &DependenceGraph,
        node: NodeId,
        sink: NodeId,
        current: &mut Vec<NodeId>,
        visited: &mut HashSet<NodeId>,
        paths: &mut Vec<Vec<NodeId>>,
        max_paths: usize,
    ) {
        if paths.len() >= max_paths {
            return;
        }
        visited.insert(node);
        current.push(node);
        if node == sink {
            paths.push(current.clone());
        } else {
            for edge in &dg.nodes[node].succs {
                if !visited.contains(&edge.to) {
                    Self::dfs_paths(dg, edge.to, sink, current, visited, paths, max_paths);
                }
            }
        }
        current.pop();
        visited.remove(&node);
    }
}

// ============================================================================
// ScheduleDAG — Topological sort, ASAP/ALAP, mobility computation
// ============================================================================
// Computes the earliest (ASAP) and latest (ALAP) possible start cycles
// for each node in the dependence graph, then derives the mobility
// (slack) for each node. The critical path is the sequence of nodes
// with zero mobility.
//
// ASAP: forward pass — a node starts after all predecessors finish.
// ALAP: backward pass — a node starts so all successors can finish by deadline.
// Mobility = ALAP - ASAP (flexibility in scheduling).

/// Result of the ASAP/ALAP schedule analysis.
#[derive(Debug, Clone)]
pub struct ScheduleDAG {
    /// Reference to the underlying dependence graph.
    graph: DependenceGraph,
    /// Maximum ASAP value (length of the critical path).
    pub critical_path_length: Cycle,
    /// Nodes in topological order (from sources to sinks).
    pub topo_order: Vec<NodeId>,
    /// Reverse topological order (from sinks to sources).
    pub rev_topo_order: Vec<NodeId>,
}

impl ScheduleDAG {
    /// Create a new ScheduleDAG from a dependence graph.
    pub fn new(graph: DependenceGraph) -> Self {
        let mut dag = Self {
            graph,
            critical_path_length: 0,
            topo_order: Vec::new(),
            rev_topo_order: Vec::new(),
        };
        dag.compute_topo_order();
        dag.compute_asap();
        dag.compute_alap();
        dag.compute_mobility();
        dag.compute_depth_height();
        dag
    }

    /// Compute topological order using Kahn's algorithm.
    fn compute_topo_order(&mut self) {
        let n = self.graph.nodes.len();
        let mut in_degree: Vec<usize> = vec![0; n];

        // Compute in-degrees.
        for node in &self.graph.nodes {
            for edge in &node.succs {
                in_degree[edge.to] += 1;
            }
        }

        // Initialize queue with nodes that have zero in-degree.
        let mut queue: VecDeque<NodeId> = VecDeque::new();
        for i in 0..n {
            if in_degree[i] == 0 {
                queue.push_back(i);
            }
        }

        // Process queue.
        self.topo_order.clear();
        while let Some(node) = queue.pop_front() {
            self.topo_order.push(node);
            for edge in &self.graph.nodes[node].succs {
                in_degree[edge.to] -= 1;
                if in_degree[edge.to] == 0 {
                    queue.push_back(edge.to);
                }
            }
        }

        // Reverse topological order.
        self.rev_topo_order = self.topo_order.clone();
        self.rev_topo_order.reverse();
    }

    /// Compute ASAP (As Soon As Possible) scheduling.
    ///
    /// Forward pass: a node starts at the maximum finish time of its
    /// predecessors. Entry starts at cycle 0.
    fn compute_asap(&mut self) {
        for &node_id in &self.topo_order {
            let mut max_pred_finish: Cycle = 0;

            for edge in &self.graph.nodes[node_id].preds {
                let pred = &self.graph.nodes[edge.from];
                let pred_finish = pred.asap + pred.latency() as u64;
                if pred_finish > max_pred_finish {
                    max_pred_finish = pred_finish;
                }
            }

            self.graph.nodes[node_id].asap = max_pred_finish;
            if max_pred_finish > self.critical_path_length {
                self.critical_path_length = max_pred_finish;
            }
        }
    }

    /// Compute ALAP (As Late As Possible) scheduling.
    ///
    /// Backward pass: a node starts so that all successors can be
    /// scheduled before the overall deadline (max ASAP).
    fn compute_alap(&mut self) {
        // Start all nodes at the critical path length.
        let deadline = self.critical_path_length;
        for node in &mut self.graph.nodes {
            node.alap = deadline;
        }

        // Backward pass in reverse topological order.
        for &node_id in &self.rev_topo_order {
            let mut min_succ_start: Cycle = deadline;

            for edge in &self.graph.nodes[node_id].succs {
                let succ = &self.graph.nodes[edge.to];
                let succ_start = succ.alap;
                if succ_start < min_succ_start {
                    min_succ_start = succ_start;
                }
            }

            let my_latency = self.graph.nodes[node_id].latency() as u64;
            let my_alap = if min_succ_start >= my_latency {
                min_succ_start - my_latency
            } else {
                0
            };

            self.graph.nodes[node_id].alap = my_alap;
        }
    }

    /// Compute mobility (slack) for each node.
    ///
    /// Mobility = ALAP - ASAP. A mobility of zero means the node is
    /// on the critical path — any delay directly increases overall
    /// schedule length.
    fn compute_mobility(&mut self) {
        for node in &mut self.graph.nodes {
            let mobility = if node.alap >= node.asap {
                node.alap - node.asap
            } else {
                0
            };
            node.mobility = mobility;
        }
    }

    /// Compute depth (longest path to sink) and height (longest path from source).
    fn compute_depth_height(&mut self) {
        // Height: forward pass (from sources).
        for &node_id in &self.topo_order {
            let node_latency = self.graph.nodes[node_id].latency() as u64;
            let mut max_height: u64 = 0;
            for edge in &self.graph.nodes[node_id].preds {
                let pred_height = self.graph.nodes[edge.from].height;
                if pred_height > max_height {
                    max_height = pred_height;
                }
            }
            self.graph.nodes[node_id].height = max_height + node_latency;
        }

        // Depth: backward pass (from sinks).
        for &node_id in self.rev_topo_order.iter().rev() {
            let node_latency = self.graph.nodes[node_id].latency() as u64;
            let mut max_depth: u64 = 0;
            for edge in &self.graph.nodes[node_id].succs {
                let succ_depth = self.graph.nodes[edge.to].depth;
                if succ_depth > max_depth {
                    max_depth = succ_depth;
                }
            }
            self.graph.nodes[node_id].depth = max_depth + node_latency;
        }
    }

    /// Return a reference to the underlying graph.
    pub fn graph(&self) -> &DependenceGraph {
        &self.graph
    }

    /// Return a mutable reference to the underlying graph.
    pub fn graph_mut(&mut self) -> &mut DependenceGraph {
        &mut self.graph
    }

    /// Get nodes on the critical path (mobility == 0).
    pub fn critical_path_nodes(&self) -> Vec<NodeId> {
        self.graph
            .nodes
            .iter()
            .filter(|n| n.mobility == 0 && !n.instr.opcode == 0)
            .map(|n| n.id)
            .collect()
    }

    /// Get the ASAP value for a node.
    pub fn asap(&self, node: NodeId) -> Cycle {
        self.graph.nodes[node].asap
    }

    /// Get the ALAP value for a node.
    pub fn alap(&self, node: NodeId) -> Cycle {
        self.graph.nodes[node].alap
    }

    /// Get the mobility for a node.
    pub fn mobility(&self, node: NodeId) -> u64 {
        self.graph.nodes[node].mobility
    }

    /// Returns the schedule if each node is placed at its ASAP cycle.
    pub fn asap_schedule(&self) -> HashMap<NodeId, Cycle> {
        let mut sched = HashMap::new();
        for &node_id in &self.topo_order {
            sched.insert(node_id, self.graph.nodes[node_id].asap);
        }
        sched
    }

    /// Returns the schedule if each node is placed at its ALAP cycle.
    pub fn alap_schedule(&self) -> HashMap<NodeId, Cycle> {
        let mut sched = HashMap::new();
        for &node_id in &self.topo_order {
            sched.insert(node_id, self.graph.nodes[node_id].alap);
        }
        sched
    }

    /// Heuristic: estimate lower bound on schedule length based on
    /// longest path and resource constraints.
    pub fn estimate_schedule_length(&self, _resource_model: &ResourceModel) -> Cycle {
        // The critical path provides one lower bound.
        // Resource usage provides another (total work / issue width).
        let total_work: u64 = self.graph.nodes.iter().map(|n| n.latency() as u64).sum();
        let issue_bound = total_work / _resource_model.issue_width as u64;
        std::cmp::max(self.critical_path_length, issue_bound)
    }

    /// Print a human-readable representation of the schedule DAG.
    pub fn display(&self) -> String {
        let mut s = String::new();
        s.push_str("ScheduleDAG:\n");
        s.push_str(&format!(
            "  Critical path length: {}\n",
            self.critical_path_length
        ));
        s.push_str("  Nodes:\n");
        for &node_id in &self.topo_order {
            let node = &self.graph.nodes[node_id];
            // Skip sentinels in display.
            if node.instr.opcode == 0
                && (Some(node_id) == self.graph.entry_node || Some(node_id) == self.graph.exit_node)
            {
                continue;
            }
            s.push_str(&format!(
                "    N{}: op={}, asap={}, alap={}, mobility={}, depth={}, height={}\n",
                node_id,
                node.instr.opcode,
                node.asap,
                node.alap,
                node.mobility,
                node.depth,
                node.height,
            ));
        }
        s
    }

    /// Consume self and return the underlying graph.
    pub fn into_graph(self) -> DependenceGraph {
        self.graph
    }
}

// ============================================================================
// ForceDirectedScheduler — Iterative improvement scheduling
// ============================================================================
// Force-directed scheduling (FDS) balances the distribution of operations
// across time steps to reduce resource congestion. Unlike list scheduling
// (greedy), FDS takes a global view and iteratively reduces the force
// (congestion penalty) to find a near-optimal schedule.
//
// Algorithm:
//   1. Start with ASAP schedule.
//   2. For each operation, compute "force" (penalty) for each possible
//      time slot in its mobility range.
//   3. The force is the sum of self-force (resource congestion caused
//      by the operation itself) and predecessor/successor forces.
//   4. Move the operation to the slot with minimum force.
//   5. Repeat until convergence.

/// Statistics for a time slot in force-directed scheduling.
#[derive(Debug, Clone, Default)]
struct TimeSlotStats {
    /// Number of operations scheduled in this slot.
    pub ops_count: usize,
    /// Resource usage per functional unit kind.
    pub resource_usage: HashMap<FuncUnitKind, f64>,
}

/// Force-directed scheduler.
#[derive(Debug, Clone)]
pub struct ForceDirectedScheduler {
    /// The dependence graph.
    graph: DependenceGraph,
    /// Current schedule: node_id → current cycle.
    schedule: HashMap<NodeId, Cycle>,
    /// Mobility (slack) for each node.
    mobility: HashMap<NodeId, u64>,
    /// Resource model.
    resource_model: ResourceModel,
    /// Distribution graph: probability that a node is in each time slot.
    distr_graph: HashMap<NodeId, Vec<f64>>,
    /// Time slot statistics.
    slot_stats: BTreeMap<Cycle, TimeSlotStats>,
    /// Iteration count.
    iterations: usize,
    /// Current temperature (for simulated annealing variant).
    temperature: f64,
}

impl ForceDirectedScheduler {
    /// Create a new force-directed scheduler.
    pub fn new(graph: DependenceGraph, resource_model: ResourceModel) -> Self {
        let dag = ScheduleDAG::new(graph.clone());
        let mut mobility = HashMap::new();
        let mut schedule = HashMap::new();

        for node in &graph.nodes {
            if node.instr.opcode != 0 {
                mobility.insert(node.id, dag.mobility(node.id));
                schedule.insert(node.id, dag.asap(node.id));
            }
        }

        Self {
            graph,
            schedule,
            mobility,
            resource_model,
            distr_graph: HashMap::new(),
            slot_stats: BTreeMap::new(),
            iterations: 0,
            temperature: 1.0,
        }
    }

    /// Run force-directed scheduling for a given number of iterations.
    pub fn run(&mut self, max_iterations: usize) -> HashMap<NodeId, Cycle> {
        for _ in 0..max_iterations {
            self.build_distribution();
            let changed = self.apply_forces();
            self.iterations += 1;
            if !changed {
                break;
            }
            if self.temperature > 0.01 {
                self.temperature *= 0.95;
            }
        }
        self.schedule.clone()
    }

    /// Build the probabilistic distribution for each node's possible time slots.
    fn build_distribution(&mut self) {
        self.distr_graph.clear();
        self.slot_stats.clear();

        for node in &self.graph.nodes {
            if node.instr.opcode == 0 {
                continue;
            }
            let mobility = self.mobility.get(&node.id).copied().unwrap_or(0);
            let asap = self.schedule.get(&node.id).copied().unwrap_or(0);

            // Uniform distribution across mobility window.
            let window = (mobility + 1) as usize;
            let prob = 1.0 / window as f64;
            let distr: Vec<f64> = (0..window).map(|_| prob).collect();
            self.distr_graph.insert(node.id, distr);

            // Update slot statistics.
            for t in asap..=asap + mobility {
                let stats = self.slot_stats.entry(t).or_default();
                stats.ops_count += 1;
            }
        }
    }

    /// Apply forces: for each node, compute the force for each feasible
    /// time slot and move to the one with minimum force.
    fn apply_forces(&mut self) -> bool {
        let mut changed = false;
        let node_ids: Vec<NodeId> = self
            .graph
            .nodes
            .iter()
            .filter(|n| n.instr.opcode != 0)
            .map(|n| n.id)
            .collect();

        for node_id in node_ids {
            let mobility = self.mobility.get(&node_id).copied().unwrap_or(0);
            let asap = self.schedule.get(&node_id).copied().unwrap_or(0);

            if mobility == 0 {
                continue; // Cannot move.
            }

            let mut best_cycle = asap;
            let mut best_force = f64::MAX;

            for t in asap..=asap + mobility {
                let force = self.compute_force(node_id, t);
                if force < best_force {
                    best_force = force;
                    best_cycle = t;
                }
            }

            if best_cycle != asap {
                self.schedule.insert(node_id, best_cycle);
                changed = true;
            }
        }

        changed
    }

    /// Compute the force for placing an operation at a given time slot.
    fn compute_force(&self, node_id: NodeId, target_cycle: Cycle) -> f64 {
        let node = &self.graph.nodes[node_id];
        let unit = self.resource_model.get_unit_kind(node.opcode());

        // Self-force: congestion at the target cycle.
        let self_force = self.congestion_at(unit, target_cycle);

        // Predecessor force: ensure predecessors finish before this cycle.
        let mut pred_force = 0.0;
        let latency = node.latency() as u64;
        for edge in &node.preds {
            if let Some(&pred_cycle) = self.schedule.get(&edge.from) {
                let pred_latency = self.graph.nodes[edge.from].latency() as u64;
                if pred_cycle + pred_latency > target_cycle {
                    pred_force += (pred_cycle + pred_latency - target_cycle) as f64 * 10.0;
                }
            }
        }

        // Successor force: ensure successors can start after this finishes.
        let mut succ_force = 0.0;
        for edge in &node.succs {
            if let Some(&succ_cycle) = self.schedule.get(&edge.to) {
                if target_cycle + latency > succ_cycle {
                    succ_force += (target_cycle + latency - succ_cycle) as f64 * 10.0;
                }
            }
        }

        self_force + pred_force + succ_force
    }

    /// Measure resource congestion at a given cycle.
    fn congestion_at(&self, unit: FuncUnitKind, cycle: Cycle) -> f64 {
        if let Some(stats) = self.slot_stats.get(&cycle) {
            *stats.resource_usage.get(&unit).unwrap_or(&0.0)
        } else {
            0.0
        }
    }

    /// Get the final schedule length.
    pub fn schedule_length(&self) -> Cycle {
        self.schedule.values().max().copied().unwrap_or(0)
    }
}

// ============================================================================
// ResourceModel — Execution unit modeling
// ============================================================================
// Models the target CPU's execution pipeline: functional units (ALU,
// memory, branch, FP, vector), pipeline stages, issue width, and a
// reservation table that tracks resource usage per cycle.
//
// The reservation table is a cycle-indexed map of resource usage
// counts, used by the hazard recognizer to detect structural hazards.

/// A functional unit type.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum FuncUnitKind {
    /// Integer ALU.
    ALU,
    /// Load unit.
    Load,
    /// Store unit.
    Store,
    /// Branch unit.
    Branch,
    /// Floating-point adder.
    FPAdd,
    /// Floating-point multiplier.
    FPMul,
    /// Floating-point divider.
    FPDiv,
    /// Vector ALU.
    VecALU,
    /// Vector load/store unit.
    VecMem,
    /// Complex integer (multiply/divide).
    Complex,
    /// General-purpose (can execute any simple instruction).
    General,
}

impl FuncUnitKind {
    pub fn as_str(self) -> &'static str {
        match self {
            FuncUnitKind::ALU => "ALU",
            FuncUnitKind::Load => "Load",
            FuncUnitKind::Store => "Store",
            FuncUnitKind::Branch => "Branch",
            FuncUnitKind::FPAdd => "FPAdd",
            FuncUnitKind::FPMul => "FPMul",
            FuncUnitKind::FPDiv => "FPDiv",
            FuncUnitKind::VecALU => "VecALU",
            FuncUnitKind::VecMem => "VecMem",
            FuncUnitKind::Complex => "Complex",
            FuncUnitKind::General => "General",
        }
    }
}

/// A single functional unit in the processor.
#[derive(Debug, Clone)]
pub struct FuncUnit {
    /// Name of the unit.
    pub name: String,
    /// Kind of the unit.
    pub kind: FuncUnitKind,
    /// Number of identical instances available per cycle.
    pub count: u32,
    /// Pipeline depth for this unit (stages).
    pub pipeline_depth: u32,
    /// Whether this unit is fully pipelined (can accept new op every cycle).
    pub fully_pipelined: bool,
    /// Whether this unit supports forwarding (bypass) from its output.
    pub supports_forwarding: bool,
    /// Cycle at which the result is available for forwarding.
    pub forwarding_cycle: u32,
}

impl FuncUnit {
    pub fn new(name: &str, kind: FuncUnitKind, count: u32) -> Self {
        Self {
            name: name.to_string(),
            kind,
            count,
            pipeline_depth: 1,
            fully_pipelined: true,
            supports_forwarding: false,
            forwarding_cycle: 0,
        }
    }

    pub fn with_pipeline(mut self, depth: u32, pipelined: bool) -> Self {
        self.pipeline_depth = depth;
        self.fully_pipelined = pipelined;
        self
    }

    pub fn with_forwarding(mut self, cycle: u32) -> Self {
        self.supports_forwarding = true;
        self.forwarding_cycle = cycle;
        self
    }
}

/// A mapping from opcode to the functional unit(s) it uses.
#[derive(Debug, Clone)]
pub struct OpcodeResourceUsage {
    /// Opcode this usage applies to.
    pub opcode: u32,
    /// The functional unit kind required.
    pub unit: FuncUnitKind,
    /// Base latency in cycles.
    pub latency: u32,
    /// Whether this opcode can be pipelined on the unit.
    pub pipelined: bool,
    /// Number of micro-ops this instruction decomposes into.
    pub micro_ops: u32,
    /// Resource usage vector: (unit_kind, cycles_used).
    pub resource_cycles: Vec<(FuncUnitKind, u32)>,
}

impl OpcodeResourceUsage {
    pub fn new(opcode: u32, unit: FuncUnitKind, latency: u32) -> Self {
        Self {
            opcode,
            unit,
            latency,
            pipelined: true,
            micro_ops: 1,
            resource_cycles: vec![(unit, latency)],
        }
    }
}

/// The resource model for a target CPU.
#[derive(Debug, Clone)]
pub struct ResourceModel {
    /// Maximum number of instructions that can be issued per cycle.
    pub issue_width: u32,
    /// Available functional units.
    pub units: Vec<FuncUnit>,
    /// Opcode → resource usage map.
    pub opcode_usage: HashMap<u32, OpcodeResourceUsage>,
    /// Default latency for unknown opcodes.
    pub default_latency: u32,
    /// Cycle-by-cycle reservation table.
    /// Maps cycle number → (unit_kind, count_used_in_that_cycle).
    reservation_table: BTreeMap<Cycle, HashMap<FuncUnitKind, u32>>,
}

impl ResourceModel {
    /// Create a default resource model for a generic out-of-order core.
    pub fn default_model() -> Self {
        let mut model = Self {
            issue_width: 4,
            units: Vec::new(),
            opcode_usage: HashMap::new(),
            default_latency: 1,
            reservation_table: BTreeMap::new(),
        };

        // Define functional units.
        model
            .units
            .push(FuncUnit::new("ALU0", FuncUnitKind::ALU, 4));
        model
            .units
            .push(FuncUnit::new("LoadUnit", FuncUnitKind::Load, 2).with_pipeline(3, true));
        model
            .units
            .push(FuncUnit::new("StoreUnit", FuncUnitKind::Store, 1).with_pipeline(1, true));
        model
            .units
            .push(FuncUnit::new("BranchUnit", FuncUnitKind::Branch, 1));
        model
            .units
            .push(FuncUnit::new("FPAdd", FuncUnitKind::FPAdd, 1).with_pipeline(3, true));
        model
            .units
            .push(FuncUnit::new("FPMul", FuncUnitKind::FPMul, 1).with_pipeline(5, true));
        model
            .units
            .push(FuncUnit::new("FPDiv", FuncUnitKind::FPDiv, 1).with_pipeline(12, false));
        model
            .units
            .push(FuncUnit::new("Complex", FuncUnitKind::Complex, 1).with_pipeline(3, false));

        model
    }

    /// Create a resource model for a typical x86-64 Skylake-like core.
    pub fn skylake_model() -> Self {
        let mut model = Self {
            issue_width: 4,
            units: Vec::new(),
            opcode_usage: HashMap::new(),
            default_latency: 1,
            reservation_table: BTreeMap::new(),
        };

        // Skylake has 8 dispatch ports, grouped logically.
        model
            .units
            .push(FuncUnit::new("Port0", FuncUnitKind::ALU, 1)); // ALU/FP/Vec
        model
            .units
            .push(FuncUnit::new("Port1", FuncUnitKind::ALU, 1)); // ALU/FP/Vec
        model
            .units
            .push(FuncUnit::new("Port2", FuncUnitKind::Load, 1)); // Load
        model
            .units
            .push(FuncUnit::new("Port3", FuncUnitKind::Load, 1)); // Load
        model
            .units
            .push(FuncUnit::new("Port4", FuncUnitKind::Store, 1)); // Store data
        model
            .units
            .push(FuncUnit::new("Port5", FuncUnitKind::ALU, 1)); // ALU/LEA
        model
            .units
            .push(FuncUnit::new("Port6", FuncUnitKind::Branch, 1)); // Branch/ALU
        model
            .units
            .push(FuncUnit::new("Port7", FuncUnitKind::Store, 1)); // Store address

        model
    }

    /// Create a resource model for a simple in-order RISC-V core.
    pub fn riscv_simple_model() -> Self {
        let mut model = Self {
            issue_width: 1,
            units: Vec::new(),
            opcode_usage: HashMap::new(),
            default_latency: 1,
            reservation_table: BTreeMap::new(),
        };

        model.units.push(FuncUnit::new("ALU", FuncUnitKind::ALU, 1));
        model
            .units
            .push(FuncUnit::new("Mem", FuncUnitKind::Load, 1).with_pipeline(1, true));
        model
            .units
            .push(FuncUnit::new("Branch", FuncUnitKind::Branch, 1));
        model
            .units
            .push(FuncUnit::new("MulDiv", FuncUnitKind::Complex, 1).with_pipeline(4, false));

        model
    }

    /// Get the latency for a given opcode.
    pub fn get_latency(&self, opcode: u32) -> u32 {
        self.opcode_usage
            .get(&opcode)
            .map(|u| u.latency)
            .unwrap_or(self.default_latency)
    }

    /// Get the functional unit kind used by an opcode.
    pub fn get_unit_kind(&self, opcode: u32) -> FuncUnitKind {
        self.opcode_usage
            .get(&opcode)
            .map(|u| u.unit)
            .unwrap_or(FuncUnitKind::ALU)
    }

    /// Check if a given unit kind is available at a given cycle.
    pub fn is_unit_available(&self, unit: FuncUnitKind, cycle: Cycle) -> bool {
        if let Some(usage_map) = self.reservation_table.get(&cycle) {
            let used = usage_map.get(&unit).copied().unwrap_or(0);
            let total = self.get_unit_count(unit);
            used < total
        } else {
            true
        }
    }

    /// Get the count of a functional unit kind.
    pub fn get_unit_count(&self, kind: FuncUnitKind) -> u32 {
        self.units
            .iter()
            .filter(|u| u.kind == kind)
            .map(|u| u.count)
            .sum()
    }

    /// Reserve a resource for an instruction at a given cycle.
    pub fn reserve(&mut self, opcode: u32, start_cycle: Cycle) {
        let usage = self
            .opcode_usage
            .get(&opcode)
            .cloned()
            .unwrap_or_else(|| OpcodeResourceUsage::new(opcode, FuncUnitKind::ALU, 1));

        let latency = usage.latency as u64;
        let unit = usage.unit;

        // Reserve the functional unit for the duration of the instruction.
        for cyc in start_cycle..start_cycle + latency {
            let entry = self
                .reservation_table
                .entry(cyc)
                .or_insert_with(HashMap::new);
            *entry.entry(unit).or_insert(0) += 1;
        }
    }

    /// Check if we can issue `count` instructions of given opcodes at cycle.
    pub fn can_issue(&self, opcodes: &[u32], cycle: Cycle) -> bool {
        if opcodes.len() as u32 > self.issue_width {
            return false;
        }
        for &opc in opcodes {
            let unit = self.get_unit_kind(opc);
            if !self.is_unit_available(unit, cycle) {
                return false;
            }
        }
        true
    }

    /// Find the next cycle where a given opcode can be issued, starting
    /// from `earliest`.
    pub fn find_issue_slot(&self, opcode: u32, earliest: Cycle) -> Cycle {
        let mut cycle = earliest;
        loop {
            let unit = self.get_unit_kind(opcode);
            if self.is_unit_available(unit, cycle) {
                return cycle;
            }
            cycle += 1;
        }
    }

    /// Clear the reservation table.
    pub fn clear_reservations(&mut self) {
        self.reservation_table.clear();
    }

    /// Return the maximum cycle in the reservation table.
    pub fn max_reserved_cycle(&self) -> Option<Cycle> {
        self.reservation_table.keys().last().copied()
    }

    /// Get a summary of resource utilization.
    pub fn utilization_summary(&self) -> String {
        let mut s = String::from("ResourceModel Utilization:\n");
        s.push_str(&format!("  Issue width: {}\n", self.issue_width));
        s.push_str("  Functional units:\n");
        for unit in &self.units {
            let count = self.get_unit_count(unit.kind);
            s.push_str(&format!(
                "    {} ({:?}): {} instance(s)\n",
                unit.name, unit.kind, count
            ));
        }
        if !self.reservation_table.is_empty() {
            s.push_str("  Reservation table:\n");
            for (cycle, usage) in self.reservation_table.iter().take(20) {
                s.push_str(&format!("    Cycle {}: ", cycle));
                for (unit, count) in usage {
                    s.push_str(&format!("{:?}={} ", unit, count));
                }
                s.push('\n');
            }
        }
        s
    }
}

impl Default for ResourceModel {
    fn default() -> Self {
        Self::default_model()
    }
}

// ============================================================================
// HazardRecognizer — Structural/Data hazard detection
// ============================================================================
// Detects pipeline hazards during scheduling:
// - Structural hazards: resource conflicts (not enough functional units)
// - Data hazards: RAW (true dependence), WAR (anti), WAW (output)
// - Forwarding paths: bypass network reduces effective latency
// - Stall insertion: cycles needed before an instruction can issue

/// Whether a forwarding path exists between two pipeline stages.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ForwardingPath {
    /// No forwarding: must wait for write-back.
    None,
    /// Full forwarding: result available same cycle.
    Full,
    /// Forwarding after N cycles.
    Delayed(u32),
    /// Forwarding only from specific execution units.
    Restricted(FuncUnitKind),
}

/// A hazard detected during scheduling.
#[derive(Debug, Clone)]
pub struct Hazard {
    /// The kind of hazard.
    pub kind: HazardKind,
    /// The instruction that causes the hazard.
    pub instr_idx: usize,
    /// The resource or register involved.
    pub resource: String,
    /// Stall cycles needed to resolve the hazard.
    pub stall_cycles: u32,
    /// Whether this hazard can be resolved by forwarding.
    pub can_forward: bool,
}

impl Hazard {
    pub fn new(kind: HazardKind, instr_idx: usize, resource: &str, stalls: u32) -> Self {
        Self {
            kind,
            instr_idx,
            resource: resource.to_string(),
            stall_cycles: stalls,
            can_forward: false,
        }
    }

    pub fn with_forwarding(mut self) -> Self {
        self.can_forward = true;
        self
    }
}

/// Kinds of pipeline hazards.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HazardKind {
    /// Structural: not enough functional units.
    Structural,
    /// RAW: true data dependence, consumer needs producer's result.
    ReadAfterWrite,
    /// WAR: anti dependence, writer must wait for readers.
    WriteAfterRead,
    /// WAW: output dependence, writes must stay ordered.
    WriteAfterWrite,
    /// Control hazard from branches.
    Control,
    /// Memory ordering hazard.
    MemoryOrder,
    /// Resource conflict on issue width.
    IssueWidth,
}

impl HazardKind {
    pub fn as_str(self) -> &'static str {
        match self {
            HazardKind::Structural => "structural",
            HazardKind::ReadAfterWrite => "RAW",
            HazardKind::WriteAfterRead => "WAR",
            HazardKind::WriteAfterWrite => "WAW",
            HazardKind::Control => "control",
            HazardKind::MemoryOrder => "memory_order",
            HazardKind::IssueWidth => "issue_width",
        }
    }
}

/// The hazard recognizer examines scheduled instructions and the
/// resource model to detect pipeline hazards and determine when
/// the next instruction can be issued.
#[derive(Debug, Clone)]
pub struct HazardRecognizer {
    /// Resource model of the target.
    pub resource_model: ResourceModel,
    /// Forwarding paths: (producer_unit, consumer_unit) → forwarding delay.
    forwarding_paths: HashMap<(FuncUnitKind, FuncUnitKind), ForwardingPath>,
    /// Scoreboard: register → (producer_node, write_cycle).
    scoreboard: HashMap<Reg, (NodeId, Cycle)>,
    /// Last cycle at which an instruction was issued.
    pub current_cycle: Cycle,
    /// Instructions issued so far: (node_id, issue_cycle).
    pub issued: Vec<(NodeId, Cycle)>,
    /// Whether to attempt forwarding.
    pub enable_forwarding: bool,
}

impl HazardRecognizer {
    /// Create a new hazard recognizer with a given resource model.
    pub fn new(resource_model: ResourceModel) -> Self {
        Self {
            resource_model,
            forwarding_paths: HashMap::new(),
            scoreboard: HashMap::new(),
            current_cycle: 0,
            issued: Vec::new(),
            enable_forwarding: true,
        }
    }

    /// Add a forwarding path.
    pub fn add_forwarding(
        &mut self,
        producer: FuncUnitKind,
        consumer: FuncUnitKind,
        path: ForwardingPath,
    ) {
        self.forwarding_paths.insert((producer, consumer), path);
    }

    /// Check for structural hazards: is there a free functional unit?
    pub fn check_structural(&self, opcode: u32, at_cycle: Cycle) -> Option<Hazard> {
        let unit = self.resource_model.get_unit_kind(opcode);
        if !self.resource_model.is_unit_available(unit, at_cycle) {
            return Some(Hazard::new(
                HazardKind::Structural,
                0,
                unit.as_str(),
                1, // Stall at least 1 cycle for structural hazard
            ));
        }
        None
    }

    /// Check for RAW (true data) hazards on a given instruction.
    ///
    /// For each use operand, checks if the defining instruction has
    /// finished and whether forwarding can reduce the effective latency.
    pub fn check_raw(&self, node: &DepNode, nodes: &[DepNode]) -> Vec<Hazard> {
        let mut hazards = Vec::new();

        for u in &node.instr.uses {
            if let Some(&(prod_node, write_cycle)) = self.scoreboard.get(u) {
                // Check if the producer has finished.
                let producer = &nodes[prod_node];
                let effective_latency = if self.enable_forwarding {
                    self.get_forwarding_latency(producer.opcode(), node.opcode())
                } else {
                    producer.latency() as u64
                };

                let available_at = write_cycle + effective_latency;
                if self.current_cycle < available_at {
                    let stalls = (available_at - self.current_cycle) as u32;
                    let mut hazard = Hazard::new(
                        HazardKind::ReadAfterWrite,
                        node.id,
                        &format!("{}", u),
                        stalls,
                    );
                    if self.enable_forwarding
                        && self.get_forwarding_latency(producer.opcode(), node.opcode())
                            < producer.latency() as u64
                    {
                        hazard = hazard.with_forwarding();
                    }
                    hazards.push(hazard);
                }
            }
        }

        hazards
    }

    /// Check for WAR (anti) hazards: a consumer's register must not be
    /// overwritten before all pending reads complete.
    pub fn check_war(&self, node: &DepNode, _nodes: &[DepNode]) -> Vec<Hazard> {
        let mut hazards = Vec::new();

        // For each def, check if there are pending uses.
        for d in &node.instr.defs {
            // If this register is in the scoreboard (meaning it was defined
            // or used by a previous instruction), a WAR may exist.
            // Simplified: check if the register is currently being read.
            if self.scoreboard.contains_key(d) {
                // The previous value might still be in use.
                // Conservative: stall 1 cycle.
                hazards.push(Hazard::new(
                    HazardKind::WriteAfterRead,
                    node.id,
                    &format!("{}", d),
                    0, // WAR is usually handled by renaming in OoO
                ));
            }
        }
        hazards
    }

    /// Check for WAW (output) hazards: two writes to the same register
    /// must stay in program order.
    pub fn check_waw(&self, node: &DepNode) -> Vec<Hazard> {
        let mut hazards = Vec::new();

        for d in &node.instr.defs {
            if self.scoreboard.contains_key(d) {
                hazards.push(Hazard::new(
                    HazardKind::WriteAfterWrite,
                    node.id,
                    &format!("{}", d),
                    0,
                ));
            }
        }
        hazards
    }

    /// Get the forwarding latency from a producer opcode to consumer opcode.
    fn get_forwarding_latency(&self, producer_opcode: u32, consumer_opcode: u32) -> u64 {
        let prod_unit = self.resource_model.get_unit_kind(producer_opcode);
        let cons_unit = self.resource_model.get_unit_kind(consumer_opcode);

        if let Some(path) = self.forwarding_paths.get(&(prod_unit, cons_unit)) {
            match path {
                ForwardingPath::None => self.resource_model.get_latency(producer_opcode) as u64,
                ForwardingPath::Full => 0,
                ForwardingPath::Delayed(d) => *d as u64,
                ForwardingPath::Restricted(_) => {
                    // Restricted forwarding: available only for some cases.
                    // Conservative: use half latency.
                    (self.resource_model.get_latency(producer_opcode) / 2) as u64
                }
            }
        } else {
            // No forwarding path: full latency.
            self.resource_model.get_latency(producer_opcode) as u64
        }
    }

    /// Can the given instruction be issued at the current cycle?
    /// Returns None if no hazards, or Some(hazards) if stalled.
    pub fn can_issue_at(&self, node: &DepNode, nodes: &[DepNode], at_cycle: Cycle) -> Vec<Hazard> {
        let mut hazards = Vec::new();

        // Check structural hazards.
        if let Some(h) = self.check_structural(node.opcode(), at_cycle) {
            hazards.push(h);
        }

        // Check issue width: don't exceed.
        let issued_this_cycle = self
            .issued
            .iter()
            .filter(|(_, cyc)| *cyc == at_cycle)
            .count();
        if issued_this_cycle as u32 >= self.resource_model.issue_width {
            hazards.push(Hazard::new(
                HazardKind::IssueWidth,
                node.id,
                "issue_width",
                self.resource_model.issue_width,
            ));
        }

        // Check data hazards.
        hazards.extend(self.check_raw(node, nodes));
        hazards.extend(self.check_war(node, nodes));
        hazards.extend(self.check_waw(node));

        hazards
    }

    /// Issue an instruction: update the scoreboard and resource reservations.
    pub fn issue(&mut self, node: &DepNode, at_cycle: Cycle) {
        // Update scoreboard for definitions.
        for d in &node.instr.defs {
            self.scoreboard
                .insert(*d, (node.id, at_cycle + node.latency() as u64));
        }

        // Mark as issued.
        self.issued.push((node.id, at_cycle));

        // Reserve resources.
        self.resource_model.reserve(node.opcode(), at_cycle);
    }

    /// Advance to the next issue slot, resolving hazards.
    pub fn advance_to(&mut self, cycle: Cycle) {
        self.current_cycle = cycle;
    }

    /// Find the next cycle where this instruction can be issued without hazards.
    pub fn find_issue_cycle(&self, node: &DepNode, nodes: &[DepNode], earliest: Cycle) -> Cycle {
        let mut cycle = earliest;
        loop {
            let hazards = self.can_issue_at(node, nodes, cycle);
            if hazards.is_empty() {
                return cycle;
            }
            // Find the minimum extra delay from hazards.
            let max_stall = hazards.iter().map(|h| h.stall_cycles).max().unwrap_or(1);
            cycle += std::cmp::max(1, max_stall as u64);
        }
    }

    /// Get the current cycle.
    pub fn cycle(&self) -> Cycle {
        self.current_cycle
    }

    /// Reset the recognizer for a new scheduling region.
    pub fn clear(&mut self) {
        self.scoreboard.clear();
        self.issued.clear();
        self.current_cycle = 0;
        self.resource_model.clear_reservations();
    }
}

// ============================================================================
// ListScheduler — Priority-based scheduling
// ============================================================================
// Implements list scheduling with priority heuristics. The scheduler
// maintains a ready list of instructions whose predecessors have all
// been scheduled, selects the highest-priority ready instruction, and
// issues it at the earliest cycle where no hazards occur.
//
// Priority heuristics:
//   - CriticalPath: use depth (longest path to sink) as priority.
//   - ResourceHeight: prioritize instructions that are on the critical
//     path for a scarce resource.
//   - LatencyHeight: combine latency and height.
//   - Balanced: blend multiple factors.
//
// Cycle-by-cycle: the scheduler advances the clock cycle by cycle,
// checking at each cycle whether any ready instruction can be issued
// without hazards.

/// Priority heuristic for the list scheduler.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SchedPriority {
    /// Priority by critical path depth (longest path to sink).
    CriticalPath,
    /// Priority by height (longest path from source).
    Height,
    /// Priority by latency (longer latency first).
    Latency,
    /// Priority by instruction count (more successors first).
    SuccessorCount,
    /// Balanced: weighted blend of depth and mobility.
    Balanced,
    /// Resource-aware: prioritize scarce-resource consumers.
    ResourceAware,
    /// Prioritize nodes that reduce register pressure.
    RegPressure,
}

/// An entry in the ready list priority queue.
#[derive(Debug, Clone, Eq)]
struct ReadyEntry {
    /// Node id in the dependence graph.
    node_id: NodeId,
    /// Computed priority value (higher = more urgent).
    priority: i64,
    /// Tiebreaker: original instruction index (preserve some order).
    tiebreaker: usize,
}

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

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

impl Ord for ReadyEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        // Higher priority comes first (max-heap).
        self.priority
            .cmp(&other.priority)
            .then_with(|| other.tiebreaker.cmp(&self.tiebreaker))
    }
}

/// The list scheduler.
#[derive(Debug, Clone)]
pub struct ListScheduler {
    /// The dependence graph being scheduled.
    pub graph: DependenceGraph,
    /// Topological order of the graph.
    pub topo_order: Vec<NodeId>,
    /// Ready list (max-heap by priority).
    ready_list: BinaryHeap<ReadyEntry>,
    /// Already scheduled nodes in order: (node_id, issue_cycle).
    pub schedule: Vec<(NodeId, Cycle)>,
    /// Current scheduling cycle.
    pub current_cycle: Cycle,
    /// Priority heuristic.
    pub priority_heuristic: SchedPriority,
    /// Resource model for hazard checking.
    pub resource_model: ResourceModel,
    /// Hazard recognizer.
    pub hazard_recognizer: HazardRecognizer,
    /// Whether to consider resource constraints.
    pub resource_aware: bool,
    /// The maximum cycle reached.
    pub max_cycle: Cycle,
}

impl ListScheduler {
    /// Create a new list scheduler from a dependence graph and resource model.
    pub fn new(graph: DependenceGraph, resource_model: ResourceModel) -> Self {
        let topo_order = ScheduleDAG::new(graph.clone()).topo_order;
        let hazard_recognizer = HazardRecognizer::new(resource_model.clone());

        Self {
            graph,
            topo_order,
            ready_list: BinaryHeap::new(),
            schedule: Vec::new(),
            current_cycle: 0,
            priority_heuristic: SchedPriority::CriticalPath,
            resource_model,
            hazard_recognizer,
            resource_aware: true,
            max_cycle: 0,
        }
    }

    /// Compute priorities for all nodes based on the selected heuristic.
    pub fn compute_priorities(&mut self) {
        match self.priority_heuristic {
            SchedPriority::CriticalPath => self.compute_critical_path_priority(),
            SchedPriority::Height => self.compute_height_priority(),
            SchedPriority::Latency => self.compute_latency_priority(),
            SchedPriority::SuccessorCount => self.compute_successor_count_priority(),
            SchedPriority::Balanced => self.compute_balanced_priority(),
            SchedPriority::ResourceAware => self.compute_resource_aware_priority(),
            SchedPriority::RegPressure => self.compute_reg_pressure_priority(),
        }
    }

    /// Priority = depth (longest path to sink). Nodes on the critical path
    /// get highest priority.
    fn compute_critical_path_priority(&mut self) {
        let dag = ScheduleDAG::new(self.graph.clone());
        for node in &mut self.graph.nodes {
            node.priority = dag.graph().nodes[node.id].depth as i64;
        }
    }

    /// Priority = height (longest path from source).
    fn compute_height_priority(&mut self) {
        let dag = ScheduleDAG::new(self.graph.clone());
        for node in &mut self.graph.nodes {
            node.priority = dag.graph().nodes[node.id].height as i64;
        }
    }

    /// Priority = latency.
    fn compute_latency_priority(&mut self) {
        for node in &mut self.graph.nodes {
            node.priority = node.latency() as i64;
        }
    }

    /// Priority = number of successors (fan-out).
    fn compute_successor_count_priority(&mut self) {
        for node in &mut self.graph.nodes {
            node.priority = node.succs.len() as i64;
        }
    }

    /// Priority = weighted combination of depth and inverse mobility.
    fn compute_balanced_priority(&mut self) {
        let dag = ScheduleDAG::new(self.graph.clone());
        for node in &mut self.graph.nodes {
            let depth = dag.graph().nodes[node.id].depth;
            let mobility = dag.graph().nodes[node.id].mobility;
            // Higher depth → higher priority; lower mobility → higher priority.
            let mobility_penalty = if mobility == 0 { 100 } else { 0 };
            node.priority = (depth * 2) as i64 + mobility_penalty;
        }
    }

    /// Resource-aware priority: nodes that use scarce resources get a boost.
    fn compute_resource_aware_priority(&mut self) {
        let dag = ScheduleDAG::new(self.graph.clone());

        // Count total instructions per functional unit kind.
        let mut unit_counts: HashMap<FuncUnitKind, usize> = HashMap::new();
        for node in &self.graph.nodes {
            let unit = self.resource_model.get_unit_kind(node.opcode());
            *unit_counts.entry(unit).or_insert(0) += 1;
        }

        for node in &mut self.graph.nodes {
            let depth = dag.graph().nodes[node.id].depth;
            let unit = self.resource_model.get_unit_kind(node.opcode());
            let unit_count = unit_counts.get(&unit).copied().unwrap_or(1) as i64;
            let unit_available = self.resource_model.get_unit_count(unit) as i64;

            // Scarce resources (high demand / low supply) get a boost.
            let scarcity = if unit_available > 0 {
                (unit_count * 10) / unit_available
            } else {
                10
            };

            node.priority = (depth as i64) * 10 + scarcity;
        }
    }

    /// Register-pressure-aware priority: prioritize nodes that release registers.
    fn compute_reg_pressure_priority(&mut self) {
        let dag = ScheduleDAG::new(self.graph.clone());

        // Count how many uses each def has.
        let mut use_counts: HashMap<Reg, usize> = HashMap::new();
        for node in &self.graph.nodes {
            for u in &node.instr.uses {
                *use_counts.entry(*u).or_insert(0) += 1;
            }
        }

        for node in &mut self.graph.nodes {
            let depth = dag.graph().nodes[node.id].depth as i64;
            // Nodes whose defs have many uses (high register pressure) get priority.
            let pressure: i64 = node
                .instr
                .defs
                .iter()
                .map(|d| *use_counts.get(d).unwrap_or(&0) as i64)
                .sum();
            node.priority = depth * 100 + pressure;
        }
    }

    /// Initialize the ready list with source nodes (no unscheduled predecessors).
    fn init_ready_list(&mut self) {
        self.ready_list.clear();

        // Reset unscheduled predecessor counts.
        for node in &mut self.graph.nodes {
            node.unscheduled_preds = node.preds.len();
            node.scheduled = false;
            node.scheduled_cycle = 0;
        }

        // Add nodes with zero unscheduled predecessors.
        for node in &self.graph.nodes {
            if node.unscheduled_preds == 0 && !node.scheduled && node.instr.opcode != 0 {
                self.ready_list.push(ReadyEntry {
                    node_id: node.id,
                    priority: node.priority,
                    tiebreaker: node.instr.index,
                });
            }
        }
    }

    /// Run the list scheduling algorithm.
    ///
    /// Returns the schedule: Vec<(node_id, issue_cycle)>.
    pub fn run(&mut self) -> Vec<(NodeId, Cycle)> {
        self.compute_priorities();
        self.init_ready_list();
        self.schedule.clear();
        self.current_cycle = 0;
        self.max_cycle = 0;

        while !self.ready_list.is_empty() {
            // Collect ready nodes and find the earliest cycle any can issue.
            let mut issued_this_cycle = false;

            while !self.ready_list.is_empty() {
                // Peek at the highest-priority ready node.
                let ready = self.ready_list.peek().unwrap().node_id;
                let node = &self.graph.nodes[ready];

                if self.resource_aware {
                    // Check if it can issue at current cycle.
                    let hazards = self.hazard_recognizer.can_issue_at(
                        node,
                        &self.graph.nodes,
                        self.current_cycle,
                    );

                    if !hazards.is_empty() {
                        // Try to advance to next cycle.
                        // Check if any lower-priority node can issue.
                        // For simplicity: if the top can't issue, try others
                        // or advance the cycle.
                        let mut found = false;
                        let mut deferred = Vec::new();

                        // Try all ready entries.
                        while let Some(entry) = self.ready_list.pop() {
                            let n = &self.graph.nodes[entry.node_id];
                            let hz = self.hazard_recognizer.can_issue_at(
                                n,
                                &self.graph.nodes,
                                self.current_cycle,
                            );
                            if hz.is_empty() {
                                // Can issue this one.
                                self.issue_node(entry.node_id);
                                found = true;
                                issued_this_cycle = true;
                                break;
                            } else {
                                deferred.push(entry);
                            }
                        }

                        // Re-add deferred entries.
                        for entry in deferred {
                            self.ready_list.push(entry);
                        }

                        if !found {
                            break; // Nothing can issue at this cycle.
                        }
                    } else {
                        // Top priority can issue.
                        self.ready_list.pop();
                        self.issue_node(ready);
                        issued_this_cycle = true;
                    }
                } else {
                    // No resource model: issue all ready nodes in this cycle.
                    self.ready_list.pop();
                    self.issue_node(ready);
                    issued_this_cycle = true;
                }
            }

            if !issued_this_cycle {
                // Advance to next cycle.
                self.current_cycle += 1;
                // Add newly ready nodes.
                self.update_ready_list();
            }
        }

        self.max_cycle = self.current_cycle;
        self.schedule.clone()
    }

    /// Issue a node at the current cycle.
    fn issue_node(&mut self, node_id: NodeId) {
        // Clone what the hazard recognizer needs before mutating self.graph.
        let node_clone = self.graph.nodes[node_id].clone();
        self.graph.nodes[node_id].scheduled = true;
        self.graph.nodes[node_id].scheduled_cycle = self.current_cycle;

        self.schedule.push((node_id, self.current_cycle));
        self.hazard_recognizer
            .issue(&node_clone, self.current_cycle);

        // Update successor predecessor counts.
        let succs: Vec<NodeId> = self.graph.nodes[node_id]
            .succs
            .iter()
            .map(|e| e.to)
            .collect();
        for succ in succs {
            self.graph.nodes[succ].unscheduled_preds =
                self.graph.nodes[succ].unscheduled_preds.saturating_sub(1);
        }

        // Re-add newly ready nodes.
        self.update_ready_list();
    }

    /// Update the ready list with nodes that became ready.
    fn update_ready_list(&mut self) {
        for node in &mut self.graph.nodes {
            if node.unscheduled_preds == 0 && !node.scheduled && node.instr.opcode != 0 {
                // Check if already in ready list (simplified: just push).
                self.ready_list.push(ReadyEntry {
                    node_id: node.id,
                    priority: node.priority,
                    tiebreaker: node.instr.index,
                });
                // Mark so we don't re-add.
                node.unscheduled_preds = usize::MAX; // sentinel
            }
        }
    }

    /// Get the schedule length in cycles.
    pub fn schedule_length(&self) -> Cycle {
        self.max_cycle
    }

    /// Reorder the original instruction sequence according to the schedule.
    pub fn reorder_instructions(&self, original: &[SchedInstr]) -> Vec<SchedInstr> {
        let mut reordered: Vec<SchedInstr> = Vec::with_capacity(original.len());
        let mut sched_map: HashMap<NodeId, Cycle> = HashMap::new();

        for &(node_id, cycle) in &self.schedule {
            sched_map.insert(node_id, cycle);
        }

        // Sort by scheduled cycle, then by node id.
        let mut sorted: Vec<(NodeId, Cycle)> = self.schedule.clone();
        sorted.sort_by_key(|&(n, c)| (c, n));

        for (node_id, _cycle) in sorted {
            if node_id < original.len() {
                reordered.push(original[node_id].clone());
            }
        }

        reordered
    }

    /// Set the priority heuristic.
    pub fn with_priority(mut self, priority: SchedPriority) -> Self {
        self.priority_heuristic = priority;
        self
    }

    /// Enable or disable resource awareness.
    pub fn with_resource_aware(mut self, aware: bool) -> Self {
        self.resource_aware = aware;
        self
    }

    /// Print a summary of the schedule.
    pub fn display_schedule(&self) -> String {
        let mut s = String::new();
        s.push_str("ListScheduler Schedule:\n");
        s.push_str(&format!(
            "  Total nodes scheduled: {}\n",
            self.schedule.len()
        ));
        s.push_str(&format!("  Schedule length: {} cycles\n", self.max_cycle));
        s.push_str("  Cycle → Instructions:\n");

        let mut by_cycle: BTreeMap<Cycle, Vec<NodeId>> = BTreeMap::new();
        for &(node_id, cycle) in &self.schedule {
            by_cycle.entry(cycle).or_default().push(node_id);
        }

        for (cycle, nodes) in by_cycle {
            s.push_str(&format!("    Cycle {}: ", cycle));
            for n in nodes {
                s.push_str(&format!("N{}(op={}) ", n, self.graph.nodes[n].opcode()));
            }
            s.push('\n');
        }

        s
    }
}

// ============================================================================
// BidirectionalScheduler — Bottom-up + Top-down scheduling
// ============================================================================
// Bidirectional list scheduling explores both directions (top-down from
// sources and bottom-up from sinks) to find better schedules, especially
// for loops where register pressure at loop boundaries matters.

/// Direction of scheduling.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SchedDirection {
    /// Schedule from sources to sinks (top-down).
    TopDown,
    /// Schedule from sinks to sources (bottom-up).
    BottomUp,
    /// Bidirectional: alternate directions.
    Bidirectional,
}

/// Bidirectional list scheduler.
#[derive(Debug, Clone)]
pub struct BidirectionalScheduler {
    /// Top-down scheduler.
    top_down: ListScheduler,
    /// Bottom-up scheduler (reversed graph).
    bottom_up: Option<ListScheduler>,
    /// Direction preference.
    pub direction: SchedDirection,
    /// Top-down schedule result.
    pub td_schedule: Vec<(NodeId, Cycle)>,
    /// Bottom-up schedule result.
    pub bu_schedule: Vec<(NodeId, Cycle)>,
    /// Best combined schedule.
    pub best_schedule: Vec<(NodeId, Cycle)>,
    /// Best schedule length.
    pub best_length: Cycle,
}

impl BidirectionalScheduler {
    /// Create a bidirectional scheduler from a graph and resource model.
    pub fn new(graph: DependenceGraph, resource_model: ResourceModel) -> Self {
        // Build reversed graph for bottom-up scheduling.
        let mut rev_graph = graph.clone();
        for node in &mut rev_graph.nodes {
            std::mem::swap(&mut node.succs, &mut node.preds);
        }

        let td = ListScheduler::new(graph, resource_model.clone());
        let bu = ListScheduler::new(rev_graph, resource_model);

        Self {
            top_down: td,
            bottom_up: Some(bu),
            direction: SchedDirection::Bidirectional,
            td_schedule: Vec::new(),
            bu_schedule: Vec::new(),
            best_schedule: Vec::new(),
            best_length: 0,
        }
    }

    /// Run bidirectional scheduling.
    pub fn run(&mut self) -> Vec<(NodeId, Cycle)> {
        match self.direction {
            SchedDirection::TopDown => {
                self.td_schedule = self.top_down.run();
                self.best_schedule = self.td_schedule.clone();
                self.best_length = self.top_down.schedule_length();
            }
            SchedDirection::BottomUp => {
                if let Some(ref mut bu) = self.bottom_up {
                    self.bu_schedule = bu.run();
                    self.best_schedule = self.bu_schedule.clone();
                    self.best_length = bu.schedule_length();
                }
            }
            SchedDirection::Bidirectional => {
                // Run both and pick the better one.
                self.td_schedule = self.top_down.run();
                let td_len = self.top_down.schedule_length();

                if let Some(ref mut bu) = self.bottom_up {
                    self.bu_schedule = bu.run();
                    let bu_len = bu.schedule_length();

                    if td_len <= bu_len {
                        self.best_schedule = self.td_schedule.clone();
                        self.best_length = td_len;
                    } else {
                        self.best_schedule = self.bu_schedule.clone();
                        self.best_length = bu_len;
                    }
                }
            }
        }

        self.best_schedule.clone()
    }

    /// Get statistics about the bidirectional scheduling.
    pub fn comparison(&self) -> (Cycle, Cycle) {
        (
            self.top_down.schedule_length(),
            self.bottom_up
                .as_ref()
                .map(|bu| bu.schedule_length())
                .unwrap_or(0),
        )
    }
}

// ============================================================================
// PostRAScheduler — Post-RA scheduling, anti-dep breaking, copy insertion
// ============================================================================
// After register allocation, physical registers are assigned. The
// PostRAScheduler re-orders instructions within a basic block, breaking
// anti (WAR) and output (WAW) dependences by inserting register copies
// when profitable. This is a critical pass for in-order processors but
// also beneficial for OoO to reduce rename register pressure.
//
// Key operations:
//   - Anti-dep breaking: if an anti-dependence prevents reordering,
//     insert a copy to a free register, breaking the false dependence.
//   - Copy insertion: when breaking a dependence, insert a MOV from the
//     original register to a scratch register.
//   - Hazard-aware scheduling: uses the HazardRecognizer to respect
//     forwarding paths and structural hazards.

/// A physical register with liveness tracking for post-RA scheduling.
#[derive(Debug, Clone)]
pub struct PostRAReg {
    /// The physical register number.
    pub reg: PhysReg,
    /// Whether this register is currently live (has a value).
    pub is_live: bool,
    /// The last instruction that defined this register.
    pub last_def: Option<NodeId>,
    /// Instructions that use this register (pending reads).
    pub pending_uses: Vec<NodeId>,
}

impl PostRAReg {
    pub fn new(reg: PhysReg) -> Self {
        Self {
            reg,
            is_live: false,
            last_def: None,
            pending_uses: Vec::new(),
        }
    }
}

/// Post-register-allocation scheduler.
#[derive(Debug, Clone)]
pub struct PostRAScheduler {
    /// The current schedule (node_id, issue_cycle).
    pub schedule: Vec<(NodeId, Cycle)>,
    /// Physical register tracking.
    pub reg_state: HashMap<PhysReg, PostRAReg>,
    /// List of free scratch registers for anti-dep breaking.
    pub scratch_regs: Vec<PhysReg>,
    /// Whether anti-dep breaking is enabled.
    pub break_anti_deps: bool,
    /// Whether copy insertion for output deps is enabled.
    pub break_output_deps: bool,
    /// Maximum number of copy insertions allowed.
    pub max_copies: usize,
    /// Number of copies inserted so far.
    pub copies_inserted: usize,
    /// Number of anti-dependences broken.
    pub anti_deps_broken: usize,
    /// The dependence graph.
    pub graph: Option<DependenceGraph>,
    /// Hazard recognizer.
    pub hazard: Option<HazardRecognizer>,
}

impl PostRAScheduler {
    /// Create a new post-RA scheduler.
    pub fn new() -> Self {
        Self {
            schedule: Vec::new(),
            reg_state: HashMap::new(),
            scratch_regs: Vec::new(),
            break_anti_deps: true,
            break_output_deps: false,
            max_copies: 16,
            copies_inserted: 0,
            anti_deps_broken: 0,
            graph: None,
            hazard: None,
        }
    }

    /// Set available scratch registers for anti-dep breaking.
    pub fn with_scratch_regs(mut self, regs: &[PhysReg]) -> Self {
        self.scratch_regs = regs.to_vec();
        self
    }

    /// Build register state from the instruction sequence.
    pub fn build_reg_state(&mut self, instrs: &[SchedInstr]) {
        self.reg_state.clear();

        for (i, instr) in instrs.iter().enumerate() {
            for d in &instr.defs {
                if let Reg::Phys(p) = d {
                    let entry = self
                        .reg_state
                        .entry(*p)
                        .or_insert_with(|| PostRAReg::new(*p));
                    entry.is_live = true;
                    entry.last_def = Some(i);
                    entry.pending_uses.clear();
                }
            }
            for u in &instr.uses {
                if let Reg::Phys(p) = u {
                    let entry = self
                        .reg_state
                        .entry(*p)
                        .or_insert_with(|| PostRAReg::new(*p));
                    entry.pending_uses.push(i);
                }
            }
        }
    }

    /// Check if an anti-dependence exists between two instructions.
    ///
    /// An anti-dep exists if instruction B defines a register that
    /// instruction A uses, and A is before B in the original order.
    pub fn has_anti_dep(&self, a: &DepNode, b: &DepNode) -> Option<PhysReg> {
        for d in &b.instr.defs {
            if let Reg::Phys(p) = d {
                if a.instr.uses.contains(&Reg::Phys(*p)) {
                    return Some(*p);
                }
            }
        }
        None
    }

    /// Check if an output dependence exists between two instructions.
    pub fn has_output_dep(&self, a: &DepNode, b: &DepNode) -> Option<PhysReg> {
        for d_a in &a.instr.defs {
            if let Reg::Phys(p_a) = d_a {
                for d_b in &b.instr.defs {
                    if let Reg::Phys(p_b) = d_b {
                        if p_a == p_b {
                            return Some(*p_a);
                        }
                    }
                }
            }
        }
        None
    }

    /// Attempt to break an anti-dependence by inserting a copy.
    ///
    /// If instruction B wants to move before instruction A, but B defines
    /// a register that A uses (anti-dep), we can:
    ///   1. Find a free scratch register.
    ///   2. Insert a copy: MOV scratch, conflicted_reg  (before B)
    ///   3. Rewrite A's use to scratch.
    ///
    /// Returns true if the dependence was successfully broken.
    pub fn break_anti_dep(&mut self, a_idx: NodeId, b_idx: NodeId, nodes: &mut [DepNode]) -> bool {
        if !self.break_anti_deps || self.copies_inserted >= self.max_copies {
            return false;
        }

        let conflict_reg = match self.has_anti_dep(&nodes[a_idx], &nodes[b_idx]) {
            Some(r) => r,
            None => return true, // No anti-dep to break.
        };

        // Find a free scratch register.
        let scratch = match self.scratch_regs.first().copied() {
            Some(r) => r,
            None => return false,
        };

        // Rewrite A's use of conflict_reg to scratch.
        for u in &mut nodes[a_idx].instr.uses {
            if *u == Reg::Phys(conflict_reg) {
                *u = Reg::Phys(scratch);
            }
        }

        // TODO: Insert a copy instruction (scratch = conflict_reg) before B.
        // This would be done in the actual instruction stream, but for the
        // dependence graph we've effectively broken the anti-dep.

        self.copies_inserted += 1;
        self.anti_deps_broken += 1;
        true
    }

    /// Run post-RA scheduling on a sequence of instructions.
    pub fn run(&mut self, instrs: &[SchedInstr]) -> Vec<SchedInstr> {
        if instrs.is_empty() {
            return Vec::new();
        }

        // Build register state.
        self.build_reg_state(instrs);

        // Build dependence graph.
        let mut dep_graph = DependenceGraph::new();
        dep_graph.include_anti_output = true;
        dep_graph.build(instrs);

        // Convert graph nodes to mutable for anti-dep breaking.
        let mut nodes = dep_graph.nodes.clone();

        // Attempt anti-dep breaking.
        if self.break_anti_deps {
            let n = instrs.len();
            for i in 0..n {
                for j in i + 1..n {
                    if self.break_anti_dep(i, j, &mut nodes) {
                        // Update dependence edges accordingly.
                    }
                }
            }
        }

        // Rebuild dependence graph with broken deps.
        let mut dep_graph2 = DependenceGraph::new();
        // Reconstruct instrs from nodes.
        let new_instrs: Vec<SchedInstr> = nodes[..nodes.len()]
            .iter()
            .map(|n| n.instr.clone())
            .collect();
        dep_graph2.include_anti_output = true;
        dep_graph2.build(&new_instrs);

        // Use list scheduler with the modified graph.
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dep_graph2.clone(), resource_model);
        let schedule = scheduler.run();

        // Reorder instructions.
        let reordered = scheduler.reorder_instructions(instrs);

        self.graph = Some(dep_graph2);
        self.schedule = schedule;

        reordered
    }

    /// Get statistics about the scheduling pass.
    pub fn stats(&self) -> PostRASchedStats {
        PostRASchedStats {
            copies_inserted: self.copies_inserted,
            anti_deps_broken: self.anti_deps_broken,
            nodes_scheduled: self.schedule.len(),
        }
    }
}

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

/// Statistics from post-RA scheduling.
#[derive(Debug, Clone, Copy)]
pub struct PostRASchedStats {
    pub copies_inserted: usize,
    pub anti_deps_broken: usize,
    pub nodes_scheduled: usize,
}

impl fmt::Display for PostRASchedStats {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "PostRASched: {} nodes, {} anti-deps broken, {} copies inserted",
            self.nodes_scheduled, self.anti_deps_broken, self.copies_inserted,
        )
    }
}

// ============================================================================
// RegLivenessAnalysis — Register liveness for post-RA scheduling
// ============================================================================
// Computes live-in and live-out sets for each instruction within a basic
// block. Used by the post-RA scheduler to determine when a physical
// register's value is dead (can be overwritten) and to find free scratch
// registers for anti-dep breaking.

/// Liveness information for a single instruction.
#[derive(Debug, Clone)]
pub struct InstrLiveness {
    /// Registers live before this instruction executes.
    pub live_in: HashSet<PhysReg>,
    /// Registers live after this instruction executes.
    pub live_out: HashSet<PhysReg>,
    /// Registers defined (killed) by this instruction.
    pub defs: HashSet<PhysReg>,
    /// Registers used (read) by this instruction.
    pub uses: HashSet<PhysReg>,
}

impl InstrLiveness {
    pub fn new() -> Self {
        Self {
            live_in: HashSet::new(),
            live_out: HashSet::new(),
            defs: HashSet::new(),
            uses: HashSet::new(),
        }
    }
}

/// Register liveness analysis for a basic block.
#[derive(Debug, Clone)]
pub struct RegLivenessAnalysis {
    /// Liveness for each instruction in the block.
    pub instr_liveness: Vec<InstrLiveness>,
    /// Live-out of the entire block.
    pub block_live_out: HashSet<PhysReg>,
    /// Live-in to the entire block.
    pub block_live_in: HashSet<PhysReg>,
}

impl RegLivenessAnalysis {
    /// Compute liveness for a sequence of instructions.
    ///
    /// Uses a backward dataflow analysis: starting from the block's
    /// live-out set, propagate backward through instructions.
    pub fn compute(instrs: &[SchedInstr], block_live_out: &HashSet<PhysReg>) -> Self {
        let n = instrs.len();
        let mut liveness: Vec<InstrLiveness> = Vec::with_capacity(n);

        // Extract def/use sets for each instruction.
        let mut def_sets: Vec<HashSet<PhysReg>> = Vec::with_capacity(n);
        let mut use_sets: Vec<HashSet<PhysReg>> = Vec::with_capacity(n);

        for instr in instrs {
            let mut defs = HashSet::new();
            let mut uses = HashSet::new();

            for d in &instr.defs {
                if let Reg::Phys(p) = d {
                    defs.insert(*p);
                }
            }
            for u in &instr.uses {
                if let Reg::Phys(p) = u {
                    uses.insert(*p);
                }
            }

            def_sets.push(defs);
            use_sets.push(uses);
            liveness.push(InstrLiveness::new());
        }

        // Backward pass.
        // LiveOut[n] = block_live_out
        // LiveOut[i] = (LiveOut[i+1] - Def[i]) ∪ Use[i]
        let mut live_out = block_live_out.clone();

        for i in (0..n).rev() {
            liveness[i].defs = def_sets[i].clone();
            liveness[i].uses = use_sets[i].clone();
            liveness[i].live_out = live_out.clone();

            // LiveIn = (LiveOut - Def) ∪ Use
            let mut live_in = live_out.clone();
            for d in &def_sets[i] {
                live_in.remove(d);
            }
            for u in &use_sets[i] {
                live_in.insert(*u);
            }
            liveness[i].live_in = live_in.clone();

            live_out = live_in;
        }

        Self {
            instr_liveness: liveness,
            block_live_out: block_live_out.clone(),
            block_live_in: live_out,
        }
    }

    /// Check if a physical register is dead after a given instruction.
    pub fn is_dead_after(&self, instr_idx: usize, reg: PhysReg) -> bool {
        if instr_idx + 1 < self.instr_liveness.len() {
            !self.instr_liveness[instr_idx + 1].live_in.contains(&reg)
        } else {
            !self.block_live_out.contains(&reg)
        }
    }

    /// Find a free physical register not live at a given point.
    pub fn find_free_reg(&self, instr_idx: usize, candidates: &[PhysReg]) -> Option<PhysReg> {
        let live = &self.instr_liveness[instr_idx].live_in;
        candidates.iter().find(|r| !live.contains(r)).copied()
    }

    /// Get the register pressure (number of live registers) at each point.
    pub fn pressure_profile(&self) -> Vec<usize> {
        self.instr_liveness
            .iter()
            .map(|l| l.live_in.len())
            .collect()
    }

    /// Maximum register pressure in the block.
    pub fn max_pressure(&self) -> usize {
        self.pressure_profile().into_iter().max().unwrap_or(0)
    }

    /// Average register pressure in the block.
    pub fn avg_pressure(&self) -> f64 {
        let profile = self.pressure_profile();
        if profile.is_empty() {
            return 0.0;
        }
        profile.iter().sum::<usize>() as f64 / profile.len() as f64
    }
}

// ============================================================================
// MacroFusion — Instruction fusion (CMP+JCC, DEC+JNZ, TEST+JCC)
// ============================================================================
// Macro-fusion combines adjacent instruction pairs into a single
// micro-op at decode time. Common x86 fusion patterns:
//   - CMP + JCC (compare and branch)
//   - TEST + JCC (test and branch)
//   - DEC/INC + JCC (decrement/increment and branch if not zero)
//   - ADD/SUB + JCC (arithmetic and branch)
//
// The fusion logic checks:
//   1. The two instructions are adjacent in the scheduled order.
//   2. The first instruction sets flags (CMP/TEST/DEC/INC/ADD/SUB).
//   3. The second instruction is a conditional branch that reads flags.
//   4. No other instruction reads the flags between them.

/// A fusion candidate pair.
#[derive(Debug, Clone)]
pub struct FusionCandidate {
    /// Index of the first instruction (flag-setting).
    pub first: usize,
    /// Index of the second instruction (branch).
    pub second: usize,
    /// The fusion pattern detected.
    pub pattern: FusionPattern,
    /// Whether this pair is eligible for fusion.
    pub eligible: bool,
    /// Reason if not eligible.
    pub reason: Option<String>,
}

/// Known macro-fusion patterns.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum FusionPattern {
    /// CMP + JCC (compare and conditional jump).
    CmpJcc,
    /// TEST + JCC (test and conditional jump).
    TestJcc,
    /// DEC + JNZ (decrement and jump if not zero).
    DecJnz,
    /// INC + JNZ (increment and jump if not zero).
    IncJnz,
    /// ADD + JCC (add and conditional jump).
    AddJcc,
    /// SUB + JCC (subtract and conditional jump).
    SubJcc,
    /// AND + JCC (bitwise AND and conditional jump).
    AndJcc,
    /// OR + JCC (bitwise OR and conditional jump).
    OrJcc,
    /// XOR + JCC (bitwise XOR and conditional jump).
    XorJcc,
}

impl FusionPattern {
    pub fn as_str(self) -> &'static str {
        match self {
            FusionPattern::CmpJcc => "CMP+JCC",
            FusionPattern::TestJcc => "TEST+JCC",
            FusionPattern::DecJnz => "DEC+JNZ",
            FusionPattern::IncJnz => "INC+JNZ",
            FusionPattern::AddJcc => "ADD+JCC",
            FusionPattern::SubJcc => "SUB+JCC",
            FusionPattern::AndJcc => "AND+JCC",
            FusionPattern::OrJcc => "OR+JCC",
            FusionPattern::XorJcc => "XOR+JCC",
        }
    }
}

/// Opcode categories used for fusion detection.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum OpCategory {
    /// Compare instruction (CMP).
    Cmp,
    /// Test instruction (TEST).
    Test,
    /// Decrement instruction (DEC).
    Dec,
    /// Increment instruction (INC).
    Inc,
    /// Add instruction (ADD).
    Add,
    /// Subtract instruction (SUB).
    Sub,
    /// Bitwise AND (AND).
    And,
    /// Bitwise OR (OR).
    Or,
    /// Bitwise XOR (XOR).
    Xor,
    /// Conditional jump (JCC).
    Jcc,
    /// Unconditional jump (JMP).
    Jmp,
    /// Other/unknown.
    Other,
}

/// The macro-fusion analyzer and transformer.
#[derive(Debug, Clone)]
pub struct MacroFusion {
    /// Known fusion patterns.
    pub patterns: Vec<FusionPattern>,
    /// Opcode ranges for each category.
    cmp_opcodes: HashSet<u32>,
    test_opcodes: HashSet<u32>,
    dec_opcodes: HashSet<u32>,
    inc_opcodes: HashSet<u32>,
    add_opcodes: HashSet<u32>,
    sub_opcodes: HashSet<u32>,
    and_opcodes: HashSet<u32>,
    or_opcodes: HashSet<u32>,
    xor_opcodes: HashSet<u32>,
    jcc_opcodes: HashSet<u32>,
    /// Whether fusion is enabled.
    pub enabled: bool,
    /// Number of fused pairs found.
    pub fused_count: usize,
}

impl MacroFusion {
    /// Create a new macro-fusion analyzer with default x86 opcodes.
    pub fn new() -> Self {
        let mut mf = Self {
            patterns: vec![
                FusionPattern::CmpJcc,
                FusionPattern::TestJcc,
                FusionPattern::DecJnz,
                FusionPattern::IncJnz,
                FusionPattern::AddJcc,
                FusionPattern::SubJcc,
                FusionPattern::AndJcc,
                FusionPattern::OrJcc,
            ],
            cmp_opcodes: HashSet::new(),
            test_opcodes: HashSet::new(),
            dec_opcodes: HashSet::new(),
            inc_opcodes: HashSet::new(),
            add_opcodes: HashSet::new(),
            sub_opcodes: HashSet::new(),
            and_opcodes: HashSet::new(),
            or_opcodes: HashSet::new(),
            xor_opcodes: HashSet::new(),
            jcc_opcodes: HashSet::new(),
            enabled: true,
            fused_count: 0,
        };

        // Populate with typical x86 opcode ranges (simplified).
        // In real LLVM, these come from target-specific .td files.
        mf.cmp_opcodes.insert(100); // CMP reg, reg
        mf.cmp_opcodes.insert(101); // CMP reg, imm
        mf.test_opcodes.insert(110); // TEST reg, reg
        mf.test_opcodes.insert(111); // TEST reg, imm
        mf.dec_opcodes.insert(120); // DEC reg
        mf.inc_opcodes.insert(121); // INC reg
        mf.add_opcodes.insert(130); // ADD reg, reg
        mf.sub_opcodes.insert(131); // SUB reg, reg
        mf.and_opcodes.insert(132); // AND reg, reg
        mf.or_opcodes.insert(133); // OR reg, reg
        mf.xor_opcodes.insert(134); // XOR reg, reg

        // Conditional branch opcodes (JCC family).
        for i in 200..216 {
            mf.jcc_opcodes.insert(i);
        }

        mf
    }

    /// Categorize an opcode.
    fn categorize(&self, opcode: u32) -> OpCategory {
        if self.cmp_opcodes.contains(&opcode) {
            OpCategory::Cmp
        } else if self.test_opcodes.contains(&opcode) {
            OpCategory::Test
        } else if self.dec_opcodes.contains(&opcode) {
            OpCategory::Dec
        } else if self.inc_opcodes.contains(&opcode) {
            OpCategory::Inc
        } else if self.add_opcodes.contains(&opcode) {
            OpCategory::Add
        } else if self.sub_opcodes.contains(&opcode) {
            OpCategory::Sub
        } else if self.and_opcodes.contains(&opcode) {
            OpCategory::And
        } else if self.or_opcodes.contains(&opcode) {
            OpCategory::Or
        } else if self.xor_opcodes.contains(&opcode) {
            OpCategory::Xor
        } else if self.jcc_opcodes.contains(&opcode) {
            OpCategory::Jcc
        } else {
            OpCategory::Other
        }
    }

    /// Determine the fusion pattern for an adjacent pair.
    fn detect_pattern(&self, first_opcode: u32, second_opcode: u32) -> Option<FusionPattern> {
        let cat1 = self.categorize(first_opcode);
        let cat2 = self.categorize(second_opcode);

        if cat2 != OpCategory::Jcc {
            return None;
        }

        match cat1 {
            OpCategory::Cmp => Some(FusionPattern::CmpJcc),
            OpCategory::Test => Some(FusionPattern::TestJcc),
            OpCategory::Dec => Some(FusionPattern::DecJnz),
            OpCategory::Inc => Some(FusionPattern::IncJnz),
            OpCategory::Add => Some(FusionPattern::AddJcc),
            OpCategory::Sub => Some(FusionPattern::SubJcc),
            OpCategory::And => Some(FusionPattern::AndJcc),
            OpCategory::Or => Some(FusionPattern::OrJcc),
            OpCategory::Xor => Some(FusionPattern::XorJcc),
            _ => None,
        }
    }

    /// Analyze an instruction stream for fusion opportunities.
    ///
    /// Scans adjacent pairs and checks eligibility:
    ///   1. Adjacent in the final order.
    ///   2. First sets flags, second is a conditional branch.
    ///   3. No flag clobbering between them.
    ///   4. Compatible with the target's fusion capabilities.
    pub fn analyze(&self, instrs: &[SchedInstr]) -> Vec<FusionCandidate> {
        let mut candidates = Vec::new();

        if instrs.len() < 2 {
            return candidates;
        }

        for i in 0..instrs.len() - 1 {
            let first = &instrs[i];
            let second = &instrs[i + 1];

            if let Some(pattern) = self.detect_pattern(first.opcode, second.opcode) {
                let mut candidate = FusionCandidate {
                    first: i,
                    second: i + 1,
                    pattern,
                    eligible: true,
                    reason: None,
                };

                // Check eligibility criteria.
                if !self.is_eligible(first, second, &pattern) {
                    candidate.eligible = false;
                    candidate.reason = Some(self.rejection_reason(first, second, &pattern));
                }

                candidates.push(candidate);
            }
        }

        candidates
    }

    /// Check if a pair is eligible for fusion.
    fn is_eligible(
        &self,
        first: &SchedInstr,
        second: &SchedInstr,
        pattern: &FusionPattern,
    ) -> bool {
        // 1. Both instructions must be in the same basic block (guaranteed
        //    since we scan within a block).

        // 2. The branch destination must be a label (not an indirect jump).
        if second
            .operands
            .iter()
            .any(|op| matches!(op, SchedOperand::Label(_)))
        {
            // Direct branch: OK for fusion.
        } else {
            // Indirect branch: not fusible in most architectures.
            // (This is a simplification; real criteria are more complex.)
        }

        // 3. First instruction must not have side effects beyond flag-setting.
        if first.has_side_effects
            && !matches!(pattern, FusionPattern::CmpJcc | FusionPattern::TestJcc)
        {
            return false;
        }

        // 4. The branch must not be the target of another jump (simplified
        //    check: the branch is the last use of flags from the first inst).

        // 5. Both instructions must be fusible according to the target's
        //    macro-fusion capabilities.
        if !self.patterns.contains(pattern) {
            return false;
        }

        true
    }

    /// Reason why a pair was rejected.
    fn rejection_reason(
        &self,
        _first: &SchedInstr,
        _second: &SchedInstr,
        _pattern: &FusionPattern,
    ) -> String {
        "not eligible for fusion".to_string()
    }

    /// Perform fusion: mark eligible adjacent pairs as fused.
    ///
    /// Returns the number of fused pairs.
    pub fn fuse(&mut self, instrs: &mut Vec<SchedInstr>) -> usize {
        if !self.enabled {
            return 0;
        }

        let candidates = self.analyze(instrs);
        let mut fused = 0;

        // Process candidates from back to front to avoid index shifting.
        for candidate in candidates.iter().rev() {
            if candidate.eligible {
                // Mark as fused (in a real implementation, we'd combine
                // them into a single macro-op). Here we just mark them.
                instrs[candidate.first].is_parallel = true;
                fused += 1;
            }
        }

        self.fused_count += fused;
        fused
    }

    /// Check if a specific pattern is supported.
    pub fn supports_pattern(&self, pattern: FusionPattern) -> bool {
        self.patterns.contains(&pattern)
    }

    /// Add support for a fusion pattern.
    pub fn add_pattern(&mut self, pattern: FusionPattern) {
        if !self.patterns.contains(&pattern) {
            self.patterns.push(pattern);
        }
    }

    /// Remove support for a fusion pattern.
    pub fn remove_pattern(&mut self, pattern: FusionPattern) {
        self.patterns.retain(|p| *p != pattern);
    }

    /// Summary of the fusion analysis.
    pub fn summary(&self) -> String {
        format!(
            "MacroFusion: {} patterns supported, {} pairs fused",
            self.patterns.len(),
            self.fused_count,
        )
    }
}

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

// ============================================================================
// FusionEligibility — Detailed fusion eligibility rules
// ============================================================================
// Models target-specific constraints on which instruction pairs can be
// fused. Different microarchitectures support different fusion patterns.

/// Detailed eligibility rules for a fusion pattern.
#[derive(Debug, Clone)]
pub struct FusionEligibility {
    /// The pattern being checked.
    pub pattern: FusionPattern,
    /// Whether the first instruction must be a flag-setting instruction.
    pub requires_flag_setting: bool,
    /// Whether the branch must be the sole consumer of the flags.
    pub requires_single_consumer: bool,
    /// Maximum displacement from the branch to the target.
    pub max_branch_displacement: Option<i64>,
    /// Whether the branch must be a forward branch.
    pub requires_forward_branch: bool,
    /// Whether the pair must be in the same decode group.
    pub requires_same_decode_group: bool,
    /// Minimum alignment for the fused pair.
    pub alignment: u32,
    /// Whether the first instruction can be a memory operand.
    pub allows_memory_operand: bool,
    /// Whether both instructions can be memory operands.
    pub allows_both_memory: bool,
}

impl FusionEligibility {
    /// Default rules for CMP+JCC fusion (most permissive).
    pub fn cmp_jcc() -> Self {
        Self {
            pattern: FusionPattern::CmpJcc,
            requires_flag_setting: true,
            requires_single_consumer: true,
            max_branch_displacement: None,
            requires_forward_branch: false,
            requires_same_decode_group: true,
            alignment: 16,
            allows_memory_operand: true,
            allows_both_memory: false,
        }
    }

    /// Rules for TEST+JCC fusion.
    pub fn test_jcc() -> Self {
        Self {
            pattern: FusionPattern::TestJcc,
            requires_flag_setting: true,
            requires_single_consumer: true,
            max_branch_displacement: None,
            requires_forward_branch: false,
            requires_same_decode_group: true,
            alignment: 16,
            allows_memory_operand: true,
            allows_both_memory: false,
        }
    }

    /// Rules for DEC+JNZ fusion (loop counter).
    pub fn dec_jnz() -> Self {
        Self {
            pattern: FusionPattern::DecJnz,
            requires_flag_setting: true,
            requires_single_consumer: true,
            max_branch_displacement: Some(128),
            requires_forward_branch: false,
            requires_same_decode_group: true,
            alignment: 16,
            allows_memory_operand: false,
            allows_both_memory: false,
        }
    }

    /// Check if a given instruction pair satisfies these eligibility rules.
    pub fn check(&self, first: &SchedInstr, second: &SchedInstr) -> Result<(), String> {
        if self.requires_flag_setting && first.defs.is_empty() {
            return Err("First instruction must set flags".to_string());
        }
        if self.requires_same_decode_group {
            // For simplicity, adjacent instructions are in the same decode group.
            // In a real implementation, check alignment and instruction length.
        }
        if !self.allows_memory_operand && (first.may_load || first.may_store) {
            return Err("Memory operand not allowed for first instruction".to_string());
        }
        if !self.allows_both_memory && first.may_load && second.may_load {
            return Err("Both memory operands not allowed".to_string());
        }
        Ok(())
    }
}

/// Micro-op fusion: combine adjacent micro-ops within the same instruction.
#[derive(Debug, Clone)]
pub struct MicroOpFusion {
    /// Whether micro-op fusion is enabled.
    pub enabled: bool,
    /// Supported micro-op fusion patterns: (uop1_unit, uop2_unit) → fused_unit.
    pub fusion_table: HashMap<(FuncUnitKind, FuncUnitKind), FuncUnitKind>,
    /// Number of micro-op pairs fused.
    pub fused_count: usize,
}

impl MicroOpFusion {
    /// Create a new micro-op fusion analyzer.
    pub fn new() -> Self {
        let mut fusion_table = HashMap::new();
        // Common micro-op fusion patterns:
        // ALU + Branch → fused ALU/Branch
        fusion_table.insert((FuncUnitKind::ALU, FuncUnitKind::Branch), FuncUnitKind::ALU);
        // Load + ALU (address generation + operation)
        fusion_table.insert((FuncUnitKind::Load, FuncUnitKind::ALU), FuncUnitKind::Load);

        Self {
            enabled: true,
            fusion_table,
            fused_count: 0,
        }
    }

    /// Try to fuse two micro-ops.
    pub fn try_fuse(&self, uop1: &MicroOp, uop2: &MicroOp) -> Option<MicroOp> {
        if !self.enabled {
            return None;
        }
        if let Some(fused_unit) = self.fusion_table.get(&(uop1.unit, uop2.unit)) {
            let mut fused = MicroOp::new(*fused_unit, uop1.latency.max(uop2.latency));
            fused
                .defs
                .extend(uop1.defs.iter().chain(uop2.defs.iter()).cloned());
            fused
                .uses
                .extend(uop1.uses.iter().chain(uop2.uses.iter()).cloned());
            Some(fused)
        } else {
            None
        }
    }

    /// Fuse micro-ops within a decomposition.
    pub fn fuse_decomposition(&mut self, decomp: &MicroOpDecomposition) -> MicroOpDecomposition {
        let mut fused_uops = Vec::new();
        let uops = &decomp.uops;
        let mut i = 0;

        while i < uops.len() {
            if i + 1 < uops.len() {
                if let Some(fused) = self.try_fuse(&uops[i], &uops[i + 1]) {
                    fused_uops.push(fused);
                    self.fused_count += 1;
                    i += 2;
                    continue;
                }
            }
            fused_uops.push(uops[i].clone());
            i += 1;
        }

        MicroOpDecomposition::new(decomp.opcode, fused_uops)
    }
}

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

// ============================================================================
// Scheduling Pipeline — Orchestrates all scheduling passes
// ============================================================================
// Top-level scheduler that runs the full deep scheduling pipeline:
//   1. Build dependence graph
//   2. Compute ScheduleDAG (ASAP/ALAP/mobility)
//   3. Run list scheduling
//   4. Run post-RA scheduling (if applicable)
//   5. Run macro-fusion detection
//
// This orchestrator provides a single entry point for the compiler.

/// Configuration for the deep scheduling pipeline.
#[derive(Debug, Clone)]
pub struct DeepSchedConfig {
    /// Priority heuristic for list scheduling.
    pub priority: SchedPriority,
    /// Whether resource-aware scheduling is enabled.
    pub resource_aware: bool,
    /// Whether hazard recognition is enabled.
    pub hazard_aware: bool,
    /// Whether anti-dep breaking is enabled.
    pub break_anti_deps: bool,
    /// Whether macro-fusion is enabled.
    pub macro_fusion: bool,
    /// Whether this is pre-RA or post-RA scheduling.
    pub post_ra: bool,
    /// Issue width of the target.
    pub issue_width: u32,
    /// Verbose output.
    pub verbose: bool,
}

impl Default for DeepSchedConfig {
    fn default() -> Self {
        Self {
            priority: SchedPriority::CriticalPath,
            resource_aware: true,
            hazard_aware: true,
            break_anti_deps: true,
            macro_fusion: true,
            post_ra: false,
            issue_width: 4,
            verbose: false,
        }
    }
}

/// The deep scheduling pipeline orchestrator.
#[derive(Debug, Clone)]
pub struct DeepScheduler {
    /// Configuration.
    pub config: DeepSchedConfig,
    /// The dependence graph.
    pub dep_graph: Option<DependenceGraph>,
    /// The schedule DAG analysis.
    pub sched_dag: Option<ScheduleDAG>,
    /// The list scheduler.
    pub list_scheduler: Option<ListScheduler>,
    /// The post-RA scheduler.
    pub post_ra_scheduler: Option<PostRAScheduler>,
    /// The macro-fusion analyzer.
    pub macro_fusion: Option<MacroFusion>,
    /// Statistics.
    pub stats: DeepSchedStats,
}

/// Statistics from the deep scheduling pipeline.
#[derive(Debug, Clone, Default)]
pub struct DeepSchedStats {
    /// Number of instructions scheduled.
    pub num_instrs: usize,
    /// Number of true dependences found.
    pub true_deps: usize,
    /// Number of anti dependences found.
    pub anti_deps: usize,
    /// Number of output dependences found.
    pub output_deps: usize,
    /// Critical path length.
    pub critical_path: Cycle,
    /// Schedule length in cycles.
    pub schedule_length: Cycle,
    /// Number of fused pairs.
    pub fused_pairs: usize,
    /// Number of anti-deps broken.
    pub anti_deps_broken: usize,
    /// Whether scheduling succeeded.
    pub success: bool,
}

impl DeepScheduler {
    /// Create a new deep scheduler with the given configuration.
    pub fn new(config: DeepSchedConfig) -> Self {
        Self {
            config,
            dep_graph: None,
            sched_dag: None,
            list_scheduler: None,
            post_ra_scheduler: None,
            macro_fusion: None,
            stats: DeepSchedStats::default(),
        }
    }

    /// Run the full deep scheduling pipeline on a sequence of instructions.
    pub fn run(&mut self, instrs: &[SchedInstr]) -> Vec<SchedInstr> {
        self.stats = DeepSchedStats::default();
        self.stats.num_instrs = instrs.len();

        if instrs.is_empty() {
            self.stats.success = true;
            return Vec::new();
        }

        // Step 1: Build dependence graph.
        let mut dep_graph = DependenceGraph::new();
        dep_graph.build(instrs);

        self.stats.true_deps = dep_graph.count_edges(DepKind::True);
        self.stats.anti_deps = dep_graph.count_edges(DepKind::Anti);
        self.stats.output_deps = dep_graph.count_edges(DepKind::Output);

        if self.config.verbose {
            eprintln!("[DeepSched] Built dependence graph:");
            eprintln!(
                "  {} nodes, {} true, {} anti, {} output edges",
                dep_graph.num_instrs,
                self.stats.true_deps,
                self.stats.anti_deps,
                self.stats.output_deps,
            );
        }

        // Step 2: Compute ScheduleDAG.
        let sched_dag = ScheduleDAG::new(dep_graph.clone());
        self.stats.critical_path = sched_dag.critical_path_length;

        if self.config.verbose {
            eprintln!(
                "[DeepSched] ScheduleDAG: critical path = {}",
                self.stats.critical_path
            );
        }

        // Step 3: Run list scheduling.
        let resource_model = if self.config.resource_aware {
            let mut rm = ResourceModel::default_model();
            rm.issue_width = self.config.issue_width;
            rm
        } else {
            ResourceModel::default_model()
        };

        let mut list_scheduler = ListScheduler::new(dep_graph.clone(), resource_model);
        list_scheduler.priority_heuristic = self.config.priority;
        list_scheduler.resource_aware = self.config.resource_aware;

        let _schedule = list_scheduler.run();
        self.stats.schedule_length = list_scheduler.schedule_length();
        let mut reordered = list_scheduler.reorder_instructions(instrs);

        if self.config.verbose {
            eprintln!(
                "[DeepSched] List scheduling complete: {} cycles",
                self.stats.schedule_length
            );
        }

        // Step 4: Post-RA scheduling (if configured).
        if self.config.post_ra {
            let mut post_ra = PostRAScheduler::new();
            post_ra.break_anti_deps = self.config.break_anti_deps;

            // Provide some scratch registers for anti-dep breaking.
            let scratch_regs: Vec<PhysReg> = (32..40).collect(); // R8-R15 as scratch
            post_ra = post_ra.with_scratch_regs(&scratch_regs);

            reordered = post_ra.run(&reordered);

            let ps = post_ra.stats();
            self.stats.anti_deps_broken = ps.anti_deps_broken;
            self.post_ra_scheduler = Some(post_ra);
        }

        // Step 5: Macro-fusion detection.
        if self.config.macro_fusion {
            let mut fusion = MacroFusion::new();
            self.stats.fused_pairs = fusion.fuse(&mut reordered);
            self.macro_fusion = Some(fusion);
        }

        // Store state.
        self.dep_graph = Some(dep_graph);
        self.sched_dag = Some(sched_dag);
        self.list_scheduler = Some(list_scheduler);

        self.stats.success = true;
        reordered
    }

    /// Run with default configuration.
    pub fn run_default(instrs: &[SchedInstr]) -> Vec<SchedInstr> {
        let mut sched = Self::new(DeepSchedConfig::default());
        sched.run(instrs)
    }

    /// Run pre-RA scheduling (virtual registers).
    pub fn run_pre_ra(instrs: &[SchedInstr]) -> Vec<SchedInstr> {
        let config = DeepSchedConfig {
            post_ra: false,
            break_anti_deps: false,
            ..DeepSchedConfig::default()
        };
        let mut sched = Self::new(config);
        sched.run(instrs)
    }

    /// Run post-RA scheduling (physical registers).
    pub fn run_post_ra(instrs: &[SchedInstr]) -> Vec<SchedInstr> {
        let config = DeepSchedConfig {
            post_ra: true,
            break_anti_deps: true,
            macro_fusion: true,
            ..DeepSchedConfig::default()
        };
        let mut sched = Self::new(config);
        sched.run(instrs)
    }

    /// Print a summary of the entire pipeline.
    pub fn display_summary(&self) -> String {
        let mut s = String::new();
        s.push_str("=== Deep Scheduling Pipeline Summary ===\n");
        s.push_str(&format!("  Instructions: {}\n", self.stats.num_instrs));
        s.push_str(&format!(
            "  Dependences: {} true, {} anti, {} output\n",
            self.stats.true_deps, self.stats.anti_deps, self.stats.output_deps,
        ));
        s.push_str(&format!(
            "  Critical path: {} cycles\n",
            self.stats.critical_path
        ));
        s.push_str(&format!(
            "  Schedule length: {} cycles\n",
            self.stats.schedule_length
        ));
        s.push_str(&format!("  Fused pairs: {}\n", self.stats.fused_pairs));
        s.push_str(&format!(
            "  Anti-deps broken: {}\n",
            self.stats.anti_deps_broken
        ));
        s.push_str(&format!("  Success: {}\n", self.stats.success));
        s
    }
}

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

// ============================================================================
// SchedulingRegion — Group of instructions scheduled together
// ============================================================================
// A scheduling region is a sequence of instructions within a basic block
// that are scheduled as a unit. Region boundaries are typically at
// barriers (branches, calls) that prevent reordering across them.

/// A scheduling region: a contiguous range of instructions.
#[derive(Debug, Clone)]
pub struct SchedulingRegion {
    /// Start index in the original instruction stream.
    pub start: usize,
    /// End index (exclusive) in the original instruction stream.
    pub end: usize,
    /// Number of instructions in this region.
    pub size: usize,
    /// Whether this region ends with a branch.
    pub ends_with_branch: bool,
    /// Whether this region contains a call.
    pub contains_call: bool,
}

impl SchedulingRegion {
    pub fn new(start: usize, end: usize) -> Self {
        Self {
            start,
            end,
            size: end.saturating_sub(start),
            ends_with_branch: false,
            contains_call: false,
        }
    }

    /// Split a sequence of instructions into scheduling regions.
    ///
    /// Region boundaries are at:
    ///   - Start and end of the sequence
    ///   - Branch instructions (end of region)
    ///   - Call instructions (boundary before and after)
    ///   - Label targets (start of new region)
    pub fn partition(instrs: &[SchedInstr]) -> Vec<Self> {
        if instrs.is_empty() {
            return Vec::new();
        }

        let mut regions = Vec::new();
        let mut region_start = 0usize;

        for i in 0..instrs.len() {
            let is_barrier = instrs[i].is_branch || instrs[i].is_call || instrs[i].has_side_effects;

            if is_barrier && i > region_start {
                // End current region before the barrier.
                let mut region = Self::new(region_start, i);
                region.ends_with_branch = instrs[i].is_branch;
                region.contains_call = instrs[i].is_call;
                regions.push(region);

                // Start new region at the barrier.
                region_start = i;
            }

            // Always start a new region after a branch.
            if instrs[i].is_branch && i + 1 < instrs.len() {
                let mut region = Self::new(region_start, i + 1);
                region.ends_with_branch = true;
                regions.push(region);
                region_start = i + 1;
            }
        }

        // Final region.
        if region_start < instrs.len() {
            let region = Self::new(region_start, instrs.len());
            regions.push(region);
        }

        regions
    }

    /// Extract the instructions in this region from a slice.
    pub fn extract<'a>(&self, instrs: &'a [SchedInstr]) -> &'a [SchedInstr] {
        &instrs[self.start..self.end.min(instrs.len())]
    }
}

// ============================================================================
// ScheduleVerifier — Verify that a schedule respects all dependences
// ============================================================================
// After scheduling, the verifier checks that:
//   1. Every instruction is scheduled exactly once.
//   2. Dependences are satisfied: a consumer starts after its producer
//      finishes plus the minimum latency.
//   3. Resource constraints are not violated (no more ops on a unit
//      than available instances).
//   4. No cycles exist in the final schedule.

/// Result of schedule verification.
#[derive(Debug, Clone)]
pub struct VerificationResult {
    /// Whether the schedule is valid.
    pub valid: bool,
    /// List of violations found.
    pub violations: Vec<String>,
    /// Number of dependence edges checked.
    pub edges_checked: usize,
    /// Number of resource constraints checked.
    pub resources_checked: usize,
}

impl VerificationResult {
    pub fn success() -> Self {
        Self {
            valid: true,
            violations: Vec::new(),
            edges_checked: 0,
            resources_checked: 0,
        }
    }

    pub fn with_violation(msg: String) -> Self {
        Self {
            valid: false,
            violations: vec![msg],
            edges_checked: 0,
            resources_checked: 0,
        }
    }
}

/// Verifier for scheduled instruction sequences.
#[derive(Debug, Clone)]
pub struct ScheduleVerifier {
    /// The dependence graph used for scheduling.
    pub graph: DependenceGraph,
    /// The resource model.
    pub resource_model: ResourceModel,
    /// The schedule to verify: node_id → issue_cycle.
    pub schedule: HashMap<NodeId, Cycle>,
}

impl ScheduleVerifier {
    /// Create a new verifier.
    pub fn new(
        graph: DependenceGraph,
        resource_model: ResourceModel,
        schedule: HashMap<NodeId, Cycle>,
    ) -> Self {
        Self {
            graph,
            resource_model,
            schedule,
        }
    }

    /// Run all verification checks.
    pub fn verify(&self) -> VerificationResult {
        let mut result = VerificationResult::success();

        self.verify_completeness(&mut result);
        self.verify_dependences(&mut result);
        self.verify_resources(&mut result);

        result
    }

    /// Check that every real instruction is scheduled exactly once.
    fn verify_completeness(&self, result: &mut VerificationResult) {
        let n = self.graph.num_instrs;
        let mut scheduled_set: HashSet<NodeId> = HashSet::new();

        for (&node_id, _) in &self.schedule {
            if node_id >= n {
                continue; // Skip sentinels.
            }
            if !scheduled_set.insert(node_id) {
                result
                    .violations
                    .push(format!("Node {} scheduled more than once", node_id));
                result.valid = false;
            }
        }

        for i in 0..n {
            if !scheduled_set.contains(&i) {
                result.violations.push(format!("Node {} not scheduled", i));
                result.valid = false;
            }
        }
    }

    /// Check that all dependence edges are satisfied.
    fn verify_dependences(&self, result: &mut VerificationResult) {
        for node in &self.graph.nodes {
            for edge in &node.succs {
                result.edges_checked += 1;

                let from_cycle = match self.schedule.get(&edge.from) {
                    Some(&c) => c,
                    None => continue, // Sentinel or not scheduled.
                };
                let to_cycle = match self.schedule.get(&edge.to) {
                    Some(&c) => c,
                    None => continue,
                };

                let from_latency = self.graph.nodes[edge.from].latency() as u64;
                let min_separation = from_latency + edge.min_latency as u64;
                let actual_separation = if to_cycle >= from_cycle {
                    to_cycle - from_cycle
                } else {
                    // Negative: to is before from — violation.
                    result.violations.push(format!(
                        "Edge {}→{} ({:?}): consumer at cycle {} before producer at cycle {}",
                        edge.from, edge.to, edge.kind, to_cycle, from_cycle
                    ));
                    result.valid = false;
                    continue;
                };

                if actual_separation < min_separation && edge.kind == DepKind::True {
                    result.violations.push(format!(
                        "Edge {}→{} ({:?}): separation {} < required {} (producer latency={})",
                        edge.from,
                        edge.to,
                        edge.kind,
                        actual_separation,
                        min_separation,
                        from_latency
                    ));
                    result.valid = false;
                }
            }
        }
    }

    /// Check resource constraints per cycle.
    fn verify_resources(&self, result: &mut VerificationResult) {
        // Build a per-cycle map of resource usage.
        let mut cycle_usage: BTreeMap<Cycle, HashMap<FuncUnitKind, u32>> = BTreeMap::new();

        for (&node_id, &cycle) in &self.schedule {
            if node_id >= self.graph.num_instrs {
                continue;
            }
            let opcode = self.graph.nodes[node_id].opcode();
            let unit = self.resource_model.get_unit_kind(opcode);

            let entry = cycle_usage.entry(cycle).or_insert_with(HashMap::new);
            *entry.entry(unit).or_insert(0) += 1;
        }

        for (cycle, usage) in &cycle_usage {
            result.resources_checked += 1;

            // Check issue width.
            let total_issued: u32 = usage.values().sum();
            if total_issued > self.resource_model.issue_width {
                result.violations.push(format!(
                    "Cycle {}: {} instructions issued (issue width = {})",
                    cycle, total_issued, self.resource_model.issue_width
                ));
                result.valid = false;
            }

            // Check per-unit constraints.
            for (unit, count) in usage {
                let available = self.resource_model.get_unit_count(*unit);
                if *count > available {
                    result.violations.push(format!(
                        "Cycle {}: {} ops on unit {:?} (available: {})",
                        cycle, count, unit, available
                    ));
                    result.valid = false;
                }
            }
        }
    }
}

// ============================================================================
// Test Helpers
// ============================================================================

/// Create a simple ALU instruction.
fn alu_instr(idx: usize, opcode: u32, def_reg: Option<Reg>, use_regs: &[Reg]) -> SchedInstr {
    let mut instr = SchedInstr::new(idx, opcode).with_latency(1);
    if let Some(def) = def_reg {
        instr = instr.def(def);
    }
    for u in use_regs {
        instr = instr.use_reg(*u);
    }
    instr
}

/// Create a load instruction.
fn load_instr(idx: usize, def_reg: Reg, base_reg: Reg) -> SchedInstr {
    SchedInstr::new(idx, 2)
        .with_latency(3)
        .def(def_reg)
        .use_reg(base_reg)
        .load()
}

/// Create a store instruction.
fn store_instr(idx: usize, src_reg: Reg, base_reg: Reg) -> SchedInstr {
    SchedInstr::new(idx, 3)
        .with_latency(1)
        .use_reg(src_reg)
        .use_reg(base_reg)
        .store()
}

/// Create a branch instruction.
fn branch_instr(idx: usize) -> SchedInstr {
    SchedInstr::new(idx, 7).with_latency(1).branch()
}

/// Create an FP add instruction.
fn fp_add_instr(idx: usize, def_reg: Reg, use1: Reg, use2: Reg) -> SchedInstr {
    SchedInstr::new(idx, 4)
        .with_latency(5)
        .def(def_reg)
        .use_reg(use1)
        .use_reg(use2)
}

/// Create an FP multiply instruction.
fn fp_mul_instr(idx: usize, def_reg: Reg, use1: Reg, use2: Reg) -> SchedInstr {
    SchedInstr::new(idx, 5)
        .with_latency(7)
        .def(def_reg)
        .use_reg(use1)
        .use_reg(use2)
}

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

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

    // ------------------------------------------------------------------------
    // DependenceGraph Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_dep_graph_empty() {
        let mut dg = DependenceGraph::new();
        let instrs: Vec<SchedInstr> = Vec::new();
        dg.build(&instrs);
        assert!(dg.nodes.is_empty());
        assert_eq!(dg.num_instrs, 0);
    }

    #[test]
    fn test_dep_graph_true_dep() {
        // r0 = op1(r1)   N0: def r0, use r1
        // r2 = op2(r0)   N1: def r2, use r0  → true dep N0 → N1 on r0
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[r1]),
            alu_instr(1, 1, Some(r2), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        let true_edges = dg.true_deps();
        assert!(!true_edges.is_empty(), "Should have at least one true dep");
        assert_eq!(true_edges[0].from, 0);
        assert_eq!(true_edges[0].to, 1);
        assert_eq!(true_edges[0].reg, Some(r0));
    }

    #[test]
    fn test_dep_graph_anti_dep() {
        // r0 = op1(r1)   N0: def r0, use r1
        // r1 = op2(r0)   N1: def r1, use r0  → anti dep N0 → N1 on r1
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[r1]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        let anti_edges = dg.anti_deps();
        assert!(!anti_edges.is_empty(), "Should have anti dep on r1");
        assert_eq!(anti_edges[0].kind, DepKind::Anti);
    }

    #[test]
    fn test_dep_graph_output_dep() {
        // r0 = op1(r1)   N0: def r0
        // r0 = op2(r2)   N1: def r0  → output dep N0 → N1 on r0
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[r1]),
            alu_instr(1, 1, Some(r0), &[r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        let output_edges = dg.output_deps();
        assert!(!output_edges.is_empty(), "Should have output dep on r0");
        assert_eq!(output_edges[0].from, 0);
        assert_eq!(output_edges[0].to, 1);
    }

    #[test]
    fn test_dep_graph_memory_dep() {
        // store [r0], r1   N0: store
        // r2 = load [r0]  N1: load  → memory dep N0 → N1
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![store_instr(0, r1, r0), load_instr(1, r2, r0)];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        let mem_edges = dg.count_edges(DepKind::Memory);
        assert!(mem_edges > 0, "Should have memory-ordering edges");
    }

    #[test]
    fn test_dep_graph_no_cycle() {
        // Build a simple linear chain: should be acyclic.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        assert!(!dg.has_cycle(), "Dependence graph should be acyclic");
    }

    #[test]
    fn test_dep_graph_no_cycle_diamond() {
        // Diamond pattern: N0 → N1, N0 → N2, N1 → N3, N2 → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r1, r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        assert!(!dg.has_cycle(), "Diamond graph should be acyclic");
    }

    #[test]
    fn test_dep_graph_transitive_succs() {
        // Chain: N0 → N1 → N2
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        let succs = dg.transitive_succs(0);
        assert!(succs.contains(&1), "N1 should be reachable from N0");
        assert!(succs.contains(&2), "N2 should be reachable from N0");
    }

    // ------------------------------------------------------------------------
    // ScheduleDAG Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_sched_dag_asap_simple() {
        // Two independent chains:
        // N0 → N2
        // N1 → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        // N0 and N1 should have ASAP = 0 (start immediately).
        assert_eq!(dag.asap(0), 0);
        assert_eq!(dag.asap(1), 0);
        // N2 and N3 should have ASAP = 1 (after N0/N1 finish).
        assert_eq!(dag.asap(2), 1);
        assert_eq!(dag.asap(3), 1);
    }

    #[test]
    fn test_sched_dag_alap_simple() {
        // Two chains: N0 → N2, N1 → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        // Nodes 2 and 3 must finish by the critical path length.
        let cpl = dag.critical_path_length;
        assert!(cpl >= 1, "Critical path length should be at least 1");

        // ALAP of leaf nodes should equal critical path length (adjusted).
        assert!(dag.alap(2) <= cpl);
        assert!(dag.alap(3) <= cpl);
    }

    #[test]
    fn test_sched_dag_mobility() {
        // N0 (critical) → N2
        // N1 (independent) → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),   // part of critical chain
            alu_instr(1, 1, Some(r1), &[]),   // independent
            alu_instr(2, 1, Some(r2), &[r0]), // on critical chain
            alu_instr(3, 1, Some(r3), &[r1]), // independent
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        // Check that at least some nodes have measurable mobility.
        let mobilities: Vec<u64> = (0..4).map(|i| dag.mobility(i)).collect();
        // There should be at least one node with non-zero mobility
        // (the independent N1 or N3).
        assert!(
            mobilities.iter().any(|&m| m > 0),
            "Should have nodes with non-zero mobility"
        );
    }

    #[test]
    fn test_sched_dag_critical_path_nodes() {
        // Chain: N0 → N1 → N2 → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
            alu_instr(3, 1, Some(r3), &[r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        let critical = dag.critical_path_nodes();
        // All nodes should be on the critical path since it's a single chain.
        assert_eq!(critical.len(), 4, "All nodes on single chain are critical");
    }

    #[test]
    fn test_sched_dag_topological_order() {
        // Chain: N0 → N1 → N2
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        // Topological order should respect dependences: N0 before N1 before N2.
        let pos0 = dag.topo_order.iter().position(|&n| n == 0).unwrap();
        let pos1 = dag.topo_order.iter().position(|&n| n == 1).unwrap();
        let pos2 = dag.topo_order.iter().position(|&n| n == 2).unwrap();
        assert!(pos0 < pos1, "N0 should come before N1 in topo order");
        assert!(pos1 < pos2, "N1 should come before N2 in topo order");
    }

    // ------------------------------------------------------------------------
    // ListScheduler Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_list_scheduler_simple_chain() {
        // r0 = op(); r1 = op(r0); r2 = op(r1)
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, resource_model);
        let schedule = scheduler.run();

        // Chain must be at least 3 cycles (one per instruction due to true deps).
        assert!(
            scheduler.schedule_length() >= 2,
            "Chain should take at least 2+ cycles"
        );
        // All 3 instructions should be scheduled.
        assert_eq!(schedule.len(), 3, "All instructions should be scheduled");
    }

    #[test]
    fn test_list_scheduler_parallel() {
        // Two independent instructions: can issue in same cycle.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, resource_model);
        let schedule = scheduler.run();

        // Both independent ALU ops should fit in <= 2 cycles (likely 1 with issue width 4).
        assert!(
            scheduler.schedule_length() <= 2,
            "Parallel ops should schedule compactly"
        );
        assert_eq!(schedule.len(), 2);
    }

    #[test]
    fn test_list_scheduler_load_latency() {
        // r0 = load [rbase]  (latency 3)
        // r1 = op(r0)        (depends on load result)
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let rbase = Reg::Virt(100);

        let instrs = vec![load_instr(0, r0, rbase), alu_instr(1, 1, Some(r1), &[r0])];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, resource_model);
        let schedule = scheduler.run();

        // The load takes 3 cycles, so the dependent ALU must wait.
        // Look at the issue cycles.
        assert_eq!(schedule.len(), 2);
        let load_cycle = schedule
            .iter()
            .find(|&&(n, _)| n == 0)
            .map(|&(_, c)| c)
            .unwrap();
        let alu_cycle = schedule
            .iter()
            .find(|&&(n, _)| n == 1)
            .map(|&(_, c)| c)
            .unwrap();
        assert!(
            alu_cycle >= load_cycle + 3,
            "ALU after load must wait for load latency ({} >= {})",
            alu_cycle,
            load_cycle + 3
        );
    }

    #[test]
    fn test_list_scheduler_reorder() {
        // Two independent chains interleaved:
        // N0: r0 = op()
        // N1: r1 = op()
        // N2: r2 = op(r0)   depends on N0
        // N3: r3 = op(r1)   depends on N1
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, resource_model);
        scheduler.run();

        let reordered = scheduler.reorder_instructions(&instrs);
        assert_eq!(reordered.len(), 4, "All instructions should be present");
        // Dependences must be preserved: N0 before N2, N1 before N3.
    }

    #[test]
    fn test_list_scheduler_priority_critical_path() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        // Long chain (critical): N0 → N2 → N3
        // Short path: N1 (independent)
        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let resource_model = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, resource_model);
        scheduler.priority_heuristic = SchedPriority::CriticalPath;
        scheduler.run();

        // Critical path nodes (N0,N2,N3) should be scheduled early.
        // N0 should be in cycle 0.
        let n0_cycle = scheduler
            .schedule
            .iter()
            .find(|&&(n, _)| n == 0)
            .map(|&(_, c)| c)
            .unwrap();
        assert_eq!(n0_cycle, 0, "Critical path node N0 should be at cycle 0");
    }

    // ------------------------------------------------------------------------
    // ResourceModel Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_resource_model_default() {
        let rm = ResourceModel::default_model();
        assert_eq!(rm.issue_width, 4);
        assert!(!rm.units.is_empty(), "Should have functional units");
        assert_eq!(rm.get_latency(1), 1, "Default ALU latency should be 1");
    }

    #[test]
    fn test_resource_model_reserve() {
        let mut rm = ResourceModel::default_model();
        rm.reserve(1, 0); // ALU op at cycle 0

        // ALU should be occupied at cycle 0.
        assert!(
            rm.is_unit_available(FuncUnitKind::ALU, 1),
            "ALU should be free at cycle 1 (latency=1)"
        );
        // After 4 ALU ops at cycle 0 (issue width 4), ALU should be full.
        rm.reserve(1, 0);
        rm.reserve(1, 0);
        rm.reserve(1, 0);
        // 4 ALU ops issued — ALU count is 4, so this fills it.
        // The 5th should not be possible, but our reservation doesn't enforce limits
        // until can_issue is called.
    }

    #[test]
    fn test_resource_model_skylake() {
        let rm = ResourceModel::skylake_model();
        assert!(rm.issue_width == 4 || rm.issue_width > 0);
        // Should have multiple ports.
        assert!(
            rm.units.len() >= 6,
            "Skylake should have multiple dispatch ports"
        );
    }

    #[test]
    fn test_resource_model_riscv_simple() {
        let rm = ResourceModel::riscv_simple_model();
        assert_eq!(rm.issue_width, 1, "Simple RISC-V is single-issue");
        assert!(rm.units.len() >= 2);
    }

    // ------------------------------------------------------------------------
    // HazardRecognizer Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_hazard_recognizer_raw() {
        let rm = ResourceModel::default_model();
        let hr = HazardRecognizer::new(rm);

        // Build a simple RAW scenario:
        // N0: r0 = add(r1, r2)  (latency 1)
        // N1: r3 = add(r0, r4)  (depends on r0)
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);
        let r2 = Reg::Phys(2);
        let r3 = Reg::Phys(3);
        let r4 = Reg::Phys(4);

        let mut n0 = DepNode::new(0, alu_instr(0, 1, Some(r0), &[r1, r2]));
        let n1 = DepNode::new(1, alu_instr(1, 1, Some(r3), &[r0, r4]));

        // Issue N0 at cycle 0.
        let mut hr2 = hr.clone();
        hr2.advance_to(0);
        hr2.issue(&n0, 0);

        // At cycle 0, N1 should have a RAW hazard (N0 hasn't finished).
        let hazards = hr2.can_issue_at(&n1, &[n0.clone(), n1.clone()], 0);
        assert!(!hazards.is_empty(), "N1 should have RAW hazard at cycle 0");

        // At cycle 1, N0 is done (latency 1), N1 should be able to issue.
        let hazards2 = hr2.can_issue_at(&n1, &[n0.clone(), n1.clone()], 1);
        // RAW may still exist if no forwarding. Let's check.
        // In our simplified model, latency is tracked via scoreboard.
    }

    #[test]
    fn test_hazard_recognizer_structural() {
        let mut rm = ResourceModel::default_model();
        // Make ALU single-issue.
        rm.units.retain(|u| u.kind != FuncUnitKind::ALU);
        rm.units.push(FuncUnit::new("ALU0", FuncUnitKind::ALU, 1));

        let hr = HazardRecognizer::new(rm);

        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let n0 = DepNode::new(0, alu_instr(0, 1, Some(r0), &[]));
        let n1 = DepNode::new(1, alu_instr(1, 1, Some(r1), &[]));

        let mut hr2 = hr.clone();
        hr2.advance_to(0);
        hr2.issue(&n0, 0);

        // At cycle 0, only one ALU available; second ALU op should have structural hazard.
        let hazards = hr2.can_issue_at(&n1, &[n0, n1.clone()], 0);
        assert!(!hazards.is_empty(), "Structural hazard with single ALU");
    }

    // ------------------------------------------------------------------------
    // PostRAScheduler Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_post_ra_scheduler_basic() {
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut post_ra = PostRAScheduler::new();
        post_ra.break_anti_deps = false;
        let result = post_ra.run(&instrs);

        assert_eq!(result.len(), 2, "Should keep all instructions");
    }

    #[test]
    fn test_post_ra_anti_dep_detection() {
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let n0 = DepNode::new(0, alu_instr(0, 1, None, &[r0])); // uses r0
        let n1 = DepNode::new(1, alu_instr(1, 1, Some(r0), &[r1])); // defs r0

        let post_ra = PostRAScheduler::new();
        let anti_reg = post_ra.has_anti_dep(&n0, &n1);
        assert_eq!(anti_reg, Some(0), "Anti-dep should be detected on r0");
    }

    // ------------------------------------------------------------------------
    // MacroFusion Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_macro_fusion_cmp_jcc() {
        let instrs = vec![
            SchedInstr::new(0, 100).with_latency(1),          // CMP
            SchedInstr::new(1, 200).with_latency(1).branch(), // JCC
        ];

        let mf = MacroFusion::new();
        let candidates = mf.analyze(&instrs);

        assert!(!candidates.is_empty(), "Should detect CMP+JCC pattern");
        assert_eq!(candidates[0].pattern, FusionPattern::CmpJcc);
        assert!(candidates[0].eligible);
    }

    #[test]
    fn test_macro_fusion_dec_jnz() {
        let instrs = vec![
            SchedInstr::new(0, 120).with_latency(1),          // DEC
            SchedInstr::new(1, 200).with_latency(1).branch(), // JCC
        ];

        let mf = MacroFusion::new();
        let candidates = mf.analyze(&instrs);

        assert!(!candidates.is_empty(), "Should detect DEC+JCC pattern");
        assert_eq!(candidates[0].pattern, FusionPattern::DecJnz);
    }

    #[test]
    fn test_macro_fusion_fuse_count() {
        let instrs = vec![
            SchedInstr::new(0, 100),          // CMP
            SchedInstr::new(1, 200).branch(), // JCC
            SchedInstr::new(2, 110),          // TEST
            SchedInstr::new(3, 201).branch(), // JCC
        ];

        let mut mf = MacroFusion::new();
        let mut instrs_mut = instrs.clone();
        let fused = mf.fuse(&mut instrs_mut);

        assert_eq!(fused, 2, "Should fuse both pairs");
        assert_eq!(mf.fused_count, 2);
    }

    #[test]
    fn test_macro_fusion_no_pattern() {
        let instrs = vec![
            SchedInstr::new(0, 1),            // Simple ALU (not fusible)
            SchedInstr::new(1, 200).branch(), // JCC
        ];

        let mf = MacroFusion::new();
        let candidates = mf.analyze(&instrs);

        assert!(
            candidates.is_empty(),
            "No fusion without recognized pattern"
        );
    }

    #[test]
    fn test_macro_fusion_disable() {
        let mut mf = MacroFusion::new();
        mf.enabled = false;

        let mut instrs = vec![SchedInstr::new(0, 100), SchedInstr::new(1, 200).branch()];

        let fused = mf.fuse(&mut instrs);
        assert_eq!(fused, 0, "No fusion when disabled");
    }

    // ------------------------------------------------------------------------
    // DeepScheduler Integration Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_deep_scheduler_default() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let result = DeepScheduler::run_default(&instrs);
        assert_eq!(result.len(), 3);
    }

    #[test]
    fn test_deep_scheduler_pre_ra() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let result = DeepScheduler::run_pre_ra(&instrs);
        assert_eq!(result.len(), 2);
    }

    #[test]
    fn test_deep_scheduler_post_ra() {
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]), // independent
        ];

        let result = DeepScheduler::run_post_ra(&instrs);
        assert_eq!(result.len(), 2);
    }

    #[test]
    fn test_deep_scheduler_stats() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut sched = DeepScheduler::new(DeepSchedConfig {
            verbose: false,
            ..DeepSchedConfig::default()
        });
        sched.run(&instrs);

        assert!(sched.stats.success, "Scheduling should succeed");
        assert_eq!(sched.stats.num_instrs, 2);
        assert!(sched.stats.true_deps > 0, "Should have true deps");
    }

    #[test]
    fn test_deep_scheduler_fp_chain() {
        // FP chain: should respect higher latencies.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![fp_add_instr(0, r0, r2, r3), fp_mul_instr(1, r1, r0, r2)];

        let mut sched = DeepScheduler::new(DeepSchedConfig::default());
        let result = sched.run(&instrs);

        assert_eq!(result.len(), 2);
        // FP mul (latency 7) after fp add (latency 5): the dependent
        // instruction should wait for the producer's result.
        assert!(
            sched.stats.schedule_length >= 5,
            "FP chain should show latency"
        );
    }

    #[test]
    fn test_deep_scheduler_empty() {
        let instrs: Vec<SchedInstr> = Vec::new();
        let result = DeepScheduler::run_default(&instrs);
        assert!(result.is_empty());
    }

    #[test]
    fn test_deep_scheduler_single_instr() {
        let r0 = Reg::Virt(0);
        let instrs = vec![alu_instr(0, 1, Some(r0), &[])];
        let result = DeepScheduler::run_default(&instrs);
        assert_eq!(result.len(), 1);
    }

    // ------------------------------------------------------------------------
    // DepGraphAnalysis Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_dep_graph_analysis_independent_groups() {
        // Two independent pairs:
        // N0 → N1  (independent chain 1)
        // N2 → N3  (independent chain 2)
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[]),
            alu_instr(3, 1, Some(r3), &[r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let analysis = DepGraphAnalysis::analyze(&dg);

        // Should find at least 2 independent groups (the two chains).
        assert!(
            analysis.independent_groups.len() >= 2,
            "Should find independent groups"
        );
        assert!(analysis.max_parallelism >= 2);
    }

    #[test]
    fn test_dep_graph_analysis_depth_sort() {
        // r0 = op()  → depth=2
        // r1 = op(r0) → depth=1
        // r2 = op(r1) → depth=0 (sink)
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        // Compute depth/height via ScheduleDAG first.
        let _dag = ScheduleDAG::new(dg.clone());

        let sorted = DepGraphAnalysis::nodes_by_depth(&dg);
        // First entry should have highest depth (N0 = closest to source).
        assert!(!sorted.is_empty(), "Should have sorted nodes");
        // N0 should be first (highest depth).
        assert_eq!(sorted[0], 0, "N0 should have highest depth");
    }

    #[test]
    fn test_dep_graph_analysis_path_enumeration() {
        // Diamond: N0 → N1, N0 → N2, N1 → N3, N2 → N3
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(r3), &[r1, r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);

        // Find paths from N0 to N3.
        let paths = DepGraphAnalysis::enumerate_paths(&dg, 0, 3, 10);
        assert_eq!(paths.len(), 2, "Diamond should have 2 paths");
    }

    // ------------------------------------------------------------------------
    // ForceDirectedScheduler Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_force_directed_scheduler_converges() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0, r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut fds = ForceDirectedScheduler::new(dg, rm);

        let schedule = fds.run(10);

        // All 3 nodes should be scheduled.
        assert_eq!(schedule.len(), 3);
        // N2 should be after N0 and N1.
        let n0_cycle = schedule[&0];
        let n1_cycle = schedule[&1];
        let n2_cycle = schedule[&2];
        assert!(n2_cycle >= n0_cycle + 1, "N2 must be after N0");
        assert!(n2_cycle >= n1_cycle + 1, "N2 must be after N1");
    }

    #[test]
    fn test_force_directed_scheduler_no_mobility() {
        // Single chain: no mobility, should stay in ASAP positions.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut fds = ForceDirectedScheduler::new(dg, rm);

        let schedule = fds.run(10);

        assert_eq!(schedule.len(), 2);
        // N1 should be exactly 1 cycle after N0.
        assert_eq!(schedule[&1], schedule[&0] + 1);
    }

    // ------------------------------------------------------------------------
    // BidirectionalScheduler Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_bidirectional_scheduler_top_down() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut bs = BidirectionalScheduler::new(dg, rm);
        bs.direction = SchedDirection::TopDown;

        let schedule = bs.run();
        assert_eq!(schedule.len(), 2);
    }

    #[test]
    fn test_bidirectional_scheduler_both_directions() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[r0, r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut bs = BidirectionalScheduler::new(dg, rm);
        bs.direction = SchedDirection::Bidirectional;

        let schedule = bs.run();
        assert_eq!(schedule.len(), 3);

        let (td_len, bu_len) = bs.comparison();
        assert!(td_len > 0);
        assert!(bu_len > 0);
    }

    // ------------------------------------------------------------------------
    // RegLivenessAnalysis Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_reg_liveness_simple() {
        // r0 = op()     def r0
        // r1 = op(r0)   use r0, def r1
        // r2 = op(r1)   use r1, def r2
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);
        let r2 = Reg::Phys(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let block_live_out = HashSet::new(); // Nothing live out.
        let liveness = RegLivenessAnalysis::compute(&instrs, &block_live_out);

        // r0 should be dead after instruction 1 (it's used and not redefined).
        assert!(
            !liveness.is_dead_after(0, 0),
            "r0 should be live after instruction 0"
        );
        assert!(
            liveness.is_dead_after(1, 0),
            "r0 should be dead after instruction 1"
        );

        // r1 should be dead after instruction 2.
        assert!(
            liveness.is_dead_after(2, 1),
            "r1 should be dead after instruction 2"
        );
    }

    #[test]
    fn test_reg_liveness_pressure() {
        // Several independent defs to increase pressure.
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);
        let r2 = Reg::Phys(2);
        let r3 = Reg::Phys(3);
        let r4 = Reg::Phys(4);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[]),
            // r3 uses r0, r1, r2 (all live)
            alu_instr(3, 1, Some(r3), &[r0, r1, r2]),
            // r4 uses r3
            alu_instr(4, 1, Some(r4), &[r3]),
        ];

        let block_live_out = HashSet::new();
        let liveness = RegLivenessAnalysis::compute(&instrs, &block_live_out);

        let profile = liveness.pressure_profile();
        // At instruction 2, r0, r1, r2 are all live = pressure 3.
        assert!(
            profile[2] >= 3,
            "Pressure at instruction 2 should be at least 3"
        );
        assert!(liveness.max_pressure() >= 3);
    }

    #[test]
    fn test_reg_liveness_find_free_reg() {
        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
        ];

        let block_live_out = HashSet::new();
        let liveness = RegLivenessAnalysis::compute(&instrs, &block_live_out);

        // At instruction 0, only r0 is live. r2 should be free.
        let free = liveness.find_free_reg(0, &[0, 2, 3]);
        assert_eq!(free, Some(2), "r2 should be free at instruction 0");
    }

    // ------------------------------------------------------------------------
    // FusionEligibility & MicroOpFusion Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_fusion_eligibility_cmp_jcc() {
        let rules = FusionEligibility::cmp_jcc();
        assert_eq!(rules.pattern, FusionPattern::CmpJcc);
        assert!(rules.requires_flag_setting);
        assert!(rules.allows_memory_operand);
    }

    #[test]
    fn test_fusion_eligibility_check_memory() {
        let rules = FusionEligibility::dec_jnz();

        let first = SchedInstr::new(0, 120).load();
        let second = SchedInstr::new(1, 200).branch();

        let result = rules.check(&first, &second);
        assert!(result.is_err(), "DEC+JNZ should reject memory operand");
    }

    #[test]
    fn test_micro_op_fusion_basic() {
        let mof = MicroOpFusion::new();

        let uop1 = MicroOp::new(FuncUnitKind::ALU, 1);
        let uop2 = MicroOp::new(FuncUnitKind::Branch, 1);

        let fused = mof.try_fuse(&uop1, &uop2);
        assert!(fused.is_some(), "ALU+Branch should fuse");
        assert_eq!(fused.unwrap().unit, FuncUnitKind::ALU);
    }

    #[test]
    fn test_micro_op_fusion_no_match() {
        let mof = MicroOpFusion::new();

        let uop1 = MicroOp::new(FuncUnitKind::FPAdd, 5);
        let uop2 = MicroOp::new(FuncUnitKind::FPMul, 7);

        let fused = mof.try_fuse(&uop1, &uop2);
        assert!(fused.is_none(), "FPAdd+FPMul should not fuse");
    }

    #[test]
    fn test_micro_op_fusion_decomposition() {
        let mut mof = MicroOpFusion::new();

        let uops = vec![
            MicroOp::new(FuncUnitKind::ALU, 1),
            MicroOp::new(FuncUnitKind::Branch, 1),
            MicroOp::new(FuncUnitKind::ALU, 1),
        ];

        let decomp = MicroOpDecomposition::new(42, uops);
        let fused = mof.fuse_decomposition(&decomp);

        // First two should fuse, leaving 2 uops total.
        assert_eq!(fused.count(), 2, "Should fuse first pair, leaving 2 uops");
        assert_eq!(mof.fused_count, 1);
    }

    // ------------------------------------------------------------------------
    // Instruction Itinerary Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_instr_itinerary_total_cycles() {
        let itinerary = InstrItinerary::new(100, "LOAD")
            .with_stage(FuncUnitKind::Load, 3)
            .with_stage(FuncUnitKind::ALU, 1);

        assert_eq!(itinerary.total_cycles(), 4);
        assert_eq!(itinerary.latency, 4);
        assert!(itinerary.uses_unit(FuncUnitKind::Load));
        assert!(itinerary.uses_unit(FuncUnitKind::ALU));
        assert!(!itinerary.uses_unit(FuncUnitKind::FPAdd));
    }

    #[test]
    fn test_micro_op_decomposition_latency() {
        let uops = vec![
            MicroOp::new(FuncUnitKind::ALU, 1),
            MicroOp::new(FuncUnitKind::ALU, 1),
            MicroOp::new(FuncUnitKind::Load, 3),
        ];

        let decomp = MicroOpDecomposition::new(42, uops);
        assert_eq!(decomp.count(), 3);
        assert_eq!(decomp.total_latency, 5);
    }

    // ------------------------------------------------------------------------
    // ScheduleDAG Additional Analysis Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_sched_dag_mobility_zero_on_critical_path() {
        // All nodes on a single chain have zero mobility.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r1]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        for i in 0..3 {
            assert_eq!(
                dag.mobility(i),
                0,
                "Node {} on single chain should have zero mobility",
                i
            );
        }
    }

    #[test]
    fn test_sched_dag_estimate_schedule_length() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);
        let rm = ResourceModel::default_model();

        let estimate = dag.estimate_schedule_length(&rm);
        assert!(estimate >= 1, "Schedule length estimate should be positive");
    }

    // ------------------------------------------------------------------------
    // ListScheduler Advanced Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_list_scheduler_balanced_priority() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        scheduler.priority_heuristic = SchedPriority::Balanced;

        let schedule = scheduler.run();
        assert_eq!(schedule.len(), 2);
    }

    #[test]
    fn test_list_scheduler_reg_pressure_priority() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        scheduler.priority_heuristic = SchedPriority::RegPressure;

        let schedule = scheduler.run();
        assert_eq!(schedule.len(), 2);
    }

    #[test]
    fn test_list_scheduler_no_resource_aware() {
        // Without resource awareness, more parallelism is possible.
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[]),
            alu_instr(3, 1, Some(r3), &[]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        scheduler.resource_aware = false;
        scheduler.run();

        // Without resource constraints, all independent ops should fit in
        // very few cycles (ideally 1).
        assert!(
            scheduler.schedule_length() <= 1,
            "Without resources, all ops fit in 1 cycle"
        );
    }

    #[test]
    fn test_list_scheduler_display() {
        let r0 = Reg::Virt(0);

        let instrs = vec![alu_instr(0, 1, Some(r0), &[])];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        scheduler.run();

        let display = scheduler.display_schedule();
        assert!(display.contains("ListScheduler Schedule"));
        assert!(display.contains("N0"));
    }

    // ------------------------------------------------------------------------
    // DeepScheduler Config & Summary Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_deep_sched_config_default() {
        let config = DeepSchedConfig::default();
        assert_eq!(config.priority, SchedPriority::CriticalPath);
        assert!(config.resource_aware);
        assert!(config.macro_fusion);
        assert_eq!(config.issue_width, 4);
    }

    #[test]
    fn test_deep_scheduler_summary() {
        let r0 = Reg::Virt(0);

        let instrs = vec![alu_instr(0, 1, Some(r0), &[])];

        let mut sched = DeepScheduler::default();
        sched.run(&instrs);

        let summary = sched.display_summary();
        assert!(summary.contains("Deep Scheduling Pipeline Summary"));
        assert!(summary.contains("Instructions: 1"));
    }

    #[test]
    fn test_deep_scheduler_verbose_config() {
        let config = DeepSchedConfig {
            verbose: true,
            ..DeepSchedConfig::default()
        };
        assert!(config.verbose);
    }

    // ------------------------------------------------------------------------
    // HazardRecognizer Feature Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_hazard_recognizer_forwarding_path() {
        let rm = ResourceModel::default_model();
        let mut hr = HazardRecognizer::new(rm);

        hr.add_forwarding(FuncUnitKind::ALU, FuncUnitKind::ALU, ForwardingPath::Full);

        let r0 = Reg::Phys(0);
        let r1 = Reg::Phys(1);

        let n0 = DepNode::new(0, alu_instr(0, 1, Some(r0), &[]));
        let n1 = DepNode::new(1, alu_instr(1, 1, Some(r1), &[r0]));

        let mut hr2 = hr.clone();
        hr2.issue(&n0, 0);

        // With full forwarding, N1 should be able to issue at cycle 0.
        let hazards = hr2.can_issue_at(&n1, &[n0.clone(), n1.clone()], 0);
        // Full forwarding means RAW hazard should be resolved.
        let has_raw = hazards.iter().any(|h| h.kind == HazardKind::ReadAfterWrite);
        assert!(!has_raw, "Full forwarding should eliminate RAW hazard");
    }

    #[test]
    fn test_hazard_recognizer_clear() {
        let rm = ResourceModel::default_model();
        let mut hr = HazardRecognizer::new(rm);

        let r0 = Reg::Phys(0);
        let n0 = DepNode::new(0, alu_instr(0, 1, Some(r0), &[]));

        hr.issue(&n0, 5);
        assert!(!hr.issued.is_empty());

        hr.clear();
        assert!(hr.issued.is_empty());
        assert_eq!(hr.current_cycle, 0);
    }

    #[test]
    fn test_hazard_kind_display() {
        assert_eq!(HazardKind::ReadAfterWrite.as_str(), "RAW");
        assert_eq!(HazardKind::Structural.as_str(), "structural");
        assert_eq!(HazardKind::IssueWidth.as_str(), "issue_width");
    }

    // ------------------------------------------------------------------------
    // Edge Case & Stress Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_empty_graph_analysis() {
        let dg = DependenceGraph::new();
        let analysis = DepGraphAnalysis::analyze(&dg);
        assert_eq!(analysis.independent_groups.len(), 0);
        assert_eq!(analysis.max_parallelism, 0);
        assert!(!analysis.has_cycle);
    }

    #[test]
    fn test_single_node_schedule() {
        let r0 = Reg::Virt(0);
        let instrs = vec![alu_instr(0, 1, Some(r0), &[])];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        let schedule = scheduler.run();

        assert_eq!(schedule.len(), 1);
        assert_eq!(schedule[0].1, 0, "Single instruction at cycle 0");
    }

    #[test]
    fn test_many_independent_ops() {
        // 16 independent ALU ops: should schedule within ceil(16/4)=4 cycles
        // with issue width 4.
        let regs: Vec<Reg> = (0..16).map(|i| Reg::Virt(i)).collect();
        let instrs: Vec<SchedInstr> = regs
            .iter()
            .enumerate()
            .map(|(i, &r)| alu_instr(i, 1, Some(r), &[]))
            .collect();

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();
        let mut scheduler = ListScheduler::new(dg, rm);
        let schedule = scheduler.run();

        assert_eq!(schedule.len(), 16);
        // With issue width 4, should take ~4 cycles.
        assert!(
            scheduler.schedule_length() <= 4,
            "16 ALU ops at issue width 4 should fit in ~4 cycles"
        );
    }

    #[test]
    fn test_diamond_dag_depth() {
        // N0 → N1, N0 → N2, N1 → M, N2 → M
        // Depth from N0 = 2 (N0→N1→M or N0→N2→M)
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let rm = Reg::Virt(3);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r2), &[r0]),
            alu_instr(3, 1, Some(rm), &[r1, r2]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let dag = ScheduleDAG::new(dg);

        // N0 is at top of critical path.
        let d0 = dag.graph().nodes[0].depth;
        assert!(d0 > 0, "N0 should have positive depth");

        // N3 (merge) is at the end.
        let d3 = dag.graph().nodes[3].depth;
        assert!(d3 < d0, "N3 should have smaller depth than N0");
    }

    // ------------------------------------------------------------------------
    // DepNode / DepEdge tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_dep_node_earliest_start_no_preds() {
        let instr = SchedInstr::new(0, 1);
        let node = DepNode::new(0, instr);
        let nodes = vec![node.clone()];

        // With no predecessors, earliest start should be 0.
        assert_eq!(node.earliest_start(&nodes), 0);
    }

    #[test]
    fn test_dep_kind_properties() {
        assert!(DepKind::True.is_true());
        assert!(!DepKind::Anti.is_true());
        assert!(DepKind::Anti.is_renamable());
        assert!(DepKind::Output.is_renamable());
        assert!(!DepKind::True.is_renamable());
        assert!(DepKind::Memory.is_memory());
    }

    #[test]
    fn test_reg_display() {
        assert_eq!(format!("{}", Reg::Virt(5)), "v5");
        assert_eq!(format!("{}", Reg::Phys(3)), "p3");
    }

    #[test]
    fn test_sched_operand_equality() {
        assert_eq!(
            SchedOperand::Reg(Reg::Virt(1)),
            SchedOperand::Reg(Reg::Virt(1))
        );
        assert_ne!(
            SchedOperand::Reg(Reg::Virt(1)),
            SchedOperand::Reg(Reg::Virt(2))
        );
        assert_eq!(SchedOperand::Imm(42), SchedOperand::Imm(42));
    }

    // ------------------------------------------------------------------------
    // ResourceModel extended tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_resource_model_find_issue_slot() {
        let mut rm = ResourceModel::default_model();
        // Reserve all ALUs at cycle 0.
        let alu_count = rm.get_unit_count(FuncUnitKind::ALU);
        for _ in 0..alu_count {
            rm.reserve(1, 0);
        }

        // Next ALU op should find slot at cycle 1.
        let slot = rm.find_issue_slot(1, 0);
        assert_eq!(
            slot, 1,
            "ALU op should be scheduled at cycle 1 when cycle 0 is full"
        );
    }

    #[test]
    fn test_resource_model_can_issue_multiple() {
        let rm = ResourceModel::default_model();
        // 4 ALU ops at issue width 4 should be ok.
        assert!(rm.can_issue(&[1, 1, 1, 1], 0));
        // 5 ALU ops should exceed issue width.
        assert!(!rm.can_issue(&[1, 1, 1, 1, 1], 0));
    }

    #[test]
    fn test_resource_model_max_reserved() {
        let mut rm = ResourceModel::default_model();
        assert_eq!(rm.max_reserved_cycle(), None);
        rm.reserve(1, 5);
        assert_eq!(rm.max_reserved_cycle(), Some(5));
    }

    // ------------------------------------------------------------------------
    // SchedulingRegion Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_scheduling_region_partition_empty() {
        let instrs: Vec<SchedInstr> = Vec::new();
        let regions = SchedulingRegion::partition(&instrs);
        assert!(regions.is_empty());
    }

    #[test]
    fn test_scheduling_region_partition_simple() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let regions = SchedulingRegion::partition(&instrs);
        assert_eq!(regions.len(), 1);
        assert_eq!(regions[0].size, 2);
    }

    #[test]
    fn test_scheduling_region_partition_with_branch() {
        let r0 = Reg::Virt(0);
        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            SchedInstr::new(1, 7).with_latency(1).branch(),
            alu_instr(2, 1, Some(r0), &[]),
        ];

        let regions = SchedulingRegion::partition(&instrs);
        // Should split at the branch.
        assert!(regions.len() >= 2, "Branch should create region boundary");
        assert!(regions.iter().any(|r| r.ends_with_branch));
    }

    #[test]
    fn test_scheduling_region_extract() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
            alu_instr(2, 1, Some(r0), &[]),
        ];

        let region = SchedulingRegion::new(0, 2);
        let slice = region.extract(&instrs);
        assert_eq!(slice.len(), 2);
    }

    // ------------------------------------------------------------------------
    // ScheduleVerifier Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_schedule_verifier_valid_schedule() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();

        // Valid schedule: N0 at cycle 0, N1 at cycle 1.
        let mut schedule = HashMap::new();
        schedule.insert(0, 0);
        schedule.insert(1, 1);

        let verifier = ScheduleVerifier::new(dg, rm, schedule);
        let result = verifier.verify();
        assert!(
            result.valid,
            "Valid schedule should pass: {:?}",
            result.violations
        );
    }

    #[test]
    fn test_schedule_verifier_violates_dependence() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();

        // Invalid schedule: N1 before N0.
        let mut schedule = HashMap::new();
        schedule.insert(0, 1);
        schedule.insert(1, 0);

        let verifier = ScheduleVerifier::new(dg, rm, schedule);
        let result = verifier.verify();
        assert!(!result.valid, "Invalid schedule should fail");
        assert!(!result.violations.is_empty());
    }

    #[test]
    fn test_schedule_verifier_missing_node() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);

        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[r0]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model();

        // Missing N1.
        let mut schedule = HashMap::new();
        schedule.insert(0, 0);

        let verifier = ScheduleVerifier::new(dg, rm, schedule);
        let result = verifier.verify();
        assert!(!result.valid, "Missing node should be detected");
    }

    #[test]
    fn test_schedule_verifier_resource_violation() {
        let r0 = Reg::Virt(0);
        let r1 = Reg::Virt(1);
        let r2 = Reg::Virt(2);
        let r3 = Reg::Virt(3);
        let r4 = Reg::Virt(4);

        // 5 independent ALU ops.
        let instrs = vec![
            alu_instr(0, 1, Some(r0), &[]),
            alu_instr(1, 1, Some(r1), &[]),
            alu_instr(2, 1, Some(r2), &[]),
            alu_instr(3, 1, Some(r3), &[]),
            alu_instr(4, 1, Some(r4), &[]),
        ];

        let mut dg = DependenceGraph::new();
        dg.build(&instrs);
        let rm = ResourceModel::default_model(); // issue_width = 4

        // Schedule all 5 at cycle 0 — exceeds issue width 4.
        let mut schedule = HashMap::new();
        for i in 0..5 {
            schedule.insert(i, 0);
        }

        let verifier = ScheduleVerifier::new(dg, rm, schedule);
        let result = verifier.verify();
        assert!(!result.valid, "Should detect issue width violation");
    }

    // ------------------------------------------------------------------------
    // InstrItinerary and Pipeline Tests
    // ------------------------------------------------------------------------

    #[test]
    fn test_pipeline_stage_creation() {
        let stage = PipelineStage::new(FuncUnitKind::ALU, 2);
        assert_eq!(stage.cycles, 2);
        assert!(stage.overlap);

        let stage2 = PipelineStage::new(FuncUnitKind::FPDiv, 12).non_overlapping();
        assert!(!stage2.overlap);
    }
}