From 296f3879b11fb2dce0a02c5aea6aae2c624c7e89 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Fri, 20 Jan 2023 17:32:17 -0800 Subject: [PATCH] start adding fuzzing --- Cargo.lock | 57 +++ register_allocator/Cargo.toml | 5 + register_allocator/fuzz/.gitignore | 4 + register_allocator/fuzz/Cargo.lock | 350 ++++++++++++++++++ register_allocator/fuzz/Cargo.toml | 27 ++ .../fuzz/fuzz_targets/fn_new.rs | 7 + register_allocator/src/error.rs | 16 + register_allocator/src/function.rs | 9 +- register_allocator/src/fuzzing.rs | 64 ++++ register_allocator/src/lib.rs | 2 + register_allocator/src/loc.rs | 148 +++++++- register_allocator/src/loc_set.rs | 60 +++ register_allocator/src/macros.rs | 16 +- 13 files changed, 760 insertions(+), 5 deletions(-) create mode 100644 register_allocator/fuzz/.gitignore create mode 100644 register_allocator/fuzz/Cargo.lock create mode 100644 register_allocator/fuzz/Cargo.toml create mode 100644 register_allocator/fuzz/fuzz_targets/fn_new.rs create mode 100644 register_allocator/src/fuzzing.rs diff --git a/Cargo.lock b/Cargo.lock index 761adf6..5c9cfba 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -13,6 +13,15 @@ dependencies = [ "version_check", ] +[[package]] +name = "arbitrary" +version = "1.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0224938f92e7aef515fac2ff2d18bd1115c1394ddf4a092e0c87e8be9499ee5" +dependencies = [ + "derive_arbitrary", +] + [[package]] name = "autocfg" version = "1.1.0" @@ -23,9 +32,11 @@ checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" name = "bigint-presentation-code-register-allocator" version = "0.1.0" dependencies = [ + "arbitrary", "enum-map", "eyre", "hashbrown 0.13.2", + "libfuzzer-sys", "num-bigint", "num-traits", "petgraph", @@ -37,12 +48,32 @@ dependencies = [ "typed-arena", ] +[[package]] +name = "cc" +version = "1.0.78" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a20104e2335ce8a659d6dd92a51a767a0c062599c73b343fd152cb401e828c3d" +dependencies = [ + "jobserver", +] + [[package]] name = "cfg-if" version = "1.0.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" +[[package]] +name = "derive_arbitrary" +version = "1.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf460bbff5f571bfc762da5102729f59f338be7db17a21fade44c5c4f5005350" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + [[package]] name = "enum-map" version = "2.4.2" @@ -118,6 +149,32 @@ version = "1.0.5" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "fad582f4b9e86b6caa621cabeb0963332d92eea04729ab12892c2533951e6440" +[[package]] +name = "jobserver" +version = "0.1.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "068b1ee6743e4d11fb9c6a1e6064b3693a1b600e7f5f5988047d98b3dc9fb90b" +dependencies = [ + "libc", +] + +[[package]] +name = "libc" +version = "0.2.139" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "201de327520df007757c1f0adce6e827fe8562fbc28bfd9c15571c66ca1f5f79" + +[[package]] +name = "libfuzzer-sys" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c8fff891139ee62800da71b7fd5b508d570b9ad95e614a53c6f453ca08366038" +dependencies = [ + "arbitrary", + "cc", + "once_cell", +] + [[package]] name = "num-bigint" version = "0.4.3" diff --git a/register_allocator/Cargo.toml b/register_allocator/Cargo.toml index 25e6f0e..05e792d 100644 --- a/register_allocator/Cargo.toml +++ b/register_allocator/Cargo.toml @@ -18,3 +18,8 @@ num-bigint = { version = "0.4.3", features = ["serde"] } enum-map = { version = "2.4.2", features = ["serde"] } num-traits = "0.2.15" petgraph = "0.6.2" +libfuzzer-sys = { version = "0.4.5", optional = true } +arbitrary = { version = "1.2.2", features = ["derive"] } + +[features] +fuzzing = ["libfuzzer-sys"] diff --git a/register_allocator/fuzz/.gitignore b/register_allocator/fuzz/.gitignore new file mode 100644 index 0000000..1a45eee --- /dev/null +++ b/register_allocator/fuzz/.gitignore @@ -0,0 +1,4 @@ +target +corpus +artifacts +coverage diff --git a/register_allocator/fuzz/Cargo.lock b/register_allocator/fuzz/Cargo.lock new file mode 100644 index 0000000..009ac03 --- /dev/null +++ b/register_allocator/fuzz/Cargo.lock @@ -0,0 +1,350 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "ahash" +version = "0.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bf6ccdb167abbf410dcb915cabd428929d7f6a04980b54a11f26a39f1c7f7107" +dependencies = [ + "cfg-if", + "once_cell", + "version_check", +] + +[[package]] +name = "arbitrary" +version = "1.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0224938f92e7aef515fac2ff2d18bd1115c1394ddf4a092e0c87e8be9499ee5" +dependencies = [ + "derive_arbitrary", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "bigint-presentation-code-register-allocator" +version = "0.1.0" +dependencies = [ + "arbitrary", + "enum-map", + "eyre", + "hashbrown 0.13.2", + "libfuzzer-sys", + "num-bigint", + "num-traits", + "petgraph", + "scoped-tls", + "serde", + "serde_json", + "smallvec", + "thiserror", + "typed-arena", +] + +[[package]] +name = "bigint-presentation-code-register-allocator-fuzz" +version = "0.0.0" +dependencies = [ + "bigint-presentation-code-register-allocator", + "libfuzzer-sys", +] + +[[package]] +name = "cc" +version = "1.0.78" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a20104e2335ce8a659d6dd92a51a767a0c062599c73b343fd152cb401e828c3d" +dependencies = [ + "jobserver", +] + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "derive_arbitrary" +version = "1.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf460bbff5f571bfc762da5102729f59f338be7db17a21fade44c5c4f5005350" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "enum-map" +version = "2.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "50c25992259941eb7e57b936157961b217a4fc8597829ddef0596d6c3cd86e1a" +dependencies = [ + "enum-map-derive", + "serde", +] + +[[package]] +name = "enum-map-derive" +version = "0.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2a4da76b3b6116d758c7ba93f7ec6a35d2e2cf24feda76c6e38a375f4d5c59f2" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "eyre" +version = "0.6.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4c2b6b5a29c02cdc822728b7d7b8ae1bab3e3b05d44522770ddd49722eeac7eb" +dependencies = [ + "indenter", + "once_cell", +] + +[[package]] +name = "fixedbitset" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80" + +[[package]] +name = "hashbrown" +version = "0.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888" + +[[package]] +name = "hashbrown" +version = "0.13.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "43a3c133739dddd0d2990f9a4bdf8eb4b21ef50e4851ca85ab661199821d510e" +dependencies = [ + "ahash", + "serde", +] + +[[package]] +name = "indenter" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ce23b50ad8242c51a442f3ff322d56b02f08852c77e4c0b4d3fd684abc89c683" + +[[package]] +name = "indexmap" +version = "1.9.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1885e79c1fc4b10f0e172c475f458b7f7b93061064d98c3293e98c5ba0c8b399" +dependencies = [ + "autocfg", + "hashbrown 0.12.3", +] + +[[package]] +name = "itoa" +version = "1.0.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fad582f4b9e86b6caa621cabeb0963332d92eea04729ab12892c2533951e6440" + +[[package]] +name = "jobserver" +version = "0.1.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "068b1ee6743e4d11fb9c6a1e6064b3693a1b600e7f5f5988047d98b3dc9fb90b" +dependencies = [ + "libc", +] + +[[package]] +name = "libc" +version = "0.2.139" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "201de327520df007757c1f0adce6e827fe8562fbc28bfd9c15571c66ca1f5f79" + +[[package]] +name = "libfuzzer-sys" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c8fff891139ee62800da71b7fd5b508d570b9ad95e614a53c6f453ca08366038" +dependencies = [ + "arbitrary", + "cc", + "once_cell", +] + +[[package]] +name = "num-bigint" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f93ab6289c7b344a8a9f60f88d80aa20032336fe78da341afc91c8a2341fc75f" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", + "serde", +] + +[[package]] +name = "num-integer" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "225d3389fb3509a24c93f5c29eb6bde2586b98d9f016636dff58d7c6f7569cd9" +dependencies = [ + "autocfg", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "578ede34cf02f8924ab9447f50c28075b4d3e5b269972345e7e0372b38c6cdcd" +dependencies = [ + "autocfg", +] + +[[package]] +name = "once_cell" +version = "1.17.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6f61fba1741ea2b3d6a1e3178721804bb716a68a6aeba1149b5d52e3d464ea66" + +[[package]] +name = "petgraph" +version = "0.6.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6d5014253a1331579ce62aa67443b4a658c5e7dd03d4bc6d302b94474888143" +dependencies = [ + "fixedbitset", + "indexmap", +] + +[[package]] +name = "proc-macro2" +version = "1.0.50" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6ef7d57beacfaf2d8aee5937dab7b7f28de3cb8b1828479bb5de2a7106f2bae2" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8856d8364d252a14d474036ea1358d63c9e6965c8e5c1885c18f73d70bff9c7b" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "ryu" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7b4b9743ed687d4b4bcedf9ff5eaa7398495ae14e61cba0a295704edbc7decde" + +[[package]] +name = "scoped-tls" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e1cf6437eb19a8f4a6cc0f7dca544973b0b78843adbfeb3683d1a94a0024a294" + +[[package]] +name = "serde" +version = "1.0.152" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bb7d1f0d3021d347a83e556fc4683dea2ea09d87bccdf88ff5c12545d89d5efb" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.152" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "af487d118eecd09402d70a5d72551860e788df87b464af30e5ea6a38c75c541e" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.91" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "877c235533714907a8c2464236f5c4b2a17262ef1bd71f38f35ea592c8da6883" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "smallvec" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a507befe795404456341dfab10cef66ead4c041f62b8b11bbb92bffe5d0953e0" +dependencies = [ + "serde", +] + +[[package]] +name = "syn" +version = "1.0.107" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1f4064b5b16e03ae50984a5a8ed5d4f8803e6bc1fd170a3cda91a1be4b18e3f5" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "thiserror" +version = "1.0.38" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6a9cd18aa97d5c45c6603caea1da6628790b37f7a34b6ca89522331c5180fed0" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.38" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fb327af4685e4d03fa8cbcf1716380da910eeb2bb8be417e7f9fd3fb164f36f" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "typed-arena" +version = "2.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6af6ae20167a9ece4bcb41af5b80f8a1f1df981f6391189ce00fd257af04126a" + +[[package]] +name = "unicode-ident" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "84a22b9f218b40614adcb3f4ff08b703773ad44fa9423e4e0d346d5db86e4ebc" + +[[package]] +name = "version_check" +version = "0.9.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f" diff --git a/register_allocator/fuzz/Cargo.toml b/register_allocator/fuzz/Cargo.toml new file mode 100644 index 0000000..6b0672c --- /dev/null +++ b/register_allocator/fuzz/Cargo.toml @@ -0,0 +1,27 @@ +[package] +name = "bigint-presentation-code-register-allocator-fuzz" +version = "0.0.0" +publish = false +edition = "2021" + +[package.metadata] +cargo-fuzz = true + +[dependencies] +libfuzzer-sys = "0.4.5" +bigint-presentation-code-register-allocator = { path = "../", features = ["fuzzing"] } + +# Prevent this from interfering with workspaces +[workspace] +members = ["."] + +[profile.release] +debug = true +debug-assertions = true +overflow-checks = true + +[[bin]] +name = "fn_new" +path = "fuzz_targets/fn_new.rs" +test = false +doc = false diff --git a/register_allocator/fuzz/fuzz_targets/fn_new.rs b/register_allocator/fuzz/fuzz_targets/fn_new.rs new file mode 100644 index 0000000..0dae950 --- /dev/null +++ b/register_allocator/fuzz/fuzz_targets/fn_new.rs @@ -0,0 +1,7 @@ +#![no_main] +use bigint_presentation_code_register_allocator::function::{FnFields, Function}; +use libfuzzer_sys::fuzz_target; + +fuzz_target!(|fields: FnFields| { + Function::new(fields).expect("should succeed"); +}); diff --git a/register_allocator/src/error.rs b/register_allocator/src/error.rs index d8e27d1..13c0414 100644 --- a/register_allocator/src/error.rs +++ b/register_allocator/src/error.rs @@ -231,6 +231,22 @@ pub enum Error { found: Option, expected: Option, }, + #[error( + "critical edges are not allowed: source block {src_block} has \ + multiple successors and target block {tgt_block} has multiple \ + predecessors: source block's terminating branch {branch_inst}" + )] + CriticalEdgeNotAllowed { + src_block: BlockIdx, + branch_inst: InstIdx, + tgt_block: BlockIdx, + }, } pub type Result = std::result::Result; + +impl From for arbitrary::Error { + fn from(_value: Error) -> Self { + Self::IncorrectFormat + } +} diff --git a/register_allocator/src/function.rs b/register_allocator/src/function.rs index 2a1e811..a9e88a0 100644 --- a/register_allocator/src/function.rs +++ b/register_allocator/src/function.rs @@ -606,7 +606,7 @@ impl Block { params, insts, preds, - immediate_dominator: _, + immediate_dominator: _, // validated by Function::new_with_global_state } = self; const _: () = assert!(BlockIdx::ENTRY_BLOCK.get() == 0); let expected_start = if block == BlockIdx::ENTRY_BLOCK { @@ -659,6 +659,13 @@ impl Block { tgt_block: block, }); } + if preds.len() > 1 && succs_and_params.len() > 1 { + return Err(Error::CriticalEdgeNotAllowed { + src_block: pred, + branch_inst: term_inst, + tgt_block: block, + }); + } } Ok(()) } diff --git a/register_allocator/src/fuzzing.rs b/register_allocator/src/fuzzing.rs new file mode 100644 index 0000000..2091a50 --- /dev/null +++ b/register_allocator/src/fuzzing.rs @@ -0,0 +1,64 @@ +use crate::{ + function::{Block, FnFields, SSAVal, SSAValDef}, + index::{BlockIdx, SSAValIdx}, + loc::Ty, +}; +use arbitrary::{Arbitrary, Error, Unstructured}; + +struct FnBuilder<'a, 'b> { + u: &'a mut Unstructured<'b>, + func: FnFields, +} + +impl FnBuilder<'_, '_> { + fn new_ssa_val(&mut self, ty: Ty, def: SSAValDef) -> SSAValIdx { + let retval = SSAValIdx::new(self.func.ssa_vals.len()); + self.func.ssa_vals.push(SSAVal { + ty, + def, + operand_uses: Default::default(), + branch_succ_param_uses: Default::default(), + }); + retval + } + fn run(&mut self) -> Result<(), Error> { + for block_idx in 0..self.u.int_in_range(1..=10)? { + let block_idx = BlockIdx::new(block_idx); + let mut params = Vec::new(); + for param_idx in 0..self.u.int_in_range(0..=10)? { + let ty = self.u.arbitrary()?; + params.push(self.new_ssa_val( + ty, + SSAValDef::BlockParam { + block: block_idx, + param_idx, + }, + )); + } + let insts = todo!(); + self.func.blocks.push(Block { + params, + insts, + preds: Default::default(), + immediate_dominator: Default::default(), + }); + } + Ok(()) + } +} + +impl<'a> Arbitrary<'a> for FnFields { + fn arbitrary(u: &mut Unstructured<'a>) -> Result { + let mut builder = FnBuilder { + u, + func: Self { + ssa_vals: Vec::new(), + insts: Vec::new(), + blocks: Vec::new(), + start_inst_to_block_map: Default::default(), + }, + }; + builder.run()?; + Ok(builder.func) + } +} diff --git a/register_allocator/src/lib.rs b/register_allocator/src/lib.rs index 4a96fe7..4a494fe 100644 --- a/register_allocator/src/lib.rs +++ b/register_allocator/src/lib.rs @@ -2,6 +2,8 @@ mod macros; pub mod error; pub mod function; +#[cfg(feature = "fuzzing")] +pub mod fuzzing; pub mod index; pub mod interned; pub mod loc; diff --git a/register_allocator/src/loc.rs b/register_allocator/src/loc.rs index eec4290..e6473ef 100644 --- a/register_allocator/src/loc.rs +++ b/register_allocator/src/loc.rs @@ -1,10 +1,22 @@ use crate::error::{Error, Result}; +use arbitrary::{size_hint, Arbitrary}; use enum_map::Enum; use serde::{Deserialize, Serialize}; use std::num::NonZeroU32; #[derive( - Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Enum, + Serialize, + Deserialize, + Copy, + Clone, + PartialEq, + Eq, + PartialOrd, + Ord, + Debug, + Hash, + Enum, + Arbitrary, )] #[repr(u8)] pub enum LocKind { @@ -36,7 +48,18 @@ impl LocKind { } #[derive( - Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Enum, + Serialize, + Deserialize, + Copy, + Clone, + PartialEq, + Eq, + PartialOrd, + Ord, + Debug, + Hash, + Enum, + Arbitrary, )] #[repr(u8)] pub enum BaseTy { @@ -61,6 +84,25 @@ impl BaseTy { Self::Ca | Self::VlMaxvl => nzu32_lit!(1), } } + + pub const fn loc_kinds(self) -> &'static [LocKind] { + match self { + BaseTy::Bits64 => &[LocKind::Gpr, LocKind::StackBits64], + BaseTy::Ca => &[LocKind::Ca], + BaseTy::VlMaxvl => &[LocKind::VlMaxvl], + } + } + + pub fn arbitrary_reg_len( + self, + u: &mut arbitrary::Unstructured<'_>, + ) -> arbitrary::Result { + Ok(NonZeroU32::new(u.int_in_range(1..=self.max_reg_len().get())?).unwrap()) + } + + pub fn arbitrary_reg_len_size_hint(depth: usize) -> (usize, Option) { + (0, NonZeroU32::size_hint(depth).1) + } } validated_fields! { @@ -72,6 +114,28 @@ validated_fields! { } } +impl<'a> Arbitrary<'a> for TyFields { + fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result { + let base_ty: BaseTy = u.arbitrary()?; + let reg_len = base_ty.arbitrary_reg_len(u)?; + Ok(Self { base_ty, reg_len }) + } + fn size_hint(depth: usize) -> (usize, Option) { + let base_ty = BaseTy::size_hint(depth); + let reg_len = BaseTy::arbitrary_reg_len_size_hint(depth); + size_hint::and(base_ty, reg_len) + } +} + +impl<'a> Arbitrary<'a> for Ty { + fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result { + Ok(Ty::new(u.arbitrary()?)?) + } + fn size_hint(depth: usize) -> (usize, Option) { + TyFields::size_hint(depth) + } +} + impl Ty { pub const fn new(fields: TyFields) -> Result { let TyFields { base_ty, reg_len } = fields; @@ -127,6 +191,35 @@ validated_fields! { } } +impl<'a> Arbitrary<'a> for LocFields { + fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result { + let kind: LocKind = u.arbitrary()?; + let reg_len = kind.base_ty().arbitrary_reg_len(u)?; + let start = Loc::arbitrary_start(kind, reg_len, u)?; + Ok(Self { + kind, + start, + reg_len, + }) + } + + fn size_hint(depth: usize) -> (usize, Option) { + let kind = LocKind::size_hint(depth); + let reg_len = BaseTy::arbitrary_reg_len_size_hint(depth); + let start = Loc::arbitrary_start_size_hint(depth); + size_hint::and(size_hint::and(kind, reg_len), start) + } +} + +impl<'a> Arbitrary<'a> for Loc { + fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result { + Ok(Loc::new(u.arbitrary()?)?) + } + fn size_hint(depth: usize) -> (usize, Option) { + LocFields::size_hint(depth) + } +} + impl LocFields { pub const fn ty(self) -> Result { Ty::new(TyFields { @@ -140,6 +233,28 @@ impl LocFields { } impl Loc { + pub fn arbitrary_with_ty( + ty: Ty, + u: &mut arbitrary::Unstructured<'_>, + ) -> arbitrary::Result { + let kind = *u.choose(ty.base_ty.loc_kinds())?; + let start = Self::arbitrary_start(kind, ty.reg_len, u)?; + Ok(Self::new(LocFields { + kind, + start, + reg_len: ty.reg_len, + })?) + } + pub fn arbitrary_start( + kind: LocKind, + reg_len: NonZeroU32, + u: &mut arbitrary::Unstructured<'_>, + ) -> arbitrary::Result { + u.int_in_range(0..=Loc::max_start(kind, reg_len)?) + } + pub fn arbitrary_start_size_hint(depth: usize) -> (usize, Option) { + (0, u32::size_hint(depth).1) + } pub const fn ty(self) -> Ty { const_unwrap_res!(self.0.ty(), "Loc can only be constructed with valid fields") } @@ -241,3 +356,32 @@ impl Loc { }), ]; } + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_base_ty_loc_kinds() { + for loc_kind in 0..LocKind::LENGTH { + let loc_kind = LocKind::from_usize(loc_kind); + let base_ty = loc_kind.base_ty(); + let loc_kinds = base_ty.loc_kinds(); + assert!( + loc_kinds.contains(&loc_kind), + "loc_kind:{loc_kind:?} base_ty:{base_ty:?} loc_kinds:{loc_kinds:?}" + ); + } + for base_ty in 0..BaseTy::LENGTH { + let base_ty = BaseTy::from_usize(base_ty); + let loc_kinds = base_ty.loc_kinds(); + for &loc_kind in loc_kinds { + assert_eq!( + loc_kind.base_ty(), + base_ty, + "loc_kind:{loc_kind:?} base_ty:{base_ty:?} loc_kinds:{loc_kinds:?}" + ); + } + } + } +} diff --git a/register_allocator/src/loc_set.rs b/register_allocator/src/loc_set.rs index 05344b7..8b7610a 100644 --- a/register_allocator/src/loc_set.rs +++ b/register_allocator/src/loc_set.rs @@ -51,7 +51,67 @@ where (b & a.borrow()) ^ a } +impl From for LocSet { + fn from(value: Loc) -> Self { + Self::from_iter([value]) + } +} + impl LocSet { + pub fn arbitrary_with_ty( + ty: Option, + u: &mut arbitrary::Unstructured<'_>, + ) -> arbitrary::Result { + let Some(ty) = ty else { + return Ok(Self::new()); + }; + let kinds = ty.base_ty.loc_kinds(); + type Mask = u128; + let kinds: Vec<_> = if kinds.len() > Mask::BITS as usize { + let chosen_kinds = kinds + .iter() + .zip(u.arbitrary_iter::()?) + .filter(|(_, cond)| !matches!(cond, Ok(false))) + .map(|(&kind, cond)| { + cond?; + Ok(kind) + }) + .collect::>>()?; + if chosen_kinds.is_empty() { + vec![*u.choose(kinds)?] + } else { + chosen_kinds + } + } else { + let max_mask = Mask::wrapping_shl(1, kinds.len() as u32).wrapping_sub(1); + let mask = u.int_in_range(1..=max_mask)?; // non-zero + kinds + .iter() + .enumerate() + .filter_map(|(idx, &kind)| { + if mask & (1 << idx) != 0 { + Some(kind) + } else { + None + } + }) + .collect() + }; + let mut starts = EnumMap::::default(); + let mut all_zero = true; + for kind in kinds { + let bit_count = Loc::max_start(kind, ty.reg_len)? + 1; + let byte_count = (bit_count + u8::BITS - 1) / u8::BITS; + let bytes = u.bytes(byte_count as usize)?; + starts[kind] = BigUint::from_bytes_le(bytes); + all_zero &= starts[kind].is_zero(); + } + if all_zero { + Ok(Loc::arbitrary_with_ty(ty, u)?.into()) + } else { + Ok(Self::from_parts(starts, Some(ty))?) + } + } pub fn starts(&self) -> &EnumMap { &self.starts } diff --git a/register_allocator/src/macros.rs b/register_allocator/src/macros.rs index 3f7a089..5386315 100644 --- a/register_allocator/src/macros.rs +++ b/register_allocator/src/macros.rs @@ -1,16 +1,28 @@ macro_rules! validated_fields { ( - #[fields_ty = $fields_ty:ident] + #[fields_ty = $fields_ty:ident $(, arbitrary = $Arbitrary:ident)? $(,)?] $(#[$meta:meta])* $vis:vis struct $ty:ident $body:tt ) => { $(#[$meta])* - #[derive(::serde::Serialize, ::serde::Deserialize)] + #[derive(::serde::Serialize, ::serde::Deserialize$(, $Arbitrary)?)] $vis struct $fields_ty $body $(#[$meta])* $vis struct $ty($fields_ty); + $(impl<'a> $Arbitrary<'a> for $ty { + fn arbitrary(u: &mut ::arbitrary::Unstructured<'a>) -> ::arbitrary::Result { + Ok(<$fields_ty as ::arbitrary::Arbitrary>::arbitrary(u)?.try_into()?) + } + fn arbitrary_take_rest(u: ::arbitrary::Unstructured<'a>) -> ::arbitrary::Result { + Ok(<$fields_ty as ::arbitrary::Arbitrary>::arbitrary_take_rest(u)?.try_into()?) + } + fn size_hint(depth: usize) -> (usize, Option) { + <$fields_ty as ::arbitrary::Arbitrary>::size_hint(depth) + } + })? + impl TryFrom<$fields_ty> for $ty { type Error = crate::error::Error; -- 2.30.2