From ff493c56d48c7abb03f031a937a87601bfb56e62 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Wed, 25 Jan 2023 18:05:29 -0800 Subject: [PATCH] wip --- .../fuzz/fuzz_targets/fn_new.rs | 21 ++- register_allocator/src/function.rs | 43 +++++- register_allocator/src/fuzzing.rs | 126 +++++++++++++++--- register_allocator/src/loc_set.rs | 9 +- 4 files changed, 171 insertions(+), 28 deletions(-) diff --git a/register_allocator/fuzz/fuzz_targets/fn_new.rs b/register_allocator/fuzz/fuzz_targets/fn_new.rs index 0dae950..7689721 100644 --- a/register_allocator/fuzz/fuzz_targets/fn_new.rs +++ b/register_allocator/fuzz/fuzz_targets/fn_new.rs @@ -1,7 +1,20 @@ #![no_main] -use bigint_presentation_code_register_allocator::function::{FnFields, Function}; -use libfuzzer_sys::fuzz_target; +use bigint_presentation_code_register_allocator::{ + function::{FnFields, Function}, + interned::GlobalState, +}; +use libfuzzer_sys::{ + arbitrary::{Arbitrary, Unstructured}, + fuzz_target, Corpus, +}; -fuzz_target!(|fields: FnFields| { - Function::new(fields).expect("should succeed"); +fuzz_target!(|data: &[u8]| -> Corpus { + GlobalState::scope(|| { + let u = Unstructured::new(data); + let Ok(fields) = FnFields::arbitrary_take_rest(u) else { + return Corpus::Reject; + }; + Function::new(fields).expect("should succeed"); + Corpus::Keep + }) }); diff --git a/register_allocator/src/function.rs b/register_allocator/src/function.rs index a9e88a0..28ff917 100644 --- a/register_allocator/src/function.rs +++ b/register_allocator/src/function.rs @@ -17,7 +17,7 @@ use smallvec::SmallVec; use std::{ collections::{btree_map, BTreeMap, BTreeSet}, mem, - ops::Index, + ops::{Index, IndexMut}, }; #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash, Serialize, Deserialize)] @@ -447,6 +447,12 @@ impl InstKind { _ => None, } } + pub fn block_term_mut(&mut self) -> Option<&mut BlockTermInstKind> { + match self { + InstKind::BlockTerm(v) => Some(v), + _ => None, + } + } pub fn copy(&self) -> Option<&CopyInstKind> { match self { InstKind::Copy(v) => Some(v), @@ -751,6 +757,11 @@ impl FnFields { .get(idx.get()) .ok_or(Error::InstIdxOutOfRange { idx }) } + pub fn try_get_inst_mut(&mut self, idx: InstIdx) -> Result<&mut Inst> { + self.insts + .get_mut(idx.get()) + .ok_or(Error::InstIdxOutOfRange { idx }) + } pub fn try_get_operand(&self, inst: InstIdx, operand_idx: usize) -> Result<&Operand> { self.try_get_inst(inst)?.try_get_operand(inst, operand_idx) } @@ -784,6 +795,18 @@ impl FnFields { .ok_or(Error::BlocksLastInstMustBeTerm { term_idx })?; Ok((term_idx, term_kind)) } + pub fn try_get_block_term_inst_and_kind_mut( + &mut self, + block: BlockIdx, + ) -> Result<(InstIdx, &mut BlockTermInstKind)> { + let term_idx = self.try_get_block_term_inst_idx(block)?; + let term_kind = self + .try_get_inst_mut(term_idx)? + .kind + .block_term_mut() + .ok_or(Error::BlocksLastInstMustBeTerm { term_idx })?; + Ok((term_idx, term_kind)) + } pub fn try_get_branch_target_params( &self, branch_inst: InstIdx, @@ -833,6 +856,12 @@ impl Index for Vec { } } +impl IndexMut for Vec { + fn index_mut(&mut self, index: SSAValIdx) -> &mut Self::Output { + &mut self[index.get()] + } +} + impl Index for Vec { type Output = Inst; @@ -841,6 +870,12 @@ impl Index for Vec { } } +impl IndexMut for Vec { + fn index_mut(&mut self, index: InstIdx) -> &mut Self::Output { + &mut self[index.get()] + } +} + impl Index for Vec { type Output = Block; @@ -849,6 +884,12 @@ impl Index for Vec { } } +impl IndexMut for Vec { + fn index_mut(&mut self, index: BlockIdx) -> &mut Self::Output { + &mut self[index.get()] + } +} + impl GraphBase for FnFields { type EdgeId = (BlockIdx, BlockIdx); type NodeId = BlockIdx; diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs index 2091a50..da43401 100644 --- a/register_allocator/src/fuzzing.rs +++ b/register_allocator/src/fuzzing.rs @@ -1,16 +1,22 @@ +use std::{collections::BTreeMap, num::NonZeroUsize}; + use crate::{ - function::{Block, FnFields, SSAVal, SSAValDef}, - index::{BlockIdx, SSAValIdx}, + function::{Block, BlockTermInstKind, FnFields, Inst, InstKind, Operand, SSAVal, SSAValDef}, + index::{BlockIdx, InstIdx, InstRange, SSAValIdx}, + interned::{GlobalState, Intern}, loc::Ty, + loc_set::LocSet, }; use arbitrary::{Arbitrary, Error, Unstructured}; +use petgraph::algo::dominators; -struct FnBuilder<'a, 'b> { +struct FnBuilder<'a, 'b, 'g> { + global_state: &'g GlobalState, u: &'a mut Unstructured<'b>, func: FnFields, } -impl FnBuilder<'_, '_> { +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 { @@ -21,8 +27,29 @@ impl FnBuilder<'_, '_> { }); retval } + fn new_inst_in_last_block( + &mut self, + kind: InstKind, + operands: Vec, + clobbers: LocSet, + ) -> InstIdx { + let block = self.func.blocks.last_mut().expect("no block"); + let inst_idx = block.insts.end; + assert_eq!(inst_idx.get(), self.func.insts.len()); + block.insts.end = block.insts.end.next(); + self.func.insts.push(Inst { + kind, + operands, + clobbers: clobbers.into_interned(self.global_state), + }); + inst_idx + } + fn make_ssa_val_use(&mut self) -> Result { + todo!() + } fn run(&mut self) -> Result<(), Error> { - for block_idx in 0..self.u.int_in_range(1..=10)? { + 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)? { @@ -35,13 +62,73 @@ impl FnBuilder<'_, '_> { }, )); } - let insts = todo!(); + let end = InstIdx::new(self.func.insts.len()); self.func.blocks.push(Block { params, - insts, + insts: InstRange { start: end, end }, preds: Default::default(), immediate_dominator: Default::default(), }); + for _ in 0..self.u.int_in_range(0..=10)? { + self.new_inst_in_last_block(InstKind::Normal, vec![], self.u.arbitrary()?); + } + 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)?.into()); + succs_and_params.insert(succ, vec![]); + } + } + 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!(), + }); + } + self.new_inst_in_last_block( + InstKind::BlockTerm(BlockTermInstKind { succs_and_params }), + operands, + self.u.arbitrary()?, + ); + } + 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) + .expect("known to have block term inst"); + let successors = self.func.insts[term_idx] + .kind + .block_term() + .expect("known to have block term inst") + .succs_and_params + .keys() + .copied(); + for succ in successors { + self.func.blocks[succ].preds.insert(block_idx); + } + 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!() + } + InstKind::Copy(_) => unreachable!(), + InstKind::BlockTerm(block_term_inst_kind) => { + for (&succ, params) in &mut block_term_inst_kind.succs_and_params {} + } + } + } } Ok(()) } @@ -49,16 +136,19 @@ impl FnBuilder<'_, '_> { impl<'a> Arbitrary<'a> for FnFields { fn arbitrary(u: &mut Unstructured<'a>) -> Result { - let mut builder = FnBuilder { - u, - func: Self { - ssa_vals: Vec::new(), - insts: Vec::new(), - blocks: Vec::new(), - start_inst_to_block_map: Default::default(), - }, - }; - builder.run()?; - Ok(builder.func) + GlobalState::get(|global_state| { + let mut builder = FnBuilder { + global_state, + u, + func: Self { + ssa_vals: Vec::new(), + insts: Vec::new(), + blocks: Vec::new(), + start_inst_to_block_map: Default::default(), + }, + }; + builder.run()?; + Ok(builder.func) + }) } } diff --git a/register_allocator/src/loc_set.rs b/register_allocator/src/loc_set.rs index 8b7610a..a9d8565 100644 --- a/register_allocator/src/loc_set.rs +++ b/register_allocator/src/loc_set.rs @@ -10,6 +10,7 @@ use serde::{Deserialize, Serialize}; use std::{ borrow::{Borrow, Cow}, cell::Cell, + collections::BTreeMap, fmt, hash::Hash, iter::{FusedIterator, Peekable}, @@ -22,23 +23,21 @@ use std::{ #[derive(Deserialize)] struct LocSetSerialized { - starts: EnumMap, - ty: Option, + reg_len_to_starts_map: BTreeMap>, } impl TryFrom for LocSet { type Error = Error; fn try_from(value: LocSetSerialized) -> Result { - Self::from_parts(value.starts, value.ty) + Self::from_reg_len_to_starts_map(value.reg_len_to_starts_map) } } #[derive(Clone, Default, PartialEq, Eq, Hash, Serialize, Deserialize)] #[serde(try_from = "LocSetSerialized")] pub struct LocSet { - starts: EnumMap, - ty: Option, + reg_len_to_starts_map: BTreeMap>, } /// computes same value as `a & !b`, but more efficiently -- 2.30.2