Missing optimization for switch from int to bool

[majnemer]

Consider a function like:

extern "C" bool src(int x) {
    switch (x) {
        case 1:
        case 2:
        case 4:
        case 8:
            return true;
        default:
            return false;
    }
}

My clang/LLVM build gives back:

define dso_local zeroext i1 @src(i32 noundef %0) local_unnamed_addr #0 {
  %2 = add i32 %0, -1
  %3 = icmp ult i32 %2, 8
  %4 = trunc i32 %2 to i8
  %5 = lshr i8 -117, %4
  %6 = and i8 %5, 1
  %7 = icmp ne i8 %6, 0
  %8 = select i1 %3, i1 %7, i1 false
  ret i1 %8
}

This is sort-of like writing:

extern "C" bool src(int x) {
    --x;
    return x < 8u & ((((1 << 0) | (1 << 1) | (1 << 3) | (1 << 7)) >> x) & 1) == 1;
}

I think this could be simplified further to:

define dso_local zeroext i1 @tgt(i32 noundef %0) local_unnamed_addr #0 {
  %2 = icmp ult i32 %0, 9
  %3 = lshr i32 278, %0
  %4 = and i32 %3, 1
  %5 = icmp ne i32 %4, 0
  %6 = select i1 %2, i1 %5, i1 false
  ret i1 %6
}

For clarity, this is as-if we wrote the code initially as:

extern "C" bool tgt(int x) {
    return x < 9u && ((((1 << 1) | (1 << 2) | (1 << 4) | (1 << 8)) >> x) & 1) == 1;
}

[erikdesjardins]

Alive2 link for convenience: https://alive2.llvm.org/ce/z/3m384E (for this specific case, not a general proof)

[alexander-shaposhnikov]

https://reviews.llvm.org/D128897

[zmodem]

Thanks for the bug report!

One way to think about this is as a special case of:

 int f(int x) {
    switch (x) {
        case 1: return 1;
        case 2: return 5;
        case 3: return 7;
        case 4: return 18;
    }
    return 0;
}

LLVM will essentially generate

return (x - 1) < 4 ? table[x - 1] : 0;

but we could avoid the subtraction if we grew the table by synthesizing a case 0. In your example, growing the table has zero cost since it would still fit in a register.