Tag: compilers

August 24, 2008 Technology Post a Comment

Erlang on LLVM? or: Outsource your JIT!

Has anyone been working on using [LLVM][1] to do just-in-time code generation for the [Erlang][2] virtual machine?

Depending on the design and structure of the Erlang virtual machine, it doesn’t seem like it would be all that tough a project. And it could provide a nice performance boost for those projects that are starting to use Erlang like [CouchDB][3] and [ejabberd][4].

For an example of what I’m talking about, there’s a project called [VMKit][5] that has implemented the Java and .NET virtual machines atop LLVM with reasonable performance. Essentially, if you have a virtual machine, rather than skipping either just-in-time or static code generation entirely, or trying to do it all yourself for some specific platform on which you want to run, take a look at what you can do with LLVM and see if you can leverage its code generation instead.

[1]: http://llvm.org/
[2]: http://erlang.org/
[3]: http://couchdb.org/
[4]: http://www.ejabberd.im/
[5]: http://www.ejabberd.im/

July 18, 2008 Technology Post a Comment

LLVM terminology

I thought the proper terminology was worth pointing out, since I’ve seen — and heard — some misuses lately.

* **[LLVM][1]** is the Low-Level Virtual Machine and the project surrounding it.

* **[LLVM-GCC][2]** is a compiler that uses GCC for its front-end and LLVM for its back-end.

* **[Clang][3]** is the C language family front-end that is part of the LLVM project. It’s a parser, semantic analyzer, and code generator — in other words, a compiler front-end that uses LLVM for its back-end.

* **[The Clang Static Analyzer][4]** is what people have been trying out lately, to find subtle bugs in their and other projects. It’s a great tool.

I just thought this was important to mention, because people have been referring to “LLVM” instead of “LLVM-GCC” in reference to the compiler included in Xcode 3.1, and people have been referring to “Clang” instead of “the Clang Static Analyzer” in reference to what they’ve been using to find bugs in their projects.

[1]: http://llvm.org/
[2]: http://llvm.org/docs/CommandGuide/html/llvmgcc.html
[3]: http://clang.llvm.org/
[4]: http://clang.llvm.org/StaticAnalysis.html

April 26, 2008 Technology 2 Comments

Build LLVM and clang!

I’ve talked about the LLVM Compiler Infrastructure in the past, but what I haven’t talked about yet is just how easy and quickly you can build it on your own Mac running Leopard! This is a great way to get into hacking on compiler lexical analyzers and parsers, code generators, optimizers, and so on.

What’s more, you can build both LLVM and the new C front-end clang very easily and in five to ten minutes.

First, create a work area to check them out into, wherever you normally create your projects. 

[~]% cd /Projects
[/Projects]% mkdir LLVM
[/Projects]% cd LLVM
[/Projects/LLVM]%

Then check out LLVM itself and clang from the LLVM Subversion repository. 

[/Projects/LLVM]% svn checkout http://llvm.org/svn/llvm-project/llvm/trunk llvm
[/Projects/LLVM]% cd llvm/tools
[/Projects/LLVM/llvm/tools]% svn checkout http://llvm.org/svn/llvm-project/cfe/trunk clang
[/Projects/LLVM/llvm/tools]% cd ../..
[/Projects/LLVM]%

Then edit the PARALLEL_DIRS definition in llvm/tools/Makefile to tell it about clang. Just add clang onto the end, like this: 

PARALLEL_DIRS := llvm-config  \
                 opt llvm-as llvm-dis \
                 llc llvm-ranlib llvm-ar llvm-nm \
                 llvm-ld llvm-prof llvm-link \
                 lli gccas gccld llvm-extract llvm-db \
                 bugpoint llvm-bcanalyzer llvm-stub llvmc2 \
                 clang

Now create a directory to build into, next to your llvm directory, and change into it. 

[/Projects/LLVM]% mkdir build
[/Projects/LLVM]% cd build
[/Projects/LLVM/build]%

This is where you’ll actually run configure. This will ensure your source tree isn’t polluted with build products, and that everything stays self-contained while you hack. 

[/Projects/LLVM/build]% ../llvm/configure --enable-targets=host-only
# lots of logging
[/Projects/LLVM/build]%

You’ll note that above I passed an argument to configure. This ensures that LLVM is only built to target the architecture I’m running on, to speed up the build process; this is generally fine for simple front-end development.

Now, to build LLVM as well as clang all I have to do is invoke make. LLVM is set up to correctly do parallel builds, so I’ll pass the number of CPUs I have in my machine via make -j 4. 

[/Projects/LLVM/build]% make -j 4
# lots of logging
[/Projects/LLVM/build]%

