Every phase covered so far in this series has moved a program steadily further away from the source code a programmer originally typed and closer to something a real processor can actually execute. Lexical and syntax analysis captured structure, semantic analysis verified meaning, intermediate code generation produced a simplified, machine-independent representation, and code optimization polished that representation to remove unnecessary work. Code generation is where this entire journey finally arrives at its destination, translating optimized intermediate code into the actual target code, whether that is assembly language or raw machine instructions, for a specific processor.
This final phase is where a compiler must finally stop being abstract and start dealing with the very concrete, very particular details of real hardware. Earlier phases could comfortably ignore questions like how many registers a processor has available, or what its instruction set looks like, precisely because those details were irrelevant to structure, meaning, and machine-independent optimization. Code generation cannot avoid these questions any longer, and how well it answers them has a direct, measurable impact on the performance of the final program.
In this tutorial, you will learn what code generation actually involves, the key requirements a good code generator must satisfy, how instruction selection works, why register allocation is one of the most important and challenging problems in this entire phase, how register descriptors and address descriptors help track information during generation, and a worked example showing how a piece of intermediate code is translated into simple target instructions.
Code generation is the final phase of a compiler, responsible for translating the optimized intermediate representation of a program into target code that a specific machine can actually execute. Depending on the compiler's design, this target code might be assembly language, which still needs to be processed by a separate assembler, or it might be raw machine code, ready to run directly on the target processor.
Unlike earlier phases, which could largely be designed once and reused across many different target machines, code generation is inherently tied to the specific architecture being targeted. A code generator built for one processor's instruction set generally cannot be reused directly for a different processor with a different set of instructions, registers, and addressing modes, which is exactly why this phase is considered part of the compiler's back end, as introduced back in the very first tutorial of this series.
Designing a code generator involves balancing several, sometimes competing, goals. A well-designed code generator should aim to satisfy the following requirements as closely as possible.
| Requirement | Description |
|---|---|
| Correctness | The generated target code must faithfully preserve the exact meaning of the intermediate code it was translated from, under all circumstances. |
| Efficiency | The generated code should run as quickly as possible and use hardware resources, such as registers and memory, as effectively as possible. |
| Effective Resource Usage | The code generator should make good use of the limited number of registers available on the target machine, minimizing unnecessary memory accesses. |
| Reasonable Compilation Speed | The code generation process itself should complete in a reasonable amount of time, even for large programs, since compilation speed matters to developers as well. |
Correctness is by far the most important of these requirements, since a code generator that produces fast but incorrect code is worse than useless. Once correctness is guaranteed, the remaining requirements often involve genuine trade-offs, and different compilers, depending on their goals, may prioritize them differently.
Instruction selection is the process of choosing which specific target machine instructions should be used to implement each operation described in the intermediate code. This might sound like a purely mechanical, one-to-one translation, but in practice, a single intermediate code instruction can often be implemented using several different sequences of target instructions, and choosing well between these options can significantly affect the efficiency of the final program.
Intermediate Code: t1 = a + b t2 = t1 + c Naive Instruction Selection: MOV R1, a ADD R1, b MOV t1, R1 MOV R2, t1 ADD R2, c MOV t2, R2 More Efficient Instruction Selection: MOV R1, a ADD R1, b ADD R1, c MOV t2, R1
The naive translation processes each intermediate instruction in complete isolation, storing and reloading the temporary value t1 through memory even though it is used again almost immediately afterward. A smarter code generator recognizes that the value can simply remain in a register between these two closely related operations, avoiding unnecessary memory traffic entirely and producing noticeably more efficient target code for exactly the same computation.
Registers are extremely fast storage locations built directly into a processor, but every real machine has only a small, fixed number of them available. Since accessing a value stored in a register is dramatically faster than accessing the same value stored in main memory, deciding which values should be kept in registers, and for how long, is one of the most consequential decisions a code generator makes. This overall problem is generally broken down into two closely related sub-problems.
| Sub-Problem | Description |
|---|---|
| Register Allocation | Deciding which values in the program should be kept in a register at a given point in execution, as opposed to being stored in main memory. |
| Register Assignment | Deciding exactly which specific register, among those available on the target machine, should be used to hold a particular value that has already been chosen for allocation. |
When there are more values that need to be kept available than there are registers to hold them, the code generator must decide which values to temporarily move out to main memory, a situation commonly referred to as register spilling. Choosing which values to spill wisely, generally favoring those that will not be needed again for the longest stretch of upcoming instructions, has a significant impact on the overall efficiency of the generated code.
To make good decisions about instruction selection and register allocation as it processes intermediate code, a code generator typically maintains two kinds of bookkeeping information throughout the generation process.
| Descriptor | Purpose |
|---|---|
| Register Descriptor | Tracks which value or values, if any, are currently held in each available register at a given point during code generation. |
| Address Descriptor | Tracks where the current value of each program variable can currently be found, whether that is a register, a memory location, or possibly both at the same time. |
Intermediate Code Instruction: t1 = a + b Before Generating Code for This Instruction: Address Descriptor: a is in memory location a; b is in register R1 Generated Instruction: ADD R1, a After Generating Code for This Instruction: Register Descriptor: R1 now holds the value of t1 Address Descriptor: t1 is currently in register R1
By consulting these descriptors before generating each instruction, a code generator can often avoid unnecessary work, such as reloading a value from memory that is already sitting conveniently in a register, or reusing a register that currently holds a value no longer needed anywhere else in the program.
Let us walk through a slightly larger example, translating a short sequence of optimized three-address code into simplified target code, paying attention to how register descriptors and address descriptors guide the decisions made along the way.
Intermediate Code: t1 = a + b t2 = t1 * c total = t2 - d Generated Target Code: MOV R1, a ; load a into R1 ADD R1, b ; R1 now holds t1 (a + b) MUL R1, c ; R1 now holds t2 (t1 * c) SUB R1, d ; R1 now holds the final result (t2 - d) MOV total, R1 ; store the final result into total
Notice how a single register, R1, is reused across every intermediate step of this computation, since each temporary value is only needed briefly before it is combined into the next operation and then discarded. A well-designed code generator recognizes this pattern automatically, using its register and address descriptors to avoid the wasted memory traffic that a more naive, one-instruction-at-a-time translation would introduce.
Depending on a compiler's overall design and goals, the target code produced during this phase can take a few different forms, each suited to slightly different use cases.
| Target Code Form | Description |
|---|---|
| Assembly Language | Human-readable, symbolic instructions that still require a separate assembler to convert them into raw machine code before execution. |
| Relocatable Machine Code | Machine code that can be combined with other compiled modules and libraries by a linker before producing a final, complete executable program. |
| Absolute Machine Code | Machine code with fixed memory addresses already assigned, ready to be loaded directly into memory and executed without any further processing. |
Most modern compilers favor generating relocatable machine code, or an equivalent intermediate object format, since this allows a program to be split across multiple source files, compiled independently, and later combined together by a separate linking step, along with any external libraries the program depends on.
Among all the phases covered throughout this series, code generation is often regarded as the most challenging to implement well, precisely because it must simultaneously satisfy correctness while also making genuinely difficult decisions, such as register allocation, that have been mathematically shown to be computationally hard to solve perfectly in the general case. Real-world code generators rely on carefully designed heuristics, approximate strategies that tend to produce good, though not always mathematically optimal, results in a reasonable amount of time, rather than attempting to find a theoretically perfect solution for every single program.
This is also the phase where the earlier separation between a compiler's front end and back end pays off most clearly. Everything discussed in this tutorial depends entirely on the target machine's specific architecture, while remaining almost completely independent of which source language originally produced the optimized intermediate code being translated, which is exactly the kind of reusability that motivated the front end and back end separation introduced at the very beginning of this series.
| Mistake | Correct Understanding |
|---|---|
| Assuming code generation is a simple, mechanical, one-to-one translation from intermediate code to target instructions. | Code generation involves genuinely difficult decisions, particularly around instruction selection and register allocation, that significantly affect the efficiency of the final program. |
| Treating register allocation and register assignment as the exact same problem. | Register allocation decides which values should be kept in registers at all, while register assignment decides specifically which register a chosen value should occupy. |
| Believing a code generator can always keep every needed value in a register at the same time. | Since registers are limited in number, a code generator must sometimes spill values out to memory, choosing carefully which values to spill to minimize the overall performance cost. |
| Assuming code generation techniques are portable across different target machines without modification. | Code generation is inherently tied to the specific architecture of the target machine, unlike earlier, largely machine-independent phases such as optimization. |
Code generation completes a compiler's journey from human-readable source code to executable target instructions, translating optimized intermediate code into assembly or machine code tailored to a specific processor. Along the way, it must carefully perform instruction selection, choosing efficient sequences of target instructions, and register allocation and assignment, deciding which values deserve the scarce, fast storage that registers provide. Register descriptors and address descriptors help the code generator track this information as it works, allowing it to avoid unnecessary memory traffic and produce efficient, correct target code.
In this tutorial, you learned what code generation involves, the key requirements a good code generator must satisfy, how instruction selection affects the efficiency of generated code, why register allocation and assignment are among the hardest problems in this phase, how register and address descriptors support the generation process, and why this final phase is so tightly bound to the specific architecture of the target machine. With this foundation in place, you are ready to explore how the symbol table and runtime environment work together to support variable storage and function execution throughout a program's lifetime.