Code generation

Code generation is the last phase of a compiler's back end, taking the optimized intermediate representation (IR) and converting it into executable target code. This phase must ensure that the generated code is semantically equivalent to the original source and that it meets target-specific constraints such as register usage, instruction formats, and calling conventions. The output is typically assembly code or machine code that can be assembled or linked into a final executable. The correctness of this phase is paramount, as any error propagates to the runtime. In modern compilers, code generation is often divided into sub-phases: instruction selection, register allocation, and instruction scheduling, each addressing a different aspect of code quality.

Instruction selection maps IR operations to target machine instructions using pattern matching, often via tree grammars (e.g., BURS, burg) or dynamic programming. Register allocation assigns variables to a limited set of registers; graph coloring and linear scan are the dominant algorithms. Instruction scheduling reorders instructions to exploit instruction-level parallelism, using list scheduling for basic blocks and modulo scheduling for loops. Some compilers also employ peephole optimization, which replaces small sequences of generated instructions with more efficient ones. These techniques are combined to produce code that runs quickly and uses resources efficiently.

One major challenge is handling complex instruction set architectures (CISC) with variable-length instructions and addressing modes, which complicates instruction selection. Pipelined processors require careful scheduling to avoid stalls, while memory hierarchy considerations demand that the code generator manage data locality. Trade-offs exist between code size and execution speed, especially in embedded systems. Additionally, modern compilers must support multiple target architectures, often using retargetable code generators such as GCC's RTL or LLVM's target description files. These tools abstract target-specific details, allowing the same optimization passes to work across platforms.

The first compilers, such as the Fortran I compiler (1957), already included a code generation phase that produced efficient machine code for the IBM 704. The theory of code generation was formalized in the 1970s and 1980s, with contributions from Alfred Aho, Ravi Sethi, and Jeffrey Ullman. Aside from static compilation, just-in-time (JIT) compilation also performs code generation at runtime, as seen in Java Virtual Machines and modern JavaScript engines. Code generation for virtual machines (e.g., bytecode generation) and for graphics processing units (GPUs) involves unique constraints. Peephole optimization, a simple yet effective technique, was first described in the 1960s and remains widely used.

Intermediate representation

The data structure or code used internally by a compiler to represent the source program, often between the front end and back end.

Instruction selection

The process of mapping IR operations to target machine instructions, often using pattern matching on tree or DAG representations.

Register allocation

The assignment of program variables to a limited number of processor registers to minimize memory accesses.

Instruction scheduling

The reordering of instructions to improve pipeline utilization and reduce stalls.

Peephole optimization

A local optimization that examines short sequences of instructions and replaces them with more efficient ones.

Back end

The part of a compiler that handles the target-dependent phases, including code generation and optimization.