amaters_core/compute/

optimizer.rs

//! Advanced circuit optimization for FHE computations
//!
//! This module provides sophisticated optimization passes to reduce the computational
//! cost of FHE circuits. The optimizer focuses on:
//!
//! 1. **Bootstrap Minimization** - Reducing expensive bootstrap operations
//! 2. **Gate Fusion** - Combining adjacent operations to reduce overhead
//! 3. **Dead Code Elimination** - Removing unused operations
//! 4. **Parallelization Analysis** - Identifying independent operations for parallel execution
//!
//! These optimizations can reduce circuit execution time by 30-50% in typical cases.

use crate::compute::circuit::{
    BinaryOperator, Circuit, CircuitNode, CircuitValue, CompareOperator, EncryptedType,
    UnaryOperator,
};
use crate::error::{AmateRSError, ErrorContext, Result};
use std::collections::{HashMap, HashSet, VecDeque};

/// Statistics collected during optimization
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct OptimizationStats {
    /// Number of gates before optimization
    pub original_gate_count: usize,

    /// Number of gates after optimization
    pub optimized_gate_count: usize,

    /// Number of bootstrap operations before optimization
    pub original_bootstrap_count: usize,

    /// Number of bootstrap operations after optimization
    pub optimized_bootstrap_count: usize,

    /// Number of dead code nodes removed
    pub dead_code_removed: usize,

    /// Number of nodes eliminated by DCE pass
    pub nodes_eliminated: usize,

    /// Number of algebraic simplifications applied
    pub algebraic_simplifications: usize,

    /// Number of constant expressions folded
    pub constants_folded: usize,

    /// Number of gates fused
    pub gates_fused: usize,

    /// Circuit depth before optimization
    pub original_depth: usize,

    /// Circuit depth after optimization
    pub optimized_depth: usize,
}

impl OptimizationStats {
    /// Calculate the reduction percentage in gate count
    pub fn gate_reduction_percent(&self) -> f64 {
        if self.original_gate_count == 0 {
            return 0.0;
        }
        let reduction = self
            .original_gate_count
            .saturating_sub(self.optimized_gate_count);
        (reduction as f64 / self.original_gate_count as f64) * 100.0
    }

    /// Calculate the reduction percentage in bootstrap operations
    pub fn bootstrap_reduction_percent(&self) -> f64 {
        if self.original_bootstrap_count == 0 {
            return 0.0;
        }
        let reduction = self
            .original_bootstrap_count
            .saturating_sub(self.optimized_bootstrap_count);
        (reduction as f64 / self.original_bootstrap_count as f64) * 100.0
    }

    /// Aggregate total statistics across all passes
    pub fn total_stats(&self) -> (usize, usize, usize) {
        (
            self.nodes_eliminated + self.dead_code_removed,
            self.algebraic_simplifications + self.gates_fused,
            self.constants_folded,
        )
    }
}

/// Dependency information for parallelization
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DependencyGraph {
    /// Node ID to its dependencies
    pub dependencies: HashMap<NodeId, Vec<NodeId>>,

    /// Nodes that can be executed in parallel (sets of independent nodes)
    pub parallel_groups: Vec<Vec<NodeId>>,

    /// Critical path through the circuit (longest dependency chain)
    pub critical_path: Vec<NodeId>,

    /// Total number of nodes in the graph
    pub node_count: usize,
}

impl DependencyGraph {
    /// Create an empty dependency graph
    pub fn new() -> Self {
        Self {
            dependencies: HashMap::new(),
            parallel_groups: Vec::new(),
            critical_path: Vec::new(),
            node_count: 0,
        }
    }

    /// Calculate the maximum parallelism (largest parallel group)
    pub fn max_parallelism(&self) -> usize {
        self.parallel_groups
            .iter()
            .map(|g| g.len())
            .max()
            .unwrap_or(0)
    }

    /// Calculate the average parallelism
    pub fn avg_parallelism(&self) -> f64 {
        if self.parallel_groups.is_empty() {
            return 0.0;
        }
        let total: usize = self.parallel_groups.iter().map(|g| g.len()).sum();
        total as f64 / self.parallel_groups.len() as f64
    }

    /// Returns nodes in topological order (dependencies before dependents)
    pub fn topological_order(&self) -> Vec<NodeId> {
        self.compute_topological_order()
    }

    fn compute_topological_order(&self) -> Vec<NodeId> {
        // Kahn's algorithm: in_degree[node] = number of prerequisites (dependencies)
        let mut in_degree: HashMap<NodeId, usize> = HashMap::new();

        // Initialize all nodes to in-degree = number of their dependencies
        for (node_id, deps) in &self.dependencies {
            *in_degree.entry(*node_id).or_insert(0) = deps.len();
            // Ensure deps are also in the map
            for dep_id in deps {
                in_degree.entry(*dep_id).or_insert(0);
            }
        }

        // Start with nodes that have no dependencies (leaves)
        let mut queue: std::collections::BTreeSet<NodeId> = in_degree
            .iter()
            .filter(|&(_, deg)| *deg == 0)
            .map(|(&id, _)| id)
            .collect();

        let mut result = Vec::new();

        // Build reverse edges: for each dep, who depends on it?
        let mut dependents: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
        for (node_id, deps) in &self.dependencies {
            for dep_id in deps {
                dependents.entry(*dep_id).or_default().push(*node_id);
            }
        }

        while let Some(&node_id) = queue.iter().next() {
            queue.remove(&node_id);
            result.push(node_id);

            if let Some(dep_nodes) = dependents.get(&node_id) {
                for &dependent_id in dep_nodes {
                    if let Some(deg) = in_degree.get_mut(&dependent_id) {
                        if *deg > 0 {
                            *deg -= 1;
                            if *deg == 0 {
                                queue.insert(dependent_id);
                            }
                        }
                    }
                }
            }
        }

        result
    }
}

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

