Register allocation by optimal graph coloring
(2003) Compiler Construction: 12th International Conference, CC 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003 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:
https://lup.lub.lu.se/record/309822
- author
- Andersson, Christian LU
- organization
- publishing date
- 2003
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 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
- conference location
- Warsaw, Poland
- conference dates
- 2003-04-07 - 2003-04-11
- external identifiers
-
- wos:000183068200003
- scopus:33644919201
- ISSN
- 1611-3349
- 0302-9743
- 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
- 2016-04-01 11:59:34
- date last changed
- 2024-01-08 04:15:22
@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 = {{1611-3349}},
language = {{eng}},
pages = {{33--45}},
publisher = {{Springer}},
title = {{Register allocation by optimal graph coloring}},
url = {{http://www.springerlink.com/content/abtmn0h7w3vpccy7/}},
volume = {{2622}},
year = {{2003}},
}