register_allocator/src/fuzzing.rs

   1 use std::{collections::BTreeMap, num::NonZeroUsize};
   2
   3 use crate::{
   4     function::{Block, BlockTermInstKind, FnFields, Inst, InstKind, Operand, SSAVal, SSAValDef},
   5     index::{BlockIdx, InstIdx, InstRange, SSAValIdx},
   6     interned::{GlobalState, Intern},
   7     loc::Ty,
   8     loc_set::LocSet,
   9 };
  10 use arbitrary::{Arbitrary, Error, Unstructured};
  11 use petgraph::algo::dominators;
  12
  13 struct FnBuilder<'a, 'b, 'g> {
  14     global_state: &'g GlobalState,
  15     u: &'a mut Unstructured<'b>,
  16     func: FnFields,
  17 }
  18
  19 impl FnBuilder<'_, '_, '_> {
  20     fn new_ssa_val(&mut self, ty: Ty, def: SSAValDef) -> SSAValIdx {
  21         let retval = SSAValIdx::new(self.func.ssa_vals.len());
  22         self.func.ssa_vals.push(SSAVal {
  23             ty,
  24             def,
  25             operand_uses: Default::default(),
  26             branch_succ_param_uses: Default::default(),
  27         });
  28         retval
  29     }
  30     fn new_inst_in_last_block(
  31         &mut self,
  32         kind: InstKind,
  33         operands: Vec<Operand>,
  34         clobbers: LocSet,
  35     ) -> InstIdx {
  36         let block = self.func.blocks.last_mut().expect("no block");
  37         let inst_idx = block.insts.end;
  38         assert_eq!(inst_idx.get(), self.func.insts.len());
  39         block.insts.end = block.insts.end.next();
  40         self.func.insts.push(Inst {
  41             kind,
  42             operands,
  43             clobbers: clobbers.into_interned(self.global_state),
  44         });
  45         inst_idx
  46     }
  47     fn make_ssa_val_use(&mut self) -> Result<SSAValIdx, Error> {
  48         todo!()
  49     }
  50     fn run(&mut self) -> Result<(), Error> {
  51         let block_count = self.u.int_in_range(1..=10u16)?;
  52         for block_idx in 0..block_count as usize {
  53             let block_idx = BlockIdx::new(block_idx);
  54             let mut params = Vec::new();
  55             for param_idx in 0..self.u.int_in_range(0..=10)? {
  56                 let ty = self.u.arbitrary()?;
  57                 params.push(self.new_ssa_val(
  58                     ty,
  59                     SSAValDef::BlockParam {
  60                         block: block_idx,
  61                         param_idx,
  62                     },
  63                 ));
  64             }
  65             let end = InstIdx::new(self.func.insts.len());
  66             self.func.blocks.push(Block {
  67                 params,
  68                 insts: InstRange { start: end, end },
  69                 preds: Default::default(),
  70                 immediate_dominator: Default::default(),
  71             });
  72             for _ in 0..self.u.int_in_range(0..=10)? {
  73                 self.new_inst_in_last_block(InstKind::Normal, vec![], self.u.arbitrary()?);
  74             }
  75             let mut succs_and_params = BTreeMap::default();
  76             let succ_range = BlockIdx::ENTRY_BLOCK.get() as u16..=(block_count - 1);
  77             if !succ_range.is_empty() {
  78                 for i in 0..self.u.int_in_range(0..=3usize)? {
  79                     if i > succ_range.len() {
  80                         break;
  81                     }
  82                     let succ = BlockIdx::new(self.u.int_in_range(succ_range)?.into());
  83                     succs_and_params.insert(succ, vec![]);
  84                 }
  85             }
  86             let mut operands = vec![];
  87             for _ in 0..self.u.int_in_range(0..=5)? {
  88                 operands.push(Operand {
  89                     ssa_val: todo!(),
  90                     kind_and_constraint: todo!(),
  91                     stage: todo!(),
  92                 });
  93             }
  94             self.new_inst_in_last_block(
  95                 InstKind::BlockTerm(BlockTermInstKind { succs_and_params }),
  96                 operands,
  97                 self.u.arbitrary()?,
  98             );
  99         }
 100         let dominators = dominators::simple_fast(&self.func, BlockIdx::ENTRY_BLOCK);
 101         for block_idx in 0..self.func.blocks.len() {
 102             let block_idx = BlockIdx::new(block_idx);
 103             self.func.blocks[block_idx].immediate_dominator =
 104                 dominators.immediate_dominator(block_idx);
 105             let term_idx = self
 106                 .func
 107                 .try_get_block_term_inst_idx(block_idx)
 108                 .expect("known to have block term inst");
 109             let successors = self.func.insts[term_idx]
 110                 .kind
 111                 .block_term()
 112                 .expect("known to have block term inst")
 113                 .succs_and_params
 114                 .keys()
 115                 .copied();
 116             for succ in successors {
 117                 self.func.blocks[succ].preds.insert(block_idx);
 118             }
 119             for inst_idx in self.func.blocks[block_idx].insts {
 120                 let inst = &mut self.func.insts[inst_idx];
 121                 match &mut inst.kind {
 122                     InstKind::Normal => {
 123                         let _;
 124                         todo!()
 125                     }
 126                     InstKind::Copy(_) => unreachable!(),
 127                     InstKind::BlockTerm(block_term_inst_kind) => {
 128                         for (&succ, params) in &mut block_term_inst_kind.succs_and_params {}
 129                     }
 130                 }
 131             }
 132         }
 133         Ok(())
 134     }
 135 }
 136
 137 impl<'a> Arbitrary<'a> for FnFields {
 138     fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self, Error> {
 139         GlobalState::get(|global_state| {
 140             let mut builder = FnBuilder {
 141                 global_state,
 142                 u,
 143                 func: Self {
 144                     ssa_vals: Vec::new(),
 145                     insts: Vec::new(),
 146                     blocks: Vec::new(),
 147                     start_inst_to_block_map: Default::default(),
 148                 },
 149             };
 150             builder.run()?;
 151             Ok(builder.func)
 152         })
 153     }
 154 }