Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 61 ยท Code Generation and Runtimes

Code Generation and Instruction Selection

Learn how a code generator turns intermediate code into machine instructions: targets, instruction selection by tree tiling, and a runnable toy CPU.

The last phase of a compiler is code generation. It takes the optimized intermediate representation and produces instructions for a real (or virtual) machine. Everything before this point was independent of the hardware; here the compiler must know how many registers exist, which operations the CPU offers, how big its instructions are and what the calling convention demands.

The code generator has three main jobs. Instruction selection chooses which target instructions implement each piece of IR. Register allocation decides which values live in which registers (next lesson). Instruction ordering (scheduling) arranges instructions so the processor stalls less. In this lesson you will focus on selection and on the overall shape of a simple generator, and you will run the output on a toy CPU emulator written in Python.

Choosing a target

A target can be:

  • Machine code for a real CPU such as x86-64, ARM64 or RISC-V, often emitted as assembly text and passed to an assembler and linker.
  • Bytecode for a virtual machine, such as the JVM, CPython or WebAssembly, discussed in bytecode and virtual machines.
  • Another high-level language, such as C or JavaScript. That is called transpiling.

CPUs fall into two broad families. A RISC machine (ARM, RISC-V, MIPS) has few, regular instructions, most operating on registers only; memory is touched by explicit load and store instructions. A CISC machine (x86) has many instructions, including ones that read memory directly and complex addressing modes such as base + index * scale + offset. Selection is easy on a RISC target and a rich optimization problem on a CISC target, because many different instruction sequences compute the same thing.

Our toy CPU resembles a small RISC machine. It has four registers R0 to R3, named memory cells for variables, and these instructions:

Instruction Effect
LDI Rd, n Rd = n (load an immediate constant)
LD Rd, v / ST v, Rs load a memory cell into a register / store a register into a cell
ADD, SUB, MUL Rd, Ra, Rb Rd = Ra op Rb
ADDI Rd, Ra, n Rd = Ra + n (an immediate form)
SHL Rd, Ra, k Rd = Ra << k (shift left)
SLT Rd, Ra, Rb Rd = 1 if Ra < Rb, else 0
JMP L / JZ Rs, L jump / jump if register is zero
PRINT Rs output a register

Instruction selection by tree tiling

Think of an expression as a tree. Each machine instruction can compute a small piece of such a tree: a pattern, or tile. ADD covers a node + with two register operands. ADDI covers a node + whose right child is a constant, so it replaces three tree nodes' worth of work (a constant load, an add) with one instruction. SHL covers a multiplication by a power of two. Selecting instructions means covering the whole tree with tiles so that the total cost is low.

flowchart TD
    P["+"] --> M["*"]
    P --> C["3"]
    M --> X["x"]
    M --> E["8"]

The tree for x * 8 + 3. One tile (ADDI) covers the + with its constant, and one tile (SHL) covers * with 8, leaving only x to load.

The common simple strategy is maximal munch. Start at the root, choose the largest tile that fits at that node, emit code for the subtrees that the tile leaves uncovered, and repeat. It is greedy and not always optimal, but it is easy and usually good. Optimal tiling on trees can be computed by dynamic programming (each node stores its cheapest cover), and tools such as BURG generate selectors from pattern tables. Modern compilers like LLVM select on DAGs, where shared subexpressions are visible, not on pure trees.

A tree-tiling generator

