[Announcement] Creating lightweight IPO branch

[Announcement] Creating lightweight IPO branch

[Xinliang David Li]

Hi, I am going to create a gcc branch for the functionality of
lightweight IPO. The description of the project and current status can
be found in http://gcc.gnu.org/wiki/LightweightIpo.  Some highlights:

1) If you already use FDO in your build, you also get IPO almost for free;
2) It is an IPO solution  practical to very large real world C++ applications;
3) Performance potential is very large (though I've seen case
increased compiler freedom can lead to performance degradation due to
over-optimization (inliner, unroller etc) -- but this is a different
matter).

If the idea is generally accepted, I will prepare a series of patches
and submit them to gcc trunk.

Thanks,

David

Re: [Announcement] Creating lightweight IPO branch

[Andi Kleen]

Xinliang David Li <davidxl@google.com> writes:
>
> If the idea is generally accepted, I will prepare a series of patches
> and submit them to gcc trunk.

I was reading your wiki page. Interesting idea. 

One aspect that wasn't clear to me on reading it was how different
compiler arguments for different files are handled. How would the
compiler compiling another source file know what special arguments
(like -I -D or special -f options) it needs? Or in what directory it
was compiled in for -I paths? Or do you assume that is always all the
same?

The other thing that wasn't clear to me was the worst case
behaviour. If there's a single large file x.c that has a function that
is called from 100 other small files with hot call sites then x.c
would be compiled 100 times, right? Is there something to mitigate
such worst case behaviour?

Thanks,
-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [Announcement] Creating lightweight IPO branch

[Xinliang David Li]

Andi,

On Tue, May 5, 2009 at 1:49 AM, Andi Kleen <andi@firstfloor.org> wrote:
> Xinliang David Li <davidxl@google.com> writes:
>>
>> If the idea is generally accepted, I will prepare a series of patches
>> and submit them to gcc trunk.
>
> I was reading your wiki page. Interesting idea.
>
> One aspect that wasn't clear to me on reading it was how different
> compiler arguments for different files are handled. How would the
> compiler compiling another source file know what special arguments
> (like -I -D or special -f options) it needs? Or in what directory it
> was compiled in for -I paths? Or do you assume that is always all the
> same?

This is actually mentioned in the document. Please see the section
about the module info record format. In each module info, the
information about -I paths, -D/-Us are recorded. Those will be passed
to the preprocessor when each module is processed.


>
> The other thing that wasn't clear to me was the worst case
> behaviour. If there's a single large file x.c that has a function that
> is called from 100 other small files with hot call sites then x.c
> would be compiled 100 times, right?

x.c as an auxiliary module, is never fully compiled. It is fully
parsed and after inlining, it is discarded (function DFEed).

> Is there something to mitigate
> such worst case behaviour?

Yes, there are related options to throttle worst case behavior.  This
problem will most likely exist in theory (very large cluster in
dynamic call graph). For most of the applications I see, hot calls are
limited intra module or small clusters.

Thanks,

David




>
> Thanks,
> -Andi
>
> --
> ak@linux.intel.com -- Speaking for myself only.
>

Re: [Announcement] Creating lightweight IPO branch

[Andi Kleen]

On Tue, May 05, 2009 at 10:25:13AM -0700, Xinliang David Li wrote:
> Andi,
> 
> On Tue, May 5, 2009 at 1:49 AM, Andi Kleen <andi@firstfloor.org> wrote:
> > Xinliang David Li <davidxl@google.com> writes:
> >>
> >> If the idea is generally accepted, I will prepare a series of patches
> >> and submit them to gcc trunk.
> >
> > I was reading your wiki page. Interesting idea.
> >
> > One aspect that wasn't clear to me on reading it was how different
> > compiler arguments for different files are handled. How would the
> > compiler compiling another source file know what special arguments
> > (like -I -D or special -f options) it needs? Or in what directory it
> > was compiled in for -I paths? Or do you assume that is always all the
> > same?
> 
> This is actually mentioned in the document. Please see the section
> about the module info record format. In each module info, the
> information about -I paths, -D/-Us are recorded. Those will be passed
> to the preprocessor when each module is processed.

I found it after the post :/. But it seems to be only a small subset of
options.  How about -m or -f flags?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [Announcement] Creating lightweight IPO branch

[Xinliang David Li]

On Tue, May 5, 2009 at 10:38 AM, Andi Kleen <andi@firstfloor.org> wrote:
> On Tue, May 05, 2009 at 10:25:13AM -0700, Xinliang David Li wrote:
>> Andi,
>>
>> On Tue, May 5, 2009 at 1:49 AM, Andi Kleen <andi@firstfloor.org> wrote:
>> > Xinliang David Li <davidxl@google.com> writes:
>> >>
>> >> If the idea is generally accepted, I will prepare a series of patches
>> >> and submit them to gcc trunk.
>> >
>> > I was reading your wiki page. Interesting idea.
>> >
>> > One aspect that wasn't clear to me on reading it was how different
>> > compiler arguments for different files are handled. How would the
>> > compiler compiling another source file know what special arguments
>> > (like -I -D or special -f options) it needs? Or in what directory it
>> > was compiled in for -I paths? Or do you assume that is always all the
>> > same?
>>
>> This is actually mentioned in the document. Please see the section
>> about the module info record format. In each module info, the
>> information about -I paths, -D/-Us are recorded. Those will be passed
>> to the preprocessor when each module is processed.
>
> I found it after the post :/. But it seems to be only a small subset of
> options.  How about -m or -f flags?

Right -- general option handling is yet need to be done. For instance,
we may not want to inline a function from a module with
-fstrict-aliasing to another function from a module with
-fno-strict-aliasing.  This is a universal CMO problem.  One simple
way is to use option checksum to make sure imported module has the
same option as the importing module.

Thanks,

David

>
> -Andi
>
> --
> ak@linux.intel.com -- Speaking for myself only.
>

Re: [Announcement] Creating lightweight IPO branch

[Richard Guenther]

On Tue, May 5, 2009 at 7:00 AM, Xinliang David Li <davidxl@google.com> wrote:
> Hi, I am going to create a gcc branch for the functionality of
> lightweight IPO. The description of the project and current status can
> be found in http://gcc.gnu.org/wiki/LightweightIpo.  Some highlights:
>
> 1) If you already use FDO in your build, you also get IPO almost for free;
> 2) It is an IPO solution  practical to very large real world C++ applications;
> 3) Performance potential is very large (though I've seen case
> increased compiler freedom can lead to performance degradation due to
> over-optimization (inliner, unroller etc) -- but this is a different
> matter).
>
> If the idea is generally accepted, I will prepare a series of patches
> and submit them to gcc trunk.

I was hoping that with LTO we can get rid of -combine, as its type/decl
merging is fragile in many cases.  Does this somehow conflict with
LIPO?  From what I understand is that you are merging TUs in the
frontend (like -combine) - did you consider merging TUs with the
LTO infrastructure, but in memory?

On the whole LIPO sounds indeed very interesting.

Thanks,
Richard.

Re: [Announcement] Creating lightweight IPO branch

[Xinliang David Li]

On Tue, May 5, 2009 at 2:47 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, May 5, 2009 at 7:00 AM, Xinliang David Li <davidxl@google.com> wrote:
>> Hi, I am going to create a gcc branch for the functionality of
>> lightweight IPO. The description of the project and current status can
>> be found in http://gcc.gnu.org/wiki/LightweightIpo.  Some highlights:
>>
>> 1) If you already use FDO in your build, you also get IPO almost for free;
>> 2) It is an IPO solution  practical to very large real world C++ applications;
>> 3) Performance potential is very large (though I've seen case
>> increased compiler freedom can lead to performance degradation due to
>> over-optimization (inliner, unroller etc) -- but this is a different
>> matter).
>>
>> If the idea is generally accepted, I will prepare a series of patches
>> and submit them to gcc trunk.
>
> I was hoping that with LTO we can get rid of -combine, as its type/decl
> merging is fragile in many cases.  Does this somehow conflict with
> LIPO?

LIPO does not depend on existing type/decl merging functionality --
though it does leverage the parser driver code -- mainly extending the
filescope push/pop thingy, so mostly there is no conflict.

 From what I understand is that you are merging TUs in the
> frontend (like -combine) - did you consider merging TUs with the
> LTO infrastructure, but in memory?

In LIPO, TU merging does not happen in frontend (the document may
sound a little confusing) -- the modules are parsed independently and
merged/linked after parsing. Diego and I talked about the possibilty
of using LTO to do this -- but that requires significant driver
change.

>
> On the whole LIPO sounds indeed very interesting.

Thanks,

David
>
> Thanks,
> Richard.
>

Re: [Announcement] Creating lightweight IPO branch

[Richard Guenther]

On Tue, May 5, 2009 at 7:56 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Tue, May 5, 2009 at 2:47 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Tue, May 5, 2009 at 7:00 AM, Xinliang David Li <davidxl@google.com> wrote:
>>> Hi, I am going to create a gcc branch for the functionality of
>>> lightweight IPO. The description of the project and current status can
>>> be found in http://gcc.gnu.org/wiki/LightweightIpo.  Some highlights:
>>>
>>> 1) If you already use FDO in your build, you also get IPO almost for free;
>>> 2) It is an IPO solution  practical to very large real world C++ applications;
>>> 3) Performance potential is very large (though I've seen case
>>> increased compiler freedom can lead to performance degradation due to
>>> over-optimization (inliner, unroller etc) -- but this is a different
>>> matter).
>>>
>>> If the idea is generally accepted, I will prepare a series of patches
>>> and submit them to gcc trunk.
>>
>> I was hoping that with LTO we can get rid of -combine, as its type/decl
>> merging is fragile in many cases.  Does this somehow conflict with
>> LIPO?
>
> LIPO does not depend on existing type/decl merging functionality --
> though it does leverage the parser driver code -- mainly extending the
> filescope push/pop thingy, so mostly there is no conflict.
>
>  From what I understand is that you are merging TUs in the
>> frontend (like -combine) - did you consider merging TUs with the
>> LTO infrastructure, but in memory?
>
> In LIPO, TU merging does not happen in frontend (the document may
> sound a little confusing) -- the modules are parsed independently and
> merged/linked after parsing. Diego and I talked about the possibilty
> of using LTO to do this -- but that requires significant driver
> change.

I see - so the modules are parsed and transformed to gimple (or generic?)
and then merged.  But then LTO and LIPO (could) share decl and type
merging code at least, no?

Thanks,
Richard.

Fwd: [Announcement] Creating lightweight IPO branch

[Xinliang David Li]

Forgot to copy the reply to the mailing list.

David


---------- Forwarded message ----------
From: Xinliang David Li <davidxl@google.com>
Date: Wed, May 6, 2009 at 10:08 AM
Subject: Re: [Announcement] Creating lightweight IPO branch
To: Richard Guenther <richard.guenther@gmail.com>


On Wed, May 6, 2009 at 2:00 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, May 5, 2009 at 7:56 PM, Xinliang David Li <davidxl@google.com> wrote:
>> On Tue, May 5, 2009 at 2:47 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, May 5, 2009 at 7:00 AM, Xinliang David Li <davidxl@google.com> wrote:
>>>> Hi, I am going to create a gcc branch for the functionality of
>>>> lightweight IPO. The description of the project and current status can
>>>> be found in http://gcc.gnu.org/wiki/LightweightIpo.  Some highlights:
>>>>
>>>> 1) If you already use FDO in your build, you also get IPO almost for free;
>>>> 2) It is an IPO solution  practical to very large real world C++ applications;
>>>> 3) Performance potential is very large (though I've seen case
>>>> increased compiler freedom can lead to performance degradation due to
>>>> over-optimization (inliner, unroller etc) -- but this is a different
>>>> matter).
>>>>
>>>> If the idea is generally accepted, I will prepare a series of patches
>>>> and submit them to gcc trunk.
>>>
>>> I was hoping that with LTO we can get rid of -combine, as its type/decl
>>> merging is fragile in many cases.  Does this somehow conflict with
>>> LIPO?
>>
>> LIPO does not depend on existing type/decl merging functionality --
>> though it does leverage the parser driver code -- mainly extending the
>> filescope push/pop thingy, so mostly there is no conflict.
>>
>>  From what I understand is that you are merging TUs in the
>>> frontend (like -combine) - did you consider merging TUs with the
>>> LTO infrastructure, but in memory?
>>
>> In LIPO, TU merging does not happen in frontend (the document may
>> sound a little confusing) -- the modules are parsed independently and
>> merged/linked after parsing. Diego and I talked about the possibilty
>> of using LTO to do this -- but that requires significant driver
>> change.
>
> I see - so the modules are parsed and transformed to gimple (or generic?)
> and then merged.  But then LTO and LIPO (could) share decl and type
> merging code at least, no?

LIPO take a approach that involves very little 'physical merging'.
Function call target fixup is only done on callgraph, and global
variable reference fix up is done on demand (lazily) when inlining
happens.  LIPO does type merging based on qualified names (not
structural equivalence) -- and there are no type reference fixups in
actual IL. The type merging is used for type based aliasing and allow
conservative merging (two different types with the same name  --- this
violates ODR and can be warned -- but such programs do exist) -- but
does not allow false negative (which can easily happen if structrual
equalivalence check fails).  The design goal of LIPO is simplicity and
least intrusiveness.


By the way, I saw a recent email asking about --combine support for
C++. In fact LIPO's mechanism can be easily adapted to support that
(and also changing C's implementation to make it more source tolerant)
-- but I doubt how useful -combine will be for C++ programs.


Thanks,

David
>
> Thanks,
> Richard.
>