A just-in-time (JIT) compiler is a compiler that in contrast to the usual compilers is not run ahead-of-time, i.e. before running the actual program, but during the program itself.

JIT compilers run during the execution of the program. Since compilation is a heavy process, the benefits brought by the compilation must clearly outweigh the time spent in compiling code. The typical scenarios where JITs are used are those where a program features a interpreter-like process, like an interpreter of a interpreted programming language. Interpretation is in general much slower than execution of compiled code. In order to speedup the interpretation, these systems usually track those parts of the program that are hot, meaning that they are run a lot of times. When a part of the code (usually at a granularity of a function) becomes hot, the implementation of the interpreted language schedules a compilation of that code. When the code has been compiled, the implementation of the language switches from interpretation to the execution of compiled code. This technique, that may bring noticeable speed improvements, has been used in several programming languages including Java, JavaScript and Python.

GCC JIT

Note: I will use GCC JIT but the official name of this component of GCC is libgccjit.

Recently GCC has earned the ability to act as a just-in-time compiler. The JIT is integrated in the GCC compilation workflow as a front end language (like C, C++ or Fortran). For this post I will be using GCC 5.2.

Installation

Given that the system compiler is a sensitive piece of software and that it is unlikely that GCC JIT is enabled in your Linux distribution, we will have to build a GCC with that support enabled.

First, create a directory where we will put everything, enter it and download GCC 5.2 

# define a variable BASEDIR that we will use all the time
$ export BASEDIR=$HOME/gcc-jit
# Create the directory, if it does not exist
$ mkdir -p $BASEDIR
# Enter the new directory
$ cd $BASEDIR
# Download gcc using 'wget' ('curl' can be used too)
$ wget http://ftp.gnu.org/gnu/gcc/gcc-5.2.0/gcc-5.2.0.tar.bz2
# Unpack the file
$ tar xfj gcc-5.2.0.tar.bz2

The next step involves building GCC. First we need to get some software required by GCC itself. 

# Enter in the source code directory of GCC
$ cd gcc-5.2.0
# And now download the prerequisites
$ ./contrib/download_prerequisites

Now, create a build directory sibling to gcc-5.2.0 and make sure you enter it. 

# We are in gcc-5.2.0, go up one level
$ cd ..
# Now create the build directory, gcc-build is a sensible name
$ mkdir gcc-build
# Enter the build directory
$ cd gcc-build

Now configure the compiler and build it. In this step we will specify where the compiler will be installed. Make sure that you are in gcc-build! This step takes several minutes (about 15 minutes or so, depending on your machine) but you only have to do it once. 

# Define an installation path, it must be an absolute path!
# '$BASEDIR/gcc-install' seems an appropiate place
$ export INSTALLDIR=$BASEDIR/gcc-install
# Configure GCC --enable-host-shared is required by jit
$ ../gcc-5.2.0/configure --prefix=$INSTALLDIR --enable-languages=c,c++,jit --enable-host-shared
# Build 'getconf _NPROCESSORS_ONLN' will return the number of threads
# we can use, in order to build GCC in parallel
$ make -j$(getconf _NPROCESSORS_ONLN)

Now install it 

$ make install

Now check the installation 

# Create a convenience variable for the path of GCC
$ export GCCDIR=$INSTALLDIR/bin
$ $GCCDIR/g++ --version
g++ (GCC) 5.2.0
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

That's it. You can find much more information about installing here.

Build programs that use the GCC JIT

The GCC JIT is designed as a library that offers a C interface. This interface is in libgccjit.h and will be located in $INSTALLDIR/include. The library itself is in $INSTALLDIR/lib. Following is a Makefile that can be used when compiling and linking a program that uses GCC JIT. 

JITCFLAGS=-I$(INSTALLDIR)/include
JITLDFLAGS=-L$(INSTALLDIR)/lib -Wl,-rpath,$(INSTALLDIR)/lib -lgccjit

all: test

test: test.o
	$(CC) -o $@ $+ $(JITLDFLAGS)

test.o : test.c
	$(CC) -c $(JITCFLAGS) -o $@ $<

The flag -Wl,-rpath,... is necessary as we installed GCC in a non-standard directory, and we will need to find libgccjit.so when executing the program.

Also make sure that the PATH environment variable contains $GCCDIR (defined above), otherwise during the execution of our program, libgccjit.so will not be able to invoke the compiler.

Our first JIT function

