Dead code elimination in Compiler Design - Mini Project: Build & Apply

Dead Code Elimination

📖 Scenario: You are working on a simple compiler optimization step called Dead Code Elimination. This process removes parts of the code that never affect the program's output, making the program smaller and faster.Imagine you have a list of instructions in a program, and some instructions assign values to variables that are never used later. Your task is to identify and remove these unnecessary instructions.

🎯 Goal: Build a step-by-step process to identify and remove dead code from a list of instructions. You will create a data structure to hold instructions, mark which variables are used, and then filter out instructions that assign to unused variables.

📋 What You'll Learn

Create a list of instructions with exact variable assignments and usage

Create a set to track variables that are used later

Implement logic to identify and remove instructions assigning to unused variables

Complete the final filtered list representing the optimized code

💡 Why This Matters

🌍 Real World

Dead code elimination is a common optimization in compilers that helps reduce program size and improve performance by removing unnecessary instructions.

💼 Career

Understanding dead code elimination is important for compiler developers, software engineers working on performance optimization, and anyone interested in how programming languages and tools improve code efficiency.

1

Create the list of instructions

Create a list called instructions with these exact strings representing code lines: 'a = 5', 'b = 10', 'c = a + b', 'd = 20', 'print(c)'.

Compiler Design

# Create the list of instructions
# Your code here

Hint

Use a Python list with the exact strings in the given order.

2

Create a set of used variables

Create a set called used_vars containing the exact variable names 'a', 'b', and 'c' which are used in the program.

Compiler Design

instructions = ['a = 5', 'b = 10', 'c = a + b', 'd = 20', 'print(c)']
# Create the set of used variables
# Your code here

Hint

Use curly braces to create a set with the exact variable names.

3

Filter out dead code instructions

Create a new list called optimized_instructions that includes only instructions from instructions where the assigned variable is in used_vars. Use a for loop with variable instr to check each instruction's assigned variable before adding it to optimized_instructions.

Compiler Design

instructions = ['a = 5', 'b = 10', 'c = a + b', 'd = 20', 'print(c)']
used_vars = {'a', 'b', 'c'}
# Create optimized_instructions by filtering dead code
# Your code here

Hint

Check if the instruction contains '=' to find assigned variables, then keep only those in used_vars. Also keep instructions without assignments like print(c).

4

Complete the optimized code list

Add the final line to the code that assigns optimized_instructions as the filtered list representing the program after dead code elimination.

Compiler Design

instructions = ['a = 5', 'b = 10', 'c = a + b', 'd = 20', 'print(c)']
used_vars = {'a', 'b', 'c'}
optimized_instructions = []
for instr in instructions:
    if '=' in instr:
        var = instr.split('=')[0].strip()
        if var in used_vars:
            optimized_instructions.append(instr)
    else:
        optimized_instructions.append(instr)
# Finalize the optimized instructions list
# Your code here

Hint

The final step confirms the filtered list is ready to use as the optimized program.

Practice

1. What is the main purpose of dead code elimination in compiler design?

easy

A. To remove code that never affects the program's output

B. To add extra debugging information

C. To increase the size of the compiled program

D. To change the program's logic for optimization

Solution

1. Step 1: Understand dead code

   Dead code is code that does not affect the program's output or behavior.

2. Step 2: Purpose of elimination

   Removing such code makes the program faster and smaller without changing its meaning.

3. Final Answer:

   To remove code that never affects the program's output -> Option A

4. Quick Check:

   Dead code elimination = Remove unused code [OK]

Hint: Dead code does not run or affect results, so remove it [OK]

Common Mistakes:

• Thinking dead code changes program logic
• Confusing dead code elimination with debugging
• Believing it increases program size

2. Which of the following code snippets is an example of dead code that can be eliminated?

easy

A. int z = 2; z = z + 1; return z;

B. int x = 5; x = 10; return x;

C. int y = 3; if (false) { y = 7; } return y;

D. int a = 4; a = a * 2; return a;

Solution

1. Step 1: Identify dead code

   The code inside if (false) never runs, so y = 7; is dead code.

2. Step 2: Check other options

   Other assignments affect the returned value, so they are not dead code.

3. Final Answer:

   int y = 3; if (false) { y = 7; } return y; -> Option C

4. Quick Check:

   Code inside false condition = Dead code [OK]

Hint: Code inside 'if(false)' or unreachable blocks is dead code [OK]

Common Mistakes:

• Thinking all variable reassignments are dead code
• Ignoring conditions that never execute
• Confusing dead code with useful code

3. Consider the following code snippet:

int a = 10;
int b = 20;
if (a > b) {
  b = a + 5;
}
return b;

After dead code elimination, what will be the returned value?

medium

A. 10

B. 20

C. 25

D. Compiler error

Solution

1. Step 1: Analyze the condition

   The condition a > b is 10 > 20, which is false, so the if block never runs.

2. Step 2: Identify dead code and final value

   The assignment inside the if block is dead code and removed. The value of b remains 20 and is returned.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   False condition skips code, return original b = 20 [OK]

Hint: If condition is false, code inside is dead and removed [OK]

Common Mistakes:

• Assuming if block runs and changes b
• Returning a instead of b
• Confusing dead code with runtime error

4. Identify the dead code in the following snippet and suggest the correct fix:

int x = 5;
return x;
x = 10;

medium

A. No dead code; code is correct as is

B. The return statement is dead code and should be removed

C. The variable declaration int x = 5; is dead code

D. The assignment x = 10; is dead code and should be removed

Solution

1. Step 1: Understand code flow

   After return x;, the function exits, so x = 10; never runs.

2. Step 2: Identify dead code and fix

   The assignment x = 10; is dead code and should be removed to clean the code.

3. Final Answer:

   The assignment x = 10; is dead code and should be removed -> Option D

4. Quick Check:

   Code after return is dead and removable [OK]

Hint: Code after return is dead and can be removed [OK]

Common Mistakes:

• Thinking code after return runs
• Removing return statement mistakenly
• Confusing variable declaration as dead code

5. You have this code:

int sum = 0;
for (int i = 0; i < 5; i++) {
  if (false) {
    sum += i;
  }
}
return sum;

How does dead code elimination optimize this loop?

hard

A. Removes the entire loop since it does nothing

B. Removes only the if block but keeps the loop

C. Keeps all code as is because loop runs 5 times

D. Changes the loop to run 0 times

Solution

1. Step 1: Analyze the loop body

   The if condition is always false, so sum += i; never runs, making the loop body dead code.

2. Step 2: Optimize the loop

   Since the loop does not change sum, the entire loop can be removed, returning 0 directly.

3. Final Answer:

   Removes the entire loop since it does nothing -> Option A

4. Quick Check:

   Loop with dead body = Remove whole loop [OK]

Hint: If loop body never runs, remove whole loop [OK]

Common Mistakes:

• Removing only if block but keeping loop
• Assuming loop changes sum despite false condition
• Changing loop count incorrectly