[Bug tree-optimization/41811] New: graphite miscompiles 454.calculix of the SPEC 2k6

[Bug tree-optimization/41811] New: graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

The kernel that is miscompiled is in shape20h.f and it looks like this:

      do i=1,3
        do j=1,3
          xs(i,j)=0.d0
          do k=1,20
            xs(i,j)=xs(i,j)+xl(i,k)*shp(j,k)
          enddo
        enddo
      enddo

There is an interchange of the j and k loops that is applied to the
kernel.  The statement induction variable order is interchanged for
scat_5 and scat_3, as in S5(scat_1,scat_5,scat_3).  The code generated
by CLooG looks like this:

for (scat_1=0;scat_1<=2;scat_1++) {
  S3(scat_1) ;
  for (scat_3=0;scat_3<=1;scat_3++) {
    S4(scat_1,scat_3) ;
    for (scat_5=0;scat_5<=2;scat_5++) {
      S5(scat_1,scat_5,scat_3) ;
      S6(scat_1,scat_5,scat_3) ;
    }
    S7(scat_1,scat_3) ;
    S26(scat_1,scat_3) ;
    S8(scat_1,scat_3) ;
  }
  S4(scat_1,2) ;
  for (scat_5=0;scat_5<=2;scat_5++) {
    S5(scat_1,scat_5,2) ;
    S6(scat_1,scat_5,2) ;
  }
  S7(scat_1,2) ;
  S26(scat_1,2) ;
  for (scat_3=3;scat_3<=18;scat_3++) {
    for (scat_5=0;scat_5<=2;scat_5++) {
      S5(scat_1,scat_5,scat_3) ;
      S6(scat_1,scat_5,scat_3) ;
    }
  }
  for (scat_5=0;scat_5<=2;scat_5++) {
    S5(scat_1,scat_5,19) ;
  }
}


-- 
           Summary: graphite miscompiles 454.calculix of the SPEC 2k6
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: spop at gcc dot gnu dot org
        ReportedBy: spop at gcc dot gnu dot org


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-10-23 18:02:33
               date|                            |


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

------- Comment #1 from spop at gcc dot gnu dot org  2009-10-23 18:16 -------
The bug disappears with disabling the loop interchange, but the code
generated by CLooG still looks strange:

for (scat_1=0;scat_1<=2;scat_1++) {
  S3(scat_1) ;
  for (scat_3=0;scat_3<=1;scat_3++) {
    S4(scat_1,scat_3) ;
    for (scat_5=0;scat_5<=18;scat_5++) {
      S5(scat_1,scat_3,scat_5) ;
      S6(scat_1,scat_3,scat_5) ;
    }
    S5(scat_1,scat_3,19) ;
    S7(scat_1,scat_3) ;
    S26(scat_1,scat_3) ;
    S8(scat_1,scat_3) ;
  }
  S4(scat_1,2) ;
  for (scat_5=0;scat_5<=18;scat_5++) {
    S5(scat_1,2,scat_5) ;
    S6(scat_1,2,scat_5) ;
  }
  S5(scat_1,2,19) ;
  S7(scat_1,2) ;
  S26(scat_1,2) ;
}

given that the original and transformed Loop Statement Trees look like
this:

original_lst (
(root
  0 (loop
    0 stmt_3
    1 (loop
      0 stmt_4
      1 (loop
        0 stmt_5
        1 stmt_6)
      2 stmt_7
      3 stmt_26
      4 stmt_8))))

transformed_lst (
(root
  0 (loop
    0 stmt_3
    1 (loop
      0 stmt_4
      1 (loop
        0 stmt_5
        1 stmt_6)
      2 stmt_7
      3 stmt_26
      4 stmt_8))))


-- 


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

------- Comment #2 from spop at gcc dot gnu dot org  2009-10-23 19:43 -------
With -fno-loop-interchange the code generated is correct but strange as the
statement
S8(scat_1,scat_3) ;
does iterate one less time than the other statements of loop scat_3.


-- 


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

