wip adding register_allocator v3
authorJacob Lifshay <programmerjake@gmail.com>
Mon, 16 Jan 2023 07:04:32 +0000 (23:04 -0800)
committerJacob Lifshay <programmerjake@gmail.com>
Mon, 16 Jan 2023 07:16:00 +0000 (23:16 -0800)
12 files changed:
.gitignore
Cargo.lock [new file with mode: 0644]
Cargo.toml [new file with mode: 0644]
register_allocator/Cargo.toml [new file with mode: 0644]
register_allocator/README.md [new file with mode: 0644]
register_allocator/src/error.rs [new file with mode: 0644]
register_allocator/src/interned.rs [new file with mode: 0644]
register_allocator/src/lib.rs [new file with mode: 0644]
register_allocator/src/loc.rs [new file with mode: 0644]
register_allocator/src/loc_set.rs [new file with mode: 0644]
register_allocator/src/macros.rs [new file with mode: 0644]
register_allocator/src/main.rs [new file with mode: 0644]

index ac96be56b996d12e043412c715c57351caad35c2..f4a5d1e2ec3d21a5154e54f61e89b3e147efbf11 100644 (file)
@@ -6,3 +6,4 @@ __pycache__
 *.il
 /.vscode
 dumped_graphs
+/target
\ No newline at end of file
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644 (file)
index 0000000..987b7be
--- /dev/null
@@ -0,0 +1,181 @@
+# 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 = "bigint-presentation-code-register-allocator"
+version = "0.1.0"
+dependencies = [
+ "eyre",
+ "hashbrown",
+ "scoped-tls",
+ "serde",
+ "serde_json",
+ "thiserror",
+ "typed-arena",
+]
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[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 = "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 = "itoa"
+version = "1.0.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fad582f4b9e86b6caa621cabeb0963332d92eea04729ab12892c2533951e6440"
+
+[[package]]
+name = "once_cell"
+version = "1.17.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6f61fba1741ea2b3d6a1e3178721804bb716a68a6aeba1149b5d52e3d464ea66"
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.49"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "57a8eca9f9c4ffde41714334dee777596264c7825420f521abc92b5b5deb63a5"
+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 = "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/Cargo.toml b/Cargo.toml
new file mode 100644 (file)
index 0000000..d2f0ff5
--- /dev/null
@@ -0,0 +1,4 @@
+[workspace]
+members = [
+    "register_allocator",
+]
diff --git a/register_allocator/Cargo.toml b/register_allocator/Cargo.toml
new file mode 100644 (file)
index 0000000..b86c156
--- /dev/null
@@ -0,0 +1,15 @@
+[package]
+name = "bigint-presentation-code-register-allocator"
+version = "0.1.0"
+edition = "2021"
+publish = false
+license = "LGPLv3+"
+
+[dependencies]
+serde_json = "1.0.91"
+serde = { version = "1.0.152", features = ["derive"] }
+eyre = "0.6.8"
+thiserror = "1.0.38"
+typed-arena = "2.0.2"
+scoped-tls = "1.0.1"
+hashbrown = { version = "0.13.2", features = ["serde"] }
diff --git a/register_allocator/README.md b/register_allocator/README.md
new file mode 100644 (file)
index 0000000..8d17cde
--- /dev/null
@@ -0,0 +1,11 @@
+The old python register allocator is too slow and has poor abstractions and produces poor output because it starts by splitting all input variables with copies and hopes the register allocator can merge them back together, the new allocator will split as needed rather than splitting everything and hoping for the best.
+
+Register allocator written in Rust, since Python is just too slow -- we can't expect everyone working on our project to understand how the register allocator works (too much deep compiler magic (TM)), so not having it written in Python isn't as much of a problem.
+
+Rust also has better low-cost abstractions, allowing me to more easily write the register allocation algorithm.
+
+As part of this rewrite, I'm using a register allocation algorithm inspired by the regalloc2 crate and combining it with the previously tested algorithms for allocating ranges.
+
+The register allocator will not use PyO3 or Maturin, since those have caused problems with others needing help to figure out how they work.
+
+Instead, it will accept the problem in JSON on stdin, and write the solution or error as JSON on stdout. The python code will use a sub-process to call the register allocator.
\ No newline at end of file
diff --git a/register_allocator/src/error.rs b/register_allocator/src/error.rs
new file mode 100644 (file)
index 0000000..77dd128
--- /dev/null
@@ -0,0 +1,20 @@
+use crate::loc::BaseTy;
+use thiserror::Error;
+
+#[derive(Debug, Error)]
+pub enum Error {
+    #[error("can't create a vector of an only-scalar type: {base_ty:?}")]
+    TriedToCreateVectorOfOnlyScalarType { base_ty: BaseTy },
+    #[error("reg_len out of range")]
+    RegLenOutOfRange,
+    #[error("invalid reg_len")]
+    InvalidRegLen,
+    #[error("start not in valid range")]
+    StartNotInValidRange,
+    #[error("BaseTy mismatch")]
+    BaseTyMismatch,
+    #[error("invalid sub-Loc: offset and/or reg_len out of range")]
+    InvalidSubLocOutOfRange,
+}
+
+pub type Result<T, E = Error> = std::result::Result<T, E>;
diff --git a/register_allocator/src/interned.rs b/register_allocator/src/interned.rs
new file mode 100644 (file)
index 0000000..f28d6af
--- /dev/null
@@ -0,0 +1,317 @@
+use hashbrown::{hash_map::RawEntryMut, HashMap};
+use serde::Serialize;
+use std::{
+    cell::RefCell,
+    cmp::Ordering,
+    fmt,
+    hash::{Hash, Hasher},
+    ops::Deref,
+    rc::Rc,
+};
+
+#[derive(Clone)]
+pub struct Interned<T: ?Sized> {
+    ptr: Rc<T>,
+}
+
+impl<T: ?Sized> Deref for Interned<T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        self.ptr.deref()
+    }
+}
+
+impl<T: ?Sized> Hash for Interned<T> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        Rc::as_ptr(&self.ptr).hash(state);
+    }
+}
+
+impl<T: ?Sized> Eq for Interned<T> {}
+
+impl<T: ?Sized + fmt::Debug> fmt::Debug for Interned<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.ptr.fmt(f)
+    }
+}
+
+impl<T: ?Sized + fmt::Display> fmt::Display for Interned<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.ptr.fmt(f)
+    }
+}
+
+impl<T: ?Sized + Serialize> Serialize for Interned<T> {
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: serde::Serializer,
+    {
+        self.ptr.serialize(serializer)
+    }
+}
+
+impl<T: ?Sized> PartialEq for Interned<T> {
+    fn eq(&self, other: &Interned<T>) -> bool {
+        Rc::ptr_eq(&self.ptr, &other.ptr)
+    }
+}
+
+impl<T: ?Sized> PartialOrd for Interned<T> {
+    fn partial_cmp(&self, other: &Interned<T>) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl<T: ?Sized> Ord for Interned<T> {
+    fn cmp(&self, other: &Interned<T>) -> Ordering {
+        Rc::as_ptr(&self.ptr).cmp(&Rc::as_ptr(&other.ptr))
+    }
+}
+
+#[derive(Default)]
+struct Interners {
+    str: Interner<str>,
+}
+
+pub struct GlobalArena {
+    interners: Interners,
+}
+
+scoped_tls::scoped_thread_local!(static GLOBAL_ARENA: GlobalArena);
+
+impl GlobalArena {
+    pub fn scope<R>(f: impl FnOnce() -> R) -> R {
+        GLOBAL_ARENA.set(
+            &GlobalArena {
+                interners: Interners::default(),
+            },
+            f,
+        )
+    }
+    pub fn get<R>(f: impl for<'a> FnOnce(&'a GlobalArena) -> R) -> R {
+        GLOBAL_ARENA.with(f)
+    }
+}
+
+pub struct Interner<T: ?Sized>(RefCell<HashMap<Rc<T>, ()>>);
+
+impl<T: ?Sized> Default for Interner<T> {
+    fn default() -> Self {
+        Self(Default::default())
+    }
+}
+
+pub struct InternInput<
+    Input,
+    T: ?Sized + Eq + Hash,
+    B: FnOnce(&Input) -> &T,
+    R: FnOnce(Input) -> Rc<T>,
+> {
+    input: Input,
+    borrow: B,
+    into_rc: R,
+}
+
+impl<T: ?Sized + Eq + Hash> Interner<T> {
+    fn intern<Input>(
+        &self,
+        v: InternInput<Input, T, impl FnOnce(&Input) -> &T, impl FnOnce(Input) -> Rc<T>>,
+    ) -> Interned<T> {
+        let InternInput {
+            input,
+            borrow,
+            into_rc,
+        } = v;
+        match self.0.borrow_mut().raw_entry_mut().from_key(borrow(&input)) {
+            RawEntryMut::Occupied(entry) => Interned {
+                ptr: entry.key().clone(),
+            },
+            RawEntryMut::Vacant(entry) => Interned {
+                ptr: entry.insert(into_rc(input), ()).0.clone(),
+            },
+        }
+    }
+}
+
+pub trait InternTarget: Intern<Target = Self> + Hash + Eq {
+    fn get_interner(global_arena: &GlobalArena) -> &Interner<Self>;
+    fn into_interned(input: Self, global_arena: &GlobalArena) -> Interned<Self>
+    where
+        Self: Sized,
+    {
+        Self::get_interner(global_arena).intern(InternInput {
+            input,
+            borrow: |v| v,
+            into_rc: Rc::new,
+        })
+    }
+    fn rc_into_interned(input: Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
+        Self::get_interner(global_arena).intern(InternInput {
+            input,
+            borrow: |v| &**v,
+            into_rc: |v| v,
+        })
+    }
+    fn rc_to_interned(input: &Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
+        Self::get_interner(global_arena).intern(InternInput {
+            input,
+            borrow: |v| &***v,
+            into_rc: |v| v.clone(),
+        })
+    }
+}
+
+impl InternTarget for str {
+    fn get_interner(global_arena: &GlobalArena) -> &Interner<Self> {
+        &global_arena.interners.str
+    }
+}
+
+impl Intern for str {
+    type Target = str;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        v.into()
+    }
+
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        Self::get_interner(global_arena).intern(InternInput {
+            input: self,
+            borrow: |v| &**v,
+            into_rc: Self::to_rc_target,
+        })
+    }
+}
+
+impl Intern for &'_ str {
+    type Target = str;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        Rc::from(*v)
+    }
+
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        Self::Target::to_interned(self, global_arena)
+    }
+
+    fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+    where
+        Self: Sized,
+    {
+        Self::Target::to_interned(self, global_arena)
+    }
+}
+
+impl Intern for &'_ mut str {
+    type Target = str;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        Rc::from(&**v)
+    }
+
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        Self::Target::to_interned(self, global_arena)
+    }
+
+    fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+    where
+        Self: Sized,
+    {
+        Self::Target::to_interned(self, global_arena)
+    }
+}
+
+impl Intern for String {
+    type Target = str;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        Rc::from(&**v)
+    }
+
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        Self::Target::to_interned(self, global_arena)
+    }
+
+    fn into_rc_target(v: Self) -> Rc<Self::Target>
+    where
+        Self: Sized,
+    {
+        Rc::from(v)
+    }
+
+    fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+    where
+        Self: Sized,
+    {
+        Self::Target::to_interned(&self, global_arena)
+    }
+}
+
+pub trait Intern {
+    type Target: ?Sized + InternTarget;
+    fn into_rc_target(v: Self) -> Rc<Self::Target>
+    where
+        Self: Sized,
+    {
+        Self::to_rc_target(&v)
+    }
+    fn to_rc_target(v: &Self) -> Rc<Self::Target>;
+    fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+    where
+        Self: Sized,
+    {
+        <<Self as Intern>::Target as InternTarget>::rc_into_interned(
+            Self::into_rc_target(self),
+            global_arena,
+        )
+    }
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        Self::Target::rc_into_interned(Self::to_rc_target(self), global_arena)
+    }
+}
+
+impl<T: ?Sized + InternTarget> Intern for Rc<T> {
+    type Target = T;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        v.clone()
+    }
+
+    fn into_rc_target(v: Self) -> Rc<Self::Target>
+    where
+        Self: Sized,
+    {
+        v
+    }
+}
+
+impl<T: Clone + InternTarget> Intern for T {
+    type Target = T;
+
+    fn to_rc_target(v: &Self) -> Rc<Self::Target> {
+        v.clone().into()
+    }
+
+    fn into_rc_target(v: Self) -> Rc<Self::Target>
+    where
+        Self: Sized,
+    {
+        v.into()
+    }
+
+    fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
+    where
+        Self: Sized,
+    {
+        InternTarget::into_interned(self, global_arena)
+    }
+
+    fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
+        InternTarget::get_interner(global_arena).intern(InternInput {
+            input: self,
+            borrow: |v| &**v,
+            into_rc: |v| v.clone().into(),
+        })
+    }
+}
diff --git a/register_allocator/src/lib.rs b/register_allocator/src/lib.rs
new file mode 100644 (file)
index 0000000..d1b478f
--- /dev/null
@@ -0,0 +1,6 @@
+#[macro_use]
+mod macros;
+pub mod error;
+pub mod interned;
+pub mod loc;
+pub mod loc_set;
diff --git a/register_allocator/src/loc.rs b/register_allocator/src/loc.rs
new file mode 100644 (file)
index 0000000..1335533
--- /dev/null
@@ -0,0 +1,201 @@
+use crate::error::{Error, Result};
+use serde::{Deserialize, Serialize};
+use std::num::NonZeroU32;
+
+#[derive(Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
+#[repr(u8)]
+pub enum LocKind {
+    Gpr,
+    StackBits64,
+    Ca,
+    VlMaxvl,
+}
+
+impl LocKind {
+    /// since `==` doesn't work with enums in const context
+    pub const fn const_eq(self, other: Self) -> bool {
+        self as u8 == other as u8
+    }
+    pub const fn base_ty(self) -> BaseTy {
+        match self {
+            Self::Gpr | Self::StackBits64 => BaseTy::Bits64,
+            Self::Ca => BaseTy::Ca,
+            Self::VlMaxvl => BaseTy::VlMaxvl,
+        }
+    }
+
+    pub const fn loc_count(self) -> NonZeroU32 {
+        match self {
+            Self::StackBits64 => nzu32_lit!(512),
+            Self::Gpr | Self::Ca | Self::VlMaxvl => self.base_ty().max_reg_len(),
+        }
+    }
+}
+
+#[derive(Serialize, Deserialize, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
+#[repr(u8)]
+pub enum BaseTy {
+    Bits64,
+    Ca,
+    VlMaxvl,
+}
+
+impl BaseTy {
+    /// since `==` doesn't work with enums in const context
+    pub const fn const_eq(self, other: Self) -> bool {
+        self as u8 == other as u8
+    }
+
+    pub const fn only_scalar(self) -> bool {
+        self.max_reg_len().get() == 1
+    }
+
+    pub const fn max_reg_len(self) -> NonZeroU32 {
+        match self {
+            Self::Bits64 => nzu32_lit!(128),
+            Self::Ca | Self::VlMaxvl => nzu32_lit!(1),
+        }
+    }
+}
+
+validated_fields! {
+    #[fields_ty = TyFields]
+    #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
+    pub struct Ty {
+        pub base_ty: BaseTy,
+        pub reg_len: NonZeroU32,
+    }
+}
+
+impl Ty {
+    pub const fn new(fields: TyFields) -> Result<Ty> {
+        let TyFields { base_ty, reg_len } = fields;
+        if base_ty.only_scalar() && reg_len.get() != 1 {
+            Err(Error::TriedToCreateVectorOfOnlyScalarType { base_ty })
+        } else if reg_len.get() > base_ty.max_reg_len().get() {
+            Err(Error::RegLenOutOfRange)
+        } else {
+            Ok(Self(fields))
+        }
+    }
+}
+
+validated_fields! {
+    #[fields_ty = LocFields]
+    #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
+    pub struct Loc {
+        pub kind: LocKind,
+        pub start: u32,
+        pub reg_len: NonZeroU32,
+    }
+}
+
+impl LocFields {
+    pub const fn ty(self) -> Result<Ty> {
+        Ty::new(TyFields {
+            base_ty: self.kind.base_ty(),
+            reg_len: self.reg_len,
+        })
+    }
+    pub const fn stop(self) -> NonZeroU32 {
+        const_unwrap_opt!(self.reg_len.checked_add(self.start), "overflow")
+    }
+}
+
+impl Loc {
+    pub const fn ty(self) -> Ty {
+        const_unwrap_res!(self.0.ty(), "Loc can only be constructed with valid fields")
+    }
+    pub const fn new(fields: LocFields) -> Result<Loc> {
+        let LocFields {
+            kind,
+            start,
+            reg_len,
+        } = fields;
+
+        // validate Ty
+        const_try!(fields.ty());
+
+        let loc_count: u32 = kind.loc_count().get();
+        let Some(max_start) = loc_count.checked_sub(reg_len.get()) else {
+            return Err(Error::InvalidRegLen)
+        };
+        if start > max_start {
+            Err(Error::StartNotInValidRange)
+        } else {
+            Ok(Self(fields))
+        }
+    }
+    pub const fn conflicts(self, other: Loc) -> bool {
+        self.0.kind.const_eq(other.0.kind)
+            && self.0.start < other.0.stop().get()
+            && other.0.start < self.0.stop().get()
+    }
+    pub const fn get_sub_loc_at_offset(self, sub_loc_ty: Ty, offset: u32) -> Result<Self> {
+        if !sub_loc_ty.get().base_ty.const_eq(self.get().kind.base_ty()) {
+            return Err(Error::BaseTyMismatch);
+        }
+        let Some(stop) = sub_loc_ty.get().reg_len.checked_add(offset) else {
+            return Err(Error::InvalidSubLocOutOfRange)
+        };
+        if stop.get() > self.get().reg_len.get() {
+            Err(Error::InvalidSubLocOutOfRange)
+        } else {
+            Self::new(LocFields {
+                kind: self.get().kind,
+                start: self.get().start + offset,
+                reg_len: sub_loc_ty.get().reg_len,
+            })
+        }
+    }
+    /// get the Loc containing `self` such that:
+    /// `retval.get_sub_loc_at_offset(self.ty(), offset) == self`
+    /// and `retval.ty() == super_loc_ty`
+    pub const fn get_super_loc_with_self_at_offset(
+        self,
+        super_loc_ty: Ty,
+        offset: u32,
+    ) -> Result<Self> {
+        if !super_loc_ty
+            .get()
+            .base_ty
+            .const_eq(self.get().kind.base_ty())
+        {
+            return Err(Error::BaseTyMismatch);
+        }
+        let Some(stop) = self.get().reg_len.checked_add(offset) else {
+            return Err(Error::InvalidSubLocOutOfRange)
+        };
+        if stop.get() > super_loc_ty.get().reg_len.get() {
+            Err(Error::InvalidSubLocOutOfRange)
+        } else {
+            Self::new(LocFields {
+                kind: self.get().kind,
+                start: self.get().start - offset,
+                reg_len: super_loc_ty.get().reg_len,
+            })
+        }
+    }
+    pub const SPECIAL_GPRS: &[Loc] = &[
+        Loc(LocFields {
+            kind: LocKind::Gpr,
+            start: 0,
+            reg_len: nzu32_lit!(1),
+        }),
+        Loc(LocFields {
+            kind: LocKind::Gpr,
+            start: 1,
+            reg_len: nzu32_lit!(1),
+        }),
+        Loc(LocFields {
+            kind: LocKind::Gpr,
+            start: 2,
+            reg_len: nzu32_lit!(1),
+        }),
+        Loc(LocFields {
+            kind: LocKind::Gpr,
+            start: 13,
+            reg_len: nzu32_lit!(1),
+        }),
+    ];
+}
diff --git a/register_allocator/src/loc_set.rs b/register_allocator/src/loc_set.rs
new file mode 100644 (file)
index 0000000..5e51d63
--- /dev/null
@@ -0,0 +1,3 @@
+pub struct LocSet {
+    // FIXME: finish
+}
diff --git a/register_allocator/src/macros.rs b/register_allocator/src/macros.rs
new file mode 100644 (file)
index 0000000..9aabe39
--- /dev/null
@@ -0,0 +1,105 @@
+macro_rules! validated_fields {
+    (
+        #[fields_ty = $fields_ty:ident]
+        $(#[$meta:meta])*
+        $vis:vis struct $ty:ident $body:tt
+    ) => {
+        $(#[$meta])*
+        #[derive(::serde::Serialize, ::serde::Deserialize)]
+        $vis struct $fields_ty $body
+
+        $(#[$meta])*
+        $vis struct $ty($fields_ty);
+
+        impl TryFrom<$fields_ty> for $ty {
+            type Error = crate::error::Error;
+
+            fn try_from(fields: $fields_ty) -> Result<Self, Self::Error> {
+                $ty::new(fields)
+            }
+        }
+
+        impl From<$ty> for $fields_ty {
+            fn from(value: $ty) -> Self {
+                value.0
+            }
+        }
+
+        impl ::std::ops::Deref for $ty {
+            type Target = $fields_ty;
+
+            fn deref(&self) -> &Self::Target {
+                &self.0
+            }
+        }
+
+        impl $ty {
+            $vis const fn get(&self) -> &$fields_ty {
+                &self.0
+            }
+        }
+
+        impl ::serde::Serialize for $ty {
+            fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+            where
+                S: ::serde::Serializer,
+            {
+                self.0.serialize(serializer)
+            }
+        }
+
+        impl<'de> ::serde::Deserialize<'de> for $ty {
+            fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+            where
+                D: ::serde::Deserializer<'de>,
+            {
+                $fields_ty::deserialize(deserializer)?
+                    .try_into()
+                    .map_err(<D::Error as ::serde::de::Error>::custom)
+            }
+        }
+    };
+}
+
+macro_rules! const_unwrap_opt {
+    ($v:expr $(, $($msg:literal $(,)?)?)?) => {
+        match $v {
+            Some(v) => v,
+            None => panic!(concat!("tried to unwrap None", $($(": ", $msg,)?)?)),
+        }
+    };
+}
+
+macro_rules! const_unwrap_res {
+    ($v:expr $(, $($msg:literal $(,)?)?)?) => {
+        match $v {
+            Ok(v) => v,
+            Err(_e) => panic!(concat!("tried to unwrap Err", $($(": ", $msg,)?)?)),
+        }
+    };
+}
+
+macro_rules! const_try {
+    ($v:expr, Err($var:ident) => Err($err:expr) $(,)?) => {
+        match $v {
+            Ok(v) => v,
+            Err($var) => return Err($err),
+        }
+    };
+    ($v:expr $(,)?) => {
+        match $v {
+            Ok(v) => v,
+            Err(e) => return Err(e),
+        }
+    };
+}
+
+macro_rules! nzu32_lit {
+    ($v:literal) => {{
+        const V: NonZeroU32 = match NonZeroU32::new($v) {
+            Some(v) => v,
+            None => panic!("literal must not be zero"),
+        };
+        V
+    }};
+}
diff --git a/register_allocator/src/main.rs b/register_allocator/src/main.rs
new file mode 100644 (file)
index 0000000..d16f532
--- /dev/null
@@ -0,0 +1,5 @@
+use eyre::Result;
+
+fn main() -> Result<()> {
+    Ok(())
+}