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

Need a 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

Need a 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

Need a 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

Need a hint?

Use a dictionary comprehension to invert the computed dictionary.