Patchwork [fortran] PR 40628, front-end optimization pass

login
register
mail settings
Submitter Thomas Koenig
Date July 17, 2010, 6:38 p.m.
Message ID <1279391905.4628.7.camel@linux-fd1f.site>
Download mbox | patch
Permalink /patch/59148/
State New
Headers show

Comments

Thomas Koenig - July 17, 2010, 6:38 p.m.
Hello world,

finally, here's the first attempt at a front-end optimization pass.
Right now, it fixes PR 40626 and optimizes comparisons between variables
(which only really is relevant for character comparisons).  Many more
things could (and should) be added over time.

This now passes regression-testing for trunk.

OK for trunk?

	Thomas

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

	* Make-lang.in:  Add fortran/optimize.o.
	* gfortran.h:  Add prototype for gfc_optimize_namespace.
	* trans-decl.c (gfc_generate_function_code):  If optimizing,
	call gfc_optimize_namespace.
	* optimize.c:  New file.

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

	* trim_optimize_1.f90:  New test.
	* character_comparision_1.f90:  New test.
Daniel Kraft - July 18, 2010, 8:46 a.m.
Hi Thomas,

Thomas Koenig wrote:
> finally, here's the first attempt at a front-end optimization pass.
> Right now, it fixes PR 40626 and optimizes comparisons between variables
> (which only really is relevant for character comparisons).  Many more
> things could (and should) be added over time.

thinking about this, I'm not really convinced that we want "front-end 
optimization passes".  At least for heavier optimization, at least 
conceptually the middle-end should be responsible.  And for smaller ones 
that are Fortran-specific, we already have the "simplify" code-path.  So 
what do you think are appropriate use-cases for your new optimization pass?

On the other hand, I like the idea of a general high-level 
pass-framework.  I think that this could help in implementing F2003 
features (and co), because I'm not sure the current handling during 
resolution is the best and cleanest (at least not for all constructs). 
I would have liked to add some construct lowering as seperate passes in 
the past, so that it does not interfere with real resolution.

What do you (and others) think about introducing your patch as a general 
pass-framework (and probably not calling it "optimization"), which could 
then both handle construct implementations as well as certain 
optimization passes (if it seems reasonable to implement them that way)?

Yours,
Daniel
Thomas Koenig - July 18, 2010, 10:17 a.m.
Hi Daniel.

> Hi Thomas,
> 
> Thomas Koenig wrote:
> > finally, here's the first attempt at a front-end optimization pass.
> > Right now, it fixes PR 40626 and optimizes comparisons between variables
> > (which only really is relevant for character comparisons).  Many more
> > things could (and should) be added over time.
> 
> thinking about this, I'm not really convinced that we want "front-end 
> optimization passes".  At least for heavier optimization, at least 
> conceptually the middle-end should be responsible.

There are things which are hard for the middle-end to do, especially
character and array expressions.  See, for example, PR 22572 (double
occurrence of matmul not optimized).

> And for smaller ones 
> that are Fortran-specific, we already have the "simplify" code-path.

Simplify is very much geared toward constant simplification.  I made
some attempt at optimization, only to find I would have to modify large
chunks, leading to unnecessary and error-prone changes.

Also, in simplify.c, removing whole statements, adding new variables
etc. is not forseen, also leading to large changes.

Adding a new pass seamed cleaner.  I also wanted the possibility of
making the front-end optimizations

> So 
> what do you think are appropriate use-cases for your new optimization pass?

Things like PR 22572, optimizing expressions like f(x) + f(x) (and warning about
cases where f(x) is non-PURE), optimizing string assignments, PR 30609, ...
A lot of cases where a programmer might be tempted to write "lazy" code
that is currently sub-optimally translated.

> On the other hand, I like the idea of a general high-level 
> pass-framework.  I think that this could help in implementing F2003 
> features (and co), because I'm not sure the current handling during 
> resolution is the best and cleanest (at least not for all constructs). 
> I would have liked to add some construct lowering as seperate passes in 
> the past, so that it does not interfere with real resolution.

That also makes sense.

> What do you (and others) think about introducing your patch as a general 
> pass-framework (and probably not calling it "optimization"), which could 
> then both handle construct implementations as well as certain 
> optimization passes (if it seems reasonable to implement them that way)?

We can use my pass as a starting point, certainly.  Currently, my patch
is run after resolution, but we could certainly set up a general pass
management system.

	Thomas
Jerry DeLisle - July 19, 2010, 4:11 a.m.
On 07/18/2010 01:46 AM, Daniel Kraft wrote:
> Hi Thomas,
>
> Thomas Koenig wrote:
>> finally, here's the first attempt at a front-end optimization pass.
>> Right now, it fixes PR 40626 and optimizes comparisons between variables
>> (which only really is relevant for character comparisons). Many more
>> things could (and should) be added over time.
>

I like the idea as long as we do not duplicate middle-end work. If we can 
improve performance without sacrificing maintainability and correctness, I am 
all for it.  The idea of general passes is good.  Rather than optimize.c maybe 
call it early_pass.c or whatever.

Do any middle-end maintainers have an opinion on adding this optimization?

Jerry
Richard Henderson - July 19, 2010, 6:21 p.m.
On 07/18/2010 09:11 PM, Jerry DeLisle wrote:
> On 07/18/2010 01:46 AM, Daniel Kraft wrote:
>> Hi Thomas,
>>
>> Thomas Koenig wrote:
>>> finally, here's the first attempt at a front-end optimization pass.
>>> Right now, it fixes PR 40626 and optimizes comparisons between variables
>>> (which only really is relevant for character comparisons). Many more
>>> things could (and should) be added over time.
>>
> 
> I like the idea as long as we do not duplicate middle-end work. If we
> can improve performance without sacrificing maintainability and
> correctness, I am all for it.  The idea of general passes is good. 
> Rather than optimize.c maybe call it early_pass.c or whatever.
> 
> Do any middle-end maintainers have an opinion on adding this optimization?

As long as the optimizations here are fortran-specific (e.g. high-level
matrix, string, or loop pre-expansion optimizations), I don't mind.


r~
Toon Moene - July 19, 2010, 6:59 p.m.
Thomas Koenig wrote:

> Hi Daniel.
> 
>> Hi Thomas,
>>
>> Thomas Koenig wrote:
>>> finally, here's the first attempt at a front-end optimization pass.
>>> Right now, it fixes PR 40626 

I have the feeling this isn't the right bug number - because it was 
already closed a year ago.

Which one do you mean ?

[ BTW, as I showed in my GCC-Summit talk in 2007, we already perform
   Fortran specific optimizations in the Front End, so it would be rather
   silly to oppose them from a middle-end perspective :-) ]
Jakub Jelinek - July 19, 2010, 7:08 p.m.
On Sun, Jul 18, 2010 at 09:11:38PM -0700, Jerry DeLisle wrote:
> On 07/18/2010 01:46 AM, Daniel Kraft wrote:
> >Hi Thomas,
> >
> >Thomas Koenig wrote:
> >>finally, here's the first attempt at a front-end optimization pass.
> >>Right now, it fixes PR 40626 and optimizes comparisons between variables
> >>(which only really is relevant for character comparisons). Many more
> >>things could (and should) be added over time.
> >
> 
> I like the idea as long as we do not duplicate middle-end work. If
> we can improve performance without sacrificing maintainability and
> correctness, I am all for it.  The idea of general passes is good.
> Rather than optimize.c maybe call it early_pass.c or whatever.

What I think would be very useful to do in -fwhole-file mode do a pass
through the front-end trees and improve using that slightly e.g.
dependency.c stuff (unless we jump to middle-end arrays, that's an easy way
to get rid e.g. of unnecessary array temporaries).  E.g. in tonto POINTER
vars are ALLOCATED in one routine and not changed afterwards, such vars
could be handled like allocatables.

	Jakub
