[Bug middle-end/105198] New: Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[Bug middle-end/105198] New: Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[tomas.kalibera at gmail dot com]

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

            Bug ID: 105198
           Summary: Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tomas.kalibera at gmail dot com
  Target Milestone: ---

Created attachment 52770
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52770&action=edit
Reproducible example to compile and execute (see comment in file)

It seems that GCC produces wrong code for function next_set found in R package
MASS (traced down by Brian Ripley):

static void next_set(int *x, int n, int k)
{
    int i, j, tmp;

    j = k - 1;
    tmp = x[j]++;
    while(j > 0 && x[j] >= n - (k - 1 -j)) tmp = ++x[--j];
    for(i = j+1; i < k; i++)  x[i] =  ++tmp;
}

The attached standalone example reproduces the problem on a slightly modified
and instrumented variant of the function, for one specific input, see comments
in the code. 

Correct output (GCC 12 -O1, and can be seen from the C code):

n == 5, k == 3, x == 0 1 4
tmp == 2, j == 1, x == 0 2 5

Incorrect but seen on x86_64/Linux (GCC 12 -O2, GCC 11 -O3):

n == 5, k == 3, x == 0 1 4
tmp == 4, j == 2, x == 0 1 5

One can modify the example to get slightly simpler native code via writing to
the array in "main" via volatile variables.

It works with GCC 10 -O3.

