[Bug c/107176] New: Wrong code at -O0/-Os on x86_64-pc-linux-gnu

[Bug c/107176] New: Wrong code at -O0/-Os on x86_64-pc-linux-gnu

[shaohua.li at inf dot ethz.ch]

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

            Bug ID: 107176
           Summary: Wrong code at -O0/-Os on x86_64-pc-linux-gnu
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: shaohua.li at inf dot ethz.ch
  Target Milestone: ---

%gcc-tk -v
Using built-in specs.
COLLECT_GCC=gcc-tk
COLLECT_LTO_WRAPPER=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-b48d7ff3570fa0ebe7790275cf020d8885120338/libexec/gcc/x86_64-pc-linux-gnu/13.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++
--prefix=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-b48d7ff3570fa0ebe7790275cf020d8885120338
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.0 20220928 (experimental) (GCC)
%
%gcc-tk -O0 a.c && ./a.out
1073741824
%
%gcc-tk -Os a.c && ./a.out 
0
%
%cat a.c
int a;
long b;
long c(unsigned d) { 
    return d; 
}
void e(d) { 
    a = d; 
}
int main() {
  b = 0;
  for (; b < 1; b = c(b - 90) + 90 + 1)
    ;
  e(b >> 2);
  printf("%d\n", a);
}
%

Compiler explorer: https://godbolt.org/z/zzMdosoKj

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |10.5
          Component|c                           |tree-optimization
           Keywords|                            |wrong-code
      Known to fail|                            |7.1.0
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
            Summary|Wrong code at -O0/-Os on    |[10/11/12/13 Regression]
                   |x86_64-pc-linux-gnu         |Wrong code at -Os on
                   |                            |x86_64-pc-linux-gnu
   Last reconfirmed|                            |2022-10-06
      Known to work|                            |6.3.0

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
Here is a better testcase:
#include <stdio.h>

int a;
long b;
static inline long c(unsigned d) { 
    return d; 
}
static inline void e(int d) { 
    a = d; 
}
int main() {
  b = 0;
  for (; b < 1; b = c(b - 90) + 90 + 1)
    ;
  e(b >> 2);
  printf("%d\n", a);
  if (a != 1073741824)
    __builtin_abort();
}

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
final value replacement:
  b_lsm.8_26 = PHI <b_lsm.8_15(4)>
 with expr: 1
 final stmt:
  b_lsm.8_26 = 1;

where

(get_scalar_evolution
  (scalar = b_lsm.8_15)
  (scalar_evolution = {0, +, 1}_1))
(chrec_apply
  (varying_loop = 1)
  (chrec = {0, +, 1}_1)
  (x = 1)
  (res = 1))

and

  <bb 3> [local count: 955630225]:
  _1 = (unsigned int) b_lsm.8_15;
  _2 = _1 + 4294967206;
  # RANGE [irange] long int [0, 4294967295] NONZERO 0xffffffff
  _12 = (long int) _2;
  # RANGE [irange] long int [91, 4294967386] NONZERO 0x1ffffffff
  _3 = _12 + 91;

  <bb 4> [local count: 1073741824]:
  # b_lsm.8_15 = PHI <0(2), _3(3)>

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[10/11/12/13 Regression]    |[10/11/12/13 Regression]
                   |Wrong code at -Os on        |Wrong code at -Os on
                   |x86_64-pc-linux-gnu         |x86_64-pc-linux-gnu since
                   |                            |r7-2012-g43aabfcfd4139e4c
           Keywords|needs-bisection             |
                 CC|                            |amker at gcc dot gnu.org,
                   |                            |marxin at gcc dot gnu.org

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r7-2012-g43aabfcfd4139e4c.

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will try to have a closer look.

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
<bb 4> [local count: 1073741824]:
# b_lsm.8_15 = PHI <0(2), _3(3)>
# b_lsm_flag.9_17 = PHI <0(2), 1(3)>
if (b_lsm.8_15 <= 0)
  goto <bb 3>; [89.00%]
else
  goto <bb 5>; [11.00%]

<bb 3> [local count: 955630225]:
_1 = (unsigned int) b_lsm.8_15;
_2 = _1 + 4294967206;
_12 = (long int) _2;
_3 = _12 + 91;
goto <bb 4>;

for this loop we get

(number_of_iterations_in_loop =
(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = b_lsm.8_15)
(get_scalar_evolution
  (scalar = b_lsm.8_15)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
b_lsm.8_15 = PHI <0(2), _3(3)>
)
  (init_cond = 0))
(analyze_evolution_in_loop
  (loop_phi_node = b_lsm.8_15 = PHI <0(2), _3(3)>
)
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = 91)
  (res = {0, +, 91}_1))
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = {0, +, 91}_1)
  (to_add = 4294967206)
  (res = {0, +, 1}_1))
Estimating # of iterations of loop 1
(number_of_iterations_in_loop =
(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = b_lsm.8_15)
(get_scalar_evolution
  (scalar = b_lsm.8_15)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
b_lsm.8_15 = PHI <0(2), _3(3)>
)
  (init_cond = 0))
