Chapter 5 — The Backend

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

If Chapter 4 was the part a compiler textbook covers in its first half, this is the part most textbooks wave away — and the part 5.0.0 built out in full. In 4.5 the backend was a direct IL-to-assembly emitter with a peephole pass. In 5.0.0 it is a proper optimizing backend: inlining, a control-flow graph, SSA construction, dataflow and liveness analysis, graph-colouring register allocation, two mirrored architecture lowerings, and a per-architecture peephole optimizer over a shared engine. This is what closes most of the gap to gcc -O2 (Chapter 7).

The single largest subsystem in the compiler now lives here: the backend lowering alone is over 27,000 lines, because supporting two architectures honestly is most of the work.

The flow:

Spectra IL → inlining → CFG → SSA + dataflow → placement → backend lowering → peephole → ELF/DWARF

◈ Inlining

A pure IL → IL transformation that substitutes the bodies of small callees into their call sites. It runs first, before the CFG and SSA are built, so the SSA cleanup passes downstream tidy the substituted bodies for free. Inlining candidates are bounded by a body budget (on the order of a couple hundred IL instructions) so the pass cannot explode code size. Because it works on the intermediate code alone, it is simple to reason about and audit — and it was audited against the heap intrinsics to confirm it never moves an allocation across an owner boundary.

◈ The control-flow graph

Optimization needs structure the flat IL doesn’t expose. The compiler builds basic blocks (maximal straight-line runs with a single entry and single exit, found by the standard leader algorithm) and the edges between them, resolving branch-target labels into real successor links. These blocks and edges are the structure the dataflow pass below turns into liveness and reaching-definitions facts.

◈ SSA — static single assignment

SSA is the form in which every value is assigned exactly once, so each name is a value — the representation that makes modern optimizations clean. Mica builds SSA as a separate IL unit rather than rewriting the code-generation unit in place, which keeps the canonical IL stable and the SSA form disposable. Construction follows Cytron et al.: build the dominator tree (by the Cooper–Harvey–Kennedy algorithm) and its dominance frontiers, place φ-functions pruned — only at the iterated dominance frontier where they are actually needed — and rename every value over the dominator tree so each name is assigned exactly once.

Over that form runs a real optimization suite — dominance, constant propagation, copy/value forwarding, value-range analysis, loop rotation, interference checking, the out-of-SSA translation, and a verifier that checks the form’s invariants after every pass. This is also the machinery the obligation analysis borrows its thinking from: lifetimes are scheduled with the same dominance-and-liveness reasoning registers are.

◈ Dataflow and liveness

The textbook monotone-dataflow passes, in Dragon-Book vocabulary: liveness (a backward may-analysis — which values are still needed at each point) and reaching definitions (a forward may-analysis), each driven by a worklist to a Kleene fixed point. Liveness is the fact the register allocator cannot live without: it turns “this value is used here” into live ranges [start, end) that placement can pack.

◈ Placement — register allocation and frame layout

Placement decides where every parameter, local, temporary, and debug location lives — a register or a stack slot — and lays out the activation record. The default release allocator is a whole-function linear scan with loop-weighted spill costs over the live ranges liveness produced; an optional Chaitin–Briggs graph-colouring allocator (with Briggs conservative coalescing) can be layered on top. In debug builds everything stays on the stack — predictable and inspectable — and register homing is a release-mode optimization over that foundation. Whichever strategy runs, an always-on verifier checks that no two interfering values are ever given the same register.

A dedicated layer classifies aggregate parameters and returns — structs, arrays, sets — into registers versus caller-owned memory, for both AAPCS64 and x86-64 System V. This is the single source of ABI truth the call emitter and the DWARF generator also read, so a struct is passed, returned, and described to the debugger the same way the ABI specifies.

◈ The dual backend — two architectures, mirrored

Here lowered IL plus placement decisions become native instructions — for two architectures that are first-class peers, not a primary plus an afterthought.

• A single seam — one interface — exposes placement, symbol, and type services to each lowering backend.
• One lowering backend realizes that seam for x86-64 / System V AMD64, another for ARM64 / AAPCS64. The two are mirrored shape-for-shape — the same functions in the same order — and every divergence is a named ISA constraint, not an accident: a structure copy is rep movs on x86-64 versus an explicit ldr/str loop on AArch64; a 64-bit immediate is one mov on x86-64 versus a movz/movk sequence on AArch64.
• A backend-neutral layer resolves scalar storage types and validates the structured address projections coming from the IL.

Below them sit the assembly models — one per architecture — that model each instruction set, its registers, and its addressing. The x86-64 model prints both Intel and AT&T syntax from one internal representation. The emitter uses all 16 general-purpose and 16 vector registers on each target, following the target’s calling convention exactly.

When --optimize checked is active, this layer is where overflow detection is woven in: an overflow check after each signed arithmetic op — a jno guard that falls through to a runtime failure handler (printing source file, line, and operation) when overflow occurs. It is compiler-generated code at every arithmetic site, not a library flag.

◈ The peephole optimizer

After lowering, a peephole pass cleans up local inefficiencies without changing semantics. A shared dispatch engine — opcode-keyed pattern lookup, driven by a block worklist — runs per-architecture pattern sets: arithmetic, boolean, and compare temp folding; compare-and-branch fusion; constant-immediate fusion; division strength reduction; call-argument and return-value forwarding; floating-point contraction; and more. Each pattern is local, provably safe, and independently tested, and the pass tracks statistics (instructions before/after, count of each pattern matched) so every improvement is measurable.

◈ ELF and DWARF v5

ELF output

Standard ELF binaries with correct section layout (.text, .data, .rodata, .bss), produced as executables, static archives (.a), or shared objects (.so).

DWARF v5 — architecture-agnostic, shared by both backends

Most hobby compilers stop at binary output. Mica generates full DWARF v5 — the current standard — and does it in a single architecture-agnostic stage both backends share, so a debugger sees the same Mica program whether it was built for x86-64 or ARM64.

• A language in the registry. Each unit’s root entry carries DW_LANG_Mica, registered in the DWARF user range. GDB reports the source language as Mica — not C, not Pascal — because the compiler emits its own identity.

• Type fidelity. The generator walks the full Mica type graph and emits a dedicated entry per type kind:

  Mica type	DWARF tag
  Integer / Float / Boolean / Char	DW_TAG_base_type (signed, float, boolean, UTF encodings)
  Pointer	DW_TAG_pointer_type
  Record	DW_TAG_structure_type + DW_TAG_member
  Array	DW_TAG_array_type + DW_TAG_subrange_type (with DW_AT_lower_bound/DW_AT_upper_bound)
  Set	DW_TAG_set_type
  Enum	DW_TAG_enumeration_type + DW_TAG_enumerator
  Subrange	DW_TAG_subrange_type with closed bounds

  An array declared array[1900..2100] appears in GDB with exactly those bounds — not zero-based — and an enum prints Red, not 0.

• Location expressions. Because every activation-record offset is fixed at compile time (the expression stack, Chapter 4), every variable’s DW_AT_location is a compile-time constant DW_OP_fbreg offset. No location lists, no live-range splits — the DWARF is as simple and correct as the rest of the compiler.

The payoff: load a Mica binary in GDB, set a breakpoint by source line, step through statements, inspect variables by their Mica names, and step into nested functions watching the static-link chain resolve — on either architecture. Everything works because the DWARF describes what the compiler actually generated.

Where to next

The machine is fully assembled — source to native binary on two architectures. Now the question every systems programmer asks: how does a binary reach the outside world? The answer is Mica’s whole platform bet.

→ Chapter 6 — Platform & Interop · back to the reading guide