Compiling C++ code at runtime

青旅半醒 2022-08-24 04:22 24阅读 0赞

*  [Download code - 5.84 KB][]

## Introduction ##

The C programming-language draws a line between compile-time and run-time: you compile your program to convert it into machine-code, which can then be run. C++ crosses this line via template-metaprogramming techniques that use the compiler to “run” meta-programs. Dynamic programming languages (e.g., Python) cross the line in the other direction by allowing runtime generation of functions (“higher level functions”).

The following is a proof-of-concept showing that higher-level functions can be implemented in C++ using the [LLVM Compiler Infrastructure][], and how they can be useful for runtime code optimization.

## Background ##

### Static Code Optimization ###

A C++ compiler can do quite sophisticated code-optimizations. However, how much optimization can be done depends on what the compiler knows of the code.

For example, one trivial optimization is “[strength reduction][]”. Generally, when faced with a code such as:

![minus.gif][]  Collapse

int divide(int x, int z) {
       return x/z;
    }

the compiler doesn’t have a choice, and will use an expensive division instruction. However, if more is known on `x` and `z`, there are many additional optimizations that can be performed. For example, if we know `z` at compile time, we can embed the known value in a function (or specialize a template function):

![minus.gif][]  Collapse

int divide8(int x) {
       return x/8;
    }

Now, the compiler can optimize the divide away, replacing it with a cheap right shift:

![minus.gif][]  Collapse

int divide8_opt(int x) {
       return x >> 3;
    }

This and similar optimizations can increase the application performance significantly.

### Target Specific Optimization ###

Additional optimizations depend on the target machine: if you know in advance the application will run on a Core 2 machine, you can use [SSE 4.1][] instructions to implement additional optimizations. However, in most cases, applications are expected to run on a wide variety of machines, and a “least-common-denominator” approach is used, emitting Pentium-compatible executables, losing potential performance gains.

### Dynamic Code Optimization ###

If we could defer part of the compilation process to runtime, more optimization opportunities are available.

First, we could generate code optimized for the actual machine the application is running on – use extensions such as SSE4.1 only when running on a Core 2 machine.

Second, we could create code that depends on values not available at compile time. For example, a packet filter may scan network traffic for specific patterns which are only known at runtime. However, these patterns are relatively static, and change infrequently (see this [for an example][]).

### The LLVM Compiler Infrastructure ###

[LLVM][LLVM Compiler Infrastructure] is a high-quality, platform independent infrastructure for compilation. It supports compilation to an intermediate “bitcode”, and an efficient Just-In-Time (JIT) compilation and execution. For a good introduction to both LLVM and writing compilers, see the excellent [LLVM tutorials][]. LLVM provides tools for generating bitcode, which it can then optimize, compile, and execute.

## Using the Code ##

### DynCompiler ###

DynCompiler is a *proof-of-concept* (read: don’t expect it to work for more than toy problems, have a nice syntax, or do anything useful) of a DSEL for dynamic code compilation, which uses LLVM to do the real work. With DynCompiler, you can create a “higher-level function” – or a function for creating other functions.

For example, the following function can create a specific quadratic polynomial (ax2\+bx+c) for given coefficients **a**, **b**, and **c**:

![minus.gif][]  Collapse

typedef int (*FType)(int);
    FType build_quad(int a, int b, int c) {
         DEF_FUNC(quad) RETURNS_INT
         ARG_INT(x);
      BEGIN
        DEF_INT(tmp);
        tmp = a*x*x + b*x + c;
        RETURN(tmp);
      END
      return (FType)FPtr;
    }

Note that `build_quad()` returns a function – it is not the quadratic function itself (the same way that function templates are not “concrete” functions). To create an actual function:

![minus.gif][]  Collapse

FType f1 = build_quad(1, 2, 1); // f1(x) := x^2+2*x+1

Which can now be used as any other function:

![minus.gif][]  Collapse

for(int x = 0; x < 10; x++) {
        std::cout << "f1(" << x << ") = " << f1(x) << std::endl;
    }

### Syntax ###

DynCompiler has an ugly syntax – the result of the limitations of the preprocessor and laziness. A function generator has a name and a return type (only “`int`” and “`double`” are supported):

![minus.gif][]  Collapse

DEF_FUNC(name) RETURNS_INT

or:

![minus.gif][]  Collapse

DEF_FUNC(name) RETURNS_DOUBLE

for a function returning a `double`. Arguments for the resulting function are provided by:

![minus.gif][]  Collapse

ARG_INT(x); // integer

![minus.gif][]  Collapse

ARG_DOUBLE(x); // double

The actual function code starts with a `BEGIN`:

![minus.gif][]  Collapse

BEGIN

Local variables can be defined with `DEF_INT` and `DEF_DOUBLE`:

![minus.gif][]  Collapse

DEF_INT(tmp);

You can then use these variables (almost) normally:

![minus.gif][]  Collapse

tmp = a*x+b;

Note that the code is not evaluated at this point except for “normal” C++ variables like `a` and `b`. Therefore, at the time this line executes `a` = 3, and b = 2, and the above code will be evaluated as:

![minus.gif][]  Collapse

tmp = 3*x+2;

Note that unused variables, or variables used before initialization, will generate an error. Returning a value from the function is done with:

![minus.gif][]  Collapse

RETURN_INT(expr);

![minus.gif][]  Collapse

RETURN_DOUBLE(expr);

Note that a function must return a value. The function block ends with:

![minus.gif][]  Collapse

END

The basic control flow is provided by `IF` and `WHILE`:

![minus.gif][]  Collapse

IF(x > 0)
         IF(y > 0)
            z = x*y;
         IFEND
      ELSE
         z = 0
      IFEND 
    
      WHILE(z > 0)
         z -= x;
      WHILEND

In addition, a `PRINT(expr)` can be used to print to standard output:

![minus.gif][]  Collapse

PRINT(i);

Finally, after `END`, `FPtr` will point to the newly created function. You will need to cast the pointer to the actual function type though:

![minus.gif][]  Collapse

f1 = (FType)FPtr;

## Running the Code ##

You will need to download and build LLVM ([check this link][] for Visual Studio specific instructions). The DynCompiler code itself requires TR1 support in addition – e.g., Visual Studio 2008 with SP1.

## Status ##

DynCompiler is a proof-of-concept, and should not be taken seriously.

[Download code - 5.84 KB]: http://www.codeproject.com/KB/cpp/runtime_compile/code.zip
[LLVM Compiler Infrastructure]: http://llvm.org/
[strength reduction]: http://en.wikipedia.org/wiki/Strength_reduction
[minus.gif]: /images/20220823/318f37b030c44d909387c6610b358912.png
[SSE 4.1]: http://en.wikipedia.org/wiki/SSE4.1
[for an example]: http://pdos.csail.mit.edu/~engler/dpf.html
[LLVM tutorials]: http://llvm.org/docs/tutorial/
[check this link]: http://llvm.org/docs/GettingStartedVS.html