/// Node identifier for dependency tracking
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(pub usize);

/// Advanced circuit optimizer with multiple optimization passes
#[derive(Debug, Clone)]
pub struct CircuitOptimizer {
    /// Enable constant folding optimization
    pub enable_constant_folding: bool,

    /// Enable dead code elimination
    pub enable_dead_code_elimination: bool,

    /// Enable bootstrap minimization
    pub enable_bootstrap_minimization: bool,

    /// Enable gate fusion
    pub enable_gate_fusion: bool,

    /// Enable parallelization analysis
    pub enable_parallelization_analysis: bool,

    /// Statistics from the last optimization
    stats: OptimizationStats,

    /// Dependency graph from the last optimization
    dependency_graph: DependencyGraph,
}

impl CircuitOptimizer {
    /// Create a new optimizer with all optimizations enabled
    pub fn new() -> Self {
        Self {
            enable_constant_folding: true,
            enable_dead_code_elimination: true,
            enable_bootstrap_minimization: true,
            enable_gate_fusion: true,
            enable_parallelization_analysis: true,
            stats: OptimizationStats::default(),
            dependency_graph: DependencyGraph::new(),
        }
    }

    /// Create an optimizer with no optimizations enabled
    pub fn disabled() -> Self {
        Self {
            enable_constant_folding: false,
            enable_dead_code_elimination: false,
            enable_bootstrap_minimization: false,
            enable_gate_fusion: false,
            enable_parallelization_analysis: false,
            stats: OptimizationStats::default(),
            dependency_graph: DependencyGraph::new(),
        }
    }

    /// Get the statistics from the last optimization
    pub fn stats(&self) -> &OptimizationStats {
        &self.stats
    }

    /// Get the dependency graph from the last optimization
    pub fn dependency_graph(&self) -> &DependencyGraph {
        &self.dependency_graph
    }

    /// Get aggregated totals: (nodes_eliminated, algebraic_simplifications, constant_folds)
    pub fn total_stats(&self) -> (usize, usize, usize) {
        self.stats.total_stats()
    }

    /// Optimize a circuit by applying all enabled optimization passes
    pub fn optimize(&mut self, circuit: Circuit) -> Result<Circuit> {
        // Record original statistics
        self.stats.original_gate_count = circuit.gate_count;
        self.stats.original_depth = circuit.depth;
        self.stats.original_bootstrap_count = self.count_bootstraps(&circuit.root);

        let mut optimized_root = circuit.root.clone();

        // Apply optimization passes in order
        if self.enable_constant_folding {
            optimized_root = self.constant_folding_pass(optimized_root);
        }

        if self.enable_gate_fusion {
            optimized_root = self.gate_fusion_pass(optimized_root);
        }

        if self.enable_bootstrap_minimization {
            optimized_root = self.bootstrap_minimization_pass(optimized_root)?;
        }

        if self.enable_dead_code_elimination {
            optimized_root = self.dead_code_elimination_pass(optimized_root);
        }

        // Build optimized circuit
        let optimized_circuit = Circuit::new(optimized_root, circuit.variable_types)?;

        // Record optimized statistics
        self.stats.optimized_gate_count = optimized_circuit.gate_count;
        self.stats.optimized_depth = optimized_circuit.depth;
        self.stats.optimized_bootstrap_count = self.count_bootstraps(&optimized_circuit.root);

        // Analyze parallelization if enabled
        if self.enable_parallelization_analysis {
            self.dependency_graph = self.analyze_parallelism(&optimized_circuit)?;
        }

        Ok(optimized_circuit)
    }

    /// Count the number of bootstrap operations in a circuit
    ///
    /// In TFHE, bootstrapping is required after certain operations to refresh noise.
    /// For this implementation, we estimate bootstraps based on operation types:
    /// - Multiplication requires bootstrap
    /// - Comparison operations require bootstrap
    /// - Deep chains of additions may require bootstrap
    #[allow(clippy::only_used_in_recursion)]
    fn count_bootstraps(&self, node: &CircuitNode) -> usize {
        match node {
            CircuitNode::Load(_)
            | CircuitNode::Constant(_)
            | CircuitNode::EncryptedConstant { .. } => 0,

            CircuitNode::BinaryOp { op, left, right } => {
                let left_bootstraps = self.count_bootstraps(left);
                let right_bootstraps = self.count_bootstraps(right);

                // Multiplication requires bootstrap
                let op_bootstrap = match op {
                    BinaryOperator::Mul => 1,
                    _ => 0,
                };

                left_bootstraps + right_bootstraps + op_bootstrap
            }

            CircuitNode::UnaryOp { operand, .. } => self.count_bootstraps(operand),

            CircuitNode::Compare { left, right, .. } => {
                let left_bootstraps = self.count_bootstraps(left);
                let right_bootstraps = self.count_bootstraps(right);

                // Comparisons typically require bootstrap
                left_bootstraps + right_bootstraps + 1
            }
            CircuitNode::NaryOp { op, operands } => {
                let operand_bootstraps: usize =
                    operands.iter().map(|o| self.count_bootstraps(o)).sum();
                let op_bootstraps = match op {
                    BinaryOperator::Mul => operands.len().saturating_sub(1),
                    _ => 0,
                };
                operand_bootstraps + op_bootstraps
            }
        }
    }

