From Tree Walking to Bytecode

Switching to Bytecode

The original interpreter just directly interpreted the C AST, as that was relatively straightforward to do, but it had a lot of limitations that I didn't like.

1. Used the C native call stack for interpreted function call boundaries.
   • Essentially, every call into an interpreted function would cause an actual recursive function call in the interpreter loop. This was noticeable when trying to run the self-hosted compiler tests with sanitizers enabled. As the tests are aggressively multithreaded, they would run with much smaller stacks so this would lead to stack exhaustion under asan. Switching to bytecode made it easy to just assign to the program counter and we already used a linked-list of interpreter stack frames to represent the interpreted call stack.
2. Couldn't do arbitrary control flow inside an expression.
   • The original interpreter had a linearized representation for statements (each statement was just a node in a flat array, which was trivial to flatten from a C AST), but expressions were kept in their original tree form. We would recurse down this tree using the host's call stack, which could also lead to native stack exhaustion for highly nested expressions under asan with default pthread worker stack sizes.
   • Because you were in the middle of recursing down a tree, you couldn't do control flow like loops, gotos, ifs, etc. in the middle of evaluating an expression. This is not a problem in standard C, but real system C headers use the gnu statement expression extension. As the goal is to use native headers and libraries, this meant we had to implement this extension. Switching to a flat bytecode where statements and expressions are just different operations in a linear array meant that we could express control in the middle of evaluating an expression.
3. It was slow
   • Not only did the tree interpreter have some significant limitations, it was also just slow. Some casual benchmarks comparing it to cpython (which is not a fast interpreter) showed it was half the speed on tasks like summing numbers or calculating primes. I think python was even faster on mandelbrot, which is kind of embarrassing. Profiling showed that we were doing a lot of semantic work in the middle of the interpreter loop, like evaluating the size of types to how big our expression result buffers needed to be. Some of these problems were because we didn't have a pass after parsing - it would just jump straight from a parsed AST to interpreting it. Adding a lowering pass means a lot of this stuff could be baked into the bytecode instead of looked up at runtime.
4. It was wrong
   • The tree interpreter also took a lot of shortcuts, especially around things like floating point (evaluating all float in double, which is a valid C FLT_EVAL_METHOD, but we are trying to match the specified native target). It did what it had to do, it got the project from just successfully parsing C to actually doing fun interactive things with it. But since we were doing some sema in the middle of interpreting, the best way to fix the correctness issues was to add a lowering pass over the AST, at which point it was easy to just lower to a bytecode.
5. JIT was intractable
   • The goal of the project is to not interpret C code forever, but to eventually generate native machine code for all functions (which will also allow us to drop libffi and its limitations). Doing that directly from the C AST was going to be too big a pain (I've tried doing that before, it sucks). So I wanted a bytecode/IR format that would be faster to execute but would also map reasonably well to something you could convert to native code.

Switching from tree-walking to bytecode is a well-tread path. Instead of walking the expression trees at runtime, the new design walks the statement/expression trees after parsing, lowering it into a flat series of instructions. I also wanted to eliminate consulting target metadata at execution time, so the bytecode bakes in things like sizes, floating point format and bounds checking (as an explicit op) into the format itself.

So work slowly began on porting all of the needed machinery into a bytecode format. If you're into that kind of thing, you can see the format here.

The Bytecode

The bytecode is 32 bytes per instruction and packs in what the operation is, src location and all the necessary metadata. Immediates up to 16 bytes can be stored inline.

A simple function like:

// foo.c
int add(int x, int y){
    return x + y;
}

Gets lowered into:

$ drc --dis add foo.c

add(int x, int y) -> int{
  0x00)  [8:12] = [0:4] + [4:8] // foo.c:2:14
  0x01)  return [8:12]          // foo.c:2:5
}

Which is a pretty printed version of the bytecode. Note that the bytecode contains src locations (which are optimized to be a pointer-sized value), which will be useful when we dynamically generate in-memory debug info for the JIT.

It is a slot-based design. Slots are sized stack offsets from the frame base. Variables and temporaries get fixed space reserved for them in the interpreter's call frame. Ops directly load from slots and write to slots. The first slots are the function's arguments.

So in this example:

0x00)  [8:12] = [0:4] + [4:8]

We directly read the operands to add from the slot spanning offset 0 to 4 (x, 4 bytes) and from the slot spanning 4 to 8 (y, 4 bytes). Those get added and directly written to the slot spanning 8 to 12. The bytecode encodes this is a 4 byte add, the pretty printer elides it as it is evident from the slot sizes. Signed and unsigned adds are the same on all of our supported targets so there is no separate bytecode.

0x01)  return [8:12]

The return value is read out of the slot spanning 8 to 12.

