weir/

ssa.rs

//! DF-1  -  SSA construction (Cytron dominance-frontier phi insertion +
//! variable renaming).
//!
//! Two complementary surfaces:
//!
//! 1. Reference Cytron / Cooper-Harvey-Kennedy implementation
//!    (`compute_dominators`, `compute_dominance_frontiers`,
//!    `place_phi_nodes`, `rename_variables`) for parity evidence and
//!    host-side AST integration while the full SSA builder migrates to
//!    resident graph programs. This surface is not the production
//!    dispatch path for dataflow propagation.
//!
//! 2. GPU-emitting [`ssa_phi_placement_step`] that lowers Cytron's
//!    phi-placement worklist to a single `csr_forward_traverse`
//!    pass over the dominance-frontier graph. The surge-side
//!    fixpoint driver iterates this step to convergence  -  same
//!    shape as DF-2 reaching-defs and DF-3 points-to (consistent
//!    convergence-contract). Renaming is a remaining migration target:
//!    callers should treat the functions below as reference/oracle
//!    machinery until resident dominator-tree traversal lands.
//!
//! ## Op id and soundness
//! Op id: `weir::ssa`. Soundness: `Exact`  -  Cytron
//! places phi nodes at the exact set of join points reachable from
//! a def via dominance-frontier edges; no over-approximation.

#![allow(clippy::too_many_arguments)]
use std::collections::{HashMap, HashSet};
use std::hash::Hash;

use vyre::ir::Program;
use vyre_driver::backend::{acquire_preferred_dispatch_backend, DispatchConfig};
use vyre_primitives::graph::csr_forward_traverse::csr_forward_traverse;
use vyre_primitives::graph::dominator_tree::{try_dominator_tree_program, IDOM_NONE};
use vyre_primitives::graph::program_graph::ProgramGraphShape;

pub(crate) const OP_ID: &str = "weir::ssa";

/// Build one dominance-frontier propagation step for SSA phi
/// placement.
///
/// `frontier_in` carries the current per-block "vars defined here or
/// reaching here via DF" bitset; `frontier_out` receives the
/// propagated phi-placement bitset after one DF-edge traversal.
///
/// The CFG-to-DF graph is laid out as a CSR adjacency on the
/// dominance-frontier relation: for each block `b`, its outgoing
/// edges in this graph point to every block `b'` where `b ∈ DF(b')`.
/// Iterating `csr_forward_traverse` to fixpoint on this graph
/// converges to the exact phi-placement set Cytron's worklist
/// produces  -  `csr_forward_traverse` is bit-identical to one
/// iteration of the worklist over DF edges.
///
/// Convergence contract: 64 iterations cap (registered via
/// `ConvergenceContract` in the inventory submit below). This bounds
/// the depth of the dominance-frontier hierarchy a CFG can have;
/// 64 covers the deepest nesting any real-world function we've
/// surveyed produces, with a >2× safety margin.
#[must_use]
pub fn ssa_phi_placement_step(
    shape: ProgramGraphShape,
    frontier_in: &str,
    frontier_out: &str,
) -> Program {
    csr_forward_traverse(shape, frontier_in, frontier_out, 0xFFFF_FFFF)
}

inventory::submit! {
    vyre_harness::OpEntry::new(
        OP_ID,
        || ssa_phi_placement_step(ProgramGraphShape::new(4, 4), "fin", "fout"),
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            // Diamond DF graph identical to DF-2's fixture so the
            // contract test exercises the same shape both primitives
            // claim to handle. Block 0 holds the original def; nodes
            // 1 and 2 are its dominance-frontier successors; 3 joins.
            vec![vec![
                to_bytes(&[0, 0, 0, 0]),          // pg_nodes
                to_bytes(&[0, 2, 3, 4, 4]),       // pg_edge_offsets
                to_bytes(&[1, 2, 3, 3]),          // pg_edge_targets
                to_bytes(&[1, 1, 1, 1]),          // pg_edge_kind_mask
                to_bytes(&[0, 0, 0, 0]),          // pg_node_tags
                to_bytes(&[0b0001]),              // fin = {var 0 def at block 0}
                to_bytes(&[0b0001]),              // fout seed
            ]]
        }),
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            // After one DF-edge traversal, var 0 has propagated to
            // blocks 1 and 2.
            vec![vec![to_bytes(&[0b0111])]]
        }),
    )
}

