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