[Bug tree-optimization/59651] New: Vectorizer failing to spot dependence causes incorrect code generation.

[Bug tree-optimization/59651] New: Vectorizer failing to spot dependence causes incorrect code generation.

[belagod at gcc dot gnu.org]

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

            Bug ID: 59651
           Summary: Vectorizer failing to spot dependence causes incorrect
                    code generation.
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: belagod at gcc dot gnu.org

Hi,

This patch (http://gcc.gnu.org/ml/gcc-patches/2013-12/msg01588.html) seems to
uncover a bug in the vectorizer where it fails to spot dependence. 

When test case gcc.dg/torture/pr52943.c is compiled with -O3, the vectorizer
generates:

main ()
{
  vector(2) int * vectp_a.10;
  vector(2) int * vectp_a.9;
  vector(2) int vect_cst_.8;
  unsigned int tmp.7;
  int tmp.6;
  int b_lsm.5;
  unsigned int patt_1;
  int patt_3;
  unsigned int ivtmp_4;
  int _5;
  _Bool _6;
  int _7;
  unsigned int ivtmp_8;
  int b.1_9;
  unsigned int ivtmp_10;
  int _11;
  int patt_12;
  unsigned int patt_15;
  int b.0_16;
  int b.0_30;
  unsigned int ivtmp_31;
  int b.1_33;
  unsigned int ivtmp_34;
  int b.0_37;
  unsigned int ivtmp_39;
  unsigned int ivtmp_48;

  <bb 2>:
  _5 = a[3];
  _6 = _5 > 1;
  _7 = (int) _6;
  vect_cst_.8_43 = {_7, _7};
  vectp_a.10_44 = &MEM[(void *)&a + 8B];

  <bb 3>:
  # b.0_16 = PHI <b.1_9(7), 3(2)>
  # ivtmp_4 = PHI <ivtmp_10(7), 3(2)>
  # vectp_a.9_45 = PHI <vectp_a.9_46(7), vectp_a.10_44(2)>
  # ivtmp_8 = PHI <ivtmp_48(7), 0(2)>
  MEM[(int *)vectp_a.9_45] = vect_cst_.8_43;
  b.1_9 = b.0_16 + -1;
  ivtmp_10 = ivtmp_4 - 1;
  vectp_a.9_46 = vectp_a.9_45 + 18446744073709551608;
  ivtmp_48 = ivtmp_8 + 1;
  if (ivtmp_48 < 1)
    goto <bb 7>;
  else
    goto <bb 6>;

  <bb 4>:
  # b.0_30 = PHI <b.1_33(5), 1(6)>
  # ivtmp_31 = PHI <ivtmp_34(5), 1(6)>
  a[b.0_30] = _7;
  b.1_33 = b.0_30 + -1;
  ivtmp_34 = ivtmp_31 - 1;
  if (ivtmp_34 != 0)
    goto <bb 5>;
  else
    goto <bb 8>;

  <bb 5>:
  goto <bb 4>;

  <bb 6>:
  # b.0_37 = PHI <b.1_9(3)>
  # ivtmp_39 = PHI <ivtmp_10(3)>
  goto <bb 4>;

  <bb 7>:
  goto <bb 3>;

  <bb 8>:
  b = 0;
  _11 = a[1];
  if (_11 != 0)
    goto <bb 9>;
  else
    goto <bb 10>;

  <bb 9>:
  abort ();

  <bb 10>:
  return 0;

}


>From the above test, it seems that _7 is precalculated in BB 2 using

 _5 = a[3];
  _6 = _5 > 1;
  _7 = (int) _6;
  vect_cst_.8_43 = {_7, _7};

and stored everywhere without considering the dependence on a[3].

  MEM[(int *)vectp_a.9_45] = vect_cst_.8_43;
  ...
  # b.0_30 = PHI <b.1_33(5), 1(6)>
  # ivtmp_31 = PHI <ivtmp_34(5), 1(6)>
  a[b.0_30] = _7;
  b.1_33 = b.0_30 + -1;
  ivtmp_34 = ivtmp_31 - 1;

I observed this while running regressions on aarch64. My config is:

.../gcc/configure --target=aarch64-none-elf --prefix=.../install
--with-gmp=.../host-tools --with-mpfr=.../host-tools --with-mpc=.../host-tools
--with-pkgversion=unknown --disable-shared --disable-nls --disable-threads
--disable-tls --enable-checking=yes --enable-languages=c,c++ --with-newlib

[Bug tree-optimization/59651] Vectorizer failing to spot dependence causes incorrect code generation.

[bmei at broadcom dot com]

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

--- Comment #1 from Bingfeng Mei <bmei at broadcom dot com> ---
That is interesting. On x86-64, GCC does say it cannot determine dist vector
between a[3] & a[b] and needs run-time aliasing test. In the end it gives up
due to too few iterations. 

note: === vect_analyze_data_ref_dependences ===
(compute_affine_dependence
  stmt_a: _5 = a[3];
  stmt_b: a[b.0_16] = _7;
(analyze_overlapping_iterations 
  (chrec_a = 3)
  (chrec_b = {3, +, -1}_1)
(analyze_siv_subscript 
)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
(Dependence relation cannot be represented by distance vector.) 
)
(compute_affine_dependence
  stmt_a: _5 = a[3];
  stmt_b: _5 = a[3];
(analyze_overlapping_iterations 
  (chrec_a = 3)
  (chrec_b = 3)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
)
(compute_affine_dependence
  stmt_a: a[b.0_16] = _7;
  stmt_b: a[b.0_16] = _7;
(analyze_overlapping_iterations 
  (chrec_a = {3, +, -1}_1)
  (chrec_b = {3, +, -1}_1)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
)
/projects/firepath_tools1_scratch/bmei/trunk/gcc/testsuite/gcc.dg/torture/pr52943.c:13:7:
note: versioning for alias required: bad dist vector for a[3] and a[b.0_16]
/projects/firepath_tools1_scratch/bmei/trunk/gcc/testsuite/gcc.dg/torture/pr52943.c:13:7:
note: mark for run-time aliasing test between a[3] and a[b.0_16]

[Bug tree-optimization/59651] Vectorizer failing to spot dependence causes incorrect code generation.

[belagod at gcc dot gnu.org]

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

--- Comment #2 from belagod at gcc dot gnu.org ---
Something simliar happens on aarch64, but later goes ahead and vectorizes it
anyway. How about trying to vectorize on x86 with -fno-vect-cost-model?

pr.c:13:7: note: === vect_analyze_data_ref_dependences ===
(compute_affine_dependence
  stmt_a: _5 = a[3];
  stmt_b: a[b.0_16] = _7;
(analyze_overlapping_iterations 
  (chrec_a = 3)
  (chrec_b = {3, +, -1}_1)
(analyze_siv_subscript 
)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
(Dependence relation cannot be represented by distance vector.) 
)
(compute_affine_dependence
  stmt_a: _5 = a[3];
  stmt_b: _5 = a[3];
(analyze_overlapping_iterations 
  (chrec_a = 3)
  (chrec_b = 3)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
)
(compute_affine_dependence
  stmt_a: a[b.0_16] = _7;
  stmt_b: a[b.0_16] = _7;
(analyze_overlapping_iterations 
  (chrec_a = {3, +, -1}_1)
  (chrec_b = {3, +, -1}_1)
  (overlap_iterations_a = [0])
  (overlap_iterations_b = [0]))
)
pr.c:13:7: note: versioning for alias required: bad dist vector for a[3] and
a[b.0_16]
pr.c:13:7: note: mark for run-time aliasing test between a[3] and a[b.0_16]

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
   Target Milestone|---                         |4.9.0
            Summary|Vectorizer failing to spot  |[4.9 Regression] Vectorizer
                   |dependence causes incorrect |failing to spot dependence
                   |code generation.            |causes incorrect code
                   |                            |generation.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[bmei at broadcom dot com]

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

--- Comment #3 from Bingfeng Mei <bmei at broadcom dot com> ---
I can reproduce on aarch64. Still try to understand why. I constructed a
similar test but with positive loop step.

extern void abort (void);
int a[] = { 6, 0, 0, 0 };

int b;
int
main ()
{
  for (;;)
    {
      b = 0;
      for (; b<3; b += 1)
    a[b] = a[0] > 1;
      break;
    }
  if (a[2] != 0)
    abort ();
  return 0;
}

Actually GCC behaves similarly during vectorization and does vectorize the
loop. The only difference is around loop versioning. 

pr52943.c
  <bb 10>:
  if (1 != 0)
    goto <bb 11>;
  else
    goto <bb 12>;

bb 11 leads to vectorized version. So scalar version gets optimized out.

Above example:
  <bb 10>:
  if (0 != 0)
    goto <bb 11>;
  else
    goto <bb 12>;
So vectorized version goes away and only scalar version remains.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[belagod at gcc dot gnu.org]

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

--- Comment #4 from belagod at gcc dot gnu.org ---
Thanks for looking at this.

Just to clarify, do you mean loop versioning happens in the up-counting loop?
Because in the down-counting loop, a partition seems to be happening with 2
iterations of the loop getting vectorized and the remaining 2 are left scalar.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[bmei at broadcom dot com]

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

--- Comment #5 from Bingfeng Mei <bmei at broadcom dot com> ---
Created attachment 31559
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31559&action=edit
initial patch

Hi, Tejas, vect_create_cond_for_alias_checks contains a bug in handling
negative step. The computed data access range should be shifted by
TYPE_SIZE_UNIT of bytes. Could you test the attached patch on aarch64 (I don't
have simulation environment setup)? Meanwhile I will check whether there is any
regression on x86-64. If everything is right, I am going to submit the patch.
Thanks.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[belagod at gcc dot gnu.org]

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

--- Comment #6 from belagod at gcc dot gnu.org ---
Thanks for the patch. It fixes this particular test case regression. I've
kicked off a full regression and will let you know the results soon.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[belagod at gcc dot gnu.org]

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

--- Comment #7 from Tejas Belagod <belagod at gcc dot gnu.org> ---
AArch64 regressions came back OK. Thanks!

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[meibf at gcc dot gnu.org]

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

--- Comment #8 from meibf at gcc dot gnu.org ---
Author: meibf
Date: Fri Jan  3 15:40:57 2014
New Revision: 206319

URL: http://gcc.gnu.org/viewcvs?rev=206319&root=gcc&view=rev
Log:
2014-01-03  Bingfeng Mei <bmei@broadcom.com>

    PR tree-optimization/59651
    * tree-vect-loop-manip.c (vect_create_cond_for_alias_checks): 
    Address    range for negative step should be added by TYPE_SIZE_UNIT.

    PR tree-optimization/59651
    * gcc.dg/torture/pr59651.c: New test.
    * gcc.dg/vect/pr59651.c: Ditto.


Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr59651.c
    trunk/gcc/testsuite/gcc.dg/vect/pr59651.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-loop-manip.c

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |jakub at gcc dot gnu.org
         Resolution|---                         |FIXED

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/59651] [4.9 Regression] Vectorizer failing to spot dependence causes incorrect code generation.

[mshawcroft at gcc dot gnu.org]

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

mshawcroft at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |christophe.lyon at st dot com

--- Comment #10 from mshawcroft at gcc dot gnu.org ---
*** Bug 59725 has been marked as a duplicate of this bug. ***