About Register Allocation


I would like to implement a register allocation scheme which is much like the Linear Scan. It’s known as Belady’s Optimal Algorithm. In fact, the algorithm is very close to the linear scan algorithm, except instead of ranges, it uses points in time. I am wondering if anyone with experience implementing register optimization algorithms within LLVM would be interested in helping me. And, if anyone has any thoughts on the performance of this algorithm, I would appreciate hearing them.

The algorithm is a very simple one. The agent records the variables needed, and the agent keeps placing the memory locations into an open slot one by one until no more slots are available. When this happens, the agent waits until it knows which of the variables will be used the furthest from the point stopped. It them spills the variable, and opens the slot. Like all good algorithms, it rinses and repeats. I can certainly go into a full system level description of the physical graphs to queues/arrays when the time comes. A simple form is two passes, and a more complex form is two iterators working with the same data.

Belady’s optimal algorithm is optimal because the data itself is an interval graph, and Belady’s algorithm is an instance of the interval graph algorithm.

About myself. I graduated from Kutztown University in December of 2009. I presented Interval Graphs at the Moravian Math Conference in 2009, and I presented the Interval Graphs / Belady’s algorithm to my Compiler class. Which leads me to implementation of this algorithm.

Jeff Kunkel