[Bug tree-optimization/105198] [11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Wrong code for C loop (GCC  |[11/12 Regression] Wrong
                   |12 -O2, GCC 11 -O3)         |code for C loop (GCC 12
                   |                            |-O2, GCC 11 -O3)
             Status|UNCONFIRMED                 |NEW
                 CC|                            |rguenth at gcc dot gnu.org
   Target Milestone|---                         |11.3
     Ever confirmed|0                           |1
          Component|middle-end                  |tree-optimization
   Last reconfirmed|                            |2022-04-08
           Keywords|                            |needs-bisection, wrong-code

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/105198] [11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
As expected, at -O2 this regressed with
r12-4240-g2b8453c401b699ed93c085d0413ab4b5030bcdb8
when vectorization has been enabled by default at -O2.
With -O3 it regressed with r11-3917-g28290cb50c7dbf87458befeb3e295b5cb13560b5

[Bug tree-optimization/105198] [11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So it's predictive commoning that triggers the miscompile, it works with
-fno-predictive-commoning.  predcom does

--- a-t.c.167t.dce6     2022-04-08 10:59:28.824746581 +0200
+++ a-t.c.168t.pcom     2022-04-08 10:59:28.824746581 +0200
@@ -4,6 +4,7 @@
 __attribute__((noipa, noinline, noclone, no_icf))
 void next_set (int * x, int n, int k)
 {
+  int D__lsm0.19;
   vector(4) int * vectp.18;
   vector(4) int * vectp.17;
   vector(4) int vect_tmp_55.16;
@@ -117,6 +118,7 @@
   [t.c:43:8] _13 = [t.c:43:8] *_12;
   [t.c:43:11] _14 = _13 + 1;
   [t.c:43:11] [t.c:43:8] *_12 = _14;
+  D__lsm0.19_72 = _14;
   [t.c:40:17] if (j_49 > 0)
     goto <bb 19>; [94.50%]
   else
@@ -132,11 +134,12 @@

   <bb 6> [local count: 1014686026]:
   # j_73 = PHI <[t.c:42:8] j_49(19), [t.c:34:7] j_46(15)>
-  # tmp_75 = PHI <[t.c:43:11] _14(19), [t.c:35:9] _8(15)>
+  # D__lsm0.19_77 = PHI <D__lsm0.19_72(19), _8(15)>
+  tmp_75 = D__lsm0.19_77;
   [t.c:40:21] _16 = (long unsigned int) j_73;
   [t.c:40:21] _17 = _16 * 4;
   [t.c:40:21] _18 = x_47(D) + _17;
-  [t.c:40:21] _19 = [t.c:40:21] *_18;
+  [t.c:40:21] _19 = D__lsm0.19_77;
   [t.c:40:39] _21 = j_46 - j_73;
   [t.c:40:30] _22 = n_41(D) - _21;
   [t.c:40:17] if (_19 >= _22)

which at first doesn't look wrong, but when disabling PRE (which without
vectorization would do the same transform) the issue also shows up w/o
vectorization

 -O2 -fno-tree-vectorize -fno-tree-pre -fpredictive-commoning

[Bug tree-optimization/105198] [11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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 #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Reduced testcase for the predictive commoning issue, fails with -O3 or
-O2 -fno-tree-pre -fpredictive-commoning

static  __attribute__ ((noipa)) void
next_set(int *x, int n, int k)
{
  int j, tmp;
  j = k - 1;
  tmp = x[j]++;
  while(j > 0 && x[j] >= n - (k - 1 -j))
    {
      j--;
      x[j]++;
      tmp = x[j];
    }
  if (tmp != 2 || j != 1 || x[0] != 0 || x[1] != 2 || x[2] != 5)
    __builtin_abort ();
}

int main()
{
  int x[3] = {0, 1, 4};
  next_set(x, 5, 3);
  return 0;
}

[Bug tree-optimization/105198] [11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
So before pcom we have

  <bb 2> [local count: 114863530]:
  j_29 = k_28(D) + -1;
  _1 = (long unsigned int) j_29;
  _2 = _1 * 4;
  _3 = x_30(D) + _2;
  _4 = *_3;
  _5 = _4 + 1;
  *_3 = _5;
  if (j_29 > 0)
    goto <bb 11>; [94.50%]

  <bb 11> [local count: 108546036]:

  <bb 3> [local count: 1014686026]:
  # j_40 = PHI <j_34(12), j_29(11)>
  # tmp_39 = PHI <_17(12), _4(11)>
  _6 = (long unsigned int) j_40;
  _7 = _6 * 4;
  _8 = x_30(D) + _7;
  _9 = *_8;
  _11 = j_29 - j_40;
  _12 = n_33(D) - _11;
  if (_9 < _12)
    goto <bb 14>; [5.50%]
  else
    goto <bb 4>; [94.50%]

and pcom replaces the _9 load like the following:

  <bb 3> [local count: 1014686026]:
  # j_40 = PHI <j_34(12), j_29(11)>
  # D__lsm0.5_25 = PHI <D__lsm0.5_18(12), _4(11)>
  tmp_39 = D__lsm0.5_25;
  _6 = (long unsigned int) j_40;
  _7 = _6 * 4;
  _8 = x_30(D) + _7;
  _9 = D__lsm0.5_25;
  _11 = j_29 - j_40;
  _12 = n_33(D) - _11;
  if (_9 < _12)
    goto <bb 14>; [5.50%]
  else
    goto <bb 4>; [94.50%]

but that fails to realize that while _4 loads from the same
address, the *_3 = _5 store clobbers the value.  So with pcom
applied we exit the loop immediately at the

  x[j] < n - (k - 1 -j))

test because we use the wrong loop entry value for x[j].  It somehow
gets derailed to use 'tmp' here (it doesn't actually even analyze
the load/store in BB2).

So it's probably wrong in determining

Store-loads chain 0x3410a90
  max distance 1, may reuse first
  inits _4
  references:
    *_15 (id 2, write)
      offset -1
      distance 0
    looparound ref
      in statement tmp_39 = PHI <_17(12), _4(11)>

      distance 1
    *_8 (id 0)
      offset 0
      distance 1

in particular identifying the looparound ref which is only partly
a looparund ref (the initial value isn't).  Indeed, prepare_initializers_chain
simply does

  /* If we have replaced some looparound phi nodes, use their initializers
     instead of creating our own.  */
  FOR_EACH_VEC_ELT (chain->refs, i, laref)
    {
      if (gimple_code (laref->stmt) != GIMPLE_PHI)
        continue;

      gcc_assert (laref->distance > 0);
      chain->inits[n - laref->distance]
        = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
    }

which would be OK, but find_looparound_phi simply looks at the def of
the loop entry value and matches it up with the chain, not considering
intermediate clobbering stmts.

[Bug tree-optimization/105198] [9/10/11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12 Regression] Wrong    |[9/10/11/12 Regression]
                   |code for C loop (GCC 12     |Wrong code for C loop (GCC
                   |-O2, GCC 11 -O3)            |12 -O2, GCC 11 -O3)
           Priority|P3                          |P2
   Target Milestone|11.3                        |9.5

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
The identified problem is latent since forever.  I'm currently testing a patch.

[Bug tree-optimization/105198] [9/10/11/12 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:e5453bcc217ea4ac53a4ac277661d6ef0ccd425b

commit r12-8059-ge5453bcc217ea4ac53a4ac277661d6ef0ccd425b
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Apr 8 13:13:29 2022 +0200

    tree-optimization/105198 - wrong code with predictive commoning

    When predictive commoning looks for a looparound PHI it tries
    to match the entry value definition (a load) up with the appropriate
    member of the chain.  But it fails to consider stmts clobbering
    the very same memory location inbetween the load and loop entry.

    In theory we could be more clever on must aliases that would be
    also picked up from a load (so not exactly stmt_kills_ref_p) and
    use the stored value from that if it is an exact match.  But we
    currently have no way to propagate this information inside predcom.

    2022-04-08  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/105198
            * tree-predcom.cc (find_looparound_phi): Check whether
            the found memory location of the entry value is clobbered
            inbetween the value we want to use and loop entry.

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

[Bug tree-optimization/105198] [9/10/11 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[9/10/11/12 Regression]     |[9/10/11 Regression] Wrong
                   |Wrong code for C loop (GCC  |code for C loop (GCC 12
                   |12 -O2, GCC 11 -O3)         |-O2, GCC 11 -O3)

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks for the nicely reduced bugreport!

[Bug tree-optimization/105198] [9/10/11 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:542c30dc4d220f6d2138e55d5fb8e1529339badf

commit r11-9800-g542c30dc4d220f6d2138e55d5fb8e1529339badf
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Apr 8 13:13:29 2022 +0200

    tree-optimization/105198 - wrong code with predictive commoning

    When predictive commoning looks for a looparound PHI it tries
    to match the entry value definition (a load) up with the appropriate
    member of the chain.  But it fails to consider stmts clobbering
    the very same memory location inbetween the load and loop entry.

    In theory we could be more clever on must aliases that would be
    also picked up from a load (so not exactly stmt_kills_ref_p) and
    use the stored value from that if it is an exact match.  But we
    currently have no way to propagate this information inside predcom.

    2022-04-08  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/105198
            * tree-predcom.c (find_looparound_phi): Check whether
            the found memory location of the entry value is clobbered
            inbetween the value we want to use and loop entry.

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

    (cherry picked from commit e5453bcc217ea4ac53a4ac277661d6ef0ccd425b)

[Bug tree-optimization/105198] [9/10 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[9/10/11 Regression] Wrong  |[9/10 Regression] Wrong
                   |code for C loop (GCC 12     |code for C loop (GCC 12
                   |-O2, GCC 11 -O3)            |-O2, GCC 11 -O3)
      Known to fail|                            |11.2.0
      Known to work|                            |11.2.1, 12.0

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed where the testcase fails, I'll eventually backport further for the latent
issue.

[Bug tree-optimization/105198] [9/10 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[tomas.kalibera at gmail dot com]

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

--- Comment #11 from Tomas Kalibera <tomas.kalibera at gmail dot com> ---
Thanks for the very quick fix! I confirm that when R is built with the fixed
version of GCC 12, the R testcase for MASS is fixed, it works with -O2.

[Bug tree-optimization/105198] [9/10 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:29e8fe04e707910b1bcf15cbc2b582ee0e0e93d6

commit r10-10595-g29e8fe04e707910b1bcf15cbc2b582ee0e0e93d6
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Apr 8 13:13:29 2022 +0200

    tree-optimization/105198 - wrong code with predictive commoning

    When predictive commoning looks for a looparound PHI it tries
    to match the entry value definition (a load) up with the appropriate
    member of the chain.  But it fails to consider stmts clobbering
    the very same memory location inbetween the load and loop entry.

    In theory we could be more clever on must aliases that would be
    also picked up from a load (so not exactly stmt_kills_ref_p) and
    use the stored value from that if it is an exact match.  But we
    currently have no way to propagate this information inside predcom.

    2022-04-08  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/105198
            * tree-predcom.c (find_looparound_phi): Check whether
            the found memory location of the entry value is clobbered
            inbetween the value we want to use and loop entry.

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

    (cherry picked from commit e5453bcc217ea4ac53a4ac277661d6ef0ccd425b)

[Bug tree-optimization/105198] [9 Regression] Wrong code for C loop (GCC 12 -O2, GCC 11 -O3)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|9.5                         |10.4
      Known to fail|                            |9.5.0
         Resolution|---                         |FIXED

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 10.4