Graph coloring for register allocation?

[Nick Ing-Simmons]

Daniel Berlin <dberlin@redhat.com> writes:
>>
>> SMALL_REGISTER_CLASSES (and therefore all kinds of cruft all over the place).
>> Inability to run the scheduler before register allocation on some machines.
>
>Unless i'm mistaken, all the papers i've looked at(save one or two, i
>think Chow and Hennessy didn't, it's hard to recall) require that
>scheduling be run before register allocation.

Which is not always ideal. For example "we" had/have DSP(s) where operations on 
address registers happen in a different pipe stage to operations on data 
registers. So schedule differs depending on whether a pseudo is assigned
to data register or address register. On that architecture at least 
it is better for something that knows data flow to "decide" that a pseudo 
should live in an address register (as that is how it is used next) and then 
schedule can arrange things correctly, then you have acurate lifetimes. 
"Our" compiler also moves the user's variable from one register to another 
during its life so that it can live in a data register if multiplied, and 
an address/index register when used as such. I attempted to mimic this in 
gcc port by creating new psuedos at the "emit" stage. But existing gcc code 
at the time "helpfully" collapsed them back, and then reload had to emit 
lots of reg/reg moves to get them in the right classes to meet the constraints.

-- 
Nick Ing-Simmons <nik@tiuk.ti.com>
Via, but not speaking for: Texas Instruments Ltd.