Change LLVM bitcode linking to use tree reduction to scale better

Change LLVM bitcode linking to use tree reduction
rather than link in one at a time.  Linking one at a time
means that the "Dst" module keeps growing yet needs to be
crawled entirely at each step to gather a set of types.

The cost becomes something 1 + 2 + 3 + ... + N (quadratic).

Instead, delay linking until we know of all the modules
so we can do linking as a tree.  The actual linking is now
done when the module-getter is called, and error messages
are also delayed till then.


Time before for linking llc.pexe: ~126 secs
Time after for linking llc.pexe: ~20 secs

Memory after for linking llc.pexe: ~1GB for 727 modules.
~1.3GB if we don't delete the sources as they are consumed.

NOTE: a separate "opt" pass can still take 1.5 min for llc,
so LTO optimized builds can still take a while, but at least
non-optimized builds can be faster.


BUG= http://code.google.com/p/nativeclient/issues/detail?id=2883
TEST= rebuild.

[jvoung (off chromium), 2012-07-18 21:38:31]

still testing, but at least smoke tests pass

[jvoung - send to chromium..., 2012-07-19 00:08:11]

On 2012/07/18 21:38:31, jvoung (chromium) wrote:
> still testing, but at least smoke tests pass

ah hold on... this seems to break the arm self-compile (segfault after writing
the .o out ???)

[jvoung (off chromium), 2012-07-24 21:42:05]

On 2012/07/19 00:08:11, jvoung wrote:
> On 2012/07/18 21:38:31, jvoung (chromium) wrote:
> > still testing, but at least smoke tests pass
> 
> ah hold on... this seems to break the arm self-compile (segfault after writing
> the .o out ???)

I think this might be tickling some var-arg bug on ARM. From some debug printfs
I see:

In IntrinsicLowering::AddPrototypes memset

In Module::getOrInsertFunction (Name=<E8><86><E1>^@^N^@^@^@^A^@^@^@<90> ...
Whole bunch of junk instead of just "memset" ..., ..., ...)

In Module::getOrInsertFunction va_start'ed
In Module::getOrInsertFunction pushing va_arg: 0x6     // This doesn't look like
a nice pointer address at all...
In Module::getOrInsertFunction pushing va_arg: 0xe6970
In Module::getOrInsertFunction pushing va_arg: 0xe10a80
In Module::getOrInsertFunction pushing va_arg: 0xe19a4c
In Module::getOrInsertFunction pushing va_arg: 0xe19a4c
In Module::getOrInsertFunction va_ended


Where the prototype for getOrInsertFunction is:

Constant *Module::getOrInsertFunction(StringRef Name,
                                      Type *RetTy, ...);

[jvoung (off chromium), 2012-08-01 00:02:41]

Newer version, now that arm self-build works.

Some data: ~jvoung/linktimes.before ~jvoung/linktimes.after to see the diff in
times and max RSS for spec2k.

E.g.,

gcc 4.85s -> 2.02s, but ~500MB -> ~725MB

[robertm, 2012-08-01 14:02:31]

LGTM

neat!

