[LLVMdev] LLVM for numerical computations

[Luc Bourhis]

Hello there,

I am considering to use LLVM as part of a numerical software. I have  
never used LLVM, but I have tried to thoroughly read the material  
available on llvm.org. I would appreciate some early pointers. Please  
bare with me as I explained the matter as concisely as possible! And  
you can already see this is not going to be that concise…

The part of our project LLVM could be relevant to has to do with  
automatic numerical differentiation. Basically we have a  
computational tree whose leaves are independent variables whereas any  
other node is a dependent variable, i.e. its value depends on the  
value of its children through some function. Finally the head of the  
tree is the final result we are interested in. One of the requirement  
is that the set of those functions is open-ended. The tree can have  
from 50 to a few thousands nodes and it is typically evaluated  
several 1000 times for different values of the leaves  (i.e. a  
forward sweep to compute the values followed by a reverse sweep to  
compute the derivatives, c.f. [*]).

Here is where I was thinking to use LLVM. Instead of actually  
computing its value and derivatives, each node could feature two  
member functions value_by_LLVM and derivatives_by_LLVM which would  
produce the LLVM code necessary to respectively compute the value and  
the derivatives, each packaged as a function I guess. A visitor  
marching through the computational tree would then assemble the calls  
to those LLVM functions to compute the head (forward sweep), then  
another visitor would assemble the function calls to compute the  
derivatives (reverse sweep) -- it should be noted that the values  
computed during the forward sweep may be needed during the reverse  
sweep but it is not always the case. The LLVM JIT would  then  
optimise the code and compile it to native code and execute it.

As I wrote, the function is evaluated 1000 times, and it seems to me  
that the overhead of assembling the LLVM code, optimising and  
compiling it during the first execution would not be significant  
overhaul. It also seems to me that LLVM would generate very efficient  
code.

Am I correct? Does it make sense to use LLVM for such a purpose?

How would the functions defined in <cmath> be called from the LLVM code?

How would I best specify in LLVM where to find the values of the  
independent variables? That is to say the inputs for the whole  
computation LLVM will perform…

You may actually wonder why I do not kit each node with two member  
functions compute_value and compute_derivatives by the by. Virtual  
calls would be involved for each of them on each node every time and  
it turns out that those functions are typically not very complex,  
which makes the cost of a virtual call significant. I should also  
mention that our golden standard is some old fashion but extremely  
fast FORTRAN program (which has only a fixed hard-wired set of types  
of node but our potential users are not quite ready to sacrifice  
speed for flexibility, the eternal story in numerical computation…).


[*] This is not quite exact: in fact we use the so-called reverse  
mode and therefore we actually propagate the derivatives from head to  
leaves but this does not matter at the level of this discussion.