(analyze_evolution_in_loop
  (loop_phi_node = b_lsm.8_15 = PHI <0(2), _3(3)>
)
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = 91)
  (res = {0, +, 91}_1))
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = {0, +, 91}_1)
  (to_add = 4294967206)
  (res = {0, +, 1}_1))
  (evolution_function = (long int) {0, +, 1}_1))
(set_scalar_evolution
  instantiated_below = 2
  (scalar = b_lsm.8_15)
  (scalar_evolution = (long int) {0, +, 1}_1))
)

and that's wrong I think.  (long int)((unsigned int)b + -90u) + 91 isn't
the same as (long int) {0, +, 1} with the evolution in unsigned int.
It's the evolution of the value in _unsigned int_.

The key somehow happens in follow_ssa_edge_expr where we do

          /* Match an assignment under the form:
             "a = b +- ...". 
             Use tail-recursion for the simple case.  */
          *evolution_of_loop = add_to_evolution
              (loop->num, chrec_convert (type, *evolution_of_loop,
                                         at_stmt),
               code, rhs1, at_stmt);
          expr = rhs0;
          goto tail_recurse; 

which converts the long int { 0, +, 91 }_1 to unsigned int and will
then add -90u to that.

We are building the CHREC "backwards", we start with '(long)0', the initial
condition but then build the CHREC from the backedge def, first
{(long)0, +, 91}, then upon _12 = (long int)_2 we're feeding the
{(long)0, +, 91} to the _2 = _1 + -90u handler above which simply
truncates the "current" CHREC and the outer recursion will simply
convert that back.  But that's not how the CHREC expression build and
simplification should work?

The most significant hint is probably that when reaching the initial
truncation '_1 = (unsigned int) b_lsm.8_15;' we get there with a
CHREC that is unsigned int already!

So it's possibly wrong to "post-recurse" to rhs0 here.  Doing

diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 9f30f78cb5d..b481c488ca8 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -1265,6 +1265,9 @@ tail_recurse:
       if (TREE_CODE (rhs0) == SSA_NAME
          && (TREE_CODE (rhs1) != SSA_NAME || code == MINUS_EXPR))
        {
+
+       t_bool res = follow_ssa_edge_expr (loop, at_stmt, rhs0, halting_phi,
+                                          evolution_of_loop, limit);
          /* Match an assignment under the form:
             "a = b +- ...".
             Use tail-recursion for the simple case.  */
@@ -1272,8 +1275,9 @@ tail_recurse:
              (loop->num, chrec_convert (type, *evolution_of_loop,
                                         at_stmt),
               code, rhs1, at_stmt);
-         expr = rhs0;
-         goto tail_recurse;
+         //expr = rhs0;
+         //goto tail_recurse;
+         return res;
        }
       /* Else search for the SCC in both rhs0 and rhs1.  */
       return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,

fixes the testcase.

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, and interestingly this fix causes PR66375 to regress again:

FAIL: gcc.dg/torture/pr66375.c   -O2  execution test
...

OK, so that's because my suggested fix is exactly an (incomplete) reversal
of the fix for PR66375 (r6-1346-gb9b79ba4264cf6) :/

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #2)
> final value replacement:
>   b_lsm.8_26 = PHI <b_lsm.8_15(4)>
>  with expr: 1
>  final stmt:
>   b_lsm.8_26 = 1;
> 
> where
> 
> (get_scalar_evolution
>   (scalar = b_lsm.8_15)
>   (scalar_evolution = {0, +, 1}_1))
> (chrec_apply
>   (varying_loop = 1)
>   (chrec = {0, +, 1}_1)
>   (x = 1)
>   (res = 1))
> 
> and
> 
>   <bb 3> [local count: 955630225]:
>   _1 = (unsigned int) b_lsm.8_15;
>   _2 = _1 + 4294967206;
>   # RANGE [irange] long int [0, 4294967295] NONZERO 0xffffffff
>   _12 = (long int) _2;
>   # RANGE [irange] long int [91, 4294967386] NONZERO 0x1ffffffff
>   _3 = _12 + 91;
> 
>   <bb 4> [local count: 1073741824]:
>   # b_lsm.8_15 = PHI <0(2), _3(3)>

For comparison in PR66375 we have

<bb 4> :
# c_6 = PHI <0(2), c_12(3)>
a.1_5 = a;
if (a.1_5 <= 12)
  goto <bb 3>; [INV]
else
  goto <bb 5>; [INV]

<bb 3> :
_1 = (signed char) c_6;
_2 = (int) _1;
c_12 = _2 + -11;
_4 = a.1_5 + 1;
a = _4;
goto <bb 4>;

so the backedge definition is

  (long)((unsigned)IV + -90u) + 91

vs.

  (int)(signed char)IV + -11


