/src/regalloc2/src/fuzzing/func.rs

Source (jump to first uncovered line)
/*
 * Released under the terms of the Apache 2.0 license with LLVM
 * exception. See `LICENSE` for details.
 */

use crate::{
    domtree, postorder, Allocation, Block, Function, Inst, InstRange, MachineEnv, Operand,
    OperandConstraint, OperandKind, OperandPos, PReg, PRegSet, RegClass, VReg,
};

use alloc::vec::Vec;
use alloc::{format, vec};

use super::arbitrary::Result as ArbitraryResult;
use super::arbitrary::{Arbitrary, Unstructured};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum InstOpcode {
    Op,
    Ret,
    Branch,
}

#[derive(Clone, Debug)]
pub struct InstData {
    op: InstOpcode,
    operands: Vec<Operand>,
    clobbers: Vec<PReg>,
    is_safepoint: bool,
}

impl InstData {
    pub fn op(def: usize, uses: &[usize]) -> InstData {
        let mut operands = vec![Operand::reg_def(VReg::new(def, RegClass::Int))];
        for &u in uses {
            operands.push(Operand::reg_use(VReg::new(u, RegClass::Int)));
        }
        InstData {
            op: InstOpcode::Op,
            operands,
            clobbers: vec![],
            is_safepoint: false,
        }
    }
    pub fn branch() -> InstData {
        InstData {
            op: InstOpcode::Branch,
            operands: vec![],
            clobbers: vec![],
            is_safepoint: false,
        }
    }
    pub fn ret() -> InstData {
        InstData {
            op: InstOpcode::Ret,
            operands: vec![],
            clobbers: vec![],
            is_safepoint: false,
        }
    }
}

#[derive(Clone)]
pub struct Func {
    insts: Vec<InstData>,
    blocks: Vec<InstRange>,
    block_preds: Vec<Vec<Block>>,
    block_succs: Vec<Vec<Block>>,
    block_params_in: Vec<Vec<VReg>>,
    block_params_out: Vec<Vec<Vec<VReg>>>,
    num_vregs: usize,
    reftype_vregs: Vec<VReg>,
    debug_value_labels: Vec<(VReg, Inst, Inst, u32)>,
}

impl Function for Func {
    fn num_insts(&self) -> usize {
        self.insts.len()
    }

    fn num_blocks(&self) -> usize {
        self.blocks.len()
    }

    fn entry_block(&self) -> Block {
        debug_assert!(self.blocks.len() > 0);
        Block::new(0)
    }

    fn block_insns(&self, block: Block) -> InstRange {
        self.blocks[block.index()]
    }

    fn block_succs(&self, block: Block) -> &[Block] {
        &self.block_succs[block.index()][..]
    }

    fn block_preds(&self, block: Block) -> &[Block] {
        &self.block_preds[block.index()][..]
    }

    fn block_params(&self, block: Block) -> &[VReg] {
        &self.block_params_in[block.index()][..]
    }

    fn is_ret(&self, insn: Inst) -> bool {
        self.insts[insn.index()].op == InstOpcode::Ret
    }

    fn is_branch(&self, insn: Inst) -> bool {
        self.insts[insn.index()].op == InstOpcode::Branch
    }

    fn branch_blockparams(&self, block: Block, _: Inst, succ: usize) -> &[VReg] {
        &self.block_params_out[block.index()][succ][..]
    }

    fn requires_refs_on_stack(&self, insn: Inst) -> bool {
        self.insts[insn.index()].is_safepoint
    }

    fn reftype_vregs(&self) -> &[VReg] {
        &self.reftype_vregs[..]
    }

    fn debug_value_labels(&self) -> &[(VReg, Inst, Inst, u32)] {
        &self.debug_value_labels[..]
    }

    fn inst_operands(&self, insn: Inst) -> &[Operand] {
        &self.insts[insn.index()].operands[..]
    }

    fn inst_clobbers(&self, insn: Inst) -> PRegSet {
        let mut set = PRegSet::default();
        for &preg in &self.insts[insn.index()].clobbers {
            set = set.with(preg);
        }
        set
    }

    fn num_vregs(&self) -> usize {
        self.num_vregs
    }

    fn spillslot_size(&self, regclass: RegClass) -> usize {
        match regclass {
            RegClass::Int => 1,
            RegClass::Float => 2,
        }
    }
}

struct FuncBuilder {
    postorder: Vec<Block>,
    idom: Vec<Block>,
    f: Func,
    insts_per_block: Vec<Vec<InstData>>,
}

impl FuncBuilder {
    fn new() -> Self {
        FuncBuilder {
            postorder: vec![],
            idom: vec![],
            f: Func {
                block_preds: vec![],
                block_succs: vec![],
                block_params_in: vec![],
                block_params_out: vec![],
                insts: vec![],
                blocks: vec![],
                num_vregs: 0,
                reftype_vregs: vec![],
                debug_value_labels: vec![],
            },
            insts_per_block: vec![],
        }
    }

    pub fn add_block(&mut self) -> Block {
        let b = Block::new(self.f.blocks.len());
        self.f
            .blocks
            .push(InstRange::forward(Inst::new(0), Inst::new(0)));
        self.f.block_preds.push(vec![]);
        self.f.block_succs.push(vec![]);
        self.f.block_params_in.push(vec![]);
        self.f.block_params_out.push(vec![]);
        self.insts_per_block.push(vec![]);
        b
    }

    pub fn add_inst(&mut self, block: Block, data: InstData) {
        self.insts_per_block[block.index()].push(data);
    }

    pub fn add_edge(&mut self, from: Block, to: Block) {
        self.f.block_succs[from.index()].push(to);
        self.f.block_preds[to.index()].push(from);
    }

    pub fn set_block_params_in(&mut self, block: Block, params: &[VReg]) {
        self.f.block_params_in[block.index()] = params.iter().cloned().collect();
    }

    pub fn set_block_params_out(&mut self, block: Block, params: Vec<Vec<VReg>>) {
        self.f.block_params_out[block.index()] = params;
    }

    fn compute_doms(&mut self) {
        self.postorder = postorder::calculate(self.f.blocks.len(), Block::new(0), |block| {
            &self.f.block_succs[block.index()][..]
        });
        self.idom = domtree::calculate(
            self.f.blocks.len(),
            |block| &self.f.block_preds[block.index()][..],
            &self.postorder[..],
            Block::new(0),
        );
    }

