SAD - ylab-nsu/cdm16-llvm-neo GitHub Wiki

• Andrey Eliseev (@aelsi2, [email protected]) — core backend, no-cocas target, rust
• Matvey Zenin (@proletcultist, [email protected]) — core backend, cocas target, cdm-rt
• Alexander Volk (@sxrose, [email protected]) — core backend, optimization, CI/CD
• Stepan Kuchenkov (@netscapenav, [email protected]) — cocas asm streamer, cdm-rt builtins

• Compilation of C and Rust programming languages
• Targeting CDM-16, generation of CDM-16 machine code
• Output of machine code as object files and assembly code
• Linking of object files, generation of CDM-16 von Neumann memory images

• Abstraction layer over platform features allowing startup, interrupt control and I/O without assembly
• Support for Ubuntu 24.04 and macOS 26 on the compilation host
• Support for C's freestanding environment (as specified by ISO/IEC 9899:2024)
• Support for Rust's core crate, no_std environment

• The compilers are based on the existing fork of LLVM with CDM-16 support
• The compilers must be able to generate assembly code and object files. They must be able to link object files into a memory image.
• There must be a standard library with an implementation of the C freestanding environment.
• There must be a library that implements the functions the compiler uses to replace operations not natively supported by the platform, such as integer multiplication and division.
• There must be high-level API for accessing hardware features of CDM-16 without the use of assembly code
• An automated CI/CD system is required to build and test the compiler for both operating systems and publish distribution artifacts.

• The compilers should be able to generate Cocas-compatible object and assembly files. This would make it easy for students to inspect these files with a text editor. This would also make it easier to integrate the compilers with students' existing projects.
• Generated code should ideally be as small as possible, because CDM-16 can only address 64 kilobytes of memory. It is not a lot for a large project, like an operating system.
• Any additional tools should be written in Python, because it's used in the existing SDK. They could also be written in C++ or Rust, if they are closely tied to the C and Rust compilers respectively.
• The distribution artifacts for each compiler should ideally be a single archive and require no setup, other than extraction. This is so that the compilers are easily accessible to students, the intended user base.
• Compiler source code must be well-structured and easy to understand for students, who will likely maintain it in the future.

The existing LLVM backend already has a Cocas assembly writer, but it needs some work, because the generated code is often invalid.

Cocas' assembly language is quite limited, as it lacks several important features:

• file-local labels
• weak labels and imports
• label assignments

It is possible to:

• extend Cocas to support these features
• implement an instruction parser in the LLVM backend and use the integrated assembly parser with GNU assembly syntax

Extending Cocas would require a lot of changes to its codebase. Support would also have to be added in the object file format and the linker. Implementing an instruction parser would not require many changes to existing code. If we use the integrated assembly parser, we would obviously need to use the integrated assembler and implement an object writer inside LLVM (see section 2.2)

The existing backend only supports generation of Cocas assembly files, but not objects files. There are several ways object generation could be handled:

• Have the compiler generate Cocas assembly files and invoke Cocas to assemble them into object files.
• Write object files directly with an object writer integrated into LLVM:
  • Use the Cocas object format
  • Use a subset of ELF (relocatable files only)

The first option would make it possible to re-use the existing assembler and linker, but it ties our compiler to Cocas as an external dependency. Writing machine code as a text file first, and having Cocas read it back to produce an object file is also not ideal for performance, especially since Cocas is written in Python. Furthermore, Cocas' proprietary object file format has the same limitations as the assembly language (no weak and file local symbols), which is problematic for LLVM support.

The second option would allow us to have no external dependencies for object generation and avoid the performance penalty of Cocas. Re-implementing a Cocas object writer in LLVM is a serious undertaking, and the format is still limited. ELF, on the other hand, is the best supported format in LLVM, so there are no issues with format limitations. Adding ELF support would also be comparatively easy, since LLVM already has a generic ELF writer.

If ELF files are used, they also need linker support. There are a few options:

• Add support for a relocatable ELF files to Cocas
• Write a linker from scratch
• Add CDM support to LLVM LLD

The first two options are very time-consuming. The last option is more viable, because LLD already has generic ELF support.

Users may want to link Cocas object files together with ELF files. There should ideally be a tool to convert Cocas objects to ELF objects and the other way around.

The C23 standard (ISO/IEC 9899:2024) requires conforming freestanding implementations to fully support <float.h>, <iso646.h>, <limits.h>, <stdalign.h>, <stdarg.h>, <stdbit.h>, <stdbool.h>, <stddef.h> and <stdint.h> headers. These headers do not declare any functions, so we can use the existing implementations, except <stdint.h>, which needs the integer types to be properly defined for CDM-16.