As a starter, we will JIT a very simple function that justs computes the addition of two numbers. Before anything we have to be aware that like in a real compiler, lots of things can go wrong before we get any actual code, so we should take care of all possible errors. We will use this very simple routine. 

void die(const char* c)
{
  fprintf(stderr, "ERROR: %s\n", c);
  exit(EXIT_FAILURE);
}

</p> To work with GCC JIT we need a context. </p>

#include <libgccjit.h>

#include <stdlib.h>
#include <stdio.h>

int main (int argc, char **argv)
{
  gcc_jit_context *ctx = gcc_jit_context_acquire(); // get the context
  if (ctx == NULL)
    die("acquired context is NULL");

Our goal is creating a function that adds two numbers, like the following. 

int add(int a, int b)
{
  return a + b;
}

GCC JIT works with entities called gcc_jit_objects. These objects are of different kinds but for this first example we will need an object of kind type that represents the C int type. We will also need two objects of kind parameter (with int type) that will represent the parameters a and b. We will create also a function, add, with two parameters (a and b) with a block containing a single expression that computes a + b.

Let's get started. First get an object representing int. Fundamental types (closely following the fundamental ones of C) are obtained using gcc_jit_context_get_type. 

gcc_jit_type *int_type = gcc_jit_context_get_type(ctx, GCC_JIT_TYPE_INT);

You will see that we will have to pass all the time the context we got at the beginning. Now we can create two parameters: a and b. Beside the context, to create a parameter we will need to pass a location, a type and a name. Since we are creating a function out of thin air, we do not have any location so we will leave it NULL. Note that we use the int type we got above. 

gcc_jit_param *param_a = gcc_jit_context_new_param(ctx, /* loc */ NULL, int_type, "a");
gcc_jit_param *param_b = gcc_jit_context_new_param(ctx, /* loc */ NULL, int_type, "b");

Now we can compute a + b. Calculations are called rvalues (borrowing the concept from the C language): it means something that has to be computed. An rvalue can be created from a parameter using gcc_jit_param_as_rvalue. This is a very simple calculation that means give me the value that the parameter has now. 

gcc_jit_rvalue *rval_a = gcc_jit_param_as_rvalue(param_a);
gcc_jit_rvalue *rval_b = gcc_jit_param_as_rvalue(param_b);

Once we have the two parameters we can add them. This will yield another rvalue of type int. 

gcc_jit_rvalue *a_plus_b = gcc_jit_context_new_binary_op(ctx, /* loc */ NULL,
    GCC_JIT_BINARY_OP_PLUS, int_type, rval_a, rval_b);

Now we need to create the function add. It has two parameters a and b that we created earlier. It will return int as well. 

gcc_jit_param* params[2] = { param_a, param_b };
gcc_jit_function *add_function = gcc_jit_context_new_function(ctx, /* loc */ NULL,
    GCC_JIT_FUNCTION_EXPORTED, int_type, "add",
    2, params, /* is_variadic */ 0);

The parameter GCC_JIT_FUNCTION_EXPORTED means that it will be available out of the JIT code, otherwise the function can only be called from the JIT code itself. We will get later this add function to call it from our C code.

Functions are constructed by blocks, which represent a sequence of calculations called statements that may have some visible effect. In our case, just adding two numbers has no effects unless the result of the addition is kept somewhere (i.e. in a variable), or used for something else (i.e. in the expression of the return statement or as the condition expression of an if-then-else statement). All statements inside a block are always executed in order: a block is never partially executed. If the code we want to generate has conditional parts each conditional part goes into a different block. When we create a block, we can give it a symbolic name that can be used for debugging. A block must be ended by transferring the control, either to another block (i.e. if-then-else, switch/case, loops, etc.) or leaving the function (i.e. return statement). 

gcc_jit_block *block = gcc_jit_function_new_block(add_function, "one_block");

Now we end the block by just returning the addition we computed. 

gcc_jit_block_end_with_return(block, /* loc */ NULL, a_plus_b);

Ok, this may have looked like a bit slow but we are done with creating code. Next step is compiling it! Compiling a context will give us a result. If the result is non-null it will represent all the functions (and global variables if any) that we have created. From the result we will be able to get the exported functions and execute them. But let's compile first. 

gcc_jit_result *result = gcc_jit_context_compile(ctx);
if (result == NULL)
  die("compilation failed");

Now we can get the exported function add. We will get a generic pointer, so we will have to cast apropiately before calling it. 

void *function_addr = gcc_jit_result_get_code(result, "add");

typedef int (*ptr_add_t)(int, int);
ptr_add_t add = (ptr_add_t)function_addr;

int x = add(1, 2); // Call the jitted code
assert(x == 3);

Finally we have to release the result of the compilation and the JIT context. 

gcc_jit_result_release(result);
gcc_jit_context_release (ctx);

More interesting examples

Conditional code

Our first function required a bit of boilerplate to build it but now that we understand the basics, we can move on to something more sophisticated. Our next function will be like this one. 

void add_or_sub(bool op, int a, int b)
{
  if (op)
    return a + b;
  else
    return a - b;
}

The only difference here is using a new parameter of type bool and then ending conditionally the first block (after evaluating op) to either go to the true (then) or false (else) block. 

// Get bool and int types
gcc_jit_type *bool_type = gcc_jit_context_get_type(ctx, GCC_JIT_TYPE_BOOL);
gcc_jit_type *int_type = gcc_jit_context_get_type(ctx, GCC_JIT_TYPE_INT);

// Create parameters: bool op, int a, int b
gcc_jit_param *param_op = gcc_jit_context_new_param(ctx, /* loc */ NULL, bool_type, "op");
gcc_jit_param *param_a = gcc_jit_context_new_param(ctx, /* loc */ NULL, int_type, "a");
gcc_jit_param *param_b = gcc_jit_context_new_param(ctx, /* loc */ NULL, int_type, "b");

// Create add_or_sub function as 'int add_or_sub(bool op, int a, int b)'
gcc_jit_param* params[3] = { param_op, param_a, param_b };
gcc_jit_function *add_function = gcc_jit_context_new_function(ctx, /* loc */ NULL,
    GCC_JIT_FUNCTION_EXPORTED, int_type, "add_or_sub",
    3, params, /* is_variadic */ 0);

// Now create three blocks
gcc_jit_block *if_block = gcc_jit_function_new_block(add_function, "if_condition");
gcc_jit_block *true_block = gcc_jit_function_new_block(add_function, "true_block");
gcc_jit_block *false_block = gcc_jit_function_new_block(add_function, "false_block");

// End the first block with a
//    if (op)
//        goto true_block;
//    else
//        goto false_block"
gcc_jit_block_end_with_conditional(
        if_block,
        /* loc */ NULL,
        gcc_jit_param_as_rvalue(param_op),
        true_block,
        false_block);

gcc_jit_rvalue *rval_a = gcc_jit_param_as_rvalue(param_a);
gcc_jit_rvalue *rval_b = gcc_jit_param_as_rvalue(param_b);

// End the first block with
//    return a + b;
gcc_jit_block_end_with_return(
        true_block,
        /* loc */ NULL,
        gcc_jit_context_new_binary_op(ctx, /* loc */ NULL,
            GCC_JIT_BINARY_OP_PLUS, int_type,
            rval_a,
            rval_b));

// End the second block with
//    return a - b;
gcc_jit_block_end_with_return(
        false_block,
        /* loc */ NULL,
        gcc_jit_context_new_binary_op(ctx, /* loc */ NULL,
            GCC_JIT_BINARY_OP_MINUS, int_type,
            rval_a,
            rval_b));

// Dump the function to dot
gcc_jit_function_dump_to_dot(add_function, "add_or_sub.dot");

We tell GCC JIT to dump a graph-like representation of the function that we have created in Graphviz. It will look like this.

add_or_sub

Now we can compile the code and see if it works. 

// Compile the code
gcc_jit_result *result = gcc_jit_context_compile(ctx);
if (result == NULL)
    die("compilation failed");

void *function_addr = gcc_jit_result_get_code(result, "add_or_sub");

typedef int (*ptr_add_or_sub_t)(bool, int, int);
ptr_add_or_sub_t add_or_sub = (ptr_add_or_sub_t)function_addr;

int x = add_or_sub(true, 1, 2);
assert(x == 3);

x = add_or_sub(false, 1, 2);
assert(x == -1);

A loop

Now we want to implement something like this. 

int sum(int n)
{
  int s = 0;
  int i;
  for (i = 0; i < n; i++)
  {
    s += i;
  }
  return s;
}

We start as usual, defining the parameter n of type int and creating a function that returns int and receives the parameter n. 

gcc_jit_type *int_type = gcc_jit_context_get_type(ctx, GCC_JIT_TYPE_INT);

// 'int n' as a parameter
gcc_jit_param *param_n = gcc_jit_context_new_param(ctx, /* loc */ NULL, int_type, "n");
gcc_jit_rvalue *rval_n = gcc_jit_param_as_rvalue(param_n);

// int sum(int n)
gcc_jit_param* params[] = { param_n };
gcc_jit_function *sum_function = gcc_jit_context_new_function(ctx, /* loc */ NULL,
    GCC_JIT_FUNCTION_EXPORTED, int_type, "sum",
    sizeof(params)/sizeof(*params), params, /* is_variadic */ 0);

We will also need a couple of local variables i and s to keep respectively the counter of the loop and the partial sum up to the i - 1 value. We also get their rvalue object that we will use later. 

// Local variables
//   int s;
gcc_jit_lvalue* sum_var = gcc_jit_function_new_local(sum_function, /* loc */ NULL, int_type, "s");
gcc_jit_rvalue* rval_sum = gcc_jit_lvalue_as_rvalue(sum_var);
//   int i;
gcc_jit_lvalue* ind_var = gcc_jit_function_new_local(sum_function, /* loc */ NULL, int_type, "i");
gcc_jit_rvalue* rval_ind = gcc_jit_lvalue_as_rvalue(ind_var);

To implement this function we will need four blocks. 

//       init
//        |
//        V
// .-- loop_header <--.
// |      |           |
// |      V           |
// |   loop_body------'
// |
// `--> return

gcc_jit_block *init_block = gcc_jit_function_new_block(sum_function, "init");
gcc_jit_block *loop_header_block = gcc_jit_function_new_block(sum_function, "loop_header");
gcc_jit_block *loop_body_block = gcc_jit_function_new_block(sum_function, "loop_body");
gcc_jit_block *return_block = gcc_jit_function_new_block(sum_function, "return");

The init block will initialize i and s to zero and then jump to the loop_header block. 

// Block --- init
//    sum = 0
gcc_jit_block_add_assignment(init_block, /* loc */ NULL,
        sum_var,
        gcc_jit_context_new_rvalue_from_int(ctx, int_type, 0));
//    init = 0
gcc_jit_block_add_assignment(init_block, /* loc */ NULL,
        ind_var,
        gcc_jit_context_new_rvalue_from_int(ctx, int_type, 0));
//    goto loop_header
gcc_jit_block_end_with_jump(init_block, /* loc */ NULL, loop_header_block);

The block loop_header checks if i < n. If the check succeeds it will jump to loop_body otherwise it will jump to return. 

// Block --- loop_header
//    if (i < n)
//       goto loop_body;
//    else
//       goto return;
gcc_jit_block_end_with_conditional(
        loop_header_block, /* loc */ NULL,
         gcc_jit_context_new_comparison(
             ctx, /* loc */ NULL,
             GCC_JIT_COMPARISON_LT, 
             rval_ind,
             rval_n),
         loop_body_block,
         return_block);

The block loop_body computes both s = s + i and i = i + 1. These two operations can be compacted as their equivalents s += i and i += 1. After this it jumps back to loop_header. 

  // Block --- loop_body
  //   s += i;
  gcc_jit_block_add_assignment_op (
          loop_body_block, /* loc */ NULL,
          sum_var,
          GCC_JIT_BINARY_OP_PLUS,
          rval_ind);
  //   i += 1;
  gcc_jit_block_add_assignment_op (
          loop_body_block, /* loc */ NULL,
          ind_var,
          GCC_JIT_BINARY_OP_PLUS,
          gcc_jit_context_one(ctx, int_type)); 
  //   goto loop_header
  gcc_jit_block_end_with_jump(
          loop_body_block, /* loc */ NULL,
          loop_header_block);

Finally the block return just returns the value currently in s. 

  // Block --- return
  //   return s;
  gcc_jit_block_end_with_return(return_block, /* loc */ NULL,
          rval_sum);

The Graphviz representation of this function looks like this.

sum

As before, we can compile and test this function. 

// Compile the code
gcc_jit_result *result = gcc_jit_context_compile(ctx);
if (result == NULL)
  die("compilation failed");

// Test it!
void *function_addr = gcc_jit_result_get_code(result, "sum");

typedef int (*ptr_sum_t)(int);
ptr_sum_t sum = (ptr_sum_t)function_addr;

int x = sum(100);
fprintf(stderr, "SUM(0..99) = %d\n", x);
assert(x == 4950);

You may want to check libgccjit documentation for more details, examples and a tutorial. In the next part of this post, we will apply GCC JIT to a very simple regular expression matcher code.

That's all for today.