[Bug tree-optimization/114074] New: wrong code at -O1 and above on x86_64-linux-gnu

[Bug tree-optimization/114074] New: wrong code at -O1 and above on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 114074
           Summary: wrong code at -O1 and above on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

This seems to be quite long-latent and affects 8.1 and later.

Compiler Explorer: https://godbolt.org/z/vbM6zsq1b

[511] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/14.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--enable-checking=yes --prefix=/local/suz-local/software/local/gcc-trunk
--enable-sanitizers --enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 14.0.1 20240223 (experimental) (GCC) 
[512] % 
[512] % gcctk -O0 small.c; ./a.out
0
0
[513] % gcctk -O1 small.c
[514] % ./a.out
0
[515] % cat small.c
int printf(const char *, ...);
int a, b;
int main() {
  for (a = 0; a > -3; a -= 2) {
    int c = a;
    b = 2000000000;
    a = ~c * b;
    printf("0\n");
    if (!a)
      break;
    a = c;
  }
  return 0;
}

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |14.0
   Last reconfirmed|                            |2024-02-23
           Priority|P3                          |P2
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
   Target Milestone|---                         |11.5
            Summary|wrong code at -O1 and above |[11/12/13/14 Regression]
                   |on x86_64-linux-gnu         |wrong code at -O1 and above
                   |                            |on x86_64-linux-gnu since
                   |                            |r8-343
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

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

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Adjusted testcase, -O0 works, -O1/-O2 aborts.

int a, b, d;

__attribute__((noipa)) void
foo (void)
{
  ++d;
}

int
main ()
{
  for (a = 0; a > -3; a -= 2)
    {
      int c = a;
      b = __INT_MAX__ - 3000;
      a = ~c * b;
      foo ();
      if (!a)
        break;
      a = c;
    }
  if (d != 2)
    __builtin_abort ();
}

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I would guess some match pattern triggers, the bisection is odd.

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The #c2 testcase with -O2 -Dnoipa=noinline,noclone bisects to either
r0-119678-g1a7de2015dfb81f40015a95be98abe50ad7382f0
or
r0-119679-g053223551fd7253097117744fcafccd28c8941c0
(r0-119674 works fine, r0-119679 doesn't and I don't have anything in between
in the seed, but other commits are go or arm or lra, while this clearly goes
wrong during ivcanon pass, where the loop is turned into a single iteration
non-loop).

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=114052
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
           Keywords|                            |wrong-code

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Possibly related to the other bug showing issues with
infer_loop_bounds_from_signedness.  OTOH:

Analyzing # of iterations of loop 1
  exit condition -2 <= [-2, + , -2](no_overflow)
  bounds on difference of bases: 0 ... 0
  result:
    # of iterations 1, bounded by 1
Loop 1 iterates 1 times.
Loop 1 iterates at most 0 times.
Loop 1 likely iterates at most 0 times.
Analyzing # of iterations of loop 1
  exit condition -2 <= [-2, + , -2](no_overflow)
  bounds on difference of bases: 0 ... 0
  result:
    # of iterations 1, bounded by 1
Removed pointless exit: if (_4 >= -2)

we incorrectly (looking at the IL) determine the exit will be taken in the
first iteration somehow.  Not sure where that other upper bound comes from,
but we have it zero upon entry of the pass already.

CDDCE has

Induction variable (int) -1 + 2 * iteration does not wrap in statement _1 =
~a.4_18;
 in loop 1.
Statement _1 = ~a.4_18;
 is executed at most 1 (bounded by 1) + 1 times in loop 1.
Induction variable (int) -2147480647 + -6002(OVF) * iteration does not wrap in
statement _2 = _1 * 2147480647;
 in loop 1. 
Statement _2 = _1 * 2147480647;
 is executed at most 0(OVF) (bounded by 0) + 1 times in loop 1.

