As mentioned in the Updated ThinLTO RFC (
http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/086211.html), I am
sending the symbol linkage and renaming required by ThinLTO as a separate
RFC. It is included below. I've also attached the doc in pdf form, since
the formatting (especially for the table at the end) may not come through
in the copied text below well.
Thanks!
Teresa
ThinLTO Symbol Linkage and Renaming
1 Introduction
2 Non-Discardable Values
2.2 Linkage Effects
2.2.2 ExternalLinkage
2.2.1 WeakAnyLinkage
2.2.2 WeakODRLinkage
2.2.3 AppendingLinkage
2.2.4 CommonLinkage
3 Linkonce Values
3.1 Linkage Effects
3.2 Importing Strategy
4 Static Values
4.1 Static Variables
4.2 Static Functions
4.3 Static Promotion
4.3.1 Linkage Effects
4.3.2 Renaming
5 Linkage Change Summary Table
1 Introduction
This document describes handling of symbols that may need linkage type
changes or renaming to support ThinLTO importing.This applies to both the
symbol in its original module as well as in the module importing it.
In LLVM, the GlobalValue class is used to represent function, variable and
alias symbols. The Function and GlobalVariable classes are both derived
from the GlobalObject class which itself is derived from GlobalValue. The
GlobalAlias class is derived directly from GlobalValue. Note that LLVM
GlobalValues include static variables and functions in C/C++.
During ThinLTO importing of a function from another module, the symbols
from that module are parsed and imported as either a declaration or
definition. Note that while we are importing one function at a time from
another module, we typically always import all variable definitions (the
one exceptions are variables with AppendingLinkage and WeakAnyLinkage, as
described in Section 2.2).
The following sections discuss the handling of values with the given
original linkage types (in the original module). The effects on the linkage
type in both the original module and in the imported copy in another module
are described.
2 Non-Discardable Values
Non-discardable values are those that cannot be discarded by a module even
when the value is unreferenced, i.e. it may be referenced by another
module. This includes all linkage types except local (internal or private)
and linkonce. For these values (both variables and functions), a reference
may be imported into another module without fear that its definition may be
eliminated in the original module. As a result, when the definitions of
these non-discardable values are imported, the imported copy may safely be
eliminated after optimizations such as inlining, as a copy is guaranteed to
be available in the original module. In practice we may not eliminate these
imported definitions, as discussed below, depending on the linkage type
handling in the imported copy.
2.2 Linkage Effects
There is no change to the linkage type required in the original module for
any non-discardable values that may be imported to another module.
During importing, ideally all non-discardable definitions have their
linkage type changed in the imported copy to AvailableExternallyLinkage.
This signals to the compiler that the definition can safely be eliminated
after inlining (i.e. by the new EliminateAvailableExternally pass). In
practice, we do not change the linkage for all imported non-discardable
defs. The linkage effects for the non-discardable linkage types are
described below:
2.2.2 ExternalLinkage
An imported ExternalLinkage definition can be changed to
AvailableExternallyLinkage. If it is eliminated later by the
EliminateAvailableExternally pass, the resulting decl becomes
ExternalLinkage.
2.2.1 WeakAnyLinkage
Importing a WeakAnyLinkage definition could change the result of the
program as it could cause a different weak definition to be selected by the
linker. WeakAnyLinkage can be specified via __attribute__ ((weak)) on a
function definition, to allow overriding by a strong definition in another
module. If no strong definition exists, the linker will select the first
weak definition. Importing a weak definition into a different module can
change the order the weak defs are seen by the linker and change the
program semantics. Therefore, any WeakAnyLinkage definitions are only
imported as declarations, which are given ExternalWeakLinkage. WeakAny
aliases are handled similarly (imported as ExternalWeakLinkage aliases).
2.2.2 WeakODRLinkage
For WeakODRLinkage, there is a guarantee that all copies will be
equivalent, so the issue described above for WeakAny does not exist, and
the definition can be imported. For WeakODRLinkage, the imported definition
should retain the original WeakODRLinkage. If imported as a declaration, it
should instead have ExternalWeakLinkage.
WeakODRLinkage symbols cannot be marked AvailableExternallyLinkage, because
if the def is later dropped (by the EliminateAvailableExternally pass), the
new decl is marked ExternalLinkage. For these weak symbols, however, the
correct linkage for the decl is actually ExternalWeakLinkage, so that they
get treated appropriately by the linker. But the information about their
original weak linkage would be gone once they were changed to
AvailableExternallyLinkage. For now, since weak symbols are expected to be
uncommon, we will leave these symbols with their original weak linkage,
which means they will not be discardable in the imported destination. If
this becomes a problem, we can investigate retaining information about the
original linkage type.
2.2.3 AppendingLinkage
This applies to special variables such as the global constructors and
destructors lists. We never import these as they would get executed
multiple times, which is incorrect.
2.2.4 CommonLinkage
Since common symbols are always zero-initialized variables, they do not
take up room. It is simplest to import these defs as common.
3 Linkonce Values
The LinkOnceODRLinkage and LinkOnceAnyLinkage types refer to linkonce
linkage, which allows merging of different globals with the same name.
Unreferenced linkonce globals may also be discarded. Linkonce values
include some COMDAT functions (COMDAT may also have Weak linkage) and
vtable variables. For linkonce values, duplicates are allowed and the
linker selects one.
3.1 Linkage Effects
Since duplicates are allowed and the linkonce values are already
discardable, imported linkonce values can remain linkonce in the imported
copy. Any duplicate imported copy will be handled by the linker, and it may
remain discardable in the importing module if it isn’t referenced after
importing/inlining.
Similarly, there is also no change in linkage type required in the original
module.
3.2 Importing Strategy
The main issue with linkonce values is that they are discardable in the
original module (e.g. if all references are inlined in the original
module). However, ThinLTO importing may introduce a cross-module reference
to a linkonce value in the original module. Care must be taken to ensure
that such a reference imported into another module is satisfied at link
time by a definition somewhere. To handle this for linkonce functions, the
ThinLTO importer must force-import any linkonce functions referenced by
another imported function. To do this, after importing a function, the
ThinLTO importer walks all newly imported operations looking for references
to functions with linkonce linkage type. Any found are also imported, along
with functions and variables in the same COMDAT group (note the COMDAT
group must always be imported in its entirety regardless of whether it has
linkonce or weak linkage). For linkonce variables, since GlobalVariable
definitions are always imported when we import a function from the same
module as described in the introduction, the linkonce variable definitions
are therefore imported and available.
4 Static Values
File static functions and variables have local linkage types (i.e. internal
or private), and are discardable. These values need special handling during
importing as described below. The local linkage types InternalLinkage and
PrivateLinkage (private is the same as internal but is omitted from the
symbol table) are handled the same for ThinLTO.
4.1 Static Variables
Read-write or address taken static variables must always be promoted to
global scope (i.e. non-discardable, non-local linkage) if they are imported
to another module. This is important to ensure that one single copy of the
static variable is used in address comparisons or when updating its value.
The mechanics of static promotion are described below in Section 4.3.
A static (local linkage) variable marked as a read-only (marked constant by
LLVM) need not be promoted/renamed, unless it is address taken as described
above. The imported copy of its definition can simply be used by any
imported references in the read-only non-address taken case.
4.2 Static Functions
When a reference to a static (local linkage) function is imported, in order
to satisfy the imported reference, there are two possible strategies:
1. The function must be promoted to global scope (i.e. non-local linkage)
both in its original module (where it is no longer discardable) and in the
importing module; OR
2. The static function definition must also be imported into the same
importing module, so that a local copy is available for the reference.
The strategy to be used for a particular function will ultimately depend on
several factors such as whether it is address taken, its size, etc. This is
discussed in more detail further on.
Note that address taken static functions must always be promoted for
correctness. The reason can be seen with the following example:
a.cc:
static void foo() { … };
static funcptr P;
void bar() {
if (P == &foo) {
...
}
}
void baz() {
P = &foo;
}
b.cc:
… bar(); …
If bar() is imported into b.cc (and gets inlined), then b.cc will have a
reference to static foo(). It we then import foo() and leave the imported
copy local/unpromoted, the imported P==&foo comparison will fail (assume
baz() is not referenced by or imported into b.cc). That is because P will
point to the a.cc::foo() and the imported comparison will compare against
the imported copy b.cc::foo(). This is avoided by promoting address taken
static functions, in both their original module (if the function is in the
global function index) and when it has been imported along with an address
taken reference into another module. Similar logic applies to read-only
static variables as mentioned in Section 4.1.
The mechanics of static promotion are described later in Section 4.3.
It is important to note that the promotion decisions between the original
module and the importing module must be consistent (it is ok for the
function to be promoted in the original module but not in the importing
module, but not vice versa, or we will have an undefined reference
reference at link time). However, the original module and importing modules
are compiled independently through the ThinLTO phase-3 parallel backend.
There are several ways to ensure consistent promotion. Two of the simplest
are:
1. Always promote imported static functions
a. When importing a static function reference or definition, always
promote the imported value
b. In the original module, promote any static functions that may be
imported into another module (any static functions in the global function
index/summary map)
2. Minimize static promotions by only promoting address taken static
functions
a. When a function is imported, look through newly imported instructions
and force import any referenced static functions.
b. When importing is complete, any imported static functions that are
address taken must be promoted
c. In the original module, promote any static functions that are address
taken.
Strategy 1 (always promote) has the disadvantage in that it potentially
results in a larger symbol table, due to promoted functions no longer being
discardable. However, in practice (based on cpu2006 measurements) this does
not turn out to be a significant issue.
Strategy 2 (promote only address taken) has the disadvantage in that it can
increase code size, in the case where imported unpromoted static functions
are not inlined into all call sites in the imported module, and we end up
with multiple copies. This turns out to be a more significant issue for a
couple of cpu2006 benchmarks, notably 400.perlbench. However, this can be
alleviated by enabling function sections and linker garbage collection.
A third intermediate strategy would be to promote static functions that are
either address-taken or unlikely to be fully inlined. Large or cold static
functions are unlikely to be inlined, and are therefore unlikely to be
imported anyway. Therefore, the plugin should not even include these
functions in the combined function summary (based on metrics such as
function size or hotness). Any static function that is not in the combined
index will therefore not be eligible for importing, and should be promoted.
So both the original module and the importing module will consult the
combined function summary for each static function to see whether it should
be static promoted (if entry not found) vs force imported (if entry found).
This can be refined further to static promote a address taken and/or
non-importable static function in the original module only if it is
referenced by a function that is found in the map (because the reference
may be imported into another module). This is summarized below:
3. Promote only address taken static functions and those not enabled for
importing by the plugin
a. When a function is imported, look through newly imported instructions
and identify any referenced static functions. If the referenced static
function is found in the function summary, force import it. Otherwise,
promote it.
b. When importing is complete, any imported (and therefore unpromoted)
static functions that are address taken must be promoted
c. In the original module, promote any static functions that either:
i. are address taken; or
ii. may not be imported into another module (any static functions
not in the global function index/summary map)
iff they are referenced by a function that may be imported into
another module.
Given the results of experiments with cpu2006, we will initially implement
strategy 1 (always promote). This is also the simplest strategy.
4.3 Static Promotion
Promoting a static variable or function to non-local/non-static requires
two main changes: changing the linkage and ensuring consistent naming
between the definition in the original module and references in importing
modules.
4.3.1 Linkage Effects
The linkage of static functions and variables are changed are as follows:
* Definition in the original module: ExternalLinkage
* Definition in the importing module: AvailableExternallyLinkage
* Declaration in the importing module (i.e. def not imported):
ExternalLinkage
Note that in the importing module the new linkage type of the promoted
function/variable definition is the same as for non-discardable (non-local,
non-linkonce) ExternalLinkage symbols as described in Section 2.
4.3.2 Renaming
Since there may be multiple static functions from different modules with
the same name before importing/promotion, or a global function which
already has the same name, the promoted static functions must be renamed to
avoid naming conflicts. It is important that the promoted definition in the
original module is given the same name as the promoted reference in the
importing module, so that the reference in the importing module can be
satisfied by the original module at link time.
To do the renaming consistently, we can include a module-specific
identifier in the new name. The plugin step in phase-2 of ThinLTO (which
builds the combined function index/summary) has visibility into all modules
included in the ThinLTO build. It can simply number the modules and record
the assigned module ID in the function summary information (either along
with each function from that module, or along with the module name which
will be shared in a module string table for efficiency). Then during
promotion, the module ID in the combined function index/summary can be
consulted and appended to the original name, along with an LLVM-specific
suffix identifying this as a promoted static.
For example,
static void foo(); // In module with ID 1
originally has bitcode definition in module ID 1:
define internal void @foo() // InternalLinkage
which becomes after promotion/renaming:
define void @foo.llvm.1() // ExternalLinkage, new suffix “.llvm.1”
When we import a static definition into another module (say module ID 2),
before promotion it has declaration:
define internal void @foo() // InternalLinkage, func summary
info: from Module ID 1
which becomes after promotion/renaming:
define available_externally void @foo.llvm.1() //
AvailableExternallyLinkage, new suffix “.llvm.1”
If a reference is imported but not the definition, before promotion the new
declaration is:
declare internal void @foo() // InternalLinkage, func summary info:
from Module ID 1
which becomes after promotion/renaming:
declare void @foo.llvm.1() // ExternalLinkage, new suffix “.llvm.1”
Note that the new EliminateAvailableExternallyPass (under review) will
change the linkage type from AvailableExternallyLinkage to ExternalLinkage
on the declaration it leaves for any eliminated available externally
definitions, which is consistent with the above behavior.
5 Linkage Change Summary Table
The following table summarizes the linkage change that happen during
ThinLTO backend compilations. Note that the only time the linkage changes
in the original module is for the static promotion case (for Internal and
Private linkages), where it changes to External as described in Section
4.3.1. In all other cases the linkage in the original module stays the
same, and therefore is not noted in the table below.
Note that there are no InternalLinkage, PrivateLinkage,
AvailableExternallyLinkage, LinkOnce*Linkage, Weak*Linkage,
AppendingLinkage and CommonLinkage declarations. There are no
ExternalWeakLinkage definitions.
+---------------------------------+------------------------------------------------+
| | Importing Module Linkage
|
| Original Module
+----------------------+-------------------------+
| | Import definition | Import as
declaration |
+----------------------------------------------------------------------------------+
| External (def) | AvailableExternally | External
|
+----------------------------------------------------------------------------------+
| External (decl) | N/A | External
|
+----------------+-----------------------------------------------------------------+
| | Promote[1] | AvailableExternally | External
|
| Internal (def)
+-----------------------------------------------------------------+
| | NoPromote | Internal | N/A (force
import def) |
+----------------------------------------------------------------------------------+
| | Promote[1] | AvailableExternally | External
|
| Private (def)
+-----------------------------------------------------------------+
| | NoPromote | Private | N/A (force
import def) |
+----------------+-----------------------------------------------------------------+
| AvailableExternally (def) | AvailableExternally | External
|
+----------------------------------------------------------------------------------+
| LinkOnceAny (def) | LinkOnceAny | N/A (force
import def) |
+----------------------------------------------------------------------------------+
| LinkOnceODR (def) | LinkOnceODR | N/A (force
import def) |
+----------------------------------------------------------------------------------+
| WeakAny (def) | N/A (never import) | ExternalWeak
|
+----------------------------------------------------------------------------------+
| WeakODR (def) | WeakODR | ExternalWeak
|
+----------------------------------------------------------------------------------+
| Appending (def) (only variables)| N/A (never import) | N/A (never
import) |
+----------------------------------------------------------------------------------+
| ExternalWeak (decl) | N/A | ExternalWeak
|
+----------------------------------------------------------------------------------+
| Common (def) (only variables) | Common | N/A (always
import def)|
+---------------------------------+----------------------+-------------------------+
[1] Linkage in original module changes to External
--
Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/3a3aad72/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ThinLTOSymbolLinkageandRenaming.pdf
Type: application/pdf
Size: 216110 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150714/3a3aad72/attachment.pdf>
Duncan P. N. Exon Smith
2015-Jul-21 20:06 UTC
[LLVMdev] RFC: ThinLTO Symbol Linkage and Renaming
> On 2015-Jul-14, at 13:33, Teresa Johnson <tejohnson at google.com> wrote: > > As mentioned in the Updated ThinLTO RFC (http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/086211.html), I am sending the symbol linkage and renaming required by ThinLTO as a separate RFC. It is included below. I've also attached the doc in pdf form, since the formatting (especially for the table at the end) may not come through in the copied text below well. > > Thanks! > Teresa > > > ThinLTO Symbol Linkage and Renaming > > > 1 Introduction > 2 Non-Discardable Values > 2.2 Linkage Effects > 2.2.2 ExternalLinkage > 2.2.1 WeakAnyLinkage > 2.2.2 WeakODRLinkage > 2.2.3 AppendingLinkage > 2.2.4 CommonLinkage > 3 Linkonce Values > 3.1 Linkage Effects > 3.2 Importing Strategy > 4 Static Values > 4.1 Static Variables > 4.2 Static Functions > 4.3 Static Promotion > 4.3.1 Linkage Effects > 4.3.2 Renaming > 5 Linkage Change Summary Table >Thanks for the writeup! A few notes/questions below. Sorry for the slow response.> 1 Introduction > > This document describes handling of symbols that may need linkage type changes or renaming to support ThinLTO importing.This applies to both the symbol in its original module as well as in the module importing it. > > In LLVM, the GlobalValue class is used to represent function, variable and alias symbols. The Function and GlobalVariable classes are both derived from the GlobalObject class which itself is derived from GlobalValue. The GlobalAlias class is derived directly from GlobalValue. Note that LLVM GlobalValues include static variables and functions in C/C++. > > During ThinLTO importing of a function from another module, the symbols from that module are parsed and imported as either a declaration or definition. Note that while we are importing one function at a time from another module, we typically always import all variable definitions (the one exceptions are variables with AppendingLinkage and WeakAnyLinkage, as described in Section 2.2). > > The following sections discuss the handling of values with the given original linkage types (in the original module). The effects on the linkage type in both the original module and in the imported copy in another module are described. > > > 2 Non-Discardable Values > > Non-discardable values are those that cannot be discarded by a module even when the value is unreferenced, i.e. it may be referenced by another module. This includes all linkage types except local (internal or private) and linkonce.(Isn't available_externally also discardable?)> For these values (both variables and functions), a reference may be imported into another module without fear that its definition may be eliminated in the original module. As a result, when the definitions of these non-discardable values are imported, the imported copy may safely be eliminated after optimizations such as inlining, as a copy is guaranteed to be available in the original module. In practice we may not eliminate these imported definitions, as discussed below, depending on the linkage type handling in the imported copy. > > 2.2 Linkage Effects > > There is no change to the linkage type required in the original module for any non-discardable values that may be imported to another module. > > During importing, ideally all non-discardable definitions have their linkage type changed in the imported copy to AvailableExternallyLinkage. This signals to the compiler that the definition can safely be eliminated after inlining (i.e. by the new EliminateAvailableExternally pass). In practice, we do not change the linkage for all imported non-discardable defs. The linkage effects for the non-discardable linkage types are described below: > > 2.2.2 ExternalLinkage > > An imported ExternalLinkage definition can be changed to AvailableExternallyLinkage. If it is eliminated later by the EliminateAvailableExternally pass, the resulting decl becomes ExternalLinkage. > > 2.2.1 WeakAnyLinkage > > Importing a WeakAnyLinkage definition could change the result of the program as it could cause a different weak definition to be selected by the linker. WeakAnyLinkage can be specified via __attribute__ ((weak)) on a function definition, to allow overriding by a strong definition in another module. If no strong definition exists, the linker will select the first weak definition. Importing a weak definition into a different module can change the order the weak defs are seen by the linker and change the program semantics. Therefore, any WeakAnyLinkage definitions are only imported as declarations, which are given ExternalWeakLinkage. WeakAny aliases are handled similarly (imported as ExternalWeakLinkage aliases). > > 2.2.2 WeakODRLinkage > > For WeakODRLinkage, there is a guarantee that all copies will be equivalent, so the issue described above for WeakAny does not exist, and the definition can be imported. For WeakODRLinkage, the imported definition should retain the original WeakODRLinkage.I think LinkOnceODRLinkage has the right semantics here.> If imported as a declaration, it should instead have ExternalWeakLinkage.I think you can get away with just ExternalLinkage for this? We found a definition to import, so it must exist somewhere. Moreover, thinking about where ODR comes from in C++, this: -- template <class T> T foo() { return 0; } extern template int foo<int>(); int bar() { return foo<int>(); } -- creates: -- declare i32 @_Z3fooIiET_v() #1 -- and this: -- template <class T> T foo() { return 0; } template int foo<int>(); -- creates: -- define weak_odr i32 @_Z3fooIiET_v() #0 { ret i32 0 } --> WeakODRLinkage symbols cannot be marked AvailableExternallyLinkage, because if the def is later dropped (by the EliminateAvailableExternally pass), the new decl is marked ExternalLinkage. For these weak symbols, however, the correct linkage for the decl is actually ExternalWeakLinkage, so that they get treated appropriately by the linker. But the information about their original weak linkage would be gone once they were changed to AvailableExternallyLinkage. For now, since weak symbols are expected to be uncommon, we will leave these symbols with their original weak linkage, which means they will not be discardable in the imported destination. If this becomes a problem, we can investigate retaining information about the original linkage type.I think importing the definitions as LinkOnceODRLinkage will just do the right thing here.> 2.2.3 AppendingLinkage > > This applies to special variables such as the global constructors and destructors lists. We never import these as they would get executed multiple times, which is incorrect. > > 2.2.4 CommonLinkage > > Since common symbols are always zero-initialized variables, they do not take up room. It is simplest to import these defs as common. > > 3 Linkonce Values > > The LinkOnceODRLinkage and LinkOnceAnyLinkage types refer to linkonce linkage, which allows merging of different globals with the same name. Unreferenced linkonce globals may also be discarded. Linkonce values include some COMDAT functions (COMDAT may also have Weak linkage) and vtable variables. For linkonce values, duplicates are allowed and the linker selects one. > > 3.1 Linkage Effects > > Since duplicates are allowed and the linkonce values are already discardable, imported linkonce values can remain linkonce in the imported copy. Any duplicate imported copy will be handled by the linker, and it may remain discardable in the importing module if it isn’t referenced after importing/inlining. > > Similarly, there is also no change in linkage type required in the original module. > > 3.2 Importing Strategy > > The main issue with linkonce values is that they are discardable in the original module (e.g. if all references are inlined in the original module). However, ThinLTO importing may introduce a cross-module reference to a linkonce value in the original module. Care must be taken to ensure that such a reference imported into another module is satisfied at link time by a definition somewhere. To handle this for linkonce functions, the ThinLTO importer must force-import any linkonce functions referenced by another imported function. To do this, after importing a function, the ThinLTO importer walks all newly imported operations looking for references to functions with linkonce linkage type. Any found are also imported, along with functions and variables in the same COMDAT group (note the COMDAT group must always be imported in its entirety regardless of whether it has linkonce or weak linkage). For linkonce variables, since GlobalVariable definitions are always imported when we import a function from the same module as described in the introduction, the linkonce variable definitions are therefore imported and available.This scares me a little for linkonce -- there's a minor change to semantics if the importing module would have linked against a *different* definition of the same symbol -- but I'm not really sure it matters much.> > 4 Static Values > > File static functions and variables have local linkage types (i.e. internal or private), and are discardable. These values need special handling during importing as described below. The local linkage types InternalLinkage and PrivateLinkage (private is the same as internal but is omitted from the symbol table) are handled the same for ThinLTO. > > 4.1 Static Variables > > Read-write or address taken static variables must always be promoted to global scope (i.e. non-discardable, non-local linkage) if they are imported to another module. This is important to ensure that one single copy of the static variable is used in address comparisons or when updating its value. > > The mechanics of static promotion are described below in Section 4.3. > > A static (local linkage) variable marked as a read-only (marked constant by LLVM) need not be promoted/renamed, unless it is address taken as described above. The imported copy of its definition can simply be used by any imported references in the read-only non-address taken case. > > 4.2 Static Functions > > When a reference to a static (local linkage) function is imported, in order to satisfy the imported reference, there are two possible strategies: > 1. The function must be promoted to global scope (i.e. non-local linkage) both in its original module (where it is no longer discardable) and in the importing module; OR > 2. The static function definition must also be imported into the same importing module, so that a local copy is available for the reference. > The strategy to be used for a particular function will ultimately depend on several factors such as whether it is address taken, its size, etc. This is discussed in more detail further on. > > Note that address taken static functions must always be promoted for correctness. The reason can be seen with the following example: > > a.cc: > static void foo() { … }; > static funcptr P; > > void bar() { > if (P == &foo) { > ... > } > } > > void baz() { > P = &foo; > } > > b.cc: > … bar(); … > > > If bar() is imported into b.cc (and gets inlined), then b.cc will have a reference to static foo(). It we then import foo() and leave the imported copy local/unpromoted, the imported P==&foo comparison will fail (assume baz() is not referenced by or imported into b.cc). That is because P will point to the a.cc::foo() and the imported comparison will compare against the imported copy b.cc::foo(). This is avoided by promoting address taken static functions, in both their original module (if the function is in the global function index) and when it has been imported along with an address taken reference into another module. Similar logic applies to read-only static variables as mentioned in Section 4.1. > > The mechanics of static promotion are described later in Section 4.3. > > It is important to note that the promotion decisions between the original module and the importing module must be consistent (it is ok for the function to be promoted in the original module but not in the importing module, but not vice versa, or we will have an undefined reference reference at link time). However, the original module and importing modules are compiled independently through the ThinLTO phase-3 parallel backend. There are several ways to ensure consistent promotion. Two of the simplest are: > > 1. Always promote imported static functions > a. When importing a static function reference or definition, always promote the imported value > b. In the original module, promote any static functions that may be imported into another module (any static functions in the global function index/summary map) > > 2. Minimize static promotions by only promoting address taken static functions > a. When a function is imported, look through newly imported instructions and force import any referenced static functions. > b. When importing is complete, any imported static functions that are address taken must be promoted > c. In the original module, promote any static functions that are address taken. > > Strategy 1 (always promote) has the disadvantage in that it potentially results in a larger symbol table, due to promoted functions no longer being discardable. However, in practice (based on cpu2006 measurements) this does not turn out to be a significant issue. > > Strategy 2 (promote only address taken) has the disadvantage in that it can increase code size, in the case where imported unpromoted static functions are not inlined into all call sites in the imported module, and we end up with multiple copies. This turns out to be a more significant issue for a couple of cpu2006 benchmarks, notably 400.perlbench. However, this can be alleviated by enabling function sections and linker garbage collection. > > A third intermediate strategy would be to promote static functions that are either address-taken or unlikely to be fully inlined. Large or cold static functions are unlikely to be inlined, and are therefore unlikely to be imported anyway. Therefore, the plugin should not even include these functions in the combined function summary (based on metrics such as function size or hotness). Any static function that is not in the combined index will therefore not be eligible for importing, and should be promoted. So both the original module and the importing module will consult the combined function summary for each static function to see whether it should be static promoted (if entry not found) vs force imported (if entry found). This can be refined further to static promote a address taken and/or non-importable static function in the original module only if it is referenced by a function that is found in the map (because the reference may be imported into another module). This is summarized below: > > 3. Promote only address taken static functions and those not enabled for importing by the plugin > a. When a function is imported, look through newly imported instructions and identify any referenced static functions. If the referenced static function is found in the function summary, force import it. Otherwise, promote it. > b. When importing is complete, any imported (and therefore unpromoted) static functions that are address taken must be promoted > c. In the original module, promote any static functions that either: > i. are address taken; or > ii. may not be imported into another module (any static functions not in the global function index/summary map) > iff they are referenced by a function that may be imported into another module. > > Given the results of experiments with cpu2006, we will initially implement strategy 1 (always promote). This is also the simplest strategy. > > 4.3 Static Promotion > > Promoting a static variable or function to non-local/non-static requires two main changes: changing the linkage and ensuring consistent naming between the definition in the original module and references in importing modules. > > 4.3.1 Linkage Effects > > The linkage of static functions and variables are changed are as follows: > * Definition in the original module: ExternalLinkage > * Definition in the importing module: AvailableExternallyLinkage > * Declaration in the importing module (i.e. def not imported): ExternalLinkage > Note that in the importing module the new linkage type of the promoted function/variable definition is the same as for non-discardable (non-local, non-linkonce) ExternalLinkage symbols as described in Section 2.This promotion can change semantics in important ways if the executable is a plugin (or a new object file, like with `ld -r`). I think you can fix this by giving promoted statics "hidden" visibility, instructing the linker to demote them back to where they came from. I think this will also fix symbol table bloat. The resulting link will downgrade the symbols back to (effectively) InternalLinkage, and the user has the option of -strip-symbols/etc. to effectively downgrade everything to PrivateLinkage if there's an obscurity concern.> 4.3.2 Renaming > > Since there may be multiple static functions from different modules with the same name before importing/promotion, or a global function which already has the same name, the promoted static functions must be renamed to avoid naming conflicts. It is important that the promoted definition in the original module is given the same name as the promoted reference in the importing module, so that the reference in the importing module can be satisfied by the original module at link time. > > To do the renaming consistently, we can include a module-specific identifier in the new name. The plugin step in phase-2 of ThinLTO (which builds the combined function index/summary) has visibility into all modules included in the ThinLTO build. It can simply number the modules and record the assigned module ID in the function summary information (either along with each function from that module, or along with the module name which will be shared in a module string table for efficiency). Then during promotion, the module ID in the combined function index/summary can be consulted and appended to the original name, along with an LLVM-specific suffix identifying this as a promoted static. > > For example, > static void foo(); // In module with ID 1 > originally has bitcode definition in module ID 1: > define internal void @foo() // InternalLinkage > which becomes after promotion/renaming: > define void @foo.llvm.1() // ExternalLinkage, new suffix “.llvm.1” > > When we import a static definition into another module (say module ID 2), before promotion it has declaration: > define internal void @foo() // InternalLinkage, func summary info: from Module ID 1 > which becomes after promotion/renaming: > define available_externally void @foo.llvm.1() // AvailableExternallyLinkage, new suffix “.llvm.1” > > If a reference is imported but not the definition, before promotion the new declaration is: > declare internal void @foo() // InternalLinkage, func summary info: from Module ID 1 > which becomes after promotion/renaming: > declare void @foo.llvm.1() // ExternalLinkage, new suffix “.llvm.1” > > Note that the new EliminateAvailableExternallyPass (under review) will change the linkage type from AvailableExternallyLinkage to ExternalLinkage on the declaration it leaves for any eliminated available externally definitions, which is consistent with the above behavior. >I wonder whether a prefix would be better? All the promotion/renaming scares me. I feel like there may be dragons here we're not aware of. The only concrete concern I have (once you switch to hidden visibility) is the interaction with non-LTO'd objects being linked into the same executable, but I wonder if I'm missing something else, too...> > 5 Linkage Change Summary Table > > The following table summarizes the linkage change that happen during ThinLTO backend compilations. Note that the only time the linkage changes in the original module is for the static promotion case (for Internal and Private linkages), where it changes to External as described in Section 4.3.1. In all other cases the linkage in the original module stays the same, and therefore is not noted in the table below. > > Note that there are no InternalLinkage, PrivateLinkage, AvailableExternallyLinkage, LinkOnce*Linkage, Weak*Linkage, AppendingLinkage and CommonLinkage declarations. There are no ExternalWeakLinkage definitions. > > +---------------------------------+------------------------------------------------+ > | | Importing Module Linkage | > | Original Module +----------------------+-------------------------+ > | | Import definition | Import as declaration | > +----------------------------------------------------------------------------------+ > | External (def) | AvailableExternally | External | > +----------------------------------------------------------------------------------+ > | External (decl) | N/A | External | > +----------------+-----------------------------------------------------------------+ > | | Promote[1] | AvailableExternally | External | > | Internal (def) +-----------------------------------------------------------------+ > | | NoPromote | Internal | N/A (force import def) | > +----------------------------------------------------------------------------------+ > | | Promote[1] | AvailableExternally | External | > | Private (def) +-----------------------------------------------------------------+ > | | NoPromote | Private | N/A (force import def) | > +----------------+-----------------------------------------------------------------+ > | AvailableExternally (def) | AvailableExternally | External | > +----------------------------------------------------------------------------------+ > | LinkOnceAny (def) | LinkOnceAny | N/A (force import def) | > +----------------------------------------------------------------------------------+ > | LinkOnceODR (def) | LinkOnceODR | N/A (force import def) | > +----------------------------------------------------------------------------------+ > | WeakAny (def) | N/A (never import) | ExternalWeak | > +----------------------------------------------------------------------------------+ > | WeakODR (def) | WeakODR | ExternalWeak | > +----------------------------------------------------------------------------------+ > | Appending (def) (only variables)| N/A (never import) | N/A (never import) | > +----------------------------------------------------------------------------------+ > | ExternalWeak (decl) | N/A | ExternalWeak | > +----------------------------------------------------------------------------------+ > | Common (def) (only variables) | Common | N/A (always import def)| > +---------------------------------+----------------------+-------------------------+ > > [1] Linkage in original module changes to External > > -- > Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413 > <ThinLTOSymbolLinkageandRenaming.pdf>_______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Thanks for the comments! Responses below. Teresa On Tue, Jul 21, 2015 at 1:06 PM, Duncan P. N. Exon Smith < dexonsmith at apple.com> wrote:> > > On 2015-Jul-14, at 13:33, Teresa Johnson <tejohnson at google.com> wrote: > > > > As mentioned in the Updated ThinLTO RFC ( > http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/086211.html), I am > sending the symbol linkage and renaming required by ThinLTO as a separate > RFC. It is included below. I've also attached the doc in pdf form, since > the formatting (especially for the table at the end) may not come through > in the copied text below well. > > > > Thanks! > > Teresa > > > > > > ThinLTO Symbol Linkage and Renaming > > > > > > 1 Introduction > > 2 Non-Discardable Values > > 2.2 Linkage Effects > > 2.2.2 ExternalLinkage > > 2.2.1 WeakAnyLinkage > > 2.2.2 WeakODRLinkage > > 2.2.3 AppendingLinkage > > 2.2.4 CommonLinkage > > 3 Linkonce Values > > 3.1 Linkage Effects > > 3.2 Importing Strategy > > 4 Static Values > > 4.1 Static Variables > > 4.2 Static Functions > > 4.3 Static Promotion > > 4.3.1 Linkage Effects > > 4.3.2 Renaming > > 5 Linkage Change Summary Table > > > > Thanks for the writeup! A few notes/questions below. Sorry > for the slow response. > > > 1 Introduction > > > > This document describes handling of symbols that may need linkage type > changes or renaming to support ThinLTO importing.This applies to both the > symbol in its original module as well as in the module importing it. > > > > In LLVM, the GlobalValue class is used to represent function, variable > and alias symbols. The Function and GlobalVariable classes are both derived > from the GlobalObject class which itself is derived from GlobalValue. The > GlobalAlias class is derived directly from GlobalValue. Note that LLVM > GlobalValues include static variables and functions in C/C++. > > > > During ThinLTO importing of a function from another module, the symbols > from that module are parsed and imported as either a declaration or > definition. Note that while we are importing one function at a time from > another module, we typically always import all variable definitions (the > one exceptions are variables with AppendingLinkage and WeakAnyLinkage, as > described in Section 2.2). > > > > The following sections discuss the handling of values with the given > original linkage types (in the original module). The effects on the linkage > type in both the original module and in the imported copy in another module > are described. > > > > > > 2 Non-Discardable Values > > > > Non-discardable values are those that cannot be discarded by a module > even when the value is unreferenced, i.e. it may be referenced by another > module. This includes all linkage types except local (internal or private) > and linkonce. > > (Isn't available_externally also discardable?) >True. Here I was going with the definition of discardable linkages returned by GlobalValue::isDiscardableIfUnused, which only returns true for local and linkonce.> > For these values (both variables and functions), a reference may be > imported into another module without fear that its definition may be > eliminated in the original module. As a result, when the definitions of > these non-discardable values are imported, the imported copy may safely be > eliminated after optimizations such as inlining, as a copy is guaranteed to > be available in the original module. In practice we may not eliminate these > imported definitions, as discussed below, depending on the linkage type > handling in the imported copy. > > > > 2.2 Linkage Effects > > > > There is no change to the linkage type required in the original module > for any non-discardable values that may be imported to another module. > > > > During importing, ideally all non-discardable definitions have their > linkage type changed in the imported copy to AvailableExternallyLinkage. > This signals to the compiler that the definition can safely be eliminated > after inlining (i.e. by the new EliminateAvailableExternally pass). In > practice, we do not change the linkage for all imported non-discardable > defs. The linkage effects for the non-discardable linkage types are > described below: > > > > 2.2.2 ExternalLinkage > > > > An imported ExternalLinkage definition can be changed to > AvailableExternallyLinkage. If it is eliminated later by the > EliminateAvailableExternally pass, the resulting decl becomes > ExternalLinkage. > > > > 2.2.1 WeakAnyLinkage > > > > Importing a WeakAnyLinkage definition could change the result of the > program as it could cause a different weak definition to be selected by the > linker. WeakAnyLinkage can be specified via __attribute__ ((weak)) on a > function definition, to allow overriding by a strong definition in another > module. If no strong definition exists, the linker will select the first > weak definition. Importing a weak definition into a different module can > change the order the weak defs are seen by the linker and change the > program semantics. Therefore, any WeakAnyLinkage definitions are only > imported as declarations, which are given ExternalWeakLinkage. WeakAny > aliases are handled similarly (imported as ExternalWeakLinkage aliases). > > > > 2.2.2 WeakODRLinkage > > > > For WeakODRLinkage, there is a guarantee that all copies will be > equivalent, so the issue described above for WeakAny does not exist, and > the definition can be imported. For WeakODRLinkage, the imported definition > should retain the original WeakODRLinkage. > > I think LinkOnceODRLinkage has the right semantics here. > > > If imported as a declaration, it should instead have ExternalWeakLinkage. > > I think you can get away with just ExternalLinkage for this? We > found a definition to import, so it must exist somewhere. > > Moreover, thinking about where ODR comes from in C++, this: > -- > template <class T> T foo() { return 0; } > extern template int foo<int>(); > int bar() { return foo<int>(); } > -- > > creates: > -- > declare i32 @_Z3fooIiET_v() #1 > -- > > and this: > -- > template <class T> T foo() { return 0; } > template int foo<int>(); > -- > creates: > -- > define weak_odr i32 @_Z3fooIiET_v() #0 { > ret i32 0 > } > -- >Ok, good, it looks like this can be treated differently from WeakAny here, with made External not ExternalWeak.> > > WeakODRLinkage symbols cannot be marked AvailableExternallyLinkage, > because if the def is later dropped (by the EliminateAvailableExternally > pass), the new decl is marked ExternalLinkage. For these weak symbols, > however, the correct linkage for the decl is actually ExternalWeakLinkage, > so that they get treated appropriately by the linker. But the information > about their original weak linkage would be gone once they were changed to > AvailableExternallyLinkage. For now, since weak symbols are expected to be > uncommon, we will leave these symbols with their original weak linkage, > which means they will not be discardable in the imported destination. If > this becomes a problem, we can investigate retaining information about the > original linkage type. > > I think importing the definitions as LinkOnceODRLinkage will just > do the right thing here. >Actually, if the decl should be ExternalLinkage, then the concern I note above about importing the def as AvailableExternally should be moot. It seems better to import as AvailableExternally so the body can be eliminated after inlining. Unlike LinkOnceODR which could only be eliminated if all references are inlined. Since the original copy is WeakODR and not-discardable, it will be available.> > 2.2.3 AppendingLinkage > > > > This applies to special variables such as the global constructors and > destructors lists. We never import these as they would get executed > multiple times, which is incorrect. > > > > 2.2.4 CommonLinkage > > > > Since common symbols are always zero-initialized variables, they do not > take up room. It is simplest to import these defs as common. > > > > 3 Linkonce Values > > > > The LinkOnceODRLinkage and LinkOnceAnyLinkage types refer to linkonce > linkage, which allows merging of different globals with the same name. > Unreferenced linkonce globals may also be discarded. Linkonce values > include some COMDAT functions (COMDAT may also have Weak linkage) and > vtable variables. For linkonce values, duplicates are allowed and the > linker selects one. > > > > 3.1 Linkage Effects > > > > Since duplicates are allowed and the linkonce values are already > discardable, imported linkonce values can remain linkonce in the imported > copy. Any duplicate imported copy will be handled by the linker, and it may > remain discardable in the importing module if it isn’t referenced after > importing/inlining. > > > > Similarly, there is also no change in linkage type required in the > original module. > > > > 3.2 Importing Strategy > > > > The main issue with linkonce values is that they are discardable in the > original module (e.g. if all references are inlined in the original > module). However, ThinLTO importing may introduce a cross-module reference > to a linkonce value in the original module. Care must be taken to ensure > that such a reference imported into another module is satisfied at link > time by a definition somewhere. To handle this for linkonce functions, the > ThinLTO importer must force-import any linkonce functions referenced by > another imported function. To do this, after importing a function, the > ThinLTO importer walks all newly imported operations looking for references > to functions with linkonce linkage type. Any found are also imported, along > with functions and variables in the same COMDAT group (note the COMDAT > group must always be imported in its entirety regardless of whether it has > linkonce or weak linkage). For linkonce variables, since GlobalVariable > definitions are always imported when we import a function from the same > module as described in the introduction, the linkonce variable definitions > are therefore imported and available. > > This scares me a little for linkonce -- there's a minor change to > semantics if the importing module would have linked against a > *different* definition of the same symbol -- but I'm not really > sure it matters much. >For LinkOnceODR the defs will be the same. LinkOnceAny appeared to be applied to a few compiler-generated definitions. It's not clear to me when/if this linkage type is used on definitions that are importable for ThinLTO and could have linked against a different definition.> > > > 4 Static Values > > > > File static functions and variables have local linkage types (i.e. > internal or private), and are discardable. These values need special > handling during importing as described below. The local linkage types > InternalLinkage and PrivateLinkage (private is the same as internal but is > omitted from the symbol table) are handled the same for ThinLTO. > > > > 4.1 Static Variables > > > > Read-write or address taken static variables must always be promoted to > global scope (i.e. non-discardable, non-local linkage) if they are imported > to another module. This is important to ensure that one single copy of the > static variable is used in address comparisons or when updating its value. > > > > The mechanics of static promotion are described below in Section 4.3. > > > > A static (local linkage) variable marked as a read-only (marked constant > by LLVM) need not be promoted/renamed, unless it is address taken as > described above. The imported copy of its definition can simply be used by > any imported references in the read-only non-address taken case. > > > > 4.2 Static Functions > > > > When a reference to a static (local linkage) function is imported, in > order to satisfy the imported reference, there are two possible strategies: > > 1. The function must be promoted to global scope (i.e. non-local > linkage) both in its original module (where it is no longer discardable) > and in the importing module; OR > > 2. The static function definition must also be imported into the same > importing module, so that a local copy is available for the reference. > > The strategy to be used for a particular function will ultimately depend > on several factors such as whether it is address taken, its size, etc. This > is discussed in more detail further on. > > > > Note that address taken static functions must always be promoted for > correctness. The reason can be seen with the following example: > > > > a.cc: > > static void foo() { … }; > > static funcptr P; > > > > void bar() { > > if (P == &foo) { > > ... > > } > > } > > > > void baz() { > > P = &foo; > > } > > > > b.cc: > > … bar(); … > > > > > > If bar() is imported into b.cc (and gets inlined), then b.cc will have a > reference to static foo(). It we then import foo() and leave the imported > copy local/unpromoted, the imported P==&foo comparison will fail (assume > baz() is not referenced by or imported into b.cc). That is because P will > point to the a.cc::foo() and the imported comparison will compare against > the imported copy b.cc::foo(). This is avoided by promoting address taken > static functions, in both their original module (if the function is in the > global function index) and when it has been imported along with an address > taken reference into another module. Similar logic applies to read-only > static variables as mentioned in Section 4.1. > > > > The mechanics of static promotion are described later in Section 4.3. > > > > It is important to note that the promotion decisions between the > original module and the importing module must be consistent (it is ok for > the function to be promoted in the original module but not in the importing > module, but not vice versa, or we will have an undefined reference > reference at link time). However, the original module and importing modules > are compiled independently through the ThinLTO phase-3 parallel backend. > There are several ways to ensure consistent promotion. Two of the simplest > are: > > > > 1. Always promote imported static functions > > a. When importing a static function reference or definition, always > promote the imported value > > b. In the original module, promote any static functions that may be > imported into another module (any static functions in the global function > index/summary map) > > > > 2. Minimize static promotions by only promoting address taken static > functions > > a. When a function is imported, look through newly imported > instructions and force import any referenced static functions. > > b. When importing is complete, any imported static functions that are > address taken must be promoted > > c. In the original module, promote any static functions that are > address taken. > > > > Strategy 1 (always promote) has the disadvantage in that it potentially > results in a larger symbol table, due to promoted functions no longer being > discardable. However, in practice (based on cpu2006 measurements) this does > not turn out to be a significant issue. > > > > Strategy 2 (promote only address taken) has the disadvantage in that it > can increase code size, in the case where imported unpromoted static > functions are not inlined into all call sites in the imported module, and > we end up with multiple copies. This turns out to be a more significant > issue for a couple of cpu2006 benchmarks, notably 400.perlbench. However, > this can be alleviated by enabling function sections and linker garbage > collection. > > > > A third intermediate strategy would be to promote static functions that > are either address-taken or unlikely to be fully inlined. Large or cold > static functions are unlikely to be inlined, and are therefore unlikely to > be imported anyway. Therefore, the plugin should not even include these > functions in the combined function summary (based on metrics such as > function size or hotness). Any static function that is not in the combined > index will therefore not be eligible for importing, and should be promoted. > So both the original module and the importing module will consult the > combined function summary for each static function to see whether it should > be static promoted (if entry not found) vs force imported (if entry found). > This can be refined further to static promote a address taken and/or > non-importable static function in the original module only if it is > referenced by a function that is found in the map (because the reference > may be imported into another module). This is summarized below: > > > > 3. Promote only address taken static functions and those not enabled for > importing by the plugin > > a. When a function is imported, look through newly imported > instructions and identify any referenced static functions. If the > referenced static function is found in the function summary, force import > it. Otherwise, promote it. > > b. When importing is complete, any imported (and therefore > unpromoted) static functions that are address taken must be promoted > > c. In the original module, promote any static functions that either: > > i. are address taken; or > > ii. may not be imported into another module (any static > functions not in the global function index/summary map) > > iff they are referenced by a function that may be imported into > another module. > > > > Given the results of experiments with cpu2006, we will initially > implement strategy 1 (always promote). This is also the simplest strategy. > > > > 4.3 Static Promotion > > > > Promoting a static variable or function to non-local/non-static requires > two main changes: changing the linkage and ensuring consistent naming > between the definition in the original module and references in importing > modules. > > > > 4.3.1 Linkage Effects > > > > The linkage of static functions and variables are changed are as follows: > > * Definition in the original module: ExternalLinkage > > * Definition in the importing module: AvailableExternallyLinkage > > * Declaration in the importing module (i.e. def not imported): > ExternalLinkage > > Note that in the importing module the new linkage type of the promoted > function/variable definition is the same as for non-discardable (non-local, > non-linkonce) ExternalLinkage symbols as described in Section 2. > > This promotion can change semantics in important ways if the > executable is a plugin (or a new object file, like with `ld -r`). > I think you can fix this by giving promoted statics "hidden" > visibility, instructing the linker to demote them back to where > they came from. > > I think this will also fix symbol table bloat. The resulting link > will downgrade the symbols back to (effectively) InternalLinkage, > and the user has the option of -strip-symbols/etc. to effectively > downgrade everything to PrivateLinkage if there's an obscurity > concern. >Ok thanks for that suggestion.> > > 4.3.2 Renaming > > > > Since there may be multiple static functions from different modules with > the same name before importing/promotion, or a global function which > already has the same name, the promoted static functions must be renamed to > avoid naming conflicts. It is important that the promoted definition in the > original module is given the same name as the promoted reference in the > importing module, so that the reference in the importing module can be > satisfied by the original module at link time. > > > > To do the renaming consistently, we can include a module-specific > identifier in the new name. The plugin step in phase-2 of ThinLTO (which > builds the combined function index/summary) has visibility into all modules > included in the ThinLTO build. It can simply number the modules and record > the assigned module ID in the function summary information (either along > with each function from that module, or along with the module name which > will be shared in a module string table for efficiency). Then during > promotion, the module ID in the combined function index/summary can be > consulted and appended to the original name, along with an LLVM-specific > suffix identifying this as a promoted static. > > > > For example, > > static void foo(); // In module with ID 1 > > originally has bitcode definition in module ID 1: > > define internal void @foo() // InternalLinkage > > which becomes after promotion/renaming: > > define void @foo.llvm.1() // ExternalLinkage, new suffix > “.llvm.1” > > > > When we import a static definition into another module (say module ID > 2), before promotion it has declaration: > > define internal void @foo() // InternalLinkage, func > summary info: from Module ID 1 > > which becomes after promotion/renaming: > > define available_externally void @foo.llvm.1() // > AvailableExternallyLinkage, new suffix “.llvm.1” > > > > If a reference is imported but not the definition, before promotion the > new declaration is: > > declare internal void @foo() // InternalLinkage, func summary > info: from Module ID 1 > > which becomes after promotion/renaming: > > declare void @foo.llvm.1() // ExternalLinkage, new suffix > “.llvm.1” > > > > Note that the new EliminateAvailableExternallyPass (under review) will > change the linkage type from AvailableExternallyLinkage to ExternalLinkage > on the declaration it leaves for any eliminated available externally > definitions, which is consistent with the above behavior. > > > > I wonder whether a prefix would be better? >Is there a particular reason? I have a slight preference for suffix, but that could just be what I am used to from other compilers.> > All the promotion/renaming scares me. I feel like there may be > dragons here we're not aware of. >It is doable based on LIPO experiences. But needs thorough testing to be sure.> > The only concrete concern I have (once you switch to hidden > visibility) is the interaction with non-LTO'd objects being linked > into the same executable, but I wonder if I'm missing something > else, too... >For non-LTO'd objects there is no importing to/from, so no impact on their symbol linkage. Renaming statics when promoted will avoid name conflicts with any non-LTO (or LTO) objects being linked. Not importing WeakAny defs should avoid issues with expected overriding from non-LTO'd objects. Thanks, Teresa> > > > 5 Linkage Change Summary Table > > > > The following table summarizes the linkage change that happen during > ThinLTO backend compilations. Note that the only time the linkage changes > in the original module is for the static promotion case (for Internal and > Private linkages), where it changes to External as described in Section > 4.3.1. In all other cases the linkage in the original module stays the > same, and therefore is not noted in the table below. > > > > Note that there are no InternalLinkage, PrivateLinkage, > AvailableExternallyLinkage, LinkOnce*Linkage, Weak*Linkage, > AppendingLinkage and CommonLinkage declarations. There are no > ExternalWeakLinkage definitions. > > > > > +---------------------------------+------------------------------------------------+ > > | | Importing Module Linkage > | > > | Original Module > +----------------------+-------------------------+ > > | | Import definition | Import as > declaration | > > > +----------------------------------------------------------------------------------+ > > | External (def) | AvailableExternally | External > | > > > +----------------------------------------------------------------------------------+ > > | External (decl) | N/A | External > | > > > +----------------+-----------------------------------------------------------------+ > > | | Promote[1] | AvailableExternally | External > | > > | Internal (def) > +-----------------------------------------------------------------+ > > | | NoPromote | Internal | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | | Promote[1] | AvailableExternally | External > | > > | Private (def) > +-----------------------------------------------------------------+ > > | | NoPromote | Private | N/A (force > import def) | > > > +----------------+-----------------------------------------------------------------+ > > | AvailableExternally (def) | AvailableExternally | External > | > > > +----------------------------------------------------------------------------------+ > > | LinkOnceAny (def) | LinkOnceAny | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | LinkOnceODR (def) | LinkOnceODR | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | WeakAny (def) | N/A (never import) | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | WeakODR (def) | WeakODR | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | Appending (def) (only variables)| N/A (never import) | N/A (never > import) | > > > +----------------------------------------------------------------------------------+ > > | ExternalWeak (decl) | N/A | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | Common (def) (only variables) | Common | N/A (always > import def)| > > > +---------------------------------+----------------------+-------------------------+ > > > > [1] Linkage in original module changes to External > > > > -- > > Teresa Johnson | Software Engineer | tejohnson at google.com | > 408-460-2413 > > > <ThinLTOSymbolLinkageandRenaming.pdf>_______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-- Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150721/7780185b/attachment.html>
Xinliang David Li
2015-Jul-21 22:35 UTC
[LLVMdev] RFC: ThinLTO Symbol Linkage and Renaming
> > This scares me a little for linkonce -- there's a minor change to > semantics if the importing module would have linked against a > *different* definition of the same symbol -- but I'm not really > sure it matters much. > >This should not be an issue in practice as it exists non thinLTO compilations too. For instance changing the optimization level of one module can lead to different inline decisions and different copy of the comdat function to be picked up in the end.> > > > I wonder whether a prefix would be better? > > All the promotion/renaming scares me. I feel like there may be > dragons here we're not aware of. > >The promotion scheme is similar to LIPO which has been exercised on large number of huge C++ apps -- I think it is robust.> The only concrete concern I have (once you switch to hidden > visibility) is the interaction with non-LTO'd objects being linked > into the same executable, but I wonder if I'm missing something > else, too... > >There is an limitation (also with LIPO, LTO) that you can not compile one module say 'a.c' in thinLTO mode with the rest of the modules, and later recompile 'a.c' into 'a.o' without thinLTO and tries to mix and match with the rest of the real object files built with thinLTO unless 'a.c' is not imported by any other modules or it does not have any statics to be promoted. thanks, David> > > > 5 Linkage Change Summary Table > > > > The following table summarizes the linkage change that happen during > ThinLTO backend compilations. Note that the only time the linkage changes > in the original module is for the static promotion case (for Internal and > Private linkages), where it changes to External as described in Section > 4.3.1. In all other cases the linkage in the original module stays the > same, and therefore is not noted in the table below. > > > > Note that there are no InternalLinkage, PrivateLinkage, > AvailableExternallyLinkage, LinkOnce*Linkage, Weak*Linkage, > AppendingLinkage and CommonLinkage declarations. There are no > ExternalWeakLinkage definitions. > > > > > +---------------------------------+------------------------------------------------+ > > | | Importing Module Linkage > | > > | Original Module > +----------------------+-------------------------+ > > | | Import definition | Import as > declaration | > > > +----------------------------------------------------------------------------------+ > > | External (def) | AvailableExternally | External > | > > > +----------------------------------------------------------------------------------+ > > | External (decl) | N/A | External > | > > > +----------------+-----------------------------------------------------------------+ > > | | Promote[1] | AvailableExternally | External > | > > | Internal (def) > +-----------------------------------------------------------------+ > > | | NoPromote | Internal | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | | Promote[1] | AvailableExternally | External > | > > | Private (def) > +-----------------------------------------------------------------+ > > | | NoPromote | Private | N/A (force > import def) | > > > +----------------+-----------------------------------------------------------------+ > > | AvailableExternally (def) | AvailableExternally | External > | > > > +----------------------------------------------------------------------------------+ > > | LinkOnceAny (def) | LinkOnceAny | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | LinkOnceODR (def) | LinkOnceODR | N/A (force > import def) | > > > +----------------------------------------------------------------------------------+ > > | WeakAny (def) | N/A (never import) | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | WeakODR (def) | WeakODR | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | Appending (def) (only variables)| N/A (never import) | N/A (never > import) | > > > +----------------------------------------------------------------------------------+ > > | ExternalWeak (decl) | N/A | > ExternalWeak | > > > +----------------------------------------------------------------------------------+ > > | Common (def) (only variables) | Common | N/A (always > import def)| > > > +---------------------------------+----------------------+-------------------------+ > > > > [1] Linkage in original module changes to External > > > > -- > > Teresa Johnson | Software Engineer | tejohnson at google.com | > 408-460-2413 > > > <ThinLTOSymbolLinkageandRenaming.pdf>_______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150721/357930e0/attachment.html>