Live variable analysis in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify variables that are live at a program point.

Compiler Design

live_vars = [1]

Drag options to blanks, or click blank then click option'

Aint()

Blist()

Cdict()

Dset()

Attempts:

3 left

💡 Hint

Common Mistakes

Using a list can cause duplicates and slower lookups.

Using a dictionary or integer is not suitable for storing variables.

Live variables are best tracked using a set to avoid duplicates and allow fast membership checks.

2fill in blank

medium

Complete the code to update live variables after processing a statement.

Compiler Design

live_vars = (live_vars - [1]) | [2]

Drag options to blanks, or click blank then click option'

Adefs

Buses

Ckills

Dgen

Attempts:

3 left

💡 Hint

Common Mistakes

Removing used variables instead of defined variables.

Confusing gen and kill sets.

Variables defined (defs) in a statement are removed from live variables because they get new values, then union with used variables (uses).

3fill in blank

hard

Fix the error in the live variable update formula.

Compiler Design

live_in = (live_out - [1]) | [2]

Drag options to blanks, or click blank then click option'

Agen

Buses

Ckills

Ddefs

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '|' for set union.

Removing uses instead of defs.

The correct operator to combine sets is union (|), not addition (+), and remove defs before adding uses.

4fill in blank

hard

Fill both blanks to compute live variables at a program point.

Compiler Design

live_in = (live_out - [1]) | [2]

Drag options to blanks, or click blank then click option'

Adefs

Buses

Ckills

Dgen

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping defs and uses in the formula.

Using kills or gen incorrectly.

Live variables coming into a statement are those live after it, minus variables defined there, plus variables used there.

5fill in blank

hard

Fill all three blanks to create a dictionary of live variables for each program point.

Compiler Design

live_vars_map = {point: ([3] - [1]) | [2] for point, ([3]) in program_points.items()}

Drag options to blanks, or click blank then click option'

Adefs

Buses

Clive_info

Dkills

Attempts:

3 left

💡 Hint

Common Mistakes

Using kills or d instead of defs or uses.

Not unpacking live_info correctly.

For each program point, remove defined variables (defs), add used variables (uses), and unpack live_info from the items.

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