[LLVMdev] Proposal: MCLinker - an LLVM integrated linker

[Tang Luba]

Hi, Nick,

Thanks for your sharing. We also think ATOM is a good idea, and thanks
for you work, the code of APPLE linker is pretty and easy to
understand.

In ELF world, section merging is relatively mature and popular
technique. As my best knowledge, no one defined ATOM for ELF before.
(Now I know Spencer is doing this, and I will reply his mail soon :p)
Most of us are not familiar with the concept of ATOM at first, and
lots of papers and textbooks are about section merging. So, please
forgive me for the conservative at the beginning, in order to make
sure we can archive  a workable linker, I and my team members decided
to adopt section merging.

I think that maybe we can put the ATOM in the roadmap, and adventure
it after we have a workable linker.

Besides the ATOM, I think the features of APPLE linker you mentioned
are also important for us. We lay our first emphasis on section
reordering. In our previous experiments, the order of the sections
highly affects the performance of multimedia codec. So, an easier
approach to change the order of sections are also one of our goal. I
think separate the layout information of a section into the offset
within the file and the size, like AsmLayout and MCSectionData does,
can help section reordering easier.

Garbage collection of sections are another problem that needs a good
approach. Transitive closure of sections is the approach used in
Google gold. We're looking forward a better solution.

Best regards,
Luba

2011/11/2 Nick Kledzik <kledzik at apple.com>:
>
> 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.
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>