Code Generation
Open in the Padhaiko app5.1 Factors affecting a code generator
The code generator is the final phase of the compiler back-end. It takes an intermediate representation (IR) of the source program—along with symbol table metadata—and produces an equivalent target program. Designing an effective code generator requires balancing three goals: correctness (preserving source semantics), target code efficiency (fast execution and small code footprint), and compilation speed.
5.1.1 Primary Design Factors
| Factor | Core Design Decisions & Impact |
|---|---|
| Input to the Code Generator | Form of the IR (Three-Address Code quadruples/triples, bytecode, ASTs, or DAGs) and assumption that syntactic and static semantic checks have already succeeded |
| Target Program Format | Absolute machine language (loads at fixed address, fast for student compilers), relocatable object module (allows separate compilation and linking), or assembly language (human-readable, delegates binary encoding to assembler) |
| Memory Management | Mapping symbol table identifiers and temporaries to static addresses, stack frame offsets, or global registers |
| Instruction Selection | Choosing target machine idioms to implement each IR operator; depends on target ISA uniformity, addressing modes, and instruction latencies (e.g., using INC R0 instead of ADD R0, #1) |
| Register Allocation & Assignment | Deciding which values reside in scarce CPU registers (allocation) and which specific physical register holds each value (assignment); optimal general assignment is NP-complete |
| Evaluation Order | Scheduling independent subexpressions and instructions to minimize live register count (register pressure) and avoid pipeline stalls |
5.2 Basic blocks and flow graphs
To perform local optimizations and register allocation systematically, linear Three-Address Code (TAC) is partitioned into straight-line segments called basic blocks, which are linked into a control-flow graph.
Basic Block
A basic block is a maximal sequence of consecutive three-address instructions with the following properties:
- Control may enter the block only at its first instruction (no jumps into the middle of the block).
- Control leaves the block only after its last instruction, without halting or branching except possibly at the final instruction.
5.2.1 Algorithm to Partition TAC into Basic Blocks
- Identify Leaders (the first instructions of basic blocks):
- Rule 1: The first three-address instruction in the intermediate code is a leader.
- Rule 2: Any instruction that is the target of a conditional or unconditional jump (
goto,if ... goto) is a leader. - Rule 3: Any instruction that immediately follows a conditional or unconditional jump is a leader.
- Construct Basic Blocks: For each leader, its basic block consists of the leader itself and all subsequent instructions up to, but not including, the next leader (or the end of the program).
5.2.2 Next-Use and Liveness Information
Before generating machine instructions for a basic block, the compiler determines whether a variable's current value will be read again before it is overwritten:
- Live Variable: Variable is live at statement if its current value at may be read along some path after before is redefined. Variables live on exit from a block must be stored back to memory if currently held only in a register.
- Next-Use: Instruction uses variable computed at instruction () if there is no intervening assignment to between and . Scanning a basic block backward from its last instruction to its first records exact next-use and liveness attributes for every statement in a single linear pass.
5.2.3 Flow Graphs
Control-Flow Graph (CFG)
A flow graph (or control-flow graph) is a directed graph whose nodes are the basic blocks of a procedure (plus distinguished ENTRY and EXIT sentinel nodes). There is a directed edge if and only if block can execute immediately after block :
- Jump edge: The last instruction of is a conditional or unconditional jump targeting the leader of .
- Fall-through edge: immediately follows in lexical order, and does not end with an unconditional jump (
gotoorreturn).
5.3 Optimization of basic blocks
Many inefficiencies in generated code arise locally within individual basic blocks. Representing a basic block as a Directed Acyclic Graph (DAG) exposes these opportunities automatically.
5.3.1 DAG Representation of a Basic Block
A DAG for a basic block is constructed sequentially from its TAC statements:
- Leaf nodes represent initial values of variables on entry to the block (labeled , ) or constants.
- Interior nodes represent operators applied to child nodes, and each node carries a list of attached variable names that currently hold that node's value.
- When an instruction
x = y op zis processed:- Look up the current nodes for operands
yandz. - Search for an existing node with operator
opand identical children (commutative operators check both orders). If none exists, create one. - Detach
xfrom any previous node's identifier list and attachxto the new (or matched) node.
- Look up the current nodes for operands
5.3.2 Local Transformations Enabled by the Basic-Block DAG
| Transformation | Mechanism in DAG | Example |
|---|---|---|
| Common Subexpression Elimination | Value-numbering reuses an existing (op, left, right) node instead of recomputing | t1 = a + b; t2 = a + b shares one + node |
| Dead-Code Elimination | Any root node (no parent) whose attached identifiers are all dead on block exit can be removed iteratively | Removing unused temporary assignments |
| Algebraic Identities & Constant Folding | Simplifying trivial operations or evaluating constant operands at compile time | , , |
| Strength Reduction | Replacing costly operations with cheaper equivalents | or shift left; |
Array References, Pointers, and Procedure Calls in DAGs
DAG construction must preserve memory aliasing safety:
- Writing to an array element
a[i] = vcreates a special[]=node that kills all previously constructed reads ofa[...]unless static analysis proves the indices cannot alias. - Writing through a pointer
*p = vor calling a procedurecall f()conservatively kills nodes whose variables might be modified via aliasing or global state.
Reassembling the Basic Block
Once dead nodes are pruned, the optimized basic block is reconstructed by listing interior nodes in a topological order (children before parents) that keeps live-on-exit identifiers attached to distinct live variables.
5.4 Register allocation and assignment
CPU registers are the fastest storage tier, yet their number is strictly limited (typically to general-purpose registers). Register allocation selects which variables live in registers at each program point, and register assignment binds each selected variable to a specific physical register.
5.4.1 Register and Address Descriptors
A simple local code generator tracks dynamic register contents using two runtime-model tables updated at every generated instruction:
- Register Descriptor: For each register
Ri, lists all variables whose current value is presently held inRi. Initially empty at the start of a basic block. - Address Descriptor: For each variable
x, lists all locations (memoryaddress and/or registersRi) wherex's current value can be found.
5.4.2 Local Code Generation Algorithm (getReg)
For a three-address instruction x = y op z, the code generator invokes getReg(x = y op z) to select destination register Rx and operand registers Ry, Rz:
- If
yis not in a register, emitLD Ry, yinto a free register (or spill a register first). - Choose destination register
Rxin priority order:- If
yis in registerRyandyhas no next use and is dead, reuseRyasRx(avoiding an extra copy or spill). - Otherwise, pick an empty register if available.
- Otherwise, spill a register
Rwhose variables either already have a valid copy in memory, are dead, or have the farthest next use (emitST v, Rifv's memory copy is stale).
- If
- Emit
OP Rx, Ry, Rz(orOP Rx, Ry, zifzcan be addressed directly from memory). - Update descriptors:
Rxholds onlyx;x's address descriptor is{Rx}(removing its stale memory location until stored). - At the end of the basic block, emit
ST v, Rfor every variablevthat is live on exit and whose only up-to-date copy is in a register.
5.4.3 Global Register Allocation and Graph Coloring
Keeping variables in registers across basic-block boundaries—especially inside inner loops—yields major speedups.
Loop Usage-Count Heuristic
If register R holds variable throughout a loop , each read/write saves memory traffic, while loading before or storing on exit adds fixed cost. The estimated savings of keeping in a register across loop is:
where counts uses of in block prior to any definition in , and if is assigned in and live on exit from (saving a store of cost memory-access units per iteration).
Register Allocation by Graph Coloring
Compilers generalize global register allocation using graph coloring:
- Build a Register Interference Graph (RIG) where each node represents a variable's live range (or symbolic register), and an undirected edge connects and if both are simultaneously live at some program point.
- Assign physical registers by finding a -coloring of (adjacent nodes receive distinct colors).
- Chaitin's Simplification Heuristic: While contains a node with degree , push onto a stack and remove and its edges from (since 's neighbors use at most colors, is guaranteed to be colorable later). If every remaining node has degree , select a spill candidate (typically one with lowest spill cost or highest degree), mark it for memory spilling, and repeat; finally, pop nodes off the stack and assign valid colors.
5.5 Dynamic programming code-generation algorithm
For expression trees on architectures with interchangeable general-purpose registers (where instructions take the forms Ri = M, Ri = Ri op Rj, Ri = Ri op M, and Ri = op Ri), the Aho–Johnson dynamic programming algorithm produces provably minimum-cost code in time.
5.5.1 Contiguous Evaluation Property
A key theorem proves that any optimal code sequence for an expression tree can be transformed into an equal-cost contiguous sequence in which every subtree is evaluated completely without interleaving instructions from sibling subtrees—provided intermediate subtree values may be spilled into memory when registers run out.
5.5.2 The Three Phases of the Dynamic Programming Algorithm
Let the target machine have registers . For every node in the expression tree, we compute a cost vector :
- (): minimum cost to evaluate the subtree rooted at into a register, assuming registers are available (and the result remains in one of those registers).
- : minimum cost to evaluate the subtree rooted at into a memory temporary (with all registers available for the computation, followed by a store
ST T, Ri).
Bottom-Up Cost Computation
Assume unit cost for each load, store, and binary operation (or machine-specific weights):
- Leaf Node (memory operand
M):- (already in memory).
- for (requires one
LD Ri, Minstruction).
- Interior Binary Node :
- Into registers (): Consider all valid evaluation strategies and pick the minimum cost:
- Evaluate into a register using registers, then evaluate into a register using the remaining registers (requires ), then execute
op:
- Evaluate into a register using registers, then evaluate into a register using the remaining registers (requires ), then execute
- Into registers (): Consider all valid evaluation strategies and pick the minimum cost:
- Evaluate first using registers, then using registers (requires ), then execute
op:
- Evaluate into a memory temporary (with all registers available, cost ), then evaluate into a register using registers, then execute
Ri = Ri op T:
Set (omitting options with where invalid).
- Into memory (): Evaluate into a register using all registers, then store to memory:
Top-Down Code Generation
Starting at the root with available registers (), traverse the tree top-down following the recorded winning choices at each node to emit optimal target instructions in exact execution order.
Worked Examples
1
Partition the following three-address code (computing a dot-product loop) into basic blocks and construct its control-flow graph:
(1) prod = 0
(2) i = 1
(3) t1 = 4 * i
(4) t2 = a[t1]
(5) t3 = 4 * i
(6) t4 = b[t3]
(7) t5 = t2 * t4
(8) t6 = prod + t5
(9) prod = t6
(10) t7 = i + 1
(11) i = t7
(12) if i <= 20 goto (3)Identify every leader with the rule that selects it, list the basic blocks, and state the CFG edges.
Identifying Leaders:
- Instruction
(1): Leader by Rule 1 (first instruction of the program). - Instruction
(3): Leader by Rule 2 (target of the conditional jumpif i <= 20 goto (3)at line(12)). - No instruction follows
(12), so Rule 3 adds no additional leader.
Total leaders .
Forming Basic Blocks:
- (lines
1–2):(1) prod = 0,(2) i = 1. - (lines
3–12):(3) t1 = 4 * ithrough(12) if i <= 20 goto (3).
Constructing the Control-Flow Graph (CFG):
- Fall-through edge : ends at
(2)without a jump, so control falls through to . - Loop back-edge : Line
(12)conditionally jumps to leader(3)at the top of . - Including
ENTRYandEXITsentinel nodes givesENTRY -> B1 -> B2 -> EXITalongside the self-loopB2 -> B2.
There are leaders ((1) and (3)), forming basic blocks (, ) with CFG edges and loop back-edge .
2
Generate target machine instructions (using LD, ST, ADD, SUB with registers R0 and R1) for the basic block below, assuming only d is live on exit:
t = a - b
u = a - c
v = t + u
d = v + uTrack the Register Descriptor and Address Descriptor after every statement, and determine the total number of generated machine instructions.
Statements 1 and 2 (t = a - b, u = a - c): Initially both registers are empty; variables a, b, c, d are in memory (mem).
t = a - b:ais not in a register. EmitLD R0, aandSUB R0, R0, b( instructions).- Register descriptors:
R0 = {t},R1 = {}. - Address descriptors:
t = {R0},a, b, c, d = {mem}.
- Register descriptors:
u = a - c:tinR0is still needed later, so allocate free registerR1. EmitLD R1, aandSUB R1, R1, c( instructions).- Register descriptors:
R0 = {t},R1 = {u}. - Address descriptors:
t = {R0},u = {R1}.
- Register descriptors:
Statements 3 and 4 (v = t + u, d = v + u) and Exit Store:
v = t + u:thas no further use after this statement, sogetRegreusesR0forv. EmitADD R0, R0, R1( instruction).- Register descriptors:
R0 = {v},R1 = {u}. - Address descriptors:
v = {R0},u = {R1}(tis dead).
- Register descriptors:
d = v + u:vhas no further use, so reuseR0ford. EmitADD R0, R0, R1( instruction).- Register descriptors:
R0 = {d},R1 = {u}. - Address descriptors:
d = {R0}(note: memory copy ofdis now stale!).
- Register descriptors:
- Block Exit: Since
dis live on exit and its only current copy is inR0, emitST d, R0( instruction).
Total instructions .
The code generator produces target instructions (LD R0, a, SUB R0, R0, b, LD R1, a, SUB R1, R1, c, ADD R0, R0, R1, ADD R0, R0, R1, ST d, R0) with zero register spills.
3
Apply the Aho–Johnson dynamic programming code-generation algorithm to the expression tree for (a - b) + c * (d / e) on a target machine with registers (R0, R1) and instructions Ri = M, Ri = Ri op Rj, Ri = Ri op M (each of unit cost ). Compute the cost vectors bottom-up and emit the optimal instruction sequence.
Leaf Nodes and Left Subtree :
- Every leaf (
a,b,c,d,e) has (cost in memory, cost to load into a register). - For :
- Using
LD R, a() followed bySUB R, R, b(, memory-operand cost ) gives and . - Storing into memory gives .
- Thus .
- Using
Right Subtree and :
- Symmetrically, has .
- For :
- With register: must evaluate into a memory temporary (), load
c(), andMUL R0, R0, T(), giving . - With registers: evaluate first using registers (), evaluate
cusing register (), andMUL R0, R0, R1(), giving . - Into memory: .
- Thus .
- With register: must evaluate into a memory temporary (), load
Root and Optimal Code Emission:
- .
- Optimal code sequence ( instructions):
LD R1, d
DIV R1, R1, e ; R1 holds (d / e)
LD R0, c
MUL R0, R0, R1 ; R0 holds c * (d / e) -- free R1!
LD R1, a
SUB R1, R1, b ; R1 holds (a - b)
ADD R0, R1, R0 ; R0 holds final resultThe DP cost vectors are , , , and . The optimal code evaluates first, requiring instructions with zero memory spills.
Exercises
Practice Exercises — Code Generation
Explain four key factors that affect the design of a compiler's code generator, giving a concrete example of how instruction selection and evaluation order influence target code efficiency.
Four Core Factors:
- Input IR: Whether the code generator receives linear TAC, ASTs, or DAGs determines how easily it spots common subexpressions and addressing idioms.
- Target Program Form: Generating assembly vs. relocatable object code vs. absolute machine code trades compile-time speed against portability and linkability.
- Instruction Selection: Mapping IR operations onto target ISA instructions. Example: translating
x = x + 1asINC xinstead ofLD R0, x; ADD R0, R0, #1; ST x, R0reduces code size and memory cycles. - Evaluation Order: Choosing the order of independent subtrees alters register pressure. Example: in
(a + b) + c * (d + e), evaluatingc * (d + e)first requires fewer simultaneous live registers than evaluating(a + b)first and holding it acrossc * (d + e).
Code generator quality depends on IR input, target output format, memory mapping, instruction selection (matching ISA idioms like INC), register allocation, and evaluation order (minimizing register spills).
Partition the following three-address code fragment into basic blocks, identify all leaders, and list the directed edges of its control-flow graph:
(1) i = 0
(2) sum = 0
(3) if i >= n goto (8)
(4) t1 = a[i]
(5) sum = sum + t1
(6) i = i + 1
(7) goto (3)
(8) result = sumIdentifying Leaders:
(1): Leader by Rule 1 (first instruction).(3): Leader by Rule 2 (target ofgoto (3)at line(7)).(4): Leader by Rule 3 (immediately follows conditional jump at line(3)).(8): Leader by Rule 2 (target ofif i >= n goto (8)at line(3)) and Rule 3 (followsgoto (7)).
Basic Blocks and CFG Edges:
Edges:
- (fall-through)
- (conditional jump when
i >= n) - (fall-through when
i < n) - (unconditional back-edge
goto (3))
There are leaders ((1), (3), (4), (8)), producing basic blocks () with CFG edges: , , , and .
Construct the basic-block DAG for the following four statements, assuming only d is live on exit, and rewrite the optimized TAC after eliminating common subexpressions and dead code:
t1 = a + b
t2 = a + b
t3 = t1 * c
t4 = t2 + c
d = t3 + t4Building the DAG:
t1 = a + b: Create leavesa0,b0, and node with attached list{t1}.t2 = a + b: Matches existing node ! Attacht2to{t1, t2}.t3 = t1 * c: Create leafc0and node with{t3}.t4 = t2 + c: Sincet2points to , create with{t4}.d = t3 + t4: Create root node with{d}.
Eliminating Redundancy and Reassembling:
- Node computes
a + bonce and feeds both and ;t2is completely eliminated. - Every remaining node (
n1,n2,n3,n4) is an ancestor of live-on-exitd, so no further nodes are dead. - Optimized TAC ( instructions instead of ):
t1 = a + b
t3 = t1 * c
t4 = t1 + c
d = t3 + t4Value numbering merges t2 = a + b into t1 = a + b, reducing the block from instructions to instructions (t1 = a + b, t3 = t1 * c, t4 = t1 + c, d = t3 + t4).
- Compute the global register-allocation savings across a two-block loop for variables
xandy, given:xhas , , , .yhas , , , .
- Which variable should receive priority for a single available loop register? Also explain how graph coloring resolves interference among registers.
Computing Loop Register Savings:
- For
x:
- For
y:
Priority and Graph Coloring Explanation: Since , y should receive priority for the loop register. In graph coloring, each live range is a node and an edge connects two nodes if they are simultaneously live. A -coloring ensures no two interfering variables share the same physical register; Chaitin's algorithm iteratively removes nodes with degree onto a stack and assigns colors in reverse order, spilling a node to memory only if all remaining nodes have degree .
and , so y gets register priority. Graph coloring models simultaneous liveness as edges in an interference graph and assigns registers via -coloring.
Using the Aho–Johnson dynamic programming code-generation algorithm with registers (R0, R1) and unit instruction cost (for LD R, M, OP R, R1, R2, OP R, R, M, ST T, R), compute for the expression tree (a + b) * (c - d) and emit the optimal instruction sequence.
Leaf and Child Subtree Costs:
- Leaves
a,b,c,deach have . - Left subtree : , , .
- Right subtree : identically .
Root Node and Code Emission:
- For registers:
Minimum .
- For register: .
- For (memory): .
- Optimal -instruction sequence:
LD R0, a
ADD R0, R0, b
LD R1, c
SUB R1, R1, d
MUL R0, R0, R1The root cost vector is , giving an optimal -instruction sequence (LD R0, a, ADD R0, R0, b, LD R1, c, SUB R1, R1, d, MUL R0, R0, R1) with zero spills.