AtlasLangsimplified

AtlasLang: The Whole Thing

From `print(1 + 2);` to a typed language with a bytecode VM, an SSA optimizer and a register allocator — twelve representations, all of them produced by a compiler in this repository that you can type into.

The question

What does it actually take to build a working language, end to end?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

Twelve representations in sequence — characters, tokens, an AST, a typed AST, three-address IR, a control-flow graph, SSA, optimized SSA, stack bytecode, live ranges with a register assignment, x86-64-flavoured assembly, and a running VM state. They are twelve views of one program, each existing because the previous one could not answer the next question, and each of them is a real data structure this compiler builds rather than a picture of one.

What this phase may assume or do

Every handover must preserve what the program is defined to observe, which in AtlasLang means exactly two things: the sequence of values print emits, and whether execution faults on a division by zero. Everything else — evaluation order within an expression, which values live in registers, whether a block exists at all, how many instructions implement an addition — is the compiler's to choose. That definition is deliberately tiny, and it is why the optimizer can be aggressive: with a small observable surface, most transformations are trivially behavior-preserving, and the two that are not are exactly the two the optimizer guards.

Key points

  • AtlasLang is a complete implementation — lexer, Pratt parser, checker, SSA, optimizer, register allocator, backend and VM — and every panel in the UI is its real output.
  • The observable behavior of an AtlasLang program is exactly two things: what print emits, and whether it faults on division by zero. Every legality argument in this module reduces to those.
  • Twelve representations, of which two — the CFG and the typed AST — lose nothing, because one is a view and the other annotates in place.
  • The loses column is the record of what a debugger would have to reconstruct, and it is why source correspondence is a deliberate, paid-for property rather than a free one.
  • The two guards that make the optimizer an optimizer rather than a bug are hasEffect and mayTrap, and there is an example program for each.
  • The default program is small on purpose and still exercises calls, precedence, a merge, a back edge and register pressure.

Start with one line

simplifiedAtlasLang has three types, no floats, no heap, no user-defined types and no imports. Those absences are what make the whole pipeline readable in an afternoon, and each one removes a genuinely hard problem: no floats means no rounding-mode or negative-zero hazards in the folder, no heap means no escape analysis and no garbage collector to emit metadata for, no imports means the whole program is always visible. A real compiler faces all three.

Open /compilers/atlaslang and replace everything in the source panel with print(1 + 2);. That is a complete AtlasLang program: the language has an implicit main built from the top-level statements, so there is no ceremony to get through before something runs.

The execution panel prints 3. What is worth looking at is the two IR listings beside it. The unoptimized IR is three instructions — compute 1 + 2 into a virtual register, print that register, return. The optimized listing is two: print 3 and ret. The addition is gone, evaluated at compile time by [[constant-folding]], and the register it produced was deleted by [[dead-code-elimination]] once nothing read it.

That two-line diff is the entire domain in miniature. A representation was built (IR), a fact was established (both operands are literals and the operation cannot fault), a transformation was applied under a precondition, and a later pass noticed that something had become unobservable. Everything else in this module is that same loop with more machinery.

What print(1 + 2); compiles to, before and after the optimizer
IR
fn main(): void {
b0: ; entry
  %0 = int 1 + 2
  print %0
  ret
}
Optimized SSA
▸fn main(): void {
▸b0: ; entry
▸  print 3
▸  ret
▸}

Read it asThe print survived and the addition did not. That asymmetry is not a size heuristic — it is the hasEffect predicate in src/compilers/sim/optimize.ts, which reports that a print is observable and an arithmetic instruction is not. Change the program to let unused = 1 + 1; print(42); and watch the entire first line vanish while print(42) stays.

Twelve stages, and what each one is for

The pipeline explorer at /compilers/pipeline shows every stage at once for whatever you type. The list below is STAGES from src/compilers/sim/index.ts — the same array the UI renders from, so the descriptions are the implementation's own account of itself rather than a summary written afterwards.

Read the loses column downward. That is the record of what each stage throws away, and it is the reason a debugger has to work so hard: by the assembly stage the names are gone, the block structure is gone, and the correspondence between a line you wrote and an instruction that runs is a relation the compiler had to deliberately keep.