Thomas Koenig - July 19, 2010, 7:11 p.m.
Am Montag, den 19.07.2010, 20:59 +0200 schrieb Toon Moene:
> Thomas Koenig wrote:
> 
> > Hi Daniel.
> > 
> >> Hi Thomas,
> >>
> >> Thomas Koenig wrote:
> >>> finally, here's the first attempt at a front-end optimization
> pass.
> >>> Right now, it fixes PR 40626 
> 
> I have the feeling this isn't the right bug number - because it was 
> already closed a year ago.

I meant PR 40628, optimizing TRIM away (I got it right in the Subject
line).

	Thomas
Thomas Koenig - July 19, 2010, 10:31 p.m.
Hi Jerry,
> On 07/18/2010 01:46 AM, Daniel Kraft wrote:
> > Hi Thomas,
> >
> > Thomas Koenig wrote:
> >> finally, here's the first attempt at a front-end optimization pass.
> >> Right now, it fixes PR 40626 and optimizes comparisons between variables
> >> (which only really is relevant for character comparisons). Many more
> >> things could (and should) be added over time.
> >
> 
> I like the idea as long as we do not duplicate middle-end work. If we can 
> improve performance without sacrificing maintainability and correctness, I am 
> all for it.  The idea of general passes is good.  Rather than optimize.c maybe 
> call it early_pass.c or whatever.

So, how do we proceed?

I could set up a general pass framework.  This have structs of
containing pointers to functions which handle assignments,
expressions, operators and actual arglists, one for each pass,
and a routine for walking the expressions and invoking the correct
functions.

This would mean one file passes.c (which contains the handle_code and
handle_code_node functions), a passes.h header and a single file (e.g.
pass-optimize.c) for each pass containing the individual functions.

This sounds doable, but will take a bit of time.

Further comments?

Thomas
Jerry DeLisle - July 20, 2010, 1:19 a.m.
On 07/19/2010 03:31 PM, Thomas Koenig wrote:
> Hi Jerry,
>> On 07/18/2010 01:46 AM, Daniel Kraft wrote:
>>> Hi Thomas,
>>>
>>> Thomas Koenig wrote:
>>>> finally, here's the first attempt at a front-end optimization pass.
>>>> Right now, it fixes PR 40626 and optimizes comparisons between variables
>>>> (which only really is relevant for character comparisons). Many more
>>>> things could (and should) be added over time.
>>>
>>
>> I like the idea as long as we do not duplicate middle-end work. If we can
>> improve performance without sacrificing maintainability and correctness, I am
>> all for it.  The idea of general passes is good.  Rather than optimize.c maybe
>> call it early_pass.c or whatever.
>
> So, how do we proceed?
>
> I could set up a general pass framework.  This have structs of
> containing pointers to functions which handle assignments,
> expressions, operators and actual arglists, one for each pass,
> and a routine for walking the expressions and invoking the correct
> functions.
>
> This would mean one file passes.c (which contains the handle_code and
> handle_code_node functions), a passes.h header and a single file (e.g.
> pass-optimize.c) for each pass containing the individual functions.
>
> This sounds doable, but will take a bit of time.
>
> Further comments?
>
> Thomas
>
>

Why not start by just changing the filename optimize.c to passes.c and go with 
what you have now, then this can evolve further with time.

One thing I would like to suggest is can you identify a real world application 
that benefits from this initial optimization pass?  Proof in the pudding so to 
speak, but not strictly necessary.  I am more curious then anything.

Jerry
Steve Kargl - July 20, 2010, 2:08 a.m.
On Mon, Jul 19, 2010 at 06:19:32PM -0700, Jerry DeLisle wrote:
> 
> One thing I would like to suggest is can you identify a real world 
> application that benefits from this initial optimization pass?  Proof in 
> the pudding so to speak, but not strictly necessary.  I am more curious 
> then anything.
> 

See Thomas's recent c.l.f post.

module foo
  implicit none
  integer :: n = 0
