Copy Elimination on Data Dependence Graphs

Florian Brandner, Quentin Colombet

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


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
ISBN (Print)978-1-4503-0857-1
Publication statusPublished - 2012
Externally publishedYes
Event27th Annual ACM Symposium on Applied Computing (SAC 2012) - Riva del Garda, Italy
Duration: 26 Mar 201230 Mar 2012


Conference27th Annual ACM Symposium on Applied Computing (SAC 2012)
CityRiva del Garda

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

Cite this