Designing a clang incremental compiler server

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Designing a clang incremental compiler server

Reid Kleckner
Hello cfe-dev,

I'm interning at Google for the summer, and the focus of my internship
is to improve C++ build times by caching the results of parsing
headers and persisting the results either on disk or in the memory of
a persistent compiler server process.

Pre-compiled headers already do this, but they generally only work for
projects that use the '#include "world.h"' header style.  My goal is
to either improve the existing pre-compiled header support so that
this restriction can be lifted, or do something else entirely.

I worked with the LLVM JIT last summer, but I'm unfamiliar with
clang's internals.  Therefore, I thought I would throw some starting
questions out to the clang community.

First and foremost, are people interested in this?  I'm pretty sure
the answer is going to be yes, but I thought I should ask.  :)

Does anyone have any design advice?  I'd like to hear from people who
worked on PCH about how to make this work.  It requires doing things
like making sure all symbols that were not macros on the first include
are still not macros when the header is re-included, and some other
stuff with operator overloading that I'm not familiar with yet.

Where should I do this development?  Depending on the invasiveness of
the changes I'm making, I think it would be best to either work on
trunk or in a branch on the public svn repo.

There's also this previous work on GCC that was done by Per Bothner at Apple:
ftp://gcc.gnu.org/pub/gcc/summit/2003/GCC%20Compile%20Server.pdf

It's from 2003.  I can't find my info about it on the web, so
presumably the effort was abandoned.  I also got the impression that
the implementation was somewhat fragile from the undo buffers that
were used to deal with unwanted AST mutations during compilation.  Can
anyone at Apple familiar with the effort share some advice that might
also apply to clang?

Cheers,
Reid
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Designing a clang incremental compiler server

Douglas Gregor
Hello Reid,

On Jun 16, 2010, at 11:14 AM, Reid Kleckner wrote:
> I'm interning at Google for the summer, and the focus of my internship
> is to improve C++ build times by caching the results of parsing
> headers and persisting the results either on disk or in the memory of
> a persistent compiler server process.
>
> Pre-compiled headers already do this, but they generally only work for
> projects that use the '#include "world.h"' header style.  My goal is
> to either improve the existing pre-compiled header support so that
> this restriction can be lifted, or do something else entirely.

Clang's precompiled header support can be improved in many ways to support incremental compilation. However, I don't think the restriction requiring that the PCH include come first in the translation unit (the prefix header approach) can be lifted in any practical system that doesn't require the system headers to change. Per Bothner's paper, which you mentioned below, describes some of the problems with inclusion-order dependencies, but it doesn't even scratch the surface of ordering dependencies for C++, which has a large number of implicit dependencies. Even if we could manage to describe all of those dependencies---and I'm not certain we can---the computation required to do so is likely to kill any performance gains in the system.

As I see it, there are two approaches:

1) Live with this limitation, building the compilation server around the idea of implicitly creating a "world.h" (or multiple "world.h"'s) and sharing it among different translation units. One could extend the idea further with multi-level PCH files, where one PCH can reference another PCH, so that common prefixes of #includes could be shared more readily, and of course there are other opportunities for sharing (mmap'd file buffers, tokenized files, etc.)

2) Do something radically different, which reduces the number of dependencies between different headers and makes them more explicit. Something akin to the C++ "modules" proposals from Daveed Vandevoorde, for example.

Both are interesting, but they're very different. The first is a system that could be put into practice immediately, without changing system headers or libraries. The second is a much more ambitious long-term project that is likely to require changes to the C++ "world". Obviously, there are certainly other approaches that I'm not describing.

> First and foremost, are people interested in this?  I'm pretty sure
> the answer is going to be yes, but I thought I should ask.  :)

Yes, this is an interesting project and could reap big benefits for Clang.

> Does anyone have any design advice?  I'd like to hear from people who
> worked on PCH about how to make this work.  It requires doing things
> like making sure all symbols that were not macros on the first include
> are still not macros when the header is re-included, and some other
> stuff with operator overloading that I'm not familiar with yet.

PCH already does simple validation of this kind. For example, say that macro X is defined when the PCH file is used. If X was also a macro definition in the PCH file, Clang will check that the definitions are identical; if X was not a macro definition, Clang will check that the identifier 'X' was not used anywhere in the PCH file.

