[LLVMdev] LLD improvement plan

[James Courtier-Dutton]

On 1 May 2015 at 20:31, Rui Ueyama <ruiu at google.com> wrote:
>
> 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.
>

Why can't LLD be free to implement a resolving algorithm that performs better.
The PE/COFF method you describe seems more efficient that the existing
ELF method.
What is stopping LLD from using the PE/COFF method for ELF. It could
also do further optimizations such as caching the resolved symbols.
To me,the existing algorithms read as ELF == Full table scan,  PE/COEF
== Indexed.

Also, could some of the symbol resolution be done at compile time?
E.g. If I include stdio.h, I know which link time library that is
associated with, so I can resolve those symbols at compile time.
Maybe we could store that information in the pre-compiled headers file
format, and subsequently in the .o files.
This would then leave far fewer symbols to resolve at link time.

Kind Regards

James