[Bug fortran/56937] New: Unnecessarily temporary with array-vector assignments

[Bug fortran/56937] New: Unnecessarily temporary with array-vector assignments

[burnus at gcc dot gnu.org]

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

             Bug #: 56937
           Summary: Unnecessarily temporary with array-vector assignments
    Classification: Unclassified
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: fortran
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: burnus@gcc.gnu.org


For assignments of the form

   array(vec_idx) = array(vec_idx) + nonaliasing_expr

no temporary should be generated.

In other words, the following program should print "1.0" and not "0.5". It
prints "1.0" with PGI and Intel (which do this optimization) and prints "0.5"
with pathf95, g95, gfortran and NAG, which don't:

real :: r(4), p(4)
integer :: idx(4)
p = [0.25, 0.25, 0.25, 0.25]
idx = [2,2,3,2]
r = 0
r(idx) = r(idx) + p
print *, sum(r)
end

The reason for the value is that gfortran (et al.) create a temporary and use:
  tmp(2) = r(1) + 0.25  ! r(1:4) == 0
  tmp(2) = r(2) + 0.25
  tmp(3) = r(3) + 0.25
  tmp(2) = r(4) + 0.25
  r(2) = tmp(2)         ! = 0.25
  r(2) = tmp(2)         ! = 0.25
  r(3) = tmp(3)         ! = 0.25
  r(2) = tmp(2)         ! = 0.25
-> sum(r) = 0.5

Without temporary one gets:
  r(2) = 0 + 0.25
  r(2) = (0.25) + 0.25
  r(3) = 0 + 0.25
  r(4) = (0.75) + 0.25
-> sum(r) = 1.0


The reason that the optimization is valid is given by the following restriction
in the Fortran standard:

"If a vector subscript has two or more elements with the same value, an array
section with that vector subscript shall not appear in a variable definition
context (16.6.7)."   (Fortran 2008, 6.5.3.3.2 Vector subscript, paragraph 3)

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[dominiq at lps dot ens.fr]

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

--- Comment #1 from Dominique d'Humieres <dominiq at lps dot ens.fr> 2013-04-12 20:56:36 UTC ---
Is the following code valid?

integer :: i, idx(4), r(4), p(4)
p = [1,2,3,4]
idx = [2,2,2,2]
r = 0
r(idx) = p
print *, sum(r)
r = 0
do i = 1, 4
  r(idx(i)) = p(i)
end do
print *, sum(r)
r = 0
do i = 4, 1, -1
  r(idx(i)) = p(i)
end do
print *, sum(r)

end

The output is

           4
           4
           1

i.e., the value of r(2) depends on the way the assignment is scalarized: my
rule of thumb for missing temporary and/or invalid code.

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[burnus at gcc dot gnu.org]

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

Tobias Burnus <burnus at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |burnus at gcc dot gnu.org

--- Comment #2 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-04-12 21:28:53 UTC ---
(In reply to comment #1)
> Is the following code valid?
...
> idx = [2,2,2,2]
> r(idx) = p
...

I think it is valid - except for "r(idx) = p" which is invalid. See F2008 quote
at the bottom of comment 0 for the reason.

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[mikael at gcc dot gnu.org]

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

Mikael Morin <mikael at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikael at gcc dot gnu.org

--- Comment #3 from Mikael Morin <mikael at gcc dot gnu.org> 2013-04-13 10:15:03 UTC ---
(In reply to comment #0)
> In other words, the following program should print "1.0" and not "0.5". 

Technically, the program is invalid (for the reason you quote), so there isn't 
any valid result.

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[mikael at gcc dot gnu.org]

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

--- Comment #4 from Mikael Morin <mikael at gcc dot gnu.org> 2013-04-13 10:26:05 UTC ---
The following variant is valid, and gives 1.0 as expected.
But it doesn't avoid the temporary either.


real :: r(4), p(4)
integer :: idx(4)
p = [0.25, 0.25, 0.25, 0.25]
idx = [4,2,3,1]
r = 0
r(idx) = r(idx) + p
print *, sum(r)
end

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[mikael at gcc dot gnu.org]

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

--- Comment #5 from Mikael Morin <mikael at gcc dot gnu.org> 2013-04-13 10:32:46 UTC ---
(In reply to comment #0)
>   tmp(2) = r(1) + 0.25  ! r(1:4) == 0
>   tmp(2) = r(2) + 0.25
>   tmp(3) = r(3) + 0.25
>   tmp(2) = r(4) + 0.25
>   r(2) = tmp(2)         ! = 0.25
>   r(2) = tmp(2)         ! = 0.25
>   r(3) = tmp(3)         ! = 0.25
>   r(2) = tmp(2)         ! = 0.25
> -> sum(r) = 0.5
> 

By the way, it's rather:
   tmp(1) = r(2) + 0.25  ! r(1:4) == 0
   tmp(2) = r(2) + 0.25
   tmp(3) = r(3) + 0.25
   tmp(4) = r(2) + 0.25
   r(2) = tmp(1)         ! = 0.25
   r(2) = tmp(2)         ! = 0.25
   r(3) = tmp(3)         ! = 0.25
   r(2) = tmp(4)         ! = 0.25
-> sum(r) = 0.5

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[dominiq at lps dot ens.fr]

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

Dominique d'Humieres <dominiq at lps dot ens.fr> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-04-29
     Ever Confirmed|0                           |1

--- Comment #6 from Dominique d'Humieres <dominiq at lps dot ens.fr> 2013-04-29 22:26:20 UTC ---
Apparently there is no dependency analysis for array-vector assignments. The
following test create a temporary that is not needed

integer :: r(10), idx(4), jdx(4)
r = [(i+10,i=1,10)]
idx = [1, 2, 3, 4]
jdx = [6, 7, 8, 9]
r(idx) = r(jdx)
print *, r
end

r(idx) = r(jdx)
         1
Warning: Creating array temporary at (1)

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

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

--- Comment #7 from Thomas Koenig <tkoenig at gcc dot gnu.org> 2013-04-30 11:58:43 UTC ---
(In reply to comment #6)
> Apparently there is no dependency analysis for array-vector assignments.

Correct, however...

> The
> following test create a temporary that is not needed
> 
> integer :: r(10), idx(4), jdx(4)
> r = [(i+10,i=1,10)]
> idx = [1, 2, 3, 4]
> jdx = [6, 7, 8, 9]
> r(idx) = r(jdx)
> print *, r
> end
> 
> r(idx) = r(jdx)
>          1
> Warning: Creating array temporary at (1)

Currently, we do not support assigning values to variables
and then later using the values for dependency analysis.

This would require forward propagation of values, which we
don't do in the front end.  Plus, a lot of dependency test cases
where we used variables to hide them from the optimization would
start failing ;-)

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[dominiq at lps dot ens.fr]

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

--- Comment #8 from Dominique d'Humieres <dominiq at lps dot ens.fr> 2013-04-30 12:15:00 UTC ---
> Currently, we do not support assigning values to variables
> and then later using the values for dependency analysis.
> ...

What about

integer :: r(10)
r = [(i+10,i=1,10)]
r([1, 2, 3, 4]) = r([6, 7, 8, 9])
print *, r
end

r([1, 2, 3, 4]) = r([6, 7, 8, 9])
                  1
Warning: Creating array temporary at (1)

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[burnus at gcc dot gnu.org]

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

--- Comment #9 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-04-30 12:35:49 UTC ---
(In reply to comment #8)
> > Currently, we do not support assigning values to variables
> > and then later using the values for dependency analysis.
> > ...

Well, as I wrote in comment 0: For assignments of the form

   array(vec_idx) = array(vec_idx) + nonaliasing_expr

no temporary should be generated.

Namely: Both sides have the same vector_idx expression. The test case in
comment 0 is based on a real world test case which exactly uses one array
variable as index.

I think one could walk the an array constructor, but my feeling is that a
constructor is not the most common usage case in a real-world code. Thus, that
has lower priority.

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[tkoenig at gcc dot gnu.org]

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

--- Comment #10 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
Author: tkoenig
Date: Sun Jul 21 13:44:03 2013
New Revision: 201094

URL: http://gcc.gnu.org/viewcvs?rev=201094&root=gcc&view=rev
Log:
2013-07-21  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/56937
    * dependency.c (gfc_dep_resolver):  Treat identical
    array subscripts as identical; don't unconditionally
    return a dependency if an array subscript is found.

2013-07-21  Thomas Koenig  <tkoenig@gcc.gnu.org>

    PR fortran/56937
    * gfortran.dg/dependency_42.f90:  New test.
    * gfortran.dg/dependency_43.f90:  New test.


Added:
    trunk/gcc/testsuite/gfortran.dg/dependency_42.f90
    trunk/gcc/testsuite/gfortran.dg/dependency_43.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/dependency.c
    trunk/gcc/testsuite/ChangeLog

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |tkoenig at gcc dot gnu.org

--- Comment #11 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
A big part is fixed now.

Do people think that the case of comment#8 is worth fixing?

[Bug fortran/56937] Unnecessarily temporary with array-vector assignments

[tkoenig at gcc dot gnu.org]

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

Thomas Koenig <tkoenig at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
           Assignee|tkoenig at gcc dot gnu.org         |unassigned at gcc dot gnu.org

--- Comment #13 from Thomas Koenig <tkoenig at gcc dot gnu.org> ---
A big part is fixed, unassigning myself for the rest (for now).