Common subexpression elimination in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the main goal of common subexpression elimination?

Choose the best description of what common subexpression elimination (CSE) aims to achieve in compiler optimization.

A To remove duplicate calculations by reusing previously computed values.

B To reorder instructions to improve parallel execution.

C To inline functions to reduce call overhead.

D To eliminate unreachable code blocks.

💡 Hint

Think about how repeated calculations can be optimized.

CSE identifies expressions that are computed multiple times and replaces later occurrences with the stored result, reducing redundant work.

📋 Factual

intermediate

Which of these expressions is a common subexpression in the code snippet below?

Given the code:
a = b + c
d = b + c + e
Which expression is a common subexpression?

A a + d

B b + e

C b + c

D c + e

💡 Hint

Look for repeated calculations with the same operands.

The expression b + c appears twice: once assigned to a and again as part of d.

🔍 Analysis

advanced

What is the effect of common subexpression elimination on the following code?

Consider this code snippet:
x = (a + b) * c
y = (a + b) * d
What will be the optimized code after applying common subexpression elimination?

A temp = a + b<br>x = temp * c<br>y = temp * d

B x = a + b * c<br>y = a + b * d

C x = (a + b) * c<br>y = (a + b) * d

D temp = a * b<br>x = temp + c<br>y = temp + d

💡 Hint

Identify repeated expressions and store them once.

The expression a + b is computed twice. CSE stores it in temp and reuses it, reducing repeated addition.

❓ Reasoning

advanced

Why might common subexpression elimination not always improve performance?

Which reason explains why applying common subexpression elimination could sometimes degrade performance?

A Because it prevents the compiler from inlining functions.

B Because storing intermediate results may increase memory usage and cause cache misses.

C Because it removes necessary computations leading to incorrect results.

D Because it always increases the number of instructions executed.

💡 Hint

Think about the trade-offs of storing extra values.

Storing intermediate results requires extra memory and registers, which can cause cache misses or register spills, sometimes slowing down the program.

❓ Comparison

expert

Compare the impact of common subexpression elimination on these two code snippets.

Which snippet benefits more from common subexpression elimination?

Snippet 1:
for i in range(1000):
x = a + b
y = x * i

Snippet 2:
for i in range(1000):
x = a + b * i
y = a + b * i + 1

A Both snippets benefit equally from common subexpression elimination.

B Snippet 2 benefits more because it has more arithmetic operations.

C Neither snippet benefits because expressions depend on 'i'.

D Snippet 1 benefits more because 'a + b' is computed once per loop and reused.

💡 Hint

Look for expressions that do not change inside the loop.

In Snippet 1, 'a + b' is loop-invariant and can be computed once outside the loop. In Snippet 2, expressions depend on 'i' and cannot be reused.

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