[RFC] WHOPR - A whole program optimizer framework for GCC

[RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

Over the last few weeks we (Google) have been discussing ideas on how to
leverage the LTO work to implement a whole program optimizer that is
both fast and scalable.

While we do not have everything thought out in detail, we think we have
enough to start doing some implementation work.  I tried attaching the 
document, but the mailing list rejected it.  I've uploaded it to
http://airs.com/dnovillo/pub/whopr.pdf

The most important goal we have with this project is the ability to
handle Really Large programs (millions of functions, millions of
call-graph edges) with some grace. So, the design tries pretty hard to
make use of concurrency and clusters to partition the work.

At this point we are interested in getting feedback on the general idea.
There is some refactoring that will be needed inside the call-graph
manager and some aspects of the design may not even need a lot of
changes in GCC. But in general, it will require very efficient IR streaming.

In terms of implementation, we will likely use the LTO branch as a
basis. Many of the features we will need are already being implemented
in the branch, so we will keep helping with that implementation.


Thanks. Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Tim Josling]

On Wed, 2007-12-12 at 15:06 -0500, Diego Novillo wrote:
> Over the last few weeks we (Google) have been discussing ideas on how to
> leverage the LTO work to implement a whole program optimizer that is
> both fast and scalable.
> 
> While we do not have everything thought out in detail, we think we have
> enough to start doing some implementation work.  I tried attaching the 
> document, but the mailing list rejected it.  I've uploaded it to
> http://airs.com/dnovillo/pub/whopr.pdf

A few questions:

Do you have any thoughts on how this approach would be able to use
profiling information, which is very a very powerful source of
information for producing good optimisations?

Would there be much duplication of code between this and normal GCC
processing or would it be possible to share a common code base?

A few years back there were various suggestions about having files
containing intermediate representations and this was criticised because
it could make it possible for people for subvert the GPL by connecting
to the optimisation phases via such an intermediate file. Arguably the
language front end is then a different program and not covered by the
GPL. It might be worth thinking about this aspect. 

This also triggers the thought that if you have this intermediate
representation, and it is somewhat robust to GCC patchlevels, you do not
actually need source code of proprietary libraries to optimize into
them. You only need the intermediate files, which may be easier to get
than source code.

Tim Josling

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Harvey Harrison]

On Wed, 2007-12-12 at 15:06 -0500, Diego Novillo wrote:
> Over the last few weeks we (Google) have been discussing ideas on how to
> leverage the LTO work to implement a whole program optimizer that is
> both fast and scalable.
> 
> While we do not have everything thought out in detail, we think we have
> enough to start doing some implementation work.  I tried attaching the 
> document, but the mailing list rejected it.  I've uploaded it to
> http://airs.com/dnovillo/pub/whopr.pdf
> 
> The most important goal we have with this project is the ability to
> handle Really Large programs (millions of functions, millions of
> call-graph edges) with some grace. So, the design tries pretty hard to
> make use of concurrency and clusters to partition the work.
> 
> At this point we are interested in getting feedback on the general idea.
> There is some refactoring that will be needed inside the call-graph
> manager and some aspects of the design may not even need a lot of
> changes in GCC. But in general, it will require very efficient IR streaming.
> 
> In terms of implementation, we will likely use the LTO branch as a
> basis. Many of the features we will need are already being implemented
> in the branch, so we will keep helping with that implementation.
> 

I'm curious how this interacts/complements  with any efforts to
using the LLVM IR in LTO.

Any pointers to where that discussion ended up?

Harvey

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Chris Lattner]

On Dec 12, 2007, at 3:41 PM, Harvey Harrison wrote:
>> In terms of implementation, we will likely use the LTO branch as a
>> basis. Many of the features we will need are already being  
>> implemented
>> in the branch, so we will keep helping with that implementation.
>>
>
> I'm curious how this interacts/complements  with any efforts to
> using the LLVM IR in LTO.
>
> Any pointers to where that discussion ended up?

There are no plans to integrate LLVM with mainline GCC.  LLVM  
maintains its own permanent fork of GCC, which we periodically sync  
up with GCC's progress (e.g. LLVM 2.2 will include a GCC 4.2 based  
front-end).  There is also work underway to build llvm-native front- 
end technology (http://clang.llvm.org).

If you want LTO today, feel free to go to http://llvm.org/ :)  
otherwise LLVM is irrelevant to this discussion.

-Chris

http://llvm.org/
http://clang.llvm.org/
http://nondot.org/sabre/

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Harvey Harrison]

On Wed, 2007-12-12 at 16:02 -0800, Chris Lattner wrote:
> On Dec 12, 2007, at 3:41 PM, Harvey Harrison wrote:
> >> In terms of implementation, we will likely use the LTO branch as a
> >> basis. Many of the features we will need are already being  
> >> implemented
> >> in the branch, so we will keep helping with that implementation.
> >>
> >
> > I'm curious how this interacts/complements  with any efforts to
> > using the LLVM IR in LTO.
> >
> > Any pointers to where that discussion ended up?
> 
> There are no plans to integrate LLVM with mainline GCC.  LLVM  
> maintains its own permanent fork of GCC, which we periodically sync  
> up with GCC's progress (e.g. LLVM 2.2 will include a GCC 4.2 based  
> front-end).  There is also work underway to build llvm-native front- 
> end technology (http://clang.llvm.org).
> 
> If you want LTO today, feel free to go to http://llvm.org/ :)  
> otherwise LLVM is irrelevant to this discussion.

I was more interested in the format of the IR gcc ends up using, I was
curious where the discussion had gotten for LTO in gcc-land.  The LLVM
representation seemed rather sane, and already has at least one
implementation of tools using it.

Harvey

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Praveen Raghavan]