The standard also requires a subset of <string.h> and memalignment from <stdlib.h> to be available. This means that we need to implement a runtime library with these functions.

We could:

• Use an existing implementation of libc (e.g. the one from LLVM)
• Use some other libc implementation
• Write our own minimal libc

A full libc implementation is overkill for our platform because the CPU is quite slow (simulated in Logisim with frequencies of up to 10KHz), there is very little RAM (only 64K), and there is no OS support (yet). We can't use LLVM's libc because it uses C++, which we do not support. Any other libc implementation would need to be supported in the Cocas target and integrated with our build system, which may be problematic.

The MOS LLVM fork, which is quite similar to the CDM fork, has its own libc implementation.

Rust's core crate depends on the memory functions from <string.h>. There are several ways to satisfy this requirement:

• Use the existing function in Rust's compiler-builtins crate (which is always included into every build)
• Rewrite the functions in compiler-builtins in assembly
• Link the library used in Clang
• Provide a separate crate with builtin functions
• Use Clang as a linker front-end and have it link the standard library automatically

The <string.h> functions in compiler-builtins are written in Rust, so they have a large memory footprint. Rewriting these functions in assembly in compiler-builtins would mean code duplication between the LLVM and Rust codebases. The Clang library could be packaged with Rust, but this would require hacks in Rust's compiler build system. Linking this would still require manual setup from the user, because Rust's build system does not search the compiler install directory for target libraries. The setup could be made easier by packaging a pre-built library into a separate crate. Alternatively, Rust could use Clang as a linker frontend, and Clang would link the same default libraries as when compiling C code. This approach has the downside of making Rustc depend on Clang.

CDM-16 has no hardware multiplication and division. The standard approach to handling this in LLVM backends is generating a call to a library function, such as __mulhi3 (16-bit multiplication). It is also possible to make the backend generate the software algorithms in-line, but this would require much more effort.

These functions could be:

• Made a part of the builtin LLVM library, compiler-rt.
• Put into a separate library.

Official targets like AVR put their builtins into compiler-rt. Putting our builtins in compiler-rt is problematic because of the need to support the Cocas target that requires special build logic.

The MOS fork has a separate library for this.

Rust's compiler-builtins crate re-implements the builtin functions implemented in compiler-rt. Some of these implementations are generic, and some are platform-specific. But notably there are no platform-independent implementations of multiplication and division. So everything said about memory functions in section 2.3 also applies to arithmetic builtins.

Users need to have access to hardware features of CDM-16 in high-level code. They need to be able to:

• disable interrupts,
• enable interrupts,
• get interrupt state,
• set interrupt state,
• wait for an interrupt,
• trigger software interrupt,
• reset processor to interrupt vector,
• halt processor.

Most of these directly map to a hardware instruction.

There are two ways these functions can be implemented in the compilers:

• As regular functions in a library written in assembly.
• As macros or inline functions that expand to inline assembly blocks.
• As intrinsics in LLVM that will expand into appropriate machine instructions with corresponding Clang and Rust builtin functions.

Implementing these as regular functions would add a bit of runtime overhead. Inline assembly and intrinsics don't add extra overhead. Intrinsics+builtins require a bit more work to implement, but the user code is cleaner with them, since builtin calls look like regular function calls.

There two ways we could set up an automated build system for our compilers:

• Use our own build server with a CI/CD system, like Jenkins.
• Use GitHub Actions.

Although the first approach gives us a wide range of customization options, it requires a server, which we may need to rent, and also need additional configuration to integrate with GitHub.

GitHub Actions gives us both servers (it is also possible to use our own server) and integration with the repository out of the box. The environment GitHub Actions provides meets the requirements for LLVM's build system.

Our toolchain consists of the following primary parts:

• Compilers
  • Clang - part of LLVM, written in C++
  • Rustc - separate from LLVM, but uses it for code generation, written in Rust
• LLVM backend - common LLVM IR to CDM-16 machine code compilation logic shared between compilers, written in C++
• Assemblers
  • Cocas - part of cdm-devkit, written in Python, used for generating object files from the proprietary syntax
  • Built-in LLVM assembler - part of the backend, can be invoked through Clang or llvm-mc, used for generating ELF object files directly from IR or from GNU assembly syntax
• Linkers
  • Cocas - used for linking objects in the proprietary format
  • LLVM LLD - part of LLVM, written in C++, used for linking ELF object files
