Live variable analysis in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is live variable analysis in compiler design?

Live variable analysis is a technique used to determine which variables hold values that may be needed in the future during program execution. It helps optimize code by identifying variables that are 'live' at certain points.

beginner

When is a variable considered 'live' in a program?

A variable is 'live' at a point if its current value will be read later before being overwritten. If the value is never used again, the variable is not live.

intermediate

How does live variable analysis help in register allocation?

By knowing which variables are live at the same time, the compiler can assign them to different registers efficiently, reducing the number of registers needed and improving performance.

intermediate

What is the direction of data flow in live variable analysis?

Live variable analysis is a backward data flow analysis. It starts from the end of the program and moves backward to find where variables are live.

intermediate

Name the two sets used in live variable analysis for each program point.

The two sets are: Use (variables used before any assignment) and Def (variables assigned values). These help compute which variables are live.

What does it mean if a variable is 'live' at a program point?

A It is declared but never used

B It has just been assigned a value

C Its value will be used later before being changed

D It is a constant value

A variable is live if its current value will be read later before any new assignment.

In which direction is live variable analysis performed?

A Backward, from program end to start

B Forward, from program start to end

C Random order

D Only at the program start

Live variable analysis works backward to find where variables are still needed.

Which sets are essential in live variable analysis?

A Input and Output sets

B Use and Def sets

C Start and End sets

D Read and Write sets

Use and Def sets help identify variables used before assignment and those assigned values.

Why is live variable analysis important for register allocation?

A It changes variable names

B It removes all variables from the program

C It increases the number of variables

D It helps assign variables to registers efficiently

Knowing which variables are live helps allocate registers without conflicts.

If a variable is not live at a point, what can the compiler do?

A Reuse its storage or remove its assignment

B Always keep its value

C Ignore the variable completely

D Convert it to a constant

If a variable is not live, its storage can be reused or its assignment removed to optimize code.

Explain what live variable analysis is and why it is useful in compiler optimization.

Think about when a variable's value is needed again and how that helps the compiler.

Describe the role of Use and Def sets in live variable analysis.

Consider how these sets help track variable usage at each program point.

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