Module exploded 

Exploded-supergraph builder - (CFG × fact) pairs as graph vertices so IFDS/IDE reduces to csr_forward_traverse. Exploded supergraph primitive (G3).

What this is

IFDS / IDE reframes interprocedural dataflow as a reachability problem on the exploded supergraph: each (proc, block, fact) triple is a graph vertex, and the edges are the flow functions (GEN / KILL + summary + call-to-return). Once expanded, the analysis collapses to a BFS over this graph - which is the exact shape crate::graph::csr_forward_traverse already handles.

This module owns the node encoding - the bit-layout that packs (proc_id, block_id, fact_id) into a single u32 node id

• plus a CPU reference that builds the exploded CSR so tests in vyre-libs::dataflow::ifds_gpu can prove the GPU kernel produces byte-identical CSR output.

Bit layout

  bits 31..20   proc_id   (12 bits  -  4096 procedures per module)
  bits 19..10   block_id  (10 bits  -  1024 blocks per procedure)
  bits 9..0     fact_id   (10 bits  -  1024 facts per workgroup;
                           matches FACTS_PER_WORKGROUP and the
                           NFA subgroup sizing)

This deliberately leaves no room for >4096 procedures in a single module. Any real codebase that exceeds that split along a module boundary first - doing interprocedural dataflow over 10 000+ procs in one pass is a different problem that we don’t solve here and shouldn’t pretend to.

Status

Node encoding, CSR builder, and tests. The GPU Program wrapper (the actual kernel that walks edges in parallel) lives in vyre-libs::dataflow::ifds_gpu and composes this encoding with csr_forward_traverse.

Structs

ExplodedIfdsCpuScratch

CPU-reference CSR builder for the exploded supergraph.

IfdsCsrDispatchPlan

Primitive-owned dispatch plan for exploded IFDS CSR construction.

IfdsCsrLayout

Checked dispatch layout for an exploded IFDS CSR build.

IfdsCsrProgramCacheKey

Primitive-owned cache identity for exploded IFDS CSR construction Programs.

IfdsCsrRuleColumns

Caller-owned structure-of-arrays rule columns for IFDS CSR dispatch.

IfdsCsrRuleInputFingerprint

Stable identity for IFDS rule tuples supplied to the CSR builder.

IfdsCsrStaticInputKey

Primitive-owned identity for reusable exploded IFDS static inputs.

Constants

BLOCK_BITS

Bits reserved for the basic-block component of the packed node id.

FACTS_PER_WORKGROUP

Number of facts per workgroup lane. A 32-lane subgroup x 32 bits = 1024 facts; wider subgroup layouts preserve the same budget. Matches the NFA window sizing in nfa::subgroup_nfa so both subsystems share occupancy budget.

FACT_BITS

Bits reserved for the fact component of the packed node id.

IFDS_CSR_COL_IDX_BUFFER

Canonical dispatch output label for CSR column indices.

IFDS_CSR_COL_LEN_BUFFER

Canonical dispatch output label for emitted column length.

IFDS_CSR_EMPTY_DISPATCH_GRID

Minimum grid for empty no-rule IFDS dispatch plans.

IFDS_CSR_GEN_BLOCK_BUFFER

Canonical dispatch input label for GEN rule blocks.

IFDS_CSR_GEN_FACT_BUFFER

Canonical dispatch input label for GEN rule facts.

IFDS_CSR_GEN_PROC_BUFFER

Canonical dispatch input label for GEN rule procedures.

IFDS_CSR_INTER_DST_BLOCK_BUFFER

Canonical dispatch input label for inter-procedural destination blocks.

IFDS_CSR_INTER_DST_PROC_BUFFER

Canonical dispatch input label for inter-procedural destination procedures.

IFDS_CSR_INTER_SRC_BLOCK_BUFFER

Canonical dispatch input label for inter-procedural source blocks.

IFDS_CSR_INTER_SRC_PROC_BUFFER

Canonical dispatch input label for inter-procedural source procedures.

IFDS_CSR_INTRA_DST_BLOCK_BUFFER

Canonical dispatch input label for intra-procedural destination blocks.

IFDS_CSR_INTRA_PROC_BUFFER

Canonical dispatch input label for intra-procedural procedure ids.

IFDS_CSR_INTRA_SRC_BLOCK_BUFFER

Canonical dispatch input label for intra-procedural source blocks.

IFDS_CSR_KILLED_BUFFER

Canonical dispatch scratch label for the dense kill bitmap.

IFDS_CSR_KILL_BLOCK_BUFFER

Canonical dispatch input label for KILL rule blocks.

IFDS_CSR_KILL_FACT_BUFFER

Canonical dispatch input label for KILL rule facts.

IFDS_CSR_KILL_PROC_BUFFER

Canonical dispatch input label for KILL rule procedures.

IFDS_CSR_ROW_CURSOR_BUFFER

Canonical dispatch scratch label for row cursors.

IFDS_CSR_ROW_PTR_BUFFER

Canonical dispatch output label for CSR row pointers.

IFDS_CSR_WORKGROUP_SIZE

Serial workgroup for exploded IFDS CSR construction.

MAX_BLOCK_ID

Maximum encodable basic-block id.

MAX_FACT_ID

Maximum encodable fact id.

MAX_PROC_ID

Max values for each component - one less than the available space because zero is a valid id.

OP_ID

Canonical op id for the IFDS CSR construction program.

PROC_BITS

Bits reserved for each component of the packed node id.

Functions

build_cpu_reference

Returns (row_ptr, col_idx) in the dense index space idx(p, b, f) = p * blocks * facts + b * facts + f. This is the space every traversal kernel operates in - packing via crate::graph::exploded::encode_node is only used at the I/O boundary when the caller needs to report results as (proc, block, fact) triples. The two spaces coincide only in the degenerate case blocks_per_proc == 1 << BLOCK_BITS and facts_per_proc == 1 << FACT_BITS; the dense layout works for any dimensions that fit in 32-bit encoding.

build_ifds_csr_program

Build a GPU Program that emits the exploded-supergraph CSR.

canonicalize_csr_within_rows

Return a row-canonical CSR copy.

canonicalize_csr_within_rows_in_place

Sort each CSR row in place after validating row ranges.

decode_node

Unpack a node id back into (proc_id, block_id, fact_id).

dense_to_encoded

Convert a dense (proc, block, fact) index - the space build_cpu_reference (requires the cpu-parity feature) operates in - into the packed encode_node form for reporting or cross-subsystem handoff.

encode_node

Pack a (proc_id, block_id, fact_id) triple into a 32-bit node id.

encoded_to_dense

Inverse of dense_to_encoded.

fits

Whether a (proc, block, fact) triple fits in the packed 32-bit representation. Callers on the production path should verify this before calling encode_node.

ifds_csr_dispatch_grid

Dispatch grid for exploded IFDS CSR construction.

ifds_node_count_checked

Checked exploded-supergraph node count.

ifds_node_count_saturating

Saturating exploded-supergraph node count for capacity planning UIs.

ifds_program_cache_key_from_program

Recover the exploded IFDS program cache key baked into a generated CSR builder Program.

max_ifds_col_count

Maximum column count needed by the deterministic IFDS CSR builder.

plan_ifds_csr_dispatch

Validate caller-owned IFDS rules and return the complete primitive dispatch plan.

split_ifds_rule_quads_into

Split IFDS quadruple rules into primitive-owned structure-of-arrays columns.

split_ifds_rule_triples_into

Split IFDS triple rules into primitive-owned structure-of-arrays columns.

try_build_cpu_reference

Fallible CPU-reference CSR builder for the exploded supergraph.

try_build_cpu_reference_into

Fallible CPU-reference CSR builder into caller-owned output and scratch.

validate_ifds_csr_inputs

Validate the full IFDS CSR dispatch contract from caller-owned rule slices.

validate_ifds_csr_layout

Validate dimensions/counts and return the exact dispatch buffer layout.

validate_ifds_csr_readback

Validate CSR data returned by an exploded IFDS backend.