[Bug c++/96480] New: missed optimisation: unnecessary compare in standard algorithms

[Bug c++/96480] New: missed optimisation: unnecessary compare in standard algorithms

[kurkindmit at gmail dot com]

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

            Bug ID: 96480
           Summary: missed optimisation: unnecessary compare in standard
                    algorithms
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kurkindmit at gmail dot com
  Target Milestone: ---

Consider the C++ code:

#include <algorithm>
#include <array>

enum ENUM { A, B, C, D, E, F, G, };

const std::array<ENUM, 4> foo{A, B, C, D};

bool is_foo(ENUM e) {
    return std::any_of(foo.begin(), foo.end(),
    [e] (auto ee) { return e == ee; });
}

GCC 7.4 optimizes if_foo to a single compare operation e <= 3,
but newer GCC versions do two comare operations e <= 2 || e == 3.

see https://godbolt.org/z/5a6aPa

[Bug c++/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |8.5
     Ever confirmed|0                           |1
            Summary|missed optimisation:        |[8/9/10/11 Regression]
                   |unnecessary compare in      |missed optimisation:
                   |standard algorithms         |unnecessary compare in
                   |                            |standard algorithms
   Last reconfirmed|                            |2020-08-05
                 CC|                            |jakub at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r8-565-g7581ce9a1ad6df9c8998a3c74256837a1ff6f7cc

[Bug c++/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
That commit changes the pre-reassoc2 dump like:
--- pr96480.ii.172t.printf-return-value2_       2020-08-05 07:22:42.000000000
-0400
+++ pr96480.ii.172t.printf-return-value2        2020-08-05 07:23:32.000000000
-0400
@@ -31,13 +31,13 @@ bool is_foo(ENUM) (ENUM e)

   <bb 5> [12.87%]:
   if (e_2(D) == 3)
-    goto <bb 7> (<L4>); [3.00%]
+    goto <bb 6>; [3.00%]
   else
-    goto <bb 6>; [97.00%]
+    goto <bb 7> (<L4>); [97.00%]

-  <bb 6> [12.48%]:
+  <bb 6> [0.39%]:

-  # prephitmp_5 = PHI <1(2), 1(3), 1(4), 1(5), 0(6)>
+  # prephitmp_5 = PHI <1(2), 1(3), 1(4), 1(6), 0(5)>
 <L4> [14.13%]:
   return prephitmp_5;

So I guess I need to debug why reassoc doesn't like that form.

[Bug tree-optimization/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
          Component|c++                         |tree-optimization
           Keywords|                            |missed-optimization

[Bug tree-optimization/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Simplified testcase:
int v[4];

int
foo (int x)
{
  int *p;
  if (x == 0)
    p = &v[0];
  else if (x == 1)
    p = &v[1];
  else if (x == 2)
    p = &v[2];
  else if (x == 3)
    p = &v[3];
  else
    p = &v[4];
  return p != &v[4];
}

[Bug tree-optimization/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49005
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49005&action=edit
gcc11-pr96480.patch

Untested fix.

[Bug tree-optimization/96480] [8/9/10/11 Regression] missed optimisation: unnecessary compare in standard algorithms

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:b3aa137212b1af0c824a9890eba2ca27a7271d56

commit r11-2593-gb3aa137212b1af0c824a9890eba2ca27a7271d56
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Aug 6 15:47:25 2020 +0200

    reassoc: Improve maybe_optimize_range_tests [PR96480]

    On the following testcase, if the IL before reassoc would be:
    ...
      <bb 4> [local count: 354334800]:
      if (x_3(D) == 2)
        goto <bb 7>; [34.00%]
      else
        goto <bb 5>; [66.00%]

      <bb 5> [local count: 233860967]:
      if (x_3(D) == 3)
        goto <bb 7>; [34.00%]
      else
        goto <bb 6>; [66.00%]

      <bb 6> [local count: 79512730]:

      <bb 7> [local count: 1073741824]:
      # prephitmp_7 = PHI <1(3), 1(4), 1(5), 1(2), 0(6)>
    then we'd optimize it properly, but as bb 5-7 is instead:
      <bb 5> [local count: 233860967]:
      if (x_3(D) == 3)
        goto <bb 6>; [34.00%]
      else
        goto <bb 7>; [66.00%]

      <bb 6> [local count: 79512730]:

      <bb 7> [local count: 1073741824]:
      # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)>
    (i.e. the true/false edges on the last bb with condition swapped
    and ditto for the phi args), we don't recognize it.  If bb 6
    is empty, there should be no functional difference between the two IL
    representations.

    This patch handles those special cases.

    2020-08-06  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/96480
            * tree-ssa-reassoc.c (suitable_cond_bb): Add TEST_SWAPPED_P
argument.
            If TEST_BB ends in cond and has one edge to *OTHER_BB and another
            through an empty bb to that block too, if PHI args don't match,
retry
            them through the other path from TEST_BB.
            (maybe_optimize_range_tests): Adjust callers.  Handle such LAST_BB
            through inversion of the condition.

            * gcc.dg/tree-ssa/pr96480.c: New test.

[Bug tree-optimization/96480] [8/9/10 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[8/9/10/11 Regression]      |[8/9/10 Regression] missed
                   |missed optimisation:        |optimisation: unnecessary
                   |unnecessary compare in      |compare in standard
                   |standard algorithms         |algorithms

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should be fixed on the trunk.
As it is essentially a new optimization, not sure if it is a good idea to
backport it, even when it has been a regression on this testcase.

[Bug tree-optimization/96480] [9/10 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug tree-optimization/96480] [9/10 Regression] missed optimisation: unnecessary compare in standard algorithms

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/96480] [10 Regression] missed optimisation: unnecessary compare in standard algorithms

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/96480] [10 Regression] missed optimisation: unnecessary compare in standard algorithms

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/96480] [10 Regression] missed optimisation: unnecessary compare in standard algorithms

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.5.0
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |11.0
   Target Milestone|10.5                        |11.0
         Resolution|---                         |FIXED

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed in GCC 11.