weirflow 0.1.0

//! GPU-native IFDS/IDE driver (G3).
//!
//! # What this does
//!
//! IFDS / IDE reframes interprocedural dataflow as reachability on
//! the **exploded supergraph**: each `(proc, block, fact)` triple
//! is a graph vertex; the analysis reduces to BFS + bitset-fixpoint
//!  -  primitives vyre already owns.
//!
//! The pieces live in
//! [`vyre_primitives::graph::exploded`] (node encoding + CSR
//! builder), [`vyre_primitives::graph::csr_forward_traverse`] (BFS
//! step), and [`vyre_primitives::fixpoint::bitset_fixpoint`]
//! (convergence loop). This module composes them.
//!
//! # Entry points
//!
//! - `solve_cpu`  -  in-process CPU reference. Conformance tests
//!   run this against the GPU output bit-for-bit.
//! - [`solve_borrowed_via`]  -  production solver route: builds the
//!   exploded CSR through GPU dispatch and reuses borrowed ProgramGraph
//!   buffers through the fixpoint loop.
//! - [`ifds_gpu_step`]  -  one BFS step over the exploded supergraph
//!   as a GPU [`Program`]. Caller dispatches this in a loop over
//!   `(frontier_in, frontier_out)` until the frontier stops
//!   growing (classic BFS-to-fixpoint). Allocates the exploded
//!   supergraph's `ProgramGraph` buffers internally  -  the caller
//!   only provides the two frontier buffer names.

#[cfg(test)]
use crate::dispatch_input_cache::OwnedDispatchInputs;
pub use crate::ifds_borrowed_solve::{
    solve_borrowed_many_via, solve_borrowed_many_with_scratch_via, solve_borrowed_via,
    solve_borrowed_with_scratch_via, solve_prepared_borrowed_into_via,
    solve_prepared_borrowed_many_with_scratch_into_via,
    solve_prepared_borrowed_many_with_scratch_via, solve_prepared_borrowed_via,
    solve_prepared_borrowed_with_adapter_scratch_via,
    solve_prepared_borrowed_with_scratch_into_via, solve_prepared_borrowed_with_scratch_via,
    solve_via,
};
#[cfg(any(test, feature = "cpu-parity"))]
#[allow(deprecated)]
pub(crate) use crate::ifds_cpu_oracle::solve_cpu;
#[cfg(test)]
use crate::ifds_csr_prepare::build_exploded_csr_borrowed_into_via;
pub use crate::ifds_csr_prepare::{
    prepare_ifds_csr_borrowed_via, prepare_ifds_csr_borrowed_with_scratch_via,
};
#[cfg(test)]
pub(crate) use crate::ifds_frontier_decode::ifds_words;
pub(crate) use crate::ifds_frontier_decode::try_ifds_words;
pub use crate::ifds_resident_alloc::{
    allocate_resident_ifds_parallel_scratch,
    allocate_resident_ifds_parallel_scratch_with_capacities,
    allocate_resident_ifds_parallel_scratch_with_iterations, allocate_resident_ifds_scratch,
    allocate_resident_ifds_scratch_with_seed_capacity, free_resident_ifds_parallel_scratch,
    free_resident_ifds_scratch, free_resident_prepared_ifds_csr, prepare_ifds_csr_resident_via,
    upload_prepared_ifds_csr_resident,
};
pub use crate::ifds_resident_solve::{
    solve_resident_prepared_many_parallel_via,
    solve_resident_prepared_many_parallel_with_scratch_and_host_into_via,
    solve_resident_prepared_many_parallel_with_scratch_and_host_via,
    solve_resident_prepared_many_parallel_with_scratch_via, solve_resident_prepared_many_via,
    solve_resident_prepared_many_with_scratch_and_host_into_via,
    solve_resident_prepared_many_with_scratch_into_via,
    solve_resident_prepared_many_with_scratch_via, solve_resident_prepared_via,
};
pub use crate::ifds_resident_types::{
    IfdsBorrowedSolveScratch, IfdsPrepareScratch, IfdsResidentDispatch, IfdsSolveScratch,
    PreparedIfdsCsr, ResidentIfdsHostScratch, ResidentIfdsParallelHostScratch,
    ResidentIfdsParallelScratch, ResidentIfdsScratch, ResidentPreparedIfdsCsr,
};
pub use crate::ifds_shape::validate_ifds_problem;
pub use crate::ifds_shape::IfdsShape;
use vyre_foundation::ir::Program;
use vyre_primitives::graph::csr_forward_traverse::csr_forward_traverse;
#[cfg(test)]
use vyre_primitives::graph::exploded::{MAX_BLOCK_ID, MAX_FACT_ID, MAX_PROC_ID};
use vyre_primitives::graph::program_graph::ProgramGraphShape;

/// Stable primitive id for Weir's GPU-native IFDS fixpoint route.
pub const OP_ID: &str = "weir::ifds_gpu";

inventory::submit! {
    vyre_harness::OpEntry::new(
        OP_ID,
        || {
            csr_forward_traverse(
                ProgramGraphShape::new(4, 3),
                "fin",
                "fout",
                u32::MAX,
            )
        },
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            vec![vec![
                to_bytes(&[0, 0, 0, 0]),
                to_bytes(&[0, 1, 2, 3, 3]),
                to_bytes(&[1, 2, 3]),
                to_bytes(&[1, 1, 1]),
                to_bytes(&[0, 0, 0, 0]),
                to_bytes(&[0b0001]),
                to_bytes(&[0b0001]),
            ]]
        }),
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            vec![vec![to_bytes(&[0b0011])]]
        }),
    ).with_category("dataflow")
}

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

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

/// Emit one GPU BFS step over the exploded supergraph.
///
/// The returned [`Program`] reads the `(pg_nodes, pg_edge_offsets,
/// pg_edge_targets, pg_edge_kind_mask, pg_node_tags)` ProgramGraph
/// buffers (preferably populated by dispatching
/// [`build_ifds_csr_program`]) plus the named `frontier_in` bitset,
/// and writes the expanded frontier to `frontier_out`.
///
/// Convergence is a host loop: repeatedly dispatch this Program
/// alternating the two frontier buffers; when a dispatch produces
/// no new bits, fixpoint is reached.
///
/// `allow_mask = u32::MAX` accepts every edge kind  -  the exploded
/// supergraph does not differentiate edge kinds, so that is the
/// right choice.
pub fn ifds_gpu_step(
    shape: IfdsShape,
    frontier_in: &str,
    frontier_out: &str,
) -> Result<Program, String> {
    if !shape.fits() {
        return Err(format!(
            "Fix: ifds_gpu_step dimensions exceed 32-bit exploded-node encoding: procs={} blocks={} facts={}",
            shape.num_procs, shape.blocks_per_proc, shape.facts_per_proc
        ));
    }
    let domain = shape.node_domain()?;
    let pg_shape = ProgramGraphShape::new(domain.element_count(), shape.edge_count);
    Ok(csr_forward_traverse(
        pg_shape,
        frontier_in,
        frontier_out,
        u32::MAX,
    ))
}

/// Backwards-compatible three-string shim over [`ifds_gpu_step`].
/// The `_exploded_adj` argument is the ProgramGraph's
/// `pg_edge_targets` buffer; it is ignored here because the step
/// kernel binds `pg_edge_*` at the canonical names. Kept so older
/// call sites compile unchanged.
pub fn ifds_gpu(
    _exploded_adj: &str,
    frontier_in: &str,
    frontier_out: &str,
) -> Result<Program, String> {
    ifds_gpu_step(
        IfdsShape {
            num_procs: 1,
            blocks_per_proc: 1,
            facts_per_proc: 1,
            edge_count: 1,
        },
        frontier_in,
        frontier_out,
    )
}

/// Marker type for the GPU-native IFDS dataflow primitive.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct IfdsGpu;

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

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

#[cfg(test)]
#[allow(deprecated)]
#[path = "ifds_gpu_core_tests/mod.rs"]
mod tests;

#[cfg(test)]
#[path = "ifds_resident_solve_tests/mod.rs"]
mod resident_tests;