[Bug fortran/31711] New: Data parallell code

[Bug fortran/31711] New: Data parallell code

[thobes at gmail dot com]

-- 
           Summary: Data parallell code
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: thobes at gmail dot com


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

[Bug fortran/31711] Data parallel code gets transformed to serial

[thobes at gmail dot com]

------- Comment #1 from thobes at gmail dot com  2007-04-26 10:56 -------
Created an attachment (id=13447)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13447&action=view)
Example of code that fails.

This program is an example of something that should produce a file where the
second column should mostly have the value 0.25 as it does with g95. However
that is not the case with gfortran.


-- 


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

[Bug fortran/31711] Data parallel code gets transformed to serial

[thobes at gmail dot com]

------- Comment #2 from thobes at gmail dot com  2007-04-26 10:58 -------
Data parallel vector operations doesn't seem to get computed correctly in all 
cases. Simple cases such as:

program test

  integer,dimension(0:9)     :: T
  integer                    :: i

  T(0:9) = 0
  T(0) = 1

  T(1:9) = T(1:9) + T(0:8)

  do i=0,9
     write(unit=*,fmt=*) 'T(',i,') = ', T(i)
  end do

end program test

seem to work, but more complex ones does not (see attached file).

This has been tested on a x86 MacBook.


-- 

thobes at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thobes at gmail dot com


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

[Bug fortran/31711] Data parallel code gets transformed to serial

[burnus at gcc dot gnu dot org]

------- Comment #3 from burnus at gcc dot gnu dot org  2007-04-26 16:04 -------
This is with which version of gfortran (use gfortran -v)?
Which options are you using?

I get here (x86-64 Linux) the same result with gfortran 4.3, 4.1.2, g95, ifort,
NAG f95:

$ gfortran -O3 -ftree-vectorize -march=opteron -funroll-loops -ffast-math
xxx.f90
$ ./a.out
 Time:   0.000000     Number of Iterations:           2
 Temperature of element T(1,1)  =  0.250000000000000


-- 


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

[Bug fortran/31711] Data parallel code gets transformed to serial

[thobes at gmail dot com]

------- Comment #4 from thobes at gmail dot com  2007-04-26 17:21 -------
$ gfortran -v
Using built-in specs.
Target: i386-apple-darwin8.8.1
Configured with: /tmp/gfortran-20070415/ibin/../gcc/configure
--prefix=/usr/local/gfortran --enable-languages=c,fortran
--with-gmp=/tmp/gfortran-20070415/gfortran_libs --enable-bootstrap
Thread model: posix
gcc version 4.3.0 20070415 (experimental)

Please note that T(1,1) will be correct. T(1,2) however, will not. This can be
seen in the file (result.dat) generated by the program.


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[burnus at gcc dot gnu dot org]

------- Comment #5 from burnus at gcc dot gnu dot org  2007-04-26 20:50 -------
> This can be seen in the file (result.dat) generated by the program.

I missed that part. Reduced test:

program laplsolv
  IMPLICIT NONE
  integer, parameter                  :: n=10
  double precision,dimension(0:n+1,0:n+1) :: T
  double precision,dimension(n)       :: tmp1,tmp2
  integer                             :: i

  T=0.0
  T(0:n+1 , 0)     = 1.0
  T(0:n+1 , n+1)   = 1.0
  T(n+1   , 0:n+1) = 2.0

  tmp1=T(1:n,0)
  T(1:n,1)=(T(0:n-1,1)+T(1:n,1+1)+tmp1)

  do i = 1, n
    print '(20f4.1)', T(i,1)
  end do
end program laplsolv

The "T(1:n,1)=(T(0:n-1,1)+T(1:n,1+1)+tmp1)" get wrongly translated as:

  {
    int8 S.4;
    S.4 = 1;
    while (1)
      {
        if (S.4 > 10) goto L.5;
        t[S.4 + 12] = (t[S.4 + 11] + t[S.4 + 24]) + tmp1[S.4 + -1];
        S.4 = S.4 + 1;
      }
    L.5:;
  }

