Re: Simple register allocation for assembly

  journeyman@compilerguru.com (journeyman) wrote:


> [ with respect to a simple register allocator ]


> 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.


What is NP-complete is graph-coloring with the absolutely minimum
number of colors. If you don't insist on getting the best possible
solution, graph coloring is much easier. Take the next variable, try
if it can use any of the existing colors, and create a new color only
when necessary.

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