Compilation Pipeline

Overview

The compilation pipeline transforms source code through several stages, each adding information or lowering the representation toward execution. All backends share the same path through mcode and streamline.

Source → Tokenize → Parse → Fold → Mcode → Streamline → Machine

The final machine stage has two targets:

• Mach VM — a register-based bytecode interpreter that directly executes the mcode instruction set as compact 32-bit binary
• Native code — lowers mcode to QBE or LLVM intermediate language, then compiles to machine code for the target CPU architecture

Stages

Tokenize (tokenize.cm)

Splits source text into tokens. Handles string interpolation by re-tokenizing template literal contents. Produces a token array with position information (line, column).

Parse (parse.cm)

Converts tokens into an AST. Also performs semantic analysis:

• Scope records: For each scope (global, function), builds a record mapping variable names to their metadata: make (var/def/function/input), function_nr, nr_uses, closure flag, and level.
• Type tags: When the right-hand side of a def is a syntactically obvious type, stamps type_tag on the scope record entry. Derivable types: "integer", "number", "text", "array", "record", "function", "logical". For def variables, type tags are also inferred from usage patterns: push (x[] = v) implies array, property access (x.foo = v) implies record, integer key implies array, text key implies record.
• Type error detection: For def variables with known type tags, provably wrong operations are reported as compile errors: property access on arrays, push on non-arrays, text keys on arrays, integer keys on records. Only def variables are checked because var can be reassigned.
• Global and endowment resolution: Names used but not locally bound must be in the fixed global-name set or start with $ as an endowment. Accepted names are recorded in ast.intrinsics; all other unbound names are compile errors.
• Access kind: Subscript ([) nodes get access_kind: "index" for numeric subscripts, "field" for string subscripts, omitted otherwise.
• Tail position: Return statements where the expression is a call get tail: true.

Fold (fold.cm)

Operates on the AST. Performs constant folding and type analysis:

• Constant folding: Evaluates arithmetic on known constants at compile time (e.g., 5 + 10 becomes 15).
• Constant propagation: Tracks def bindings whose values are known constants.
• Type propagation: Extends type_tag through operations. When both operands of an arithmetic op have known types, the result type is known. Propagates type tags to reference sites.
• Intrinsic specialization: When an intrinsic call’s argument types are known, stamps a hint on the call node. For example, length(x) where x is a known array gets hint: "array_length". Type checks like is_array(known_array) are folded to true.
• Purity analysis: Expressions with no side effects are marked pure (literals, name references, arithmetic on pure operands, calls to pure intrinsics). The pure intrinsic set contains only is_* sensory functions — they are the only intrinsics guaranteed to never disrupt regardless of argument types. Other intrinsics like text, number, and length can disrupt on wrong argument types and are excluded.
• Dead code elimination: Removes unreachable branches when conditions are known constants. Removes unused var/def declarations with pure initializers. Removes standalone calls to pure intrinsics where the result is discarded.

Mcode (mcode.cm)

Lowers the AST to a JSON-based intermediate representation with explicit operations. Key design principle: every type check is an explicit instruction so downstream optimizers can see and eliminate them.

• Guarded load/store: Emits explicit guards around canonical load and store operations so Mach receives only valid array or record access.
• Decomposed calls: Function calls are split into frame (create call frame) + setarg (set arguments) + invoke (execute call).
• Intrinsic access: Intrinsic functions are loaded via access with an intrinsic marker rather than global lookup.
• Intrinsic inlining: Type-check intrinsics (is_array, is_text, is_number, is_integer, is_logical, is_null, is_function, is_record, is_stone) and length are emitted as direct opcodes instead of frame/setarg/invoke call sequences. Array append syntax (x[] = v) lowers to the push opcode.
• Disruption handler labels: When a function has a disruption handler, a label is emitted before the handler code. This allows the streamline optimizer’s unreachable code elimination to safely nop dead code after return without accidentally eliminating the handler.
• Tail call marking: When a return statement’s expression is a call and the function has no disruption handler, the final invoke is renamed to tail_invoke. This marks the call site for future tail call optimization. Functions with disruption handlers cannot use TCO because the handler frame must remain on the stack.

See Mcode IR for the instruction format and complete instruction reference.

Streamline (streamline.cm)

Optimizes the Mcode IR through a series of independent passes. Operates per-function:

1. Backward type inference: Infers parameter types from how they are used in typed operators (add, subtract, multiply, divide, modulo, eq, push, pop, etc.). Immutable def parameters keep their inferred type across label join points.
2. Write-type invariance: Determines which local slots have a consistent write type across all instructions. Slots written by child closures (via put) are excluded (forced to unknown).
3. Type-check elimination: When a slot’s type is known, eliminates is_<type> + conditional jump pairs around canonical operations.
4. Algebraic simplification: Rewrites identity operations (add 0, multiply 1, divide 1) and folds same-slot comparisons.
5. Boolean simplification: Fuses not + conditional jump into a single jump with inverted condition.
6. Move elimination: Removes self-moves (move a, a).
7. Unreachable elimination: Nops dead code after return until the next label.
8. Dead jump elimination: Removes jumps to the immediately following label.
9. Compile-time diagnostics (optional): When _warn is set on the mcode input, emits errors for provably wrong operations (storing named property on array, invoking null, etc.) and warnings for suspicious patterns (named property access on array/text). The engine aborts compilation if any error-severity diagnostics are emitted.

The optimizer’s passes, and the flags that disable them, are summarized in Build and Artifacts.

Machine

The streamlined mcode is lowered to a machine target for execution.

Mach VM (default)

The Mach VM is a register-based virtual machine that directly interprets the mcode instruction set as 32-bit binary bytecode. Since the mach bytecode is a direct encoding of the mcode, the Mcode IR reference serves as the authoritative instruction set documentation.

Producing a pool is two steps on opposite sides of the C floor: C lowers, Pit links. The single mcode-to-mach code generator lives in source/mach_pool.c and is the one authority on instruction encoding and object layout; per unit it emits target-final instruction words and values plus relocation rows naming constant operands, branches, pool-global shapes, and imports. The pool linker, in Pit, takes N of those to one pool: it interns finalized VALUES pool-wide, deduplicates stone objects by byte equality, widens relocated constant operands when necessary, rebases control flow and provenance, recomputes self-relative displacements, patches shape/import operands, and emits the origin map and cross-pool rows. Pit never learns an opcode and never constructs an object header. C keeps the interpreter, this lowering, the pool validator/mapper, and the fixed cold-boot header. The handoff between the two is pit.mach.fragment@1.

pit script.ce

Native Code (QBE / LLVM)

Lowers the streamlined mcode to QBE or LLVM intermediate language for compilation to native machine code. Each mcode function becomes a native function that calls into the ƿit runtime (pit_rt_* functions) for operations that require the runtime (allocation, intrinsic dispatch, etc.).

String constants are emitted once into a data section and referenced from there. Integer constants are encoded inline.

QBE is not part of the core VM or the fixed shop root. The development shop realizes pit-qbe/compiler on the first native build and sends optimized IR to that actor. Its closure owns the Pit emitter, representation templates, C backend, and vendored QBE sources. A Mach-only or shipped target that never requests native realization carries none of that compiler closure; desktop targets may still carry the much smaller qbe_helpers.c native-payload ABI.

pit --emit-qbe script.ce > output.ssa

Boot Artifacts

The boot path is intentionally smaller than the full compiler pipeline. A target runtime boots from a read-only linker section inside the binary. Its internal fixed header names the engine pool and boot entry; C obtains the section from a known start/end symbol pair, validates the named ranges, and enters the engine without opening a file. See Boot. Compiler, linker, fetch, policy, and package behavior are service actors the root starts, not firmware built into C.

boot/root.cart remains temporarily named for its historical format, but it is a git-visible forge input, not a runtime artifact. Forge injects its bytes through a generated .s/.incbin unit. The output artifact is only the binary; pit.bare, appendable boot tails, boot/boot.cart, and cement as a separate producer do not exist in this lane. External content is a bundle; boot.qop is the development bundle and is mounted after Pit is running.

The boot inputs regenerate byte-identically. On an ordinary build forge writes a candidate pair, boots it, runs the smoke subset, and has the clean candidate reproduce its own boot image. Only an exact byte match may promote. Before P5, an ABI move first uses a forge-internal candidate that accepts exactly the previous pool generation and presses with its own C lowerer; forge then rebuilds without acceptance and performs the same fixpoint gate. The portable mcode snapshot cannot cross alone because the engine that opens it is itself a pool.

boot.qop, boot/root.cart, and boot/engine_lite.mach are tracked inputs for the cold bootstrap and the fixpoint proof. boot/content is not.

Byte-identical is a real invariant, not an aspiration: nothing host-local may be embedded in these artifacts. In particular a source file’s debug filename — the name the compiler stamps onto every function and the runtime prints in stack traces — must be the stable locator (engine/engine_lite.cm), never the absolute path the seeding shop happened to slurp it from. Such a path is debug metadata — it is printed in stack traces and crash dumps, never opened — so it does not break boot, but it makes the artifact’s bytes differ in every checkout, which is exactly what reproducibility forbids. Regenerate them with:

make seed

Changing engine/engine_lite.cm, pit-shop/shop_actor.ce, or a program in the development content fleet requires regenerating the boot artifacts and restarting the local shop node. Cross-target builds use pit bootstrap --target <target> --out <directory> so they never replace the host boot tree.

Files

Debug Tools

Test Files