    fn finalize(mut self) -> Func {
        for (blocknum, blockrange) in self.f.blocks.iter_mut().enumerate() {
            let begin_inst = self.f.insts.len();
            for inst in &self.insts_per_block[blocknum] {
                self.f.insts.push(inst.clone());
            }
            let end_inst = self.f.insts.len();
            *blockrange = InstRange::forward(Inst::new(begin_inst), Inst::new(end_inst));
        }

        self.f
    }
}

impl Arbitrary<'_> for OperandConstraint {
    fn arbitrary(u: &mut Unstructured) -> ArbitraryResult<Self> {
        Ok(*u.choose(&[OperandConstraint::Any, OperandConstraint::Reg])?)
    }
}

fn choose_dominating_block(
    idom: &[Block],
    mut block: Block,
    allow_self: bool,
    u: &mut Unstructured,
) -> ArbitraryResult<Block> {
    debug_assert!(block.is_valid());
    let orig_block = block;
    loop {
        if (allow_self || block != orig_block) && bool::arbitrary(u)? {
            break;
        }
        if idom[block.index()].is_invalid() {
            break;
        }
        block = idom[block.index()];
    }
    let block = if block != orig_block || allow_self {
        block
    } else {
        Block::invalid()
    };
    Ok(block)
}

#[derive(Clone, Copy, Debug)]
pub struct Options {
    pub reused_inputs: bool,
    pub fixed_regs: bool,
    pub fixed_nonallocatable: bool,
    pub clobbers: bool,
    pub control_flow: bool,
    pub reducible: bool,
    pub block_params: bool,
    pub always_local_uses: bool,
    pub reftypes: bool,
}

impl core::default::Default for Options {
    fn default() -> Self {
        Options {
            reused_inputs: false,
            fixed_regs: false,
            fixed_nonallocatable: false,
            clobbers: false,
            control_flow: true,
            reducible: false,
            block_params: true,
            always_local_uses: false,
            reftypes: false,
        }
    }
}

impl Arbitrary<'_> for Func {
    fn arbitrary(u: &mut Unstructured) -> ArbitraryResult<Func> {
        Func::arbitrary_with_options(u, &Options::default())
    }
}