That’s it! LLVM is now (hopefully) successfully built. All of the pieces are in the build directory under Debug/bin and Debug/lib and so on; see the LLVM web site for details about what the various components are.

July 16, 2007 Technology Post a Comment

LLVM Developers’ Meeting 2007-05

The LLVM Compiler Infrastructure is a great technology that came out of the computer science research community and can be used to develop extensible compiler platforms. Among other things, it provides a platform-independent assembly and object code (the “low level virtual machine” that its name is taken from), and a great object-oriented compilation, linking, optimization and code-generation infrastructure that you can use to efficiently target real hardware. The main idea is that LLVM provides a comprehensive back-end that you can easily build a front-end to target.

There’s a huge amount of material available on the LLVM web site, including the LLVM Assembly Language Reference Manual and LLVM Programmer’s Manual, a wide variety of papers on LLVM, and a great walkthrough of the creation of Stacker, a Forth front-end that targets LLVM. It shows how the budding language creator might leverage the tools available as part of the LLVM infrastructure. I fully expect that in time, “little languages” will have no excuse not to be JIT compiled simply because targeting LLVM is actually easier than writing your own interpreter or bytecode engine! Just walk your AST and generate naïve LLVM code for what you encounter, and let the infrastructure handle the rest. (For those who aren’t developer tools weenies, an Abstract Syntax Tree is the internal representation of a program’s structure before it’s turned into instructions to execute.)

A couple months back, the May 2007 LLVM Developers’ Meeting was held at Apple. The proceedings from this meeting — the actual session content, both in slides and in video form — are available online, and I’ve even created an LLVM Developers’ Meeting podcast (including a subscribe-directly-in-iTunes version) for easy viewing. The video may be low bit rate, but it has a 16:9 aspect ratio so you can even pretend it’s HD. (I put together the podcast primarily so I could watch the sessions on my Apple TV, since I couldn’t attend the meeting.)

So if you’re at all interested in compilers, language design or development, optimization, or development platforms in general, you’ll be very well-served by checking out LLVM. It is a seriously cool enabling technology.

September 12, 2006 Technology Post a Comment

It’s not the dynamic dispatch!

Joel has decided to blame the use of dynamic dispatch for Ruby’s speed issues:

Without knowing much about the implementation of Ruby, I would guess that the biggest issue is around late binding and especially duck typing, which prevents type inference or strong typing, which means that function calls will always be slow because you can never get something compiled down to the point where a function call is just a single CALL instruction (on x86)… you always have to be exploring the object, possibly even scanning a hash table to find the function you want to call.

In other words, “it’s always going to be slow because if it’s not strongly-typed it can’t be statically compiled to the most minimal possible instruction sequence!” Which is, simply put, a bullshit argument even if you ignore the fact that he said right up front it was bullshit.

There’s a lot that you can do to optimize dynamic dispatch. If you don’t believe me, take a look at the implementation of the Apple/NeXT Objective-C runtime, objc4. Go ahead, it’s Open Source. (The link is for the version that’s part of Mac OS X 10.4.7 for Intel processors.) It implements full Smalltalk-style dynamic dispatch — the same type of dynamic dispatch that Ruby uses. And what’s more, Ridiculous Fish also wrote a great article on how dynamic dispatch is implemented in the objc_msgSend() primitive — with particular attention focused on its performance characteristics!

No, it’s not message-based dynamic dispatch or “duck typing” (runtime polymorphism) that makes Ruby slow. It’s the fact that Ruby is a single-pass interpreted language. It’s not compiled to bytecode. It’s not compiled to native code. It’s scanned, parsed, and then immediately executed.

Imagine if your C compiler, or your Fortran compiler, or your Java compiler — or your Visual Basic compiler, for that matter — had to be invoked every time you ran your program. Imagine how slow that would be! That’s essentially what Ruby is doing, and that’s why it’s slow. Ruby 2.0 is planned to run on the YARV virtual machine, and there has also been work to compile Ruby code for LLVM. There’s nothing in Ruby’s nature that makes this a particularly difficult problem, especially since all of the issues of efficiently compiling dynamic languages with reflection and self-modification features were solved by Lisp in the 1960s and Smalltalk in the 1970s.

Incidentally, this is why I react so vehemently when people talk about “Lisp interpreters.” Lisp is almost never interpreted, specifically to avoid these types of performance issues. At the least most Lisp systems compile to a custom bytecode and then use an optimized bytecode engine to execute that. That way they can eliminate the scanning and parsing overhead — yes, it does exist for Lisp, because contrary to what Lispers may say, the language does have syntax — while still stay portable.

Others have also been piling on, such as Avi Bryant and Obie Fernandez. As Obie points out, Avi knows what he’s talking about. And so do folks who work with Objective-C intimately, day in and day out.