[Bug tree-optimization/46194] New: [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[Bug tree-optimization/46194] New: [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[zsojka at seznam dot cz]

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

           Summary: [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs
                    with -ftree-parallelize-loops
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zsojka@seznam.cz


Graphite is not needed to reproduce this. The output value looks "random", it
differs in different runs.

Output (with #define DEBUG 1):
$ gcc -O -ftree-parallelize-loops=2 block-0.c && ./a.out 
res = 2155 
Aborted
$ ./a.out 
res = 2156 
Aborted
$ ./a.out 
res = 2201 
Aborted

Tested revisions:
r165915 - fail
r153685 - fail
4.5 r165781 - fail
4.4 r165754 - OK

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[hjl.tools at gmail dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.10.27 10:19:03
                 CC|                            |hubicka at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2010-10-27 10:19:03 UTC ---
It is caused by revision 153457:

http://gcc.gnu.org/ml/gcc-cvs/2009-10/msg01110.html

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.5.2

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.2                       |4.5.3

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-12-16 13:03:46 UTC ---
GCC 4.5.2 is being released, adjusting target milestone.

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-12-31 12:01:51 UTC ---
This shouldn't be parallelized, the loop clearly is not parallelizable.  But we
have:
(Data Dep: 
#(Data Ref: 
#  stmt: D.2709_5 = a[i_16];
#  ref: a[i_16];
#  base_object: a
#  Access function 0: {0, +, 1}_1
#)
#(Data Ref: 
#  stmt: a[j_20] = D.2710_6;
#  ref: a[j_20];
#  base_object: a
#  Access function 0: {0, +, 1}_2
#)
  access_fn_A: {0, +, 1}_1
  access_fn_B: {0, +, 1}_2

 (subscript 
  iterations_that_access_an_element_twice_in_A: [0 + 1 * x_1]
  last_conflict: 1000
  iterations_that_access_an_element_twice_in_B: [0 + 1 * x_1]
  last_conflict: 1000
  (Subscript distance: 0
  )
 )
  inner loop index: 0
  loop nest: (1 2 )
  distance_vector:   0   0 
  direction_vector:     =    =
)
(Data Dep: 
#(Data Ref: 
#  stmt: D.2709_5 = a[i_16];
#  ref: a[i_16];
#  base_object: a
#  Access function 0: {0, +, 1}_1
#)
#(Data Ref: 
#  stmt: D.2709_5 = a[i_16];
#  ref: a[i_16];
#  base_object: a
#  Access function 0: {0, +, 1}_1
#)
  inner loop index: 0
  loop nest: (1 2 )
  distance_vector:   0   0 
  direction_vector:     +    +
)
(Data Dep: 
#(Data Ref: 
#  stmt: a[j_20] = D.2710_6;
#  ref: a[j_20];
#  base_object: a
#  Access function 0: {0, +, 1}_2
#)
#(Data Ref: 
#  stmt: a[j_20] = D.2710_6;
#  ref: a[j_20];
#  base_object: a
#  Access function 0: {0, +, 1}_2
#)
  inner loop index: 0
  loop nest: (1 2 )
  distance_vector:   0   0 
  direction_vector:     +    +
)
  SUCCESS: may be parallelized

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[zsojka at seznam dot cz]

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

--- Comment #4 from Zdenek Sojka <zsojka at seznam dot cz> 2010-12-31 13:09:08 UTC ---
When -fcheck-data-deps is added, the testcase doesn't fail (r168358,
x86_64-linux):

$ gcc -O -ftree-parallelize-loops=2 block-0.c -fcheck-data-deps
$ ./a.out
$ echo $?
0

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-02-03 08:41:46 UTC ---
Sebastian, could you please look at this?  Thanks.

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

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

--- Comment #6 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-03 17:33:52 UTC ---
Mine.  I will have a look at this.

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[sebpop at gmail dot com]

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

--- Comment #7 from sebpop at gmail dot com <sebpop at gmail dot com> 2011-02-03 18:11:09 UTC ---
Here is the loop kernel from block-0.c

  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      a[j] = a[i] + 1;

On Fri, Dec 31, 2010 at 06:01, jakub at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
>  access_fn_A: {0, +, 1}_1
>  access_fn_B: {0, +, 1}_2
>
>  (subscript
>  iterations_that_access_an_element_twice_in_A: [0 + 1 * x_1]
>  last_conflict: 1000
>  iterations_that_access_an_element_twice_in_B: [0 + 1 * x_1]

I think that this representation of affine functions is wrong:
the access in B should read [0 + 0 * x_1 + 1 * x_2] and that
would not lead to a wrong conclusion like the following...

>  last_conflict: 1000
>  (Subscript distance: 0
>  )
>  )
>  inner loop index: 0
>  loop nest: (1 2 )
>  distance_vector:   0   0
>  direction_vector:     =    =
> )

Re: [Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[Sebastian Pop]

Here is the loop kernel from block-0.c

  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      a[j] = a[i] + 1;

On Fri, Dec 31, 2010 at 06:01, jakub at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
>  access_fn_A: {0, +, 1}_1
>  access_fn_B: {0, +, 1}_2
>
>  (subscript
>  iterations_that_access_an_element_twice_in_A: [0 + 1 * x_1]
>  last_conflict: 1000
>  iterations_that_access_an_element_twice_in_B: [0 + 1 * x_1]

I think that this representation of affine functions is wrong:
the access in B should read [0 + 0 * x_1 + 1 * x_2] and that
would not lead to a wrong conclusion like the following...

>  last_conflict: 1000
>  (Subscript distance: 0
>  )
>  )
>  inner loop index: 0
>  loop nest: (1 2 )
>  distance_vector:   0   0
>  direction_vector:     =    =
> )

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

--- Comment #8 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-03 18:20:56 UTC ---
The problem seems to be in analyze_miv_subscript where I see this note:

  /* FIXME:  This is a MIV subscript, not yet handled.
     Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
     (A[i] vs. A[j]).

     In the SIV test we had to solve a Diophantine equation with two
     variables.  In the MIV case we have to solve a Diophantine
     equation with 2*n variables (if the subscript uses n IVs).
  */

Re: [Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[Sebastian Pop]

>>  access_fn_A: {0, +, 1}_1
>>  access_fn_B: {0, +, 1}_2
>>
>>  (subscript
>>  iterations_that_access_an_element_twice_in_A: [0 + 1 * x_1]
>>  last_conflict: 1000
>>  iterations_that_access_an_element_twice_in_B: [0 + 1 * x_1]
>
> I think that this representation of affine functions is wrong:
> the access in B should read [0 + 0 * x_1 + 1 * x_2] and that
> would not lead to a wrong conclusion like the following...

This representation is correct, as it stands for: there exists
a dependence for all x_1 from 0 to 1000, that is, there exist
a possible overlap that is represented by:

{0, +, 1}_1 ([0 + 1 * x_1]) == {0, +, 1}_2 ([0 + 1 * x_1])

>
>>  last_conflict: 1000
>>  (Subscript distance: 0
>>  )
>>  )
>>  inner loop index: 0
>>  loop nest: (1 2 )
>>  distance_vector:   0   0
>>  direction_vector:     =    =
>> )
>

This representation is still wrong, and so I went to see where this
was computed, and the bug seems to be in build_classic_dist_vector_1
I will submit a patch to fix this.

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[sebpop at gmail dot com]

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

--- Comment #9 from sebpop at gmail dot com <sebpop at gmail dot com> 2011-02-03 19:54:36 UTC ---
>>  access_fn_A: {0, +, 1}_1
>>  access_fn_B: {0, +, 1}_2
>>
>>  (subscript
>>  iterations_that_access_an_element_twice_in_A: [0 + 1 * x_1]
>>  last_conflict: 1000
>>  iterations_that_access_an_element_twice_in_B: [0 + 1 * x_1]
>
> I think that this representation of affine functions is wrong:
> the access in B should read [0 + 0 * x_1 + 1 * x_2] and that
> would not lead to a wrong conclusion like the following...

This representation is correct, as it stands for: there exists
a dependence for all x_1 from 0 to 1000, that is, there exist
a possible overlap that is represented by:

{0, +, 1}_1 ([0 + 1 * x_1]) == {0, +, 1}_2 ([0 + 1 * x_1])

>
>>  last_conflict: 1000
>>  (Subscript distance: 0
>>  )
>>  )
>>  inner loop index: 0
>>  loop nest: (1 2 )
>>  distance_vector:   0   0
>>  direction_vector:     =    =
>> )
>

This representation is still wrong, and so I went to see where this
was computed, and the bug seems to be in build_classic_dist_vector_1
I will submit a patch to fix this.

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

--- Comment #10 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-04 04:00:22 UTC ---
Patch:
http://gcc.gnu.org/ml/gcc-patches/2011-02/msg00271.html

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

--- Comment #11 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-05 01:39:23 UTC ---
Author: spop
Date: Sat Feb  5 01:39:20 2011
New Revision: 169847

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169847
Log:
Fix PR46194: fix the computation of distance vectors.

2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>

    PR tree-optimization/46194
    * tree-data-ref.c (analyze_miv_subscript): Remove comment.
    (build_classic_dist_vector_1): Do not represent classic distance
    vectors when the access functions are variating in different loops.

    * gcc.dg/autopar/pr46194.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/autopar/pr46194.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-data-ref.c

[Bug tree-optimization/46194] [4.5/4.6 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.6.0
      Known to fail|4.6.0                       |

--- Comment #12 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-05 01:41:41 UTC ---
Fixed on trunk.
Should I backport this patch to 4.5?

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|4.6.0                       |4.5.4
   Target Milestone|4.5.3                       |4.5.4
            Summary|[4.5/4.6 Regression]        |[4.5 Regression]
                   |gcc.dg/graphite/block-0.c   |gcc.dg/graphite/block-0.c
                   |FAILs with                  |FAILs with
                   |-ftree-parallelize-loops    |-ftree-parallelize-loops

--- Comment #13 from Sebastian Pop <spop at gcc dot gnu.org> 2011-02-07 22:45:02 UTC ---
Adjust subject and milestone.

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|4.5.4                       |4.6.0
   Target Milestone|4.5.4                       |4.5.3

--- Comment #14 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-18 14:43:23 UTC ---
A backport would be nice.

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

--- Comment #15 from Sebastian Pop <spop at gcc dot gnu.org> 2011-04-18 16:09:49 UTC ---
The same patch applies to the 4.5 branch.
I am currently testing the patch on amd64-linux.

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

--- Comment #16 from Sebastian Pop <spop at gcc dot gnu.org> 2011-04-19 16:24:44 UTC ---
The patch produces these fails on the 4.5 branch:

FAIL: gcc.dg/tree-ssa/ltrans-1.c scan-tree-dump-times ltrans "converted loop
nest to perfect loop nest" 1
FAIL: gcc.dg/tree-ssa/ltrans-1.c scan-tree-dump-times ltrans "transformed loop"
1
FAIL: gfortran.dg/ltrans-7.f90  -O  scan-tree-dump-times ltrans "transformed
loop" 1

It looks like the change was needed to make the loop interchange
possible on these examples.  In 4.6, Graphite is taking care of
the interchange cases and so we don't exercise the corner cases of
the multivariate data dependence test.

The patch removes this case:
-         /* The dependence is carried by the outermost loop.  Example:
-            | loop_1
-            |   A[{4, +, 1}_1]
-            |   loop_2
-            |     A[{5, +, 1}_2]
-            |   endloop_2
-            | endloop_1
-            In this case, the dependence is carried by loop_1.  */

because we use the information that the dependence is carried
by the outermost loop to wrongly infer that the innermost loop
does not carry dependences, leading to the parallelization of the
innermost loop:

+  for (i = 0; i < N; i++)
+    for (j = 0; j < N; j++)
+      a[j] = a[i] + 1;
+/* This loop cannot be parallelized due to a dependence.  */

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.3                       |4.5.4

--- Comment #17 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-28 14:51:53 UTC ---
GCC 4.5.3 is being released, adjusting target milestone.

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

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

--- Comment #18 from Sebastian Pop <spop at gcc dot gnu.org> 2011-07-26 19:38:41 UTC ---
Unassigning: I won't backport this patch.
So I guess we could just close it as wont_fix.

[Bug tree-optimization/46194] [4.5 Regression] gcc.dg/graphite/block-0.c FAILs with -ftree-parallelize-loops

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX

--- Comment #19 from Sebastian Pop <spop at gcc dot gnu.org> 2011-07-27 18:25:14 UTC ---
Closing as wont backport fix to 4.5.