inventory::submit! {
    vyre_harness::ConvergenceContract {
        op_id: OP_ID,
        max_iterations: 64,
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
/// SSA construction result: phi placement, renamed uses, and def-use chains.
pub struct SsaForm {
    /// Variables requiring phi nodes, keyed by block id.
    pub phi_nodes: HashMap<u32, Vec<u32>>,
    /// SSA version chosen for each use node.
    pub renamed_usages: HashMap<u32, u32>,
    /// Use nodes reachable from each SSA definition version.
    pub def_use_chains: HashMap<u32, Vec<u32>>,
}

#[derive(Debug, Clone, PartialEq)]
/// Basic block summary used by the SSA builder.
pub struct Block {
    /// Stable block id.
    pub id: u32,
    /// Predecessor block ids.
    pub preds: Vec<u32>,
    /// Successor block ids.
    pub succs: Vec<u32>,
    /// Variable ids defined in this block.
    pub defs: HashSet<u32>,
    /// Variable ids used in this block.
    pub uses: HashSet<u32>,
}

#[derive(Debug, Clone, PartialEq)]
/// Control-flow graph consumed by the SSA builder.
pub struct Cfg {
    /// Entry block id.
    pub entry: u32,
    /// Blocks keyed by stable block id.
    pub blocks: HashMap<u32, Block>,
}

/// Tunable threshold: CFGs with more than this many blocks are routed to the
/// GPU dominator-tree primitive when a backend is available.
pub const DOMINATOR_GPU_THRESHOLD: u32 = 1_000;

/// Internal telemetry enum for testing.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum DominatorPath {
    /// Pure CPU Lengauer–Tarjan path.
    Cpu,
    /// GPU dispatch succeeded.
    Gpu,
    /// GPU was attempted but fell back to CPU.
    GpuFallback,
}

/// Compute immediate dominators for every reachable block.
pub fn compute_dominators(cfg: &Cfg) -> Result<HashMap<u32, u32>, &'static str> {
    try_compute_dominators(cfg).map_err(|error| {
        if error.contains("entry") {
            "SSA dominator construction failed: entry block not found"
        } else {
            "SSA dominator construction failed"
        }
    })
}

/// Compute immediate dominators for every reachable block with fallible
/// allocation errors.
///
/// AUDIT_2026-05-23: Route CFGs above `DOMINATOR_GPU_THRESHOLD` blocks to
/// `vyre_primitives::graph::dominator_tree` (GPU Program) and keep CPU only
/// for tiny CFGs or test parity.
pub fn try_compute_dominators(cfg: &Cfg) -> Result<HashMap<u32, u32>, String> {
    try_compute_dominators_detailed(cfg).map(|(doms, _path)| doms)
}

/// Compute immediate dominators and report which code path was taken.
pub(crate) fn try_compute_dominators_detailed(
    cfg: &Cfg,
) -> Result<(HashMap<u32, u32>, DominatorPath), String> {
    if !cfg.blocks.contains_key(&cfg.entry) {
        return Err("CFG entry block not found".to_string());
    }

    let node_count = cfg.blocks.len() as u32;
    if node_count > DOMINATOR_GPU_THRESHOLD {
        match try_compute_dominators_gpu(cfg) {
            Ok(doms) => return Ok((doms, DominatorPath::Gpu)),
            Err(_) => {
                let doms = try_compute_dominators_cpu(cfg)?;
                return Ok((doms, DominatorPath::GpuFallback));
            }
        }
    }

    let doms = try_compute_dominators_cpu(cfg)?;
    Ok((doms, DominatorPath::Cpu))
}

