regalloc2 0.15.1

//! Fuzz the dominator-tree calculation.

use crate::{domtree, postorder, Block};
use arbitrary::{Arbitrary, Result, Unstructured};
use std::collections::HashSet;
use std::{vec, vec::Vec};

#[derive(Clone, Debug)]
struct CFG {
    num_blocks: usize,
    preds: Vec<Vec<Block>>,
    succs: Vec<Vec<Block>>,
}

impl Arbitrary<'_> for CFG {
    fn arbitrary(u: &mut Unstructured) -> Result<CFG> {
        let num_blocks = u.int_in_range(1..=1000)?;
        let mut succs = vec![];
        for _ in 0..num_blocks {
            let mut block_succs = vec![];
            for _ in 0..u.int_in_range(0..=5)? {
                block_succs.push(Block::new(u.int_in_range(0..=(num_blocks - 1))?));
            }
            succs.push(block_succs);
        }
        let mut preds = vec![];
        for _ in 0..num_blocks {
            preds.push(vec![]);
        }
        for from in 0..num_blocks {
            for succ in &succs[from] {
                preds[succ.index()].push(Block::new(from));
            }
        }
        Ok(CFG {
            num_blocks,
            preds,
            succs,
        })
    }
}

#[derive(Clone, Debug)]
struct Path {
    blocks: Vec<Block>,
}

impl Path {
    fn choose_from_cfg(cfg: &CFG, u: &mut Unstructured) -> Result<Path> {
        let succs = u.int_in_range(0..=(2 * cfg.num_blocks))?;
        let mut block = Block::new(0);
        let mut blocks = vec![];
        blocks.push(block);
        for _ in 0..succs {
            if cfg.succs[block.index()].is_empty() {
                break;
            }
            block = *u.choose(&cfg.succs[block.index()])?;
            blocks.push(block);
        }
        Ok(Path { blocks })
    }
}

fn check_idom_violations(idom: &[Block], path: &Path) {
    // "a dom b" means that any path from the entry block through the CFG that
    // contains a and b will contain a before b.
    //
    // To test this, for any given block b_i, we have the set S of b_0 ..
    // b_{i-1}, and we walk up the domtree from b_i to get all blocks that
    // dominate b_i; each such block must appear in S. (Otherwise, we have a
    // counterexample for which dominance says it should appear in the path
    // prefix, but it does not.)
    let mut visited = HashSet::new();
    visited.insert(Block::new(0));
    for block in &path.blocks {
        let mut parent = idom[block.index()];
        let mut domset = HashSet::new();
        domset.insert(*block);
        while parent.is_valid() {
            assert!(visited.contains(&parent));
            domset.insert(parent);
            let next = idom[parent.index()];
            parent = next;
        }

        // Check that `dominates()` returns true for every block in domset,
        // and false for every other block.
        for domblock in 0..idom.len() {
            let domblock = Block::new(domblock);
            assert_eq!(
                domset.contains(&domblock),
                domtree::dominates(idom, domblock, *block)
            );
        }
        visited.insert(*block);
    }
}

/// A control-flow graph ([`CFG`]) and a [`Path`] through it.
#[derive(Clone, Debug)]
pub struct TestCase {
    cfg: CFG,
    path: Path,
}

impl Arbitrary<'_> for TestCase {
    fn arbitrary(u: &mut Unstructured) -> Result<TestCase> {
        let cfg = CFG::arbitrary(u)?;
        let path = Path::choose_from_cfg(&cfg, u)?;
        Ok(TestCase { cfg, path })
    }
}

pub fn check(t: TestCase) {
    let mut postorder = vec![];
    postorder::calculate(
        t.cfg.num_blocks,
        Block::new(0),
        &mut vec![],
        &mut postorder,
        |block| &t.cfg.succs[block.index()],
    )
    .unwrap();

    let mut idom = vec![];
    domtree::calculate(
        t.cfg.num_blocks,
        |block| &t.cfg.preds[block.index()],
        &postorder[..],
        &mut vec![],
        &mut idom,
        Block::new(0),
    );
    check_idom_violations(&idom[..], &t.path);
}

#[test]
fn smoke() {
    arbtest::arbtest(|u| {
        let test_case = TestCase::arbitrary(u)?;
        check(test_case);
        Ok(())
    })
    .budget_ms(1_000);
}