vyre_reference/execution/
mod.rs

1//! Generic reference interpreter entry points.
2//!
3//! The stable statement-IR [`reference_eval`] entry point remains delegated to
4//! the existing invocation simulator until `Program` stores graph nodes
5//! directly.
6
7pub(crate) mod call;
8pub mod expr;
9pub(crate) mod expr_cast;
10pub(crate) mod hashmap;
11pub mod node;
12pub(crate) mod node_tree;
13/// Thread-local arithmetic-IR-op counting for roofline / complexity analysis.
14pub mod op_count;
15pub mod sequential;
16pub(crate) mod typed_ops;
17
18use std::borrow::Cow;
19
20use rustc_hash::FxHashMap;
21use vyre::ir::{InterpCtx, Node, NodeId, NodeStorage, Program, Value as IrValue};
22
23use crate::value::Value;
24
25/// If the program satisfies the public top-level-Region model, return a
26/// byte-identical clone. If not, the usual case is
27/// `optimizer::passes::cleanup::region_inline_engine` having flattened a Category-A wrapper;
28/// in that case [`Program::reconcile_runnable_top_level`] matches
29/// `Program::wrapped` again. When the first entry node is a `Store` (or the
30/// entry is empty), we do **not** auto-wrap: those programs must still use
31/// `Program::wrapped` explicitly, matching `region_gate` negative tests.
32pub(crate) fn program_for_interpreter(program: &Program) -> Result<Cow<'_, Program>, vyre::Error> {
33    let normalized = if let Some(message) = program.top_level_region_violation() {
34        if program.entry().is_empty() {
35            return Err(vyre::Error::interp(format!(
36                "reference interpreter requires a top-level Region-wrapped Program: {message}"
37            )));
38        }
39        if matches!(program.entry().first(), Some(Node::Store { .. })) {
40            return Err(vyre::Error::interp(format!(
41                "reference interpreter requires a top-level Region-wrapped Program: {message}"
42            )));
43        }
44        Cow::Owned(program.clone().reconcile_runnable_top_level())
45    } else {
46        Cow::Borrowed(program)
47    };
48    match vyre_foundation::transform::collectives::lower_single_rank_collectives(
49        normalized.as_ref(),
50    ) {
51        Ok(Some(lowered)) => Ok(Cow::Owned(lowered)),
52        Ok(None) => Ok(normalized),
53        Err(error) => Err(vyre::Error::interp(error.to_string())),
54    }
55}
56
57/// The interpreter's output ABI, single-homed: [`is_reference_output`] is the exact
58/// predicate `reference_eval` uses to collect the buffers it returns, and
59/// [`output_index`] locates a named output by that predicate. Re-exported so test
60/// harnesses never hand-roll (and drift from) the selection.
61pub use hashmap::{is_reference_output, output_index};
62
63/// Execute a vyre IR program on the pure Rust reference interpreter.
64///
65/// The current public [`Program`] model is statement-oriented, so this stable
66/// entry point delegates to the statement evaluator. Graph-shaped extension
67/// nodes use [`run_storage_graph`].
68pub fn reference_eval(program: &Program, inputs: &[Value]) -> Result<Vec<Value>, vyre::Error> {
69    run_arena_reference(program, inputs)
70}
71
72/// [`reference_eval`] plus an [`OobReport`](crate::oob::OobReport) of every
73/// out-of-bounds access the interpreter silently absorbed during the run.
74///
75/// The interpreter DEFINES OOB loads as zero-fill and OOB stores as a no-op so
76/// its output stays deterministic, but that silent absorption is exactly what
77/// masks a GPU/CPU parity hazard: an IR program with an ungated data-derived index
78/// "works" here yet a real GPU (CUDA does no bounds-checking) reads garbage or
79/// corrupts memory. Use this to assert a program NEVER relies on that masking: a
80/// correctly bounds-gated program handles an out-of-contract index with explicit
81/// control flow, so it records `OobReport::total() == 0` even on hostile input. A
82/// nonzero total means the IR indexed past a buffer end and needs an explicit gate
83/// (the class of fix applied to ziftsieve/base64/sketch/simplicial).
84///
85/// The tally is per-thread and reset at the start of this call, so it measures
86/// exactly this run.
87///
88/// # Errors
89/// Same as [`reference_eval`].
90pub fn reference_eval_oob_report(
91    program: &Program,
92    inputs: &[Value],
93) -> Result<(Vec<Value>, crate::oob::OobReport), vyre::Error> {
94    crate::oob::reset_oob_report();
95    let outputs = reference_eval(program, inputs)?;
96    Ok((outputs, crate::oob::oob_report()))
97}
98
99/// [`reference_eval_with_dispatch`] plus an [`OobReport`](crate::oob::OobReport).
100///
101/// The grid floor lets a caller deliberately OVER-FIRE the dispatch (more lanes
102/// than the buffer-inferred grid) to probe whether a primitive's per-lane guard
103/// actually protects the extra lanes. A guard written as `Expr::and(t < n, load(buf,
104/// t))` does NOT, the data-flow AND evaluates the load for `t >= n`, an OOB read
105/// (the ssa_dominance_scan bug). Running a valid fixture at an inflated grid and
106/// asserting `OobReport::total() == 0` catches that whole class registry-wide.
107///
108/// # Errors
109/// Same as [`reference_eval_with_dispatch`].
110pub fn reference_eval_with_dispatch_oob_report(
111    program: &Program,
112    inputs: &[Value],
113    min_dispatch_elements: u32,
114) -> Result<(Vec<Value>, crate::oob::OobReport), vyre::Error> {
115    crate::oob::reset_oob_report();
116    let outputs = reference_eval_with_dispatch(program, inputs, min_dispatch_elements)?;
117    Ok((outputs, crate::oob::oob_report()))
118}
119
120/// [`reference_eval`] with an explicit grid floor.
121///
122/// The reference interpreter infers its dispatch grid from buffer SHAPES, which
123/// cannot express the per-invocation count of a byte-scan program (the haystack
124/// is packed 4 bytes/u32 and the scan length is a runtime value). Pass the true
125/// grid, e.g. `haystack_len` for a one-lane-per-byte scan, so the interpreter
126/// covers exactly what the real dispatch config would; otherwise high positions
127/// are silently skipped (the CPU-ref oracle under-fires while the GPU is correct).
128/// `min_dispatch_elements` is a FLOOR: the interpreter still runs at least the
129/// buffer-inferred grid, so passing `0` is identical to [`reference_eval`].
130///
131/// # Errors
132/// Same as [`reference_eval`].
133pub fn reference_eval_with_dispatch(
134    program: &Program,
135    inputs: &[Value],
136    min_dispatch_elements: u32,
137) -> Result<Vec<Value>, vyre::Error> {
138    run_arena_reference_with_dispatch(program, inputs, min_dispatch_elements)
139}
140
141/// Execute using the statement-IR reference evaluator.
142pub fn run_arena_reference(program: &Program, inputs: &[Value]) -> Result<Vec<Value>, vyre::Error> {
143    run_arena_reference_with_dispatch(program, inputs, 0)
144}
145
146/// [`run_arena_reference`] with an explicit grid floor (see
147/// [`reference_eval_with_dispatch`]).
148///
149/// # Errors
150/// Same as [`run_arena_reference`].
151pub fn run_arena_reference_with_dispatch(
152    program: &Program,
153    inputs: &[Value],
154    min_dispatch_elements: u32,
155) -> Result<Vec<Value>, vyre::Error> {
156    let program = program_for_interpreter(program)?;
157    hashmap::run_hashmap_reference(
158        &program,
159        inputs,
160        min_dispatch_elements,
161        hashmap::LaneOrder::Forward,
162    )
163}
164
165/// Execute a program with the workgroup/invocation STEP ORDER reversed.
166///
167/// The result is identical to [`reference_eval`] for any RACE-FREE program (every
168/// output slot is written by exactly one lane, or shared slots are touched only by
169/// commutative atomics). It DIFFERS only when a non-atomic cross-lane write-write
170/// race exists, two lanes plain-`store` the same slot, because the GPU leaves the
171/// winner driver-defined while the single-threaded reference otherwise resolves it
172/// deterministically (last stepped lane wins). Comparing this against
173/// [`reference_eval`] therefore surfaces a hidden race the same way a real GPU would
174/// nondeterministically diverge.
175///
176/// # Errors
177/// Same as [`reference_eval`].
178pub fn reference_eval_lane_reversed(
179    program: &Program,
180    inputs: &[Value],
181) -> Result<Vec<Value>, vyre::Error> {
182    let program = program_for_interpreter(program)?;
183    hashmap::run_hashmap_reference(&program, inputs, 0, hashmap::LaneOrder::Reversed)
184}
185
186/// Differential oracle retained for tests during the generic interpreter transition.
187#[cfg(test)]
188pub fn eval_hashmap_reference(
189    program: &Program,
190    inputs: &[Value],
191) -> Result<Vec<Value>, vyre::Error> {
192    run_arena_reference(program, inputs)
193}
194
195/// Interpret a compact [`NodeStorage`] graph and return output node values.
196pub fn run_storage_graph(
197    nodes: &[(NodeId, NodeStorage)],
198    outputs: &[NodeId],
199) -> Result<Vec<IrValue>, vyre::Error> {
200    let mut graph = FxHashMap::with_capacity_and_hasher(nodes.len(), Default::default());
201    for (id, node) in nodes {
202        if graph.insert(*id, node).is_some() {
203            return Err(duplicate_node_error(*id));
204        }
205    }
206    let mut ctx = InterpCtx::default();
207    let mut states = FxHashMap::with_capacity_and_hasher(graph.len(), Default::default());
208
209    for output in outputs {
210        eval_storage_node(*output, &graph, &mut ctx, &mut states)?;
211    }
212
213    outputs
214        .iter()
215        .map(|id| ctx.get(*id).map_err(interp_error))
216        .collect()
217}
218
219#[derive(Clone, Copy, Debug, PartialEq, Eq)]
220enum VisitState {
221    Visiting,
222    Done,
223}
224
225fn eval_storage_node(
226    id: NodeId,
227    graph: &FxHashMap<NodeId, &NodeStorage>,
228    ctx: &mut InterpCtx,
229    states: &mut FxHashMap<NodeId, VisitState>,
230) -> Result<(), vyre::Error> {
231    match states.get(&id).copied() {
232        Some(VisitState::Done) => return Ok(()),
233        Some(VisitState::Visiting) => return Err(cycle_error(id)),
234        None => {}
235    }
236
237    let node = *graph.get(&id).ok_or_else(|| missing_node_error(id))?;
238    states.insert(id, VisitState::Visiting);
239    let inputs = node.input_ids();
240    for input in &inputs {
241        eval_storage_node(*input, graph, ctx, states)?;
242    }
243    ctx.set_operands(inputs);
244    let value = node.interpret(ctx).map_err(interp_error)?;
245    ctx.set(id, value);
246    states.insert(id, VisitState::Done);
247    Ok(())
248}
249
250fn interp_error(error: vyre::ir::EvalError) -> vyre::Error {
251    vyre::Error::interp(error.to_string())
252}
253
254fn missing_node_error(id: NodeId) -> vyre::Error {
255    vyre::Error::interp(format!(
256        "graph references missing node {}. Fix: include every dependency in the interpreter input graph.",
257        id.0
258    ))
259}
260
261fn cycle_error(id: NodeId) -> vyre::Error {
262    vyre::Error::interp(format!(
263        "graph contains a dependency cycle at node {}. Fix: submit an acyclic dataflow graph.",
264        id.0
265    ))
266}
267
268fn duplicate_node_error(id: NodeId) -> vyre::Error {
269    vyre::Error::interp(format!(
270        "graph contains duplicate node {}. Fix: submit exactly one storage record for each NodeId before reference execution.",
271        id.0
272    ))
273}
274
275#[cfg(test)]
276mod tests {
277    use super::*;
278    use vyre::ir::{BinOp, BufferAccess, BufferDecl, DataType, Expr, Node, NodeStorage};
279
280    #[test]
281    fn reference_eval_dispatches_singleton_atomic_flags_across_dynamic_byte_input() {
282        let program = Program::wrapped(
283            vec![
284                BufferDecl::storage("bytes_in", 0, BufferAccess::ReadOnly, DataType::U8)
285                    .with_count(0),
286                BufferDecl::storage("flag", 1, BufferAccess::ReadWrite, DataType::U32)
287                    .with_count(1),
288            ],
289            [256, 1, 1],
290            vec![
291                Node::let_bind("i", Expr::InvocationId { axis: 0 }),
292                Node::if_then(
293                    Expr::lt(Expr::var("i"), Expr::buf_len("bytes_in")),
294                    vec![Node::if_then(
295                        Expr::ne(
296                            Expr::cast(DataType::U32, Expr::load("bytes_in", Expr::var("i"))),
297                            Expr::u32(0),
298                        ),
299                        vec![Node::let_bind(
300                            "flag_old",
301                            Expr::atomic_or("flag", Expr::u32(0), Expr::u32(1)),
302                        )],
303                    )],
304                ),
305            ],
306        );
307        let mut bytes = vec![0u8; 4097];
308        bytes[4096] = 1;
309
310        let outputs = reference_eval(&program, &[Value::from(bytes), Value::from(vec![0u8; 4])])
311            .expect("Fix: reference interpreter should execute singleton atomic flag scans.");
312        let flag = outputs[0].to_bytes();
313
314        assert_eq!(u32::from_le_bytes([flag[0], flag[1], flag[2], flag[3]]), 1);
315    }
316
317    /// A byte-scan program whose haystack is PACKED (4 bytes/u32) has fewer buffer
318    /// elements than the invocations it needs, one per byte. Buffer-shape grid
319    /// inference therefore UNDER-covers it, silently skipping high positions. This
320    /// is exactly the region-presence CPU-ref under-fire that the GPU did not have.
321    /// `reference_eval_with_dispatch` lets the caller pass the true byte grid so
322    /// the interpreter covers what the real dispatch would, no silent
323    /// under-coverage (Law 10). This locks both halves: the default under-covers,
324    /// the floor covers.
325    #[test]
326    fn dispatch_floor_covers_packed_byte_scan_that_buffer_inference_under_covers() {
327        // 1024 packed words == 4096 bytes; the marker is at byte 4095 (word 1023),
328        // reachable only if the grid runs 4096 invocations, not the 1024 the
329        // packed buffer's element count implies.
330        const PACKED_WORDS: u32 = 1024;
331        const BYTE_LEN: u32 = PACKED_WORDS * 4; // 4096
332        const MARKER_POS: u32 = BYTE_LEN - 1; // 4095
333        let program = Program::wrapped(
334            vec![
335                BufferDecl::storage("packed", 0, BufferAccess::ReadOnly, DataType::U32)
336                    .with_count(PACKED_WORDS),
337                BufferDecl::storage("byte_len", 1, BufferAccess::ReadOnly, DataType::U32)
338                    .with_count(1),
339                BufferDecl::storage("flag", 2, BufferAccess::ReadWrite, DataType::U32)
340                    .with_count(1),
341            ],
342            [256, 1, 1],
343            vec![
344                Node::let_bind("i", Expr::InvocationId { axis: 0 }),
345                Node::if_then(
346                    Expr::lt(Expr::var("i"), Expr::load("byte_len", Expr::u32(0))),
347                    vec![Node::if_then(
348                        Expr::eq(Expr::var("i"), Expr::u32(MARKER_POS)),
349                        vec![
350                            // Read the packed word for this byte so `packed` is a
351                            // genuine input (its 1024 elements are what buffer-shape
352                            // inference would cap the grid at).
353                            Node::let_bind(
354                                "word",
355                                Expr::load("packed", Expr::div(Expr::var("i"), Expr::u32(4))),
356                            ),
357                            Node::if_then(
358                                Expr::eq(Expr::var("word"), Expr::u32(0)),
359                                vec![Node::let_bind(
360                                    "flag_old",
361                                    Expr::atomic_or("flag", Expr::u32(0), Expr::u32(1)),
362                                )],
363                            ),
364                        ],
365                    )],
366                ),
367            ],
368        );
369        let read_flag = |outputs: &[Value]| {
370            let bytes = outputs[0].to_bytes();
371            u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]])
372        };
373        let make_inputs = || {
374            vec![
375                Value::from(vec![0u8; PACKED_WORDS as usize * 4]),
376                Value::from(BYTE_LEN.to_le_bytes().to_vec()),
377                Value::from(vec![0u8; 4]),
378            ]
379        };
380
381        // Default grid: buffer-shape inference caps at the packed buffer's 1024
382        // elements, so byte 4095 is never visited, the flag stays clear. This is
383        // the SILENT under-coverage the region-presence gate hit.
384        let under = reference_eval(&program, &make_inputs())
385            .expect("Fix: interpreter runs the packed byte-scan");
386        assert_eq!(
387            read_flag(&under),
388            0,
389            "buffer-shape grid inference must under-cover this packed byte-scan (documents the hole)"
390        );
391
392        // Floor = true byte length: the interpreter now covers byte 4095 and the
393        // marker is found (parity with what the real dispatch config produces).
394        let covered = reference_eval_with_dispatch(&program, &make_inputs(), BYTE_LEN)
395            .expect("Fix: interpreter runs the packed byte-scan with an explicit grid floor");
396        assert_eq!(
397            read_flag(&covered),
398            1,
399            "an explicit grid floor of haystack_len must cover every byte position"
400        );
401    }
402
403    #[test]
404    fn generic_storage_graph_matches_recursive_oracle_for_10k_programs() {
405        let mut rng = 0x9e37_79b9_u64;
406        for case in 0..10_000 {
407            let graph = random_graph(&mut rng, case);
408            let output = graph.last().expect("Fix: generated graph is non-empty").0;
409            let expected =
410                recursive_value(output, &graph).expect("Fix: recursive oracle evaluates");
411            let actual = run_storage_graph(&graph, &[output])
412                .expect("Fix: generic graph interpreter evaluates")[0];
413            assert_eq!(actual, expected, "case {case}");
414        }
415    }
416
417    fn random_graph(rng: &mut u64, case: u32) -> Vec<(NodeId, NodeStorage)> {
418        let len = 2 + (next(rng) as usize % 31);
419        let mut graph = Vec::with_capacity(len);
420        graph.push((NodeId(0), NodeStorage::LitU32(case)));
421        graph.push((NodeId(1), NodeStorage::LitU32(next(rng))));
422        for index in 2..len {
423            let left = NodeId(next(rng) % index as u32);
424            let right = NodeId(next(rng) % index as u32);
425            let op = match next(rng) % 5 {
426                0 => BinOp::Add,
427                1 => BinOp::Sub,
428                2 => BinOp::Mul,
429                3 => BinOp::BitXor,
430                _ => BinOp::BitAnd,
431            };
432            graph.push((NodeId(index as u32), NodeStorage::BinOp { op, left, right }));
433        }
434        graph
435    }
436
437    fn recursive_value(
438        id: NodeId,
439        graph: &[(NodeId, NodeStorage)],
440    ) -> Result<IrValue, vyre::Error> {
441        let node = graph
442            .iter()
443            .find(|(node_id, _)| *node_id == id)
444            .map(|(_, node)| node)
445            .ok_or_else(|| missing_node_error(id))?;
446        match node {
447            NodeStorage::LitU32(value) => Ok(IrValue::U32(*value)),
448            NodeStorage::BinOp { op, left, right } => {
449                let left = expect_u32(recursive_value(*left, graph)?)?;
450                let right = expect_u32(recursive_value(*right, graph)?)?;
451                let value = match op {
452                    BinOp::Add => left.wrapping_add(right),
453                    BinOp::Sub => left.wrapping_sub(right),
454                    BinOp::Mul => left.wrapping_mul(right),
455                    BinOp::BitXor => left ^ right,
456                    BinOp::BitAnd => left & right,
457                    _ => {
458                        return Err(vyre::Error::interp(
459                            "recursive parity oracle received unsupported op. Fix: keep test generation within the oracle domain.",
460                        ));
461                    }
462                };
463                Ok(IrValue::U32(value))
464            }
465            _ => Err(vyre::Error::interp(
466                "recursive parity oracle received unsupported node. Fix: keep test generation within the oracle domain.",
467            )),
468        }
469    }
470
471    fn expect_u32(value: IrValue) -> Result<u32, vyre::Error> {
472        match value {
473            IrValue::U32(value) => Ok(value),
474            other => Err(vyre::Error::interp(format!(
475                "recursive parity oracle expected u32, got {other:?}. Fix: keep generated graphs scalar-u32 only."
476            ))),
477        }
478    }
479
480    fn next(rng: &mut u64) -> u32 {
481        *rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1);
482        (*rng >> 32) as u32
483    }
484}
vyre_reference/execution/mod.rs

vyre_reference/execution/
mod.rs
