Code Generation and Optimization

Learning Objectives

• Explain where code generation fits in the compiler pipeline and what it produces
• Describe the three main sub-tasks of code generation: instruction selection, register allocation, and instruction scheduling
• Apply dead code elimination and constant folding to a small code example
• Explain why register allocation is treated as a graph coloring problem
• Distinguish machine-independent optimizations from machine-dependent ones
• Identify the tradeoffs optimization introduces between compile time and runtime performance

Quick Answer

Code generation is the final phase of compilation: it takes the (often optimized) intermediate representation of a program and translates it into actual machine code or assembly that a processor can execute. Along the way, the compiler applies optimizations — transformations that make the generated code faster or smaller without changing what the program computes. The three core jobs of code generation are deciding which machine instructions to use (instruction selection), deciding which values live in the limited set of CPU registers (register allocation), and ordering instructions efficiently (instruction scheduling). Optimization can happen at multiple points — on the intermediate representation, during code generation, or on the final machine code — and ranges from simple local cleanups like removing unreachable code to global techniques like register allocation via graph coloring.

Where Code Generation Fits

By the time code generation begins, the program has already been checked for grammatical correctness (syntax analysis), checked for meaning (semantic analysis), and typically translated into an intermediate representation (IR) — a simplified, often three-address-code-like form that is easier to analyze and transform than either the original source or raw machine code. Optimization passes operate mainly on this IR, and code generation then maps the (possibly optimized) IR onto the instruction set of a specific target machine.

Why this staged design matters: separating "what the program means" (IR) from "how a specific CPU executes it" (machine code) lets the same front end and optimizer support many target architectures — only the final code generation stage needs to know the details of a specific instruction set.

Instruction Selection

Instruction selection is the process of mapping each IR operation onto one or more actual machine instructions. This sounds mechanical, but real instruction sets offer choices: an addition might be doable with a plain ADD, or folded into a single LEA (load effective address) instruction on x86 if it's really computing an address, or combined with a multiply into a single fused instruction on architectures that support it.

IR:        t1 = a + b
           t2 = t1 * 2
Naive:     ADD  R1, a, b
           MUL  R2, R1, #2
Better:    LEA  R2, [a + b + a + b]   ; if the target supports scaled addressing

Why it matters: picking the wrong instruction sequence leaves performance on the table even if the program is logically correct — instruction selection is where the compiler starts caring about the actual hardware, not just the program's meaning.

Register Allocation

CPUs have a small, fixed number of registers (often 8 to 32 general-purpose ones), but a typical function may reference far more variables and temporaries than that. Register allocation decides which values are kept in registers at each point in the program and which must be spilled to memory when there aren't enough registers to go around.

The standard technique models this as graph coloring: build an interference graph where each node is a variable/temporary, and an edge connects two nodes if their live ranges overlap (i.e., both hold values needed at the same point in the program, so they cannot share a register). Register allocation then becomes the problem of coloring this graph with k colors, where k is the number of available registers — two nodes connected by an edge cannot receive the same color. If no valid k-coloring exists, the allocator spills a variable (assigns it to memory instead) to reduce interference and tries again.

a = 1
b = 2
c = a + b     ; a and b both live here -> interfere
d = c * 2     ; a and b are dead now; c is live

Here a and b interfere (both needed for the c = a + b line) and must get different registers, but d can safely reuse whichever register held a or b, since neither is needed anymore once c is computed.

Why it matters: registers are dramatically faster to access than memory. A poor allocation that spills frequently-used variables to memory can slow a program down far more than most other optimization decisions combined — this is why register allocation gets its own dedicated, carefully studied algorithm rather than being treated as an afterthought.

Optimization Techniques

Optimizations are correctness-preserving transformations: the optimized program must compute the exact same result as the unoptimized one, just faster, smaller, or using less memory. They're commonly split into machine-independent optimizations (performed on the IR, useful for any target) and machine-dependent ones (tailored to a specific CPU's instruction set and quirks).

Constant folding evaluates constant expressions at compile time instead of at runtime:

Before:  x = 3 * 4 + 2
After:   x = 14

Constant propagation substitutes a known constant value for a variable at points where it hasn't changed:

Before:  a = 5
         b = a + 2
After:   a = 5
         b = 7

Dead code elimination removes computations whose results are never used:

Before:  x = compute_something()   ; x never used afterward
         y = 10
         return y

After:   y = 10
         return y

Common subexpression elimination (CSE) detects when the same expression is computed more than once with no changes to its operands in between, and reuses the first result instead of recomputing it:

