The p-code back end of chapter 8 is 450 lines and produces a machine that does not exist. This one is 560 lines and produces an executable.

It does not do that by generating assembly. It generates an intermediate language, and hands it to a backend that was written for a different compiler entirely.

What an intermediate language is for

A compiler that goes straight from a parse to instructions for one processor has to be rewritten for the next processor. A compiler that goes from a parse to an intermediate language, and from that language to instructions, splits the problem in two — and the second half can be shared by every language that emits the same intermediate form.

That is why GCC has GIMPLE and LLVM has LLVM IR, and it is why the compiler in this series can produce optimized ARM64 and x86-64 code without containing a single line of code about either.

The intermediate language here is called Spectra, and the backend that compiles it is called Dragon. Dragon is the backend of the Mica compiler: the same control-flow analysis, SSA middle-end, storage placement, register allocation and instruction emission that compile Mica itself. Nothing in it was written for PL/0.

What Spectra looks like

You have already seen it, in chapter 2:

@main:
    prologue @main, 0
    t1.1:int64 = copyLiteral 1:int64
    storeVariable t1.1:int64, v1.1:int64
    ...
@l1.3:
    t1.4:int64 = loadVariable v1.1:int64
    t1.5:int64 = copyLiteral 10:int64
    t1.6:bool = less t1.4:int64, t1.5:int64
    jumpNotEqual t1.6:bool, @l1.4

Compare it with the p-code for the same program and three differences stand out.

It is three-address code. t1.6 = less t1.4, t1.5 names its two operands and its result. P-code’s opr 0 10 names nothing — the operands are wherever the stack top happens to be. Naming them is what lets an optimizer reason about them: it can see that t1.4 is the same value as some earlier temporary, or that t1.5 is a constant, and act on it.

There is no stack. Not a real one and not an implied one. The values live in temporaries, and where those temporaries actually end up — a register, a stack slot — is decided later, by the register allocator.

Control flow uses labels. @l1.3 is a name, not an index into an array. Positions changed under Wirth’s backpatch; names do not, so an optimizer may reorder and duplicate code freely.

Everything else you might expect is deliberately absent. Spectra has no types beyond machine types, no expressions, no nesting — every instruction is one operation on named operands. That flatness is what makes analysis tractable.

The compile-time stack

The seam speaks a stack discipline (chapter 7). Spectra wants three-address code. Bridging the two is one of the most reusable tricks in the compiler:

static void spectra_arithmetic(Backend* seam, ArithmeticOperation operation) {
    SpectraBackend* backend = (SpectraBackend*)seam;

    /* the RIGHT operand pops first because it was pushed last — the parser evaluates left before
     * right, so the stack holds them in reverse; getting this backwards flips every subtraction */
    drg_addr right = spectra_pop(backend);
    drg_addr left = spectra_pop(backend);

    /* one three-address instruction replaces Wirth's operate-on-the-stack-top: the operands are named,
     * the result is a fresh temporary, and the machine stack has disappeared entirely */
    char temp[MAX_NAME];
    spectra_mint(backend, backend->current, prefix_temporary, temp);
    drg_addr result = spectra_temporary(backend, ..., backend->type_i64, temp);
    ...

The stack exists, and it exists only inside the compiler. load_constant pushes an operand name; arithmetic pops two names and emits one instruction naming them; the result name is pushed. When the parse ends the stack is empty and no stack operation has been emitted at all.

Note the comment about pop order. The right operand pops first because it was pushed last. Get that backwards and every subtraction and every comparison silently reverses — a bug that passes any test using only addition and multiplication. It is worth writing the comment.

Problem 1: a variable is a depth and an offset

PL/0 hands the back end (level_difference, address). Wirth’s machine walks static links at run time. What does a production backend do?

It turns out Spectra has this concept natively, because Mica has nested procedures too:

static drg_addr spectra_variable_address(SpectraBackend* backend, int level_difference, int offset) {
    int declaring = backend->current;

    for (int step = 0; step < level_difference; step++) {
        declaring = backend->procedures[declaring].parent;
    }

    char name[MAX_NAME];
    snprintf(name, sizeof name, "v%d.%d", backend->procedures[declaring].block, offset + 1);

    drg_addr address;
    spectra_check(backend, spectra_addr_variable(backend->ctx, backend->type_i64, name,
                                                 level_difference, DRG_MODIFIER_VALUE, &address), name);
    return address;
}

The walk at compile time finds which block declares the variable, so the name is right. The level_difference then rides on the address itself, and Dragon’s storage placement resolves it — emitting the frame-pointer chain walk, or something better, as it sees fit.

The hardest thing about PL/0 turned out to be free, because the backend was built for a language with the same feature. That is the argument for reusing a backend rather than writing one, stated as concretely as this series can state it.

Problem 2: nested procedures come out in the wrong order

This one is not free, and it is the most interesting engineering in the file.

PL/0 compiles a procedure’s nested procedures before its own body — the grammar says so:

block = [const…] [var…] { procedure ident ";" block ";" } statement .

Spectra wants each function as one contiguous label-delimited region, entry point first. So the order the parse produces is not the order the target wants.

Wirth had the same problem on his machine, and solved it with the entry jump you saw at line 0 of the listing: jmp 0 8 hops over the nested code into the main body. That works when code is an array of instructions and a jump is free.

A label-delimited representation solves it by ordering instead:

static void spectra_splice(SpectraBackend* backend) {
    for (int index = 0; index < backend->procedure_count; index++) {
        const SpectraProcedure* procedure = &backend->procedures[index];

        for (int at = procedure->body_start; at < procedure->body_end; at++) {
            ...

Instructions are not sent through the surface as they are conceived. Each one is recorded — its operand handles are owned by the session and stay valid indefinitely — and when the outermost procedure ends, the records replay procedure by procedure, the program block first.

typedef struct {
    const char* operation;       /* a 'DRG_OP_*' name — the engine's one public vocabulary  */
    drg_addr arg1;
    drg_addr arg2;
    drg_addr result;
    bool guarded;                /* whether the guarded builder mints safety labels         */
    int32_t block;
    char define_label[MAX_NAME];
} EmittedInstruction;

Two things make this cheap. The operand handles are minted eagerly and remain valid, so a record is nothing but the builder call it stands for. And symbols, address-table registrations and argument bundles go through the surface immediately rather than being recorded, because those tables are keyed by block and carry no ordering.

When a producer’s natural order does not match a consumer’s required order, buffer and replay. It is a small pattern and it appears constantly once you have a name for it.

Where the printing comes from

PL/0 prints every store. Wirth’s interpreter does it with one fprintf. A native program has no interpreter to do it, so the compiler must emit the call:

static void spectra_print_stored(SpectraBackend* backend, int level_difference, int offset) {
    spectra_write_line_signature(backend);
    ...

The store is followed by a call to pl0_write_line — this compiler’s own formatted line writer, a one-function standard library shipped as pl0-stdlib.c beside the seven units. The unit only names that external symbol; whichever archive or object the link supplies must resolve it.

That is why step 5 of chapter 2 links against the Dragon runtime archive, and it is the general shape of the arrangement: the compiler emits calls to a floor it does not contain, and the standard library above that floor is each language’s own. Keeping the library pluggable per frontend is what lets one backend serve languages with very different libraries.

Validate, then build

The single most useful thing the surface does is refuse work:

validate: 0 findings
build: ok

Validation runs before emission. A frontend that hands the engine a malformed unit — an instruction whose operands have incompatible types, a branch to a label that is never placed, arithmetic without the runtime-safety labels the contract demands — gets a sentence naming the instruction and the rule it broke.

You can see it work. The twins carry a deliberate contract probe:

../build/c/pl0 build broken ../testdata/square.pl0 -trap

The -trap flag sends the first arithmetic through the raw instruction door without the safety labels the contract requires — the mistake every foreign frontend makes first — and the expected outcome is that validation names the finding rather than the backend crashing somewhere later.

This matters more than it sounds. A backend that trusts its input crashes deep inside register allocation with a stack trace through code the frontend author has never seen. A backend that validates is a backend a stranger can write a frontend for, and that difference is most of what makes an engine publishable at all.

The session, in ten lines

Stripped of error handling, driving the engine is this:

dragon_context_new(&ctx);                          /* a session          */
spectra_registry_new(ctx, HOST_PLATFORM, &reg);    /* the type registry  */
spectra_type_builtin(ctx, reg, "int64", &i64);     /* the types you need */
spectra_unit_new(ctx, &unit);                      /* the unit           */

/* … append symbols, addresses and instructions … */

dragon_validate(ctx, unit, reg, &findings);        /* refuse bad input   */
dragon_build(ctx, unit, reg, HOST_PLATFORM, level, DRG_SYNTAX_INTEL, "square", "square.s");
dragon_runtime(ctx, HOST_PLATFORM, DRG_SYNTAX_INTEL, "pl0", "square.rt.s");
dragon_context_free(ctx);

Nine calls. Everything else in spectra.c is PL/0-specific bookkeeping — the compile-time stack, the record buffer, the name minting.

From Mica the same nine, reached by import rather than by header:

imp
    ContextNew, ContextFree, RegistryNew : dragon;
    TypeBuiltin, UnitNew, Validate, Build, Runtime : dragon;

What you actually got

When dragon_build returns, the assembly on disk has been through:

  • validation against the intermediate language’s contract
  • control-flow analysis — basic blocks, the flow graph, dominance
  • an SSA middle-end — value numbering, constant propagation, dead-code elimination
  • storage placement — which values live in frames, which in registers
  • register allocation
  • instruction selection and emission for your architecture
  • peephole optimization

None of it written for PL/0. The 560 lines in spectra.c bought all of it.

That is the honest summary of what an intermediate language is for, and it is why the last fifty years of compiler engineering have converged on this shape.

Next: 10 — Proving it, where the two back ends are made to check each other.