[Bug 45764] (tree-optimization) New: wrong code -O2 vs -O3 (problem in vectorizer???)

[Bug 45764] (tree-optimization) New: wrong code -O2 vs -O3 (problem in vectorizer???)

[wouter.vermaelen at scarlet dot be]

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

           Summary: wrong code  -O2 vs -O3    (problem in vectorizer???)
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wouter.vermaelen@scarlet.be


> cat bug.cc
int result[64][16];

int main()
{
        double dbuf[1000] = {0.0};
        int ibuf[900];

        double d1 = 0.0;
        double d2 = 0.0;
        for (int i = 0; i < 900; ++i) {
                ibuf[i] = int(d2 - d1);
                d1 += dbuf[i];
                d2 += dbuf[i + 64];
        }

        for (int i = 0; i < 64; ++i) {
                for (int j = 0; j < 8; ++j) {
                        result[i][     j] = ibuf[64 - i + 64 * j];
                        result[i][15 - j] = ibuf[     i + 64 * j];
                }
        }
}

> g++ -O2 bug.cc
> ./a.out
> g++ -O3 bug.cc
> ./a.out
Segmentation fault (core dumped)

I'm using SVN revision 164570 on linux_x86_64.

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug 45764] (tree-optimization) wrong code -O2 vs -O3 (problem in vectorizer???)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86-linux-gnu

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2010-09-23 22:20:26 UTC ---
Works for me with an slightly older GCC:
GNU C (GCC) version 4.6.0 20100905 (experimental) [trunk revision 163885]
(x86_64-unknown-linux-gnu)
    compiled by GNU C version 4.6.0 20100905 (experimental) [trunk revision
163885], GMP version 4.3.2, MPFR version 2.4.2, MPC version 0.8.1

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug 45764] (tree-optimization) wrong code -O2 vs -O3 (problem in vectorizer???)

[hjl.tools at gmail dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.09.24 04:33:18
               date|                            |
                 CC|                            |hjl.tools at gmail dot com,
                   |                            |matz at gcc dot gnu.org
   Target Milestone|---                         |4.6.0
     Ever Confirmed|0                           |1

--- Comment #2 from H.J. Lu <hjl.tools at gmail dot com> 2010-09-24 04:33:18 UTC ---
It is caused by revision 45764:

http://gcc.gnu.org/ml/gcc-cvs/2010-09/msg00661.html

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[matz at gcc dot gnu.org]

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

--- Comment #3 from Michael Matz <matz at gcc dot gnu.org> 2010-09-24 13:37:04 UTC ---
The problem is how the alignment for the read accesses is computed.
When we vectorize this data_ref:
  ibuf[64 - i]   (0 <= i < 64)
i.e.
  ibuf[64 .. 1]
The first access is to ibuf[64], which is aligned to 16 just fine.
But when accessing multiple elements (ibuf[64 .. 61]) the actual
base address will be &ibuf[61], which is not aligned to 16 bytes.

I think the code in vectorizable_load that tries to recompute alignment
info from the underlying scalar pointers is incorrect.  We currently have:

                pi = get_ptr_info (dataref_ptr);
                pi->align = TYPE_ALIGN_UNIT (vectype);
                if (alignment_support_scheme == dr_aligned)
                  {
                    gcc_assert (aligned_access_p (first_dr));
                    pi->misalign = 0;
                  }
                else if (DR_MISALIGNMENT (first_dr) == -1)
                  {
                    TREE_TYPE (data_ref)
                      = build_aligned_type (TREE_TYPE (data_ref),
                                            TYPE_ALIGN (TREE_TYPE (vectype)));
                    pi->align = TYPE_ALIGN_UNIT (TREE_TYPE (vectype));
                    pi->misalign = 0;
                  }
                else
                  {
                    TREE_TYPE (data_ref)
                      = build_aligned_type (TREE_TYPE (data_ref),
                                            TYPE_ALIGN (TREE_TYPE (vectype)));
                    pi->misalign = DR_MISALIGNMENT (first_dr);
                  }

dataref_ptr will be the vector pointer.  One problem is that for the
testcase alignment_support_scheme is set to dr_aligned.  That is because
DR_MISALIGNMENT of first_dr is zero.  But first_dr is in terms of the scalar
type, so it seems problematic to use that to assess if the vectorized
access is also aligned.  OTOH that is historic code.

But even if we would fix that (set alignment_support_scheme to 
dr_unaligned_supported) the code above would do the wrong thing.
DR_MISALIGNMENT (first_dr) is zero, so pi->align would remain at the
(large) alignment of the vector type, and it's misalignment (which was with
respect to the smaller scalar type) would be copied over, also be zero,
and therefore wrong.

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-09-24 14:22:23 UTC ---
It looks like when vectorizing with negative step the alignment needs to be
computed differently.

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[matz at gcc dot gnu.org]

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

