/src/regalloc.rs/bin/fuzzing.rs

Source (jump to first uncovered line)
//! Implements fuzzing primitives for everything.

use arbitrary::{Arbitrary, Result, Unstructured};
use std::collections::{HashMap, HashSet};
use std::iter::FromIterator;

use crate::test_framework::{self as ir, *};
use regalloc::*;

pub const NUM_REAL_REGS_PER_RC: u8 = 4;
const NUM_REG_CLASSES: u32 = 5;

/// Maximum number of vregs.
const NUM_VREGS: u16 = 16;
/// Maximum number of blocks.
const NUM_BLOCKS: u8 = 8;
/// Maximum number of instructions per block.
const NUM_BLOCK_INSTS: u8 = 8;

struct FuzzingEnv {
    num_blocks: u8,
    num_virtual_regs: u16,
    num_reftyped_regs: u16, // numbered in vreg space above ordinary vregs.
    /// Map of virtual register index to register class. None means the register hasn't been ever defined.
    vregs: HashMap<u16, RegClass>,
    /// Set of reftyped vregs that have been defined.
    reftyped_regs: HashSet<u16>,
    /// Really a hashmap from rc to HashSet<Reg>.
    regs_by_rc: Vec<HashSet<Reg>>,
    vregs_by_rc: Vec<HashSet<u16>>,
}

impl FuzzingEnv {
    fn block(&self, u: &mut Unstructured) -> Result<BlockIx> {
        Ok(BlockIx::new((u8::arbitrary(u)? % self.num_blocks) as u32))
    }

    fn label(&self, u: &mut Unstructured) -> Result<Label> {
        let bix = self.block(u)?;
        Ok(Label::Resolved {
            name: format!("{:?}", bix),
            bix,
        })
    }

    /// Returns true whenever a register of the given register class may be used.
    fn can_use_reg(&self, rc: RegClass) -> bool {
        !self.regs_by_rc[rc as usize].is_empty()
    }

    /// Returns true whenever a reftyped register may be used.
    fn can_use_reftyped_reg(&self) -> bool {
        !self.reftyped_regs.is_empty()
    }

    /// Returns true whenever a register of the given register class may be defined.
    fn can_def_reg(&self, rc: RegClass) -> bool {
        // If we can use one with the given reg class, then we can redefine it!
        self.can_use_reg(rc) || self.vregs.len() != (self.num_virtual_regs as usize)
    }

    /// Returns true whenever a virtual register of the given register class may be defined.
    fn can_def_vreg(&self, rc: RegClass) -> bool {
        !self.vregs_by_rc[rc as usize].is_empty()
            || self.vregs.len() != (self.num_virtual_regs as usize)
    }

    /// Returns true whenever a reftyped vreg may be defined.
    fn can_def_reftyped_reg(&self) -> bool {
        self.can_use_reftyped_reg() || self.reftyped_regs.len() != (self.num_reftyped_regs as usize)
    }

    fn def_reg(&mut self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
        debug_assert!(self.can_def_reg(rc));
        let reg = if self.can_def_vreg(rc) && bool::arbitrary(u)? {
            // virtual.
            let mut index = u16::arbitrary(u)? % self.num_virtual_regs;
            while self.vregs.contains_key(&index) && self.vregs[&index] != rc {
                // linear probing!
                index = (index + 1) % self.num_virtual_regs;
            }
            self.vregs.insert(index, rc);
            self.vregs_by_rc[rc as usize].insert(index);
            Reg::new_virtual(rc, index as u32)
        } else {
            // real.
            // TODO there's insider knowledge about the real reg universe stuck here.
            let index = match rc {
                RegClass::I32 => 0,
                RegClass::F32 => NUM_REAL_REGS_PER_RC,
                _ => panic!("unexpected rc"),
            } + u8::arbitrary(u)? % NUM_REAL_REGS_PER_RC;
            Reg::new_real(rc, 0x0, index)
        };
        self.regs_by_rc[rc as usize].insert(reg);
        Ok(reg)
    }

