How a Compiler Turns Code into Machine Instructions

A compiler does not translate each source line into one assembly line. It repeatedly changes the program’s representation. Each representation discards details that are no longer useful and makes a different question easier to answer: Which characters form a token? What does an identifier refer to? Is an addition legal? Which values are constant? Which machine instruction can implement an operation? Where should every temporary live?

Consider the small expression let total: i32 = price * 4 + 2. Its spelling matters to the lexer, its tree shape matters to the parser, its declared type matters to semantic analysis, and its arithmetic dependencies matter to the optimizer. By the time a backend emits instructions, names such as total may have disappeared entirely. What remains is a graph of values, effects, branches, and storage locations.

This article follows that transformation through a miniature TypeScript compiler. The language has integer literals, variables, let declarations, addition, and multiplication. It is intentionally small, but the boundaries are real ones used by production compilers.

The front end turns text into meaning #

Lexing groups characters into tokens. It removes irrelevant whitespace while preserving categories and source positions. The input price * 4 + 2 becomes identifier(price), star, integer(4), plus, and integer(2). Keeping offsets is essential: later phases must report an unknown name or type mismatch at the original source location, not at some generated instruction.

Parsing then recognizes grammatical structure. Precedence makes multiplication bind more tightly than addition, so the expression becomes Add(Mul(Name("price"), Int(4)), Int(2)). This abstract syntax tree omits punctuation that has served its purpose. A concrete syntax tree, used by formatters and refactoring tools, usually retains comments, whitespace, and delimiters as well.

The front end below keeps only the expression grammar. A regular expression recognizes the token classes, while precedence climbing gives * a tighter binding than +:

type Expr =
  | { kind: 'int'; value: number; offset: number }
  | { kind: 'name'; name: string; offset: number }
  | { kind: 'binary'; op: '+' | '*'; left: Expr; right: Expr; offset: number };

type Token = { kind: 'int' | 'name' | 'plus' | 'star' | 'eof'; text: string; offset: number };

function lex(source: string): Token[] {
  const pattern = /\s+|\d+|[A-Za-z_]\w*|[+*]/gy;
  const tokens: Token[] = [];
  while (pattern.lastIndex < source.length) {
    const offset = pattern.lastIndex;
    const match = pattern.exec(source);
    if (!match) throw new SyntaxError(`unexpected input at ${offset}`);
    const text = match[0];
    if (/^\s+$/.test(text)) continue;
    const kind = /^\d+$/.test(text) ? 'int'
      : /^\w+$/.test(text) ? 'name'
      : text === '+' ? 'plus' : 'star';
    tokens.push({ kind, text, offset });
  }
  return [...tokens, { kind: 'eof', text: '', offset: source.length }];
}

class Parser {
  private cursor = 0;
  constructor(private readonly tokens: Token[]) {}

  parseExpression(minPrecedence = 0): Expr {
    const token = this.tokens[this.cursor++]!;
    let left: Expr;
    if (token.kind === 'int') left = { kind: 'int', value: Number(token.text), offset: token.offset };
    else if (token.kind === 'name') left = { kind: 'name', name: token.text, offset: token.offset };
    else throw new SyntaxError(`expected expression at ${token.offset}`);

    const precedence = { plus: 1, star: 2 } as const;
    while (true) {
      const operator = this.tokens[this.cursor]!;
      const level = operator.kind === 'plus' || operator.kind === 'star' ? precedence[operator.kind] : -1;
      if (level < minPrecedence) break;
      this.cursor++;
      const right = this.parseExpression(level + 1);
      left = { kind: 'binary', op: operator.kind === 'plus' ? '+' : '*', left, right, offset: operator.offset };
    }
    return left;
  }
}

Real parsers also recover after errors and handle ambiguous grammar. The contract remains: parsing creates structure, not meaning.

Semantic analysis resolves names and types #

An AST can be grammatically valid and still be meaningless. price * missing references an undeclared variable. A language with strings might parse price + "four", yet reject it because no matching addition exists. Semantic analysis builds scopes, binds every name use to a declaration, checks visibility and mutability, infers or verifies types, and often annotates the tree with symbols and conversions.

Our language has one type, but it still demonstrates the boundary. An environment maps source names to stable symbol IDs. Stable IDs distinguish two variables both spelled value in nested scopes and let later phases forget source spelling.

