Coursify

Optimization That Eliminates Repeated Computation of the Same Expression: Choosing the Correct Pass

Optimization That Eliminates Repeated Computation of the Same Expression: Choosing the Correct Pass

Verified Sources
Nov 3, 2026

When a program contains the same expression appearing multiple times, an important class of compiler optimizations targets redundancy: avoiding recomputation of an expression when its value can be reused. The optimization that directly eliminates repeated computation of the same expression is Common subexpression elimination—not loop interchange, not dead-code elimination, and not register allocation. 2

Key terms you will use:

  • Common subexpression elimination
  • Dead-code elimination
  • Loop interchange
  • Register allocation

Footnotes

  1. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩

  2. Common Subexpression Elimination - GeeksforGeeks - Explains CSE as computing a repeated subexpression once and reusing it to reduce redundant calculations. ↩

Common Subexpression Elimination (Local) in Compiler Design

Why the answer is (iii) Common subexpression elimination

Common subexpression elimination (CSE) is defined as a compiler optimization that detects redundantly computed expressions and replaces later occurrences with a previously computed temporary/variable. In classical compiler theory, it is based on data-flow notions such as available expressions and is often described as local vs global depending on scope (basic block vs entire procedure). 2

A typical transformation is:

  • Before: compute b∘cb \circ c multiple times at different program points
  • After: compute it once (e.g., tmp = b*c) and reuse tmp at each place where the repeated expression would occur.

This exactly matches the prompt: “Which optimization eliminates repeated computation of the same expression?”

Footnotes

  1. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩

  2. Common subexpression elimination - Wikipedia - Formal description, principle, and examples of CSE; distinguishes local/global based on data-flow analysis. ↩ ↩2

Reuses the value of identical expressions instead of recomputing them.

Distinguishing the four options (what each optimization really does)

How to identify the optimization that targets repeated computation

  1. 1
    Step 1

    If the prompt says the optimization “eliminates repeated computation,” it is pointing to redundancy-removal of the same expression value.

  2. 2
    Step 2

    CSE specifically replaces later occurrences of an identical expression with a previously computed value.

    Footnotes

    1. Common subexpression elimination - Wikipedia - Formal description, principle, and examples of CSE; distinguishes local/global based on data-flow analysis. ↩

  3. 3
    Step 3

    Loop interchange is about rearranging loop nesting for performance (often memory locality). Dead-code elimination removes code that does not affect results (reachability/liveness). Register allocation maps temporaries to CPU registers to reduce memory traffic.

    Footnotes

    1. 3.4: Loop Optimizations - Engineering LibreTexts - Describes loop interchange as rearranging loop nests to improve memory access patterns and performance. ↩

    2. Dead-code elimination - Wikipedia - Defines DCE as removing dead code that doesn’t affect program results, with benefits and examples. ↩

    3. Register allocation - Wikipedia - Defines register allocation as assigning variables/temporaries to processor registers to reduce memory usage (spilling/assignments/coalescing). ↩

  4. 4
    Step 4

    The only choice whose purpose is reuse of computed expression results is (iii) Common subexpression elimination.

    Footnotes

    1. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩

(i) Loop interchange — why it doesn’t match “repeated computation of the same expression”

Loop interchange swaps the order of loops in a loop nest. It is used to change memory access patterns and sometimes to improve performance by making the “right stuff” appear in the inner loop (e.g., better cache behavior).
This optimization does not inherently detect identical expressions and replace them with a reused temporary—so it does not directly eliminate repeated computation of the same expression.

Footnotes

  1. 3.4: Loop Optimizations - Engineering LibreTexts - Describes loop interchange as rearranging loop nests to improve memory access patterns and performance. ↩

(ii) Dead-code elimination only — why it doesn’t match

Dead-code elimination (DCE) removes code that is provably unnecessary because it doesn’t affect observable program behavior (e.g., unreachable code or computations whose results are never used).

Even if repeated computation becomes “dead” in some cases, DCE is not the targeted redundancy-removal mechanism described in the prompt. The prompt asks for eliminating repeated computation of the same expression, which is the hallmark of CSE. 2

Footnotes

  1. Dead-code elimination - Wikipedia - Defines DCE as removing dead code that doesn’t affect program results, with benefits and examples. ↩

  2. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩

  3. Common subexpression elimination - Wikipedia - Formal description, principle, and examples of CSE; distinguishes local/global based on data-flow analysis. ↩

(iii) Common subexpression elimination — the direct answer

Common subexpression elimination (CSE) is defined as replacing redundantly computed expressions with a stored value so the expression is computed only once. 2

This is exactly:

  • Identify identical expressions occurring multiple times
  • Ensure operands haven’t changed in between (via availability/data-flow analysis)
  • Reuse a previously computed temporary instead of recomputing. 2

Footnotes

  1. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩ ↩2

  2. Common subexpression elimination - Wikipedia - Formal description, principle, and examples of CSE; distinguishes local/global based on data-flow analysis. ↩ ↩2

(iv) Register allocation — why it doesn’t match

Register allocation assigns variables/temporaries to the limited set of CPU registers to reduce memory accesses. It aims to keep values in registers rather than on the stack/memory.

This changes where values are stored (register vs memory), not whether a repeated expression is recomputed. Therefore, it is not the optimization that specifically eliminates repeated computation of the same expression.

Footnotes

  1. Register allocation - Wikipedia - Defines register allocation as assigning variables/temporaries to processor registers to reduce memory usage (spilling/assignments/coalescing). ↩ ↩2

Which optimization targets “repeated computation of the same expression”?

Scores reflect direct alignment with the prompt’s redundancy-reuse goal (higher = more direct match).

Pro tip for exam-style questions

If you see phrases like “repeated,” “redundant,” “compute once,” or “reuse the previously computed value,” think Common subexpression elimination first.

Footnotes

  1. Common Subexpression Elimination - Cornell CS course notes - Defines CSE as replacing redundantly computed expressions with a temporary and reusing it. ↩

Common confusion: redundancy vs unused code vs storage

CSE prevents recomputation of identical expressions. Dead-code elimination removes unused effects/results. Register allocation reduces memory traffic. These are related but not interchangeable. 2

Footnotes

  1. Dead-code elimination - Wikipedia - Defines DCE as removing dead code that doesn’t affect program results, with benefits and examples. ↩

  2. Register allocation - Wikipedia - Defines register allocation as assigning variables/temporaries to processor registers to reduce memory usage (spilling/assignments/coalescing). ↩

Quick FAQ: edge interpretations of the prompt

Knowledge Check

Question 1 of 4
Q1Single choice

Which optimization eliminates repeated computation of the same expression by computing it once and reusing the result?

Explore Related Topics

1

Compiler Phases: Which Analyzer Checks Every Character?

2

Minimizing Register–Memory Operations on RISC: Two Core Approaches

3

Dynamic Method Dispatch in Compilers: Correct Choice and Why

Browse all research articles