[MLton] Register allocation in MLton

[Jesper Louis Andersen]

I am currently in the proces of writing a register allocator for RISC 
machines. This seems quite simple with the obvious approach based on
vertex coloring a graph with coalesce and intereference edges; the
graph in both a bit-matrix and a linked-list representation. With 32
registers available you seldomly spill anyway. 

My problem is it seems to simple. Andrew Appel provides an algorithm
in his ''Tiger book'' "Modern compiler implementation in ML", which
seems to quite fast, based on worklists and sets represented as 
doubly linked lists to avoid quadratic blowup. Is there a more clever
way which could be recommended?

I know you can allocate smarter if you have an expression. And that 
SML/NJ allocates registers directly on the CPS transformation; 
after closure converting the CPS, they rewrite the CPS such that
there are always strictly less than N free variables, where N is the 
number of machine registers. So when a new variable is bound, there are
a free register to assign it to. Quite clever. Since the article was
old, I expect this is what is done in SML/NJ 110.

For JITs theres the Linear scan algorithm which almost looks like
cheating, but it is easy to grasp and probably rather fast.

But I ran out of good ideas when you only have 6 registers available.
You can spill coalesce in various ways of course, but is there more
tricks to be applied? And what does MLton do? And is there anything
to be aware of which also applies to RISC machines and improves the
allocation? 

Reading material is also greatly appreciated.

-- 
j.