analyssa 0.1.0

//! Phi node representation for SSA form.
//!
//! Phi nodes are the cornerstone of SSA form — they merge values at control flow
//! join points. When multiple control flow paths converge, a phi node selects
//! which value to use based on which predecessor path was taken.
//!
//! # Semantics
//!
//! A phi node `v3 = phi(v1 from B1, v2 from B2)` means:
//! - If control reached this block from predecessor B1, the phi evaluates to `v1`
//! - If control reached from predecessor B2, the phi evaluates to `v2`
//!
//! Phi nodes have "instantaneous" semantics: all phi nodes at the start of a block
//! are conceptually evaluated simultaneously before any regular instruction executes.
//! This avoids ordering issues when one phi's result feeds into another phi's operand.
//!
//! # Placement Algorithm (Cytron et al.)
//!
//! During SSA construction, phi nodes are placed at dominance frontiers:
//!
//! 1. Compute the dominator tree of the CFG
//! 2. Compute dominance frontiers for each block
//! 3. For each variable, find all blocks that define it
//! 4. Place phi nodes at the dominance frontiers of those definition blocks
//! 5. Prune: skip phi placement for variables not live at the frontier block entry
//!
//! # Block Structure
//!
//! ```text
//! Block B3:
//!   v5 = phi(v1 from B1, v2 from B2)   // Merging values
//!   v6 = add v5, v3
//!   jump B4
//! ```
//!
//! # Invariants
//!
//! - Each phi has exactly one operand per predecessor of its containing block
//! - All operands should have the same type
//! - A phi's result is derived from its `origin` (the original variable being merged)
//! - Phi nodes appear ONLY at block start, before any instructions

use std::fmt;

use crate::ir::variable::{SsaVarId, VariableOrigin};

/// An operand of a phi node - a value coming from a specific predecessor block.
///
/// Each phi operand represents one possible value that could be selected,
/// associated with the predecessor block from which that value comes.
///
/// # Examples
///
/// ```rust
/// use analyssa::ir::{phi::PhiOperand, variable::SsaVarId};
///
/// // Value coming from block 1
/// let var = SsaVarId::from_index(0);
/// let operand = PhiOperand::new(var, 1);
/// assert_eq!(operand.value(), var);
/// assert_eq!(operand.predecessor(), 1);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PhiOperand {
    /// The SSA variable providing the value.
    value: SsaVarId,
    /// The predecessor block from which this value comes.
    predecessor: usize,
}

impl PhiOperand {
    /// Creates a new phi operand.
    ///
    /// # Arguments
    ///
    /// * `value` - The SSA variable providing the value
    /// * `predecessor` - The block index from which this value comes
    #[must_use]
    pub const fn new(value: SsaVarId, predecessor: usize) -> Self {
        Self { value, predecessor }
    }

    /// Returns the SSA variable providing the value.
    #[must_use]
    pub const fn value(&self) -> SsaVarId {
        self.value
    }

    /// Returns the predecessor block index.
    #[must_use]
    pub const fn predecessor(&self) -> usize {
        self.predecessor
    }

    /// Updates the predecessor block index.
    ///
    /// Used when block merging redirects edges, requiring phi operands
    /// to reference the new predecessor instead of the eliminated trampoline.
    pub fn set_predecessor(&mut self, predecessor: usize) {
        self.predecessor = predecessor;
    }
}

impl fmt::Display for PhiOperand {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} from B{}", self.value, self.predecessor)
    }
}

/// A phi node that merges values from multiple control flow predecessors.
///
/// Placed at the beginning of basic blocks with multiple predecessors. Each phi
/// node has one [`PhiOperand`] per predecessor, linking the predecessor block
/// to the SSA variable providing the value along that edge.
///
/// # Invariants
///
/// - Each phi has at most one operand per predecessor (enforced by `set_operand`)
/// - The result variable is defined by this phi node at the block entry
/// - Phi nodes appear before all regular instructions in a block
///
/// # Examples
///
/// ```rust
/// use analyssa::ir::{phi::{PhiNode, PhiOperand}, variable::{SsaVarId, VariableOrigin}};
///
/// let v1 = SsaVarId::from_index(0);
/// let v2 = SsaVarId::from_index(1);
/// let result = SsaVarId::from_index(2);
/// let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
/// phi.add_operand(PhiOperand::new(v1, 1));
/// phi.add_operand(PhiOperand::new(v2, 2));
/// assert_eq!(phi.result(), result);
/// assert_eq!(phi.operand_count(), 2);
/// ```
#[derive(Debug, Clone)]
pub struct PhiNode {
    /// The SSA variable that this phi node defines (its result).
    /// This is the variable that subsequent instructions in this block
    /// should use to read the merged value.
    result: SsaVarId,

    /// The original variable this phi node merges — identifies which
    /// CIL argument or local variable this phi corresponds to. Used
    /// during SSA construction and rebuild for rename grouping.
    origin: VariableOrigin,

