Questions: Register Allocation

Question 1

Two variables x and y both appear in the same function. Variable x holds the result of a computation that is only used at line 5, and y is first assigned at line 8. Can they safely share a register?

• A. No — two variables can never share a register in the same function
• B. Yes — their live ranges don't overlap, so they don't interfere and can share a register
• C. Only if they have the same data type
• D. Only if the compiler can prove they hold the same value

Answer: (B)

Two variables can share a register whenever their live ranges don't overlap — that is, they are never simultaneously alive. x is live only up to line 5 (where its last use occurs); y only becomes live at line 8 (its assignment). Since there is no point where both are simultaneously alive, they don't interfere in the interference graph, so there is no edge between them, and they can receive the same color (register).

Question 2

The graph coloring heuristic for register allocation works by repeatedly removing nodes with fewer than k neighbors. Why does this guarantee those nodes can always be colored at assignment time?

• A. Nodes with fewer neighbors interfere with fewer variables, so they are less important and can be spilled cheaply
• B. A node with fewer than k neighbors will always have at least one color available no matter what colors its neighbors receive, since there are k colors and fewer than k constraints
• C. Low-degree nodes are always assigned to callee-saved registers, which are always available
• D. The heuristic does not guarantee colorability — it just provides an approximation

Answer: (B)

This is the key insight of the Chaitin-Briggs coloring heuristic. If a node has degree < k, then its neighbors can use at most (k–1) distinct colors, leaving at least one color free for this node regardless of how neighbors are colored. So when you pop this node off the stack after all its neighbors are colored, you are guaranteed a valid color exists. This is not just a heuristic — it is a provable guarantee for nodes that were removed during the simplification phase.

Question 3

Spilling a variable that is used inside a deeply nested loop is more expensive than spilling a variable used once outside any loop.

• T. True
• F. False

Answer: True

Spilling inserts a store before the variable's definition and a load before each of its uses, replacing register access with memory access. If the variable is inside a loop that executes N times, these loads and stores execute N times per loop iteration — potentially millions of times at runtime. A variable used once outside any loop incurs the memory access cost only once. Good allocators use loop depth and use frequency as part of their spill cost heuristic to minimize the runtime penalty of spilling.

Question 4

Two variables that are seldom simultaneously live can still interfere and is expected to be given different registers if they are both used in the same basic block.

• T. True
• F. False

Answer: False

Interference is defined entirely by live range overlap — two variables interfere if and only if they are simultaneously live at some program point. Being in the same basic block is irrelevant; what matters is whether both are alive at the same time. If x's live range ends before y's begins (even within the same block), they have no edge in the interference graph and can share a register. This is precisely why live variable analysis must be computed before building the interference graph.

Question 5

Why is live variable analysis a required prerequisite for register allocation, and what would go wrong if you tried to allocate registers without it?

Model answer: Live variable analysis determines, for every program point, which variables hold values that will be used in the future — their live ranges. Register allocation needs this to know which pairs of variables must not share a register (those that are simultaneously live). Without it, you cannot construct the interference graph. If you naively gave every variable its own register, you would need as many registers as variables — usually far more than the hardware has. Without live range information, you also cannot identify opportunities for register sharing between variables whose lifetimes don't overlap, leading to unnecessary and costly spills.

The entire graph coloring model depends on live ranges: nodes are variables, edges connect variables that are simultaneously live, and graph coloring assigns registers such that interfering variables get different ones. Live variable analysis is what makes this model possible. It reveals that many variables in a real program never coexist simultaneously, allowing the compiler to reuse registers far more aggressively than a naive one-variable-one-register approach — often keeping most variables in the small register file that modern CPUs provide.