vyre_primitives/graph/exploded/layout.rs
1/// Checked dispatch layout for an exploded IFDS CSR build.
2#[derive(Debug, Clone, Copy, PartialEq, Eq)]
3pub struct IfdsCsrLayout {
4 /// Whether the declared IFDS domain is empty and should not dispatch.
5 pub empty: bool,
6 /// Number of procedures in the exploded domain.
7 pub num_procs: u32,
8 /// Number of blocks per procedure.
9 pub blocks_per_proc: u32,
10 /// Number of facts per procedure.
11 pub facts_per_proc: u32,
12 /// Number of intra-procedural control-flow edges.
13 pub intra_count: u32,
14 /// Number of inter-procedural call/return edges.
15 pub inter_count: u32,
16 /// Number of GEN rules.
17 pub gen_count: u32,
18 /// Number of KILL rules.
19 pub kill_count: u32,
20 /// Number of u32 words required by each intra edge field buffer.
21 pub intra_storage_words: usize,
22 /// Number of u32 words required by each inter edge field buffer.
23 pub inter_storage_words: usize,
24 /// Number of u32 words required by each GEN rule field buffer.
25 pub gen_storage_words: usize,
26 /// Number of u32 words required by each KILL rule field buffer.
27 pub kill_storage_words: usize,
28 /// Dense nodes per procedure.
29 pub slots_per_proc: u32,
30 /// Total dense node count.
31 pub total_nodes: u32,
32 /// Number of `u32` words in `row_ptr`.
33 pub row_words: usize,
34 /// Number of `u32` words in the dispatch row cursor scratch buffer.
35 pub row_cursor_words: usize,
36 /// Number of `u32` words in the dense kill bitmap scratch buffer.
37 pub killed_words: usize,
38 /// Maximum emitted column count for the declared edge/rule counts.
39 pub max_col_count: u32,
40 /// Number of `u32` words allocated for `col_idx`.
41 pub col_buffer_words: usize,
42}
43
44/// Primitive-owned cache identity for exploded IFDS CSR construction Programs.
45#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
46pub struct IfdsCsrProgramCacheKey {
47 /// Number of procedures in the exploded domain.
48 pub num_procs: u32,
49 /// Number of blocks per procedure.
50 pub blocks_per_proc: u32,
51 /// Number of facts per procedure.
52 pub facts_per_proc: u32,
53 /// Number of intra-procedural control-flow edges.
54 pub intra_count: u32,
55 /// Number of inter-procedural call/return edges.
56 pub inter_count: u32,
57 /// Number of GEN rules.
58 pub gen_count: u32,
59 /// Number of KILL rules.
60 pub kill_count: u32,
61 /// Maximum emitted column count baked into the generated Program.
62 pub max_col_count: u32,
63}
64
65/// Stable identity for IFDS rule tuples supplied to the CSR builder.
66///
67/// This is intentionally distinct from [`IfdsCsrProgramCacheKey`]: the generated
68/// program depends on dimensions and rule counts, while staged dispatch input
69/// reuse also depends on the actual tuple contents.
70#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
71pub struct IfdsCsrRuleInputFingerprint {
72 /// Fingerprint of `(proc, src_block, dst_block)` intra edges.
73 pub intra: u128,
74 /// Fingerprint of `(src_proc, src_block, dst_proc, dst_block)` inter edges.
75 pub inter: u128,
76 /// Fingerprint of `(proc, block, fact)` GEN rules.
77 pub gen: u128,
78 /// Fingerprint of `(proc, block, fact)` KILL rules.
79 pub kill: u128,
80}
81
82/// Primitive-owned identity for reusable exploded IFDS static inputs.
83///
84/// The generated Program depends on [`IfdsCsrProgramCacheKey`]. Staged rule
85/// inputs also depend on tuple contents, so dispatch wrappers use this key to
86/// refresh uploads without owning IFDS fingerprint composition.
87#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
88pub struct IfdsCsrStaticInputKey {
89 /// Program-shape key selected by the primitive dispatch plan.
90 pub program_key: IfdsCsrProgramCacheKey,
91 /// Stable content fingerprint of all staged IFDS rule tuples.
92 pub rule_fingerprint: IfdsCsrRuleInputFingerprint,
93}
94
95impl IfdsCsrRuleInputFingerprint {
96 /// Build a stable rule-content fingerprint without allocating columns.
97 #[must_use]
98 pub fn from_rules(
99 intra_edges: &[(u32, u32, u32)],
100 inter_edges: &[(u32, u32, u32, u32)],
101 flow_gen: &[(u32, u32, u32)],
102 flow_kill: &[(u32, u32, u32)],
103 ) -> Self {
104 Self {
105 intra: fingerprint_rule_triples(intra_edges),
106 inter: fingerprint_rule_quads(inter_edges),
107 gen: fingerprint_rule_triples(flow_gen),
108 kill: fingerprint_rule_triples(flow_kill),
109 }
110 }
111}
112
113fn mix_rule_word(hash: &mut u128, value: u32) {
114 *hash ^= u128::from(value)
115 .wrapping_add(0x9E37_79B9_7F4A_7C15_6A09_E667_F3BC_C909)
116 .wrapping_add(*hash << 7)
117 .wrapping_add(*hash >> 3);
118 *hash = hash
119 .rotate_left(31)
120 .wrapping_mul(0xD6E8_FD9D_DA37_3C91_BB67_AE85_84CA_A73B);
121}
122
123fn fingerprint_rule_triples(rules: &[(u32, u32, u32)]) -> u128 {
124 let mut hash = 0x243F_6A88_85A3_08D3_1319_8A2E_0370_7344_u128 ^ rules.len() as u128;
125 for &(a, b, c) in rules {
126 mix_rule_word(&mut hash, a);
127 mix_rule_word(&mut hash, b);
128 mix_rule_word(&mut hash, c);
129 }
130 hash
131}
132
133fn fingerprint_rule_quads(rules: &[(u32, u32, u32, u32)]) -> u128 {
134 let mut hash = 0xA409_3822_299F_31D0_082E_FA98_EC4E_6C89_u128 ^ rules.len() as u128;
135 for &(a, b, c, d) in rules {
136 mix_rule_word(&mut hash, a);
137 mix_rule_word(&mut hash, b);
138 mix_rule_word(&mut hash, c);
139 mix_rule_word(&mut hash, d);
140 }
141 hash
142}
143
144impl IfdsCsrProgramCacheKey {
145 /// Build a Program cache key from a validated IFDS layout.
146 #[must_use]
147 pub const fn from_layout(layout: &IfdsCsrLayout) -> Self {
148 Self {
149 num_procs: layout.num_procs,
150 blocks_per_proc: layout.blocks_per_proc,
151 facts_per_proc: layout.facts_per_proc,
152 intra_count: layout.intra_count,
153 inter_count: layout.inter_count,
154 gen_count: layout.gen_count,
155 kill_count: layout.kill_count,
156 max_col_count: layout.max_col_count,
157 }
158 }
159}