> While we do not have everything thought out in detail, we think we have
> enough to start doing some implementation work.  I tried attaching the
> document, but the mailing list rejected it.  I've uploaded it to
> http://airs.com/dnovillo/pub/whopr.pdf
>

Very very interesting proposal indeed!
I have a few questions:

1. Are there also plans to extend the global transformation
capabilities. I see that the original set of global transformations is
limited (rightfully so).
2. Also any thoughts on how you keep the complete GIMPLE
representation of millions of functions together? You would have some
serious complexity issues inside the WPA engine?
Or is it the idea that you start with the minimal information in the
wpo1 file and if required read in the GIMPLE section?
3. Is there a plan/schedule on when 'a' version of this would be out?

Regards,
Praveen

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Ollie Wild]

On Dec 12, 2007 3:28 PM, Tim Josling <tejgcc@westnet.com.au> wrote:
>
> Do you have any thoughts on how this approach would be able to use
> profiling information, which is very a very powerful source of
> information for producing good optimisations?

The intent is for the WPA phase to utilize profile information, both
for making transformation decisions and for assigning call-graph edge
weights (which impacts partitioning and, hence, the local
optimizations available during LTRANS).  We've also discussed the
possibility of bypassing LTRANS altogether for portions of the
call-graph which profiling determines are insignificant.

> A few years back there were various suggestions about having files
> containing intermediate representations and this was criticised because
> it could make it possible for people for subvert the GPL by connecting
> to the optimisation phases via such an intermediate file. Arguably the
> language front end is then a different program and not covered by the
> GPL. It might be worth thinking about this aspect.

The lto branch is already doing this, so presumably that discussion
was resolved (Maybe someone in the know should pipe up.).  This
proposal aims to leverage (and augment) that work in progress.

> This also triggers the thought that if you have this intermediate
> representation, and it is somewhat robust to GCC patchlevels, you do not
> actually need source code of proprietary libraries to optimize into
> them. You only need the intermediate files, which may be easier to get
> than source code.

I believe a stable representation is an explicit non-goal of the LTO
project (Perhaps that was the "resolution" of the discussion above.).
It's an interesting idea, though.  Maybe this is something to revisit
once the representation has had a chance to stabilize.

Ollie

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Ollie Wild]

On Dec 12, 2007 11:14 PM, Praveen Raghavan <praveen.gcc@gmail.com> wrote:
>
> 1. Are there also plans to extend the global transformation
> capabilities. I see that the original set of global transformations is
> limited (rightfully so).

This is still at a very early design stage.  Additional
transformations could (and should) be added where they make sense.
The main constraints to consider are the time and memory requirements
of the WPA phase.  Since this is the only phase which can't be
parallelized, its scalability is paramount.

> 2. Also any thoughts on how you keep the complete GIMPLE
> representation of millions of functions together? You would have some
> serious complexity issues inside the WPA engine?
> Or is it the idea that you start with the minimal information in the
> wpo1 file and if required read in the GIMPLE section?

You don't.  WPA is the only global phase, and it operates only on
summary data.  The actually reading of GIMPLE occurs in LTRANS, which
partitions the problem.  Depending on how large partitions need to be
before reasonable performance benefits are observed, it may be
necessary to allow LTRANS to swap functions in and out of memory.
That's still an open question.

> 3. Is there a plan/schedule on when 'a' version of this would be out?

TBD.

Ollie

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On 12/13/07 2:39 AM, Ollie Wild wrote:

> The lto branch is already doing this, so presumably that discussion
> was resolved (Maybe someone in the know should pipe up.).

Yes, streaming the IL to/from disk is a resolved issue.

> I believe a stable representation is an explicit non-goal of the LTO
> project (Perhaps that was the "resolution" of the discussion above.).

Right.  The on-disk representation will tend to be unstable.


Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On 12/12/07 6:41 PM, Harvey Harrison wrote:

> I'm curious how this interacts/complements  with any efforts to
> using the LLVM IR in LTO.

No.  At least not at this moment.  GCC uses its own IR (GIMPLE) as the 
in-core and on-disk representation.

> Any pointers to where that discussion ended up?

There was some discussion about merging LLVM and GCC a couple of years 
back but nothing concrete came out of it.


Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Chris Lattner]

On Dec 13, 2007, at 5:32 AM, Diego Novillo wrote:
> On 12/12/07 6:41 PM, Harvey Harrison wrote:
>> Any pointers to where that discussion ended up?
>
> There was some discussion about merging LLVM and GCC a couple of  
> years back but nothing concrete came out of it.

The concrete thing that came out of it is that it isn't going to  
happen. :)

-Chris

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Jan Hubicka]

Hi,
thanks for writting the proposal.  It seems that at least in general
terms we are all in sync.
> At this point we are interested in getting feedback on the general idea.
> There is some refactoring that will be needed inside the call-graph
> manager and some aspects of the design may not even need a lot of
> changes in GCC. But in general, it will require very efficient IR streaming.