Michael Matz <matz at gcc dot gnu.org> changed:

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

--- Comment #5 from Michael Matz <matz at gcc dot gnu.org> 2010-09-24 16:06:03 UTC ---
This patch will set the correct misalign info on that data-reference:

Index: tree-vect-data-refs.c
===================================================================
--- tree-vect-data-refs.c       (revision 164476)
+++ tree-vect-data-refs.c       (working copy)
@@ -900,6 +900,19 @@ vect_compute_data_ref_alignment (struct
              || (TREE_CODE (base) == VAR_DECL
                  && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));

+  /* If this is a backward running DR then first access in the larger
+     vectype actually is N-1 elements before the address in the DR.
+     Adjust misalign accordingly.  */
+  if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
+    {
+      tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
+      /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
+         otherwise we wouldn't be here.  */
+      offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
+      /* PLUS because DR_STEP was negative.  */
+      misalign = size_binop (PLUS_EXPR, misalign, offset);
+    }
+
   /* Modulo alignment.  */
   misalign = size_binop (FLOOR_MOD_EXPR, misalign, alignment);


Unfortunately this will later result in an ICE during peeling.  It
wants to peel these data-refs that now are known misaligned, and during cost
computation changes data-refs that have the same alignment state to be
aligned too (makes sense because those data-refs will also be aligned when
the to-be-peeled DR is aligned).

Unfortunately the STMT_VINFO_SAME_ALIGN_REFS contains bogus reference,
because ultimately the distance vectors are wrong:

(compute_affine_dependence
  (stmt_a = D.2097_46 = ibuf[D.2094_43];)
  (stmt_b = D.2100_64 = ibuf[D.2099_63];)
(subscript_dependence_tester
(analyze_overlapping_iterations
  (chrec_a = {64, +, -1}_2)
  (chrec_b = {64, +, 1}_2)
(analyze_siv_subscript
(analyze_subscript_affine_affine
  (overlaps_a = [0]
  (overlaps_b = [0]
  (overlap_iterations_a = [0]
  (overlap_iterations_b = [0]
(build_classic_dist_vector
  dist_vector = (  0  )

So, we have two DRs running in opposite directions, which happen to
have the initial element in common (index 64), but afterwards diverge and
have nothing in common anymore.  So overlap_iterations_a/b is correct.
But the distance vector is 0, meaning 'same in all iterations'.  That
is used to initialize STMT_VINFO_SAME_ALIGN_REFS in
vect_find_same_alignment_drs .

Obviously the distance vector should be unknown (it could be a chrec, if
we really want, namely {0, +, 2}_2, but we don't do anything with such
distances).  I tried to determine why it is wrong, it's ultimately
coming from SUB_DISTANCE of that DDR, computed like so
(compute_subscript_distance):

          subscript = DDR_SUBSCRIPT (ddr, i);
          cf_a = SUB_CONFLICTS_IN_A (subscript);
          cf_b = SUB_CONFLICTS_IN_B (subscript);

          fn_a = common_affine_function (cf_a);
          fn_b = common_affine_function (cf_b);
          if (!fn_a || !fn_b)
            {
              SUB_DISTANCE (subscript) = chrec_dont_know;
              return;
            }
          diff = affine_fn_minus (fn_a, fn_b);

          if (affine_function_constant_p (diff))
            SUB_DISTANCE (subscript) = affine_function_base (diff);
          else
            SUB_DISTANCE (subscript) = chrec_dont_know;

And this is baffling me a bit.  How could it be correct to
determine a distance vector from only the conflict functions?  Doing so
ignores all non-conflicting accesses, although they can (and indeed here do)
influence the distance too.

CCing Zdenek and Sebastian, maybe they have some insight in the latter
problem, as those aren't really related to the vectorizer.

-- 
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from hjl at gcc dot gnu.org <hjl at gcc dot gnu.org> 2010-10-03 05:41:44 UTC ---
Author: hjl
Date: Sun Oct  3 05:39:32 2010
New Revision: 164914

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=164914
Log:
Disallow negative steps in vectorizer.

gcc/

2010-10-02  H.J. Lu  <hongjiu.lu@intel.com>

    PR tree-optimization/45720
    PR tree-optimization/45764
    * tree-vect-data-refs.c (vect_analyze_data_ref_access):
    Don't accept backwards consecutive accesses.
    (vect_create_data_ref_ptr): Disallow negative steps.

    * tree-vect-stmts.c (vectorizable_store): Allow negative steps.
    (perm_mask_for_reverse): Removed.
    (reverse_vec_elements): Likewise.
    (vectorizable_load): Don't hanle negative steps.

gcc/testsuite/

2010-10-02  H.J. Lu  <hongjiu.lu@intel.com>

    PR tree-optimization/45720
    PR tree-optimization/45764
    * g++.dg/torture/pr45764.C: New.

    * gcc.dg/vect/pr43432.c: Xfail.
    * gcc.dg/vect/vect-114.c: Likewise.
    * gcc.dg/vect/vect-15.c: Likewise.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr45764.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/vect/pr43432.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-114.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-15.c
    trunk/gcc/tree-vect-data-refs.c
    trunk/gcc/tree-vect-stmts.c

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-14 10:19:07 UTC ---
(In reply to comment #5)
> This patch will set the correct misalign info on that data-reference:
> 
> Index: tree-vect-data-refs.c
> ===================================================================
> --- tree-vect-data-refs.c       (revision 164476)
> +++ tree-vect-data-refs.c       (working copy)
> @@ -900,6 +900,19 @@ vect_compute_data_ref_alignment (struct
>               || (TREE_CODE (base) == VAR_DECL
>                   && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
> 
> +  /* If this is a backward running DR then first access in the larger
> +     vectype actually is N-1 elements before the address in the DR.
> +     Adjust misalign accordingly.  */
> +  if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
> +    {
> +      tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
> +      /* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
> +         otherwise we wouldn't be here.  */
> +      offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
> +      /* PLUS because DR_STEP was negative.  */
> +      misalign = size_binop (PLUS_EXPR, misalign, offset);
> +    }
> +
>    /* Modulo alignment.  */
>    misalign = size_binop (FLOOR_MOD_EXPR, misalign, alignment);
> 
> 
> Unfortunately this will later result in an ICE during peeling.  It
> wants to peel these data-refs that now are known misaligned, and during cost
> computation changes data-refs that have the same alignment state to be
> aligned too (makes sense because those data-refs will also be aligned when
> the to-be-peeled DR is aligned).
> 
> Unfortunately the STMT_VINFO_SAME_ALIGN_REFS contains bogus reference,
> because ultimately the distance vectors are wrong:
> 
> (compute_affine_dependence
>   (stmt_a = D.2097_46 = ibuf[D.2094_43];)
>   (stmt_b = D.2100_64 = ibuf[D.2099_63];)
> (subscript_dependence_tester
> (analyze_overlapping_iterations
>   (chrec_a = {64, +, -1}_2)
>   (chrec_b = {64, +, 1}_2)
> (analyze_siv_subscript
> (analyze_subscript_affine_affine
>   (overlaps_a = [0]
>   (overlaps_b = [0]
>   (overlap_iterations_a = [0]
>   (overlap_iterations_b = [0]
> (build_classic_dist_vector
>   dist_vector = (  0  )
> 
> So, we have two DRs running in opposite directions, which happen to
> have the initial element in common (index 64), but afterwards diverge and
> have nothing in common anymore.  So overlap_iterations_a/b is correct.
> But the distance vector is 0, meaning 'same in all iterations'.  That
> is used to initialize STMT_VINFO_SAME_ALIGN_REFS in
> vect_find_same_alignment_drs .
> 
> Obviously the distance vector should be unknown (it could be a chrec, if
> we really want, namely {0, +, 2}_2, but we don't do anything with such
> distances).  I tried to determine why it is wrong, it's ultimately
> coming from SUB_DISTANCE of that DDR, computed like so
> (compute_subscript_distance):
> 
>           subscript = DDR_SUBSCRIPT (ddr, i);
>           cf_a = SUB_CONFLICTS_IN_A (subscript);
>           cf_b = SUB_CONFLICTS_IN_B (subscript);
> 
>           fn_a = common_affine_function (cf_a);
>           fn_b = common_affine_function (cf_b);
>           if (!fn_a || !fn_b)
>             {
>               SUB_DISTANCE (subscript) = chrec_dont_know;
>               return;
>             }
>           diff = affine_fn_minus (fn_a, fn_b);
> 
>           if (affine_function_constant_p (diff))
>             SUB_DISTANCE (subscript) = affine_function_base (diff);
>           else
>             SUB_DISTANCE (subscript) = chrec_dont_know;
> 
> And this is baffling me a bit.  How could it be correct to
> determine a distance vector from only the conflict functions?  Doing so
> ignores all non-conflicting accesses, although they can (and indeed here do)
> influence the distance too.
> 
> CCing Zdenek and Sebastian, maybe they have some insight in the latter
> problem, as those aren't really related to the vectorizer.

It seems to be that the distance vector should be unknown if for
any pair of indices in the data-references the evolution of the
access function is different.  Thus,

   if (tree_does_not_contain_chrecs
        (chrec_fold_minus (some-type,
                         DR_ACCESS_FN (DDR_A (ddr), i),
                         DR_ACCESS_FN (DDR_B (ddr), i))))
     {
       SUB_DISTANCE (subscript) = chrec_dont_know;
       return;
     }

in case the DDR subscripts match up with the DR access-fns.  Otherwise
something more complicated of course.

And maybe there's a helper for the above already.

Zdenek?  Sebastian?

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-14 11:54:13 UTC ---
The snippet seems to work as far as to set SUB_DISTANCE to chrec_dont_know,
together with the suggested fix in comment #5 it fixes this PR.

Now, the hunk below alone would already compute the distance vector,
so I'm not sure what the rest of the function is supposed to do
(and why it doesn't handle steps appropriately).

Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c     (revision 165456)
+++ tree-data-ref.c     (working copy)
@@ -1165,6 +1165,16 @@ compute_subscript_distance (struct data_
              SUB_DISTANCE (subscript) = chrec_dont_know;
              return;
            }
+
+         if (tree_contains_chrecs
+               (chrec_fold_minus (TREE_TYPE (DR_ACCESS_FN (DDR_A (ddr), i)),
+                                  DR_ACCESS_FN (DDR_A (ddr), i),
+                                  DR_ACCESS_FN (DDR_B (ddr), i)), NULL))
+           {
+             SUB_DISTANCE (subscript) = chrec_dont_know;
+             return;
+           }
+
          diff = affine_fn_minus (fn_a, fn_b);

          if (affine_function_constant_p (diff))


It looks like if we ever start to vectorize strided stores then we'd miscompile

  a[i*2] = a[(i+1)*2];

as well.  Here we have no dependence, thus the conflict function should
be no-conflict (which leads us to no distance vector).

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-21 10:01:10 UTC ---
Testing a patch.

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-21 11:10:45 UTC ---
Author: rguenth
Date: Thu Oct 21 11:10:41 2010
New Revision: 165768

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=165768
Log:
2010-10-21  Richard Guenther  <rguenther@suse.de>
    Michael Matz  <matz@suse.de>

    PR tree-optimization/45764
    * tree-vect-data-refs.c (vect_compute_data_ref_alignment):
    Adjust initial misalignment for negative DR_STEP.
    (vect_find_same_alignment_drs): Two DRs with different DR_STEP
    do not have the same alignment over the whole iteration domain.

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

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr45764.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-data-refs.c

[Bug tree-optimization/45764] [4.6 Regression] wrong code -O2 vs -O3 (problem in vectorizer???)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-21 11:11:18 UTC ---
Fixed.