1 use crate::config::Config; 2 use crate::cranelift_arbitrary::CraneliftArbitrary; 3 use crate::target_isa_extras::TargetIsaExtras; 4 use anyhow::Result; 5 use arbitrary::{Arbitrary, Unstructured}; 6 use cranelift::codegen::data_value::DataValue; 7 use cranelift::codegen::ir::immediates::Offset32; 8 use cranelift::codegen::ir::instructions::{InstructionFormat, ResolvedConstraint}; 9 use cranelift::codegen::ir::stackslot::StackSize; 10 11 use cranelift::codegen::ir::{ 12 AliasRegion, AtomicRmwOp, Block, BlockArg, ConstantData, Endianness, ExternalName, FuncRef, 13 Function, LibCall, Opcode, SigRef, Signature, StackSlot, UserExternalName, UserFuncName, Value, 14 types::*, 15 }; 16 use cranelift::codegen::isa::CallConv; 17 use cranelift::frontend::{FunctionBuilder, FunctionBuilderContext, Switch, Variable}; 18 use cranelift::prelude::isa::OwnedTargetIsa; 19 use cranelift::prelude::{ 20 ExtFuncData, FloatCC, InstBuilder, IntCC, JumpTableData, MemFlags, StackSlotData, StackSlotKind, 21 }; 22 use std::collections::HashMap; 23 use std::ops::RangeInclusive; 24 use std::str::FromStr; 25 use std::sync::LazyLock; 26 use target_lexicon::{Architecture, Triple}; 27 28 type BlockSignature = Vec<Type>; 29 30 fn insert_opcode( 31 fgen: &mut FunctionGenerator, 32 builder: &mut FunctionBuilder, 33 opcode: Opcode, 34 args: &[Type], 35 rets: &[Type], 36 ) -> Result<()> { 37 let mut vals = Vec::with_capacity(args.len()); 38 for &arg in args.into_iter() { 39 let var = fgen.get_variable_of_type(arg)?; 40 let val = builder.use_var(var); 41 vals.push(val); 42 } 43 44 // Some opcodes require us to look at their input arguments to determine the 45 // controlling type. This is not the general case, but we can neatly check this 46 // using `requires_typevar_operand`. 47 let ctrl_type = if opcode.constraints().requires_typevar_operand() { 48 args.first() 49 } else { 50 rets.first() 51 } 52 .copied() 53 .unwrap_or(INVALID); 54 55 // Choose the appropriate instruction format for this opcode 56 let (inst, dfg) = match opcode.format() { 57 InstructionFormat::NullAry => builder.ins().NullAry(opcode, ctrl_type), 58 InstructionFormat::Unary => builder.ins().Unary(opcode, ctrl_type, vals[0]), 59 InstructionFormat::Binary => builder.ins().Binary(opcode, ctrl_type, vals[0], vals[1]), 60 InstructionFormat::Ternary => builder 61 .ins() 62 .Ternary(opcode, ctrl_type, vals[0], vals[1], vals[2]), 63 _ => unimplemented!(), 64 }; 65 let results = dfg.inst_results(inst).to_vec(); 66 67 for (val, &ty) in results.into_iter().zip(rets) { 68 let var = fgen.get_variable_of_type(ty)?; 69 builder.def_var(var, val); 70 } 71 Ok(()) 72 } 73 74 fn insert_call_to_function( 75 fgen: &mut FunctionGenerator, 76 builder: &mut FunctionBuilder, 77 call_opcode: Opcode, 78 sig: &Signature, 79 sig_ref: SigRef, 80 func_ref: FuncRef, 81 ) -> Result<()> { 82 let actuals = fgen.generate_values_for_signature( 83 builder, 84 sig.params.iter().map(|abi_param| abi_param.value_type), 85 )?; 86 87 let addr_ty = fgen.isa.pointer_type(); 88 let call = match call_opcode { 89 Opcode::Call => builder.ins().call(func_ref, &actuals), 90 Opcode::ReturnCall => builder.ins().return_call(func_ref, &actuals), 91 Opcode::CallIndirect => { 92 let addr = builder.ins().func_addr(addr_ty, func_ref); 93 builder.ins().call_indirect(sig_ref, addr, &actuals) 94 } 95 Opcode::ReturnCallIndirect => { 96 let addr = builder.ins().func_addr(addr_ty, func_ref); 97 builder.ins().return_call_indirect(sig_ref, addr, &actuals) 98 } 99 _ => unreachable!(), 100 }; 101 102 // Assign the return values to random variables 103 let ret_values = builder.inst_results(call).to_vec(); 104 let ret_types = sig.returns.iter().map(|p| p.value_type); 105 for (ty, val) in ret_types.zip(ret_values) { 106 let var = fgen.get_variable_of_type(ty)?; 107 builder.def_var(var, val); 108 } 109 110 Ok(()) 111 } 112 113 fn insert_call( 114 fgen: &mut FunctionGenerator, 115 builder: &mut FunctionBuilder, 116 opcode: Opcode, 117 _args: &[Type], 118 _rets: &[Type], 119 ) -> Result<()> { 120 assert!(matches!( 121 opcode, 122 Opcode::Call | Opcode::CallIndirect | Opcode::PatchableCall 123 )); 124 let (sig, sig_ref, func_ref) = fgen.u.choose(&fgen.resources.func_refs)?.clone(); 125 if opcode == Opcode::PatchableCall && sig.call_conv != CallConv::Patchable { 126 return Err(arbitrary::Error::IncorrectFormat.into()); 127 } 128 129 insert_call_to_function(fgen, builder, opcode, &sig, sig_ref, func_ref) 130 } 131 132 fn insert_stack_load( 133 fgen: &mut FunctionGenerator, 134 builder: &mut FunctionBuilder, 135 _opcode: Opcode, 136 _args: &[Type], 137 rets: &[Type], 138 ) -> Result<()> { 139 let typevar = rets[0]; 140 let type_size = typevar.bytes(); 141 let (slot, slot_size, _align, category) = fgen.stack_slot_with_size(type_size)?; 142 143 // `stack_load` doesn't support setting MemFlags, and it does not set any 144 // alias analysis bits, so we can only emit it for `Other` slots. 145 if category != AACategory::Other { 146 return Err(arbitrary::Error::IncorrectFormat.into()); 147 } 148 149 let offset = fgen.u.int_in_range(0..=(slot_size - type_size))? as i32; 150 151 let val = builder.ins().stack_load(typevar, slot, offset); 152 let var = fgen.get_variable_of_type(typevar)?; 153 builder.def_var(var, val); 154 155 Ok(()) 156 } 157 158 fn insert_stack_store( 159 fgen: &mut FunctionGenerator, 160 builder: &mut FunctionBuilder, 161 _opcode: Opcode, 162 args: &[Type], 163 _rets: &[Type], 164 ) -> Result<()> { 165 let typevar = args[0]; 166 let type_size = typevar.bytes(); 167 168 let (slot, slot_size, _align, category) = fgen.stack_slot_with_size(type_size)?; 169 170 // `stack_store` doesn't support setting MemFlags, and it does not set any 171 // alias analysis bits, so we can only emit it for `Other` slots. 172 if category != AACategory::Other { 173 return Err(arbitrary::Error::IncorrectFormat.into()); 174 } 175 176 let offset = fgen.u.int_in_range(0..=(slot_size - type_size))? as i32; 177 178 let arg0 = fgen.get_variable_of_type(typevar)?; 179 let arg0 = builder.use_var(arg0); 180 181 builder.ins().stack_store(arg0, slot, offset); 182 Ok(()) 183 } 184 185 fn insert_cmp( 186 fgen: &mut FunctionGenerator, 187 builder: &mut FunctionBuilder, 188 opcode: Opcode, 189 args: &[Type], 190 rets: &[Type], 191 ) -> Result<()> { 192 let lhs = fgen.get_variable_of_type(args[0])?; 193 let lhs = builder.use_var(lhs); 194 195 let rhs = fgen.get_variable_of_type(args[1])?; 196 let rhs = builder.use_var(rhs); 197 198 let res = if opcode == Opcode::Fcmp { 199 let cc = *fgen.u.choose(FloatCC::all())?; 200 201 // We filter out condition codes that aren't supported by the target at 202 // this point after randomly choosing one, instead of randomly choosing a 203 // supported one, to avoid invalidating the corpus when these get implemented. 204 let unimplemented_cc = match (fgen.isa.triple().architecture, cc) { 205 // Some FloatCC's are not implemented on AArch64, see: 206 // https://github.com/bytecodealliance/wasmtime/issues/4850 207 (Architecture::Aarch64(_), FloatCC::OrderedNotEqual) => true, 208 (Architecture::Aarch64(_), FloatCC::UnorderedOrEqual) => true, 209 (Architecture::Aarch64(_), FloatCC::UnorderedOrLessThan) => true, 210 (Architecture::Aarch64(_), FloatCC::UnorderedOrLessThanOrEqual) => true, 211 (Architecture::Aarch64(_), FloatCC::UnorderedOrGreaterThan) => true, 212 (Architecture::Aarch64(_), FloatCC::UnorderedOrGreaterThanOrEqual) => true, 213 214 // These are not implemented on x86_64, for vectors. 215 (Architecture::X86_64, FloatCC::UnorderedOrEqual | FloatCC::OrderedNotEqual) => { 216 args[0].is_vector() 217 } 218 _ => false, 219 }; 220 if unimplemented_cc { 221 return Err(arbitrary::Error::IncorrectFormat.into()); 222 } 223 224 builder.ins().fcmp(cc, lhs, rhs) 225 } else { 226 let cc = *fgen.u.choose(IntCC::all())?; 227 builder.ins().icmp(cc, lhs, rhs) 228 }; 229 230 let var = fgen.get_variable_of_type(rets[0])?; 231 builder.def_var(var, res); 232 233 Ok(()) 234 } 235 236 fn insert_const( 237 fgen: &mut FunctionGenerator, 238 builder: &mut FunctionBuilder, 239 _opcode: Opcode, 240 _args: &[Type], 241 rets: &[Type], 242 ) -> Result<()> { 243 let typevar = rets[0]; 244 let var = fgen.get_variable_of_type(typevar)?; 245 let val = fgen.generate_const(builder, typevar)?; 246 builder.def_var(var, val); 247 Ok(()) 248 } 249 250 fn insert_bitcast( 251 fgen: &mut FunctionGenerator, 252 builder: &mut FunctionBuilder, 253 args: &[Type], 254 rets: &[Type], 255 ) -> Result<()> { 256 let from_var = fgen.get_variable_of_type(args[0])?; 257 let from_val = builder.use_var(from_var); 258 259 let to_var = fgen.get_variable_of_type(rets[0])?; 260 261 // TODO: We can generate little/big endian flags here. 262 let mut memflags = MemFlags::new(); 263 264 // When bitcasting between vectors of different lane counts, we need to 265 // specify the endianness. 266 if args[0].lane_count() != rets[0].lane_count() { 267 memflags.set_endianness(Endianness::Little); 268 } 269 270 let res = builder.ins().bitcast(rets[0], memflags, from_val); 271 builder.def_var(to_var, res); 272 Ok(()) 273 } 274 275 fn insert_load_store( 276 fgen: &mut FunctionGenerator, 277 builder: &mut FunctionBuilder, 278 opcode: Opcode, 279 args: &[Type], 280 rets: &[Type], 281 ) -> Result<()> { 282 if opcode == Opcode::Bitcast { 283 return insert_bitcast(fgen, builder, args, rets); 284 } 285 286 let ctrl_type = *rets.first().or(args.first()).unwrap(); 287 let type_size = ctrl_type.bytes(); 288 289 let is_atomic = [Opcode::AtomicLoad, Opcode::AtomicStore].contains(&opcode); 290 let (address, flags, offset) = 291 fgen.generate_address_and_memflags(builder, type_size, is_atomic)?; 292 293 // The variable being loaded or stored into 294 let var = fgen.get_variable_of_type(ctrl_type)?; 295 296 match opcode.format() { 297 InstructionFormat::LoadNoOffset => { 298 let (inst, dfg) = builder 299 .ins() 300 .LoadNoOffset(opcode, ctrl_type, flags, address); 301 302 let new_val = dfg.first_result(inst); 303 builder.def_var(var, new_val); 304 } 305 InstructionFormat::StoreNoOffset => { 306 let val = builder.use_var(var); 307 308 builder 309 .ins() 310 .StoreNoOffset(opcode, ctrl_type, flags, val, address); 311 } 312 InstructionFormat::Store => { 313 let val = builder.use_var(var); 314 315 builder 316 .ins() 317 .Store(opcode, ctrl_type, flags, offset, val, address); 318 } 319 InstructionFormat::Load => { 320 let (inst, dfg) = builder 321 .ins() 322 .Load(opcode, ctrl_type, flags, offset, address); 323 324 let new_val = dfg.first_result(inst); 325 builder.def_var(var, new_val); 326 } 327 _ => unimplemented!(), 328 } 329 330 Ok(()) 331 } 332 333 fn insert_atomic_rmw( 334 fgen: &mut FunctionGenerator, 335 builder: &mut FunctionBuilder, 336 _: Opcode, 337 _: &[Type], 338 rets: &[Type], 339 ) -> Result<()> { 340 let ctrl_type = *rets.first().unwrap(); 341 let type_size = ctrl_type.bytes(); 342 343 let rmw_op = *fgen.u.choose(AtomicRmwOp::all())?; 344 345 let (address, flags, offset) = fgen.generate_address_and_memflags(builder, type_size, true)?; 346 347 // AtomicRMW does not directly support offsets, so add the offset to the address separately. 348 let address = builder.ins().iadd_imm(address, i64::from(offset)); 349 350 // Load and store target variables 351 let source_var = fgen.get_variable_of_type(ctrl_type)?; 352 let target_var = fgen.get_variable_of_type(ctrl_type)?; 353 354 let source_val = builder.use_var(source_var); 355 let new_val = builder 356 .ins() 357 .atomic_rmw(ctrl_type, flags, rmw_op, address, source_val); 358 359 builder.def_var(target_var, new_val); 360 Ok(()) 361 } 362 363 fn insert_atomic_cas( 364 fgen: &mut FunctionGenerator, 365 builder: &mut FunctionBuilder, 366 _: Opcode, 367 _: &[Type], 368 rets: &[Type], 369 ) -> Result<()> { 370 let ctrl_type = *rets.first().unwrap(); 371 let type_size = ctrl_type.bytes(); 372 373 let (address, flags, offset) = fgen.generate_address_and_memflags(builder, type_size, true)?; 374 375 // AtomicCas does not directly support offsets, so add the offset to the address separately. 376 let address = builder.ins().iadd_imm(address, i64::from(offset)); 377 378 // Source and Target variables 379 let expected_var = fgen.get_variable_of_type(ctrl_type)?; 380 let store_var = fgen.get_variable_of_type(ctrl_type)?; 381 let loaded_var = fgen.get_variable_of_type(ctrl_type)?; 382 383 let expected_val = builder.use_var(expected_var); 384 let store_val = builder.use_var(store_var); 385 let new_val = builder 386 .ins() 387 .atomic_cas(flags, address, expected_val, store_val); 388 389 builder.def_var(loaded_var, new_val); 390 Ok(()) 391 } 392 393 fn insert_shuffle( 394 fgen: &mut FunctionGenerator, 395 builder: &mut FunctionBuilder, 396 opcode: Opcode, 397 _: &[Type], 398 rets: &[Type], 399 ) -> Result<()> { 400 let ctrl_type = *rets.first().unwrap(); 401 402 let lhs = builder.use_var(fgen.get_variable_of_type(ctrl_type)?); 403 let rhs = builder.use_var(fgen.get_variable_of_type(ctrl_type)?); 404 405 let mask = { 406 let mut lanes = [0u8; 16]; 407 for lane in lanes.iter_mut() { 408 *lane = fgen.u.int_in_range(0..=31)?; 409 } 410 let lanes = ConstantData::from(lanes.as_ref()); 411 builder.func.dfg.immediates.push(lanes) 412 }; 413 414 // This function is called for any `InstructionFormat::Shuffle`. Which today is just 415 // `shuffle`, but lets assert that, just to be sure we don't accidentally insert 416 // something else. 417 assert_eq!(opcode, Opcode::Shuffle); 418 let res = builder.ins().shuffle(lhs, rhs, mask); 419 420 let target_var = fgen.get_variable_of_type(ctrl_type)?; 421 builder.def_var(target_var, res); 422 423 Ok(()) 424 } 425 426 fn insert_ins_ext_lane( 427 fgen: &mut FunctionGenerator, 428 builder: &mut FunctionBuilder, 429 opcode: Opcode, 430 args: &[Type], 431 rets: &[Type], 432 ) -> Result<()> { 433 let vector_type = *args.first().unwrap(); 434 let ret_type = *rets.first().unwrap(); 435 436 let lhs = builder.use_var(fgen.get_variable_of_type(vector_type)?); 437 let max_lane = (vector_type.lane_count() as u8) - 1; 438 let lane = fgen.u.int_in_range(0..=max_lane)?; 439 440 let res = match opcode { 441 Opcode::Insertlane => { 442 let rhs = builder.use_var(fgen.get_variable_of_type(args[1])?); 443 builder.ins().insertlane(lhs, rhs, lane) 444 } 445 Opcode::Extractlane => builder.ins().extractlane(lhs, lane), 446 _ => todo!(), 447 }; 448 449 let target_var = fgen.get_variable_of_type(ret_type)?; 450 builder.def_var(target_var, res); 451 452 Ok(()) 453 } 454 455 type OpcodeInserter = fn( 456 fgen: &mut FunctionGenerator, 457 builder: &mut FunctionBuilder, 458 Opcode, 459 &[Type], 460 &[Type], 461 ) -> Result<()>; 462 463 macro_rules! exceptions { 464 ($op:expr, $args:expr, $rets:expr, $(($($cases:pat),*)),* $(,)?) => { 465 match ($op, $args, $rets) { 466 $( ($($cases,)* ..) => return false, )* 467 _ => true, 468 } 469 } 470 } 471 472 /// Returns true if we believe this `OpcodeSignature` should compile correctly 473 /// for the given target triple. We currently have a range of known issues 474 /// with specific lowerings on specific backends, and we don't want to get 475 /// fuzz bug reports for those. Over time our goal is to eliminate all of these 476 /// exceptions. 477 fn valid_for_target(triple: &Triple, op: Opcode, args: &[Type], rets: &[Type]) -> bool { 478 // Rule out invalid combinations that we don't yet have a good way of rejecting with the 479 // instruction DSL type constraints. 480 match op { 481 Opcode::FcvtToUintSat | Opcode::FcvtToSintSat => { 482 assert_eq!(args.len(), 1); 483 assert_eq!(rets.len(), 1); 484 485 let arg = args[0]; 486 let ret = rets[0]; 487 488 // Vector arguments must produce vector results, and scalar arguments must produce 489 // scalar results. 490 if arg.is_vector() != ret.is_vector() { 491 return false; 492 } 493 494 if arg.is_vector() && ret.is_vector() { 495 // Vector conversions must have the same number of lanes, and the lanes must be the 496 // same bit-width. 497 if arg.lane_count() != ret.lane_count() { 498 return false; 499 } 500 501 if arg.lane_of().bits() != ret.lane_of().bits() { 502 return false; 503 } 504 } 505 } 506 507 Opcode::Bitcast => { 508 assert_eq!(args.len(), 1); 509 assert_eq!(rets.len(), 1); 510 511 let arg = args[0]; 512 let ret = rets[0]; 513 514 // The opcode generator still allows bitcasts between different sized types, but these 515 // are rejected in the verifier. 516 if arg.bits() != ret.bits() { 517 return false; 518 } 519 } 520 521 // This requires precise runtime integration so it's not supported at 522 // all in fuzzgen just yet. 523 Opcode::StackSwitch => return false, 524 525 _ => {} 526 } 527 528 match triple.architecture { 529 Architecture::X86_64 => { 530 exceptions!( 531 op, 532 args, 533 rets, 534 (Opcode::UmulOverflow | Opcode::SmulOverflow, &[I128, I128]), 535 (Opcode::Imul, &[I8X16, I8X16]), 536 // https://github.com/bytecodealliance/wasmtime/issues/4756 537 (Opcode::Udiv | Opcode::Sdiv, &[I128, I128]), 538 // https://github.com/bytecodealliance/wasmtime/issues/5474 539 (Opcode::Urem | Opcode::Srem, &[I128, I128]), 540 // https://github.com/bytecodealliance/wasmtime/issues/3370 541 ( 542 Opcode::Smin | Opcode::Umin | Opcode::Smax | Opcode::Umax, 543 &[I128, I128] 544 ), 545 // https://github.com/bytecodealliance/wasmtime/issues/5107 546 (Opcode::Cls, &[I8], &[I8]), 547 (Opcode::Cls, &[I16], &[I16]), 548 (Opcode::Cls, &[I32], &[I32]), 549 (Opcode::Cls, &[I64], &[I64]), 550 (Opcode::Cls, &[I128], &[I128]), 551 // TODO 552 (Opcode::Bitselect, &[_, _, _], &[F32 | F64]), 553 // https://github.com/bytecodealliance/wasmtime/issues/4897 554 // https://github.com/bytecodealliance/wasmtime/issues/4899 555 ( 556 Opcode::FcvtToUint 557 | Opcode::FcvtToUintSat 558 | Opcode::FcvtToSint 559 | Opcode::FcvtToSintSat, 560 &[F32 | F64], 561 &[I8 | I16 | I128] 562 ), 563 (Opcode::FcvtToUint | Opcode::FcvtToSint, &[F32X4], &[I32X4]), 564 ( 565 Opcode::FcvtToUint 566 | Opcode::FcvtToUintSat 567 | Opcode::FcvtToSint 568 | Opcode::FcvtToSintSat, 569 &[F64X2], 570 &[I64X2] 571 ), 572 // https://github.com/bytecodealliance/wasmtime/issues/4900 573 (Opcode::FcvtFromUint, &[I128], &[F32 | F64]), 574 // This has a lowering, but only when preceded by `uwiden_low`. 575 (Opcode::FcvtFromUint, &[I64X2], &[F64X2]), 576 // https://github.com/bytecodealliance/wasmtime/issues/4900 577 (Opcode::FcvtFromSint, &[I128], &[F32 | F64]), 578 (Opcode::FcvtFromSint, &[I64X2], &[F64X2]), 579 ( 580 Opcode::Umulhi | Opcode::Smulhi, 581 &([I8X16, I8X16] | [I16X8, I16X8] | [I32X4, I32X4] | [I64X2, I64X2]) 582 ), 583 ( 584 Opcode::UaddSat | Opcode::SaddSat | Opcode::UsubSat | Opcode::SsubSat, 585 &([I32X4, I32X4] | [I64X2, I64X2]) 586 ), 587 (Opcode::Fcopysign, &([F32X4, F32X4] | [F64X2, F64X2])), 588 (Opcode::Popcnt, &([I8X16] | [I16X8] | [I32X4] | [I64X2])), 589 ( 590 Opcode::Umax | Opcode::Smax | Opcode::Umin | Opcode::Smin, 591 &[I64X2, I64X2] 592 ), 593 // https://github.com/bytecodealliance/wasmtime/issues/6104 594 (Opcode::Bitcast, &[I128], &[_]), 595 (Opcode::Bitcast, &[_], &[I128]), 596 (Opcode::Uunarrow), 597 (Opcode::Snarrow | Opcode::Unarrow, &[I64X2, I64X2]), 598 (Opcode::SqmulRoundSat, &[I32X4, I32X4]), 599 // This Icmp is not implemented: #5529 600 (Opcode::Icmp, &[I64X2, I64X2]), 601 // IaddPairwise is implemented, but only for some types, and with some preceding ops. 602 (Opcode::IaddPairwise), 603 // Nothing wrong with this select. But we have an isle rule that can optimize it 604 // into a `min`/`max` instructions, which we don't have implemented yet. 605 (Opcode::Select, &[_, I128, I128]), 606 // These stack accesses can cause segfaults if they are merged into an SSE instruction. 607 // See: #5922 608 ( 609 Opcode::StackStore, 610 &[I8X16 | I16X8 | I32X4 | I64X2 | F32X4 | F64X2] 611 ), 612 ( 613 Opcode::StackLoad, 614 &[], 615 &[I8X16 | I16X8 | I32X4 | I64X2 | F32X4 | F64X2] 616 ), 617 // TODO 618 ( 619 Opcode::Sshr | Opcode::Ushr | Opcode::Ishl, 620 &[I8X16 | I16X8 | I32X4 | I64X2, I128] 621 ), 622 ( 623 Opcode::Rotr | Opcode::Rotl, 624 &[I8X16 | I16X8 | I32X4 | I64X2, _] 625 ), 626 ) 627 } 628 629 Architecture::Aarch64(_) => { 630 exceptions!( 631 op, 632 args, 633 rets, 634 (Opcode::UmulOverflow | Opcode::SmulOverflow, &[I128, I128]), 635 // https://github.com/bytecodealliance/wasmtime/issues/4864 636 (Opcode::Udiv | Opcode::Sdiv, &[I128, I128]), 637 // https://github.com/bytecodealliance/wasmtime/issues/5472 638 (Opcode::Urem | Opcode::Srem, &[I128, I128]), 639 // https://github.com/bytecodealliance/wasmtime/issues/4313 640 ( 641 Opcode::Smin | Opcode::Umin | Opcode::Smax | Opcode::Umax, 642 &[I128, I128] 643 ), 644 // https://github.com/bytecodealliance/wasmtime/issues/4870 645 (Opcode::Bnot, &[F32 | F64]), 646 ( 647 Opcode::Band 648 | Opcode::Bor 649 | Opcode::Bxor 650 | Opcode::BandNot 651 | Opcode::BorNot 652 | Opcode::BxorNot, 653 &([F32, F32] | [F64, F64]) 654 ), 655 // https://github.com/bytecodealliance/wasmtime/issues/5198 656 (Opcode::Bitselect, &[I128, I128, I128]), 657 // https://github.com/bytecodealliance/wasmtime/issues/4934 658 ( 659 Opcode::FcvtToUint 660 | Opcode::FcvtToUintSat 661 | Opcode::FcvtToSint 662 | Opcode::FcvtToSintSat, 663 &[F32 | F64], 664 &[I128] 665 ), 666 // https://github.com/bytecodealliance/wasmtime/issues/4933 667 ( 668 Opcode::FcvtFromUint | Opcode::FcvtFromSint, 669 &[I128], 670 &[F32 | F64] 671 ), 672 ( 673 Opcode::Umulhi | Opcode::Smulhi, 674 &([I8X16, I8X16] | [I16X8, I16X8] | [I32X4, I32X4] | [I64X2, I64X2]) 675 ), 676 (Opcode::Popcnt, &[I16X8 | I32X4 | I64X2]), 677 // Nothing wrong with this select. But we have an isle rule that can optimize it 678 // into a `min`/`max` instructions, which we don't have implemented yet. 679 (Opcode::Select, &[I8, I128, I128]), 680 // https://github.com/bytecodealliance/wasmtime/issues/6104 681 (Opcode::Bitcast, &[I128], &[_]), 682 (Opcode::Bitcast, &[_], &[I128]), 683 // TODO 684 ( 685 Opcode::Sshr | Opcode::Ushr | Opcode::Ishl, 686 &[I8X16 | I16X8 | I32X4 | I64X2, I128] 687 ), 688 ( 689 Opcode::Rotr | Opcode::Rotl, 690 &[I8X16 | I16X8 | I32X4 | I64X2, _] 691 ), 692 // TODO 693 (Opcode::Bitselect, &[_, _, _], &[F32 | F64]), 694 (Opcode::VhighBits, &[F32X4 | F64X2]), 695 ) 696 } 697 698 Architecture::S390x => { 699 exceptions!( 700 op, 701 args, 702 rets, 703 (Opcode::UaddOverflow | Opcode::SaddOverflow), 704 (Opcode::UsubOverflow | Opcode::SsubOverflow), 705 (Opcode::UmulOverflow | Opcode::SmulOverflow), 706 ( 707 Opcode::Udiv | Opcode::Sdiv | Opcode::Urem | Opcode::Srem, 708 &[I128, I128] 709 ), 710 (Opcode::Bnot, &[F32 | F64]), 711 ( 712 Opcode::Band 713 | Opcode::Bor 714 | Opcode::Bxor 715 | Opcode::BandNot 716 | Opcode::BorNot 717 | Opcode::BxorNot, 718 &([F32, F32] | [F64, F64]) 719 ), 720 ( 721 Opcode::FcvtToUint 722 | Opcode::FcvtToUintSat 723 | Opcode::FcvtToSint 724 | Opcode::FcvtToSintSat, 725 &[F32 | F64], 726 &[I128] 727 ), 728 ( 729 Opcode::FcvtFromUint | Opcode::FcvtFromSint, 730 &[I128], 731 &[F32 | F64] 732 ), 733 (Opcode::SsubSat | Opcode::SaddSat, &[I64X2, I64X2]), 734 // https://github.com/bytecodealliance/wasmtime/issues/6104 735 (Opcode::Bitcast, &[I128], &[_]), 736 (Opcode::Bitcast, &[_], &[I128]), 737 // TODO 738 (Opcode::Bitselect, &[_, _, _], &[F32 | F64]), 739 ) 740 } 741 742 Architecture::Riscv64(_) => { 743 exceptions!( 744 op, 745 args, 746 rets, 747 // TODO 748 (Opcode::UaddOverflow | Opcode::SaddOverflow), 749 (Opcode::UsubOverflow | Opcode::SsubOverflow), 750 (Opcode::UmulOverflow | Opcode::SmulOverflow), 751 // TODO 752 ( 753 Opcode::Udiv | Opcode::Sdiv | Opcode::Urem | Opcode::Srem, 754 &[I128, I128] 755 ), 756 // TODO 757 (Opcode::Iabs, &[I128]), 758 // TODO 759 (Opcode::Bitselect, &[I128, I128, I128]), 760 // https://github.com/bytecodealliance/wasmtime/issues/5528 761 ( 762 Opcode::FcvtToUint | Opcode::FcvtToSint, 763 [F32 | F64], 764 &[I128] 765 ), 766 ( 767 Opcode::FcvtToUintSat | Opcode::FcvtToSintSat, 768 &[F32 | F64], 769 &[I128] 770 ), 771 // https://github.com/bytecodealliance/wasmtime/issues/5528 772 ( 773 Opcode::FcvtFromUint | Opcode::FcvtFromSint, 774 &[I128], 775 &[F32 | F64] 776 ), 777 // TODO 778 ( 779 Opcode::SelectSpectreGuard, 780 &[_, _, _], 781 &[F32 | F64 | I8X16 | I16X8 | I32X4 | I64X2 | F64X2 | F32X4] 782 ), 783 // TODO 784 (Opcode::Bitselect, &[_, _, _], &[F32 | F64]), 785 ( 786 Opcode::Rotr | Opcode::Rotl, 787 &[I8X16 | I16X8 | I32X4 | I64X2, _] 788 ), 789 ) 790 } 791 792 _ => true, 793 } 794 } 795 796 type OpcodeSignature = (Opcode, Vec<Type>, Vec<Type>); 797 798 static OPCODE_SIGNATURES: LazyLock<Vec<OpcodeSignature>> = LazyLock::new(|| { 799 let types = &[ 800 I8, I16, I32, I64, I128, // Scalar Integers 801 F32, F64, // Scalar Floats 802 I8X16, I16X8, I32X4, I64X2, // SIMD Integers 803 F32X4, F64X2, // SIMD Floats 804 ]; 805 806 // When this env variable is passed, we only generate instructions for the opcodes listed in 807 // the comma-separated list. This is useful for debugging, as it allows us to focus on a few 808 // specific opcodes. 809 let allowed_opcodes = std::env::var("FUZZGEN_ALLOWED_OPS").ok().map(|s| { 810 s.split(',') 811 .map(|s| s.trim()) 812 .filter(|s| !s.is_empty()) 813 .map(|s| Opcode::from_str(s).expect("Unrecoginzed opcode")) 814 .collect::<Vec<_>>() 815 }); 816 817 Opcode::all() 818 .iter() 819 .filter(|op| { 820 match op { 821 // Control flow opcodes should not be generated through `generate_instructions`. 822 Opcode::BrTable 823 | Opcode::Brif 824 | Opcode::Jump 825 | Opcode::Return 826 | Opcode::ReturnCall 827 | Opcode::ReturnCallIndirect 828 | Opcode::TryCall 829 | Opcode::TryCallIndirect => false, 830 831 // Constants are generated outside of `generate_instructions` 832 Opcode::Iconst => false, 833 834 // TODO: extract_vector raises exceptions during return type generation because it 835 // uses dynamic vectors. 836 Opcode::ExtractVector => false, 837 838 _ => true, 839 } 840 }) 841 .flat_map(|op| { 842 let constraints = op.constraints(); 843 844 let ctrl_types = if let Some(ctrls) = constraints.ctrl_typeset() { 845 Vec::from_iter(types.iter().copied().filter(|ty| ctrls.contains(*ty))) 846 } else { 847 vec![INVALID] 848 }; 849 850 ctrl_types.into_iter().flat_map(move |ctrl_type| { 851 let rets = Vec::from_iter( 852 (0..constraints.num_fixed_results()) 853 .map(|i| constraints.result_type(i, ctrl_type)), 854 ); 855 856 // Cols is a vector whose length will match `num_fixed_value_arguments`, and whose 857 // elements will be vectors of types that are valid for that fixed argument 858 // position. 859 let mut cols = vec![]; 860 861 for i in 0..constraints.num_fixed_value_arguments() { 862 match constraints.value_argument_constraint(i, ctrl_type) { 863 ResolvedConstraint::Bound(ty) => cols.push(Vec::from([ty])), 864 ResolvedConstraint::Free(tys) => cols.push(Vec::from_iter( 865 types.iter().copied().filter(|ty| tys.contains(*ty)), 866 )), 867 } 868 } 869 870 // Generate the cartesian product of cols to produce a vector of argument lists, 871 // argss. The argss vector is seeded with the empty argument list, so there's an 872 // initial value to be extended in the loop below. 873 let mut argss = vec![vec![]]; 874 let mut cols = cols.as_slice(); 875 while let Some((col, rest)) = cols.split_last() { 876 cols = rest; 877 878 let mut next = vec![]; 879 for current in argss.iter() { 880 // Extend the front of each argument candidate with every type in `col`. 881 for ty in col { 882 let mut args = vec![*ty]; 883 args.extend_from_slice(¤t); 884 next.push(args); 885 } 886 } 887 888 let _ = std::mem::replace(&mut argss, next); 889 } 890 891 argss.into_iter().map(move |args| (*op, args, rets.clone())) 892 }) 893 }) 894 .filter(|(op, args, rets)| { 895 // These op/signature combinations need to be vetted 896 exceptions!( 897 op, 898 args.as_slice(), 899 rets.as_slice(), 900 (Opcode::Debugtrap), 901 (Opcode::Trap), 902 (Opcode::Trapz), 903 (Opcode::Trapnz), 904 (Opcode::CallIndirect, &[I32]), 905 (Opcode::FuncAddr), 906 (Opcode::X86Pshufb), 907 (Opcode::AvgRound), 908 (Opcode::Uload8x8), 909 (Opcode::Sload8x8), 910 (Opcode::Uload16x4), 911 (Opcode::Sload16x4), 912 (Opcode::Uload32x2), 913 (Opcode::Sload32x2), 914 (Opcode::StackAddr), 915 (Opcode::DynamicStackLoad), 916 (Opcode::DynamicStackStore), 917 (Opcode::DynamicStackAddr), 918 (Opcode::GlobalValue), 919 (Opcode::SymbolValue), 920 (Opcode::TlsValue), 921 (Opcode::GetPinnedReg), 922 (Opcode::SetPinnedReg), 923 (Opcode::GetFramePointer), 924 (Opcode::GetStackPointer), 925 (Opcode::GetReturnAddress), 926 (Opcode::X86Blendv), 927 (Opcode::IcmpImm), 928 (Opcode::X86Pmulhrsw), 929 (Opcode::IaddImm), 930 (Opcode::ImulImm), 931 (Opcode::UdivImm), 932 (Opcode::SdivImm), 933 (Opcode::UremImm), 934 (Opcode::SremImm), 935 (Opcode::IrsubImm), 936 (Opcode::UaddOverflowCin), 937 (Opcode::SaddOverflowCin), 938 (Opcode::UaddOverflowTrap), 939 (Opcode::UsubOverflowBin), 940 (Opcode::SsubOverflowBin), 941 (Opcode::BandImm), 942 (Opcode::BorImm), 943 (Opcode::BxorImm), 944 (Opcode::RotlImm), 945 (Opcode::RotrImm), 946 (Opcode::IshlImm), 947 (Opcode::UshrImm), 948 (Opcode::SshrImm), 949 (Opcode::ScalarToVector), 950 (Opcode::X86Pmaddubsw), 951 (Opcode::X86Cvtt2dq), 952 (Opcode::Umulhi, &[I128, I128], &[I128]), 953 (Opcode::Smulhi, &[I128, I128], &[I128]), 954 // https://github.com/bytecodealliance/wasmtime/issues/6073 955 (Opcode::Iconcat, &[I32, I32], &[I64]), 956 (Opcode::Iconcat, &[I16, I16], &[I32]), 957 (Opcode::Iconcat, &[I8, I8], &[I16]), 958 // https://github.com/bytecodealliance/wasmtime/issues/6073 959 (Opcode::Isplit, &[I64], &[I32, I32]), 960 (Opcode::Isplit, &[I32], &[I16, I16]), 961 (Opcode::Isplit, &[I16], &[I8, I8]), 962 (Opcode::Fmin, &[F32X4, F32X4], &[F32X4]), 963 (Opcode::Fmin, &[F64X2, F64X2], &[F64X2]), 964 (Opcode::Fmax, &[F32X4, F32X4], &[F32X4]), 965 (Opcode::Fmax, &[F64X2, F64X2], &[F64X2]), 966 (Opcode::FcvtToUintSat, &[F32X4], &[I8]), 967 (Opcode::FcvtToUintSat, &[F64X2], &[I8]), 968 (Opcode::FcvtToUintSat, &[F32X4], &[I16]), 969 (Opcode::FcvtToUintSat, &[F64X2], &[I16]), 970 (Opcode::FcvtToUintSat, &[F32X4], &[I32]), 971 (Opcode::FcvtToUintSat, &[F64X2], &[I32]), 972 (Opcode::FcvtToUintSat, &[F32X4], &[I64]), 973 (Opcode::FcvtToUintSat, &[F64X2], &[I64]), 974 (Opcode::FcvtToUintSat, &[F32X4], &[I128]), 975 (Opcode::FcvtToUintSat, &[F64X2], &[I128]), 976 (Opcode::FcvtToUintSat, &[F32], &[I8X16]), 977 (Opcode::FcvtToUintSat, &[F64], &[I8X16]), 978 (Opcode::FcvtToUintSat, &[F32X4], &[I8X16]), 979 (Opcode::FcvtToUintSat, &[F64X2], &[I8X16]), 980 (Opcode::FcvtToUintSat, &[F32], &[I16X8]), 981 (Opcode::FcvtToUintSat, &[F64], &[I16X8]), 982 (Opcode::FcvtToUintSat, &[F32X4], &[I16X8]), 983 (Opcode::FcvtToUintSat, &[F64X2], &[I16X8]), 984 (Opcode::FcvtToUintSat, &[F32], &[I32X4]), 985 (Opcode::FcvtToUintSat, &[F64], &[I32X4]), 986 (Opcode::FcvtToUintSat, &[F64X2], &[I32X4]), 987 (Opcode::FcvtToUintSat, &[F32], &[I64X2]), 988 (Opcode::FcvtToUintSat, &[F64], &[I64X2]), 989 (Opcode::FcvtToUintSat, &[F32X4], &[I64X2]), 990 (Opcode::FcvtToSintSat, &[F32X4], &[I8]), 991 (Opcode::FcvtToSintSat, &[F64X2], &[I8]), 992 (Opcode::FcvtToSintSat, &[F32X4], &[I16]), 993 (Opcode::FcvtToSintSat, &[F64X2], &[I16]), 994 (Opcode::FcvtToSintSat, &[F32X4], &[I32]), 995 (Opcode::FcvtToSintSat, &[F64X2], &[I32]), 996 (Opcode::FcvtToSintSat, &[F32X4], &[I64]), 997 (Opcode::FcvtToSintSat, &[F64X2], &[I64]), 998 (Opcode::FcvtToSintSat, &[F32X4], &[I128]), 999 (Opcode::FcvtToSintSat, &[F64X2], &[I128]), 1000 (Opcode::FcvtToSintSat, &[F32], &[I8X16]), 1001 (Opcode::FcvtToSintSat, &[F64], &[I8X16]), 1002 (Opcode::FcvtToSintSat, &[F32X4], &[I8X16]), 1003 (Opcode::FcvtToSintSat, &[F64X2], &[I8X16]), 1004 (Opcode::FcvtToSintSat, &[F32], &[I16X8]), 1005 (Opcode::FcvtToSintSat, &[F64], &[I16X8]), 1006 (Opcode::FcvtToSintSat, &[F32X4], &[I16X8]), 1007 (Opcode::FcvtToSintSat, &[F64X2], &[I16X8]), 1008 (Opcode::FcvtToSintSat, &[F32], &[I32X4]), 1009 (Opcode::FcvtToSintSat, &[F64], &[I32X4]), 1010 (Opcode::FcvtToSintSat, &[F64X2], &[I32X4]), 1011 (Opcode::FcvtToSintSat, &[F32], &[I64X2]), 1012 (Opcode::FcvtToSintSat, &[F64], &[I64X2]), 1013 (Opcode::FcvtToSintSat, &[F32X4], &[I64X2]), 1014 (Opcode::FcvtFromUint, &[I8X16], &[F32]), 1015 (Opcode::FcvtFromUint, &[I16X8], &[F32]), 1016 (Opcode::FcvtFromUint, &[I32X4], &[F32]), 1017 (Opcode::FcvtFromUint, &[I64X2], &[F32]), 1018 (Opcode::FcvtFromUint, &[I8X16], &[F64]), 1019 (Opcode::FcvtFromUint, &[I16X8], &[F64]), 1020 (Opcode::FcvtFromUint, &[I32X4], &[F64]), 1021 (Opcode::FcvtFromUint, &[I64X2], &[F64]), 1022 (Opcode::FcvtFromUint, &[I8], &[F32X4]), 1023 (Opcode::FcvtFromUint, &[I16], &[F32X4]), 1024 (Opcode::FcvtFromUint, &[I32], &[F32X4]), 1025 (Opcode::FcvtFromUint, &[I64], &[F32X4]), 1026 (Opcode::FcvtFromUint, &[I128], &[F32X4]), 1027 (Opcode::FcvtFromUint, &[I8X16], &[F32X4]), 1028 (Opcode::FcvtFromUint, &[I16X8], &[F32X4]), 1029 (Opcode::FcvtFromUint, &[I64X2], &[F32X4]), 1030 (Opcode::FcvtFromUint, &[I8], &[F64X2]), 1031 (Opcode::FcvtFromUint, &[I16], &[F64X2]), 1032 (Opcode::FcvtFromUint, &[I32], &[F64X2]), 1033 (Opcode::FcvtFromUint, &[I64], &[F64X2]), 1034 (Opcode::FcvtFromUint, &[I128], &[F64X2]), 1035 (Opcode::FcvtFromUint, &[I8X16], &[F64X2]), 1036 (Opcode::FcvtFromUint, &[I16X8], &[F64X2]), 1037 (Opcode::FcvtFromUint, &[I32X4], &[F64X2]), 1038 (Opcode::FcvtFromSint, &[I8X16], &[F32]), 1039 (Opcode::FcvtFromSint, &[I16X8], &[F32]), 1040 (Opcode::FcvtFromSint, &[I32X4], &[F32]), 1041 (Opcode::FcvtFromSint, &[I64X2], &[F32]), 1042 (Opcode::FcvtFromSint, &[I8X16], &[F64]), 1043 (Opcode::FcvtFromSint, &[I16X8], &[F64]), 1044 (Opcode::FcvtFromSint, &[I32X4], &[F64]), 1045 (Opcode::FcvtFromSint, &[I64X2], &[F64]), 1046 (Opcode::FcvtFromSint, &[I8], &[F32X4]), 1047 (Opcode::FcvtFromSint, &[I16], &[F32X4]), 1048 (Opcode::FcvtFromSint, &[I32], &[F32X4]), 1049 (Opcode::FcvtFromSint, &[I64], &[F32X4]), 1050 (Opcode::FcvtFromSint, &[I128], &[F32X4]), 1051 (Opcode::FcvtFromSint, &[I8X16], &[F32X4]), 1052 (Opcode::FcvtFromSint, &[I16X8], &[F32X4]), 1053 (Opcode::FcvtFromSint, &[I64X2], &[F32X4]), 1054 (Opcode::FcvtFromSint, &[I8], &[F64X2]), 1055 (Opcode::FcvtFromSint, &[I16], &[F64X2]), 1056 (Opcode::FcvtFromSint, &[I32], &[F64X2]), 1057 (Opcode::FcvtFromSint, &[I64], &[F64X2]), 1058 (Opcode::FcvtFromSint, &[I128], &[F64X2]), 1059 (Opcode::FcvtFromSint, &[I8X16], &[F64X2]), 1060 (Opcode::FcvtFromSint, &[I16X8], &[F64X2]), 1061 (Opcode::FcvtFromSint, &[I32X4], &[F64X2]), 1062 // Only supported on x64 with a feature at this time, so 128-bit 1063 // atomics are not suitable to fuzz yet. 1064 (Opcode::AtomicRmw, _, &[I128]), 1065 (Opcode::AtomicCas, _, &[I128]), 1066 (Opcode::AtomicLoad, _, &[I128]), 1067 (Opcode::AtomicStore, &[I128, _], _), 1068 (Opcode::SequencePoint), 1069 ) 1070 }) 1071 .filter(|(op, ..)| { 1072 allowed_opcodes 1073 .as_ref() 1074 .map_or(true, |opcodes| opcodes.contains(op)) 1075 }) 1076 .collect() 1077 }); 1078 1079 fn inserter_for_format(fmt: InstructionFormat) -> OpcodeInserter { 1080 match fmt { 1081 InstructionFormat::AtomicCas => insert_atomic_cas, 1082 InstructionFormat::AtomicRmw => insert_atomic_rmw, 1083 InstructionFormat::Binary => insert_opcode, 1084 InstructionFormat::BinaryImm64 => todo!(), 1085 InstructionFormat::BinaryImm8 => insert_ins_ext_lane, 1086 InstructionFormat::Call => insert_call, 1087 InstructionFormat::CallIndirect => insert_call, 1088 InstructionFormat::CondTrap => todo!(), 1089 InstructionFormat::DynamicStackLoad => todo!(), 1090 InstructionFormat::DynamicStackStore => todo!(), 1091 InstructionFormat::FloatCompare => insert_cmp, 1092 InstructionFormat::FuncAddr => todo!(), 1093 InstructionFormat::IntAddTrap => todo!(), 1094 InstructionFormat::IntCompare => insert_cmp, 1095 InstructionFormat::IntCompareImm => todo!(), 1096 InstructionFormat::Load => insert_load_store, 1097 InstructionFormat::LoadNoOffset => insert_load_store, 1098 InstructionFormat::NullAry => insert_opcode, 1099 InstructionFormat::Shuffle => insert_shuffle, 1100 InstructionFormat::StackLoad => insert_stack_load, 1101 InstructionFormat::StackStore => insert_stack_store, 1102 InstructionFormat::Store => insert_load_store, 1103 InstructionFormat::StoreNoOffset => insert_load_store, 1104 InstructionFormat::Ternary => insert_opcode, 1105 InstructionFormat::TernaryImm8 => insert_ins_ext_lane, 1106 InstructionFormat::Trap => todo!(), 1107 InstructionFormat::Unary => insert_opcode, 1108 InstructionFormat::UnaryConst => insert_const, 1109 InstructionFormat::UnaryGlobalValue => todo!(), 1110 InstructionFormat::UnaryIeee16 => insert_const, 1111 InstructionFormat::UnaryIeee32 => insert_const, 1112 InstructionFormat::UnaryIeee64 => insert_const, 1113 InstructionFormat::UnaryImm => insert_const, 1114 InstructionFormat::ExceptionHandlerAddress => insert_const, 1115 1116 InstructionFormat::BranchTable 1117 | InstructionFormat::Brif 1118 | InstructionFormat::Jump 1119 | InstructionFormat::MultiAry 1120 | InstructionFormat::TryCall 1121 | InstructionFormat::TryCallIndirect => { 1122 panic!("Control-flow instructions should be handled by 'insert_terminator': {fmt:?}") 1123 } 1124 } 1125 } 1126 1127 pub struct FunctionGenerator<'r, 'data> 1128 where 1129 'data: 'r, 1130 { 1131 u: &'r mut Unstructured<'data>, 1132 config: &'r Config, 1133 resources: Resources, 1134 isa: OwnedTargetIsa, 1135 name: UserFuncName, 1136 signature: Signature, 1137 } 1138 1139 #[derive(Debug, Clone)] 1140 enum BlockTerminator { 1141 Return, 1142 Jump(Block), 1143 Br(Block, Block), 1144 BrTable(Block, Vec<Block>), 1145 Switch(Type, Block, HashMap<u128, Block>), 1146 TailCall(FuncRef), 1147 TailCallIndirect(FuncRef), 1148 } 1149 1150 #[derive(Debug, Clone)] 1151 enum BlockTerminatorKind { 1152 Return, 1153 Jump, 1154 Br, 1155 BrTable, 1156 Switch, 1157 TailCall, 1158 TailCallIndirect, 1159 } 1160 1161 /// Alias Analysis Category 1162 /// 1163 /// Our alias analysis pass supports 4 categories of accesses to distinguish 1164 /// different regions. The "Other" region is the general case, and is the default 1165 /// Although they have highly suggestive names there is no difference between any 1166 /// of the categories. 1167 /// 1168 /// We assign each stack slot a category when we first generate them, and then 1169 /// ensure that all accesses to that stack slot are correctly tagged. We already 1170 /// ensure that memory accesses never cross stack slots, so there is no risk 1171 /// of a memory access being tagged with the wrong category. 1172 #[derive(Debug, PartialEq, Clone, Copy)] 1173 enum AACategory { 1174 Other, 1175 Heap, 1176 Table, 1177 VmCtx, 1178 } 1179 1180 impl AACategory { 1181 pub fn all() -> &'static [Self] { 1182 &[ 1183 AACategory::Other, 1184 AACategory::Heap, 1185 AACategory::Table, 1186 AACategory::VmCtx, 1187 ] 1188 } 1189 1190 pub fn update_memflags(&self, flags: &mut MemFlags) { 1191 flags.set_alias_region(match self { 1192 AACategory::Other => None, 1193 AACategory::Heap => Some(AliasRegion::Heap), 1194 AACategory::Table => Some(AliasRegion::Table), 1195 AACategory::VmCtx => Some(AliasRegion::Vmctx), 1196 }) 1197 } 1198 } 1199 1200 pub type StackAlignment = StackSize; 1201 1202 #[derive(Default)] 1203 struct Resources { 1204 vars: HashMap<Type, Vec<Variable>>, 1205 blocks: Vec<(Block, BlockSignature)>, 1206 blocks_without_params: Vec<Block>, 1207 block_terminators: Vec<BlockTerminator>, 1208 func_refs: Vec<(Signature, SigRef, FuncRef)>, 1209 /// This field is required to be sorted by stack slot size at all times. 1210 /// We use this invariant when searching for stack slots with a given size. 1211 /// See [FunctionGenerator::stack_slot_with_size] 1212 stack_slots: Vec<(StackSlot, StackSize, StackAlignment, AACategory)>, 1213 usercalls: Vec<(UserExternalName, Signature)>, 1214 libcalls: Vec<LibCall>, 1215 } 1216 1217 impl Resources { 1218 /// Partitions blocks at `block`. Only blocks that can be targeted by branches are considered. 1219 /// 1220 /// The first slice includes all blocks up to and including `block`. 1221 /// The second slice includes all remaining blocks. 1222 fn partition_target_blocks( 1223 &self, 1224 block: Block, 1225 ) -> (&[(Block, BlockSignature)], &[(Block, BlockSignature)]) { 1226 // Blocks are stored in-order and have no gaps, this means that we can simply index them by 1227 // their number. We also need to exclude the entry block since it isn't a valid target. 1228 let target_blocks = &self.blocks[1..]; 1229 target_blocks.split_at(block.as_u32() as usize) 1230 } 1231 1232 /// Returns blocks forward of `block`. Only blocks that can be targeted by branches are considered. 1233 fn forward_blocks(&self, block: Block) -> &[(Block, BlockSignature)] { 1234 let (_, forward_blocks) = self.partition_target_blocks(block); 1235 forward_blocks 1236 } 1237 1238 /// Generates a slice of `blocks_without_params` ahead of `block` 1239 fn forward_blocks_without_params(&self, block: Block) -> &[Block] { 1240 let partition_point = self.blocks_without_params.partition_point(|b| *b <= block); 1241 &self.blocks_without_params[partition_point..] 1242 } 1243 1244 /// Generates an iterator of all valid tail call targets. This includes all functions with both 1245 /// the `tail` calling convention and the same return values as the caller. 1246 fn tail_call_targets<'a>( 1247 &'a self, 1248 caller_sig: &'a Signature, 1249 ) -> impl Iterator<Item = &'a (Signature, SigRef, FuncRef)> { 1250 self.func_refs.iter().filter(|(sig, _, _)| { 1251 sig.call_conv == CallConv::Tail && sig.returns == caller_sig.returns 1252 }) 1253 } 1254 } 1255 1256 impl<'r, 'data> FunctionGenerator<'r, 'data> 1257 where 1258 'data: 'r, 1259 { 1260 pub fn new( 1261 u: &'r mut Unstructured<'data>, 1262 config: &'r Config, 1263 isa: OwnedTargetIsa, 1264 name: UserFuncName, 1265 signature: Signature, 1266 usercalls: Vec<(UserExternalName, Signature)>, 1267 libcalls: Vec<LibCall>, 1268 ) -> Self { 1269 Self { 1270 u, 1271 config, 1272 resources: Resources { 1273 usercalls, 1274 libcalls, 1275 ..Resources::default() 1276 }, 1277 isa, 1278 name, 1279 signature, 1280 } 1281 } 1282 1283 /// Generates a random value for config `param` 1284 fn param(&mut self, param: &RangeInclusive<usize>) -> Result<usize> { 1285 Ok(self.u.int_in_range(param.clone())?) 1286 } 1287 1288 fn system_callconv(&mut self) -> CallConv { 1289 // TODO: This currently only runs on linux, so this is the only choice 1290 // We should improve this once we generate flags and targets 1291 CallConv::SystemV 1292 } 1293 1294 /// Finds a stack slot with size of at least n bytes 1295 fn stack_slot_with_size( 1296 &mut self, 1297 n: u32, 1298 ) -> Result<(StackSlot, StackSize, StackAlignment, AACategory)> { 1299 let first = self 1300 .resources 1301 .stack_slots 1302 .partition_point(|&(_slot, size, _align, _category)| size < n); 1303 Ok(*self.u.choose(&self.resources.stack_slots[first..])?) 1304 } 1305 1306 /// Generates an address that should allow for a store or a load. 1307 /// 1308 /// Addresses aren't generated like other values. They are never stored in variables so that 1309 /// we don't run the risk of returning them from a function, which would make the fuzzer 1310 /// complain since they are different from the interpreter to the backend. 1311 /// 1312 /// `min_size`: Controls the amount of space that the address should have. 1313 /// 1314 /// `aligned`: When passed as true, the resulting address is guaranteed to be aligned 1315 /// on an 8 byte boundary. 1316 /// 1317 /// Returns a valid address and the maximum possible offset that still respects `min_size`. 1318 fn generate_load_store_address( 1319 &mut self, 1320 builder: &mut FunctionBuilder, 1321 min_size: u32, 1322 aligned: bool, 1323 ) -> Result<(Value, u32, AACategory)> { 1324 // TODO: Currently our only source of addresses is stack_addr, but we 1325 // should add global_value, symbol_value eventually 1326 let (addr, available_size, category) = { 1327 let (ss, slot_size, _align, category) = self.stack_slot_with_size(min_size)?; 1328 1329 // stack_slot_with_size guarantees that slot_size >= min_size 1330 let max_offset = slot_size - min_size; 1331 let offset = if aligned { 1332 self.u.int_in_range(0..=max_offset / min_size)? * min_size 1333 } else { 1334 self.u.int_in_range(0..=max_offset)? 1335 }; 1336 1337 let base_addr = builder.ins().stack_addr(I64, ss, offset as i32); 1338 let available_size = slot_size.saturating_sub(offset); 1339 (base_addr, available_size, category) 1340 }; 1341 1342 // TODO: Insert a bunch of amode opcodes here to modify the address! 1343 1344 // Now that we have an address and a size, we just choose a random offset to return to the 1345 // caller. Preserving min_size bytes. 1346 let max_offset = available_size.saturating_sub(min_size); 1347 Ok((addr, max_offset, category)) 1348 } 1349 1350 // Generates an address and memflags for a load or store. 1351 fn generate_address_and_memflags( 1352 &mut self, 1353 builder: &mut FunctionBuilder, 1354 min_size: u32, 1355 is_atomic: bool, 1356 ) -> Result<(Value, MemFlags, Offset32)> { 1357 // Should we generate an aligned address 1358 // Some backends have issues with unaligned atomics. 1359 // AArch64: https://github.com/bytecodealliance/wasmtime/issues/5483 1360 // RISCV: https://github.com/bytecodealliance/wasmtime/issues/5882 1361 let requires_aligned_atomics = matches!( 1362 self.isa.triple().architecture, 1363 Architecture::Aarch64(_) | Architecture::Riscv64(_) 1364 ); 1365 let aligned = if is_atomic && requires_aligned_atomics { 1366 true 1367 } else if min_size > 8 { 1368 // TODO: We currently can't guarantee that a stack_slot will be aligned on a 16 byte 1369 // boundary. We don't have a way to specify alignment when creating stack slots, and 1370 // cranelift only guarantees 8 byte alignment between stack slots. 1371 // See: https://github.com/bytecodealliance/wasmtime/issues/5922#issuecomment-1457926624 1372 false 1373 } else { 1374 bool::arbitrary(self.u)? 1375 }; 1376 1377 let mut flags = MemFlags::new(); 1378 // Even if we picked an aligned address, we can always generate unaligned memflags 1379 if aligned && bool::arbitrary(self.u)? { 1380 flags.set_aligned(); 1381 } 1382 // If the address is aligned, then we know it won't trap 1383 if aligned && bool::arbitrary(self.u)? { 1384 flags.set_notrap(); 1385 } 1386 1387 let (address, max_offset, category) = 1388 self.generate_load_store_address(builder, min_size, aligned)?; 1389 1390 // Set the Alias Analysis bits on the memflags 1391 category.update_memflags(&mut flags); 1392 1393 // Pick an offset to pass into the load/store. 1394 let offset = if aligned { 1395 0 1396 } else { 1397 self.u.int_in_range(0..=max_offset)? as i32 1398 } 1399 .into(); 1400 1401 Ok((address, flags, offset)) 1402 } 1403 1404 /// Get a variable of type `ty` from the current function 1405 fn get_variable_of_type(&mut self, ty: Type) -> Result<Variable> { 1406 let opts = self.resources.vars.get(&ty).map_or(&[][..], Vec::as_slice); 1407 let var = self.u.choose(opts)?; 1408 Ok(*var) 1409 } 1410 1411 /// Generates an instruction(`iconst`/`fconst`/etc...) to introduce a constant value 1412 fn generate_const(&mut self, builder: &mut FunctionBuilder, ty: Type) -> Result<Value> { 1413 Ok(match self.u.datavalue(ty)? { 1414 DataValue::I8(i) => builder.ins().iconst(ty, i as u8 as i64), 1415 DataValue::I16(i) => builder.ins().iconst(ty, i as u16 as i64), 1416 DataValue::I32(i) => builder.ins().iconst(ty, i as u32 as i64), 1417 DataValue::I64(i) => builder.ins().iconst(ty, i), 1418 DataValue::I128(i) => { 1419 let hi = builder.ins().iconst(I64, (i >> 64) as i64); 1420 let lo = builder.ins().iconst(I64, i as i64); 1421 builder.ins().iconcat(lo, hi) 1422 } 1423 DataValue::F16(f) => builder.ins().f16const(f), 1424 DataValue::F32(f) => builder.ins().f32const(f), 1425 DataValue::F64(f) => builder.ins().f64const(f), 1426 DataValue::F128(f) => { 1427 let handle = builder.func.dfg.constants.insert(f.into()); 1428 builder.ins().f128const(handle) 1429 } 1430 DataValue::V128(bytes) => { 1431 let data = bytes.to_vec().into(); 1432 let handle = builder.func.dfg.constants.insert(data); 1433 builder.ins().vconst(ty, handle) 1434 } 1435 _ => unimplemented!(), 1436 }) 1437 } 1438 1439 /// Chooses a random block which can be targeted by a jump / branch. 1440 /// This means any block that is not the first block. 1441 fn generate_target_block(&mut self, source_block: Block) -> Result<Block> { 1442 // We try to mostly generate forward branches to avoid generating an excessive amount of 1443 // infinite loops. But they are still important, so give them a small chance of existing. 1444 let (backwards_blocks, forward_blocks) = 1445 self.resources.partition_target_blocks(source_block); 1446 let ratio = self.config.backwards_branch_ratio; 1447 let block_targets = if !backwards_blocks.is_empty() && self.u.ratio(ratio.0, ratio.1)? { 1448 backwards_blocks 1449 } else { 1450 forward_blocks 1451 }; 1452 assert!(!block_targets.is_empty()); 1453 1454 let (block, _) = self.u.choose(block_targets)?.clone(); 1455 Ok(block) 1456 } 1457 1458 fn generate_values_for_block( 1459 &mut self, 1460 builder: &mut FunctionBuilder, 1461 block: Block, 1462 ) -> Result<Vec<BlockArg>> { 1463 let (_, sig) = self.resources.blocks[block.as_u32() as usize].clone(); 1464 Ok(self 1465 .generate_values_for_signature(builder, sig.iter().copied())? 1466 .into_iter() 1467 .map(|val| BlockArg::Value(val)) 1468 .collect::<Vec<_>>()) 1469 } 1470 1471 fn generate_values_for_signature<I: Iterator<Item = Type>>( 1472 &mut self, 1473 builder: &mut FunctionBuilder, 1474 signature: I, 1475 ) -> Result<Vec<Value>> { 1476 signature 1477 .map(|ty| { 1478 let var = self.get_variable_of_type(ty)?; 1479 let val = builder.use_var(var); 1480 Ok(val) 1481 }) 1482 .collect() 1483 } 1484 1485 /// The terminator that we need to insert has already been picked ahead of time 1486 /// we just need to build the instructions for it 1487 fn insert_terminator( 1488 &mut self, 1489 builder: &mut FunctionBuilder, 1490 source_block: Block, 1491 ) -> Result<()> { 1492 let terminator = self.resources.block_terminators[source_block.as_u32() as usize].clone(); 1493 1494 match terminator { 1495 BlockTerminator::Return => { 1496 let types: Vec<Type> = { 1497 let rets = &builder.func.signature.returns; 1498 rets.iter().map(|p| p.value_type).collect() 1499 }; 1500 let vals = self.generate_values_for_signature(builder, types.into_iter())?; 1501 1502 builder.ins().return_(&vals[..]); 1503 } 1504 BlockTerminator::Jump(target) => { 1505 let args = self.generate_values_for_block(builder, target)?; 1506 builder.ins().jump(target, &args[..]); 1507 } 1508 BlockTerminator::Br(left, right) => { 1509 let left_args = self.generate_values_for_block(builder, left)?; 1510 let right_args = self.generate_values_for_block(builder, right)?; 1511 1512 let condbr_types = [I8, I16, I32, I64, I128]; 1513 let _type = *self.u.choose(&condbr_types[..])?; 1514 let val = builder.use_var(self.get_variable_of_type(_type)?); 1515 builder 1516 .ins() 1517 .brif(val, left, &left_args[..], right, &right_args[..]); 1518 } 1519 BlockTerminator::BrTable(default, targets) => { 1520 // Create jump tables on demand 1521 let mut jt = Vec::with_capacity(targets.len()); 1522 for block in targets { 1523 let args = self.generate_values_for_block(builder, block)?; 1524 jt.push(builder.func.dfg.block_call(block, &args)) 1525 } 1526 1527 let args = self.generate_values_for_block(builder, default)?; 1528 let jt_data = JumpTableData::new(builder.func.dfg.block_call(default, &args), &jt); 1529 let jt = builder.create_jump_table(jt_data); 1530 1531 // br_table only supports I32 1532 let val = builder.use_var(self.get_variable_of_type(I32)?); 1533 1534 builder.ins().br_table(val, jt); 1535 } 1536 BlockTerminator::Switch(_type, default, entries) => { 1537 let mut switch = Switch::new(); 1538 for (&entry, &block) in entries.iter() { 1539 switch.set_entry(entry, block); 1540 } 1541 1542 let switch_val = builder.use_var(self.get_variable_of_type(_type)?); 1543 1544 switch.emit(builder, switch_val, default); 1545 } 1546 BlockTerminator::TailCall(target) | BlockTerminator::TailCallIndirect(target) => { 1547 let (sig, sig_ref, func_ref) = self 1548 .resources 1549 .func_refs 1550 .iter() 1551 .find(|(_, _, f)| *f == target) 1552 .expect("Failed to find previously selected function") 1553 .clone(); 1554 1555 let opcode = match terminator { 1556 BlockTerminator::TailCall(_) => Opcode::ReturnCall, 1557 BlockTerminator::TailCallIndirect(_) => Opcode::ReturnCallIndirect, 1558 _ => unreachable!(), 1559 }; 1560 1561 insert_call_to_function(self, builder, opcode, &sig, sig_ref, func_ref)?; 1562 } 1563 } 1564 1565 Ok(()) 1566 } 1567 1568 /// Fills the current block with random instructions 1569 fn generate_instructions(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1570 for _ in 0..self.param(&self.config.instructions_per_block)? { 1571 let (op, args, rets) = self.u.choose(&OPCODE_SIGNATURES)?; 1572 1573 // We filter out instructions that aren't supported by the target at this point instead 1574 // of building a single vector of valid instructions at the beginning of function 1575 // generation, to avoid invalidating the corpus when instructions are enabled/disabled. 1576 if !valid_for_target(&self.isa.triple(), *op, &args, &rets) { 1577 return Err(arbitrary::Error::IncorrectFormat.into()); 1578 } 1579 1580 let inserter = inserter_for_format(op.format()); 1581 inserter(self, builder, *op, &args, &rets)?; 1582 } 1583 1584 Ok(()) 1585 } 1586 1587 fn generate_funcrefs(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1588 let usercalls: Vec<_> = self 1589 .resources 1590 .usercalls 1591 .iter() 1592 .map(|(name, signature)| { 1593 let user_func_ref = builder.func.declare_imported_user_function(name.clone()); 1594 let name = ExternalName::User(user_func_ref); 1595 (name, signature.clone()) 1596 }) 1597 .collect(); 1598 1599 let lib_callconv = self.system_callconv(); 1600 let libcalls: Vec<_> = self 1601 .resources 1602 .libcalls 1603 .iter() 1604 .map(|libcall| { 1605 let pointer_type = Type::int_with_byte_size( 1606 self.isa.triple().pointer_width().unwrap().bytes().into(), 1607 ) 1608 .unwrap(); 1609 let signature = libcall.signature(lib_callconv, pointer_type); 1610 let name = ExternalName::LibCall(*libcall); 1611 (name, signature) 1612 }) 1613 .collect(); 1614 1615 for (name, signature) in usercalls.into_iter().chain(libcalls) { 1616 let sig_ref = builder.import_signature(signature.clone()); 1617 let func_ref = builder.import_function(ExtFuncData { 1618 name, 1619 signature: sig_ref, 1620 1621 // Libcalls can't be colocated because they can be very far away 1622 // from allocated memory at runtime, and additionally at this 1623 // time cranelift-jit puts all functions in their own mmap so 1624 // they also cannot be colocated. 1625 colocated: false, 1626 }); 1627 1628 self.resources 1629 .func_refs 1630 .push((signature, sig_ref, func_ref)); 1631 } 1632 1633 Ok(()) 1634 } 1635 1636 fn generate_stack_slots(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1637 for _ in 0..self.param(&self.config.static_stack_slots_per_function)? { 1638 let bytes = self.param(&self.config.static_stack_slot_size)? as u32; 1639 let alignment = self.param(&self.config.stack_slot_alignment_log2)? as u8; 1640 let alignment_bytes = 1 << alignment; 1641 1642 let ss_data = StackSlotData::new(StackSlotKind::ExplicitSlot, bytes, alignment); 1643 let slot = builder.create_sized_stack_slot(ss_data); 1644 1645 // Generate one Alias Analysis Category for each slot 1646 let category = *self.u.choose(AACategory::all())?; 1647 1648 self.resources 1649 .stack_slots 1650 .push((slot, bytes, alignment_bytes, category)); 1651 } 1652 1653 self.resources 1654 .stack_slots 1655 .sort_unstable_by_key(|&(_slot, bytes, _align, _category)| bytes); 1656 1657 Ok(()) 1658 } 1659 1660 /// Zero initializes the stack slot by inserting `stack_store`'s. 1661 fn initialize_stack_slots(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1662 let i8_zero = builder.ins().iconst(I8, 0); 1663 let i16_zero = builder.ins().iconst(I16, 0); 1664 let i32_zero = builder.ins().iconst(I32, 0); 1665 let i64_zero = builder.ins().iconst(I64, 0); 1666 let i128_zero = builder.ins().uextend(I128, i64_zero); 1667 1668 for &(slot, init_size, _align, category) in self.resources.stack_slots.iter() { 1669 let mut size = init_size; 1670 1671 // Insert the largest available store for the remaining size. 1672 while size != 0 { 1673 let offset = (init_size - size) as i32; 1674 let (val, filled) = match size { 1675 sz if sz / 16 > 0 => (i128_zero, 16), 1676 sz if sz / 8 > 0 => (i64_zero, 8), 1677 sz if sz / 4 > 0 => (i32_zero, 4), 1678 sz if sz / 2 > 0 => (i16_zero, 2), 1679 _ => (i8_zero, 1), 1680 }; 1681 let addr = builder.ins().stack_addr(I64, slot, offset); 1682 1683 // Each stack slot has an associated category, that means we have to set the 1684 // correct memflags for it. So we can't use `stack_store` directly. 1685 let mut flags = MemFlags::new(); 1686 flags.set_notrap(); 1687 category.update_memflags(&mut flags); 1688 1689 builder.ins().store(flags, val, addr, 0); 1690 1691 size -= filled; 1692 } 1693 } 1694 Ok(()) 1695 } 1696 1697 /// Creates a random amount of blocks in this function 1698 fn generate_blocks(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1699 let extra_block_count = self.param(&self.config.blocks_per_function)?; 1700 1701 // We must always have at least one block, so we generate the "extra" blocks and add 1 for 1702 // the entry block. 1703 let block_count = 1 + extra_block_count; 1704 1705 // Blocks need to be sorted in ascending order 1706 self.resources.blocks = (0..block_count) 1707 .map(|i| { 1708 let is_entry = i == 0; 1709 let block = builder.create_block(); 1710 1711 // Optionally mark blocks that are not the entry block as cold 1712 if !is_entry { 1713 if bool::arbitrary(self.u)? { 1714 builder.set_cold_block(block); 1715 } 1716 } 1717 1718 // The first block has to have the function signature, but for the rest of them we generate 1719 // a random signature; 1720 if is_entry { 1721 builder.append_block_params_for_function_params(block); 1722 Ok(( 1723 block, 1724 self.signature.params.iter().map(|a| a.value_type).collect(), 1725 )) 1726 } else { 1727 let sig = self.generate_block_signature()?; 1728 sig.iter().for_each(|ty| { 1729 builder.append_block_param(block, *ty); 1730 }); 1731 Ok((block, sig)) 1732 } 1733 }) 1734 .collect::<Result<Vec<_>>>()?; 1735 1736 // Valid blocks for jump tables have to have no parameters in the signature, and must also 1737 // not be the first block. 1738 self.resources.blocks_without_params = self.resources.blocks[1..] 1739 .iter() 1740 .filter(|(_, sig)| sig.len() == 0) 1741 .map(|(b, _)| *b) 1742 .collect(); 1743 1744 // Compute the block CFG 1745 // 1746 // cranelift-frontend requires us to never generate unreachable blocks 1747 // To ensure this property we start by constructing a main "spine" of blocks. So block1 can 1748 // always jump to block2, and block2 can always jump to block3, etc... 1749 // 1750 // That is not a very interesting CFG, so we introduce variations on that, but always 1751 // ensuring that the property of pointing to the next block is maintained whatever the 1752 // branching mechanism we use. 1753 let blocks = self.resources.blocks.clone(); 1754 self.resources.block_terminators = blocks 1755 .iter() 1756 .map(|&(block, _)| { 1757 let next_block = Block::with_number(block.as_u32() + 1).unwrap(); 1758 let forward_blocks = self.resources.forward_blocks(block); 1759 let paramless_targets = self.resources.forward_blocks_without_params(block); 1760 let has_paramless_targets = !paramless_targets.is_empty(); 1761 let next_block_is_paramless = paramless_targets.contains(&next_block); 1762 1763 let mut valid_terminators = vec![]; 1764 1765 if forward_blocks.is_empty() { 1766 // Return is only valid on the last block. 1767 valid_terminators.push(BlockTerminatorKind::Return); 1768 } else { 1769 // If we have more than one block we can allow terminators that target blocks. 1770 // TODO: We could add some kind of BrReturn here, to explore edges where we 1771 // exit in the middle of the function 1772 valid_terminators.extend_from_slice(&[ 1773 BlockTerminatorKind::Jump, 1774 BlockTerminatorKind::Br, 1775 BlockTerminatorKind::BrTable, 1776 ]); 1777 } 1778 1779 // As the Switch interface only allows targeting blocks without params we need 1780 // to ensure that the next block has no params, since that one is guaranteed to be 1781 // picked in either case. 1782 if has_paramless_targets && next_block_is_paramless { 1783 valid_terminators.push(BlockTerminatorKind::Switch); 1784 } 1785 1786 // Tail Calls are a block terminator, so we should insert them as any other block 1787 // terminator. We should ensure that we can select at least one target before considering 1788 // them as candidate instructions. 1789 let has_tail_callees = self 1790 .resources 1791 .tail_call_targets(&self.signature) 1792 .next() 1793 .is_some(); 1794 let is_tail_caller = self.signature.call_conv == CallConv::Tail; 1795 1796 let supports_tail_calls = match self.isa.triple().architecture { 1797 Architecture::Aarch64(_) | Architecture::Riscv64(_) => true, 1798 // TODO: x64 currently requires frame pointers for tail calls. 1799 Architecture::X86_64 => self.isa.flags().preserve_frame_pointers(), 1800 // TODO: Other platforms do not support tail calls yet. 1801 _ => false, 1802 }; 1803 1804 if is_tail_caller && has_tail_callees && supports_tail_calls { 1805 valid_terminators.extend([ 1806 BlockTerminatorKind::TailCall, 1807 BlockTerminatorKind::TailCallIndirect, 1808 ]); 1809 } 1810 1811 let terminator = self.u.choose(&valid_terminators)?; 1812 1813 // Choose block targets for the terminators that we picked above 1814 Ok(match terminator { 1815 BlockTerminatorKind::Return => BlockTerminator::Return, 1816 BlockTerminatorKind::Jump => BlockTerminator::Jump(next_block), 1817 BlockTerminatorKind::Br => { 1818 BlockTerminator::Br(next_block, self.generate_target_block(block)?) 1819 } 1820 // TODO: Allow generating backwards branches here 1821 BlockTerminatorKind::BrTable => { 1822 // Make the default the next block, and then we don't have to worry 1823 // that we can reach it via the targets 1824 let default = next_block; 1825 1826 let target_count = self.param(&self.config.jump_table_entries)?; 1827 let targets = Result::from_iter( 1828 (0..target_count).map(|_| self.generate_target_block(block)), 1829 )?; 1830 1831 BlockTerminator::BrTable(default, targets) 1832 } 1833 BlockTerminatorKind::Switch => { 1834 // Make the default the next block, and then we don't have to worry 1835 // that we can reach it via the entries below 1836 let default_block = next_block; 1837 1838 let _type = *self.u.choose(&[I8, I16, I32, I64, I128][..])?; 1839 1840 // Build this into a HashMap since we cannot have duplicate entries. 1841 let mut entries = HashMap::new(); 1842 for _ in 0..self.param(&self.config.switch_cases)? { 1843 // The Switch API only allows for entries that are addressable by the index type 1844 // so we need to limit the range of values that we generate. 1845 let (ty_min, ty_max) = _type.bounds(false); 1846 let range_start = self.u.int_in_range(ty_min..=ty_max)?; 1847 1848 // We can either insert a contiguous range of blocks or a individual block 1849 // This is done because the Switch API specializes contiguous ranges. 1850 let range_size = if bool::arbitrary(self.u)? { 1851 1 1852 } else { 1853 self.param(&self.config.switch_max_range_size)? 1854 } as u128; 1855 1856 // Build the switch entries 1857 for i in 0..range_size { 1858 let index = range_start.wrapping_add(i) % ty_max; 1859 let block = *self 1860 .u 1861 .choose(self.resources.forward_blocks_without_params(block))?; 1862 1863 entries.insert(index, block); 1864 } 1865 } 1866 1867 BlockTerminator::Switch(_type, default_block, entries) 1868 } 1869 BlockTerminatorKind::TailCall => { 1870 let targets = self 1871 .resources 1872 .tail_call_targets(&self.signature) 1873 .collect::<Vec<_>>(); 1874 let (_, _, funcref) = *self.u.choose(&targets[..])?; 1875 BlockTerminator::TailCall(*funcref) 1876 } 1877 BlockTerminatorKind::TailCallIndirect => { 1878 let targets = self 1879 .resources 1880 .tail_call_targets(&self.signature) 1881 .collect::<Vec<_>>(); 1882 let (_, _, funcref) = *self.u.choose(&targets[..])?; 1883 BlockTerminator::TailCallIndirect(*funcref) 1884 } 1885 }) 1886 }) 1887 .collect::<Result<_>>()?; 1888 1889 Ok(()) 1890 } 1891 1892 fn generate_block_signature(&mut self) -> Result<BlockSignature> { 1893 let param_count = self.param(&self.config.block_signature_params)?; 1894 1895 let mut params = Vec::with_capacity(param_count); 1896 for _ in 0..param_count { 1897 params.push(self.u._type((&*self.isa).supports_simd())?); 1898 } 1899 Ok(params) 1900 } 1901 1902 fn build_variable_pool(&mut self, builder: &mut FunctionBuilder) -> Result<()> { 1903 let block = builder.current_block().unwrap(); 1904 1905 // Define variables for the function signature 1906 let mut vars: Vec<_> = builder 1907 .func 1908 .signature 1909 .params 1910 .iter() 1911 .map(|param| param.value_type) 1912 .zip(builder.block_params(block).iter().copied()) 1913 .collect(); 1914 1915 // Create a pool of vars that are going to be used in this function 1916 for _ in 0..self.param(&self.config.vars_per_function)? { 1917 let ty = self.u._type((&*self.isa).supports_simd())?; 1918 let value = self.generate_const(builder, ty)?; 1919 vars.push((ty, value)); 1920 } 1921 1922 for (ty, value) in vars.into_iter() { 1923 let var = builder.declare_var(ty); 1924 builder.def_var(var, value); 1925 1926 // Randomly declare variables as needing a stack map. 1927 // We limit these to only types that have fewer than 16 bytes 1928 // since the stack map mechanism does not support larger types. 1929 if ty.bytes() <= 16 && self.u.arbitrary()? { 1930 builder.declare_var_needs_stack_map(var); 1931 } 1932 1933 self.resources 1934 .vars 1935 .entry(ty) 1936 .or_insert_with(Vec::new) 1937 .push(var); 1938 } 1939 1940 Ok(()) 1941 } 1942 1943 /// We generate a function in multiple stages: 1944 /// 1945 /// * First we generate a random number of empty blocks 1946 /// * Then we generate a random pool of variables to be used throughout the function 1947 /// * We then visit each block and generate random instructions 1948 /// 1949 /// Because we generate all blocks and variables up front we already know everything that 1950 /// we need when generating instructions (i.e. jump targets / variables) 1951 pub fn generate(mut self) -> Result<Function> { 1952 let mut fn_builder_ctx = FunctionBuilderContext::new(); 1953 let mut func = Function::with_name_signature(self.name.clone(), self.signature.clone()); 1954 1955 let mut builder = FunctionBuilder::new(&mut func, &mut fn_builder_ctx); 1956 1957 // Build the function references before generating the block CFG since we store 1958 // function references in the CFG. 1959 self.generate_funcrefs(&mut builder)?; 1960 self.generate_blocks(&mut builder)?; 1961 1962 // Function preamble 1963 self.generate_stack_slots(&mut builder)?; 1964 1965 // Main instruction generation loop 1966 for (block, block_sig) in self.resources.blocks.clone().into_iter() { 1967 let is_block0 = block.as_u32() == 0; 1968 builder.switch_to_block(block); 1969 1970 if is_block0 { 1971 // The first block is special because we must create variables both for the 1972 // block signature and for the variable pool. Additionally, we must also define 1973 // initial values for all variables that are not the function signature. 1974 self.build_variable_pool(&mut builder)?; 1975 1976 // Stack slots have random bytes at the beginning of the function 1977 // initialize them to a constant value so that execution stays predictable. 1978 self.initialize_stack_slots(&mut builder)?; 1979 } else { 1980 // Define variables for the block params 1981 for (i, ty) in block_sig.iter().enumerate() { 1982 let var = self.get_variable_of_type(*ty)?; 1983 let block_param = builder.block_params(block)[i]; 1984 builder.def_var(var, block_param); 1985 } 1986 } 1987 1988 // Generate block instructions 1989 self.generate_instructions(&mut builder)?; 1990 1991 // Insert a terminator to safely exit the block 1992 self.insert_terminator(&mut builder, block)?; 1993 } 1994 1995 builder.seal_all_blocks(); 1996 builder.finalize(); 1997 1998 Ok(func) 1999 } 2000 } 2001