some requests for more commenting below

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
File llvm/tools/lto/LTOCodeGenerator.cpp (right):

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:106: bool
LTOCodeGenerator::gatherModule(LTOModule* mod) {
gather is no a very specific term.
Maybe add a comment or use a better function name:
e.g. :
// Add module to list of modules which are part of the "linked" image.
// Note: the link does not happen right away but is delayed 
// so that we can optimize this rather costly step

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:111: // We gather the asm undefs earlier
than addModule() does,
since the llvm folks did not seem to have commented this asm undef stuff.
Could you describe in a comment what you have learned about that.

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:124: // will be Module 0.
not sure whether this adds all that much:
After the first round (stride = 1) only modules with even index are still there,
after the second round (stride = 2) only the modules with indices divisible by 4
are still there, etc. 


If you can find some algorithmic reference that would be even better. 
Also say that we disregard module sizes for now.

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:127: while (stride < len) {
why not use a for loop here as well

[robertm, 2012-08-01 14:28:38]

One more question: is it essential that we only merge adjacent modules?


On 2012/08/01 14:02:31, robertm wrote:
> LGTM
> 
> neat!
> 
> some requests for more commenting below
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> File llvm/tools/lto/LTOCodeGenerator.cpp (right):
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:106: bool
> LTOCodeGenerator::gatherModule(LTOModule* mod) {
> gather is no a very specific term.
> Maybe add a comment or use a better function name:
> e.g. :
> // Add module to list of modules which are part of the "linked" image.
> // Note: the link does not happen right away but is delayed 
> // so that we can optimize this rather costly step
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:111: // We gather the asm undefs earlier
> than addModule() does,
> since the llvm folks did not seem to have commented this asm undef stuff.
> Could you describe in a comment what you have learned about that.
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:124: // will be Module 0.
> not sure whether this adds all that much:
> After the first round (stride = 1) only modules with even index are still
there,
> after the second round (stride = 2) only the modules with indices divisible by
4
> are still there, etc. 
> 
> 
> If you can find some algorithmic reference that would be even better. 
> Also say that we disregard module sizes for now.
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:127: while (stride < len) {
> why not use a for loop here as well

[jvoung (off chromium), 2012-08-01 17:11:01]

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
File llvm/tools/lto/LTOCodeGenerator.cpp (right):

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:106: bool
LTOCodeGenerator::gatherModule(LTOModule* mod) {
On 2012/08/01 14:02:31, robertm wrote:
> gather is no a very specific term.
> Maybe add a comment or use a better function name:
> e.g. :
> // Add module to list of modules which are part of the "linked" image.
> // Note: the link does not happen right away but is delayed 
> // so that we can optimize this rather costly step

renamed to gatherModuleForLink(), but yeah, not sure what is best.  Added some
comments though.

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:111: // We gather the asm undefs earlier
than addModule() does,
On 2012/08/01 14:02:31, robertm wrote:
> since the llvm folks did not seem to have commented this asm undef stuff.
> Could you describe in a comment what you have learned about that.

Added some comments.  Hopefully this is a constant array that is not modified by
merging.  It looks like it is a "char*" of some global's name coming straight
from ASM, so that shouldn't be interpreted and changed by llvm???

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:124: // will be Module 0.
On 2012/08/01 14:02:31, robertm wrote:
> not sure whether this adds all that much:
> After the first round (stride = 1) only modules with even index are still
there,
> after the second round (stride = 2) only the modules with indices divisible by
4
> are still there, etc. 
> 
> 
> If you can find some algorithmic reference that would be even better. 
> Also say that we disregard module sizes for now.

Done.

http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
llvm/tools/lto/LTOCodeGenerator.cpp:127: while (stride < len) {
On 2012/08/01 14:02:31, robertm wrote:
> why not use a for loop here as well

Done.

http://codereview.chromium.org/10808021/diff/10001/llvm/tools/gold/gold-plugi...
File llvm/tools/gold/gold-plugin.cpp (right):

http://codereview.chromium.org/10808021/diff/10001/llvm/tools/gold/gold-plugi...
llvm/tools/gold/gold-plugin.cpp:134: gather_then_link = false;
changed this flag to be "no-gather-..." so that one could turn it back to the
original behavior, since I had set it on by default.

[robertm, 2012-08-01 17:24:37]

LGTM (still)

On 2012/08/01 17:11:01, jvoung (chromium) wrote:
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> File llvm/tools/lto/LTOCodeGenerator.cpp (right):
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:106: bool
> LTOCodeGenerator::gatherModule(LTOModule* mod) {
> On 2012/08/01 14:02:31, robertm wrote:
> > gather is no a very specific term.
> > Maybe add a comment or use a better function name:
> > e.g. :
> > // Add module to list of modules which are part of the "linked" image.
> > // Note: the link does not happen right away but is delayed 
> > // so that we can optimize this rather costly step
> 
> renamed to gatherModuleForLink(), but yeah, not sure what is best.  Added some
> comments though.
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:111: // We gather the asm undefs earlier
> than addModule() does,
> On 2012/08/01 14:02:31, robertm wrote:
> > since the llvm folks did not seem to have commented this asm undef stuff.
> > Could you describe in a comment what you have learned about that.
> 
> Added some comments.  Hopefully this is a constant array that is not modified
by
> merging.  It looks like it is a "char*" of some global's name coming straight
> from ASM, so that shouldn't be interpreted and changed by llvm???
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:124: // will be Module 0.
> On 2012/08/01 14:02:31, robertm wrote:
> > not sure whether this adds all that much:
> > After the first round (stride = 1) only modules with even index are still
> there,
> > after the second round (stride = 2) only the modules with indices divisible
by
> 4
> > are still there, etc. 
> > 
> > 
> > If you can find some algorithmic reference that would be even better. 
> > Also say that we disregard module sizes for now.
> 
> Done.
> 
>
http://codereview.chromium.org/10808021/diff/5001/llvm/tools/lto/LTOCodeGener...
> llvm/tools/lto/LTOCodeGenerator.cpp:127: while (stride < len) {
> On 2012/08/01 14:02:31, robertm wrote:
> > why not use a for loop here as well
> 
> Done.
> 
>
http://codereview.chromium.org/10808021/diff/10001/llvm/tools/gold/gold-plugi...
> File llvm/tools/gold/gold-plugin.cpp (right):
> 
>
http://codereview.chromium.org/10808021/diff/10001/llvm/tools/gold/gold-plugi...
> llvm/tools/gold/gold-plugin.cpp:134: gather_then_link = false;
> changed this flag to be "no-gather-..." so that one could turn it back to the
> original behavior, since I had set it on by default.