register_allocator/src/fuzzing.rs

   1 #![cfg(feature = "fuzzing")]
   2 use crate::{
   3     function::{
   4         Block, BlockTermInstKind, BranchSuccParamUse, Constraint, CopyInstKind, FnFields, Inst,
   5         InstKind, InstStage, KindAndConstraint, Operand, OperandKind, OperandKindDefOnly,
   6         OperandUse, SSAVal, SSAValDef,
   7     },
   8     index::{BlockIdx, InstIdx, InstRange, SSAValIdx},
   9     interned::{GlobalState, Intern},
  10     loc::Ty,
  11     loc_set::LocSet,
  12 };
  13 use arbitrary::{Arbitrary, Error, Unstructured};
  14 use enum_map::EnumMap;
  15 use hashbrown::HashMap;
  16 use petgraph::algo::dominators;
  17 use std::{borrow::Borrow, collections::BTreeMap, ops::Deref};
  18
  19 #[derive(Clone, Debug, Default)]
  20 struct SSAValIdxs {
  21     per_ty: HashMap<Ty, Vec<SSAValIdx>>,
  22     all: Vec<SSAValIdx>,
  23 }
  24
  25 impl SSAValIdxs {
  26     fn per_ty(&self, ty: Ty) -> &[SSAValIdx] {
  27         self.per_ty.get(&ty).map(Deref::deref).unwrap_or_default()
  28     }
  29     fn extend<T: Borrow<SSAValIdx>>(
  30         &mut self,
  31         ssa_vals: &Vec<SSAVal>,
  32         ssa_val_idxs: impl IntoIterator<Item = T>,
  33     ) {
  34         for ssa_val_idx in ssa_val_idxs {
  35             let ssa_val_idx: SSAValIdx = *ssa_val_idx.borrow();
  36             self.per_ty
  37                 .entry(ssa_vals[ssa_val_idx].ty)
  38                 .or_default()
  39                 .push(ssa_val_idx);
  40             self.all.push(ssa_val_idx);
  41         }
  42     }
  43 }
  44
  45 struct FnBuilder<'a, 'b, 'g> {
  46     global_state: &'g GlobalState,
  47     u: &'a mut Unstructured<'b>,
  48     func: FnFields,
  49     available_ssa_vals_at_end: HashMap<BlockIdx, SSAValIdxs>,
  50 }
  51
  52 impl FnBuilder<'_, '_, '_> {
  53     fn available_ssa_vals_at_end(&mut self, block_idx: Option<BlockIdx>) -> SSAValIdxs {
  54         let Some(block_idx) = block_idx else {
  55             return Default::default();
  56         };
  57         if let Some(retval) = self.available_ssa_vals_at_end.get(&block_idx) {
  58             return retval.clone();
  59         }
  60         let mut available_ssa_vals = self.available_ssa_vals_before_start(block_idx);
  61         let block = &self.func.blocks[block_idx];
  62         available_ssa_vals.extend(&self.func.ssa_vals, &block.params);
  63         for inst_idx in block.insts {
  64             let inst = &self.func.insts[inst_idx];
  65             available_ssa_vals.extend(
  66                 &self.func.ssa_vals,
  67                 inst.operands
  68                     .iter()
  69                     .filter(|o| o.kind_and_constraint.kind() == OperandKind::Def)
  70                     .map(|o| o.ssa_val),
  71             );
  72         }
  73         self.available_ssa_vals_at_end
  74             .insert(block_idx, available_ssa_vals.clone());
  75         available_ssa_vals
  76     }
  77     fn available_ssa_vals_before_start(&mut self, block_idx: BlockIdx) -> SSAValIdxs {
  78         let idom = self.func.blocks[block_idx].immediate_dominator;
  79         self.available_ssa_vals_at_end(idom)
  80     }
  81     fn new_ssa_val(ssa_vals: &mut Vec<SSAVal>, ty: Ty, def: SSAValDef) -> SSAValIdx {
  82         let retval = SSAValIdx::new(ssa_vals.len());
  83         ssa_vals.push(SSAVal {
  84             ty,
  85             def,
  86             operand_uses: Default::default(),
  87             branch_succ_param_uses: Default::default(),
  88         });
  89         retval
  90     }
  91     fn new_inst_in_last_block(
  92         &mut self,
  93         kind: InstKind,
  94         operands: Vec<Operand>,
  95         clobbers: LocSet,
  96     ) -> InstIdx {
  97         let block = self.func.blocks.last_mut().expect("no block");
  98         let inst_idx = block.insts.end;
  99         assert_eq!(inst_idx.get(), self.func.insts.len());
 100         block.insts.end = block.insts.end.next();
 101         self.func.insts.push(Inst {
 102             kind,
 103             operands,
 104             clobbers: clobbers.into_interned(self.global_state),
 105         });
 106         inst_idx
 107     }
 108     fn make_copy_inst_kind(
 109         u: &mut Unstructured<'_>,
 110         // takes ref to Vec since Index<SSAValIdx> is only implemented for Vec
 111         ssa_vals: &Vec<SSAVal>,
 112         _inst_idx: InstIdx, // for debugging
 113         operands: &[Operand],
 114     ) -> Result<Option<CopyInstKind>, Error> {
 115         if operands.is_empty() {
 116             return Ok(None);
 117         }
 118         let mut possible_src_operand_idxs = vec![];
 119         let mut possible_dest_operand_idxs = vec![];
 120         for (operand_idx, operand) in operands.iter().enumerate() {
 121             match operand.kind_and_constraint.kind() {
 122                 OperandKind::Use => possible_src_operand_idxs.push(operand_idx),
 123                 OperandKind::Def => possible_dest_operand_idxs.push(operand_idx),
 124             }
 125         }
 126         if possible_src_operand_idxs.is_empty() || possible_dest_operand_idxs.is_empty() {
 127             return Ok(None);
 128         }
 129         // src can have duplicates, so pick randomly
 130         let possible_src_operand_idxs = (0..u.int_in_range(1..=3)?)
 131             .map(|_| u.choose(&possible_src_operand_idxs).copied())
 132             .collect::<Result<Vec<usize>, Error>>()?;
 133         // dest can't have duplicates, so shuffle
 134         let len = possible_dest_operand_idxs.len();
 135         for i in 0..len {
 136             possible_dest_operand_idxs.swap(i, u.choose_index(len)?);
 137         }
 138         possible_dest_operand_idxs.truncate(u.int_in_range(1..=3)?);
 139         let mut copy_ty: Option<Ty> = None;
 140         let mut src_operand_idxs = vec![];
 141         let mut dest_operand_idxs = vec![];
 142         for src_operand_idx in possible_src_operand_idxs {
 143             let operand_type = ssa_vals[operands[src_operand_idx].ssa_val].ty;
 144             let proposed_copy_ty = match copy_ty.map(|ty| ty.try_concat(operand_type)) {
 145                 None => operand_type,
 146                 Some(Ok(ty)) => ty,
 147                 Some(Err(_)) => continue,
 148             };
 149             let mut proposed_dest_operand_idxs = vec![];
 150             let mut dest_copy_ty: Option<Ty> = None;
 151             for &dest_operand_idx in &possible_dest_operand_idxs {
 152                 let dest_operand_ty = ssa_vals[operands[dest_operand_idx].ssa_val].ty;
 153                 if dest_operand_ty.base_ty != proposed_copy_ty.base_ty
 154                     || dest_operand_ty.reg_len > proposed_copy_ty.reg_len
 155                 {
 156                     continue;
 157                 }
 158                 let next_dest_copy_ty = if let Some(dest_copy_ty) = dest_copy_ty {
 159                     let Ok(ty) = dest_copy_ty.try_concat(dest_operand_ty) else {
 160                         continue;
 161                     };
 162                     ty
 163                 } else {
 164                     dest_operand_ty
 165                 };
 166                 if next_dest_copy_ty.reg_len > proposed_copy_ty.reg_len {
 167                     continue;
 168                 }
 169                 dest_copy_ty = Some(next_dest_copy_ty);
 170                 proposed_dest_operand_idxs.push(dest_operand_idx);
 171             }
 172             if dest_copy_ty != Some(proposed_copy_ty) || proposed_dest_operand_idxs.is_empty() {
 173                 continue;
 174             }
 175             copy_ty = Some(proposed_copy_ty);
 176             src_operand_idxs.push(src_operand_idx);
 177             dest_operand_idxs = proposed_dest_operand_idxs;
 178         }
 179         Ok(copy_ty.map(|copy_ty| CopyInstKind {
 180             src_operand_idxs,
 181             dest_operand_idxs,
 182             copy_ty,
 183         }))
 184     }
 185     fn run(&mut self) -> Result<(), Error> {
 186         let block_count = self.u.int_in_range(1..=10u16)?;
 187         for block_idx in 0..block_count as usize {
 188             let block_idx = BlockIdx::new(block_idx);
 189             let mut params = Vec::new();
 190             if block_idx != BlockIdx::ENTRY_BLOCK {
 191                 for param_idx in 0..self.u.int_in_range(0..=10)? {
 192                     let ty = self.u.arbitrary()?;
 193                     params.push(Self::new_ssa_val(
 194                         &mut self.func.ssa_vals,
 195                         ty,
 196                         SSAValDef::BlockParam {
 197                             block: block_idx,
 198                             param_idx,
 199                         },
 200                     ));
 201                 }
 202             }
 203             let end = InstIdx::new(self.func.insts.len());
 204             self.func.blocks.push(Block {
 205                 params,
 206                 insts: InstRange { start: end, end },
 207                 preds: Default::default(),
 208                 immediate_dominator: Default::default(),
 209             });
 210             for is_term in (0..self.u.int_in_range(0..=10)?)
 211                 .map(|_| false)
 212                 .chain([true])
 213             {
 214                 let mut operands = vec![];
 215                 for _ in 0..self.u.int_in_range(0..=5)? {
 216                     let kind = self.u.arbitrary()?;
 217                     let ssa_val = if let OperandKind::Def = kind {
 218                         let ty = self.u.arbitrary()?;
 219                         let def = SSAValDef::Operand {
 220                             inst: InstIdx::new(self.func.insts.len()),
 221                             operand_idx: operands.len(),
 222                         };
 223                         Self::new_ssa_val(&mut self.func.ssa_vals, ty, def)
 224                     } else {
 225                         SSAValIdx::new(!0)
 226                     };
 227                     operands.push(Operand {
 228                         ssa_val,
 229                         kind_and_constraint: KindAndConstraint::Constraint {
 230                             kind,
 231                             constraint: Constraint::Any,
 232                         },
 233                         stage: self.u.arbitrary()?,
 234                     });
 235                 }
 236                 let inst_kind = if is_term {
 237                     let mut succs_and_params = BTreeMap::default();
 238                     let succ_range = (BlockIdx::ENTRY_BLOCK.get() as u16 + 1)..=(block_count - 1);
 239                     if !succ_range.is_empty() {
 240                         for i in 0..self.u.int_in_range(0..=3usize)? {
 241                             if i > succ_range.len() {
 242                                 break;
 243                             }
 244                             let succ =
 245                                 BlockIdx::new(self.u.int_in_range(succ_range.clone())?.into());
 246                             succs_and_params.insert(succ, vec![]);
 247                         }
 248                     }
 249                     InstKind::BlockTerm(BlockTermInstKind { succs_and_params })
 250                 } else {
 251                     InstKind::Normal
 252                 };
 253                 let clobbers = self.u.arbitrary()?;
 254                 self.new_inst_in_last_block(inst_kind, operands, clobbers);
 255             }
 256         }
 257         for block_idx in 0..self.func.blocks.len() {
 258             let block_idx = BlockIdx::new(block_idx);
 259             let term_idx = self
 260                 .func
 261                 .try_get_block_term_inst_idx(block_idx)
 262                 .expect("known to have block term inst");
 263             let successors = self.func.insts[term_idx]
 264                 .kind
 265                 .block_term()
 266                 .expect("known to have block term inst")
 267                 .succs_and_params
 268                 .keys()
 269                 .copied();
 270             for succ in successors {
 271                 self.func.blocks[succ].preds.insert(block_idx);
 272             }
 273         }
 274         for block_idx in 0..self.func.blocks.len() {
 275             let block_idx = BlockIdx::new(block_idx);
 276             let term_idx = self
 277                 .func
 278                 .try_get_block_term_inst_idx(block_idx)
 279                 .expect("known to have block term inst");
 280             let succs_and_params = &mut self.func.insts[term_idx]
 281                 .kind
 282                 .block_term_mut()
 283                 .expect("known to have block term inst")
 284                 .succs_and_params;
 285             if succs_and_params.len() <= 1 {
 286                 continue;
 287             }
 288             if succs_and_params
 289                 .keys()
 290                 .all(|&succ_idx| self.func.blocks[succ_idx].preds.len() <= 1)
 291             {
 292                 continue;
 293             }
 294             // has critical edges -- delete all but first succ to fix that
 295             let mut first = true;
 296             succs_and_params.retain(|&succ_idx, _| {
 297                 if first {
 298                     first = false;
 299                     return true;
 300                 }
 301                 let succ = &mut self.func.blocks[succ_idx];
 302                 succ.preds.remove(&block_idx);
 303                 false
 304             });
 305         }
 306         let dominators = dominators::simple_fast(&self.func, BlockIdx::ENTRY_BLOCK);
 307         for block_idx in 0..self.func.blocks.len() {
 308             let block_idx = BlockIdx::new(block_idx);
 309             self.func.blocks[block_idx].immediate_dominator =
 310                 dominators.immediate_dominator(block_idx);
 311         }
 312         // must have filled dominators first since available_ssa_vals_before_start() needs them
 313         for block_idx in 0..self.func.blocks.len() {
 314             let block_idx = BlockIdx::new(block_idx);
 315             let mut available_ssa_vals = self.available_ssa_vals_before_start(block_idx);
 316             available_ssa_vals.extend(&self.func.ssa_vals, &self.func.blocks[block_idx].params);
 317             for inst_idx in self.func.blocks[block_idx].insts {
 318                 let inst = &mut self.func.insts[inst_idx];
 319                 for (operand_idx, operand) in inst.operands.iter_mut().enumerate() {
 320                     if operand.kind_and_constraint.kind() != OperandKind::Use {
 321                         continue;
 322                     }
 323                     if available_ssa_vals.all.is_empty() {
 324                         // no ssa vals available, change to def
 325                         *operand = Operand {
 326                             kind_and_constraint: KindAndConstraint::Constraint {
 327                                 kind: OperandKind::Def,
 328                                 constraint: Constraint::Any,
 329                             },
 330                             ssa_val: Self::new_ssa_val(
 331                                 &mut self.func.ssa_vals,
 332                                 self.u.arbitrary()?,
 333                                 SSAValDef::Operand {
 334                                     inst: inst_idx,
 335                                     operand_idx,
 336                                 },
 337                             ),
 338                             stage: self.u.arbitrary()?,
 339                         };
 340                     } else {
 341                         operand.ssa_val = *self.u.choose(&available_ssa_vals.all)?;
 342                     }
 343                     self.func.ssa_vals[operand.ssa_val]
 344                         .operand_uses
 345                         .insert(OperandUse {
 346                             inst: inst_idx,
 347                             operand_idx,
 348                         });
 349                 }
 350                 available_ssa_vals.extend(
 351                     &self.func.ssa_vals,
 352                     inst.operands
 353                         .iter()
 354                         .filter(|o| o.kind_and_constraint.kind() == OperandKind::Def)
 355                         .map(|o| o.ssa_val),
 356                 );
 357                 match &mut inst.kind {
 358                     InstKind::Normal => {}
 359                     InstKind::Copy(_) => unreachable!(),
 360                     InstKind::BlockTerm(block_term_inst_kind) => {
 361                         for (&succ_idx, params) in &mut block_term_inst_kind.succs_and_params {
 362                             let succ = &self.func.blocks[succ_idx];
 363                             for (param_idx, &succ_param) in succ.params.iter().enumerate() {
 364                                 let succ_param_ty = self.func.ssa_vals[succ_param].ty;
 365                                 let choices = available_ssa_vals.per_ty(succ_param_ty);
 366                                 let ssa_val_idx;
 367                                 if choices.is_empty() {
 368                                     // no available ssa vals with correct type, fix that by appending def operand with that type
 369                                     ssa_val_idx = Self::new_ssa_val(
 370                                         &mut self.func.ssa_vals,
 371                                         succ_param_ty,
 372                                         SSAValDef::Operand {
 373                                             inst: inst_idx,
 374                                             operand_idx: inst.operands.len(),
 375                                         },
 376                                     );
 377                                     available_ssa_vals.extend(&self.func.ssa_vals, [ssa_val_idx]);
 378                                     self.func.ssa_vals[ssa_val_idx].operand_uses.insert(
 379                                         OperandUse {
 380                                             inst: inst_idx,
 381                                             operand_idx: inst.operands.len(),
 382                                         },
 383                                     );
 384                                     inst.operands.push(Operand {
 385                                         kind_and_constraint: KindAndConstraint::Constraint {
 386                                             kind: OperandKind::Def,
 387                                             constraint: Constraint::Any,
 388                                         },
 389                                         ssa_val: ssa_val_idx,
 390                                         stage: self.u.arbitrary()?,
 391                                     });
 392                                 } else {
 393                                     ssa_val_idx = *self.u.choose(choices)?
 394                                 };
 395                                 params.push(ssa_val_idx);
 396                                 self.func.ssa_vals[ssa_val_idx]
 397                                     .branch_succ_param_uses
 398                                     .insert(BranchSuccParamUse {
 399                                         branch_inst: inst_idx,
 400                                         succ: succ_idx,
 401                                         param_idx,
 402                                     });
 403                             }
 404                         }
 405                     }
 406                 }
 407             }
 408         }
 409         for (inst_idx, inst) in self.func.insts.iter_mut().enumerate() {
 410             let inst_idx = InstIdx::new(inst_idx);
 411             let mut reusable_operand_idxs: HashMap<Ty, Vec<usize>> = HashMap::new();
 412             for (operand_idx, operand) in inst.operands.iter().enumerate() {
 413                 if operand.kind_and_constraint.kind() == OperandKind::Use {
 414                     reusable_operand_idxs
 415                         .entry(self.func.ssa_vals[operand.ssa_val].ty)
 416                         .or_default()
 417                         .push(operand_idx);
 418                 }
 419             }
 420             let mut used_locs = EnumMap::<InstStage, LocSet>::default();
 421             for operand_idx in 0..inst.operands.len() {
 422                 let operand = &inst.operands[operand_idx];
 423                 let operand_ty = self.func.ssa_vals[operand.ssa_val].ty;
 424                 if operand.kind_and_constraint.kind() == OperandKind::Def && self.u.arbitrary()? {
 425                     let reuse_operand_idx = self.u.choose_index(inst.operands.len())?;
 426                     let reuse_operand = &inst.operands[reuse_operand_idx];
 427                     if reuse_operand_idx != operand_idx
 428                         && reuse_operand.kind_and_constraint.kind() == OperandKind::Use
 429                         && self.func.ssa_vals[reuse_operand.ssa_val].ty == operand_ty
 430                     {
 431                         inst.operands[operand_idx].kind_and_constraint = KindAndConstraint::Reuse {
 432                             kind: OperandKindDefOnly,
 433                             reuse_operand_idx,
 434                         };
 435                         continue;
 436                     }
 437                 }
 438                 let operand = &mut inst.operands[operand_idx];
 439                 let KindAndConstraint::Constraint {
 440                     kind,
 441                     ref mut constraint,..
 442                 } = operand.kind_and_constraint else {
 443                     unreachable!();
 444                 };
 445                 *constraint = Constraint::arbitrary_with_ty(operand_ty, self.u)?;
 446                 if let Some(fixed_loc) = constraint.fixed_loc() {
 447                     // is the operand probably live for both stages
 448                     let probably_live_for_both_stages = match (kind, operand.stage) {
 449                         (OperandKind::Use, InstStage::Late) => true, // also probably live for early stage
 450                         (OperandKind::Def, InstStage::Early) => true, // also probably live for late stage
 451                         _ => false,
 452                     };
 453                     let mut conflicts = inst
 454                         .clobbers
 455                         .clone()
 456                         .conflicts_with(fixed_loc, self.global_state);
 457                     if probably_live_for_both_stages {
 458                         for used_locs in used_locs.values() {
 459                             conflicts = conflicts
 460                                 || used_locs
 461                                     .to_interned(self.global_state)
 462                                     .conflicts_with(fixed_loc, self.global_state);
 463                         }
 464                     } else {
 465                         conflicts = conflicts
 466                             || used_locs[operand.stage]
 467                                 .to_interned(self.global_state)
 468                                 .conflicts_with(fixed_loc, self.global_state);
 469                     }
 470                     if conflicts {
 471                         // conflicting constraint, so switch to a safe default instead
 472                         *constraint = Constraint::Any;
 473                     } else if probably_live_for_both_stages {
 474                         for used_locs in used_locs.values_mut() {
 475                             used_locs.insert(fixed_loc);
 476                         }
 477                     } else {
 478                         used_locs[operand.stage].insert(fixed_loc);
 479                     }
 480                 }
 481             }
 482             match inst.kind {
 483                 InstKind::Normal => {
 484                     if self.u.arbitrary()? {
 485                         if let Some(copy_inst_kind) = Self::make_copy_inst_kind(
 486                             self.u,
 487                             &self.func.ssa_vals,
 488                             inst_idx,
 489                             &inst.operands,
 490                         )? {
 491                             inst.kind = InstKind::Copy(copy_inst_kind);
 492                         }
 493                     }
 494                 }
 495                 InstKind::Copy(_) => unreachable!(),
 496                 InstKind::BlockTerm(_) => {}
 497             }
 498         }
 499         Ok(())
 500     }
 501 }
 502
 503 impl<'a> Arbitrary<'a> for FnFields {
 504     fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self, Error> {
 505         GlobalState::get(|global_state| {
 506             let mut builder = FnBuilder {
 507                 global_state,
 508                 u,
 509                 func: Self {
 510                     ssa_vals: Vec::new(),
 511                     insts: Vec::new(),
 512                     blocks: Vec::new(),
 513                     start_inst_to_block_map: Default::default(),
 514                 },
 515                 available_ssa_vals_at_end: Default::default(),
 516             };
 517             builder.run()?;
 518             Ok(builder.func)
 519         })
 520     }
 521 }