Re: Coalescing register allocators

rusa@microsoft.com (Bjarne 'Rusa' Steensgaard) writes:
>One weakness of Chaitin's approach is that it requires the instructions to
>be scheduled, before it can be applied. We would like to combine the
>scheduling and the register allocation phase.


There are some recent papers in the area. One is


    author="Schlomit S. Pinter",
    title="Register Allocation with Instruction Scheduling: A New Approach",
    pages="248--257",
    journal=sigplan,
    year=1993,
    month=jun,
    volume=28,
    number=6,
    note=pldi93


>To make the job easier for the combined scheduling/allocation phase,
>I want to perform register *assignment* (as the term is used in the
>red dragon book) before that phase, coalescing virtual register names
>whenever beneficial.


The question of coalescing whenever beneficial is tough. Generally, all
coalesces help because each will eliminate at least one copy. Further,
coalescing can sometimes make it easier to color. For example, when
coalescing rA and rB into rAB, we reduce the degree of all names that
interfere with both rA and rB. On the other hand, the degree of rAB may
be significantly higher than either rA or rB.


Chaitin's approach is optimistic: he performs every coalesce he can find,
trusting that there will be enough registers to color without excessive
spilling. I suggested a couple of conservative approaches -- coalescing
when we can be sure that it won't cause any new spills. While you might
find a better heuristic, I don't think you'll be able to coalesce
optimally, in polynomial time; however, I've never proved it.


Preston Briggs
[Anyone have rules of thumb about what approaches make sense for what sizes
of register sets. I'd expect the best techniques for a Pentium which
still only has six general registers would be quite different from those
for a system with 16 or 31 of them. -John]
--

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