Graph Coloring Algorithm
- As written in previous post, graph coloring algorithm is used to produce RIGs which in turn produces mapping function from temporaries to registers.
- In k-colorable graph, two vertices are not joined if they have same color and number of least total colors given to the graph is k.
- In the mapping function, if the graph made has k colors, then a register assignment won’t have more than k registers. l is number of machine register.
- Its a NP-hard problem, hence some heuristics are used.
- The heuristic is to use the node having neighbous less than k.
REPEAT Choose a node having fewer than k neighbors PUSH this node in STACK remove the node's edges from the graph UNTIL graph is empty REPEAT POP a node from STACK pick a different color from the colors assigned to its neighbors UNTIL stack is empty
Example is here.
If in the problem, one node can be assigned two register then the lowest register that means that register that entered the graph first while popping from stack is used.