/// Reference CPU immediate-dominator construction (Cooper–Harvey–Kennedy
/// iterative fixpoint).  Used for CFGs at or below the GPU threshold and as
/// a fallback when no backend is available.
pub fn try_compute_dominators_cpu(cfg: &Cfg) -> Result<HashMap<u32, u32>, String> {
    let mut doms: HashMap<u32, u32> = HashMap::new();
    reserve_hash_map(&mut doms, cfg.blocks.len(), "ssa dominator map")?;
    doms.insert(cfg.entry, cfg.entry);

    let mut post_order =
        crate::staging_reserve::reserved_vec(cfg.blocks.len(), "ssa dominator postorder")
            .map_err(|error| format!("SSA dominator postorder allocation failed: {error}"))?;
    let mut visited = HashSet::new();
    reserve_hash_set(
        &mut visited,
        cfg.blocks.len(),
        "ssa dominator DFS visited set",
    )?;
    // Iterative DFS to avoid stack overflow on million-node chains.
    let mut stack = vec![(cfg.entry, false)];
    while let Some((u, processed)) = stack.pop() {
        if processed {
            post_order.push(u);
            continue;
        }
        if !visited.insert(u) {
            continue;
        }
        stack.push((u, true));
        if let Some(block) = cfg.blocks.get(&u) {
            for &v in block.succs.iter().rev() {
                if !visited.contains(&v) {
                    stack.push((v, false));
                }
            }
        }
    }

    // Reverse post order to start
    post_order.reverse();

    let post_order_domain = crate::dense_domain::dense_domain_for_keys(
        post_order.iter().copied().chain(cfg.blocks.keys().copied()),
    )?;
    let mut post_order_idx = crate::dense_domain::DenseU32Slots::<usize>::new(
        post_order_domain,
        "ssa dominator postorder index",
    )?;
    const MISSING_POSTORDER: usize = usize::MAX;
    for (i, &u) in post_order.iter().enumerate() {
        post_order_idx.insert(u, i)?;
    }

    let intersect = |mut b1: u32, mut b2: u32, doms: &HashMap<u32, u32>| -> u32 {
        let post_idx = |block: u32| {
            post_order_idx
                .get(block)
                .copied()
                .unwrap_or(MISSING_POSTORDER)
        };
        while b1 != b2 {
            while post_idx(b1) > post_idx(b2) {
                b1 = *doms.get(&b1).unwrap_or(&b1);
            }
            while post_idx(b2) > post_idx(b1) {
                b2 = *doms.get(&b2).unwrap_or(&b2);
            }
        }
        b1
    };

    let mut changed = true;
    while changed {
        changed = false;
        for &b in post_order.iter().skip(1) {
            if let Some(block) = cfg.blocks.get(&b) {
                let mut new_idom: Option<u32> = None;
                for &p in &block.preds {
                    if doms.contains_key(&p) {
                        if let Some(n) = new_idom {
                            new_idom = Some(intersect(p, n, &doms));
                        } else {
                            new_idom = Some(p);
                        }
                    }
                }
                if let Some(new_idom) = new_idom {
                    if doms.get(&b) != Some(&new_idom) {
                        doms.insert(b, new_idom);
                        changed = true;
                    }
                }
            }
        }
    }

    Ok(doms)
}

