Common Subexpression Elimination
What you'll learn: How compilers avoid redundant calculations by recognizing when the same expression is computed multiple times and reusing the result.
The Core Problem
Imagine you're writing code that calculates a * b + c in one statement, then later computes x = a * b + d. Your source code repeats the calculation a * b, but why should the CPU compute it twice if nothing changed between those two points?
Common Subexpression Elimination (CSE) is an optimization that identifies expressions computed more than once with the same operand values, then replaces subsequent computations with a reference to the first result.
How It Works
The compiler analyzes your code looking for identical expressions. When it finds a subexpression that:
- Has already been computed earlier in the code
- Uses operands whose values haven't changed since the first computation
- Isn't affected by any side effects
...it can save the first result in a temporary variable and reuse it, eliminating the redundant work.
Example in Three-Address Code
Before CSE:
t1 = a * b
x = t1 + c
t2 = a * b // redundant!
y = t2 + d
After CSE:
t1 = a * b
x = t1 + c
y = t1 + d // reuses t1
The second a * b multiplication is eliminated entirely.
Think of It Like Cooking
If a recipe needs "chopped onions" in two different steps, you chop all the onions once and set them aside—you don't chop the same onion twice. CSE does the same for computational "ingredients."
Key Takeaway: Common Subexpression Elimination reduces redundant calculations by identifying identical expressions and reusing their computed values, improving both execution speed and code efficiency.