path: root/docs
diff options
authorDimitry Andric <dim@FreeBSD.org>2016-07-23 20:48:50 +0000
committerDimitry Andric <dim@FreeBSD.org>2016-07-23 20:48:50 +0000
commit1c98619801a5705c688e683be3ef9d70169a0686 (patch)
tree8422105cd1a94c368315f2db16b9ac746cf7c000 /docs
parentf4f3ce4613680903220815690ad79fc7ba0a2e26 (diff)
Vendor import of lld release_39 branch r276489:vendor/lld/lld-release_39-r276489
Notes: svn path=/vendor/lld/dist/; revision=303239 svn path=/vendor/lld/lld-release_39-r276489/; revision=303240; tag=vendor/lld/lld-release_39-r276489
Diffstat (limited to 'docs')
7 files changed, 452 insertions, 105 deletions
diff --git a/docs/AtomLLD.rst b/docs/AtomLLD.rst
new file mode 100644
index 000000000000..4d36ac60a7db
--- /dev/null
+++ b/docs/AtomLLD.rst
@@ -0,0 +1,61 @@
+ATOM-based lld
+ATOM-based lld is a new set of modular code for creating linker tools.
+Currently it supports Mach-O.
+* End-User Features:
+ * Compatible with existing linker options
+ * Reads standard Object Files
+ * Writes standard Executable Files
+ * Remove clang's reliance on "the system linker"
+ * Uses the LLVM `"UIUC" BSD-Style license`__.
+* Applications:
+ * Modular design
+ * Support cross linking
+ * Easy to add new CPU support
+ * Can be built as static tool or library
+* Design and Implementation:
+ * Extensive unit tests
+ * Internal linker model can be dumped/read to textual format
+ * Additional linking features can be plugged in as "passes"
+ * OS specific and CPU specific code factored out
+Why a new linker?
+The fact that clang relies on whatever linker tool you happen to have installed
+means that clang has been very conservative adopting features which require a
+recent linker.
+In the same way that the MC layer of LLVM has removed clang's reliance on the
+system assembler tool, the lld project will remove clang's reliance on the
+system linker tool.
+.. toctree::
+ :maxdepth: 2
+ design
+ getting_started
+ ReleaseNotes
+ development
+ windows_support
+ open_projects
+ sphinx_intro
+Indices and tables
+* :ref:`genindex`
+* :ref:`search`
+__ http://llvm.org/docs/DeveloperPolicy.html#license
diff --git a/docs/NewLLD.rst b/docs/NewLLD.rst
new file mode 100644
index 000000000000..1f9bf87f10e3
--- /dev/null
+++ b/docs/NewLLD.rst
@@ -0,0 +1,350 @@
+The ELF and COFF Linkers
+We started rewriting the ELF (Unix) and COFF (Windows) linkers in May 2015.
+Since then, we have been making a steady progress towards providing
+drop-in replacements for the system linkers.
+Currently, the Windows support is mostly complete and is about 2x faster
+than the linker that comes as a part of Micrsoft Visual Studio toolchain.
+The ELF support is in progress and is able to link large programs
+such as Clang or LLD itself. Unless your program depends on linker scripts,
+you can expect it to be linkable with LLD.
+It is currently about 1.2x to 2x faster than GNU gold linker.
+We aim to make it a drop-in replacement for the GNU linker.
+We expect that FreeBSD is going to be the first large system
+to adopt LLD as the system linker.
+We are working on it in collaboration with the FreeBSD project.
+The linkers are notably small; as of June 2016,
+the COFF linker is under 7k lines and the ELF linker is about 13k lines,
+while gold is 146K lines.
+The linkers are designed to be as fast and simple as possible.
+Because it is simple, it is easy to extend to support new features.
+It already supports several advanced features such section garbage
+collection and identical code folding.
+The COFF linker supports i386, x86-64 and ARM. The ELF linker supports
+i386, x86-64, x32, MIPS32, MIPS64, PowerPC, AMDGPU, ARM and Aarch64,
+although the quality varies depending on platform. By default, LLD
+provides support for all targets because the amount of code we have for
+each target is so small. We do not even provide a way to disable
+targets at compile time.
+There are a few key design choices that we made to achieve these goals.
+We will describe them in this document.
+The ELF Linker as a Library
+You can embed LLD to your program by linking against it and calling the linker's
+entry point function lld::elf::link.
+The current policy is that it is your reponsibility to give trustworthy object
+files. The function is guaranteed to return as long as you do not pass corrupted
+or malicious object files. A corrupted file could cause a fatal error or SEGV.
+That being said, you don't need to worry too much about it if you create object
+files in the usual way and give them to the linker. It is naturally expected to
+work, or otherwise it's a linker's bug.
+We will describe the design of the linkers in the rest of the document.
+Key Concepts
+Linkers are fairly large pieces of software.
+There are many design choices you have to make to create a complete linker.
+This is a list of design choices we've made for ELF and COFF LLD.
+We believe that these high-level design choices achieved a right balance
+between speed, simplicity and extensibility.
+* Implement as native linkers
+ We implemented the linkers as native linkers for each file format.
+ The two linkers share the same design but do not share code.
+ Sharing code makes sense if the benefit is worth its cost.
+ In our case, ELF and COFF are different enough that we thought the layer to
+ abstract the differences wouldn't worth its complexity and run-time cost.
+ Elimination of the abstract layer has greatly simplified the implementation.
+* Speed by design
+ One of the most important things in archiving high performance is to
+ do less rather than do it efficiently.
+ Therefore, the high-level design matters more than local optimizations.
+ Since we are trying to create a high-performance linker,
+ it is very important to keep the design as efficient as possible.
+ Broadly speaking, we do not do anything until we have to do it.
+ For example, we do not read section contents or relocations
+ until we need them to continue linking.
+ When we need to do some costly operation (such as looking up
+ a hash table for each symbol), we do it only once.
+ We obtain a handler (which is typically just a pointer to actual data)
+ on the first operation and use it throughout the process.
+* Efficient archive file handling
+ LLD's handling of archive files (the files with ".a" file extension) is different
+ from the traditional Unix linkers and similar to Windows linkers.
+ We'll describe how the traditional Unix linker handles archive files,
+ what the problem is, and how LLD approached the problem.
+ The traditional Unix linker maintains a set of undefined symbols during linking.
+ The linker visits each file in the order as they appeared in the command line
+ until the set becomes empty. What the linker would do depends on file type.
+ - If the linker visits an object file, the linker links object files to the result,
+ and undefined symbols in the object file are added to the set.
+ - If the linker visits an archive file, it checks for the archive file's symbol table
+ and extracts all object files that have definitions for any symbols in the set.
+ This algorithm sometimes leads to a counter-intuitive behavior.
+ If you give archive files before object files, nothing will happen
+ because when the linker visits archives, there is no undefined symbols in the set.
+ As a result, no files are extracted from the first archive file,
+ and the link is done at that point because the set is empty after it visits one file.
+ You can fix the problem by reordering the files,
+ but that cannot fix the issue of mutually-dependent archive files.
+ Linking mutually-dependent archive files is tricky.
+ You may specify the same archive file multiple times to
+ let the linker visit it more than once.
+ Or, you may use the special command line options, `--start-group` and `--end-group`,
+ to let the linker loop over the files between the options until
+ no new symbols are added to the set.
+ Visiting the same archive files multiple makes the linker slower.
+ Here is how LLD approached the problem. Instead of memorizing only undefined symbols,
+ we program LLD so that it memorizes all symbols.
+ When it sees an undefined symbol that can be resolved by extracting an object file
+ from an archive file it previously visited, it immediately extracts the file and link it.
+ It is doable because LLD does not forget symbols it have seen in archive files.
+ We believe that the LLD's way is efficient and easy to justify.
+ The semantics of LLD's archive handling is different from the traditional Unix's.
+ You can observe it if you carefully craft archive files to exploit it.
+ However, in reality, we don't know any program that cannot link
+ with our algorithm so far, so it's not going to cause trouble.
+Numbers You Want to Know
+To give you intuition about what kinds of data the linker is mainly working on,
+I'll give you the list of objects and their numbers LLD has to read and process
+in order to link a very large executable. In order to link Chrome with debug info,
+which is roughly 2 GB in output size, LLD reads
+- 17,000 files,
+- 1,800,000 sections,
+- 6,300,000 symbols, and
+- 13,000,000 relocations.
+LLD produces the 2 GB executable in 15 seconds.
+These numbers vary depending on your program, but in general,
+you have a lot of relocations and symbols for each file.
+If your program is written in C++, symbol names are likely to be
+pretty long because of name mangling.
+It is important to not waste time on relocations and symbols.
+In the above case, the total amount of symbol strings is 450 MB,
+and inserting all of them to a hash table takes 1.5 seconds.
+Therefore, if you causally add a hash table lookup for each symbol,
+it would slow down the linker by 10%. So, don't do that.
+On the other hand, you don't have to pursue efficiency
+when handling files.
+Important Data Strcutures
+We will describe the key data structures in LLD in this section.
+The linker can be understood as the interactions between them.
+Once you understand their functions, the code of the linker should look obvious to you.
+* SymbolBody
+ SymbolBody is a class to represent symbols.
+ They are created for symbols in object files or archive files.
+ The linker creates linker-defined symbols as well.
+ There are basically three types of SymbolBodies: Defined, Undefined, or Lazy.
+ - Defined symbols are for all symbols that are considered as "resolved",
+ including real defined symbols, COMDAT symbols, common symbols,
+ absolute symbols, linker-created symbols, etc.
+ - Undefined symbols represent undefined symbols, which need to be replaced by
+ Defined symbols by the resolver until the link is complete.
+ - Lazy symbols represent symbols we found in archive file headers
+ which can turn into Defined if we read archieve members.
+* Symbol
+ A Symbol is a container for a SymbolBody. There's only one Symbol for each
+ unique symbol name (this uniqueness is guaranteed by the symbol table).
+ Each global symbol has only one SymbolBody at any one time, which is
+ the SymbolBody stored within a memory region of the Symbol large enough
+ to store any SymbolBody.
+ As the resolver reads symbols from input files, it replaces the Symbol's
+ SymbolBody with the "best" SymbolBody for its symbol name by constructing
+ the new SymbolBody in place on top of the existing SymbolBody. For example,
+ if the resolver is given a defined symbol, and the SymbolBody with its name
+ is undefined, it will construct a Defined SymbolBody over the Undefined
+ SymbolBody.
+ This means that each SymbolBody pointer always points to the best SymbolBody,
+ and it is possible to get from a SymbolBody to a Symbol, or vice versa,
+ by adding or subtracting a fixed offset. This memory layout helps reduce
+ the cache miss rate through high locality and a small number of required
+ pointer indirections.
+* SymbolTable
+ SymbolTable is basically a hash table from strings to Symbols
+ with a logic to resolve symbol conflicts. It resolves conflicts by symbol type.
+ - If we add Defined and Undefined symbols, the symbol table will keep the former.
+ - If we add Defined and Lazy symbols, it will keep the former.
+ - If we add Lazy and Undefined, it will keep the former,
+ but it will also trigger the Lazy symbol to load the archive member
+ to actually resolve the symbol.
+* Chunk (COFF specific)
+ Chunk represents a chunk of data that will occupy space in an output.
+ Each regular section becomes a chunk.
+ Chunks created for common or BSS symbols are not backed by sections.
+ The linker may create chunks to append additional data to an output as well.
+ Chunks know about their size, how to copy their data to mmap'ed outputs,
+ and how to apply relocations to them.
+ Specifically, section-based chunks know how to read relocation tables
+ and how to apply them.
+* InputSection (ELF specific)
+ Since we have less synthesized data for ELF, we don't abstract slices of
+ input files as Chunks for ELF. Instead, we directly use the input section
+ as an internal data type.
+ InputSection knows about their size and how to copy themselves to
+ mmap'ed outputs, just like COFF Chunks.
+* OutputSection
+ OutputSection is a container of InputSections (ELF) or Chunks (COFF).
+ An InputSection or Chunk belongs to at most one OutputSection.
+There are mainly three actors in this linker.
+* InputFile
+ InputFile is a superclass of file readers.
+ We have a different subclass for each input file type,
+ such as regular object file, archive file, etc.
+ They are responsible for creating and owning SymbolBodies and
+ InputSections/Chunks.
+* Writer
+ The writer is responsible for writing file headers and InputSections/Chunks to a file.
+ It creates OutputSections, put all InputSections/Chunks into them,
+ assign unique, non-overlapping addresses and file offsets to them,
+ and then write them down to a file.
+* Driver
+ The linking process is driven by the driver. The driver
+ - processes command line options,
+ - creates a symbol table,
+ - creates an InputFile for each input file and put all symbols in it into the symbol table,
+ - checks if there's no remaining undefined symbols,
+ - creates a writer,
+ - and passes the symbol table to the writer to write the result to a file.
+Link-Time Optimization
+LTO is implemented by handling LLVM bitcode files as object files.
+The linker resolves symbols in bitcode files normally. If all symbols
+are successfully resolved, it then runs LLVM passes
+with all bitcode files to convert them to one big regular ELF/COFF file.
+Finally, the linker replaces bitcode symbols with ELF/COFF symbols,
+so that they are linked as if they were in the native format from the beginning.
+The details are described in this document.
+ Short for Relative Virtual Address.
+ Windows executables or DLLs are not position-independent; they are
+ linked against a fixed address called an image base. RVAs are
+ offsets from an image base.
+ Default image bases are 0x140000000 for executables and 0x18000000
+ for DLLs. For example, when we are creating an executable, we assume
+ that the executable will be loaded at address 0x140000000 by the
+ loader, so we apply relocations accordingly. Result texts and data
+ will contain raw absolute addresses.
+* VA
+ Short for Virtual Address. For COFF, it is equivalent to RVA + image base.
+* Base relocations (COFF)
+ Relocation information for the loader. If the loader decides to map
+ an executable or a DLL to a different address than their image
+ bases, it fixes up binaries using information contained in the base
+ relocation table. A base relocation table consists of a list of
+ locations containing addresses. The loader adds a difference between
+ RVA and actual load address to all locations listed there.
+ Note that this run-time relocation mechanism is much simpler than ELF.
+ There's no PLT or GOT. Images are relocated as a whole just
+ by shifting entire images in memory by some offsets. Although doing
+ this breaks text sharing, I think this mechanism is not actually bad
+ on today's computers.
+* ICF
+ Short for Identical COMDAT Folding (COFF) or Identical Code Folding (ELF).
+ ICF is an optimization to reduce output size by merging read-only sections
+ by not only their names but by their contents. If two read-only sections
+ happen to have the same metadata, actual contents and relocations,
+ they are merged by ICF. It is known as an effective technique,
+ and it usually reduces C++ program's size by a few percent or more.
+ Note that this is not entirely sound optimization. C/C++ require
+ different functions have different addresses. If a program depends on
+ that property, it would fail at runtime.
+ On Windows, that's not really an issue because MSVC link.exe enabled
+ the optimization by default. As long as your program works
+ with the linker's default settings, your program should be safe with ICF.
+ On Unix, your program is generally not guaranteed to be safe with ICF,
+ although large programs happen to work correctly.
+ LLD works fine with ICF for example.
diff --git a/docs/ReleaseNotes.rst b/docs/ReleaseNotes.rst
new file mode 100644
index 000000000000..79b8c2f88d72
--- /dev/null
+++ b/docs/ReleaseNotes.rst
@@ -0,0 +1,35 @@
+LLD 3.9 Release Notes
+.. contents::
+ :local:
+.. warning::
+ These are in-progress notes for the upcoming LLVM 3.9 release.
+This document contains the release notes for the LLD linker, release 3.9.
+Here we describe the status of LLD, including major improvements
+from the previous release. All LLD releases may be downloaded
+from the `LLVM releases web site <http://llvm.org/releases/>`_.
+Non-comprehensive list of changes in this release
+ELF Improvements
+* Initial support for LTO.
+COFF Improvements
+* Item 1.
+MachO Improvements
+* Item 1.
diff --git a/docs/conf.py b/docs/conf.py
index 99866e1bd1e1..88fcdd8afcae 100644
--- a/docs/conf.py
+++ b/docs/conf.py
@@ -11,6 +11,7 @@
# serve to show the default.
import sys, os
+from datetime import date
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here. If the directory is relative to the
@@ -40,7 +41,7 @@ master_doc = 'index'
# General information about the project.
project = u'lld'
-copyright = u'2011-2014, LLVM Project'
+copyright = u'2011-%d, LLVM Project' % date.today().year
# The version info for the project you're documenting, acts as replacement for
# |version| and |release|, also used in various other places throughout the
diff --git a/docs/design.rst b/docs/design.rst
index 408b8acaf890..14d180936902 100644
--- a/docs/design.rst
+++ b/docs/design.rst
@@ -150,37 +150,6 @@ into an Atom graph. For instance, you may want the Reader to only accept
certain architectures. The options class can be instantiated from command
line options, or it can be subclassed and the ivars programmatically set.
-ELF Section Groups
-Reference : `ELF Section Groups <http://mentorembedded.github.io/cxx-abi/abi/prop-72-comdat.html>`_
-C++ has many situations where the compiler may need to emit code or data,
-but may not be able to identify a unique compilation unit where it should be
-emitted. The approach chosen by the C++ ABI group to deal with this problem, is
-to allow the compiler to emit the required information in multiple compilation
-units, in a form which allows the linker to remove all but one copy. This is
-essentially the feature called COMDAT in several existing implementations.
-The COMDAT sections in ELF are modeled by using '.group' sections in the input
-files. Each '.group' section is associated with a signature. The '.group'
-section has a list of members that are part of the the '.group' which the linker
-selects to appear in the input file(Whichever .group section appeared first
-in the link). References to any of the '.group' members can also appear from
-outside the '.group'.
-In lld the the '.group' sections with COMDAT are identified by contentType(
-typeGroupComdat). The '.group' members are identified by using
-**kindGroupChild** references.
-The point to be noted here is the 'group child' members would need to be emitted
-in the output file **iff** the group was selected by the resolver.
-This is modeled in lld by removing the 'group child' members from the
-definedAtom List.
-Any reference to the group-child from **outside the group** is referenced using
-a 'undefined' atom.
diff --git a/docs/index.rst b/docs/index.rst
index 88c6f217531a..d019c4f9fd8c 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -4,55 +4,12 @@ lld - The LLVM Linker
lld contains two linkers whose architectures are different from each other.
-One is a linker that implements native features directly.
-They are in `COFF` or `ELF` directories. Other directories contains the other
-implementation that is designed to be a set of modular code for creating
-linker tools. This document covers mainly the latter.
-For the former, please read README.md in `COFF` directory.
-* End-User Features:
- * Compatible with existing linker options
- * Reads standard Object Files (e.g. ELF, Mach-O, PE/COFF)
- * Writes standard Executable Files (e.g. ELF, Mach-O, PE)
- * Remove clang's reliance on "the system linker"
- * Uses the LLVM `"UIUC" BSD-Style license`__.
-* Applications:
- * Modular design
- * Support cross linking
- * Easy to add new CPU support
- * Can be built as static tool or library
-* Design and Implementation:
- * Extensive unit tests
- * Internal linker model can be dumped/read to textual format
- * Additional linking features can be plugged in as "passes"
- * OS specific and CPU specific code factored out
-Why a new linker?
-The fact that clang relies on whatever linker tool you happen to have installed
-means that clang has been very conservative adopting features which require a
-recent linker.
-In the same way that the MC layer of LLVM has removed clang's reliance on the
-system assembler tool, the lld project will remove clang's reliance on the
-system linker tool.
-Current Status
-lld can self host on x86-64 FreeBSD and Linux and x86 Windows.
-All SingleSource tests in test-suite pass on x86-64 Linux.
+.. toctree::
+ :maxdepth: 1
-All SingleSource and MultiSource tests in the LLVM test-suite
-pass on MIPS 32-bit little-endian Linux.
+ NewLLD
+ AtomLLD
@@ -66,24 +23,3 @@ lld is also available via the read-only git mirror::
git clone http://llvm.org/git/lld.git
Put it in llvm's tools/ directory, rerun cmake, then build target lld.
-.. toctree::
- :maxdepth: 2
- design
- getting_started
- development
- windows_support
- open_projects
- sphinx_intro
-Indices and tables
-* :ref:`genindex`
-* :ref:`search`
-__ http://llvm.org/docs/DeveloperPolicy.html#license
diff --git a/docs/open_projects.rst b/docs/open_projects.rst
index 448e967b5536..eeb9f9f48f34 100644
--- a/docs/open_projects.rst
+++ b/docs/open_projects.rst
@@ -4,11 +4,6 @@ Open Projects
.. include:: ../include/lld/Core/TODO.txt
-.. include:: ../lib/Driver/TODO.rst
-.. include:: ../lib/ReaderWriter/ELF/X86_64/TODO.rst
-.. include:: ../lib/ReaderWriter/ELF/AArch64/TODO.rst
-.. include:: ../lib/ReaderWriter/ELF/ARM/TODO.rst
-.. include:: ../tools/lld/TODO.txt
Documentation TODOs