type SymbolId = number;
type TypedExpr =
  | { kind: 'const'; value: number; type: 'i32' }
  | { kind: 'load'; symbol: SymbolId; type: 'i32' }
  | { kind: 'binary'; op: '+' | '*'; left: TypedExpr; right: TypedExpr; type: 'i32' };

function checkExpression(expression: Expr, scope: Map<string, SymbolId>): TypedExpr {
  switch (expression.kind) {
    case 'int':
      if (!Number.isInteger(expression.value) || expression.value > 2_147_483_647) {
        throw new TypeError(`i32 literal out of range at ${expression.offset}`);
      }
      return { kind: 'const', value: expression.value, type: 'i32' };
    case 'name': {
      const symbol = scope.get(expression.name);
      if (symbol === undefined) throw new ReferenceError(`unknown name '${expression.name}' at ${expression.offset}`);
      return { kind: 'load', symbol, type: 'i32' };
    }
    case 'binary':
      return {
        kind: 'binary',
        op: expression.op,
        left: checkExpression(expression.left, scope),
        right: checkExpression(expression.right, scope),
        type: 'i32',
      };
  }
}

Type checking is more than preventing crashes. It chooses operations. Signed and unsigned comparison use different machine instructions; integer and floating-point addition obey different overflow and rounding rules; a generic call may need specialization. The type system therefore supplies facts on which lowering and optimization depend.

IR and SSA expose data flow #

Compilers usually lower the typed AST into an intermediate representation (IR). An AST mirrors source nesting; IR makes control flow and data dependencies explicit. A single compiler may use several levels: a rich typed IR for language features, a mid-level control-flow IR for optimization, and a machine IR close to the target architecture.

Static single assignment form, or SSA, gives each value exactly one definition. Instead of repeatedly assigning x, the compiler creates x0, x1, and so on. At a control-flow merge, a phi node chooses the value associated with the predecessor that executed. This property makes use-definition chains direct and enables sparse analyses.

For a straight-line expression, virtual registers provide the important SSA-like property:

v0 = load symbol0       ; price
v1 = const 4
v2 = mul.i32 v0, v1
v3 = const 2
v4 = add.i32 v2, v3
store symbol1, v4       ; total

Optimization is not one magic step. It is a sequence of analyses and rewrites that preserve observable behavior.

The order matters. Inlining may reveal constants; folding those constants may make a branch unreachable; deleting the branch may expose dead values. Production optimizers repeat pass groups until no useful changes occur, while limiting compile time and code growth.

The backend selects instructions and registers #

Instruction selection maps IR operations to legal target patterns. A multiplication by four could become imul, but on some targets and cost models a shift is preferable. An addition whose result immediately forms an address might fold into an addressing mode. Selection must account for operand constraints, condition flags, calling conventions, and CPU-specific costs, not merely opcode names.

The target initially still uses unlimited virtual registers. Real hardware has a small, irregular register file. Register allocation computes where values are live, assigns non-interfering live ranges to the same physical register, and spills excess values to stack slots. Graph coloring can produce strong allocations; linear scan is faster and is common in JITs. Calling conventions reserve some registers, classify argument and return locations, and specify which registers a callee must preserve.

This focused backend lowers stack-shaped IR, folds constants, computes last uses, reuses dead registers, and emits x64-like assembly:

type Ir =
  | { op: 'const'; out: number; value: number }
  | { op: 'load'; out: number; stackOffset: number }
  | { op: 'add' | 'mul'; out: number; left: number; right: number }
  | { op: 'store'; value: number; stackOffset: number };

function foldConstants(instructions: Ir[]): Ir[] {
  const constants = new Map<number, number>();
  return instructions.map((instruction) => {
    if (instruction.op === 'const') constants.set(instruction.out, instruction.value);
    if (instruction.op !== 'add' && instruction.op !== 'mul') return instruction;
    const left = constants.get(instruction.left);
    const right = constants.get(instruction.right);
    if (left === undefined || right === undefined) return instruction;
    const value = instruction.op === 'add' ? (left + right) | 0 : Math.imul(left, right);
    constants.set(instruction.out, value);
    return { op: 'const', out: instruction.out, value };
  });
}

