[Bug tree-optimization/66375] New: wrong code at -O2 and -O3 on x86_64-linux-gnu

[Bug tree-optimization/66375] New: wrong code at -O2 and -O3 on x86_64-linux-gnu

[su at cs dot ucdavis.edu]

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

            Bug ID: 66375
           Summary: wrong code at -O2 and -O3 on x86_64-linux-gnu
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: su at cs dot ucdavis.edu
  Target Milestone: ---

The current gcc trunk miscompiles the following code on x86_64-linux at -O2 and
-O3 in both 32-bit and 64-bit modes.  

It also affects gcc 4.8.x, 4.9.x and 5.1.x. This is a regression from 4.7.x.


$ gcc-trunk -v
Using built-in specs.
COLLECT_GCC=gcc-trunk
COLLECT_LTO_WRAPPER=/usr/local/gcc-trunk/libexec/gcc/x86_64-unknown-linux-gnu/6.0.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../gcc-trunk/configure --prefix=/usr/local/gcc-trunk
--enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
gcc version 6.0.0 20150601 (experimental) [trunk revision 223995] (GCC) 
$  
$ gcc-trunk -Os small.c; ./a.out
$ gcc-4.7 -O3 small.c; ./a.out
$ 
$ gcc-trunk -O2 small.c
$ ./a.out
Aborted (core dumped)
$ 


---------------------------------


int a, b, c, d[6];

int
main ()
{
  c = 0;
  for (; a < 14; a++)
    {
      int i = 0;
      for (; i < 6; i++)
        d[i] = 11;
      char e = b = c;
      c = e - d[0];
    }

  if (b != 113)
    __builtin_abort();

  return 0;
}

[Bug middle-end/66375] wrong code at -O2 and -O3 on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |middle-end

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Works for me on aarch64-linux-gnu.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-06-02
                 CC|                            |jakub at gcc dot gnu.org
   Target Milestone|---                         |4.8.5
            Summary|wrong code at -O2 and -O3   |[4.8/4.9/5 Regression]
                   |on x86_64-linux-gnu         |wrong code at -O2 and -O3
                   |                            |on x86_64-linux-gnu
     Ever confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r185691.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a looksee.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
PRE doesn't seem to do sth wrong here.  The testcase can be fixed by for
example disabling VRP2.  VRP2 needs either store-motion or complete unrolling
to
make it trigger the miscompile.  Nicest IL before VRP2 is with -fno-ivopts
-fno-tree-loop-im.  The transform VRP2 does is

Folding statement: if (a.4_17 <= 13)
Simplified relational if (a.4_17 <= 13)
 into if (a.4_17 != 14)

and

  Registering jump thread: (6, 7) incoming edge;  (7, 8) normal;
  Threaded jump 6 --> 7 to 12

  <bb 6>:
  # prephitmp_3 = PHI <prephitmp_22(5)>
  # prephitmp_39 = PHI <prephitmp_22(5)>

  <bb 7>:
  # prephitmp_26 = PHI <prephitmp_39(6), pretmp_23(3)>
  if (prephitmp_26 != 113)
    goto <bb 8>;
  else
    goto <bb 9>;

  <bb 8>:
  __builtin_abort ();

so it looks jump-threading related to me.  Somehow the equivalences I
see being recorded miss the backedge for prephitmp_22 but only record zero.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hum.

  <bb 5>:
  # prephitmp_22 = PHI <0(4), c.2_15(10)>
...
  e_12 = (char) prephitmp_22;
  _13 = (int) e_12;
...
  c.2_15 = _13 + -11;

Simulating statement (from ssa_edges): prephitmp_22 = PHI <0(4), c.2_15(10)>

Visiting PHI node: prephitmp_22 = PHI <0(4), c.2_15(10)>
    Argument #0 (4 -> 5 executable)
        0: [0, 0]
    Argument #1 (10 -> 5 executable)
        c.2_15: [-22, -11]
Meeting
  [0, 0]
and
  [-22, -11]
to
  [-22, 0]
...
Found new range for prephitmp_22: [-2147483647, 0]

...

Visiting statement:
_13 = (int) e_12;
Intersecting
  [-128, 127]
and
  [-128, 127]
to
  [-128, 127]
Found new range for _13: [-128, 127]
marking stmt to be not simulated again

Simulating statement (from ssa_edges): c.2_15 = _13 + -11;

