Fri, 26 Oct 90 14:04:11 GMT

Related articles |
---|

Reg. Alloc. - Graph Coloring pkolte@cs.clemson.edu (1990-10-18) |

Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-18) |

Re: Reg. Alloc. - Graph Coloring hankd@ecn.purdue.edu (1990-10-19) |

Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-23) |

Re: Reg. Alloc. - Graph Coloring siritzky@apollo.hp.com (1990-10-25) |

Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-26) |

Re: Reg. Alloc. - Graph Coloring sasmkg@dev.sas.com (1990-11-02) |

Newsgroups: | comp.compilers |

From: | preston@titan.rice.edu (Preston Briggs) |

Keywords: | optimize, design |

Organization: | Rice University, Houston |

References: | <9010251440.AA25798@xuucp.ch.apollo.com> |

Date: | Fri, 26 Oct 90 14:04:11 GMT |

I wrote:

*>> I think you've probably understated Chaitin's contribution. He (and others)*

*>> built the first graph coloring register allocator. They also published the*

*>> first 2 papers describing such a beast. Chaitin was listed first in an*

*>> otherwise alphabetical author list and was the only author on the second*

*>> paper.*

and

In article <9010251440.AA25798@xuucp.ch.apollo.com> siritzky@apollo.hp.com (Brian Siritzky) writes:

*>The first reference I have found applying graph coloring to the register*

*>allocation problem is in the book "On Programming -- An Interim Report on the*

*>SETL Project" by Jack Schwartz, 1975. Chaitin's paper is 1982.*

*>On page 485 Schwartz gives the graph coloring algorithm for register *

*>allocation, attributing ("The first algorithm due to J. Cocke ...") it to*

*>Cocke.*

The 1st Chaitin paper appeared in 1981. John Cocke was a coauthor.

Ershov talked about finding opportunities for overlapping storage

using graph coloring (and other NP-Complete problems) long ago,

perhaps 1967. Janet Fabri did further work in this area.

Cocke and Schwartz talked about it some.

But Chaitin et al. built it. That means they worked out all the

gory details that made it practical and interesting.

I think that's a significant contribution.

--

Preston Briggs

preston@titan.rice.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.