Re: Simple register allocation for assembly

On 7 Jan 2003 23:28:46 -0500, Falk Hueffner
<falk.hueffner@student.uni-tuebingen.de> wrote:
>There are only instructions with 0 to 3 inputs and 0 to 1 outputs,
>conditional branches, and unconditional branches. No spilling is to be
>done, if no register allocation can be done, the program should
>abort. Also, I expect very small input sizes, so resource usage is not
>very important. So at first glance this looks pretty easy, but I can't
>really come up with a simple algoritm, any hints?


Okay, you've striped out the hard part of of register allocation,
which is what to do when you don't have enough registers. But, you're
still left with a not-completely-trivial problem.


A basic algorithm for register allocation is to compute the live range
of the register candidates, and construct an interference graph that
links together candidates that are live at the same time. Then you
assign "colors" to each node. If you can color the graph using only n
colors, you can allocate the candidates using only n registers.


You compute the live range by propagating backwards information about
values used, and propagating forward information about values defined.
A candidate is live at any point in the program when it's been defined
and will be used. This is a standard dataflow algorithm.


Unfortunately, graph-coloring is NP-complete, so it gets expensive
real fast as the size of your interference graph gets larger.
Production allocators use heuristics to select the colors.


If you're really talking about small programs, it's probably not worth
the effort. Try using macro expansions (#define) to rename the
registers by hand.


As a random musing, you might try estimating the live ranges
textually, using a good string-oriented language (Perl) to match
patterns. It might work if you keep your program structured. You'll
have to take backward branches into account...


HTH,


Morris

Return to the comp.compilers page.
Search the comp.compilers archives again.