The AtlasLang pipeline, from STAGES in src/compilers/sim/index.tsimplementation
  1. Sourceyou write it
    A sequence of characters.
    Nothing yet — this is the input.
  2. Tokensbuild time
    A flat list of classified lexemes, each with a source range.
    Which characters belong together, and what kind of thing each group is.
    Whitespace and comments, unless kept deliberately as trivia.
  3. ASTbuild time
    A tree of semantically meaningful nodes.
    What is applied to what — grouping, precedence and nesting.
    Parentheses and the exact token sequence.
  4. Typed ASTbuild time
    The same tree with a resolved symbol and a type on every node.
    Whether the names exist and whether the program means anything.
    Nothing — this stage annotates rather than restructures.
  5. IRbuild time
    Three-address instructions over virtual registers, in basic blocks.
    In what order things happen, and which value flows where.
    Expression nesting. The tree is now a linear sequence.
  6. CFGbuild time
    The same instructions, viewed as a graph of blocks and edges.
    Which paths exist through the function, and what dominates what.
    Nothing — the CFG is a view of the IR, not a replacement.
  7. SSAbuild time
    IR where every value is defined exactly once, with phi nodes at merges.
    For any use, which single definition produced it.
    The named variables. x is now several distinct values.
  8. Optimized IRbuild time
    SSA after the enabled passes have run to a fixed point.
    What the program does, with everything unobservable removed.
    Correspondence with the source. Lines vanish and merge.
  9. Bytecodebuild time
    A linear stack-machine instruction sequence with local slots.
    What an interpreter would execute, step by step.
    The block structure. Control flow is now numeric jump targets.
  10. Registersbuild time
    Live ranges and an assignment of values to a finite register set.
    Where every live value physically lives, and what had to spill.
    The illusion of unlimited names.
  11. Assemblybuild time
    Target instructions with physical registers and stack slots.
    Exactly which machine operations implement the program.
    Portability, and the source-level names.
  12. Executionrun time
    A running program: an instruction pointer, an operand stack and frames.
    What the program actually does.
    Everything static. Only the trace remains.

Read it asTwo of these are not translations at all. The CFG loses nothing because it is a *view* of the IR — the same instructions, read as a graph. The typed AST loses nothing because it annotates in place rather than restructuring. Every other row is a genuine handover with something discarded, and knowing which is which tells you where a piece of information can still be recovered and where it cannot.

The default program, and why it is that program

The source panel starts with a program chosen so that no panel is empty. It defines a function, so there is a call graph and a second focusable function. It has 1 + 2 * 3, so precedence is visible in the AST. It has an if inside a while, so there is a merge that forces phi nodes and a back edge that forms a natural loop.

Compiled today, that program produces three phi nodes, reaches a fixed point after three passes of the optimizer over nineteen instructions, needs four physical registers at its peak, and prints 22. You do not have to take those numbers on trust — they are on the screen, and if you edit the program they change.

The instructive experiment is to reduce the register count on /compilers/registers until something spills, or to switch to the pressure example, which computes nine values from a parameter specifically so that nothing folds away and the allocator has a real problem. That is where the illusion of unlimited names ends.

`DEFAULT_SOURCE` from `src/compilers/sim/index.ts`
1fn add(a: int, b: int): int {
2  return a + b;
3}
4 
5let x = 1 + 2 * 3;
6let n = 0;
7while (n < 3) {
8  if (n == 1) { x = x + 10; } else { x = x + 1; }
9  n = n + 1;
10}
11print(add(x, n));

Every element earns its place. The function gives the call graph a second node; 1 + 2 * 3 makes precedence visible; the if inside the while produces both a merge and a back edge, which is the minimum needed for phi nodes and a natural loop to exist at all. Programs this small are the ones worth reading in full.

Ten worked examples, each isolating one phenomenon

The example selector holds ten programs from EXAMPLES, each chosen to make exactly one thing visible. Four of them are worth knowing about before you start experimenting, because they demonstrate the things people most often assume compilers get wrong.

trap is let a = 10; let b = 0; print(a / b);. The optimizer propagates both constants, produces %2 = int 10 / 0, and then refuses to fold it. Run it and the VM reports a division-by-zero fault. That refusal is mayTrap in the optimizer: folding a faulting operation would move a runtime fault to build time, which changes the program's observable behavior even though it was going to fault anyway.

effect is let unused = 1 + 1; print(42);. The dead binding disappears entirely and print(42) remains, because hasEffect reports that printing is observable regardless of whether anything reads its result.

shortcircuit is if (a != 0 && 10 / a > 1) with a zero. It prints 0 rather than faulting, because && is lowered to control flow rather than to an arithmetic instruction, so the right operand is genuinely not evaluated. Getting that wrong is a real compiler bug with a real symptom.

errors puts a lexer error, a parse error and a type error in one file and recovers between them, which is the best short demonstration in the whole build that a compiler stopping at the first error is a worse tool than one that does not.

  • one-line — the smallest program that still touches every stage.
  • precedence — why 1 + 2 * 3 is 7 and not 9, visible in the AST and not in the tokens.
  • folding — arithmetic on literals evaluated at build time, and the dead store that follows.
  • phi — a branch that assigns on both paths, forcing a phi at the merge.
  • loop — a back edge, a loop-carried phi, and values live across a whole body.
  • pressure — nine values live at once, computed from a parameter so nothing folds. Lower the register count and watch a spill.
  • trap — a fold the optimizer refuses, because the operation can fault.
  • effect — a deletion the optimizer refuses, because printing is observable.
  • shortcircuit — && as control flow, which is why the right operand can be skipped.
  • errors — three errors from three different stages in one file, with recovery between them.

