Hello,
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.
Thanks,
Jeff Kunkel
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100825/dc179801/attachment.html>
