[LLVMdev] Optimization feasibility

[Gordon Henriksen]

Hi Jo,

On 2007-12-24, at 14:43, Joachim Durchholz wrote:

> I'm in a very preliminary phase of a language project which requires  
> some specific optimizations to be reasonably efficient.
>
> LLVM already looks very good; I'd just like to know whether I can  
> push these optimizations through LLVM to the JIT phase (which, as  
> far as I understand the docs, is a pretty powerful part of LLVM).

Cool.

> The optimizations that I need to get to work are:
>
> * Tail call elimination.

LLVM already has tail call elimination (i.e., it will transform direct  
recursion into iteration). It also supports emitting tail calls on  
x86, but its support is somewhat weak. This is partially mandated by  
calling conventions, but those implementing functional languages might  
be disappointed. Check the llvmdev archives for details.

> * Constant evaluation. To implement this, the JIT phase would have  
> to evaluate the constant and somehow store it so that future runs  
> don't need to reevaluate it.
> * Dead code elimination, enabled by constant evaluation.

LLVM has both constant propagation and dead code elimination, but if  
your language has a high-level functional concept of "constant" here  
(or you're referring to memoization), your runtime may need to help  
LLVM out.

> * Monomorphisation, i.e. constant evaluation may establish that some  
> data structures aren't polymorphic, so it would be worth generating  
> code that keeps integers in registers instead of generating boxed  
> representations on the heap. Again, constant evaluation can enable  
> this optimization.

LLVM will not rearrange your high-level data structures. If your  
runtime finds a more representation, it can modify the IR and use  
LLVM's JIT to recompile a more specialized function, though.

— Gordon