[Bug tree-optimization/53366] New: wrong code generation by tree vectorizer using AVX

[Bug tree-optimization/53366] New: wrong code generation by tree vectorizer using AVX

[martin@mpa-garching.mpg.de]

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

             Bug #: 53366
           Summary: wrong code generation by tree vectorizer using AVX
    Classification: Unclassified
           Product: gcc
           Version: 4.7.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: martin@mpa-garching.mpg.de


Created attachment 27410
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27410
Testcase demonstrating the problem

The attached code is the reduction of a numerical library. It should print
"2.816937e+08" if executed correctly.
Using the current head of the 4.7 branch and trunk, and compiling on an
Intel Core i3-2120 using

gcc testcase.c -std=c99 -g -O3 -march=native -fno-tree-vectorize

everything works as expected.
When omitting the "-fno-tree-vectorize", random results are printed, and a
different number is generated for every run.

The testcase is the result of several hours' reduction. Currently I don't have
time to reduce it further.

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

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

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2012-05-16 04:53:46 UTC ---
It is caused by revision 172817:

http://gcc.gnu.org/ml/gcc-cvs/2011-04/msg01013.html

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-05-16
                 CC|                            |jakub at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-16 09:30:07 UTC ---
Well, that is just the first revision that actually vectorizes the loop, so it
may be either a vectorizer bug, or backend bug.

Here is a slightly cleaned up testcase, for -O3 -mavx (with -O3 -msse4 it
doesn't get vectorized and therefore doesn't fail):

struct S { double v[3]; };
struct T { struct S r, i; };
struct U { struct T j[5]; };

void
foo (struct U *__restrict p1, struct U *__restrict p2,
     struct S l1, struct S l2, struct S l3, struct S l4,
     const double _Complex * __restrict x, int y, int z)
{
  int i, j;
  while (y < z - 2)
    {
      for (j = 0; j < 5; ++j)
        {
          double a = __builtin_creal (x[5 * y + j]);
          double b = __builtin_cimag (x[5 * y + j]);
          double c = __builtin_creal (x[5 * (y + 2) + j]);
          double d = __builtin_cimag (x[5 * (y + 2) + j]);
          double e = __builtin_creal (x[5 * (y + 1) + j]);
          double f = __builtin_cimag (x[5 * (y + 1) + j]);
          double g = __builtin_creal (x[5 * (y + 3) + j]);
          double h = __builtin_cimag (x[5 * (y + 3) + j]);
          for (i = 0; i < 3; ++i)
            {
              p1->j[j].r.v[i] += l2.v[i] * a;
              p1->j[j].r.v[i] += l4.v[i] * c;
              p1->j[j].i.v[i] += l2.v[i] * b;
              p1->j[j].i.v[i] += l4.v[i] * d;
              p2->j[j].r.v[i] += l3.v[i] * e;
              p2->j[j].r.v[i] += l1.v[i] * g;
              p2->j[j].i.v[i] += l3.v[i] * f;
              p2->j[j].i.v[i] += l1.v[i] * h;
            }
        }
      y += 4;
    }
}

_Complex double x[5005];
struct U p1, p2;

int
main ()
{
  int i, j;
  struct S l1, l2, l3, l4;
  for (i = 0; i < 5005; ++i)
    x[i] = i + 1.0iF * (2 * i);
  for (i = 0; i < 3; ++i)
    {
      l1.v[i] = 1;
      l2.v[i] = 2;
      l3.v[i] = 3;
      l4.v[i] = 4;
    }
  foo (&p1, &p2, l1, l2, l3, l4, x, 5, 1000);
  for (j = 0; j < 5; ++j)
    for (i = 0; i < 3; ++i)
      if (p1.j[j].r.v[i] != 3752430 + j * 1494
          || p1.j[j].i.v[i] != p1.j[j].r.v[i] * 2
          || p2.j[j].r.v[i] != 2502450 + j * 996
          || p2.j[j].i.v[i] != p2.j[j].r.v[i] * 2)
        __builtin_abort ();
  return 0;
}

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |UNCONFIRMED
                 CC|                            |ubizjak at gmail dot com
     Ever Confirmed|1                           |0

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[ubizjak at gmail dot com]

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

Uros Bizjak <ubizjak at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1

--- Comment #3 from Uros Bizjak <ubizjak at gmail dot com> 2012-05-16 16:48:39 UTC ---
Even more reduced testcase, fails with -O3 -mavx, works with -O3 -msse4:

--cut here--
struct S { double v[3]; };
struct T { struct S r, i; };
struct U { struct T j[2]; };

void __attribute__((noinline))
foo (struct U *__restrict p1,
     const double _Complex * __restrict x)
{
  int i, j;

  for (j = 0; j < 2; ++j)
    {
      double a = __builtin_creal (x[j]);
      double b = __builtin_cimag (x[j]);
      double c = __builtin_creal (x[j+2]);
      double d = __builtin_cimag (x[j+2]);

      for (i = 0; i < 3; ++i)
    {
      p1->j[j].r.v[i] += a;
      p1->j[j].r.v[i] += c;

      p1->j[j].i.v[i] += b;
      p1->j[j].i.v[i] += d;
    }
    }
}

_Complex double x[4];

struct U p1;

int
main ()
{
  int i, j;

  for (i = 0; i < 4; ++i)
    x[i] = i + 1.0iF * (2 * i);

  foo (&p1, x);

  for (j = 0; j < 2; ++j)
    for (i = 0; i < 3; ++i)
      if (p1.j[j].r.v[i] != __builtin_creal (x[j] + x[j+2])
      || p1.j[j].i.v[i] != __builtin_cimag (x[j] + x[j+2]))
    __builtin_abort ();

  return 0;
}
--cut here--

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[ubizjak at gmail dot com]

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

--- Comment #4 from Uros Bizjak <ubizjak at gmail dot com> 2012-05-16 17:15:58 UTC ---
foo (struct U * restrict p1, const complex double * restrict x)
{
  vector(4) double vect_var_.41;
  vector(4) double vect_var_.40;
  vector(4) double vect_var_.39;
  vector(4) double vect_var_.38;
  vector(4) double vect_var_.37;
  vector(4) double vect_var_.32;
  vector(4) double vect_var_.31;
  vector(4) double vect_var_.30;
  vector(4) double * restrict vect_p.26;
  vector(4) double vect_var_.25;

<bb 2>:
  vect_var_.37_84 = MEM[(const complex double *)x_5(D)];
  vect_var_.38_86 = MEM[(const complex double *)x_5(D) + 32B];
  vect_var_.39_88 = MEM[(const complex double *)x_5(D) + 64B];
  vect_var_.25_72 = MEM[(const complex double *)x_5(D) + 96B];
  vect_var_.30_76 = MEM[(struct U *)p1_14(D)];
  vect_p.26_77 = p1_14(D) + 32;
  vect_var_.31_78 = MEM[(struct U *)p1_14(D) + 32B];
  vect_p.26_79 = &MEM[(void *)p1_14(D) + 64B];
  vect_var_.32_80 = MEM[(struct U *)p1_14(D) + 64B];
  vect_var_.40_89 = vect_var_.30_76 + vect_var_.37_84;
  vect_var_.40_90 = vect_var_.31_78 + vect_var_.38_86;
  vect_var_.40_91 = vect_var_.32_80 + vect_var_.39_88;
  vect_var_.41_92 = vect_var_.38_86 + vect_var_.40_89;
  vect_var_.41_93 = vect_var_.39_88 + vect_var_.40_90;
  vect_var_.41_94 = vect_var_.25_72 + vect_var_.40_91;
  MEM[(struct U *)p1_14(D)] = vect_var_.41_92;
  MEM[(struct U *)p1_14(D) + 32B] = vect_var_.41_93;
  MEM[(struct U *)p1_14(D) + 64B] = vect_var_.41_94;
  return;

}

It looks to me that x is handled in a totally wrong way.

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[ubizjak at gmail dot com]

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

--- Comment #5 from Uros Bizjak <ubizjak at gmail dot com> 2012-05-16 17:25:50 UTC ---
This testcase fails with -O3 with plain SSE vectorization:

--cut here--
struct S { float v[3]; };
struct T { struct S r, i; };
struct U { struct T j[2]; };

void __attribute__((noinline))
foo (struct U *__restrict p1,
     const float _Complex * __restrict x)
{
  int i, j;

  for (j = 0; j < 2; ++j)
    {
      float a = __builtin_crealf (x[j]);
      float b = __builtin_cimagf (x[j]);
      float c = __builtin_crealf (x[j+2]);
      float d = __builtin_cimagf (x[j+2]);

      for (i = 0; i < 3; ++i)
    {
      p1->j[j].r.v[i] += a;
      p1->j[j].r.v[i] += c;

      p1->j[j].i.v[i] += b;
      p1->j[j].i.v[i] += d;
    }
    }
}

_Complex float x[4];

struct U p1;

int
main ()
{
  int i, j;

  for (i = 0; i < 4; ++i)
    x[i] = i + 1.0iF * (2 * i);

  foo (&p1, x);

  for (j = 0; j < 2; ++j)
    for (i = 0; i < 3; ++i)
      if (p1.j[j].r.v[i] != __builtin_crealf (x[j] + x[j+2])
      || p1.j[j].i.v[i] != __builtin_cimagf (x[j] + x[j+2]))
    __builtin_abort ();

  return 0;
}
--cut here--

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-17 08:45:40 UTC ---
Slightly more reduced:

struct T { float r[3], i[3]; };
struct U { struct T j[2]; };

void __attribute__ ((noinline))
foo (struct U *__restrict y, const float _Complex *__restrict x)
{
  int i, j;
  for (j = 0; j < 2; ++j)
    {
      float a = __real__ x[j];
      float b = __imag__ x[j];
      float c = __real__ x[j + 2];
      float d = __imag__ x[j + 2];
      for (i = 0; i < 3; ++i)
        {
          y->j[j].r[i] = y->j[j].r[i] + a + c;
          y->j[j].i[i] = y->j[j].i[i] + b + d;
        }
    }
}

_Complex float x[4];
struct U y;

int
main ()
{
  int i, j;
  for (i = 0; i < 4; ++i)
    x[i] = i + 1.0iF * (2 * i);
  foo (&y, x);
  for (j = 0; j < 2; ++j)
    for (i = 0; i < 3; ++i)
      if (y.j[j].r[i] != __real__ (x[j] + x[j + 2])
          || y.j[j].i[i] != __imag__ (x[j] + x[j + 2]))
        __builtin_abort ();
  return 0;
}

I bet the bug is in vect_supported_load_permutation_p, in particular the
complex_numbers == 2 handling there.
The if (complex_numbers) doesn't do anything, because
GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == first in all cases,
and then just
  /* We checked that this case ok, so there is no need to proceed with 
     permutation tests.  */
  if (complex_numbers == 2)
    {
      VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (slp_instn));
      VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));
      return true;
    }
I guess we need way more checks than that to verify we don't need to proceed
with permutation tests.  E.g. one possible reason not to return early might be
that complex_numbers != VEC_length (slp_tree, SLP_INSTANCE_LOADS (slp_instn)) ?
In that case we fail to check altogether whether the non-complex permutations
match the complex ones.  I also wonder whether group lengths smaller than
group_size can't be a problem (in this case, group_size is 6, but the complex
groups have just 2 elements).  This stuff has been added as part of the PR44152
fix.

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-17 08:55:36 UTC ---
Indeed,

