Re: What ideas are better for assigning registers to terminals?

"Bill A." <bill@megahits.com> wrote:


> Assume an intermediate representation coded as a tree or dag. If an
> operator at a node must use a specific processor register to calculate
> the result, is it better to:
>
> 1. Traverse the tree and pre-assign these registers, then globally
> allocate registers using these fixed ones as predetermined and
> unchangeable, or
>
> 2. Globally allocate across the function and add register copies to
> satisfy the requirements of the operators needing specific registers
> (which implies possibly having to spill a globally allocated one to
> free it for use by the operator).
>
> Thank you in advance if you have any ideas.


Assume -2- intermediate representations: the tree, and a symbolic
representation of the target-machine instructions. (As opposed to a
fully-assembled bitpattern) The essential feature of this lower
representation is that you need to be able to find/iterate over all
registers used/defined by a each instruction.


Generate code for the entire tree using virtual registers everywhere
except for those machine instructions requiring a particular physical
register--generate copies of the operands into the proper register before
such instructions.


Use a graph-coloring based register allocator to assign the rest of the
real registers to the virtual registers. The coalescing phase will clean
up most/all of these extra copy instructions. This algorithm will exploit
these special registers in regions where they are not needed for
particular instructions "by magic"


Don't be fooled into thinking that an on-the-fly allocation scheme is
simpler--I was once. It's better to treat instruction selection and
register allocation as two distinct problems. (Caveat: this presumes a
mostly uniform register set with a reasonable number of general purpose
registers--it can be difficult to contort the coloring algorithm to handle
nonuniform register sets in e.g. DSPs)


There are 2 good starting resources for graph-coloring algorithms: Andrew
Appel's "modern compiler design in C/Java/ML" and Preston Briggs PhD
Thesis (poke around www.cs.rice.edu and you'll find it)


Appel's book is designed for an undergraduate course so it's quite
straightforward. Briggs' thesis gathers all of the related knowledge (of
the time) in one place. There are many more primary sources; check the
references of these if you need more.


A few tips: the representation of the Interference Graph described in
Morgan's "Building an Optimizing Compiler" makes things a lot simpler.
(The rest of his allocator is quite a bit more complex) And the
representation for liveness info in Briggs' thesis wherein you can iterate
over all members of a live set in O(#members) rather than O(size of
universe) is essential to avoiding O(N^2) complexity in the allocator.


If you have a decent data structure for your lowered IL you should be able
to code a simple allocator in 500 or so lines of C. Even using the
simplest spill scheme--emit loads and stores for spilled regsters around
each instruction where it is used/defined--you should handily beat the
on-the-fly technique in code quality, and your code generator will be a
lot easier to read.


--
John McEnerney (mcenerney@metrowerks.com)

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