Doing call graph changes should not be that hard (I was trying to keep
similar deisgn in mind when implementing it, even if we stepped away
from the plan in some cases, like reorganizing passes from vertical to
horisontal order). Nearest problem I see is merging different
declarations of units read back, I have prototype implementation of DECL
merging pass done from my trip this week and hope to have it working at
least for --combine and C during christmas.

Honza
> 
> In terms of implementation, we will likely use the LTO branch as a
> basis. Many of the features we will need are already being implemented
> in the branch, so we will keep helping with that implementation.
> 
> 
> Thanks. Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On 12/18/07 08:29, Jan Hubicka wrote:

> Doing call graph changes should not be that hard (I was trying to keep
> similar deisgn in mind when implementing it, even if we stepped away
> from the plan in some cases, like reorganizing passes from vertical to
> horisontal order). Nearest problem I see is merging different
> declarations of units read back, I have prototype implementation of DECL
> merging pass done from my trip this week and hope to have it working at
> least for --combine and C during christmas.

Cool.  Yeah, that is going to be one of the main things we need to 
continue.  For the next little while I will be working on finishing 
tuples, most of what remains are mechanical changes to get bootstraps 
going.  I will then work on tuning RTL generation.

Since we have these two ongoing branches (LTO and tuples) that will be 
used by whole program optimizer, I think we need to coordinate a little 
bit.  I wrote up a wiki page to keep all these things linked from one place.

http://gcc.gnu.org/wiki/whopr

I started a very incomplete implementation plan that I would like folks 
to help fill in.

Ken/Nathan, what are the major issues still missing in LTO?  I wrote up 
a couple, but I'm sure you guys have a much more complete list.

Jan, wrt the optimization plan coming out of the analysis phase, and the 
various pieces of header/summary information, what do you think are the 
major pieces we need?

In terms of branch mechanics, I'm initially tempted to do this 
implementation on a branch separate from tuples and lto.  This will 
allow us to merge both lto and tuples separately, as the rest of the 
optimizer is still a long ways away.  What do folks think?


Thanks.  Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Kenneth Zadeck]

Diego Novillo wrote
> On 12/18/07 08:29, Jan Hubicka wrote:
>
>> Doing call graph changes should not be that hard (I was trying to keep
>> similar deisgn in mind when implementing it, even if we stepped away
>> from the plan in some cases, like reorganizing passes from vertical to
>> horisontal order). Nearest problem I see is merging different
>> declarations of units read back, I have prototype implementation of DECL
>> merging pass done from my trip this week and hope to have it working at
>> least for --combine and C during christmas.
>
> Cool.  Yeah, that is going to be one of the main things we need to
> continue.  For the next little while I will be working on finishing
> tuples, most of what remains are mechanical changes to get bootstraps
> going.  I will then work on tuning RTL generation.
>
> Since we have these two ongoing branches (LTO and tuples) that will be
> used by whole program optimizer, I think we need to coordinate a
> little bit.  I wrote up a wiki page to keep all these things linked
> from one place.
>
> http://gcc.gnu.org/wiki/whopr
>
> I started a very incomplete implementation plan that I would like
> folks to help fill in.
>
> Ken/Nathan, what are the major issues still missing in LTO?  I wrote
> up a couple, but I'm sure you guys have a much more complete list.
>
> Jan, wrt the optimization plan coming out of the analysis phase, and
> the various pieces of header/summary information, what do you think
> are the major pieces we need?
>
> In terms of branch mechanics, I'm initially tempted to do this
> implementation on a branch separate from tuples and lto.  This will
> allow us to merge both lto and tuples separately, as the rest of the
> optimizer is still a long ways away.  What do folks think?
>
>
> Thanks.  Diego.
I am hoping that in the next couple of days, Nathan and I will be able
to say that we have completed to work that Codesourcery/NaturalBridge
contracted to do with IBM.  Completion means that we are able to compile
and run the C language spec 2000 benchmarks in LTO mode, as well as
compile all of the gcc compiler itself (this does not include the runtime).

There are still many open issues that we are hoping that the community
would address
(The next four items are considered general cleanups/improvements
independent of LTO and would be welcomed as changes to the truck when
stage I opens.  However a complete LTO implementation depends on them
being completed):

1) Removal of the rest of the lang hooks.
2) Removal of support for not file at time mode (I believe that IanT has
a patch for this.)
3) Removal of any remaining places where the front ends directly
generate rtl.
4) Gimplifying static initializers at the same time as everything else.

When these 4 items are done, it will be possible to consider the making
lto work
with other front ends. 

There are still LTO items that do not work with the C front ends.  Most
of these support extensions to C.

1) We do not handle types that reference local variables.  Such as
arrays that are sized by the parameter to a function.
2) Nested functions.
3) Attributes associated with types, like packed.

(1) may be hard. The rest of a simple matter of programming.

There is still a matter that it is difficult to separate the LTO type
information from the debugging information. 

There are a large number of things that need to change to make lto/whopr
a reality.  Many of them are addressed in the google document. 

