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

//! WAVE2 (flowgraph successor: `weir::graph_layout` CSR invariants).
#![cfg(feature = "cpu-parity")]
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]

use proptest::prelude::*;
use weir::graph_layout::{stable_csr_layout_hash, CsrGraph, LinearDomain};

fn build_valid_csr(node_count: u32, edges: &[(u32, u32, u32)]) -> (Vec<u32>, Vec<u32>, Vec<u32>) {
    let n = node_count as usize;
    if n == 0 {
        return (vec![0], Vec::new(), Vec::new());
    }
    let mut offsets = vec![0u32];
    let mut targets = Vec::new();
    let mut kinds = Vec::new();
    let mut per_row: Vec<Vec<(u32, u32)>> = vec![Vec::new(); n];
    for &(from, to, kind) in edges {
        if (from as usize) < n && (to as usize) < n {
            per_row[from as usize].push((to, kind));
        }
    }
    for row in &mut per_row {
        row.sort_unstable_by_key(|(t, _)| *t);
    }
    for row in per_row {
        for (t, k) in row {
            targets.push(t);
            kinds.push(k);
        }
        offsets.push(targets.len() as u32);
    }
    (offsets, targets, kinds)
}

macro_rules! wave2_flowgraph {
    ($($name:ident => |$bind:ident| $body:block),+ $(,)?) => {
        $(proptest! {
            #![proptest_config(ProptestConfig::with_cases(32))]
            #[test]
            fn $name($bind in 0u32..8) {
                $body
            }
        })+
    };
}

wave2_flowgraph! {
    p00_linear_domain_bitset_words_bounds => |p| { let d = LinearDomain::new(p); let w = d.bitset_words(); prop_assert!(w >= 1 || p == 0); },
    p01_linear_domain_scalar_slots_ok_small => |p| { let d = LinearDomain::new(p.min(64)); prop_assert!(d.scalar_slots("w2", 1).is_ok()); },
    p02_validate_accepts_well_formed_csr => |p| { let nc = p.min(7); let edges: Vec<(u32,u32,u32)> = (0..8).map(|i| ((i%nc.max(1)) as u32, ((i/2)%nc.max(1)) as u32, 1)).collect(); let (o,t,k) = build_valid_csr(nc, &edges); let g = CsrGraph::new(nc, &o, &t, &k); prop_assert!(g.validate("w2").is_ok()); },
    p03_normalize_idempotent_hash => |p| { let nc = p.max(1).min(5); let edges = vec![(0u32, 1, 1), (1, 2, 2)]; let (o,t,k) = build_valid_csr(nc, &edges); let n1 = CsrGraph::new(nc, &o, &t, &k).normalize("w2a").expect("n1"); let n2 = CsrGraph::new(n1.node_count(), n1.edge_offsets(), n1.edge_targets(), n1.edge_kind_mask()).normalize("w2b").expect("n2"); prop_assert_eq!(n1.stable_layout_hash(), n2.stable_layout_hash()); },
    p04_stable_hash_deterministic => |p| { let nc = 3u32; let (o,t,k) = build_valid_csr(nc, &[(0,1,1)]); let h1 = stable_csr_layout_hash(nc, 1, &o, &t, &k); let h2 = stable_csr_layout_hash(nc, 1, &o, &t, &k); prop_assert_eq!(h1, h2); },
    p05_validate_rejects_bad_first_offset => |p| { let g = CsrGraph::new(2, &[1,1], &[], &[]); prop_assert!(g.validate("w2").is_err()); },
    p06_empty_graph_validate_ok => |p| { let g = CsrGraph::new(0, &[0], &[], &[]); prop_assert!(g.validate("w2").is_ok()); },
    p07_normalized_rows_sorted => |p| { let nc = 3u32; let (o,t,k) = build_valid_csr(nc, &[(0,2,1),(0,1,2),(1,0,3)]); let n = CsrGraph::new(nc, &o, &t, &k).normalize("w2").expect("norm"); let offs = n.edge_offsets(); let tgts = n.edge_targets(); for node in 0..nc as usize { let s = offs[node] as usize; let e = offs[node+1] as usize; for w in tgts[s..e].windows(2) { prop_assert!(w[0] < w[1]); } } },
    p08_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p09_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p10_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p11_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p12_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p13_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p14_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p15_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p16_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p17_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p18_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p19_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p20_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p21_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p22_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p23_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p24_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p25_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p26_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p27_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p28_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p29_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p30_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p31_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p32_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p33_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p34_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p35_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p36_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p37_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p38_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p39_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p40_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p41_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 3u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p42_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 1u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
    p43_csr_validate_no_panic_on_offsets => |p| { let nc = p.min(6); let mut offs = vec![0u32]; let step = 2u32; for _j in 0..=nc { offs.push(offs.last().copied().unwrap_or(0).saturating_add(step)); } let g = CsrGraph::new(nc, &offs, &[], &[]); let _ = g.validate("w2"); },
}