r0nsha/cwerg

A light-weight compiler backend

Cwerg

[Documentation]

Cwerg is a lightweight compiler backend aimed at experimental programming language implementations that want to avoid heavy dependencies like LLVM. It has no dependencies and can directly generate ELF executables for Arm32 and Arm64 ISAs.

The project is very much "work in progress" and currently consists of:

• RICS like Intermediate Representation (IR)
• Optimizer for the IR
• C Frontend (supports a subset of C)
• WASM Frontend (transpiler WASM to Cwerg)
• Elf Support Lib ((de-)compiler for ELF object files)
• A32 Support Lib ((dis-) assembler for ARM32 instructions)
• A64 Support Lib ((dis-) assembler for ARM64 instructions)
• A32 Backend (code generator emitting ARM32 instructions)
• A64 Backend (code generator emitting ARM64 instructions)
• C Backend (code generator emitting C code)

It is primarily aimed at AOT compilation but JITing will also be supported.

Most components are implemented twice (see rationale):

1. spec/reference implementation: Python 3.7
2. high performance implementation: C++17 (with limited STL usage)

Re-implementations in other languages are explicitly encouraged. A lot of code is table driven to facilitate that.

Cwerg de-emphasizes quality of the generated code (we hope to come within 50% of state of the art compilers) in favor of a small code base that can be understood by a single developer and very fast translation times.

Size Targets

The project tracks code size in LOC carefully. The goal is to limit the IR optimizer to 10kLOC and an additional 5kLOC for each supported target ISA (per implementation language). Note, that code generated from tables is not counted but the tables (written in Python) are.

Speed Targets

The goal for the c++ implementation is to translate the IR to an Elf executable at a speed of 500k IR instructions per sec using at most 4 cores on a 2020 era midrange desktop or high end laptop.

Whole program translation and parallel translation at the function level are explicit design goals for the C++ implementations.

Cwerg does not have a linker. Instead the responsibility of generating executables and resolving relocations rests with the assembler components of the various backends. An ELF library helps with the generation of ELF executables, which is the only object format currently supported.

Intentional Limitations

To keep the project lightweight the feature set must be curtailed. Since the project is still evolving, the details are not entirely cast in stone but the following features are unlikely to be supported (contact us before starting any work on these):

• Instruction sets other than little endian (host and target) with 2's complement integers.
• Variable number of function parameters (var-args). Basically only used for printf/scanf and responsible for a disproportionate amount of complexity in ABIs. (Note, this precludes a proper C frontend.)
• Full-blown dwarf debug info. The standard is over 300 pages long and unlikely to fit into the complexity budget. Line numbers will likely be supported.
• C++ exception/unwind tables. A lot of code and complexity that only benefits one language.
• Linking against code produced with other toolchains. There are currently no plans to emit linkable object code. And there is no ABI compatibility except for simple cases.
• Shared libs/dynamic linking adds complexity and slows programs down (both because of slower code idioms and prevention of optimizations), not to mention the DLL hell problem. (see also: https://drewdevault.com/dynlib, https://www.kix.in/2008/06/19/an-alternative-to-shared-libraries/)
• Sophisticated instruction scheduling which is less important for memory bound code and out-of-order CPUs.
• Sophisticated loop optimizations. Probably best left to the frontend.
• Variable sized stack frames (alloca). This requires a frame pointer, wasting a register, and makes it more difficult to reason about stack overflows.
• A large standard library with unicode and locale support. Those add a lot of complexity and are better left to dedicated libraries.

It is not clear if an X86-64 backend will fit into the complexity budget, especially since X64-64 idiosyncrasies tend to leak complexity into the generic layers.

The IR optimizer currently does not use a full-blown Single Static Assigment (SSA) form. Instead it uses a modified use-def chain approach to get some of the benefits of SSA.

Dependencies

Cwerg controls dependencies carefully to keep them at a bare minimum:

• pycparser used by the (optional) C frontend

Inspirations

• LLVM
• QBE (QBE vs LLVM)
• Mir (blog post)
• Wirth: A Plea for Lean Software, Oberon (compiler implementation)
• Delphi's compilation speed
• gcc code size