Live variable analysis in Compiler Design - Step-by-Step Execution

Concept Flow - Live variable analysis

Start at end of program

↓

Initialize live variables as empty

↓

For each statement backward

↓

Remove variables defined here

↓

Add variables used here

↓

Update live variable set

↓

Repeat for all statements

↓

Result: live variables at each point

Live variable analysis works backward through code, tracking which variables are needed later by removing those redefined and adding those used.

Execution Sample

Compiler Design

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

Analyze live variables backward from line 5 to line 1.

Analysis Table

Step	Statement	Live Variables Before	Variables Defined	Variables Used	Live Variables After
1	print(c)	{}	{}	{c}	{c}
2	c = a + b	{c}	{c}	{a,b}	{a,b}
3	a = 3	{a,b}	{a}	{}	{b}
4	b = a + 1	{b}	{b}	{a}	{a}
5	a = 5	{a}	{a}	{}	{}

💡 Reached start of program; live variables at start are empty.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	undefined	undefined	present	removed	present	removed
b	undefined	undefined	present	present	removed	removed
c	undefined	present	removed	removed	removed	removed

Key Insights - 3 Insights

Why do we remove a variable from the live set when it is defined?

Because defining a variable means its old value is overwritten, so the previous value is no longer needed. See step 3 in execution_table where 'a' is removed after being defined.

Why do we add variables used in a statement to the live set?

Variables used are needed for the current computation, so they must be live before this statement. For example, at step 2, 'a' and 'b' are added because they are used.

Why does the analysis proceed backward through the code?

Because we want to know which variables are needed in the future, so we start from the end and move backward to see what must be kept alive.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. Which variable is removed from the live set after this step?

A b

B a

C c

D none

💡 Hint

Check the 'Live Variables After' column at step 3 in execution_table.

At which step does variable 'c' stop being live?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at when 'c' disappears from the live variables in execution_table rows.

If variable 'b' was not used in statement 4, how would the live variables after step 4 change?

A b would be removed

B a would be removed

C b would remain live

D no change

💡 Hint

Refer to step 4 in execution_table and consider the effect of usage on live variables.

Concept Snapshot

Live Variable Analysis:
- Works backward through code
- Removes variables when defined (overwritten)
- Adds variables when used
- Tracks variables needed in future
- Helps optimize by identifying unused values

Full Transcript

Live variable analysis is a method used in compiler design to find which variables hold values that will be used later in the program. It works by starting at the end of the program and moving backward through each statement. At each step, variables that are defined (assigned new values) are removed from the live set because their old values are no longer needed. Variables that are used (read) are added to the live set because their values are needed for computation. This process continues until the start of the program is reached, resulting in a set of live variables at each point. This helps compilers optimize code by knowing which variables can be safely discarded or reused.

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