From 37019b019aec7e279f1fbcb2ce9188f41c643152 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Wed, 1 Feb 2023 17:43:48 -0800 Subject: [PATCH] fn_new passes fuzzing afaict --- .../fuzz/fuzz_targets/fn_new.rs | 6 +- register_allocator/src/function.rs | 213 ++++++++++++++---- register_allocator/src/fuzzing.rs | 154 +++++++++---- 3 files changed, 283 insertions(+), 90 deletions(-) diff --git a/register_allocator/fuzz/fuzz_targets/fn_new.rs b/register_allocator/fuzz/fuzz_targets/fn_new.rs index 7689721..1f52aa4 100644 --- a/register_allocator/fuzz/fuzz_targets/fn_new.rs +++ b/register_allocator/fuzz/fuzz_targets/fn_new.rs @@ -1,4 +1,5 @@ #![no_main] + use bigint_presentation_code_register_allocator::{ function::{FnFields, Function}, interned::GlobalState, @@ -14,7 +15,10 @@ fuzz_target!(|data: &[u8]| -> Corpus { let Ok(fields) = FnFields::arbitrary_take_rest(u) else { return Corpus::Reject; }; - Function::new(fields).expect("should succeed"); + let fields_str = format!("{fields:#?}"); + if let Err(e) = Function::new(fields) { + panic!("{fields_str}\nerror: {e}"); + } Corpus::Keep }) }); diff --git a/register_allocator/src/function.rs b/register_allocator/src/function.rs index 4577581..b823f3c 100644 --- a/register_allocator/src/function.rs +++ b/register_allocator/src/function.rs @@ -2,11 +2,12 @@ use crate::{ error::{Error, Result}, index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, interned::{GlobalState, Intern, Interned}, - loc::{BaseTy, Loc, Ty}, + loc::{BaseTy, Loc, LocFields, LocKind, Ty}, loc_set::LocSet, }; use arbitrary::Arbitrary; use core::fmt; +use enum_map::Enum; use hashbrown::HashSet; use petgraph::{ algo::dominators, @@ -108,7 +109,18 @@ impl SSAVal { } #[derive( - Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary, + Copy, + Clone, + PartialEq, + Eq, + PartialOrd, + Ord, + Debug, + Hash, + Serialize, + Deserialize, + Arbitrary, + Enum, )] #[repr(u8)] pub enum InstStage { @@ -181,7 +193,18 @@ impl TryFrom for ProgPoint { } #[derive( - Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary, + Copy, + Clone, + PartialEq, + Eq, + PartialOrd, + Ord, + Debug, + Hash, + Serialize, + Deserialize, + Arbitrary, + Enum, )] #[repr(u8)] pub enum OperandKind { @@ -189,7 +212,9 @@ pub enum OperandKind { Def = 1, } -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize)] +#[derive( + Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Serialize, Deserialize, Arbitrary, +)] pub enum Constraint { /// any register or stack location Any, @@ -210,6 +235,68 @@ impl Constraint { pub fn is_any(&self) -> bool { matches!(self, Self::Any) } + pub fn fixed_loc(&self) -> Option { + match *self { + Constraint::Any + | Constraint::BaseGpr + | Constraint::SVExtra2VGpr + | Constraint::SVExtra2SGpr + | Constraint::SVExtra3Gpr + | Constraint::Stack => None, + Constraint::FixedLoc(v) => Some(v), + } + } + pub fn non_fixed_choices_for_ty(ty: Ty) -> &'static [Constraint] { + match (ty.base_ty, ty.reg_len.get()) { + (BaseTy::Bits64, 1) => &[ + Constraint::Any, + Constraint::BaseGpr, + Constraint::SVExtra2SGpr, + Constraint::SVExtra2VGpr, + Constraint::SVExtra3Gpr, + Constraint::Stack, + ], + (BaseTy::Bits64, _) => &[ + Constraint::Any, + Constraint::SVExtra2VGpr, + Constraint::SVExtra3Gpr, + Constraint::Stack, + ], + (BaseTy::Ca, _) | (BaseTy::VlMaxvl, _) => &[Constraint::Any, Constraint::Stack], + } + } + pub fn arbitrary_with_ty( + ty: Ty, + u: &mut arbitrary::Unstructured<'_>, + ) -> arbitrary::Result { + let non_fixed_choices = Self::non_fixed_choices_for_ty(ty); + if let Some(&retval) = non_fixed_choices.get(u.choose_index(non_fixed_choices.len() + 1)?) { + Ok(retval) + } else { + Ok(Constraint::FixedLoc(Loc::arbitrary_with_ty(ty, u)?)) + } + } + pub fn check_for_ty_mismatch(&self, ty: Ty) -> Result<(), ()> { + match self { + Constraint::Any | Constraint::Stack => {} + Constraint::BaseGpr | Constraint::SVExtra2SGpr => { + if ty != Ty::scalar(BaseTy::Bits64) { + return Err(()); + } + } + Constraint::SVExtra2VGpr | Constraint::SVExtra3Gpr => { + if ty.base_ty != BaseTy::Bits64 { + return Err(()); + } + } + Constraint::FixedLoc(loc) => { + if ty != loc.ty() { + return Err(()); + } + } + } + Ok(()) + } } impl Default for Constraint { @@ -376,42 +463,21 @@ impl Operand { } } let constraint = self.try_constraint(inst, func)?; - match constraint { - Constraint::Any | Constraint::Stack => {} - Constraint::BaseGpr | Constraint::SVExtra2SGpr => { - if ssa_val.ty != Ty::scalar(BaseTy::Bits64) { - return Err(Error::ConstraintTyMismatch { - ssa_val_idx, - inst, - operand_idx, - }); - } - } - Constraint::SVExtra2VGpr | Constraint::SVExtra3Gpr => { - if ssa_val.ty.base_ty != BaseTy::Bits64 { - return Err(Error::ConstraintTyMismatch { - ssa_val_idx, - inst, - operand_idx, - }); - } - } - Constraint::FixedLoc(loc) => { - if func - .try_get_inst(inst)? - .clobbers - .clone() - .conflicts_with(loc, global_state) - { - return Err(Error::FixedLocConflictsWithClobbers { inst, operand_idx }); - } - if ssa_val.ty != loc.ty() { - return Err(Error::ConstraintTyMismatch { - ssa_val_idx, - inst, - operand_idx, - }); - } + constraint + .check_for_ty_mismatch(ssa_val.ty) + .map_err(|()| Error::ConstraintTyMismatch { + ssa_val_idx, + inst, + operand_idx, + })?; + if let Some(fixed_loc) = constraint.fixed_loc() { + if func + .try_get_inst(inst)? + .clobbers + .clone() + .conflicts_with(fixed_loc, global_state) + { + return Err(Error::FixedLocConflictsWithClobbers { inst, operand_idx }); } } Ok(()) @@ -680,7 +746,7 @@ impl Block { for &pred in preds { let (term_inst, BlockTermInstKind { succs_and_params }) = func.try_get_block_term_inst_and_kind(pred)?; - if !succs_and_params.contains_key(&pred) { + if !succs_and_params.contains_key(&block) { return Err(Error::PredMissingFromPredsTermBranchsTargets { src_block: pred, branch_inst: term_inst, @@ -969,3 +1035,68 @@ impl Visitable for FnFields { impl GraphProp for FnFields { type EdgeType = Directed; } + +#[cfg(test)] +mod tests { + use super::*; + use crate::loc::TyFields; + use std::num::NonZeroU32; + + #[test] + fn test_constraint_non_fixed_choices_for_ty() { + macro_rules! seen { + ( + enum ConstraintWithoutFixedLoc { + $($field:ident,)* + } + ) => { + #[derive(Default)] + #[allow(non_snake_case)] + struct Seen { + $($field: bool,)* + } + + impl Seen { + fn add(&mut self, constraint: &Constraint) { + match constraint { + Constraint::FixedLoc(_) => {} + $(Constraint::$field => self.$field = true,)* + } + } + fn check(self) { + $(assert!(self.$field, "never seen field: {}", stringify!($field));)* + } + } + }; + } + seen! { + enum ConstraintWithoutFixedLoc { + Any, + BaseGpr, + SVExtra2VGpr, + SVExtra2SGpr, + SVExtra3Gpr, + Stack, + } + } + let mut seen = Seen::default(); + for base_ty in 0..BaseTy::LENGTH { + let base_ty = BaseTy::from_usize(base_ty); + for reg_len in [1, 2, 100] { + let reg_len = NonZeroU32::new(reg_len).unwrap(); + let ty = Ty::new_or_scalar(TyFields { base_ty, reg_len }); + let non_fixed_choices = Constraint::non_fixed_choices_for_ty(ty); + assert_eq!(non_fixed_choices.first(), Some(&Constraint::Any)); + assert_eq!(non_fixed_choices.last(), Some(&Constraint::Stack)); + for constraint in non_fixed_choices { + assert_eq!(constraint.fixed_loc(), None); + seen.add(constraint); + if constraint.check_for_ty_mismatch(ty).is_err() { + panic!("constraint ty mismatch: constraint={constraint:?} ty={ty:?}"); + } + } + } + } + seen.check(); + } +} diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs index 165530b..235ed73 100644 --- a/register_allocator/src/fuzzing.rs +++ b/register_allocator/src/fuzzing.rs @@ -2,7 +2,8 @@ use crate::{ function::{ Block, BlockTermInstKind, BranchSuccParamUse, Constraint, CopyInstKind, FnFields, Inst, - InstKind, KindAndConstraint, Operand, OperandKind, OperandUse, SSAVal, SSAValDef, + InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly, + OperandUse, SSAVal, SSAValDef, }, index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, interned::{GlobalState, Intern}, @@ -10,6 +11,7 @@ use crate::{ loc_set::LocSet, }; use arbitrary::{Arbitrary, Error, Unstructured}; +use enum_map::EnumMap; use hashbrown::HashMap; use petgraph::algo::dominators; use std::{borrow::Borrow, collections::BTreeMap, ops::Deref}; @@ -107,6 +109,7 @@ impl FnBuilder<'_, '_, '_> { u: &mut Unstructured<'_>, // takes ref to Vec since Index is only implemented for Vec ssa_vals: &Vec, + _inst_idx: InstIdx, // for debugging operands: &[Operand], ) -> Result, Error> { if operands.is_empty() { @@ -123,35 +126,32 @@ impl FnBuilder<'_, '_, '_> { 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)?); + // src can have duplicates, so pick randomly + let possible_src_operand_idxs = (0..u.int_in_range(1..=3)?) + .map(|_| u.choose(&possible_src_operand_idxs).copied()) + .collect::, Error>>()?; + // dest can't have duplicates, so shuffle + let len = possible_dest_operand_idxs.len(); + for i in 0..len { + possible_dest_operand_idxs.swap(i, u.choose_index(len)?); } - 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; + possible_dest_operand_idxs.truncate(u.int_in_range(1..=3)?); + let mut copy_ty: Option = None; + let mut src_operand_idxs = vec![]; + let mut dest_operand_idxs = vec![]; + for src_operand_idx in possible_src_operand_idxs { + let operand_type = ssa_vals[operands[src_operand_idx].ssa_val].ty; + let proposed_copy_ty = match copy_ty.map(|ty| ty.try_concat(operand_type)) { + None => operand_type, + Some(Ok(ty)) => ty, + Some(Err(_)) => continue, }; - let mut possible_dest_operand_idxs = possible_dest_operand_idxs.clone(); - let mut dest_operand_idxs = vec![]; + let mut proposed_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); + for &dest_operand_idx in &possible_dest_operand_idxs { 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 + if dest_operand_ty.base_ty != proposed_copy_ty.base_ty + || dest_operand_ty.reg_len > proposed_copy_ty.reg_len { continue; } @@ -163,22 +163,24 @@ impl FnBuilder<'_, '_, '_> { } else { dest_operand_ty }; - if next_dest_copy_ty.reg_len > copy_ty.reg_len { + if next_dest_copy_ty.reg_len > proposed_copy_ty.reg_len { continue; } dest_copy_ty = Some(next_dest_copy_ty); - dest_operand_idxs.push(dest_operand_idx); + proposed_dest_operand_idxs.push(dest_operand_idx); } - if dest_copy_ty != Some(copy_ty) || dest_operand_idxs.is_empty() { + if dest_copy_ty != Some(proposed_copy_ty) || proposed_dest_operand_idxs.is_empty() { continue; } - return Ok(Some(CopyInstKind { - src_operand_idxs, - dest_operand_idxs, - copy_ty, - })); + copy_ty = Some(proposed_copy_ty); + src_operand_idxs.push(src_operand_idx); + dest_operand_idxs = proposed_dest_operand_idxs; } - Ok(None) + Ok(copy_ty.map(|copy_ty| CopyInstKind { + src_operand_idxs, + dest_operand_idxs, + copy_ty, + })) } fn run(&mut self) -> Result<(), Error> { let block_count = self.u.int_in_range(1..=10u16)?; @@ -225,7 +227,7 @@ impl FnBuilder<'_, '_, '_> { operands.push(Operand { ssa_val, kind_and_constraint: KindAndConstraint::Constraint { - kind: self.u.arbitrary()?, + kind, constraint: Constraint::Any, }, stage: self.u.arbitrary()?, @@ -233,7 +235,7 @@ impl FnBuilder<'_, '_, '_> { } 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); + let succ_range = (BlockIdx::ENTRY_BLOCK.get() as u16 + 1)..=(block_count - 1); if !succ_range.is_empty() { for i in 0..self.u.int_in_range(0..=3usize)? { if i > succ_range.len() { @@ -404,7 +406,8 @@ impl FnBuilder<'_, '_, '_> { } } } - for inst in &mut self.func.insts { + for (inst_idx, inst) in self.func.insts.iter_mut().enumerate() { + let inst_idx = InstIdx::new(inst_idx); 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 { @@ -414,22 +417,77 @@ impl FnBuilder<'_, '_, '_> { .push(operand_idx); } } - for operand in &mut inst.operands { - let KindAndConstraint::Constraint { kind, constraint } = &mut operand.kind_and_constraint else { + let mut used_locs = EnumMap::::default(); + for operand_idx in 0..inst.operands.len() { + let operand = &inst.operands[operand_idx]; + let operand_ty = self.func.ssa_vals[operand.ssa_val].ty; + if operand.kind_and_constraint.kind() == OperandKind::Def && self.u.arbitrary()? { + let reuse_operand_idx = self.u.choose_index(inst.operands.len())?; + let reuse_operand = &inst.operands[reuse_operand_idx]; + if reuse_operand_idx != operand_idx + && reuse_operand.kind_and_constraint.kind() == OperandKind::Use + && self.func.ssa_vals[reuse_operand.ssa_val].ty == operand_ty + { + inst.operands[operand_idx].kind_and_constraint = KindAndConstraint::Reuse { + kind: OperandKindDefOnly, + reuse_operand_idx, + }; + continue; + } + } + let operand = &mut inst.operands[operand_idx]; + let KindAndConstraint::Constraint { + kind, + ref mut constraint,.. + } = operand.kind_and_constraint else { unreachable!(); }; - // FIXME: change some defs to reuses - // FIXME: fill in constraint type - // match kind { - // OperandKind::Def - // } + *constraint = Constraint::arbitrary_with_ty(operand_ty, self.u)?; + if let Some(fixed_loc) = constraint.fixed_loc() { + // is the operand probably live for both stages + let probably_live_for_both_stages = match (kind, operand.stage) { + (OperandKind::Use, InstStage::Late) => true, // also probably live for early stage + (OperandKind::Def, InstStage::Early) => true, // also probably live for late stage + _ => false, + }; + let mut conflicts = inst + .clobbers + .clone() + .conflicts_with(fixed_loc, self.global_state); + if probably_live_for_both_stages { + for used_locs in used_locs.values() { + conflicts = conflicts + || used_locs + .to_interned(self.global_state) + .conflicts_with(fixed_loc, self.global_state); + } + } else { + conflicts = conflicts + || used_locs[operand.stage] + .to_interned(self.global_state) + .conflicts_with(fixed_loc, self.global_state); + } + if conflicts { + // conflicting constraint, so switch to a safe default instead + *constraint = Constraint::Any; + } else if probably_live_for_both_stages { + for used_locs in used_locs.values_mut() { + used_locs.insert(fixed_loc); + } + } else { + used_locs[operand.stage].insert(fixed_loc); + } + } } 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)? - { + if let Some(copy_inst_kind) = Self::make_copy_inst_kind( + self.u, + &self.func.ssa_vals, + inst_idx, + &inst.operands, + )? { inst.kind = InstKind::Copy(copy_inst_kind); } } -- 2.30.2