--- gcc/tree-vect-slp.c.jj    2012-04-19 11:09:13.000000000 +0200
+++ gcc/tree-vect-slp.c    2012-05-17 10:47:30.124290361 +0200
@@ -1199,7 +1199,8 @@ vect_supported_load_permutation_p (slp_i

   /* We checked that this case ok, so there is no need to proceed with 
      permutation tests.  */
-  if (complex_numbers == 2)
+  if (complex_numbers == 2
+      && VEC_length (slp_tree, SLP_INSTANCE_LOADS (slp_instn)) == 2)
     {
       VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (slp_instn));
       VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));

alone fixes this as the further load permutation checks fail.  Whether this is
the right fix and whether it is sufficient, no idea unfortunately, not familiar
enough with the interleaving code.  Richard or Michael, any thoughts?

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-18 10:36:04 UTC ---
(In reply to comment #7)
> Indeed,
> 
> --- gcc/tree-vect-slp.c.jj    2012-04-19 11:09:13.000000000 +0200
> +++ gcc/tree-vect-slp.c    2012-05-17 10:47:30.124290361 +0200
> @@ -1199,7 +1199,8 @@ vect_supported_load_permutation_p (slp_i
> 
>    /* We checked that this case ok, so there is no need to proceed with 
>       permutation tests.  */
> -  if (complex_numbers == 2)
> +  if (complex_numbers == 2
> +      && VEC_length (slp_tree, SLP_INSTANCE_LOADS (slp_instn)) == 2)
>      {
>        VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (slp_instn));
>        VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (slp_instn));
> 
> alone fixes this as the further load permutation checks fail.  Whether this is
> the right fix and whether it is sufficient, no idea unfortunately, not familiar
> enough with the interleaving code.  Richard or Michael, any thoughts?

I'm not very familiar with the code, but the above looks sensible and safe
at least.

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-21 14:29:19 UTC ---
Author: jakub
Date: Mon May 21 14:29:11 2012
New Revision: 187717

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187717
Log:
    PR tree-optimization/53366
    * tree-vect-slp.c (vect_supported_load_permutation_p): Don't shortcut
    tests if complex_numbers == 2, but there are non-complex number loads
    too.

    * gcc.dg/torture/pr53366-1.c: New test.
    * gcc.dg/torture/pr53366-2.c: New test.
    * gcc.target/i386/pr53366-1.c: New test.
    * gcc.target/i386/pr53366-2.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr53366-1.c
    trunk/gcc/testsuite/gcc.dg/torture/pr53366-2.c
    trunk/gcc/testsuite/gcc.target/i386/pr53366-1.c
    trunk/gcc/testsuite/gcc.target/i386/pr53366-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-slp.c

[Bug tree-optimization/53366] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-21 21:03:50 UTC ---
Author: jakub
Date: Mon May 21 21:03:42 2012
New Revision: 187740

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187740
Log:
    PR tree-optimization/53366
    * tree-vect-slp.c (vect_supported_load_permutation_p): Don't shortcut
    tests if complex_numbers == 2, but there are non-complex number loads
    too.

    * gcc.dg/torture/pr53366-1.c: New test.
    * gcc.dg/torture/pr53366-2.c: New test.
    * gcc.target/i386/pr53366-1.c: New test.
    * gcc.target/i386/pr53366-2.c: New test.

Added:
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr53366-1.c
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr53366-2.c
    branches/gcc-4_7-branch/gcc/testsuite/gcc.target/i386/pr53366-1.c
    branches/gcc-4_7-branch/gcc/testsuite/gcc.target/i386/pr53366-2.c
Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_7-branch/gcc/tree-vect-slp.c

[Bug tree-optimization/53366] [4.7/4.8 Regression] wrong code generation by tree vectorizer using AVX

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.7.1
            Summary|wrong code generation by    |[4.7/4.8 Regression] wrong
                   |tree vectorizer using AVX   |code generation by tree
                   |                            |vectorizer using AVX

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-05-22 07:38:53 UTC ---
Fixed.