Spilling a symbol doesn't improve colorability

Say I have this intermediate representation of some code:

t1 = 1
t2 = 2
t3 = 3

t4 = t1 + t2
t5 = t3 + t4

use t5

The ultimate goal is to do register assignment using only two ARM registers, r0 and r1, and possibly spill some symbols.

The first step is to compute live ranges for each instruction:

t1 = 1       |
t2 = 2       | t1
t3 = 3       | t1, t2

t4 = t1 + t2 | t1, t2, t3 (this is going to become a problem)
t5 = t3 + t4 | t3, t4

use t5       | t5

Register interference graph

              t2
            /    \     
           /      \    
          /        \   
        t1----------t3
                    | 
                    | 
        t5          t4

Register assignment via graph coloring

Now use Chaitin's algorithm on it to color it with the two registers:

1. Find node with fewer than 2 edges
   1. Found => t5
   2. Remove it from the graph
   3. Push it onto the stack: [t5]
2. Find node with fewer than 2 edges
   1. Found => t4
   2. Remove it from graph, push: [t5, t4]
3. No nodes with fewer than 2 edges! (we're looking at the t1 - t2 - t3 triangle)
   1. Pick one at random (or with the highest degree (2 for all remaining nodes)) => t3 (this might be a problem)
   2. Remove it from graph, push: [t5, t4, t3]
4. Find node with fewer than 2 edges
   1. Found t2
   2. Remove it from graph, push: [t5, t4, t3, t2]
5. Push the last node: [t5, t4, t3, t2, t1]

Now assign registers in reversed order:

1. Pop symbol => t1
   1. Conflicting nodes: none
   2. Assign: t1 => r0
   3. Put t1 back in the graph
2. Pop t2
   1. Conflicting nodes: {t1: r0}
   2. We have one more free register
   3. Assign: t2 => r1
   4. Put t2 back in the graph
3. Pop t3
   1. Conflicting nodes: {t1: r0, t2: r1}
   2. OOPS! No more free registers!
   3. Spill it => t3 => m0
   4. Put t3 back in the graph
4. No more spills required!

Final assignment:

t1 -> r0
t2 -> r1
t3 -> m0 (spilled)
t4 -> r0 (or r1)
t5 -> r0 (or r1)

Inserting spills

Now, as per this (slide 29) and this (slide 4):

Before each operation that uses [the spilled symbol t3], insert t3 := load m0

After each operation that defines [the spilled symbol t3], insert store t3, m0

Let's do this and also compute the live ranges:

t1 = 1       |
t2 = 2       | t1

t3 = 3       | t1, t2
// STORE
store t3, m0 | t1, t2, t3 (STILL 3 SYMBOLS!)

t4 = t1 + t2 | t1, t2

// LOAD
t3 = load m0 | t4
t5 = t3 + t4 | t3, t4

use t5       | t5

Problem

As you can see, we still have an instruction where three symbols interfere, and we'll also get the same RIG as before.

So the spill didn't work!

Now, I brute-forced the possible candidates for spilling by hand and found out that the RIG remains not 2-colorable if we spill any one symbol, but it becomes 2-colorable if we spill any of these pairs of symbols:

• t1 and t3
• t2 and t3

...and also t1, t2 and t3, but spilling only two symbols looks simpler.

Actual question

How do I decide what to spill? What heuristic do I use? I'd also like the algorithm to do global register assignment, so plain live ranges and linear-scan assignment (as opposed to building the RIG) seems to be a pretty cumbersome approach.

Also, if I re-run the same algorithm on the code with spills, the result will be "spill t3" again, even though it's been done already, so the code will loop forever. Even more, if I continue spilling t3 and inserting load/store code, I'll get more and more instructions where t1, t2 and t3 interfere, so the situation will be getting worse.

And that's assuming that I can just t3 = load m0, while on ARM (that I'm targeting) m0 should be stored in its own register first.