dotscope 0.7.0

//! PHI node analysis and placement utilities.
//!
//! This module provides utilities for PHI nodes in SSA form:
//!
//! - [`PhiAnalyzer`] - Identifies patterns like trivial PHIs (single unique source),
//!   uniform constants (all operands resolve to the same value), and finding PHI definitions.
//! - [`place_pruned_phis`] - Shared pruned phi placement algorithm used by both
//!   `SsaConverter` (initial construction) and `SsaRebuilder` (repair).
//!
//! # Example
//!
//! ```rust,ignore
//! use dotscope::analysis::{PhiAnalyzer, ConstEvaluator, SsaFunction};
//!
//! let analyzer = PhiAnalyzer::new(&ssa);
//!
//! // Check if a PHI is trivial (has single unique non-self source)
//! if let Some(source) = analyzer.is_trivial(phi) {
//!     println!("PHI can be replaced with copy from {:?}", source);
//! }
//!
//! // Check if all PHI operands resolve to the same constant
//! let mut evaluator = ConstEvaluator::new(&ssa, PointerSize::Bit64);
//! if let Some(value) = analyzer.uniform_constant(phi, &mut evaluator) {
//!     println!("PHI always produces: {:?}", value);
//! }
//! ```

use std::collections::{BTreeMap, BTreeSet};

use crate::{
    analysis::ssa::{
        ConstEvaluator, ConstValue, PhiNode, PhiOperand, SsaBlock, SsaFunction, SsaOp, SsaVarId,
        VariableOrigin,
    },
    utils::{graph::NodeId, BitSet},
};

/// Analyzes PHI nodes for various patterns.
///
/// This struct provides methods for common PHI node analysis tasks:
/// - Detecting trivial PHIs that can be replaced with copies
/// - Finding PHIs where all operands resolve to the same constant
/// - Looking up PHI operands by predecessor block
/// - Finding the PHI node that defines a variable
pub struct PhiAnalyzer<'a> {
    /// Reference to the SSA function being analyzed.
    ssa: &'a SsaFunction,
}

impl<'a> PhiAnalyzer<'a> {
    /// Creates a new PHI analyzer for the given SSA function.
    ///
    /// # Arguments
    ///
    /// * `ssa` - The SSA function to analyze.
    #[must_use]
    pub fn new(ssa: &'a SsaFunction) -> Self {
        Self { ssa }
    }

    /// Returns a reference to the SSA function being analyzed.
    #[must_use]
    pub fn ssa(&self) -> &SsaFunction {
        self.ssa
    }

    /// Checks if a PHI is trivial (has a single unique non-self source).
    ///
    /// A trivial PHI can be replaced with a simple copy operation.
    /// This occurs when all non-self-referential operands point to the
    /// same source variable.
    ///
    /// # Arguments
    ///
    /// * `phi` - The PHI node to analyze.
    ///
    /// # Returns
    ///
    /// `Some(source)` if the PHI has exactly one unique non-self source,
    /// `None` otherwise.
    ///
    /// # Examples
    ///
    /// ```text
    /// // Trivial PHI (can be replaced with: result = v1)
    /// result = phi(v1, v1, result)  // Returns Some(v1)
    ///
    /// // Non-trivial PHI (multiple different sources)
    /// result = phi(v1, v2)  // Returns None
    ///
    /// // Non-trivial PHI (only self-references, unreachable)
    /// result = phi(result, result)  // Returns None
    /// ```
    #[must_use]
    pub fn is_trivial(&self, phi: &PhiNode) -> Option<SsaVarId> {
        let result = phi.result();

        // Collect non-self-referential operands
        let unique_sources: BTreeSet<SsaVarId> = phi
            .operands()
            .iter()
            .map(PhiOperand::value)
            .filter(|&v| v != result)
            .collect();

        // Trivial if exactly one unique non-self source
        if unique_sources.len() == 1 {
            let source = unique_sources.into_iter().next()?;

            // Check if replacing result with source would create a self-referential instruction.
            if self.ssa.would_create_self_reference(source, result) {
                return None;
            }

            Some(source)
        } else {
            None
        }
    }