impl Func {
    pub fn arbitrary_with_options(u: &mut Unstructured, opts: &Options) -> ArbitraryResult<Func> {
        // General strategy:
        // 1. Create an arbitrary CFG.
        // 2. Create a list of vregs to define in each block.
        // 3. Define some of those vregs in each block as blockparams.f.
        // 4. Populate blocks with ops that define the rest of the vregs.
        //    - For each use, choose an available vreg: either one
        //      already defined (via blockparam or inst) in this block,
        //      or one defined in a dominating block.

        let mut builder = FuncBuilder::new();
        for _ in 0..u.int_in_range(1..=100)? {
            builder.add_block();
        }
        let num_blocks = builder.f.blocks.len();

        // Generate a CFG. Create a "spine" of either single blocks,
        // with links to the next; or fork patterns, with the left
        // fork linking to the next and the right fork in `out_blocks`
        // to be connected below. This creates an arbitrary CFG with
        // split critical edges, which is a property that we require
        // for the regalloc.
        let mut from = 0;
        let mut out_blocks = vec![];
        let mut in_blocks = vec![];
        // For reducibility, if selected: enforce strict nesting of backedges
        let mut max_backedge_src = 0;
        let mut min_backedge_dest = num_blocks;
        while from < num_blocks {
            in_blocks.push(from);
            if num_blocks > 3 && from < num_blocks - 3 && bool::arbitrary(u)? && opts.control_flow {
                // To avoid critical edges, we use from+1 as an edge
                // block, and advance `from` an extra block; `from+2`
                // will be the next normal iteration.
                builder.add_edge(Block::new(from), Block::new(from + 1));
                builder.add_edge(Block::new(from), Block::new(from + 2));
                builder.add_edge(Block::new(from + 2), Block::new(from + 3));
                out_blocks.push(from + 1);
                from += 2;
            } else if from < num_blocks - 1 {
                builder.add_edge(Block::new(from), Block::new(from + 1));
            }
            from += 1;
        }
        for pred in out_blocks {
            let mut succ = *u.choose(&in_blocks[..])?;
            if opts.reducible && (pred >= succ) {
                if pred < max_backedge_src || succ > min_backedge_dest {
                    // If the chosen edge would result in an
                    // irreducible CFG, just make this a diamond
                    // instead.
                    succ = pred + 2;
                } else {
                    max_backedge_src = pred;
                    min_backedge_dest = succ;
                }
            }
            builder.add_edge(Block::new(pred), Block::new(succ));
        }

        builder.compute_doms();

        for block in 0..num_blocks {
            builder.f.block_preds[block].clear();
        }
        for block in 0..num_blocks {
            for &succ in &builder.f.block_succs[block] {
                builder.f.block_preds[succ.index()].push(Block::new(block));
            }
        }

        builder.compute_doms();

        let mut vregs_by_block = vec![];
        let mut vregs_by_block_to_be_defined = vec![];
        let mut block_params = vec![vec![]; num_blocks];
        for block in 0..num_blocks {
            let mut vregs = vec![];
            for _ in 0..u.int_in_range(5..=15)? {
                let vreg = VReg::new(builder.f.num_vregs, RegClass::Int);
                builder.f.num_vregs += 1;
                vregs.push(vreg);
                if opts.reftypes && bool::arbitrary(u)? {
                    builder.f.reftype_vregs.push(vreg);
                }
                if bool::arbitrary(u)? {
                    let assumed_end_inst = 10 * num_blocks;
                    let mut start = u.int_in_range::<usize>(0..=assumed_end_inst)?;
                    for _ in 0..10 {
                        if start >= assumed_end_inst {
                            break;
                        }
                        let end = u.int_in_range::<usize>(start..=assumed_end_inst)?;
                        let label = u.int_in_range::<u32>(0..=100)?;
                        builder.f.debug_value_labels.push((
                            vreg,
                            Inst::new(start),
                            Inst::new(end),
                            label,
                        ));
                        start = end;
                    }
                }
            }
            vregs_by_block.push(vregs.clone());
            vregs_by_block_to_be_defined.push(vec![]);
            let mut max_block_params = u.int_in_range(0..=core::cmp::min(3, vregs.len() / 3))?;
            for &vreg in &vregs {
                if block > 0 && opts.block_params && bool::arbitrary(u)? && max_block_params > 0 {
                    block_params[block].push(vreg);
                    max_block_params -= 1;
                } else {
                    vregs_by_block_to_be_defined.last_mut().unwrap().push(vreg);
                }
            }
            vregs_by_block_to_be_defined.last_mut().unwrap().reverse();
            builder.set_block_params_in(Block::new(block), &block_params[block][..]);
        }

        for block in 0..num_blocks {
            let mut avail = block_params[block].clone();
            let mut remaining_nonlocal_uses = u.int_in_range(0..=3)?;
            while let Some(vreg) = vregs_by_block_to_be_defined[block].pop() {
                let def_constraint = OperandConstraint::arbitrary(u)?;
                let def_pos = if bool::arbitrary(u)? {
                    OperandPos::Early
                } else {
                    OperandPos::Late
                };
                let mut operands = vec![Operand::new(
                    vreg,
                    def_constraint,
                    OperandKind::Def,
                    def_pos,
                )];
                let mut allocations = vec![Allocation::none()];
                for _ in 0..u.int_in_range(0..=3)? {
                    let vreg = if avail.len() > 0
                        && (opts.always_local_uses
                            || remaining_nonlocal_uses == 0
                            || bool::arbitrary(u)?)
                    {
                        *u.choose(&avail[..])?
                    } else if !opts.always_local_uses {
                        let def_block = choose_dominating_block(
                            &builder.idom[..],
                            Block::new(block),
                            /* allow_self = */ false,
                            u,
                        )?;
                        if !def_block.is_valid() {
                            // No vregs already defined, and no pred blocks that dominate us
                            // (perhaps we are the entry block): just stop generating inputs.
                            break;
                        }
                        remaining_nonlocal_uses -= 1;
                        *u.choose(&vregs_by_block[def_block.index()])?
                    } else {
                        break;
                    };
                    let use_constraint = OperandConstraint::arbitrary(u)?;
                    operands.push(Operand::new(
                        vreg,
                        use_constraint,
                        OperandKind::Use,
                        OperandPos::Early,
                    ));
                    allocations.push(Allocation::none());
                }
                let mut clobbers: Vec<PReg> = vec![];
                if operands.len() > 1 && opts.reused_inputs && bool::arbitrary(u)? {
                    // Make the def a reused input.
                    let op = operands[0];
                    debug_assert_eq!(op.kind(), OperandKind::Def);
                    let reused = u.int_in_range(1..=(operands.len() - 1))?;
                    operands[0] = Operand::new(
                        op.vreg(),
                        OperandConstraint::Reuse(reused),
                        op.kind(),
                        OperandPos::Late,
                    );
                    // Make sure reused input is a Reg.
                    let op = operands[reused];
                    operands[reused] = Operand::new(
                        op.vreg(),
                        OperandConstraint::Reg,
                        op.kind(),
                        OperandPos::Early,
                    );
                } else if opts.fixed_regs && bool::arbitrary(u)? {
                    let mut fixed_early = vec![];
                    let mut fixed_late = vec![];
                    for _ in 0..u.int_in_range(0..=operands.len() - 1)? {
                        // Pick an operand and make it a fixed reg.
                        let i = u.int_in_range(0..=(operands.len() - 1))?;
                        let op = operands[i];
                        let fixed_reg = PReg::new(u.int_in_range(0..=62)?, RegClass::Int);
                        let fixed_list = match op.pos() {
                            OperandPos::Early => &mut fixed_early,
                            OperandPos::Late => &mut fixed_late,
                        };
                        if fixed_list.contains(&fixed_reg) {
                            break;
                        }
                        if op.kind() != OperandKind::Def && op.pos() == OperandPos::Late {
                            // Late-uses/mods with fixed constraints
                            // can't be allowed if we're allowing
                            // different constraints at Early and
                            // Late, because we can't move something
                            // into a location between Early and
                            // Late. Differing constraints only make
                            // sense if the instruction itself
                            // produces the newly-constrained values.
                            break;
                        }
                        if op.kind() != OperandKind::Use && op.pos() == OperandPos::Early {
                            // Likewise, we can *only* allow uses for
                            // fixed constraints at Early.
                            break;
                        }
                        fixed_list.push(fixed_reg);
                        operands[i] = Operand::new(
                            op.vreg(),
                            OperandConstraint::FixedReg(fixed_reg),
                            op.kind(),
                            op.pos(),
                        );
                    }
                } else if opts.clobbers && bool::arbitrary(u)? {
                    for _ in 0..u.int_in_range(0..=5)? {
                        let reg = u.int_in_range(0..=30)?;
                        if clobbers.iter().any(|r| r.hw_enc() == reg) {
                            break;
                        }
                        clobbers.push(PReg::new(reg, RegClass::Int));
                    }
                } else if opts.fixed_nonallocatable && bool::arbitrary(u)? {
                    operands.push(Operand::fixed_nonallocatable(PReg::new(63, RegClass::Int)));
                }

                let is_safepoint = opts.reftypes
                    && operands
                        .iter()
                        .all(|op| !builder.f.reftype_vregs.contains(&op.vreg()))
                    && bool::arbitrary(u)?;

                builder.add_inst(
                    Block::new(block),
                    InstData {
                        op: InstOpcode::Op,
                        operands,
                        clobbers,
                        is_safepoint,
                    },
                );
                avail.push(vreg);
            }

            // Define the branch with blockparam args that must end
            // the block.
            if builder.f.block_succs[block].len() > 0 {
                let mut params = vec![];
                for &succ in &builder.f.block_succs[block] {
                    let mut args = vec![];
                    for _ in 0..builder.f.block_params_in[succ.index()].len() {
                        let dom_block = choose_dominating_block(
                            &builder.idom[..],
                            Block::new(block),
                            false,
                            u,
                        )?;
                        let vreg = if dom_block.is_valid() && bool::arbitrary(u)? {
                            u.choose(&vregs_by_block[dom_block.index()][..])?
                        } else {
                            u.choose(&avail[..])?
                        };
                        args.push(*vreg);
                    }
                    params.push(args);
                }
                builder.set_block_params_out(Block::new(block), params);
                builder.add_inst(Block::new(block), InstData::branch());
            } else {
                builder.add_inst(Block::new(block), InstData::ret());
            }
        }

        builder.f.debug_value_labels.sort_unstable();

        Ok(builder.finalize())
    }
}

impl core::fmt::Debug for Func {
    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
        write!(f, "{{\n")?;
        for vreg in self.reftype_vregs() {
            write!(f, "  REF: {}\n", vreg)?;
        }
        for (i, blockrange) in self.blocks.iter().enumerate() {
            let succs = self.block_succs[i]
                .iter()
                .map(|b| b.index())
                .collect::<Vec<_>>();
            let preds = self.block_preds[i]
                .iter()
                .map(|b| b.index())
                .collect::<Vec<_>>();
            let params_in = self.block_params_in[i]
                .iter()
                .map(|v| format!("v{}", v.vreg()))
                .collect::<Vec<_>>()
                .join(", ");
            let params_out = self.block_params_out[i]
                .iter()
                .enumerate()
                .map(|(succ_idx, vec)| {
                    let succ = self.block_succs[i][succ_idx];
                    let params = vec
                        .iter()
                        .map(|v| format!("v{}", v.vreg()))
                        .collect::<Vec<_>>()
                        .join(", ");
                    format!("block{}({})", succ.index(), params)
                })
                .collect::<Vec<_>>()
                .join(", ");
            write!(
                f,
                "  block{}({}): # succs:{:?} preds:{:?}\n",
                i, params_in, succs, preds
            )?;
            for inst in blockrange.iter() {
                if self.requires_refs_on_stack(inst) {
                    write!(f, "    -- SAFEPOINT --\n")?;
                }
                write!(
                    f,
                    "    inst{}: {:?} ops:{:?} clobber:{:?}\n",
                    inst.index(),
                    self.insts[inst.index()].op,
                    self.insts[inst.index()].operands,
                    self.insts[inst.index()].clobbers
                )?;
                if let InstOpcode::Branch = self.insts[inst.index()].op {
                    write!(f, "    params: {}\n", params_out)?;
                }
            }
        }
        write!(f, "}}\n")?;
        Ok(())
    }
}

pub fn machine_env() -> MachineEnv {
    fn regs(r: core::ops::Range<usize>) -> Vec<PReg> {
        r.map(|i| PReg::new(i, RegClass::Int)).collect()
    }
    let preferred_regs_by_class: [Vec<PReg>; 2] = [regs(0..24), vec![]];
    let non_preferred_regs_by_class: [Vec<PReg>; 2] = [regs(24..32), vec![]];
    let scratch_by_class: [Option<PReg>; 2] = [None, None];
    let fixed_stack_slots = regs(32..63);
    // Register 63 is reserved for use as a fixed non-allocatable register.
    MachineEnv {
        preferred_regs_by_class,
        non_preferred_regs_by_class,
        scratch_by_class,
        fixed_stack_slots,
    }
}

Coverage Report

