Live variable analysis in Compiler Design - Mini Project: Build & Apply

Live Variable Analysis

📖 Scenario: You are working on a simple compiler optimization module. One important step is to find which variables are "live" at each point in a program. A variable is "live" if its current value might be used later before being overwritten.Understanding live variable analysis helps optimize memory and improve program speed by removing unnecessary variable storage.

🎯 Goal: Build a step-by-step live variable analysis for a small program represented as basic blocks with instructions. You will create data structures for the program, set up initial live sets, compute live variables using backward data flow analysis, and finalize the live variable sets for each block.

📋 What You'll Learn

Create a dictionary representing basic blocks with their instructions

Create initial empty live-in and live-out sets for each block

Implement the backward data flow equations to compute live-in and live-out sets

Update live-in and live-out sets until no changes occur (fixed point)

Output the final live-in and live-out sets for each block

💡 Why This Matters

🌍 Real World

Live variable analysis is used in compilers to optimize memory usage by identifying variables that are no longer needed and can be safely overwritten or removed.

💼 Career

Understanding live variable analysis is essential for compiler engineers, performance optimization specialists, and anyone working on low-level code analysis or static analysis tools.

1

Create the program basic blocks

Create a dictionary called basic_blocks with these exact entries:
'B1': ['a = 1', 'b = 2', 'c = a + b'],
'B2': ['b = c + 1', 'd = b + 2'],
'B3': ['e = d + a']

Compiler Design

# Create the dictionary basic_blocks with the given blocks and instructions
# Your code here

Hint

Use a dictionary with keys 'B1', 'B2', 'B3' and lists of strings as values.

2

Initialize live-in and live-out sets

Create two dictionaries called live_in and live_out with keys 'B1', 'B2', 'B3'. Initialize each value as an empty set set().

Compiler Design

basic_blocks = {
    'B1': ['a = 1', 'b = 2', 'c = a + b'],
    'B2': ['b = c + 1', 'd = b + 2'],
    'B3': ['e = d + a']
}
# Initialize live_in and live_out dictionaries with empty sets for each block
# Your code here

Hint

Use dictionary literals with keys 'B1', 'B2', 'B3' and values as empty sets.

3

Implement live variable analysis core logic

Write a function called analyze_live_variables that takes basic_blocks, live_in, and live_out as arguments. Inside, implement a loop that updates live-in and live-out sets for each block until no changes occur. Use these rules:
- live_out[block] is the union of live_in of successor blocks
- live_in[block] is use[block] union (live_out[block] minus def[block])
Assume the control flow graph successors are: {'B1': ['B2'], 'B2': ['B3'], 'B3': []}.
For simplicity, define use and def sets for each block as:
use = {'B1': {'a', 'b'}, 'B2': {'c', 'b'}, 'B3': {'d', 'a'}}
def = {'B1': {'a', 'b', 'c'}, 'B2': {'b', 'd'}, 'B3': {'e'}}

Compiler Design

basic_blocks = {
    'B1': ['a = 1', 'b = 2', 'c = a + b'],
    'B2': ['b = c + 1', 'd = b + 2'],
    'B3': ['e = d + a']
}
live_in = {'B1': set(), 'B2': set(), 'B3': set()}
live_out = {'B1': set(), 'B2': set(), 'B3': set()}
# Define analyze_live_variables function and implement the fixed-point iteration
# Your code here

Hint

Use a while loop with a changed flag. Update live_out by union of successors' live_in. Update live_in by use union (live_out minus def).

4

Run analysis and finalize live variable sets

Call the function analyze_live_variables with basic_blocks, live_in, and live_out. Then add a dictionary called final_live that maps each block to a tuple of (live_in[block], live_out[block]).

Compiler Design

basic_blocks = {
    'B1': ['a = 1', 'b = 2', 'c = a + b'],
    'B2': ['b = c + 1', 'd = b + 2'],
    'B3': ['e = d + a']
}
live_in = {'B1': set(), 'B2': set(), 'B3': set()}
live_out = {'B1': set(), 'B2': set(), 'B3': set()}

successors = {'B1': ['B2'], 'B2': ['B3'], 'B3': []}
use = {'B1': {'a', 'b'}, 'B2': {'c', 'b'}, 'B3': {'d', 'a'}}
defs = {'B1': {'a', 'b', 'c'}, 'B2': {'b', 'd'}, 'B3': {'e'}}

