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)
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.
Still valid with: gcc version 4.6.0 20100509 (experimental) (GCC)
I'm working on this (designing an algorithm so far). It is an interesting problem.
> It is an interesting problem. Should not it be handled by the middle-end, possibly with the help of graphite?
(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?
> 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.
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.
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?
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.
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.
> 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.
(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.
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
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.
Fixed with Author: tkoenig Date: Thu Mar 28 21:30:26 2013 New Revision: 197217 URL: http://gcc.gnu.org/viewcvs?rev=197217&root=gcc&view=rev Log: 2013-03-28 Thomas Koenig <tkoenig@gcc.gnu.org> PR fortran/45159 * gfortran.h (gfc_dep_difference): Add prototype. * dependency.c (discard_nops): New function. (gfc_dep_difference): New function. (check_section_vs_section): Use gfc_dep_difference to calculate the difference of starting indices. * trans-expr.c (gfc_conv_substring): Use gfc_dep_difference to calculate the length of substrings where possible. 2013-03-28 Thomas Koenig <tkoenig@gcc.gnu.org> PR fortran/45159 * gfortran.dg/string_length_2.f90: New test. * gfortran.dg/dependency_41.f90: New test. Added: trunk/gcc/testsuite/gfortran.dg/dependency_41.f90 trunk/gcc/testsuite/gfortran.dg/string_length_2.f90 Modified: trunk/gcc/fortran/ChangeLog trunk/gcc/fortran/dependency.c trunk/gcc/fortran/gfortran.h trunk/gcc/fortran/trans-expr.c trunk/gcc/testsuite/ChangeLog