Course contentsShow
← Computer Science
Lesson 2064 of 2,87246. Compilation and InterpretationFree lesson

Common Subexpression Elimination

Identifying and reusing previously computed expressions to avoid redundant calculations.

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:

  1. Has already been computed earlier in the code
  2. Uses operands whose values haven't changed since the first computation
  3. 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.