Copy Elimination on Data Dependence Graphs

Florian Brandner, Quentin Colombet

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Register allocation recently regained much interest due to new decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination.
A common assumption of existing copy elimination approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs.

Original languageEnglish
Title of host publicationProceedings of the 27th Annual ACM Symposium on Applied Computing
PublisherAssociation for Computing Machinery
Publication date2012
Pages1916-1918
ISBN (Print)978-1-4503-0857-1
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event27th Annual ACM Symposium on Applied Computing (SAC 2012) - Riva del Garda, Italy
Duration: 26 Mar 201230 Mar 2012

Conference

Conference27th Annual ACM Symposium on Applied Computing (SAC 2012)
CountryItaly
CityRiva del Garda
Period26/03/201230/03/2012

Fingerprint Dive into the research topics of 'Copy Elimination on Data Dependence Graphs'. Together they form a unique fingerprint.

Cite this