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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

use super::IFDS_REACH_MASK;

fn ifds_bit_is_set(words: &[u32], bit: usize) -> bool {
    words
        .get(bit / 32)
        .is_some_and(|word| (word & (1u32 << (bit % 32))) != 0)
}

fn ifds_set_bit(words: &mut [u32], bit: usize) -> bool {
    let Some(word) = words.get_mut(bit / 32) else {
        return false;
    };
    let mask = 1u32 << (bit % 32);
    let changed = (*word & mask) == 0;
    *word |= mask;
    changed
}

#[must_use]
#[deprecated(
    note = "reference oracle only; production code must dispatch the Weir Program on a concrete GPU backend or use weir::oracle for parity evidence"
)]
pub(crate) fn ifds_reach_closure_cpu(
    node_count: u32,
    edge_offsets: &[u32],
    edge_targets: &[u32],
    edge_kind_mask: &[u32],
    seed_bits: &[u32],
) -> Vec<u32> {
    let nodes = node_count as usize;
    let words = nodes.checked_add(31).unwrap_or_else(|| {
        panic!(
            "ifds_reach_closure_cpu node_count={node_count} overflows host bitset word calculation. Fix: shard the oracle graph."
        )
    }) / 32;
    crate::dispatch_decode::require_bitset_words("ifds_reachability_cpu", seed_bits, words)
        .expect("ifds_reachability CPU oracle received malformed seed bitset");
    crate::dispatch_decode::require_csr_shape(
        "ifds_reachability_cpu",
        node_count,
        edge_offsets,
        edge_targets,
        edge_kind_mask,
    )
    .expect("ifds_reachability CPU oracle received malformed CSR graph");
    let mut reached = vec![0u32; words];
    for (dst, src) in reached.iter_mut().zip(seed_bits.iter().copied()) {
        *dst = src;
    }
    if words > 0 && nodes % 32 != 0 {
        let keep = (1u32 << (nodes % 32)) - 1;
        if let Some(last) = reached.last_mut() {
            *last &= keep;
        }
    }

    let mut changed = true;
    while changed {
        changed = false;
        for node in 0..nodes {
            if !ifds_bit_is_set(&reached, node) {
                continue;
            }
            let start = edge_offsets[node] as usize;
            let end = edge_offsets[node + 1] as usize;
            for edge in start..end {
                let kind = edge_kind_mask[edge];
                if (kind & IFDS_REACH_MASK) == 0 {
                    continue;
                }
                let target = edge_targets[edge] as usize;
                if target < nodes {
                    changed |= ifds_set_bit(&mut reached, target);
                }
            }
        }
    }
    reached
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::ifds_reach_closure_cpu;

    #[test]
    #[should_panic(expected = "ifds_reachability CPU oracle received malformed seed bitset")]
    fn ifds_reach_closure_rejects_bad_seed_len() {
        let _ = ifds_reach_closure_cpu(2, &[0, 1, 1], &[1], &[0], &[0b1, 0b0]);
    }

    #[test]
    #[should_panic(expected = "ifds_reachability CPU oracle received malformed CSR graph")]
    fn ifds_reach_closure_rejects_malformed_csr() {
        let _ = ifds_reach_closure_cpu(2, &[1, 1, 1], &[0], &[0], &[0b1]);
    }

    #[test]
    #[should_panic(expected = "ifds_reachability CPU oracle received malformed CSR graph")]
    fn ifds_reach_closure_rejects_oob_target() {
        let _ = ifds_reach_closure_cpu(2, &[0, 1, 1], &[2], &[0], &[0b1]);
    }
}