ranges look somewhat odd (_4 starts at -4 but the merge PHI a.4_18 only at -2),
but not necessarily wrong.  So this might also be a SCEV issue computing
that odd IV for _2.

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
  <bb 3> [local count: 1014686025]:
  # a.4_18 = PHI <_4(8), 0(2)>
  b = 2147480647;
  _1 = ~a.4_18;
  _2 = _1 * 2147480647;
  a = _2;
  foo ();
  a.2_3 = a;
  if (a.2_3 == 0)
    goto <bb 5>; [5.50%]
  else
    goto <bb 4>; [94.50%]

  <bb 4> [local count: 958878295]:
  _4 = a.4_18 + -2;
  a = _4;
  if (_4 >= -2)
    goto <bb 8>; [94.50%]
  else
    goto <bb 5>; [5.50%]

  <bb 8> [local count: 906139989]:
  goto <bb 3>; [100.00%]

and we get

(set_scalar_evolution
  instantiated_below = 2
  (scalar = _1)
  (scalar_evolution = {-1, +, 2}_1))
)

this is ~{0, + -2} which I think we handle as -1 - X

And we get

(set_scalar_evolution
  instantiated_below = 2
  (scalar = _2)
  (scalar_evolution = {-2147480647, +, -6002(OVF)}_1))
)

and that's wrong, the 2nd iteration _2 should be 1 * 2147480647 but indeed
the difference isn't representable in the signed integer increment of the
CHREC.

It's probably safes to go chrec_dont_know here, the alternative would be
probably (int){-2147480647u, +, -6002u}_1 which likely doesn't help much
in practice?

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
In fact SCEV does, in chrec_fold_multiply for a mixed multiplication:

          return build_polynomial_chrec
            (CHREC_VARIABLE (op0),
             chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
             chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));

but that's (a + b) * c -> a * c + b * c which does not preserve overflow
behavior and thus isn't valid when the result is a signed CHREC with
undefined behavior on overflow and 'a + b' evaluates to 0, 1 or -1 as is
the case here with a == -1 and b == 2.  In the SCEV case it's OK to
do CHREC_LEFT * op1 but CHREC_RIGHT * op1 may not be evaluated this way.

fold-const.cc:fold_plusminus_mult deals with this by doing the multiplications
and addition in unsigned.

The exception we can definitely make is when for {a, +, b}_1 a and b have
the same sign or a is zero.  I'm not sure we can generally handle any
other case - we are already special-casing c == 0 and c == 1.

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from GCC 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:a0b1798042d033fd2cc2c806afbb77875dd2909b

commit r14-9193-ga0b1798042d033fd2cc2c806afbb77875dd2909b
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Feb 26 13:33:21 2024 +0100

    tree-optimization/114074 - CHREC multiplication and undefined overflow

    When folding a multiply CHRECs are handled like {a, +, b} * c
    is {a*c, +, b*c} but that isn't generally correct when overflow
    invokes undefined behavior.  The following uses unsigned arithmetic
    unless either a is zero or a and b have the same sign.

    I've used simple early outs for INTEGER_CSTs and otherwise use
    a range-query since we lack a tree_expr_nonpositive_p and
    get_range_pos_neg isn't a good fit.

            PR tree-optimization/114074
            * tree-chrec.h (chrec_convert_rhs): Default at_stmt arg to NULL.
            * tree-chrec.cc (chrec_fold_multiply): Canonicalize inputs.
            Handle poly vs. non-poly multiplication correctly with respect
            to undefined behavior on overflow.

            * gcc.dg/torture/pr114074.c: New testcase.
            * gcc.dg/pr68317.c: Adjust expected location of diagnostic.
            * gcc.dg/vect/vect-early-break_119-pr114068.c: Do not expect
            loop to be vectorized.

[Bug tree-optimization/114074] [11/12/13 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13/14 Regression]    |[11/12/13 Regression] wrong
                   |wrong code at -O1 and above |code at -O1 and above on
                   |on x86_64-linux-gnu since   |x86_64-linux-gnu since
                   |r8-343                      |r8-343
      Known to work|                            |14.0

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