It should be something like:
  for(int i = 1; i < 10; i++) {
    t.1[i + 12 ] = (t[S.4 + 11] + t[S.4 + 24]) + tmp1[S.4 + -1];
  for(int i = 1; i < 10; i++) {
    t[i + 12] = t.1[i + 12]

That is: First the right-hand side needs to be evaluated before the lhs is
written.


-- 

burnus at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |burnus at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2007-04-26 20:50:32
               date|                            |
            Summary|Data parallel code gets     |rhs array is changed while
                   |transformed to serial       |assiging to same lhs array


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[tkoenig at gcc dot gnu dot org]

------- Comment #6 from tkoenig at gcc dot gnu dot org  2007-04-26 21:31 -------
Nasty.

Paul, I've added you to the CC list because you probably
know more about the scalarizer than most.  Just in case :-)

Thomas


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pault at gcc dot gnu dot
                   |                            |org, tkoenig at gcc dot gnu
                   |                            |dot org


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[paulthomas2 at wanadoo dot fr]

------- Comment #7 from paulthomas2 at wanadoo dot fr  2007-04-26 23:04 -------
Subject: Re:  rhs array is changed while assiging to same
 lhs array

Thomas,

It's some trivial failure of the logic in gfc_dep_resolver.  I took a 
quick look but did not see it because I am totally exhausted.  I'll come 
back to it at the weekend if you do not beat me to it.  Another person 
that might see it right away is Roger Sayle.

Best regards

Paul


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[tkoenig at gcc dot gnu dot org]

------- Comment #8 from tkoenig at gcc dot gnu dot org  2007-04-27 07:01 -------
Hi Roger,

I'm adding you to the CC list on this PR on Paul T.'s
suggestion.  You are one of our dependency experts, so
maybe you can do something about this :-)

Thomas


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |roger at eyesopen dot com


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[pault at gcc dot gnu dot org]

------- Comment #9 from pault at gcc dot gnu dot org  2007-04-27 17:27 -------
(In reply to comment #8)
The patch below seems too simple to be true - it fixes the problem, I guess it
will regtest but we will have to see what it does to performance.  If you look
at it, it is potentially rather horrifying; cf 4.2.0

Paul

Index: gcc/fortran/trans-array.c
===================================================================
*** gcc/fortran/trans-array.c   (revision 124192)
--- gcc/fortran/trans-array.c   (working copy)
*************** gfc_conv_resolve_dependencies (gfc_loopi
*** 3000,3006 ****
          lref = dest->expr->ref;
          rref = ss->expr->ref;

!         nDepend = gfc_dep_resolver (lref, rref);
  #if 0
          /* TODO : loop shifting.  */
          if (nDepend == 1)
--- 3000,3006 ----
          lref = dest->expr->ref;
          rref = ss->expr->ref;

!         nDepend |= gfc_dep_resolver (lref, rref);
  #if 0
          /* TODO : loop shifting.  */
          if (nDepend == 1)


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pault at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-04-26 20:50:32         |2007-04-27 17:27:20
               date|                            |


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[roger at eyesopen dot com]

------- Comment #10 from roger at eyesopen dot com  2007-04-27 18:20 -------
Paul's fix looks correct to me.  It appears that when the "#if 0" was added
to disable broken loop shifting at some point in the distant past, the critical
functionality.

  if (nDepend)
    break;

was accidentally removed.  This is similar to the idiom used a few lines
earlier "nDepend = 1;  break;"


I would normally have suggested that the type of nDepend and the return type of
gfc_dep_resolver be changed to bool, and the dead "#if 0" code removed to
clean-up this code...

However, I think a much better longer term strategy is to completely remove
gfc_conv_resolve_dependencies, and gfc_dep_resolver and the automatic handling
of temporaries in the scalarizer.  Instead, in line with the TODO above
gfc_conv_resolve_dependencies, I think it's much better to handle this at a
higher level using the new/preferred gfc_check_dependency API that's used
through-out the front-end.

For example, when lhs=rhs has a dependency, this can be transformed into
"tmp=rhs; lhs=tmp" during lowering or at the front-end tree-level, which
greatly simplifies the complex code in the scalarizer.  It also allows the
post-assignment copy "lhs=tmp" to be performed efficiently [though I may have
already implemented that in the scalarizer already :-)].

One benefit of doing this at a higher level of abstraction is that
loop-reversal isn't a simple matter of running our default scalarized loop
backwards (as hinted by the comment, and the PRs in bugzilla).  Consider the
general case of a(s1:e1,s2:e2,s3:e3) = rhs.  The dependency analysis in
gfc_check_dependency may show that s1:e1 needs to run forwards to avoid a
conflict, and that s3:e3 needs to run backwards for the same reason.  It's
trivial then to treat this almost like a source-to-source transformation (ala
KAP) and convert the assignment into a(s1:e1:1,s2:e2,s3:e3:-1) instead of
attempting to shoehorn all this into the scalarizer at a low-level and perform
book-keeping on the direction vectors.  By the time, we've lowered gfc_expr to
gfc_ss, we've made things much harder for ourselves.  And things get much more
complex once we start seriously tackling CSHIFT, TRANSPOSE and friends!

Keeping the scalarizer simple also eases support for autovectorization and/or
moving it into the middle-end (the topic of Toon's GCC summit presentation).

I'm as surprised as Paul that this hasn't been a problem before.  I suspect
it's because we use the alternate gfc_check_dependency in the vast majority of
cases, and the empirical observation in the research literature that most f90
array assignments in real code don't carry a dependency.

Roger
--


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[steven at gcc dot gnu dot org]

------- Comment #11 from steven at gcc dot gnu dot org  2007-04-28 21:32 -------
Can this go into gcc 4.2?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |steven at gcc dot gnu dot
                   |                            |org


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[pault at gcc dot gnu dot org]

------- Comment #12 from pault at gcc dot gnu dot org  2007-04-29 06:10 -------
Subject: Bug 31711

Author: pault
Date: Sun Apr 29 06:10:22 2007
New Revision: 124269

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=124269
Log:
2007-04-29  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/31711
        * trans-array.c (gfc_conv_resolve_dependencies): Create a temp
        whenever a dependency is found.

2007-04-29  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/31711
        * gfortran.dg/dependency_21.f90: New test.

Added:
    trunk/gcc/testsuite/gfortran.dg/dependency_21.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/trans-array.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[pault at gcc dot gnu dot org]

------- Comment #13 from pault at gcc dot gnu dot org  2007-04-29 06:31 -------
(In reply to comment #11)
> Can this go into gcc 4.2?
> 
Steven, It's not strictly a regression.  Mark is on vacation right now, so I
cannot get a yeah or nay from him.  By popular acclaim, I have decided to
declare it as being so bad that it should be treated as a regression and to
commit it this morning (it's just now regtesting on 4.2).

Paul


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[pault at gcc dot gnu dot org]

------- Comment #14 from pault at gcc dot gnu dot org  2007-04-29 07:16 -------
Subject: Bug 31711

Author: pault
Date: Sun Apr 29 07:16:45 2007
New Revision: 124270

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=124270
Log:
2007-04-29  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/31711
        * trans-array.c (gfc_conv_resolve_dependencies): Create a temp
        whenever a dependency is found.

2007-04-29  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/31711
        * gfortran.dg/dependency_21.f90: New test.

Added:
    branches/gcc-4_2-branch/gcc/testsuite/gfortran.dg/dependency_21.f90
Modified:
    branches/gcc-4_2-branch/gcc/fortran/ChangeLog
    branches/gcc-4_2-branch/gcc/fortran/trans-array.c
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug fortran/31711] rhs array is changed while assiging to same lhs array

[pault at gcc dot gnu dot org]

------- Comment #15 from pault at gcc dot gnu dot org  2007-04-29 07:20 -------
I have changed the designation of this PR to normal/missed-optization, so that
comment #10 from Roger-Sayle is kept "live".

Otherwise this is fixed on trunk and 4.2.

Paul 


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal
           Keywords|wrong-code                  |missed-optimization


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

[Bug fortran/31711] was "rhs array is changed while assiging to same lhs array"

[pault at gcc dot gnu dot org]

------- Comment #16 from pault at gcc dot gnu dot org  2007-08-20 07:16 -------
comment #10 from Roger-Sayle is being kept "live" by this PR.  Whilst I am
interested, I have to give priority to other PRs to make best use of my limited
time.  I may yet come back to it....

Paul


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pault at gcc dot gnu dot org|unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW
            Summary|rhs array is changed while  |was "rhs array is changed
                   |assiging to same lhs array  |while assiging to same lhs
                   |                            |array"


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

[Bug fortran/31711] was "rhs array is changed while assiging to same lhs array"

[tkoenig at gcc dot gnu dot org]

------- Comment #17 from tkoenig at gcc dot gnu dot org  2007-08-26 11:24 -------
Changing severity to enhancement.


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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