    /// Checks if a PHI is fully self-referential (all operands reference the PHI's result).
    ///
    /// A fully self-referential PHI indicates unreachable code or undefined behavior,
    /// since there's no external value entering the PHI. Such PHIs can be safely removed.
    ///
    /// # Arguments
    ///
    /// * `phi` - The PHI node to analyze.
    ///
    /// # Returns
    ///
    /// `true` if all operands reference the PHI's own result variable, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```text
    /// // Fully self-referential (returns true)
    /// result = phi(result, result)
    ///
    /// // Not fully self-referential (returns false)
    /// result = phi(v1, result)
    /// result = phi(v1, v2)
    /// ```
    #[must_use]
    pub fn is_fully_self_referential(&self, phi: &PhiNode) -> bool {
        let result = phi.result();
        !phi.operands().is_empty() && phi.operands().iter().all(|op| op.value() == result)
    }

    /// Analyzes a PHI to determine its trivial status.
    ///
    /// This is the comprehensive analysis method that distinguishes between:
    /// - Trivial PHIs with a single replacement value
    /// - Fully self-referential PHIs that should be removed
    /// - Non-trivial PHIs that must be kept
    ///
    /// # Arguments
    ///
    /// * `phi` - The PHI node to analyze.
    ///
    /// # Returns
    ///
    /// - `Some(Some(var))` - PHI is trivial, can be replaced with `var`
    /// - `Some(None)` - PHI is fully self-referential, can be removed
    /// - `None` - PHI is not trivial, must be kept
    #[must_use]
    pub fn analyze_trivial(&self, phi: &PhiNode) -> Option<Option<SsaVarId>> {
        // Check if trivial with a replacement value
        if let Some(source) = self.is_trivial(phi) {
            return Some(Some(source));
        }

        // Check if fully self-referential (can be removed)
        if self.is_fully_self_referential(phi) {
            return Some(None);
        }

        // Not trivial
        None
    }

    /// Finds all trivial PHI nodes in the SSA function.
    ///
    /// Scans all reachable blocks for PHI nodes that are either:
    /// - Trivial with a single replacement value
    /// - Fully self-referential and can be removed
    ///
    /// # Arguments
    ///
    /// * `reachable` - Set of reachable block indices to scan.
    ///
    /// # Returns
    ///
    /// A vector of `(block_idx, phi_idx, replacement)` tuples where:
    /// - `replacement = Some(var)` - PHI can be replaced with `var`
    /// - `replacement = None` - PHI is fully self-referential and can be removed
    #[must_use]
    pub fn find_all_trivial(
        &self,
        reachable: &BTreeSet<usize>,
    ) -> Vec<(usize, usize, Option<SsaVarId>)> {
        let mut trivial = Vec::new();

        for &block_idx in reachable {
            if let Some(block) = self.ssa.block(block_idx) {
                for (phi_idx, phi) in block.phi_nodes().iter().enumerate() {
                    if let Some(replacement) = self.analyze_trivial(phi) {
                        trivial.push((block_idx, phi_idx, replacement));
                    }
                }
            }
        }

        trivial
    }

    /// Collects all copy-like operations in the SSA function.
    ///
    /// This method identifies all operations that are effectively copies:
    /// - Explicit `Copy` instructions: `dest = copy src`
    /// - Trivial phi nodes: `dest = phi(src, src, ...)` where all non-self operands are identical
    ///
    /// This is the unified entry point for copy detection, used by copy propagation
    /// and other optimizations that need to identify copy relationships.
    ///
    /// # Returns
    ///
    /// A map from each copy destination to its immediate source.
    ///
    /// # Example
    ///
    /// ```text
    /// // Given:
    /// v1 = copy v0           // Explicit copy
    /// v2 = phi(v0, v0)       // Trivial phi (all same source)
    /// v3 = phi(v0, v3)       // Trivial phi (self-ref excluded)
    /// v4 = phi(v0, v1)       // Non-trivial (different sources)
    ///
    /// // Returns: {v1 → v0, v2 → v0, v3 → v0}
    /// ```
    #[must_use]
    pub fn collect_all_copies(&self) -> BTreeMap<SsaVarId, SsaVarId> {
        let mut copies = BTreeMap::new();

        for block in self.ssa.blocks() {
            // Collect explicit copy instructions
            for instr in block.instructions() {
                if let SsaOp::Copy { dest, src } = instr.op() {
                    copies.insert(*dest, *src);
                }
            }

            // Collect trivial phi nodes (effectively copies)
            for phi in block.phi_nodes() {
                if let Some(source) = self.is_trivial(phi) {
                    copies.insert(phi.result(), source);
                }
            }
        }

        copies
    }

    /// Checks if all PHI operands resolve to the same constant.
    ///
    /// This is useful for detecting PHIs that always produce the same value,
    /// which can be replaced with a constant assignment.
    ///
    /// # Arguments
    ///
    /// * `phi` - The PHI node to analyze.
    /// * `evaluator` - A constant evaluator for resolving operand values.
    ///
    /// # Returns
    ///
    /// `Some(value)` if all operands evaluate to the same constant,
    /// `None` if operands differ, cannot be evaluated, or PHI is empty.
    ///
    /// # Examples
    ///
    /// ```text
    /// // Given: v1 = 42, v2 = 42
    /// result = phi(v1, v2)  // Returns Some(42)
    ///
    /// // Given: v1 = 42, v2 = 99
    /// result = phi(v1, v2)  // Returns None (values differ)
    ///
    /// // Given: v1 = 42, v2 = unknown
    /// result = phi(v1, v2)  // Returns None (v2 not constant)
    /// ```
    pub fn uniform_constant(
        &self,
        phi: &PhiNode,
        evaluator: &mut ConstEvaluator,
    ) -> Option<ConstValue> {
        let operands = phi.operands();

        // Empty PHI has no uniform value
        if operands.is_empty() {
            return None;
        }

        // Get the first operand's constant value
        let first_value = evaluator.evaluate_var(operands[0].value())?;

        // Check that all other operands have the same value
        for operand in operands.iter().skip(1) {
            let value = evaluator.evaluate_var(operand.value())?;
            if value != first_value {
                return None;
            }
        }

        Some(first_value)
    }

    /// Finds the PHI node that defines a variable.
    ///
    /// This delegates to [`SsaFunction::find_phi_defining`] for the actual lookup,
    /// which uses O(1) lookup via the variable's definition site when available.
    ///
    /// # Arguments
    ///
    /// * `var` - The SSA variable ID to find the defining PHI for.
    ///
    /// # Returns
    ///
    /// `Some((block_idx, &PhiNode))` if the variable is defined by a PHI node,
    /// `None` if the variable is not defined by a PHI or doesn't exist.
    #[must_use]
    pub fn find_phi_defining(&self, var: SsaVarId) -> Option<(usize, &PhiNode)> {
        self.ssa.find_phi_defining(var)
    }
}

/// Callback type for resolving Leave targets in exception handler blocks.
pub(crate) type LeaveTargetFn<'a> = dyn Fn(usize, &[SsaBlock]) -> Option<usize> + 'a;

