llvm dev - Oct 2004 - [LLVMdev] Automatic Loadable Linker Optimization Modules

Hi,

I'm soliciting feedback on a design feature for llvm-ld, loadable linker 
optimization modules.

The Problem:

The llvm-ld tool expects that the bytecode files it is linking to already have 
been compile-time optimized appropriately. When it links all the bytecode 
together, it needs to apply link-time optimizations, if appropriate. The 
problem is, because of various front-ends involved, it is not reasonable for 
llvm-ld to "know" which passes to be run. Furthermore, front-ends may
have
specific passes they need to be run at link time (e.g. C++ template generation, 
or optimizing exception handling which wouldn't be applicable to modules 
compiled from C or Scheme or Stacker).

Goal:
Have llvm-ld automatically load (similar to opt --load=libPasses.so ) link-time 
optimization passes based on the bytecode it is linking.

Issues:
1. Should the loadable module be a native .so or a bytecode library?
2. How does the linker automatically know which loadable modules to load? What
    in the bytecode lets it know the modules to load and run?
3. How does llvm-ld find the loadable modules?
4. When do the passes in the loaded module run? Before standard passes, after
    them or intermingled?
5. What's the interface between llvm-ld and the passes in the loadable
module?
6. How do we identify which passes to run given the various -On options?

Current Thinking On Issues:
1. Only native .so
2. Augment the bytecode to specify the language from which it is compiled.
    Provide the necessary module information via the language-specific
    configuration files that llvmc uses.
3. Loadable modules need to be installed in the LLVM lib directory like any
    other library. Have llvm-ld look there.
4. Standard passes are run first. llvm-ld doesn't run the passes
individually,
    it just invokes the loaded module to run them for it. That way the module
    has complete freedom to run passes it needs.
5. A single function in the loaded module is called. That function is passed
    three things: the Module* to be optimized, the optimization level to apply,
    and a list of the passes already made (so the module can eliminate redundant
    passes). The loaded module may return a Module* to replace the previous one
    or null to indicate that the original Module* passed in should be used for
    further loaded modules.
6. Leave it up to the loaded module.

Thoughts on this?

Reid

On Thu, 28 Oct 2004, Reid Spencer wrote:
> The llvm-ld tool expects that the bytecode files it is linking to already
have
> been compile-time optimized appropriately. When it links all the bytecode
Ok.
> together, it needs to apply link-time optimizations, if appropriate. The
> problem is, because of various front-ends involved, it is not reasonable
> for llvm-ld to "know" which passes to be run. Furthermore,
front-ends
> may have specific passes they need to be run at link time (e.g. C++
> template generation
Hrm, C++ template emission is not really an LLVM-to-LLVM transformation,
and I don't think we should worry about it at all for now.  In the future,
allowing the front-end to provide hooks to be executed at link time (and
some way for the linker to get the code) would be useful.  I think that HP
linker has some way of doing this for example.  The portions of this paper
(e.g. sec 3.3) that talks about plugging stuff into their linker may be
interesting to you (and there are probably better sources as well):

http://www.cgo.org/cgo2004/papers/05_77_moon_s.pdf
>, or optimizing exception handling which wouldn't be
> applicable to modules compiled from C or Scheme or Stacker).
Actually, EH optimization is equally applicable to C programs as C++,
because they may call setjmp/longjmp.  I'm sure that scheme has a way of
unwinding too.

The basic point is that the optimization won't HURT the program, it just
might increase linking times.  Because we have a problem where it's
possible to have any combination of object files from any source
languages, I don't know of a scalable way to represent which opts should
be run.  For now, I recommend just leaving it hard coded.
> Goal:
> Have llvm-ld automatically load (similar to opt --load=libPasses.so )
link-time
> optimization passes based on the bytecode it is linking.
That is fine, but I don't think that it should be the default.  Large
shared objects are noticably slow to load and slow to execute (PIC mode
code).
> Issues:
> 1. Should the loadable module be a native .so or a bytecode library?
Why would we want to load LLVM bytecode into the linker?
> 3. How does llvm-ld find the loadable modules?
The llvmc config?  LLVMC could pass this down to llvm-ld.
> 5. What's the interface between llvm-ld and the passes in the loadable
module?
The standard interface is fine: passes just get added in a particular
order to a pass manager, then they are run.
> 2. How does the linker automatically know which loadable modules to load?
What
>     in the bytecode lets it know the modules to load and run?
> 4. When do the passes in the loaded module run? Before standard passes,
after
>     them or intermingled?
> 6. How do we identify which passes to run given the various -On options?
These are the hard questions.  I have no easy answer for you :)

-Chris
> Current Thinking On Issues:
> 1. Only native .so
> 2. Augment the bytecode to specify the language from which it is compiled.
>     Provide the necessary module information via the language-specific
>     configuration files that llvmc uses.
> 3. Loadable modules need to be installed in the LLVM lib directory like any
>     other library. Have llvm-ld look there.
> 4. Standard passes are run first. llvm-ld doesn't run the passes
individually,
>     it just invokes the loaded module to run them for it. That way the
module
>     has complete freedom to run passes it needs.
> 5. A single function in the loaded module is called. That function is
passed
>     three things: the Module* to be optimized, the optimization level to
apply,
>     and a list of the passes already made (so the module can eliminate
redundant
>     passes). The loaded module may return a Module* to replace the previous
one
>     or null to indicate that the original Module* passed in should be used
for
>     further loaded modules.
> 6. Leave it up to the loaded module.
>
> Thoughts on this?
>
> Reid
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-Chris

-- 
http://llvm.org/
http://nondot.org/sabre/