transmutability: Mark edges by ranges, not values

In the `Tree` and `Dfa` representations of a type's layout, store byte
ranges rather than needing to separately store each byte value. This
permits us to, for example, represent a `u8` using a single 0..=255 edge
in the DFA rather than using 256 separate edges.

This leads to drastic performance improvements. For example, on the
author's 2024 MacBook Pro, the time to convert the `Tree` representation
of a `u64` to its equivalent DFA representation drops from ~8.5ms to
~1us, a reduction of ~8,500x. See `bench_dfa_from_tree`.

Similarly, the time to execute a transmutability query from `u64` to
`u64` drops from ~35us to ~1.7us, a reduction of ~20x. See
`bench_transmute`.

1 files changed, 4 insertions, 4 deletions

diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
index 70ecc75403f..6a09be18ef9 100644
--- a/compiler/rustc_transmute/src/layout/tree.rs
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -54,22 +54,22 @@ where
 
     /// A `Tree` containing a single, uninitialized byte.
     pub(crate) fn uninit() -> Self {
-        Self::Byte(Byte::Uninit)
+        Self::Byte(Byte::uninit())
     }
 
     /// A `Tree` representing the layout of `bool`.
     pub(crate) fn bool() -> Self {
-        Self::from_bits(0x00).or(Self::from_bits(0x01))
+        Self::Byte(Byte::new(0x00..=0x01))
     }
 
     /// A `Tree` whose layout matches that of a `u8`.
     pub(crate) fn u8() -> Self {
-        Self::Alt((0u8..=255).map(Self::from_bits).collect())
+        Self::Byte(Byte::new(0x00..=0xFF))
     }
 
     /// A `Tree` whose layout accepts exactly the given bit pattern.
     pub(crate) fn from_bits(bits: u8) -> Self {
-        Self::Byte(Byte::Init(bits))
+        Self::Byte(Byte::from_val(bits))
     }
 
     /// A `Tree` whose layout is a number of the given width.