weir/dominators.rs
1//! `dominators` - pre-dominator tree (dual of `post_dominates`).
2//!
3//! Given a CFG and an entry node, computes for every node `n` the
4//! set `dom(n)` of nodes that dominate `n`. Used by dataflow consumers for a
5//! `dominates($a, $b)` predicate to project "every path from entry
6//! to some node in $b passes through a node in $a" onto the per-
7//! node bitset the GPU primitive consumes.
8//!
9//! ## Shape contract
10//!
11//! Inputs:
12//! - `node_count`: total node count.
13//! - `dom_set`: per-node bitset where bit `m` of node `n`'s row is
14//! set iff `n` dominates `m`. Production construction uses the
15//! GPU-resident fixed-point step in this module; [`compute_cpu`]
16//! remains only as a parity oracle.
17//! - `target_set`: bitset of target nodes the predicate queries.
18//! - `out`: bitset; bit `n` set iff `n` dominates SOME target.
19//!
20//! The query projection matches `post_dominates`: a single `bitset_and`
21//! step over a dominator matrix built by GPU fixed-point construction.
22
23#[cfg(any(test, feature = "cpu-parity"))]
24mod cpu_oracle;
25mod dispatch;
26mod program;
27mod registry;
28mod tag;
29
30#[cfg(test)]
31mod tests;
32
33pub(crate) const OP_ID: &str = "weir::dominators";
34
35#[cfg(any(test, feature = "cpu-parity"))]
36#[allow(deprecated)]
37pub(crate) use cpu_oracle::cpu_ref;
38#[cfg(any(test, feature = "cpu-parity"))]
39#[allow(deprecated)]
40pub(crate) use cpu_oracle::{compute_bitmap_bytes, compute_cpu};
41#[cfg(test)]
42#[allow(deprecated)]
43pub(crate) use dispatch::compute_borrowed_into_via;
44#[cfg(any(test, feature = "cpu-parity"))]
45#[allow(deprecated)]
46pub(crate) use dispatch::compute_via;
47pub use program::dominates;
48#[cfg(any(test, feature = "cpu-parity"))]
49pub(crate) use program::dominator_step;
50pub use tag::Dominators;