CD Notes

Common Subexpression Elimination (CSE) in Compiler Optimization

Detailed guide to common subexpression elimination covering local and global CSE, available expressions analysis, DAG-based detection, and practical optimization examples.

What is CSE?

Common Subexpression Elimination identifies expressions that are computed more than once with the same operand values, and replaces redundant computations with a reference to the previously computed result. It is one of the most effective compiler optimizations, often yielding 10-30% improvement.

Identifying Common Subexpressions

An expression E is a common subexpression at point P if

1. E was previously computed at point Q

2. None of the operands of E have been modified between Q and P

Example

t1 = a + b ← first computation of (a + b)

t2 = a - c

t3 = a + b ← COMMON! Same as t1, a and b unchanged

t4 = t1 * t3 can be optimized to: t4 = t1 * t1

Before CSE: After CSE:

t1 = a + b t1 = a + b

t2 = a - c t2 = a - c

t3 = a + b t3 = t1 ← reuse t1

t4 = t1 * t3 t4 = t1 * t1

Local CSE Using DAGs

Within a basic block, DAGs naturally detect common subexpressions:

Code

a = b + c

d = b + c

e = a + d

DAG construction

Step 1: a = b + c

[+] → a

/ \

[b] [c]

Step 2: d = b + c (same + node exists with same children!)

[+] → a, d ← d points to SAME node

/ \

[b] [c]

Step 3: e = a + d (both operands point to same node!)

[+] → e ← this is actually a+a = 2*a

[+] → a, d

/ \

[b] [c]

Optimized code from DAG

a = b + c

d = a (copy instead of recomputation)

e = a + a (or e = a + d, same thing)

Algorithm for Local CSE

Algorithm	Value Numbering (local CSE)
3. If YES	x gets same value number, replace with copy
4. If NO	create new entry, assign new value number to x
a = b + c VN: b=1, c=2, (+=,1,2)	3, a=3
d = b + c VN lookup: (+,1,2) exists	value 3! d=3, emit: d=a
e = d + b VN: (+,3,1)	new value 4, e=4
f = a + b VN lookup: (+,3,1) exists	value 4! f=4, emit: f=e

Global CSE: Available Expressions

For CSE across basic blocks, we need Available Expressions analysis:

An expression e is AVAILABLE at point P if

- On EVERY path from program entry to P, e is computed

- AND none of its operands are redefined after that computation

Dataflow equations

AVAIL_IN[B] = ∩ AVAIL_OUT[P] for all predecessors P

AVAIL_OUT[B] = (AVAIL_IN[B] - KILL[B]) ∪ GEN[B]

GEN[B] = expressions computed in B with operands not later redefined in B

KILL[B] = expressions whose operands are defined in B

Example

┌─────┐

│ B1 │

│a=b+c│ GEN={b+c}

└──┬──┘

┌───┴───┐

┌────┐ ┌────┐

│ B2 │ │ B3 │

│d=b+c│ │b=7 │ KILL={b+c, b+d, ...}

└──┬─┘ └──┬─┘

└──────┬──────┘

┌───┴──┐

│ B4 │

│e=b+c │ ← Is b+c available here?

└──────┘

Analysis

AVAIL_OUT[B1] = {b+c}

AVAIL_OUT[B2] = {b+c} (b+c generated, operands unchanged)

AVAIL_OUT[B3] = {} (b redefined, kills b+c)

AVAIL_IN[B4] = AVAIL_OUT[B2] ∩ AVAIL_OUT[B3] = {b+c} ∩ {} = {}

b+c is NOT available at B4 (because path through B3 redefines b)

Cannot eliminate e = b+c in B4.

Global CSE with Temporaries

B1		B1
...		t=b+c
x=b+c		x=t
B2		B2
...		...

CSE in Loops

Example

