Code Optimization

Optimization improves the intermediate code so it runs faster or uses less memory, without changing what the program does.

Basic Blocks and Flow Graphs

A basic block is a maximal sequence of statements with one entry and one exit. Leaders are: (1) the first statement, (2) any target of a jump, (3) any statement immediately after a jump.

Optimization Techniques

Technique	Before	After
Constant folding	x = 2 * 3.14	x = 6.28
Constant propagation	n = 5; y = n * 2	y = 10
Common subexpression elimination	a = bc; d = bc + e	t = b*c; a = t; d = t + e
Copy propagation	x = y; z = x + 1	z = y + 1
Dead code elimination	if (false) {...}	(removed)
Strength reduction	x * 2, i * 4 in loop	x + x, t = t + 4
Loop-invariant code motion	for(...) { y = a*b; ... }	y = a*b; for(...) {...}
Loop unrolling	for i in 0..3: s += a[i]	s += a[0]+a[1]+a[2]+a[3]

DAG for a Basic Block

Text

a = b + c
b = a - d
c = b + c
d = a - d       ← same as line 2 (a - d already computed)  ⇒  d = b

Optimized:
a = b + c
b = a - d
c = b + c
d = b

Peephole Optimization

Examines a small window of target code to remove redundant loads and stores, eliminate unreachable code, simplify jump chains and apply algebraic simplifications (x + 0 → x).

Text

MOV R0, a
MOV a, R0      ← redundant (a already in R0): delete

Track your progress through the Compiler Design course

← Prev Next →