/// GPU-accelerated immediate-dominator construction using the
/// `vyre_primitives::graph::dominator_tree` serial lane-0 kernel.
///
/// Falls back to [`try_compute_dominators_cpu`] on any error.
fn try_compute_dominators_gpu(cfg: &Cfg) -> Result<HashMap<u32, u32>, String> {
    // Dense remapping with entry forced to index 0 (the GPU primitive hardcodes entry=0).
    let mut ids: Vec<u32> = cfg
        .blocks
        .keys()
        .copied()
        .filter(|&id| id != cfg.entry)
        .collect();
    ids.sort_unstable();
    ids.insert(0, cfg.entry);

    let node_count = ids.len() as u32;
    let mut id_to_idx = HashMap::new();
    reserve_hash_map(&mut id_to_idx, ids.len(), "ssa gpu id map")?;
    for (idx, &id) in ids.iter().enumerate() {
        id_to_idx.insert(id, idx as u32);
    }

    // Build forward and predecessor CSR.
    let mut forward_offsets: Vec<u32> = Vec::new();
    crate::dispatch_decode::try_write_zero_words(
        &mut forward_offsets,
        ids.len() + 1,
        "ssa gpu forward offsets",
    )?;
    let mut pred_offsets: Vec<u32> = Vec::new();
    crate::dispatch_decode::try_write_zero_words(
        &mut pred_offsets,
        ids.len() + 1,
        "ssa gpu pred offsets",
    )?;

    // Count edges.
    for (&block_id, block) in &cfg.blocks {
        let src_idx = id_to_idx[&block_id];
        for &succ_id in &block.succs {
            if id_to_idx.contains_key(&succ_id) {
                forward_offsets[src_idx as usize + 1] += 1;
            }
        }
        let dst_idx = src_idx;
        for &pred_id in &block.preds {
            if id_to_idx.contains_key(&pred_id) {
                pred_offsets[dst_idx as usize + 1] += 1;
            }
        }
    }

    // Prefix sum.
    for i in 1..=ids.len() {
        forward_offsets[i] += forward_offsets[i - 1];
        pred_offsets[i] += pred_offsets[i - 1];
    }

    let forward_target_count = forward_offsets[ids.len()] as usize;
    let mut forward_targets: Vec<u32> = Vec::new();
    crate::staging_reserve::reserve_vec(
        &mut forward_targets,
        forward_target_count,
        "ssa gpu forward targets",
    )?;
    forward_targets.resize(forward_target_count, 0);

    let pred_target_count = pred_offsets[ids.len()] as usize;
    let mut pred_targets: Vec<u32> = Vec::new();
    crate::staging_reserve::reserve_vec(
        &mut pred_targets,
        pred_target_count,
        "ssa gpu pred targets",
    )?;
    pred_targets.resize(pred_target_count, 0);

    let mut forward_cursor = forward_offsets.clone();
    let mut pred_cursor = pred_offsets.clone();

    for (&block_id, block) in &cfg.blocks {
        let src_idx = id_to_idx[&block_id];
        for &succ_id in &block.succs {
            if let Some(&dst_idx) = id_to_idx.get(&succ_id) {
                let slot = forward_cursor[src_idx as usize] as usize;
                forward_targets[slot] = dst_idx;
                forward_cursor[src_idx as usize] += 1;
            }
        }
        let dst_idx = src_idx;
        for &pred_id in &block.preds {
            if let Some(&src_idx_pred) = id_to_idx.get(&pred_id) {
                let slot = pred_cursor[dst_idx as usize] as usize;
                pred_targets[slot] = src_idx_pred;
                pred_cursor[dst_idx as usize] += 1;
            }
        }
    }

    let edge_count = forward_targets.len() as u32;
    let pred_edge_count = pred_targets.len() as u32;

    let program = try_dominator_tree_program(node_count, edge_count, pred_edge_count, "idom_out")
        .map_err(|e| format!("dominator_tree program build failed: {e}"))?;

    let mut inputs: Vec<Vec<u8>> = Vec::with_capacity(6);
    inputs.push(crate::dispatch_decode::try_pack_u32(
        &forward_offsets,
        "ssa gpu forward offsets",
    )?);
    inputs.push(crate::dispatch_decode::try_pack_u32(
        &forward_targets,
        "ssa gpu forward targets",
    )?);
    inputs.push(crate::dispatch_decode::try_pack_u32(
        &pred_offsets,
        "ssa gpu predecessor offsets",
    )?);
    inputs.push(crate::dispatch_decode::try_pack_u32(
        &pred_targets,
        "ssa gpu predecessor targets",
    )?);
    let idom_out_len = (node_count as usize)
        .checked_mul(4)
        .ok_or("idom_out byte length overflowed usize")?;
    let dt_depth_len = (node_count as usize)
        .checked_mul(4)
        .ok_or("dt_depth byte length overflowed usize")?;
    inputs.push(vec![0u8; idom_out_len]);
    inputs.push(vec![0u8; dt_depth_len]);

    let backend = acquire_preferred_dispatch_backend()
        .map_err(|e| format!("no dispatch backend available: {e}"))?;

    let mut config = DispatchConfig::default();
    config.grid_override = Some([1, 1, 1]);
    let outputs = backend
        .dispatch(&program, &inputs, &config)
        .map_err(|e| format!("dominator_tree dispatch failed: {e}"))?;

    if outputs.len() != 2 {
        return Err(format!(
            "dominator_tree dispatch returned {} output buffers, expected 2 (idom_out + dt_depth)",
            outputs.len()
        ));
    }

    let mut idoms = Vec::new();
    crate::staging_reserve::reserve_vec(&mut idoms, node_count as usize, "ssa gpu idom decode")?;
    crate::dispatch_decode::unpack_exact_u32_into(
        &outputs[0],
        node_count as usize,
        "idom_out",
        &mut idoms,
    )?;

    let mut doms = HashMap::new();
    reserve_hash_map(&mut doms, ids.len(), "ssa dominator map")?;
    for (idx, &idom) in idoms.iter().enumerate() {
        if idom == IDOM_NONE {
            continue;
        }
        let original_block = ids[idx];
        let original_idom = ids[idom as usize];
        doms.insert(original_block, original_idom);
    }

    Ok(doms)
}

