How the compiler works

The four crates

The repository is one Cargo workspace with four crates. All are written in Rust.

The driver, crates/sisuc/src/lib.rs, reads the command line, runs the stages in order and prints diagnostics. args.rs parses the command line with clap into a mode, and run.rs links a program into a private temporary directory, runs it and removes the directory. The sisu binary, main.rs, runs the driver on a thread with a 64 MiB stack. The compiler reads at most 1 GiB of source, so every position in the file fits in 32 bits.

The pipeline

All stages run in one process, with LLVM linked in as a library. Only the link step calls another program.

1. Lexertext → tokensSplits the UTF-8 source into names, numbers and symbols.
2. Parsertokens → ASTBuilds the syntax tree: the program as you wrote it.
3. CheckerAST → TIRResolves every name and types every expression. Rewrites shorthand such as for and ?? into simpler forms, and reports every error in one run. Its output is the typed tree, TIR.
4. MonoTIR → TIRCopies each generic function, class and enum once for each list of type arguments the program uses, so the stages after it see only concrete types.
5. MIRTIR → MIRA mid-level form in which every reference-count change is its own statement. It hands over each counted value's reference at its last read, so an array can change in place without a copy, and debug builds check every function. Borrowing the parameters a function only reads, removing the pairs that cancel out within a block, and building a new enum box into one that a match freed, are built and await their measured verdicts.
6. CodegenMIR → LLVM IRWrites the program in LLVM's language.
7. LLVMLLVM IR → objectOptimizes and writes x86-64 or ARM64 machine code.
8. Linkobject → executableThe system C compiler, cc, links it with the Sisu runtime.

The first four stages are the front end. front_end.rs runs them in order and returns the program with every diagnostic, sorted by position. sisu check stops after the checker. sisu build --emit stops later and prints what a stage produced: tokens, the AST, TIR, MIR or LLVM IR.

Lexer

crates/sisuc/src/lexer/, symbol.rs

A line break that can end a statement becomes a Newline token: statements end at newlines. A ; between two statements on one line becomes a Newline too, and an unnecessary one, such as a ; at the end of a line, is dropped with W0007 (ADR 0028). Escapes in a string or char literal are decoded here, so later stages never see them. A string with {expr} parts becomes a run of tokens around the expression's own tokens. A > at the end of a line ends the statement when it closes a type, as in b: Box<i64>; after a comparison it does not.

Each name is interned into a Symbol, so the parser and checker compare and hash names as integers. After most errors the lexer skips the bad text and goes on, so it records every error. An unclosed or mismatched bracket is the exception: the run reports one diagnostic and stops. A literal that is not closed can eat the closers after it on its line, so after one, a closer also closes the brackets above its opener that were opened before the literal, and the run goes on.

Parser

crates/sisuc/src/parser.rs, ast.rs

