[Bug fortran/36928] New: array temporary for interleaving assignment

[Bug fortran/36928] New: array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

The temporary is not needed in this case.

$ cat foo.f90
program main
  real, dimension(10) :: a
  read (10) a
  a(2:10:2) = a (1:9:2)
end program main
$ gfortran -Warray-temporaries foo.f90
foo.f90:4.14:

  a(2:10:2) = a (1:9:2)
             1
Warning: Creating array temporary at (1)


-- 
           Summary: array temporary for interleaving assignment
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tkoenig at gcc dot gnu dot org


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

[Bug fortran/36928] array temporary for interleaving assignment

[burnus at gcc dot gnu dot org]

------- Comment #1 from burnus at gcc dot gnu dot org  2008-07-25 08:42 -------
See also PR 36915. This is one of the items where the middle-end array
expressions would help (see links in PR 36915). The ME array expr. support is
planned for 4.5.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[jv244 at cam dot ac dot uk]

-- 

jv244 at cam dot ac dot uk changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-11-14 08:26:12
               date|                            |


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

[Bug fortran/36928] array temporary for interleaving assignment

[dfranke at gcc dot gnu dot org]

------- Comment #2 from dfranke at gcc dot gnu dot org  2010-05-09 20:28 -------
Still valid with: gcc version 4.6.0 20100509 (experimental) (GCC)


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #3 from tkoenig at gcc dot gnu dot org  2010-05-15 15:55 -------
I'm working on this (designing an algorithm so far).

It is an interesting problem.


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |tkoenig at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-11-14 08:26:12         |2010-05-15 15:55:58
               date|                            |


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

[Bug fortran/36928] array temporary for interleaving assignment

[dominiq at lps dot ens dot fr]

------- Comment #4 from dominiq at lps dot ens dot fr  2010-05-15 17:05 -------
> It is an interesting problem.

Should not it be handled by the middle-end, possibly with the help of graphite?


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #5 from tkoenig at gcc dot gnu dot org  2010-05-15 17:30 -------
(In reply to comment #4)
> > It is an interesting problem.
> 
> Should not it be handled by the middle-end, possibly with the help of graphite?

If we can improve dependency analysis in the front end, where we (potentially)
have some more information, it should not hurt the middle-end.

OTOH, if somebody is already doing work in this direction, it would be
a waste to duplicate.

So... is any work going on with this?


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[dominiq at lps dot ens dot fr]

------- Comment #6 from dominiq at lps dot ens dot fr  2010-05-15 18:01 -------
> If we can improve dependency analysis in the front end, where we (potentially)
> have some more information, it should not hurt the middle-end.
> 
> OTOH, if somebody is already doing work in this direction, it would be
> a waste to duplicate.
>
> So... is any work going on with this?

I think Paul Thomas has something in his files, but I don't have any pointer at
hand (IIRC along the line a(2:n)=a(1:n-1) replaced with a(n:2:-1)=a(n-1:1:-1)).

I have given some thoughts to the problem a while ago, but did not go further
than the easy cases, such  as the one in the example, are easy;-)  but writing
something general quite difficult. In top of that what is already implemented
is documented only in the code.

I think if you start this problem, it would be worth to look at what is done in
the middle-end (or in graphite) and what can be reused.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[jvdelisle at gcc dot gnu dot org]

------- Comment #7 from jvdelisle at gcc dot gnu dot org  2010-05-15 18:13 -------
I suggest you give a chat to Richard Guenther who seems quite up on the
optimisation aspects of things.  If we are creating a temporary in the front
end I think that would be the least optimal approach.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #8 from tkoenig at gcc dot gnu dot org  2010-05-16 09:00 -------
Richard, what do you think of this?

Does it make sense to do the dependency analysis in the
front end?

Does Graphite (about which I know next to nothing, I admit) have
the necessary infrastructure to detect the dependencies?


-- 

tkoenig at gcc dot gnu dot org changed:

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


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

[Bug fortran/36928] array temporary for interleaving assignment

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2010-05-16 10:30 -------
It makes sense to do this in the frontend.  The worst thing is when the
frontend
creates array temporaries - those are really really hard to get rid of in the
middle-end.

There are basically two (or maybe two and a half) ways to this and similar
problems.

 1) Do as much dependence analysis in the frontend as possible and create the
remaining necessary temporaries there

 2) Delay creation of all temporaries until somewhen in the middle-end

 2.5) Mark the generated temporaries somehow to make them easier accessible
to later middle-end optimizations

I once was working on the necessary infrastructure to do 2) (the so-called
middle-end array expressions).  This work has been pushed back on my
TODO list again and again (and recently I discovered some cases that it
might not be able to handle) - simply due to lack of time (and lack of
knowledge of the Fortran frontend which would be the only (or at least major)
consumer).

I do not think 2.5) is the proper way out of the issue, though probably
it won't hurt (but I didn't think a lot about it nor do I have a proposal
on how to do it).

