Common subexpression elimination in Compiler Design - Mini Project: Build & Apply

Common Subexpression Elimination

📖 Scenario: Imagine you are optimizing a simple program that calculates values using repeated expressions. To make the program faster, you want to find expressions that appear more than once and compute them only once.

🎯 Goal: You will build a step-by-step process to identify common subexpressions in a list of expressions and replace duplicates with a single computed value.

📋 What You'll Learn

Create a list of expressions with some duplicates

Create a dictionary to store computed expressions

Identify and replace duplicate expressions with a reference

Produce a final list with duplicates replaced by references

💡 Why This Matters

🌍 Real World

Common subexpression elimination is used in compilers to optimize code by avoiding repeated calculations, making programs run faster.

💼 Career

Understanding this optimization technique is important for compiler developers, performance engineers, and software developers interested in code efficiency.

1

Create the list of expressions

Create a list called expressions with these exact string values in order: 'a + b', 'c * d', 'a + b', 'e - f', 'c * d'.

Compiler Design

# Create the list called expressions with the given values
# Your code here

Hint

Use square brackets to create a list and separate the strings with commas.

2

Create a dictionary to track computed expressions

Create an empty dictionary called computed to store expressions that have been computed.

Compiler Design

expressions = ['a + b', 'c * d', 'a + b', 'e - f', 'c * d']
# Create an empty dictionary called computed
# Your code here

Hint

Use curly braces to create an empty dictionary.

3

Identify and replace duplicate expressions

Create a new list called optimized. Use a for loop with variable expr to iterate over expressions. Inside the loop, if expr is not in computed, add it to computed with a value like 'temp' + str(len(computed) + 1) and append expr to optimized. Otherwise, append the stored value from computed[expr] to optimized.

Compiler Design

expressions = ['a + b', 'c * d', 'a + b', 'e - f', 'c * d']
computed = {}
# Create optimized list and fill it by replacing duplicates
# Your code here

Hint

Use a for loop and an if-else statement to check and replace duplicates.

4

Complete the optimized expressions mapping

Create a dictionary called final_mapping that maps each temp variable in computed to its original expression. Use a dictionary comprehension iterating over computed.items() with variables expr and temp_var.

Compiler Design

expressions = ['a + b', 'c * d', 'a + b', 'e - f', 'c * d']
computed = {}
optimized = []
for expr in expressions:
    if expr not in computed:
        computed[expr] = 'temp' + str(len(computed) + 1)
        optimized.append(expr)
    else:
        optimized.append(computed[expr])
# Create final_mapping dictionary using dictionary comprehension
# Your code here

Hint

Use a dictionary comprehension to invert the computed dictionary.

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