vyre_primitives/graph/
exploded.rs

1//! Exploded supergraph primitive (G3).
2//!
3//! # What this is
4//!
5//! IFDS / IDE reframes interprocedural dataflow as a reachability
6//! problem on the **exploded supergraph**: each `(proc, block,
7//! fact)` triple is a graph vertex, and the edges are the flow
8//! functions (GEN / KILL + summary + call-to-return). Once
9//! expanded, the analysis collapses to a BFS over this graph  -
10//! which is the exact shape
11//! [`crate::graph::csr_forward_traverse`] already handles.
12//!
13//! This module owns the **node encoding**  -  the bit-layout that
14//! packs `(proc_id, block_id, fact_id)` into a single `u32` node id
15//!  -  plus a CPU reference that builds the exploded CSR so tests in
16//! `vyre-libs::dataflow::ifds_gpu` can prove the GPU kernel produces
17//! byte-identical CSR output.
18//!
19//! # Bit layout
20//!
21//! ```text
22//!   bits 31..20   proc_id   (12 bits  -  4096 procedures per module)
23//!   bits 19..10   block_id  (10 bits  -  1024 blocks per procedure)
24//!   bits 9..0     fact_id   (10 bits  -  1024 facts per workgroup;
25//!                            matches FACTS_PER_WORKGROUP and the
26//!                            NFA subgroup sizing)
27//! ```
28//!
29//! This deliberately leaves no room for >4096 procedures in a
30//! single module. Any real codebase that exceeds that split along
31//! a module boundary first  -  doing interprocedural dataflow over
32//! 10 000+ procs in one pass is a different problem that we don't
33//! solve here and shouldn't pretend to.
34//!
35//! # Status
36//!
37//! Node encoding, CSR builder, and tests. The GPU Program wrapper
38//! (the actual kernel that walks edges in parallel) lives in
39//! `vyre-libs::dataflow::ifds_gpu` and composes this encoding with
40//! `csr_forward_traverse`.
41
42#[path = "exploded/abi.rs"]
43mod abi;
44#[path = "exploded/canonicalize.rs"]
45mod canonicalize;
46#[path = "exploded/cpu_ref.rs"]
47mod cpu_ref;
48#[path = "exploded/dispatch_plan.rs"]
49mod dispatch_plan;
50#[path = "exploded/encoding.rs"]
51mod encoding;
52#[path = "exploded/layout.rs"]
53mod layout;
54#[path = "exploded/program_ir.rs"]
55mod program_ir;
56#[path = "exploded/program_key.rs"]
57mod program_key;
58#[path = "exploded/validation.rs"]
59mod validation;
60
61#[cfg(test)]
62#[path = "exploded/tests/mod.rs"]
63mod tests;
64
65pub use abi::{
66    ifds_csr_dispatch_grid, IFDS_CSR_COL_IDX_BUFFER, IFDS_CSR_COL_LEN_BUFFER,
67    IFDS_CSR_EMPTY_DISPATCH_GRID, IFDS_CSR_GEN_BLOCK_BUFFER, IFDS_CSR_GEN_FACT_BUFFER,
68    IFDS_CSR_GEN_PROC_BUFFER, IFDS_CSR_INTER_DST_BLOCK_BUFFER, IFDS_CSR_INTER_DST_PROC_BUFFER,
69    IFDS_CSR_INTER_SRC_BLOCK_BUFFER, IFDS_CSR_INTER_SRC_PROC_BUFFER,
70    IFDS_CSR_INTRA_DST_BLOCK_BUFFER, IFDS_CSR_INTRA_PROC_BUFFER, IFDS_CSR_INTRA_SRC_BLOCK_BUFFER,
71    IFDS_CSR_KILLED_BUFFER, IFDS_CSR_KILL_BLOCK_BUFFER, IFDS_CSR_KILL_FACT_BUFFER,
72    IFDS_CSR_KILL_PROC_BUFFER, IFDS_CSR_ROW_CURSOR_BUFFER, IFDS_CSR_ROW_PTR_BUFFER,
73    IFDS_CSR_WORKGROUP_SIZE, OP_ID,
74};
75pub use canonicalize::{canonicalize_csr_within_rows, canonicalize_csr_within_rows_in_place};
76#[cfg(any(test, feature = "cpu-parity"))]
77pub use cpu_ref::{
78    build_cpu_reference, try_build_cpu_reference, try_build_cpu_reference_into,
79    ExplodedIfdsCpuScratch,
80};
81pub use dispatch_plan::{
82    plan_ifds_csr_dispatch, split_ifds_rule_quads_into, split_ifds_rule_triples_into,
83    IfdsCsrDispatchPlan, IfdsCsrRuleColumns,
84};
85pub use encoding::{
86    decode_node, dense_to_encoded, encode_node, encoded_to_dense, fits, BLOCK_BITS,
87    FACTS_PER_WORKGROUP, FACT_BITS, MAX_BLOCK_ID, MAX_FACT_ID, MAX_PROC_ID, PROC_BITS,
88};
89pub use layout::{
90    IfdsCsrLayout, IfdsCsrProgramCacheKey, IfdsCsrRuleInputFingerprint, IfdsCsrStaticInputKey,
91};
92pub use program_ir::build_ifds_csr_program;
93#[cfg(any(test, feature = "cpu-parity"))]
94pub use program_key::ifds_program_cache_key_from_program;
95pub use validation::{
96    ifds_node_count_checked, ifds_node_count_saturating, max_ifds_col_count,
97    validate_ifds_csr_inputs, validate_ifds_csr_layout, validate_ifds_csr_readback,
98};
vyre_primitives/graph/exploded.rs

vyre_primitives/graph/
exploded.rs
