Register allocation

Hello,

I have a question about register allocation using a graph coloring
algorithm.
The front-end of my compiler produces a three address code
representation.
The register allocation should be performed on the intermediate
representation (to assign temporaries to registers) or should I choose
the instructions of the target processor first, assuming an infinite
number of registers and then use the register allocation to match the
actual set of registers ?

Thibault Langlois

thibault.langlois@di.fc.ul.pt wrote:

> The register allocation should be performed on the intermediate
> representation (to assign temporaries to registers) or should I choose
> the instructions of the target processor first, assuming an infinite
> number of registers and then use the register allocation to match the
> actual set of registers ?

For most instruction sets it would make sense to do instruction
selection before register allocation.  The instructions selected might
need to evaluate into a particular register, or else require operands
in another register.

By pre-allocating registers you might prevent the use of certain
instructions or even make code generation impossible.

"thibault.langlois@di.fc.ul.pt" <thibault.langlois@di.fc.ul.pt> writes:


> I have a question about register allocation using a graph coloring
> algorithm.
> The front-end of my compiler produces a three address code
> representation.
> The register allocation should be performed on the intermediate
> representation (to assign temporaries to registers) or should I choose
> the instructions of the target processor first, assuming an infinite
> number of registers and then use the register allocation to match the
> actual set of registers ?

There are advantages and divantages to both approaches:

If you do register allocation on intermediate code:

- You can share the register allocator among all target
architectures, just parameterising with number of registers etc.

- You can generate spill code as intermediate code, which the
instruction selector may optimise.

- The register allocator wil be simpler, as intermediate code is more
regular than machine code.

- But you will have to leve a few register unallocated, as the code
generator may have to use extra registers as temporaries etc.

With allocation on machine code:

- You can more easily handle instructions that require
operands/results in specific registers.

- You can tune the allocator better to the calling convention, i.e.,
regarding caller-saves/callee-saves registers, parameter registers
and spill.

- But spill code may break the optimality of instruction selection
and scheduling.

- And it is more work to port the register allocator to a different
target architecture.

Overall, I would say you get the best result by postponing register
allocation to machine code, but it will also be more work to do so.

Torben

Thanks for the advice.
The language and compiler are created for teaching purpose. That should
not be too difficult to test both aproaches and compare the results.
I'd like to target mips and pentium architectures in order to give
students different examples of code generation.

Thanks again.

Thibault Langlois

Many years ago I did a paper for my Masters on register allocation using
coloring.  What I found out during my research (and some fairly tedious
hand-worked examples) was that using an infinite number of registers,
followed by temporary variable (pseudo-register) consolidation THEN coloring
yielded good results.

Chuck

"thibault.langlois@di.fc.ul.pt" <thibault.langlois@di.fc.ul.pt> writes: