Which Optimization Removes Repeated Computations?
In compiler optimization, the transformation specifically aimed at removing repeated computations of the same expression is Common Sub-expression Elimination (CSE). CSE detects identical expressions that occur multiple times within a region (e.g., a basic block) and replaces later occurrences with a previously computed value, reducing redundant instruction execution.
By contrast:
- Dead code elimination removes computations whose results are never used (it eliminates unused work, not necessarily repeated work).
- Loop optimization is a broad set of transformations (e.g., loop invariant code motion, unrolling) that can reduce repeated computations but is not the canonical optimization that directly targets repeated sub-expressions.
- Register allocation determines where values live (registers vs memory). It can reduce repeated loads/stores (so it can indirectly affect “repeated computation-like overhead”), but it does not perform expression reuse.
Below is a structured view of each option and how they relate to “repeated computations.”
Key terms: Common Sub-expression Elimination , Dead Code Elimination , Loop Invariant Code Motion , Register Allocation
Note: Due to current tool access limits, I cannot fetch and cite web sources in this run, so citations are omitted.
Compiler Optimizations: Common Subexpression Elimination (Overview)
Answer (direct)
Correct option: (ii) Common sub-expression elimination.
Reason: CSE removes repeated computations by computing a sub-expression once and reusing the result, rather than recomputing the same expression multiple times.
Reuses previously computed identical expressions (removes redundancy).
How Common Sub-expression Elimination Removes Repeated Computations
- 1Step 1
Scan instructions for repeated algebraic/semantic expressions (e.g., occurring multiple times), typically within the same basic block or value-numbering region.
- 2Step 2
Verify that between occurrences, operands and memory locations used by the expression are not modified in a way that would change the result.
- 3Step 3
When the first occurrence is reached, keep (or compute) it and record where the result is stored (temporary/register).
- 4Step 4
Substitute later identical computations with uses of the recorded earlier result.
- 5Step 5
"Optionally delete now-dead redundant computations produced by the replacement."
Mermaid intuition:
Quick mental test for CSE
If the question is about recomputing the same expression multiple times, the direct match is CSE (ii). If the question is about unused results, it’s dead code elimination (i).
Why register allocation isn’t the “repeated computation” answer
Register allocation mainly avoids extra loads/stores (memory traffic). Repeated computations of the same expression are about reusing computed values, which is what CSE does—not where values are stored.
Why the other options don’t directly remove repeated computations
Where these optimizations typically fit in a compilation pipeline (conceptually)
Identify candidates
IR analysis stageCompute dominance/value info; prepare for CSE and DCE."
Apply CSE / DCE
Optimization transformationsReplace repeated expressions (CSE) and remove unused computations (DCE)."
Apply loop transformations
Loop passesPerform loop invariant code motion, unrolling, etc."
Register allocation
Low-level loweringAssign values to physical registers; insert loads/stores when needed."
Knowledge Check
Which optimization removes repeated computations of the same expression by reusing an earlier result?