suboptimal code for switch statement

[bhaible]

In a switch statement with identical code in two branches, clang 20 (on x86_64) produces suboptimal code (with more conditional jumps than needed).

How to reproduce:
Save this file as foo.c:

int foo (int c)
{
  int p = 0;
  switch (c)
    {
    case 'c': case 's':
      p = 1;
      break;
    case 'f': case 'F': case 'e': case 'E': case 'g': case 'G':
    case 'a': case 'A':
      p = 1;
      break;
    }
  return p;
}

Run this command:

$ clang -O2 -c foo.c && objdump -d -r foo.o

Actual output:

foo.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
   0:   31 c0                   xor    %eax,%eax
   2:   83 c7 bf                add    $0xffffffbf,%edi
   5:   83 ff 32                cmp    $0x32,%edi
   8:   77 15                   ja     1f <foo+0x1f>
   a:   48 b9 71 00 00 00 71    movabs $0x7100000071,%rcx
  11:   00 00 00 
  14:   48 0f a3 f9             bt     %rdi,%rcx
  18:   73 06                   jae    20 <foo+0x20>
  1a:   b8 01 00 00 00          mov    $0x1,%eax
  1f:   c3                      ret
  20:   48 b9 00 00 00 00 04    movabs $0x4000400000000,%rcx
  27:   00 04 00 
  2a:   48 0f a3 f9             bt     %rdi,%rcx
  2e:   72 ea                   jb     1a <foo+0x1a>
  30:   eb ed                   jmp    1f <foo+0x1f>

Expected output:

foo.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
   0:   31 c0                   xor    %eax,%eax
   2:   83 c7 bf                add    $0xffffffbf,%edi
   5:   83 ff 32                cmp    $0x32,%edi
   8:   77 15                   ja     1f <foo+0x1f>
   a:   48 b9 71 00 00 00 75    movabs $0x4007500000071,%rcx
  11:   00 04 00 
  14:   48 0f a3 f9             bt     %rdi,%rcx
  18:   73 05                   jae    1f <foo+0x1f>
  1a:   b8 01 00 00 00          mov    $0x1,%eax
  1f:   c3                      ret

[bhaible]

gcc 5 or newer generates the optimized code. It looks like gcc merges the various cases before generating the code for the switch statement, and clang does not do so.

[nikic]

Hm, we have two predecessors with the same phi node entry: https://clang.godbolt.org/z/8aha439cG

I thought simplifyDuplicateSwitchArms() would handle this, but I think this check prevents it: https://github.com/llvm/llvm-project/blame/19afd27eb8efbe88392aea3294c2d7591eadc94f/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L7510 We could cache the unique predecessor to avoid quadratic runtime.

cc @antoniofrighetto