[Bug tree-optimization/42637] New: wrong code for -floop-interchange -ftree-loop-distribution

[Bug tree-optimization/42637] New: wrong code for -floop-interchange -ftree-loop-distribution

[janis at gcc dot gnu dot org]

As mentioned in PR 42334, 200.sixtrack from SPEC CPU2000 started getting wrong
answers on powerpc64-linux with the Graphite merge at r140301 when compiled
with "-O2 -floop-interchange -ftree-loop-distribution".  The loop that is
miscompiled is:

      real*8 rt(6,6),r(6,6),rtt(6,6)
      do i=1,6
        do j=1,6
          do ia=1,6
            rtt(i,ia)=rt(i,j)*r(j,ia)+rtt(i,ia)
          end do
        end do
      end do

I'll attach a complete executable testcase that demonstrates the failure.

This testcase, and 200.sixtrack, pass when compiled with these options with GCC
4.4.2 and with trunk r150248 (the last trunk revision before r150301 that
builds on powerpc64-linux).


-- 
           Summary: wrong code for -floop-interchange -ftree-loop-
                    distribution
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: janis at gcc dot gnu dot org
GCC target triplet: powerpc64-linux


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

[Bug tree-optimization/42637] wrong code for -floop-interchange -ftree-loop-distribution

[janis at gcc dot gnu dot org]

------- Comment #1 from janis at gcc dot gnu dot org  2010-01-06 18:27 -------
Created an attachment (id=19488)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19488&action=view)
executable testcase


-- 


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[graphite] wrong code for - |[4.5 Regression][graphite]
                   |floop-interchange -ftree-   |wrong code for -floop-
                   |loop-distribution           |interchange -ftree-loop-
                   |                            |distribution
   Target Milestone|---                         |4.5.0


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[dominiq at lps dot ens dot fr]

------- Comment #2 from dominiq at lps dot ens dot fr  2010-01-06 19:19 -------
The test in comment #1 fails also with "-O2 -floop-block" on
x86_64-apple-darwin10. This pr could be a duplicate of pr42479.


-- 


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #3 from spop at gcc dot gnu dot org  2010-01-14 08:41 -------
Mine.


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |spop at gcc dot gnu dot org
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-01-14 08:41:06
               date|                            |


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #4 from spop at gcc dot gnu dot org  2010-01-15 01:20 -------
The problem here is that the loop invariant motion moves rt(i,j) into
a temporary outside the innermost loop:

   real*8 rt(6,6),r(6,6),rtt(6,6)
      do i=1,6
        do j=1,6
          t = rt(i,j)
          do ia=1,6
            rtt(i,ia)=t*r(j,ia)+rtt(i,ia)
          end do
        end do
      end do

and then we get the cleanup before graphite translating this into an
array:

      do i=1,6
        do j=1,6
          cross_bb[0] = rt(i,j)
          do ia=1,6
            rtt(i,ia)=cross_bb[0]*r(j,ia)+rtt(i,ia)
          end do
        end do
      end do

Then the loop interchange would ask for loop distribution when it
considers the loops 'j' and 'ia', and from the original LST we get:

original_lst (
(root
  0 (loop
    0 (loop
      0 stmt_4
      1 (loop
        0 stmt_5)))))

transformed_lst (
(root
  0 (loop 1
    0 (loop 2
      0 stmt_4)
    1 (loop 3
      0 (loop 4
        0 stmt_5)))))

that is then validated as "legal" by the graphite_legal_transform.

The problem seems to be in the build_lexicographically_gt_constraint
that does not add the information "first instance of stmt_5 is
executed after the last instance of stmt_4 in loop 2".

We would have then a write into cross_bb[0] for all the iterations of
loop 2:

cross_bb[0] = rt(i,0)
cross_bb[0] = rt(i,1)
cross_bb[0] = rt(i,2)
cross_bb[0] = rt(i,3)
cross_bb[0] = rt(i,4)
cross_bb[0] = rt(i,5)

and then only we would read the value of cross_bb[0] in stmt_5:

= cross_bb[0] * ...
= cross_bb[0] * ...
= cross_bb[0] * ...
= cross_bb[0] * ...
= cross_bb[0] * ...
= cross_bb[0] * ...

In the original program we would have had these writes and reads
interleaved like this:

cross_bb[0] = rt(i,0)
= cross_bb[0] * ...
cross_bb[0] = rt(i,1)
= cross_bb[0] * ...
cross_bb[0] = rt(i,2)
= cross_bb[0] * ...
cross_bb[0] = rt(i,3)
= cross_bb[0] * ...
cross_bb[0] = rt(i,4)
= cross_bb[0] * ...
cross_bb[0] = rt(i,5)
= cross_bb[0] * ...

Konrad could you have a look at build_lexicographically_gt_constraint?

Thanks,
Sebastian


-- 


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #5 from spop at gcc dot gnu dot org  2010-01-16 22:17 -------
I have looked again to this function, and I just realized that there
were changes to one of the functions of the data dependence test:
build_pairwise_scheduling_inequality used to build strict inequalities
for the lexicographic comparison, and then Tobias changed it like this:

-    cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
PPL_CONSTRAINT_TYPE_GREATER_THAN); 
+    cstr = build_pairwise_constraint (dim, pos, pos + offset, -1,
+                                     PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
   else
-    cstr = build_pairwise_constraint (dim, pos, pos + offset, 0,
PPL_CONSTRAINT_TYPE_LESS_THAN); 
+    cstr = build_pairwise_constraint (dim, pos, pos + offset, 1,
+                                     PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);


This is wrong.

This change was done when we decided to remove the use of the NNC
(Non-Necessarily Closed) polyhedra into C (Closed) polyhedra, that do
not allow the strict inequalities.  I am working on a fix for this PR.

Sebastian


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|trifunovic at gcc dot gnu   |spop at gcc dot gnu dot org
                   |dot org                     |


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #6 from spop at gcc dot gnu dot org  2010-01-16 22:31 -------
Actually the change by Tobias is correct. 
Still, the problem is around that point.


-- 


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #7 from spop at gcc dot gnu dot org  2010-02-06 07:14 -------
Subject: Bug 42637

Author: spop
Date: Sat Feb  6 07:13:39 2010
New Revision: 156538

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=156538
Log:
Fix PR42637.

2010-02-05  Sebastian Pop  <sebastian.pop@amd.com>
            Konrad Trifunovic  <konrad.trifunovic@inria.fr>

        PR middle-end/42637
        * graphite-dependences.c (build_lexicographical_constraint): Return
        a union of dependence polyhedra.
        (dependence_polyhedron_1): Adapt for build_lexicographical_constraint.

        * testsuite/gcc.dg/graphite/block-0.c: Enable runtime check.  XFAILed.
        * testsuite/gcc.dg/graphite/block-4.c: Same.
        * testsuite/gcc.dg/graphite/block-7.c: Same.
        * testsuite/gcc.dg/graphite/interchange-12.c: Same.
        * testsuite/gcc.dg/graphite/interchange-mvt.c: Same.
        * testsuite/gfortran.dg/graphite/interchange-1.f: XFAILed.
        * testsuite/gfortran.dg/graphite/interchange-3.f90: XFAILed.
        * testsuite/gfortran.dg/graphite/run-id-1.f: New testcase for PR42637.

Added:
    branches/graphite/gcc/testsuite/gfortran.dg/graphite/run-id-1.f
Modified:
    branches/graphite/gcc/ChangeLog.graphite
    branches/graphite/gcc/graphite-dependences.c
    branches/graphite/gcc/testsuite/gcc.dg/graphite/block-0.c
    branches/graphite/gcc/testsuite/gcc.dg/graphite/block-4.c
    branches/graphite/gcc/testsuite/gcc.dg/graphite/block-7.c
    branches/graphite/gcc/testsuite/gcc.dg/graphite/interchange-12.c
    branches/graphite/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
    branches/graphite/gcc/testsuite/gfortran.dg/graphite/interchange-1.f
    branches/graphite/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90


-- 


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #8 from spop at gcc dot gnu dot org  2010-02-06 16:33 -------
*** Bug 42479 has been marked as a duplicate of this bug. ***


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dominiq at lps dot ens dot
                   |                            |fr


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #9 from spop at gcc dot gnu dot org  2010-02-06 16:44 -------
*** Bug 42558 has been marked as a duplicate of this bug. ***


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jv244 at cam dot ac dot uk


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #11 from spop at gcc dot gnu dot org  2010-02-06 17:42 -------
Fixed.


-- 

spop at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/42637] [4.5 Regression][graphite] wrong code for -floop-interchange -ftree-loop-distribution

[spop at gcc dot gnu dot org]

------- Comment #10 from spop at gcc dot gnu dot org  2010-02-06 17:42 -------
Subject: Bug 42637

Author: spop
Date: Sat Feb  6 17:41:54 2010
New Revision: 156552

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=156552
Log:
Fix PR42637.

2010-02-05  Sebastian Pop  <sebastian.pop@amd.com>
            Konrad Trifunovic  <konrad.trifunovic@inria.fr>

        PR middle-end/42637
        * graphite-dependences.c (build_lexicographical_constraint): Return
        a union of dependence polyhedra.
        (dependence_polyhedron_1): Adapt for build_lexicographical_constraint.

        * testsuite/gcc.dg/graphite/block-0.c: Enable runtime check.  XFAILed.
        * testsuite/gcc.dg/graphite/block-4.c: Same.
        * testsuite/gcc.dg/graphite/block-7.c: Same.
        * testsuite/gcc.dg/graphite/interchange-12.c: Same.
        * testsuite/gcc.dg/graphite/interchange-mvt.c: Same.
        * testsuite/gfortran.dg/graphite/interchange-1.f: XFAILed.
        * testsuite/gfortran.dg/graphite/interchange-3.f90: XFAILed.
        * testsuite/gfortran.dg/graphite/run-id-1.f: New testcase for PR42637.

Added:
    trunk/gcc/testsuite/gfortran.dg/graphite/run-id-1.f
Modified:
    trunk/gcc/ChangeLog.graphite
    trunk/gcc/graphite-dependences.c
    trunk/gcc/testsuite/gcc.dg/graphite/block-0.c
    trunk/gcc/testsuite/gcc.dg/graphite/block-4.c
    trunk/gcc/testsuite/gcc.dg/graphite/block-7.c
    trunk/gcc/testsuite/gcc.dg/graphite/interchange-12.c
    trunk/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c
    trunk/gcc/testsuite/gfortran.dg/graphite/interchange-1.f
    trunk/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90


-- 


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