[Bug tree-optimization/102927] New: Failure to optimize series of if-else to use array when possible

[Bug tree-optimization/102927] New: Failure to optimize series of if-else to use array when possible

[gabravier at gmail dot com]

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

            Bug ID: 102927
           Summary: Failure to optimize series of if-else to use array
                    when possible
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int foo(int i) {
  if (i == 0)
    return 52;
  else if (i == 1)
    return 77;
  else if (i == 2)
    return 91;
  else if (i == 3)
    return 10;
  else
    return 42;
}

int bar(int i) {
  switch (i) {
  case 0:
    return 52;
  case 1:
    return 77;
  case 2:
    return 91;
  case 3:
    return 10;
  default:
    return 42;
  }
}

int baz(int i)
{
    static const int results[] = {52, 77, 91, 10};
    if (__builtin_expect_with_probability((unsigned)i < 4, 1, 0.5))
        return results[(unsigned)i];
    return 42;
}

foo can be optimized to be equivalent to baz (like bar is). This optimization
is done by LLVM, but not by GCC.

PS: I've observed that making the if-else chain longer triggers the
optimization. Is GCC considering the if-else chain to be faster than an array
access ? Because in that case, it seems like bar should be optimized to an
if-else chain (perhaps along with bar).

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-10-25
                 CC|                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think we're doing a two-step conversion, if-to-switch and then switch
conversion rather than analyzing to a common representation and then doing
code generation as IIRC I suggested when if-to-switch was introduced.

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[marxin at gcc dot gnu.org]

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

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Gabriel Ravier from comment #0)
> int foo(int i) {
>   if (i == 0)
>     return 52;
>   else if (i == 1)
>     return 77;
>   else if (i == 2)
>     return 91;
>   else if (i == 3)
>     return 10;
>   else
>     return 42;
> }
> 

As Richi said, we do the transformation to switch only if we can expand it by
jump table, bit test or array access.

You can expand this example with:
--param case-values-threshold=4

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[marxin at gcc dot gnu.org]

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

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
> As Richi said, we do the transformation to switch only if we can expand it
> by jump table, bit test or array access.
> 
> You can expand this example with:
> --param case-values-threshold=4

and we end up with array access:

$ gcc -c pr102927.c -O2 --param case-values-threshold=4
-fdump-tree-optimized=/dev/stdout

;; Function foo (foo, funcdef_no=0, decl_uid=1943, cgraph_uid=1,
symbol_order=0)

Removing basic block 5
int foo (int i)
{
  int _1;
  unsigned int _3;
  int _4;

  <bb 2> [local count: 1073741824]:
  _3 = (unsigned int) i_2(D);
  if (_3 <= 3)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  _4 = CSWTCH.1[_3];

  <bb 4> [local count: 1073741824]:
  # _1 = PHI <42(2), _4(3)>
  return _1;

}

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |INVALID
             Status|NEW                         |RESOLVED

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
I tend to close it as invalid.

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[gabravier at gmail dot com]

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

--- Comment #5 from Gabriel Ravier <gabravier at gmail dot com> ---
Um, what ? How is this invalid, exactly ? Are you saying foo is faster than baz
(in which case it seems the opposite optimization should be implemented for baz
and bar), or that this optimization just won't ever be implemented (which seems
like more of a WONTFIX), or something else ? This seems kind of odd...

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|INVALID                     |---
             Status|RESOLVED                    |NEW

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, note there might be another bug for this already filed too where I
have some suggestions on how to have this fixed  too.

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[marxin at gcc dot gnu.org]

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

--- Comment #7 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Gabriel Ravier from comment #5)
> Um, what ? How is this invalid, exactly ? Are you saying foo is faster than
> baz (in which case it seems the opposite optimization should be implemented
> for baz and bar), or that this optimization just won't ever be implemented
> (which seems like more of a WONTFIX), or something else ? This seems kind of
> odd...

I say that we optimize 'foo' as 'baz' (if you adjust the minimal number of
cases we consider beneficial: --param case-values-threshold=4).

[Bug tree-optimization/102927] Failure to optimize series of if-else to use array when possible

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |DUPLICATE
             Status|NEW                         |RESOLVED

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Dup of bug 40748 and others.

*** This bug has been marked as a duplicate of bug 40748 ***