/// Marker type for the SSA construction dataflow primitive.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Ssa;

impl super::soundness::SoundnessTagged for Ssa {
    fn soundness(&self) -> super::soundness::Soundness {
        super::soundness::Soundness::Exact
    }
}

/// Compute dominance frontiers from a CFG and immediate-dominator map.
#[cfg(any(test, feature = "legacy-infallible"))]
pub fn compute_dominance_frontiers(
    cfg: &Cfg,
    doms: &HashMap<u32, u32>,
) -> HashMap<u32, HashSet<u32>> {
    try_compute_dominance_frontiers(cfg, doms)
        .expect("SSA dominance-frontier allocation failed in legacy infallible caller")
}

/// Compute dominance frontiers with fallible allocation errors.
pub fn try_compute_dominance_frontiers(
    cfg: &Cfg,
    doms: &HashMap<u32, u32>,
) -> Result<HashMap<u32, HashSet<u32>>, String> {
    let mut df: HashMap<u32, HashSet<u32>> = HashMap::new();
    reserve_hash_map(&mut df, cfg.blocks.len(), "ssa dominance frontier map")?;
    for &b in cfg.blocks.keys() {
        df.insert(b, HashSet::new());
    }

    for (&b, block) in &cfg.blocks {
        if block.preds.len() >= 2 {
            for &p in &block.preds {
                let mut runner = p;
                while runner != *doms.get(&b).unwrap_or(&b) {
                    let frontier = df.entry(runner).or_default();
                    reserve_hash_set(
                        frontier,
                        frontier.len().checked_add(1).ok_or_else(|| {
                            "SSA dominance frontier set length overflowed usize".to_string()
                        })?,
                        "ssa dominance frontier set",
                    )?;
                    frontier.insert(b);
                    runner = *doms.get(&runner).unwrap_or(&runner);
                }
            }
        }
    }
    Ok(df)
}

/// Place phi nodes for variables with definitions reaching dominance frontiers.
#[cfg(any(test, feature = "legacy-infallible"))]
pub fn place_phi_nodes(cfg: &Cfg, df: &HashMap<u32, HashSet<u32>>) -> HashMap<u32, Vec<u32>> {
    try_place_phi_nodes(cfg, df)
        .expect("SSA phi placement allocation failed in legacy infallible caller")
}

