Adding an unreachable branch helps optimize the code when matching on `x % N`

[WaffleLapkin]

Consider this example:

pub fn parse(x: usize) -> usize {
    match x % 5 {
        0 => f1(x),
        1 => f2(x),
        2 => f3(x),
        3 => f4(x),
        4 => f5(x),
        // 5 | 6 | 7 => loop{},
        _ => loop{},
    }
}

It currently generates similar LLVM-IR:

start:
  %_2 = urem i64 %x, 5, !dbg !10
  switch i64 %_2, label %bb12 [
    i64 0, label %bb2
    i64 1, label %bb4
    i64 2, label %bb6
    i64 3, label %bb8
    i64 4, label %bb10
  ], !dbg !11
; ...
bb12:
  br label %bb12, !dbg !32

Even though the default branch is unreachable (x % 5 can't be greater than 4) it is still generated.

But, when un-commenting 5 | 6 | 7 => loop{} line (still unreachable branch, that does the same as default) the default branch becomes unreachable:

start:
  %_2 = urem i64 %x, 5, !dbg !10
  switch i64 %_2, label %bb14 [
    i64 0, label %bb2
    i64 1, label %bb4
    i64 2, label %bb6
    i64 3, label %bb8
    i64 4, label %bb10
  ], !dbg !11
; ...
bb14:
  unreachable

So, adding an unreachable branch that does the same as the default helps optimize the code.

Some notes:

• These differences then propagate to assembler, i.e. it also has an unreachable branch when 5 | 6 | 7 is commented-out
• godbolt link
• Range patterns (like 5..=7) do not help
• Making the default branch 5 | 6 | 7 | _ doesn't help either
• Similar things happen for any N in x % N that is not a power of two -- adding unreachable branches until the last branch has a power-of-two-minus-one-value helps optimizing the code
  • N = 3 (3 =>)
  • N = 9 (9 | 10 | 11 | 12 | 13 | 14 | 15 =>)
  • N = 14 (14 | 15 =>)
• loop{}s can be replaced with anything else, for example unreachable!() or panic!(), effect is still the same
  • in case of panic-like things not removing the panicking branch seems like a big deal
  • I've used loop{}s to make diffs less noisy
• if-else-if chains are identical to match here
• clang seems to handle this situation just fine in any case: godbolt link
  • it also makes the last reachable branch default in llvm-ir, instead of generating an unreachable one

[WaffleLapkin]

@rustbot label +A-codegen +C-enhancement +I-slow +T-compiler

[scottmcm]

I think there's an LLVM bug here, despite your clang example.

Here's a demonstration using just opt that it doesn't notice the defaultdest is unreachable, and thus leaves the infinite loop there: https://llvm.godbolt.org/z/GcG1dM3sq

[erikdesjardins]

In LLVM, when the optimization fires, the unreachable bb is replaced with .unreachabledefault (https://llvm.godbolt.org/z/jWeeWYKhE), so we can tell it's created by createUnreachableSwitchDefault, called from here: https://github.com/llvm/llvm-project/blob/c25ba3c79020246b24aa658ac02770be07eee0f5/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L4990.

That code determines whether or not the default condition is reachable based on the number of significant bits in the condition, which is why it doesn't work until you have power-of-2-minus-1 cases. It could be made more precise. (I'm looking into this.)

[nikic]

I believe https://reviews.llvm.org/D106056 has already fixed this. Unfortunately, this exposed some compile-time issues in the backend, which haven't been resolved yet, so the patch is reverted for now.

[erikdesjardins]

Looks like this will be handled better in LLVM 18 (after #120055): https://godbolt.org/z/reaf5oKcb

[nikic]

@erikdesjardins I believe the relevant change has been reverted.

[mati865]

There is a PR that adds unreachable like that: https://github.com/rust-lang/rust/pull/120268

[DianQK]

There is a PR that adds unreachable like that: #120268

It only solves enum scenarios. https://github.com/llvm/llvm-project/pull/76669 will partially solve the issue. It was also reverted due to some codegen issues.

[DianQK]

I believe https://reviews.llvm.org/D106056 has already fixed this. Unfortunately, this exposed some compile-time issues in the backend, which haven't been resolved yet, so the patch is reverted for now.

Looks like the same issue I'm having.

[DianQK]

There is a PR that adds unreachable like that: #120268

It only solves enum scenarios. The enum scenario has been solved, this PR is an extension.

https://github.com/llvm/llvm-project/pull/76669 will partially solve the issue. It was also reverted due to some backend issues.

[erikdesjardins]

llvm/llvm-project#76669 will partially solve the issue. It was also reverted due to some backend issues.

That change got unreverted and was included in the recent LLVM 19 upgrade, so I believe this is now fixed: https://godbolt.org/z/1MvffeWff

@rustbot label E-needs-test

[DianQK]

This is probably fixed by https://github.com/llvm/llvm-project/pull/79993.

Hmm, looks like 1.78 has fixed this: https://rust.godbolt.org/z/n4fbG4xj4.