    fn def_reftyped_reg(&mut self, u: &mut Unstructured) -> Result<Reg> {
        debug_assert!(self.can_def_reftyped_reg());
        if self.reftyped_regs.len() == 0
            || (self.reftyped_regs.len() < (self.num_reftyped_regs as usize) && bool::arbitrary(u)?)
        {
            let mut index = u16::arbitrary(u)? % self.num_reftyped_regs;
            while self.reftyped_regs.contains(&index) {
                index = (index + 1) % self.num_reftyped_regs;
            }
            self.reftyped_regs.insert(index);
            let index = index + self.num_virtual_regs;
            Ok(Reg::new_virtual(RegClass::I32, index as u32))
        } else {
            assert!(self.reftyped_regs.len() > 0);
            let list_index = usize::arbitrary(u)? % self.reftyped_regs.len();
            let reg_index = self
                .reftyped_regs
                .iter()
                .skip(list_index)
                .cloned()
                .next()
                .unwrap();
            let reg_index = reg_index + self.num_virtual_regs;
            Ok(Reg::new_virtual(RegClass::I32, reg_index as u32))
        }
    }

    fn mod_reg(&mut self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
        // No need to handle the def part! If there was such a register, it was inserted in the first
        // place with the same register class.
        self.get_reg(rc, u)
    }

    fn get_reg(&self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
        debug_assert!(self.can_use_reg(rc));
        let regs = Vec::from_iter(self.regs_by_rc[rc as usize].iter());
        let reg = *regs[usize::arbitrary(u)? % regs.len()];
        Ok(reg)
    }

    fn get_reftyped_reg(&self, u: &mut Unstructured) -> Result<Reg> {
        debug_assert!(self.can_use_reftyped_reg());
        let regs = Vec::from_iter(self.reftyped_regs.iter());
        let reg_index = *regs[usize::arbitrary(u)? % regs.len()];
        let reg_index = reg_index + self.num_virtual_regs;
        Ok(Reg::new_virtual(RegClass::I32, reg_index as u32))
    }

    fn get_ri(&self, u: &mut Unstructured) -> Result<RI> {
        Ok(if self.can_use_reg(RegClass::I32) && bool::arbitrary(u)? {
            RI::Reg {
                reg: self.get_reg(RegClass::I32, u)?,
            }
        } else {
            RI::Imm {
                imm: u32::arbitrary(u)?,
            }
        })
    }

    fn get_am(&self, u: &mut Unstructured) -> Result<AM> {
        debug_assert!(self.can_use_reg(RegClass::I32));
        let base = self.get_reg(RegClass::I32, u)?;
        Ok(if bool::arbitrary(u)? {
            // RI
            AM::RI {
                base,
                offset: u32::arbitrary(u)?,
            }
        } else {
            // RR
            let offset = self.get_reg(RegClass::I32, u)?;
            AM::RR { base, offset }
        })
    }

    fn inst(&mut self, u: &mut Unstructured) -> Result<Inst> {
        use Inst::*;
        use RegClass::*;

        enum AllowedInst {
            Imm,
            ImmF,
            Copy,
            CopyF,
            CopyRef,
            BinOp,
            BinOpM,
            BinOpF,
            Load,
            LoadF,
            Store,
            StoreF,
            MakeRef,
            UseRef,
        }

        let mut allowed_insts = Vec::new();
        if self.can_def_reg(I32) {
            allowed_insts.push(AllowedInst::Imm);
        }
        if self.can_def_reg(F32) {
            allowed_insts.push(AllowedInst::ImmF);
        }
        if self.can_use_reg(I32) {
            allowed_insts.push(AllowedInst::Copy);
            allowed_insts.push(AllowedInst::BinOp);
            allowed_insts.push(AllowedInst::BinOpM);
            allowed_insts.push(AllowedInst::Load);
            allowed_insts.push(AllowedInst::Store);
            if self.can_def_reg(F32) {
                allowed_insts.push(AllowedInst::LoadF);
            }
            if self.can_use_reg(F32) {
                allowed_insts.push(AllowedInst::StoreF);
            }
        }
        if self.can_use_reg(F32) {
            allowed_insts.push(AllowedInst::CopyF);
            allowed_insts.push(AllowedInst::BinOpF);
        }
        if self.can_def_reftyped_reg() && self.can_use_reg(I32) {
            allowed_insts.push(AllowedInst::MakeRef);
        }
        if self.can_use_reftyped_reg() && self.can_def_reg(I32) {
            allowed_insts.push(AllowedInst::UseRef);
        }
        if self.can_def_reftyped_reg() && self.can_use_reftyped_reg() {
            allowed_insts.push(AllowedInst::CopyRef);
        }

        debug_assert!(!allowed_insts.is_empty());

        let index = u8::arbitrary(u)? as usize % (allowed_insts.len() + 1);
        if index == allowed_insts.len() {
            return self.inst_control_flow(u);
        }

        // Get uses before defs!
        Ok(match allowed_insts[index] {
            AllowedInst::Imm => Imm {
                dst: self.def_reg(I32, u)?,
                imm: u32::arbitrary(u)?,
            },
            AllowedInst::ImmF => ImmF {
                dst: self.def_reg(F32, u)?,
                imm: f32::arbitrary(u)?,
            },
            AllowedInst::Copy => {
                let src = self.get_reg(I32, u)?;
                Copy {
                    dst: self.def_reg(I32, u)?,
                    src,
                }
            }
            AllowedInst::CopyF => {
                let src = self.get_reg(F32, u)?;
                CopyF {
                    dst: self.def_reg(F32, u)?,
                    src,
                }
            }
            AllowedInst::CopyRef => {
                let dst = self.def_reftyped_reg(u)?;
                let src = self.get_reftyped_reg(u)?;
                Copy { dst, src }
            }
            AllowedInst::BinOp => {
                let src_left = self.get_reg(I32, u)?;
                let src_right = self.get_ri(u)?;
                BinOp {
                    op: ir::BinOp::arbitrary(u)?,
                    dst: self.def_reg(I32, u)?,
                    src_left,
                    src_right,
                }
            }
            AllowedInst::BinOpM => BinOpM {
                op: ir::BinOp::arbitrary(u)?,
                dst: self.mod_reg(I32, u)?,
                src_right: self.get_ri(u)?,
            },
            AllowedInst::BinOpF => {
                let src_left = self.get_reg(F32, u)?;
                let src_right = self.get_reg(F32, u)?;
                BinOpF {
                    op: ir::BinOpF::arbitrary(u)?,
                    dst: self.def_reg(F32, u)?,
                    src_left,
                    src_right,
                }
            }
            AllowedInst::Load => {
                let addr = self.get_am(u)?;
                Load {
                    dst: self.def_reg(I32, u)?,
                    addr,
                }
            }
            AllowedInst::LoadF => {
                let addr = self.get_am(u)?;
                LoadF {
                    dst: self.def_reg(F32, u)?,
                    addr,
                }
            }
            AllowedInst::Store => Store {
                addr: self.get_am(u)?,
                src: self.get_reg(I32, u)?,
            },
            AllowedInst::StoreF => StoreF {
                addr: self.get_am(u)?,
                src: self.get_reg(F32, u)?,
            },
            AllowedInst::MakeRef => MakeRef {
                dst: self.def_reftyped_reg(u)?,
                src: self.get_reg(I32, u)?,
            },
            AllowedInst::UseRef => UseRef {
                dst: self.def_reg(I32, u)?,
                src: self.get_reftyped_reg(u)?,
            },
        })
    }

    fn inst_control_flow(&self, u: &mut Unstructured) -> Result<Inst> {
        use Inst::*;
        use RegClass::*;

        enum AllowedInst {
            Goto,
            GotoCtf,
            Finish,
        }

        let mut allowed_insts = vec![AllowedInst::Goto, AllowedInst::Finish];
        if self.can_use_reg(I32) {
            allowed_insts.push(AllowedInst::GotoCtf);
        }

        Ok(
            match allowed_insts[u8::arbitrary(u)? as usize % allowed_insts.len()] {
                AllowedInst::GotoCtf => GotoCTF {
                    cond: self.get_reg(I32, u)?,
                    target_true: self.label(u)?,
                    target_false: self.label(u)?,
                },
                AllowedInst::Goto => Goto {
                    target: self.label(u)?,
                },
                AllowedInst::Finish => {
                    let ret_value = if bool::arbitrary(u)? {
                        if self.can_use_reg(I32) {
                            Some(self.get_reg(I32, u)?)
                        } else if self.can_use_reg(F32) {
                            Some(self.get_reg(F32, u)?)
                        } else {
                            None
                        }
                    } else {
                        None
                    };
                    Finish { reg: ret_value }
                }
            },
        )
    }
}

impl Arbitrary for Func {
    fn arbitrary(u: &mut Unstructured) -> arbitrary::Result<Func> {
        let num_virtual_regs = 1 + (u16::arbitrary(u)? % NUM_VREGS);
        let num_reftyped_regs = 1 + (u16::arbitrary(u)? % NUM_VREGS);
        let mut num_blocks = 1 + (u8::arbitrary(u)? % NUM_BLOCKS);

        let mut env = FuzzingEnv {
            num_blocks,
            num_virtual_regs,
            num_reftyped_regs,
            vregs: HashMap::new(),
            reftyped_regs: HashSet::new(),
            regs_by_rc: vec![HashSet::new(); NUM_REG_CLASSES as usize],
            vregs_by_rc: vec![HashSet::new(); NUM_REG_CLASSES as usize],
        };

        let entry = Some(Label::Resolved {
            name: "entry".to_string(),
            bix: BlockIx::new(0),
        });

        let mut insts = TypedIxVec::new();
        let mut blocks = TypedIxVec::new();

        let mut cur_block = 0;

        while num_blocks > 0 {
            let start = insts.len();

            let mut num_block_insts = 1 + (u8::arbitrary(u)? % NUM_BLOCK_INSTS);

            if bool::arbitrary(u)? {
                insts.push(Inst::Safepoint);
            }
            while num_block_insts > 0 {
                let inst = if num_block_insts == 1 {
                    env.inst_control_flow(u)?
                } else {
                    env.inst(u)?
                };
                let is_control_flow = inst.is_control_flow();
                insts.push(inst);
                num_block_insts -= 1;
                if is_control_flow {
                    break;
                }
            }

            debug_assert!(insts.len() > start);
            let len = insts.len() - start;
            let block = Block {
                name: format!("b{}", cur_block),
                start: InstIx::new(start),
                len,
                estimated_execution_frequency: 0,
            };
            blocks.push(block);

            cur_block += 1;
            num_blocks -= 1;
        }

        Ok(Func {
            name: "funk".to_string(),
            entry,
            num_virtual_regs: (num_virtual_regs + num_reftyped_regs) as u32,
            reftype_reg_start: Some(num_virtual_regs as u32),
            insns: insts,
            blocks,
        })
    }
}

Coverage Report

Created: 2021-03-22 08:29