> Where should I do this development?  Depending on the invasiveness of
> the changes I'm making, I think it would be best to either work on
> trunk or in a branch on the public svn repo.

Trunk is fine, so long as your work doesn't destabilize the Clang compiler itself.

> There's also this previous work on GCC that was done by Per Bothner at Apple:
> ftp://gcc.gnu.org/pub/gcc/summit/2003/GCC%20Compile%20Server.pdf
>
> It's from 2003.  I can't find my info about it on the web, so
> presumably the effort was abandoned.  I also got the impression that
> the implementation was somewhat fragile from the undo buffers that
> were used to deal with unwanted AST mutations during compilation.  Can
> anyone at Apple familiar with the effort share some advice that might
> also apply to clang?

I am not familiar with that effort, but it has definitely been abandoned. I wouldn't attempt that approach again, because (as I said above) I don't believe it's practical to try to cope with all of the ordering dependencies in the current C/ObjC/C++ languages.

FWIW, 3x speedup (which Per Bothner's paper mentions) is what we're used to seeing for C and Objective-C  projects that use Clang's PCH mechanism, so even if the compiler server were to "just" implicitly create prefix headers (as the first option I mentioned at the beginning), there are big wins available.

        - Doug
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Designing a clang incremental compiler server

Christopher Jefferson
In reply to this post by Reid Kleckner

On 16 Jun 2010, at 19:14, Reid Kleckner wrote:

> Hello cfe-dev,
>
> I'm interning at Google for the summer, and the focus of my internship
> is to improve C++ build times by caching the results of parsing
> headers and persisting the results either on disk or in the memory of
> a persistent compiler server process.
>
> Pre-compiled headers already do this, but they generally only work for
> projects that use the '#include "world.h"' header style.  My goal is
> to either improve the existing pre-compiled header support so that
> this restriction can be lifted, or do something else entirely.
>
> I worked with the LLVM JIT last summer, but I'm unfamiliar with
> clang's internals.  Therefore, I thought I would throw some starting
> questions out to the clang community.
>
> First and foremost, are people interested in this?  I'm pretty sure
> the answer is going to be yes, but I thought I should ask.  :)

I have no useful design advice, but I can tell you the major problems that we had trying to make use of precompiled headers in a project where we used g++, to the point where we abandoned it, and also some thoughts.

1) Just getting it to work is good :) We found that g++ was very unstable and often segfaulted on significant projects. It would often crash if we tried to compile a pre-compiled header which itself included a pre-compiled header. Also, it required different precompiled headers for different optimisation settings, which was very difficult to automate.

2) Making it much more automated would be ideal -- I would much prefer it to "just happen" given the appropriate compiler flags, along with checking if headers need recompiling if headers get out of date (maybe too much of a hope?)

3) My source files often start (for example)

#include "myheader1.h"
#include "myheader2.h"
#include <vector>

I would really like to have a system which, for each source file, precompiled all the headers up to the first non-header (and non-define?) token. Obviously share these between sources if possible. While this might require quite a lot of compiling on the first compiling pass, hopefully it will speed up later passes.

Chris



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Designing a clang incremental compiler server

Chris Lattner
In reply to this post by Douglas Gregor
On Jun 16, 2010, at 2:47 PM, Douglas Gregor wrote:
>> Pre-compiled headers already do this, but they generally only work for
>> projects that use the '#include "world.h"' header style.  My goal is
>> to either improve the existing pre-compiled header support so that
>> this restriction can be lifted, or do something else entirely.
>
> However, I don't think the restriction requiring that the PCH include come first in the translation unit (the prefix header approach) can be lifted in any practical system that doesn't require the system headers to change.

I completely agree.