    /// Operands, one per predecessor block, each linking a predecessor
    /// to the SSA variable providing the value along that edge.
    operands: Vec<PhiOperand>,
}

impl PhiNode {
    /// Creates a new phi node for the given variable origin.
    ///
    /// The phi node is created with no operands - they must be added
    /// during SSA construction as predecessor blocks are processed.
    ///
    /// # Arguments
    ///
    /// * `result` - The SSA variable that this phi node defines
    /// * `origin` - The original variable (Argument or Local) this phi merges
    #[must_use]
    pub fn new(result: SsaVarId, origin: VariableOrigin) -> Self {
        Self {
            result,
            origin,
            operands: Vec::new(),
        }
    }

    /// Creates a new phi node with pre-allocated operand capacity.
    ///
    /// Use this when the number of predecessors is known in advance
    /// to avoid reallocations.
    ///
    /// # Arguments
    ///
    /// * `result` - The SSA variable that this phi node defines
    /// * `origin` - The original variable this phi merges
    /// * `predecessor_count` - Expected number of predecessor blocks
    #[must_use]
    pub fn with_capacity(
        result: SsaVarId,
        origin: VariableOrigin,
        predecessor_count: usize,
    ) -> Self {
        Self {
            result,
            origin,
            operands: Vec::with_capacity(predecessor_count),
        }
    }

    /// Returns the SSA variable defined by this phi node.
    #[must_use]
    pub const fn result(&self) -> SsaVarId {
        self.result
    }

    /// Returns the original variable origin this phi merges.
    #[must_use]
    pub const fn origin(&self) -> VariableOrigin {
        self.origin
    }

    /// Sets the SSA variable defined by this phi node.
    ///
    /// Used during SSA construction when renaming variables.
    pub fn set_result(&mut self, var: SsaVarId) {
        self.result = var;
    }

    /// Returns the operands of this phi node.
    #[must_use]
    pub fn operands(&self) -> &[PhiOperand] {
        &self.operands
    }

    /// Returns a mutable reference to the operands.
    pub fn operands_mut(&mut self) -> &mut Vec<PhiOperand> {
        &mut self.operands
    }

    /// Adds an operand to this phi node.
    ///
    /// # Arguments
    ///
    /// * `operand` - The phi operand to add
    pub fn add_operand(&mut self, operand: PhiOperand) {
        self.operands.push(operand);
    }

    /// Returns the number of operands.
    #[must_use]
    pub fn operand_count(&self) -> usize {
        self.operands.len()
    }

    /// Returns `true` if this phi node has no operands.
    ///
    /// A phi node with no operands is incomplete and should not appear
    /// in a fully-constructed SSA form.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.operands.is_empty()
    }

    /// Finds the operand coming from the specified predecessor block.
    ///
    /// # Arguments
    ///
    /// * `predecessor` - The block index to look up
    ///
    /// # Returns
    ///
    /// The phi operand if found, or `None` if no operand comes from that predecessor.
    #[must_use]
    pub fn operand_from(&self, predecessor: usize) -> Option<&PhiOperand> {
        self.operands
            .iter()
            .find(|op| op.predecessor == predecessor)
    }

    /// Returns all the SSA variables used by this phi node.
    ///
    /// This is useful for building def-use chains and liveness analysis.
    pub fn used_variables(&self) -> impl Iterator<Item = SsaVarId> + '_ {
        self.operands.iter().map(|op| op.value)
    }

    /// Retains only operands whose predecessor satisfies the predicate.
    pub fn retain_operands<F: Fn(usize) -> bool>(&mut self, pred: F) {
        self.operands.retain(|op| pred(op.predecessor));
    }

    /// Sets the origin of this phi node.
    ///
    /// This is used during local variable optimization to update indices
    /// after unused locals are removed.
    pub fn set_origin(&mut self, origin: VariableOrigin) {
        self.origin = origin;
    }

    /// Sets the operand value for a specific predecessor.
    ///
    /// If an operand from that predecessor already exists, it is updated.
    /// Otherwise, a new operand is added.
    ///
    /// # Arguments
    ///
    /// * `predecessor` - The predecessor block index
    /// * `value` - The SSA variable value from that predecessor
    pub fn set_operand(&mut self, predecessor: usize, value: SsaVarId) {
        if let Some(existing) = self
            .operands
            .iter_mut()
            .find(|op| op.predecessor == predecessor)
        {
            existing.value = value;
        } else {
            self.operands.push(PhiOperand::new(value, predecessor));
        }
    }
}

