Contents
Page-10
Prev
Next
Page+10
Index
Register Allocation by Graph Coloring
An undirected graph is colored by assigning a ``color'' to each node,
such that no two nodes that are connected have the same color.
Graph coloring is applied to register assignment in the following way:
- Nodes of this graph correspond to def-use chains.
- Nodes are connected by arcs if the variables are busy at the same time.
- Colors correspond to registers.
A heuristic algorithm is applied to find approximately
the minimum
number of colors needed to color the graph. If this is more than
the number of available registers, spill code
is added to
reduce the number of colors needed.
By keeping as many variables as possible in registers, the code
can be significantly improved.