def analyze_live_variables(basic_blocks, live_in, live_out):
    changed = True
    while changed:
        changed = False
        for block in basic_blocks:
            old_live_in = live_in[block].copy()
            old_live_out = live_out[block].copy()
            live_out[block] = set()
            for succ in successors[block]:
                live_out[block] |= live_in[succ]
            live_in[block] = use[block] | (live_out[block] - defs[block])
            if live_in[block] != old_live_in or live_out[block] != old_live_out:
                changed = True

# Call analyze_live_variables and create final_live dictionary
# Your code here

Hint

Call the analysis function with the dictionaries, then create final_live using a dictionary comprehension.

Practice

1. What is the main purpose of live variable analysis in compiler design?

easy

A. To find variables that will be used later in the program

B. To count how many variables are declared

C. To check syntax errors in variable declarations

D. To rename variables for better readability

Solution

1. Step 1: Understand live variable analysis goal

   Live variable analysis identifies variables that are needed in future parts of the program.

2. Step 2: Compare options with this goal

   Only To find variables that will be used later in the program matches this purpose; others describe unrelated tasks.

3. Final Answer:

   To find variables that will be used later in the program -> Option A

4. Quick Check:

   Live variable analysis = find needed variables later [OK]

Hint: Live variables are those used later, not just declared [OK]

Common Mistakes:

• Confusing live variables with all declared variables
• Thinking it checks syntax or renames variables
• Assuming it counts variables instead of analyzing usage

2. Which direction does live variable analysis typically work in a program's control flow?

easy

A. Randomly, checking all statements equally

B. Forward, from start to end

C. Backward, from end to start

D. Only on loops, ignoring other code

Solution

1. Step 1: Recall live variable analysis flow

   It analyzes variables starting from the program's end moving backward to the start.

2. Step 2: Match direction with options

   Backward, from end to start correctly states backward analysis; others are incorrect directions or limited scopes.

3. Final Answer:

   Backward, from end to start -> Option C

4. Quick Check:

   Live variable analysis = backward flow [OK]

Hint: Live variable analysis goes backward through code [OK]

Common Mistakes:

• Assuming analysis goes forward like normal execution
• Thinking it only applies to loops or parts of code
• Believing it checks statements randomly

3. Consider this code snippet:

1: x = 5
2: y = x + 2
3: print(y)
4: z = 10

Which variable is live after line 3?

medium

A. x

B. y

C. z

D. None

Solution

1. Step 1: Identify variables used after line 3

   Line 3 prints y, so y is used there. After line 3, line 4 assigns z but does not use any variable.

2. Step 2: Determine live variables after line 3

   After line 3, no further use of x, y, or z occurs. So no variables are live after line 3.

3. Final Answer:

   None -> Option D

4. Quick Check:

   Variables live after last use = None [OK]

Hint: Variables not used later are not live [OK]

Common Mistakes:

• Thinking z is live because it is assigned
• Assuming y remains live after printing
• Confusing variable assignment with usage

4. Identify the error in this live variable analysis step:

At line 2: live variables = {x, y}
At line 1: live variables = {y}

What is wrong?

medium

A. Live variables cannot be sets

B. Live variables at line 1 should include x, not just y

C. Live variables at line 2 should be empty

D. Live variables at line 1 should be empty

Solution

1. Step 1: Understand live variable propagation

   If x is live at line 2, but line 1 does not assign x, then x should be live before line 1.

2. Step 2: Check correctness of live sets

   Live variables at line 1 missing x means analysis missed that x is needed later.

3. Final Answer:

   Live variables at line 1 should include x, not just y -> Option B

4. Quick Check:

   Live variables must include all needed vars [OK]

Hint: Live vars must include all needed before assignment [OK]

Common Mistakes:

• Ignoring variables used after assignment
• Thinking live variables can't be sets
• Assuming live variables disappear too early

5. Given this code:

1: a = 3
2: b = a + 4
3: a = 5
4: print(b)

Which variables are live at line 2 during live variable analysis?

hard

A. {a, b}

B. {a}

C. {b}

D. {}

Solution

1. Step 1: Analyze variable usage after line 2

   Variable b is assigned at line 2 and used at line 4. Variable a is used at line 2 and reassigned at line 3.

2. Step 2: Determine live variables at line 2

   At line 2, a is live because it is used to compute b. b is also live because it is assigned here and used later at line 4.

3. Final Answer:

   {a, b} -> Option A

4. Quick Check:

   Variables used before reassignment and assigned variables used later are live [OK]

Hint: Variables used in expressions and assigned variables used later are live [OK]

Common Mistakes:

• Excluding b as live before its use
• Ignoring a's usage in expression
• Assuming no variables are live at assignment