The generator below handles the expression x * 8 + (y + 3 - x * y). It runs twice. In the naive mode it uses only the generic tiles: load a constant, load a variable, and one three-register instruction per operator. In the tiled mode it adds the ADDI tile and the SHL tile. It also chooses which child to evaluate first by computing how many registers each subtree needs (the Ershov number: a leaf needs 1, and a node needs the larger child's value, or one more if both are equal). Evaluating the hungrier subtree first keeps the number of simultaneously live registers small, which matters on a four-register machine.

Python Instruction selection with tiles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both programs print 15, the same as Python computes for x = 5, y = 7, so the tiling did not change the meaning. The tiled version needs 9 instructions instead of 11: y + 3 became a single ADDI and x * 8 became a single SHL, which also avoids two constant loads. Look at where the right-hand subtree is evaluated: the code for y + 3 - x * y is emitted first because it needs three registers while x * 8 needs two, and keeping the larger computation first leaves room for the smaller one afterwards. Three of the four registers were enough for the whole expression.

If the tree had been so deep that more registers were needed than exist, the generator would spill: store an intermediate result in memory and reload it later. The register allocator in the next lesson treats this problem for a whole function.

From three-address code to assembly

Trees describe single expressions. A full generator also translates statements, jumps and labels. The simplest scheme walks the three-address code one instruction at a time: load the operands into registers, perform the operation, store the result back into the variable's memory cell. Labels and jumps map one-to-one to labels and jump instructions, and a conditional ifz t goto L becomes a load plus JZ.

This produces correct but wasteful code, since every temporary makes a round trip through memory. A peephole optimizer repairs the worst of it. It slides a small window of two or three instructions over the output and replaces known wasteful patterns. A classic pattern is a store followed by a load of the same variable, where the load can become a register-to-register MOV (or disappear if it targets the same register).

The second example translates the TAC of a loop that sums squares. It includes a runnable emulator that counts executed instructions and memory accesses before and after the peephole pass.

Python Translating three-address code and a peephole pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions print 55 (1 + 4 + 9 + 16 + 25). The peephole pass changed one place: after ST t1, R2 the next instruction reloaded t1, which is replaced by MOV R0, R2. The loop runs the test six times, so the pass removes six memory accesses. The instruction count stays the same, but a register move is much cheaper than a memory access on real hardware. A better generator would go further: keep i and s in registers for the whole loop, never store the temporaries at all, and use a compare-and-branch instruction. That is the job of register allocation.

Issues in the design of a code generator

Before looking at tiles and registers, it helps to know the questions every code generator designer has to answer. The same list appears in every compiler textbook, because it is the real set of decisions.

1. The input. The generator receives the program in some intermediate representation (three-address code, a tree, bytecode) together with the symbol table. A good input is already checked: all types are known, the operations are low-level enough that each maps to a few machine instructions, and obviously impossible things have been rejected earlier. The generator can assume this and does not repeat the semantic checks.

2. The target program. The output can take one of three forms, with different trade-offs:

Form What it is Advantage Disadvantage
Absolute machine code binary with fixed addresses, ready to load at one place runs immediately cannot be combined with other modules
Relocatable machine code binary with symbols and relocation records, as in an object file modules compile separately and are joined by the linker needs a linking step
Assembly text readable instructions for an assembler easy to debug and to generate one more tool in the pipeline

3. Instruction selection. There are usually many instruction sequences that compute the same thing, and they differ in size and speed. A multiplication by 8 can be a shift or a multiply. The selector needs a cost model that says what "better" means, and the answer can depend on the goal: smallest code or fastest code.

4. Register allocation and assignment. Registers are few and fast. The generator decides which values live in registers (register allocation) and in which ones, and some instructions or calling conventions force particular registers.

5. Evaluation order. The order in which independent operations are computed can change the code quality, for example the number of registers needed. But when operands have side effects, the language fixes the order and the generator must obey it.

6. Memory management. The front end named things with symbols. The generator must turn them into addresses: each variable gets a stack offset or a static address (from the runtime environment), and each label becomes the address of an instruction. Jumps forward need the address of code not yet generated, which is backpatching or a second pass.

Quality criteria. The last point is how to judge the result. First comes correctness: the generated code must do exactly what the source means, including in corner cases. Then efficiency of the target code (speed, size, power) and, less obviously, efficiency of the compiler itself: a generator that finds the optimal sequence with exponential search is useless if it makes the build take hours. Real generators accept good but not optimal code.

The next program shows three of these issues in miniature: turning labels and variable names into addresses in two passes (issue 6), choosing instruction sequences by cost under two different goals (issue 3), and how side effects limit evaluation order (issue 5). The costs in part two are illustrative numbers for a made-up machine, not measurements of a real CPU.

Python Addresses, cost models and evaluation order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part one is the work of an assembler folded into the generator: pass one finds where each label lands (top is instruction 0, end is instruction 6) and pass two replaces names by numbers, so LD R0, i becomes LD R0, 100. Part two prints different winners for the same source expressions: with the goal "speed" the shift-and-add sequences beat the slow multiply for x * 9 and x * 15, while with the goal "size" the single MUL wins. Neither answer is wrong; the compiler's optimization level (-O2 versus -Os in GCC and Clang) decides which cost model applies. Part three prints 20 for one order and 10 for the other, because g multiplies the shared state that f just changed. A generator may reorder pure expressions to save registers, but not these.

Other concerns of a real back end

  • Addressing modes. x86 can compute [base + index*4 + 8] inside a single load; the selector must recognize that pattern in the address tree.
  • Instruction scheduling. A load takes several cycles, so the compiler places independent instructions between a load and its first use.
  • Branch layout. Putting the likely path as the fall-through lowers the penalty for mispredicted jumps.
  • Calling convention code. Prologue, epilogue, argument passing and saved registers follow the rules from runtime environments.
  • Emitting the output. The generator writes assembly or object code with relocations; the linker joins the pieces.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is instruction selection?

    Selection maps IR operations to target instructions, usually by covering the IR tree with instruction patterns (tiles). Ordering and register assignment are separate jobs.
  2. 2. Why does the tiled generator produce fewer instructions for x * 8 + 3?

    Larger tiles cover several tree nodes with one instruction. Maximal munch picks the biggest matching tile at each node.
  3. 3. What does maximal munch do?

    Maximal munch is a greedy top-down strategy. It is simple and usually good, though not guaranteed to find the cheapest tiling.
  4. 4. What does the peephole optimizer do in the lesson?

    A peephole pass is a local clean-up over the target code. The store/load pair becomes a register move because the value is already in a register.

Summary

  • A code generator must settle the input IR, the form of the target program, instruction selection under a cost model, evaluation order, and the mapping of names and labels to addresses.
  • Code generation maps optimized IR onto a target machine; its main tasks are instruction selection, register allocation and scheduling.
  • Targets include machine code, VM bytecode and other languages; RISC targets make selection simple, CISC targets make it rich.
  • Instruction selection covers expression trees with tiles, often greedily with maximal munch or optimally with dynamic programming.
  • A simple translator loads operands, applies the operator and stores the result; a peephole pass then removes redundant patterns.
  • Evaluating the subtree with the larger register need first reduces register pressure.

Next: Register Allocation