> 1) Live with this limitation, building the compilation server ... and of course there are other opportunities for sharing (mmap'd file buffers, tokenized files, etc.)

If you're looking to make a real impact in a realistic timeframe, I think this approach is the right answer.  I think you can actually get a pretty significant win out of just doing something simple like:

1. Make a shared multi-threaded compiler server process that individual 'clang' invocations talk to.
2. The compiler server caches headers as pre-lexed token streams, similar to a persistent PTH, but without requiring any setup.
3. For projects that already do use PCH, the PCH file can be cached by the compiler server making them benefit from PCH even more.

I think that just getting this level of sharing would be a pretty big win (20%?) for C++ projects building on a multicore machine, and the win will go up as Clang++ gets faster in other ways.  For example, someday we'll do the obvious "lazy creation of implicit member" optimization that G++ does (speeding up Sema), eventually ELF systems will support the integrated assembler, fastisel is going to get faster, etc.  As these other things get faster, more percentage of time is spent in the preprocessor.

After this first level is implemented, then we talk about doing incremental/modular parsing, and other interesting things.  For example, if clang ASTs are immutable once created (we're close to that, but not fully there) then you could imagine a "checkpointing" mechanism where .cpp files which share a common prefix can share declarations and avoid reparsing the common prefix.  Another idea is to use information in the compiler server to know what templates are instantiated in one .o file to avoid re-instantiating/codegen'ing redundant stuff in other .o file.  This is also useful for vtables that have no key method etc.

These sorts of optimizations are "big wins" but really need something like a compiler server to get a more holistic view of the build.  To answer your higher level question: YES this would be a great project!  Please start small and build obviously useful stuff (in mainline) like the basic compiler server.  Once the obviously useful stuff is there, it will be more clear which of the crazy ideas is the biggest win (because we can measure to make educated guesses) and most possible to implementable.

-Chris


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Designing a clang incremental compiler server

Reid Kleckner-2
On Wed, Jun 16, 2010 at 6:04 PM, Chris Lattner <[hidden email]> wrote:
> On Jun 16, 2010, at 2:47 PM, Douglas Gregor wrote:
>>> Pre-compiled headers already do this, but they generally only work for
>>> projects that use the '#include "world.h"' header style.  My goal is
>>> to either improve the existing pre-compiled header support so that
>>> this restriction can be lifted, or do something else entirely.
>>
>> However, I don't think the restriction requiring that the PCH include come first in the translation unit (the prefix header approach) can be lifted in any practical system that doesn't require the system headers to change.
>
> I completely agree.

Having gotten now several opinions from people who know C++ better
than I, I have realized that this is not a tractable problem for C++.
It seems much more promising for something like C.

>> 1) Live with this limitation, building the compilation server ... and of course there are other opportunities for sharing (mmap'd file buffers, tokenized files, etc.)
>
> If you're looking to make a real impact in a realistic timeframe, I think this approach is the right answer.  I think you can actually get a pretty significant win out of just doing something simple like:
>
> 1. Make a shared multi-threaded compiler server process that individual 'clang' invocations talk to.
> 2. The compiler server caches headers as pre-lexed token streams, similar to a persistent PTH, but without requiring any setup.
> 3. For projects that already do use PCH, the PCH file can be cached by the compiler server making them benefit from PCH even more.
>
> I think that just getting this level of sharing would be a pretty big win (20%?) for C++ projects building on a multicore machine, and the win will go up as Clang++ gets faster in other ways.  For example, someday we'll do the obvious "lazy creation of implicit member" optimization that G++ does (speeding up Sema), eventually ELF systems will support the integrated assembler, fastisel is going to get faster, etc.  As these other things get faster, more percentage of time is spent in the preprocessor.
>
> After this first level is implemented, then we talk about doing incremental/modular parsing, and other interesting things.  For example, if clang ASTs are immutable once created (we're close to that, but not fully there) then you could imagine a "checkpointing" mechanism where .cpp files which share a common prefix can share declarations and avoid reparsing the common prefix.  Another idea is to use information in the compiler server to know what templates are instantiated in one .o file to avoid re-instantiating/codegen'ing redundant stuff in other .o file.  This is also useful for vtables that have no key method etc.
>
> These sorts of optimizations are "big wins" but really need something like a compiler server to get a more holistic view of the build.  To answer your higher level question: YES this would be a great project!  Please start small and build obviously useful stuff (in mainline) like the basic compiler server.  Once the obviously useful stuff is there, it will be more clear which of the crazy ideas is the biggest win (because we can measure to make educated guesses) and most possible to implementable.

Great, I'm glad to hear there are other reasons to pursue this.

Right now I'm trying to improve -ftime-report to do some simple
profiling that breaks down time spent into broad categories, like
lexing, PP, parse, sema, irgen, iropt, and codegen.  That way I can
actually know if any of this will be profitable enough.  Expect a
patch soon.

Reid

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev