weir/reaching/
program.rs

1use super::OP_ID;
2use vyre::ir::Program;
3use vyre_primitives::graph::csr_forward_traverse::csr_forward_traverse;
4use vyre_primitives::graph::program_graph::ProgramGraphShape;
5
6/// Build one CFG-forward propagation step for reaching-defs.
7///
8/// `frontier_in` reads the current `out[n]` bit-sets across all CFG
9/// nodes (flat; surge stdlib is responsible for laying it out as
10/// `n * defs_per_word` per node). `frontier_out` receives the
11/// propagated `in'[n]` after one CFG-edge traversal.
12///
13/// The `gen[n] ∪ (in[n] − kill[n])` transfer runs on the surge side
14/// as a pointwise pre-union step in the fixpoint driver  -  this keeps
15/// the vyre primitive a single traversal call (same shape as
16/// `flows_to`), which composes cleanly with
17/// `vyre_primitives::bitset` ops for the transfer.
18#[must_use]
19pub fn reaching_defs_step(
20    shape: ProgramGraphShape,
21    frontier_in: &str,
22    frontier_out: &str,
23) -> Program {
24    csr_forward_traverse(shape, frontier_in, frontier_out, 0xFFFF_FFFF)
25}
26
27inventory::submit! {
28    vyre_harness::OpEntry::new(
29        OP_ID,
30        || reaching_defs_step(ProgramGraphShape::new(4, 4), "fin", "fout"),
31        Some(|| {
32            let to_bytes = crate::dispatch_decode::pack_u32;
33            // Diamond CFG  -  four nodes with a join at node 3:
34            //   0 → 1 → 3
35            //   0 → 2 → 3
36            // Reaching-defs start at node 0 with def-set {0b0001}.
37            // After one forward step, def 0 has propagated to nodes 1
38            // and 2 after one propagation step; the join into 3 is reached by
39            // the next fixpoint iteration.
40            vec![vec![
41                to_bytes(&[0, 0, 0, 0]),          // pg_nodes
42                to_bytes(&[0, 2, 3, 4, 4]),       // pg_edge_offsets: 0→{1,2}, 1→{3}, 2→{3}, 3→{}
43                to_bytes(&[1, 2, 3, 3]),          // pg_edge_targets
44                to_bytes(&[1, 1, 1, 1]),          // pg_edge_kind_mask
45                to_bytes(&[0, 0, 0, 0]),          // pg_node_tags
46                to_bytes(&[0b0001]),              // fin = {def 0 at node 0}
47                to_bytes(&[0b0001]),              // fout seed = same
48            ]]
49        }),
50        Some(|| {
51            let to_bytes = crate::dispatch_decode::pack_u32;
52            // Diamond 0→{1,2}→3: one forward step from {0} reaches
53            // {0, 1, 2}. A no-op impl that returns the input would
54            // only produce {0} and fail.
55            vec![vec![to_bytes(&[0b0111])]]
56        }),
57    )
58}
59
60inventory::submit! {
61    vyre_harness::ConvergenceContract {
62        op_id: OP_ID,
63        max_iterations: 64,
64    }
65}
66
67/// Marker type for the reaching-definitions dataflow primitive.
68#[derive(Clone, Copy, Debug, PartialEq, Eq)]
69pub struct ReachingDefs;
70
71impl crate::soundness::SoundnessTagged for ReachingDefs {
72    fn soundness(&self) -> crate::soundness::Soundness {
73        crate::soundness::Soundness::Exact
74    }
75}
weir/reaching/program.rs

weir/reaching/
program.rs
