Tue, 04 Dec 2007 11:53:05 +0100

Related articles |
---|

[6 earlier articles] |

Re: Graph colouring and local register allocation Sid.Touati@uvsq.fr (Sid Touati) (2007-11-30) |

Re: Graph colouring and local register allocation gneuner2@comcast.net (George Neuner) (2007-12-01) |

Re: Graph colouring and local register allocation sjdutoit@gmail.com (sdt) (2007-12-01) |

Re: Graph colouring and local register allocation preston.briggs@gmail.com (preston.briggs@gmail.com) (2007-12-01) |

Re: Graph colouring and local register allocation gneuner2@/comcast.net (George Neuner) (2007-12-01) |

Re: Graph colouring and local register allocation pertti.kellomaki@tut.fi (=?ISO-8859-1?Q?Pertti_Kellom=E4ki?=) (2007-12-03) |

Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-12-04) |

Re: Graph colouring and local register allocation torbenm@app-1.diku.dk (2007-12-05) |

Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-12-08) |

Re: Graph colouring and local register allocation anton@mips.complang.tuwien.ac.at (2007-12-09) |

Re: Graph colouring and local register allocation gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-12-09) |

Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-12-10) |

From: | Sid Touati <SidTouati@inria.fr> |

Newsgroups: | comp.compilers |

Date: | Tue, 04 Dec 2007 11:53:05 +0100 |

Organization: | I.N.R.I.A Rocquencourt |

References: | 07-10-103 07-11-019 07-11-063 07-11-091 07-12-003 07-12-005 07-12-007 |

Keywords: | registers, parallel |

Posted-Date: | 04 Dec 2007 22:02:01 EST |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.