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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)