RFC: IPO optimization framework for GCC

RFC: IPO optimization framework for GCC

[Steve Ellcey]

I have been given some time by my management to work on creating a
framework for IPO optimizations in GCC by creating an intermediate file
reader and writer for GCC.

I would like to start by getting any input and advice the members of the
GCC community might have for me.  I would also like to see if I can get
some names of folks who might be interested in helping or advising me on
this project.

My current thought is that if I can get a start made I would create a
branch for this work in CVS and a project page on the GCC Wiki.

In the meantime I would be interested in any opinions people have on
what level we should be writing things out at.  Generic?  Gimple?  RTL?
(Just kidding on that last one.)  Also any opinions on what format to
write things out in; binary form vs. an ascii file, XML?  ANDF?  If you
know of any good papers I should read I would like to hear about those
too.

Steve Ellcey
sje@cup.hp.com

Re: RFC: IPO optimization framework for GCC

[Andrew Pinski]

> 
> I have been given some time by my management to work on creating a
> framework for IPO optimizations in GCC by creating an intermediate file
> reader and writer for GCC.
> 
> I would like to start by getting any input and advice the members of the
> GCC community might have for me.  I would also like to see if I can get
> some names of folks who might be interested in helping or advising me on
> this project.
> 
> My current thought is that if I can get a start made I would create a
> branch for this work in CVS and a project page on the GCC Wiki.
> 
> In the meantime I would be interested in any opinions people have on
> what level we should be writing things out at.  Generic?  Gimple?  RTL?

Generic but you might want to start by trying to define a type
system first.

-- Pinski

Re: RFC: IPO optimization framework for GCC

[Daniel Berlin]

> Generic but you might want to start by trying to define a type
> system first.
> 

Actually, we shouldn't be writing out any of them, at least in their
current form.

(IE it shouldn't be pickled trees)

> -- Pinski

Re: RFC: IPO optimization framework for GCC

[Richard Guenther]

On 10/8/05, Daniel Berlin <dberlin@dberlin.org> wrote:
> > Generic but you might want to start by trying to define a type
> > system first.

Why not gimple?

> Actually, we shouldn't be writing out any of them, at least in their
> current form.
>
> (IE it shouldn't be pickled trees)

Or even dump SSA form, which would make it easier to dump something
different than trees.  But of course, dumping the expressions is easy, dumping
all the extra information in it's current form is a mess.

Richard.

Re: RFC: IPO optimization framework for GCC

[Gabriel Dos Reis]

Daniel Berlin <dberlin@dberlin.org> writes:

| > Generic but you might want to start by trying to define a type
| > system first.
| > 
| 
| Actually, we shouldn't be writing out any of them, at least in their
| current form.
| 
| (IE it shouldn't be pickled trees)

I strongly agree.

-- Gaby

Re: RFC: IPO optimization framework for GCC

[Steven Bosscher]

On Saturday 08 October 2005 01:23, Steve Ellcey wrote:
> I would like to start by getting any input and advice the members of the
> GCC community might have for me.

This may be a totally stupid idea, but perhaps you can start with
writing a new PCH format that is not just a memory dump but a real
dump of the IL, and work from there.  At least that way you have
something you can test your IL reader/writer with right now, and
it buys other folks some time to address some more fundamental
problems blocking real IPA at the moment.

Gr.
Steven

Re: RFC: IPO optimization framework for GCC

[Devang Patel]

On 10/7/05, Steve Ellcey <sje@cup.hp.com> wrote:

[snip]

> In the meantime I would be interested in any opinions people have on
> what level we should be writing things out at.  Generic?  Gimple?  RTL?
> (Just kidding on that last one.)  Also any opinions on what format to
> write things out in; binary form vs. an ascii file, XML?  ANDF?  If you
> know of any good papers I should read I would like to hear about those
> too.

It is useful to get clear understanding of few simpler things before
tackling IL issue.

First question is - What is the user interface ? Few alternatives :

1)  gcc <blah> -fenable-ipo input1.c input2.c input3.c -o output

     Here, writing IL on the disk, and reading it back, and optimizing it,
etc.. are all hidden from users.

2)  gcc <blah> -fwrite-ipo input1.c -o input1.data
     gcc <blah> -fwrite-ipo input2.c -o input2.data
     gcc <blah> -fwrite-ipo input3.c -o input3.data

     gcc <blah> -fread-ipo input1.data input2.data input3.data -o output

3)  gcc <blah> -fwrite-ipo input1.c -o input1.data
     gcc <blah> -fuse-ipo input1.data input2.c -o input2.data
     gcc <blah> -fuse-ipo input2.data input3.c -o output

