Common subexpression elimination in Compiler Design - Step-by-Step Execution

Concept Flow - Common subexpression elimination

Start: Code with expressions

↓

Identify repeated expressions

↓

Check if operands unchanged

Yes No↓

Replace with temp

↓

Use temp variable instead

↓

Optimized code output

The process finds repeated expressions, checks if their inputs stay the same, then replaces duplicates with a temporary variable to avoid recomputing.

Execution Sample

Compiler Design

a = b + c
x = b + c
y = a * 2
z = b + c + y

This code has the expression 'b + c' repeated three times, which can be optimized by computing it once and reusing.

Analysis Table

Step	Action	Expression Found	Operands Unchanged?	Replace with Temp?	Resulting Code
1	Scan first expression	b + c	N/A	No	a = b + c
2	Scan second expression	b + c	Yes	Yes	x = temp1
3	Create temp1 = b + c	b + c	N/A	No	temp1 = b + c
4	Scan third expression	a * 2	N/A	No	y = a * 2
5	Scan fourth expression	b + c	Yes	Yes	z = temp1 + y
6	Final optimized code	N/A	N/A	N/A	temp1 = b + c a = temp1 x = temp1 y = a * 2 z = temp1 + y

💡 All repeated expressions replaced with temp1 where operands unchanged, optimization complete.

State Tracker

Variable	Start	After Step 1	After Step 3	After Step 6
a	undefined	b + c	b + c	temp1
x	undefined	undefined	undefined	temp1
y	undefined	undefined	undefined	a * 2
z	undefined	undefined	undefined	temp1 + y
temp1	undefined	undefined	b + c	b + c

Key Insights - 2 Insights

Why do we need to check if operands are unchanged before replacing expressions?

Because if operands changed, the repeated expression would produce different results. The execution_table rows 2 and 5 show replacement only when operands are unchanged.

Why create a temporary variable for the common expression?

To store the computed value once and reuse it, avoiding repeated calculations. Step 3 in the execution_table shows creating temp1 for this purpose.

Visual Quiz - 3 Questions

According to the execution_table, at which step is the temporary variable created?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Action' and 'Resulting Code' columns in the execution_table for step 3.

In the variable_tracker, what is the value of 'x' after step 6?

A temp1

B undefined

C b + c

D a * 2

💡 Hint

Check the 'After Step 6' column for variable 'x' in variable_tracker.

If operands changed between expressions, what would happen according to the concept_flow?

A Replace with temp variable anyway

B Create multiple temp variables

C Do not replace repeated expression

D Stop optimization

💡 Hint

Refer to the decision branch 'Operands Unchanged?' in concept_flow ASCII diagram.

Concept Snapshot

Common subexpression elimination:
- Find repeated expressions in code
- Check if operands are unchanged
- If yes, compute once and store in temp variable
- Replace repeated expressions with temp variable
- Saves computation time by avoiding repeats

Full Transcript

Common subexpression elimination is a compiler optimization that finds expressions repeated multiple times in code. It checks if the inputs to these expressions remain the same. If they do, the compiler computes the expression once, stores the result in a temporary variable, and replaces all repeated occurrences with this variable. This reduces redundant calculations and improves efficiency. The process involves scanning code, identifying repeated expressions, verifying operand stability, creating temporary variables, and rewriting code accordingly.

Practice

1. What is the main purpose of Common Subexpression Elimination in compiler design?

easy

A. To find repeated calculations and compute them only once

B. To remove unused variables from the code

C. To reorder instructions for parallel execution

D. To translate code into machine language

Solution

1. Step 1: Understand the concept of repeated calculations

   Common subexpression elimination looks for expressions that appear multiple times in code.

2. Step 2: Identify the optimization goal

   It computes these expressions once and reuses the result to save time and work.

3. Final Answer:

   To find repeated calculations and compute them only once -> Option A

4. Quick Check:

   Repeated calculations = compute once [OK]

