Adding upstream version 86.0.1.upstream/86.0.1upstream

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

14 files changed, 2975 insertions, 0 deletions

diff --git a/third_party/rust/cranelift-entity-0.41.0/.cargo-checksum.json b/third_party/rust/cranelift-entity-0.41.0/.cargo-checksum.json
new file mode 100644
index 0000000000..6be0055473
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"29f0990526d383231ac5e68c48c089c5a75b2afc8dee5f894674fd9f40586c1d","LICENSE":"268872b9816f90fd8e85db5a28d33f8150ebb8dd016653fb39ef1f94f2686bc5","README.md":"96ceffbfd88fb06e3b41aa4d3087cffbbf8441d04eba7ab09662a72ab600a321","src/boxed_slice.rs":"687428ee0442013c0d5962dd78d0964830233bc4cb19aa530d30da0f1dc437a9","src/iter.rs":"4a4d3309fe9aad14fd7702f02459f4277b4ddb50dba700e58dcc75665ffebfb3","src/keys.rs":"b8c2fba26dee15bf3d1880bb2b41e8d66fe1428d242ee6d9fd30ee94bbd0407d","src/lib.rs":"c47e858b6a46f8b5f584ca7f83c466e0fa616bbed9cb28622c53d4c1faf197c4","src/list.rs":"fc3decc81bcef92e106aae53e586a0ef21d70916fa53a48f7b813c5da44b8dc2","src/map.rs":"cf4d7d3cc928f7bd0217fdbcb2ac97623fde530f438cae8e66818d93b27a5e43","src/packed_option.rs":"9d47f5b8302ee685c096817e376144e363507d1c77ef562d3ae4dbddae568195","src/primary.rs":"8237b5c473fd219dc606efd7c989ec5216e4ae62c6cbb2857fbe11593c42aae9","src/set.rs":"97b860818c9577546201271f7ca457a5784c2e4447b68202a274f7fe75e937f2","src/sparse.rs":"cf345a81d69a5dddaed4778b6aaaf06c70da2c1fd4cd21e366ed6ca5906ffdab"},"package":null}
\ No newline at end of file
diff --git a/third_party/rust/cranelift-entity-0.41.0/Cargo.toml b/third_party/rust/cranelift-entity-0.41.0/Cargo.toml
new file mode 100644
index 0000000000..3aecf29d9b
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/Cargo.toml
@@ -0,0 +1,25 @@
+[package]
+authors = ["The Cranelift Project Developers"]
+name = "cranelift-entity"
+version = "0.41.0"
+description = "Data structures using entity references as mapping keys"
+license = "Apache-2.0 WITH LLVM-exception"
+documentation = "https://cranelift.readthedocs.io/"
+repository = "https://github.com/CraneStation/cranelift"
+categories = ["no-std"]
+readme = "README.md"
+keywords = ["entity", "set", "map"]
+edition = "2018"
+
+[dependencies]
+serde = { version = "1.0.94", features = ["derive"], optional = true }
+
+[features]
+default = ["std"]
+std = []
+core = []
+enable-serde = ["serde"]
+
+[badges]
+maintenance = { status = "experimental" }
+travis-ci = { repository = "CraneStation/cranelift" }
diff --git a/third_party/rust/cranelift-entity-0.41.0/LICENSE b/third_party/rust/cranelift-entity-0.41.0/LICENSE
new file mode 100644
index 0000000000..f9d81955f4
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/LICENSE
@@ -0,0 +1,220 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+
+
+--- LLVM Exceptions to the Apache 2.0 License ----
+
+As an exception, if, as a result of your compiling your source code, portions
+of this Software are embedded into an Object form of such source code, you
+may redistribute such embedded portions in such Object form without complying
+with the conditions of Sections 4(a), 4(b) and 4(d) of the License.
+
+In addition, if you combine or link compiled forms of this Software with
+software that is licensed under the GPLv2 ("Combined Software") and if a
+court of competent jurisdiction determines that the patent provision (Section
+3), the indemnity provision (Section 9) or other Section of the License
+conflicts with the conditions of the GPLv2, you may retroactively and
+prospectively choose to deem waived or otherwise exclude such Section(s) of
+the License, but only in their entirety and only with respect to the Combined
+Software.
+
diff --git a/third_party/rust/cranelift-entity-0.41.0/README.md b/third_party/rust/cranelift-entity-0.41.0/README.md
new file mode 100644
index 0000000000..f840b142e6
--- /dev/null
+++ b/third_party/rust/cranelift-entity-0.41.0/README.md
@@ -0,0 +1,40 @@
+This crate contains array-based data structures used by the core Cranelift code
+generator which use densely numbered entity references as mapping keys.
+
+One major difference between this crate and crates like [slotmap], [slab],
+and [generational-arena] is that this crate currently provides no way to delete
+entities. This limits its use to situations where deleting isn't important,
+however this also makes it more efficient, because it doesn't need extra
+bookkeeping state to reuse the storage for deleted objects, or to ensure that
+new objects always have unique keys (eg. slotmap's and generational-arena's
+versioning).
+
+Another major difference is that this crate protects against using a key from
+one map to access an element in another. Where `SlotMap`, `Slab`, and `Arena`
+have a value type parameter, `PrimaryMap` has a key type parameter and a value
+type parameter. The crate also provides the `entity_impl` macro which makes it
+easy to declare new unique types for use as keys. Any attempt to use a key in
+a map it's not intended for is diagnosed with a type error.
+
+Another is that this crate has two core map types, `PrimaryMap` and
+`SecondaryMap`, which serve complementary purposes. A `PrimaryMap` creates its
+own keys when elements are inserted, while an `SecondaryMap` reuses the keys
+values of a `PrimaryMap`, conceptually storing additional data in the same
+index space. `SecondaryMap`'s values must implement `Default` and all elements
+in an `SecondaryMap` initially have the value of `default()`.
+
+A common way to implement `Default` is to wrap a type in `Option`, however
+this crate also provides the `PackedOption` utility which can use less memory
+in some cases.
+
+Additional utilities provided by this crate include:
+ - `EntityList`, for allocating many small arrays (such as instruction operand
+    lists in a compiler code generator).
+ - `SparseMap`: an alternative to `SecondaryMap` which can use less memory
+   in some situations.
+ - `EntitySet`: a specialized form of `SecondaryMap` using a bitvector to
+   record which entities are members of the set.
+
+[slotmap]: https://crates.io/crates/slotmap
+[slab]: https://crates.io/crates/slab
+[generational-arena]: https://crates.io/crates/generational-arena
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));
+    }
+}