[Bug tree-optimization/114074] [11/12/13 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Some thoughts on the CHREC folding, in the context of the many reported
optimization regressions.

We try to handle { a, +, b } * c as { a * c, +, b * c } and the issue is
cases of undefined overflow this exposes.

We have to make sure to not introduce undefined behavior that isn't there

 - at the first evaluation (the first iteration) both expressions behave
   the same with respect to overflow since it's a * c without any increment
 - further evaluations will do ((a + b) + ... + b) * c before and
   (a * c + b * c) + ... + b * c after the transform
 - (a + b) + b doesn't necessarily behave the same as a + 2*b

I'm not sure we can, say, rely on a * c not invoking undefined overflow
since we do not know whether the expression will be evaluated at runtime
and whether SCEV analysis properly handles conditional execution in this
regard (it just follows the data dependence graph).

For the fix I've looked at the simplest part, when does (a + b) * c possibly
not overflow but a * c or b * c does?  Only when a + b has smaller magnitude
than a or b which should mean a and b have to have opposite sign.  Without
proving I think (a + b + b) * c vs. a * c + b * c + b * c doesn't add
anything, thus the addition can be ignored and just the multiplication matters.

When in the future maybe adding 'assumptions' to SCEV results we could
unconditionally do the simplification but register an appropriate
assumption that needs to hold (and which we could check at runtime).
At runtime it's probably enough to verify that b * c does not overflow,
the evaluation of a * c should be guarded.

[Bug tree-optimization/114074] [11/12/13 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC 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:018ddc86b928514d7dfee024dcdeb204d5dcdd61

commit r14-9391-g018ddc86b928514d7dfee024dcdeb204d5dcdd61
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Mar 8 13:27:12 2024 +0100

    tree-optimization/114269 - 434.zeusmp regression after SCEV analysis fix

    The following addresses a performance regression caused by the recent
    SCEV analysis fix with regard to folding multiplications and undefined
    behavior on overflow.  We do not handle (T) { a, +, b } * c but can
    treat sign-conversions from unsigned by performing the multiplication
    in the unsigned type.  That's what we already do for additions (but
    that misses one case that turns out important).

    This fixes the 434.zeusmp regression for me.

            PR tree-optimization/114269
            PR tree-optimization/114074
            * tree-chrec.cc (chrec_fold_plus_1): Handle sign-conversions
            in the third CASE_CONVERT case as well.
            (chrec_fold_multiply): Handle sign-conversions from unsigned
            by performing the operation in the unsigned type.

[Bug tree-optimization/114074] [11/12/13 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 from GCC 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:e0e9499aeffdaca88f0f29334384aa5f710a81a4

commit r14-9540-ge0e9499aeffdaca88f0f29334384aa5f710a81a4
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Mar 19 12:24:08 2024 +0100

    tree-optimization/114151 - revert PR114074 fix

    The following reverts the chrec_fold_multiply fix and only keeps
    handling of constant overflow which keeps the original testcase
    fixed.  A better solution might involve ranger improvements or
    tracking of assumptions during SCEV analysis similar to what niter
    analysis does.

            PR tree-optimization/114151
            PR tree-optimization/114269
            PR tree-optimization/114322
            PR tree-optimization/114074
            * tree-chrec.cc (chrec_fold_multiply): Restrict the use of
            unsigned arithmetic when actual overflow on constant operands
            is observed.

            * gcc.dg/pr68317.c: Revert last change.

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13 Regression] wrong |[11/12/13/14 Regression]
                   |code at -O1 and above on    |wrong code at -O1 and above
                   |x86_64-linux-gnu since      |on x86_64-linux-gnu since
                   |r8-343                      |r8-343
   Target Milestone|11.5                        |15.0

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
The fix was largely reverted and post-poned to GCC15+, adjusting target
milestone.  The actual testcase in this bug is still fixed but the more
general issue (without a testcase sofar) remains.

I do not plan to do anything on branches for this.

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

Bug 114322 Summary: [14 Regression] SCEV analysis failed for bases like A[(i+x)*stride] since r14-9193-ga0b1798042d033
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114322

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

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

Bug 114269 Summary: [14 Regression] Multiple 3-6% exec time regressions of 434.zeusmp since r14-9193-ga0b1798042d033
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114269

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

[Bug tree-optimization/114074] [11/12/13/14 Regression] wrong code at -O1 and above on x86_64-linux-gnu since r8-343

[rguenth at gcc dot gnu.org]

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

Bug 114151 Summary: [14 Regression] weird and inefficient codegen and addressing modes since r14-9193
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114151

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