I personally was planning to start restructuring the ipa passes and
serializing the cgraph.  I was waiting for Honza to get back to being
regularly available so that we could work on that together.  The current
code does not need serialize the cgraph since it loads all functions
into memory, the call graph is just rebuilt as each function is loaded. 
This obviously needs to be changed before we can at all talk about
distributing the compilation. 

I personally think that the most pressing problems are

1) making lto/whopr work in the presence of modules that do not fit
perfectly together, because of type or function argument mismatches.  I
think that this will be a challenging problem that will require a lot of
thought and code.  The easy case of just dying when things do not match
up is ok, but it is unlikely that lto/whopr will be a generally useful
tool without at least being able to swallow any existing program and at
least do try to do something good.

2) making the front end specific aliasing information available in some
language independent manner to the back ends.  Gcc is basically a C
compiler with a bunch of other front ends graphed onto it.  While it
makes many accommodations to the requirements of other languages, it
rarely does things to take advantage of the "higher level" information
that is available in non C languages.  Toon's paper at last year's
summit is a good example of exactly how badly we do, and the problem is
likely to only get worse with LTO/whopr as the lang hooks go away. 
While the last section of the whopr pays some lip service to this, we as
a community have never really addressed the issues of how we could
expand/change our internal representation to accomodate the high level
features supported by the non c frontends.

I have not looked at the code for Diego's tuplization.  The wiki does
not indicate that there is any semantic difference between gimple trees
and gimple tuples, it just appears to be a well designed data structure
cleanup.  It would be nice if this next round of intermediate code was
able to represent some of the information that we will be throwing away
the lang hooks. 

Both of these are very hard problems and they are likely to require the
same level of commitment that will be required to make Whopr work.  It
is not that i think that making lto/whopr work in a distributed
environment is not an important problem, it is just that i think that we
need to make LTO produce good code on real programs first. 

Kenny

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Tim Josling]

On Thu, 2007-12-13 at 08:27 -0500, Diego Novillo wrote:
> On 12/13/07 2:39 AM, Ollie Wild wrote:
> 
> > The lto branch is already doing this, so presumably that discussion
> > was resolved (Maybe someone in the know should pipe up.).
> 
> Yes, streaming the IL to/from disk is a resolved issue.
> ...
> 
> Diego.

I found this thread
http://gcc.gnu.org/ml/gcc/2005-11/msg00735.html

>> From: Mark Mitchell <mark at codesourcery dot com>
>> To: gcc mailing list <gcc at gcc dot gnu dot org>
>> Date: Wed, 16 Nov 2005 14:26:28 -0800
>> Subject: Link-time optimzation

________________________________________________________________________
>> The GCC community has talked about link-time optimization for some time.
>> ...
>> We would prefer not to have this thread devolve into a discussion about
>> legal and "political" issues relating to reading and writing GCC's
>> internal representation.  I've said publicly for a couple of years that
>> GCC would need to have this ability, and, more constructively, David
>> Edelsohn has talked with the FSF (both RMS and Eben Moglen) about it.
>> The FSF has indicated that GCC now can explore adding this feature,
>> although there are still some legal details to resolve.

>> ...
>>  http://gcc.gnu.org/projects/lto/lto.pdf
>> ... 

Was there any more about this?

I have restarted work on my COBOL front end. Based on my previous
experiences writing a GCC front end I want to have as little code as
possible in the same process as the GCC back end. 

This means passing over a file. So I would like to understand how to
avoid getting into political/legal trouble when doing this.

Thanks,
Tim Josling

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On Dec 19, 2007 5:19 PM, Tim Josling <tejgcc@westnet.com.au> wrote:

> This means passing over a file. So I would like to understand how to
> avoid getting into political/legal trouble when doing this.

Passing over a file in what format?  If you are writing a COBOL to C
translator, that will certainly be fine.  If you are emitting GENERIC
or GIMPLE, you are much better off implementing your FE like any other
GCC FE.  Fortran is a good example of an FE that is totally
independent from the rest of GCC.  It hands out a GENERIC
representation built out of its internal data structures.

Otherwise, you will need to translate to GIMPLE, stream it out from
the COBOL FE and feed it into the LTO FE.


Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Chris Lattner]

On Dec 19, 2007, at 2:19 PM, Tim Josling wrote:

>
>>> ...
>>>  http://gcc.gnu.org/projects/lto/lto.pdf
>>> ...
>
> Was there any more about this?
>
> I have restarted work on my COBOL front end. Based on my previous
> experiences writing a GCC front end I want to have as little code as
> possible in the same process as the GCC back end.
>
> This means passing over a file. So I would like to understand how to
> avoid getting into political/legal trouble when doing this.

While it is possible to make this work once LTO is finished, it seems  
unlikely that it will be pleasant.  Doing so will basically mean  
reimplementing a 'writer' for the LTO format to interoperate with the  
GCC code.  This seems to be a hard task, as there is no document on  
the structure and contents of the LTO file.  OTOH, you can get this   
by reverse engineering the code to find out what it does.  Further,  
it has been publicly stated that the format will evolve and is not  
going to be stable (though I don't recall where).  Unless you want to  
fight to keep up with the format, this sounds like a major pain.

You might be interested in checking out LLVM: http://llvm.org/ which  
has a well defined and well specified file formats (one text and one  
binary), and preserves backwards compatibility with them across major  
release (i.e. 1.0 -> 1.9 and 2.0 -> 2.x).  http://llvm.org/docs/ 
LangRef.html

I'd be interested to hear if keeping the LTO format stable is  
something the GCC community plans to do,

-Chris

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On Dec 19, 2007 5:29 PM, Chris Lattner <clattner@apple.com> wrote:

> I'd be interested to hear if keeping the LTO format stable is
> something the GCC community plans to do,

I doubt it.  We may end up doing it for practical reasons within a
release, but I'm not sure if it's high on anyone's priority list.


Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Diego Novillo]