So I think 1) indeed makes sense.  At the moment the frontend is the only
one that can avoid generating temporaries.

Note that Jakub had the useful suggestion of emitting versioned code from
the frontend.  Basically when the frontend knows that an array temporary
might not be necessary emit two versions of the loop guarded with
a proper runtime condition.  One with and one without temporaries.
This also has the chance that the middle-end will figure out that one
of the cases is not necessary.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #10 from tkoenig at gcc dot gnu dot org  2010-05-22 10:11 -------
I've gotten a bit further with this.

For x(la:ua:sa) = x(lb,ub,sb), there can be no collision

if abs(la-lb) mod gcd(sa, sb) == 0

where gcd is the greatest common divisor.

This will at least fix the test case from comment #1, and also cases like

a(2:x:2) = a(1:y:4).

but will not work in the cases where there is partial overlap only.

Also, it would be nice to have complete simplification so that cases like

a(2*n**2+3*n+1:x:2) = a(2*n**2+3*n:x:2)

can be caught.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[dominiq at lps dot ens dot fr]

------- Comment #11 from dominiq at lps dot ens dot fr  2010-05-22 10:50 -------
> For x(la:ua:sa) = x(lb,ub,sb), there can be no collision
>
> if abs(la-lb) mod gcd(sa, sb) == 0
>
> where gcd is the greatest common divisor.

You probably mean "if abs(la-lb) mod gcd(sa, sb) != 0" (assuming
x(lb:ub:sb);-). Note that if I am not mistaken, this result extends to
multi-dimension arrays: a(1,:) never overlap a(2,:) if the extent of the first
dimension is larger than 1 (or a(1:x:2,:) and a(2:y:2,:) if a(2*n,m)).

> Also, it would be nice to have complete simplification so that cases like
>
> a(2*n**2+3*n+1:x:2) = a(2*n**2+3*n:x:2)
>
> can be caught.

I think you assume that n is unknown at compile time, isn't it? In this case
you need to find in gcc a simplifier for la-lb. Did you have a look to graphite
or did you contact the guys? They may have some answer to this kind of problem.


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #12 from tkoenig at gcc dot gnu dot org  2010-05-22 21:20 -------
(In reply to comment #11)

> You probably mean "if abs(la-lb) mod gcd(sa, sb) != 0" (assuming
> x(lb:ub:sb);-).

Yes, I had this reversed when I wrote this.

Note that if I am not mistaken, this result extends to

> > Also, it would be nice to have complete simplification so that cases like
> >
> > a(2*n**2+3*n+1:x:2) = a(2*n**2+3*n:x:2)
> >
> > can be caught.
> 
> I think you assume that n is unknown at compile time, isn't it? In this case
> you need to find in gcc a simplifier for la-lb. Did you have a look to graphite
> or did you contact the guys? They may have some answer to this kind of problem.

We already have very aggressive simplification operating on trees,
which can do this.  The code in depedency.c operates on gfc_expr
only, and includes a limited simplification for catching stuff
like a(x) vs a(x+1).

Paul, what do you think of the idea of using the tree simplifier
for something like a(2*n**2+3*n:m:2) = a(2*n**2+3n+1:m:2)?
It should be able to calculate the difference of the lower bounds and
find out it is a constant, but maybe some prerequisite isn't there
when dependency checking is done.


-- 

tkoenig at gcc dot gnu dot org changed:

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


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

[Bug fortran/36928] array temporary for interleaving assignment

[tkoenig at gcc dot gnu dot org]

------- Comment #13 from tkoenig at gcc dot gnu dot org  2010-05-31 20:22 -------
Subject: Bug 36928

Author: tkoenig
Date: Mon May 31 20:22:10 2010
New Revision: 160085

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160085
Log:
2010-05-31  Thomas Koenig  <tkoenig@gcc.gnu.org>

        PR fortran/36928
        * dependency.c (gfc_check_section_vs_section):  Check
        for interleaving array assignments without conflicts.

2010-05-31  Thomas Koenig  <tkoenig@gcc.gnu.org>

        PR fortran/36928
        * gfortran.dg/dependency_27.f90:  New test.
        * gfortran.dg/array_assign_1.F90:  New test.


Added:
    trunk/gcc/testsuite/gfortran.dg/array_assignment_1.F90
    trunk/gcc/testsuite/gfortran.dg/dependency_27.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/dependency.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug fortran/36928] array temporary for interleaving assignment with non-constant start values

[tkoenig at gcc dot gnu dot org]

------- Comment #14 from tkoenig at gcc dot gnu dot org  2010-06-01 05:30 -------
Fixed for the constant case.

Still to do, but much harder: A case like

a(n,m,2) = a(n+1,m,2).

Unassigning myself for now.


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|tkoenig at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW
            Summary|array temporary for         |array temporary for
                   |interleaving assignment     |interleaving assignment with
                   |                            |non-constant start values


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