Repository: rust
Issue: Combined enum optimization
Labels: T-compiler,C-feature-request

Not totally sure how to title this issue. Not even sure if this can be solved in `rustc`, or if such optimizations happen in `llvm`. The issue is about an exhaustiveness optimization that the compiler performs for certain enums, but not for others, depending on the discriminant value.

Let's say we have two enums:
```rust
#[repr(u8)]
pub enum InnerA {
    A = 0b00,
    B = 0b01,
}

#[repr(u8)]
pub enum InnerB {
    A = 0b00,
    B = 0b10,
}
```

and want to create a combined type that also only takes up 8 bits. Using a `struct` with two fields does not work here, since the compiler doesn't 'merge' the enums into one byte, so we'd end up with 2 bytes instead.
We either have to use a bitmap, or we have to create a third enum. A third enum is more verbose but usually leads to cleaner (and better optimized) code down the line.

```rust
#[repr(u8)]
pub enum Combined {
    AA = 0b00,
    BA = 0b01,
    AB = 0b10,
    BB = 0b11,
}
```

If we now add all the required methods for converting between `u8` and the enum and checkout the generated code, we can see that the compiler does an amazing job at optimizing all the `unreachable`s away. [[godbolt](https://rust.godbolt.org/z/5EdfG7vq6)]

<details>
<summary>Code</summary>

```rust
#[repr(u8)]
#[derive(Copy, Clone)]
pub enum Combined {
    AA = 0b00,
    BA = 0b01,
    AB = 0b10,
    BB = 0b11,
}

impl Combined {
    pub const fn new(a: InnerA, b: InnerB) -> Self {
        match Self::from_u8(a as u8 | b as u8) {
            Some(combined) => combined,
            None => unreachable!(),
        }
    }
    
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b00 => Some(Self::AA),
            0b01 => Some(Self::BA),
            0b10 => Some(Self::AB),
            0b11 => Some(Self::BB),
            _ => None,
        }
    }
    
    pub const fn a(self) -> InnerA {
        let a = self as u8 & InnerA::B as u8;
        match InnerA::from_u8(a) {
            Some(a) => a,
            None => unreachable!(),
        }
    }
    
    pub const fn b(self) -> InnerB {
        let b = self as u8 & InnerB::B as u8;
        match InnerB::from_u8(b) {
            Some(b) => b,
            None => unreachable!(),
        }
    }
}

#[repr(u8)]
pub enum InnerA {
    A = 0b00,
    B = 0b01,
}

impl InnerA {
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b00 => Some(Self::A),
            0b01 => Some(Self::B),
            _ => None,
        }
    }
}

#[repr(u8)]
pub enum InnerB {
    A = 0b00,
    B = 0b10,
}


impl InnerB {
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b00 => Some(Self::A),
            0b10 => Some(Self::B),
            _ => None,
        }
    }
}
```
</details>
<details>
<summary>Assembly</summary>

```asm
example::Combined::new:
        mov     eax, edi
        or      eax, esi
        ret

example::Combined::from_u8:
        cmp     dil, 4
        mov     eax, 4
        cmovb   eax, edi
        ret

example::Combined::a:
        mov     eax, edi
        and     al, 1
        ret

example::Combined::b:
        cmp     dil, 2
        setae   al
        add     al, al
        ret

example::InnerA::from_u8:
        cmp     dil, 1
        sete    al
        mov     cl, 2
        sub     cl, al
        xor     edx, edx
        test    dil, dil
        movzx   eax, cl
        cmove   eax, edx
        ret

example::InnerB::from_u8:
        cmp     dil, 2
        sete    al
        xor     al, 3
        xor     ecx, ecx
        test    dil, dil
        movzx   eax, al
        cmove   eax, ecx
        ret
```
</details>

If we now change the enum discriminates, however, so that not every possible bit pattern is covered, there's now suddenly a branch in `Combined::new` [[godbolt](https://rust.godbolt.org/z/s8jfTofvM)].

<details>
<summary>Code</summary>

```rust
#[repr(u8)]
#[derive(Copy, Clone)]
pub enum Combined {
    AA = 0b000,
    BA = 0b001,
    AB = 0b100,
    BB = 0b101,
}

impl Combined {
    pub const fn new(a: InnerA, b: InnerB) -> Self {
        match Self::from_u8(a as u8 | b as u8) {
            Some(combined) => combined,
            None => unreachable!(),
        }
    }
    
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b000 => Some(Self::AA),
            0b001 => Some(Self::BA),
            0b100 => Some(Self::AB),
            0b101 => Some(Self::BB),
            _ => None,
        }
    }
    
    pub const fn a(self) -> InnerA {
        let a = self as u8 & InnerA::B as u8;
        match InnerA::from_u8(a) {
            Some(a) => a,
            None => unreachable!(),
        }
    }
    
    pub const fn b(self) -> InnerB {
        let b = self as u8 & InnerB::B as u8;
        match InnerB::from_u8(b) {
            Some(b) => b,
            None => unreachable!(),
        }
    }
}

#[repr(u8)]
pub enum InnerA {
    A = 0b000,
    B = 0b001,
}

impl InnerA {
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b000 => Some(Self::A),
            0b001 => Some(Self::B),
            _ => None,
        }
    }
}

#[repr(u8)]
pub enum InnerB {
    A = 0b000,
    B = 0b100,
}


impl InnerB {
    pub const fn from_u8(val: u8) -> Option<Self> {
        match val {
            0b000 => Some(Self::A),
            0b100 => Some(Self::B),
            _ => None,
        }
    }
}
```
</details>

<details>
<summary>Assembly</summary>

```asm
example::Combined::new:
        or      edi, esi
        cmp     dil, 5
        ja      .LBB0_2
        movzx   eax, dil
        mov     ecx, 51
        bt      ecx, eax
        jae     .LBB0_2
        mov     eax, edi
        ret
.LBB0_2:
        push    rax
        lea     rdi, [rip + .L__unnamed_1]
        lea     rdx, [rip + .L__unnamed_2]
        mov     esi, 40
        call    qword ptr [rip + core::panicking::panic@GOTPCREL]
        ud2

example::Combined::from_u8:
        lea     ecx, [8*rdi]
        movabs  rdx, 5514839064832
        shr     rdx, cl
        cmp     dil, 6
        mov     eax, 6
        cmovb   eax, edx
        ret

example::Combined::a:
        mov     eax, edi
        and     al, 1
        ret

example::Combined::b:
        cmp     dil, 4
        setae   al
        shl     al, 2
        ret

example::InnerA::from_u8:
        cmp     dil, 1
        sete    al
        mov     cl, 2
        sub     cl, al
        xor     edx, edx
        test    dil, dil
        movzx   eax, cl
        cmove   eax, edx
        ret

example::InnerB::from_u8:
        cmp     dil, 4
        sete    al
        xor     al, 5
        xor     ecx, ecx
        test    dil, dil
        movzx   eax, al
        cmove   eax, ecx
        ret

.L__unnamed_1:
        .ascii  "internal error: entered unreachable code"

.L__unnamed_3:
        .ascii  "/app/example.rs"

.L__unnamed_2:
        .quad   .L__unnamed_3
        .asciz  "\017\000\000\000\000\000\000\000\016\000\000\000\025\000\000"
```
</details>

In my [original code](https://rust.godbolt.org/z/Er5fEo9sG) there are even more branches.

Is there a way to fix the relevant optimizations to apply to all enums, no matter the discriminant values? I'd be happy to do the required work myself. I've however never worked on the compiler, so I'd need some hints about which pieces of code to look at.