On Dec 19, 2007 1:41 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:

> I am hoping that in the next couple of days, Nathan and I will be able
> to say that we have completed to work that Codesourcery/NaturalBridge
> contracted to do with IBM.  Completion means that we are able to compile
> and run the C language spec 2000 benchmarks in LTO mode, as well as
> compile all of the gcc compiler itself (this does not include the runtime).

Sounds good.  Do you folks have some criteria for merging into
mainline?  I ran the C testsuite today by forcing every single test to
use -flto, there were about <8,000 testsuite failures (FAIL +
UNRESOLVED), which is about a 16% failure rate.

We (Google) plan to keep working on those failures and getting the C++
front end in shape.  We (GCC) should probably figure out a set of
criteria to consider merging the branch into mainline.  Should we
shoot for being able to bootstrap with -flto enabled?  I would at
least be able to pass all the testsuites with -flto enabled.

> There are still many open issues that we are hoping that the community
> would address

Thanks.  I've added some of these items to the implementation plan on
the wiki page.  The rest were already there, please take a look and
add/modify to the list.

> I personally was planning to start restructuring the ipa passes and
> serializing the cgraph.

Great.  Those are items under the WPA phase. If you have a list of
things to be done besides the ones that are already there, could you
add them?  The more specific we are in this list, the easier it will
be for folks to pick up stuff to do.

> I personally think that the most pressing problems are
>
> 1) making lto/whopr work in the presence of modules that do not fit
> perfectly together, because of type or function argument mismatches.

Agreed.

> that is available in non C languages.  Toon's paper at last year's
> summit is a good example of exactly how badly we do, and the problem is
> likely to only get worse with LTO/whopr as the lang hooks go away.

Are you talking about aliasing or things like high-level array operations?

> While the last section of the whopr pays some lip service to this

Well, no.  That only addresses some of the aliasing problems.
Representing high-level concepts like array/vector arithmetic or class
hierarchies is not something we have done well in GIMPLE.  In terms of
whole program optimization, we will be interested in addressing class
hierarchy optimizations.

> a community have never really addressed the issues of how we could
> expand/change our internal representation to accomodate the high level
> features supported by the non c frontends.

We have for concurrency with the extensions to support OpenMP which
are useful in contexts like auto-parallelism.  But in general, we
don't transfer some things like array syntax or class hierarchies very
well.

Now, adding high-level concepts to an IL is usually expensive in
several ways.  Beyond arrays and class hierarchies, do you see any
other high-level concept worth transferring into GIMPLE?  I wouldn't
want to represent very many high-level concepts in GIMPLE.

> The wiki does not indicate that there is any semantic difference between gimple trees
> and gimple tuples

Right, there isn't.  The work on tuples is orthogonal and can go
in/out at any time.  It's just mechanically big, as it changes data
structures used by most of the compiler.  All this work can proceed in
parallel.

> Both of these are very hard problems and they are likely to require the
> same level of commitment that will be required to make Whopr work.  It
> is not that i think that making lto/whopr work in a distributed
> environment is not an important problem, it is just that i think that we
> need to make LTO produce good code on real programs first.

Oh, absolutely.  The design simply allows the first (LGEN) and last
stage (LTRANS) to operate in a distributed environment.  The initial
implementation can simply assume a shared file system.  Distribution
can be added later.  The only important parameter is to avoid
implementation decisions that will prevent processing massively large
applications.


Thanks.  Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Kenneth Zadeck]

Diego Novillo wrote:
> On Dec 19, 2007 1:41 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
>   
>> I am hoping that in the next couple of days, Nathan and I will be able
>> to say that we have completed to work that Codesourcery/NaturalBridge
>> contracted to do with IBM.  Completion means that we are able to compile
>> and run the C language spec 2000 benchmarks in LTO mode, as well as
>> compile all of the gcc compiler itself (this does not include the runtime).
>>     
>
> Sounds good.  Do you folks have some criteria for merging into
> mainline?  I ran the C testsuite today by forcing every single test to
> use -flto, there were about <8,000 testsuite failures (FAIL +
> UNRESOLVED), which is about a 16% failure rate.
>   
I never tried such a test.  My listing of things to do was based on the
execute tests.
It is hard to say what that 16% really means without going thur case by
case.  I did this for the execute tests.  That was what I based my list
on.  It would not surprise me if there are other issues, but it could
also be the case that the listed failures are just over expressed in the
test suite.
 
The "last" bug that nathan and I are working on is that local statics
are not done correctly.
The hope is that will be fixed tomorrow. 

An idea that has been kicked around is that when lto is good enough to
replace the old --combine, then we should remove --combine and replace
it with lto.  I have not really thought thru the details of this, but
given that --combine is (i believe) a c only thing, having lto be c only
is not that big a deal.  Certainly no extra regressions in the c
testsuite is required.