function emitX64(instructions: Ir[]): string[] {
  const registers = ['eax', 'ecx', 'edx'];
  const location = new Map<number, string>();
  const lastUse = new Map<number, number>();
  const assembly: string[] = [];

  instructions.forEach((instruction, index) => {
    if (instruction.op === 'add' || instruction.op === 'mul') {
      lastUse.set(instruction.left, index);
      lastUse.set(instruction.right, index);
    } else if (instruction.op === 'store') lastUse.set(instruction.value, index);
  });

  const acquire = (index: number): string => {
    for (const [value, register] of location) {
      if ((lastUse.get(value) ?? -1) < index) location.delete(value);
      else if (register.startsWith('spill')) continue;
    }
    const used = new Set(location.values());
    const free = registers.find((register) => !used.has(register));
    if (!free) throw new Error('spill required: allocate a stack slot');
    return free;
  };

  instructions.forEach((instruction, index) => {
    if (instruction.op === 'const') {
      const target = acquire(index);
      location.set(instruction.out, target);
      assembly.push(`mov ${target}, ${instruction.value}`);
    } else if (instruction.op === 'load') {
      const target = acquire(index);
      location.set(instruction.out, target);
      assembly.push(`mov ${target}, DWORD PTR [rbp${instruction.stackOffset}]`);
    } else if (instruction.op === 'add' || instruction.op === 'mul') {
      const left = location.get(instruction.left)!;
      const right = location.get(instruction.right)!;
      location.delete(instruction.left);
      const target = left;
      location.set(instruction.out, target);
      assembly.push(`${instruction.op === 'add' ? 'add' : 'imul'} ${target}, ${right}`);
    } else {
      assembly.push(`mov DWORD PTR [rbp${instruction.stackOffset}], ${location.get(instruction.value)!}`);
    }
  });
  return assembly;
}

This allocator intentionally reports when spilling is required rather than hiding the hard part. A complete allocator inserts stores and reloads, splits live ranges, handles fixed-register instructions, and may rerun allocation after rewriting. After allocation, the assembler encodes instructions into bytes, chooses immediate widths, and records locations it cannot yet resolve.

Object files, linking, JITs, and correctness #

An object file is more than machine-code bytes. It contains named sections such as executable code, read-only constants, writable data, symbol tables, and relocations. A call to a function in another file has an unknown final address, so the assembler emits a placeholder and a relocation saying how the linker must patch it. The linker combines objects and libraries, resolves symbols, lays out sections, removes unreachable sections when configured, and produces an executable or shared library. The operating-system loader maps that image into memory and performs remaining dynamic relocations.

Debug information preserves a route back through all those transformations. DWARF or PDB records can map instruction ranges to source lines, describe scopes and types, and express where a variable currently lives. Optimization complicates the story: an inlined function has no ordinary stack frame, a variable may move between a register and a stack slot, and dead code has no instruction address. A debugger saying “optimized out” is often the honest answer.

Ahead-of-time and just-in-time compilers use many of the same phases but optimize different constraints:

A JIT may observe that a JavaScript addition has always received small integers and emit a fast integer sequence guarded by type checks. If a string arrives later, deoptimization metadata reconstructs interpreter state and resumes in generic code. Tiered runtimes begin by interpreting or compiling quickly, collect profiles, then spend more optimization effort only on hot functions. AOT compilers can approximate that knowledge through profile-guided optimization, but their profile may not match the next deployment.

Correctness remains the non-negotiable constraint. Each pass should preserve the language’s observable semantics, including exceptions, memory ordering, volatile access, integer overflow, and floating-point corner cases. Compiler teams combine unit tests, end-to-end conformance suites, IR verifiers, differential testing against another compiler or interpreter, fuzz-generated programs, and translation validation. Optimization is a proof obligation disguised as an engineering transformation.

Takeaways #

• Compilation is a sequence of representations, not a direct text-to-assembly substitution.
• Tokens and ASTs recover syntax; name resolution and type checking establish meaning and preserve source diagnostics.
• SSA-like IR exposes use-definition and control-flow relationships that make optimization tractable.
• Instruction selection, calling conventions, liveness, register allocation, and spilling adapt unlimited IR values to constrained hardware.
• Assemblers create machine code plus relocation records; linkers resolve the final program, while debug metadata maps optimized instructions back to source.
• AOT compilers spend time before execution; JITs use live profiles and guarded specialization, then deoptimize when assumptions fail.
• Every optimization is constrained by source-language semantics. Faster wrong code is a compiler bug, not an optimization.

The source variable total became a token, AST declaration, typed symbol, virtual value, physical register, encoded bytes, and finally an address in a loaded process. A compiler makes one hard translation into smaller, checkable decisions.