IU-Fall-2021

Course web page for Fall 2021.

View the Project on GitHub IUCompilerCourse/IU-Fall-2021

Register Allocation: Graph Coloring via Sudoku

If you aren’t familiar with graph coloring, you might instead be familiar with another instance of it, Sudoku.

Review Sudoku and relate it to graph coloring.

-------------------
|  9  |5 3 7|  1 4|
|  3 8|  4 6|  9  |
|4    |1    |2    |
-------------------
|     |     |    2|
|7   9|8   2|1   5|
|6    |     |     |
-------------------
|    4|    8|    6|
|  6  |4 9  |7 2  |
|8 7  |6 2 3|  4  |
-------------------

What strategies do you use to play Sudoku?

We’ll use the DSATUR algorithm of Brelaz (1979). Use natural numbers for colors. The set W is our worklist, that is, the vertices that still need to be colored.

W <- vertices(G)
while W /= {} do
  pick a vertex u from W with maximal saturation
  find the lowest color c not in { color[v] | v in adjacent(u) }.
  color[u] <- c
  W <- W - {u}

Initial state:

{}     {}     {}
t ---- z      x
       |\_    |
       |  \__ |
       |     \|
       y ---- w ---- v
       {}     {}    {}

There’s a tie amogst all vertices. Color t 0. Update saturation of adjacent.

{}    {0}     {}
t:0----z      x
       |\_    |
       |  \__ |
       |     \|
       y ---- w ---- v
       {}    {}     {}

Vertex z is the most saturated. Color z 1. Update saturation of adjacent.

{1}   {0}     {}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
       y ---- w ---- v
      {1}    {1}    {}

There is a tie between y and w. Color w 0.

{1}   {0}     {0}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
       y ----w:0---- v
      {0,1}  {1}    {0}

Vertex y is the most saturated. Color y 2.

{1}   {0,2}   {0}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
       y:2----w:0---- v
      {0,1}  {1,2}   {0}

Vertex x and v are the most saturated. Color v 1.

{1}   {0,2}   {0}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
       y:2----w:0----v:1
      {0,1}  {1,2}   {0}

Vertex x is the most saturated. Color x 1.

{1}   {0,2}   {0}
t:0----z:1    x:1
       |\_    |
       |  \__ |
       |     \|
       y:2----w:0----v:1
      {0,1}  {1,2}   {0}

Challenge: Move Biasing

In the above output code there are two movq instructions that can be removed because their source and target are the same. A better register allocation would have put t, v, x, and y into the same register, thereby removing the need for three of the movq instructions.

Here is the move-graph for the example program.

t     z --- x
 \_       _/ \_
   \_   _/     \_
     \ /         \
      y     w     v

Let’s redo the coloring, fast-forwarding past the coloring of t and z.

{1}   {0}     {}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
       y ---- w ---- v
      {1}    {1}    {}

There is a tie between y and w regarding saturation, but this time we note that y is move related to t, which has color 0, whereas w is not move related. So we color y to 0.

{1}   {0}     {}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
      y:0---- w ---- v
      {1}    {0,1}    {}

Next we color w to 2.

{1}   {0,2}  {2}
t:0----z:1    x
       |\_    |
       |  \__ |
       |     \|
      y:0----w:2---- v
     {1,2}   {0,1}  {2}

Now x and v are equally saturated, but x is move related to y and z whereas v is not move related to any vertex that has already been colored. So we color x to 0.

{1}   {0,2}  {2}
t:0----z:1   x:0
       |\_    |
       |  \__ |
       |     \|
      y:0----w:2----v:0
     {1,2}   {0,1}  {2}

Finally, we color v to 0.

So we have the assignment:

v -> rbx
w -> rdx
x -> rbx
y -> rbx
z -> rcx
t -> rbx

and generate the following code.

movq $1, %rbx
movq $42, %rdx
movq %rbx, %rbx
addq $7, %rbx
movq %rbx, %rbx
movq %rbx, %rcx
addq %rdx, %rcx
movq %rbx, %rbx
negq %rbx
movq %rcx, %rax
addq %rbx, %rax
jmp conclusion

As promised, there are three trivial movq’s that can be removed in patch-instructions.

movq $1, %rbx
movq $42, %rdx
addq $7, %rbx
movq %rbx, %rcx
addq %rdx, %rcx
negq %rbx
movq %rcx, %rax
addq %rbx, %rax
jmp conclusion