I think the issue is the CONVERT_EXPR handling in follow_ssa_edge_expr where
it isn't all that clear in which case we can analyze the evolution in the
narrower or the wider type.  In the case in this PR we mishandled the
middle conversion while in the older case we mishandle the "initial"
conversion.  I suspect that trying to optimize things on-the-fly is
difficult (and reasoning about the relevant cases there).

I've tried (again) to more correctly have the current evolution tentative
until we hit the loop PHI again when following the use-def chain from the
latch definition, but then we don't even know whether we will have an
evolution in the end (tried { initial, +, scev_not_known }).  Going fully
symbolic will lead to the issue pointed out in comment 6 of PR66375,
we'd get { (int)(signed char)0, +, -11 } which isn't what we want.

If, as in this bug, we have two evolutions in different types, we probably
have to give up.  Maybe we need to think of a PLUS as { unknown, +, val }
and instead fend off "wrongly" typed evolutions when we reach the
loop PHI node again.  But then the PR66375 case _does_ have an expression
correctly describing the evolution of the IV.  Just in this PRs case there
is none I think.  Or rather, I guess it would be
{ (long){ 0u, +, -90u }_1, +, 90 }_1 but that wouldn't be affine at least.

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=42512

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
PR42512 is also related and its "fix" is even worse...  it's worse in that
it hides wrong cases but also throws away correct ones.  But it also
shows that we still mishandle that testcase with or without the fix(es).

It seems that the intent of the SCC analysis in interpret_loop_phi is to
look at the linear operation (or the chain of linear operations) associated
in a way that it matches

 (T2)(init + ev)

from which then (T2) { init, +, ev } follows.

So when

 PHI' = (int)(signed char)PHI + 11

we directly match (int)(signed char){ init, +, 11 }

and for

 PHI' = (long)((unsigned)PHI + -90u) + 91

we'd have to associate the outer + 91 which we can't do (but effectively
do due to the present bug).

[Bug tree-optimization/107176] [10/11/12/13 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:4c5b1160776382772fc0a33130dfaf621699fdbf

commit r13-3486-g4c5b1160776382772fc0a33130dfaf621699fdbf
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Oct 24 08:52:12 2022 +0200

    tree-optimization/107176 - SCEV analysis association issue

    The following fixes a wrong-code issue caused by SCEV analysis
    associating an addition due trying to use tail-recursion in
    follow_ssa_edge_expr.  That causes us to apply a conversion at
    the wrong point and thus miscompute the scalar evolution of
    an induction variable.  This reverts the PR66375 fix and
    revisits the PR42512 fix by keeping the evolution symbolic
    up to the point we process the first linear function when
    we then can check for the supported cases and substitute the
    whole symbolic expression with the built chrec substituting
    the proper initial value.

    To simplify passing around things and to clarify scoping of
    the involved functions this change wraps the SCEV DFS walking
    code into a class.

            PR tree-optimization/107176
            PR tree-optimization/66375
            PR tree-optimization/42512
            * tree-scalar-evolution.cc (follow_ssa_edge_expr): Revert
            the PR66375 fix, do not not associate PLUS_EXPR to be able
            to use tail-recursion.
            (follow_ssa_edge_binary): Likewise.
            (interpret_loop_phi): Revert PR42512 fix, do not throw
            away analyze_evolution_in_loop result after the fact.
            (follow_ssa_edge_expr): When reaching halting_phi initalize
            the evolution to the symbolic value of the PHI result.
            (add_to_evolution_1): When adding the first evolution verify
            we can handle the expression wrapping the symbolic evolution
            and replace that in full using the initial condition.
            (class scev_dfs): New, contains ...
            (follow_ssa_edge_expr, follow_ssa_edge_binary,
            follow_ssa_edge_in_condition_phi_branch,
            follow_ssa_edge_in_condition_phi,
            follow_ssa_edge_inner_loop_phi,
            add_to_evolution, add_to_evolution_1): ... these with
            loop and halting_phi arguments in class data.
            (scev_dfs::get_ev): New toplevel DFS entry, start with
            a chrec_dont_know evolution.
            (analyze_evolution_in_loop): Use scev_dfs.

            * gcc.dg/torture/pr107176.c: New testcase.

[Bug tree-optimization/107176] [10/11/12 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[10/11/12/13 Regression]    |[10/11/12 Regression] Wrong
                   |Wrong code at -Os on        |code at -Os on
                   |x86_64-pc-linux-gnu since   |x86_64-pc-linux-gnu since
                   |r7-2012-g43aabfcfd4139e4c   |r7-2012-g43aabfcfd4139e4c
      Known to work|                            |13.0

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/107176] [10/11/12 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107176
Bug 107176 depends on bug 107493, which changed state.

Bug 107493 Summary: [13 Regression] Wrong code at -Os on x86_64-linux-gnu since r13-3486-g4c5b116077638277
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107493

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

[Bug tree-optimization/107176] [11/12 Regression] Wrong code at -Os on x86_64-pc-linux-gnu since r7-2012-g43aabfcfd4139e4c

[rguenth at gcc dot gnu.org]

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

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

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

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