Chapter 4 — The Pipeline

Mica 5.0.0 Technical Portrait · Chapter 4 of 9 · reading guide

Mica implements a textbook-clean compilation pipeline with explicit phase boundaries. Every intermediate representation can be inspected, exported, and reasoned about independently — which is what makes the compiler a teaching instrument as much as a tool.

┌───────────────┐
│  Source Code  │   UTF-8 encoded .mica files
└───────┬───────┘
        ▼   Scanner            lexical analysis → token stream
        ▼   Parser             recursive descent → abstract syntax tree
        ▼   Analyzer           semantic passes + obligation analysis → validated AST
        ▼   Generator          AST traversal → Spectra IL (three-address code)
        ▼   Inliner            IL → IL: substitute small callees                  ┐
        ▼   CFG                basic blocks + edges                                │
        ▼   SSA + Dataflow     φ placement, dominance; liveness, reaching-defs     │  Chapter 5
        ▼   Placement          register/stack homes (graph-colouring allocation)   │
        ▼   Backend lowering   per target: x86_64 (System V) · ARM64 (AAPCS64)     │
        ▼   Peephole optimizer per-arch patterns over a shared dispatcher          │
        ▼   ELF / DWARF v5     binary encoding + debug information                 ┘
        ▼
┌───────────────┐
│  GNU Binutils │   as + ld → executable, static archive, or shared object
└───────────────┘

This chapter walks the front and middle end — source text down to Spectra IL. The backend half (everything in the braced block) is Chapter 5.

◈ Phase 1 — The Scanner

The scanner converts UTF-8 source bytes into a stream of tokens, fully Unicode-aware and position-tracked.

