Advanced

Register allocation by optimal graph coloring

Andersson, Christian LU (2003) Compiler Construction: 12th International Conference, CC 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003 In Lecture Notes in Computer Science (Compiler Construction) 2622. p.33-45
Abstract
We here present new insights of properties of real-life interference graphs emerging in register allocation. These new insights imply good hopes for a possibility of improving the coloring approach towards optimal solutions. The conclusions axe based on measurements of nearly 28,000 real instances of such interference graphs. All the instances explored are determined to possess the so-called 1-perfectness property, a fact that seems to make them easy to color optimally. The exact algorithms presented not only produce better solutions than the traditional heuristic methods, but also, indeed, seem to perform surprisingly fast, according to the measurements on our implementations.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science (Compiler Construction)
volume
2622
pages
33 - 45
publisher
Springer
conference name
Compiler Construction: 12th International Conference, CC 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003
external identifiers
  • wos:000183068200003
  • scopus:33644919201
ISSN
0302-9743
1611-3349
language
English
LU publication?
yes
id
1726004c-9165-4972-ae19-ef264e2a2191 (old id 309822)
alternative location
http://www.springerlink.com/content/abtmn0h7w3vpccy7/
date added to LUP
2007-08-22 11:12:30
date last changed
2018-05-29 10:10:12
@inproceedings{1726004c-9165-4972-ae19-ef264e2a2191,
  abstract     = {We here present new insights of properties of real-life interference graphs emerging in register allocation. These new insights imply good hopes for a possibility of improving the coloring approach towards optimal solutions. The conclusions axe based on measurements of nearly 28,000 real instances of such interference graphs. All the instances explored are determined to possess the so-called 1-perfectness property, a fact that seems to make them easy to color optimally. The exact algorithms presented not only produce better solutions than the traditional heuristic methods, but also, indeed, seem to perform surprisingly fast, according to the measurements on our implementations.},
  author       = {Andersson, Christian},
  booktitle    = {Lecture Notes in Computer Science (Compiler Construction)},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {33--45},
  publisher    = {Springer},
  title        = {Register allocation by optimal graph coloring},
  volume       = {2622},
  year         = {2003},
}