[LLVMdev] Proposal: MCLinker - an LLVM integrated linker

[Nick Kledzik]

On Nov 1, 2011, at 6:26 PM, Michael Spencer wrote:
> A major feature of the linker design I have been working on is the
> object file IR it is based on. It takes the concept of an atom (a
> named range of data) and formalizes it into a graph based data
> structure where edges represent the relations between atoms such as
> relocations, groupings, and layout constraints. This provides a format
> for the core linker algorithms to work on, and also for plugins and
> file-format specific processing to happen. This can also enable more
> efficent intermidate object and debug file formats.


This is, in fact, how Apple's linker (http://www.opensource.apple.com/source/ld64/ld64-127.2) works.

We realized a few years back that the traditional way of linking (section merging) made advanced linker features very difficult.  The kinds of features Apple wanted were (and still are): dead code stripping, weak symbol coalescing, and order files (functions and data are re-ordering to minimize runtime RAM footprint).  A better model is based on Atoms (nodes).  An Atom is an indivisible subrange of a section.  Atoms have References/Fixups (edges) to other Atoms.  As Michael said, once you have your object file data in this representation, all the linker algorithms are much simpler.  

The hard part of linking is parsing object files into Atoms.  ELF should be a little easier because the symbol table has the st_size field.  But there are lots of cases (like dwarf unwind info) where symbol table entries are not created.  


Nick Kledzik
Linker Engineer
Apple Inc.