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 don’t 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s