Graph coloring for register allocation in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the minimum number of colors needed for register allocation.

Compiler Design

min_colors = max_degree + [1]

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

A0

B2

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using zero instead of one, which underestimates the colors needed.

Subtracting one, which is incorrect for register allocation.

The minimum number of colors needed is the maximum degree of the graph plus one.

2fill in blank

medium

Complete the code to check if two variables interfere (cannot share the same register).

Compiler Design

if var1 in interference_graph[[1]]:

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

Avar2

Bcolor

Cregister

Dvar1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking var1 in its own adjacency list instead of var2.

Using register or color instead of variable names.

We check if var1 is in the adjacency list of var2 to see if they interfere.

3fill in blank

hard

Fix the error in the code that assigns colors to variables ensuring no two adjacent nodes share the same color.

Compiler Design

for color in range(1, [1] + 1):

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

Amin_colors

Bnum_variables

Cnum_registers

Dmax_degree

Attempts:

3 left

💡 Hint

Common Mistakes

Using max_degree which might be less than needed.

Using total number of variables which is inefficient.

The loop should run up to the minimum number of colors needed to assign registers properly.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps variables to colors only if the color is not used by adjacent variables.

Compiler Design

color_assignment = {var: [1] for var in variables if all(color_assignment.get(adj) != [2] for adj in interference_graph[var])}

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

Acolor

Bvar

Ccolor_assignment[var]

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names instead of colors.

Referencing color_assignment[var] inside the comprehension before assignment.

The comprehension assigns a color to each variable ensuring no adjacent variable has the same color.

5fill in blank

hard

Fill all three blanks to complete the code that builds the interference graph from a list of variable pairs that interfere.

Compiler Design

interference_graph = {}
for var1, var2 in variable_pairs:
    interference_graph.setdefault([1], set()).add([2])
    interference_graph.setdefault([3], set()).add(var1)

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

Avar1

Bvar2

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up which variable is added to which adjacency set.

Not adding both directions, resulting in a directed graph.

The graph is undirected, so each variable is added to the other's adjacency set.