    /// Constant folding optimization pass
    ///
    /// Evaluates constant expressions at compile time to reduce runtime computation
    fn constant_folding_pass(&mut self, node: CircuitNode) -> CircuitNode {
        match node {
            CircuitNode::BinaryOp { op, left, right } => {
                let left = self.constant_folding_pass(*left);
                let right = self.constant_folding_pass(*right);

                // Try to fold constants
                if let (CircuitNode::Constant(l), CircuitNode::Constant(r)) = (&left, &right) {
                    if let Some(result) = self.fold_binary_constants(op, l, r) {
                        self.stats.constants_folded += 1;
                        return CircuitNode::Constant(result);
                    }
                }

                // Apply algebraic identities
                if let Some(simplified) = self.apply_algebraic_identities(op, &left, &right) {
                    return simplified;
                }

                CircuitNode::BinaryOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            CircuitNode::UnaryOp { op, operand } => {
                let operand = self.constant_folding_pass(*operand);

                if let CircuitNode::Constant(val) = &operand {
                    if let Some(result) = self.fold_unary_constant(op, val) {
                        self.stats.constants_folded += 1;
                        return CircuitNode::Constant(result);
                    }
                }

                CircuitNode::UnaryOp {
                    op,
                    operand: Box::new(operand),
                }
            }

            CircuitNode::Compare { op, left, right } => {
                let left = self.constant_folding_pass(*left);
                let right = self.constant_folding_pass(*right);

                CircuitNode::Compare {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            CircuitNode::NaryOp { op, operands } => {
                let new_operands: Vec<CircuitNode> = operands
                    .into_iter()
                    .map(|o| self.constant_folding_pass(o))
                    .collect();
                CircuitNode::NaryOp {
                    op,
                    operands: new_operands,
                }
            }

            other => other,
        }
    }

    /// Fold binary operation on constants
    fn fold_binary_constants(
        &self,
        op: BinaryOperator,
        left: &CircuitValue,
        right: &CircuitValue,
    ) -> Option<CircuitValue> {
        match (left, right) {
            (CircuitValue::U8(l), CircuitValue::U8(r)) => match op {
                BinaryOperator::Add => Some(CircuitValue::U8(l.wrapping_add(*r))),
                BinaryOperator::Sub => Some(CircuitValue::U8(l.wrapping_sub(*r))),
                BinaryOperator::Mul => Some(CircuitValue::U8(l.wrapping_mul(*r))),
                _ => None,
            },
            (CircuitValue::U16(l), CircuitValue::U16(r)) => match op {
                BinaryOperator::Add => Some(CircuitValue::U16(l.wrapping_add(*r))),
                BinaryOperator::Sub => Some(CircuitValue::U16(l.wrapping_sub(*r))),
                BinaryOperator::Mul => Some(CircuitValue::U16(l.wrapping_mul(*r))),
                _ => None,
            },
            (CircuitValue::U32(l), CircuitValue::U32(r)) => match op {
                BinaryOperator::Add => Some(CircuitValue::U32(l.wrapping_add(*r))),
                BinaryOperator::Sub => Some(CircuitValue::U32(l.wrapping_sub(*r))),
                BinaryOperator::Mul => Some(CircuitValue::U32(l.wrapping_mul(*r))),
                _ => None,
            },
            (CircuitValue::U64(l), CircuitValue::U64(r)) => match op {
                BinaryOperator::Add => Some(CircuitValue::U64(l.wrapping_add(*r))),
                BinaryOperator::Sub => Some(CircuitValue::U64(l.wrapping_sub(*r))),
                BinaryOperator::Mul => Some(CircuitValue::U64(l.wrapping_mul(*r))),
                _ => None,
            },
            (CircuitValue::Bool(l), CircuitValue::Bool(r)) => match op {
                BinaryOperator::And => Some(CircuitValue::Bool(*l && *r)),
                BinaryOperator::Or => Some(CircuitValue::Bool(*l || *r)),
                BinaryOperator::Xor => Some(CircuitValue::Bool(*l ^ *r)),
                _ => None,
            },
            _ => None,
        }
    }

    /// Fold unary operation on constant
    fn fold_unary_constant(&self, op: UnaryOperator, value: &CircuitValue) -> Option<CircuitValue> {
        match (op, value) {
            (UnaryOperator::Not, CircuitValue::Bool(v)) => Some(CircuitValue::Bool(!*v)),
            _ => None,
        }
    }

    /// Apply algebraic identities to simplify expressions
    /// Examples: x + 0 = x, x * 1 = x, x * 0 = 0, x AND true = x, etc.
    fn apply_algebraic_identities(
        &mut self,
        op: BinaryOperator,
        left: &CircuitNode,
        right: &CircuitNode,
    ) -> Option<CircuitNode> {
        match op {
            BinaryOperator::Add => {
                // x + 0 = x
                if Self::is_zero(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
                // 0 + x = x
                if Self::is_zero(left) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
            }

            BinaryOperator::Sub => {
                // x - 0 = x
                if Self::is_zero(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
            }

            BinaryOperator::Mul => {
                // x * 0 = 0
                if Self::is_zero(right) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
                if Self::is_zero(left) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }

                // x * 1 = x
                if Self::is_one(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
                // 1 * x = x
                if Self::is_one(left) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
            }

            BinaryOperator::And => {
                // x AND true = x
                if Self::is_true(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
                if Self::is_true(left) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }

                // x AND false = false
                if Self::is_false(right) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
                if Self::is_false(left) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
            }

            BinaryOperator::Or => {
                // x OR false = x
                if Self::is_false(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
                if Self::is_false(left) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }

                // x OR true = true
                if Self::is_true(right) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
                if Self::is_true(left) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
            }

            BinaryOperator::Xor => {
                // x XOR false = x
                if Self::is_false(right) {
                    self.stats.gates_fused += 1;
                    return Some(left.clone());
                }
                if Self::is_false(left) {
                    self.stats.gates_fused += 1;
                    return Some(right.clone());
                }
            }
        }

        None
    }

    /// Check if a node is constant zero
    fn is_zero(node: &CircuitNode) -> bool {
        matches!(
            node,
            CircuitNode::Constant(CircuitValue::U8(0))
                | CircuitNode::Constant(CircuitValue::U16(0))
                | CircuitNode::Constant(CircuitValue::U32(0))
                | CircuitNode::Constant(CircuitValue::U64(0))
        )
    }

    /// Check if a node is constant one
    fn is_one(node: &CircuitNode) -> bool {
        matches!(
            node,
            CircuitNode::Constant(CircuitValue::U8(1))
                | CircuitNode::Constant(CircuitValue::U16(1))
                | CircuitNode::Constant(CircuitValue::U32(1))
                | CircuitNode::Constant(CircuitValue::U64(1))
        )
    }

    /// Check if a node is constant true
    fn is_true(node: &CircuitNode) -> bool {
        matches!(node, CircuitNode::Constant(CircuitValue::Bool(true)))
    }

    /// Check if a node is constant false
    fn is_false(node: &CircuitNode) -> bool {
        matches!(node, CircuitNode::Constant(CircuitValue::Bool(false)))
    }

    /// Gate fusion optimization pass
    ///
    /// Combines adjacent operations to reduce overhead:
    /// - Associative+commutative same-op chains are flattened into NaryOp nodes
    /// - Multiple consecutive NOT operations are eliminated
    fn gate_fusion_pass(&mut self, node: CircuitNode) -> CircuitNode {
        match node {
            CircuitNode::BinaryOp { op, left, right } => {
                let left = self.gate_fusion_pass(*left);
                let right = self.gate_fusion_pass(*right);

                match op {
                    BinaryOperator::Add
                    | BinaryOperator::Mul
                    | BinaryOperator::And
                    | BinaryOperator::Or
                    | BinaryOperator::Xor => {
                        // Collect flat operand list by flattening same-op children.
                        // After these two calls, left/right are consumed into operands.
                        let mut operands: Vec<CircuitNode> = Vec::new();
                        Self::collect_nary_operands(op, left, &mut operands);
                        Self::collect_nary_operands(op, right, &mut operands);
                        // Invariant: operands.len() >= 2 (each of left/right contributes >= 1)

                        if operands.len() >= 3 {
                            self.stats.gates_fused += operands.len().saturating_sub(2);
                            CircuitNode::NaryOp { op, operands }
                        } else {
                            // Exactly 2 operands — BinaryOp is the canonical form
                            Self::build_balanced_reduction(op, operands)
                        }
                    }
                    _ => CircuitNode::BinaryOp {
                        op,
                        left: Box::new(left),
                        right: Box::new(right),
                    },
                }
            }

            CircuitNode::NaryOp { op, operands } => {
                // Recurse into operands and potentially absorb more
                let new_operands: Vec<CircuitNode> = operands
                    .into_iter()
                    .map(|o| self.gate_fusion_pass(o))
                    .collect();
                // Re-flatten after recursion
                let mut flat_operands = Vec::new();
                for operand in new_operands {
                    Self::collect_nary_operands(op, operand, &mut flat_operands);
                }
                if flat_operands.len() >= 2 {
                    CircuitNode::NaryOp {
                        op,
                        operands: flat_operands,
                    }
                } else if flat_operands.len() == 1 {
                    flat_operands.remove(0)
                } else {
                    CircuitNode::NaryOp {
                        op,
                        operands: flat_operands,
                    }
                }
            }

            CircuitNode::UnaryOp {
                op: UnaryOperator::Not,
                operand,
            } => {
                let operand = self.gate_fusion_pass(*operand);

                // NOT(NOT(x)) = x
                if let CircuitNode::UnaryOp {
                    op: UnaryOperator::Not,
                    operand: inner,
                } = operand
                {
                    self.stats.gates_fused += 2;
                    return *inner;
                }

                CircuitNode::UnaryOp {
                    op: UnaryOperator::Not,
                    operand: Box::new(operand),
                }
            }

            CircuitNode::UnaryOp { op, operand } => {
                let operand = self.gate_fusion_pass(*operand);
                CircuitNode::UnaryOp {
                    op,
                    operand: Box::new(operand),
                }
            }

            CircuitNode::Compare { op, left, right } => {
                let left = self.gate_fusion_pass(*left);
                let right = self.gate_fusion_pass(*right);
                CircuitNode::Compare {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            other => other,
        }
    }

    /// Helper to collect operands for N-ary fusion by flattening same-op chains
    fn collect_nary_operands(op: BinaryOperator, node: CircuitNode, out: &mut Vec<CircuitNode>) {
        match node {
            CircuitNode::BinaryOp {
                op: child_op,
                left,
                right,
            } if child_op == op => {
                Self::collect_nary_operands(op, *left, out);
                Self::collect_nary_operands(op, *right, out);
            }
            CircuitNode::NaryOp {
                op: child_op,
                operands,
            } if child_op == op => {
                for operand in operands {
                    Self::collect_nary_operands(op, operand, out);
                }
            }
            other => out.push(other),
        }
    }

    /// Bootstrap minimization pass
    ///
    /// Analyzes the circuit to minimize expensive bootstrap operations by:
    /// - Reordering operations to delay bootstraps
    /// - Combining operations that share bootstrap requirements
    /// - Eliminating redundant bootstraps
    fn bootstrap_minimization_pass(&mut self, node: CircuitNode) -> Result<CircuitNode> {
        Ok(self.reorder_for_bootstrap_efficiency(node))
    }

    /// Reorder operations to minimize bootstraps
    ///
    /// For commutative operators, places the higher-bootstrap-cost subtree
    /// first (left), which improves scheduling locality. For NaryOp Mul
    /// (bootstrap-heavy), builds a balanced binary reduction tree.
    fn reorder_for_bootstrap_efficiency(&mut self, node: CircuitNode) -> CircuitNode {
        match node {
            CircuitNode::BinaryOp { op, left, right } => {
                let left = self.reorder_for_bootstrap_efficiency(*left);
                let right = self.reorder_for_bootstrap_efficiency(*right);

                let is_commutative = matches!(
                    op,
                    BinaryOperator::Add
                        | BinaryOperator::Mul
                        | BinaryOperator::And
                        | BinaryOperator::Or
                        | BinaryOperator::Xor
                );

                if is_commutative {
                    let left_cost = self.count_bootstraps(&left);
                    let right_cost = self.count_bootstraps(&right);
                    if right_cost > left_cost {
                        return CircuitNode::BinaryOp {
                            op,
                            left: Box::new(right),
                            right: Box::new(left),
                        };
                    }
                }

                CircuitNode::BinaryOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            CircuitNode::NaryOp { op, operands } => {
                // Recurse into operands
                let processed_operands: Vec<CircuitNode> = operands
                    .into_iter()
                    .map(|o| self.reorder_for_bootstrap_efficiency(o))
                    .collect();

                // For Mul (bootstrap-heavy), build balanced binary reduction tree
                if matches!(op, BinaryOperator::Mul) && processed_operands.len() >= 2 {
                    return Self::build_balanced_reduction(op, processed_operands);
                }

                // For Add and logical ops (no bootstrap cost), sort by cost descending
                let mut with_costs: Vec<(usize, CircuitNode)> = processed_operands
                    .into_iter()
                    .map(|o| {
                        let cost = self.count_bootstraps(&o);
                        (cost, o)
                    })
                    .collect();
                with_costs.sort_by_key(|b| std::cmp::Reverse(b.0));
                let sorted_operands: Vec<CircuitNode> =
                    with_costs.into_iter().map(|(_, o)| o).collect();

                CircuitNode::NaryOp {
                    op,
                    operands: sorted_operands,
                }
            }

            CircuitNode::UnaryOp { op, operand } => {
                let operand = self.reorder_for_bootstrap_efficiency(*operand);
                CircuitNode::UnaryOp {
                    op,
                    operand: Box::new(operand),
                }
            }

            CircuitNode::Compare { op, left, right } => {
                let left = self.reorder_for_bootstrap_efficiency(*left);
                let right = self.reorder_for_bootstrap_efficiency(*right);
                CircuitNode::Compare {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            other => other,
        }
    }

    /// Build a balanced binary reduction tree for N operands
    fn build_balanced_reduction(op: BinaryOperator, operands: Vec<CircuitNode>) -> CircuitNode {
        if operands.is_empty() {
            // Degenerate case: return a zero-value placeholder
            return CircuitNode::Constant(crate::compute::circuit::CircuitValue::U8(0));
        }
        if operands.len() == 1 {
            // unwrap is safe here: len == 1, so next() always returns Some
            return operands.into_iter().next().unwrap_or(CircuitNode::Constant(
                crate::compute::circuit::CircuitValue::U8(0),
            ));
        }
        if operands.len() == 2 {
            let mut it = operands.into_iter();
            // Both next() calls succeed because len == 2
            let left = it.next().unwrap_or(CircuitNode::Constant(
                crate::compute::circuit::CircuitValue::U8(0),
            ));
            let right = it.next().unwrap_or(CircuitNode::Constant(
                crate::compute::circuit::CircuitValue::U8(0),
            ));
            return CircuitNode::BinaryOp {
                op,
                left: Box::new(left),
                right: Box::new(right),
            };
        }

        let mid = operands.len() / 2;
        let (left_operands, right_operands) = operands.into_iter().enumerate().fold(
            (Vec::new(), Vec::new()),
            |(mut l, mut r), (i, node)| {
                if i < mid {
                    l.push(node);
                } else {
                    r.push(node);
                }
                (l, r)
            },
        );

        let left_node = Self::build_balanced_reduction(op, left_operands);
        let right_node = Self::build_balanced_reduction(op, right_operands);

        CircuitNode::BinaryOp {
            op,
            left: Box::new(left_node),
            right: Box::new(right_node),
        }
    }

    /// Dead code elimination pass
    ///
    /// Performs real DCE by:
    /// 1. Applying algebraic simplifications that eliminate redundant operations
    ///    (e.g., `x - x` -> `0`, `x + 0` -> `x`, double negation)
    /// 2. Constant folding any newly-exposed constant sub-expressions
    /// 3. Iterating until a fixed point is reached (no further changes)
    ///
    /// For single-output tree-structured circuits every reachable node is live,
    /// so classical "unused result" DCE is a no-op on the tree. Instead we focus
    /// on strength-reducing and identity-collapsing operations that produce
    /// effectively dead work (operations whose result equals an operand or a
    /// constant).
    fn dead_code_elimination_pass(&mut self, node: CircuitNode) -> CircuitNode {
        let mut current = node;
        // Iterate to a fixed point so nested simplifications cascade
        loop {
            let simplified = self.dce_simplify(current.clone());
            if simplified == current {
                break;
            }
            current = simplified;
        }
        current
    }

    /// Single pass of DCE simplification applied bottom-up
    fn dce_simplify(&mut self, node: CircuitNode) -> CircuitNode {
        match node {
            CircuitNode::BinaryOp { op, left, right } => {
                // Recurse first (bottom-up)
                let left = self.dce_simplify(*left);
                let right = self.dce_simplify(*right);

                // Constant folding on newly-exposed constants
                if let (CircuitNode::Constant(l), CircuitNode::Constant(r)) = (&left, &right) {
                    if let Some(result) = self.fold_binary_constants(op, l, r) {
                        self.stats.nodes_eliminated += 1;
                        self.stats.constants_folded += 1;
                        return CircuitNode::Constant(result);
                    }
                }

                // x - x = 0 (same subtree detection)
                if op == BinaryOperator::Sub && left == right {
                    self.stats.nodes_eliminated += 1;
                    self.stats.algebraic_simplifications += 1;
                    // Produce a zero of the appropriate type based on left subtree
                    return self.zero_like(&left);
                }

                // x XOR x = false
                if op == BinaryOperator::Xor && left == right {
                    self.stats.nodes_eliminated += 1;
                    self.stats.algebraic_simplifications += 1;
                    return CircuitNode::Constant(CircuitValue::Bool(false));
                }

                // Algebraic identities: x+0, 0+x, x-0, x*1, 1*x, x*0, 0*x
                match op {
                    BinaryOperator::Add => {
                        if Self::is_zero(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_zero(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                    }
                    BinaryOperator::Sub => {
                        if Self::is_zero(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                    }
                    BinaryOperator::Mul => {
                        if Self::is_zero(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                        if Self::is_zero(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_one(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_one(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                    }
                    BinaryOperator::And => {
                        // x AND x = x
                        if left == right {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_true(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_true(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                        if Self::is_false(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                        if Self::is_false(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                    }
                    BinaryOperator::Or => {
                        // x OR x = x
                        if left == right {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_false(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_false(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                        if Self::is_true(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                        if Self::is_true(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                    }
                    BinaryOperator::Xor => {
                        if Self::is_false(&right) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return left;
                        }
                        if Self::is_false(&left) {
                            self.stats.nodes_eliminated += 1;
                            self.stats.algebraic_simplifications += 1;
                            return right;
                        }
                    }
                }

                CircuitNode::BinaryOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            CircuitNode::UnaryOp { op, operand } => {
                let operand = self.dce_simplify(*operand);

                // Constant folding
                if let CircuitNode::Constant(val) = &operand {
                    if let Some(result) = self.fold_unary_constant(op, val) {
                        self.stats.nodes_eliminated += 1;
                        self.stats.constants_folded += 1;
                        return CircuitNode::Constant(result);
                    }
                }

                // Double negation: NOT(NOT(x)) = x
                if op == UnaryOperator::Not {
                    if let CircuitNode::UnaryOp {
                        op: UnaryOperator::Not,
                        operand: inner,
                    } = operand
                    {
                        self.stats.nodes_eliminated += 2;
                        self.stats.algebraic_simplifications += 1;
                        return *inner;
                    }
                }

                // Double negation for Neg: Neg(Neg(x)) = x
                if op == UnaryOperator::Neg {
                    if let CircuitNode::UnaryOp {
                        op: UnaryOperator::Neg,
                        operand: inner,
                    } = operand
                    {
                        self.stats.nodes_eliminated += 2;
                        self.stats.algebraic_simplifications += 1;
                        return *inner;
                    }
                }

                CircuitNode::UnaryOp {
                    op,
                    operand: Box::new(operand),
                }
            }

            CircuitNode::Compare { op, left, right } => {
                let left = self.dce_simplify(*left);
                let right = self.dce_simplify(*right);

                // Constant fold comparisons
                if let (CircuitNode::Constant(l), CircuitNode::Constant(r)) = (&left, &right) {
                    if let Some(result) = self.fold_comparison(op, l, r) {
                        self.stats.nodes_eliminated += 1;
                        self.stats.constants_folded += 1;
                        return CircuitNode::Constant(CircuitValue::Bool(result));
                    }
                }

                CircuitNode::Compare {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                }
            }

            CircuitNode::NaryOp { op, operands } => {
                let new_operands: Vec<CircuitNode> =
                    operands.into_iter().map(|o| self.dce_simplify(o)).collect();
                CircuitNode::NaryOp {
                    op,
                    operands: new_operands,
                }
            }

            other => other,
        }
    }

    /// Produce a zero constant matching the type inferred from a subtree
    fn zero_like(&self, node: &CircuitNode) -> CircuitNode {
        match node {
            CircuitNode::Constant(CircuitValue::U8(_)) => {
                CircuitNode::Constant(CircuitValue::U8(0))
            }
            CircuitNode::Constant(CircuitValue::U16(_)) => {
                CircuitNode::Constant(CircuitValue::U16(0))
            }
            CircuitNode::Constant(CircuitValue::U32(_)) => {
                CircuitNode::Constant(CircuitValue::U32(0))
            }
            CircuitNode::Constant(CircuitValue::U64(_)) => {
                CircuitNode::Constant(CircuitValue::U64(0))
            }
            // Default to U8(0) for non-constant nodes where type is unknown
            _ => CircuitNode::Constant(CircuitValue::U8(0)),
        }
    }

    /// Fold comparison of two constants into a boolean result
    fn fold_comparison(
        &self,
        op: CompareOperator,
        left: &CircuitValue,
        right: &CircuitValue,
    ) -> Option<bool> {
        match (left, right) {
            (CircuitValue::U8(l), CircuitValue::U8(r)) => Some(self.compare_values(op, *l, *r)),
            (CircuitValue::U16(l), CircuitValue::U16(r)) => Some(self.compare_values(op, *l, *r)),
            (CircuitValue::U32(l), CircuitValue::U32(r)) => Some(self.compare_values(op, *l, *r)),
            (CircuitValue::U64(l), CircuitValue::U64(r)) => Some(self.compare_values(op, *l, *r)),
            (CircuitValue::Bool(l), CircuitValue::Bool(r)) => match op {
                CompareOperator::Eq => Some(l == r),
                CompareOperator::Ne => Some(l != r),
                _ => None,
            },
            _ => None,
        }
    }

    /// Compare two ordered values with a comparison operator
    fn compare_values<T: PartialOrd + PartialEq>(&self, op: CompareOperator, l: T, r: T) -> bool {
        match op {
            CompareOperator::Eq => l == r,
            CompareOperator::Ne => l != r,
            CompareOperator::Lt => l < r,
            CompareOperator::Le => l <= r,
            CompareOperator::Gt => l > r,
            CompareOperator::Ge => l >= r,
        }
    }

    /// Collect the set of variable names that are actually used in the circuit tree
    pub fn collect_live_variables(&self, node: &CircuitNode) -> HashSet<String> {
        let mut live = HashSet::new();
        self.mark_live_nodes(node, &mut live);
        live
    }

    /// Mark nodes that contribute to the output
    #[allow(clippy::only_used_in_recursion)]
    fn mark_live_nodes(&self, node: &CircuitNode, live_nodes: &mut HashSet<String>) {
        match node {
            CircuitNode::Load(name) => {
                live_nodes.insert(name.clone());
            }

            CircuitNode::Constant(_) | CircuitNode::EncryptedConstant { .. } => {}

            CircuitNode::BinaryOp { left, right, .. } => {
                self.mark_live_nodes(left, live_nodes);
                self.mark_live_nodes(right, live_nodes);
            }

            CircuitNode::UnaryOp { operand, .. } => {
                self.mark_live_nodes(operand, live_nodes);
            }

            CircuitNode::Compare { left, right, .. } => {
                self.mark_live_nodes(left, live_nodes);
                self.mark_live_nodes(right, live_nodes);
            }
            CircuitNode::NaryOp { operands, .. } => {
                for operand in operands {
                    self.mark_live_nodes(operand, live_nodes);
                }
            }
        }
    }

    /// Analyze circuit for parallelization opportunities
    ///
    /// Builds a dependency graph and identifies operations that can run in parallel
    fn analyze_parallelism(&self, circuit: &Circuit) -> Result<DependencyGraph> {
        let mut graph = DependencyGraph::new();
        let mut node_id_map = HashMap::new();
        let mut cse_map = HashMap::new();
        let mut next_id = 0;

        // Build dependency graph with CSE deduplication
        self.build_dependency_graph(
            &circuit.root,
            &mut graph,
            &mut node_id_map,
            &mut cse_map,
            &mut next_id,
        );

        graph.node_count = next_id;

        // Identify parallel groups using level-wise traversal
        graph.parallel_groups = self.identify_parallel_groups(&graph);

        // Find critical path using memoized algorithm
        graph.critical_path = self.find_critical_path(&graph);

        Ok(graph)
    }

    /// Build dependency graph recursively, using CSE map to deduplicate identical subtrees
    #[allow(clippy::only_used_in_recursion)]
    fn build_dependency_graph(
        &self,
        node: &CircuitNode,
        graph: &mut DependencyGraph,
        node_id_map: &mut HashMap<String, NodeId>,
        cse_map: &mut HashMap<u64, NodeId>,
        next_id: &mut usize,
    ) -> NodeId {
        // Check for structural CSE deduplication
        let node_hash = Self::structural_hash(node);
        if let Some(&existing_id) = cse_map.get(&node_hash) {
            return existing_id;
        }

        let current_id = NodeId(*next_id);
        *next_id += 1;
        cse_map.insert(node_hash, current_id);

        match node {
            CircuitNode::Load(name) => {
                node_id_map.insert(name.clone(), current_id);
                graph.dependencies.insert(current_id, Vec::new());
                current_id
            }

            CircuitNode::Constant(_) | CircuitNode::EncryptedConstant { .. } => {
                graph.dependencies.insert(current_id, Vec::new());
                current_id
            }

            CircuitNode::BinaryOp { left, right, .. } => {
                let left_id =
                    self.build_dependency_graph(left, graph, node_id_map, cse_map, next_id);
                let right_id =
                    self.build_dependency_graph(right, graph, node_id_map, cse_map, next_id);
                graph
                    .dependencies
                    .insert(current_id, vec![left_id, right_id]);
                current_id
            }

            CircuitNode::UnaryOp { operand, .. } => {
                let operand_id =
                    self.build_dependency_graph(operand, graph, node_id_map, cse_map, next_id);
                graph.dependencies.insert(current_id, vec![operand_id]);
                current_id
            }

            CircuitNode::Compare { left, right, .. } => {
                let left_id =
                    self.build_dependency_graph(left, graph, node_id_map, cse_map, next_id);
                let right_id =
                    self.build_dependency_graph(right, graph, node_id_map, cse_map, next_id);
                graph
                    .dependencies
                    .insert(current_id, vec![left_id, right_id]);
                current_id
            }

            CircuitNode::NaryOp { operands, .. } => {
                let dep_ids: Vec<NodeId> = operands
                    .iter()
                    .map(|o| self.build_dependency_graph(o, graph, node_id_map, cse_map, next_id))
                    .collect();
                graph.dependencies.insert(current_id, dep_ids);
                current_id
            }
        }
    }

    /// Compute a structural hash for a circuit node (for CSE deduplication)
    fn structural_hash(node: &CircuitNode) -> u64 {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::Hasher;

        let mut hasher = DefaultHasher::new();
        Self::hash_node(node, &mut hasher);
        hasher.finish()
    }

    fn hash_node(node: &CircuitNode, hasher: &mut impl std::hash::Hasher) {
        use std::hash::Hash;
        match node {
            CircuitNode::Load(name) => {
                0u8.hash(hasher);
                name.hash(hasher);
            }
            CircuitNode::Constant(value) => {
                1u8.hash(hasher);
                match value {
                    crate::compute::circuit::CircuitValue::Bool(v) => {
                        0u8.hash(hasher);
                        v.hash(hasher);
                    }
                    crate::compute::circuit::CircuitValue::U8(v) => {
                        1u8.hash(hasher);
                        v.hash(hasher);
                    }
                    crate::compute::circuit::CircuitValue::U16(v) => {
                        2u8.hash(hasher);
                        v.hash(hasher);
                    }
                    crate::compute::circuit::CircuitValue::U32(v) => {
                        3u8.hash(hasher);
                        v.hash(hasher);
                    }
                    crate::compute::circuit::CircuitValue::U64(v) => {
                        4u8.hash(hasher);
                        v.hash(hasher);
                    }
                }
            }
            CircuitNode::EncryptedConstant {
                data,
                original_type,
            } => {
                2u8.hash(hasher);
                data.hash(hasher);
                match original_type {
                    crate::compute::circuit::ConstantType::Integer => 0u8.hash(hasher),
                    crate::compute::circuit::ConstantType::Boolean => 1u8.hash(hasher),
                    crate::compute::circuit::ConstantType::Float => 2u8.hash(hasher),
                    crate::compute::circuit::ConstantType::Bytes => 3u8.hash(hasher),
                }
            }
            CircuitNode::BinaryOp { op, left, right } => {
                3u8.hash(hasher);
                Self::hash_binary_op(*op, hasher);
                Self::hash_node(left, hasher);
                Self::hash_node(right, hasher);
            }
            CircuitNode::UnaryOp { op, operand } => {
                4u8.hash(hasher);
                match op {
                    UnaryOperator::Not => 0u8.hash(hasher),
                    UnaryOperator::Neg => 1u8.hash(hasher),
                }
                Self::hash_node(operand, hasher);
            }
            CircuitNode::Compare { op, left, right } => {
                5u8.hash(hasher);
                match op {
                    CompareOperator::Eq => 0u8.hash(hasher),
                    CompareOperator::Ne => 1u8.hash(hasher),
                    CompareOperator::Lt => 2u8.hash(hasher),
                    CompareOperator::Le => 3u8.hash(hasher),
                    CompareOperator::Gt => 4u8.hash(hasher),
                    CompareOperator::Ge => 5u8.hash(hasher),
                }
                Self::hash_node(left, hasher);
                Self::hash_node(right, hasher);
            }
            CircuitNode::NaryOp { op, operands } => {
                6u8.hash(hasher);
                Self::hash_binary_op(*op, hasher);
                operands.len().hash(hasher);
                for o in operands {
                    Self::hash_node(o, hasher);
                }
            }
        }
    }

    fn hash_binary_op(op: BinaryOperator, hasher: &mut impl std::hash::Hasher) {
        use std::hash::Hash;
        match op {
            BinaryOperator::Add => 0u8.hash(hasher),
            BinaryOperator::Sub => 1u8.hash(hasher),
            BinaryOperator::Mul => 2u8.hash(hasher),
            BinaryOperator::And => 3u8.hash(hasher),
            BinaryOperator::Or => 4u8.hash(hasher),
            BinaryOperator::Xor => 5u8.hash(hasher),
        }
    }

    /// Identify groups of nodes that can execute in parallel
    fn identify_parallel_groups(&self, graph: &DependencyGraph) -> Vec<Vec<NodeId>> {
        let mut levels: HashMap<NodeId, usize> = HashMap::new();
        let mut queue = VecDeque::new();

        // Find all nodes with no dependencies (level 0)
        for (node_id, deps) in &graph.dependencies {
            if deps.is_empty() {
                levels.insert(*node_id, 0);
                queue.push_back(*node_id);
            }
        }

        // Level-wise traversal
        while let Some(node_id) = queue.pop_front() {
            let current_level = levels[&node_id];

            // Find nodes that depend on this node
            for (dependent_id, deps) in &graph.dependencies {
                if deps.contains(&node_id) {
                    // Calculate level for dependent node
                    let max_dep_level = deps
                        .iter()
                        .filter_map(|dep_id| levels.get(dep_id))
                        .max()
                        .copied()
                        .unwrap_or(0);

                    let dependent_level = max_dep_level + 1;

                    if !levels.contains_key(dependent_id) {
                        levels.insert(*dependent_id, dependent_level);
                        queue.push_back(*dependent_id);
                    }
                }
            }
        }

        // Group nodes by level
        let max_level = levels.values().max().copied().unwrap_or(0);
        let mut parallel_groups = vec![Vec::new(); max_level + 1];

        for (node_id, level) in levels {
            parallel_groups[level].push(node_id);
        }

        // Sort each group for deterministic output
        for group in &mut parallel_groups {
            group.sort();
        }

        parallel_groups
    }

    /// Find the critical path (longest dependency chain) using memoization
    fn find_critical_path(&self, graph: &DependencyGraph) -> Vec<NodeId> {
        let mut memo = HashMap::new();

        // Compute longest path length to each node
        for &node_id in graph.dependencies.keys() {
            self.longest_path_to(node_id, graph, &mut memo);
        }

        // Find the node with the maximum path length
        let max_node = graph
            .dependencies
            .keys()
            .max_by_key(|&&id| memo.get(&id).copied().unwrap_or(0));

        let Some(&end_node) = max_node else {
            return Vec::new();
        };

        // Reconstruct path from end_node following max-cost dependencies
        let mut path = Vec::new();
        let mut current = end_node;
        path.push(current);

        loop {
            let deps = match graph.dependencies.get(&current) {
                Some(d) if !d.is_empty() => d,
                _ => break,
            };
            let next = deps
                .iter()
                .max_by_key(|&&dep_id| memo.get(&dep_id).copied().unwrap_or(0))
                .copied();
            match next {
                Some(next_id) if next_id != current => {
                    path.push(next_id);
                    current = next_id;
                }
                _ => break,
            }
        }

        path.reverse();
        path
    }

    /// Memoized computation of longest path from a leaf to `node_id`
    fn longest_path_to(
        &self,
        node_id: NodeId,
        graph: &DependencyGraph,
        memo: &mut HashMap<NodeId, usize>,
    ) -> usize {
        if let Some(&cached) = memo.get(&node_id) {
            return cached;
        }

        let deps = graph
            .dependencies
            .get(&node_id)
            .map(|v| v.as_slice())
            .unwrap_or(&[]);

        let result = if deps.is_empty() {
            1
        } else {
            let max_dep = deps
                .iter()
                .map(|&dep_id| self.longest_path_to(dep_id, graph, memo))
                .max()
                .unwrap_or(0);
            max_dep + 1
        };

        memo.insert(node_id, result);
        result
    }
}

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

#[cfg(test)]
#[path = "optimizer_tests.rs"]
mod tests;