Compilers
In register allocation by coloring an interference graph, what do the nodes and edges represent?
- ANodes are instructions, and edges are their execution order
- BNodes are registers, and edges are the wiring between registers
- CNodes are values; edges join values live at the same time
Show answer and explanation
Answer: C. Nodes are values; edges join values live at the same time
In an interference graph, variables and temporaries are nodes, and two values that are both still in use (live) at some point are joined by an edge. Connected values are needed simultaneously, so they cannot share a register. With k registers, if the graph can be colored with k colors so that no neighbors share a color, each color maps directly to a register. If not, some values are spilled to memory. The graph does not represent instruction order or register wiring.
- A. It does not represent instruction order.
- B. It does not represent register wiring.
- C. Correct. Edges join values that are live at the same time.