4)  gcc <blah> -fwrite-ipo input1.c -o input1.data
     gcc <blah> -fwrite-ipo input2.c -o input2.data
     gcc <blah> -fwrite-ipo input3.c -o input3.data

     glo <blah> -fread-ipo input1.data input2.data input3.data -o output

and so on...

Second question is - When to put info on the disk? Few alternatives,
1) Before gimplfication
2) Before optimizing tree-ssa
3) After tree-ssa optimization is complete
4) Immediately after generating RTL
5) Halfway throuh RTL passes
etc.. And answer to this question largely depend on the optimization
passes that work on whole program info.

I do not know whether these two questions are already answered or not.

And finally, reading and writing one or other form of trees (GENERIC,
GIMPLE,...), it is not a show stopper. It can be done as a last resort,
but you want to check all possible alternatives first.

-
Devang

Re: RFC: IPO optimization framework for GCC

[Steve Ellcey]

Thanks to everyone who replied to my mail, I am currently waiting for
some follow-ups to replies I got off-list.  In the mean time I wonder if
we could talk about Devang's questions on what this might look like to
a user.

> From: Devang Patel <devang.patel@gmail.com>
>
> It is useful to get clear understanding of few simpler things before
> tackling IL issue.
> 
> First question is - What is the user interface ? Few alternatives :
> 
> 1)  gcc <blah> -fenable-ipo input1.c input2.c input3.c -o output
> 
>      Here, writing IL on the disk, and reading it back, and optimizing it,
> etc.. are all hidden from users.

But at the cost of having to put all the source compiles on one GCC
command line.  We could probably do this today without reading or
writing anything to disk (as long as we didn't run out of memory).

> 2)  gcc <blah> -fwrite-ipo input1.c -o input1.data
>      gcc <blah> -fwrite-ipo input2.c -o input2.data
>      gcc <blah> -fwrite-ipo input3.c -o input3.data
> 
>      gcc <blah> -fread-ipo input1.data input2.data input3.data -o output
> 
> 3)  gcc <blah> -fwrite-ipo input1.c -o input1.data
>      gcc <blah> -fuse-ipo input1.data input2.c -o input2.data
>      gcc <blah> -fuse-ipo input2.data input3.c -o output
> 
> 4)  gcc <blah> -fwrite-ipo input1.c -o input1.data
>      gcc <blah> -fwrite-ipo input2.c -o input2.data
>      gcc <blah> -fwrite-ipo input3.c -o input3.data
> 
>      glo <blah> -fread-ipo input1.data input2.data input3.data -o output

Could we just have -fwrite-ipo create a '.o' file that contains the
intermediate representation (instead of being a real object file).

Then when the linker is called it would call the compiler with all the
files that have intermediate code instead of object code and finish up
the compilation.  Actually, maybe we could add the restriction that
you have to use GCC to call the linker when doing IPO and that way 
GCC could finish up the compilations before it calls the linker.

> Second question is - When to put info on the disk? Few alternatives,
> 1) Before gimplfication
> 2) Before optimizing tree-ssa
> 3) After tree-ssa optimization is complete
> 4) Immediately after generating RTL
> 5) Halfway throuh RTL passes
> etc.. And answer to this question largely depend on the optimization
> passes that work on whole program info.

I would think one would want to put the info out before optimizing
tree-ssa since you would hope that the IPO data from other modules would
let you do better tree-ssa optimizations.

> I do not know whether these two questions are already answered or not.

I don't think anything has been answered yet.

Steve Ellcey
sje@cup.hp.com

Re: RFC: IPO optimization framework for GCC

[Daniel Berlin]