• Token categories: integer / floating-point / string / unicode-character literals; the operator set (+ - * / = # < <= > >=); structural symbols (( ) [ ] , : ; . .. :=); and over 45 reserved words — now including the heap keywords new, dispose, defer, until, and nil.
• Numeric literals: decimal, hexadecimal (0x), and binary (0b), with optional digit separators; floating-point with scientific notation.
• Comments: { block } and // line forms.
• Position tracking: every token carries its source line and column, and that coordinate propagates through the entire pipeline into DWARF — so error messages, runtime failures, and debugger breakpoints all point to exact source.

◈ Phase 2 — The Parser

A classic recursive-descent parser producing the AST. It handles the full grammar: declarations, type expressions, every statement form, and expressions with correct precedence.

Every source file is a program (executable) or library (reusable module), followed by declaration sections in order:

program/library → imp → const → type → var → procedures/functions → begin...end.

Note that the pointer operators value and address bind tightest, while not and odd sit with the comparison operators — and the as conversion has its own level between arithmetic and comparison.

Type expressions cover records (and packed record), single- and multi-dimensional arrays with custom bounds, set of, subranges, enums, pointer T, and file of T. Functions and procedures nest up to 16 levels deep, and the parser propagates that depth through the tree for static-link generation. Token-level synchronization lets one compilation report many diagnostics instead of stopping at the first.

◈ Phase 3 — The Abstract Syntax Tree

The AST is the compiler’s central data structure — every syntactic construct as a typed node, and the shared currency between parsing, analysis, code generation, and export. It is the largest component of the front end.

• Node taxonomy across five families: declarations (import, constant, parameter, variable, signature, function, data type, record field); expressions (arithmetic, comparison, logical, memory address/dereference, conversion, selection); type expressions (record, array, set, subrange, enum, file, set constructor); statements (assignment, call, leave, if, while, for, repeat, case, compound — and the heap statements); and uses (identifier, literal).
• The visitor pattern with double dispatch separates the structure of the tree from the operations on it (analysis, generation, export). Pre-, in-, post-, and level-order traversals are all supported.
• A global registry coordinates declarations across compilation units for multi-file builds, and validates imports through type fingerprinting — a deterministic digest of a type’s structure that catches ABI mismatches before linking.
• Symbol annotations enrich each declaration through the pipeline: an internal IL name, an external export symbol, a compile-time constant value, the parameter passing mode at the ABI level, and the nesting depth used for static links.

◈ Phase 4 — The Type System

The backbone of Mica’s static guarantees: it describes every data type, tracks its properties, and decides what operations are legal.

Rather than a hard-coded switch, types advertise what they can do through a capability bit-mask — Numeric, Ordered, Equality, Logical, Integral, Fractional, Dereferenceable, Addressable, Convertible, Callable, Selectable, Indexable, Ordinal. “Is this type valid as a for control variable?” becomes a single capability query, not a sprawling type switch.

The type system is ABI-aware from the ground up. Every type knows its size, its alignment, how it is passed (integer register, SSE/vector register, or hidden pointer), how it is returned, and its classification under each target ABI. This one classification is consumed by the call emitter, the register allocator, and the DWARF generator — so function signatures tell the truth, adding a field never silently changes how a record is passed, and an array never decays to a pointer.

New in 5.0.0, the type system also tracks incompleteness: a record may refer to its own type (pointer Node inside Node), the change that makes linked lists and trees expressible, and a dedicated sentinel gives the nil literal a concrete pointer type at each use site.

◈ Phase 5 — Semantic Analysis

The analyzer proves a syntactically correct program is also semantically correct — names resolve, types match, constants fold, and every statement obeys its rules. It runs as eight coordinated passes:

1  StaticShallow        register top-level declarations (order-independent)
2  StaticImportAttach    resolve imports across compilation units
3  StaticResolveDeferred resolve forward references (mutually recursive types)
4  StaticDeep            the main validation pass — 100+ distinct error codes
5  Lowering              normalize expression forms for the generator
6  TypeCoercion          insert explicit conversion nodes where widening is legal
7  ConstantFolding       evaluate compile-time constants (5 + 7*2 → 19)
8  StaticWarn            report unused variables, parameters, imports

Pass 4 does the heavy lifting: it resolves every identifier, checks every operation against operand types, validates call arity and argument types, array index types, set membership, for-loop control rules, case label validity, and until conditions. Pass 7 leans on a dedicated compile-time evaluator — a full arithmetic, comparison, logical, and cast engine that even detects division by zero, infinity, and NaN in constant expressions.

Two analyses join the front end in 5.0.0:

• The obligation analysis — the heap-safety proof from Chapter 3. It runs over the IL and control-flow graph in every compilation mode, classifying each allocation site.
• Quality gates — internal consistency checks that verify the compiler’s own transformations are correct. These are compiler self-tests, not user-facing guards: a serious second opinion the compiler holds against itself.

◈ Phase 6 — Spectra: the intermediate language

Between the high-level AST and the low-level machine code sits Spectra — Mica’s three-address-code intermediate language. Spectra is where the program stops being a tree and becomes a flat sequence of operations that map almost directly to instructions.

    v1.1:int32 = literal 0:int32        { i := 0 }
    store v1.1:int32, i
    m1.2:int32 = literal 3:int32        { final bound, evaluated once }
    store m1.2:int32, _final
.loop_test:
    m1.3:int32 = load i
    m1.4:int32 = load _final
    jumpGreater m1.3:int32, m1.4:int32, .loop_exit
    ...
    jump .loop_test
.loop_exit:

Every value has a name (m1.3), a type annotation (:int32), and a clear origin (m = temporary, v = variable, p = parameter). The instruction set spans arithmetic, comparison, logical, conversion, memory (literal/load/store), structured access (loadField/storeField, loadElement/storeElement), set operations, control flow, and the function-call group — plus, in 5.0.0, the allocator intrinsics (allocate, deallocate, register, allocate in owner region, …) that the heap lowers to. The IL never names malloc.

Two architectural ideas make Spectra distinctive:

• Identity is separate from storage. An address name like m2.3 is a lookup key into the symbol table, not a memory location. Which register or stack slot it lands in is decided later, by the backend.
• Storage is decided later, not here. When the generator walks a + b * c, each temporary gets a name, not a location. Where it ultimately lives is the backend’s decision (Chapter 5): a release build allocates values to CPU registers and spills to stack slots only when registers run out; a debug build keeps every value in a stable stack slot so the debugger can read it at any point. Either way the stack pointer moves at most once per call, in the prologue — there are no runtime push/pop sequences for expression evaluation. The complexity lives in the compiler; the output stays simple and debugger-friendly.

Where to next

The program is now a clean, flat IL. Next comes the part that is new in 5.0.0 and that does the heavy lifting for speed: the SSA-based optimizing backend, register allocation, and code generation for two architectures.

→ Chapter 5 — The Backend · back to the reading guide