LLVM features powerful intermodular optimizations which can be used at link time. Link Time Optimization is another name for intermodular optimization when performed during the link stage. This document describes the interface and design between the LLVM intermodular optimizer and the linker.

The LLVM Link Time Optimizer provides complete transparency, while doing intermodular optimization, in the compiler tool chain. Its main goal is to let the developer take advantage of intermodular optimizations without making any significant changes to the developer's makefiles or build system. This is achieved through tight integration with the linker. In this model, the linker treates LLVM bitcode files like native object files and allows mixing and matching among them. The linker uses LLVMlto, a dynamically loaded library, to handle LLVM bitcode files. This tight integration between the linker and LLVM optimizer helps to do optimizations that are not possible in other models. The linker input allows the optimizer to avoid relying on conservative escape analysis.

The following example illustrates the advantages of LTO's integrated approach and clean interface. This example requires a system linker which supports LTO through the interface described in this document. Here, llvm-gcc4 transparently invokes system linker.

• Input source file a.c is compiled into LLVM bitcode form.
• Input source file main.c is compiled into native object code.

--- a.h ---
extern int foo1(void);
extern void foo2(void);
extern void foo4(void);
--- a.c ---
#include "a.h"

static signed int i = 0;

void foo2(void) {
 i = -1;
}

static int foo3() {
foo4();
return 10;
}

int foo1(void) {
int data = 0;

if (i < 0) { data = foo3(); }

data = data + 42;
return data;
}

--- main.c ---
#include <stdio.h>
#include "a.h"

void foo4(void) {
 printf ("Hi\n");
}

int main() {
 return foo1();
}

--- command lines ---
$ llvm-gcc4 --emit-llvm -c a.c -o a.o  # <-- a.o is LLVM bitcode file
$ llvm-gcc4 -c main.c -o main.o # <-- main.o is native object file
$ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifications

In this example, the linker recognizes that foo2() is an externally visible symbol defined in LLVM bitcode file. This information is collected using readLLVMObjectFile(). Based on this information, the linker completes its usual symbol resolution pass and finds that foo2() is not used anywhere. This information is used by the LLVM optimizer and it removes foo2(). As soon as foo2() is removed, the optimizer recognizes that condition i < 0 is always false, which means foo3() is never used. Hence, the optimizer removes foo3(), also. And this in turn, enables linker to remove foo4(). This example illustrates the advantage of tight integration with the linker. Here, the optimizer can not remove foo3() without the linker's input.

Compiler driver invokes link time optimizer separately.

In this model the link time optimizer is not able to take advantage of information collected during the linker's normal symbol resolution phase. In the above example, the optimizer can not remove foo2() without the linker's input because it is externally visible. This in turn prohibits the optimizer from removing foo3().

Use separate tool to collect symbol information from all object files.

In this model, a new, separate, tool or library replicates the linker's capability to collect information for link time optimization. Not only is this code duplication difficult to justify, but it also has several other disadvantages. For example, the linking semantics and the features provided by the linker on various platform are not unique. This means, this new tool needs to support all such features and platforms in one super tool or a separate tool per platform is required. This increases maintance cost for link time optimizer significantly, which is not necessary. This approach also requires staying synchronized with linker developements on various platforms, which is not the main focus of the link time optimizer. Finally, this approach increases end user's build time due to the duplication of work done by this separate tool and the linker itself.

The linker collects information about symbol defininitions and uses in various link objects which is more accurate than any information collected by other tools during typical build cycles. The linker collects this information by looking at the definitions and uses of symbols in native .o files and using symbol visibility information. The linker also uses user-supplied information, such as a list of exported symbols. LLVM optimizer collects control flow information, data flow information and knows much more about program structure from the optimizer's point of view. Our goal is to take advantage of tight intergration between the linker and the optimizer by sharing this information during various linking phases.

The linker first reads all object files in natural order and collects symbol information. This includes native object files as well as LLVM bitcode files. In this phase, the linker uses readLLVMObjectFile() to collect symbol information from each LLVM bitcode files and updates its internal global symbol table accordingly. The intent of this interface is to avoid overhead in the non LLVM case, where all input object files are native object files, by putting this code in the error path of the linker. When the linker sees the first llvm .o file, it dlopen()s the dynamic library. This is to allow changes to the LLVM LTO code without relinking the linker.

In this stage, the linker resolves symbols using global symbol table information to report undefined symbol errors, read archive members, resolve weak symbols, etc. The linker is able to do this seamlessly even though it does not know the exact content of input LLVM bitcode files because it uses symbol information provided by readLLVMObjectFile(). If dead code stripping is enabled then the linker collects the list of live symbols.

After symbol resolution, the linker updates symbol information supplied by LLVM bitcode files appropriately. For example, whether certain LLVM bitcode supplied symbols are used or not. In the example above, the linker reports that foo2() is not used anywhere in the program, including native .o files. This information is used by the LLVM interprocedural optimizer. The linker uses optimizeModules() and requests an optimized native object file of the LLVM portion of the program.

In this phase, the linker reads optimized a native object file and updates the internal global symbol table to reflect any changes. The linker also collects information about any changes in use of external symbols by LLVM bitcode files. In the examle above, the linker notes that foo4() is not used any more. If dead code stripping is enabled then the linker refreshes the live symbol information appropriately and performs dead code stripping.

After this phase, the linker continues linking as if it never saw LLVM bitcode files.

LLVMlto is a dynamic library that is part of the LLVM tools, and is intended for use by a linker. LLVMlto provides an abstract C++ interface to use the LLVM interprocedural optimizer without exposing details of LLVM's internals. The intention is to keep the interface as stable as possible even when the LLVM optimizer continues to evolve.

The LLVMSymbol class is used to describe the externally visible functions and global variables, defined in LLVM bitcode files, to the linker. This includes symbol visibility information. This information is used by the linker to do symbol resolution. For example: function foo2() is defined inside an LLVM bitcode module and it is an externally visible symbol. This helps the linker connect the use of foo2() in native object files with a future definition of the symbol foo2(). The linker will see the actual definition of foo2() when it receives the optimized native object file in Symbol Resolution after optimization phase. If the linker does not find any uses of foo2(), it updates LLVMSymbol visibility information to notify LLVM intermodular optimizer that it is dead. The LLVM intermodular optimizer takes advantage of such information to generate better code.

The readLLVMObjectFile() function is used by the linker to read LLVM bitcode files and collect LLVMSymbol information. This routine also supplies a list of externally defined symbols that are used by LLVM bitcode files. The linker uses this symbol information to do symbol resolution. Internally, LLVMlto maintains LLVM bitcode modules in memory. This function also provides a list of external references used by bitcode files.

The linker invokes optimizeModules to optimize already read LLVM bitcode files by applying LLVM intermodular optimization techniques. This function runs the LLVM intermodular optimizer and generates native object code as .o files at the name and location provided by the linker.

The linker may use getTargetTriple() to query target architecture while validating LLVM bitcode file.

Internally, LLVMlto maintains LLVM bitcode modules in memory. The linker may use removeModule() method to remove desired modules from memory.

The linker may use LLVMSymbol method getAlignment() to query symbol alignment information.

... To be completed ...