Re: [whopr] Design/implementation alternatives for the driver and WPA
On Jun 4, 2008, at 12:44 PM, Ian Lance Taylor wrote:
Chris Lattner <[EMAIL PROTECTED]> writes:
* The return value of lto_module_get_symbol_attributes is not
defined.
Ah, sorry about that. Most of the details are actually in the public
header. The result of this function is a 'lto_symbol_attributes'
bitmask. This should be more useful and revealing:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm-c/lto.h?revision=HEAD&view=markup
From an ELF perspective, this doesn't seem to have a way to indicate a
common symbol, and it doesn't provide the symbol's type.
The current lto interface does return whether a symbol is
REGULAR, TENTATIVE, WEAK_DEF, or UNDEFINED. There is also
CODE vs DATA which could be used to indicate STT_FUNC vs STT_OBJECT.
It also
doesn't have a way to indicate section groups.
(How do section groups work in Mach-O? Example is a C++ template
function with a static constant array which winds up in the .rodata
section. Section groups permit discarding the array when we discard
the function code.)
Neither mach-o or llvm have group comdat. We just rely on dead code
stripping.
If the temple function was coalesced away, there would no longer be
a reference to that static const array, so it would get dead stripped.
Dead stripping is an important pass in LTO.
* Interfaces like lto_module_get_symbol_name and
lto_codegen_add_must_preserve_symbol are inefficient when dealing
with large symbol tables.
The intended model is for the linker to query the LTO plugin for its
symbol list and build up its own linker-specific hash table. This
way
you don't need to force the linker to use the plugin's data structure
or the plugin to use the linker data structure. We converged on this
approach after trying it the other way.
Does this make sense, do you have a better idea?
In gcc's LTO approach, I think the linker will already have access to
the symbol table anyhow. But my actual point here is that requiring a
function call for every symbol is inefficient. These functions should
take an array and a count. There can be hundreds of thousands of
entries in a symbol table, and the interface should scale accordingly.
I see you have your gold hat on here! The current interface is
simple and clean. If it does turn out that repeated calls to
lto_module_get_symbol*
are really a bottleneck, we could add a "bulk" function.
The LLVM
interface does not do that.
Yes it does, the linker fully handles symbol resolution in our model.
Suppose the linker is invoked on a
sequence of object files, some with with LTO information, some
without, all interspersed. Suppose some symbols are defined in
multiple .o files, through the use of common symbols, weak symbols,
and/or section groups. The LLVM interface simply passes each object
file to the plugin.
No, the native linker handles all the native .o files.
The result is that the plugin is required to do
symbol resolution itself. This 1) loses one of the benefits of
having
the linker around; 2) will yield incorrect results when some non-LTO
object is linked in between LTO objects but redefines some earlier
weak symbol.
In the LLVM LTO model, the plugin only needs to know about its .o
files, and the linker uses this information to reason about symbol
merging etc. The Mac OS X linker can even do dead code stripping
across Macho .o files and LLVM .bc files.
To be clear, when I said object file here, I meant any input file.
You may have understood that.
In ELF you have to think about symbol overriding. Let's say you link
a.o b.o c.o. a.o has a reference to symbol S. b.o has a strong
definition. c.o has a weak definition. a.o and c.o have LTO
information, b.o does not. ELF requires that a.o call the symbol from
b.o, not the symbol from c.o. I don't see how to make that work with
the LLVM interface.
This does work. There are two parts to it. First the linker's master
symbol
table sees the strong definition of S in b.o and the weak in c.o and
decides to use the strong one from b.o. Second (because of that) the
linker
calls lto_codegen_add_must_preserve_symbol("S"). The LTO engine then
sees it has a weak global function S and it cannot inline those. Put
together
the LTO engine does generate a copy of S, but the linker throws it away
and uses the one from b.o.
-Nick
Re: [whopr] Design/implementation alternatives for the driver and WPA
On Jun 4, 2008, at 1:45 PM, Ian Lance Taylor wrote:
The result is that the plugin is required to do
symbol resolution itself. This 1) loses one of the benefits of
having
the linker around; 2) will yield incorrect results when some non-
LTO
object is linked in between LTO objects but redefines some earlier
weak symbol.
In the LLVM LTO model, the plugin only needs to know about its .o
files, and the linker uses this information to reason about symbol
merging etc. The Mac OS X linker can even do dead code stripping
across Macho .o files and LLVM .bc files.
To be clear, when I said object file here, I meant any input file.
You may have understood that.
In ELF you have to think about symbol overriding. Let's say you
link
a.o b.o c.o. a.o has a reference to symbol S. b.o has a strong
definition. c.o has a weak definition. a.o and c.o have LTO
information, b.o does not. ELF requires that a.o call the symbol
from
b.o, not the symbol from c.o. I don't see how to make that work
with
the LLVM interface.
This does work. There are two parts to it. First the linker's
master
symbol
table sees the strong definition of S in b.o and the weak in c.o and
decides to use the strong one from b.o. Second (because of that) the
linker
calls lto_codegen_add_must_preserve_symbol("S"). The LTO engine then
sees it has a weak global function S and it cannot inline those. Put
together
the LTO engine does generate a copy of S, but the linker throws it
away
and uses the one from b.o.
OK, for that case. But are you asserting that this works in all
cases? Should I come up with other examples of mixing LTO objects
with non-LTO objects using different types of symbols?
I don't claim our current implementation is bug free, but the lto
interface
matches the Apple linker internal model, so we don't expect and have
not encountered any problems mixing mach-o and llvm bitcode files.
-Nick
Re: [whopr] Design/implementation alternatives for the driver and WPA
On Jun 4, 2008, at 5:00 PM, Ian Lance Taylor wrote: Nick Kledzik <[EMAIL PROTECTED]> writes: I don't claim our current implementation is bug free, but the lto interface matches the Apple linker internal model, so we don't expect and have not encountered any problems mixing mach-o and llvm bitcode files. Hmmm, OK, how about this example: a.o: contains LTO information, refers to S b.o: no LTO information, defines S c.o: contains LTO information, defines S at version V, S/V is not hidden In the absence of b.o, the reference to S in a.o will be resolved against the definition of S in c.o. In the presence of b.o, the reference to S in a.o will be resolved against the definition of S in b.o. I suppose we could refuse to inline versioned symbols, but that doesn't seem desirable since it is normally fine. As Chris mentioned earlier today, the Apple tool chain does not support versioned symbols. But if versioned symbols are a naming convention (that is everything is encoded in the symbol name), then this would work the same as your previous example. Namely, the linker would coalesce away S in c.o, which in turns tell the LTO engine that it can't inline/optimize away c.o's S and after LTO is done, the linker throws away the LTO generated S and uses b.o's S instead. -Nick On Jun 4, 2008, at 9:29 AM, Chris Lattner wrote: When I look at the LLVM interface as described on that web page, I see these issues, all fixable: * No support for symbol versioning. Very true. I think it would great to work from a common model that can be extended to support both compilers. Having a unified interface would be very useful, and we are happy to evolve the interface to suit more general needs.
Re: [whopr] Design/implementation alternatives for the driver and WPA
On Jun 4, 2008, at 5:39 PM, Ian Lance Taylor wrote:
Nick Kledzik <[EMAIL PROTECTED]> writes:
On Jun 4, 2008, at 5:00 PM, Ian Lance Taylor wrote:
Nick Kledzik <[EMAIL PROTECTED]> writes:
I don't claim our current implementation is bug free, but the lto
interface
matches the Apple linker internal model, so we don't expect and
have
not encountered any problems mixing mach-o and llvm bitcode files.
Hmmm, OK, how about this example:
a.o: contains LTO information, refers to S
b.o: no LTO information, defines S
c.o: contains LTO information, defines S at version V, S/V is not
hidden
In the absence of b.o, the reference to S in a.o will be resolved
against the definition of S in c.o. In the presence of b.o, the
reference to S in a.o will be resolved against the definition of S
in
b.o.
I suppose we could refuse to inline versioned symbols, but that
doesn't seem desirable since it is normally fine.
As Chris mentioned earlier today, the Apple tool chain does not
support versioned symbols.
But if versioned symbols are a naming convention (that is everything
is encoded in
the symbol name), then this would work the same as your previous
example. Namely,
the linker would coalesce away S in c.o, which in turns tell the LTO
engine that it
can't inline/optimize away c.o's S and after LTO is done, the linker
throws away
the LTO generated S and uses b.o's S instead.
Versioned symbols are not a naming convention, but they aren't all
that different from one. Basically every symbol may have an optional
version, and when a symbol has a version the version may be hidden or
not. A symbol definition with a hidden version may only be matched by
a symbol reference with that exact version. A symbol definition with
a non-hidden version definition may be matched by a symbol reference
with the same name without a version. This is most interesting in the
dynamic linker, of course.
How does the linker inform the plugin that the plugin is not permitted
to use c.o's S?
In the previous case where S was weak, the call to
lto_codegen_add_must_preserve_symbol("S")
caused the LTO engine to know it could not inline S (because it was
a weak definition and used outside the LTO usage sphere). And then
after LTO was done, the linker threw away the LTO produced S and used
the one from c.o instead.
In this case S is a regular symbol. So the previous trick won't
work. Probably
the best solution would be to add a new lto_ API to tell the LTO
engine to
ignore a definition is already has. It would make more sense to use
this
new API in the weak case too.
-Nick
Re: [whopr] Design/implementation alternatives for the driver and WPA
On Jun 5, 2008, at 10:43 AM, Ian Lance Taylor wrote: Chris Lattner <[EMAIL PROTECTED]> writes: LLVM LTO handles this by marking symbols "internal" (aka static, aka not TREE_PUBLIC, whatever) when the symbol is not visible outside the LTO scope. This allows the optimizers to go crazy and hack away at the symbols, but only when safe. How does the linker do this? Are you saying that when generating a shared library, the linker calls lto_codegen_add_must_preserve_symbol for every externally visible symbol? Yes. How does the linker tell LTO that a symbol may be inlined, but must also be externally visible? The linker just tells LTO which symbols must remain. The LTO engine is free to inline anything that would improve codegen, with the exception that any weak definition that must remain (preserved) cannot be inlined. -Nick
