Codegen

An experiment on AOT and JIT code generation, including IR transformations for optimisation.

The goal of this project is not only to learn how to implement optimisations by putting into practice data-flow analysis theory, but also to design and structure the code as clearly as possible such that it is easy for others to read, and thus learn from. This project currently focusses on the back-end, so front-end operations such as lexing and parsing are omitted.

The project will take an incremental approach of first compiling a tiny subset of the source language all the way down to the target language or machine code, which at the moment is x64, then gradually increasing the size of the subset—a method inspired by Abdulaziz Ghuloum's An Incremental Approach to Compiler Construction, and Nora Sandler's Writing a C Compiler.

Current Progress

The program is currently capable of transforming, without optimisations, an AST representing a C-like compound statement containing multiple return statements with optional return values (either add expressions of depth 1, or unsigned 32-bit integers), to x64 assembly, then executing it dynamically. An example is as follows:

Input AST:

compound_statement
|-return_statement
| `-additive_expression '+'
|   |-integer_literal 3735928549U # 0xDEADBEE5
|   `-integer_literal 10U # 0xA
|-return_statement
`-return_statement
  `-integer_literal 0U # 0x0

IR:

0000 basic_block {
    $0 = add 3735928549U, 10U
    return $0
    return ()
    return 0U
}

Generated bytes:

            00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
0x00000000: B8 E5 BE AD DE 05 0A 00 00 00 C3 C3 B8 00 00 00  ................
0x00000010: 00 C3                                            ..

Disassembly:

0x00000000: mov     eax, 0xDEADBEE5
0x00000005: add     eax, 0xA
0x0000000A: ret
0x0000000B: ret
0x0000000C: mov     eax, 0
0x00000011: ret

Execution:

function() = 0xDEADBEEF

Building

Requirement	Minimum Version
CMake	3.23
Ninja	-
vcpkg	-
C++ Compiler	C++23 support

CMake and Ninja are available through your system package manager.

Although not advised, libraries that are used can be found in vcpkg.json, and can alternatively be installed manually using your system package manager as well.

Build using the following commands:

cmake --preset <preset> .
cmake --build ./build/<preset>

Where <preset> is one of the non-hidden presets in CMakePresets.json. The /build directory will contain the executable.