+#![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<Ty, Vec<SSAValIdx>>,
+ all: Vec<SSAValIdx>,
+}
+
+impl SSAValIdxs {
+ fn per_ty(&self, ty: Ty) -> &[SSAValIdx] {
+ self.per_ty.get(&ty).map(Deref::deref).unwrap_or_default()
+ }
+ fn extend<T: Borrow<SSAValIdx>>(
+ &mut self,
+ ssa_vals: &Vec<SSAVal>,
+ ssa_val_idxs: impl IntoIterator<Item = T>,
+ ) {
+ 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<BlockIdx, SSAValIdxs>,
}
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<BlockIdx>) -> 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<SSAVal>, ty: Ty, def: SSAValDef) -> SSAValIdx {
+ let retval = SSAValIdx::new(ssa_vals.len());
+ ssa_vals.push(SSAVal {
ty,
def,
operand_uses: Default::default(),
});
inst_idx
}
- fn make_ssa_val_use(&mut self) -> Result<SSAValIdx, Error> {
- todo!()
+ fn make_copy_inst_kind(
+ u: &mut Unstructured<'_>,
+ // takes ref to Vec since Index<SSAValIdx> is only implemented for Vec
+ ssa_vals: &Vec<SSAVal>,
+ operands: &[Operand],
+ ) -> Result<Option<CopyInstKind>, 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<Ty> = 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 {
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)
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<Ty, Vec<usize>> = 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(())
blocks: Vec::new(),
start_inst_to_block_map: Default::default(),
},
+ available_ssa_vals_at_end: Default::default(),
};
builder.run()?;
Ok(builder.func)
projects / bigint-presentation-code.git / blobdiff