/// Places phi nodes at iterated dominance frontier blocks, pruned by liveness.
///
/// This implements the standard IDF phi placement algorithm from Cytron et al.,
/// with pruning based on liveness analysis (only placing phis where the variable
/// is live-in).
///
/// Data structures are keyed by `u32` group IDs. The `group_to_origin` mapping
/// translates group IDs to `VariableOrigin` values for the created phi nodes.
///
/// # Arguments
///
/// * `blocks` - Mutable slice of SSA blocks to insert phi nodes into
/// * `defs` - Definition sites for each group ID
/// * `live_in` - Liveness information: for each group ID, the set of blocks where it's live-in
/// * `dominance_frontiers` - Precomputed dominance frontiers
/// * `reachable` - Set of reachable block indices (if `None`, all blocks are considered reachable)
/// * `group_filter` - Predicate to select which group IDs to process
/// * `group_to_origin` - Maps group ID to the `VariableOrigin` to use for the phi node
/// * `leave_target_fn` - Optional function to get Leave targets for exception handler blocks
///   (used to add extra phi placement points for handler exits)
///
/// # Returns
/// A list of `(block_idx, group)` pairs for each phi node placed, in the order
/// they were added to each block. This allows callers to associate phi nodes
/// with their rename groups during the rename phase.
#[allow(clippy::too_many_arguments)]
pub(crate) fn place_pruned_phis(
    blocks: &mut [SsaBlock],
    defs: &BTreeMap<u32, BitSet>,
    live_in: &BTreeMap<u32, BitSet>,
    dominance_frontiers: &[BitSet],
    reachable: Option<&BitSet>,
    group_filter: &dyn Fn(u32) -> bool,
    group_to_origin: &dyn Fn(u32) -> VariableOrigin,
    leave_target_fn: Option<&LeaveTargetFn<'_>>,
) -> Vec<(usize, u32)> {
    let block_count = blocks.len();
    let mut placements: Vec<(usize, u32)> = Vec::new();

    for (&group, def_blocks) in defs {
        if !group_filter(group) {
            continue;
        }

        // Compute iterated dominance frontier
        let mut phi_blocks = BitSet::new(block_count);
        let mut worklist: Vec<usize> = def_blocks.iter().collect();

        while let Some(block_idx) = worklist.pop() {
            let node_id = NodeId::new(block_idx);
            if node_id.index() < dominance_frontiers.len() {
                for frontier_idx in dominance_frontiers[node_id.index()].iter() {
                    let is_reachable = reachable.is_none_or(|r| r.contains(frontier_idx));
                    if frontier_idx < block_count && is_reachable && phi_blocks.insert(frontier_idx)
                    {
                        worklist.push(frontier_idx);
                    }
                }
            }

            // For exception handler blocks, use Leave targets as phi placement points
            if let Some(leave_fn) = leave_target_fn {
                if let Some(target) = leave_fn(block_idx, blocks) {
                    let is_reachable = reachable.is_none_or(|r| r.contains(target));
                    if target < block_count && is_reachable && phi_blocks.insert(target) {
                        worklist.push(target);
                    }
                }
            }
        }

        // Pruned SSA: only place phi if variable is live at the frontier block.
        // If no liveness data for this group, place unconditionally (used by
        // converter for Stack origins that don't have liveness tracking).
        let group_live_in = live_in.get(&group);

        for phi_block_idx in phi_blocks.iter() {
            if let Some(live_set) = group_live_in {
                if !live_set.contains(phi_block_idx) {
                    continue;
                }
            }

            if let Some(block) = blocks.get_mut(phi_block_idx) {
                let origin = group_to_origin(group);
                // Phi result IDs are temporary placeholders; they will be replaced
                // during the rename phase with properly allocated variable IDs.
                let phi = PhiNode::new(SsaVarId::PLACEHOLDER, origin);
                block.add_phi(phi);
                placements.push((phi_block_idx, group));
            }
        }
    }

    placements
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeSet;

    use crate::{
        analysis::ssa::{
            ConstEvaluator, ConstValue, DefSite, PhiAnalyzer, PhiNode, PhiOperand, SsaBlock,
            SsaFunction, SsaInstruction, SsaOp, SsaType, SsaVarId, VariableOrigin,
        },
        metadata::typesystem::PointerSize,
    };

    #[test]
    fn test_phi_analyzer_creation() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        // Basic sanity check
        assert_eq!(analyzer.ssa().num_args(), 0);
        assert_eq!(analyzer.ssa().num_locals(), 0);
    }

    #[test]
    fn test_is_trivial_single_source() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source = SsaVarId::from_index(1);

        // phi(v1, v1) - trivial, single unique source
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source, 0));
        phi.add_operand(PhiOperand::new(source, 1));

        assert_eq!(analyzer.is_trivial(&phi), Some(source));
    }

    #[test]
    fn test_is_trivial_with_self_reference() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source = SsaVarId::from_index(1);

        // phi(v1, result, v1) - trivial, self-references are ignored
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source, 0));
        phi.add_operand(PhiOperand::new(result, 1)); // self-reference
        phi.add_operand(PhiOperand::new(source, 2));

        assert_eq!(analyzer.is_trivial(&phi), Some(source));
    }

    #[test]
    fn test_is_trivial_multiple_sources() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source1 = SsaVarId::from_index(1);
        let source2 = SsaVarId::from_index(2);

        // phi(v1, v2) - not trivial, multiple different sources
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source1, 0));
        phi.add_operand(PhiOperand::new(source2, 1));

        assert_eq!(analyzer.is_trivial(&phi), None);
    }

    #[test]
    fn test_is_trivial_only_self_references() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);

        // phi(result, result) - not trivial, only self-references (unreachable)
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(result, 0));
        phi.add_operand(PhiOperand::new(result, 1));

        assert_eq!(analyzer.is_trivial(&phi), None);
    }

    #[test]
    fn test_uniform_constant_same_values() {
        let mut ssa = SsaFunction::new(0, 0);
        let mut block = SsaBlock::new(0);

        // v1 = 42
        let v1_id = ssa.create_variable(
            VariableOrigin::Local(0),
            0,
            DefSite::instruction(0, 0),
            SsaType::Unknown,
        );

        // v2 = 42
        let v2_id = ssa.create_variable(
            VariableOrigin::Local(1),
            0,
            DefSite::instruction(0, 1),
            SsaType::Unknown,
        );

        block.add_instruction(SsaInstruction::synthetic(SsaOp::Const {
            dest: v1_id,
            value: ConstValue::I32(42),
        }));
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Const {
            dest: v2_id,
            value: ConstValue::I32(42),
        }));
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Return { value: None }));
        ssa.add_block(block);

        let analyzer = PhiAnalyzer::new(&ssa);
        let mut evaluator = ConstEvaluator::new(&ssa, PointerSize::Bit64);

        // phi(v1, v2) where both are 42
        let phi_result = SsaVarId::from_index(0);
        let mut phi = PhiNode::new(phi_result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(v1_id, 0));
        phi.add_operand(PhiOperand::new(v2_id, 1));

        assert_eq!(
            analyzer.uniform_constant(&phi, &mut evaluator),
            Some(ConstValue::I32(42))
        );
    }

    #[test]
    fn test_uniform_constant_different_values() {
        let mut ssa = SsaFunction::new(0, 0);
        let mut block = SsaBlock::new(0);

        // v1 = 42
        let v1_id = ssa.create_variable(
            VariableOrigin::Local(0),
            0,
            DefSite::instruction(0, 0),
            SsaType::Unknown,
        );

        // v2 = 99
        let v2_id = ssa.create_variable(
            VariableOrigin::Local(1),
            0,
            DefSite::instruction(0, 1),
            SsaType::Unknown,
        );

        block.add_instruction(SsaInstruction::synthetic(SsaOp::Const {
            dest: v1_id,
            value: ConstValue::I32(42),
        }));
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Const {
            dest: v2_id,
            value: ConstValue::I32(99),
        }));
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Return { value: None }));
        ssa.add_block(block);

        let analyzer = PhiAnalyzer::new(&ssa);
        let mut evaluator = ConstEvaluator::new(&ssa, PointerSize::Bit64);

        // phi(v1, v2) where v1=42 and v2=99
        let phi_result = SsaVarId::from_index(0);
        let mut phi = PhiNode::new(phi_result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(v1_id, 0));
        phi.add_operand(PhiOperand::new(v2_id, 1));

        assert_eq!(analyzer.uniform_constant(&phi, &mut evaluator), None);
    }

    #[test]
    fn test_uniform_constant_empty_phi() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);
        let mut evaluator = ConstEvaluator::new(&ssa, PointerSize::Bit64);

        // Empty PHI
        let phi_result = SsaVarId::from_index(0);
        let phi = PhiNode::new(phi_result, VariableOrigin::Local(0));

        assert_eq!(analyzer.uniform_constant(&phi, &mut evaluator), None);
    }

    #[test]
    fn test_uniform_constant_non_constant_operand() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);
        let mut evaluator = ConstEvaluator::new(&ssa, PointerSize::Bit64);

        // phi(v1, v2) where neither is defined (not constant)
        let phi_result = SsaVarId::from_index(0);
        let v1_id = SsaVarId::from_index(1);
        let v2_id = SsaVarId::from_index(2);

        let mut phi = PhiNode::new(phi_result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(v1_id, 0));
        phi.add_operand(PhiOperand::new(v2_id, 1));

        assert_eq!(analyzer.uniform_constant(&phi, &mut evaluator), None);
    }

    #[test]
    fn test_find_defining_phi() {
        let mut ssa = SsaFunction::new(0, 0);

        // Create a variable defined by a PHI
        let phi_result_id = ssa.create_variable(
            VariableOrigin::Local(0),
            0,
            DefSite::phi(0),
            SsaType::Unknown,
        );

        // Create block with PHI node
        let mut block = SsaBlock::new(0);
        let mut phi = PhiNode::new(phi_result_id, VariableOrigin::Local(0));
        let operand_id = SsaVarId::from_index(0);
        phi.add_operand(PhiOperand::new(operand_id, 1));
        block.add_phi(phi);
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Return { value: None }));
        ssa.add_block(block);

        let analyzer = PhiAnalyzer::new(&ssa);

        // Should find the PHI
        let result = analyzer.find_phi_defining(phi_result_id);
        assert!(result.is_some());
        let (block_idx, found_phi) = result.unwrap();
        assert_eq!(block_idx, 0);
        assert_eq!(found_phi.result(), phi_result_id);
    }

    #[test]
    fn test_find_defining_not_phi() {
        let mut ssa = SsaFunction::new(0, 0);
        let mut block = SsaBlock::new(0);

        // Create a variable defined by a regular instruction (not PHI)
        let var_id = ssa.create_variable(
            VariableOrigin::Local(0),
            0,
            DefSite::instruction(0, 0),
            SsaType::Unknown,
        );

        block.add_instruction(SsaInstruction::synthetic(SsaOp::Const {
            dest: var_id,
            value: ConstValue::I32(42),
        }));
        block.add_instruction(SsaInstruction::synthetic(SsaOp::Return { value: None }));
        ssa.add_block(block);

        let analyzer = PhiAnalyzer::new(&ssa);

        // Should not find a PHI (variable is defined by Const, not PHI)
        assert!(analyzer.find_phi_defining(var_id).is_none());
    }

    #[test]
    fn test_is_fully_self_referential_true() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);

        // phi(result, result) - fully self-referential
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(result, 0));
        phi.add_operand(PhiOperand::new(result, 1));

        assert!(analyzer.is_fully_self_referential(&phi));
    }

    #[test]
    fn test_is_fully_self_referential_false() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source = SsaVarId::from_index(1);

        // phi(source, result) - not fully self-referential
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source, 0));
        phi.add_operand(PhiOperand::new(result, 1));

        assert!(!analyzer.is_fully_self_referential(&phi));
    }

    #[test]
    fn test_is_fully_self_referential_empty() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);

        // Empty phi - not fully self-referential
        let phi = PhiNode::new(result, VariableOrigin::Local(0));

        assert!(!analyzer.is_fully_self_referential(&phi));
    }

    #[test]
    fn test_analyze_trivial_with_replacement() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source = SsaVarId::from_index(1);

        // phi(source, source) - trivial with replacement
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source, 0));
        phi.add_operand(PhiOperand::new(source, 1));

        assert_eq!(analyzer.analyze_trivial(&phi), Some(Some(source)));
    }

    #[test]
    fn test_analyze_trivial_self_referential_removal() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);

        // phi(result, result) - fully self-referential, should be removed
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(result, 0));
        phi.add_operand(PhiOperand::new(result, 1));

        assert_eq!(analyzer.analyze_trivial(&phi), Some(None));
    }

    #[test]
    fn test_analyze_trivial_not_trivial() {
        let ssa = SsaFunction::new(0, 0);
        let analyzer = PhiAnalyzer::new(&ssa);

        let result = SsaVarId::from_index(0);
        let source1 = SsaVarId::from_index(1);
        let source2 = SsaVarId::from_index(2);

        // phi(source1, source2) - not trivial (different sources)
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(source1, 0));
        phi.add_operand(PhiOperand::new(source2, 1));

        assert_eq!(analyzer.analyze_trivial(&phi), None);
    }

    #[test]
    fn test_find_all_trivial() {
        let mut ssa = SsaFunction::new(0, 0);

        // Block 0: entry with trivial phi
        let mut block0 = SsaBlock::new(0);
        let phi_result1 = SsaVarId::from_index(0);
        let source1 = SsaVarId::from_index(1);
        let mut phi1 = PhiNode::new(phi_result1, VariableOrigin::Local(0));
        phi1.add_operand(PhiOperand::new(source1, 1)); // trivial: single source
        block0.add_phi(phi1);
        block0.add_instruction(SsaInstruction::synthetic(SsaOp::Jump { target: 1 }));
        ssa.add_block(block0);

        // Block 1: self-referential phi
        let mut block1 = SsaBlock::new(1);
        let phi_result2 = SsaVarId::from_index(2);
        let mut phi2 = PhiNode::new(phi_result2, VariableOrigin::Local(1));
        phi2.add_operand(PhiOperand::new(phi_result2, 0)); // self-referential
        phi2.add_operand(PhiOperand::new(phi_result2, 1));
        block1.add_phi(phi2);
        block1.add_instruction(SsaInstruction::synthetic(SsaOp::Return { value: None }));
        ssa.add_block(block1);

        let analyzer = PhiAnalyzer::new(&ssa);
        let reachable: BTreeSet<usize> = [0, 1].iter().copied().collect();

        let trivial = analyzer.find_all_trivial(&reachable);

        // Should find 2 trivial PHIs
        assert_eq!(trivial.len(), 2);

        // Block 0, phi 0: trivial with replacement source1
        assert!(trivial.contains(&(0, 0, Some(source1))));

        // Block 1, phi 0: self-referential, no replacement
        assert!(trivial.contains(&(1, 0, None)));
    }
}