How it works

The steps, in the order the compiler takes them.

  • compile(source) in src/compilers/sim/index.ts runs every stage in one call and returns all of them, because the point of the flagship UI is seeing them side by side.
  • Lexing produces tokens with half-open byte ranges; parsing produces an AST whose nodes carry the spans of the tokens they came from.
  • Checking annotates the tree in place with a resolved symbol and a type on every node, and reports diagnostics without throwing.
  • Lowering flattens the tree into three-address instructions in basic blocks, with local variables as named slots.
  • Dominance is computed by iterative data flow, and SSA construction places phi nodes at the iterated dominance frontier before renaming.
  • The optimizer runs the enabled passes to a fixed point, recording every pass that changed anything for the pass-manager UI.
  • Bytecode is emitted from the pre-SSA IR, because a phi node has no execution semantics, and the VM runs it under a step budget.
  • Out-of-SSA inserts copies, the allocator colours the interference graph, and the backend emits assembly for the allocation the allocator actually chose.
  • If an earlier stage found a problem, later stages still run on whatever survived recovery, and stoppedAt names the first stage that complained.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • Reading the assembly panel as advice about real x86-64 code generation: it is a teaching backend, and the calling convention it models is followed only far enough to be recognisable.
  • Concluding from the optimized listing that a real compiler would delete the same instructions, when the reason ours can is that AtlasLang's observable surface is two things and C's is not.
  • Assuming a program that runs here runs the same anywhere: AtlasLang arithmetic does not wrap, so a program that depends on overflow behaves differently under any real integer type.
  • Writing a non-terminating loop and reading the reported result as an answer — the VM stops at a step budget and says so, and the status field is the part to read.
  • Expecting an error in one stage to suppress later stages: they still run on the recovered tree, so a file with a parse error may also show type diagnostics that are artefacts of the recovery.
  • Editing the source and reading a stale panel from memory rather than from the screen. Every number in this module changes when the program does.

When it helps

  • Seeing a whole compiler at a size where the whole thing fits in your head, which no production toolchain permits.
  • Testing a claim from any other lesson in this domain immediately: type the program, look at the stage, see whether the claim holds.
  • Building intuition for which stage owns which kind of bug, which is the single most useful debugging skill in this subject.
  • Understanding why real compilers are structured the way they are, by watching a much smaller one arrive at the same structure for the same reasons.

When it hurts

  • As a source of facts about production compilers. AtlasLang shows the shape of the reasoning, not the numbers; carrying a number from here to LLVM is a mistake.
  • For anything involving floating point, memory, aliasing, concurrency or dynamic loading — none of which AtlasLang has, which is exactly why it is small.
  • As evidence about performance. The VM is a teaching interpreter and the assembly is not assembled, so nothing here measures anything.

What it costs

Every one of these is paid by something.

  • A tiny language buys a pipeline you can read end to end and pays by removing the hard problems — no floats, no heap, no modules, and therefore no rounding hazards, no escape analysis and no separate compilation.
  • Running every stage on every keystroke buys the side-by-side view and pays in doing far more work than a real compiler would, which is affordable only because the programs are small.
  • Lowering locals as load/store against slots buys a realistic mem2reg demonstration and pays with unoptimized IR that is noticeably longer than the source suggests.
  • Emitting bytecode from pre-SSA IR buys a VM that can actually run and pays by making the bytecode panel show a different form than the optimized SSA panel, which surprises people until they know why.
  • A step budget buys a browser tab that never hangs and pays by making genuine non-termination inexpressible — the VM reports steps-exhausted rather than looping.

What else you could do

What a different compiler or language does instead, and when that is better.

  • A tree-walking interpreter would stop after the typed AST and execute it directly: far less code, far slower, and a completely legitimate implementation of the same language — see [[atlaslang-interpreter]].
  • Emitting bytecode straight from the AST, skipping the IR entirely, which is what many small languages do and what makes them unable to optimize — see [[bytecode-compiler]].
  • Targeting a real backend such as LLVM instead of a hand-written one, which buys production code generation and costs the ability to read the whole thing — see [[llvm-architecture]].
  • Compiling to WebAssembly rather than to a bespoke VM, which is what a language wanting portability without writing an interpreter would actually do — [[webassembly]].

See it for yourself

