weirflow 0.1.0

GPU-first dataflow analysis primitives for Vyre and Santh compiler pipelines.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

use super::OP_ID;
use vyre::ir::Program;
use vyre_primitives::graph::csr_forward_traverse::csr_forward_traverse;
use vyre_primitives::graph::program_graph::ProgramGraphShape;

/// Build one CFG-forward propagation step for reaching-defs.
///
/// `frontier_in` reads the current `out[n]` bit-sets across all CFG
/// nodes (flat; surge stdlib is responsible for laying it out as
/// `n * defs_per_word` per node). `frontier_out` receives the
/// propagated `in'[n]` after one CFG-edge traversal.
///
/// The `gen[n] ∪ (in[n] − kill[n])` transfer runs on the surge side
/// as a pointwise pre-union step in the fixpoint driver  -  this keeps
/// the vyre primitive a single traversal call (same shape as
/// `flows_to`), which composes cleanly with
/// `vyre_primitives::bitset` ops for the transfer.
#[must_use]
pub fn reaching_defs_step(
    shape: ProgramGraphShape,
    frontier_in: &str,
    frontier_out: &str,
) -> Program {
    csr_forward_traverse(shape, frontier_in, frontier_out, 0xFFFF_FFFF)
}

inventory::submit! {
    vyre_harness::OpEntry::new(
        OP_ID,
        || reaching_defs_step(ProgramGraphShape::new(4, 4), "fin", "fout"),
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            // Diamond CFG  -  four nodes with a join at node 3:
            //   0 → 1 → 3
            //   0 → 2 → 3
            // Reaching-defs start at node 0 with def-set {0b0001}.
            // After one forward step, def 0 has propagated to nodes 1
            // and 2 after one propagation step; the join into 3 is reached by
            // the next fixpoint iteration.
            vec![vec![
                to_bytes(&[0, 0, 0, 0]),          // pg_nodes
                to_bytes(&[0, 2, 3, 4, 4]),       // pg_edge_offsets: 0→{1,2}, 1→{3}, 2→{3}, 3→{}
                to_bytes(&[1, 2, 3, 3]),          // pg_edge_targets
                to_bytes(&[1, 1, 1, 1]),          // pg_edge_kind_mask
                to_bytes(&[0, 0, 0, 0]),          // pg_node_tags
                to_bytes(&[0b0001]),              // fin = {def 0 at node 0}
                to_bytes(&[0b0001]),              // fout seed = same
            ]]
        }),
        Some(|| {
            let to_bytes = crate::dispatch_decode::pack_u32;
            // Diamond 0→{1,2}→3: one forward step from {0} reaches
            // {0, 1, 2}. A no-op impl that returns the input would
            // only produce {0} and fail.
            vec![vec![to_bytes(&[0b0111])]]
        }),
    )
}

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

/// Marker type for the reaching-definitions dataflow primitive.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ReachingDefs;

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