> We (Google) plan to keep working on those failures and getting the C++
> front end in shape.  We (GCC) should probably figure out a set of
> criteria to consider merging the branch into mainline.  Should we
> shoot for being able to bootstrap with -flto enabled?  I would at
> least be able to pass all the testsuites with -flto enabled.
>
>   
My guess is that you are not going to get C++ working until all of the
lang hooks are properly resolved.  Some of the ways that some of these
langhooks were resolved in the lto branch was to assume c. 

>> There are still many open issues that we are hoping that the community
>> would address
>>     
>
> Thanks.  I've added some of these items to the implementation plan on
> the wiki page.  The rest were already there, please take a look and
> add/modify to the list.
>
>   
>> I personally was planning to start restructuring the ipa passes and
>> serializing the cgraph.
>>     
>
> Great.  Those are items under the WPA phase. If you have a list of
> things to be done besides the ones that are already there, could you
> add them?  The more specific we are in this list, the easier it will
> be for folks to pick up stuff to do.
>
>   
sure
>> I personally think that the most pressing problems are
>>
>> 1) making lto/whopr work in the presence of modules that do not fit
>> perfectly together, because of type or function argument mismatches.
>>     
>
> Agreed.
>
>   
>> that is available in non C languages.  Toon's paper at last year's
>> summit is a good example of exactly how badly we do, and the problem is
>> likely to only get worse with LTO/whopr as the lang hooks go away.
>>     
>
> Are you talking about aliasing or things like high-level array operations?
>
>   
Arrays and type heirarchy games are certainly the two that come to
mind.  Strings are also a possibility.  Many languages do magical things
with strings that go way beyond what one can do with arrays.
>> While the last section of the whopr pays some lip service to this
>>     
>
> Well, no.  That only addresses some of the aliasing problems.
> Representing high-level concepts like array/vector arithmetic or class
> hierarchies is not something we have done well in GIMPLE.  In terms of
> whole program optimization, we will be interested in addressing class
> hierarchy optimizations.
>
>   
>> a community have never really addressed the issues of how we could
>> expand/change our internal representation to accomodate the high level
>> features supported by the non c frontends.
>>     
>
> We have for concurrency with the extensions to support OpenMP which
> are useful in contexts like auto-parallelism.  But in general, we
> don't transfer some things like array syntax or class hierarchies very
> well.
>
> Now, adding high-level concepts to an IL is usually expensive in
> several ways.  Beyond arrays and class hierarchies, do you see any
> other high-level concept worth transferring into GIMPLE?  I wouldn't
> want to represent very many high-level concepts in GIMPLE.
>
>   
>> The wiki does not indicate that there is any semantic difference between gimple trees
>> and gimple tuples
>>     
>
> Right, there isn't.  The work on tuples is orthogonal and can go
> in/out at any time.  It's just mechanically big, as it changes data
> structures used by most of the compiler.  All this work can proceed in
> parallel.
>
>   
>> Both of these are very hard problems and they are likely to require the
>> same level of commitment that will be required to make Whopr work.  It
>> is not that i think that making lto/whopr work in a distributed
>> environment is not an important problem, it is just that i think that we
>> need to make LTO produce good code on real programs first.
>>     
>
> Oh, absolutely.  The design simply allows the first (LGEN) and last
> stage (LTRANS) to operate in a distributed environment.  The initial
> implementation can simply assume a shared file system.  Distribution
> can be added later.  The only important parameter is to avoid
> implementation decisions that will prevent processing massively large
> applications.
>
>
> Thanks.  Diego.
>   

kenny

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Jan Hubicka]

Hi,
> 
> Jan, wrt the optimization plan coming out of the analysis phase, and the 
> various pieces of header/summary information, what do you think are the 
> major pieces we need?

The cgraph used to be organized on a separate analysis, propagation and
modify stages and the passes in implemented fall quite naturally into
those pieces. Naturally it is limiting ellement, but not that bad and
for some fancier passes I am sure we can arrange interesting things to
be compiled at once or something like that.

As discussed with Kenny in the past, there are ordering issues - ie one
pass might invalidate info of other so there is a lot of interference
that makes it more challenging to order the IPA pass queue than for
all-in-memory IPA consisting of couple of completely independent passes.

We will need better memory management for Gimple, have effective way to
load function body into memory and actually cheaply release it when it
is no longer needed that is quite challenging with GGC.  I would hope
that in longer term we can move tupleized gimple into pools.

I also have sort of implementation plan TODO, I never got around putting
it into wiki well, but I will try to check how much ours differ and
update it.  One area that is quite nasty WRT LTO is debug info.

Honza
> 
> In terms of branch mechanics, I'm initially tempted to do this 
> implementation on a branch separate from tuples and lto.  This will 
> allow us to merge both lto and tuples separately, as the rest of the 
> optimizer is still a long ways away.  What do folks think?
> 
> 
> Thanks.  Diego.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Nicholas Nethercote]

On Wed, 12 Dec 2007, J.C. Pizarro wrote:

> [...]
>
> * "executable" means "it's from an execution to death of the e-prisoner"?
>
> * "Indirect call promotion" means "this promotion indirectly ehhhh?"?
>
> * "Dead variable elimination" means "elimination variable of R.I.P.s"?
>
> * etc.
>
>   J.C.Pizarro i though that the Apocalypsis is near.

My theory is that J.C.Pizarro is an advanced AI chat-bot designed to produce 
streams of nearly-intelligible programming-related verbiage, and that last 
email was the result of a malfunction that caused it to dump part of its 
internal word association database.

Nick

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Paolo Bonzini]

> They are gaming or playing with the words of the language for Google.
> 
> If the world is global then
>    ^^ what means "global optimizer" using the infraestructure for google? ^^.

Wow, paranoia is a new feature of J.C.'s messages.

Seriously, your future employers might search for your name in the 
future, and this will not be good advertising for you.  In the past it 
has already happened that someone asked his messages to be removed, and 
this request was impossible to fulfill (not even taking into account the 
moral issues).  You are being ridiculed *forever*.  Why can't you 
understand this?

Paolo

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Sebastian Pop]

Please stop spamming my gcc@gcc.gnu.org email box.
All the messages that you sent are just off-topic for this mailing list.
Please STOP sending emails.

Thank you,
Sebastian Pop

On Dec 12, 2007 4:42 PM, J.C. Pizarro <jcpiza@gmail.com> wrote:
>
> On 2007/12/12, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> > On 12/12/2007, J.C. Pizarro <jcpiza@gmail.com> wrote:
> > >
> > > * The googlish user says
> > >      "i'm using the massive googlecc compiler that uses a lot of tons
> > > of libraries
> > >       distributed in all the world!"
> > >
> > > * google shutdown => googlecc compiler doesn't work, ended history, byebye.
> >
> > Yet again you've jumped into a thread without understanding the
> > subject and you've said something completely irrelevant.  Bravo!
> >
> > I suggest you shut up and read the paper before you embarrass yourself further.
> >
> > This is only a suggestion, intended to be helpful.  I respect your
> > right to say anything you want and to make yourself look like a fool
> > in public.  I will not prevent you from doing that.
> >
> > Jon
> >
>
> They are gaming or playing with the words of the language for Google.
>
> If the world is global then
>    ^^ what means "global optimizer" using the infraestructure for google? ^^.
>
> For google:
> -----------
> * "whole program optimizer infrastructure for GCC" means
>   "a whole program (like DoD program?) to build an optimizer infrastructure
>   (physical, it that has Google but want to optimize still more it) for GCC"?
>
> * "flexible enough to accommodate" means "like it from google.com"?
>
> * "an efficient implementation" means
>   "an efficient construction of the infrastructure"?
>
> * "Whole-program analysis" means "to analyze the whole program"?
>
> * "massive memory consumption during compilation" means
>   "hey, more memory? => more machines like from google!"?
>
> * "whole-program optimization framework for GCC" doesn't mean
>   "program whole-optimization framework for GCC" but,
>   means it "a whole-program that optimizes the framework for GCC"?
>
> * "Call-graph partitioning to group closely related functions" means
>   "fragmenting the graph of remote calls to group closely related services"?
>
> * "Support incremental optimization" means
>   "we can support incrementaly our services of optimizing the infrastructure"?
>
> * "impossible (or undesirable) to fit all the function bodies in memory"
>   means "impossible in memory of machines but possible in disks of machines"?
>
> * "global call-graph" means "world's graph of remote calls"?
>
> * "global call-graph itself can always fit in memory" means
>   "ohh, the world's graph of remote calls always is in memory of machines"?
>
> * "1M nodes" means "one million of machines"?
>
> * "1M edges" means "one million of cables"?
>
> * "< 500 Mb of memory" means "< 500 megabits of memory for remote calls"?
> * "WHOPR tries to maximize the amount of parallel and independent work to
>   take advantage of clustered and multiprocessor machines" means
>   "WHOPR tries to use ALL that Google has parallelly it taking its advantage
>    due to its machines that Google has"?
>
> * "local generation" means "it generated locally by each machine"?
>
> * "global call-graph is assembled" means
>   "world's graph of remote calls is assembled"?
>
> * "global analysis process makes transformation decisions" means
>   "the process that Google analyzes spying the world make decisions of how to
>    transformate the world"?
>
> * "partitioned to facilite optimization" means "fragmented to facilite the
>    reduced computation of Google"? Or
>
> * "global call-graph may be partitioned to facilitate optimization" means
>   "partitioned to metropolies, cities and towns the ADSL telephonic branches
>    needed by Google to facilitate its operation of this infrastructure"?
>
> * "local transformations" means "the local police will do its action
>    against e-criminals"?
>
> * "executable" means "it's from an execution to death of the e-prisoner"?
>
> * "Indirect call promotion" means "this promotion indirectly ehhhh?"?
>
> * "Dead variable elimination" means "elimination variable of R.I.P.s"?
>
> * etc.
>
>    J.C.Pizarro i though that the Apocalypsis is near.
>

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Daniel Jacobowitz]

On Wed, Dec 12, 2007 at 11:42:23PM +0100, J.C. Pizarro wrote:
> They are gaming or playing with the words of the language for Google.

This is absurd and off-topic.  Please stop.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[J.C. Pizarro]

