Re: Graph coloring when targeting IA32 processors?

For my SoftWire project (http://softwire.sourceforge.net) I use a
simple heuristic based on usage frequency. It works very well in
practice for my swShader project (http://sw-shader.sourceforge.net).


Basically what I do first is assigning virtual registers (actually
they are labeled with the reference to the memory location the
variable is stored). Then I step trough the code one instruction at a
time. When a virtual register is used, I look up if it's already
allocated to a register. If not, I search for a free register and add
a mov instruction to store it there. When there are no registers left
I look at which (virtual) register was referenced the least and write
that back to it's corresponding memory location so it's available for
the new virtual register. Currently it does not look ahead to
determine if there are virtual registers that are not used any more
(so their corresponding physical register is available), but in almost
all cases the least frequent used register is dead anyway (although I
do have free and spill functions to do it 'manually'). The main
benefits of this method (mostly referred to as linear-scan register
allocation) are that it is easy to implement, and it's very fast. In
my case it even produces near-optimal code as if I had written it
myself. I don't know if it works equally well for general compilers.


Anyway, the book doesn't say graph coloring won't work, the heuristic
just doesn't work optimally with a low number of colors. I am not
sure, but I think many x86 compilers do use graph coloring or a
variant. Although that's manybe because most books focus on writing a
compiler for architectures with more registers...

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