Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

10 files changed, 2689 insertions, 0 deletions

diff --git a/third_party/rust/cranelift-entity-0.41.0/src/boxed_slice.rs b/third_party/rust/cranelift-entity-0.41.0/src/boxed_slice.rs
new file mode 100644
index 0000000000..2030c6b536
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/boxed_slice.rs
@@ -0,0 +1,312 @@
+//! Boxed slices for `PrimaryMap`.
+
+use crate::iter::{Iter, IterMut};
+use crate::keys::Keys;
+use crate::EntityRef;
+use core::marker::PhantomData;
+use core::ops::{Index, IndexMut};
+use core::slice;
+use std::boxed::Box;
+
+/// A slice mapping `K -> V` allocating dense entity references.
+///
+/// The `BoxedSlice` data structure uses the dense index space to implement a map with a boxed
+/// slice.
+#[derive(Debug, Clone)]
+pub struct BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    elems: Box<[V]>,
+    unused: PhantomData<K>,
+}
+
+impl<K, V> BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    /// Create a new slice from a raw pointer. A safer way to create slices is
+    /// to use `PrimaryMap::into_boxed_slice()`.
+    pub unsafe fn from_raw(raw: *mut [V]) -> Self {
+        Self {
+            elems: Box::from_raw(raw),
+            unused: PhantomData,
+        }
+    }
+
+    /// Check if `k` is a valid key in the map.
+    pub fn is_valid(&self, k: K) -> bool {
+        k.index() < self.elems.len()
+    }
+
+    /// Get the element at `k` if it exists.
+    pub fn get(&self, k: K) -> Option<&V> {
+        self.elems.get(k.index())
+    }
+
+    /// Get the element at `k` if it exists, mutable version.
+    pub fn get_mut(&mut self, k: K) -> Option<&mut V> {
+        self.elems.get_mut(k.index())
+    }
+
+    /// Is this map completely empty?
+    pub fn is_empty(&self) -> bool {
+        self.elems.is_empty()
+    }
+
+    /// Get the total number of entity references created.
+    pub fn len(&self) -> usize {
+        self.elems.len()
+    }
+
+    /// Iterate over all the keys in this map.
+    pub fn keys(&self) -> Keys<K> {
+        Keys::with_len(self.elems.len())
+    }
+
+    /// Iterate over all the values in this map.
+    pub fn values(&self) -> slice::Iter<V> {
+        self.elems.iter()
+    }
+
+    /// Iterate over all the values in this map, mutable edition.
+    pub fn values_mut(&mut self) -> slice::IterMut<V> {
+        self.elems.iter_mut()
+    }
+
+    /// Iterate over all the keys and values in this map.
+    pub fn iter(&self) -> Iter<K, V> {
+        Iter::new(self.elems.iter())
+    }
+
+    /// Iterate over all the keys and values in this map, mutable edition.
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        IterMut::new(self.elems.iter_mut())
+    }
+
+    /// Returns the last element that was inserted in the map.
+    pub fn last(&self) -> Option<&V> {
+        self.elems.last()
+    }
+}
+
+/// Immutable indexing into a `BoxedSlice`.
+/// The indexed value must be in the map.
+impl<K, V> Index<K> for BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    type Output = V;
+
+    fn index(&self, k: K) -> &V {
+        &self.elems[k.index()]
+    }
+}
+
+/// Mutable indexing into a `BoxedSlice`.
+impl<K, V> IndexMut<K> for BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    fn index_mut(&mut self, k: K) -> &mut V {
+        &mut self.elems[k.index()]
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    type Item = (K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        Iter::new(self.elems.iter())
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a mut BoxedSlice<K, V>
+where
+    K: EntityRef,
+{
+    type Item = (K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IterMut::new(self.elems.iter_mut())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::primary::PrimaryMap;
+    use std::vec::Vec;
+
+    // `EntityRef` impl for testing.
+    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
+    struct E(u32);
+
+    impl EntityRef for E {
+        fn new(i: usize) -> Self {
+            E(i as u32)
+        }
+        fn index(self) -> usize {
+            self.0 as usize
+        }
+    }
+
+    #[test]
+    fn basic() {
+        let r0 = E(0);
+        let r1 = E(1);
+        let p = PrimaryMap::<E, isize>::new();
+        let m = p.into_boxed_slice();
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, []);
+
+        assert!(!m.is_valid(r0));
+        assert!(!m.is_valid(r1));
+    }
+
+    #[test]
+    fn iter() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let mut m = p.into_boxed_slice();
+
+        let mut i = 0;
+        for (key, value) in &m {
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+        i = 0;
+        for (key_mut, value_mut) in m.iter_mut() {
+            assert_eq!(key_mut.index(), i);
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn iter_rev() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let mut m = p.into_boxed_slice();
+
+        let mut i = 2;
+        for (key, value) in m.iter().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+
+        i = 2;
+        for (key, value) in m.iter_mut().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+    }
+    #[test]
+    fn keys() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let m = p.into_boxed_slice();
+
+        let mut i = 0;
+        for key in m.keys() {
+            assert_eq!(key.index(), i);
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn keys_rev() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let m = p.into_boxed_slice();
+
+        let mut i = 2;
+        for key in m.keys().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+        }
+    }
+
+    #[test]
+    fn values() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let mut m = p.into_boxed_slice();
+
+        let mut i = 0;
+        for value in m.values() {
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+        i = 0;
+        for value_mut in m.values_mut() {
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn values_rev() {
+        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
+        p.push(12);
+        p.push(33);
+        let mut m = p.into_boxed_slice();
+
+        let mut i = 2;
+        for value in m.values().rev() {
+            i -= 1;
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+        i = 2;
+        for value_mut in m.values_mut().rev() {
+            i -= 1;
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+        }
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/iter.rs b/third_party/rust/cranelift-entity-0.41.0/src/iter.rs
new file mode 100644
index 0000000000..8c681023d2
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/iter.rs
@@ -0,0 +1,86 @@
+//! A double-ended iterator over entity references and entities.
+
+use crate::EntityRef;
+use core::iter::Enumerate;
+use core::marker::PhantomData;
+use core::slice;
+
+/// Iterate over all keys in order.
+pub struct Iter<'a, K: EntityRef, V>
+where
+    V: 'a,
+{
+    enumerate: Enumerate<slice::Iter<'a, V>>,
+    unused: PhantomData<K>,
+}
+
+impl<'a, K: EntityRef, V> Iter<'a, K, V> {
+    /// Create an `Iter` iterator that visits the `PrimaryMap` keys and values
+    /// of `iter`.
+    pub fn new(iter: slice::Iter<'a, V>) -> Self {
+        Self {
+            enumerate: iter.enumerate(),
+            unused: PhantomData,
+        }
+    }
+}
+
+impl<'a, K: EntityRef, V> Iterator for Iter<'a, K, V> {
+    type Item = (K, &'a V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.enumerate.next().map(|(i, v)| (K::new(i), v))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.enumerate.size_hint()
+    }
+}
+
+impl<'a, K: EntityRef, V> DoubleEndedIterator for Iter<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.enumerate.next_back().map(|(i, v)| (K::new(i), v))
+    }
+}
+
+impl<'a, K: EntityRef, V> ExactSizeIterator for Iter<'a, K, V> {}
+
+/// Iterate over all keys in order.
+pub struct IterMut<'a, K: EntityRef, V>
+where
+    V: 'a,
+{
+    enumerate: Enumerate<slice::IterMut<'a, V>>,
+    unused: PhantomData<K>,
+}
+
+impl<'a, K: EntityRef, V> IterMut<'a, K, V> {
+    /// Create an `IterMut` iterator that visits the `PrimaryMap` keys and values
+    /// of `iter`.
+    pub fn new(iter: slice::IterMut<'a, V>) -> Self {
+        Self {
+            enumerate: iter.enumerate(),
+            unused: PhantomData,
+        }
+    }
+}
+
+impl<'a, K: EntityRef, V> Iterator for IterMut<'a, K, V> {
+    type Item = (K, &'a mut V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.enumerate.next().map(|(i, v)| (K::new(i), v))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.enumerate.size_hint()
+    }
+}
+
+impl<'a, K: EntityRef, V> DoubleEndedIterator for IterMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.enumerate.next_back().map(|(i, v)| (K::new(i), v))
+    }
+}
+
+impl<'a, K: EntityRef, V> ExactSizeIterator for IterMut<'a, K, V> {}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/keys.rs b/third_party/rust/cranelift-entity-0.41.0/src/keys.rs
new file mode 100644
index 0000000000..bfbaa0cb90
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/keys.rs
@@ -0,0 +1,58 @@
+//! A double-ended iterator over entity references.
+//!
+//! When `core::iter::Step` is stabilized, `Keys` could be implemented as a wrapper around
+//! `core::ops::Range`, but for now, we implement it manually.
+
+use crate::EntityRef;
+use core::marker::PhantomData;
+
+/// Iterate over all keys in order.
+pub struct Keys<K: EntityRef> {
+    pos: usize,
+    rev_pos: usize,
+    unused: PhantomData<K>,
+}
+
+impl<K: EntityRef> Keys<K> {
+    /// Create a `Keys` iterator that visits `len` entities starting from 0.
+    pub fn with_len(len: usize) -> Self {
+        Self {
+            pos: 0,
+            rev_pos: len,
+            unused: PhantomData,
+        }
+    }
+}
+
+impl<K: EntityRef> Iterator for Keys<K> {
+    type Item = K;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.pos < self.rev_pos {
+            let k = K::new(self.pos);
+            self.pos += 1;
+            Some(k)
+        } else {
+            None
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let size = self.rev_pos - self.pos;
+        (size, Some(size))
+    }
+}
+
+impl<K: EntityRef> DoubleEndedIterator for Keys<K> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        if self.rev_pos > self.pos {
+            let k = K::new(self.rev_pos - 1);
+            self.rev_pos -= 1;
+            Some(k)
+        } else {
+            None
+        }
+    }
+}
+
+impl<K: EntityRef> ExactSizeIterator for Keys<K> {}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/lib.rs b/third_party/rust/cranelift-entity-0.41.0/src/lib.rs
new file mode 100644
index 0000000000..aa10264ab8
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/lib.rs
@@ -0,0 +1,152 @@
+//! Array-based data structures using densely numbered entity references as mapping keys.
+//!
+//! This crate defines a number of data structures based on arrays. The arrays are not indexed by
+//! `usize` as usual, but by *entity references* which are integers wrapped in new-types. This has
+//! a couple advantages:
+//!
+//! - Improved type safety. The various map and set types accept a specific key type, so there is
+//!   no confusion about the meaning of an array index, as there is with plain arrays.
+//! - Smaller indexes. The normal `usize` index is often 64 bits which is way too large for most
+//!   purposes. The entity reference types can be smaller, allowing for more compact data
+//!   structures.
+//!
+//! The `EntityRef` trait should be implemented by types to be used as indexed. The `entity_impl!`
+//! macro provides convenient defaults for types wrapping `u32` which is common.
+//!
+//! - [`PrimaryMap`](struct.PrimaryMap.html) is used to keep track of a vector of entities,
+//!   assigning a unique entity reference to each.
+//! - [`SecondaryMap`](struct.SecondaryMap.html) is used to associate secondary information to an
+//!   entity. The map is implemented as a simple vector, so it does not keep track of which
+//!   entities have been inserted. Instead, any unknown entities map to the default value.
+//! - [`SparseMap`](struct.SparseMap.html) is used to associate secondary information to a small
+//!   number of entities. It tracks accurately which entities have been inserted. This is a
+//!   specialized data structure which can use a lot of memory, so read the documentation before
+//!   using it.
+//! - [`EntitySet`](struct.EntitySet.html) is used to represent a secondary set of entities.
+//!   The set is implemented as a simple vector, so it does not keep track of which entities have
+//!   been inserted into the primary map. Instead, any unknown entities are not in the set.
+//! - [`EntityList`](struct.EntityList.html) is a compact representation of lists of entity
+//!   references allocated from an associated memory pool. It has a much smaller footprint than
+//!   `Vec`.
+
+#![deny(missing_docs, trivial_numeric_casts, unused_extern_crates)]
+#![warn(unused_import_braces)]
+#![cfg_attr(feature = "std", deny(unstable_features))]
+#![cfg_attr(feature = "clippy", plugin(clippy(conf_file = "../../clippy.toml")))]
+#![cfg_attr(
+    feature = "cargo-clippy",
+    allow(clippy::new_without_default, clippy::new_without_default_derive)
+)]
+#![cfg_attr(
+    feature = "cargo-clippy",
+    warn(
+        clippy::float_arithmetic,
+        clippy::mut_mut,
+        clippy::nonminimal_bool,
+        clippy::option_map_unwrap_or,
+        clippy::option_map_unwrap_or_else,
+        clippy::print_stdout,
+        clippy::unicode_not_nfc,
+        clippy::use_self
+    )
+)]
+#![no_std]
+
+#[cfg(not(feature = "std"))]
+#[macro_use]
+extern crate alloc as std;
+#[cfg(feature = "std")]
+#[macro_use]
+extern crate std;
+
+// Re-export core so that the macros works with both std and no_std crates
+#[doc(hidden)]
+pub extern crate core as __core;
+
+/// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key
+/// of an `SecondaryMap` or `SparseMap`.
+pub trait EntityRef: Copy + Eq {
+    /// Create a new entity reference from a small integer.
+    /// This should crash if the requested index is not representable.
+    fn new(_: usize) -> Self;
+
+    /// Get the index that was used to create this entity reference.
+    fn index(self) -> usize;
+}
+
+/// Macro which provides the common implementation of a 32-bit entity reference.
+#[macro_export]
+macro_rules! entity_impl {
+    // Basic traits.
+    ($entity:ident) => {
+        impl $crate::EntityRef for $entity {
+            fn new(index: usize) -> Self {
+                debug_assert!(index < ($crate::__core::u32::MAX as usize));
+                $entity(index as u32)
+            }
+
+            fn index(self) -> usize {
+                self.0 as usize
+            }
+        }
+
+        impl $crate::packed_option::ReservedValue for $entity {
+            fn reserved_value() -> $entity {
+                $entity($crate::__core::u32::MAX)
+            }
+        }
+
+        impl $entity {
+            /// Return the underlying index value as a `u32`.
+            #[allow(dead_code)]
+            pub fn from_u32(x: u32) -> Self {
+                debug_assert!(x < $crate::__core::u32::MAX);
+                $entity(x)
+            }
+
+            /// Return the underlying index value as a `u32`.
+            #[allow(dead_code)]
+            pub fn as_u32(self) -> u32 {
+                self.0
+            }
+        }
+    };
+
+    // Include basic `Display` impl using the given display prefix.
+    // Display an `Ebb` reference as "ebb12".
+    ($entity:ident, $display_prefix:expr) => {
+        entity_impl!($entity);
+
+        impl $crate::__core::fmt::Display for $entity {
+            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
+                write!(f, concat!($display_prefix, "{}"), self.0)
+            }
+        }
+
+        impl $crate::__core::fmt::Debug for $entity {
+            fn fmt(&self, f: &mut $crate::__core::fmt::Formatter) -> $crate::__core::fmt::Result {
+                (self as &dyn $crate::__core::fmt::Display).fmt(f)
+            }
+        }
+    };
+}
+
+pub mod packed_option;
+
+mod boxed_slice;
+mod iter;
+mod keys;
+mod list;
+mod map;
+mod primary;
+mod set;
+mod sparse;
+
+pub use self::boxed_slice::BoxedSlice;
+pub use self::iter::{Iter, IterMut};
+pub use self::keys::Keys;
+pub use self::list::{EntityList, ListPool};
+pub use self::map::SecondaryMap;
+pub use self::primary::PrimaryMap;
+pub use self::set::EntitySet;
+pub use self::sparse::{SparseMap, SparseMapValue, SparseSet};
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/list.rs b/third_party/rust/cranelift-entity-0.41.0/src/list.rs
new file mode 100644
index 0000000000..009b3d70b1
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/list.rs
@@ -0,0 +1,707 @@
+//! Small lists of entity references.
+use crate::packed_option::ReservedValue;
+use crate::EntityRef;
+use core::marker::PhantomData;
+use core::mem;
+use std::vec::Vec;
+
+/// A small list of entity references allocated from a pool.
+///
+/// An `EntityList<T>` type provides similar functionality to `Vec<T>`, but with some important
+/// differences in the implementation:
+///
+/// 1. Memory is allocated from a `ListPool<T>` instead of the global heap.
+/// 2. The footprint of an entity list is 4 bytes, compared with the 24 bytes for `Vec<T>`.
+/// 3. An entity list doesn't implement `Drop`, leaving it to the pool to manage memory.
+///
+/// The list pool is intended to be used as a LIFO allocator. After building up a larger data
+/// structure with many list references, the whole thing can be discarded quickly by clearing the
+/// pool.
+///
+/// # Safety
+///
+/// Entity lists are not as safe to use as `Vec<T>`, but they never jeopardize Rust's memory safety
+/// guarantees. These are the problems to be aware of:
+///
+/// - If you lose track of an entity list, its memory won't be recycled until the pool is cleared.
+///   This can cause the pool to grow very large with leaked lists.
+/// - If entity lists are used after their pool is cleared, they may contain garbage data, and
+///   modifying them may corrupt other lists in the pool.
+/// - If an entity list is used with two different pool instances, both pools are likely to become
+///   corrupted.
+///
+/// Entity lists can be cloned, but that operation should only be used as part of cloning the whole
+/// function they belong to. *Cloning an entity list does not allocate new memory for the clone*.
+/// It creates an alias of the same memory.
+///
+/// Entity lists cannot be hashed and compared for equality because it's not possible to compare the
+/// contents of the list without the pool reference.
+///
+/// # Implementation
+///
+/// The `EntityList` itself is designed to have the smallest possible footprint. This is important
+/// because it is used inside very compact data structures like `InstructionData`. The list
+/// contains only a 32-bit index into the pool's memory vector, pointing to the first element of
+/// the list.
+///
+/// The pool is just a single `Vec<T>` containing all of the allocated lists. Each list is
+/// represented as three contiguous parts:
+///
+/// 1. The number of elements in the list.
+/// 2. The list elements.
+/// 3. Excess capacity elements.
+///
+/// The total size of the three parts is always a power of two, and the excess capacity is always
+/// as small as possible. This means that shrinking a list may cause the excess capacity to shrink
+/// if a smaller power-of-two size becomes available.
+///
+/// Both growing and shrinking a list may cause it to be reallocated in the pool vector.
+///
+/// The index stored in an `EntityList` points to part 2, the list elements. The value 0 is
+/// reserved for the empty list which isn't allocated in the vector.
+#[derive(Clone, Debug)]
+pub struct EntityList<T: EntityRef + ReservedValue> {
+    index: u32,
+    unused: PhantomData<T>,
+}
+
+/// Create an empty list.
+impl<T: EntityRef + ReservedValue> Default for EntityList<T> {
+    fn default() -> Self {
+        Self {
+            index: 0,
+            unused: PhantomData,
+        }
+    }
+}
+
+/// A memory pool for storing lists of `T`.
+#[derive(Clone, Debug)]
+pub struct ListPool<T: EntityRef + ReservedValue> {
+    // The main array containing the lists.
+    data: Vec<T>,
+
+    // Heads of the free lists, one for each size class.
+    free: Vec<usize>,
+}
+
+/// Lists are allocated in sizes that are powers of two, starting from 4.
+/// Each power of two is assigned a size class number, so the size is `4 << SizeClass`.
+type SizeClass = u8;
+
+/// Get the size of a given size class. The size includes the length field, so the maximum list
+/// length is one less than the class size.
+fn sclass_size(sclass: SizeClass) -> usize {
+    4 << sclass
+}
+
+/// Get the size class to use for a given list length.
+/// This always leaves room for the length element in addition to the list elements.
+fn sclass_for_length(len: usize) -> SizeClass {
+    30 - (len as u32 | 3).leading_zeros() as SizeClass
+}
+
+/// Is `len` the minimum length in its size class?
+fn is_sclass_min_length(len: usize) -> bool {
+    len > 3 && len.is_power_of_two()
+}
+
+impl<T: EntityRef + ReservedValue> ListPool<T> {
+    /// Create a new list pool.
+    pub fn new() -> Self {
+        Self {
+            data: Vec::new(),
+            free: Vec::new(),
+        }
+    }
+
+    /// Clear the pool, forgetting about all lists that use it.
+    ///
+    /// This invalidates any existing entity lists that used this pool to allocate memory.
+    ///
+    /// The pool's memory is not released to the operating system, but kept around for faster
+    /// allocation in the future.
+    pub fn clear(&mut self) {
+        self.data.clear();
+        self.free.clear();
+    }
+
+    /// Read the length of a list field, if it exists.
+    fn len_of(&self, list: &EntityList<T>) -> Option<usize> {
+        let idx = list.index as usize;
+        // `idx` points at the list elements. The list length is encoded in the element immediately
+        // before the list elements.
+        //
+        // The `wrapping_sub` handles the special case 0, which is the empty list. This way, the
+        // cost of the bounds check that we have to pay anyway is co-opted to handle the special
+        // case of the empty list.
+        self.data.get(idx.wrapping_sub(1)).map(|len| len.index())
+    }
+
+    /// Allocate a storage block with a size given by `sclass`.
+    ///
+    /// Returns the first index of an available segment of `self.data` containing
+    /// `sclass_size(sclass)` elements. The allocated memory is filled with reserved
+    /// values.
+    fn alloc(&mut self, sclass: SizeClass) -> usize {
+        // First try the free list for this size class.
+        match self.free.get(sclass as usize).cloned() {
+            Some(head) if head > 0 => {
+                // The free list pointers are offset by 1, using 0 to terminate the list.
+                // A block on the free list has two entries: `[ 0, next ]`.
+                // The 0 is where the length field would be stored for a block in use.
+                // The free list heads and the next pointer point at the `next` field.
+                self.free[sclass as usize] = self.data[head].index();
+                head - 1
+            }
+            _ => {
+                // Nothing on the free list. Allocate more memory.
+                let offset = self.data.len();
+                self.data
+                    .resize(offset + sclass_size(sclass), T::reserved_value());
+                offset
+            }
+        }
+    }
+
+    /// Free a storage block with a size given by `sclass`.
+    ///
+    /// This must be a block that was previously allocated by `alloc()` with the same size class.
+    fn free(&mut self, block: usize, sclass: SizeClass) {
+        let sclass = sclass as usize;
+
+        // Make sure we have a free-list head for `sclass`.
+        if self.free.len() <= sclass {
+            self.free.resize(sclass + 1, 0);
+        }
+
+        // Make sure the length field is cleared.
+        self.data[block] = T::new(0);
+        // Insert the block on the free list which is a single linked list.
+        self.data[block + 1] = T::new(self.free[sclass]);
+        self.free[sclass] = block + 1
+    }
+
+    /// Returns two mutable slices representing the two requested blocks.
+    ///
+    /// The two returned slices can be longer than the blocks. Each block is located at the front
+    /// of the respective slice.
+    fn mut_slices(&mut self, block0: usize, block1: usize) -> (&mut [T], &mut [T]) {
+        if block0 < block1 {
+            let (s0, s1) = self.data.split_at_mut(block1);
+            (&mut s0[block0..], s1)
+        } else {
+            let (s1, s0) = self.data.split_at_mut(block0);
+            (s0, &mut s1[block1..])
+        }
+    }
+
+    /// Reallocate a block to a different size class.
+    ///
+    /// Copy `elems_to_copy` elements from the old to the new block.
+    fn realloc(
+        &mut self,
+        block: usize,
+        from_sclass: SizeClass,
+        to_sclass: SizeClass,
+        elems_to_copy: usize,
+    ) -> usize {
+        debug_assert!(elems_to_copy <= sclass_size(from_sclass));
+        debug_assert!(elems_to_copy <= sclass_size(to_sclass));
+        let new_block = self.alloc(to_sclass);
+
+        if elems_to_copy > 0 {
+            let (old, new) = self.mut_slices(block, new_block);
+            (&mut new[0..elems_to_copy]).copy_from_slice(&old[0..elems_to_copy]);
+        }
+
+        self.free(block, from_sclass);
+        new_block
+    }
+}
+
+impl<T: EntityRef + ReservedValue> EntityList<T> {
+    /// Create a new empty list.
+    pub fn new() -> Self {
+        Default::default()
+    }
+
+    /// Create a new list with the contents initialized from a slice.
+    pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self {
+        let len = slice.len();
+        if len == 0 {
+            return Self::new();
+        }
+
+        let block = pool.alloc(sclass_for_length(len));
+        pool.data[block] = T::new(len);
+        pool.data[block + 1..=block + len].copy_from_slice(slice);
+
+        Self {
+            index: (block + 1) as u32,
+            unused: PhantomData,
+        }
+    }
+
+    /// Returns `true` if the list has a length of 0.
+    pub fn is_empty(&self) -> bool {
+        // 0 is a magic value for the empty list. Any list in the pool array must have a positive
+        // length.
+        self.index == 0
+    }
+
+    /// Get the number of elements in the list.
+    pub fn len(&self, pool: &ListPool<T>) -> usize {
+        // Both the empty list and any invalidated old lists will return `None`.
+        pool.len_of(self).unwrap_or(0)
+    }
+
+    /// Returns `true` if the list is valid
+    pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
+        // We consider an empty list to be valid
+        self.is_empty() || pool.len_of(self) != None
+    }
+
+    /// Get the list as a slice.
+    pub fn as_slice<'a>(&'a self, pool: &'a ListPool<T>) -> &'a [T] {
+        let idx = self.index as usize;
+        match pool.len_of(self) {
+            None => &[],
+            Some(len) => &pool.data[idx..idx + len],
+        }
+    }
+
+    /// Get a single element from the list.
+    pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
+        self.as_slice(pool).get(index).cloned()
+    }
+
+    /// Get the first element from the list.
+    pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
+        if self.is_empty() {
+            None
+        } else {
+            Some(pool.data[self.index as usize])
+        }
+    }
+
+    /// Get the list as a mutable slice.
+    pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T] {
+        let idx = self.index as usize;
+        match pool.len_of(self) {
+            None => &mut [],
+            Some(len) => &mut pool.data[idx..idx + len],
+        }
+    }
+
+    /// Get a mutable reference to a single element from the list.
+    pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
+        self.as_mut_slice(pool).get_mut(index)
+    }
+
+    /// Removes all elements from the list.
+    ///
+    /// The memory used by the list is put back in the pool.
+    pub fn clear(&mut self, pool: &mut ListPool<T>) {
+        let idx = self.index as usize;
+        match pool.len_of(self) {
+            None => debug_assert_eq!(idx, 0, "Invalid pool"),
+            Some(len) => pool.free(idx - 1, sclass_for_length(len)),
+        }
+        // Switch back to the empty list representation which has no storage.
+        self.index = 0;
+    }
+
+    /// Take all elements from this list and return them as a new list. Leave this list empty.
+    ///
+    /// This is the equivalent of `Option::take()`.
+    pub fn take(&mut self) -> Self {
+        mem::replace(self, Default::default())
+    }
+
+    /// Appends an element to the back of the list.
+    /// Returns the index where the element was inserted.
+    pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
+        let idx = self.index as usize;
+        match pool.len_of(self) {
+            None => {
+                // This is an empty list. Allocate a block and set length=1.
+                debug_assert_eq!(idx, 0, "Invalid pool");
+                let block = pool.alloc(sclass_for_length(1));
+                pool.data[block] = T::new(1);
+                pool.data[block + 1] = element;
+                self.index = (block + 1) as u32;
+                0
+            }
+            Some(len) => {
+                // Do we need to reallocate?
+                let new_len = len + 1;
+                let block;
+                if is_sclass_min_length(new_len) {
+                    // Reallocate, preserving length + all old elements.
+                    let sclass = sclass_for_length(len);
+                    block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
+                    self.index = (block + 1) as u32;
+                } else {
+                    block = idx - 1;
+                }
+                pool.data[block + new_len] = element;
+                pool.data[block] = T::new(new_len);
+                len
+            }
+        }
+    }
+
+    /// Grow list by adding `count` reserved-value elements at the end.
+    ///
+    /// Returns a mutable slice representing the whole list.
+    fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
+        let idx = self.index as usize;
+        let new_len;
+        let block;
+        match pool.len_of(self) {
+            None => {
+                // This is an empty list. Allocate a block.
+                debug_assert_eq!(idx, 0, "Invalid pool");
+                if count == 0 {
+                    return &mut [];
+                }
+                new_len = count;
+                block = pool.alloc(sclass_for_length(new_len));
+                self.index = (block + 1) as u32;
+            }
+            Some(len) => {
+                // Do we need to reallocate?
+                let sclass = sclass_for_length(len);
+                new_len = len + count;
+                let new_sclass = sclass_for_length(new_len);
+                if new_sclass != sclass {
+                    block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
+                    self.index = (block + 1) as u32;
+                } else {
+                    block = idx - 1;
+                }
+            }
+        }
+        pool.data[block] = T::new(new_len);
+        &mut pool.data[block + 1..block + 1 + new_len]
+    }
+
+    /// Appends multiple elements to the back of the list.
+    pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
+    where
+        I: IntoIterator<Item = T>,
+    {
+        // TODO: use `size_hint()` to reduce reallocations.
+        for x in elements {
+            self.push(x, pool);
+        }
+    }
+
+    /// Inserts an element as position `index` in the list, shifting all elements after it to the
+    /// right.
+    pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
+        // Increase size by 1.
+        self.push(element, pool);
+
+        // Move tail elements.
+        let seq = self.as_mut_slice(pool);
+        if index < seq.len() {
+            let tail = &mut seq[index..];
+            for i in (1..tail.len()).rev() {
+                tail[i] = tail[i - 1];
+            }
+            tail[0] = element;
+        } else {
+            debug_assert_eq!(index, seq.len());
+        }
+    }
+
+    /// Removes the element at position `index` from the list. Potentially linear complexity.
+    pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
+        let len;
+        {
+            let seq = self.as_mut_slice(pool);
+            len = seq.len();
+            debug_assert!(index < len);
+
+            // Copy elements down.
+            for i in index..len - 1 {
+                seq[i] = seq[i + 1];
+            }
+        }
+
+        // Check if we deleted the last element.
+        if len == 1 {
+            self.clear(pool);
+            return;
+        }
+
+        // Do we need to reallocate to a smaller size class?
+        let mut block = self.index as usize - 1;
+        if is_sclass_min_length(len) {
+            let sclass = sclass_for_length(len);
+            block = pool.realloc(block, sclass, sclass - 1, len);
+            self.index = (block + 1) as u32;
+        }
+
+        // Finally adjust the length.
+        pool.data[block] = T::new(len - 1);
+    }
+
+    /// Removes the element at `index` in constant time by switching it with the last element of
+    /// the list.
+    pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
+        let len = self.len(pool);
+        debug_assert!(index < len);
+        if index == len - 1 {
+            self.remove(index, pool);
+        } else {
+            {
+                let seq = self.as_mut_slice(pool);
+                seq.swap(index, len - 1);
+            }
+            self.remove(len - 1, pool);
+        }
+    }
+
+    /// Grow the list by inserting `count` elements at `index`.
+    ///
+    /// The new elements are not initialized, they will contain whatever happened to be in memory.
+    /// Since the memory comes from the pool, this will be either zero entity references or
+    /// whatever where in a previously deallocated list.
+    pub fn grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>) {
+        let data = self.grow(count, pool);
+
+        // Copy elements after `index` up.
+        for i in (index + count..data.len()).rev() {
+            data[i] = data[i - count];
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use super::{sclass_for_length, sclass_size};
+    use crate::EntityRef;
+
+    /// An opaque reference to an instruction in a function.
+    #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
+    pub struct Inst(u32);
+    entity_impl!(Inst, "inst");
+
+    #[test]
+    fn size_classes() {
+        assert_eq!(sclass_size(0), 4);
+        assert_eq!(sclass_for_length(0), 0);
+        assert_eq!(sclass_for_length(1), 0);
+        assert_eq!(sclass_for_length(2), 0);
+        assert_eq!(sclass_for_length(3), 0);
+        assert_eq!(sclass_for_length(4), 1);
+        assert_eq!(sclass_for_length(7), 1);
+        assert_eq!(sclass_for_length(8), 2);
+        assert_eq!(sclass_size(1), 8);
+        for l in 0..300 {
+            assert!(sclass_size(sclass_for_length(l)) >= l + 1);
+        }
+    }
+
+    #[test]
+    fn block_allocator() {
+        let mut pool = ListPool::<Inst>::new();
+        let b1 = pool.alloc(0);
+        let b2 = pool.alloc(1);
+        let b3 = pool.alloc(0);
+        assert_ne!(b1, b2);
+        assert_ne!(b1, b3);
+        assert_ne!(b2, b3);
+        pool.free(b2, 1);
+        let b2a = pool.alloc(1);
+        let b2b = pool.alloc(1);
+        assert_ne!(b2a, b2b);
+        // One of these should reuse the freed block.
+        assert!(b2a == b2 || b2b == b2);
+
+        // Check the free lists for a size class smaller than the largest seen so far.
+        pool.free(b1, 0);
+        pool.free(b3, 0);
+        let b1a = pool.alloc(0);
+        let b3a = pool.alloc(0);
+        assert_ne!(b1a, b3a);
+        assert!(b1a == b1 || b1a == b3);
+        assert!(b3a == b1 || b3a == b3);
+    }
+
+    #[test]
+    fn empty_list() {
+        let pool = &mut ListPool::<Inst>::new();
+        let mut list = EntityList::<Inst>::default();
+        {
+            let ilist = &list;
+            assert!(ilist.is_empty());
+            assert_eq!(ilist.len(pool), 0);
+            assert_eq!(ilist.as_slice(pool), &[]);
+            assert_eq!(ilist.get(0, pool), None);
+            assert_eq!(ilist.get(100, pool), None);
+        }
+        assert_eq!(list.as_mut_slice(pool), &[]);
+        assert_eq!(list.get_mut(0, pool), None);
+        assert_eq!(list.get_mut(100, pool), None);
+
+        list.clear(pool);
+        assert!(list.is_empty());
+        assert_eq!(list.len(pool), 0);
+        assert_eq!(list.as_slice(pool), &[]);
+        assert_eq!(list.first(pool), None);
+    }
+
+    #[test]
+    fn from_slice() {
+        let pool = &mut ListPool::<Inst>::new();
+
+        let list = EntityList::<Inst>::from_slice(&[Inst(0), Inst(1)], pool);
+        assert!(!list.is_empty());
+        assert_eq!(list.len(pool), 2);
+        assert_eq!(list.as_slice(pool), &[Inst(0), Inst(1)]);
+        assert_eq!(list.get(0, pool), Some(Inst(0)));
+        assert_eq!(list.get(100, pool), None);
+
+        let list = EntityList::<Inst>::from_slice(&[], pool);
+        assert!(list.is_empty());
+        assert_eq!(list.len(pool), 0);
+        assert_eq!(list.as_slice(pool), &[]);
+        assert_eq!(list.get(0, pool), None);
+        assert_eq!(list.get(100, pool), None);
+    }
+
+    #[test]
+    fn push() {
+        let pool = &mut ListPool::<Inst>::new();
+        let mut list = EntityList::<Inst>::default();
+
+        let i1 = Inst::new(1);
+        let i2 = Inst::new(2);
+        let i3 = Inst::new(3);
+        let i4 = Inst::new(4);
+
+        assert_eq!(list.push(i1, pool), 0);
+        assert_eq!(list.len(pool), 1);
+        assert!(!list.is_empty());
+        assert_eq!(list.as_slice(pool), &[i1]);
+        assert_eq!(list.first(pool), Some(i1));
+        assert_eq!(list.get(0, pool), Some(i1));
+        assert_eq!(list.get(1, pool), None);
+
+        assert_eq!(list.push(i2, pool), 1);
+        assert_eq!(list.len(pool), 2);
+        assert!(!list.is_empty());
+        assert_eq!(list.as_slice(pool), &[i1, i2]);
+        assert_eq!(list.first(pool), Some(i1));
+        assert_eq!(list.get(0, pool), Some(i1));
+        assert_eq!(list.get(1, pool), Some(i2));
+        assert_eq!(list.get(2, pool), None);
+
+        assert_eq!(list.push(i3, pool), 2);
+        assert_eq!(list.len(pool), 3);
+        assert!(!list.is_empty());
+        assert_eq!(list.as_slice(pool), &[i1, i2, i3]);
+        assert_eq!(list.first(pool), Some(i1));
+        assert_eq!(list.get(0, pool), Some(i1));
+        assert_eq!(list.get(1, pool), Some(i2));
+        assert_eq!(list.get(2, pool), Some(i3));
+        assert_eq!(list.get(3, pool), None);
+
+        // This triggers a reallocation.
+        assert_eq!(list.push(i4, pool), 3);
+        assert_eq!(list.len(pool), 4);
+        assert!(!list.is_empty());
+        assert_eq!(list.as_slice(pool), &[i1, i2, i3, i4]);
+        assert_eq!(list.first(pool), Some(i1));
+        assert_eq!(list.get(0, pool), Some(i1));
+        assert_eq!(list.get(1, pool), Some(i2));
+        assert_eq!(list.get(2, pool), Some(i3));
+        assert_eq!(list.get(3, pool), Some(i4));
+        assert_eq!(list.get(4, pool), None);
+
+        list.extend([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
+        assert_eq!(list.len(pool), 12);
+        assert_eq!(
+            list.as_slice(pool),
+            &[i1, i2, i3, i4, i1, i1, i2, i2, i3, i3, i4, i4]
+        );
+    }
+
+    #[test]
+    fn insert_remove() {
+        let pool = &mut ListPool::<Inst>::new();
+        let mut list = EntityList::<Inst>::default();
+
+        let i1 = Inst::new(1);
+        let i2 = Inst::new(2);
+        let i3 = Inst::new(3);
+        let i4 = Inst::new(4);
+
+        list.insert(0, i4, pool);
+        assert_eq!(list.as_slice(pool), &[i4]);
+
+        list.insert(0, i3, pool);
+        assert_eq!(list.as_slice(pool), &[i3, i4]);
+
+        list.insert(2, i2, pool);
+        assert_eq!(list.as_slice(pool), &[i3, i4, i2]);
+
+        list.insert(2, i1, pool);
+        assert_eq!(list.as_slice(pool), &[i3, i4, i1, i2]);
+
+        list.remove(3, pool);
+        assert_eq!(list.as_slice(pool), &[i3, i4, i1]);
+
+        list.remove(2, pool);
+        assert_eq!(list.as_slice(pool), &[i3, i4]);
+
+        list.remove(0, pool);
+        assert_eq!(list.as_slice(pool), &[i4]);
+
+        list.remove(0, pool);
+        assert_eq!(list.as_slice(pool), &[]);
+        assert!(list.is_empty());
+    }
+
+    #[test]
+    fn growing() {
+        let pool = &mut ListPool::<Inst>::new();
+        let mut list = EntityList::<Inst>::default();
+
+        let i1 = Inst::new(1);
+        let i2 = Inst::new(2);
+        let i3 = Inst::new(3);
+        let i4 = Inst::new(4);
+
+        // This is not supposed to change the list.
+        list.grow_at(0, 0, pool);
+        assert_eq!(list.len(pool), 0);
+        assert!(list.is_empty());
+
+        list.grow_at(0, 2, pool);
+        assert_eq!(list.len(pool), 2);
+
+        list.as_mut_slice(pool).copy_from_slice(&[i2, i3]);
+
+        list.grow_at(1, 0, pool);
+        assert_eq!(list.as_slice(pool), &[i2, i3]);
+
+        list.grow_at(1, 1, pool);
+        list.as_mut_slice(pool)[1] = i1;
+        assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
+
+        // Append nothing at the end.
+        list.grow_at(3, 0, pool);
+        assert_eq!(list.as_slice(pool), &[i2, i1, i3]);
+
+        // Append something at the end.
+        list.grow_at(3, 1, pool);
+        list.as_mut_slice(pool)[3] = i4;
+        assert_eq!(list.as_slice(pool), &[i2, i1, i3, i4]);
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/map.rs b/third_party/rust/cranelift-entity-0.41.0/src/map.rs
new file mode 100644
index 0000000000..bb1b94aeca
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/map.rs
@@ -0,0 +1,287 @@
+//! Densely numbered entity references as mapping keys.
+
+use crate::iter::{Iter, IterMut};
+use crate::keys::Keys;
+use crate::EntityRef;
+use core::marker::PhantomData;
+use core::ops::{Index, IndexMut};
+use core::slice;
+#[cfg(feature = "enable-serde")]
+use serde::{
+    de::{Deserializer, SeqAccess, Visitor},
+    ser::{SerializeSeq, Serializer},
+    Deserialize, Serialize,
+};
+use std::cmp::min;
+use std::vec::Vec;
+
+/// A mapping `K -> V` for densely indexed entity references.
+///
+/// The `SecondaryMap` data structure uses the dense index space to implement a map with a vector.
+/// Unlike `PrimaryMap`, an `SecondaryMap` can't be used to allocate entity references. It is used
+/// to associate secondary information with entities.
+///
+/// The map does not track if an entry for a key has been inserted or not. Instead it behaves as if
+/// all keys have a default entry from the beginning.
+#[derive(Debug, Clone)]
+pub struct SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone,
+{
+    elems: Vec<V>,
+    default: V,
+    unused: PhantomData<K>,
+}
+
+/// Shared `SecondaryMap` implementation for all value types.
+impl<K, V> SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone,
+{
+    /// Create a new empty map.
+    pub fn new() -> Self
+    where
+        V: Default,
+    {
+        Self {
+            elems: Vec::new(),
+            default: Default::default(),
+            unused: PhantomData,
+        }
+    }
+
+    /// Create a new empty map with a specified default value.
+    ///
+    /// This constructor does not require V to implement Default.
+    pub fn with_default(default: V) -> Self {
+        Self {
+            elems: Vec::new(),
+            default,
+            unused: PhantomData,
+        }
+    }
+
+    /// Get the element at `k` if it exists.
+    pub fn get(&self, k: K) -> Option<&V> {
+        self.elems.get(k.index())
+    }
+
+    /// Is this map completely empty?
+    pub fn is_empty(&self) -> bool {
+        self.elems.is_empty()
+    }
+
+    /// Remove all entries from this map.
+    pub fn clear(&mut self) {
+        self.elems.clear()
+    }
+
+    /// Iterate over all the keys and values in this map.
+    pub fn iter(&self) -> Iter<K, V> {
+        Iter::new(self.elems.iter())
+    }
+
+    /// Iterate over all the keys and values in this map, mutable edition.
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        IterMut::new(self.elems.iter_mut())
+    }
+
+    /// Iterate over all the keys in this map.
+    pub fn keys(&self) -> Keys<K> {
+        Keys::with_len(self.elems.len())
+    }
+
+    /// Iterate over all the values in this map.
+    pub fn values(&self) -> slice::Iter<V> {
+        self.elems.iter()
+    }
+
+    /// Iterate over all the values in this map, mutable edition.
+    pub fn values_mut(&mut self) -> slice::IterMut<V> {
+        self.elems.iter_mut()
+    }
+
+    /// Resize the map to have `n` entries by adding default entries as needed.
+    #[inline]
+    pub fn resize(&mut self, n: usize) {
+        self.elems.resize(n, self.default.clone());
+    }
+}
+
+/// Immutable indexing into an `SecondaryMap`.
+///
+/// All keys are permitted. Untouched entries have the default value.
+impl<K, V> Index<K> for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone,
+{
+    type Output = V;
+
+    fn index(&self, k: K) -> &V {
+        self.get(k).unwrap_or(&self.default)
+    }
+}
+
+/// Mutable indexing into an `SecondaryMap`.
+///
+/// The map grows as needed to accommodate new keys.
+impl<K, V> IndexMut<K> for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone,
+{
+    #[inline]
+    fn index_mut(&mut self, k: K) -> &mut V {
+        let i = k.index();
+        if i >= self.elems.len() {
+            self.resize(i + 1);
+        }
+        &mut self.elems[i]
+    }
+}
+
+impl<K, V> PartialEq for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone + PartialEq,
+{
+    fn eq(&self, other: &Self) -> bool {
+        let min_size = min(self.elems.len(), other.elems.len());
+        self.default == other.default
+            && self.elems[..min_size] == other.elems[..min_size]
+            && self.elems[min_size..].iter().all(|e| *e == self.default)
+            && other.elems[min_size..].iter().all(|e| *e == other.default)
+    }
+}
+
+impl<K, V> Eq for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone + PartialEq + Eq,
+{
+}
+
+#[cfg(feature = "enable-serde")]
+impl<K, V> Serialize for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone + PartialEq + Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        // TODO: bincode encodes option as "byte for Some/None" and then optionally the content
+        // TODO: we can actually optimize it by encoding manually bitmask, then elements
+        let mut elems_cnt = self.elems.len();
+        while elems_cnt > 0 && self.elems[elems_cnt - 1] == self.default {
+            elems_cnt -= 1;
+        }
+        let mut seq = serializer.serialize_seq(Some(1 + elems_cnt))?;
+        seq.serialize_element(&Some(self.default.clone()))?;
+        for e in self.elems.iter().take(elems_cnt) {
+            let some_e = Some(e);
+            seq.serialize_element(if *e == self.default { &None } else { &some_e })?;
+        }
+        seq.end()
+    }
+}
+
+#[cfg(feature = "enable-serde")]
+impl<'de, K, V> Deserialize<'de> for SecondaryMap<K, V>
+where
+    K: EntityRef,
+    V: Clone + Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        use std::fmt;
+        struct SecondaryMapVisitor<K, V> {
+            unused: PhantomData<fn(K) -> V>,
+        }
+
+        impl<'de, K, V> Visitor<'de> for SecondaryMapVisitor<K, V>
+        where
+            K: EntityRef,
+            V: Clone + Deserialize<'de>,
+        {
+            type Value = SecondaryMap<K, V>;
+
+            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+                formatter.write_str("struct SecondaryMap")
+            }
+
+            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
+            where
+                A: SeqAccess<'de>,
+            {
+                match seq.next_element()? {
+                    Some(Some(default_val)) => {
+                        let default_val: V = default_val; // compiler can't infer the type
+                        let mut m = SecondaryMap::with_default(default_val.clone());
+                        let mut idx = 0;
+                        while let Some(val) = seq.next_element()? {
+                            let val: Option<_> = val; // compiler can't infer the type
+                            m[K::new(idx)] = val.unwrap_or_else(|| default_val.clone());
+                            idx += 1;
+                        }
+                        Ok(m)
+                    }
+                    _ => Err(serde::de::Error::custom("Default value required")),
+                }
+            }
+        }
+
+        deserializer.deserialize_seq(SecondaryMapVisitor {
+            unused: PhantomData {},
+        })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    // `EntityRef` impl for testing.
+    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
+    struct E(u32);
+
+    impl EntityRef for E {
+        fn new(i: usize) -> Self {
+            E(i as u32)
+        }
+        fn index(self) -> usize {
+            self.0 as usize
+        }
+    }
+
+    #[test]
+    fn basic() {
+        let r0 = E(0);
+        let r1 = E(1);
+        let r2 = E(2);
+        let mut m = SecondaryMap::new();
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, []);
+
+        m[r2] = 3;
+        m[r1] = 5;
+
+        assert_eq!(m[r1], 5);
+        assert_eq!(m[r2], 3);
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, [r0, r1, r2]);
+
+        let shared = &m;
+        assert_eq!(shared[r0], 0);
+        assert_eq!(shared[r1], 5);
+        assert_eq!(shared[r2], 3);
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/packed_option.rs b/third_party/rust/cranelift-entity-0.41.0/src/packed_option.rs
new file mode 100644
index 0000000000..0757e9e19b
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/packed_option.rs
@@ -0,0 +1,157 @@
+//! Compact representation of `Option<T>` for types with a reserved value.
+//!
+//! Small Cranelift types like the 32-bit entity references are often used in tables and linked
+//! lists where an `Option<T>` is needed. Unfortunately, that would double the size of the tables
+//! because `Option<T>` is twice as big as `T`.
+//!
+//! This module provides a `PackedOption<T>` for types that have a reserved value that can be used
+//! to represent `None`.
+
+use core::fmt;
+use core::mem;
+
+/// Types that have a reserved value which can't be created any other way.
+pub trait ReservedValue: Eq {
+    /// Create an instance of the reserved value.
+    fn reserved_value() -> Self;
+}
+
+/// Packed representation of `Option<T>`.
+#[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord, Hash)]
+pub struct PackedOption<T: ReservedValue>(T);
+
+impl<T: ReservedValue> PackedOption<T> {
+    /// Returns `true` if the packed option is a `None` value.
+    pub fn is_none(&self) -> bool {
+        self.0 == T::reserved_value()
+    }
+
+    /// Returns `true` if the packed option is a `Some` value.
+    pub fn is_some(&self) -> bool {
+        self.0 != T::reserved_value()
+    }
+
+    /// Expand the packed option into a normal `Option`.
+    pub fn expand(self) -> Option<T> {
+        if self.is_none() {
+            None
+        } else {
+            Some(self.0)
+        }
+    }
+
+    /// Maps a `PackedOption<T>` to `Option<U>` by applying a function to a contained value.
+    pub fn map<U, F>(self, f: F) -> Option<U>
+    where
+        F: FnOnce(T) -> U,
+    {
+        self.expand().map(f)
+    }
+
+    /// Unwrap a packed `Some` value or panic.
+    pub fn unwrap(self) -> T {
+        self.expand().unwrap()
+    }
+
+    /// Unwrap a packed `Some` value or panic.
+    pub fn expect(self, msg: &str) -> T {
+        self.expand().expect(msg)
+    }
+
+    /// Takes the value out of the packed option, leaving a `None` in its place.
+    pub fn take(&mut self) -> Option<T> {
+        mem::replace(self, None.into()).expand()
+    }
+}
+
+impl<T: ReservedValue> Default for PackedOption<T> {
+    /// Create a default packed option representing `None`.
+    fn default() -> Self {
+        PackedOption(T::reserved_value())
+    }
+}
+
+impl<T: ReservedValue> From<T> for PackedOption<T> {
+    /// Convert `t` into a packed `Some(x)`.
+    fn from(t: T) -> Self {
+        debug_assert!(
+            t != T::reserved_value(),
+            "Can't make a PackedOption from the reserved value."
+        );
+        PackedOption(t)
+    }
+}
+
+impl<T: ReservedValue> From<Option<T>> for PackedOption<T> {
+    /// Convert an option into its packed equivalent.
+    fn from(opt: Option<T>) -> Self {
+        match opt {
+            None => Self::default(),
+            Some(t) => t.into(),
+        }
+    }
+}
+
+impl<T: ReservedValue> Into<Option<T>> for PackedOption<T> {
+    fn into(self) -> Option<T> {
+        self.expand()
+    }
+}
+
+impl<T> fmt::Debug for PackedOption<T>
+where
+    T: ReservedValue + fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        if self.is_none() {
+            write!(f, "None")
+        } else {
+            write!(f, "Some({:?})", self.0)
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    // Dummy entity class, with no Copy or Clone.
+    #[derive(Debug, PartialEq, Eq)]
+    struct NoC(u32);
+
+    impl ReservedValue for NoC {
+        fn reserved_value() -> Self {
+            NoC(13)
+        }
+    }
+
+    #[test]
+    fn moves() {
+        let x = NoC(3);
+        let somex: PackedOption<NoC> = x.into();
+        assert!(!somex.is_none());
+        assert_eq!(somex.expand(), Some(NoC(3)));
+
+        let none: PackedOption<NoC> = None.into();
+        assert!(none.is_none());
+        assert_eq!(none.expand(), None);
+    }
+
+    // Dummy entity class, with Copy.
+    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
+    struct Ent(u32);
+
+    impl ReservedValue for Ent {
+        fn reserved_value() -> Self {
+            Ent(13)
+        }
+    }
+
+    #[test]
+    fn copies() {
+        let x = Ent(2);
+        let some: PackedOption<Ent> = x.into();
+        assert_eq!(some.expand(), x.into());
+        assert_eq!(some, x.into());
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/primary.rs b/third_party/rust/cranelift-entity-0.41.0/src/primary.rs
new file mode 100644
index 0000000000..9cde5e779d
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/primary.rs
@@ -0,0 +1,404 @@
+//! Densely numbered entity references as mapping keys.
+use crate::boxed_slice::BoxedSlice;
+use crate::iter::{Iter, IterMut};
+use crate::keys::Keys;
+use crate::EntityRef;
+use core::iter::FromIterator;
+use core::marker::PhantomData;
+use core::ops::{Index, IndexMut};
+use core::slice;
+#[cfg(feature = "enable-serde")]
+use serde::{Deserialize, Serialize};
+use std::boxed::Box;
+use std::vec::Vec;
+
+/// A primary mapping `K -> V` allocating dense entity references.
+///
+/// The `PrimaryMap` data structure uses the dense index space to implement a map with a vector.
+///
+/// A primary map contains the main definition of an entity, and it can be used to allocate new
+/// entity references with the `push` method.
+///
+/// There should only be a single `PrimaryMap` instance for a given `EntityRef` type, otherwise
+/// conflicting references will be created. Using unknown keys for indexing will cause a panic.
+///
+/// Note that `PrimaryMap` doesn't implement `Deref` or `DerefMut`, which would allow
+/// `&PrimaryMap<K, V>` to convert to `&[V]`. One of the main advantages of `PrimaryMap` is
+/// that it only allows indexing with the distinct `EntityRef` key type, so converting to a
+/// plain slice would make it easier to use incorrectly. To make a slice of a `PrimaryMap`, use
+/// `into_boxed_slice`.
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
+pub struct PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    elems: Vec<V>,
+    unused: PhantomData<K>,
+}
+
+impl<K, V> PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    /// Create a new empty map.
+    pub fn new() -> Self {
+        Self {
+            elems: Vec::new(),
+            unused: PhantomData,
+        }
+    }
+
+    /// Create a new empty map with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            elems: Vec::with_capacity(capacity),
+            unused: PhantomData,
+        }
+    }
+
+    /// Check if `k` is a valid key in the map.
+    pub fn is_valid(&self, k: K) -> bool {
+        k.index() < self.elems.len()
+    }
+
+    /// Get the element at `k` if it exists.
+    pub fn get(&self, k: K) -> Option<&V> {
+        self.elems.get(k.index())
+    }
+
+    /// Get the element at `k` if it exists, mutable version.
+    pub fn get_mut(&mut self, k: K) -> Option<&mut V> {
+        self.elems.get_mut(k.index())
+    }
+
+    /// Is this map completely empty?
+    pub fn is_empty(&self) -> bool {
+        self.elems.is_empty()
+    }
+
+    /// Get the total number of entity references created.
+    pub fn len(&self) -> usize {
+        self.elems.len()
+    }
+
+    /// Iterate over all the keys in this map.
+    pub fn keys(&self) -> Keys<K> {
+        Keys::with_len(self.elems.len())
+    }
+
+    /// Iterate over all the values in this map.
+    pub fn values(&self) -> slice::Iter<V> {
+        self.elems.iter()
+    }
+
+    /// Iterate over all the values in this map, mutable edition.
+    pub fn values_mut(&mut self) -> slice::IterMut<V> {
+        self.elems.iter_mut()
+    }
+
+    /// Iterate over all the keys and values in this map.
+    pub fn iter(&self) -> Iter<K, V> {
+        Iter::new(self.elems.iter())
+    }
+
+    /// Iterate over all the keys and values in this map, mutable edition.
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        IterMut::new(self.elems.iter_mut())
+    }
+
+    /// Remove all entries from this map.
+    pub fn clear(&mut self) {
+        self.elems.clear()
+    }
+
+    /// Get the key that will be assigned to the next pushed value.
+    pub fn next_key(&self) -> K {
+        K::new(self.elems.len())
+    }
+
+    /// Append `v` to the mapping, assigning a new key which is returned.
+    pub fn push(&mut self, v: V) -> K {
+        let k = self.next_key();
+        self.elems.push(v);
+        k
+    }
+
+    /// Returns the last element that was inserted in the map.
+    pub fn last(&self) -> Option<&V> {
+        self.elems.last()
+    }
+
+    /// Reserves capacity for at least `additional` more elements to be inserted.
+    pub fn reserve(&mut self, additional: usize) {
+        self.elems.reserve(additional)
+    }
+
+    /// Reserves the minimum capacity for exactly `additional` more elements to be inserted.
+    pub fn reserve_exact(&mut self, additional: usize) {
+        self.elems.reserve_exact(additional)
+    }
+
+    /// Shrinks the capacity of the `PrimaryMap` as much as possible.
+    pub fn shrink_to_fit(&mut self) {
+        self.elems.shrink_to_fit()
+    }
+
+    /// Consumes this `PrimaryMap` and produces a `BoxedSlice`.
+    pub fn into_boxed_slice(self) -> BoxedSlice<K, V> {
+        unsafe { BoxedSlice::<K, V>::from_raw(Box::<[V]>::into_raw(self.elems.into_boxed_slice())) }
+    }
+}
+
+/// Immutable indexing into an `PrimaryMap`.
+/// The indexed value must be in the map.
+impl<K, V> Index<K> for PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    type Output = V;
+
+    fn index(&self, k: K) -> &V {
+        &self.elems[k.index()]
+    }
+}
+
+/// Mutable indexing into an `PrimaryMap`.
+impl<K, V> IndexMut<K> for PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    fn index_mut(&mut self, k: K) -> &mut V {
+        &mut self.elems[k.index()]
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    type Item = (K, &'a V);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        Iter::new(self.elems.iter())
+    }
+}
+
+impl<'a, K, V> IntoIterator for &'a mut PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    type Item = (K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IterMut::new(self.elems.iter_mut())
+    }
+}
+
+impl<K, V> FromIterator<V> for PrimaryMap<K, V>
+where
+    K: EntityRef,
+{
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = V>,
+    {
+        Self {
+            elems: Vec::from_iter(iter),
+            unused: PhantomData,
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    // `EntityRef` impl for testing.
+    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
+    struct E(u32);
+
+    impl EntityRef for E {
+        fn new(i: usize) -> Self {
+            E(i as u32)
+        }
+        fn index(self) -> usize {
+            self.0 as usize
+        }
+    }
+
+    #[test]
+    fn basic() {
+        let r0 = E(0);
+        let r1 = E(1);
+        let m = PrimaryMap::<E, isize>::new();
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, []);
+
+        assert!(!m.is_valid(r0));
+        assert!(!m.is_valid(r1));
+    }
+
+    #[test]
+    fn push() {
+        let mut m = PrimaryMap::new();
+        let k0: E = m.push(12);
+        let k1 = m.push(33);
+
+        assert_eq!(m[k0], 12);
+        assert_eq!(m[k1], 33);
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, [k0, k1]);
+    }
+
+    #[test]
+    fn iter() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 0;
+        for (key, value) in &m {
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+        i = 0;
+        for (key_mut, value_mut) in m.iter_mut() {
+            assert_eq!(key_mut.index(), i);
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn iter_rev() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 2;
+        for (key, value) in m.iter().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+
+        i = 2;
+        for (key, value) in m.iter_mut().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+    }
+    #[test]
+    fn keys() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 0;
+        for key in m.keys() {
+            assert_eq!(key.index(), i);
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn keys_rev() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 2;
+        for key in m.keys().rev() {
+            i -= 1;
+            assert_eq!(key.index(), i);
+        }
+    }
+
+    #[test]
+    fn values() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 0;
+        for value in m.values() {
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+        i = 0;
+        for value_mut in m.values_mut() {
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+            i += 1;
+        }
+    }
+
+    #[test]
+    fn values_rev() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let mut i = 2;
+        for value in m.values().rev() {
+            i -= 1;
+            match i {
+                0 => assert_eq!(*value, 12),
+                1 => assert_eq!(*value, 33),
+                _ => panic!(),
+            }
+        }
+        i = 2;
+        for value_mut in m.values_mut().rev() {
+            i -= 1;
+            match i {
+                0 => assert_eq!(*value_mut, 12),
+                1 => assert_eq!(*value_mut, 33),
+                _ => panic!(),
+            }
+        }
+    }
+
+    #[test]
+    fn from_iter() {
+        let mut m: PrimaryMap<E, usize> = PrimaryMap::new();
+        m.push(12);
+        m.push(33);
+
+        let n = m.values().collect::<PrimaryMap<E, _>>();
+        assert!(m.len() == n.len());
+        for (me, ne) in m.values().zip(n.values()) {
+            assert!(*me == **ne);
+        }
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/set.rs b/third_party/rust/cranelift-entity-0.41.0/src/set.rs
new file mode 100644
index 0000000000..a4759a1712
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/set.rs
@@ -0,0 +1,162 @@
+//! Densely numbered entity references as set keys.
+
+use crate::keys::Keys;
+use crate::EntityRef;
+use core::marker::PhantomData;
+use std::vec::Vec;
+
+/// A set of `K` for densely indexed entity references.
+///
+/// The `EntitySet` data structure uses the dense index space to implement a set with a bitvector.
+/// Like `SecondaryMap`, an `EntitySet` is used to associate secondary information with entities.
+#[derive(Debug, Clone)]
+pub struct EntitySet<K>
+where
+    K: EntityRef,
+{
+    elems: Vec<u8>,
+    len: usize,
+    unused: PhantomData<K>,
+}
+
+/// Shared `EntitySet` implementation for all value types.
+impl<K> EntitySet<K>
+where
+    K: EntityRef,
+{
+    /// Create a new empty set.
+    pub fn new() -> Self {
+        Self {
+            elems: Vec::new(),
+            len: 0,
+            unused: PhantomData,
+        }
+    }
+
+    /// Get the element at `k` if it exists.
+    pub fn contains(&self, k: K) -> bool {
+        let index = k.index();
+        if index < self.len {
+            (self.elems[index / 8] & (1 << (index % 8))) != 0
+        } else {
+            false
+        }
+    }
+
+    /// Is this set completely empty?
+    pub fn is_empty(&self) -> bool {
+        // Note that this implementation will become incorrect should it ever become possible
+        // to remove elements from an `EntitySet`.
+        self.len == 0
+    }
+
+    /// Returns the cardinality of the set.  More precisely, it returns the number of calls to
+    /// `insert` with different key values, that have happened since the the set was most recently
+    /// `clear`ed or created with `new`.
+    pub fn cardinality(&self) -> usize {
+        let mut n: usize = 0;
+        for byte_ix in 0..self.len / 8 {
+            n += self.elems[byte_ix].count_ones() as usize;
+        }
+        for bit_ix in (self.len / 8) * 8..self.len {
+            if (self.elems[bit_ix / 8] & (1 << (bit_ix % 8))) != 0 {
+                n += 1;
+            }
+        }
+        n
+    }
+
+    /// Remove all entries from this set.
+    pub fn clear(&mut self) {
+        self.len = 0;
+        self.elems.clear()
+    }
+
+    /// Iterate over all the keys in this set.
+    pub fn keys(&self) -> Keys<K> {
+        Keys::with_len(self.len)
+    }
+
+    /// Resize the set to have `n` entries by adding default entries as needed.
+    pub fn resize(&mut self, n: usize) {
+        self.elems.resize((n + 7) / 8, 0);
+        self.len = n
+    }
+
+    /// Insert the element at `k`.
+    pub fn insert(&mut self, k: K) -> bool {
+        let index = k.index();
+        if index >= self.len {
+            self.resize(index + 1)
+        }
+        let result = !self.contains(k);
+        self.elems[index / 8] |= 1 << (index % 8);
+        result
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use core::u32;
+
+    // `EntityRef` impl for testing.
+    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
+    struct E(u32);
+
+    impl EntityRef for E {
+        fn new(i: usize) -> Self {
+            E(i as u32)
+        }
+        fn index(self) -> usize {
+            self.0 as usize
+        }
+    }
+
+    #[test]
+    fn basic() {
+        let r0 = E(0);
+        let r1 = E(1);
+        let r2 = E(2);
+        let mut m = EntitySet::new();
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, []);
+        assert!(m.is_empty());
+
+        m.insert(r2);
+        m.insert(r1);
+
+        assert!(!m.contains(r0));
+        assert!(m.contains(r1));
+        assert!(m.contains(r2));
+        assert!(!m.contains(E(3)));
+        assert!(!m.is_empty());
+
+        let v: Vec<E> = m.keys().collect();
+        assert_eq!(v, [r0, r1, r2]);
+
+        m.resize(20);
+        assert!(!m.contains(E(3)));
+        assert!(!m.contains(E(4)));
+        assert!(!m.contains(E(8)));
+        assert!(!m.contains(E(15)));
+        assert!(!m.contains(E(19)));
+
+        m.insert(E(8));
+        m.insert(E(15));
+        assert!(!m.contains(E(3)));
+        assert!(!m.contains(E(4)));
+        assert!(m.contains(E(8)));
+        assert!(!m.contains(E(9)));
+        assert!(!m.contains(E(14)));
+        assert!(m.contains(E(15)));
+        assert!(!m.contains(E(16)));
+        assert!(!m.contains(E(19)));
+        assert!(!m.contains(E(20)));
+        assert!(!m.contains(E(u32::MAX)));
+
+        m.clear();
+        assert!(m.is_empty());
+    }
+}
diff --git a/third_party/rust/cranelift-entity-0.41.0/src/sparse.rs b/third_party/rust/cranelift-entity-0.41.0/src/sparse.rs
new file mode 100644
index 0000000000..83c519f47f
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/src/sparse.rs
@@ -0,0 +1,364 @@
+//! Sparse mapping of entity references to larger value types.
+//!
+//! This module provides a `SparseMap` data structure which implements a sparse mapping from an
+//! `EntityRef` key to a value type that may be on the larger side. This implementation is based on
+//! the paper:
+//!
+//! > Briggs, Torczon, *An efficient representation for sparse sets*,
+//!   ACM Letters on Programming Languages and Systems, Volume 2, Issue 1-4, March-Dec. 1993.
+
+use crate::map::SecondaryMap;
+use crate::EntityRef;
+use core::mem;
+use core::slice;
+use core::u32;
+use std::vec::Vec;
+
+/// Trait for extracting keys from values stored in a `SparseMap`.
+///
+/// All values stored in a `SparseMap` must keep track of their own key in the map and implement
+/// this trait to provide access to the key.
+pub trait SparseMapValue<K> {
+    /// Get the key of this sparse map value. This key is not allowed to change while the value
+    /// is a member of the map.
+    fn key(&self) -> K;
+}
+
+/// A sparse mapping of entity references.
+///
+/// A `SparseMap<K, V>` map provides:
+///
+/// - Memory usage equivalent to `SecondaryMap<K, u32>` + `Vec<V>`, so much smaller than
+///   `SecondaryMap<K, V>` for sparse mappings of larger `V` types.
+/// - Constant time lookup, slightly slower than `SecondaryMap`.
+/// - A very fast, constant time `clear()` operation.
+/// - Fast insert and erase operations.
+/// - Stable iteration that is as fast as a `Vec<V>`.
+///
+/// # Compared to `SecondaryMap`
+///
+/// When should we use a `SparseMap` instead of a secondary `SecondaryMap`? First of all,
+/// `SparseMap` does not provide the functionality of a `PrimaryMap` which can allocate and assign
+/// entity references to objects as they are pushed onto the map. It is only the secondary entity
+/// maps that can be replaced with a `SparseMap`.
+///
+/// - A secondary entity map assigns a default mapping to all keys. It doesn't distinguish between
+///   an unmapped key and one that maps to the default value. `SparseMap` does not require
+///   `Default` values, and it tracks accurately if a key has been mapped or not.
+/// - Iterating over the contents of an `SecondaryMap` is linear in the size of the *key space*,
+///   while iterating over a `SparseMap` is linear in the number of elements in the mapping. This
+///   is an advantage precisely when the mapping is sparse.
+/// - `SparseMap::clear()` is constant time and super-fast. `SecondaryMap::clear()` is linear in
+///   the size of the key space. (Or, rather the required `resize()` call following the `clear()`
+///   is).
+/// - `SparseMap` requires the values to implement `SparseMapValue<K>` which means that they must
+///   contain their own key.
+pub struct SparseMap<K, V>
+where
+    K: EntityRef,
+    V: SparseMapValue<K>,
+{
+    sparse: SecondaryMap<K, u32>,
+    dense: Vec<V>,
+}
+
+impl<K, V> SparseMap<K, V>
+where
+    K: EntityRef,
+    V: SparseMapValue<K>,
+{
+    /// Create a new empty mapping.
+    pub fn new() -> Self {
+        Self {
+            sparse: SecondaryMap::new(),
+            dense: Vec::new(),
+        }
+    }
+
+    /// Returns the number of elements in the map.
+    pub fn len(&self) -> usize {
+        self.dense.len()
+    }
+
+    /// Returns true is the map contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.dense.is_empty()
+    }
+
+    /// Remove all elements from the mapping.
+    pub fn clear(&mut self) {
+        self.dense.clear();
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    pub fn get(&self, key: K) -> Option<&V> {
+        if let Some(idx) = self.sparse.get(key).cloned() {
+            if let Some(entry) = self.dense.get(idx as usize) {
+                if entry.key() == key {
+                    return Some(entry);
+                }
+            }
+        }
+        None
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// Note that the returned value must not be mutated in a way that would change its key. This
+    /// would invalidate the sparse set data structure.
+    pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
+        if let Some(idx) = self.sparse.get(key).cloned() {
+            if let Some(entry) = self.dense.get_mut(idx as usize) {
+                if entry.key() == key {
+                    return Some(entry);
+                }
+            }
+        }
+        None
+    }
+
+    /// Return the index into `dense` of the value corresponding to `key`.
+    fn index(&self, key: K) -> Option<usize> {
+        if let Some(idx) = self.sparse.get(key).cloned() {
+            let idx = idx as usize;
+            if let Some(entry) = self.dense.get(idx) {
+                if entry.key() == key {
+                    return Some(idx);
+                }
+            }
+        }
+        None
+    }
+
+    /// Return `true` if the map contains a value corresponding to `key`.
+    pub fn contains_key(&self, key: K) -> bool {
+        self.get(key).is_some()
+    }
+
+    /// Insert a value into the map.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old value is returned.
+    ///
+    /// It is not necessary to provide a key since the value knows its own key already.
+    pub fn insert(&mut self, value: V) -> Option<V> {
+        let key = value.key();
+
+        // Replace the existing entry for `key` if there is one.
+        if let Some(entry) = self.get_mut(key) {
+            return Some(mem::replace(entry, value));
+        }
+
+        // There was no previous entry for `key`. Add it to the end of `dense`.
+        let idx = self.dense.len();
+        debug_assert!(idx <= u32::MAX as usize, "SparseMap overflow");
+        self.dense.push(value);
+        self.sparse[key] = idx as u32;
+        None
+    }
+
+    /// Remove a value from the map and return it.
+    pub fn remove(&mut self, key: K) -> Option<V> {
+        if let Some(idx) = self.index(key) {
+            let back = self.dense.pop().unwrap();
+
+            // Are we popping the back of `dense`?
+            if idx == self.dense.len() {
+                return Some(back);
+            }
+
+            // We're removing an element from the middle of `dense`.
+            // Replace the element at `idx` with the back of `dense`.
+            // Repair `sparse` first.
+            self.sparse[back.key()] = idx as u32;
+            return Some(mem::replace(&mut self.dense[idx], back));
+        }
+
+        // Nothing to remove.
+        None
+    }
+
+    /// Remove the last value from the map.
+    pub fn pop(&mut self) -> Option<V> {
+        self.dense.pop()
+    }
+
+    /// Get an iterator over the values in the map.
+    ///
+    /// The iteration order is entirely determined by the preceding sequence of `insert` and
+    /// `remove` operations. In particular, if no elements were removed, this is the insertion
+    /// order.
+    pub fn values(&self) -> slice::Iter<V> {
+        self.dense.iter()
+    }
+
+    /// Get the values as a slice.
+    pub fn as_slice(&self) -> &[V] {
+        self.dense.as_slice()
+    }
+}
+
+/// Iterating over the elements of a set.
+impl<'a, K, V> IntoIterator for &'a SparseMap<K, V>
+where
+    K: EntityRef,
+    V: SparseMapValue<K>,
+{
+    type Item = &'a V;
+    type IntoIter = slice::Iter<'a, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.values()
+    }
+}
+
+/// Any `EntityRef` can be used as a sparse map value representing itself.
+impl<T> SparseMapValue<T> for T
+where
+    T: EntityRef,
+{
+    fn key(&self) -> Self {
+        *self
+    }
+}
+
+/// A sparse set of entity references.
+///
+/// Any type that implements `EntityRef` can be used as a sparse set value too.
+pub type SparseSet<T> = SparseMap<T, T>;
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::EntityRef;
+
+    /// An opaque reference to an instruction in a function.
+    #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
+    pub struct Inst(u32);
+    entity_impl!(Inst, "inst");
+
+    // Mock key-value object for testing.
+    #[derive(PartialEq, Eq, Debug)]
+    struct Obj(Inst, &'static str);
+
+    impl SparseMapValue<Inst> for Obj {
+        fn key(&self) -> Inst {
+            self.0
+        }
+    }
+
+    #[test]
+    fn empty_immutable_map() {
+        let i1 = Inst::new(1);
+        let map: SparseMap<Inst, Obj> = SparseMap::new();
+
+        assert!(map.is_empty());
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.get(i1), None);
+        assert_eq!(map.values().count(), 0);
+    }
+
+    #[test]
+    fn single_entry() {
+        let i0 = Inst::new(0);
+        let i1 = Inst::new(1);
+        let i2 = Inst::new(2);
+        let mut map = SparseMap::new();
+
+        assert!(map.is_empty());
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.get(i1), None);
+        assert_eq!(map.get_mut(i1), None);
+        assert_eq!(map.remove(i1), None);
+
+        assert_eq!(map.insert(Obj(i1, "hi")), None);
+        assert!(!map.is_empty());
+        assert_eq!(map.len(), 1);
+        assert_eq!(map.get(i0), None);
+        assert_eq!(map.get(i1), Some(&Obj(i1, "hi")));
+        assert_eq!(map.get(i2), None);
+        assert_eq!(map.get_mut(i0), None);
+        assert_eq!(map.get_mut(i1), Some(&mut Obj(i1, "hi")));
+        assert_eq!(map.get_mut(i2), None);
+
+        assert_eq!(map.remove(i0), None);
+        assert_eq!(map.remove(i2), None);
+        assert_eq!(map.remove(i1), Some(Obj(i1, "hi")));
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.get(i1), None);
+        assert_eq!(map.get_mut(i1), None);
+        assert_eq!(map.remove(i0), None);
+        assert_eq!(map.remove(i1), None);
+        assert_eq!(map.remove(i2), None);
+    }
+
+    #[test]
+    fn multiple_entries() {
+        let i0 = Inst::new(0);
+        let i1 = Inst::new(1);
+        let i2 = Inst::new(2);
+        let i3 = Inst::new(3);
+        let mut map = SparseMap::new();
+
+        assert_eq!(map.insert(Obj(i2, "foo")), None);
+        assert_eq!(map.insert(Obj(i1, "bar")), None);
+        assert_eq!(map.insert(Obj(i0, "baz")), None);
+
+        // Iteration order = insertion order when nothing has been removed yet.
+        assert_eq!(
+            map.values().map(|obj| obj.1).collect::<Vec<_>>(),
+            ["foo", "bar", "baz"]
+        );
+
+        assert_eq!(map.len(), 3);
+        assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
+        assert_eq!(map.get(i1), Some(&Obj(i1, "bar")));
+        assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
+        assert_eq!(map.get(i3), None);
+
+        // Remove front object, causing back to be swapped down.
+        assert_eq!(map.remove(i1), Some(Obj(i1, "bar")));
+        assert_eq!(map.len(), 2);
+        assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
+        assert_eq!(map.get(i1), None);
+        assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
+        assert_eq!(map.get(i3), None);
+
+        // Reinsert something at a previously used key.
+        assert_eq!(map.insert(Obj(i1, "barbar")), None);
+        assert_eq!(map.len(), 3);
+        assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
+        assert_eq!(map.get(i1), Some(&Obj(i1, "barbar")));
+        assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
+        assert_eq!(map.get(i3), None);
+
+        // Replace an entry.
+        assert_eq!(map.insert(Obj(i0, "bazbaz")), Some(Obj(i0, "baz")));
+        assert_eq!(map.len(), 3);
+        assert_eq!(map.get(i0), Some(&Obj(i0, "bazbaz")));
+        assert_eq!(map.get(i1), Some(&Obj(i1, "barbar")));
+        assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
+        assert_eq!(map.get(i3), None);
+
+        // Check the reference `IntoIter` impl.
+        let mut v = Vec::new();
+        for i in &map {
+            v.push(i.1);
+        }
+        assert_eq!(v.len(), map.len());
+    }
+
+    #[test]
+    fn entity_set() {
+        let i0 = Inst::new(0);
+        let i1 = Inst::new(1);
+        let mut set = SparseSet::new();
+
+        assert_eq!(set.insert(i0), None);
+        assert_eq!(set.insert(i0), Some(i0));
+        assert_eq!(set.insert(i1), None);
+        assert_eq!(set.get(i0), Some(&i0));
+        assert_eq!(set.get(i1), Some(&i1));
+    }
+}