PadhaikoAll subjects

Code Generation

Compiler Design (ENCT 326)

Open in the Padhaiko app

5.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

Factors Affecting Code Generator Design
FactorCore Design Decisions & Impact
Input to the Code GeneratorForm 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 FormatAbsolute 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 ManagementMapping symbol table identifiers and temporaries to static addresses, stack frame offsets, or global registers
Instruction SelectionChoosing 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 & AssignmentDeciding which values reside in scarce CPU registers (allocation) and which specific physical register holds each value (assignment); optimal general assignment is NP-complete
Evaluation OrderScheduling 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.

Definition

Basic Block

A basic block is a maximal sequence of consecutive three-address instructions with the following properties:

  1. Control may enter the block only at its first instruction (no jumps into the middle of the block).
  2. 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

  1. 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.
  2. 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:

5.2.3 Flow Graphs

Definition

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 :


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:

5.3.2 Local Transformations Enabled by the Basic-Block DAG

Basic Block Optimizations via DAG
TransformationMechanism in DAGExample
Common Subexpression EliminationValue-numbering reuses an existing (op, left, right) node instead of recomputingt1 = a + b; t2 = a + b shares one + node
Dead-Code EliminationAny root node (no parent) whose attached identifiers are all dead on block exit can be removed iterativelyRemoving unused temporary assignments
Algebraic Identities & Constant FoldingSimplifying trivial operations or evaluating constant operands at compile time, ,
Strength ReductionReplacing costly operations with cheaper equivalents or shift left;

Array References, Pointers, and Procedure Calls in DAGs

DAG construction must preserve memory aliasing safety:

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:

  1. Register Descriptor: For each register Ri, lists all variables whose current value is presently held in Ri. Initially empty at the start of a basic block.
  2. Address Descriptor: For each variable x, lists all locations (memory address and/or registers Ri) where x'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:

  1. If y is not in a register, emit LD Ry, y into a free register (or spill a register first).
  2. Choose destination register Rx in priority order:
    • If y is in register Ry and y has no next use and is dead, reuse Ry as Rx (avoiding an extra copy or spill).
    • Otherwise, pick an empty register if available.
    • Otherwise, spill a register R whose variables either already have a valid copy in memory, are dead, or have the farthest next use (emit ST v, R if v's memory copy is stale).
  3. Emit OP Rx, Ry, Rz (or OP Rx, Ry, z if z can be addressed directly from memory).
  4. Update descriptors: Rx holds only x; x's address descriptor is {Rx} (removing its stale memory location until stored).
  5. At the end of the basic block, emit ST v, R for every variable v that 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:

  1. 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.
  2. Assign physical registers by finding a -coloring of (adjacent nodes receive distinct colors).
  3. 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 :

Bottom-Up Cost Computation

Assume unit cost for each load, store, and binary operation (or machine-specific weights):

  1. Leaf Node (memory operand M):
    • (already in memory).
    • for (requires one LD Ri, M instruction).
  2. Interior Binary Node :
    • Into registers (): Consider all valid evaluation strategies and pick the minimum cost:
      1. Evaluate into a register using registers, then evaluate into a register using the remaining registers (requires ), then execute op:
  1. Evaluate first using registers, then using registers (requires ), then execute op:
  1. 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).

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

Example 1

1

Partition the following three-address code (computing a dot-product loop) into basic blocks and construct its control-flow graph:

Three-Address CodeText
(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 jump if 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 * i through (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 ENTRY and EXIT sentinel nodes gives ENTRY -> B1 -> B2 -> EXIT alongside the self-loop B2 -> B2.
Answer:

There are leaders ((1) and (3)), forming basic blocks (, ) with CFG edges and loop back-edge .

Example 2

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:

Basic Block TACText
t = a - b
u = a - c
v = t + u
d = v + u

Track 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).

  1. t = a - b: a is not in a register. Emit LD R0, a and SUB R0, R0, b ( instructions).
    • Register descriptors: R0 = {t}, R1 = {}.
    • Address descriptors: t = {R0}, a, b, c, d = {mem}.
  2. u = a - c: t in R0 is still needed later, so allocate free register R1. Emit LD R1, a and SUB R1, R1, c ( instructions).
    • Register descriptors: R0 = {t}, R1 = {u}.
    • Address descriptors: t = {R0}, u = {R1}.

Statements 3 and 4 (v = t + u, d = v + u) and Exit Store:

  1. v = t + u: t has no further use after this statement, so getReg reuses R0 for v. Emit ADD R0, R0, R1 ( instruction).
    • Register descriptors: R0 = {v}, R1 = {u}.
    • Address descriptors: v = {R0}, u = {R1} (t is dead).
  2. d = v + u: v has no further use, so reuse R0 for d. Emit ADD R0, R0, R1 ( instruction).
    • Register descriptors: R0 = {d}, R1 = {u}.
    • Address descriptors: d = {R0} (note: memory copy of d is now stale!).
  3. Block Exit: Since d is live on exit and its only current copy is in R0, emit ST d, R0 ( instruction).

Total instructions .

Answer:

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.

Example 3

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 by SUB R, R, b (, memory-operand cost ) gives and .
    • Storing into memory gives .
    • Thus .

Right Subtree and :

  • Symmetrically, has .
  • For :
    • With register: must evaluate into a memory temporary (), load c (), and MUL R0, R0, T (), giving .
    • With registers: evaluate first using registers (), evaluate c using register (), and MUL R0, R0, R1 (), giving .
    • Into memory: .
    • Thus .

Root and Optimal Code Emission:

  • .
  • Optimal code sequence ( instructions):
Optimal Code for (a - b) + c * (d / e)Text
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 result
Answer:

The DP cost vectors are , , , and . The optimal code evaluates first, requiring instructions with zero memory spills.


Exercises

Practice Exercises — Code Generation

Question 1

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:

  1. Input IR: Whether the code generator receives linear TAC, ASTs, or DAGs determines how easily it spots common subexpressions and addressing idioms.
  2. Target Program Form: Generating assembly vs. relocatable object code vs. absolute machine code trades compile-time speed against portability and linkability.
  3. Instruction Selection: Mapping IR operations onto target ISA instructions. Example: translating x = x + 1 as INC x instead of LD R0, x; ADD R0, R0, #1; ST x, R0 reduces code size and memory cycles.
  4. Evaluation Order: Choosing the order of independent subtrees alters register pressure. Example: in (a + b) + c * (d + e), evaluating c * (d + e) first requires fewer simultaneous live registers than evaluating (a + b) first and holding it across c * (d + e).
Answer:

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).

Question 2

Partition the following three-address code fragment into basic blocks, identify all leaders, and list the directed edges of its control-flow graph:

TAC FragmentText
(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 = sum

Identifying Leaders:

  • (1): Leader by Rule 1 (first instruction).
  • (3): Leader by Rule 2 (target of goto (3) at line (7)).
  • (4): Leader by Rule 3 (immediately follows conditional jump at line (3)).
  • (8): Leader by Rule 2 (target of if i >= n goto (8) at line (3)) and Rule 3 (follows goto (7)).

Basic Blocks and CFG Edges:

Edges:

  • (fall-through)
  • (conditional jump when i >= n)
  • (fall-through when i < n)
  • (unconditional back-edge goto (3))
Answer:

There are leaders ((1), (3), (4), (8)), producing basic blocks () with CFG edges: , , , and .

Question 3

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:

Basic BlockText
t1 = a + b
t2 = a + b
t3 = t1 * c
t4 = t2 + c
d  = t3 + t4

Building the DAG:

  1. t1 = a + b: Create leaves a0, b0, and node with attached list {t1}.
  2. t2 = a + b: Matches existing node ! Attach t2 to {t1, t2}.
  3. t3 = t1 * c: Create leaf c0 and node with {t3}.
  4. t4 = t2 + c: Since t2 points to , create with {t4}.
  5. d = t3 + t4: Create root node with {d}.

Eliminating Redundancy and Reassembling:

  • Node computes a + b once and feeds both and ; t2 is completely eliminated.
  • Every remaining node (n1, n2, n3, n4) is an ancestor of live-on-exit d, so no further nodes are dead.
  • Optimized TAC ( instructions instead of ):
Optimized Basic BlockText
t1 = a + b
t3 = t1 * c
t4 = t1 + c
d  = t3 + t4
Answer:

Value 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).

Question 4
  1. Compute the global register-allocation savings across a two-block loop for variables x and y, given:
    • x has , , , .
    • y has , , , .
  2. 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 .

Answer:

and , so y gets register priority. Graph coloring models simultaneous liveness as edges in an interference graph and assigns registers via -coloring.

Question 5

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, d each have .
  • Left subtree : , , .
  • Right subtree : identically .

Root Node and Code Emission:

  • For registers:

Minimum .

  • For register: .
  • For (memory): .
  • Optimal -instruction sequence:
Optimal Code for (a + b) * (c - d)Text
LD  R0, a
ADD R0, R0, b
LD  R1, c
SUB R1, R1, d
MUL R0, R0, R1
Answer:

The 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.

← Syntax-Directed Translation and Semantic Analysis (part 2: 4.5–4.8)Code Optimization →