#[derive(Debug, Clone, PartialEq, Eq)]
pub struct IfdsProblemFixture {
pub num_procs: u32,
pub blocks_per_proc: u32,
pub facts_per_proc: u32,
pub intra_edges: Vec<(u32, u32, u32)>,
pub inter_edges: Vec<(u32, u32, u32, u32)>,
pub flow_gen: Vec<(u32, u32, u32)>,
pub flow_kill: Vec<(u32, u32, u32)>,
pub seed_facts: Vec<(u32, u32, u32)>,
pub expected_reached: Vec<u32>,
}
pub struct IfdsProblemBuilder;
impl IfdsProblemBuilder {
#[allow(clippy::too_many_arguments)]
pub fn random_valid(
num_procs: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
intra_edge_count: u32,
seed_count: u32,
summary_edge_count: u32,
seed: u64,
) -> IfdsProblemFixture {
assert!(
num_procs > 0 && blocks_per_proc > 0 && facts_per_proc > 0,
"IfdsProblemBuilder::random_valid requires non-zero dimensions"
);
let _ = checked_total_nodes(num_procs, blocks_per_proc, facts_per_proc);
let mut rng = SplitMix64::new(
seed ^ ((num_procs as u64) << 42)
^ ((blocks_per_proc as u64) << 21)
^ facts_per_proc as u64,
);
let mut intra_edges = Vec::with_capacity(intra_edge_count as usize);
for edge_idx in 0..intra_edge_count {
let proc_id = if edge_idx < num_procs {
edge_idx
} else {
rng.below(num_procs)
};
let src_block = if blocks_per_proc <= 1 {
0
} else if edge_idx < blocks_per_proc - 1 {
edge_idx
} else {
rng.below(blocks_per_proc)
};
let mut dst_block = if blocks_per_proc <= 1 {
0
} else if edge_idx < blocks_per_proc - 1 {
src_block + 1
} else {
rng.below(blocks_per_proc)
};
if blocks_per_proc > 1 && dst_block == src_block {
dst_block = (dst_block + 1) % blocks_per_proc;
}
intra_edges.push((proc_id % num_procs, src_block, dst_block));
}
let mut inter_edges = Vec::with_capacity(summary_edge_count as usize);
for _ in 0..summary_edge_count {
let src_proc = rng.below(num_procs);
let mut dst_proc = rng.below(num_procs);
if num_procs > 1 && dst_proc == src_proc {
dst_proc = (dst_proc + 1) % num_procs;
}
inter_edges.push((
src_proc,
rng.below(blocks_per_proc),
dst_proc,
rng.below(blocks_per_proc),
));
}
let mut flow_gen = Vec::with_capacity(summary_edge_count as usize);
let mut flow_kill = Vec::with_capacity((summary_edge_count / 2) as usize);
for rule_idx in 0..summary_edge_count {
let proc_id = rng.below(num_procs);
let block_id = rng.below(blocks_per_proc);
let gen_fact = rng.below(facts_per_proc);
flow_gen.push((proc_id, block_id, gen_fact));
if rule_idx % 2 == 1 {
let kill_fact = if facts_per_proc > 1 {
1 + rng.below(facts_per_proc - 1)
} else {
0
};
flow_kill.push((proc_id, block_id, kill_fact));
}
}
let mut seed_facts = Vec::with_capacity(seed_count as usize);
for seed_idx in 0..seed_count {
let proc_id = if seed_idx < num_procs {
seed_idx
} else {
rng.below(num_procs)
};
let block_id = if blocks_per_proc > 1 && seed_idx == 0 {
0
} else {
rng.below(blocks_per_proc)
};
let fact_id = if facts_per_proc > 1 && seed_idx == 0 {
0
} else {
rng.below(facts_per_proc)
};
seed_facts.push((proc_id % num_procs, block_id, fact_id));
}
let expected_reached = expected_reachability(
num_procs,
blocks_per_proc,
facts_per_proc,
&intra_edges,
&inter_edges,
&flow_gen,
&flow_kill,
&seed_facts,
);
IfdsProblemFixture {
num_procs,
blocks_per_proc,
facts_per_proc,
intra_edges,
inter_edges,
flow_gen,
flow_kill,
seed_facts,
expected_reached,
}
}
pub fn adversarial_zero_dimensions() -> IfdsProblemFixture {
IfdsProblemFixture {
num_procs: 0,
blocks_per_proc: 1,
facts_per_proc: 1,
intra_edges: Vec::new(),
inter_edges: Vec::new(),
flow_gen: Vec::new(),
flow_kill: Vec::new(),
seed_facts: Vec::new(),
expected_reached: Vec::new(),
}
}
pub fn adversarial_overflow_shape() -> IfdsProblemFixture {
IfdsProblemFixture {
num_procs: 4097,
blocks_per_proc: 1,
facts_per_proc: 1,
intra_edges: Vec::new(),
inter_edges: Vec::new(),
flow_gen: Vec::new(),
flow_kill: Vec::new(),
seed_facts: Vec::new(),
expected_reached: Vec::new(),
}
}
}
#[allow(clippy::too_many_arguments)]
fn expected_reachability(
num_procs: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
intra_edges: &[(u32, u32, u32)],
inter_edges: &[(u32, u32, u32, u32)],
flow_gen: &[(u32, u32, u32)],
flow_kill: &[(u32, u32, u32)],
seed_facts: &[(u32, u32, u32)],
) -> Vec<u32> {
let total_nodes = checked_total_nodes(num_procs, blocks_per_proc, facts_per_proc);
let mut killed = vec![false; total_nodes];
for &(proc_id, block_id, fact_id) in flow_kill {
killed[dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc)] = true;
}
let mut visited = vec![false; total_nodes];
let mut queue = Vec::with_capacity(seed_facts.len());
for &(proc_id, block_id, fact_id) in seed_facts {
mark_reached(
proc_id,
block_id,
fact_id,
blocks_per_proc,
facts_per_proc,
&mut visited,
&mut queue,
);
}
let mut head = 0usize;
while head < queue.len() {
let (proc_id, block_id, fact_id) = queue[head];
head += 1;
for &(edge_proc, src_block, dst_block) in intra_edges {
if edge_proc != proc_id || src_block != block_id {
continue;
}
let current_idx =
dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc);
if !killed[current_idx] {
mark_reached(
proc_id,
dst_block,
fact_id,
blocks_per_proc,
facts_per_proc,
&mut visited,
&mut queue,
);
}
if fact_id == 0 {
for &(gen_proc, gen_block, gen_fact) in flow_gen {
if gen_proc == proc_id && gen_block == block_id {
mark_reached(
proc_id,
dst_block,
gen_fact,
blocks_per_proc,
facts_per_proc,
&mut visited,
&mut queue,
);
}
}
}
}
for &(src_proc, src_block, dst_proc, dst_block) in inter_edges {
if src_proc == proc_id && src_block == block_id {
mark_reached(
dst_proc,
dst_block,
fact_id,
blocks_per_proc,
facts_per_proc,
&mut visited,
&mut queue,
);
}
}
}
visited
.into_iter()
.enumerate()
.filter_map(|(dense_id, reached)| reached.then_some(dense_id as u32))
.collect()
}
fn mark_reached(
proc_id: u32,
block_id: u32,
fact_id: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
visited: &mut [bool],
queue: &mut Vec<(u32, u32, u32)>,
) {
let idx = dense_index(proc_id, block_id, fact_id, blocks_per_proc, facts_per_proc);
if !visited[idx] {
visited[idx] = true;
queue.push((proc_id, block_id, fact_id));
}
}
fn checked_total_nodes(num_procs: u32, blocks_per_proc: u32, facts_per_proc: u32) -> usize {
let total = (num_procs as u64)
.checked_mul(blocks_per_proc as u64)
.and_then(|value| value.checked_mul(facts_per_proc as u64))
;
assert!(
total.is_some(),
"IFDS fixture node count overflows u64"
);
let total = total.unwrap_or(u64::MAX);
assert!(
total <= u32::MAX as u64,
"IFDS fixture node count {total} exceeds u32 dense domain"
);
assert!(
total <= usize::MAX as u64,
"IFDS fixture node count {total} does not fit usize"
);
total as usize
}
fn dense_index(
proc_id: u32,
block_id: u32,
fact_id: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
) -> usize {
let idx = (proc_id as u64)
.checked_mul(blocks_per_proc as u64)
.and_then(|value| value.checked_mul(facts_per_proc as u64))
.and_then(|value| {
(block_id as u64)
.checked_mul(facts_per_proc as u64)
.and_then(|block_offset| value.checked_add(block_offset))
})
.and_then(|value| value.checked_add(fact_id as u64))
;
assert!(idx.is_some(), "IFDS fixture dense index overflows u64");
let idx = idx.unwrap_or(u64::MAX);
assert!(
idx <= usize::MAX as u64,
"IFDS fixture dense index {idx} does not fit usize"
);
idx as usize
}
#[derive(Debug, Clone, Copy)]
struct SplitMix64 {
state: u64,
}
impl SplitMix64 {
fn new(seed: u64) -> Self {
Self {
state: seed ^ 0x9e37_79b9_7f4a_7c15,
}
}
fn next(&mut self) -> u64 {
self.state = self.state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = self.state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
fn below(&mut self, upper: u32) -> u32 {
if upper == 0 {
return 0;
}
(self.next() % upper as u64) as u32
}
}