[llvm-dev] RFC [ThinLTO]: Promoting more aggressively in order to reduce incremental link time and allow sharing between linkage units

Wed May 4 08:55:32 PDT 2016

On Wed, May 4, 2016 at 8:47 AM, Peter Collingbourne <peter at pcc.me.uk> wrote:

>
>
> On Wed, May 4, 2016 at 8:19 AM, David Blaikie <dblaikie at gmail.com> wrote:
>
>>
>>
>> On Wed, Apr 6, 2016 at 4:41 PM, Peter Collingbourne via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Hi all,
>>>
>>> I'd like to propose changes to how we do promotion of global values in
>>> ThinLTO. The goal here is to make it possible to pre-compile parts of the
>>> translation unit to native code at compile time. For example, if we know
>>> that:
>>>
>>> 1) A function is a leaf function, so it will never import any other
>>> functions, and
>>> 2) The function's instruction count falls above a threshold specified at
>>> compile time, so it will never be imported.
>>> or
>>> 3) The compile-time threshold is zero, so there is no possibility of
>>> functions being imported (What's the utility of this? Consider a program
>>> transformation that requires whole-program information, such as CFI. During
>>> development, the import threshold may be set to zero in order to minimize
>>> the incremental link time while still providing the same CFI enforcement
>>> that would be used in production builds of the application.)
>>>
>>> then the function's body will not be affected by link-time decisions,
>>> and we might as well produce its object code at compile time. This will
>>> also allow the object code to be shared between linkage units (this should
>>> hopefully help solve a major scalability problem for Chromium, as that
>>> project contains a large number of test binaries based on common libraries).
>>>
>>> This can be done with a change to the intermediate object file format.
>>> We can represent object files as native code containing statically compiled
>>> functions and global data in the .text,. data, .rodata (etc.) sections,
>>> with an .llvmbc section (or, I suppose, "__LLVM, __bitcode" when targeting
>>> Mach-O) containing bitcode for functions to be compiled at link time.
>>>
>>> In order to make this work, we need to make sure that references from
>>> link-time compiled functions to statically compiled functions work
>>> correctly in the case where the statically compiled function has internal
>>> linkage. We can do this by promoting every global value with internal
>>> linkage, using a hash of the external names (as I mentioned in [1]).
>>>
>>
>> What about translation units that have no external names? I hit this
>> problem with DWARF Fission hashing recently, where two files had code
>> equivalent to this:
>>
>>   struct foo { foo(); }
>>   static foo f;
>>
>> Thus no external symbols, and indeed exactly the same set of symbols for
>> two instances of this file (& I have seen examples of this in Google's
>> codebase - though I haven't searched extensively, and it may be that the
>> linker never actually picks two of these together, but the DWP tool doesn't
>> have the same kind of "skip this library if no symbols are needed from it"
>> behavior as the linker).
>>
>
> Yes, I came across this case in my prototype. This can happen if two such
> TUs appear directly as linker inputs (rather than as library members). This
> is a rare case, and the code in such a TU is most likely initialization
> code that does not require extensive optimization, so the solution I
> decided on was to inhibit ThinLTO for such modules. In my prototype, I
> caused such modules to be compiled with regular LTO, but there are other
> possible solutions, such as compiling to a native object.
>

Fair enough

>
> Also, (I haven't read the whole thread, but I assume) you're considering
>> doing this with debug info too? All type information could pretty easily be
>> emitted up-front and just reduced to declarations (again, on non-LLDB
>> platforms... :/) for the rest of the debug info. The extra declarations
>> might make object files a bit bigger, though. (eg: if there were types that
>> weren't used in any of the ahead-of-time compiled code, but were used in
>> the ThinLTO'd code - the naive approach would still produce the type info
>> up front and a declaration in ThinLTO which would make for bigger output
>> than just putting the type in the ThinLTO'd code - but it would potentially
>> improve parallelism by reducing the amount of type goo needing to be
>> imported/exported/emitted during ThinLTO)
>>
>
> That's an interesting idea. I hadn't thought about just emitting type
> declarations in the ThinLTO'd code but yes, that's something we could
> consider doing. It would be interesting to see what the tradeoff would be
> in terms of the edit/compile/debug cycle time, as we'd be exchanging linker
> work for debugger work.
>

Potentially, yes - it's certainly a tradeoff we already make to reduce
debug info size (the default (on non-LLDB platforms) of
-fno-standalone-debug causes type definitions to be emitted only along with
the vtable for types with vtables, only where a type is required to be
complete (so if you just use pointers to a type, etc you get a
declaration), and only along with a template explicit instantiation
definition if the type has an explicit instantiation declaration) - so I
think this would be consistent with that, but it would be more aggressive,
to be sure. I'm not sure what sort of GDB performance infrastructure we
have available to get better numbers on this.

- David

>
> Peter
>
>
>
>>
>>
>>>
>>> I imagine that for some linkers, it may not be possible to deal with
>>> this scheme. For example, I did some investigation last year and discovered
>>> that I could not use the gold plugin interface to load a native object file
>>> if we had already claimed it as an IR file. I wouldn't be surprised to
>>> learn that ld64 has similar problems.
>>>
>>> In cases where we completely control the linker (e.g. lld), we can
>>> easily support this scheme, as the linker can directly do whatever it
>>> wants. But for linkers that cannot support this, I suggest that we promote
>>> consistently under ThinLTO rather than having different promotion schemes
>>> for different linkers, in order to reduce overall complexity.
>>>
>>> Thanks for your feedback!
>>>
>>> Thanks,
>>> --
>>> --
>>> Peter
>>>
>>> [1] http://lists.llvm.org/pipermail/llvm-dev/2016-April/098062.html
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>>
>>
>
>
> --
> --
> Peter
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160504/212b5e80/attachment.html>