Line	Count	Source (jump to first uncovered line)
1		//! Implements fuzzing primitives for everything.
2
3		use arbitrary::{Arbitrary, Result, Unstructured};
4		use std::collections::{HashMap, HashSet};
5		use std::iter::FromIterator;
6
7		use crate::test_framework::{self as ir, *};
8		use regalloc::*;
9
10		pub const NUM_REAL_REGS_PER_RC: u8 = 4;
11		const NUM_REG_CLASSES: u32 = 5;
12
13		/// Maximum number of vregs.
14		const NUM_VREGS: u16 = 16;
15		/// Maximum number of blocks.
16		const NUM_BLOCKS: u8 = 8;
17		/// Maximum number of instructions per block.
18		const NUM_BLOCK_INSTS: u8 = 8;
19
20		struct FuzzingEnv {
21		num_blocks: u8,
22		num_virtual_regs: u16,
23		num_reftyped_regs: u16, // numbered in vreg space above ordinary vregs.
24		/// Map of virtual register index to register class. None means the register hasn't been ever defined.
25		vregs: HashMap<u16, RegClass>,
26		/// Set of reftyped vregs that have been defined.
27		reftyped_regs: HashSet<u16>,
28		/// Really a hashmap from rc to HashSet<Reg>.
29		regs_by_rc: Vec<HashSet<Reg>>,
30		vregs_by_rc: Vec<HashSet<u16>>,
31		}
32
33		impl FuzzingEnv {
34	26.5k	fn block(&self, u: &mut Unstructured) -> Result<BlockIx> {
35	26.5k	Ok(BlockIx::new((u8::arbitrary(u)? % self.num_blocks) as u32))
36	26.5k	}
37
38	26.5k	fn label(&self, u: &mut Unstructured) -> Result<Label> {
39	26.5k	let bix = self.block(u)?;
40	26.5k	Ok(Label::Resolved {
41	26.5k	name: format!("{:?}", bix),
42	26.5k	bix,
43	26.5k	})
44	26.5k	}
45
46		/// Returns true whenever a register of the given register class may be used.
47	697k	fn can_use_reg(&self, rc: RegClass) -> bool {
48	697k	!self.regs_by_rc[rc as usize].is_empty()
49	697k	}
50
51		/// Returns true whenever a reftyped register may be used.
52	357k	fn can_use_reftyped_reg(&self) -> bool {
53	357k	!self.reftyped_regs.is_empty()
54	357k	}
55
56		/// Returns true whenever a register of the given register class may be defined.
57	320k	fn can_def_reg(&self, rc: RegClass) -> bool {
58		// If we can use one with the given reg class, then we can redefine it!
59	320k	self.can_use_reg(rc) \|\| self.vregs.len() != (self.num_virtual_regs as usize)
60	320k	}
61
62		/// Returns true whenever a virtual register of the given register class may be defined.
63	58.0k	fn can_def_vreg(&self, rc: RegClass) -> bool {
64	58.0k	!self.vregs_by_rc[rc as usize].is_empty()
65	15.5k	\|\| self.vregs.len() != (self.num_virtual_regs as usize)
66	58.0k	}
67
68		/// Returns true whenever a reftyped vreg may be defined.
69	178k	fn can_def_reftyped_reg(&self) -> bool {
70	178k	self.can_use_reftyped_reg() \|\| self.reftyped_regs.len() != (self.num_reftyped_regs as usize)
71	178k	}
72
73	58.0k	fn def_reg(&mut self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
74		debug_assert!(self.can_def_reg(rc));
75	58.0k	let reg = if self.can_def_vreg(rc) && bool::arbitrary(u)? {
76		// virtual.
77	32.2k	let mut index = u16::arbitrary(u)? % self.num_virtual_regs;
78	41.0k	while self.vregs.contains_key(&index) && self.vregs[&index] != rc {
79	8.79k	// linear probing!
80	8.79k	index = (index + 1) % self.num_virtual_regs;
81	8.79k	}
82	32.2k	self.vregs.insert(index, rc);
83	32.2k	self.vregs_by_rc[rc as usize].insert(index);
84	32.2k	Reg::new_virtual(rc, index as u32)
85		} else {
86		// real.
87		// TODO there's insider knowledge about the real reg universe stuck here.
88	25.8k	let index = match rc {
89	21.9k	RegClass::I32 => 0,
90	3.85k	RegClass::F32 => NUM_REAL_REGS_PER_RC,
91	0	_ => panic!("unexpected rc"),
92	25.8k	} + u8::arbitrary(u)? % NUM_REAL_REGS_PER_RC;
93	25.8k	Reg::new_real(rc, 0x0, index)
94		};
95	58.0k	self.regs_by_rc[rc as usize].insert(reg);
96	58.0k	Ok(reg)
97	58.0k	}
98
99	21.0k	fn def_reftyped_reg(&mut self, u: &mut Unstructured) -> Result<Reg> {
100		debug_assert!(self.can_def_reftyped_reg());
101	21.0k	if self.reftyped_regs.len() == 0
102	18.4k	\|\| (self.reftyped_regs.len() < (self.num_reftyped_regs as usize) && bool::arbitrary(u)?)
103		{
104	6.16k	let mut index = u16::arbitrary(u)? % self.num_reftyped_regs;
105	15.6k	while self.reftyped_regs.contains(&index) {
106	9.50k	index = (index + 1) % self.num_reftyped_regs;
107	9.50k	}
108	6.16k	self.reftyped_regs.insert(index);
109	6.16k	let index = index + self.num_virtual_regs;
110	6.16k	Ok(Reg::new_virtual(RegClass::I32, index as u32))
111		} else {
112	14.8k	assert!(self.reftyped_regs.len() > 0);
113	14.8k	let list_index = usize::arbitrary(u)? % self.reftyped_regs.len();
114	14.8k	let reg_index = self
115	14.8k	.reftyped_regs
116	14.8k	.iter()
117	14.8k	.skip(list_index)
118	14.8k	.cloned()
119	14.8k	.next()
120	14.8k	.unwrap();
121	14.8k	let reg_index = reg_index + self.num_virtual_regs;
122	14.8k	Ok(Reg::new_virtual(RegClass::I32, reg_index as u32))
123		}
124	21.0k	}
125
126	2.72k	fn mod_reg(&mut self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
127	2.72k	// No need to handle the def part! If there was such a register, it was inserted in the first
128	2.72k	// place with the same register class.
129	2.72k	self.get_reg(rc, u)
130	2.72k	}
131
132	48.2k	fn get_reg(&self, rc: RegClass, u: &mut Unstructured) -> Result<Reg> {
133		debug_assert!(self.can_use_reg(rc));
134	48.2k	let regs = Vec::from_iter(self.regs_by_rc[rc as usize].iter());
135	48.2k	let reg = *regs[usize::arbitrary(u)? % regs.len()];
136	48.2k	Ok(reg)
137	48.2k	}
138
139	17.7k	fn get_reftyped_reg(&self, u: &mut Unstructured) -> Result<Reg> {
140		debug_assert!(self.can_use_reftyped_reg());
141	17.7k	let regs = Vec::from_iter(self.reftyped_regs.iter());
142	17.7k	let reg_index = *regs[usize::arbitrary(u)? % regs.len()];
143	17.7k	let reg_index = reg_index + self.num_virtual_regs;
144	17.7k	Ok(Reg::new_virtual(RegClass::I32, reg_index as u32))
145	17.7k	}
146
147	3.65k	fn get_ri(&self, u: &mut Unstructured) -> Result<RI> {
148	3.65k	Ok(if self.can_use_reg(RegClass::I32) && bool::arbitrary(u)? {
149		RI::Reg {
150	2.31k	reg: self.get_reg(RegClass::I32, u)?,
151		}
152		} else {
153		RI::Imm {
154	1.34k	imm: u32::arbitrary(u)?,
155		}
156		})
157	3.65k	}
158
159	7.53k	fn get_am(&self, u: &mut Unstructured) -> Result<AM> {
160		debug_assert!(self.can_use_reg(RegClass::I32));
161	7.53k	let base = self.get_reg(RegClass::I32, u)?;
162	7.53k	Ok(if bool::arbitrary(u)? {
163		// RI
164		AM::RI {
165	3.92k	base,
166	3.92k	offset: u32::arbitrary(u)?,
167		}
168		} else {
169		// RR
170	3.60k	let offset = self.get_reg(RegClass::I32, u)?;
171	3.60k	AM::RR { base, offset }
172		})
173	7.53k	}
174
175	89.3k	fn inst(&mut self, u: &mut Unstructured) -> Result<Inst> {
176		use Inst::*;
177		use RegClass::*;
178
179		enum AllowedInst {
180		Imm,
181		ImmF,
182		Copy,
183		CopyF,
184		CopyRef,
185		BinOp,
186		BinOpM,
187		BinOpF,
188		Load,
189		LoadF,
190		Store,
191		StoreF,
192		MakeRef,
193		UseRef,
194		}
195
196	89.3k	let mut allowed_insts = Vec::new();
197	88.7k	if self.can_def_reg(I32) {
198	88.7k	allowed_insts.push(AllowedInst::Imm);
199	628	}
200	89.3k	if self.can_def_reg(F32) {
201	84.1k	allowed_insts.push(AllowedInst::ImmF);
202	5.22k	}
203	89.3k	if self.can_use_reg(I32) {
204	83.4k	allowed_insts.push(AllowedInst::Copy);
205	83.4k	allowed_insts.push(AllowedInst::BinOp);
206	83.4k	allowed_insts.push(AllowedInst::BinOpM);
207	83.4k	allowed_insts.push(AllowedInst::Load);
208	83.4k	allowed_insts.push(AllowedInst::Store);
209	78.1k	if self.can_def_reg(F32) {
210	78.1k	allowed_insts.push(AllowedInst::LoadF);
211	5.22k	}
212	83.4k	if self.can_use_reg(F32) {
213	64.4k	allowed_insts.push(AllowedInst::StoreF);
214	18.9k	}
215	5.92k	}
216	89.3k	if self.can_use_reg(F32) {
217	66.1k	allowed_insts.push(AllowedInst::CopyF);
218	66.1k	allowed_insts.push(AllowedInst::BinOpF);
219	23.1k	}
220	89.3k	if self.can_def_reftyped_reg() && self.can_use_reg(I32) {
221	83.4k	allowed_insts.push(AllowedInst::MakeRef);
222	5.92k	}
223	89.3k	if self.can_use_reftyped_reg() && self.can_def_reg(I32) {
224	58.3k	allowed_insts.push(AllowedInst::UseRef);
225	31.0k	}
226	89.3k	if self.can_def_reftyped_reg() && self.can_use_reftyped_reg() {
227	58.3k	allowed_insts.push(AllowedInst::CopyRef);
228	31.0k	}
229
230		debug_assert!(!allowed_insts.is_empty());
231
232	89.3k	let index = u8::arbitrary(u)? as usize % (allowed_insts.len() + 1);
233	89.3k	if index == allowed_insts.len() {
234	2.89k	return self.inst_control_flow(u);
235	86.4k	}
236
237		// Get uses before defs!
238	86.4k	Ok(match allowed_insts[index] {
239	86.4k	AllowedInst::Imm => Imm {
240	32.9k	dst: self.def_reg(I32, u)?,
241	32.9k	imm: u32::arbitrary(u)?,
242		},
243		AllowedInst::ImmF => ImmF {
244	4.91k	dst: self.def_reg(F32, u)?,
245	4.91k	imm: f32::arbitrary(u)?,
246		},
247		AllowedInst::Copy => {
248	11.7k	let src = self.get_reg(I32, u)?;
249		Copy {
250	11.7k	dst: self.def_reg(I32, u)?,
251	11.7k	src,
252		}
253		}
254		AllowedInst::CopyF => {
255	2.05k	let src = self.get_reg(F32, u)?;
256		CopyF {
257	2.05k	dst: self.def_reg(F32, u)?,
258	2.05k	src,
259		}
260		}
261		AllowedInst::CopyRef => {
262	15.4k	let dst = self.def_reftyped_reg(u)?;
263	15.4k	let src = self.get_reftyped_reg(u)?;
264	15.4k	Copy { dst, src }
265		}
266		AllowedInst::BinOp => {
267	932	let src_left = self.get_reg(I32, u)?;
268	932	let src_right = self.get_ri(u)?;
269		BinOp {
270	932	op: ir::BinOp::arbitrary(u)?,
271	932	dst: self.def_reg(I32, u)?,
272	932	src_left,
273	932	src_right,
274		}
275		}
276		AllowedInst::BinOpM => BinOpM {
277	2.72k	op: ir::BinOp::arbitrary(u)?,
278	2.72k	dst: self.mod_reg(I32, u)?,
279	2.72k	src_right: self.get_ri(u)?,
280		},
281		AllowedInst::BinOpF => {
282	419	let src_left = self.get_reg(F32, u)?;
283	419	let src_right = self.get_reg(F32, u)?;
284		BinOpF {
285	419	op: ir::BinOpF::arbitrary(u)?,
286	419	dst: self.def_reg(F32, u)?,
287	419	src_left,
288	419	src_right,
289		}
290		}
291		AllowedInst::Load => {
292	1.25k	let addr = self.get_am(u)?;
293		Load {
294	1.25k	dst: self.def_reg(I32, u)?,
295	1.25k	addr,
296		}
297		}
298		AllowedInst::LoadF => {
299	1.62k	let addr = self.get_am(u)?;
300		LoadF {
301	1.62k	dst: self.def_reg(F32, u)?,
302	1.62k	addr,
303		}
304		}
305		AllowedInst::Store => Store {
306	1.97k	addr: self.get_am(u)?,
307	1.97k	src: self.get_reg(I32, u)?,
308		},
309		AllowedInst::StoreF => StoreF {
310	2.66k	addr: self.get_am(u)?,
311	2.66k	src: self.get_reg(F32, u)?,
312		},
313		AllowedInst::MakeRef => MakeRef {
314	5.51k	dst: self.def_reftyped_reg(u)?,
315	5.51k	src: self.get_reg(I32, u)?,
316		},
317		AllowedInst::UseRef => UseRef {
318	2.24k	dst: self.def_reg(I32, u)?,
319	2.24k	src: self.get_reftyped_reg(u)?,
320		},
321		})
322	89.3k	}
323
324	21.8k	fn inst_control_flow(&self, u: &mut Unstructured) -> Result<Inst> {
325	21.8k	use Inst::*;
326	21.8k	use RegClass::*;
327	21.8k
328	21.8k	enum AllowedInst {
329	21.8k	Goto,
330	21.8k	GotoCtf,
331	21.8k	Finish,
332	21.8k	}
333	21.8k
334	21.8k	let mut allowed_insts = vec![AllowedInst::Goto, AllowedInst::Finish];
335	20.9k	if self.can_use_reg(I32) {
336	20.9k	allowed_insts.push(AllowedInst::GotoCtf);
337	951	}
338
339		Ok(
340	21.8k	match allowed_insts[u8::arbitrary(u)? as usize % allowed_insts.len()] {
341	21.8k	AllowedInst::GotoCtf => GotoCTF {
342	5.87k	cond: self.get_reg(I32, u)?,
343	5.87k	target_true: self.label(u)?,
344	5.87k	target_false: self.label(u)?,
345		},
346		AllowedInst::Goto => Goto {
347	14.7k	target: self.label(u)?,
348		},
349		AllowedInst::Finish => {
350	1.21k	let ret_value = if bool::arbitrary(u)? {
351	542	if self.can_use_reg(I32) {
352	427	Some(self.get_reg(I32, u)?)
353	115	} else if self.can_use_reg(F32) {
354	53	Some(self.get_reg(F32, u)?)
355		} else {
356	62	None
357		}
358		} else {
359	675	None
360		};
361	1.21k	Finish { reg: ret_value }
362		}
363		},
364		)
365	21.8k	}
366		}
367
368		impl Arbitrary for Func {
369	4.26k	fn arbitrary(u: &mut Unstructured) -> arbitrary::Result<Func> {
370	4.26k	let num_virtual_regs = 1 + (u16::arbitrary(u)? % NUM_VREGS);
371	4.26k	let num_reftyped_regs = 1 + (u16::arbitrary(u)? % NUM_VREGS);
372	4.26k	let mut num_blocks = 1 + (u8::arbitrary(u)? % NUM_BLOCKS);
373
374	4.26k	let mut env = FuzzingEnv {
375	4.26k	num_blocks,
376	4.26k	num_virtual_regs,
377	4.26k	num_reftyped_regs,
378	4.26k	vregs: HashMap::new(),
379	4.26k	reftyped_regs: HashSet::new(),
380	4.26k	regs_by_rc: vec![HashSet::new(); NUM_REG_CLASSES as usize],
381	4.26k	vregs_by_rc: vec![HashSet::new(); NUM_REG_CLASSES as usize],
382	4.26k	};
383	4.26k
384	4.26k	let entry = Some(Label::Resolved {
385	4.26k	name: "entry".to_string(),
386	4.26k	bix: BlockIx::new(0),
387	4.26k	});
388	4.26k
389	4.26k	let mut insts = TypedIxVec::new();
390	4.26k	let mut blocks = TypedIxVec::new();
391	4.26k
392	4.26k	let mut cur_block = 0;
393
394	26.1k	while num_blocks > 0 {
395	21.8k	let start = insts.len();
396
397	21.8k	let mut num_block_insts = 1 + (u8::arbitrary(u)? % NUM_BLOCK_INSTS);
398
399	21.8k	if bool::arbitrary(u)? {
400	14.7k	insts.push(Inst::Safepoint);
401	7.10k	}
402	108k	while num_block_insts > 0 {
403	108k	let inst = if num_block_insts == 1 {
404	18.9k	env.inst_control_flow(u)?
405		} else {
406	89.3k	env.inst(u)?
407		};
408	108k	let is_control_flow = inst.is_control_flow();
409	108k	insts.push(inst);
410	108k	num_block_insts -= 1;
411	108k	if is_control_flow {
412	21.8k	break;
413	86.4k	}
414		}
415
416		debug_assert!(insts.len() > start);
417	21.8k	let len = insts.len() - start;
418	21.8k	let block = Block {
419	21.8k	name: format!("b{}", cur_block),
420	21.8k	start: InstIx::new(start),
421	21.8k	len,
422	21.8k	estimated_execution_frequency: 0,
423	21.8k	};
424	21.8k	blocks.push(block);
425	21.8k
426	21.8k	cur_block += 1;
427	21.8k	num_blocks -= 1;
428		}
429
430	4.26k	Ok(Func {
431	4.26k	name: "funk".to_string(),
432	4.26k	entry,
433	4.26k	num_virtual_regs: (num_virtual_regs + num_reftyped_regs) as u32,
434	4.26k	reftype_reg_start: Some(num_virtual_regs as u32),
435	4.26k	insns: insts,
436	4.26k	blocks,
437	4.26k	})
438	4.26k	}
439		}