impl fmt::Display for PhiNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} = phi(", self.result)?;
        for (i, operand) in self.operands.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{operand}")?;
        }
        write!(f, ")")
    }
}

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

    #[test]
    fn test_phi_operand_creation() {
        let v = SsaVarId::from_index(0);
        let operand = PhiOperand::new(v, 2);
        assert_eq!(operand.value(), v);
        assert_eq!(operand.predecessor(), 2);
    }

    #[test]
    fn test_phi_operand_display() {
        let operand = PhiOperand::new(SsaVarId::from_index(3), 1);
        assert_eq!(format!("{operand}"), "v3 from B1");
    }

    #[test]
    fn test_phi_node_creation() {
        let result = SsaVarId::from_index(0);
        let phi = PhiNode::new(result, VariableOrigin::Local(0));
        assert_eq!(phi.result(), result);
        assert_eq!(phi.origin(), VariableOrigin::Local(0));
        assert!(phi.is_empty());
        assert_eq!(phi.operand_count(), 0);
    }

    #[test]
    fn test_phi_node_with_capacity() {
        let result = SsaVarId::from_index(0);
        let phi = PhiNode::with_capacity(result, VariableOrigin::Argument(1), 3);
        assert_eq!(phi.result(), result);
        assert_eq!(phi.origin(), VariableOrigin::Argument(1));
        assert!(phi.is_empty());
    }

    #[test]
    fn test_phi_node_add_operands() {
        let result = SsaVarId::from_index(0);
        let v1 = SsaVarId::from_index(1);
        let v2 = SsaVarId::from_index(2);
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));

        phi.add_operand(PhiOperand::new(v1, 0));
        phi.add_operand(PhiOperand::new(v2, 1));

        assert!(!phi.is_empty());
        assert_eq!(phi.operand_count(), 2);

        let ops = phi.operands();
        assert_eq!(ops[0].value(), v1);
        assert_eq!(ops[0].predecessor(), 0);
        assert_eq!(ops[1].value(), v2);
        assert_eq!(ops[1].predecessor(), 1);
    }

    #[test]
    fn test_phi_node_operand_from() {
        let result = SsaVarId::from_index(0);
        let v1 = SsaVarId::from_index(1);
        let v3 = SsaVarId::from_index(2);
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(v1, 2));
        phi.add_operand(PhiOperand::new(v3, 4));

        assert!(phi.operand_from(2).is_some());
        assert_eq!(phi.operand_from(2).unwrap().value(), v1);

        assert!(phi.operand_from(4).is_some());
        assert_eq!(phi.operand_from(4).unwrap().value(), v3);

        assert!(phi.operand_from(0).is_none());
        assert!(phi.operand_from(99).is_none());
    }

    #[test]
    fn test_phi_node_set_operand_new() {
        let result = SsaVarId::from_index(0);
        let v10 = SsaVarId::from_index(1);
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));

        phi.set_operand(1, v10);
        assert_eq!(phi.operand_count(), 1);
        assert_eq!(phi.operand_from(1).unwrap().value(), v10);
    }

    #[test]
    fn test_phi_node_set_operand_update() {
        let result = SsaVarId::from_index(0);
        let v10 = SsaVarId::from_index(1);
        let v20 = SsaVarId::from_index(2);
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));

        phi.set_operand(1, v10);
        phi.set_operand(1, v20); // Update existing

        assert_eq!(phi.operand_count(), 1);
        assert_eq!(phi.operand_from(1).unwrap().value(), v20);
    }

    #[test]
    fn test_phi_node_used_variables() {
        let result = SsaVarId::from_index(0);
        let v1 = SsaVarId::from_index(1);
        let v2 = SsaVarId::from_index(2);
        let v3 = SsaVarId::from_index(3);
        let mut phi = PhiNode::new(result, VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(v1, 0));
        phi.add_operand(PhiOperand::new(v2, 1));
        phi.add_operand(PhiOperand::new(v3, 2));

        let used: Vec<_> = phi.used_variables().collect();
        assert_eq!(used.len(), 3);
        assert!(used.contains(&v1));
        assert!(used.contains(&v2));
        assert!(used.contains(&v3));
    }

    #[test]
    fn test_phi_node_display() {
        let mut phi = PhiNode::new(SsaVarId::from_index(5), VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(SsaVarId::from_index(1), 0));
        phi.add_operand(PhiOperand::new(SsaVarId::from_index(2), 1));

        let display = format!("{phi}");
        assert_eq!(display, "v5 = phi(v1 from B0, v2 from B1)");
    }

    #[test]
    fn test_phi_node_display_empty() {
        let phi = PhiNode::new(SsaVarId::from_index(3), VariableOrigin::Local(0));
        assert_eq!(format!("{phi}"), "v3 = phi()");
    }

    #[test]
    fn test_phi_node_display_single_operand() {
        let mut phi = PhiNode::new(SsaVarId::from_index(7), VariableOrigin::Local(0));
        phi.add_operand(PhiOperand::new(SsaVarId::from_index(4), 2));
        assert_eq!(format!("{phi}"), "v7 = phi(v4 from B2)");
    }
}