Common subexpression elimination in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Common Subexpression Elimination (CSE) in compiler design?

CSE is an optimization technique that finds expressions which are computed more than once and reuses the result instead of recomputing it.

beginner

Why is Common Subexpression Elimination useful?

It reduces the number of repeated calculations, which makes the program run faster and use less resources.

beginner

Give a simple example of a common subexpression.

In the code a = b + c; d = b + c + e;, the expression b + c is a common subexpression.

intermediate

What is a key challenge when applying CSE?

Ensuring that the values used in the expression have not changed between uses, so the reused result is still correct.

intermediate

How does CSE improve program efficiency?

By avoiding repeated calculations, it saves CPU time and can reduce power consumption, especially in large or complex programs.

What does Common Subexpression Elimination do?

A Adds comments to explain code

B Removes unused variables from the code

C Changes variable names to shorter ones

D Reuses results of repeated expressions to avoid recalculation

CSE finds expressions that appear multiple times and reuses their computed values to save time.

Which of the following is an example of a common subexpression?

A x = y + z; a = y + z + 1;

B x = y + z; a = y - z;

C x = y * z; a = y / z;

D x = y + 1; a = z + 1;

The expression y + z appears in both assignments, so it is a common subexpression.

What must be true for CSE to safely reuse a computed value?

A The expression is at the start of the program

B The variables in the expression have not changed since last calculation

C The expression uses only constants

D The expression is inside a loop

If variables change, the old result is no longer valid, so CSE must ensure values are unchanged.

Which of these is NOT a benefit of CSE?

A Reduced memory usage by removing variables

B Less CPU work by avoiding repeated calculations

C Faster program execution

D Potentially lower power consumption

CSE focuses on avoiding repeated calculations, not on removing variables to save memory.

When is CSE typically applied in the compilation process?

A During the optimization phase after code generation

B Before parsing the source code

C During the optimization phase after intermediate code generation

D During linking of compiled files

CSE is usually done on intermediate code to optimize before final code generation.

Explain in your own words what Common Subexpression Elimination is and why it is important.

Think about how repeating the same math over and over can slow down a program.

Describe a simple example where CSE can be applied and what the compiler does to optimize it.

Use a small code snippet with repeated addition or multiplication.

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