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