CodeGen

Experimental wrapper over LLVM for generating and compiling code at run-time.

About

CodeGen is a library that builds on top of LLVM. It facilitates just-in-time code generation and compilation, including debugging information and human-readable source code. C++ type system is employed to guard against, at least some, errors in the generated intermediate representation. The intention is to allow the application to improve performance by taking advantage of information that becomes available only once it is running. A sample use case would be prepared statements in of database engines.

The general idea is not unlike that described in P1609R0: C++ Should Support Just-in-Time Compilation.

Building

The build requirements are as follows:

CMake 3.12
GCC 8+ or Clang 8+
LLVM 8
fmt
Google Test (optional)

fedora:30 docker container may be a good place to start.

The build instructions are quite usual for a CMake-based project:

cd <build-directory>
cmake -DCMAKE_BUILD_TYPE=<Debug|Release> -G Ninja <source-directory>
ninja
ninja test

Design

The main object representing the JIT compiler is codegen::compiler. All function pointers to the compiled code remain valid during its lifetime. codegen::module_builder allows creating an LLVM builder, while codegen::module represents an already compiled module. The general template that for CodeGen use looks as follows:

  namespace cg = codegen;
  auto compiler = cg::compiler{};
  auto builder = cg::module_builder(compiler, "module_name");

  auto function_reference = builder.create_function<int(int)>("function_name",
    [](cg::value<int> v) {
      /* more logic here */
      cg::return_(v + cg::constant<int>(1));
    });

  auto module = std::move(builder).build();
  using function_pointer_type = int(*)(int);
  function_pointer_type function_pointer = module.get_address(function_reference);

The code above compiles a function that returns an integer that was passed to it as an argument incremented by one. Each module may contain multiple functions. codegen::module_builder::create_function returns a function reference that can be used to obtain a pointer to the function after the module is compiled (as in this example) or to call it from another function generated with CodeGen.

codegen::value<T> is a typed equivalent of llvm::Value and represents a SSA value. As of now, only fundamental types are supported. CodeGen provides operators for those arithmetic and relational operations that make sense for a given type. Expression templates are used in a limited fashion to allow producing more concise human-readable source code. Unlike C++ there are no automatic promotions or implicit casts of any kind. Instead, bit_cast<T> or cast<T> need to be explicitly used where needed.

SSA starts getting a bit more cumbersome to use once the control flow diverges, and a Φ function is required. This can be avoided by using local variables codegen::variable<T>. The resulting IR is not going to be perfect, but the LLVM optimisation passes tend to do an excellent job converting those memory accesses.

Statements

return_(), return_(Value) – returns from function. Note, that the type of the returned value is not verified and CodeGen will not prevent generating a function of type int() that returns void.
load(Pointer) – takes a pointer of type T* and loads the value from memory, codegen::value<T >.
store(Value, Pointer) – stores Value of type T at the location pointed to by Pointer. The type of the pointer needs to be T*.
if_(Value, TrueBlock, FalseBlock), if_(Value, TrueBlock) – an if conditional statement. The type of the provided value needs to be bool. TrueBlock and FalseBlock are expected to be lambdas. For example:

auto silly_function = builder.create_function<bool(bool)>("silly_function",
    [](cg::value<bool> is_true) {
      cg::if_(is_true, [] { cg::return_(cg::true_()); }, [] { cg::return_(cg::false_()); });
    });

while_(Condition, LoopBody) – a while loop. Condition is a lambda returning a value of type bool. LoopBody is a lambda that generates the body of the loop. For example:

auto silly_function2 = builder.create_function<unsigned(unsigned)>("silly_function2",
    [](cg::value<unsigned> target) {
      auto var = cg::variable<unsigned>("var", cg::constant<unsigned>(0));
      cg::while_([&] { return var.get() < target; },
        [&] {
          var.set(var.get() + cg::constant<unsigned>(1));
        });
      cg::return_(var.get());
    });

call(Function, Arguments...) – a function call. Function is a function reference. Arguments... is a list of arguments matching the function type.

Examples

Tuple comparator

In this example, let's consider tuples which element's types are known only at run-time. If the goal is to write a less-comparator for such tuples, the naive approach would be to have a virtual function call for each element. That is far from ideal if the actual comparison is very cheap, e.g. the elements are integers. With CodeGen, we can do better. First, let's write a comparator for an element of a fundamental type:

template<typename T>
size_t less_cmp(cg::value<std::byte const*> a_ptr, cg::value<std::byte const*> b_ptr, size_t off) {
  auto a_val = cg::load(cg::bit_cast<T*>(a_ptr + cg::constant<uint64_t>(off)));
  auto b_val = cg::load(cg::bit_cast<T*>(b_ptr + cg::constant<uint64_t>(off)));
  cg::if_(a_val < b_val, [&] { cg::return_(cg::true_()); });
  cg::if_(a_val > b_val, [&] { cg::return_(cg::false_()); });
  return sizeof(T) + off;
}