Hint: Look for repeated expressions to compute once [OK]

Common Mistakes:

• Confusing with dead code elimination
• Thinking it changes instruction order
• Assuming it translates code

2. Which of the following is the correct way to represent a common subexpression elimination in code optimization?

easy

A. Recompute the same expression every time it appears

B. Remove the expression completely from the code

C. Store the result of the expression in a temporary variable and reuse it

D. Replace the expression with a random value

Solution

1. Step 1: Identify the optimization technique

   Common subexpression elimination stores the result of repeated expressions in a temporary variable.

2. Step 2: Understand reuse of stored value

   Later uses of the expression reuse this stored value instead of recomputing.

3. Final Answer:

   Store the result of the expression in a temporary variable and reuse it -> Option C

4. Quick Check:

   Store once, reuse many [OK]

Hint: Store repeated results once to reuse [OK]

Common Mistakes:

• Thinking expressions are removed
• Believing expressions are recomputed every time
• Replacing expressions with unrelated values

3. Consider the code snippet:

a = b + c
d = b + c + e

After applying common subexpression elimination, what is the optimized code?

medium

A. temp = b + c
a = temp
d = temp + e

B. a = b + c
d = b + c + e

C. a = b + c + e
d = b + c + e

D. temp = b + c + e
a = temp
d = temp

Solution

1. Step 1: Identify common subexpression

   The expression b + c appears twice in the code.

2. Step 2: Store and reuse the common expression

   Compute b + c once, store in temp, then use temp for both a and part of d.

3. Final Answer:

   temp = b + c a = temp d = temp + e -> Option A

4. Quick Check:

   Common part stored once =

   temp = b + c
   a = temp
   d = temp + e

   [OK]

Hint: Extract repeated parts into temp variable [OK]

Common Mistakes:

• Not storing the common part
• Storing the entire expression incorrectly
• Duplicating computations

4. Identify the error in the following code after applying common subexpression elimination:

temp = a * b
c = temp + d
temp = a * b + e

medium

A. No error, code is optimized correctly

B. Reassigning temp overwrites previous value causing incorrect reuse

C. The expression a * b is not a common subexpression

D. temp should be declared as a constant

Solution

1. Step 1: Analyze temp variable usage

   The variable temp is assigned a * b first, then reassigned a * b + e.

2. Step 2: Understand impact on reuse

   Reassigning temp overwrites the original value, so reuse of temp later may be incorrect.

3. Final Answer:

   Reassigning temp overwrites previous value causing incorrect reuse -> Option B

4. Quick Check:

   Overwriting temp breaks reuse [OK]

Hint: Avoid overwriting temp holding common subexpression [OK]

Common Mistakes:

• Ignoring reassignment effects
• Assuming temp is constant automatically
• Thinking all expressions are common

5. Given the code:

x = (a + b) * c
y = (a + b) * d
z = (a + b) * c + (a + b) * d

How can common subexpression elimination be applied to optimize this code?

hard

A. temp = (a + b) * (c + d)
x = temp
y = temp
z = temp + temp

B. x = (a + b) * c
y = (a + b) * d
z = x + y

C. temp1 = a + b
z = temp1 * (c + d)
x = z - temp1 * d
y = z - temp1 * c

D. temp = a + b
x = temp * c
y = temp * d
z = x + y

Solution

1. Step 1: Identify common subexpression

   The expression a + b repeats in all calculations.

2. Step 2: Store common subexpression and reuse

   Compute temp = a + b once, then use temp * c and temp * d for x and y. Finally, z = x + y.

3. Final Answer:

   temp = a + b x = temp * c y = temp * d z = x + y -> Option D

4. Quick Check:

   Extract common sum, reuse in products [OK]

Hint: Extract repeated sums first, then multiply [OK]

Common Mistakes:

• Not extracting (a + b) once
• Incorrectly combining terms
• Duplicating calculations