Compiler Designing W09L1602

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.

[II]

  • Its a NP-hard problem, hence some heuristics are used.
  • The heuristic is to use the node having neighbous less than k.
  • Algorithm:
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.

Advertisements

Help to improve or comment as you wish

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s