weir/test_harness/
dominator_fixture.rs

1//! Reusable CFG fixtures for dominator-analysis tests.
2
3use std::collections::{HashMap, HashSet};
4
5use rand::{Rng, SeedableRng};
6
7use crate::ssa::{try_compute_dominators, Block, Cfg};
8
9#[derive(Clone, Debug)]
10pub struct CfgFixture {
11    pub node_count: u32,
12    pub entry: u32,
13    pub preds: Vec<Vec<u32>>,
14    pub succs: Vec<Vec<u32>>,
15    pub idoms: HashMap<u32, u32>,
16}
17
18pub struct DominatorFixture;
19
20impl DominatorFixture {
21    pub fn random_dag(node_count: u32, edge_probability: f64, seed: u64) -> CfgFixture {
22        if node_count == 0 {
23            return empty_fixture();
24        }
25        let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
26        let probability = edge_probability.clamp(0.0, 1.0);
27        let mut succs = vec![Vec::new(); node_count as usize];
28
29        for dst in 1..node_count {
30            let parent = rng.random_range(0..dst);
31            succs[parent as usize].push(dst);
32        }
33        for src in 0..node_count {
34            for dst in (src + 1)..node_count {
35                if rng.random::<f64>() < probability {
36                    succs[src as usize].push(dst);
37                }
38            }
39        }
40        normalize_fixture(node_count, 0, succs)
41    }
42
43    pub fn random_irreducible(node_count: u32, edge_probability: f64, seed: u64) -> CfgFixture {
44        let mut fixture = Self::random_dag(node_count, edge_probability, seed);
45        if node_count > 1 {
46            fixture.succs[(node_count - 1) as usize].push(0);
47            if node_count > 2 {
48                fixture.succs[(node_count - 1) as usize].push(1);
49                fixture.succs[1].push(node_count - 1);
50            }
51            fixture = normalize_fixture(node_count, 0, fixture.succs);
52        }
53        fixture
54    }
55}
56
57fn empty_fixture() -> CfgFixture {
58    CfgFixture {
59        node_count: 0,
60        entry: 0,
61        preds: Vec::new(),
62        succs: Vec::new(),
63        idoms: HashMap::new(),
64    }
65}
66
67fn normalize_fixture(node_count: u32, entry: u32, mut succs: Vec<Vec<u32>>) -> CfgFixture {
68    for targets in &mut succs {
69        targets.retain(|target| *target < node_count);
70        targets.sort_unstable();
71        targets.dedup();
72    }
73
74    let mut preds = vec![Vec::new(); node_count as usize];
75    for (src, targets) in succs.iter().enumerate() {
76        for &dst in targets {
77            preds[dst as usize].push(src as u32);
78        }
79    }
80    for sources in &mut preds {
81        sources.sort_unstable();
82        sources.dedup();
83    }
84
85    let cfg = cfg_from_parts(entry, &preds, &succs);
86    let idoms = try_compute_dominators(&cfg).unwrap_or_default();
87    CfgFixture {
88        node_count,
89        entry,
90        preds,
91        succs,
92        idoms,
93    }
94}
95
96fn cfg_from_parts(entry: u32, preds: &[Vec<u32>], succs: &[Vec<u32>]) -> Cfg {
97    let mut blocks = HashMap::with_capacity(succs.len());
98    for id in 0..succs.len() as u32 {
99        blocks.insert(
100            id,
101            Block {
102                id,
103                preds: preds[id as usize].clone(),
104                succs: succs[id as usize].clone(),
105                defs: HashSet::new(),
106                uses: HashSet::new(),
107            },
108        );
109    }
110    Cfg { entry, blocks }
111}
weir/test_harness/dominator_fixture.rs

weir/test_harness/
dominator_fixture.rs
