use super::{andersen_points_to, POINTS_TO_EDGE_MASK};
#[cfg(any(test, feature = "cpu-parity"))]
use crate::dispatch_input_cache::OwnedDispatchInputs;
use vyre_primitives::graph::program_graph::ProgramGraphShape;
#[cfg(any(test, feature = "cpu-parity"))]
pub(crate) fn subset_closure_via<F>(
dispatch: &F,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
max_iterations: u32,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[Vec<u8>], Option<[u32; 3]>) -> Result<Vec<Vec<u8>>, String>,
{
let owned_inputs = OwnedDispatchInputs::new();
subset_closure_borrowed_via(
&|program, inputs, grid| {
owned_inputs.dispatch_refreshing_slots(program, inputs, grid, &[5], dispatch)
},
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
seed_bits,
max_iterations,
)
}
#[cfg(any(test, feature = "cpu-parity"))]
pub(crate) fn subset_closure_borrowed_via<F>(
dispatch: &F,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
max_iterations: u32,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>) -> Result<Vec<Vec<u8>>, String>,
{
crate::dispatch_decode::require_positive_iterations(
"points_to subset_closure_via",
max_iterations,
)?;
crate::dispatch_decode::require_bitset_tail_clear(
"points_to subset_closure_via",
seed_bits,
node_count,
)?;
let out = subset_closure_borrowed_into_via(
&|program, inputs, grid, outputs| {
let result = dispatch(program, inputs, grid)?;
crate::output_scratch::replace_outputs_preserving_slots(outputs, result);
Ok(())
},
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
seed_bits,
max_iterations,
)?;
crate::dispatch_decode::require_bitset_tail_clear(
"points_to subset_closure_via output",
&out,
node_count,
)?;
Ok(out)
}
#[cfg(any(test, feature = "cpu-parity"))]
pub(crate) fn subset_closure_borrowed_into_via<F>(
dispatch: &F,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
max_iterations: u32,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
let mut scratch = crate::fixed_point_scratch::FixedPointScratch::default();
subset_closure_borrowed_into_with_scratch_via(
dispatch,
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
seed_bits,
max_iterations,
&mut scratch,
)
}
pub(crate) fn subset_closure_borrowed_into_with_scratch_via<F>(
dispatch: &F,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
let mut result = crate::staging_reserve::reserved_vec(
crate::dispatch_decode::bitset_word_capacity(
"points_to subset_closure result",
node_count,
)?,
"fixed-point result word",
)?;
subset_closure_borrowed_into_result_with_scratch_via(
dispatch,
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
seed_bits,
max_iterations,
scratch,
&mut result,
)?;
Ok(result)
}
pub(crate) fn subset_closure_borrowed_into_result_with_scratch_via<F>(
dispatch: &F,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
result: &mut Vec<u32>,
) -> Result<(), String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
crate::dispatch_decode::require_positive_iterations(
"points_to subset_closure_via",
max_iterations,
)?;
let words =
crate::dispatch_decode::bitset_word_capacity("points_to subset_closure", node_count)?;
crate::dispatch_decode::require_csr_shape(
"points_to subset_closure_via",
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
)?;
crate::dispatch_decode::require_bitset_words("points_to subset_closure_via", seed_bits, words)?;
crate::dispatch_decode::require_bitset_tail_clear(
"points_to subset_closure_via",
seed_bits,
node_count,
)?;
scratch.prepare_edge_kind_masks(edge_kind_mask, POINTS_TO_EDGE_MASK)?;
let graph = crate::fixed_point_graph::FixedPointForwardGraph::new_for_kind(
crate::fixed_point_graph::FixedPointAnalysisKind::PointsToSubset,
"points_to subset_closure_via",
node_count,
edge_offsets,
edge_targets,
&scratch.edge_kind_masks,
)?;
subset_closure_prepared_borrowed_into_result_with_scratch_via(
dispatch,
&graph,
seed_bits,
max_iterations,
scratch,
result,
)
}
pub(crate) fn subset_closure_prepared_borrowed_into_with_scratch_via<F>(
dispatch: &F,
graph: &crate::fixed_point_graph::FixedPointForwardGraph,
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
let mut result = crate::staging_reserve::reserved_vec(
crate::dispatch_decode::bitset_word_capacity(
"points_to subset_closure prepared result",
graph.node_count,
)?,
"fixed-point result word",
)?;
subset_closure_prepared_borrowed_into_result_with_scratch_via(
dispatch,
graph,
seed_bits,
max_iterations,
scratch,
&mut result,
)?;
Ok(result)
}
pub(crate) fn subset_closure_prepared_borrowed_into_result_with_scratch_via<F>(
dispatch: &F,
graph: &crate::fixed_point_graph::FixedPointForwardGraph,
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
result: &mut Vec<u32>,
) -> Result<(), String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
let program = andersen_points_to(
ProgramGraphShape::new(graph.node_count, graph.edge_count),
"pts_in",
"pts_out",
);
subset_closure_prepared_program_borrowed_into_result_with_scratch_via(
dispatch,
graph,
&program,
seed_bits,
max_iterations,
scratch,
result,
)
}
pub(crate) fn subset_closure_plan_borrowed_into_with_scratch_via<F>(
dispatch: &F,
plan: &crate::fixed_point_graph::FixedPointAnalysisPlan,
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
) -> Result<Vec<u32>, String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
let mut result = crate::staging_reserve::reserved_vec(
crate::dispatch_decode::bitset_word_capacity(
"points_to subset_closure planned result",
plan.graph().node_count,
)?,
"fixed-point result word",
)?;
subset_closure_plan_borrowed_into_result_with_scratch_via(
dispatch,
plan,
seed_bits,
max_iterations,
scratch,
&mut result,
)?;
Ok(result)
}
pub(crate) fn subset_closure_plan_borrowed_into_result_with_scratch_via<F>(
dispatch: &F,
plan: &crate::fixed_point_graph::FixedPointAnalysisPlan,
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
result: &mut Vec<u32>,
) -> Result<(), String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
plan.require_kind(
crate::fixed_point_graph::FixedPointAnalysisKind::PointsToSubset,
"subset_closure_plan_borrowed_into_result_with_scratch_via",
)?;
subset_closure_prepared_program_borrowed_into_result_with_scratch_via(
dispatch,
plan.graph(),
plan.program(),
seed_bits,
max_iterations,
scratch,
result,
)
}
fn subset_closure_prepared_program_borrowed_into_result_with_scratch_via<F>(
dispatch: &F,
graph: &crate::fixed_point_graph::FixedPointForwardGraph,
program: &vyre::ir::Program,
seed_bits: &[u32],
max_iterations: u32,
scratch: &mut crate::fixed_point_scratch::FixedPointScratch,
result: &mut Vec<u32>,
) -> Result<(), String>
where
F: Fn(&vyre::ir::Program, &[&[u8]], Option<[u32; 3]>, &mut Vec<Vec<u8>>) -> Result<(), String>,
{
graph.require_kind(
crate::fixed_point_graph::FixedPointAnalysisKind::PointsToSubset,
"subset_closure_prepared_program_borrowed_into_result_with_scratch_via",
)?;
crate::dispatch_decode::require_positive_iterations(
"points_to subset_closure_via",
max_iterations,
)?;
let words =
crate::dispatch_decode::bitset_word_capacity("points_to subset_closure", graph.node_count)?;
crate::dispatch_decode::require_bitset_words("points_to subset_closure_via", seed_bits, words)?;
crate::dispatch_decode::require_bitset_tail_clear(
"points_to subset_closure_via",
seed_bits,
graph.node_count,
)?;
scratch.prepare_frontier_words(words, seed_bits)?;
scratch.begin_frontier_density(graph.node_count);
scratch.prepare_next_words(words)?;
for _ in 0..max_iterations {
crate::dispatch_decode::try_pack_u32_into(&scratch.frontier_words, &mut scratch.frontier_bytes, "weir u32 byte staging")?;
let inputs = [
graph.pg_nodes_bytes.as_slice(),
graph.edge_offsets_bytes.as_slice(),
graph.edge_targets_bytes.as_slice(),
graph.edge_kind_mask_bytes.as_slice(),
graph.pg_node_tags_bytes.as_slice(),
scratch.frontier_bytes.as_slice(),
scratch.frontier_bytes.as_slice(),
];
dispatch(
program,
&inputs,
Some([graph.node_count.max(1), 1, 1]),
&mut scratch.outputs,
)?;
crate::dispatch_decode::unpack_only_exact_u32_into(
&scratch.outputs,
"points_to subset_closure_via",
"points-to frontier",
words,
&mut scratch.next,
)?;
crate::dispatch_decode::require_bitset_tail_clear(
"points_to subset_closure_via output",
&scratch.next,
graph.node_count,
)?;
scratch.record_decoded_frontier_transition();
if crate::fixed_point_scratch::copy_if_converged(
&scratch.next,
&scratch.frontier_words,
result,
)? {
return Ok(());
}
std::mem::swap(&mut scratch.frontier_words, &mut scratch.next);
}
Err(format!(
"points_to subset_closure_via did not converge within {max_iterations} iterations"
))
}