Before CSE: After CSE: for (i = 0; i < n; i++) { t = b * c; // loop invariant CSE a[i] = b * c + i; for (i = 0; i < n; i++) { } a[i] = t + i; } // b*c computed n times! // b*c computed once! More complex loop example: for (i=0; i<n; i++) { x = a[i] + b[i]; // array access involves addr calc y = a[i] * 2; // a[i] is common with line above } After CSE: for (i=0; i<n; i++) { t = a[i]; // load once x = t + b[i]; y = t * 2; // reuse loaded value }

Algebraic Identities and CSE

CSE can be enhanced by recognizing algebraic equivalences:

Example

Commutativity: a+b = b+a, a*b = b*a t1 = a + b t2 = b + a ← same as t1 (commutative) Strength reduction interaction: t1 = i * 4 t2 = i << 2 ← equivalent to t1 (strength-reduced form) Both should be recognized as common by a smart CSE pass.

Limitations of CSE

Example

1. May increase register pressure: Before: x = a+b; ... (large gap) ...; y = a+b After: t = a+b; x = t; ... (t must stay in register!) ...; y = t If register pressure is already high, spilling t costs more than recomputing. 2. Cannot cross redefinitions: t1 = a + b a = 5 ← redefines a t2 = a + b ← NOT common (different 'a') 3. Pointer aliasing problems: t1 = *p + *q *r = 10 ← might r alias p or q? Conservatively, yes. t2 = *p + *q ← might not be common if *p or *q changed!

CSE Implementation with Hash Tables

Example

Data structure: Hash map from (operator, operand1, operand2) → value hash_key(op, v1, v2): // Canonicalize commutative ops if is_commutative(op) and v1 > v2: swap(v1, v2) return hash(op, v1, v2) Process instruction "x = y op z": vy = value_number[y] vz = value_number[z] key = hash_key(op, vy, vz) if key in table: // Common subexpression found! value_number[x] = table[key] replace instruction with: x = representative[table[key]] else: vx = new_value_number() table[key] = vx value_number[x] = vx representative[vx] = x

Interview Questions

Q: What is the difference between local and global CSE?

A: Local CSE works within a single basic block using value numbering (simple, no control flow). Global CSE works across blocks using available expressions dataflow analysis (must ensure expression is computed on ALL paths to the point). Global CSE requires inserting temporary variables to carry values across blocks.

Q: How does pointer aliasing affect CSE?

A: If two pointers might alias (point to same memory), a store through one may invalidate expressions involving the other. Example: after *p = 5, the compiler cannot assume *q still has its old value. Conservative alias analysis limits CSE effectiveness — expressions involving pointed-to values are killed by any potentially aliasing store.

Q: Can CSE increase register pressure? When is it not profitable?

A: Yes. CSE replaces recomputation with a saved value that must remain live (in a register or stack slot). If the live range is long and registers are scarce, the spill cost may exceed the recomputation cost. This is especially true for cheap operations (single ADD) with long distances between uses.

Q: How does CSE interact with other optimizations?

A: CSE enables dead code elimination (redundant computation becomes dead), reduces instruction count (fewer operations to schedule), and interacts with loop invariant code motion (loop-invariant CSEs should be hoisted). Constant propagation can expose new CSE opportunities by making operands identical.

Q: What is the time complexity of local CSE vs global CSE?

A: Local CSE using value numbering is O(n) where n is instructions in the block (hash table lookups). Global CSE requires dataflow analysis: O(n × e) where e is edges in CFG, iterated to fixed point. In practice, convergence is fast (2-3 iterations), making it O(n) for typical programs.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Common Subexpression Elimination (CSE) in Compiler Optimization.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, optimization, common, subexpression

Continue learning this concept

Code OptimizationDead Code Elimination in Compiler OptimizationComplete guide to dead code elimination covering unreachable code, useless computations, liveness analysis, and aggressive dead code elimination techniques in compiler optimization.Code OptimizationIntroduction to Code Optimization in Compiler DesignComprehensive introduction to compiler code optimization covering optimization levels, classification, basic blocks, control flow graphs, and the role of optimization in the compilation pipeline.Code OptimizationConstant Folding Optimization in Compiler DesignComplete guide to constant folding optimization covering compile-time evaluation, constant expressions, type handling, and interaction with other optimizations in the compilation pipeline.Code OptimizationConstant Propagation in Compiler OptimizationComplete guide to constant propagation optimization covering forward analysis, conditional constant propagation, lattice framework, and practical implementation with dataflow analysis.Code OptimizationGlobal Optimization Techniques in Compiler DesignComprehensive guide to global (intraprocedural) optimization techniques including dataflow analysis frameworks, reaching definitions, live variables, and global optimization passes.Code OptimizationLocal Optimization Techniques in Compiler DesignGuide to local optimization within basic blocks covering algebraic simplification, constant folding, copy propagation, dead code elimination, and DAG-based optimization approaches.

PreviousIntroduction to Code Optimization in Compiler Design NextConstant Folding Optimization in Compiler Design

CD Notes

Common Subexpression Elimination (CSE) in Compiler Optimization

Detailed guide to common subexpression elimination covering local and global CSE, available expressions analysis, DAG-based detection, and practical optimization examples.

What is CSE?

Identifying Common Subexpressions

An expression E is a common subexpression at point P if

1. E was previously computed at point Q

2. None of the operands of E have been modified between Q and P

Example

t1 = a + b ← first computation of (a + b)

t2 = a - c

t3 = a + b ← COMMON! Same as t1, a and b unchanged

t4 = t1 * t3 can be optimized to: t4 = t1 * t1

Before CSE: After CSE:

t1 = a + b t1 = a + b

t2 = a - c t2 = a - c

t3 = a + b t3 = t1 ← reuse t1

t4 = t1 * t3 t4 = t1 * t1

Local CSE Using DAGs

Within a basic block, DAGs naturally detect common subexpressions:

Code

a = b + c

d = b + c

e = a + d

DAG construction

Step 1: a = b + c

[+] → a

/ \

[b] [c]

Step 2: d = b + c (same + node exists with same children!)

[+] → a, d ← d points to SAME node

/ \

[b] [c]

Step 3: e = a + d (both operands point to same node!)

[+] → e ← this is actually a+a = 2*a

[+] → a, d

/ \

[b] [c]

Optimized code from DAG

a = b + c

d = a (copy instead of recomputation)

e = a + a (or e = a + d, same thing)

Algorithm for Local CSE

Algorithm	Value Numbering (local CSE)
3. If YES	x gets same value number, replace with copy
4. If NO	create new entry, assign new value number to x
a = b + c VN: b=1, c=2, (+=,1,2)	3, a=3
d = b + c VN lookup: (+,1,2) exists	value 3! d=3, emit: d=a
e = d + b VN: (+,3,1)	new value 4, e=4
f = a + b VN lookup: (+,3,1) exists	value 4! f=4, emit: f=e

Global CSE: Available Expressions

For CSE across basic blocks, we need Available Expressions analysis:

An expression e is AVAILABLE at point P if

- On EVERY path from program entry to P, e is computed

- AND none of its operands are redefined after that computation

Dataflow equations

AVAIL_IN[B] = ∩ AVAIL_OUT[P] for all predecessors P

AVAIL_OUT[B] = (AVAIL_IN[B] - KILL[B]) ∪ GEN[B]

GEN[B] = expressions computed in B with operands not later redefined in B

KILL[B] = expressions whose operands are defined in B

Example

┌─────┐

│ B1 │

│a=b+c│ GEN={b+c}

└──┬──┘

┌───┴───┐

┌────┐ ┌────┐

│ B2 │ │ B3 │

│d=b+c│ │b=7 │ KILL={b+c, b+d, ...}

└──┬─┘ └──┬─┘

└──────┬──────┘

┌───┴──┐

│ B4 │

│e=b+c │ ← Is b+c available here?

└──────┘

Analysis

AVAIL_OUT[B1] = {b+c}

AVAIL_OUT[B2] = {b+c} (b+c generated, operands unchanged)

AVAIL_OUT[B3] = {} (b redefined, kills b+c)

AVAIL_IN[B4] = AVAIL_OUT[B2] ∩ AVAIL_OUT[B3] = {b+c} ∩ {} = {}

b+c is NOT available at B4 (because path through B3 redefines b)

Cannot eliminate e = b+c in B4.

Global CSE with Temporaries

B1		B1
...		t=b+c
x=b+c		x=t
B2		B2
...		...

CSE in Loops

Example

Algebraic Identities and CSE

CSE can be enhanced by recognizing algebraic equivalences:

Example

Limitations of CSE

Example

CSE Implementation with Hash Tables

Example

Interview Questions

Q: What is the difference between local and global CSE?

Q: How does pointer aliasing affect CSE?

Q: Can CSE increase register pressure? When is it not profitable?

Q: How does CSE interact with other optimizations?

Q: What is the time complexity of local CSE vs global CSE?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Common Subexpression Elimination (CSE) in Compiler Optimization.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, optimization, common, subexpression

Continue learning this concept

PreviousIntroduction to Code Optimization in Compiler Design NextConstant Folding Optimization in Compiler Design