diff options
Diffstat (limited to 'library/compiler-builtins/builtins-test/src/lib.rs')
| -rw-r--r-- | library/compiler-builtins/builtins-test/src/lib.rs | 337 |
1 files changed, 337 insertions, 0 deletions
diff --git a/library/compiler-builtins/builtins-test/src/lib.rs b/library/compiler-builtins/builtins-test/src/lib.rs new file mode 100644 index 00000000000..c596ac21380 --- /dev/null +++ b/library/compiler-builtins/builtins-test/src/lib.rs @@ -0,0 +1,337 @@ +//! This crate is for integration testing and fuzz testing of functions in `compiler-builtins`. This +//! includes publicly documented intrinsics and some internal alternative implementation functions +//! such as `usize_leading_zeros_riscv` (which are tested because they are configured for +//! architectures not tested by the CI). +//! +//! The general idea is to use a combination of edge case testing and randomized fuzz testing. The +//! edge case testing is crucial for checking cases like where both inputs are equal or equal to +//! special values such as `i128::MIN`, which is unlikely for the random fuzzer by itself to +//! encounter. The randomized fuzz testing is specially designed to cover wide swaths of search +//! space in as few iterations as possible. See `fuzz_values` in `builtins-test/tests/misc.rs` for +//! an example. +//! +//! Some floating point tests are disabled for specific architectures, because they do not have +//! correct rounding. +#![no_std] +#![cfg_attr(f128_enabled, feature(f128))] +#![cfg_attr(f16_enabled, feature(f16))] + +pub mod bench; +extern crate alloc; + +use compiler_builtins::float::Float; +use compiler_builtins::int::{Int, MinInt}; +use rand_xoshiro::Xoshiro128StarStar; +use rand_xoshiro::rand_core::{RngCore, SeedableRng}; + +/// Sets the number of fuzz iterations run for most tests. In practice, the vast majority of bugs +/// are caught by the edge case testers. Most of the remaining bugs triggered by more complex +/// sequences are caught well within 10_000 fuzz iterations. For classes of algorithms like division +/// that are vulnerable to rare edge cases, we want 1_000_000 iterations to be more confident. In +/// practical CI, however, we only want to run the more strenuous test once to catch algorithmic +/// level bugs, and run the 10_000 iteration test on most targets. Target-dependent bugs are likely +/// to involve miscompilation and misconfiguration that is likely to break algorithms in quickly +/// caught ways. We choose to configure `N = 1_000_000` iterations for `x86_64` targets (and if +/// debug assertions are disabled. Tests without `--release` would take too long) which are likely +/// to have fast hardware, and run `N = 10_000` for all other targets. +pub const N: u32 = if cfg!(target_arch = "x86_64") && !cfg!(debug_assertions) { + 1_000_000 +} else { + 10_000 +}; + +/// Random fuzzing step. When run several times, it results in excellent fuzzing entropy such as: +/// 11110101010101011110111110011111 +/// 10110101010100001011101011001010 +/// 1000000000000000 +/// 10000000000000110111110000001010 +/// 1111011111111101010101111110101 +/// 101111111110100000000101000000 +/// 10000000110100000000100010101 +/// 1010101010101000 +fn fuzz_step<I: Int>(rng: &mut Xoshiro128StarStar, x: &mut I) { + let ones = !I::ZERO; + let bit_indexing_mask: u32 = I::BITS - 1; + // It happens that all the RNG we need can come from one call. 7 bits are needed to index a + // worst case 128 bit integer, and there are 4 indexes that need to be made plus 4 bits for + // selecting operations + let rng32 = rng.next_u32(); + + // Randomly OR, AND, and XOR randomly sized and shifted continuous strings of + // ones with `lhs` and `rhs`. + let r0 = bit_indexing_mask & rng32; + let r1 = bit_indexing_mask & (rng32 >> 7); + let mask = ones.wrapping_shl(r0).rotate_left(r1); + match (rng32 >> 14) % 4 { + 0 => *x |= mask, + 1 => *x &= mask, + // both 2 and 3 to make XORs as common as ORs and ANDs combined + _ => *x ^= mask, + } + + // Alternating ones and zeros (e.x. 0b1010101010101010). This catches second-order + // problems that might occur for algorithms with two modes of operation (potentially + // there is some invariant that can be broken and maintained via alternating between modes, + // breaking the algorithm when it reaches the end). + let mut alt_ones = I::ONE; + for _ in 0..(I::BITS / 2) { + alt_ones <<= 2; + alt_ones |= I::ONE; + } + let r0 = bit_indexing_mask & (rng32 >> 16); + let r1 = bit_indexing_mask & (rng32 >> 23); + let mask = alt_ones.wrapping_shl(r0).rotate_left(r1); + match rng32 >> 30 { + 0 => *x |= mask, + 1 => *x &= mask, + _ => *x ^= mask, + } +} + +// We need macros like this, because `#![no_std]` prevents us from using iterators +macro_rules! edge_cases { + ($I:ident, $case:ident, $inner:block) => { + for i0 in 0..$I::FUZZ_NUM { + let mask_lo = (!$I::UnsignedInt::ZERO).wrapping_shr($I::FUZZ_LENGTHS[i0] as u32); + for i1 in i0..I::FUZZ_NUM { + let mask_hi = + (!$I::UnsignedInt::ZERO).wrapping_shl($I::FUZZ_LENGTHS[i1 - i0] as u32); + let $case = I::from_unsigned(mask_lo & mask_hi); + $inner + } + } + }; +} + +/// Feeds a series of fuzzing inputs to `f`. The fuzzer first uses an algorithm designed to find +/// edge cases, followed by a more random fuzzer that runs `n` times. +pub fn fuzz<I: Int, F: FnMut(I)>(n: u32, mut f: F) +where + <I as MinInt>::UnsignedInt: Int, +{ + // edge case tester. Calls `f` 210 times for u128. + // zero gets skipped by the loop + f(I::ZERO); + edge_cases!(I, case, { + f(case); + }); + + // random fuzzer + let mut rng = Xoshiro128StarStar::seed_from_u64(0); + let mut x: I = MinInt::ZERO; + for _ in 0..n { + fuzz_step(&mut rng, &mut x); + f(x) + } +} + +/// The same as `fuzz`, except `f` has two inputs. +pub fn fuzz_2<I: Int, F: Fn(I, I)>(n: u32, f: F) +where + <I as MinInt>::UnsignedInt: Int, +{ + // Check cases where the first and second inputs are zero. Both call `f` 210 times for `u128`. + edge_cases!(I, case, { + f(I::ZERO, case); + }); + edge_cases!(I, case, { + f(case, I::ZERO); + }); + // Nested edge tester. Calls `f` 44100 times for `u128`. + edge_cases!(I, case0, { + edge_cases!(I, case1, { + f(case0, case1); + }) + }); + + // random fuzzer + let mut rng = Xoshiro128StarStar::seed_from_u64(0); + let mut x: I = I::ZERO; + let mut y: I = I::ZERO; + for _ in 0..n { + fuzz_step(&mut rng, &mut x); + fuzz_step(&mut rng, &mut y); + f(x, y) + } +} + +/// Tester for shift functions +pub fn fuzz_shift<I: Int, F: Fn(I, u32)>(f: F) { + // Shift functions are very simple and do not need anything other than shifting a small + // set of random patterns for every fuzz length. + let mut rng = Xoshiro128StarStar::seed_from_u64(0); + let mut x: I = MinInt::ZERO; + for i in 0..I::FUZZ_NUM { + fuzz_step(&mut rng, &mut x); + f(x, MinInt::ZERO); + f(x, I::FUZZ_LENGTHS[i] as u32); + } +} + +fn fuzz_float_step<F: Float>(rng: &mut Xoshiro128StarStar, f: &mut F) { + let rng32 = rng.next_u32(); + // we need to fuzz the different parts of the float separately, because the masking on larger + // significands will tend to set the exponent to all ones or all zeros frequently + + // sign bit fuzzing + let sign = (rng32 & 1) != 0; + + // exponent fuzzing. Only 4 bits for the selector needed. + let ones = (F::Int::ONE << F::EXP_BITS) - F::Int::ONE; + let r0 = (rng32 >> 1) % F::EXP_BITS; + let r1 = (rng32 >> 5) % F::EXP_BITS; + // custom rotate shift. Note that `F::Int` is unsigned, so we can shift right without smearing + // the sign bit. + let mask = if r1 == 0 { + ones.wrapping_shr(r0) + } else { + let tmp = ones.wrapping_shr(r0); + (tmp.wrapping_shl(r1) | tmp.wrapping_shr(F::EXP_BITS - r1)) & ones + }; + let mut exp = (f.to_bits() & F::EXP_MASK) >> F::SIG_BITS; + match (rng32 >> 9) % 4 { + 0 => exp |= mask, + 1 => exp &= mask, + _ => exp ^= mask, + } + + // significand fuzzing + let mut sig = f.to_bits() & F::SIG_MASK; + fuzz_step(rng, &mut sig); + sig &= F::SIG_MASK; + + *f = F::from_parts(sign, exp, sig); +} + +macro_rules! float_edge_cases { + ($F:ident, $case:ident, $inner:block) => { + for exponent in [ + F::Int::ZERO, + F::Int::ONE, + F::Int::ONE << (F::EXP_BITS / 2), + (F::Int::ONE << (F::EXP_BITS - 1)) - F::Int::ONE, + F::Int::ONE << (F::EXP_BITS - 1), + (F::Int::ONE << (F::EXP_BITS - 1)) + F::Int::ONE, + (F::Int::ONE << F::EXP_BITS) - F::Int::ONE, + ] + .iter() + { + for significand in [ + F::Int::ZERO, + F::Int::ONE, + F::Int::ONE << (F::SIG_BITS / 2), + (F::Int::ONE << (F::SIG_BITS - 1)) - F::Int::ONE, + F::Int::ONE << (F::SIG_BITS - 1), + (F::Int::ONE << (F::SIG_BITS - 1)) + F::Int::ONE, + (F::Int::ONE << F::SIG_BITS) - F::Int::ONE, + ] + .iter() + { + for sign in [false, true].iter() { + let $case = F::from_parts(*sign, *exponent, *significand); + $inner + } + } + } + }; +} + +pub fn fuzz_float<F: Float, E: Fn(F)>(n: u32, f: E) { + float_edge_cases!(F, case, { + f(case); + }); + + // random fuzzer + let mut rng = Xoshiro128StarStar::seed_from_u64(0); + let mut x = F::ZERO; + for _ in 0..n { + fuzz_float_step(&mut rng, &mut x); + f(x); + } +} + +pub fn fuzz_float_2<F: Float, E: Fn(F, F)>(n: u32, f: E) { + float_edge_cases!(F, case0, { + float_edge_cases!(F, case1, { + f(case0, case1); + }); + }); + + // random fuzzer + let mut rng = Xoshiro128StarStar::seed_from_u64(0); + let mut x = F::ZERO; + let mut y = F::ZERO; + for _ in 0..n { + fuzz_float_step(&mut rng, &mut x); + fuzz_float_step(&mut rng, &mut y); + f(x, y) + } +} + +/// Perform an operation using builtin types if available, falling back to apfloat if not. +#[macro_export] +macro_rules! apfloat_fallback { + ( + $float_ty:ty, + // Type name in `rustc_apfloat::ieee`. Not a full path, it automatically gets the prefix. + $apfloat_ty:ident, + // Cfg expression for when builtin system operations should be used + $sys_available:meta, + // The expression to run. This expression may use `FloatTy` for its signature. + // Optionally, the final conversion back to a float can be suppressed using + // `=> no_convert` (for e.g. operations that return a bool). + // + // If the apfloat needs a different operation, it can be provided here. + $op:expr $(=> $convert:ident)? $(; $apfloat_op:expr)?, + // Arguments that get passed to `$op` after converting to a float + $($arg:expr),+ + $(,)? + ) => {{ + #[cfg($sys_available)] + let ret = { + type FloatTy = $float_ty; + $op( $($arg),+ ) + }; + + #[cfg(not($sys_available))] + let ret = { + use rustc_apfloat::Float; + type FloatTy = rustc_apfloat::ieee::$apfloat_ty; + + apfloat_fallback!(@inner + fty: $float_ty, + // Apply a conversion to `FloatTy` to each arg, then pass all args to `$op` + op_res: $op( $(FloatTy::from_bits($arg.to_bits().into())),+ ), + $(apfloat_op: $apfloat_op, )? + $(conv_opts: $convert,)? + args: $($arg),+ + ) + }; + + ret + }}; + + // Operations that do not need converting back to a float + (@inner fty: $float_ty:ty, op_res: $val:expr, conv_opts: no_convert, args: $($_arg:expr),+) => { + $val + }; + + // Some apfloat operations return a `StatusAnd` that we need to extract the value from. This + // is the default. + (@inner fty: $float_ty:ty, op_res: $val:expr, args: $($_arg:expr),+) => {{ + // ignore the status, just get the value + let unwrapped = $val.value; + + <$float_ty>::from_bits(FloatTy::to_bits(unwrapped).try_into().unwrap()) + }}; + + // This is the case where we can't use the same expression for the default builtin and + // nonstandard apfloat fallback (e.g. `as` casts in std are normal functions in apfloat, so + // two separate expressions must be specified. + (@inner + fty: $float_ty:ty, op_res: $_val:expr, + apfloat_op: $apfloat_op:expr, args: $($arg:expr),+ + ) => {{ + $apfloat_op($($arg),+) + }}; +} |