The AOT Advantage

In my previous blog post I briefly mentioned PHP, HipHop, and AOT. For readers coming late to the party, HipHop is a native code compilation system for PHP, created by Facebook. The idea is that compiling down a relatively large subset of PHP (basically everything besides eval) to C++ code and passing it to an optimizing compiler can produce a much more efficient program than interpretation alone or even compiling to bytecode in advance and executing that.

Let's look at this same idea, but in relation to Parrot's intended LLVM backend system.

We can start off with a basic PHP compiler. The compiler doesn't need to be particularly fast since compilation happens once in advance. Sure, we don't want compilation to take forever because that slows down development, but it doesn't have the same kind of speed mandate we would have in an interpreted environment where we compile the script every single time we run it.

Our basic, feature-light compiler compiles the PHP code down to PAST. From there we kick in a series of optimization stages. Again, if we know we're doing ahead-of-time compilation, we can add more optimization stages up front and take a little more time to compile. For a release build of a high-throughput application, maybe we really want to swing for the fences with this one and enable every optimization in the book. Let's hope it's a long, well-written book.

We compile the PAST down to Parrot bytecode, after all the optimizations have run their course. At this point, we hand off the bytecode to the LLVM backend. LLVM converts the Parrot bytecode into LLVM IR, and passes that through it's own impressive suite of optimizations. At the end, LLVM spits out a native executable which is screaming fast.

The converse side is a case where we want to shorten the turnaround time, such as when we are doing direct interpretation, or even making executables for debugging purposes and don't want our developers sitting around for a long time waiting for the thing to compile. We don't want to completely avoid optimizations, because after compilation the developers have huge and expensive test suites to run which can take much much longer.

What we do in this case is compile the code to PAST, maybe run a handful of "good bang for the buck" (GBFTB) optimizations like constant folding, and compile the PAST down to bytecode. We'll avoid the last step and just execute the bytecode directly, since this is a debug build. When we run it, the JIT engine will kick in to do basic runtime compilation of detected hot spots, giving us nice speedups for programs with tight loops. The JIT compiler will likewise use a few of the GTFTB optimizations, but won't go crazy; we're doing this at runtime now and we have a user waiting.

There are some people in the world of scripting languages who view the complete lack of native executable support as a virtue. After all, they say, the nature of these languages is fast turnaround; We can make changes and run them directly without needing to invoke a separate compiler to produce a separate executable. Plus, the immediate availability of human-readable source code furthers the common goals of open source software and knowledge sharing.

Fast turnaround, from script to execution, certainly is a virtue--in development. Once we're ready to cut that release however, things change pretty dramatically. At my job, I write some applications in C#. During development, I keep things in "Debug" mode, and do lots of tests very quickly. When it's time to cut that release I change the VisualStudio configuration to "Release" and then click "Build All". Where I was doing incremental debug builds, now I'm doing a full release build with optimizations turned on and debugging symbols stripped out. I also build a separate installer project, and to test everything I need to install the software first and run it from it's installed location. This is a lot of extra cost, but I don't do it frequently. I go from about a 10 second compile time turnaround to almost 10 minutes worth of compilation and installation work. The net result is a faster, better executable for my end users.

In the case of Facebook, using HipHop to compile PHP down to native machine code improves throughput performance by 30%, which translates into lower server load, lower wait times for users and, at the end of the day, real money. Say what you want to about obfuscation of the source code, 30% is nothing to ignore.

I like to think that the Parrot infrastructure will support any workflow that our end users want. Having speedy interpretation around for people who want that is a very good thing, and we do it already. But, having the ability to employ tiered libraries of optimizations and create native machine binaries for fast execution is a very very good thing as well. This is why I keep pushing for our eventual JIT system to also support AOT as well. LLVM will already handle all the nitty-gritty, so the amount of scaffolding we'll have to provide in Parrot is minimal in comparison.

Haskell with LLVM