Before:  a = x * y + 1
         b = x * y - 1

After:   t = x * y
         a = t + 1
         b = t - 1

Why it matters: each of these techniques targets a specific, common pattern of wasted work that programmers routinely leave behind (whether from writing clear code, using named constants, or after other transformations expose new opportunities). Applied together and often repeatedly — since eliminating one piece of dead code can expose more — they can measurably shrink and speed up the generated program without the programmer having to hand-optimize anything.

Key Terms

Term	Definition	Related Concept
Intermediate Representation (IR)	A simplified, target-independent form of the program used between the front end and code generation	Code generation
Instruction Selection	Mapping IR operations onto specific machine instructions	Instruction Set Architecture
Register Allocation	Deciding which values occupy the limited set of CPU registers at each program point	Graph coloring, spilling
Interference Graph	A graph where nodes are variables and edges connect variables whose live ranges overlap	Register allocation
Spilling	Storing a value in memory instead of a register because not enough registers are available	Register allocation
Constant Folding	Evaluating constant expressions at compile time rather than runtime	Constant propagation
Constant Propagation	Replacing a variable with its known constant value at points where it hasn't changed	Constant folding
Dead Code Elimination	Removing code whose results are never used	Optimization
Common Subexpression Elimination (CSE)	Computing a repeated expression once and reusing the result	Optimization
Machine-Independent Optimization	An optimization performed on the IR, applicable regardless of target architecture	Machine-dependent optimization

Common Mistakes

Misconception: Optimization means the compiler can make any code run arbitrarily fast if you just enable enough flags. Why it's wrong: Optimizations are correctness-preserving transformations of existing logic — they eliminate waste (redundant computation, unused values, poor instruction choices), but they cannot change the algorithmic complexity of what the programmer wrote. A compiler will not turn a quadratic-time algorithm into a linear one. Correct understanding: Optimization improves the constant factors and removes local inefficiencies within the algorithm you actually wrote; choosing a better algorithm is still the programmer's job.

---

Misconception: More registers always means register allocation is trivial, so it barely matters as a compiler topic. Why it's wrong: Even with many registers, real programs routinely have more simultaneously live values than any practical register file can hold, and different candidate values interfere in complex, overlapping ways. Correct understanding: Register allocation is a genuinely hard problem (graph coloring is NP-complete in general), which is why compilers use heuristic algorithms rather than guaranteed-optimal ones, and why spilling to memory remains a real, performance-relevant possibility even on modern CPUs.

---

Misconception: Dead code elimination and constant folding are one-time passes that run once and are done. Why it's wrong: Applying one optimization frequently creates new opportunities for another — folding a constant can make a branch condition provably always-true or always-false, which then makes the other branch dead code, which can expose further foldable constants. Correct understanding: Real optimizers run passes repeatedly (or in a carefully chosen fixed-point loop) until no further changes occur, precisely because these transformations feed each other.

Comparison and Connections

Aspect	Machine-Independent Optimization	Machine-Dependent Optimization
Operates on	Intermediate representation (IR)	Target machine instructions
Portable across architectures?	Yes	No — tied to a specific ISA
Examples	Constant folding, dead code elimination, CSE	Instruction selection tuned to an ISA, peephole optimization on emitted assembly
When it runs	Before code generation	During/after code generation
Typical goal	Remove logical waste in computation	Exploit specific hardware capabilities

Practice Questions

Recall

1. What are the three core sub-tasks of code generation? Answer guidance: Instruction selection, register allocation, and instruction scheduling.

2. What does "spilling" mean in the context of register allocation? Answer guidance: Storing a value in memory instead of a register because there aren't enough available registers to hold all currently live values.

Understanding

3. Why is register allocation modeled as a graph coloring problem? Answer guidance: Variables that are simultaneously live (needed at the same point in the program) interfere and cannot share a register, which is naturally represented as an edge in a graph. Assigning registers becomes equivalent to coloring the graph so that no two connected (interfering) nodes get the same color, with the number of colors limited to the number of available registers.

4. Why do compilers run optimization passes repeatedly rather than just once? Answer guidance: Optimizations interact — for example, constant folding can make a branch condition always-true or always-false, which turns the other branch into dead code, and eliminating that dead code can expose more constants to fold. Running passes repeatedly (until reaching a fixed point) catches these cascading opportunities.

Application

