Elimination of Parallel Copies using Code Motion on Data Dependence Graphs

Florian Brandner, Quentin Colombet

    Research output: Contribution to journalJournal articleResearchpeer-review


    Register allocation regained much interest in recent years due to the development of decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination.

    Traditional approaches to copy elimination during register allocation are based on interference graphs and register coalescing. Variables are represented as nodes in a graph, which are coalesced, if they can be assigned the same register. However, decoupled approaches strive to avoid interference graphs and thus often resort to local recoloring.

    A common assumption of existing coalescing and recoloring 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
    JournalComputer Languages, Systems and Structures
    Issue number1
    Pages (from-to)25–47
    Publication statusPublished - 2013


    • Parallel CopyMotion
    • Data dependencegraph
    • Register allocation
    • Register coalescing
    • Copy elimination


    Dive into the research topics of 'Elimination of Parallel Copies using Code Motion on Data Dependence Graphs'. Together they form a unique fingerprint.

    Cite this