The Essence of Register Allocation

As an independent study project, I designed a new method for register allocation. Different from earlier methods, it departs from the graph coloring formulation and is based on a variation of abstract interpretation which I call model transformer semantics. I show that register allocation is essentially not a graph coloring problem, but rather similar to a cache replacement or scheduling problem, thus possibly deserves much easier solutions.

I have drafted a paper, but because of other priorities, I dont have time benchmarking it and submitting to a compiler conference. I have put the full text to arxiv. I welcome any feedback.

I gave a talk about it at Indiana University in Nov 2011. Here are the slides [PPT] [PDF].