Re: Graph colouring and local register allocation

> >> So what do "modern" compilers use?
> >
> >The term "modern" has no sense. It's marketing. Maybe you mean "actual".


He probably means the same thing you meant when you wrote "modern".


> > Most of the compilers use old register
> >allocation techniques, designed for sequential processors. When ILP
> >came, few of them used advanced techniques based on strong theoretical
> >research results[...]


> Frankly, I don't see what impact ILP has on register allocation [...]


If we schedule to minimize register pressure, then allocate, then try
to reschedule to maxmize ILP, we'll have a hard time. The initial
schedule and allocation will leave us very little "room to work". On
the other hand, if we initially schedule for maximum ILP, then
allocation will require more registers, perhaps causing spill code.


For an easy example, consider finding the sum of 4 integers.
If we write the code like this


        r = A
        r += B
        r += C
        r += D
        SUM = r


versus


        r1 = A r2 = C
        r1 += B r2 += D
        r1 += C
        SUM = r1


(where I've written in this 2-column form to make the ILP obvious).
The 1st approach requires only a single register but will take at
least 5 ticks.
The 2nd approach requires 2 registers but can run a bit faster.


Google up "Register Allocation with Instruction Scheduling: A New
Approach" by Schlomit Pinter. That and the papers that cite it will
get you off to a good start.


Preston

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