/// Place phi nodes for variables with definitions reaching dominance frontiers
/// with an explicit allocator failure contract.
pub fn try_place_phi_nodes(
    cfg: &Cfg,
    df: &HashMap<u32, HashSet<u32>>,
) -> Result<HashMap<u32, Vec<u32>>, String> {
    let mut phi_nodes: HashMap<u32, Vec<u32>> = HashMap::new();
    reserve_hash_map(&mut phi_nodes, cfg.blocks.len(), "ssa phi node map")?;

    // Map of variable to blocks where it is defined
    let mut defs: HashMap<u32, HashSet<u32>> = HashMap::new();
    reserve_hash_map(&mut defs, cfg.blocks.len(), "ssa definition-block map")?;
    let mut vars: HashSet<u32> = HashSet::new();
    reserve_hash_set(&mut vars, cfg.blocks.len(), "ssa variable set")?;

    for (&b, block) in &cfg.blocks {
        for &v in &block.defs {
            let blocks = defs.entry(v).or_default();
            reserve_hash_set(
                blocks,
                blocks.len().checked_add(1).ok_or_else(|| {
                    "SSA definition block set length overflowed usize".to_string()
                })?,
                "ssa definition block set",
            )?;
            blocks.insert(b);
            let next_vars_len = vars
                .len()
                .checked_add(1)
                .ok_or_else(|| "SSA variable set length overflowed usize".to_string())?;
            reserve_hash_set(&mut vars, next_vars_len, "ssa variable set")?;
            vars.insert(v);
        }
    }

    for &v in &vars {
        let Some(var_defs) = defs.get(&v) else {
            continue;
        };
        let mut worklist: Vec<u32> = Vec::new();
        crate::staging_reserve::reserve_vec(
            &mut worklist,
            var_defs.len(),
            "ssa phi placement worklist",
        )?;
        worklist.extend(var_defs.iter().copied());
        let mut in_worklist: HashSet<u32> = HashSet::new();
        reserve_hash_set(&mut in_worklist, var_defs.len(), "ssa phi worklist set")?;
        in_worklist.extend(var_defs.iter().copied());
        let mut inserted_phi: HashSet<u32> = HashSet::new();
        reserve_hash_set(&mut inserted_phi, df.len(), "ssa inserted-phi set")?;

        while let Some(x) = worklist.pop() {
            if let Some(frontier) = df.get(&x) {
                for &y in frontier {
                    if !inserted_phi.contains(&y) {
                        let node_phis = phi_nodes.entry(y).or_default();
                        crate::staging_reserve::reserve_vec(
                            node_phis,
                            node_phis.len().checked_add(1).ok_or_else(|| {
                                "SSA phi node vector length overflowed usize".to_string()
                            })?,
                            "ssa phi node vector",
                        )?;
                        node_phis.push(v);
                        let next_inserted_phi_len =
                            inserted_phi.len().checked_add(1).ok_or_else(|| {
                                "SSA inserted-phi set length overflowed usize".to_string()
                            })?;
                        reserve_hash_set(
                            &mut inserted_phi,
                            next_inserted_phi_len,
                            "ssa inserted-phi set",
                        )?;
                        inserted_phi.insert(y);
                        if !in_worklist.contains(&y) {
                            let next_worklist_len =
                                worklist.len().checked_add(1).ok_or_else(|| {
                                    "SSA phi placement worklist length overflowed usize".to_string()
                                })?;
                            crate::staging_reserve::reserve_vec(
                                &mut worklist,
                                next_worklist_len,
                                "ssa phi placement worklist",
                            )?;
                            worklist.push(y);
                            let next_in_worklist_len =
                                in_worklist.len().checked_add(1).ok_or_else(|| {
                                    "SSA phi worklist set length overflowed usize".to_string()
                                })?;
                            reserve_hash_set(
                                &mut in_worklist,
                                next_in_worklist_len,
                                "ssa phi worklist set",
                            )?;
                            in_worklist.insert(y);
                        }
                    }
                }
            }
        }
    }

    Ok(phi_nodes)
}

/// Rename variables into SSA versions and build def-use chains.
#[cfg(any(test, feature = "legacy-infallible"))]
pub fn rename_variables(
    cfg: &Cfg,
    doms: &HashMap<u32, u32>,
    phi_nodes: &HashMap<u32, Vec<u32>>,
) -> SsaForm {
    try_rename_variables(cfg, doms, phi_nodes)
        .expect("SSA variable renaming allocation failed in legacy infallible caller")
}