This function template generates comparison code for any fundamental type. The arguments are pointers to buffers containing both tuples and an offset at which the element is located. The return value is the offset of the next element.

Now, let's say we want to generate a less-comparator for tuple<i32, float, u16>.

  auto less = builder.create_function<bool(std::byte const*, std::byte const*)>(
      "less", [&](cg::value<std::byte const*> a_ptr, cg::value<std::byte const*> b_ptr) {
        size_t offset = 0;
        offset = less_cmp<int32_t>(a_ptr, b_ptr, offset);
        offset = less_cmp<float>(a_ptr, b_ptr, offset);
        offset = less_cmp<uint16_t>(a_ptr, b_ptr, offset);
        (void)offset;
        cg::return_(cg::false_());
      });

As we can see, building the actual comparator is quite straightforward. The human-readable source code that CodeGen generates looks like this:

1   bool less(byte* arg0, byte* arg1) {
2       val0 = *bit_cast<i32*>((arg0 + 0))
3       val1 = *bit_cast<i32*>((arg1 + 0))
4       if ((val0 < val1)) {
5           return true;
6       }
7       if ((val0 > val1)) {
8           return false;
9       }
10      val2 = *bit_cast<f32*>((arg0 + 4))
11      val3 = *bit_cast<f32*>((arg1 + 4))
12      if ((val2 < val3)) {
13          return true;
14      }
15      if ((val2 > val3)) {
16          return false;
17      }
18      val4 = *bit_cast<u16*>((arg0 + 8))
19      val5 = *bit_cast<u16*>((arg1 + 8))
20      if ((val4 < val5)) {
21          return true;
22      }
23      if ((val4 > val5)) {
24          return false;
25      }
26      return false;
27  }

The assembly that LLVM emits:

   0x00007fffefd57000 <+0>:   mov    (%rdi),%ecx
   0x00007fffefd57002 <+2>:   mov    (%rsi),%edx
   0x00007fffefd57004 <+4>:   mov    $0x1,%al
   0x00007fffefd57006 <+6>:   cmp    %edx,%ecx
   0x00007fffefd57008 <+8>:   jl     0x7fffefd57026 <less+38>
   0x00007fffefd5700a <+10>:  cmp    %edx,%ecx
   0x00007fffefd5700c <+12>:  jg     0x7fffefd57024 <less+36>
   0x00007fffefd5700e <+14>:  vmovss 0x4(%rdi),%xmm0
   0x00007fffefd57013 <+19>:  vmovss 0x4(%rsi),%xmm1
   0x00007fffefd57018 <+24>:  vucomiss %xmm0,%xmm1
   0x00007fffefd5701c <+28>:  ja     0x7fffefd57026 <less+38>
   0x00007fffefd5701e <+30>:  vucomiss %xmm1,%xmm0
   0x00007fffefd57022 <+34>:  jbe    0x7fffefd57027 <less+39>
   0x00007fffefd57024 <+36>:  xor    %eax,%eax
   0x00007fffefd57026 <+38>:  retq
   0x00007fffefd57027 <+39>:  movzwl 0x8(%rdi),%eax
   0x00007fffefd5702b <+43>:  cmp    0x8(%rsi),%ax
   0x00007fffefd5702f <+47>:  setb   %al
   0x00007fffefd57032 <+50>:  retq

Since CodeGen takes care of emitting all necessary debugging information, and informing GDB about the JIT-ed functions, the debugging experience shouldn't be too bad:

(gdb) b 3
Breakpoint 2 at 0x7fffefd57002: file /tmp/examples-11076310111440055155/tuple_i32f32u16_less.txt, line 3.
(gdb) c
Continuing.

Breakpoint 2, less (arg0=0x60200001c7b0 "", arg1=0x60200001c790 "\001") at /tmp/examples-11076310111440055155/tuple_i32f32u16_less.txt:3
3	    val1 = *bit_cast<i32*>((arg1 + 0))
(gdb) p val0
$1 = 0
(gdb) n
4	    if ((val0 < val1)) {
(gdb) p val1
$3 = 1
(gdb) n
less (arg0=0x60200001c7b0 "", arg1=0x60200001c790 "\001") at /tmp/examples-11076310111440055155/tuple_i32f32u16_less.txt:5
5	        return true;

A more complicated example would be if one of the tuple elements was an ASCII string. The following code generates a comparator for tuple<i32, string> assuming that a string is serialised in the form of <length:u32><bytes...>:

  auto less = builder.create_function<bool(std::byte const*, std::byte const*)>(
      "less", [&](cg::value<std::byte const*> a_ptr, cg::value<std::byte const*> b_ptr) {
        size_t offset = 0;
        offset = less_cmp<int32_t>(a_ptr, b_ptr, offset);

        auto a_len = cg::load(cg::bit_cast<uint32_t*>(a_ptr + cg::constant<uint64_t>(offset)));
        auto b_len = cg::load(cg::bit_cast<uint32_t*>(b_ptr +

Codegen

Install / Use

README