• Runtime library - written in CDM-16 assembly, linked with user's code, provides implementations of various standard functions
• Testing system
  • llvm-lit - written in Python, LLVM's testing system for verifying code generation correctness
  • End-to-end testing system - written in Python, compiles C code with Clang and runs it on a CDM-16 emulator

The compilation process is described in more detail in section 4.2.

All CDM-specific runtime libraries used by Clang are grouped into cdm-rt, a separate project in the LLVM repository. All functions in cdm-rt are implemented in assembly to ensure maximum performance. cdm-rt consists of the following parts:

• builtins - implementation of compiler-generated functions (like __mulhi3)
• crt0 - default interrupt vector table, minimal startup code
• c - implementation of the standard C library functions required in freestanding environments

cdm-rt is not used in Rust. The compiler-generated functions (arithmetic and memory operations) are implemented in Rust's compiler-builtins crate (also in assembly). Rust doesn't include startup code by default when compiling for no_std targets, so the interrupt vector table has to be defined by the user.

There is a set of standard CDM-specific headers included in the Clang distribution:

• <cdm/execution.h> - processor execution control functions
• <cdm/register.h> - special registers access functions
• <cdm/interrupt.h> - interrupt control functions
• <cdm/ivt.h> - macros for defining interrupt handler functions

Analogously, there is a set of Rust crates called cdm-rs, providing access to CDM-16 platform features:

• cdm
  • interrupt and processor status control API
  • an implementation of critical-section (optional Cargo feature)
  • a panic handler (optional Cargo feature)
• cdm-rt
  • minimal startup code
  • default exception handlers
  • utilities for defining the interrupt vector table (IVT)
  • a linker script required for placing the IVT at the correct memory location

Our projects use the existing build systems from LLVM (based on CMake) and Rust (custom Rust build scripts).

cdm-rt is built as a part of LLVM. It is first compiled into ELF files for the cdm target (see section 4.1) and then converted into Cocas object files for the cdm-cocas target with llvm-objcopy. This is done so that Cocas is not required for building the compiler itself.

Both compilers are built in the cloud using GitHub Actions. Releases are made automatically when a Git tag is created.

Our testing system consists of two parts:

• assembly-based codegen tests
• end-to-end integration tests

Codegen tests are implemented using LLVM's testing system called llvm-lit. These tests mostly verify that LLVM IR code is compiled into machine code correctly. Some of these tests also verify compilation of C source code. End-to-end tests use a custom testing system written in Python that compiles C programs and runs them on the CDM-16 emulator from cdm-devkit.

Both kinds of tests are run automatically when building the compiler with GitHub Actions.

Our toolchain support two LLVM target triples that differ in which assembler and linker is used:

Target triple	Assembler (syntax)	Linker (format)	Supported by
cdm	Integrated LLVM assembler (GNU)	LLVM LLD (ELF)	Clang, Rustc (known as cdm_none)
cdm-cocas	Cocas (proprietary)	Cocas (proprietary)	Clang

Code generated for the cdm target may be used with Cocas by converting ELF object files to Cocas' proprietary format using the llvm-objcopy tool.

Both Clang and Rustc implement a so-called compilation driver. A compilation driver is a subsystem that orchestrates the process of compilation by invoking different tools, like the compiler, assembler, linker and possibly others.

Clang allows targets to customize any part of the toolchain, including the assembler and the linker. Our two targets have different driver implementations:

• cdm-cocas driver implements abstract interfaces for Cocas as both the linker and the assembler and forbids direct source-to-object compilation
• cdm driver implements an interface for LLD but does not implement an interface for an assembler and instead allows direct compilation to object files

Unlike Clang, Rustc does not allow such customization. The only thing that can be swapped is the linker. Rustc's cdm_none target also uses LLVM LLD as its linker.

The compilation steps for Rustc and Clang (both targets) shown on the image below.

• Host OS/Arch (any of the following):
  • Ubuntu 24.04/x86_64
  • macOS 26/aarch64
• Target OS/Arch:
  • bare metal/CDM-16
• Host runtime dependencies:
  • cdm-devkit 0.2.3 or later (cdm-cocas target only)-
  • Clang CDM-16 (for Rust)
• Target runtime dependencies:
  • none
• Languages:
  • C++ (LLVM)
  • Rust (Rust toolchain)
  • Python (Cocas, testing system)
• Compiler build dependencies:
  • Clang 17 or later
  • CMake 3.28.3 or later
  • Ninja 1.11.1 or later
  • Python 3.10 or later
  • Rust 1.89 or later (can be auto-downloaded)
• Compiler test dependencies:
  • GNU Make 3.81 or later
  • cdm-devkit 0.2.3 or later
  • Python 3.10 or later