Visiting statement:
c.2_15 = _13 + -11;
Found new range for c.2_15: [-139, 116]
marking stmt to be not simulated again

Simulating statement (from ssa_edges): prephitmp_22 = PHI <0(4), c.2_15(10)>

Visiting PHI node: prephitmp_22 = PHI <0(4), c.2_15(10)>
    Argument #0 (4 -> 5 executable)
        0: [0, 0]
    Argument #1 (10 -> 5 executable)
        c.2_15: [-139, 116]
Meeting
  [0, 0]
and
  [-139, 116]
to
  [-139, 116]
marking stmt to be not simulated again

(note no "Found new range for prephitmp_22" here!)

Value ranges after VRP:

prephitmp_22: [-2147483647, 0]

oops.

This seems to be because we drop to [-2147483647, 2147483646] but then
adjust_range_with_scev computes {0, +, -11}_1 for _22  which is obviously
wrong.

It looks like the CHREC gets built from

static t_bool
follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
                        tree type, tree rhs0, enum tree_code code, tree rhs1,
                        gphi *halting_phi, tree *evolution_of_loop,
                        int limit)
{
...
  switch (code)
    {
    case POINTER_PLUS_EXPR:
    case PLUS_EXPR:
      if (TREE_CODE (rhs0) == SSA_NAME)
        {
          if (TREE_CODE (rhs1) == SSA_NAME)
            {
...
          else
            {
              /* Match an assignment under the form:
                 "a = b + ...".  */
              res = follow_ssa_edge
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
                 evolution_of_loop, limit);
              if (res == t_true)
                *evolution_of_loop = add_to_evolution
                  (loop->num, chrec_convert (type, *evolution_of_loop,
                                             at_stmt),
                   code, rhs1, at_stmt);

and what goes wrong is follow_ssa_edge skipping the (unsigned char) truncation.

Still digging...

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Indeed as we just feed the initial condition to chrec_convert it happily just
fold_convert()s the zero to signed char and then back to int ...

So

              res = follow_ssa_edge
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
                 evolution_of_loop, limit);
              if (res == t_true)
                *evolution_of_loop = add_to_evolution
                  (loop->num, chrec_convert (type, *evolution_of_loop,
                                             at_stmt),
                   code, rhs1, at_stmt);

doesn't work at all (the follow_ssa_edge call just picking up the initial
value converted to the type of the add).

static tree
analyze_evolution_in_loop (gphi *loop_phi_node,
                           tree init_cond)
{
...
          /* Pass in the initial condition to the follow edge function.  */
          ev_fn = init_cond;
          res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);

I suppose a trick would be to always pass a symbolic initial condition
but then this would likely pessimize code.  With that we get

(add_to_evolution
  (loop_nb = 1)
  (chrec_before = (int) (signed char) D.1876)
  (to_add = -11)
  (res = {(int) (signed char) D.1876, +, -11}_1))
  (evolution_function = {(int) (signed char) 0, +, -11}_1))

Hmm, but that isn't correct either.  We want (int)(signed char){(int)0, +,
-11)_1


Sorter testcase pin-pointing the issue in VRP/SCEV:


int a;
extern void abort (void);
int main ()
{
  int c = 0;
  for (; a < 13; ++a)
    c = (signed char)c - 11;
  if (c != 113)
    abort ();
  return c;
}

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Sebastian - it seems that we have to somehow tell the analysis phase that we
are analyzing an evolution, not just an initial value.  Like instead of

              /* Match an assignment under the form:
                 "a = b + ...".  */
              res = follow_ssa_edge
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
                 evolution_of_loop, limit);
              if (res == t_true)
                *evolution_of_loop = add_to_evolution
                  (loop->num, chrec_convert (type, *evolution_of_loop,
                                             at_stmt),
                   code, rhs1, at_stmt);

doing the add_to_evolution first and only then following the SSA edge.
That seems to kind-of work, though the debug output is strange:

(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = c_1)
(get_scalar_evolution
  (scalar = c_1)
  (scalar_evolution = ))
(analyze_initial_condition
  (loop_phi_node =
c_1 = PHI <0(2), c_7(3)>
)
  (init_cond = 0))
(analyze_evolution_in_loop
  (loop_phi_node = c_1 = PHI <0(2), c_7(3)>
)
(add_to_evolution
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = -11)
  (res = {0, +, -11}_1))