The parser reads type parameters on a function, class or enum, <T>, and type arguments on a type or a call, Stack<i64> and first<i64>([]). In an expression, a < starts type arguments only when what follows reads as types and a ( or . comes after the >; otherwise it compares. The parser reports one error per broken item, then resumes at the next item. A broken item keeps its name, so a use of it is not reported as missing. It rejects an item that nests deeper than 256 levels, because every later stage walks the tree recursively.

Checker

crates/sisuc/src/check/, tir.rs, types.rs

The checker resolves names, types every expression and lowers shorthand: while and for become loops, ?. and ?? become if let, and x += 1 becomes x = x + 1. It folds each const to a literal. It checks a generic body once, at its definition, with each type parameter an opaque type, and infers a call's type arguments from its arguments and the type it should have. check/cycle.rs rejects a generic declaration that would need copies of itself without end. check/exhaust.rs runs Maranget's usefulness algorithm over each match: a missed value is an error that names it as a pattern, and an arm no value reaches is a warning. After a check with no error, check/unused_names.rs walks the recorded uses out from main and each _ name, and warns about each item, field, variant, local and parameter that no live code uses.

An expression that already failed gets a poison type, so one mistake produces one diagnostic. A program with no errors comes out as TIR, the typed tree, which MIR is built from. A type in TIR is a 4-byte handle into one table, and equal types get the same handle.

Mono

crates/sisuc/src/mono.rs

Monomorphization. Starting from the functions that are not generic, mono copies each generic function, class and enum once for each list of type arguments it reaches, and names the copy as a program writes it: first<i64>, Stack<string>.peek. Then it lays out the enums again, because a copy can close a cycle that needs a box. MIR and codegen see only concrete types. A program with no generic declaration passes through unchanged.

MIR

crates/sisuc/src/mir/

MIR sits between TIR and LLVM IR, as Rust's MIR and Swift's SIL do. Each function becomes a list of typed locals and basic blocks, and every retain, release and move is its own statement. Parameter inference (mir/params.rs, ADR 0029) then searches the whole program for the counted parameters that their functions only read, marks them borrowed, and rewrites each call to pass such an argument in place. The reuse pass (mir/reuse.rs, ADR 0030) then builds each box of a construction into the block that a match arm took apart when it held that box alone. The ownership pass (mir/ownership.rs) uses liveness to find every read of a counted local that is its last, and makes that read a move: the local hands over its reference instead of sharing it, so a later write to the array can skip the copy. A loop that writes an array nothing in it shares makes the array unique once, before the first iteration. Elaboration (mir/elaborate.rs) then removes each release at the end of a scope that no path reaches with the reference still owned, and makes one that every path reaches owned unconditional. In debug builds the compiler also checks each function: on every path, each owned reference is moved or released once. Pair removal (mir/pairs.rs) then turns a copy that is only borrowed within a block into a borrow, and its release into an end; a copy that is passed on, or whose release is in another block, stays. The debug check also rejects a borrow whose owner is written or released, or whose source a call or a counted write could change. MIR is built on the build path only, so sisu check does not pay for it. General optimization stays with LLVM.

Codegen

crates/sisuc/src/codegen/

Codegen walks MIR and builds an LLVM module through the inkwell bindings. Each Sisu function becomes an LLVM function named sisu.<name>. Codegen also emits a C main, which runs sisu.main. Integer overflow and division by zero call the runtime's panic instead of wrapping.

Codegen lays out every value in memory:

• An object lives on the heap, with a reference count in front of its fields.
• An array is one counted block: the count, the length, then the elements.
• A string is one counted block: the count, the length, the capacity, then the UTF-8 bytes.
• An enum value has no heap block of its own: it is a tag and its variant's payload, held inline. A field that would make an enum contain itself goes behind a counted box.

For each type it emits the helpers that retain, release and compare it. It tags loads and stores with type-based alias information, so LLVM knows that writing a field or an element leaves every count and length alone. MIR tests the arms of a match in order, and codegen/matching.rs traps after the last one. The checker has proved that some arm matches, and a bug in the checker must not become undefined behaviour.

LLVM

LLVM 23, linked as a library

A plain build runs only the mem2reg pass, which turns stack slots into registers. With -O2 or -O3 it runs LLVM's default<O2> or default<O3> pipeline. Then LLVM writes x86-64 object code for the machine sisu runs on.

Link

crates/sisuc/src/link.rs

Before it compiles, the driver checks that the runtime archive and the output's directory exist, so a missing one fails at once. --allocator picks the archive: libsisu_runtime_mimalloc.a by default, libsisu_runtime_system.a for --allocator system. The link step then writes the object code to a fresh temporary file and runs cc on it with that archive. cc adds the C startup code and libc and writes the executable, through its default linker or the one --linker names. The temporary file is removed whether or not the link succeeds.

Memory

Sisu manages memory by reference counting. Every heap object carries a count of the references to it. Generated code adds 1 when a reference is copied and subtracts 1 when one is dropped, and the object is freed when its count reaches 0. Swift works the same way.

There is no garbage collector and no borrow checker. Objects are freed at a known point. Every count change is ordinary LLVM IR, which --emit ir shows, and Valgrind can check that a run frees everything.

The costs are known too. Every copy of a reference costs an add and a later subtract. Counts are not atomic. A cycle of objects leaks; weak references, which break cycles, are planned.

Arrays are values

Binding an array, passing it or storing it behaves as a copy: no other holder can change your array. The copy is made only when it is needed. A write to an element first checks the count. At 1 it writes in place; above 1 it copies the block, then writes. A read, a binding, an argument and a loop over an array never copy.

A function cannot change its caller's array. A function that changes an array returns the new one, and the caller writes xs = f(xs).

What last use buys

When a local is read for the last time, its reference moves instead of being shared. So in xs = f(xs), when nothing else holds the array, f holds the only reference and its writes happen in place. This is a language rule, not an optimizer pass, and it never causes an error. The quicksort benchmark shows it: Sisu holds 83.8 MiB, against C's 77.6 MiB for its one array of 10 000 000 integers; the extra 6 MiB is mimalloc's own.

A loop goes one step further. When it writes a local array that nothing in the loop shares, the compiler makes the array unique once, before the first iteration. The writes inside the loop then skip the count check.

The runtime

sisu-runtime is a Rust library with a C ABI, which the two static archives sisu-runtime-mimalloc and sisu-runtime-system link; every program links one. Generated code calls it for many things, among them these three:

• Input and output. Sisu code reaches the operating system only through the runtime. Standard output goes through a buffer the runtime owns, and main flushes it before it returns. Text crosses the boundary as a pointer and a length. The runtime never builds or reads a Sisu object, so an object's layout lives in one place: codegen.
• Memory. sisu_alloc, sisu_realloc and sisu_free allocate and free objects, arrays and strings.
• Panics. A panic prints the file, line and column where it happened to standard error, and exits with code 101. A failed read or write has no location to print.

fn div(a: i64, b: i64) -> i64 {
    a / b
}

fn main() {
    print(div(7, 0))
}

sisu: panic at div_zero.sisu:2:5: division by zero

The runtime also counts the blocks that are allocated and not yet freed. A program built with --rc-checks checks each count before it changes, and fails at exit, with code 102, if any block is still allocated.

Diagnostics

The lexer, parser and checker report problems as diagnostics. Every diagnostic has a stable code: E0001 and up for errors, W0001 and up for warnings. A code is never reused or renumbered.

• One registry. diagnostic/registry.rs holds every message, label, help and fix. A stage names what happened and where, and writes no text, so the same code always has the same wording.
• An explanation per code. sisu explain E0001 prints what the code means, an example that triggers it, and the fix. The explanations live in docs/diagnostics/.
• No cascades. A broken item is reported once. Nothing that depends on it adds a second report.
• Fixes marked safe or unsafe. A safe fix always removes its diagnostic and leaves source that still lexes and parses, so a tool may apply it without asking. An unsafe fix is applied only when you pick it. Before it reports a fix for a lexer or parser diagnostic, the compiler applies it and drops it if the result lexes or parses worse; past the first 100 such fixes it drops the rest, since each check parses the source again. The fuzz target checks that no fix shown makes the syntax worse.
• JSON output. sisu check --format json writes each diagnostic as one JSON object per line, with the code, severity, spans and fixes, for editors, scripts and agents.

The diagnostics page shows them in use.

How it is tested

make test runs the unit tests and the end-to-end cases with cargo-nextest. CI runs them on every pull request and every push to main.

• Test programs. Each end-to-end case is a .sisu file with its expected output beside it, under crates/sisuc/tests. A program in run/ must pass in a plain and an -O2 build, both again under Valgrind, and in a --rc-checks build. A program in run-fail/ must panic with exit code 101. A case in diagnostics/ pins the text and the JSON of what sisu check reports.
• Explanations. A test compiles the broken and fixed example of every diagnostic code, and applies each safe fix to the broken one.
• Fuzzing. A cargo-fuzz target feeds arbitrary bytes to the front end and checks every span and fix edit. It also applies each safe fix alone and checks the result. An input that checks clean is printed as a typed tree and compiled, without and with --rc-checks, and LLVM must verify both modules. It runs every night for 30 minutes. A second target turns the bytes into a well-typed program, builds it at O0, at -O2 and with --rc-checks, and runs each build. The builds must agree and die by no signal, a build that exits normally must leak nothing, a rewritten copy must print the same, and integer answers the generator worked out must come out right. It also runs every night for 30 minutes.
• Miri. The runtime's unit tests run under Miri in CI, which stops at undefined behaviour.
• Coverage and mutation testing. make verify measures the coverage of a change with cargo-llvm-cov, then runs cargo-mutants on the changed code. It ends with verify: PASS only when no uncovered region touches the change and no mutant survives.
• Performance. CodSpeed counts instructions on the benchmarks and the compiler, on pushes to main and on pull requests that touch the code. See Benchmarks.

Further reading

• docArchitectureEvery stage in full, with the data between them.
• 0005Memory is managed by reference countingWhy counting, and what else was considered.
• 0007Arrays are values, shared until writtenCopy on write, and the last-use rule.
• 0009The runtime owns I/O; Sisu builds its own objectsWhere the line between generated code and the runtime sits.
• 0013Diagnostics have stable codesCodes, one registry, explanations and fixes.
• 0021A loop makes its written arrays unique before it startsMoving the count check out of the loop.