[Update 23 Feb 2010: I've been informed that this was not a JIT, but instead a native-code generation backend for LLVM demonstrating LLVM's aggressive optimization potential. These numbers are not representative of JIT performance.]

Several people sent me a link to a very interesting blog post yesterday about using LLVM to provide native code generation for Haskell in GHC. I recommend it as an interesting read.

One thing I will point out is that the blog post doesn't really explain the whole situation. He shows plenty of examples where LLVM improved performance, but only mentions briefly that this isn't typical of larger programs and that most programs won't experience as much speed up, if any. So to anybody who reads this remember the caveat that the results aren't typical. JIT speeds some things up and slows some things down. It's not a magic bullet that makes everything better.

Parrot's libJIT framebuilder

I offered a bit of a challenge to my readers a while back, and I mentioned that I had received one (very good) submission from plobsing. It used libJIT to implement a frame builder for Parrot, to replace the old home-brew one that we had been using.

I also hear tell that he's planning a framebuilder using libffi too, although I'll have to talk more about that in a later post.

There were some bumps in the road, however. Regular readers will recognize that between the time he sent me the code and now the big PCC refactor landed, which changed the landscape for anything involving function calls quite substantially. But plobsing persevered, and with some configuration help from our own kid51, we ended up with a very nice working branch running the new framebuilder.

Assuming things test well, I would like to push to get the libjit_framebuilder branch merged into trunk soon. We need testing so here is something you, the reader, can do:

Test the Branch

Checkout the libjit_framebuilder branch and give it a whirl. You want to do this before you have libJIT installed on your system to get a baseline. Parrot should work normally without libJIT installed.

Get libJIT

Getting libJIT is probably the hardest part of the whole process. There don't seem to be any debian packages for downloading, and there definitely don't seem to be any Windows binary installers floating around. Google returns few results when I search for "libjit", mostly Wikipedia and plobsing's own work (not usually a good sign!).

You can download the source to the mainline project HERE, and can apparently download source from a fork of it HERE as well. If you have SVN, you can get the source of the fork from it's googlecode project. I'm not really able to find a repo link for the project mainline. Maybe somebody else can help point me in the right direction for that.

From the source you can type this to get it to build on Linux:

./configure
make
sudo make install

On my machine, I also had to run "sudo ldconfig" to update some kind of cache or something. I don't know the details, but if you're on Linux and it doesn't work, try that.

I have no idea how to get this working on Windows. You may be SOL.

Test the Branch Again

Now that you have libJIT reconfigure, rebuild, and retest Parrot. It should detect libJIT, use it for the framebuilder, and (I hope) you should see some kind of performance improvement. At the very least, it shouldn't be noticeably slower.

Send Reports

If things work on your platform, let us know. If things don't work, we definitely need to know that as well. If you have any information about how to get or build libJIT on various systems, we would love to start compiling some documentation about that too. More information is always better, and if Parrot is going to use libJIT going forward (even as an optional component for some performance improvements) we should all be aware of how to get and use it.

Planning for Lorito

I had an interesting conversation with plobsing this morning about Lorito. He has been wrapping up his work on the libjit-based framebuilder, and is looking to break ground on another project. Specifically, he wanted to start putting together a prototype for Lorito.

I had, along with chromatic and some other people, been thinking about Lorito as a very very low-level language, similar to an assembly language. The idea being that each Lorito op would share a close correspondence with an operation in the JIT engine, and would therefore be trivially easy to compile at runtime.

Plobsing was taking a different approach: He's thinking about a higher-level structured language that we would parse down into native JIT format at build time. There are some merits to this idea and since he mentioned it to me I've been thinking about it more and more. Let's take a look at things in more detail, focusing on LLVM specifically.