The flag, dump or tool that shows you this directly.

  • /compilers/atlaslang — type a program, see its output, its IR and its optimized SSA side by side.
  • /compilers/pipeline — all twelve stages of the same program at once, with spans linked between panels.
  • /compilers/passes — toggle individual optimizer passes and watch which instructions survive.
  • /compilers/registers — reduce the register count until something spills.
  • /compilers/vm — step the bytecode one instruction at a time and watch the operand stack.
  • The source itself: src/compilers/sim/ is ten files, and the pass legality conditions are in optimize.ts as data, not as comments.
  • TSX_TSCONFIG_PATH=tsconfig.app.json npx tsx -e "import {compile} from '@/compilers/sim'; console.log(compile('print(1+2);').optimizedText.join(String.fromCharCode(10)))" runs the compiler from a terminal.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "It is a simulation of a compiler." It is a compiler. It lexes, parses, checks, lowers, optimizes, allocates and executes, and the panels are its output rather than illustrations of it.
  • "It optimizes aggressively, so real compilers must too." It optimizes aggressively because AtlasLang defines almost nothing as observable. A language with pointers, threads or floats hands its optimizer a far harder problem.
  • "The assembly panel shows what my CPU would run." It shows an x86-64-flavoured listing for the allocation the allocator chose. It is not assembled, and it models the calling convention only far enough to be legible.
  • "If a program works here it is correct." AtlasLang integers do not wrap and the VM stops at a step budget. Both are places where a real target behaves differently.

Misconceptions

The claim, and what is actually true.

A language needs a large team and years before anything runs.
A complete pipeline for a small language is a few thousand lines. What takes years is the long tail: numerics, memory, generics, tooling, compatibility and diagnostics good enough for strangers.
The optimizer is the interesting part of a compiler.
Most of the code and most of the difficulty here is in the frontend and in the representations. The optimizer is short precisely because the representations before it did their jobs.
Each stage is a translation into a different language.
Two of the twelve stages translate nothing. The CFG is a view of the IR and the typed AST annotates the AST in place — and knowing that is what tells you where information still exists.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

AtlasLang is a small language with a real compiler you can type into. It reads characters, groups them into tokens, builds a tree, checks the names and types, flattens the tree into instructions, optimizes them, allocates registers, emits assembly, and runs the program on a small virtual machine. Every one of those steps is visible in the browser, and the panels are what the compiler actually produced.

practical

Start at /compilers/atlaslang with print(1 + 2); and watch the optimizer remove the addition. Then load the trap example and watch it refuse to remove a different one. Those two behaviours next to each other are the most useful five minutes in this module: they show that an optimization is a rewrite with a precondition, and that the preconditions are in the code rather than in the prose. After that, /compilers/passes to see which pass does what, and /compilers/registers to make something spill.

advanced

The design decision most worth stealing is that every pass carries its own legality condition as data. PASSES in optimize.ts is an array of objects with legal and illegalWhen fields, and the UI renders them next to the transformation they describe — so a reader cannot see a rewrite without seeing what makes it valid and a program where it would not be. That is not decoration: it forced the implementation to have an answer for each pass before the pass was written, which is how mayTrap came to exist at all. The second decision worth noting is that spans are threaded through every stage rather than added later. That is what makes cross-panel highlighting possible, and it is also why it is possible at all to say which character produced a given instruction — a property real compilers have to design for from the first day, because it cannot be retrofitted cheaply.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

simplifiedAtlasLang has int, bool and str and nothing else: no floats, no user-defined types, no heap allocation, no modules and no concurrency. Each absence removes a hard problem a real compiler must solve — floating-point identities that do not hold, escape analysis, separate compilation, and a memory model that constrains reordering. Read the shape of the reasoning here; do not carry the simplifications anywhere else.
implementationEvery number in this lesson — three phi nodes, three optimizer iterations, nineteen instructions, four registers, output 22 — is what this compiler produces for DEFAULT_SOURCE at this revision. Change the program and they change; change a heuristic in the source and they change. They are observations of one implementation, not properties of compilation.
targetThe assembly panel is x86-64-flavoured: System V argument registers, rbp frames and a lea-style addition. It is a teaching backend, not an assembler, and the register names, argument order and instruction choices would all differ on AArch64 or Windows x64.

If you were asked this in an interview

  • What is the observable behavior of an AtlasLang program, and why does the answer determine how aggressive its optimizer can be?
  • Two of the twelve stages lose nothing. Which, and why does that matter?
  • Why does the optimizer delete 1 + 2 and refuse to delete 10 / 0?

Connections

DSAbinary-treedfsstackhash-table
Computer Architectureregistersinstruction-set-architecture
Domains that do not exist yet
  • Programming Languages & Runtime Internals — What a runtime provides that AtlasLang simply does without: allocation, object layout, garbage collection and dynamic dispatch
    AtlasLang has no heap, which is why it needs no collector, no write barriers and no stack maps — and therefore why its backend is short. Seeing which parts of a real compiler exist only to serve a runtime is easiest from a compiler that has no runtime to serve.