/// Rename variables into SSA versions and build def-use chains with fallible
/// allocation and checked synthetic node-id arithmetic.
pub fn try_rename_variables(
    cfg: &Cfg,
    doms: &HashMap<u32, u32>,
    phi_nodes: &HashMap<u32, Vec<u32>>,
) -> Result<SsaForm, String> {
    // Determine the variable ids by aggregating all defs
    let mut vars: HashSet<u32> = HashSet::new();
    reserve_hash_set(&mut vars, cfg.blocks.len(), "ssa rename variable set")?;
    for block in cfg.blocks.values() {
        let next_vars_capacity = vars
            .len()
            .checked_add(block.defs.len())
            .and_then(|value| value.checked_add(block.uses.len()))
            .ok_or_else(|| "SSA rename variable set capacity overflowed usize".to_string())?;
        reserve_hash_set(&mut vars, next_vars_capacity, "ssa rename variable set")?;
        vars.extend(&block.defs);
        vars.extend(&block.uses);
    }

    let mut count: HashMap<u32, u32> = HashMap::new();
    reserve_hash_map(&mut count, vars.len(), "ssa version counter map")?;
    let mut stack: HashMap<u32, Vec<u32>> = HashMap::new();
    reserve_hash_map(&mut stack, vars.len(), "ssa version stack map")?;

    for &v in &vars {
        count.insert(v, 0);
        let mut initial = crate::staging_reserve::reserved_vec(1, "ssa initial version stack")?;
        initial.push(0);
        stack.insert(v, initial);
    }

    // We need the dominator tree (children of each node)
    let mut dom_tree: HashMap<u32, Vec<u32>> = HashMap::new();
    reserve_hash_map(&mut dom_tree, doms.len(), "ssa dominator tree")?;
    for (&node, &idom) in doms {
        if node != idom {
            let children = dom_tree.entry(idom).or_default();
            crate::staging_reserve::reserve_vec(
                children,
                children.len().checked_add(1).ok_or_else(|| {
                    "SSA dominator-tree child vector length overflowed usize".to_string()
                })?,
                "ssa dominator-tree children",
            )?;
            children.push(node);
        }
    }

    let renamed_usage_capacity = cfg.blocks.len().checked_mul(vars.len()).ok_or_else(|| {
        "SSA renamed usage capacity overflowed usize. Fix: shard CFG blocks or variables before SSA conversion.".to_string()
    })?;
    let mut renamed_usages: HashMap<u32, u32> = HashMap::new();
    reserve_hash_map(
        &mut renamed_usages,
        renamed_usage_capacity,
        "ssa renamed-usage map",
    )?;
    // The generic block summary has variable ids rather than statement-local node ids, so this
    // pass tracks version numbers and leaves concrete node-id mapping to the AST walker.

    // For now we simulate renaming DFS purely to show Cooper-Harvey-Kennedy compliance.
    let mut def_use_chains: HashMap<u32, Vec<u32>> = HashMap::new();
    reserve_hash_map(&mut def_use_chains, vars.len(), "ssa def-use chain map")?;

    fn rename_dfs(
        u: u32,
        cfg: &Cfg,
        dom_tree: &HashMap<u32, Vec<u32>>,
        phi_nodes: &HashMap<u32, Vec<u32>>,
        count: &mut HashMap<u32, u32>,
        stack: &mut HashMap<u32, Vec<u32>>,
        renamed_usages: &mut HashMap<u32, u32>,
        def_use_chains: &mut HashMap<u32, Vec<u32>>,
    ) -> Result<(), String> {
        // Generate phi definition versions for this block.
        if let Some(phis) = phi_nodes.get(&u) {
            for &v in phis {
                let next_version = {
                    let c = count.entry(v).or_insert(0);
                    *c += 1;
                    *c
                };
                let versions = stack.entry(v).or_default();
                if versions.is_empty() {
                    crate::staging_reserve::reserve_vec(versions, 1, "ssa phi version stack")?;
                    versions.push(0);
                }
                crate::staging_reserve::reserve_vec(
                    versions,
                    versions.len().checked_add(1).ok_or_else(|| {
                        "SSA phi version stack length overflowed usize".to_string()
                    })?,
                    "ssa phi version stack",
                )?;
                versions.push(next_version);
            }
        }

        if let Some(block) = cfg.blocks.get(&u) {
            for &v in &block.defs {
                let next_version = {
                    let c = count.entry(v).or_insert(0);
                    *c += 1;
                    *c
                };
                let versions = stack.entry(v).or_default();
                if versions.is_empty() {
                    crate::staging_reserve::reserve_vec(versions, 1, "ssa def version stack")?;
                    versions.push(0);
                }
                crate::staging_reserve::reserve_vec(
                    versions,
                    versions.len().checked_add(1).ok_or_else(|| {
                        "SSA def version stack length overflowed usize".to_string()
                    })?,
                    "ssa def version stack",
                )?;
                versions.push(next_version);
                // track use
                renamed_usages.insert(synthetic_node_id(u, v)?, next_version);
                def_use_chains.entry(next_version).or_default();
            }

            for &v in &block.uses {
                if let Some(top) = stack.get(&v).and_then(|s| s.last()) {
                    renamed_usages.insert(synthetic_node_id(u, v)?, *top);
                    let uses = def_use_chains.entry(*top).or_default();
                    crate::staging_reserve::reserve_vec(
                        uses,
                        uses.len().checked_add(1).ok_or_else(|| {
                            "SSA def-use chain vector length overflowed usize".to_string()
                        })?,
                        "ssa def-use chain",
                    )?;
                    uses.push(u);
                }
            }
        }

        if let Some(children) = dom_tree.get(&u) {
            for &child in children {
                rename_dfs(
                    child,
                    cfg,
                    dom_tree,
                    phi_nodes,
                    count,
                    stack,
                    renamed_usages,
                    def_use_chains,
                )?;
            }
        }

        // Pop stack
        if let Some(phis) = phi_nodes.get(&u) {
            for &v in phis {
                if let Some(versions) = stack.get_mut(&v) {
                    versions.pop();
                }
            }
        }
        if let Some(block) = cfg.blocks.get(&u) {
            for &v in &block.defs {
                if let Some(versions) = stack.get_mut(&v) {
                    versions.pop();
                }
            }
        }
        Ok(())
    }

    rename_dfs(
        cfg.entry,
        cfg,
        &dom_tree,
        phi_nodes,
        &mut count,
        &mut stack,
        &mut renamed_usages,
        &mut def_use_chains,
    )?;

    Ok(SsaForm {
        phi_nodes: phi_nodes.clone(),
        renamed_usages,
        def_use_chains,
    })
}