Created: 2023-04-25 07:07

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Released under the terms of the Apache 2.0 license with LLVM
3		* exception. See `LICENSE` for details.
4		*/
5
6		use crate::{
7		domtree, postorder, Allocation, Block, Function, Inst, InstRange, MachineEnv, Operand,
8		OperandConstraint, OperandKind, OperandPos, PReg, PRegSet, RegClass, VReg,
9		};
10
11		use alloc::vec::Vec;
12		use alloc::{format, vec};
13
14		use super::arbitrary::Result as ArbitraryResult;
15		use super::arbitrary::{Arbitrary, Unstructured};
16
17	13.1M	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18		pub enum InstOpcode {
19		Op,
20		Ret,
21		Branch,
22		}
23
24	3.48M	#[derive(Clone, Debug)]
25		pub struct InstData {
26		op: InstOpcode,
27		operands: Vec<Operand>,
28		clobbers: Vec<PReg>,
29		is_safepoint: bool,
30		}
31
32		impl InstData {
33	0	pub fn op(def: usize, uses: &[usize]) -> InstData {
34	0	let mut operands = vec![Operand::reg_def(VReg::new(def, RegClass::Int))];
35	0	for &u in uses {
36	0	operands.push(Operand::reg_use(VReg::new(u, RegClass::Int)));
37	0	}
38	0	InstData {
39	0	op: InstOpcode::Op,
40	0	operands,
41	0	clobbers: vec![],
42	0	is_safepoint: false,
43	0	}
44	0	}
45	439k	pub fn branch() -> InstData {
46	439k	InstData {
47	439k	op: InstOpcode::Branch,
48	439k	operands: vec![],
49	439k	clobbers: vec![],
50	439k	is_safepoint: false,
51	439k	}
52	439k	}
53	9.54k	pub fn ret() -> InstData {
54	9.54k	InstData {
55	9.54k	op: InstOpcode::Ret,
56	9.54k	operands: vec![],
57	9.54k	clobbers: vec![],
58	9.54k	is_safepoint: false,
59	9.54k	}
60	9.54k	}
61		}
62
63	0	#[derive(Clone)]
64		pub struct Func {
65		insts: Vec<InstData>,
66		blocks: Vec<InstRange>,
67		block_preds: Vec<Vec<Block>>,
68		block_succs: Vec<Vec<Block>>,
69		block_params_in: Vec<Vec<VReg>>,
70		block_params_out: Vec<Vec<Vec<VReg>>>,
71		num_vregs: usize,
72		reftype_vregs: Vec<VReg>,
73		debug_value_labels: Vec<(VReg, Inst, Inst, u32)>,
74		}
75
76		impl Function for Func {
77	57.2k	fn num_insts(&self) -> usize {
78	57.2k	self.insts.len()
79	57.2k	}
80
81	19.6M	fn num_blocks(&self) -> usize {
82	19.6M	self.blocks.len()
83	19.6M	}
84
85	2.67M	fn entry_block(&self) -> Block {
86	0	debug_assert!(self.blocks.len() > 0);
87	2.67M	Block::new(0)
88	2.67M	}
89
90	7.14M	fn block_insns(&self, block: Block) -> InstRange {
91	7.14M	self.blocks[block.index()]
92	7.14M	}
93
94	11.5M	fn block_succs(&self, block: Block) -> &[Block] {
95	11.5M	&self.block_succs[block.index()][..]
96	11.5M	}
97
98	10.7M	fn block_preds(&self, block: Block) -> &[Block] {
99	10.7M	&self.block_preds[block.index()][..]
100	10.7M	}
101
102	3.02M	fn block_params(&self, block: Block) -> &[VReg] {
103	3.02M	&self.block_params_in[block.index()][..]
104	3.02M	}
105
106	4.68M	fn is_ret(&self, insn: Inst) -> bool {
107	4.68M	self.insts[insn.index()].op == InstOpcode::Ret
108	4.68M	}
109
110	8.44M	fn is_branch(&self, insn: Inst) -> bool {
111	8.44M	self.insts[insn.index()].op == InstOpcode::Branch
112	8.44M	}
113
114	2.40M	fn branch_blockparams(&self, block: Block, _: Inst, succ: usize) -> &[VReg] {
115	2.40M	&self.block_params_out[block.index()][succ][..]
116	2.40M	}
117
118	8.26M	fn requires_refs_on_stack(&self, insn: Inst) -> bool {
119	8.26M	self.insts[insn.index()].is_safepoint
120	8.26M	}
121
122	66.1k	fn reftype_vregs(&self) -> &[VReg] {
123	66.1k	&self.reftype_vregs[..]
124	66.1k	}
125
126	9.54k	fn debug_value_labels(&self) -> &[(VReg, Inst, Inst, u32)] {
127	9.54k	&self.debug_value_labels[..]
128	9.54k	}
129
130	62.3M	fn inst_operands(&self, insn: Inst) -> &[Operand] {
131	62.3M	&self.insts[insn.index()].operands[..]
132	62.3M	}
133
134	10.5M	fn inst_clobbers(&self, insn: Inst) -> PRegSet {
135	10.5M	let mut set = PRegSet::default();
136	10.5M	for &preg in &self.insts[insn.index()].clobbers {
137	532k	set = set.with(preg);
138	532k	}
139	10.5M	set
140	10.5M	}
141
142	19.0k	fn num_vregs(&self) -> usize {
143	19.0k	self.num_vregs
144	19.0k	}
145
146	3.30M	fn spillslot_size(&self, regclass: RegClass) -> usize {
147	3.30M	match regclass {
148	3.30M	RegClass::Int => 1,
149	0	RegClass::Float => 2,
150		}
151	3.30M	}
152		}
153
154		struct FuncBuilder {
155		postorder: Vec<Block>,
156		idom: Vec<Block>,
157		f: Func,
158		insts_per_block: Vec<Vec<InstData>>,
159		}
160
161		impl FuncBuilder {
162	9.54k	fn new() -> Self {
163	9.54k	FuncBuilder {
164	9.54k	postorder: vec![],
165	9.54k	idom: vec![],
166	9.54k	f: Func {
167	9.54k	block_preds: vec![],
168	9.54k	block_succs: vec![],
169	9.54k	block_params_in: vec![],
170	9.54k	block_params_out: vec![],
171	9.54k	insts: vec![],
172	9.54k	blocks: vec![],
173	9.54k	num_vregs: 0,
174	9.54k	reftype_vregs: vec![],
175	9.54k	debug_value_labels: vec![],
176	9.54k	},
177	9.54k	insts_per_block: vec![],
178	9.54k	}
179	9.54k	}
180
181	448k	pub fn add_block(&mut self) -> Block {
182	448k	let b = Block::new(self.f.blocks.len());
183	448k	self.f
184	448k	.blocks
185	448k	.push(InstRange::forward(Inst::new(0), Inst::new(0)));
186	448k	self.f.block_preds.push(vec![]);
187	448k	self.f.block_succs.push(vec![]);
188	448k	self.f.block_params_in.push(vec![]);
189	448k	self.f.block_params_out.push(vec![]);
190	448k	self.insts_per_block.push(vec![]);
191	448k	b
192	448k	}
193
194	3.48M	pub fn add_inst(&mut self, block: Block, data: InstData) {
195	3.48M	self.insts_per_block[block.index()].push(data);
196	3.48M	}
197
198	553k	pub fn add_edge(&mut self, from: Block, to: Block) {
199	553k	self.f.block_succs[from.index()].push(to);
200	553k	self.f.block_preds[to.index()].push(from);
201	553k	}
202
203	448k	pub fn set_block_params_in(&mut self, block: Block, params: &[VReg]) {
204	448k	self.f.block_params_in[block.index()] = params.iter().cloned().collect();
205	448k	}
206
207	439k	pub fn set_block_params_out(&mut self, block: Block, params: Vec<Vec<VReg>>) {
208	439k	self.f.block_params_out[block.index()] = params;
209	439k	}
210
211	19.0k	fn compute_doms(&mut self) {
212	897k	self.postorder = postorder::calculate(self.f.blocks.len(), Block::new(0), \|block\| {
213	897k	&self.f.block_succs[block.index()][..]
214	897k	});
215	19.0k	self.idom = domtree::calculate(
216	19.0k	self.f.blocks.len(),
217	4.40M	\|block\| &self.f.block_preds[block.index()][..],
218	19.0k	&self.postorder[..],
219	19.0k	Block::new(0),
220	19.0k	);
221	19.0k	}
222
223	9.54k	fn finalize(mut self) -> Func {
224	448k	for (blocknum, blockrange) in self.f.blocks.iter_mut().enumerate() {
225	448k	let begin_inst = self.f.insts.len();
226	3.48M	for inst in &self.insts_per_block[blocknum] {
227	3.48M	self.f.insts.push(inst.clone());
228	3.48M	}
229	448k	let end_inst = self.f.insts.len();
230	448k	*blockrange = InstRange::forward(Inst::new(begin_inst), Inst::new(end_inst));
231		}
232
233	9.54k	self.f
234	9.54k	}
235		}
236
237		impl Arbitrary<'_> for OperandConstraint {
238	5.04M	fn arbitrary(u: &mut Unstructured) -> ArbitraryResult<Self> {
239	5.04M	Ok(*u.choose(&[OperandConstraint::Any, OperandConstraint::Reg])?)
240	5.04M	}
241		}
242
243	805k	fn choose_dominating_block(
244	805k	idom: &[Block],
245	805k	mut block: Block,
246	805k	allow_self: bool,
247	805k	u: &mut Unstructured,
248	805k	) -> ArbitraryResult<Block> {
249	0	debug_assert!(block.is_valid());
250	805k	let orig_block = block;
251		loop {
252	7.93M	if (allow_self \|\| block != orig_block) && bool::arbitrary(u)? {
253	478k	break;
254	7.46M	}
255	7.46M	if idom[block.index()].is_invalid() {
256	327k	break;
257	7.13M	}
258	7.13M	block = idom[block.index()];
259		}
260	805k	let block = if block != orig_block \|\| allow_self {
261	769k	block
262		} else {
263	36.2k	Block::invalid()
264		};
265	805k	Ok(block)
266	805k	}
267
268	0	#[derive(Clone, Copy, Debug)]
269		pub struct Options {
270		pub reused_inputs: bool,
271		pub fixed_regs: bool,
272		pub fixed_nonallocatable: bool,
273		pub clobbers: bool,
274		pub control_flow: bool,
275		pub reducible: bool,
276		pub block_params: bool,
277		pub always_local_uses: bool,
278		pub reftypes: bool,
279		}
280
281		impl core::default::Default for Options {
282	0	fn default() -> Self {
283	0	Options {
284	0	reused_inputs: false,
285	0	fixed_regs: false,
286	0	fixed_nonallocatable: false,
287	0	clobbers: false,
288	0	control_flow: true,
289	0	reducible: false,
290	0	block_params: true,
291	0	always_local_uses: false,
292	0	reftypes: false,
293	0	}
294	0	}
295		}
296
297		impl Arbitrary<'_> for Func {
298	0	fn arbitrary(u: &mut Unstructured) -> ArbitraryResult<Func> {
299	0	Func::arbitrary_with_options(u, &Options::default())
300	0	}
301		}
302
303		impl Func {
304	9.54k	pub fn arbitrary_with_options(u: &mut Unstructured, opts: &Options) -> ArbitraryResult<Func> {
305	9.54k	// General strategy:
306	9.54k	// 1. Create an arbitrary CFG.
307	9.54k	// 2. Create a list of vregs to define in each block.
308	9.54k	// 3. Define some of those vregs in each block as blockparams.f.
309	9.54k	// 4. Populate blocks with ops that define the rest of the vregs.
310	9.54k	// - For each use, choose an available vreg: either one
311	9.54k	// already defined (via blockparam or inst) in this block,
312	9.54k	// or one defined in a dominating block.
313	9.54k
314	9.54k	let mut builder = FuncBuilder::new();
315	448k	for _ in 0..u.int_in_range(1..=100)? {
316	448k	builder.add_block();
317	448k	}
318	9.54k	let num_blocks = builder.f.blocks.len();
319	9.54k
320	9.54k	// Generate a CFG. Create a "spine" of either single blocks,
321	9.54k	// with links to the next; or fork patterns, with the left
322	9.54k	// fork linking to the next and the right fork in `out_blocks`
323	9.54k	// to be connected below. This creates an arbitrary CFG with
324	9.54k	// split critical edges, which is a property that we require
325	9.54k	// for the regalloc.
326	9.54k	let mut from = 0;
327	9.54k	let mut out_blocks = vec![];
328	9.54k	let mut in_blocks = vec![];
329	9.54k	// For reducibility, if selected: enforce strict nesting of backedges
330	9.54k	let mut max_backedge_src = 0;
331	9.54k	let mut min_backedge_dest = num_blocks;
332	229k	while from < num_blocks {
333	219k	in_blocks.push(from);
334	219k	if num_blocks > 3 && from < num_blocks - 3 && bool::arbitrary(u)? && opts.control_flow {
335	114k	// To avoid critical edges, we use from+1 as an edge
336	114k	// block, and advance `from` an extra block; `from+2`
337	114k	// will be the next normal iteration.
338	114k	builder.add_edge(Block::new(from), Block::new(from + 1));
339	114k	builder.add_edge(Block::new(from), Block::new(from + 2));
340	114k	builder.add_edge(Block::new(from + 2), Block::new(from + 3));
341	114k	out_blocks.push(from + 1);
342	114k	from += 2;
343	114k	} else if from < num_blocks - 1 {
344	95.7k	builder.add_edge(Block::new(from), Block::new(from + 1));
345	95.7k	}
346	219k	from += 1;
347		}
348	124k	for pred in out_blocks {
349	114k	let mut succ = *u.choose(&in_blocks[..])?;
350	114k	if opts.reducible && (pred >= succ) {
351	0	if pred < max_backedge_src \|\| succ > min_backedge_dest {
352	0	// If the chosen edge would result in an
353	0	// irreducible CFG, just make this a diamond
354	0	// instead.
355	0	succ = pred + 2;
356	0	} else {
357	0	max_backedge_src = pred;
358	0	min_backedge_dest = succ;
359	0	}
360	114k	}
361	114k	builder.add_edge(Block::new(pred), Block::new(succ));
362		}
363
364	9.54k	builder.compute_doms();
365
366	448k	for block in 0..num_blocks {
367	448k	builder.f.block_preds[block].clear();
368	448k	}
369	448k	for block in 0..num_blocks {
370	553k	for &succ in &builder.f.block_succs[block] {
371	553k	builder.f.block_preds[succ.index()].push(Block::new(block));
372	553k	}
373		}
374
375	9.54k	builder.compute_doms();
376	9.54k
377	9.54k	let mut vregs_by_block = vec![];
378	9.54k	let mut vregs_by_block_to_be_defined = vec![];
379	9.54k	let mut block_params = vec![vec![]; num_blocks];
380	448k	for block in 0..num_blocks {
381	448k	let mut vregs = vec![];
382	448k	for _ in 0..u.int_in_range(5..=15)? {
383	3.30M	let vreg = VReg::new(builder.f.num_vregs, RegClass::Int);
384	3.30M	builder.f.num_vregs += 1;
385	3.30M	vregs.push(vreg);
386	3.30M	if opts.reftypes && bool::arbitrary(u)? {
387	930k	builder.f.reftype_vregs.push(vreg);
388	2.37M	}
389	3.30M	if bool::arbitrary(u)? {
390	294k	let assumed_end_inst = 10 * num_blocks;
391	294k	let mut start = u.int_in_range::<usize>(0..=assumed_end_inst)?;
392	2.23M	for _ in 0..10 {
393	2.12M	if start >= assumed_end_inst {
394	180k	break;
395	1.94M	}
396	1.94M	let end = u.int_in_range::<usize>(start..=assumed_end_inst)?;
397	1.94M	let label = u.int_in_range::<u32>(0..=100)?;
398	1.94M	builder.f.debug_value_labels.push((
399	1.94M	vreg,
400	1.94M	Inst::new(start),
401	1.94M	Inst::new(end),
402	1.94M	label,
403	1.94M	));
404	1.94M	start = end;
405		}
406	3.00M	}
407		}
408	448k	vregs_by_block.push(vregs.clone());
409	448k	vregs_by_block_to_be_defined.push(vec![]);
410	448k	let mut max_block_params = u.int_in_range(0..=core::cmp::min(3, vregs.len() / 3))?;
411	3.74M	for &vreg in &vregs {
412	3.30M	if block > 0 && opts.block_params && bool::arbitrary(u)? && max_block_params > 0 {
413	260k	block_params[block].push(vreg);
414	260k	max_block_params -= 1;
415	3.04M	} else {
416	3.04M	vregs_by_block_to_be_defined.last_mut().unwrap().push(vreg);
417	3.04M	}
418		}
419	448k	vregs_by_block_to_be_defined.last_mut().unwrap().reverse();
420	448k	builder.set_block_params_in(Block::new(block), &block_params[block][..]);
421		}
422
423	448k	for block in 0..num_blocks {
424	448k	let mut avail = block_params[block].clone();
425	448k	let mut remaining_nonlocal_uses = u.int_in_range(0..=3)?;
426	3.48M	while let Some(vreg) = vregs_by_block_to_be_defined[block].pop() {
427	3.04M	let def_constraint = OperandConstraint::arbitrary(u)?;
428	3.04M	let def_pos = if bool::arbitrary(u)? {
429	765k	OperandPos::Early
430		} else {
431	2.27M	OperandPos::Late
432		};
433	3.04M	let mut operands = vec![Operand::new(
434	3.04M	vreg,
435	3.04M	def_constraint,
436	3.04M	OperandKind::Def,
437	3.04M	def_pos,
438	3.04M	)];
439	3.04M	let mut allocations = vec![Allocation::none()];
440	3.04M	for _ in 0..u.int_in_range(0..=3)? {
441	2.02M	let vreg = if avail.len() > 0
442	1.83M	&& (opts.always_local_uses
443	1.83M	\|\| remaining_nonlocal_uses == 0
444	586k	\|\| bool::arbitrary(u)?)
445		{
446	1.58M	*u.choose(&avail[..])?
447	442k	} else if !opts.always_local_uses {
448	442k	let def_block = choose_dominating_block(
449	442k	&builder.idom[..],
450	442k	Block::new(block),
451	442k	/* allow_self = */ false,
452	442k	u,
453	442k	)?;
454	442k	if !def_block.is_valid() {
455		// No vregs already defined, and no pred blocks that dominate us
456		// (perhaps we are the entry block): just stop generating inputs.
457	24.3k	break;
458	418k	}
459	418k	remaining_nonlocal_uses -= 1;
460	418k	*u.choose(&vregs_by_block[def_block.index()])?
461		} else {
462	0	break;
463		};
464	2.00M	let use_constraint = OperandConstraint::arbitrary(u)?;
465	2.00M	operands.push(Operand::new(
466	2.00M	vreg,
467	2.00M	use_constraint,
468	2.00M	OperandKind::Use,
469	2.00M	OperandPos::Early,
470	2.00M	));
471	2.00M	allocations.push(Allocation::none());
472		}
473	3.04M	let mut clobbers: Vec<PReg> = vec![];
474	3.04M	if operands.len() > 1 && opts.reused_inputs && bool::arbitrary(u)? {
475		// Make the def a reused input.
476	627k	let op = operands[0];
477	0	debug_assert_eq!(op.kind(), OperandKind::Def);
478	627k	let reused = u.int_in_range(1..=(operands.len() - 1))?;
479	627k	operands[0] = Operand::new(
480	627k	op.vreg(),
481	627k	OperandConstraint::Reuse(reused),
482	627k	op.kind(),
483	627k	OperandPos::Late,
484	627k	);
485	627k	// Make sure reused input is a Reg.
486	627k	let op = operands[reused];
487	627k	operands[reused] = Operand::new(
488	627k	op.vreg(),
489	627k	OperandConstraint::Reg,
490	627k	op.kind(),
491	627k	OperandPos::Early,
492	627k	);
493	2.41M	} else if opts.fixed_regs && bool::arbitrary(u)? {
494	296k	let mut fixed_early = vec![];
495	296k	let mut fixed_late = vec![];
496	296k	for _ in 0..u.int_in_range(0..=operands.len() - 1)? {
497		// Pick an operand and make it a fixed reg.
498	254k	let i = u.int_in_range(0..=(operands.len() - 1))?;
499	254k	let op = operands[i];
500	254k	let fixed_reg = PReg::new(u.int_in_range(0..=62)?, RegClass::Int);
501	254k	let fixed_list = match op.pos() {
502	236k	OperandPos::Early => &mut fixed_early,
503	17.8k	OperandPos::Late => &mut fixed_late,
504		};
505	254k	if fixed_list.contains(&fixed_reg) {
506	54.6k	break;
507	199k	}
508	199k	if op.kind() != OperandKind::Def && op.pos() == OperandPos::Late {
509		// Late-uses/mods with fixed constraints
510		// can't be allowed if we're allowing
511		// different constraints at Early and
512		// Late, because we can't move something
513		// into a location between Early and
514		// Late. Differing constraints only make
515		// sense if the instruction itself
516		// produces the newly-constrained values.
517	0	break;
518	199k	}
519	199k	if op.kind() != OperandKind::Use && op.pos() == OperandPos::Early {
520		// Likewise, we can only allow uses for
521		// fixed constraints at Early.
522	10.1k	break;
523	189k	}
524	189k	fixed_list.push(fixed_reg);
525	189k	operands[i] = Operand::new(
526	189k	op.vreg(),
527	189k	OperandConstraint::FixedReg(fixed_reg),
528	189k	op.kind(),
529	189k	op.pos(),
530	189k	);
531		}
532	2.11M	} else if opts.clobbers && bool::arbitrary(u)? {
533	118k	for _ in 0..u.int_in_range(0..=5)? {
534	192k	let reg = u.int_in_range(0..=30)?;
535	196k	if clobbers.iter().any(\|r\| r.hw_enc() == reg) {
536	29.0k	break;
537	163k	}
538	163k	clobbers.push(PReg::new(reg, RegClass::Int));
539		}
540	1.99M	} else if opts.fixed_nonallocatable && bool::arbitrary(u)? {
541	62.5k	operands.push(Operand::fixed_nonallocatable(PReg::new(63, RegClass::Int)));
542	1.93M	}
543
544	3.04M	let is_safepoint = opts.reftypes
545	3.04M	&& operands
546	3.04M	.iter()
547	4.52M	.all(\|op\| !builder.f.reftype_vregs.contains(&op.vreg()))
548	2.23M	&& bool::arbitrary(u)?;
549
550	3.04M	builder.add_inst(
551	3.04M	Block::new(block),
552	3.04M	InstData {
553	3.04M	op: InstOpcode::Op,
554	3.04M	operands,
555	3.04M	clobbers,
556	3.04M	is_safepoint,
557	3.04M	},
558	3.04M	);
559	3.04M	avail.push(vreg);
560		}
561
562		// Define the branch with blockparam args that must end
563		// the block.
564	448k	if builder.f.block_succs[block].len() > 0 {
565	439k	let mut params = vec![];
566	553k	for &succ in &builder.f.block_succs[block] {
567	553k	let mut args = vec![];
568	553k	for _ in 0..builder.f.block_params_in[succ.index()].len() {
569	362k	let dom_block = choose_dominating_block(
570	362k	&builder.idom[..],
571	362k	Block::new(block),
572	362k	false,
573	362k	u,
574	362k	)?;
575	362k	let vreg = if dom_block.is_valid() && bool::arbitrary(u)? {
576	51.2k	u.choose(&vregs_by_block[dom_block.index()][..])?
577		} else {
578	311k	u.choose(&avail[..])?
579		};
580	362k	args.push(*vreg);
581		}
582	553k	params.push(args);
583		}
584	439k	builder.set_block_params_out(Block::new(block), params);
585	439k	builder.add_inst(Block::new(block), InstData::branch());
586	9.54k	} else {
587	9.54k	builder.add_inst(Block::new(block), InstData::ret());
588	9.54k	}
589		}
590
591	9.54k	builder.f.debug_value_labels.sort_unstable();
592	9.54k
593	9.54k	Ok(builder.finalize())
594	9.54k	}
595		}
596
597		impl core::fmt::Debug for Func {
598		fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
599	0	write!(f, "{{\n")?;
600	0	for vreg in self.reftype_vregs() {
601	0	write!(f, " REF: {}\n", vreg)?;
602		}
603	0	for (i, blockrange) in self.blocks.iter().enumerate() {
604	0	let succs = self.block_succs[i]
605	0	.iter()
606	0	.map(\|b\| b.index())
607	0	.collect::<Vec<_>>();
608	0	let preds = self.block_preds[i]
609	0	.iter()
610	0	.map(\|b\| b.index())
611	0	.collect::<Vec<_>>();
612	0	let params_in = self.block_params_in[i]
613	0	.iter()
614	0	.map(\|v\| format!("v{}", v.vreg()))
615	0	.collect::<Vec<_>>()
616	0	.join(", ");
617	0	let params_out = self.block_params_out[i]
618	0	.iter()
619	0	.enumerate()
620	0	.map(\|(succ_idx, vec)\| {
621	0	let succ = self.block_succs[i][succ_idx];
622	0	let params = vec
623	0	.iter()
624	0	.map(\|v\| format!("v{}", v.vreg()))
625	0	.collect::<Vec<_>>()
626	0	.join(", ");
627	0	format!("block{}({})", succ.index(), params)
628	0	})
629	0	.collect::<Vec<_>>()
630	0	.join(", ");
631	0	write!(
632	0	f,
633	0	" block{}({}): # succs:{:?} preds:{:?}\n",
634	0	i, params_in, succs, preds
635	0	)?;
636	0	for inst in blockrange.iter() {
637	0	if self.requires_refs_on_stack(inst) {
638	0	write!(f, " -- SAFEPOINT --\n")?;
639	0	}
640	0	write!(
641	0	f,
642	0	" inst{}: {:?} ops:{:?} clobber:{:?}\n",
643	0	inst.index(),
644	0	self.insts[inst.index()].op,
645	0	self.insts[inst.index()].operands,
646	0	self.insts[inst.index()].clobbers
647	0	)?;
648	0	if let InstOpcode::Branch = self.insts[inst.index()].op {
649	0	write!(f, " params: {}\n", params_out)?;
650	0	}
651		}
652		}
653	0	write!(f, "}}\n")?;
654	0	Ok(())
655	0	}
656		}
657
658	9.54k	pub fn machine_env() -> MachineEnv {
659	28.6k	fn regs(r: core::ops::Range<usize>) -> Vec<PReg> {
660	601k	r.map(\|i\| PReg::new(i, RegClass::Int)).collect()
661	28.6k	}
662	9.54k	let preferred_regs_by_class: [Vec<PReg>; 2] = [regs(0..24), vec![]];
663	9.54k	let non_preferred_regs_by_class: [Vec<PReg>; 2] = [regs(24..32), vec![]];
664	9.54k	let scratch_by_class: [Option<PReg>; 2] = [None, None];
665	9.54k	let fixed_stack_slots = regs(32..63);
666	9.54k	// Register 63 is reserved for use as a fixed non-allocatable register.
667	9.54k	MachineEnv {
668	9.54k	preferred_regs_by_class,
669	9.54k	non_preferred_regs_by_class,
670	9.54k	scratch_by_class,
671	9.54k	fixed_stack_slots,
672	9.54k	}
673	9.54k	}