A more complicated function:

long fib(long n){
    long a = 0, b = 1, c;
    for(long i = 0; i < n; i++){
        c = a + b;
        a = b;
        b = c;
    }
    return a;
}

$ drc --dis fib fib.c
fib(long n) -> long{
  0x00)  [8:16] = 0                     // fib.c:2:14
  0x01)  [16:24] = 1                    // fib.c:2:21
  0x02)  [32:40] = 0                    // fib.c:3:18
  0x03)  if !([32:40] < [0:8]) jump 0x9 // fib.c:3:5
  0x04)  [24:32] = [8:16] + [16:24]     // fib.c:4:15
  0x05)  [8:16] = [16:24]               // fib.c:5:13
  0x06)  [16:24] = [24:32]              // fib.c:6:13
  0x07)  [32:40] = [32:40] +u 1         // fib.c:3:29
  0x08)  jump 0x3                       // fib.c:3:5
  0x09)  return [8:16]                  // fib.c:8:5
}

The first 3 instructions are initializing a, b, and i. c was not initialized so we do nothing (in the interpreter, frames are zero-allocated anyway, but this leaves the IR more similar to native code).

Then we hit the loop condition. We have a specialized fused cmp-jmp instruction as it is so common and reading the check out of a slot wouldn't actually match most native instructions anyway. This way we can avoid materializing an actual boolean slot, just to read it back out again immediately.

The loop body does the usual fibonacci arithmetic, then we increment i using an add with an immediate value (the u annotation is a consequence of all arithmetic ops being packed into one instruction so it is an add with an unsigned immediate, which would matter for other arithmetic ops other than add). Finally we jump back to the conditional. The conditional can jump us forward to the return.

And an example with gnu statement expressions (one of the main motivations):

typedef struct Result Result;
struct Result {
    _Bool error;
    int payload;
};
Result may_fail(int);
void abort(void);
int use_result(int x){
    // pretend this is the result of macro expansion
    return ({
        typeof(may_fail(x)) r = may_fail(x);
        if(r.error)
            abort();
        r.payload;
    }) + 3;
}

$ drc --dis use_result gnu.c
use_result(int x) -> int{
  0x00)  [16:20] = [0:4]                 // gnu.c:11:42
  0x01)  [4:12] = call may_fail([16:20]) // gnu.c:11:41
  0x02)  if ![4:5] jump 0x4              // gnu.c:12:9
  0x03)  call abort()                    // gnu.c:13:18
  0x04)  [12:16] = [8:12] + 3            // gnu.c:15:8
  0x05)  return [12:16]                  // gnu.c:10:5
}

The 8 byte struct return value of may_fail() gets written to the slot spanning 4 to 12. We can then read the 1 byte bool out of the slot and use it to jump over the abort. Finally, a read + add with immediate 3 from the payload field of the struct is assigned to the slot used for the return value.

Despite an expression with control flow, local variables and external calls appearing in the middle of an add expression in the middle of a return statement, the flat IR handles it perfectly.

Speedup

The following C programs were used to measure the bytecode speedup. An equivalent python script was also run. Timings were obtained on my apple laptop from 2021 while watching TV and browsing the web, and I ran it a few times, so very scientific results. All of the program results/checksums were identical. I checked out an old commit for Treewalker that was before bytecode work.

// mandelbrot.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
enum {
    WIDTH      = 800,
    HEIGHT     = 800,
    MAX_ITER   = 256,
    NTHREADS   = 4,
};
int iterations[WIDTH * HEIGHT];
typedef struct WorkItem WorkItem;
struct WorkItem {
    int row_start;
};
void* worker(void* arg){
    WorkItem* w = (WorkItem*)arg;
    for(int py = w->row_start; py < HEIGHT; py += NTHREADS){
        for(int px = 0; px < WIDTH; px++){
            double x0 = (px - WIDTH  / 2.0) * 4.0 / WIDTH;
            double y0 = (py - HEIGHT / 2.0) * 4.0 / HEIGHT;
            double x = 0, y = 0;
            int iter = 0;
            while(x*x + y*y <= 4.0 && iter < MAX_ITER){
                double tmp = x*x - y*y + x0;
                y = 2*x*y + y0;
                x = tmp;
                iter++;
            }
            iterations[py * WIDTH + px] = iter;
        }
    }
    return NULL;
}