First, LLVM uses it's own platform-neutral LLVM bytecode format natively. High-level code is parsed and compiled down to LLVM bytecode which can then be optionally optimized before conversion to machine code. That first part ("parsed and compiled") is expensive: We don't want to be parsing and compiling to LLVM bytecode at runtime, that would eat up any potential gains we could get from JIT in the first place. What we want is for the Lorito code to be compiled only once: during the Parrot build. From there we will have LLVM .bc files which contain the raw bytecode definitions for each op, which can be combined together into large methods or traces and compiled to machine code in one go.

Ops are defined in .ops files, which are currently written in a preprocessed C-like language but which will eventually be rewritten in Lorito. During the build, we want two things to happen: First, we want to compile the Lorito down into machine code, as we currently do with our ops, for interpretted cores (fast core, switch core, etc). Second, we want to compile down the ops into LLVM bytecode for use with the JIT at runtime. By comparison:

Interpretted: Good startup time, Reasonable execution time
JIT'd: Slower startup time, better execution time. Many tradeoffs available between the two (usually in terms of adding/removing optimization stages)

For long running programs, costs necessary to startup the JIT engine can be amortized over the entire execution time, which produces benefits overall.

But, I'm digressing. The goal of Lorito was to produce a language that would be trivially easy to JIT at runtime. I was assuming that what we needed was a very small language to perform the job. However, what's really the most trivial to JIT is LLVM's native bytecode format. If we generate that bytecode at compile time, the runtime costs will stay to a minimum. This means that we can have Lorito be any language of any complexity: The only requirements are that we be able to compile it down to LLVM bytecode, hopefully in a process that isn't overly complex or fraught with error possibilities. So long as the conversion only happens once at build time, it doesn't really matter how complicated it is.

Any parser for anything that's more complicated than assembly language will take development effort. The tradeoff is reduced development effort when we start rewriting the ops in Lorito, and increased inclination to write more things in Lorito than just ops. For instance, rewriting PMCs and their VTABLEs in Lorito means that we can start exposing those to the JIT as well. The more of Parrot that we expose to the JIT, the more gains there are to be had from it.

Assuming Lorito is going to now be a relatively high-level structured language as plobsing suggests, the question now is what should it look like? Should it be C, or like C? Should it be NQP, or like NQP? NQNQP?

As a thought experiment, consider the case where Lorito is C. In that case, our ops and VTABLEs are already all written in Lorito, and we already have a Lorito compiler available (LLVM). In this case, there are only a handful of steps to do before Parrot has a working (if naive) JIT:

1. Add a configure probe to detect LLVM
2. During the build, compile down ops to LLVM Bytecode, in addition to everything else we already do with them
3. Add a utility function to compile a stream of bytecode (such as an entire Sub) to machine code using the LLVM bytecode.
4. Add a way (such as in the Sub invoke VTABLE) to cache methods that have already been compiled, and add a switching mechanism to invoke that instead of the bytecode

There are a few more necessary details, of course, but if we take this approach Parrot isn't too far away from a working, proof-of-concept JIT.

I'm sure this idea won't jive well with chromatic's "welcome to the new millenium" general distaste for C. I'm not 100% sure about it all myself. However, it is interesting and worthy of some consideration. It certainly does seem like a path of least resistance

libJIT NCI Frame Builder Branch

I alluded to it earlier, but today is the big announcement: Newcomer Peter Lobsinger has developed a patchset to replace Parrot's ad hoc NCI frame builder with a libJIT-based solution instead, and sent it to me as part of my JIT Challenge. Well, today he set up a branch of Parrot on github with the patch for public review. I recommend that all Parrot developers check it out to see what kinds of things are possible in a libJIT-integrated Parrot.

First Project Challenge Reminder

Ten days ago I posted a challenge for my readers. Here's a quick recap of the two challenge options:

1. Create a proof-of-concept NCI frame builder using a "real" JIT engine. You can pick anything you want (libJIT, LLVM, GNU Lighting, dynASM, nanoJIT, etc). It must be able to take a function pointer, a string representing the call signature, and proper arguments and no other unnecessary state information or metadata. The frame builder should return the compiled thunk from the JIT engine that can be used to call the target function.
2. Create a proof-of-concept NCI function caller using pure assembly or C with inline assembly. Your assembly routine should take a signature string, a function pointer, and a list of arguments, and a pointer to a memory location to hold a return value (if any).