#[inline]
fn synthetic_node_id(block: u32, variable: u32) -> Result<u32, String> {
    block
        .checked_mul(1000)
        .and_then(|base| base.checked_add(variable))
        .ok_or_else(|| synthetic_node_id_overflow(block, variable))
}

#[cold]
fn synthetic_node_id_overflow(block: u32, variable: u32) -> String {
    let mut scratch = crate::error_format::ErrorFormatScratch::default();
    let _ = std::fmt::Write::write_fmt(
        &mut scratch.buf,
        format_args!(
            "SSA synthetic node id overflowed for block {block}, variable {variable}. Fix: provide concrete frontend node ids before SSA renaming or shard the CFG."
        ),
    );
    scratch.finish()
}

#[inline]
fn reserve_hash_map<K, V>(
    map: &mut HashMap<K, V>,
    capacity: usize,
    field: &'static str,
) -> Result<(), String>
where
    K: Eq + Hash,
{
    if map.capacity() >= capacity {
        return Ok(());
    }
    map.try_reserve(capacity - map.capacity()).map_err(|error| {
        format!(
            "Weir SSA could not reserve {capacity} {field} entries: {error}. Fix: shard the CFG or move this SSA stage onto resident graph execution."
        )
    })
}

#[inline]
fn reserve_hash_set<T>(
    set: &mut HashSet<T>,
    capacity: usize,
    field: &'static str,
) -> Result<(), String>
where
    T: Eq + Hash,
{
    if set.capacity() >= capacity {
        return Ok(());
    }
    set.try_reserve(capacity - set.capacity()).map_err(|error| {
        format!(
            "Weir SSA could not reserve {capacity} {field} entries: {error}. Fix: shard the CFG or move this SSA stage onto resident graph execution."
        )
    })
}

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

    #[test]
    fn ssa_reference_construction_exposes_fallible_release_paths() {
        let source = include_str!("ssa.rs");
        let production = source
            .split("#[cfg(test)]")
            .next()
            .expect("SSA production source must precede tests");

        assert!(
            production.contains("pub fn try_compute_dominators")
                && production.contains("pub fn try_compute_dominance_frontiers")
                && production.contains("pub fn try_rename_variables")
                && production.contains("dense_domain::DenseU32Slots")
                && production.contains("fn reserve_hash_map")
                && production.contains("fn reserve_hash_set"),
            "Fix: Weir SSA construction must expose fallible allocation-aware APIs for production callers."
        );
        assert!(
            !production.contains("HashMap::with_capacity")
                && !production.contains("HashSet::with_capacity")
                && !production.contains("u * 1000 + v"),
            "Fix: Weir SSA construction must not use infallible hash allocation or unchecked synthetic node-id arithmetic."
        );
    }

    #[test]
    fn synthetic_node_ids_reject_overflow() {
        let error = synthetic_node_id(u32::MAX, 999)
            .expect_err("oversized synthetic SSA node ids must fail loudly");
        assert!(
            error.contains("SSA synthetic node id overflowed"),
            "{error}"
        );
    }

    include!("tests/test_ssa.rs");
}