[Bug c/60276] New: -O3 autovectorizer breaks on a particular loop

[Bug c/60276] New: -O3 autovectorizer breaks on a particular loop

[maister at archlinux dot us]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

            Bug ID: 60276
           Summary: -O3 autovectorizer breaks on a particular loop
           Product: gcc
           Version: 4.8.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: maister at archlinux dot us

Created attachment 32174
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32174&action=edit
Reduced testcase

GCC 4.8.2 with -O3 breaks a certain loop I'm compiling. Disabling the
vectorizer with -fno-tree-vectorize fixes the issue, as well as compiling with
-O2.

I've reduced the problem to a small test case which is attached as legall.c.

Distro: Arch Linux x86_64
gcc -v: 
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-unknown-linux-gnu/4.8.2/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /build/gcc/src/gcc-4.8-20140206/configure --prefix=/usr
--libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/
--enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared
--enable-threads=posix --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch
--disable-libssp --enable-gnu-unique-object --enable-linker-build-id
--enable-cloog-backend=isl --disable-cloog-version-check --enable-lto
--enable-plugin --enable-install-libiberty --with-linker-hash-style=gnu
--disable-multilib --disable-werror --enable-checking=release
Thread model: posix
gcc version 4.8.2 20140206 (prerelease) (GCC)

Miscompile: gcc -o legall legall.c -std=gnu99 -O3
Working: gcc -o legall legall.c -std=gnu99 -O3 -fno-tree-vectorize

Expected output:
(0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) (17)
(18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29) (30) (31) (32) (33)
(34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48)

Wrong output by -O3:
(0) (1) (2) (2) (4) (3) (6) (4) (8) (5) (10) (6) (12) (7) (14) (8) (16) (17)
(18) (10) (20) (11) (22) (12) (24) (13) (26) (14) (28) (15) (30) (16) (32) (33)
(34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48)

[Bug tree-optimization/60276] [4.7/4.8 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-02-20
      Known to work|                            |4.9.0
   Target Milestone|---                         |4.7.4
            Summary|-O3 autovectorizer breaks   |[4.7/4.8 Regression] -O3
                   |on a particular loop        |autovectorizer breaks on a
                   |                            |particular loop
     Ever confirmed|0                           |1
      Known to fail|                            |4.7.3, 4.8.2

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Works with GCC 4.9, still fails on the 4.8 branch and the 4.7 branch, works
with 4.3 so a regression.

Curious what fixed it on trunk.

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
      Known to work|4.9.0                       |
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
            Summary|[4.7/4.8 Regression] -O3    |[4.7/4.8/4.9 Regression]
                   |autovectorizer breaks on a  |-O3 autovectorizer breaks
                   |particular loop             |on a particular loop

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

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
extern void abort (void);

static void
foo (short *out, const short *lp, const short *hp, unsigned samples)
{
  int x, target;
  for (x = 0, target = 0; x < (int)samples; x += 2, target++)
    {
      out[x + 0] = lp[target] - ((hp[target] + hp[target - 1] + 2) >> 2);
      out[x - 1] = hp[target - 1] + ((out[x - 2] + out[x]) >> 1);
    }
}

int main(void)
{
  const short lp[25] = {
      0, 2, 4, 6, 8,
      10, 12, 14, 16,
      18, 20, 22, 24,
      26, 28, 30, 32,
      34, 36, 38, 40,
      42, 44, 46, 48,
  };
  const short hp[25] = {0};
  short out[49] = {0};
  int s;

  out[0] = lp[0] - (((hp[0] << 1) + 2) >> 2);
  foo (out + 2, lp + 1, hp + 1, 48);

  for (s = 0; s < 49; s++)
    if (out[s] != s)
      abort ();

  return 0;
}

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
But you can clearly see that this isn't valid vectorization because of the
read-after-write dependence of out[x].

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #6)
> But you can clearly see that this isn't valid vectorization because of the
> read-after-write dependence of out[x].

Well, only after unrolling which happens here - then the introduced dependence
(we CSE the in-source one) becomes explicit:

      tem0 = lp[target] - ((hp[target] + hp[target - 1] + 2) >> 2);
      out[x] = tem0;
      out[x - 1] = hp[target - 1] + ((out[x - 2] + tem0) >> 1);
      tem2 = lp[target + 1] - ((hp[target + 1] + hp[target] + 2) >> 2);
      out[x + 2] = tem2;
      out[x + 1] = hp[target] + ((out[x] + tem2) >> 1);

thus

static bool
vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
                                  loop_vec_info loop_vinfo, int *max_vf)
{
...
      if (dist > 0 && DDR_REVERSED_P (ddr))
        {
          /* If DDR_REVERSED_P the order of the data-refs in DDR was
             reversed (to make distance vector positive), and the actual
             distance is negative.  */
          if (dump_enabled_p ())
            dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
                             "dependence distance negative.\n");
          continue;
        }

