Re: basic question on register allocation

Thanks both for your input.

My misunderstanding was that I was thinking once it is determined that
a variable is spilled, all the interferences go away. I re-read my
compiler book (Muchnick's book) and indeed there is a loop that
repeats when allocation fails after spiling.

I've read Hack's work recently that is based on the fact that
interference graphs in SSA form are chordal and the chromatic number
of them can be determined in polynomial time. It is very interesting
to see there are still ways to improve on existing solutions to an old
problem like register allocation.