[Bug tree-optimization/110481] New: Possible improvements in dense switch statement returning values

["tkoenig at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110481

            Bug ID: 110481
           Summary: Possible improvements in dense switch statement
                    returning values
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

Putting this provisionally into tree-optimization, although there may
be other aspects.

Consider

unsigned int foo(unsigned int a)
{
  switch ((a >> 10) & 3)
    {
    case 0:
      return 8;
    case 1:
      return 16;
    case 2:
      return 32;
    case 3:
      return 64;
    }
}

unsigned int bar(unsigned int a)
{
  return 1u << (((a >> 10) & 3) + 3);
}

unsigned int baz (unsigned int a)
{
  switch (a & (3 << 10))
    {
    case 0:
      return 8;
    case 1 << 10:
      return 16;
    case 2 << 10:
      return 32;
    case 3 << 10:
      return 64;
    }
}

which all do the same thing.

The code for bar is

bar:
.LFB1:
        .cfi_startproc
        shrl    $10, %edi
        movl    $1, %eax
        movl    %edi, %ecx
        andl    $3, %ecx
        addl    $3, %ecx
        sall    %cl, %eax
        ret

which is optimum except for the register move (submitted as PR110479).

The compiler does not recognize that foo or baz are equivalent to bar,
but that may be too much of a special case to really consider. 

The code for foo is

foo:
.LFB0:
        .cfi_startproc
        shrl    $10, %edi
        movl    $8, %eax
        andl    $3, %edi
        decl    %edi
        cmpl    $2, %edi
        ja      .L1
        movzbl  CSWTCH.1(%rdi), %eax
.L1:
        ret
        .cfi_endproc

[...]

CSWTCH.1:
        .byte   16
        .byte   32
        .byte   64

where it seems strange that there is a comparison and conditional
jump around the load.  A look at *.optimized shows

<bb 2> [local count: 1073741824]:
  _1 = a_4(D) >> 10;
  _2 = _1 & 3;
  _8 = _2 + 4294967295;
  if (_8 <= 2)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  _6 = CSWTCH.1[_8];
  _5 = (unsigned int) _6;

  <bb 4> [local count: 1073741824]:
  # _3 = PHI <_5(3), 8(2)>
  return _3;

which assigns a probability of 50% to (a>>10)& 3 being zero.
Where this comes from is unclear to me.  A straightforward load
from a table which also includes the 8 seems more logical to me
(especially with -Os).

Finally, baz generates

baz:
.LFB2:
        .cfi_startproc
        andl    $3072, %edi
        movl    $32, %eax
        cmpl    $2048, %edi
        je      .L6
        ja      .L8
        movl    $8, %eax
        testl   %edi, %edi
        je      .L6
        movl    $16, %eax
        ret
.L8:
        movl    $64, %eax
.L6:
        ret

when transforming into something equivalent to foo (or even bar)
would seem advantageous.