[LLVMdev] Optimization feasibility

[Joachim Durchholz]

Gordon Henriksen schrieb:
> 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.

I'm not too picky. Unless there are structural reasons that tail call 
support is weak, I think this can be improved if and when the need comes.

>> * 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.

If LLVM *can* be helped out, that's enough.

>> * 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.

Of course not. LLVM is supposed to be low-level after all :-)

> If your runtime finds a more representation, it can modify the IR and
> use LLVM's JIT to recompile a more specialized function, though.

Fair enough. Self-modifying code isn't exactly what will make virus 
scanners and the like happy, but I doubt there's a good way for caching 
JIT results without making them unhappy, so there...

Anyway, as I said: LLVM is a good candidate, and I think I have at least 
a rough ideas how much leverage it will give me.
I'll be back when I have more to report.
And, of course, as questions arise :-)

Regards,
Jo