[LLVMdev] Proposal: MCLinker - an LLVM integrated linker

[Chinyen Chou]

Thanks for the useful information. We notice that the idea of LIPO also can
help LLVM LTO if LLVM has FDO/PGO. And regarding Diablo, we'll learn from
it and I think we'll get some good ideas from it.

In MCLinker, the detail of the instructions and data in bitcode are still
kept during linking, so some opportunities to optimize the instruction in
bitcode become intuitive. Instruction relaxation is one of the cases.
(Since ARM is one of the target we focus on, I'm going to use ARM to
illustrate the problem.)

When linking bitcode and other object files, stubs are necessary if the
branch range is too far or ARM/THUMB mode switching. Google gold linker
uses two kinds of stubs basically. One is consecutive branch instructions,
and the other is one branch instruction with one following instruction
(e.g., ldr) which changes PC directly.

Example of the later cases,

1: bl    <stub_address>
...
2: ldr   pc, [pc, #-4]   ; stub
3: dcd   R_ARM_ABS32(X)

In MCLinker, we can optimize it as following:

X: ldr   ip, [pc, #-4]
Y: dcd   R_ARM_ABS32(X)
Z: bx    ip

Before optimization, some processors suffer from flushing ROB/Q because
their pipelines are fulfilled with the invalid instructions that
immediately appear after ldr. However, all of these instructions should not
be executed, and processors must flush them when ldr is committed.

Since all details of instruction and data are reserved, MCLinker can
directly rewrite the program without insertion of stub. It can replace the
1:bl instruction with a longer branch Z: bx, and the performance of the
program is therefore improved by efficient use of branch target buffer
(BTB).
This is just one case, and there are other optimizations we can do..

Thanks,
Chinyen

> In GCC, LTO causes 'fat' object files, because GCC needs to serialize
> > IR into 'intermediate language' (IL) and compress IL in object files.
> > In our experience, the 'fat' object files are x10 bigger than the
> > original one, and slow down the linking process significantly. The
> > generated code can get about only 7%~13% improvement.
>
> Right.  Though GCC 4.7 will offer an option to emit just bytecode in
> object files.  Additionally, the biggest gains we generally observe
> with LTO is when it's coupled with FDO.  And almost always, the
> biggest wins are in the inliner
> (http://gcc.gnu.org/wiki/LightweightIpo).
>
> > Apart from the LTO, we also have some good idea on link time
> > optimization. I will open another thread to discuss this later.
>
> You may want to look at Diablo (http://diablo.elis.ugent.be/).  An
> optimizing linker that has been around for a while.  I'm not sure
> whether it is still being developed, but they had several interesting
> ideas in it.
>
>
> Diego.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111102/fb517538/attachment.html>