contains
  integer function f(k)
    integer, intent(in) :: k
    f = k
    n = n + 1
  end function f
end module foo

program main
  use foo
  implicit none
  print *,f(3) + f(3)
  print *,n
end program main 

An optimizer can replace the 2 function calls in the print 
statement to 'print *, 2*f(3)'.  If the optimizer is really
smart, it can replace it by 'print *, 6'.  The question
then becomes what does 'print *, n' print?  The answer is
that it can print 0, 1, 2, or some other value.  The thread
has been quite interesting.
Diego Novillo - July 20, 2010, 2:39 a.m.
On 10-07-19 21:19 , Jerry DeLisle wrote:

> Why not start by just changing the filename optimize.c to passes.c and
> go with what you have now, then this can evolve further with time.
>
> One thing I would like to suggest is can you identify a real world
> application that benefits from this initial optimization pass? Proof in
> the pudding so to speak, but not strictly necessary. I am more curious
> then anything.

Just so I don't get confused, y'all are talking about adding a general 
pass framework to the fortran FE files, right?

One thing you may want to consider is see how much of the existing pass 
manager framework can be made to share with fortran/*.


Diego.
Jerry DeLisle - July 20, 2010, 2:54 a.m.
On 07/19/2010 07:39 PM, Diego Novillo wrote:
> On 10-07-19 21:19 , Jerry DeLisle wrote:
>
>> Why not start by just changing the filename optimize.c to passes.c and
>> go with what you have now, then this can evolve further with time.
>>
>> One thing I would like to suggest is can you identify a real world
>> application that benefits from this initial optimization pass? Proof in
>> the pudding so to speak, but not strictly necessary. I am more curious
>> then anything.
>
> Just so I don't get confused, y'all are talking about adding a general
> pass framework to the fortran FE files, right?
>

Right!

Jerry
Tobias Burnus - July 20, 2010, 8:05 a.m.
On 07/20/2010 03:19 AM, Jerry DeLisle wrote:
>>>> Thomas Koenig wrote:
>>>>> finally, here's the first attempt at a front-end optimization pass.
>>>>> Right now, it fixes PR 40626 and optimizes comparisons between
>>>>> variables
>>>>> (which only really is relevant for character comparisons). Many more
>>>>> things could (and should) be added over time.
> Why not start by just changing the filename optimize.c to passes.c and
> go with what you have now, then this can evolve further with time.

I concur and I like Jakub's idea. In general, avoiding function calls
(e.g. TRIM()) and avoiding the generation of temporaries helps a lot as
the ME has difficulties to optimize those way while the FE knows the
language constraints and has a more high-level view which facilitates
certain optimizations.

> One thing I would like to suggest is can you identify a real world
> application that benefits from this initial optimization pass?  Proof
> in the pudding so to speak, but not strictly necessary.  I am more
> curious then anything.

That the such code exists and that a real-world spends quite some time
with trim can be seen at the link of the PR. For many Fortran program,
it probably does not help much as the string processing part is small
(though if you go to 10000s of processes, a single-process config read
starts to matter), but in some cases (like memory tracing in this
example), it can matter a lot.

In case of the real-code program linked in the PR, "TRIM(a) == TRIM(b)"
was changed to "a == b" and the commit log was:

" I think I solved the performance hit when running profiling in memory.
The problem is that trim was being called 8 million times for the c60
test, while not being really necessary. So I got rid of it. Now trim is
only called 200 000 times ;)"

Cf. http://www.tddft.org/trac/octopus/changeset/5672  (octopus is an
electronic structure calculation program available under the GPL from
http://tddft.org/ )

Tobias
Daniel Kraft - July 20, 2010, 8:26 a.m.
Tobias Burnus wrote:
> On 07/20/2010 03:19 AM, Jerry DeLisle wrote:
>>>>> Thomas Koenig wrote:
>>>>>> finally, here's the first attempt at a front-end optimization pass.
>>>>>> Right now, it fixes PR 40626 and optimizes comparisons between
>>>>>> variables
>>>>>> (which only really is relevant for character comparisons). Many more
>>>>>> things could (and should) be added over time.
>> Why not start by just changing the filename optimize.c to passes.c and
>> go with what you have now, then this can evolve further with time.
> 
> I concur and I like Jakub's idea. In general, avoiding function calls
> (e.g. TRIM()) and avoiding the generation of temporaries helps a lot as
> the ME has difficulties to optimize those way while the FE knows the
> language constraints and has a more high-level view which facilitates
> certain optimizations.

I just wonder if there is not yet any way to tell the middle-end that it 
is allowed to optimize function calls away (like marking the functions 
"pure" -- according to the c.l.f thread, this should be allowed for all 
Fortran functions (if I understood it correctly)).

I guess this is in principle something Fortran specific right now, but 
the general concept does not seem that specific to me (although it is 
not applicable to C or C++, I guess).

Yours,
Daniel
Toon Moene - July 20, 2010, 9:44 a.m.
Daniel Kraft wrote:

> I just wonder if there is not yet any way to tell the middle-end that it 
> is allowed to optimize function calls away (like marking the functions 
> "pure" -- according to the c.l.f thread, this should be allowed for all 
> Fortran functions (if I understood it correctly)).

No, that's not sufficient, as I argued in my 2007 GCC Summit paper (see 
paragraph 6.3 - you also have to get rid of the temporaries that are 
allocated to hold the function results, which can be quite large (i.e., 
when eliding MATMUL calls).

It is hard to see how the middle end could do this.
Richard Guenther - July 20, 2010, 9:58 a.m.
On Tue, Jul 20, 2010 at 11:44 AM, Toon Moene <toon@moene.org> wrote:
> Daniel Kraft wrote:
>
>> I just wonder if there is not yet any way to tell the middle-end that it
>> is allowed to optimize function calls away (like marking the functions
>> "pure" -- according to the c.l.f thread, this should be allowed for all
>> Fortran functions (if I understood it correctly)).
>
> No, that's not sufficient, as I argued in my 2007 GCC Summit paper (see
> paragraph 6.3 - you also have to get rid of the temporaries that are
> allocated to hold the function results, which can be quite large (i.e., when
> eliding MATMUL calls).
>
> It is hard to see how the middle end could do this.

It generally can't if it doesn't know that MATMUL is MATMUL.
Middle-end arrays would help, but they keep being below the top
of my TODO list ;)

Richard.

Patch

Index: Make-lang.in
===================================================================
--- Make-lang.in	(Revision 161930)
+++ Make-lang.in	(Arbeitskopie)
@@ -66,7 +66,7 @@ 
     fortran/trans.o fortran/trans-array.o fortran/trans-common.o \
     fortran/trans-const.o fortran/trans-decl.o fortran/trans-expr.o \
     fortran/trans-intrinsic.o fortran/trans-io.o fortran/trans-openmp.o \
-    fortran/trans-stmt.o fortran/trans-types.o
+    fortran/trans-stmt.o fortran/trans-types.o fortran/optimize.o
 
 fortran_OBJS = $(F95_OBJS) gfortranspec.o
 
Index: gfortran.h
===================================================================
--- gfortran.h	(Revision 161930)
+++ gfortran.h	(Arbeitskopie)
@@ -2828,4 +2828,8 @@ 
 
 #define CLASS_DATA(sym) sym->ts.u.derived->components
 
+/* optimize.c */
+
+void gfc_optimize_namespace (gfc_namespace *);
+
 #endif /* GCC_GFORTRAN_H  */
Index: trans-decl.c
===================================================================
--- trans-decl.c	(Revision 161930)
+++ trans-decl.c	(Arbeitskopie)
@@ -4374,6 +4374,9 @@ 
   int rank;
   bool is_recursive;
 
+  if (optimize)
+    gfc_optimize_namespace (ns);
+
   sym = ns->proc_name;
 
   /* Check that the frontend isn't still using this.  */