On 2007/12/12, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> On 12/12/2007, J.C. Pizarro <jcpiza@gmail.com> wrote:
> >
> > * The googlish user says
> >      "i'm using the massive googlecc compiler that uses a lot of tons
> > of libraries
> >       distributed in all the world!"
> >
> > * google shutdown => googlecc compiler doesn't work, ended history, byebye.
>
> Yet again you've jumped into a thread without understanding the
> subject and you've said something completely irrelevant.  Bravo!
>
> I suggest you shut up and read the paper before you embarrass yourself further.
>
> This is only a suggestion, intended to be helpful.  I respect your
> right to say anything you want and to make yourself look like a fool
> in public.  I will not prevent you from doing that.
>
> Jon
>

They are gaming or playing with the words of the language for Google.

If the world is global then
   ^^ what means "global optimizer" using the infraestructure for google? ^^.

For google:
-----------
* "whole program optimizer infrastructure for GCC" means
  "a whole program (like DoD program?) to build an optimizer infrastructure
  (physical, it that has Google but want to optimize still more it) for GCC"?

* "flexible enough to accommodate" means "like it from google.com"?

* "an efficient implementation" means
  "an efficient construction of the infrastructure"?

* "Whole-program analysis" means "to analyze the whole program"?

* "massive memory consumption during compilation" means
  "hey, more memory? => more machines like from google!"?

* "whole-program optimization framework for GCC" doesn't mean
  "program whole-optimization framework for GCC" but,
  means it "a whole-program that optimizes the framework for GCC"?

* "Call-graph partitioning to group closely related functions" means
  "fragmenting the graph of remote calls to group closely related services"?

* "Support incremental optimization" means
  "we can support incrementaly our services of optimizing the infrastructure"?

* "impossible (or undesirable) to fit all the function bodies in memory"
  means "impossible in memory of machines but possible in disks of machines"?

* "global call-graph" means "world's graph of remote calls"?

* "global call-graph itself can always fit in memory" means
  "ohh, the world's graph of remote calls always is in memory of machines"?

* "1M nodes" means "one million of machines"?

* "1M edges" means "one million of cables"?

* "< 500 Mb of memory" means "< 500 megabits of memory for remote calls"?
* "WHOPR tries to maximize the amount of parallel and independent work to
  take advantage of clustered and multiprocessor machines" means
  "WHOPR tries to use ALL that Google has parallelly it taking its advantage
   due to its machines that Google has"?

* "local generation" means "it generated locally by each machine"?

* "global call-graph is assembled" means
  "world's graph of remote calls is assembled"?

* "global analysis process makes transformation decisions" means
  "the process that Google analyzes spying the world make decisions of how to
   transformate the world"?

* "partitioned to facilite optimization" means "fragmented to facilite the
   reduced computation of Google"? Or

* "global call-graph may be partitioned to facilitate optimization" means
  "partitioned to metropolies, cities and towns the ADSL telephonic branches
   needed by Google to facilitate its operation of this infrastructure"?

* "local transformations" means "the local police will do its action
   against e-criminals"?

* "executable" means "it's from an execution to death of the e-prisoner"?

* "Indirect call promotion" means "this promotion indirectly ehhhh?"?

* "Dead variable elimination" means "elimination variable of R.I.P.s"?

* etc.

   J.C.Pizarro i though that the Apocalypsis is near.

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[Jonathan Wakely]

On 12/12/2007, J.C. Pizarro <jcpiza@gmail.com> wrote:
>
> * The googlish user says
>      "i'm using the massive googlecc compiler that uses a lot of tons
> of libraries
>       distributed in all the world!"
>
> * google shutdown => googlecc compiler doesn't work, ended history, byebye.

Yet again you've jumped into a thread without understanding the
subject and you've said something completely irrelevant.  Bravo!

I suggest you shut up and read the paper before you embarrass yourself further.

This is only a suggestion, intended to be helpful.  I respect your
right to say anything you want and to make yourself look like a fool
in public.  I will not prevent you from doing that.

Jon

Re: [RFC] WHOPR - A whole program optimizer framework for GCC

[J.C. Pizarro]

On 2007/12/12, "Diego Novillo" <dnovillo@google.com> wrote:
> Over the last few weeks we (Google) have been discussing ideas on how to
> leverage the LTO work to implement a whole program optimizer that is
> both fast and scalable.
>
> While we do not have everything thought out in detail, we think we have
> enough to start doing some implementation work. I tried attaching the document,
> but the mailing list rejected it. I've uploaded it to
> http://airs.com/dnovillo/pub/whopr.pdf
>
> The most important goal we have with this project is the ability to
> handle Really Large programs (millions of functions, millions of
> call-graph edges) with some grace. So, the design tries pretty hard to
> make use of concurrency and clusters to partition the work.
>
> At this point we are interested in getting feedback on the general idea.
> There is some refactoring that will be needed inside the call-graph
> manager and some aspects of the design may not even need a lot of
> changes in GCC. But in general, it will require very efficient IR streaming.
>
> In terms of implementation, we will likely use the LTO branch as a
> basis. Many of the features we will need are already being implemented
> in the branch, so we will keep helping with that implementation.
>
> Thanks. Diego.

* The googlish user says
     "i'm using the massive googlecc compiler that uses a lot of tons
of libraries
      distributed in all the world!"

* google shutdown => googlecc compiler doesn't work, ended history, byebye.

   J.C.Pizarro