5. Given a = 2 * 3; b = a + 1; c = compute_expensive(); return b;, identify which optimizations apply and rewrite the code after applying them. Answer guidance: Constant folding turns 2 * 3 into 6. Constant propagation then turns a + 1 into 6 + 1, foldable to 7. Since c is never used, dead code elimination removes the compute_expensive() call entirely. Result: return 7;.

6. A function computes x * y in two separate statements with no intervening changes to x or y. What optimization applies, and what does the transformed code look like? Answer guidance: Common subexpression elimination applies. The compiler computes t = x * y once and substitutes t everywhere the original expression appeared, avoiding the redundant second multiplication.

Analysis

7. Explain why register allocation being NP-complete in the general graph-coloring sense doesn't stop real compilers from allocating registers quickly and reasonably well in practice. Answer guidance: Compilers don't solve graph coloring exactly/optimally; they use fast heuristic algorithms (e.g., Chaitin-style graph-coloring allocators, or linear-scan allocators used in just-in-time compilers) that find good-enough colorings quickly, accepting occasional extra spills rather than guaranteeing a minimal number. This tradeoff favors reasonable compile times over perfect allocation.

8. Compare machine-independent and machine-dependent optimizations in terms of when a compiler team would invest effort in each, given that a compiler might target multiple CPU architectures. Answer guidance: Machine-independent optimizations (constant folding, dead code elimination, CSE) are written once against the IR and benefit every target the compiler supports, making them high-leverage investments. Machine-dependent optimizations must be reimplemented or tuned per architecture, so compiler teams typically prioritize machine-independent passes first and add machine-specific tuning selectively for performance-critical targets.

FAQ

Does more aggressive optimization always produce faster programs? Usually, but not unconditionally — some optimizations (like aggressive inlining or unrolling) can increase code size enough to hurt instruction-cache performance, and highly optimized code can also be harder to debug because the generated machine code no longer maps cleanly to the source. This is why compilers offer multiple optimization levels (like -O1, -O2, -O3) instead of a single all-or-nothing setting.

Why doesn't the compiler just always allocate every variable to memory and skip the complexity of register allocation? Because memory access is dramatically slower than register access — often by an order of magnitude in latency. Skipping register allocation would produce technically correct but very slow code, defeating a large part of the point of compiling instead of interpreting.

Is optimization guaranteed to preserve program correctness? That's the design goal, and correctness-preserving is the formal requirement for calling something an "optimization" rather than a bug. In practice, compiler bugs in optimization passes do occasionally cause miscompilation, which is why compiler correctness testing (including techniques like differential testing) is its own active area of work.

What's the difference between optimizing the IR and optimizing the final machine code? IR-level optimization is machine-independent and works on a simplified representation, catching general redundancy and waste. Machine code (or "peephole") optimization works on the actual emitted instructions and catches target-specific inefficiencies, like replacing a multiply-by-2 with a cheaper shift-left instruction on architectures where that's faster.

Can code generation and optimization be skipped for interpreted languages? Interpreters that execute source or bytecode directly don't need a traditional code generation phase, but many modern implementations (like JIT compilers in JavaScript engines or the JVM) still perform code generation and optimization at runtime, compiling hot code paths to native machine code on the fly for speed.

Quick Revision

• Code generation is the final compiler phase: it translates (optimized) intermediate representation into target machine code
• The three core sub-tasks are instruction selection, register allocation, and instruction scheduling
• Instruction selection maps IR operations to actual machine instructions, exploiting target-specific capabilities where possible
• Register allocation decides which values live in registers versus memory; overflow is handled by spilling
• Register allocation is commonly modeled as graph coloring, using an interference graph of overlapping live ranges
• Constant folding evaluates constant expressions at compile time; constant propagation substitutes known constant values
• Dead code elimination removes computations whose results are never used
• Common subexpression elimination (CSE) avoids recomputing the same expression when operands haven't changed
• Optimizations are correctness-preserving: they must not change what the program computes, only how efficiently
• Optimization passes are often run repeatedly, since one optimization can expose opportunities for another
• Machine-independent optimizations work on the IR and are portable across targets; machine-dependent ones are ISA-specific
• More optimization isn't always strictly better — it can increase compile time, code size, or hurt debuggability

Related Topics

Prerequisites: Semantic analysis and symbol tables, intermediate representations (three-address code), basic computer architecture (registers, memory hierarchy)

Related Topics: Data flow analysis, graph coloring algorithms, just-in-time (JIT) compilation

Next Topics: Runtime environments and memory management, linking and loading, compiler correctness and testing