[Bug c/105276] New: [12 Regression] executed once loop not optimized anymore

[Bug c/105276] New: [12 Regression] executed once loop not optimized anymore

[denis.campredon at gmail dot com]

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

            Bug ID: 105276
           Summary: [12 Regression]  executed once loop not optimized
                    anymore
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: denis.campredon at gmail dot com
  Target Milestone: ---

bool foo(unsigned i) {
    bool result = true;
    while (i) {
        i = i % 3;
        i = i - (i==2 ? 2 : i ? 1 : 0);
        result = !result;
    }
    return result;
}
--------------
compiled with g++ 11.2 and -O2 it produces:

-----------------
foo(unsigned int):
        test    edi, edi
        sete    al
        ret
----------------

With current trunk and -02 lots of instructions are generated, the loop is
still present, about 30 instructions are produced.


Also, when compiled with -Os trunk produces loopless assembly:
------------------
foo(unsigned int):
        mov     dl, 1
        test    edi, edi
        je      .L1
        xor     edx, edx
.L1:
        mov     eax, edx
        ret
-------------------
Whereas using -Os and g++ 11.2 it uses one less register:
------------------
foo(unsigned int):
        mov     al, 1
        test    edi, edi
        je      .L4
        xor     eax, eax
.L4:
        ret

[Bug tree-optimization/105276] [12 Regression] executed once loop not optimized anymore

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization,
                   |                            |needs-bisection
          Component|c                           |tree-optimization
   Target Milestone|---                         |12.0

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
likely jump threading changes

[Bug tree-optimization/105276] [12 Regression] executed once loop not optimized anymore

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
                 CC|                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-04-20

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-5688-gcb137e85720654e41db370d952df226654e576a6
The difference starts in vrp2, where the actual IL change is:
-  _5 = (bool) i_16;
-  _12 = i_16;
+  _5 = i_16 != 0;
+  _12 = (unsigned int) _5;
and the ranges changes are:
-i_1  : unsigned int [0, 1]
+i_1  : unsigned int [0, 2]
 i_7  : unsigned int [0, 2]
-i_8  : unsigned int [0, 1][+INF, +INF]
+i_8  : unsigned int [0, 2][+INF, +INF]
 _12  : unsigned int [0, 1]
 i_13  : unsigned int [1, +INF]
-i_14  : unsigned int [1, 1][+INF, +INF]
-i_16  : unsigned int [0, 1]
+i_14  : unsigned int [1, 2][+INF, +INF]
+i_16  : unsigned int [0, 2]
The old ranges were narrower and I think correct.
  i_7 = i_13 % 3;
...
  if (i_7 != 2)
...
  # i_16 = PHI <i_7(3), i_1(5)>
  _5 = i_16 != 0;
  _12 = (unsigned int) _5;
  i_8 = i_16 - _12;
  if (i_8 != 0)
...
  # i_14 = PHI <i_8(4)>
  i_1 = i_14 % 3;
Now, that
  i = i % 3;
  (i==2 ? 2 : i ? 1 : 0)
in the source is just an obfuscated way of saying i = i % 3; i
so obviously the loop will iterate at most once (0 times if i is 0, otherwise
there will be i = i - i; and it will be zero at the end of the first
iteration).
That is something the ranger doesn't need to decipher obviously, but the
above means i_7 is [0, 2], on i_16 PHI i_7 is known to be [0, 1], so assuming
it comes from that edge, i_8 is [0, 1][+INF, +INF] aka ~[2, 0xfffffffe],
for 0 it doesn't even jump to i_14 PHI (but 0 % 3 is 0), for i_14 == 1 is 1 % 3
1 and for i_14 == -1U is -1U % 3 == 0.  So, i_1 is in [0, 1] range and loops,
so the original assumptions that i_16 is [0, 1] don't change.

[Bug tree-optimization/105276] [12 Regression] executed once loop not optimized anymore

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 52848
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52848&action=edit
proposed patch

When I removed the recursion from range_of_stmt, I neglected to incorporate the
existing known global range for an ssa-name into the calculated value.

Range_of_stmt does this, but the prefill calculation missed it.  This patch
fixes that oversight.

[Bug tree-optimization/105276] [12 Regression] executed once loop not optimized anymore

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:362e2a9c6297203bcf7f66bfb51dffb82b42d3b3

commit r12-8246-g362e2a9c6297203bcf7f66bfb51dffb82b42d3b3
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Apr 25 09:56:35 2022 -0400

    Retain existing range knowledge when prefilling statements.

    When range_of_stmt was adjusted to avoid large recursion depth, we need to
    intersect the calculated range whth the any known range to avoid losing
    info.  Range_of_stmt does this, but the new prefill code missed it.

            PR tree-optimization/105276
            gcc/
            * gimple-range.cc (gimple_ranger::prefill_stmt_dependencies):
Include
            existing global range with calculated value.

            gcc/testsuite/
            * g++.dg/pr105276.C: New.

[Bug tree-optimization/105276] [12 Regression] executed once loop not optimized anymore

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.