int main(){
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_t threads[NTHREADS];
    WorkItem items[NTHREADS];
    for(int i = 0; i < NTHREADS; i++){
        items[i].row_start = i;
        pthread_create(&threads[i], NULL, worker, &items[i]);
    }
    for(int i = 0; i < NTHREADS; i++)
        pthread_join(threads[i], NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    long checksum = 0;
    for(int i = 0; i < WIDTH * HEIGHT; i++)
        checksum += iterations[i];
    printf("Grid:     %dx%d, max_iter=%d, threads=%d\n", WIDTH, HEIGHT, MAX_ITER, NTHREADS);
    printf("Checksum: %ld\n", checksum);
    printf("Time:     %.3f seconds\n", elapsed);
    return 0;
}

# mandelbrot.py
import time
from multiprocessing import Pool
WIDTH    = 800
HEIGHT   = 800
MAX_ITER = 256
NTHREADS = 4

def compute_rows(row_start):
    results = []
    for py in range(row_start, HEIGHT, NTHREADS):
        for px in range(WIDTH):
            x0 = (px - WIDTH  / 2.0) * 4.0 / WIDTH
            y0 = (py - HEIGHT / 2.0) * 4.0 / HEIGHT
            x, y = 0.0, 0.0
            it = 0
            while x*x + y*y <= 4.0 and it < MAX_ITER:
                x, y = x*x - y*y + x0, 2*x*y + y0
                it += 1
            results.append(it)
    return results

def main():
    t0 = time.monotonic()
    chunks = list(range(NTHREADS))
    with Pool(NTHREADS) as pool:
        all_results = pool.map(compute_rows, chunks)
    t1 = time.monotonic()
    checksum = sum(sum(r) for r in all_results)
    print(f"Grid:     {WIDTH}x{HEIGHT}, max_iter={MAX_ITER}, threads={NTHREADS}")
    print(f"Checksum: {checksum}")
    print(f"Time:     {t1 - t0:.3f} s")

if __name__ == "__main__":
    main()

// sieve.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

typedef struct {
    bool* data;
    long length;
} InterpreterList;

InterpreterList* create_list(long length, bool default_value) {
    InterpreterList* list = malloc(sizeof *list);
    list->data = malloc(sizeof(bool) * length);
    list->length = length;
    memset(list->data, default_value, length);
    return list;
}

void free_list(InterpreterList* list) {
    free(list->data);
    free(list);
}

long run_sieve(long limit) {
    InterpreterList* primes = create_list(limit + 1, true);
    primes->data[0] = false;
    primes->data[1] = false;
    long p = 2;
    while(p * p <= limit){
        if(primes->data[p]){
            long i = p * p;
            while(i <= limit){
                primes->data[i] = false;
                i += p;
            }
        }
        p++;
    }
    // Count the primes
    long count = 0;
    for(long idx = 0; idx < primes->length; idx++){
        if (primes->data[idx]) {
            count++;
        }
    }
    free_list(primes);
    return count;
}

int main() {
    long limit = 2000000;
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    long count = run_sieve(limit);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("Found %ld primes.\n", count);
    printf("Execution time: %.3f seconds\n", elapsed);
    return 0;
}

# sieve.py
import time
def run_sieve(limit):
    primes = bytearray([True]) * (limit + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= limit:
        if primes[p]:
            i = p * p
            while i <= limit:
                primes[i] = False
                i += p
        p += 1
    count = 0
    for is_prime in primes:
        if is_prime:
            count += 1
    return count

def main():
    limit = 2000000
    start = time.perf_counter()
    count = run_sieve(limit)
    end = time.perf_counter()
    print(f"Found {count} primes.")
    print(f"Execution time: {end - start:.4f} seconds")

if __name__ == "__main__":
    main()

// sum.c
#include <stdio.h>
#include <time.h>
void do_sum(long cap){
    // volatile as otherwise clang optimizes this out lol
    volatile long x = 0;
    for(long i = 0; i < cap; i++)
        x += i;
    printf("%ld\n", x);
}
int main(){
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    do_sum(100000000);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("Execution Time: %.3f seconds\n", elapsed);
    return 0;
}

import time
# in real code, you just do sum(range(cap)), but
# we're trying to measure the speed of the interpreter,
# not the Cpython builtins.
def do_sum(cap):
    x = 0;
    i = 0
    while i < cap:
        x += i
        i += 1
    print(x)

def main():
    start = time.perf_counter()
    do_sum(100000000)
    end = time.perf_counter()
    print(f"Execution time: {end - start:.4f} seconds")

if __name__ == '__main__':
    main()

"Native" is apple-clang -O0.

Huge difference! Still far off from native instructions, but we're getting there.

Conclusion

I was originally going to write about multiple things I thought were neat in my C compiler. Instead you got to read about how I switched my C interpreter from tree-walking to an IR-ish bytecode and got an 8x speedup.

The interpreter still needs to be profiled and optimized, but we have ditched the native recursion for every expression, encoded sizes in the instructions themselves and made unconventional control flow easy to produce. We've also set up a better foundation for generating machine code at runtime.