llvm dev - Sep 2003 - [LLVMdev] LLVM for dynamic languages

How suitable do the developers think that LLVM would be as a code-generator 
for a dynamically typed langage? Would the lack of static type information 
make the traditional code optimizations performed by LLVM relatively 
ineffective? 

Sincerely,
	Rayiner Hashem

On Thu, 11 Sep 2003, Rayiner Hashem wrote:
> How suitable do the developers think that LLVM would be as a code-generator
> for a dynamically typed langage? Would the lack of static type information
> make the traditional code optimizations performed by LLVM relatively
> ineffective?
LLVM is designed to be able to support "any" language, efficiently,
without restriction.  However, the mapping for some languages may not be a
clean as for others (lots of casting might be involved for example).  That
said, many dynamic languages should be cleanly mappable to the LLVM layer.
What are you thinking about in particular?

As far as the optimizations already in LLVM: LLVM provides an excellent
infrastructure for interprocedural optimizations.  As such, I would
recommend writing some language tuned optimizations (as necessary) that
would lower the dynamic objects into the primitives the optimizers
already understand.

For example, think of a language like smalltalk (the most dynamic language
that I know of).  Say you have a program that looks like this:

(8*(4/2)) print

The LLVM constant folding optimizations will not be able to fold these
constants, because they are actually instances of the SmallInteger class,
which have dynamically dispatched messages to perform the operations.

Now, however, if you preceed the standard LLVM optimizations with some
simple partial evaluation/resolution transformations, you can show that *
and / will resolve to the implementations in the SmallInteger class.  As
such, you can convert it to a direct call, have it inlined, and the
objects themselves would be turned into primitives.

If you can express the method dispatch in a way that is useful to the
preexisting optimizations, of course, you wouldn't have to do anything
special to support this (C++/Java v-tables fit into the catagory).

Basically the idea is that some optimizations are much more important to
certain languages than others.  In this case, it's method resolution, for
functional languages, it's tail call elimination, for C++ it's scalar
replacement of aggregates, etc.

Since LLVM provides the facilities needed to efficiently implement these
types of optimizations, it is a pretty good infrastructure for doing them
in, even though it currently does not support "all possible"
optimizations
out-of-the-box (yet :)

Please let me know if I have confused the issue or missed your question
completely.  :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

> That said, many dynamic languages should be cleanly mappable to the LLVM
> layer. What are you thinking about in particular? 
Not thinking of one in particular right now, but it would probably something 
like an object-oriented Scheme. 
> recommend writing some language tuned optimizations (as necessary) that
> would lower the dynamic objects into the primitives the optimizers
> already understand.
Yep. I'm assuming that a language-specific optimizer would handle things
like
type inference, so the llvm code would either see plain primitives or a 
dynamic representation:

struct object {
	int typecode;
};

struct integer {
	int typecode;
	int value;
};

Thus, the calling code could manipulate integers with pointers to objects. 
> If you can express the method dispatch in a way that is useful to the
> preexisting optimizations, of course, you wouldn't have to do anything
> special to support this (C++/Java v-tables fit into the catagory).
As far as I can see, casting needs to be done only once. All the calling code 
knows is that it has a pointer to an object. After using the typecode to 
lookup the method to call, it calls a given function, passing it the object 
parameter. This function knows the precise llvm type of the object, so it 
needs to cast the object* to (say) an integer*. Come to think of it, C++/Java 
code needs to do the same thing, though the dispatch mechanism is different. 
Since llvm doesn't appear to have any notion of inheritence, C++/Java
virtual
methods should need to cast their 'this' pointer to the precise type. I 
presume this doesn't interfere too much with the other optimizations? 

Sincerely,
	Rayiner Hashem