From b86583d38aa312e22f1b1fe2461a1afb5e77c038 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Fri, 27 Jan 2023 17:19:31 -0800 Subject: [PATCH] nearly done writing code that generates fuzzing input for reg alloc --- register_allocator/src/error.rs | 12 + register_allocator/src/function.rs | 36 ++- register_allocator/src/fuzzing.rs | 410 +++++++++++++++++++++++++---- register_allocator/src/lib.rs | 1 - 4 files changed, 399 insertions(+), 60 deletions(-) diff --git a/register_allocator/src/error.rs b/register_allocator/src/error.rs index 13c0414..d504213 100644 --- a/register_allocator/src/error.rs +++ b/register_allocator/src/error.rs @@ -241,6 +241,18 @@ pub enum Error { branch_inst: InstIdx, tgt_block: BlockIdx, }, + #[error( + "operand can't reuse operand of differing type: in {inst}: reuse \ + source operand: index {src_operand_idx} type {src_ty:?}) reuse \ + target operand: index {tgt_operand_idx} type {tgt_ty:?})" + )] + ReuseOperandTyMismatch { + inst: InstIdx, + tgt_operand_idx: usize, + src_operand_idx: usize, + src_ty: Ty, + tgt_ty: Ty, + }, } pub type Result = std::result::Result; diff --git a/register_allocator/src/function.rs b/register_allocator/src/function.rs index 28ff917..4577581 100644 --- a/register_allocator/src/function.rs +++ b/register_allocator/src/function.rs @@ -5,6 +5,7 @@ use crate::{ loc::{BaseTy, Loc, Ty}, loc_set::LocSet, }; +use arbitrary::Arbitrary; use core::fmt; use hashbrown::HashSet; use petgraph::{ @@ -28,15 +29,15 @@ pub enum SSAValDef { #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] pub struct BranchSuccParamUse { - branch_inst: InstIdx, - succ: BlockIdx, - param_idx: usize, + pub branch_inst: InstIdx, + pub succ: BlockIdx, + pub param_idx: usize, } #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] pub struct OperandUse { - inst: InstIdx, - operand_idx: usize, + pub inst: InstIdx, + pub operand_idx: usize, } #[derive(Clone, PartialEq, Eq, Debug, Hash, Serialize, Deserialize)] @@ -106,7 +107,9 @@ impl SSAVal { } } -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] +#[derive( + Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary, +)] #[repr(u8)] pub enum InstStage { Early = 0, @@ -177,7 +180,9 @@ impl TryFrom for ProgPoint { } } -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] +#[derive( + Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary, +)] #[repr(u8)] pub enum OperandKind { Use = 0, @@ -353,6 +358,23 @@ impl Operand { } } } + if let KindAndConstraint::Reuse { + kind: _, + reuse_operand_idx, + } = self.kind_and_constraint + { + let reuse_src = func.try_get_operand(inst, reuse_operand_idx)?; + let reuse_src_ssa_val = func.try_get_ssa_val(reuse_src.ssa_val)?; + if ssa_val.ty != reuse_src_ssa_val.ty { + return Err(Error::ReuseOperandTyMismatch { + inst, + tgt_operand_idx: operand_idx, + src_operand_idx: reuse_operand_idx, + src_ty: reuse_src_ssa_val.ty, + tgt_ty: ssa_val.ty, + }); + } + } let constraint = self.try_constraint(inst, func)?; match constraint { Constraint::Any | Constraint::Stack => {} diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs index 8338fe4..165530b 100644 --- a/register_allocator/src/fuzzing.rs +++ b/register_allocator/src/fuzzing.rs @@ -1,24 +1,84 @@ +#![cfg(feature = "fuzzing")] use crate::{ - function::{Block, BlockTermInstKind, FnFields, Inst, InstKind, Operand, SSAVal, SSAValDef}, + function::{ + Block, BlockTermInstKind, BranchSuccParamUse, Constraint, CopyInstKind, FnFields, Inst, + InstKind, KindAndConstraint, Operand, OperandKind, OperandUse, SSAVal, SSAValDef, + }, index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, interned::{GlobalState, Intern}, loc::Ty, loc_set::LocSet, }; use arbitrary::{Arbitrary, Error, Unstructured}; +use hashbrown::HashMap; use petgraph::algo::dominators; -use std::collections::BTreeMap; +use std::{borrow::Borrow, collections::BTreeMap, ops::Deref}; + +#[derive(Clone, Debug, Default)] +struct SSAValIdxs { + per_ty: HashMap>, + all: Vec, +} + +impl SSAValIdxs { + fn per_ty(&self, ty: Ty) -> &[SSAValIdx] { + self.per_ty.get(&ty).map(Deref::deref).unwrap_or_default() + } + fn extend>( + &mut self, + ssa_vals: &Vec, + ssa_val_idxs: impl IntoIterator, + ) { + for ssa_val_idx in ssa_val_idxs { + let ssa_val_idx: SSAValIdx = *ssa_val_idx.borrow(); + self.per_ty + .entry(ssa_vals[ssa_val_idx].ty) + .or_default() + .push(ssa_val_idx); + self.all.push(ssa_val_idx); + } + } +} struct FnBuilder<'a, 'b, 'g> { global_state: &'g GlobalState, u: &'a mut Unstructured<'b>, func: FnFields, + available_ssa_vals_at_end: HashMap, } impl FnBuilder<'_, '_, '_> { - fn new_ssa_val(&mut self, ty: Ty, def: SSAValDef) -> SSAValIdx { - let retval = SSAValIdx::new(self.func.ssa_vals.len()); - self.func.ssa_vals.push(SSAVal { + fn available_ssa_vals_at_end(&mut self, block_idx: Option) -> SSAValIdxs { + let Some(block_idx) = block_idx else { + return Default::default(); + }; + if let Some(retval) = self.available_ssa_vals_at_end.get(&block_idx) { + return retval.clone(); + } + let mut available_ssa_vals = self.available_ssa_vals_before_start(block_idx); + let block = &self.func.blocks[block_idx]; + available_ssa_vals.extend(&self.func.ssa_vals, &block.params); + for inst_idx in block.insts { + let inst = &self.func.insts[inst_idx]; + available_ssa_vals.extend( + &self.func.ssa_vals, + inst.operands + .iter() + .filter(|o| o.kind_and_constraint.kind() == OperandKind::Def) + .map(|o| o.ssa_val), + ); + } + self.available_ssa_vals_at_end + .insert(block_idx, available_ssa_vals.clone()); + available_ssa_vals + } + fn available_ssa_vals_before_start(&mut self, block_idx: BlockIdx) -> SSAValIdxs { + let idom = self.func.blocks[block_idx].immediate_dominator; + self.available_ssa_vals_at_end(idom) + } + fn new_ssa_val(ssa_vals: &mut Vec, ty: Ty, def: SSAValDef) -> SSAValIdx { + let retval = SSAValIdx::new(ssa_vals.len()); + ssa_vals.push(SSAVal { ty, def, operand_uses: Default::default(), @@ -43,23 +103,100 @@ impl FnBuilder<'_, '_, '_> { }); inst_idx } - fn make_ssa_val_use(&mut self) -> Result { - todo!() + fn make_copy_inst_kind( + u: &mut Unstructured<'_>, + // takes ref to Vec since Index is only implemented for Vec + ssa_vals: &Vec, + operands: &[Operand], + ) -> Result, Error> { + if operands.is_empty() { + return Ok(None); + } + let mut possible_src_operand_idxs = vec![]; + let mut possible_dest_operand_idxs = vec![]; + for (operand_idx, operand) in operands.iter().enumerate() { + match operand.kind_and_constraint.kind() { + OperandKind::Use => possible_src_operand_idxs.push(operand_idx), + OperandKind::Def => possible_dest_operand_idxs.push(operand_idx), + } + } + if possible_src_operand_idxs.is_empty() || possible_dest_operand_idxs.is_empty() { + return Ok(None); + } + let mut src_operand_idxs = vec![]; + for _ in 0..u.int_in_range(1..=3)? { + // src can have duplicates, don't remove chosen items + src_operand_idxs.push(*u.choose(&possible_src_operand_idxs)?); + } + for src_operand_idxs_len in (1..=src_operand_idxs.len()).rev() { + let mut operand_types = src_operand_idxs[..src_operand_idxs_len] + .iter() + .map(|&idx| ssa_vals[operands[idx].ssa_val].ty); + let copy_ty = operand_types.next_back().unwrap(); + let copy_ty = operand_types + .filter(|v| v.base_ty == copy_ty.base_ty) + .try_fold(copy_ty, Ty::try_concat); + let Ok(copy_ty) = copy_ty else { + continue; + }; + let mut possible_dest_operand_idxs = possible_dest_operand_idxs.clone(); + let mut dest_operand_idxs = vec![]; + let mut dest_copy_ty: Option = None; + for _ in 0..u.int_in_range(1..=3)? { + if possible_dest_operand_idxs.is_empty() { + break; + } + // dest can't have duplicates, so remove items that were chosen + let chosen_index = u.choose_index(possible_src_operand_idxs.len())?; + let dest_operand_idx = possible_dest_operand_idxs.swap_remove(chosen_index); + let dest_operand_ty = ssa_vals[operands[dest_operand_idx].ssa_val].ty; + if dest_operand_ty.base_ty != copy_ty.base_ty + || dest_operand_ty.reg_len > copy_ty.reg_len + { + continue; + } + let next_dest_copy_ty = if let Some(dest_copy_ty) = dest_copy_ty { + let Ok(ty) = dest_copy_ty.try_concat(dest_operand_ty) else { + continue; + }; + ty + } else { + dest_operand_ty + }; + if next_dest_copy_ty.reg_len > copy_ty.reg_len { + continue; + } + dest_copy_ty = Some(next_dest_copy_ty); + dest_operand_idxs.push(dest_operand_idx); + } + if dest_copy_ty != Some(copy_ty) || dest_operand_idxs.is_empty() { + continue; + } + return Ok(Some(CopyInstKind { + src_operand_idxs, + dest_operand_idxs, + copy_ty, + })); + } + Ok(None) } fn run(&mut self) -> Result<(), Error> { let block_count = self.u.int_in_range(1..=10u16)?; for block_idx in 0..block_count as usize { let block_idx = BlockIdx::new(block_idx); let mut params = Vec::new(); - for param_idx in 0..self.u.int_in_range(0..=10)? { - let ty = self.u.arbitrary()?; - params.push(self.new_ssa_val( - ty, - SSAValDef::BlockParam { - block: block_idx, - param_idx, - }, - )); + if block_idx != BlockIdx::ENTRY_BLOCK { + for param_idx in 0..self.u.int_in_range(0..=10)? { + let ty = self.u.arbitrary()?; + params.push(Self::new_ssa_val( + &mut self.func.ssa_vals, + ty, + SSAValDef::BlockParam { + block: block_idx, + param_idx, + }, + )); + } } let end = InstIdx::new(self.func.insts.len()); self.func.blocks.push(Block { @@ -68,41 +205,55 @@ impl FnBuilder<'_, '_, '_> { preds: Default::default(), immediate_dominator: Default::default(), }); - for _ in 0..self.u.int_in_range(0..=10)? { - let clobbers = self.u.arbitrary()?; - self.new_inst_in_last_block(InstKind::Normal, vec![], clobbers); - } - let mut succs_and_params = BTreeMap::default(); - let succ_range = BlockIdx::ENTRY_BLOCK.get() as u16..=(block_count - 1); - if !succ_range.is_empty() { - for i in 0..self.u.int_in_range(0..=3usize)? { - if i > succ_range.len() { - break; - } - let succ = BlockIdx::new(self.u.int_in_range(succ_range.clone())?.into()); - succs_and_params.insert(succ, vec![]); + for is_term in (0..self.u.int_in_range(0..=10)?) + .map(|_| false) + .chain([true]) + { + let mut operands = vec![]; + for _ in 0..self.u.int_in_range(0..=5)? { + let kind = self.u.arbitrary()?; + let ssa_val = if let OperandKind::Def = kind { + let ty = self.u.arbitrary()?; + let def = SSAValDef::Operand { + inst: InstIdx::new(self.func.insts.len()), + operand_idx: operands.len(), + }; + Self::new_ssa_val(&mut self.func.ssa_vals, ty, def) + } else { + SSAValIdx::new(!0) + }; + operands.push(Operand { + ssa_val, + kind_and_constraint: KindAndConstraint::Constraint { + kind: self.u.arbitrary()?, + constraint: Constraint::Any, + }, + stage: self.u.arbitrary()?, + }); } + let inst_kind = if is_term { + let mut succs_and_params = BTreeMap::default(); + let succ_range = BlockIdx::ENTRY_BLOCK.get() as u16..=(block_count - 1); + if !succ_range.is_empty() { + for i in 0..self.u.int_in_range(0..=3usize)? { + if i > succ_range.len() { + break; + } + let succ = + BlockIdx::new(self.u.int_in_range(succ_range.clone())?.into()); + succs_and_params.insert(succ, vec![]); + } + } + InstKind::BlockTerm(BlockTermInstKind { succs_and_params }) + } else { + InstKind::Normal + }; + let clobbers = self.u.arbitrary()?; + self.new_inst_in_last_block(inst_kind, operands, clobbers); } - let mut operands = vec![]; - for _ in 0..self.u.int_in_range(0..=5)? { - operands.push(Operand { - ssa_val: todo!(), - kind_and_constraint: todo!(), - stage: todo!(), - }); - } - let clobbers = self.u.arbitrary()?; - self.new_inst_in_last_block( - InstKind::BlockTerm(BlockTermInstKind { succs_and_params }), - operands, - clobbers, - ); } - let dominators = dominators::simple_fast(&self.func, BlockIdx::ENTRY_BLOCK); for block_idx in 0..self.func.blocks.len() { let block_idx = BlockIdx::new(block_idx); - self.func.blocks[block_idx].immediate_dominator = - dominators.immediate_dominator(block_idx); let term_idx = self .func .try_get_block_term_inst_idx(block_idx) @@ -117,20 +268,174 @@ impl FnBuilder<'_, '_, '_> { for succ in successors { self.func.blocks[succ].preds.insert(block_idx); } + } + for block_idx in 0..self.func.blocks.len() { + let block_idx = BlockIdx::new(block_idx); + let term_idx = self + .func + .try_get_block_term_inst_idx(block_idx) + .expect("known to have block term inst"); + let succs_and_params = &mut self.func.insts[term_idx] + .kind + .block_term_mut() + .expect("known to have block term inst") + .succs_and_params; + if succs_and_params.len() <= 1 { + continue; + } + if succs_and_params + .keys() + .all(|&succ_idx| self.func.blocks[succ_idx].preds.len() <= 1) + { + continue; + } + // has critical edges -- delete all but first succ to fix that + let mut first = true; + succs_and_params.retain(|&succ_idx, _| { + if first { + first = false; + return true; + } + let succ = &mut self.func.blocks[succ_idx]; + succ.preds.remove(&block_idx); + false + }); + } + let dominators = dominators::simple_fast(&self.func, BlockIdx::ENTRY_BLOCK); + for block_idx in 0..self.func.blocks.len() { + let block_idx = BlockIdx::new(block_idx); + self.func.blocks[block_idx].immediate_dominator = + dominators.immediate_dominator(block_idx); + } + // must have filled dominators first since available_ssa_vals_before_start() needs them + for block_idx in 0..self.func.blocks.len() { + let block_idx = BlockIdx::new(block_idx); + let mut available_ssa_vals = self.available_ssa_vals_before_start(block_idx); + available_ssa_vals.extend(&self.func.ssa_vals, &self.func.blocks[block_idx].params); for inst_idx in self.func.blocks[block_idx].insts { let inst = &mut self.func.insts[inst_idx]; - match &mut inst.kind { - InstKind::Normal => { - let _: (); - todo!() + for (operand_idx, operand) in inst.operands.iter_mut().enumerate() { + if operand.kind_and_constraint.kind() != OperandKind::Use { + continue; } + if available_ssa_vals.all.is_empty() { + // no ssa vals available, change to def + *operand = Operand { + kind_and_constraint: KindAndConstraint::Constraint { + kind: OperandKind::Def, + constraint: Constraint::Any, + }, + ssa_val: Self::new_ssa_val( + &mut self.func.ssa_vals, + self.u.arbitrary()?, + SSAValDef::Operand { + inst: inst_idx, + operand_idx, + }, + ), + stage: self.u.arbitrary()?, + }; + } else { + operand.ssa_val = *self.u.choose(&available_ssa_vals.all)?; + } + self.func.ssa_vals[operand.ssa_val] + .operand_uses + .insert(OperandUse { + inst: inst_idx, + operand_idx, + }); + } + available_ssa_vals.extend( + &self.func.ssa_vals, + inst.operands + .iter() + .filter(|o| o.kind_and_constraint.kind() == OperandKind::Def) + .map(|o| o.ssa_val), + ); + match &mut inst.kind { + InstKind::Normal => {} InstKind::Copy(_) => unreachable!(), InstKind::BlockTerm(block_term_inst_kind) => { - for (&succ, params) in &mut block_term_inst_kind.succs_and_params { - todo!(); + for (&succ_idx, params) in &mut block_term_inst_kind.succs_and_params { + let succ = &self.func.blocks[succ_idx]; + for (param_idx, &succ_param) in succ.params.iter().enumerate() { + let succ_param_ty = self.func.ssa_vals[succ_param].ty; + let choices = available_ssa_vals.per_ty(succ_param_ty); + let ssa_val_idx; + if choices.is_empty() { + // no available ssa vals with correct type, fix that by appending def operand with that type + ssa_val_idx = Self::new_ssa_val( + &mut self.func.ssa_vals, + succ_param_ty, + SSAValDef::Operand { + inst: inst_idx, + operand_idx: inst.operands.len(), + }, + ); + available_ssa_vals.extend(&self.func.ssa_vals, [ssa_val_idx]); + self.func.ssa_vals[ssa_val_idx].operand_uses.insert( + OperandUse { + inst: inst_idx, + operand_idx: inst.operands.len(), + }, + ); + inst.operands.push(Operand { + kind_and_constraint: KindAndConstraint::Constraint { + kind: OperandKind::Def, + constraint: Constraint::Any, + }, + ssa_val: ssa_val_idx, + stage: self.u.arbitrary()?, + }); + } else { + ssa_val_idx = *self.u.choose(choices)? + }; + params.push(ssa_val_idx); + self.func.ssa_vals[ssa_val_idx] + .branch_succ_param_uses + .insert(BranchSuccParamUse { + branch_inst: inst_idx, + succ: succ_idx, + param_idx, + }); + } + } + } + } + } + } + for inst in &mut self.func.insts { + let mut reusable_operand_idxs: HashMap> = HashMap::new(); + for (operand_idx, operand) in inst.operands.iter().enumerate() { + if operand.kind_and_constraint.kind() == OperandKind::Use { + reusable_operand_idxs + .entry(self.func.ssa_vals[operand.ssa_val].ty) + .or_default() + .push(operand_idx); + } + } + for operand in &mut inst.operands { + let KindAndConstraint::Constraint { kind, constraint } = &mut operand.kind_and_constraint else { + unreachable!(); + }; + // FIXME: change some defs to reuses + // FIXME: fill in constraint type + // match kind { + // OperandKind::Def + // } + } + match inst.kind { + InstKind::Normal => { + if self.u.arbitrary()? { + if let Some(copy_inst_kind) = + Self::make_copy_inst_kind(self.u, &self.func.ssa_vals, &inst.operands)? + { + inst.kind = InstKind::Copy(copy_inst_kind); } } } + InstKind::Copy(_) => unreachable!(), + InstKind::BlockTerm(_) => {} } } Ok(()) @@ -149,6 +454,7 @@ impl<'a> Arbitrary<'a> for FnFields { blocks: Vec::new(), start_inst_to_block_map: Default::default(), }, + available_ssa_vals_at_end: Default::default(), }; builder.run()?; Ok(builder.func) diff --git a/register_allocator/src/lib.rs b/register_allocator/src/lib.rs index 4a494fe..c359562 100644 --- a/register_allocator/src/lib.rs +++ b/register_allocator/src/lib.rs @@ -2,7 +2,6 @@ mod macros; pub mod error; pub mod function; -#[cfg(feature = "fuzzing")] pub mod fuzzing; pub mod index; pub mod interned; -- 2.30.2