Copy Elimination on Data Dependence Graphs

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

Without internal affiliation

  • Author: Brandner, Florian

    Universite Claude Bernard Lyon 1

  • Author: Colombet, Quentin

    Universite Claude Bernard Lyon 1, France

View graph of relations

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
StatePublished - 2012
Externally publishedYes
Event27th Annual ACM Symposium on Applied Computing (SAC 2012) - Riva del Garda, Italy


Conference27th Annual ACM Symposium on Applied Computing (SAC 2012)
CityRiva del Garda
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 51218603