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
insert_opcode( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, args: &[Type], rets: &[Type], ) -> Result<()>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
insert_call_to_function( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, call_opcode: Opcode, sig: &Signature, sig_ref: SigRef, func_ref: FuncRef, ) -> Result<()>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
insert_call( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, _args: &[Type], _rets: &[Type], ) -> Result<()>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
insert_stack_load( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, _opcode: Opcode, _args: &[Type], rets: &[Type], ) -> Result<()>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
insert_stack_store( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, _opcode: Opcode, args: &[Type], _rets: &[Type], ) -> Result<()>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
insert_cmp( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, args: &[Type], rets: &[Type], ) -> Result<()>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
insert_const( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, _opcode: Opcode, _args: &[Type], rets: &[Type], ) -> Result<()>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
insert_bitcast( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, args: &[Type], rets: &[Type], ) -> Result<()>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
insert_load_store( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, args: &[Type], rets: &[Type], ) -> Result<()>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
insert_atomic_rmw( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, _: Opcode, _: &[Type], rets: &[Type], ) -> Result<()>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
insert_atomic_cas( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, _: Opcode, _: &[Type], rets: &[Type], ) -> Result<()>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
insert_shuffle( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, _: &[Type], rets: &[Type], ) -> Result<()>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
insert_ins_ext_lane( fgen: &mut FunctionGenerator, builder: &mut FunctionBuilder, opcode: Opcode, args: &[Type], rets: &[Type], ) -> Result<()>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.
valid_for_target(triple: &Triple, op: Opcode, args: &[Type], rets: &[Type]) -> bool474 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
inserter_for_format(fmt: InstructionFormat) -> OpcodeInserter1076 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 {
all() -> &'static [Self]1178 pub fn all() -> &'static [Self] {
1179 &[
1180 AACategory::Other,
1181 AACategory::Heap,
1182 AACategory::Table,
1183 AACategory::VmCtx,
1184 ]
1185 }
1186
update_memflags(&self, flags: &mut MemFlags)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.
partition_target_blocks( &self, block: Block, ) -> (&[(Block, BlockSignature)], &[(Block, BlockSignature)])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.
forward_blocks(&self, block: Block) -> &[(Block, BlockSignature)]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`
forward_blocks_without_params(&self, block: Block) -> &[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.
tail_call_targets<'a>( &'a self, caller_sig: &'a Signature, ) -> impl Iterator<Item = &'a (Signature, SigRef, FuncRef)>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 {
new( u: &'r mut Unstructured<'data>, config: &'r Config, isa: OwnedTargetIsa, name: UserFuncName, signature: Signature, usercalls: Vec<(UserExternalName, Signature)>, libcalls: Vec<LibCall>, ) -> Self1257 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`
param(&mut self, param: &RangeInclusive<usize>) -> Result<usize>1281 fn param(&mut self, param: &RangeInclusive<usize>) -> Result<usize> {
1282 Ok(self.u.int_in_range(param.clone())?)
1283 }
1284
system_callconv(&mut self) -> CallConv1285 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
stack_slot_with_size( &mut self, n: u32, ) -> Result<(StackSlot, StackSize, StackAlignment, AACategory)>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`.
generate_load_store_address( &mut self, builder: &mut FunctionBuilder, min_size: u32, aligned: bool, ) -> Result<(Value, u32, AACategory)>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.
generate_address_and_memflags( &mut self, builder: &mut FunctionBuilder, min_size: u32, is_atomic: bool, ) -> Result<(Value, MemFlags, Offset32)>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
get_variable_of_type(&mut self, ty: Type) -> Result<Variable>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
generate_const(&mut self, builder: &mut FunctionBuilder, ty: Type) -> Result<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.
generate_target_block(&mut self, source_block: Block) -> Result<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
generate_values_for_block( &mut self, builder: &mut FunctionBuilder, block: Block, ) -> Result<Vec<BlockArg>>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
generate_values_for_signature<I: Iterator<Item = Type>>( &mut self, builder: &mut FunctionBuilder, signature: I, ) -> Result<Vec<Value>>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
insert_terminator( &mut self, builder: &mut FunctionBuilder, source_block: Block, ) -> Result<()>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
generate_instructions(&mut self, builder: &mut FunctionBuilder) -> Result<()>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
generate_funcrefs(&mut self, builder: &mut FunctionBuilder) -> Result<()>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
generate_stack_slots(&mut self, builder: &mut FunctionBuilder) -> Result<()>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.
initialize_stack_slots(&mut self, builder: &mut FunctionBuilder) -> Result<()>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
generate_blocks(&mut self, builder: &mut FunctionBuilder) -> Result<()>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
generate_block_signature(&mut self) -> Result<BlockSignature>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
build_variable_pool(&mut self, builder: &mut FunctionBuilder) -> Result<()>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)
generate(mut self) -> Result<Function>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