becomes invalid once we unroll if the distance is less than the
vectorization factor.  Unless we apply the same CSE during vectorization
transform.

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[mpolacek at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #8 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Note that in r196871 this was broken, but r196872 is fine.

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

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

Patch I am testing.

[Bug tree-optimization/60276] [4.7/4.8/4.9 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Feb 21 13:18:54 2014
New Revision: 207992

URL: http://gcc.gnu.org/viewcvs?rev=207992&root=gcc&view=rev
Log:
2014-02-21  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/60276
    * tree-vectorizer.h (struct _stmt_vec_info): Add min_neg_dist field.
    (STMT_VINFO_MIN_NEG_DIST): New macro.
    * tree-vect-data-refs.c (vect_analyze_data_ref_dependence): Record
    STMT_VINFO_MIN_NEG_DIST.
    * tree-vect-stmts.c (vectorizable_load): Verify if assumptions
    made for negative dependence distances still hold.

    * gcc.dg/vect/pr60276.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/vect/pr60276.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-data-refs.c
    trunk/gcc/tree-vect-stmts.c
    trunk/gcc/tree-vectorizer.h

[Bug tree-optimization/60276] [4.7/4.8 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.0
            Summary|[4.7/4.8/4.9 Regression]    |[4.7/4.8 Regression] -O3
                   |-O3 autovectorizer breaks   |autovectorizer breaks on a
                   |on a particular loop        |particular loop

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

[Bug tree-optimization/60276] [4.7/4.8 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Tue Feb 25 12:42:59 2014
New Revision: 208119

URL: http://gcc.gnu.org/viewcvs?rev=208119&root=gcc&view=rev
Log:
2014-02-25  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2014-02-21  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/60276
        * tree-vectorizer.h (struct _stmt_vec_info): Add min_neg_dist field.
        (STMT_VINFO_MIN_NEG_DIST): New macro.
        * tree-vect-data-refs.c (vect_analyze_data_ref_dependence): Record
        STMT_VINFO_MIN_NEG_DIST.
        * tree-vect-stmts.c (vectorizable_load): Verify if assumptions
        made for negative dependence distances still hold.

        * gcc.dg/vect/pr60276.c: New testcase.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/vect/pr60276.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vect-data-refs.c
    branches/gcc-4_8-branch/gcc/tree-vect-stmts.c
    branches/gcc-4_8-branch/gcc/tree-vectorizer.h

[Bug tree-optimization/60276] [4.7 Regression] -O3 autovectorizer breaks on a particular loop

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60276

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Mar  6 08:23:36 2014
New Revision: 208373

URL: http://gcc.gnu.org/viewcvs?rev=208373&root=gcc&view=rev
Log:
    PR tree-optimization/60276
    * tree-vect-data-refs.c (vect_analyze_data_ref_dependence): Avoid
    a -Wsign-compare warning.

Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vect-data-refs.c

[Bug tree-optimization/60276] [4.7 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|4.7.4                       |4.8.3
      Known to fail|                            |4.7.4

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for 4.8.3.

[Bug tree-optimization/60276] [4.7 Regression] -O3 autovectorizer breaks on a particular loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |doug.gilmore at imgtec dot com

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 63148 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/60276] [4.7 Regression] -O3 autovectorizer breaks on a particular loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 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:8a9b159a86081053289be0c44339623ff59717a2

commit r15-431-g8a9b159a86081053289be0c44339623ff59717a2
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Nov 9 11:30:22 2023 +0100

    PR60276 fix for single-lane SLP

    When enabling single-lane SLP and not splitting groups the fix for
    PR60276 is no longer effective since it for unknown reason exempted
    pure SLP.  The following removes this exemption, making
    gcc.dg/vect/pr60276.c PASS even with --param vect-single-lane-slp=1

            PR tree-optimization/60276
            * tree-vect-stmts.cc (vectorizable_load): Do not exempt
            pure_slp grouped loads from the STMT_VINFO_MIN_NEG_DIST
            restriction.