Re: Graph colouring and local register allocation

George Neuner a icrit :
>
>
> My point was that register allocation for ILP is not, as Sid Touati
> seemed to be claiming, a fundamentally different problem from
> allocating for a sequential processor. There is some additional
> effort to iterate scheduling and allocation to find a good balance,
> but existing methods are up to that task already (whether existing
> compilers do as well as they could using them is a different
> discussion).
>


I am sorry if I was not clear enough. I try to provide a better message
below.


The problem of register allocation if you consider sequential codes is
fundamentally different from the case of ILP codes. Indeed, register
allocation on sequential codes tries to minimize the number of required
registers. This is the main objective (since it minimizes spill code as
side effect). Such objective can be solved by a classical interference
graph coloring, as initially presented by Chaitin, revisited recently by
Alain Darte (by the way, I suggest the community to study the recent
results of Alain Darte on this topic, since he revisited this old
problem and his team proveed many excellent new results). In ILP codes,
you should not only minimise the register need, but you should also take
care of critical path. In reality, you can just tackle the problem of
minimizing the critical path without exceeding the number of available
registers. This new constraints produces a new mathematical problem,
which is fundamentally different from just minimizing the register need.


For instance, I give one common example showing a fundamental difference
on register allocation on sequential and ILP codes. Let take a binary
tree, representing for example the DDG of an arithmetic expression. Then:
- the problem of register allocation on a sequential processor can be
solved optimally by Sethi Ullman algorithm, which is a well known
polynomial algorithm. While the general problem is NP-complete, the
problem is polynomial in case of binary trees.
- the problem of register allocation with critical path minimization on
ILP codes is NP-complete (see the paper of Gasperoni and Eisenbeis 1995
on this topic). This problem is NP-complete even for trees and chains.


As you can see, a well known polynomial register allocation problem in
sequential code becomes an NP-complete problem on ILP codes. Introducing
a new constraints (take care of critical path) in the register
allocation problem makes it distinct mathematically. Furthermore, the
spilling problem in ILP codes is different from the spilling problem in
sequential codes.


There are many other mathematical differences... To understand them, one
should read fundamental research papers in computer science, which use
formal reasoning and provide some mathematical results. If one relies on
ad-hoc heuristics to understand the problems, the understanding would
remain somehow superficial.


S.T.

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