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.