register_allocator/src/fuzzing.rs

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