weir/
ifds_gpu.rs

1//! GPU-native IFDS/IDE driver (G3).
2//!
3//! # What this does
4//!
5//! IFDS / IDE reframes interprocedural dataflow as reachability on
6//! the **exploded supergraph**: each `(proc, block, fact)` triple
7//! is a graph vertex; the analysis reduces to BFS + bitset-fixpoint
8//!  -  primitives vyre already owns.
9//!
10//! The pieces live in
11//! [`vyre_primitives::graph::exploded`] (node encoding + CSR
12//! builder), [`vyre_primitives::graph::csr_forward_traverse`] (BFS
13//! step), and [`vyre_primitives::fixpoint::bitset_fixpoint`]
14//! (convergence loop). This module composes them.
15//!
16//! # Entry points
17//!
18//! - `solve_cpu`  -  in-process CPU reference. Conformance tests
19//!   run this against the GPU output bit-for-bit.
20//! - [`solve_borrowed_via`]  -  production solver route: builds the
21//!   exploded CSR through GPU dispatch and reuses borrowed ProgramGraph
22//!   buffers through the fixpoint loop.
23//! - [`ifds_gpu_step`]  -  one BFS step over the exploded supergraph
24//!   as a GPU [`Program`]. Caller dispatches this in a loop over
25//!   `(frontier_in, frontier_out)` until the frontier stops
26//!   growing (classic BFS-to-fixpoint). Allocates the exploded
27//!   supergraph's `ProgramGraph` buffers internally  -  the caller
28//!   only provides the two frontier buffer names.
29
30#[cfg(test)]
31use crate::dispatch_input_cache::OwnedDispatchInputs;
32pub use crate::ifds_borrowed_solve::{
33    solve_borrowed_many_via, solve_borrowed_many_with_scratch_via, solve_borrowed_via,
34    solve_borrowed_with_scratch_via, solve_prepared_borrowed_into_via,
35    solve_prepared_borrowed_many_with_scratch_into_via,
36    solve_prepared_borrowed_many_with_scratch_via, solve_prepared_borrowed_via,
37    solve_prepared_borrowed_with_adapter_scratch_via,
38    solve_prepared_borrowed_with_scratch_into_via, solve_prepared_borrowed_with_scratch_via,
39    solve_via,
40};
41#[cfg(any(test, feature = "cpu-parity"))]
42#[allow(deprecated)]
43pub(crate) use crate::ifds_cpu_oracle::solve_cpu;
44#[cfg(test)]
45use crate::ifds_csr_prepare::build_exploded_csr_borrowed_into_via;
46pub use crate::ifds_csr_prepare::{
47    prepare_ifds_csr_borrowed_via, prepare_ifds_csr_borrowed_with_scratch_via,
48};
49#[cfg(test)]
50pub(crate) use crate::ifds_frontier_decode::ifds_words;
51pub(crate) use crate::ifds_frontier_decode::try_ifds_words;
52pub use crate::ifds_resident_alloc::{
53    allocate_resident_ifds_parallel_scratch,
54    allocate_resident_ifds_parallel_scratch_with_capacities,
55    allocate_resident_ifds_parallel_scratch_with_iterations, allocate_resident_ifds_scratch,
56    allocate_resident_ifds_scratch_with_seed_capacity, free_resident_ifds_parallel_scratch,
57    free_resident_ifds_scratch, free_resident_prepared_ifds_csr, prepare_ifds_csr_resident_via,
58    upload_prepared_ifds_csr_resident,
59};
60pub use crate::ifds_resident_solve::{
61    solve_resident_prepared_many_parallel_via,
62    solve_resident_prepared_many_parallel_with_scratch_and_host_into_via,
63    solve_resident_prepared_many_parallel_with_scratch_and_host_via,
64    solve_resident_prepared_many_parallel_with_scratch_via, solve_resident_prepared_many_via,
65    solve_resident_prepared_many_with_scratch_and_host_into_via,
66    solve_resident_prepared_many_with_scratch_into_via,
67    solve_resident_prepared_many_with_scratch_via, solve_resident_prepared_via,
68};
69pub use crate::ifds_resident_types::{
70    IfdsBorrowedSolveScratch, IfdsPrepareScratch, IfdsResidentDispatch, IfdsSolveScratch,
71    PreparedIfdsCsr, ResidentIfdsHostScratch, ResidentIfdsParallelHostScratch,
72    ResidentIfdsParallelScratch, ResidentIfdsScratch, ResidentPreparedIfdsCsr,
73};
74pub use crate::ifds_shape::validate_ifds_problem;
75pub use crate::ifds_shape::IfdsShape;
76use vyre_foundation::ir::Program;
77use vyre_primitives::graph::csr_forward_traverse::csr_forward_traverse;
78#[cfg(test)]
79use vyre_primitives::graph::exploded::{MAX_BLOCK_ID, MAX_FACT_ID, MAX_PROC_ID};
80use vyre_primitives::graph::program_graph::ProgramGraphShape;
81
82/// Stable primitive id for Weir's GPU-native IFDS fixpoint route.
83pub const OP_ID: &str = "weir::ifds_gpu";
84
85inventory::submit! {
86    vyre_harness::OpEntry::new(
87        OP_ID,
88        || {
89            csr_forward_traverse(
90                ProgramGraphShape::new(4, 3),
91                "fin",
92                "fout",
93                u32::MAX,
94            )
95        },
96        Some(|| {
97            let to_bytes = crate::dispatch_decode::pack_u32;
98            vec![vec![
99                to_bytes(&[0, 0, 0, 0]),
100                to_bytes(&[0, 1, 2, 3, 3]),
101                to_bytes(&[1, 2, 3]),
102                to_bytes(&[1, 1, 1]),
103                to_bytes(&[0, 0, 0, 0]),
104                to_bytes(&[0b0001]),
105                to_bytes(&[0b0001]),
106            ]]
107        }),
108        Some(|| {
109            let to_bytes = crate::dispatch_decode::pack_u32;
110            vec![vec![to_bytes(&[0b0011])]]
111        }),
112    ).with_category("dataflow")
113}
114
115inventory::submit! {
116    vyre_harness::ConvergenceContract {
117        op_id: OP_ID,
118        max_iterations: 128,
119    }
120}
121
122#[cfg(test)]
123#[path = "ifds_gpu_tests.rs"]
124mod ifds_gpu_tests;
125
126/// Emit one GPU BFS step over the exploded supergraph.
127///
128/// The returned [`Program`] reads the `(pg_nodes, pg_edge_offsets,
129/// pg_edge_targets, pg_edge_kind_mask, pg_node_tags)` ProgramGraph
130/// buffers (preferably populated by dispatching
131/// [`build_ifds_csr_program`]) plus the named `frontier_in` bitset,
132/// and writes the expanded frontier to `frontier_out`.
133///
134/// Convergence is a host loop: repeatedly dispatch this Program
135/// alternating the two frontier buffers; when a dispatch produces
136/// no new bits, fixpoint is reached.
137///
138/// `allow_mask = u32::MAX` accepts every edge kind  -  the exploded
139/// supergraph does not differentiate edge kinds, so that is the
140/// right choice.
141pub fn ifds_gpu_step(
142    shape: IfdsShape,
143    frontier_in: &str,
144    frontier_out: &str,
145) -> Result<Program, String> {
146    if !shape.fits() {
147        return Err(format!(
148            "Fix: ifds_gpu_step dimensions exceed 32-bit exploded-node encoding: procs={} blocks={} facts={}",
149            shape.num_procs, shape.blocks_per_proc, shape.facts_per_proc
150        ));
151    }
152    let domain = shape.node_domain()?;
153    let pg_shape = ProgramGraphShape::new(domain.element_count(), shape.edge_count);
154    Ok(csr_forward_traverse(
155        pg_shape,
156        frontier_in,
157        frontier_out,
158        u32::MAX,
159    ))
160}
161
162/// Backwards-compatible three-string shim over [`ifds_gpu_step`].
163/// The `_exploded_adj` argument is the ProgramGraph's
164/// `pg_edge_targets` buffer; it is ignored here because the step
165/// kernel binds `pg_edge_*` at the canonical names. Kept so older
166/// call sites compile unchanged.
167pub fn ifds_gpu(
168    _exploded_adj: &str,
169    frontier_in: &str,
170    frontier_out: &str,
171) -> Result<Program, String> {
172    ifds_gpu_step(
173        IfdsShape {
174            num_procs: 1,
175            blocks_per_proc: 1,
176            facts_per_proc: 1,
177            edge_count: 1,
178        },
179        frontier_in,
180        frontier_out,
181    )
182}
183
184/// Marker type for the GPU-native IFDS dataflow primitive.
185#[derive(Clone, Copy, Debug, PartialEq, Eq)]
186pub struct IfdsGpu;
187
188impl super::soundness::SoundnessTagged for IfdsGpu {
189    fn soundness(&self) -> super::soundness::Soundness {
190        super::soundness::Soundness::Exact
191    }
192}
193
194impl super::soundness::SoundnessTagged for IfdsShape {
195    fn soundness(&self) -> super::soundness::Soundness {
196        super::soundness::Soundness::Exact
197    }
198}
199
200#[cfg(test)]
201#[allow(deprecated)]
202#[path = "ifds_gpu_core_tests/mod.rs"]
203mod tests;
204
205#[cfg(test)]
206#[path = "ifds_resident_solve_tests/mod.rs"]
207mod resident_tests;
weir/ifds_gpu.rs

weir/
ifds_gpu.rs
