Self-hosting¶
Kod's compiler is written in Kod and compiles itself. A checked-in binary of it, the snapshot, is what builds it from source.
Status¶
The self-hosted compiler sh_kodc exists and is the production path. make stage1 builds it, and every kod build / kod run / kod test invocation uses it for codegen when available.
Sources in Kod:
| File | Role |
|---|---|
stdlib/kod/lexing.kod |
Tokenizer |
stdlib/kod/parsing.kod |
Parser (AST built into a pool of int64 ids) |
stdlib/kod/ast.kod |
AST node types |
stdlib/kod/regalloc.kod |
Register allocation over the emitted instructions |
stdlib/kod/codegen.kod |
ARM64 assembly emitter |
stdlib/kod/build.kod |
Import resolution and whole-program registration |
kodc.kod |
sh_kodc entry point: compile a module, emit the _main shim |
tools/kod.kod |
The native kod driver: build / run / test / check |
sh_kodc reads a .kod file and emits ARM64 assembly to stdout, plus a few internal subcommands (_compile, _emit-runtime-main, _emit-test-runtime-main).
Build chain¶
bootstrap/sh_kodc checked-in sh_kodc snapshot
build/stage0/ C runtime objects, the always-linked stdlib modules, and the
compiler library shared by sh_kodc and the kod driver
build/stage1/ sh_kodc + its .s/.o, plus runtime_main.{s,o}
build/apps/kod/ the native kod driver
build/apps/<stem>/ the final executable; its objects are in <stem>.obj/, a tree that
mirrors the source tree (see Modules, "Symbol and object names")
link.cfg how everything is linked, read by the Makefile and by kod
Driven by the Makefile:
- stage0: the checked-in snapshot
bootstrap/sh_kodccompiles the always-linked stdlib modules and the compiler library to assembly;asassembles them andclangbuildsarena.c,rc.candruntime.c. - stage1: the snapshot compiles
kodc.kodand writes the_mainshim;clanglinks everything intobuild/stage1/sh_kodc. Sosh_kodcis the current compiler sources, compiled by the snapshot. - apps:
kod build foo.kodcompiles each of the program's modules withbuild/stage1/sh_kodctobuild/apps/foo/foo.obj/<path>.oand links them againstbuild/stage0/.
Two consequences: a codegen change reaches user programs right away, but the stage0 stdlib modules keep the snapshot's codegen until make bootstrap-snapshot refreshes it. And the compiler sources themselves may only use features the snapshot can compile.
There is no other way in: without the snapshot, make stops and says how to restore it. See Refreshing the snapshot and Recovering from a bad snapshot.
The link configuration¶
link.cfg at the repository root describes the link once. The Makefile includes it and tools/kod.kod reads it, so both link the same way. One NAME := word word ... per line, and nothing else:
- A name is capital letters, digits and
_, starting with a letter, and is set once per file. - Words are separated by one space. A word is letters, digits and the characters
_ . / , = + @ -; there is no quoting, no$(...), no continuation line, no tab, no trailing space. - A line that starts with
#is a comment, and an empty line is skipped. A#anywhere else in a line is an error, and so is a comment that ends in\.
kod rejects a line that does not fit, naming the file and line; for a line that fits, Make and kod read the same words. link.local.cfg (untracked) is read after link.cfg and overrides single names on one machine; a new git worktree needs its own copy. It overrides and does not add: a name there that link.cfg does not set (a typo, or a name of Make's own such as STAGE0 or SHELL) is an error in both. Neither accepts a LINK, AS, RUNTIME_C or STAGE0_KOD that ends up empty.
| Name | Meaning |
|---|---|
LINK |
command that links an executable: clang -target arm64-apple-darwin -Wl,-dead_strip. clang finds the SDK and the macOS version. |
AS |
what assembles a .s file. kod (the default) writes the object in the compiler's own process, with stdlib/kod/macho.kod: no assembler is started, and a module compiled by kod build goes from the compiler's instructions to its object without being written as text at all. Any other value is a command run as AS -o file.o file.s, such as clang -target arm64-apple-darwin -c -x assembler, clang's own assembler (what as runs, minus an xcrun shim and a script). The Makefile's own rules read kod as the compiler that wrote the .s (the snapshot, or the stage being checked), run as sh_kodc _assemble file.s file.o. tools/as_diff.kod (./kod run tools/as_diff.kod) checks that the two agree, by meaning, over every file of the corpus. |
CC, CFLAGS |
compile a C file: clang, -target arm64-apple-darwin -I stdlib -O2. The target is pinned as in LINK (and as), so a clang that follows the architecture of the shell it runs in (one under Rosetta) does not produce x86_64 objects that the arm64 link rejects. |
RUNTIME_C |
C files linked into every program; built to build/stage0/<name>.o |
STAGE0_KOD |
Kod modules linked into every program, in link order; prebuilt by the snapshot compiler to build/stage0/_<basename>.o, so their basenames must be unique |
A program links, in order: LINK, -o <exe>, the RUNTIME_C objects, the STAGE0_KOD objects, the program's module objects, the objects of the C files its modules name, its _main shim, and last the arguments its modules give with kod:link (see Modules). A module that declares such lines cannot be in STAGE0_KOD, nor be one of the compiler's own modules: the Makefile does not read them. kod says so for STAGE0_KOD, and a test checks the others. Adding an always-linked module is one more word in STAGE0_KOD; the Makefile derives its rule. make rebuilds the C runtime objects and relinks sh_kodc and kod when link.cfg or link.local.cfg changes (the objects also when a header in stdlib/ does, such as kod_rt.h), and also when the configuration in force is not the one they were built with (it keeps that in build/.link-config), so removing link.local.cfg, or a name from it, rebuilds too. A program gets the deployment target of the machine that builds it, as clang chooses it (MACOSX_DEPLOYMENT_TARGET in the environment overrides that).
Requirements: clang (Xcode Command Line Tools). kod is run from the repository root; from another directory it says link.cfg not found. Calling build/apps/kod/kod directly does not rebuild build/stage0/, so after a change to runtime.c or link.cfg run make kod (or ./kod, which does); when the configuration names an always-linked object that is not there yet, kod says build/stage0/_name.o not found; run make.
Refreshing the snapshot¶
Runs make selfhost-check, checks that the stage2 and stage3 binaries are byte-identical, and only then copies the stage2 sh_kodc over bootstrap/sh_kodc. It takes seconds. Commit the new binary on its own.
A feature takes two steps to reach the compiler's own sources: commit the feature, refresh the snapshot, and only then use it there. The compiler sources may use only what the snapshot can compile.
Don't rewrite the history of bootstrap/sh_kodc: each old version can build the sources of its time, which makes them the way back.
The snapshot is arm64-darwin only. Bringing the compiler to another platform means adding the target and cross-compiling from a Mac.
Recovering from a bad snapshot¶
The fixed-point check shows that a compiler reproduces itself, not that it is right: a snapshot with a bug that reproduces itself passes. If bootstrap/sh_kodc is lost or bad:
- Restore a good version from git, the newest one before the problem:
git log -- bootstrap/sh_kodc, thengit checkout <rev> -- bootstrap/sh_kodc. If it can't compile the current sources, check out the sources of that commit as well and work forward one snapshot at a time. - As a last resort, the tag
python-bootstrapis the last commit with the Python interpreter, which builds the compiler with no binary at all: check it out and runmake bootstrap-snapshot(about 11 minutes). From that compiler, work forward through later commits the same way.
What's still Python¶
Nothing. ./kod, the link at the repository root, starts the native tool, which refreshes the toolchain with make itself. Tests call build/apps/kod/kod and build/stage1/sh_kodc directly, and the stand-in servers some of them start (tests/support/github_api.kod, tests/support/http_fixture.kod) are Kod programs they build.
Codegen design¶
codegen.kod is a single-pass emitter built around a few key data structures:
- Expression / statement / type-expr pools on the parser: AST nodes are stored in flat arrays and referenced by
int64ids. - Struct / enum / interface tables on the codegen: registration happens before compilation; field/method lookups index these tables. Each module also keeps a table of the type names it declares, so a type name resolves in the module that wrote it: through that module's own table, the tables of the modules its import lists name, then the builtins', and
m.Tthrough the table of the module imported asm. - Register pool:
x8–x15used as expression temporaries; saved/restored across calls via stack spills as needed. Code nested too deeply for the pool saves every live register to frame slots and compiles with all of them free, so nesting has no fixed limit. - Instructions: each function is emitted into a buffer of
regalloc.Insnvalues, a low-level IR of operations on virtual registers (see Compiler IR);regallocallocates registers over it andarm64.kodwrites it out as assembly. - Generic monomorphisation: each unique
Map[str, int64]instantiation gets its own struct entry; methods compile once per instantiation. - Interface dispatch:
{data_ptr, vtable_ptr}cells on the heap, one vtable per (struct, interface) pair; primitives box implicitly.
Verifying self-hosting¶
Fixed-point check. build/stage1/sh_kodc compiles the compiler into build/selfhost/stage2/, that compiler compiles it again into build/selfhost/stage3/, and the two sets of assembly must be byte-identical. A miscompile in the compiler that changes its own behavior shows up as a difference. Takes a few seconds; make test runs it (tests/selfhost_test.kod).
It then compiles every .kod file in the repo (the make asm-diff corpus) with both build/stage1/sh_kodc and the stage2 compiler, and fails if any file's assembly, diagnostics or exit status differ, writing both outputs under build/selfhost/corpus-diff/. Stage1 is the current sources compiled by the snapshot and stage2 the same sources compiled by themselves, so a difference means the snapshot miscompiles some of the new compiler code, typically a construct it handles differently than the current compiler does. Compiler sources must then avoid that construct until the snapshot is refreshed.
Checking that a compiler refactor changes nothing¶
Builds sh_kodc at BASE (cached under build/asm-diff/), compiles every .kod file in the repo with both that compiler and the working tree's, and reports each file whose assembly, diagnostics or exit status differ. A pure refactor should report no differences. Both compilers read the working tree's stdlib/, so the comparison isolates changes to the compiler itself. The comparison is tools/asm_diff.kod, built to build/apps/asm_diff/asm_diff, which make asm-diff runs from the repository root. With --objects (build/apps/asm_diff/asm_diff --objects [BASE]), a file whose assembly is only written differently, the same diagnostics and status and the same object bytes once assembled (bne against b.ne), counts as unchanged.
Reading the assembly¶
kod build doesn't write a module's assembly: the instructions go straight
into its object. With KOD_ASM_TEXT set it does, as <module>.kod.s beside
the .o, and each instruction written as its machine word (.inst 0xaa0103e0)
has its text as a comment after the word. sh_kodc file.kod prints the
assembly, with the comments only when KOD_ASM_TEXT is set:
The object file is the same either way.
Checking that types are worked out consistently¶
With KOD_SHADOW_TYPES set, the compiler reports on stderr two things that would make a recorded type per expression unsafe:
SHADOW <phases> file:line <first> -> <later>: an expression whose inferred type changed within one function. The phases areC(reserving the function's slots, which types only function literals and, for the inliner, a callee's locals),W(the walk that checks whether a function returns) andE(compiling). Narrowing (x is T(y),x? or d) and a generic instance's default fields are the expectedEEcases.UNTYPED-STORE file <function number> <name>: a store into a binding before it has a type, which counts the value as a reference whatever it is. A program that compiles should have none.
tests/shadow_types_test.kod runs this over every .kod file in the repo and fails on anything but an EE change in a file that compiles. The language server relies on it: it compiles the buffer with record_kinds, which keeps the type each local, field, call and element had where it was compiled, and shows those types on hover and uses them to complete after x., a.b., f(). or xs[i]..