------- Comment #3 from spop at gcc dot gnu dot org  2009-10-23 19:46 -------
Also with -O3 the code of the loop body looks much nicer: several statements
disappear as they do not contain code anymore:  so we have this LST 

transformed_lst (
(root
  0 (loop
    0 (loop
      0 stmt_4
      1 (loop
        0 stmt_5)
      2 stmt_7
      3 stmt_18))))

and the code generated by CLooG for the interchange looks like this: 

for (scat_1=0;scat_1<=2;scat_1++) {
  for (scat_3=0;scat_3<=2;scat_3++) {
    S4(scat_1,scat_3) ;
    for (scat_5=0;scat_5<=2;scat_5++) {
      S5(scat_1,scat_5,scat_3) ;
    }
    S7(scat_1,scat_3) ;
    S18(scat_1,scat_3) ;
  }
  for (scat_3=3;scat_3<=19;scat_3++) {
    for (scat_5=0;scat_5<=2;scat_5++) {
      S5(scat_1,scat_5,scat_3) ;
    }
  }
}


-- 


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

Re: [Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[Sebastian Pop]

On Fri, Oct 23, 2009 at 14:46, spop at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
> and the code generated by CLooG for the interchange looks like this:
>
> for (scat_1=0;scat_1<=2;scat_1++) {
>  for (scat_3=0;scat_3<=2;scat_3++) {
>    S4(scat_1,scat_3) ;
>    for (scat_5=0;scat_5<=2;scat_5++) {
>      S5(scat_1,scat_5,scat_3) ;
>    }
>    S7(scat_1,scat_3) ;
>    S18(scat_1,scat_3) ;
>  }

S7 and S18 should not be generated before S5 finishes to execute over
all the iterations of the original innermost loop (do k=1,20).

S7 and S18 contain the end of the reduction and the write in the array
xs(i,j) that is independent of the k loop.

>  for (scat_3=3;scat_3<=19;scat_3++) {
>    for (scat_5=0;scat_5<=2;scat_5++) {
>      S5(scat_1,scat_5,scat_3) ;
>    }
>  }
> }

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[sebpop at gmail dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1068 bytes --]



------- Comment #4 from sebpop at gmail dot com  2009-10-23 19:54 -------
Subject: Re:  graphite miscompiles 454.calculix 
        of the SPEC 2k6

On Fri, Oct 23, 2009 at 14:46, spop at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
> and the code generated by CLooG for the interchange looks like this:
>
> for (scat_1=0;scat_1<=2;scat_1++) {
>  for (scat_3=0;scat_3<=2;scat_3++) {
>    S4(scat_1,scat_3) ;
>    for (scat_5=0;scat_5<=2;scat_5++) {
>      S5(scat_1,scat_5,scat_3) ;
>    }
>    S7(scat_1,scat_3) ;
>    S18(scat_1,scat_3) ;
>  }

S7 and S18 should not be generated before S5 finishes to execute over
all the iterations of the original innermost loop (do k=1,20).

S7 and S18 contain the end of the reduction and the write in the array
xs(i,j) that is independent of the k loop.

>  for (scat_3=3;scat_3<=19;scat_3++) {
>    for (scat_5=0;scat_5<=2;scat_5++) {
>      S5(scat_1,scat_5,scat_3) ;
>    }
>  }
> }


-- 


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

------- Comment #5 from spop at gcc dot gnu dot org  2009-10-23 20:52 -------
The data dependence analysis is not instructed that the iteration
domain of the k loop will be splitted, and thus it answers
"interchanging stmt_5 is a correct transform".

To correct this problem we have to distribute the loop such that we
will ask the question "is it legal to transform the loops to be
interchanged around stmt_5 in a perfect loop nest"?


-- 


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

[Bug tree-optimization/41811] graphite miscompiles 454.calculix of the SPEC 2k6

[spop at gcc dot gnu dot org]

------- Comment #6 from spop at gcc dot gnu dot org  2009-11-03 05:57 -------
Fixed in the graphite branch as explained above.


-- 

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=41811