This morning, I've received my first submission to challenge #1: an NCI frame builder using libJIT. It's quite impressive, and I'll post more information about the solution and the submitter later, with permission.

I'm going to try to set up an online store, like spreadshirt.com or cafepress.com or something to sell Parrot T-Shirts (all profits directed to the Parrot Foundation, of course). Once I get that set up, I'm going to sweeten the pot: All good unique submissions will receive a free Parrot-branded T-Shirt. You'll have to be willing to give me your shirt size and mailing address, of course. I'll post updates as I get things set up.

Submissions are unique if they solve different problems in different ways. So #1 with libJIT is already done (assuming it passes all my tests). Interested entrants could try #1 with LLVM or GNU Lightning, or any other JIT engine besides libJIT. Entrants could also be attempting #2 on various platforms (x86, x86_64, PPC, SPARC, SPARC64, etc). If I receive two or more submissions of the same type, the better one wins. Preference will probably be given to a patch that applies against Parrot trunk to any other type of solution, but integration with Parrot was never a requirement (just a nice bonus).

I'll make the October release as the deadline. So if you are interested, you have until 20 October to get one in.

JIT: First Project Challenge

Darbelo merged in a branch that finally gets rid of the old JIT and PIC systems. However one vestige of the JIT system still remains: the NCI frame builder. The NCI frame builder is used to create a call frame for interacting with an arbitrary library function. As I mentioned in my earlier post on Stack Frames, to call a function that follows the standard conventions, we push the arguments onto the system stack, use the call opcode to jump to the subroutine, and then when control flow returns we extract the return value from the appropriate register.

The problem is that the C programming language doesn't offer any facilities for manually constructing a call frame. In pure C, you cannot push an arbitrary value onto the stack, perform a non-local jump to a subroutine label, specify which register a value is stored in, etc. You can accomplish some of this with inlined assembly code, but if you're playing with the stack you run the risk of corrupting your program and crashing your computer. Keep in mind that local variables to a function are typically accessed as an offset from the esp register (on x86 anyway), so pushing things onto the stack will change the value of that register, which in turn will make constant offsets from that location point to different values.

When we are talking about calling arbitrary library functions from Parrot, there are three approaches:

1. Generate a list of function calling "thunks" from a predefined list of function signatures. You end up with hundreds of such thunks but still can't interact with some functions without adding a signature and recompiling Parrot. Also, all those hundreds of functions need to be loaded into memory when Parrot starts, creating a larger memory footprint and slower startup times.
   
2. Create a function in pure assembly that takes a signature string and manually constructs a call frame. In assembly we can interact with the system stack and processor registers directly. There are two problems with this: Portability, because we would need to write a new assembly routine for each combination of platform and assembler. Also, we couldn't cache the results of the generated call frame, every call to the library function would have to manually build the frame again.
   
3. Use a JIT solution. The current frame builder uses Parrot's old JIT framework to build the frame code in a block of memory, but only works on x86. A "real" solution here would use a JIT package like LLVM or libJIT to generate these frames. This has the benefit that we can cache the generated thunks. We generate them lazily when we need them and cache them for when we need them again.

Option #3 is probably what we are going to end up with, although being able to sanely fall back to Option#2 when a JIT library isn't available might be a good idea, especially for those rare platforms that aren't supported by our JIT engine.

This in mind, I have two challenges for readers who have some spare time:

1. Create a proof-of-concept NCI frame builder using a "real" JIT engine. You can pick anything you want (libJIT, LLVM, GNU Lighting, dynASM, nanoJIT, etc). It must be able to take a function pointer, a string representing the call signature, and proper arguments and no other unnecessary state information or metadata. The frame builder should return the compiled thunk from the JIT engine that can be used to call the target function.
2. Create a proof-of-concept NCI function caller using pure assembly or C with inline assembly. Your assembly routine should take a signature string, a function pointer, and a list of arguments, and a pointer to a memory location to hold a return value (if any).

Winning solutions don't need to be integrated into Parrot or use Parrot-style signature strings. Solutions don't need to be large or involved either, just a simple demonstration of the mechanisms needed to call arbitrary functions on your target platform. Bonus points for providing a solution that is related to what Parrot needs, and definite bonus points for targetting an uncommon platform (x86+GCC for instance is very common).

There is no real prize for "winning", but I'll post good submissions here to my blog, publically talk about how awesome you are, and maybe try to get your solution added to Parrot in some way and in some form.

First Steps on JIT Overhaul

Allison's email was the start of something big, and I have been absolutely excited by the prospect of a proper JIT system since she sent it. It's going to be a lot of work and will have a dramatic and overarching impact on our entire codebase, but it will be well worth it. There are a few things I especially like about this plan: There are a lot of options so we can test what does and does not work as we go. We can break it up into stages so huge changes aren't happening in disruptive chunks. We can get started immediately. We can parallelize several tasks so many people can be working towards the ultimate goal in many ways.

Mostly what I am excited about is that the rest of the developer team has been so excited about it as well. bacek has started moving through the ticket queue closing tickets relating to our current JIT system that won't ever be fixed now. moritz has been talking to developers on #llvm. People have started adding info to the wiki and adding their names to the list of tasks, and giving lots of good feedback as they go!

In the short term, possibly immediately following the 1.6.0 release, the parrot command line interface is going to be tweaked a little bit to hide the current JIT system. The command line argument --runcore=jit is going to be redirected so that it invokes the fastcore instead of the JIT core. What this does is removes the unworking underlying system but keeps the user interface the same. In the end, --runcore=JIT will not only continue working for users that already have it but will actually start working on platforms that have never had it. We're lying because it's not really executing a JIT engine underneith, but the deprecation policy doesn't say anywhere that we can't lie a little bit.

With the commandline papered over, we can get started on the work of removing the guts of the JIT system. This is going to be both interesting and fun work, because we're going to be deleting lots of evil code, but we're also going to need to preserve some functions for the NCI thunk generation. I think [hope] that once we start cleaning things out that we will be able to radically simplify and improve the NCI thunk generator.

LLVM seems like a really cool JIT solution for us to use, and it actually offers a lot more functionality then we will need (or even want). One big benefit is that LLVM operates on a low-level platform-independent intermediate representation (IR), which should be easy to translate to from Parrot ops. Some of our ops, especially the arithmetic ones, will have a very direct translation indeed. We're probably going to want to abstract away the details and create macros or even an improved syntax parser to take away the rough edges so we aren't programming in assembly, but that's something we can worry about later.

We're going to need the configuration system to detect LLVM. Nothing more to say about this one, we've got a great configuration system and this should be no issue.

These other steps out of the way, we are going to need to modify parrot to build the subroutines from LLVM IR fragments, then use LLVM to compile those subs into machine code at runtime and execute them. This step is the biggest one where everything comes together, but luckily we don't need to worry about all the details just yet.

The JIT Plan

A big thing has happened today with JIT: Allison has taken a look at all the information and laid out a plan for replacing Parrot's ailing JIT system. Since she said it better then I ever have, I'll just post her email here for your viewing enjoyment:

The current JIT will be disabled, with Parrot set to run the default 'fast' core when the 'jit' core is selected. This change can occur immediately following the 1.6 release. Between 1.6 and 1.7, code supporting the current JIT can be removed. A deprecation notice will go in before 2.0, eliminating the 'jit' runcore option. (There will be other ways of enabling and disabling JIT functionality later, but it won't be a runcore. For one thing, enabling the JIT is likely to require special compilation, see later comments.)

The basic requirement for the replacement JIT is the ability to generate machine code on the fly at runtime for a code object (Sub, Method, NCI, etc), so that any subsequent executions of that code object run the machine code directly. It must support all of Parrot's target platforms.

LLVM provides a set of tools that look promising for allowing us to quickly develop a JIT, taking advantage of the platforms they already support. (Note that LLVM currently has limited support for Windows, so it's not quite there on *all* our target platforms.) The plan is to develop a rapid prototype of an LLVM-based JIT, to see if it might work as the primary Parrot JIT, or perhaps as one of several JIT strategies.

The prototype will implement a subset of the core Parrot ops in a lightweight language ("Lorito", an extension of what we've already been talking about for that language). For the sake of the prototype, the Lorito compiler will output LLVM's Low-level Intermediate Representation (LIR), but the language will be developed so that it's general enough that it could be compiled to various different output formats (including C).

The old JIT compiled each op down to a separate chunk of machine code. The new JIT would potentially be able to JIT at the level of a single opcode (since the definitions are there), but the greater speed gains will come from JITing entire subs (where the opcode definitions are building blocks for larger units to compile, rather than compiled individually), so that's where the prototype will focus.

The JIT is not a runcore (it's a dynamic compilation strategy), but it also doesn't necessarily have to be compatible with every runcore variant we've developed.

Using LLVM for the JIT (or any external JIT library) will add an optional dependency. A Parrot built without LLVM will simply disable the JIT features.

I'll post more indepth information about all this in the days ahead. Also, make sure to keep up with the planning page on the wiki, where things are starting to come together.

JIT Redesign

The time has come. Parrot's JIT system is now in my crosshairs and phasers are set to kill.

bacek has spent a lot of his time in the past two weeks working on the Context PMC stuff. The last thing he was blocking on was a failure in the JIT system that only appeared when "make testj" was run. I, of course, couldn't even observe this failure because Parrot doesn't have JIT support on x86_64. The root problem for him was that the JIT system has a lot of hardcoded knowledge about the shape of some of Parrot's core data structures, and any changes to those structures breaks what JIT thinks it knows. In response to this problem, and some frustrations I have been building up over the past few months, I sent a mail to the list suggesting we deprecate the current JIT system and schedule it for removal in 2.0. Response there was mostly positive, but the ball really got moving when I mentioned the issue in this week's #parrotsketch meeting.

Why do I want to deprecate JIT? Isn't JIT the new hotness for virtual machines and interpreters? Isn't it the savior of performance for dynamic languages? The short answer is that I want to deprecate our current JIT implementation and replace it with something even better.

What JIT does is this: It takes information about the instructions to execute from the parser. This is going to be the compiler's Low-level Intermediate Representation (LIR). Parrot's LIR is the compiled bytecode that we are supposed to execute. JIT takes this information and converts it to machine code on the fly, so that it can be executed directly by the processor without need to dispatch to op routines. In theory what this can do is significantly reduce the overhead of opcode dispatch, by making control flow more "natural" to the machine, which in turn helps with branch prediction and caching. If you combine this with the ability of some JIT engines to optimize the output machine code agressively, you can end up with some major performance savings with a good JIT. I'll discuss the workings of JIT in more detail later this weekend.

In short, Parrot wants JIT. Parrot needs JIT. We simply aren't going to be a viable alternative to other VMs without it in the long term. Especially not when you start looking at some of the amazing performance improvements VMs have been making recently directly because of their JITs.

Parrot's current JIT just doesn't fit the bill though. It suffers from a number of terrible problems, which I enumerated to the list also:

1. It doesn't really provide much performance improvement for most programs. It also doesn't have much opportunity to perform any optimizations at the machine-code level.
   
2. It is too closely tied to Parrot's core, breaking all sorts of encapsulation barriers. As I said earlier, the JIT system needs to mirror certain algorithms and data structures used in Parrot core, which means a change made in the one needs to be faithfully preserved in the other. When we can't do that because none of our current developers know the system well enough we end up with a huge decrease in development momentum. Of course an argument could be made here that more people need to learn the JIT system.
   
3. Parrot's JIT system is very platform specific. There simply is no implementation on most systems (only x86 and PPC have it), and there is no easy way to share code between platforms to give new platforms a head start. If I want to write a JIT for a different system (such as amd64 for example), I basically need to start completely from scratch.
   
4. It is an absolute mess, and a maintainability nightmare. Nobody really knows what all it does or how it all works. It's also not documented well enough to bring any new developers up to speed on it. Top this all off with the overly complicated way that it is written. We simply can't make any improvements on the code, not without a herculean effort that honestly isn't worth the time.
5. It is nowhere near some of the other existing JIT engines in terms of usability, quality of generated code or capabilities. libJIT, nanoJIT and LLVM have entire dedicated teams working on them, we aren't ever going to match what they have without a similar expenditure of time and effort.
   

So I made the request that we deprecate the system. But not just that, I suggested that we start serious planning for a replacement. And I mean serious. I've been beating the pavement for the last two days, tracking down developers and asking questions. Some of the fruits of my labor have already been added to the wiki. Here are some ideas that I have about how our future JIT system could work (I'll explain this all in more detail later). Notice that this is not an order of tasks, just a logical outline of the system I am envisioning:

1. We rewrite Parrot's PASM ops in terms of a new LIR. This could be Lorito (Previously L1) if we want it to be backend-neutral, or it could be something that's specific to the particular JIT engine we use (like LLVM ops, for example).
   
2. We need to be able to convert the LIR to C for direct execution, and to a JIT definition for indirect execution. There are a number of ways we could do this, depending on the skills and availability of our development team.
3. The configure system will determine which JIT backends are available (if any), and generate the necessary code to support them during the build.
4. We only need a minimal API that the Core of Parrot will interact with: JIT the incoming PBC, call into JIT'd code, output an executable and maybe a select few other operations. Much of the code can be generated at build time.
   

This kind of system gives us pluggability in the sense that we can support multiple JIT engines, even though we can only plug them during the build. It also means we don't have to define a huge comprehensive API to satisfy all JIT engines, we only need a minimal API and can generate the rest of the code specifically for individual JITs.

Obviously this is all very preliminary, and we will refine the design as we move forward and gather more information about all our options. I'm sure I'll be posting updates here as new things start happening.

L1: The Language of Parrot Internals

A while back I mentioned using a special-purpose small language to be used for implementing some of the Parrot internals, such as PMC VTABLEs, and OPS. Well, the idea is slowly taking shape and it's going by the name L1. I don't know the exact genesis of the name, so I can't point you to a link containing a "let's call this thing L1!" quote, but that's the name of it, and here's some discussion. By way of disclaimer, this all isn't anywhere on my personal pre-2.0 roadmap, but I do intend to offer my moral support where possible, and look very closely at this issue if it hasn't been resolved before 2.0.

cotto and bacek have been doing a lot of great work on a PCT-based PMC parser, and ultimately we hope that such a bootstrapping tool would help enable ubiquitous use of L1. I'll talk more about that later.

To understand why this is needed, and to put into context some of the things I am going to talk about in this post, let's look at a small example that comes directly from the libJIT documentation. Let's take a small function to multiply two numbers together and return a result:

int mul_add(int x, int y, int z)
{
return x * y + z;
}

If we want to compile this operation at runtime with libJIT, we would have to do this:

jit_context_t context;
context = jit_context_create();
jit_context_build_start(context);
jit_function_t function;
function = jit_function_create(context, signature);
jit_type_t params[3];
jit_type_t signature;
params[0] = jit_type_int;
params[1] = jit_type_int;
params[2] = jit_type_int;
signature = jit_type_create_signature
 (jit_abi_cdecl, jit_type_int, params, 3, 1);
jit_value_t x, y, z;
x = jit_value_get_param(function, 0);
y = jit_value_get_param(function, 1);
z = jit_value_get_param(function, 2);
jit_value_t temp1, temp2;
temp1 = jit_insn_mul(function, x, y);
temp2 = jit_insn_add(function, temp1, z);
jit_insn_return(function, temp2);
jit_function_compile(function);
jit_context_build_end(context);

What this listing shows is not the function itself, but how to tell the computer to write the function itself at runtime. The computer will build and compile the function into executable code at runtime and then will be able to execute it. The benefit to JIT is that the compiled code pieces are reusable, so all the overhead of describing the function only needs to occur once and the resulting machine code can be executed over and over again. The mechanics of JIT aren't really important for this discussion, but what is important is to see that the two versions of the code are very different from each other, and if we're generating C code at runtime we potentially need to generate several different versions of each code snippet.

Currently, we do JIT by writing the opcode definitions in a C-like script in one place, and writing JIT versions of them in another place. And when one doesnt match the other, there's a problem. One thing that we absolutely need in Parrot, for our own sanity if nothing else, is the ability to specify operations using a common, simplified, non-C small language that can be converted into multiple forms and executed in multiple ways, as necessary. This, I think, is a good use for L1: An abstraction layer that enables us to write an almost behavioral description of a piece of code and have that used at build time to produce all the various pieces of C code and other code that we need.

chromatic has a slightly different conception of what L1 could be, although I don't think it's entirely incompatible from what I was talking about above. Instead of simply being a common front-end language that gets converted into other stuff for compilation and execution, chromatic suggests that it could be used in the virtual machine in the same way that microcodes are used in a hardware processor. A small, fast Parrot core (called "nanoparrot") would execute the L1 microcodes directly. There are some different ideas here about what the relationship will be between PIR/PASM and L1, but I will talk about those differences later. chromatic also hopes that a pure L1 execution environment would be self-contained and save us from the frequent switching between C and PIR calling conventions. Let's explore that idea a little bit more.

PIR code is executing and reaches a particular operation which internally calls PCCINVOKE on a PIR subroutine. This creates a new runloop to execute the new PIR function, which returns a value to PCCINVOKE, which in turn returns results back to PIR. All the while, marshaling data back and forth between two very different environments (C and PIR). Likewise, consider the case of PIR code executing and throwing an exception. Parrot searches for a handler (which itself may be PIR or C, which in turn calls a function in PIR or C again, ad infinitem), executes it, and possibly returns execution to where it was. We're jumping back and forth between C and PIR for control flow, creating runloops and shuffling data all too frequently. The situation, in short, is complex and unsustainable in the long run. Plus, there are serious performance problems associated with all this jumping between PIR and C.

Now consider the alternative of a pure L1 execution environment, where PASM opcodes are little more than named sequences of L1 opcodes. L1 code is executing, and throws an exception. A return continuation is created and passed to an L1-based hander, which returns control through the return continuation. No C code involved. Almost too good to be true. Almost. The case of calling into L1 code from C is a little bit more tricky but not impossible. Instead of passing a return continuation we pass a C-based return continuation which will probably consist of a cached image of the interpreter structure and a jump point or something. In any case we still save on performance because the arguments get passed in PIR registers and that's where they stay.

What I personally would like from L1 is a unified solution, something that meets these requirements:

1. Has to be easy, trivially easy, to JIT.
2. Has to be a small set of operations capable of implementing all other ops
3. Should be suitable, at least in the long term, for implementing VTABLEs and METHODs in PMCs.

chromatic suggests that L1 should be a subset of PIR, but I'm not sure I agree with that. I am thinking right now (and I may change my mind as I think about this more) that it should be a separate assembly-level language entirely. There are a number of reasons for that, and I will discuss them later. I have plenty more to say about L1, and I'll do that in later posts.