In compiler back-ends, Register Allocation via Graph Coloring maps variables to registers by modeling variables as nodes and drawing an edge between two nodes if:
In Register Interference Graphs (RIG), nodes represent variables and undirected edges represent interference (simultaneous liveness). Coloring the graph with K colors maps variables to K physical registers.
If a Register Interference Graph (RIG) cannot be colored using K available physical registers, what action must the compiler perform?
When K-coloring fails, the compiler selects a spilled variable, stores its value in memory (stack frame), and frees its register.
What NP-complete problem does Chaitin's register allocation algorithm solve using heuristics?
Chaitin modeled register allocation as the NP-complete K-graph coloring problem and introduced degree-based removal heuristics (Kempe's heuristic).
The Sethi-Ullman algorithm (Ershov numbers) is used in code generation for:
The Sethi-Ullman algorithm labels nodes of an expression tree to determine the optimal evaluation order minimizing register usage.
In runtime environment organization, an Activation Record (Stack Frame) contains:
An activation record manages all state associated with a single execution call of a procedure/function on the runtime stack.