[Bug tree-optimization/96245] New: Failure to optimize arithmetic pattern in switch

[Bug tree-optimization/96245] New: Failure to optimize arithmetic pattern in switch

[gabravier at gmail dot com]

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

            Bug ID: 96245
           Summary: Failure to optimize arithmetic pattern in switch
           Product: gcc
           Version: 11.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: ---

void f(int x)
{
    switch (x)
    {
        case 0:
            putchar('0');
            break;
        case 1:
            putchar('1');
            break;
        case 2:
            putchar('2');
            break;
        case 3:
            putchar('3');
            break;
        case 4:
            putchar('4');
            break;
        case 5:
            putchar('5');
            break;
        case 6:
            putchar('6');
            break;
        case 7:
            putchar('7');
            break;
        case 8:
            putchar('8');
            break;
        case 9:
            putchar('9');
            break;
    }
}

This can be optimized to `if ((unsigned)x < 10) putchar('0' + x);`. This
transformation is done by LLVM, but not by GCC.

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-07-20
                 CC|                            |marxin at gcc dot gnu.org
           Keywords|                            |missed-optimization
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
switch-conversion(?), it does look like a very special case.  Similar:

int y;
void f(int x)
{
    switch (x)
    {
        case 0:
          y = 0;
          break;
        case 1:
          y = 1;
          break;
...

converting to  if (...) y = x;  or more general to x + CST.  The store
commoning patch should in this case sink this to y = PHI<...> where
switch-conversion would convert the PHI<...>.  For the putchar case
there's nothing "commoming" the call (the same code doing the store
sinking could also sink calls if we want that).  Not sure if
switch-conversion itself would want to do this (profitability increases
if we can eliminate the PHI<> by arithmetics).

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[msebor at gcc dot gnu.org]

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

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |msebor at gcc dot gnu.org

--- Comment #2 from Martin Sebor <msebor at gcc dot gnu.org> ---
I wonder if discouraging this pattern by warning on it and suggesting the
simpler alternative would be worthwhile (either in addition to or in lieu of
the optimization) to help avoid typos resulting from copy-and-paste mistakes
that cannot very well be detected.  As in:

void f(int x)
{
    switch (x)
    {
        case 0:
            putchar('0');
            break;
        case 1:
            putchar('1');
            break;
        ...
        case 7:
            putchar('6');   <<< typo
            break;
        ...
  }

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[josephcsible at gmail dot com]

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

Joseph C. Sible <josephcsible at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |josephcsible at gmail dot com

--- Comment #3 from Joseph C. Sible <josephcsible at gmail dot com> ---
(In reply to Martin Sebor from comment #2)
> I wonder if discouraging this pattern by warning on it and suggesting the
> simpler alternative would be worthwhile (either in addition to or in lieu of
> the optimization) to help avoid typos resulting from copy-and-paste mistakes
> that cannot very well be detected.

I don't see how such a warning would be particularly useful in practice.
Wouldn't one of these two things have to be true?

1. It would only warn you when you used the typo-prone pattern but didn't
actually make any typos in it
2. The warning would trigger in code where the author intentionally breaks the
pattern for some cases

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[msebor at gcc dot gnu.org]

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

--- Comment #4 from Martin Sebor <msebor at gcc dot gnu.org> ---
Only (1) would be true.  Like the optimization, the warning wouldn't trigger in
code that didn't follow the pattern because there's no way to tell if that's
deliberate or a bug.

I'd expect the warning to be useful by discouraging a questionable pattern.  I
don't suppose this comes up a lot so like the optimization, the difference the
warning would make in practice can be debated.  Unlike the optimization alone,
though, it would lead to less repetitive and so more readable code.

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |marxin at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
           Assignee|marxin at gcc dot gnu.org          |unassigned at gcc dot gnu.org

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Leaving for now as it's probably not material for switch-coversion (I mean the
putchar test-case).

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |vries at gcc dot gnu.org

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think it isn't really a too special case, of course one shouldn't take it
literally and look for a particular call etc.
But, generally try to see if all the switch cases are the same except some
constant or two (same e.g. in the ICF sense) and if that constant or two is
linear vs. the corresponding case.
It can be done either in switchconv, or could be perhaps some kind of
GIMPLE_SWITCH aware parametrized tail merging/cross jumping.
As it would (or could) turn constant expressions into non-constant, I guess
we'd need to take some conservative approach with __builtin_constant_p, punt if
there is a __builtin_constant_p in the block, either altogether, or if it is
among (recursively) the immediate uses of the stmt where the constant(s)
appear.

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Looking at godbolt and LLVM release notes, this optimization appeared in LLVM 9
and looks to be a switch optimization:

LLVM can now sink similar instructions to a common successor block also when
the instructions have no uses, such as calls to void functions. This allows
code such as

void g(int);
enum e { A, B, C, D };
void f(e x, int y, int z) {
  switch(x) {
    case A: g(6); break;
    case B: g(3); break;
    case C: g(9); break;
    case D: g(2); break;
  }
}

to be optimized to a single call to g, with the argument loaded from a lookup
table.
I bet it is https://reviews.llvm.org/D59936

We don't optimize even:
void
foo (int *p, int x)
{
  switch (x)
    {
    case 7: *p = 14; break;
    case 8: *p = 15; break;
    case 9: *p = 16; break;
    case 10: *p = 17; break;
    case 11: *p = 18; break;
    case 12: *p = 19; break;
    default: return;
    }
}
but do optimize if one performs the switch parametrized tail merging manually:
void
bar (int *p, int x)
{
  int y;
  switch (x)
    {
    case 7: y = 14; break;
    case 8: y = 15; break;
    case 9: y = 16; break;
    case 10: y = 17; break;
    case 11: y = 18; break;
    case 12: y = 19; break;
    default: return;
    }
  *p = y;
}

So, do you prefer to do this in tree-ssa-tail-merge.c (for blocks starting with
switches) or in tree-switch-conversion.c, and should we handle both the case
where the constant(s) are linear vs. the switch expression, or also any other
(let the switchconv pass then create the arrays)?

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Effectively it would be the inverse of jump threading optimization, though I
think we don't do it for switches, turning say:
void
foo (int *p, int x)
{
  switch (x)
    {
    case 7:
    case 8:
    case 9:
    case 10:
    case 11:
    case 12: *p = 12 + x; break;
    default: return;
    }
}
into the above foo.

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[rguenther at suse dot de]

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

--- Comment #9 from rguenther at suse dot de <rguenther at suse dot de> ---
On December 14, 2020 12:19:32 PM GMT+01:00, "jakub at gcc dot gnu.org"
<gcc-bugzilla@gcc.gnu.org> wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96245
>
>--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
>Looking at godbolt and LLVM release notes, this optimization appeared
>in LLVM 9
>and looks to be a switch optimization:
>
>LLVM can now sink similar instructions to a common successor block also
>when
>the instructions have no uses, such as calls to void functions. This
>allows
>code such as
>
>void g(int);
>enum e { A, B, C, D };
>void f(e x, int y, int z) {
>  switch(x) {
>    case A: g(6); break;
>    case B: g(3); break;
>    case C: g(9); break;
>    case D: g(2); break;
>  }
>}
>
>to be optimized to a single call to g, with the argument loaded from a
>lookup
>table.
>I bet it is https://reviews.llvm.org/D59936
>
>We don't optimize even:
>void
>foo (int *p, int x)
>{
>  switch (x)
>    {
>    case 7: *p = 14; break;
>    case 8: *p = 15; break;
>    case 9: *p = 16; break;
>    case 10: *p = 17; break;
>    case 11: *p = 18; break;
>    case 12: *p = 19; break;
>    default: return;
>    }
>}

Store commoning in the sink pass should do this. But it would need to create a
forwarder because of the default case. 
That's a missed piece there. 

>but do optimize if one performs the switch parametrized tail merging
>manually:
>void
>bar (int *p, int x)
>{
>  int y;
>  switch (x)
>    {
>    case 7: y = 14; break;
>    case 8: y = 15; break;
>    case 9: y = 16; break;
>    case 10: y = 17; break;
>    case 11: y = 18; break;
>    case 12: y = 19; break;
>    default: return;
>    }
>  *p = y;
>}
>
>So, do you prefer to do this in tree-ssa-tail-merge.c (for blocks
>starting with
>switches) or in tree-switch-conversion.c, and should we handle both the
>case
>where the constant(s) are linear vs. the switch expression, or also any
>other
>(let the switchconv pass then create the arrays)?

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
That is just one specific special case, it can be anything else, like
case 7: p[14] = 1; break;
case 8: p[13] = 1; break;
case 9: p[12] = 1; break;
case 10: p[11] = 1; break;
etc.
I think there are advantages of doing this in switchconv, namely that it would
be done only if the switchconv pass finds out it would be beneficial, but there
can be advantages doing that in tail-merging too, mainly for -Os or proven cold
code it is often but not always to optimize this (not only if either the code
is very small or if between pre and switchconv we can simplify it if it is
constant).

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |llvm at rifkin dot dev

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 103072 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/96245] Failure to optimize arithmetic pattern in switch

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |b.buschinski at googlemail dot com

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 113741 has been marked as a duplicate of this bug. ***