[LLVMdev] LLD improvement plan

[Rui Ueyama]

Hi guys, After working for a long period of time on LLD, I think I found a
few things that we should improve in the LLD design for both development
ease and runtime performance. I would like to get feedback on this
proposal. Thanks! *Problems with the current LLD architecture *The current
LLD architecture has, in my opinion, two issues.

*The atom model is not the best model for some architectures *The atom
model makes sense only for Mach-O, but it’s used everywhere. I guess that
we originally expected that we would be able to model the linker’s behavior
beautifully using the atom model because the atom model seemed like a
superset of the section model. Although it *can*, it turned out that it’s
not necessarily natural and efficient model for ELF or PE/COFF on which
section-based linking is expected. On ELF or PE/COFF, sections are units of
atomic data. We divide a section into smaller “atoms” and then restore the
original data layout later to preserve section’s atomicity. That
complicates the linker internals. Also it slows down the linker because of
the overhead of creating and manipulating atoms. In addition to that, since
section-based linking is expected on the architectures, some linker
features are defined in terms of sections. An example is “select largest
section” in PE/COFF. In the atom model, we don’t have a notion of sections
at all, so we had to simulate such features using atoms in tricky ways.

*One symbol resolution model doesn’t fit all *The symbol resolution
semantics are not the same on three architectures (ELF, Mach-O and
PE/COFF), but we only have only one "core" linker for the symbol
resolution. The core linker implements the Unix linker semantics; the
linker visits a file at a time until all undefined symbols are resolved.
For archive files having circular dependencies, you can group them to tell
the linker to visit them more than once. This is not the only model to
create a linker. It’s not the simplest nor fastest. It’s just that the Unix
linker semantics is designed this way, and we all follow for compatibility.
For PE/COFF, the linker semantics are different. The order of files in the
command line doesn’t matter. The linker scans all files first to create a
map from symbols to files, and use the map to resolve all undefined
symbols. The PE/COFF semantics are currently simulated using the Unix
linker semantics and groups. That made the linker inefficient because of
the overhead to visit archive files again and again. Also it made the code
bloated and awkward. In short, we generalize too much, and we share code
too much.

*Proposal*

   1. Re-architect the linker based on the section model where it’s
   appropriate.
   2. Stop simulating different linker semantics using the Unix model.
   Instead, directly implement the native behavior.

When it’s done, the atom model will be used only for Mach-O. The other two
will be built based on the section model. PE/COFF will have a different
"core" linker than Unix’s. I expect this will simplify the design and also
improve the linker’s performance (achieving better performance is probably
the best way to convince people to try LLD). I don’t think we can gradually
move from the atom model to the section model because atoms are everywhere.
They are so different that we cannot mix them together at one place.
Although we can reuse the design and the outline the existing code, this is
going to be more like a major rewriting rather than updating. So I propose
developing section-based ports as new "ports" of LLD. I plan to start
working on PE/COFF port first because I’m familiar with the code base and
the amount of code is less than the ELF port. Also, the fact that the ELF
port is developed and maintained by many developers makes porting harder
compared to PE/COFF, which is written and maintained only by me. Thus, I’m
going to use PE/COFF as an experiment platform to see how it works. Here is
a plan.

   1. Create a section-based PE/COFF linker backend as a new port
   2. If everything is fine, do the same thing for ELF. We may want to move
   common code for a section-based linker out of the new PE/COFF port to share
   it with ELF.
   3. Move the library for the atom model to the sub-directory for the
   Mach-O port.

The resulting linker will share less code between ports. That’s not
necessarily a bad thing -- we actually think it’s a good thing because in
order to share code we currently have too many workarounds. This change
should fix the balance so that we get (1) shared code that’s naturally able
to be shared by multiple ports, and (2) simpler, faster code.
*Work Estimation *It’s hard to tell, but I’m probably able to create a
PE/COFF linker in a few weeks, which works reasonably well and ready for
code review as a first set of patches. I have already built a complete
linker for Windows, so the hardest part (understanding it) is already done.
Once it’s done, I can get a better estimation for ELF.
*Caveat **Why not define a section as an atom and keep using the atom
model? *If we do this, we would have to allow atoms to have more than one
name. Each name would have an offset in the atom (to represent symbols
whose offset from the section start is not zero). But still we need to copy
section attributes to each atom. The resulting model no longer looks like
the atom model, but a mix of the atom model and the section model, and that
comes with the cost of both designs. I think it’s too complicated.

*Notes*
We want to make sure there’s no existing LLD users who depend on the atom
model for ELF, or if there’s such users, we want to come up with a
transition path for them.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150501/4db15a0c/attachment.html>