> > Second question is - When to put info on the disk? Few alternatives,
> > 1) Before gimplfication
> > 2) Before optimizing tree-ssa
> > 3) After tree-ssa optimization is complete
> > 4) Immediately after generating RTL
> > 5) Halfway throuh RTL passes
> > etc.. And answer to this question largely depend on the optimization
> > passes that work on whole program info.
> 
> I would think one would want to put the info out before optimizing
> tree-ssa since you would hope that the IPO data from other modules would
> let you do better tree-ssa optimizations.

Actually, you want to do it right after what the ipa-branch does
early-optimizations.

That will write out a cleaned up IL that has had CCP and DCE run on it.

We discussed almost *all* of this stuff at the summit.
There are people working on detailed plans for IPA (Mark Mitchell and
Ken Zadeck).
You really should email or call them and find out what they are doing.

Re: RFC: IPO optimization framework for GCC

[Diego Novillo]

On Monday 10 October 2005 19:25, Steve Ellcey wrote:

> Could we just have -fwrite-ipo create a '.o' file that contains the
> intermediate representation (instead of being a real object file).
>
> Then when the linker is called it would call the compiler with all the
> files that have intermediate code instead of object code and finish up
> the compilation.  Actually, maybe we could add the restriction that
> you have to use GCC to call the linker when doing IPO and that way
> GCC could finish up the compilations before it calls the linker.
>
That's the model I'm used to, so I would prefer this approach.

> > Second question is - When to put info on the disk? Few alternatives,
> > 1) Before gimplfication
> > 2) Before optimizing tree-ssa
> > 3) After tree-ssa optimization is complete
>
Here.  You want to pick up at a point where you can still do high level 
optimizations.  HLO can be more powerful when done with the whole program 
at hand.  If you stream the IL when you are in RTL, it's too late for 
that.

> I would think one would want to put the info out before optimizing
> tree-ssa since you would hope that the IPO data from other modules would
> let you do better tree-ssa optimizations.
>
Yes, but if you can optimize locally first, you'd be able to write out a 
cleaner IL.

Re: RFC: IPO optimization framework for GCC

[Devang Patel]

On 10/12/05, Diego Novillo <dnovillo@redhat.com> wrote:
> On Monday 10 October 2005 19:25, Steve Ellcey wrote:
>
> > Could we just have -fwrite-ipo create a '.o' file that contains the
> > intermediate representation (instead of being a real object file).
> >
> > Then when the linker is called it would call the compiler with all the
> > files that have intermediate code instead of object code and finish up
> > the compilation.  Actually, maybe we could add the restriction that
> > you have to use GCC to call the linker when doing IPO and that way
> > GCC could finish up the compilations before it calls the linker.
> >
> That's the model I'm used to, so I would prefer this approach.

That is why I used name "glo" to mean gnu linktime optimizer or something
like that. I was raising the issue of whether cc1*, in middle of a compilation,
is expected to read other compilation unit's IL from disk or not. This decision
has big influence on the form of IL being written/read.

-
Devang

Re: RFC: IPO optimization framework for GCC

[Sebastian Pop]

Steve Ellcey wrote:
> 
> In the meantime I would be interested in any opinions people have on
> what level we should be writing things out at.  Generic?  Gimple?  RTL?

Or just dumping plain C code?  This is almost what the pretty printers
are doing, and the way back to the compiler is already there ;-)

Sebastian

Re: RFC: IPO optimization framework for GCC

[Florian Weimer]

* Sebastian Pop:

> Steve Ellcey wrote:
>> 
>> In the meantime I would be interested in any opinions people have on
>> what level we should be writing things out at.  Generic?  Gimple?  RTL?
>
> Or just dumping plain C code?  This is almost what the pretty printers
> are doing, and the way back to the compiler is already there ;-)

Some front ends generate trees which cannot be generated by any C
program.  It might be possible to add some extensions (which would
also help to come up with C test cases for bugs which are currently
exposed by non-C front ends only), and this might even ease concerns
that an ISO C backend might make it possible to use GCC as a library.

But I think it's still better to use some binary serialized IL, just
to discourage external reuse and make clear that it's an internal
format, subject to frequent changes.