... computing niter, from chrec_convert stuff I guess
  (evolution_function = (int) (signed char) {0, +, 245}_1))

(that 245 looks wrong)

but at least the scalar evolution ends up (correctly) as being not know...

That is with

Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c     (revision 224013)
+++ tree-scalar-evolution.c     (working copy)
@@ -991,15 +991,15 @@ follow_ssa_edge_binary (struct loop *loo
            {
              /* Match an assignment under the form:
                 "a = b + ...".  */
+             *evolution_of_loop = add_to_evolution
+                 (loop->num, chrec_convert (type, *evolution_of_loop,
+                                            at_stmt),
+                  code, rhs1, at_stmt);
              res = follow_ssa_edge
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
                 evolution_of_loop, limit);
              if (res == t_true)
-               *evolution_of_loop = add_to_evolution
-                 (loop->num, chrec_convert (type, *evolution_of_loop,
-                                            at_stmt),
-                  code, rhs1, at_stmt);
-
+               ;
              else if (res == t_dont_know)
                *evolution_of_loop = chrec_dont_know;
            }

but as said, I don't think this is correct ...?  (just thrown it to testing)

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 35678
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35678&action=edit
patch

What I am testing.

[Bug middle-end/66375] [4.8/4.9/5/6 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed Jun  3 07:57:13 2015
New Revision: 224060

URL: https://gcc.gnu.org/viewcvs?rev=224060&root=gcc&view=rev
Log:
2015-06-03  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/66375
        * tree-scalar-evolution.c (follow_ssa_edge_binary): First
        add to the evolution before following SSA edges.

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

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr66375.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c

[Bug middle-end/66375] [4.8/4.9/5/6 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[bernhard.kaindl at thalesgroup dot com]

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

Bernhard Kaindl <bernhard.kaindl at thalesgroup dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bernhard.kaindl@thalesgroup
                   |                            |.com

--- Comment #11 from Bernhard Kaindl <bernhard.kaindl at thalesgroup dot com> ---
Created attachment 35735
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35735&action=edit
Backport to gcc-4_9-branch/gcc-4.9.2: PR tree-optimization/66375 (wrong code
fix!)

Backport from mainline to gcc-4_9-branch (also applies to gcc-4.9.2):

Note: Fixes wrong code for x86 and x86_64 targets
      (other targets apparently not affected)

URL: <this attachment>
Log:
2015-06-10  Bernhard Kaindl <bernhard.kaindl@thalesgroup.com>

       Backport from mainline
       2015-06-03  Richard Biener  <rguenther@suse.de>

       PR tree-optimization/66375

       * tree-scalar-evolution.c (follow_ssa_edge_binary): First
       add to the evolution before following SSA edges.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr66375.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c

The context of the ChangeLogs is removed, so it applies using "patch -p1"
without ever causing a conflict (other changes may be merged before this,
the ChangeLogs are automatically added on top without context matching),
but it won't apply with "git apply" this way.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |6.0
            Summary|[4.8/4.9/5/6 Regression]    |[4.8/4.9/5 Regression]
                   |wrong code at -O2 and -O3   |wrong code at -O2 and -O3
                   |on x86_64-linux-gnu         |on x86_64-linux-gnu
      Known to fail|                            |5.1.0

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks, I am going to do another round of backporting today or tomorrow.

[Bug middle-end/66375] [4.8/4.9/5 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Jun 18 14:04:05 2015
New Revision: 224610

URL: https://gcc.gnu.org/viewcvs?rev=224610&root=gcc&view=rev
Log:
2015-06-18  Richard Biener  <rguenther@suse.de>

        Backport from mainline
        2015-06-03  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/66375
        * tree-scalar-evolution.c (follow_ssa_edge_binary): First
        add to the evolution before following SSA edges.

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

Added:
    branches/gcc-5-branch/gcc/testsuite/gcc.dg/torture/pr66375.c
Modified:
    branches/gcc-5-branch/gcc/ChangeLog
    branches/gcc-5-branch/gcc/testsuite/ChangeLog
    branches/gcc-5-branch/gcc/tree-scalar-evolution.c

[Bug middle-end/66375] [4.8/4.9 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug middle-end/66375] [4.9 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug middle-end/66375] [4.9 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug middle-end/66375] [4.9 Regression] wrong code at -O2 and -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #18 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.